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

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 用戶(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。

004.jpg

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

  1.png

  使用熵權(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):

  25.jpg

  通過(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ù)簇中。

  6.png

  其中,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ù)的分布似然最大化。

  7.png

  (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ì)算:

  8.png

  將用戶(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所示。

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ò)濾推薦算法,其核心是把用戶(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.


此內(nèi)容為AET網(wǎng)站原創(chuàng),未經(jīng)授權(quán)禁止轉(zhuǎn)載。
主站蜘蛛池模板: 久久久久国产精品免费 | a级精品国产片在线观看 | 九七影院不用播放器下载 | 久久99久久99精品 | 婷婷综合七月激情啪啪 | 久久99国产精品久久 | 国产精品96久久久久久久 | 春色www视频在线观看 | 成人av在线电影 | 日韩欧美中文字幕在线播放 | 久久综合给合久久狠狠狠… | 日本免费网站视频www区 | 久久99精品久久久久久噜噜噜 | 丁香婷婷色 | 国产视频资源在线观看 | 热久久国产 | 国内精品久久久久不卡 | 狠狠色狠色综合曰曰 | 五月婷婷激情五月 | 丁香激情综合网 | 你懂的视频在线 | 91国自产精品中文字幕亚洲 | 精品毛片免费看 | 五月婷激情 | 欧美综合自拍亚洲综合百度 | 国内精品日本久久久久影院 | 亚洲精品99久久久久久 | 四虎成人影院网址 | 久久人人草 | 青草视频在线观看国产 | 国产一区二区成人 | 李丽珍电影免费观看全集 | 五月激情六月 | 中文字幕99在线精品视频免费看 | 7799国产精品久久久久99 | 国产一级片免费 | 欧美69视频 | 99久久精品免费看国产 | 99热这里只有精品久久免费 | 2023男人天堂 | 欧美视频网址 |