《電子技術(shù)應(yīng)用》
您所在的位置:首頁(yè) > 嵌入式技術(shù) > 設(shè)計(jì)應(yīng)用 > 基于Spark的分層協(xié)同過(guò)濾推薦算法
基于Spark的分層協(xié)同過(guò)濾推薦算法
2015年電子技術(shù)應(yīng)用第9期
車晉強(qiáng),謝紅薇
(太原理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,山西 太原030024)
摘要: 協(xié)同過(guò)濾是推薦系統(tǒng)中最廣泛使用的推薦算法。針對(duì)單機(jī)模型已經(jīng)不能滿足推薦系統(tǒng)的實(shí)時(shí)性與擴(kuò)展性,提出一種基于Spark的分層協(xié)同過(guò)濾推薦算法。算法首先基于用戶時(shí)間行為序列構(gòu)建用戶興趣模型;其次基于RDD實(shí)現(xiàn)了并行化EM聚類算法,將用戶劃分為不同的用戶簇;最后基于不同的用戶簇實(shí)現(xiàn)了并行化Item-based協(xié)同過(guò)濾推薦算法。通過(guò)阿里巴巴天池?cái)?shù)據(jù)集實(shí)驗(yàn)表明,該算法可明顯減少推薦時(shí)間并提高了推薦準(zhǔn)確度,具有良好的可擴(kuò)展性。
中圖分類號(hào): TP3
文獻(xiàn)標(biāo)識(shí)碼: A
DOI:10.16157/j.issn.0258-7998.2015.09.037

中文引用格式: 車晉強(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.
Hierarchical collaborative filtering algorithm based on Spark
Che Jinqiang,Xie Hongwei
College of Compute Science and Technology,Taiyuan University of Technology,Taiyuan 030024,China
Abstract: Collaborative filtering is the most widely used method in recommendation system. As the single computer is not suitable for the real-time and scalability of the recommendation system, a hierarchical collaborative filtering algorithm based on spark is proposed. First, according to user action sequences,a user interest model is created in the algorithm. Then, the parallelized Expectation-maximization(EM) clustering algorithm based on Resilient Distributed Datasets(RDD) is realized,and as a result, users is divided into different user cluster model. Last, the parallelized item-based collaborative filtering is achieved based on different user cluster. The experiments in Alibaba tianchi datasets show that the algorithm can significantly reduce the time, improve the accuracy of recommentation,and it has good scalability at the same time.
Key words : collaborative filtering;Spark;EM;recommendation algorithm

  

0 引言

  互聯(lián)網(wǎng)和電子商務(wù)的迅猛發(fā)展已經(jīng)把人們帶入了一個(gè)信息爆炸的時(shí)代,商品種類和數(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],其主要分為基于用戶(User-based)和基于商品(Item-based)的推薦算法[3]?;谟脩舻膮f(xié)同過(guò)濾算法主要通過(guò)計(jì)算用戶之間的相似性,通過(guò)對(duì)與目標(biāo)用戶相似性較高的用戶對(duì)商品的評(píng)價(jià)信息從而推薦給目標(biāo)用戶?;陧?xiàng)目的協(xié)同過(guò)濾算法則是查找項(xiàng)目之間的相關(guān)性。但是在電子商務(wù)網(wǎng)站當(dāng)中,用戶評(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]研究了將用戶行為關(guān)聯(lián)聚類以實(shí)現(xiàn)更好的推薦效果,任帥[9]基于用戶行為模型和蟻群聚類以實(shí)現(xiàn)更合理的推薦。Spark作為一個(gè)新的開源集群計(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所示。

001.jpg

  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所示。

002.jpg

  2 用戶偏好模型

  定義1(用戶偏好集合)將用戶在網(wǎng)站瀏覽行為中的平均訪問(wèn)時(shí)間、點(diǎn)擊數(shù)目、購(gòu)買數(shù)目、點(diǎn)擊收藏比、點(diǎn)擊加入購(gòu)物車、平均收藏與購(gòu)買間隔以及平均點(diǎn)擊與購(gòu)買間隔7種特征構(gòu)成用戶偏好集和:IA={A1,A2,A3,…,A7}。

  為了構(gòu)建用戶偏好模型,需要為用戶偏好集合中不同的特征賦予不同的權(quán)值,以便區(qū)分不同特征對(duì)模型的貢獻(xiàn)程度,如表1。

004.jpg

  表1中的7種偏好特征從不同程度上代表了用戶的行為習(xí)慣,為每一種偏好特征賦予一個(gè)權(quán)值,從而得出的用戶偏好模型如下:

  1.png

  使用熵權(quán)法[10]來(lái)確定每一個(gè)偏好特征的權(quán)值,它通過(guò)統(tǒng)計(jì)的方法處理后獲得權(quán)重。將用戶ui的偏好特征表示成n×7階矩陣B=(bij)n×7,其中bij表示用戶i第j個(gè)特征的值。熵權(quán)法的計(jì)算過(guò)程如下:

  (1)標(biāo)準(zhǔn)化數(shù)據(jù)處理,如式(2)、式(3):

  25.jpg

  通過(guò)以上方法便可計(jì)算出用戶偏好模型中每一種偏好特征的權(quán)值。

  3 并行化EM算法

  期望最大化(EM)算法是在模型中尋找參數(shù)的最大似然估計(jì)或者最大后驗(yàn)估計(jì)的算法,它從一個(gè)最初的假設(shè)開始,迭代計(jì)算隱藏變量的期望值。再重新計(jì)算極大似然估計(jì),直到收斂于一個(gè)局部最大似然估計(jì)。算法的實(shí)現(xiàn)過(guò)程如下:

  (1)估計(jì)參數(shù):利用式(5)將每個(gè)對(duì)象xi指派到對(duì)應(yīng)的用戶簇中。

  6.png

  其中,p(xi|Ck)=N(k,E(xi))服從方差為E(xi)、期望為k的正態(tài)分布,參數(shù)估計(jì)是對(duì)每一個(gè)用戶簇計(jì)算對(duì)象的隸屬概率。

  (2)最大化:利用上一步驟的結(jié)果重新估計(jì)參數(shù)以使針對(duì)給定數(shù)據(jù)的分布似然最大化。

  7.png

  (3)重復(fù)以上步驟直到參數(shù)收斂,聚類過(guò)程完成。

  為了實(shí)現(xiàn)EM算法的并行化,首先將用戶偏好模型數(shù)據(jù)劃分到集群上的每一個(gè)節(jié)點(diǎn),即將用戶劃分成 M個(gè)組:U1,… UM,每一組用戶為一張二維關(guān)系表,行為用戶實(shí)例,列為偏好特征值,并行化算法如下:

  (1)Combine users,分別在不同的結(jié)點(diǎn)計(jì)算任意兩個(gè)用戶的相似度,并將相似度高的兩個(gè)類別合并成一個(gè)類別;

  (2)Compute similarity,根據(jù)式(6)計(jì)算每一個(gè)類別的相似性;

  (3)Shufflle,全局hash劃分類別;

  (4)Checkpoint,將不同類別緩存到內(nèi)存中;

  (5)Recycle ,根據(jù)式(7)對(duì)參數(shù)求精,并重復(fù)此過(guò)程,直到完成聚類;

  (6)Clean,清除中間數(shù)據(jù),并將結(jié)果按類別存儲(chǔ)在不同計(jì)算節(jié)點(diǎn)上。

4 并行化協(xié)同過(guò)濾算法

  Item-based協(xié)同過(guò)濾將一個(gè)用戶所購(gòu)買的商品推薦其匹配的相似商品,即將所有用戶對(duì)購(gòu)買的商品的評(píng)價(jià)作為一個(gè)向量,通過(guò)向量計(jì)算物品之間的相似度。用U對(duì)商品i與商品j共同評(píng)價(jià)的用戶集合,則它們之間的相似度sim(i,j)可通過(guò)Pearson相關(guān)系數(shù)計(jì)算:

  8.png

  將用戶評(píng)分?jǐn)?shù)據(jù)文件存放在HDFS上,每一行數(shù)據(jù)代表一個(gè)用戶的歷史購(gòu)買項(xiàng)目記錄,詳細(xì)算法如下:

  (1)data=sc.textFile(“hdfs://”),加載數(shù)據(jù),每行數(shù)據(jù)代表一個(gè)用戶的歷史購(gòu)買項(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)買商品的評(píng)分;

  (11)saveAsTextFile(),輸出并存儲(chǔ)用戶推薦商品列表。

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??梢允褂胏ache將數(shù)據(jù)加載到內(nèi)存以便重復(fù)使用。詳細(xì)算法實(shí)現(xiàn)如下:

  (1)準(zhǔn)備:搭建Hadoop與Spark集群,并將數(shù)據(jù)存放到HDFS;

  (2)由用戶行為計(jì)算偏好特征權(quán)值;

  (3)存儲(chǔ)用戶偏好特征數(shù)據(jù);

  (4)并行EM算法對(duì)用戶聚類;

  (5)將不同用戶簇存放不同結(jié)點(diǎn);

  (6)將用戶-評(píng)分?jǐn)?shù)據(jù)存入相同用戶結(jié)點(diǎn),數(shù)據(jù)本地性;

  (7)并行運(yùn)行協(xié)同過(guò)濾算法;

  (8)預(yù)測(cè)用戶-商品評(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集成開發(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所示。

005.jpg

  從表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所示。

003.jpg

  從圖中可以看到,當(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ò)濾推薦算法,其核心是把用戶按不同的偏好特征劃分不同的用戶簇,之后針對(duì)不同的用戶簇作協(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)年紅.云模式用戶行為關(guān)聯(lián)聚類的協(xié)同過(guò)濾推薦算法[J].計(jì)算機(jī)應(yīng)用,2011,31(9):2421-2426.

  [9] 任帥,王浙明,王明敏.基于用戶行為模型和蟻群聚類的協(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.


此內(nèi)容為AET網(wǎng)站原創(chuàng),未經(jīng)授權(quán)禁止轉(zhuǎn)載。