文獻(xiàn)標(biāo)識(shí)碼: A
DOI:10.16157/j.issn.0258-7998.2015.09.037
中文引用格式: 車(chē)晉強(qiáng),謝紅薇. 基于Spark的分層協(xié)同過(guò)濾推薦算法[J].電子技術(shù)應(yīng)用,2015,41(9):135-138.
英文引用格式: Che Jinqiang,Xie Hongwei. Hierarchical collaborative filtering algorithm based on Spark[J].Application of Electronic Technique,2015,41(9):135-138.
0 引言
互聯(lián)網(wǎng)和電子商務(wù)的迅猛發(fā)展已經(jīng)把人們帶入了一個(gè)信息爆炸的時(shí)代,商品種類(lèi)和數(shù)量的快速增長(zhǎng),使得顧客花費(fèi)了大量的時(shí)間瀏覽無(wú)關(guān)的信息,個(gè)性化推薦系統(tǒng)作為解決信息過(guò)載的方法應(yīng)運(yùn)而生,被廣泛的應(yīng)用到了當(dāng)前的電子商務(wù)系統(tǒng)[1]。而基于協(xié)同過(guò)濾的推薦算法無(wú)疑是最廣泛使用的算法[2],其主要分為基于用戶(hù)(User-based)和基于商品(Item-based)的推薦算法[3]。基于用戶(hù)的協(xié)同過(guò)濾算法主要通過(guò)計(jì)算用戶(hù)之間的相似性,通過(guò)對(duì)與目標(biāo)用戶(hù)相似性較高的用戶(hù)對(duì)商品的評(píng)價(jià)信息從而推薦給目標(biāo)用戶(hù)。基于項(xiàng)目的協(xié)同過(guò)濾算法則是查找項(xiàng)目之間的相關(guān)性。但是在電子商務(wù)網(wǎng)站當(dāng)中,用戶(hù)評(píng)分?jǐn)?shù)據(jù)不會(huì)超過(guò)項(xiàng)目總數(shù)的百分之一[4],稀疏性以及實(shí)時(shí)性都是急需解決的問(wèn)題。
針對(duì)推薦實(shí)時(shí)性問(wèn)題,文獻(xiàn)[5]在Hadoop平臺(tái)上實(shí)現(xiàn)了User-based并行協(xié)同過(guò)濾推薦算法;文獻(xiàn)[6]在Hadoop平臺(tái)上實(shí)現(xiàn)了Item-based協(xié)同過(guò)濾推薦算法,其時(shí)間復(fù)雜度為O(n2m2);燕存[7]針對(duì)其時(shí)間復(fù)雜度過(guò)高的問(wèn)題,提出了一種改進(jìn)的Item-based協(xié)同過(guò)濾推薦算法。針對(duì)數(shù)據(jù)稀疏性問(wèn)題,王雪蓉[8]研究了將用戶(hù)行為關(guān)聯(lián)聚類(lèi)以實(shí)現(xiàn)更好的推薦效果,任帥[9]基于用戶(hù)行為模型和蟻群聚類(lèi)以實(shí)現(xiàn)更合理的推薦。Spark作為一個(gè)新的開(kāi)源集群計(jì)算框架,其基于內(nèi)存計(jì)算以及粗粒度的RDD機(jī)制非常適合于迭代型的計(jì)算。本文針對(duì)推薦實(shí)時(shí)性以及數(shù)據(jù)稀疏性問(wèn)題,基于Spark平臺(tái),提出一個(gè)分層的協(xié)同過(guò)濾推薦算法。
1 Spark相關(guān)技術(shù)
Spark作為一個(gè)分布式框架,它支持內(nèi)存計(jì)算、多迭代處理、流處理與圖計(jì)算多種范式,非常適合于各種迭代算法和交互式數(shù)據(jù)分析,Spark的核心抽象模型是RDD(彈性分布式數(shù)據(jù)集),基于RDD,Spark提供了一個(gè)非常容易使用的編程接口。
1.1 彈性分布式數(shù)據(jù)集
RDD是不可變的,RDD一旦創(chuàng)建就沒(méi)有辦法對(duì)其進(jìn)行更改,但是卻能創(chuàng)建出新的RDD。其次,RDD的不可變性使得Spark提供了高效的容錯(cuò)機(jī)制,由于每個(gè)RDD都保留有計(jì)算至當(dāng)前數(shù)值的全部歷史記錄,而且其他進(jìn)程無(wú)法對(duì)其作出更改。因此,當(dāng)某個(gè)節(jié)點(diǎn)丟失數(shù)據(jù)時(shí),只需要對(duì)該節(jié)點(diǎn)的RDD重新計(jì)算即可,并不影響其他節(jié)點(diǎn)的運(yùn)行。RDD機(jī)制如圖1所示。
1.2 Spark應(yīng)用程序框架
Spark Application的運(yùn)行架構(gòu)由兩部分組成:driver program(SparkContext)和executor。Spark Application一般都是在集群中運(yùn)行,如standalone、yarn、mesos等。在這些集群當(dāng)中提供了計(jì)算資源和資源管理,這些資源即可以給executor執(zhí)行,也可以給driver program運(yùn)行。根據(jù)driver program 是否在集群中,SparkContext又可以分為cluster與client模式。Spark應(yīng)用程序框架如圖2所示。
2 用戶(hù)偏好模型
定義1(用戶(hù)偏好集合)將用戶(hù)在網(wǎng)站瀏覽行為中的平均訪問(wèn)時(shí)間、點(diǎn)擊數(shù)目、購(gòu)買(mǎi)數(shù)目、點(diǎn)擊收藏比、點(diǎn)擊加入購(gòu)物車(chē)、平均收藏與購(gòu)買(mǎi)間隔以及平均點(diǎn)擊與購(gòu)買(mǎi)間隔7種特征構(gòu)成用戶(hù)偏好集和:IA={A1,A2,A3,…,A7}。
為了構(gòu)建用戶(hù)偏好模型,需要為用戶(hù)偏好集合中不同的特征賦予不同的權(quán)值,以便區(qū)分不同特征對(duì)模型的貢獻(xiàn)程度,如表1。
表1中的7種偏好特征從不同程度上代表了用戶(hù)的行為習(xí)慣,為每一種偏好特征賦予一個(gè)權(quán)值,從而得出的用戶(hù)偏好模型如下:
使用熵權(quán)法[10]來(lái)確定每一個(gè)偏好特征的權(quán)值,它通過(guò)統(tǒng)計(jì)的方法處理后獲得權(quán)重。將用戶(hù)ui的偏好特征表示成n×7階矩陣B=(bij)n×7,其中bij表示用戶(hù)i第j個(gè)特征的值。熵權(quán)法的計(jì)算過(guò)程如下:
(1)標(biāo)準(zhǔn)化數(shù)據(jù)處理,如式(2)、式(3):
通過(guò)以上方法便可計(jì)算出用戶(hù)偏好模型中每一種偏好特征的權(quán)值。
3 并行化EM算法
期望最大化(EM)算法是在模型中尋找參數(shù)的最大似然估計(jì)或者最大后驗(yàn)估計(jì)的算法,它從一個(gè)最初的假設(shè)開(kāi)始,迭代計(jì)算隱藏變量的期望值。再重新計(jì)算極大似然估計(jì),直到收斂于一個(gè)局部最大似然估計(jì)。算法的實(shí)現(xiàn)過(guò)程如下:
(1)估計(jì)參數(shù):利用式(5)將每個(gè)對(duì)象xi指派到對(duì)應(yīng)的用戶(hù)簇中。
其中,p(xi|Ck)=N(k,E(xi))服從方差為E(xi)、期望為k的正態(tài)分布,參數(shù)估計(jì)是對(duì)每一個(gè)用戶(hù)簇計(jì)算對(duì)象的隸屬概率。
(2)最大化:利用上一步驟的結(jié)果重新估計(jì)參數(shù)以使針對(duì)給定數(shù)據(jù)的分布似然最大化。
(3)重復(fù)以上步驟直到參數(shù)收斂,聚類(lèi)過(guò)程完成。
為了實(shí)現(xiàn)EM算法的并行化,首先將用戶(hù)偏好模型數(shù)據(jù)劃分到集群上的每一個(gè)節(jié)點(diǎn),即將用戶(hù)劃分成 M個(gè)組:U1,… UM,每一組用戶(hù)為一張二維關(guān)系表,行為用戶(hù)實(shí)例,列為偏好特征值,并行化算法如下:
(1)Combine users,分別在不同的結(jié)點(diǎn)計(jì)算任意兩個(gè)用戶(hù)的相似度,并將相似度高的兩個(gè)類(lèi)別合并成一個(gè)類(lèi)別;
(2)Compute similarity,根據(jù)式(6)計(jì)算每一個(gè)類(lèi)別的相似性;
(3)Shufflle,全局hash劃分類(lèi)別;
(4)Checkpoint,將不同類(lèi)別緩存到內(nèi)存中;
(5)Recycle ,根據(jù)式(7)對(duì)參數(shù)求精,并重復(fù)此過(guò)程,直到完成聚類(lèi);
(6)Clean,清除中間數(shù)據(jù),并將結(jié)果按類(lèi)別存儲(chǔ)在不同計(jì)算節(jié)點(diǎn)上。
4 并行化協(xié)同過(guò)濾算法
Item-based協(xié)同過(guò)濾將一個(gè)用戶(hù)所購(gòu)買(mǎi)的商品推薦其匹配的相似商品,即將所有用戶(hù)對(duì)購(gòu)買(mǎi)的商品的評(píng)價(jià)作為一個(gè)向量,通過(guò)向量計(jì)算物品之間的相似度。用U對(duì)商品i與商品j共同評(píng)價(jià)的用戶(hù)集合,則它們之間的相似度sim(i,j)可通過(guò)Pearson相關(guān)系數(shù)計(jì)算:
將用戶(hù)評(píng)分?jǐn)?shù)據(jù)文件存放在HDFS上,每一行數(shù)據(jù)代表一個(gè)用戶(hù)的歷史購(gòu)買(mǎi)項(xiàng)目記錄,詳細(xì)算法如下:
(1)data=sc.textFile(“hdfs://”),加載數(shù)據(jù),每行數(shù)據(jù)代表一個(gè)用戶(hù)的歷史購(gòu)買(mǎi)項(xiàng)目記錄;
(2)getItemsAndRatings(data,items,ratings,len),劃分?jǐn)?shù)據(jù),獲取到所有項(xiàng)目及評(píng)分存入items數(shù)組與ratings數(shù)組中;
(3)(item_a,item_b)=zip(items 1 to len),將項(xiàng)目?jī)蓛山M成對(duì);
(4)(ratings_a,ratings_b)=zip(ratings 1 to len);
(5)shuffle ,全局hash劃分?jǐn)?shù)據(jù),將相同項(xiàng)目對(duì)劃分到同一個(gè)結(jié)點(diǎn);
(6)Compute Pearson(),由式(8)計(jì)算兩項(xiàng)目之間的相似度;
(7)readItem(key,item1,item2),從項(xiàng)目對(duì)中解析出兩個(gè)項(xiàng)目;
(8)Shuffle,將包含某一項(xiàng)目的所有項(xiàng)目劃分到同一個(gè)結(jié)點(diǎn)中;
(9)Cache(key,value),緩存項(xiàng)目及其相似度列表;
(10)Prediction(),預(yù)測(cè)未購(gòu)買(mǎi)商品的評(píng)分;
(11)saveAsTextFile(),輸出并存儲(chǔ)用戶(hù)推薦商品列表。
5 基于Spark分層協(xié)同過(guò)濾推薦算法
在執(zhí)行算法之前,首先需要將數(shù)據(jù)集加載到HDFS文件系統(tǒng)中,首先Spark會(huì)生成一個(gè)SparkContext全局常量,將基于SparkContext從HDFS上讀取數(shù)據(jù),textFile()這個(gè)函數(shù)有助于從HDFS上讀取數(shù)據(jù)并形成一行一行為基礎(chǔ)的RDD。可以使用cache將數(shù)據(jù)加載到內(nèi)存以便重復(fù)使用。詳細(xì)算法實(shí)現(xiàn)如下:
(1)準(zhǔn)備:搭建Hadoop與Spark集群,并將數(shù)據(jù)存放到HDFS;
(2)由用戶(hù)行為計(jì)算偏好特征權(quán)值;
(3)存儲(chǔ)用戶(hù)偏好特征數(shù)據(jù);
(4)并行EM算法對(duì)用戶(hù)聚類(lèi);
(5)將不同用戶(hù)簇存放不同結(jié)點(diǎn);
(6)將用戶(hù)-評(píng)分?jǐn)?shù)據(jù)存入相同用戶(hù)結(jié)點(diǎn),數(shù)據(jù)本地性;
(7)并行運(yùn)行協(xié)同過(guò)濾算法;
(8)預(yù)測(cè)用戶(hù)-商品評(píng)分;
(9)形成推薦列表并保存。
6 實(shí)驗(yàn)及分析
在實(shí)驗(yàn)集群當(dāng)中,有一個(gè)master節(jié)點(diǎn)、3個(gè)slaves節(jié)點(diǎn),每個(gè)節(jié)點(diǎn)的內(nèi)存為8 GB,2核。集群當(dāng)中安裝的是Hadoop2.4.1與Spark1.3.0版本。程序采用IntelliJ集成開(kāi)發(fā)環(huán)境完成,本實(shí)驗(yàn)主要實(shí)現(xiàn)了基于Spark的分層協(xié)同過(guò)濾算法并與基于MapReduce的并行算法的對(duì)比。
(1)準(zhǔn)確率、時(shí)間復(fù)雜度分析
實(shí)驗(yàn)一數(shù)據(jù)采用阿里巴巴云平臺(tái)的天池?cái)?shù)據(jù),總共十萬(wàn)多條行為記錄,MapReduce使用并行Item-based協(xié)同過(guò)濾算法,Spark使用分層協(xié)同過(guò)濾推薦算法,實(shí)驗(yàn)結(jié)果如表2所示。
從表1可以看出,基于Spark的分層協(xié)同過(guò)濾算法在準(zhǔn)確率上比普通的協(xié)同過(guò)濾算法更高,并且大大節(jié)約了時(shí)間,提高了性能。
(2)性能表現(xiàn)
實(shí)驗(yàn)二測(cè)試Spark實(shí)現(xiàn)的分層協(xié)同過(guò)濾算法的擴(kuò)展性,分析了在不同節(jié)點(diǎn)個(gè)數(shù)上的性能表現(xiàn),如圖3所示。
從圖中可以看到,當(dāng)節(jié)點(diǎn)數(shù)量達(dá)到一定程度以后,其所消耗的時(shí)間并沒(méi)有減小得太厲害。接下來(lái)將會(huì)測(cè)試在不同大小的數(shù)據(jù)集上算法所表現(xiàn)出來(lái)的性能。
7 結(jié)束語(yǔ)
協(xié)同過(guò)濾是推薦算法中最為廣泛使用的推薦算法,研究協(xié)同過(guò)濾的并行化算法也非常多。本文在前人的基礎(chǔ)上,提出一種基于Spark的分層協(xié)同過(guò)濾推薦算法,其核心是把用戶(hù)按不同的偏好特征劃分不同的用戶(hù)簇,之后針對(duì)不同的用戶(hù)簇作協(xié)同過(guò)濾推薦。另外,在Spark平臺(tái)上實(shí)現(xiàn)該算法并與MapReduce的算法比較。實(shí)驗(yàn)結(jié)果表明,算法提高了推薦準(zhǔn)確率與時(shí)間性能,并具有一定的拓展性。
參考文獻(xiàn)
[1] MALTONI D,MAIO D,JAIN.A handbook of fingerprint recognication[M].Berlin,Springer,2009.
[2] LINDEN G,SMITH B,YORK J.Amazeon.com recommenda-tions:item-to-item collaborative filtering[J].IEEE Internet Computing,2003,7(1):76-80.
[3] SCHAFER J B,F(xiàn)RANKOWSKI D,HERLOCKER J,et al.Collaborative filtering recommender systems[M].Berlin Heidelberg:Springer,2007:291-324.
[4] SUN X H,KONG F S,YE S.A comparison of several algorithms for collaborative filtering in startup stage[C].Proceedings of the 2006 IEEE International Conference on Networking,Sensing and Controlling.Washington,DC:IEEE Computer Society,2006:25-28.
[5] ZHAO Z D,SHANG M S.User-based collaborative-filteringrecommendation algorithms on hadoop[C].Third International
Conference on Knowledge Discovery and Data Mining.Thailang:IEEE,2010:478-481.
[6] JIANG J,LU J,ZHANG G,et al.Scaling-up item-based collaborative filtering recommendation algorithm based on hadoop[C].2011 IEEE World Congress on Services(SER-VICES).Washington:IEEE,2011:490-497.
[7] 燕存,吉根林.Item-Based并行協(xié)同過(guò)濾推薦算法的設(shè)計(jì)與實(shí)現(xiàn)[J].南京師大學(xué)報(bào)(自然科學(xué)版),2014,37(1): 71-76.
[8] 王雪蓉,萬(wàn)年紅.云模式用戶(hù)行為關(guān)聯(lián)聚類(lèi)的協(xié)同過(guò)濾推薦算法[J].計(jì)算機(jī)應(yīng)用,2011,31(9):2421-2426.
[9] 任帥,王浙明,王明敏.基于用戶(hù)行為模型和蟻群聚類(lèi)的協(xié)同過(guò)濾推薦算法[J].微型電腦應(yīng)用,2014,30(3):5-9.
[10] COVER T M,THOMAS J A.Elements of information theory[M].[S.1.]:Wiley-Interscience,2006.