基于Spark+MLlib分布式學習算法的研究

李彥廣

（商洛學院數(shù)學與計算機應用學院，陜西商洛726000）

基于Spark+MLlib分布式學習算法的研究

李彥廣

（商洛學院數(shù)學與計算機應用學院，陜西商洛726000）

電子商務服務的關鍵是用戶的需求，隨著電子商務業(yè)務的急速擴展，用戶數(shù)據(jù)量的海量增長，針對傳統(tǒng)的單機算法很難滿足業(yè)務需求的現(xiàn)狀，提出了基于Spark+MLlib的分布式學習算法，系統(tǒng)在實現(xiàn)過程中進行了分類和預測，并實現(xiàn)了用戶標簽系統(tǒng)。通過測試，新的算法明顯優(yōu)于單機算法。

Spark；MLlib；標簽系統(tǒng)；構建

對用戶需求的了解是電子商務企業(yè)服務好用戶的關鍵[1]。對用戶進行畫像是了解用戶的屬性和行為特征的最好途徑[2]。一些商業(yè)行為的背后，需要對海量數(shù)據(jù)進行分析，歸類用戶的各種屬性和行為特征，以便做分類和預測。機器學習是實現(xiàn)分類和預測的重要手段，然而，電子商務業(yè)蓬勃發(fā)展，數(shù)據(jù)量大規(guī)模增長，按文獻[1]所提到的傳統(tǒng)單機算法很難以滿足需求，文獻[2]所提到的梯度下降法非常費時。Spark的出現(xiàn)，便以多迭代、輕量級的框架設計，窄依賴流水化的計算模式擺脫了大量磁盤交換的桎梏[3]。MLlib是Spark對常用的機器學習算法的實現(xiàn)庫，同時包括相關的測試和數(shù)據(jù)生成器[4]。鑒于Spark及MLlib的特性，本文提出了基于Spark+MLlib的分布式機器學習算法，主要描述使用Spark+MLlib進行分類與預測的原理、實現(xiàn)方法。

1 Spark+MLlib平臺

1.1 Spark

Spark是一個基于內存的分布式計算系統(tǒng)，是由UC Berkeley AMPLab實驗室于2009年開發(fā)的開源數(shù)據(jù)分析集群計算框架，是BDAS (Berkeley Data Analytics Stack)中的核心項目,被設計用來完成交互式的數(shù)據(jù)分析任務[4]。Spark起源于Hadoop開源社區(qū)，基于HDFS構建系統(tǒng)，但相比Hadoop，它在性能上比Hadoop要高100倍，計算過程能兼容MapReduce，但并不局限于兩個階段式MapReduce范型[5]。

1.2 MLib

MLlib是建立在Apache Spark上的分布式機器學習庫，在機器學習算法上比基于Mapreduce實現(xiàn)的分布式算法有100倍的性能提升[5]。MLlib支持分類、回歸、聚類、協(xié)同過濾、降維等主要機器學習算法。底層數(shù)值優(yōu)化算法主要包括SGD和L-BFGS(Limited-memory BFGS)。

MLlib的線性代數(shù)計算使用了Breeze包，這個包依賴于netlib-java和jblas，都需要Fortran運行環(huán)境。最近發(fā)布的Spark1.0中已經增加了對稀疏矩陣的支持，這給MLlib的使用者帶來了很大便利[6]。

2 分類和回歸的數(shù)學表示

定義1機器學習問題可以表示為min w∈Rdf(w)，表示包含d維變量w的凸函數(shù)f的最小值，其中w就是機器學習中的權重矩陣。

定義2機器學習問題可以表示成數(shù)學上一個最優(yōu)化問題目標函數(shù)，其中向量集合Xi∈Rd是訓練樣本，n表示訓練樣本的個數(shù)，yi∈R是樣本所屬類的標簽。

在定義2中，目標函數(shù)f主要是由損失函數(shù)L(w;x,y)和正則化項R(w)組成,λ的作用是調節(jié)損失函數(shù)和模型復雜度的權重。

3 分類和回歸問題的設計

3.1 MLlib的分類和回歸

機器學習問題的結果有兩種類型，結果連續(xù)的是回歸問題，結果離散的是分類問題。

MLlib主要支持的分類算法有支持向量機（SVM，Linear support Vector mschine）、邏輯回歸（LR，Logistic regression）、決策樹（DT，Decision Tree）和樸素貝葉斯（NB，Naive Bayes）。

支持向量機SVM算法使用式(1)作為損失函數(shù)，使用式(2)為正則化項，基于式(1)中wTx的計算結果做分類預測。如果wTx≥0輸出是正例，否則是負例。

邏輯回歸LR算法使用式(4)作為損失函數(shù)，使用式(5)進行預測。默認情況下，如果log it(wT)>0.5，結果是正例，否則是負例。在MLlib中實現(xiàn)這個算法的類是LogisticRegressionWithSGD。

MLlib主要支持的回歸算法有Linear least squares、Lasso和ridge regression，這一系列方法都是線性回歸。Linear least squares的損失函數(shù)是squares loss，根據(jù)使用的正則化方法不同，又分為ordinary least squares和Linear least squares，Linear least squares不使用任何正則化；ridge regression使用式(2)正則化；Lasso regression使用式(3)正則化。Squared loss對于異常非常敏感，所以在實際應用時候、推薦使用帶有正規(guī)化的回歸。MLlib中實現(xiàn)這三種方法的類分別是LogisticRegressionWithSGD、RidgeRegression WithSGD和LassoWithSGD。

3.2 分類效果的評價

通過訓練集把模型訓練出來之后就需要放在測試機上評價這個分類模型的好壞[7]。在分類問題中常用的評價指標有Precision、recall、F-measure、ROC（Receiver Operating Characteristic）、Precision-recall曲線和AUC（area under the curves）。通常ROC是用來比較模型好壞的，而Precision、recall和F-measure等是用來決定Threshold的。這些評價指標在MLlib中都支持。

4 分類的算法描述

在機器學習中，很多問題都可以歸結為參數(shù)優(yōu)化問題，即找到使目標函數(shù)最大或者最小的參數(shù)[8]。在MLlib里求解minw∈Rdf(w)這樣的最優(yōu)化的問題主要的方法有SGD算法和L-BFGS算法。

4.1 SGD算法

在梯度下降最快的那個方向尋找函數(shù)極值，不斷迭代就可以尋找到最大值或者最小值[9]。當目標函數(shù)不可微時使用次梯度尋找極值，這樣的一階優(yōu)化方法也非常適合大規(guī)模分布式計算。梯度下降法在計算每個點的梯度或者次梯度過程中需要使用全部的訓練數(shù)據(jù)，非常費時，所以在實際使用中更常見的是隨機梯度下降法（SGD，Stochastic Gradient Descent），算法描述如下：

在i∈[1,…,n]選擇一個隨機樣本點，得到目標函數(shù)f(w)的一個隨機梯度，表示為f'w，I：=L'W,I+ λR'w，其中L'w,i∈Rd是第i個樣本點決定的損失函數(shù)的梯度，表示為。其中R'w的梯度是正則化R(w)的結果，表示為，而且R'w和i沒有相關性。f'w，I表示起始目標函數(shù)f的一個梯度，表示為。這樣運行SGD算法可以用式(6)表示。

在式(6)中，γ表示第t輪迭代中步長值，與迭代次數(shù)成反比，其數(shù)值可以用式(7)計算得到。在式(7)中，t代表迭代的輪次，s代表初始步長。

SGD算法是MLlib中的一種通用優(yōu)化方法，在各種線性模型的訓練中被廣泛運用。MLlib中通過Mini-Batch Gradient Descent算法實現(xiàn)隨機梯度下降。在每一輪的迭代計算梯度時，通過MiniBatchFraction參數(shù)指定用于計算梯度或次梯度的樣本比例，然后取平均值作為該點的隨機梯度。如果MiniBatchFraction=1，那么這個實現(xiàn)就變成了標準的梯度下降；如果MiniBatchFraction非常小，在GradientDescent.runMiniBatchSGD方法，已通過類似LogisticRegressionWithSGD的形式和模型包裝在一起了。

4.2 L-BFGS算法

L-BFGS算法是Quasi-Newton方法中的一種，其思路是用目標函數(shù)值和特征的變化量來近似Hessian矩陣[10]。L-BFGS算法的基本思想是只保存最近的m次迭代信息，從而大大降低數(shù)據(jù)存儲空間。

L-BFGS在MLlib中目前還只是一種優(yōu)化方法，還沒有和模型包裝在一起，如果使用這個優(yōu)化方法需要用戶顯示調用LBFGS.runLBFGS方法。

5 標簽系統(tǒng)的實現(xiàn)關鍵代碼

按照分類問題的實現(xiàn)方法，給出了基于Spark0.9平臺的關鍵代碼。

在每一輪迭代過程中都會產生一個新的weights矩陣，然后下一輪迭代中會使用這個變量，但這個weights變量會比較大，在任務中一般有幾十個MB到幾百MB，對于相對比較大的變量建議使用廣播變量，例如可以這樣寫：

由于模型大多比較復雜，百萬級別的數(shù)據(jù)和百萬級別的維度，產生的模型權重矩陣weights會非常大。這個權重矩陣weights在每次迭代計算之后都要更新，更新后會重新廣播一份新的數(shù)據(jù)到所有worker節(jié)點。由于內存計算的速度非?？欤瑱嘀鼐仃噖eights生成的速度非常快，worker節(jié)點的內存很快就會填滿。即使worker節(jié)點會將之前的數(shù)據(jù)dump到磁盤，但磁盤I/O的速度還是不如權重矩陣生成的速度快，這樣的結果就是worker節(jié)點OOM。解決這個問題最簡單的思路就是增加內存，但這個不是長久之計。令人欣喜的是在最新的Spark 1.0中看到了可以手動銷毀過時的廣播變量接口。

6 結語

針對目前電子商務的海量數(shù)據(jù)，單機算法很難滿足用戶的服務需求的缺點，本文深入分析了機器學習的分類和回歸問題，給出了基于Spark+MLlib平臺的機器學習數(shù)學模型，并在Spark0.9給出了核心代碼的實現(xiàn)。但是分布式機器算法也受到環(huán)境的限制，主要存在兩方面，其一是Spark的計算和存儲都在內存中，而且是分布在不同的worker節(jié)點上，所以要保證機器內存足夠大。其二是Spark雖然支持Python和Java語言，但在實際中還是使用了原生的Scala開發(fā)，而且解決的又是數(shù)學味道比較濃的機器學習問題，因此需要對模型的原理和實現(xiàn)有比較深入的了解才能得到正確的結果。總而言之，使用Spark+MLlib做機器學習是一項處于初級階段，是未來發(fā)展的一個方向，隨著機器軟硬件的發(fā)展和模型的優(yōu)化，目前的一些瓶頸問題會慢慢突破。

[1]嚴霄鳳,張德馨.大數(shù)據(jù)研究[J].計算機技術與發(fā)展, 2013,23(4)：168-172.

[2]Ghemawat S,Gobioff H,Leung S T.The Google file system[C].ACM SIGOPS Operating Systems Review, 2003,37(5)：29-43.

[3]唐振坤.基于Spark的機器學習平臺設計與實現(xiàn)[D].廈門：廈門大學,2014.

[4]淘寶技術部.Spark 0.9.1 MLLib機器學習庫簡介[EB/OL].http：//www.tuicool.com/articles/aymuien,2014-05-10.

[5]吳韶鴻.大數(shù)據(jù)開源技術發(fā)展研究[J].現(xiàn)代電信科技, 2014(8)：17-22.

[6]Xin R S,Rosen J,Zaharia M,et al.Shark：SQL and rich analytics at scale[C].Proceedings of the 2013 international conference on Management of data,2013：13-24.

[7]李彥廣.基于HTTP平臺的網絡安全性研究[J].商洛學院學報,2013,27(4)：59-62.

[8]Armbrust M,Fox A,Griffith R,et al.A view of cloud computing[J].Communications of the ACM,ACM, 2010,53(4)：50-58.

[9]Weng J,Lim E P,Jiang J,et al.Twitterrank：finding topicsensitive influential twitterers[C].Proceedings of the Third ACM International Conference on Web Search and data mining,2010：261-270.

[10]李彥廣.網絡攻防仿真系統(tǒng)終端子系統(tǒng)的設計與實現(xiàn)[J].計算機與現(xiàn)代化,2014(3)：169-172.

[11]李彥廣.基于PHP的Flash與MySQL數(shù)據(jù)庫通訊的實現(xiàn)[J].商洛學院學報,2013,27(6)：53-56.

（責任編輯：李堆淑）

Research on Distribution Learning Algorithm Based on Spark+MLlib

LI Yan-guang
（College of Mathematics and Computer Application,Shangluo University,Shangluo726000,Shaanxi）

The key of E-commerce service is the users'demands.With the rapid expansion of E-commerce business,and the enormously increasing of the users'data amount,due to the fact that traditional single algorithm hardly meets the current business requirements,based on Spark+MLlib,the distributed learning algorithm is proposed,the system is able to carry on classification and prediction in the process of implementation,as well as the tag system.According to the testing,the new algorithm is obviously superior to single algorithm.

Spark;MLlib;tag system;construction

TP392

A

1674-0033（2015）02-0016-04

10.13440/j.slxy.1674-0033.2015.02.005

2015-01-16

商洛學院科研基金項目（09SKY007）

李彥廣，男，陜西鎮(zhèn)安人，碩士，講師