李 輝，黃祖源，田 園

（云南電網(wǎng)有限責(zé)任公司信息中心，云南昆明 650011）

大數(shù)據(jù)時代已經(jīng)來臨。機器學(xué)習(xí)和數(shù)據(jù)分析是將大數(shù)據(jù)轉(zhuǎn)換成有用知識的關(guān)鍵技術(shù)，并且有研究表明，在很多情況下，處理的數(shù)據(jù)規(guī)模越大，機器學(xué)習(xí)模型的效果會越好。因此，機器學(xué)習(xí)是大數(shù)據(jù)智能化分析處理應(yīng)用中的重要手段。在大數(shù)據(jù)背景下，計算數(shù)據(jù)量級已升至TB 級或PB 級，給傳統(tǒng)機器學(xué)習(xí)帶來了挑戰(zhàn)和機遇。機器學(xué)習(xí)算法本身含有大量的選代計算，非常適用干并行化。目前，對大數(shù)據(jù)機器學(xué)習(xí)并行化研究已成為應(yīng)對大數(shù)據(jù)應(yīng)用需求的熱點研究方向。

傳統(tǒng)機器學(xué)習(xí)算法，由于理論設(shè)計局限，大部分都是串行算法，只能運行于單機環(huán)境，在面對大數(shù)據(jù)量時表現(xiàn)不佳，隨著并行化技術(shù)的發(fā)展，在面對海量數(shù)據(jù)時，如何提升算法的執(zhí)行效率，就成為學(xué)術(shù)界和行業(yè)研究的熱點。文章提出的基于集成學(xué)習(xí)及ADMM 的分布式并行挖掘算法，有效地解決了單機算法無法并行化的問題，在不改變原有算法理論的基礎(chǔ)上，使得原有的單機算法更好地適配分布式的計算模式。

稀疏信息處理近來受到研究與應(yīng)用界的廣泛關(guān)注，針對稀疏求解，文章提出一種基于L1/2正則化稀疏問題求解的方法，包括L1/2稀疏迭代分類算法、L1/2稀疏迭代回歸算法和L1/2稀疏迭代時間序列算法。基于L1/2正則化的稀疏迭代算法是求解基于損失函數(shù)與L1/2范數(shù)（正則項）的極小化非凸優(yōu)化問題，以期望得到問題的稀疏解，相比于L1正則化算法，L1/2正則化的解更稀疏。

文章介紹了ADMM 算法的實現(xiàn)原理，在ADMM并行化算法的研究基礎(chǔ)上，對L1/2稀疏迭代算法進行了并行化改造。

1 ADMM

交替方向乘子法（Alternating Direction Method of Multipliers，ADMM）是一種解決可分解凸優(yōu)化問題的簡單方法。它可以將原問題的目標(biāo)函數(shù)等價地分解成若干個可求解的子問題，然后并行求解每一個子問題，最后協(xié)調(diào)子問題的解得到原問題的全局解。ADMM 被廣泛地應(yīng)用在信號處理、圖像處理、機器學(xué)習(xí)、工程計算等領(lǐng)域，具有收斂速度快，收斂性能好的優(yōu)勢。

ADMM 通常用于解決存在兩個優(yōu)化變量的只含等式約束的優(yōu)化類問題，其一般形式為：

式中，x∈Rn，z∈Rm為優(yōu)化變量；A∈Rp×n，B∈Rp×m，C∈Rp；f和g為凸函數(shù)。

為解決此類凸優(yōu)化問題，定義增廣拉格朗日函數(shù)：

算法流程如下：

每一步只更新一個變量而固定另外兩個變量，如此交替重復(fù)更新。即，對于k=1，2，3，…，重復(fù)如下步驟：

ADMM 算法提供了一個將多優(yōu)化變量問題轉(zhuǎn)化為單優(yōu)化變量問題的轉(zhuǎn)化方式（交替方向），并未涉及具體的下降方法，其中關(guān)于x和z的更新過程需要結(jié)合具體的下降類算法，如梯度下降算法等。

上面這個式子被稱為是ADMM 的縮放形式。

相應(yīng)地，更新步驟變?yōu)椋?/p>

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

稀疏信息處理近來受到研究與應(yīng)用界的廣泛關(guān)注。L1/2正則化是一種處理稀疏問題的方法?；贚1/2正則化的稀疏迭代算法是求解基于損失函數(shù)與L1/2范數(shù)的罰函數(shù)（正則項）的和的極小化非凸優(yōu)化問題，以期望得到問題的稀疏解。相比于L1正則化算法，L1/2正則化的解更稀疏。求解L1/2正則化的算法有：重賦權(quán)迭代算法、soft 閾值迭代算法（軟門限閾值迭代算法）。

算法可采用分類和回歸兩類損失函數(shù)，實現(xiàn)對分類和回歸問題的處理。算法將這一極小化目標(biāo)的過程通過解決L1/2的軟門限閾值迭代算法實現(xiàn)。

具體實現(xiàn)思路如下：

求解采用重賦權(quán)迭代算法：

對于凸的可拆解的算法，可采用ADMM，將全局問題分解為多個較小、較容易求解的局部子問題，并通過協(xié)調(diào)子問題的解得到全局問題的解。文章中自主創(chuàng)新的L1/2稀疏迭代分類算法、L1/2稀疏迭代回歸算法、L1/2稀疏迭代時間序列算法均采用基于ADMM 的分布式并行思路實現(xiàn)。其基本思路如下。

若優(yōu)化問題為：

式中，x∈Rd，A∈Rp×d，y∈Rp，λ>0，可將其轉(zhuǎn)換為ADMM 的Consensus 型優(yōu)化問題：

其可以直接采用分布式方式進行計算，流程如圖1所示。

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

3 應(yīng)用實例

基于ADMM 的L1/2 稀疏迭代分布式算法是基于極小化損失函數(shù)與關(guān)于稀疏解L1/2范數(shù)正則項的高效稀疏算法，L1/2 正則化與L2 正則化相比更容易求解，而與L1正則化相比能產(chǎn)生更稀疏的解，說明L1/2 正則化具有廣泛且重要的應(yīng)用價值。基于ADMM 的L1/2稀疏迭代分布式算法具有高效，精確的優(yōu)點。

電力數(shù)據(jù)具有實時性、真實性、覆蓋性等特征，能夠客觀且真實的反映社會經(jīng)濟變革過程中行業(yè)的發(fā)展現(xiàn)狀及其趨勢，可助力政府部門實時監(jiān)測行業(yè)動態(tài)，準(zhǔn)確把握政策實施效果。電力行業(yè)中存在著大量的分類場景和回歸場景中，并且數(shù)據(jù)多且雜。

分類場景：在傳統(tǒng)用戶用電行為分析和異常用戶識別定位過程中，主要是通過相關(guān)人員的經(jīng)驗、業(yè)務(wù)規(guī)則以及各個專項模型等方法實現(xiàn)異常用戶識別。通常業(yè)務(wù)人員會結(jié)合相關(guān)業(yè)務(wù)經(jīng)驗知識，搭建多維行業(yè)用戶行為特性特征指標(biāo)體系，建立智能化、自動化嫌疑用戶智能識別模型，用于異常用電用戶快速定位，包括反竊電、臺區(qū)線損識別以及企業(yè)信用評價等應(yīng)用場景。

回歸場景：業(yè)務(wù)人員基于電力客戶基本信息、長期的用電記錄、繳費情況、繳費能力等數(shù)據(jù)，對各類數(shù)據(jù)進行統(tǒng)計分析，構(gòu)建售電量預(yù)測模型。

在上述電力相關(guān)的分類場景和回歸場景中，在建模過程中運用基于ADMM 的L1/2稀疏迭代分布式算法建立相關(guān)模型，能取得好的結(jié)果以及效果。

4 結(jié)束語

在機器學(xué)習(xí)特定的應(yīng)用中，算法的空間復(fù)雜度和時間復(fù)雜度，或者說算法的效率是和算法的準(zhǔn)確率同樣重要的問題。傳統(tǒng)的機器學(xué)習(xí)算法大多是串行的，在數(shù)據(jù)量、數(shù)據(jù)維度不斷增長的情況下，單機的存儲容量和運行時長都是無法忍受的。在這種情況下，考慮將算法并行化是一個非常自然的想法。通過基于ADMM 并行化方法的研究，對L1/2稀疏迭代算法進行并行化改造。通過實驗可以發(fā)現(xiàn)基于ADMM 的L1/2稀疏迭代分布式算法的執(zhí)行效率極大提升，特別是在大數(shù)據(jù)量的情況下?；贏DMM 的L1/2稀疏迭代分布式算法可以應(yīng)用于不同的場景中，包括分類以及回歸等業(yè)務(wù)場景中。