李彥廣

（商洛學(xué)院數(shù)學(xué)與計(jì)算機(jī)應(yīng)用學(xué)院，陜西商洛726000）

基于Spark+MLlib分布式學(xué)習(xí)算法的研究

李彥廣

（商洛學(xué)院數(shù)學(xué)與計(jì)算機(jī)應(yīng)用學(xué)院，陜西商洛726000）

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

Spark；MLlib；標(biāo)簽系統(tǒng)；構(gòu)建

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

1 Spark+MLlib平臺(tái)

1.1 Spark

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

1.2 MLib

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

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

2 分類(lèi)和回歸的數(shù)學(xué)表示

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

定義2機(jī)器學(xué)習(xí)問(wèn)題可以表示成數(shù)學(xué)上一個(gè)最優(yōu)化問(wèn)題目標(biāo)函數(shù)，其中向量集合Xi∈Rd是訓(xùn)練樣本，n表示訓(xùn)練樣本的個(gè)數(shù)，yi∈R是樣本所屬類(lèi)的標(biāo)簽。

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

3 分類(lèi)和回歸問(wèn)題的設(shè)計(jì)

3.1 MLlib的分類(lèi)和回歸

機(jī)器學(xué)習(xí)問(wèn)題的結(jié)果有兩種類(lèi)型，結(jié)果連續(xù)的是回歸問(wèn)題，結(jié)果離散的是分類(lèi)問(wèn)題。

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

支持向量機(jī)SVM算法使用式(1)作為損失函數(shù)，使用式(2)為正則化項(xiàng)，基于式(1)中wTx的計(jì)算結(jié)果做分類(lèi)預(yù)測(cè)。如果wTx≥0輸出是正例，否則是負(fù)例。

邏輯回歸LR算法使用式(4)作為損失函數(shù)，使用式(5)進(jìn)行預(yù)測(cè)。默認(rèn)情況下，如果log it(wT)>0.5，結(jié)果是正例，否則是負(fù)例。在MLlib中實(shí)現(xiàn)這個(gè)算法的類(lèi)是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對(duì)于異常非常敏感，所以在實(shí)際應(yīng)用時(shí)候、推薦使用帶有正規(guī)化的回歸。MLlib中實(shí)現(xiàn)這三種方法的類(lèi)分別是LogisticRegressionWithSGD、RidgeRegression WithSGD和LassoWithSGD。

3.2 分類(lèi)效果的評(píng)價(jià)

通過(guò)訓(xùn)練集把模型訓(xùn)練出來(lái)之后就需要放在測(cè)試機(jī)上評(píng)價(jià)這個(gè)分類(lèi)模型的好壞[7]。在分類(lèi)問(wèn)題中常用的評(píng)價(jià)指標(biāo)有Precision、recall、F-measure、ROC（Receiver Operating Characteristic）、Precision-recall曲線和AUC（area under the curves）。通常ROC是用來(lái)比較模型好壞的，而Precision、recall和F-measure等是用來(lái)決定Threshold的。這些評(píng)價(jià)指標(biāo)在MLlib中都支持。

4 分類(lèi)的算法描述

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

4.1 SGD算法

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

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

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

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

4.2 L-BFGS算法

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

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

5 標(biāo)簽系統(tǒng)的實(shí)現(xiàn)關(guān)鍵代碼

按照分類(lèi)問(wèn)題的實(shí)現(xiàn)方法，給出了基于Spark0.9平臺(tái)的關(guān)鍵代碼。

在每一輪迭代過(guò)程中都會(huì)產(chǎn)生一個(gè)新的weights矩陣，然后下一輪迭代中會(huì)使用這個(gè)變量，但這個(gè)weights變量會(huì)比較大，在任務(wù)中一般有幾十個(gè)MB到幾百M(fèi)B，對(duì)于相對(duì)比較大的變量建議使用廣播變量，例如可以這樣寫(xiě)：

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

6 結(jié)語(yǔ)

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

[1]嚴(yán)霄鳳,張德馨.大數(shù)據(jù)研究[J].計(jì)算機(jī)技術(shù)與發(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的機(jī)器學(xué)習(xí)平臺(tái)設(shè)計(jì)與實(shí)現(xiàn)[D].廈門(mén)：廈門(mén)大學(xué),2014.

[4]淘寶技術(shù)部.Spark 0.9.1 MLLib機(jī)器學(xué)習(xí)庫(kù)簡(jiǎn)介[EB/OL].http：//www.tuicool.com/articles/aymuien,2014-05-10.

[5]吳韶鴻.大數(shù)據(jù)開(kāi)源技術(shù)發(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平臺(tái)的網(wǎng)絡(luò)安全性研究[J].商洛學(xué)院學(xué)報(bào),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]李彥廣.網(wǎng)絡(luò)攻防仿真系統(tǒng)終端子系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(jī)與現(xiàn)代化,2014(3)：169-172.

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

（責(zé)任編輯：李堆淑）

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

商洛學(xué)院科研基金項(xiàng)目（09SKY007）

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