李 辉，黄祖源，田 园

（云南电网有限责任公司信息中心，云南昆明 650011）

大数据时代已经来临。机器学习和数据分析是将大数据转换成有用知识的关键技术，并且有研究表明，在很多情况下，处理的数据规模越大，机器学习模型的效果会越好。因此，机器学习是大数据智能化分析处理应用中的重要手段。在大数据背景下，计算数据量级已升至TB 级或PB 级，给传统机器学习带来了挑战和机遇。机器学习算法本身含有大量的选代计算，非常适用干并行化。目前，对大数据机器学习并行化研究已成为应对大数据应用需求的热点研究方向。

传统机器学习算法，由于理论设计局限，大部分都是串行算法，只能运行于单机环境，在面对大数据量时表现不佳，随着并行化技术的发展，在面对海量数据时，如何提升算法的执行效率，就成为学术界和行业研究的热点。文章提出的基于集成学习及ADMM 的分布式并行挖掘算法，有效地解决了单机算法无法并行化的问题，在不改变原有算法理论的基础上，使得原有的单机算法更好地适配分布式的计算模式。

稀疏信息处理近来受到研究与应用界的广泛关注，针对稀疏求解，文章提出一种基于L1/2正则化稀疏问题求解的方法，包括L1/2稀疏迭代分类算法、L1/2稀疏迭代回归算法和L1/2稀疏迭代时间序列算法。基于L1/2正则化的稀疏迭代算法是求解基于损失函数与L1/2范数（正则项）的极小化非凸优化问题，以期望得到问题的稀疏解，相比于L1正则化算法，L1/2正则化的解更稀疏。

文章介绍了ADMM 算法的实现原理，在ADMM并行化算法的研究基础上，对L1/2稀疏迭代算法进行了并行化改造。

1 ADMM

交替方向乘子法（Alternating Direction Method of Multipliers，ADMM）是一种解决可分解凸优化问题的简单方法。它可以将原问题的目标函数等价地分解成若干个可求解的子问题，然后并行求解每一个子问题，最后协调子问题的解得到原问题的全局解。ADMM 被广泛地应用在信号处理、图像处理、机器学习、工程计算等领域，具有收敛速度快，收敛性能好的优势。

ADMM 通常用于解决存在两个优化变量的只含等式约束的优化类问题，其一般形式为：

式中，x∈Rn，z∈Rm为优化变量；A∈Rp×n，B∈Rp×m，C∈Rp；f和g为凸函数。

为解决此类凸优化问题，定义增广拉格朗日函数：

算法流程如下：

每一步只更新一个变量而固定另外两个变量，如此交替重复更新。即，对于k=1，2，3，…，重复如下步骤：

ADMM 算法提供了一个将多优化变量问题转化为单优化变量问题的转化方式（交替方向），并未涉及具体的下降方法，其中关于x和z的更新过程需要结合具体的下降类算法，如梯度下降算法等。

上面这个式子被称为是ADMM 的缩放形式。

相应地，更新步骤变为：

2 基于ADMM的L1/2稀疏迭代分布式算法

稀疏信息处理近来受到研究与应用界的广泛关注。L1/2正则化是一种处理稀疏问题的方法。基于L1/2正则化的稀疏迭代算法是求解基于损失函数与L1/2范数的罚函数（正则项）的和的极小化非凸优化问题，以期望得到问题的稀疏解。相比于L1正则化算法，L1/2正则化的解更稀疏。求解L1/2正则化的算法有：重赋权迭代算法、soft 阈值迭代算法（软门限阈值迭代算法）。

算法可采用分类和回归两类损失函数，实现对分类和回归问题的处理。算法将这一极小化目标的过程通过解决L1/2的软门限阈值迭代算法实现。

具体实现思路如下：

求解采用重赋权迭代算法：

对于凸的可拆解的算法，可采用ADMM，将全局问题分解为多个较小、较容易求解的局部子问题，并通过协调子问题的解得到全局问题的解。文章中自主创新的L1/2稀疏迭代分类算法、L1/2稀疏迭代回归算法、L1/2稀疏迭代时间序列算法均采用基于ADMM 的分布式并行思路实现。其基本思路如下。

若优化问题为：

式中，x∈Rd，A∈Rp×d，y∈Rp，λ>0，可将其转换为ADMM 的Consensus 型优化问题：

其可以直接采用分布式方式进行计算，流程如图1所示。

图1 基于ADMM的分布式并行挖掘算法

3 应用实例

基于ADMM 的L1/2 稀疏迭代分布式算法是基于极小化损失函数与关于稀疏解L1/2范数正则项的高效稀疏算法，L1/2 正则化与L2 正则化相比更容易求解，而与L1正则化相比能产生更稀疏的解，说明L1/2 正则化具有广泛且重要的应用价值。基于ADMM 的L1/2稀疏迭代分布式算法具有高效，精确的优点。

电力数据具有实时性、真实性、覆盖性等特征，能够客观且真实的反映社会经济变革过程中行业的发展现状及其趋势，可助力政府部门实时监测行业动态，准确把握政策实施效果。电力行业中存在着大量的分类场景和回归场景中，并且数据多且杂。

分类场景：在传统用户用电行为分析和异常用户识别定位过程中，主要是通过相关人员的经验、业务规则以及各个专项模型等方法实现异常用户识别。通常业务人员会结合相关业务经验知识，搭建多维行业用户行为特性特征指标体系，建立智能化、自动化嫌疑用户智能识别模型，用于异常用电用户快速定位，包括反窃电、台区线损识别以及企业信用评价等应用场景。

回归场景：业务人员基于电力客户基本信息、长期的用电记录、缴费情况、缴费能力等数据，对各类数据进行统计分析，构建售电量预测模型。

在上述电力相关的分类场景和回归场景中，在建模过程中运用基于ADMM 的L1/2稀疏迭代分布式算法建立相关模型，能取得好的结果以及效果。

4 结束语

在机器学习特定的应用中，算法的空间复杂度和时间复杂度，或者说算法的效率是和算法的准确率同样重要的问题。传统的机器学习算法大多是串行的，在数据量、数据维度不断增长的情况下，单机的存储容量和运行时长都是无法忍受的。在这种情况下，考虑将算法并行化是一个非常自然的想法。通过基于ADMM 并行化方法的研究，对L1/2稀疏迭代算法进行并行化改造。通过实验可以发现基于ADMM 的L1/2稀疏迭代分布式算法的执行效率极大提升，特别是在大数据量的情况下。基于ADMM 的L1/2稀疏迭代分布式算法可以应用于不同的场景中，包括分类以及回归等业务场景中。