基于Spark平臺的ALS加速算法研究

賈曉芳,桑國明,祁文凱

(大連海事大學(xué) 信息科學(xué)技術(shù)學(xué)院,遼寧 大連 116026)

0 概述

在互聯(lián)網(wǎng)時(shí)代,海量規(guī)模的數(shù)據(jù)信息雖然能夠滿足用戶的多樣化需求,卻難以讓用戶在搜索時(shí)直接獲取目標(biāo)信息,信息處理技術(shù)的性能具有很大的提升空間。國際數(shù)據(jù)集團(tuán)(IDC)2012年的報(bào)告顯示,預(yù)計(jì)2020年的全球數(shù)據(jù)總量將達(dá)到35.2 ZB,是2011年的22倍[1]。從信息匱乏到信息過載[2-3],數(shù)據(jù)信息量產(chǎn)生巨大改變,但用戶對信息的使用效率并未大幅提高。在這樣的大數(shù)據(jù)背景下,推薦系統(tǒng)[4-5]應(yīng)運(yùn)而生,其根據(jù)用戶潛在需求和興趣來提供個(gè)性化的推薦服務(wù)。文獻(xiàn)[6]中的郵件過濾系統(tǒng)被認(rèn)為是互聯(lián)網(wǎng)時(shí)代較早提出并被廣泛應(yīng)用的協(xié)同過濾系統(tǒng)。協(xié)同過濾推薦系統(tǒng)[7-8]可以盡可能地滿足用戶的需求,產(chǎn)生與用戶喜好相關(guān)且數(shù)量有限的物品推薦列表。Amazon、NetFlix、淘寶等眾多國內(nèi)外知名網(wǎng)站中的推薦服務(wù)皆依賴協(xié)同過濾推薦系統(tǒng),其中,用戶和物品種類的數(shù)量相當(dāng)龐大,這對協(xié)同過濾推薦系統(tǒng)的準(zhǔn)確性、執(zhí)行效率和排名精度都有非常高的要求。

協(xié)同過濾推薦算法[9]是一種典型的大數(shù)據(jù)挖掘算法,其基于用戶或物品的相似性來進(jìn)行推薦。盡管協(xié)同過濾推薦算法的應(yīng)用使推薦系統(tǒng)獲得了用戶的認(rèn)可,但稀疏性高、執(zhí)行效率與排名精度低等問題依然存在。為此,研究人員提出一類高效的基于模型的協(xié)同過濾算法,其中,基于交替最小二乘(Alternating Least Squares,ALS)[10]的矩陣分解(Matrix Factorization,MF)模型[11]可實(shí)現(xiàn)并行計(jì)算,該特性使其在速度方面具有明顯優(yōu)勢,但是,該模型存在數(shù)據(jù)加載時(shí)間長、矩陣分解與迭代收斂慢等問題。國內(nèi)外學(xué)者先后圍繞上述問題進(jìn)行了優(yōu)化,其中,快速矩陣分解模型IALS[12]、LS-WR、NALS-WR[13]、ALS++[14]等改進(jìn)優(yōu)化方法的側(cè)重點(diǎn)在于縮短數(shù)據(jù)加載與矩陣分解的時(shí)間以及改變ALS預(yù)測模型等,但對于ALS迭代收斂慢的問題研究較少。

本文提出一種在ALS中融入非線性共軛梯度(Nonlinear Conjugate Gradient,NCG)的算法ALS-NCG[15],以加速ALS算法的收斂,提高執(zhí)行效率和排名精度。

1 基于矩陣分解的ALS算法

MF算法具有伸縮性好、靈活性高的特點(diǎn)[16]。在Netflix Prize算法比賽中,文獻(xiàn)[17]提出了基于ALS的協(xié)同過濾算法,其能很好地解決矩陣稀疏性問題。

1.1 ALS算法

ALS算法利用迭代求解一系列最小二乘的回歸問題。對于用戶-項(xiàng)目評分矩陣R,找到一個(gè)低秩矩陣R′來逼近原始數(shù)據(jù)評分矩陣R,完整過程如下:

R≈R′=UVT

(1)

損失函數(shù)定義為:

(2)

其中,L表示損失函數(shù)。

為防止過擬合,對式(2)進(jìn)行正則化處理,得到優(yōu)化式(3):

(3)

其中,λ表示正則化參數(shù)。

(4)

其中,Ri.表示用戶i對項(xiàng)目的評分矩陣,Vui表示用戶i所評價(jià)過的項(xiàng)目涉及的特征向量所形成的特征矩陣,nui表示用戶i所評價(jià)的項(xiàng)目數(shù)量。同理,固定U后對Vi求導(dǎo),然后根據(jù)求導(dǎo)結(jié)果解出Vj.:

(5)

(6)

其中,R.j表示評分過項(xiàng)目j的用戶的評分向量,Umj表示評分過項(xiàng)目j的用戶的特征向量所組成的特征矩陣,nmj表示評分項(xiàng)目j的用戶數(shù)量。

1.2 ALS算法存在的問題

基于ALS矩陣分解的協(xié)同過濾推薦算法通過對ALS算法的迭代,在Spark集群環(huán)境下訓(xùn)練出最佳模型并獲取最優(yōu)參數(shù),但是ALS算法自身存在的一些不足無法通過模型訓(xùn)練、參數(shù)優(yōu)化來改進(jìn)。比如成本消耗問題,有數(shù)據(jù)表明,推薦系統(tǒng)利用基于Spark的ALS算法進(jìn)行實(shí)時(shí)推薦,輸入數(shù)據(jù)114 GB,訓(xùn)練時(shí)間和預(yù)測時(shí)間總和超過50 min,是實(shí)際要求時(shí)間的3倍多,超出的時(shí)間將導(dǎo)致巨大的資源消耗,且推薦結(jié)果的準(zhǔn)確性也較低。

針對ALS算法存在的問題,本文將加速收斂過程以優(yōu)化ALS模型,并在優(yōu)化f(U,M)的過程中提高推送結(jié)果的準(zhǔn)確性。

2 基于NCG的ALS算法

2.1 NCG算法

(7)

NCG算法用遞推關(guān)系xk+1=xk+αkpk從初始猜測x0中生成迭代序列xi,i≥1,步長參數(shù)αk>0是沿著搜索方向pk的線搜索而確定的,每次迭代包括計(jì)算線搜索方向pk和步長因子αk兩部分,搜索方向pk要求為下降的方向,沿著該方向搜索找到比xk更好的點(diǎn)。求解minU,MLλ(R,U,M)的共軛梯度算法是根據(jù)求解線性方程組問題推廣而來,搜索方向?yàn)樨?fù)梯度與上一次搜索方向的線性組合。pk求解如下:

(8)

其中,βk+1表示更新參數(shù),本文在更新βk+1時(shí)使用PRP共軛梯度法[20],如式(9)所示。

(9)

NCG算法偽代碼描述如下:

算法1NCG算法

輸入x0

輸出xk

g0←f(xk);

p0←-g0;

k←0;

while gk≠0 do

Compute αk;

xk+1←xk+αkpk;

gk←f(xk+1);

Compute βk+1;

pk+1←-gk+1+βk+1pk;

k←k+1;

end

2.2 ALS-NCG算法設(shè)計(jì)

(10)

(11)

ALS-NCG算法偽代碼描述如下:

算法2ALS-NCG算法

輸入x0

輸出xk

k←0;

while gk≠0 do

Compute αk;

xk+1←xk+αkpk;

k←k+1;

end

算法2是改進(jìn)的ALS算法,將初始值x0作為輸入,利用遞推關(guān)系求解xk并輸出。算法3是步長因子αk的計(jì)算過程,將算法2求解的xk作為算法3的輸入,在求解過程中,需要注意線搜索類型的選擇。線搜索類型通常可以分為精確線搜索和非精確線搜索,參數(shù)αk對線搜索類型選取至關(guān)重要，αk是從xk在沿著pk的方向?qū)ふ业囊粋€(gè)最好的點(diǎn)，將其作為下一個(gè)迭代點(diǎn)，此時(shí)最好的點(diǎn)就是函數(shù)f(xk+αkpk)在該方向上數(shù)值最小的點(diǎn)，但是此時(shí)屬于精確線搜索狀態(tài),其計(jì)算量太大,實(shí)際應(yīng)用時(shí)具有較高難度,因此,本文算法求解步長因子時(shí)選擇非精確線搜索類型。c和τ的取值范圍為[0,1],本文算法3的參數(shù)選擇最佳經(jīng)驗(yàn)結(jié)果為:c=0.9,τ=0.5。算法3具體描述如下:

算法3步長因子αk計(jì)算算法

輸入xk,pk,c=0.9,τ=0.5

輸出αk

αk←10;

αk←ταk;

end

算法4ALS一次迭代算法H(xk)

輸入xk

solve U and M from xk;

for i=1,2,…,nudo

End

for j=1,2,…,nmdo

End

2.3 ALS-NCG算法的Spark并行實(shí)現(xiàn)

將ALS-NCG算法的數(shù)據(jù)結(jié)構(gòu)在Spark彈性分布式數(shù)據(jù)集(Resilient Distributed Dataset,RDD)上分區(qū),每個(gè)分區(qū)就是一個(gè)數(shù)據(jù)集片段,并且一個(gè)RDD的不同分區(qū)可以被保存到集群中不同的節(jié)點(diǎn)上,從而在集群中的不同節(jié)點(diǎn)上進(jìn)行并行計(jì)算。本文將因子矩陣U和M存儲為單精度列塊矩陣,分別表示用戶子集的因子矢量和電影子集的因子矢量。規(guī)定單精度列塊的每一塊作為RDD的一個(gè)分區(qū)單元,R和RT的行塊均以壓縮的稀疏矩陣的方式進(jìn)行存儲。圖1所示為M存儲的分配方式,將M區(qū)塊分割成若干塊,編號為M1,M2,…,Mnb,共分解成nb塊。

圖1 數(shù)據(jù)在RDD上的分區(qū)

U的存儲方式與M相同。U和R的RDD分區(qū)相同,存儲U的節(jié)點(diǎn)也可以存儲R。在更新U用戶塊時(shí),需要本地評分在R中可用,而本地U塊中用戶評分電影的M因子矢量必須混洗。由于電影因子來自不同的節(jié)點(diǎn),可通過建立路由表存儲所需的本地評分?jǐn)?shù)據(jù),避免重復(fù)發(fā)送信息。緩沖區(qū)一旦構(gòu)造,就會被混合集中到R的分區(qū),此時(shí)電影因子和本地評分?jǐn)?shù)據(jù)可用來計(jì)算新的U子塊。

圖2 RDD路由表策略

3 實(shí)驗(yàn)結(jié)果與分析

3.1 實(shí)驗(yàn)數(shù)據(jù)集

本文采用MovieLens上10 M大小的數(shù)據(jù)集進(jìn)行實(shí)驗(yàn),該數(shù)據(jù)集包括71 567個(gè)用戶、10 681部電影和10 000 054條評分,為更好地比較算法性能,ALS與ALS-NCG均使用相同的數(shù)據(jù)集。在實(shí)際應(yīng)用中,并非所有數(shù)據(jù)都滿足建立實(shí)驗(yàn)數(shù)據(jù)集的要求,因此,本文找到原始完整數(shù)據(jù)集中按照每個(gè)用戶評分?jǐn)?shù)目進(jìn)行排序的中位數(shù),用c表示,舍棄對電影評分?jǐn)?shù)目與中位數(shù)值相差較大的用戶,保留評分?jǐn)?shù)目與中位數(shù)相近的用戶,將這些數(shù)據(jù)組成實(shí)驗(yàn)數(shù)據(jù)集。

3.2 Spark運(yùn)行環(huán)境

Spark是一種類Hadoop MapReduce的基于內(nèi)存計(jì)算的大數(shù)據(jù)并行計(jì)算框架[21],Spark較Hadoop的優(yōu)勢之一是提出了RDD。RDD的高容錯(cuò)性表現(xiàn)在2個(gè)方面:1)若其中一個(gè)RDD分片丟失,則Spark可以根據(jù)日志信息重構(gòu)RDD;2)在內(nèi)存中緩存RDD后,只需從內(nèi)存中讀取數(shù)據(jù)即可計(jì)算,這樣節(jié)省了大量的磁盤存取開銷,適合迭代計(jì)算的矩陣分解算法。因此,本文搭建Spark集群作為實(shí)驗(yàn)平臺。

本文將Spark計(jì)算集群搭建在Hadoop分布式平臺上,以Hadoop中的HDFS作為集群的分布式文件存儲系統(tǒng),選擇Spark原生語言Scala[22]作為編程語言,該語言比較簡潔完善,是Spark領(lǐng)域較為常用的程序設(shè)計(jì)語言。本文實(shí)驗(yàn)的集群環(huán)境配置如表1所示。

表1 實(shí)驗(yàn)環(huán)境配置

3.3 ALS-NCG算法與ALS算法時(shí)間性能比較

表2 收斂值為10-6時(shí)2種算法的時(shí)間性能對比

表3 收斂值為10-3時(shí)2種算法的時(shí)間性能對比

從表2、表3可以看出,ALS-NCG達(dá)到目標(biāo)收斂值較快,相對ALS的加速效果明顯。

圖3表示不同規(guī)模的評分矩陣下2種算法在迭代次數(shù)相同時(shí)所用時(shí)間比值的變化趨勢,可以看出,ALS-NCG在時(shí)間消耗上比ALS小很多,隨著矩陣規(guī)模的增大,ALS-NCG的加速效果更明顯,性能更加優(yōu)越。在不同收斂值時(shí),ALS與ALS-NCG的時(shí)間性能比值變化趨勢近似一致,可見,將改進(jìn)的組合算法應(yīng)用于大數(shù)據(jù)環(huán)境中,即使收斂值擴(kuò)大到10-3,也可以達(dá)到同樣的加速效果。

圖3 不同收斂值時(shí)ALS與ALS-NCG的時(shí)間比值對比

3.4 ALS-NCG算法與ALS算法排名精度比較

由于實(shí)驗(yàn)條件限制,本文僅對排名前20的電影進(jìn)行準(zhǔn)確度實(shí)驗(yàn),使用電影排名矢量轉(zhuǎn)化所需的成對互換次數(shù)作為度量。本次實(shí)驗(yàn)借助Kendall-Tau距離來計(jì)算向量之間的差異,將距離歸一化范圍限制在[0,1]之間,再求取所有用戶的距離平均值。

若p1=[6,3,1,4,2,5]、p2=[3,4,5,2,6,1]是用戶u對2個(gè)不同電影的排名,設(shè)置t=4表示對排名前4的電影進(jìn)行排名精度計(jì)算。p1中排名第1的電影6在p2中排名第5,若要將p2中電影6排在第1位,需要交換4次位置,此時(shí)產(chǎn)生第1次迭代排名順序p21=[6,3,4,5,2,1],p1中排名第2位的是電影3,在p21中電影3同樣排在第2位,此時(shí)不需要轉(zhuǎn)換,即p22=p21,同理可得p23=[6,3,1,4,5,2],轉(zhuǎn)換3次,p24=p23,轉(zhuǎn)換0次。匹配p2到p1所需成對互換的距離總數(shù)si=4+0+3+0=7。若匹配時(shí)相同位置的電影相同,則不需要轉(zhuǎn)換,否則將會發(fā)生轉(zhuǎn)換,若匹配與被匹配的序列相反,則會出現(xiàn)最大交換次數(shù),在第1次匹配發(fā)生nm-1次交換,第2次匹配發(fā)生nm-2次交換,以此類推,最大交換次數(shù)可表示為:

smax=(nm-1)+(nm-2)+…+(nm-t)=

實(shí)驗(yàn)2選取400×80和800×160兩種規(guī)模的評分矩陣,2種算法都以20個(gè)不同的隨機(jī)起始值進(jìn)行迭代運(yùn)行求解,達(dá)到給定的不同排序精度,記錄時(shí)間數(shù)據(jù),結(jié)果如表4、表5所示。從表4、表5可以看出,在排序精度為70%時(shí),ALS對于2種規(guī)模矩陣的收斂速度相對較快,而在排序精度大于70%時(shí),ALS收斂時(shí)間較長,ALS-NCG的收斂時(shí)間比ALS算法小很多,其效率較高。

表4 400×80矩陣規(guī)模下2種算法的時(shí)間對比

表5 800×160矩陣規(guī)模下2種算法的時(shí)間對比

圖4、圖5分別呈現(xiàn)矩陣規(guī)模為400×80、800×160時(shí)2種算法的運(yùn)行時(shí)間趨勢。從中可以看出,隨著排序精度的提高,ALS-NCG算法的時(shí)間消耗變化較為平緩,更符合實(shí)際需求,而ALS算法需要更長的時(shí)間才能達(dá)到目標(biāo)精度。

圖4 矩陣規(guī)模為400×80時(shí)的算法時(shí)間趨勢對比

圖5 矩陣規(guī)模為800×160時(shí)的算法時(shí)間趨勢對比

3.5 ALS-NCG算法與ALS算法性能指標(biāo)比較

本文采用推薦系統(tǒng)領(lǐng)域常用的均方根誤差(Root Mean Squared Error,RMSE)來度量算法的性能。RMSE是預(yù)測值與真實(shí)值偏差的平方與預(yù)測值的比值的平方根,其值越小說明測量的精確度越高。

ALS-NCG算法在執(zhí)行速度與排序精度上都優(yōu)于ALS算法,實(shí)驗(yàn)3將在ALS訓(xùn)練的最優(yōu)參數(shù)模型的基礎(chǔ)上對2種算法的RMSE值進(jìn)行求解,其中,ALS算法最佳迭代次數(shù)為25,實(shí)驗(yàn)結(jié)果如表6所示。從表6可以看出,ALS-NCG算法達(dá)到與ALS算法相近的RMSE值僅需迭代7次,迭代次數(shù)明顯減少。

表6 2種算法的RMSE值對比

3.6 ALS-NCG算法與其他算法性能指標(biāo)比較

將ALS-NCG算法與受限玻爾茲曼機(jī)(RBM)、k=21時(shí)的k近鄰(kNN)算法、ALS算法、ALS+kNN+RBM組合方法以及均值模型的RMSE值進(jìn)行比較,結(jié)果如表7所示。從表7可以看出,ALS-NCG算法具有明顯優(yōu)勢,它相對其他算法的RMSE改善率最高可達(dá)25.17%。

表7 不同方法的RMSE值比較

ALS算法雖然應(yīng)用于推薦系統(tǒng)時(shí)效果較好,但是其迭代時(shí)間過長,影響推薦系統(tǒng)性能。NCG算法數(shù)值表現(xiàn)良好,并且具有較高的收斂性,可以加速ALS算法的收斂,提高推薦效果。雖然ALS-NCG算法的每一步迭代復(fù)雜度較高,但是算法整體收斂程度增大,使得總迭代次數(shù)減少,在Spark環(huán)境中,其收斂速度明顯高于ALS算法,當(dāng)兩者的RMSE值接近時(shí),ALS-NCG算法的迭代次數(shù)僅為ALS算法的1/3左右。

4 結(jié)束語

基于矩陣分解的ALS算法應(yīng)用于推薦系統(tǒng)時(shí),執(zhí)行速率與排名精度均較低。本文分析ALS算法自身存在的問題,提出一種融合NCG與ALS的協(xié)同過濾推薦算法ALS-NCG,并在Spark集群環(huán)境中進(jìn)行實(shí)驗(yàn),結(jié)果表明,ALS-NCG算法在收斂速度和排名精度上都優(yōu)于ALS算法。下一步將通過卷積神經(jīng)網(wǎng)絡(luò)對用戶評論中的文本特征進(jìn)行學(xué)習(xí),并將提取的文本特征引入到ALS-NCG算法中,以進(jìn)一步改善推薦效果。