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

賈曉芳,桑國明,祁文凱

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

0 概述

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

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

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

1 基于矩陣分解的ALS算法

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

1.1 ALS算法

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

R≈R′=UVT

(1)

損失函數定義為:

(2)

其中,L表示損失函數。

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

(3)

其中,λ表示正則化參數。

(4)

其中,Ri.表示用戶i對項目的評分矩陣,Vui表示用戶i所評價過的項目涉及的特征向量所形成的特征矩陣,nui表示用戶i所評價的項目數量。同理,固定U后對Vi求導,然后根據求導結果解出Vj.:

(5)

(6)

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

1.2 ALS算法存在的問題

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

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

2 基于NCG的ALS算法

2.1 NCG算法

(7)

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

(8)

其中,βk+1表示更新參數,本文在更新βk+1時使用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算法設計

(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是改進的ALS算法,將初始值x0作為輸入,利用遞推關系求解xk并輸出。算法3是步長因子αk的計算過程,將算法2求解的xk作為算法3的輸入,在求解過程中,需要注意線搜索類型的選擇。線搜索類型通常可以分為精確線搜索和非精確線搜索,參數αk對線搜索類型選取至關重要，αk是從xk在沿著pk的方向尋找的一個最好的點，將其作為下一個迭代點，此時最好的點就是函數f(xk+αkpk)在該方向上數值最小的點，但是此時屬于精確線搜索狀態,其計算量太大,實際應用時具有較高難度,因此,本文算法求解步長因子時選擇非精確線搜索類型。c和τ的取值范圍為[0,1],本文算法3的參數選擇最佳經驗結果為:c=0.9,τ=0.5。算法3具體描述如下:

算法3步長因子αk計算算法

輸入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并行實現

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

圖1 數據在RDD上的分區

U的存儲方式與M相同。U和R的RDD分區相同,存儲U的節點也可以存儲R。在更新U用戶塊時,需要本地評分在R中可用,而本地U塊中用戶評分電影的M因子矢量必須混洗。由于電影因子來自不同的節點,可通過建立路由表存儲所需的本地評分數據,避免重復發送信息。緩沖區一旦構造,就會被混合集中到R的分區,此時電影因子和本地評分數據可用來計算新的U子塊。

圖2 RDD路由表策略

3 實驗結果與分析

3.1 實驗數據集

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

3.2 Spark運行環境

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

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

表1 實驗環境配置

3.3 ALS-NCG算法與ALS算法時間性能比較

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

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

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

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

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

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

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

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

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

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

表4 400×80矩陣規模下2種算法的時間對比

表5 800×160矩陣規模下2種算法的時間對比

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

圖4 矩陣規模為400×80時的算法時間趨勢對比

圖5 矩陣規模為800×160時的算法時間趨勢對比

3.5 ALS-NCG算法與ALS算法性能指標比較

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

ALS-NCG算法在執行速度與排序精度上都優于ALS算法,實驗3將在ALS訓練的最優參數模型的基礎上對2種算法的RMSE值進行求解,其中,ALS算法最佳迭代次數為25,實驗結果如表6所示。從表6可以看出,ALS-NCG算法達到與ALS算法相近的RMSE值僅需迭代7次,迭代次數明顯減少。

表6 2種算法的RMSE值對比

3.6 ALS-NCG算法與其他算法性能指標比較

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

表7 不同方法的RMSE值比較

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

4 結束語

基于矩陣分解的ALS算法應用于推薦系統時,執行速率與排名精度均較低。本文分析ALS算法自身存在的問題,提出一種融合NCG與ALS的協同過濾推薦算法ALS-NCG,并在Spark集群環境中進行實驗,結果表明,ALS-NCG算法在收斂速度和排名精度上都優于ALS算法。下一步將通過卷積神經網絡對用戶評論中的文本特征進行學習,并將提取的文本特征引入到ALS-NCG算法中,以進一步改善推薦效果。