基于Spark的分層協(xié)同過濾推薦算法*

車晉強，謝紅薇

(太原理工大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，山西 太原 030024)

基于Spark的分層協(xié)同過濾推薦算法*

車晉強，謝紅薇

(太原理工大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，山西 太原 030024)

協(xié)同過濾是推薦系統(tǒng)中最廣泛使用的推薦算法。針對單機模型已經(jīng)不能滿足推薦系統(tǒng)的實時性與擴展性，提出一種基于Spark的分層協(xié)同過濾推薦算法。算法首先基于用戶時間行為序列構(gòu)建用戶興趣模型；其次基于RDD實現(xiàn)了并行化EM聚類算法，將用戶劃分為不同的用戶簇；最后基于不同的用戶簇實現(xiàn)了并行化 Item－based協(xié)同過濾推薦算法。通過阿里巴巴天池數(shù)據(jù)集實驗表明，該算法可明顯減少推薦時間并提高了推薦準確度，具有良好的可擴展性。

協(xié)同過濾；Spark；EM；推薦算法

0　引言

互聯(lián)網(wǎng)和電子商務(wù)的迅猛發(fā)展已經(jīng)把人們帶入了一個信息爆炸的時代，商品種類和數(shù)量的快速增長，使得顧客花費了大量的時間瀏覽無關(guān)的信息，個性化推薦系統(tǒng)作為解決信息過載的方法應(yīng)運而生，被廣泛的應(yīng)用到了當前的電子商務(wù)系統(tǒng)[1]。而基于協(xié)同過濾的推薦算法無疑是最廣泛使用的算法[2]，其主要分為基于用戶（User－based）和基于商品(Item－based)的推薦算法[3]?；谟脩舻膮f(xié)同過濾算法主要通過計算用戶之間的相似性，通過對與目標用戶相似性較高的用戶對商品的評價信息從而推薦給目標用戶?；陧椖康膮f(xié)同過濾算法則是查找項目之間的相關(guān)性。但是在電子商務(wù)網(wǎng)站當中，用戶評分數(shù)據(jù)不會超過項目總數(shù)的百分之一[4]，稀疏性以及實時性都是急需解決的問題。

針對推薦實時性問題，文獻[5]在 Hadoop平臺上實現(xiàn)了User－based并行協(xié)同過濾推薦算法；文獻[6]在Hadoop平臺上實現(xiàn)了Item－based協(xié)同過濾推薦算法，其時間復(fù)雜度為 O(n2m2)；燕存[7]針對其時間復(fù)雜度過高的問題，提出了一種改進的Item－based協(xié)同過濾推薦算法。針對數(shù)據(jù)稀疏性問題，王雪蓉[8]研究了將用戶行為關(guān)聯(lián)聚類以實現(xiàn)更好的推薦效果，任帥[9]基于用戶行為模型和蟻群聚類以實現(xiàn)更合理的推薦。Spark作為一個新的開源集群計算框架，其基于內(nèi)存計算以及粗粒度的RDD機制非常適合于迭代型的計算。本文針對推薦實時性以及數(shù)據(jù)稀疏性問題，基于Spark平臺，提出一個分層的協(xié)同過濾推薦算法。

1　Spark相關(guān)技術(shù)

Spark作為一個分布式框架，它支持內(nèi)存計算、多迭代處理、流處理與圖計算多種范式，非常適合于各種迭代算法和交互式數(shù)據(jù)分析，Spark的核心抽象模型是RDD（彈性分布式數(shù)據(jù)集），基于RDD，Spark提供了一個非常容易使用的編程接口。

1.1彈性分布式數(shù)據(jù)集

RDD是不可變的，RDD一旦創(chuàng)建就沒有辦法對其進行更改，但是卻能創(chuàng)建出新的 RDD。其次，RDD的不可變性使得 Spark提供了高效的容錯機制，由于每個 RDD都保留有計算至當前數(shù)值的全部歷史記錄，而且其他進程無法對其作出更改。因此，當某個節(jié)點丟失數(shù)據(jù)時，只需要對該節(jié)點的RDD重新計算即可，并不影響其他節(jié)點的運行。RDD機制如圖1所示。

圖1　RDD機制

1.2Spark應(yīng)用程序框架

Spark Application的運行架構(gòu)由兩部分組成：driver program(SparkContext)和executor。Spark Application一般都是在集群中運行，如standalone、yarn、mesos等。在這些集群當中提供了計算資源和資源管理，這些資源即可以給executor執(zhí)行，也可以給 driver program運行。根據(jù) driver program 是否在集群中，SparkContext又可以分為 cluster與client模式。Spark應(yīng)用程序框架如圖2所示。

圖2　Spark應(yīng)用程序框架

2　用戶偏好模型

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

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

表1　偏好特征及權(quán)值

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

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

(1)標準化數(shù)據(jù)處理，如式（2）、式（3）：

其中，sij表示用戶i第j個特征權(quán)值的值，max(bij)與min(bij)分別是第j項特征權(quán)值的最大值與最小值。

(2)計算各種偏好特征的熵值，如式（4）：

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

3　并行化EM算法

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

(1)估計參數(shù)：利用式（5）將每個對象 xi指派到對應(yīng)的用戶簇中。

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

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

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

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

(1)Combine users，分別在不同的結(jié)點計算任意兩個用戶的相似度，并將相似度高的兩個類別合并成一個類別；

(2)Compute similarity，根據(jù)式（6）計算每一個類別的相似性；

(3)Shufflle，全局hash劃分類別；

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

(5)Recycle,根據(jù)式（7）對參數(shù)求精，并重復(fù)此過程，直到完成聚類；

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

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

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

將用戶評分數(shù)據(jù)文件存放在HDFS上，每一行數(shù)據(jù)代表一個用戶的歷史購買項目記錄，詳細算法如下：

(1)data=sc.textFile(“hdfs://”)，加載數(shù)據(jù)，每行數(shù)據(jù)代表一個用戶的歷史購買項目記錄；

(2)getItemsAndRatings(data，items，ratings，len)，劃分數(shù)據(jù)，獲取到所有項目及評分存入items數(shù)組與ratings數(shù)組中；

(3)(item_a，item_b)=zip(items 1 to len)，將項目兩兩組成對；

(4)(ratings_a，ratings_b)=zip(ratings 1 to len)；

(5)shuffle,全局 hash劃分數(shù)據(jù)，將相同項目對劃分到同一個結(jié)點；

(6)Compute Pearson()，由式(8)計算兩項目之間的相似度；

(7)readItem(key，item1，item2)，從項目對中解析出兩個項目；

(8)Shuffle，將包含某一項目的所有項目劃分到同一個結(jié)點中；

(9)Cache(key，value)，緩存項目及其相似度列表；

(10)Prediction()，預(yù)測未購買商品的評分；

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

5　基于Spark分層協(xié)同過濾推薦算法

在執(zhí)行算法之前，首先需要將數(shù)據(jù)集加載到HDFS文件系統(tǒng)中，首先Spark會生成一個 SparkContext全局常量，將基于SparkContext從HDFS上讀取數(shù)據(jù)，textFile()這個函數(shù)有助于從HDFS上讀取數(shù)據(jù)并形成一行一行為基礎(chǔ)的RDD?？梢允褂胏ache將數(shù)據(jù)加載到內(nèi)存以便重復(fù)使用。詳細算法實現(xiàn)如下：

(1)準備：搭建 Hadoop與 Spark集群，并將數(shù)據(jù)存放到HDFS；

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

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

(4)并行EM算法對用戶聚類；

(5)將不同用戶簇存放不同結(jié)點；

(6)將用戶－評分數(shù)據(jù)存入相同用戶結(jié)點，數(shù)據(jù)本地性；

(7)并行運行協(xié)同過濾算法；

(8)預(yù)測用戶－商品評分；

(9)形成推薦列表并保存。

6　實驗及分析

在實驗集群當中，有一個 master節(jié)點、3個slaves節(jié)點，每個節(jié)點的內(nèi)存為8 GB，2核。集群當中安裝的是Hadoop2.4.1與Spark1.3.0版本。程序采用IntelliJ集成開發(fā)環(huán)境完成，本實驗主要實現(xiàn)了基于 Spark的分層協(xié)同過濾算法并與基于MapReduce的并行算法的對比。

(1)準確率、時間復(fù)雜度分析

實驗一數(shù)據(jù)采用阿里巴巴云平臺的天池數(shù)據(jù)，總共十萬多條行為記錄，MapReduce使用并行 Item-based協(xié)同過濾算法，Spark使用分層協(xié)同過濾推薦算法，實驗結(jié)果如表2所示。

表2　算法運行結(jié)果

從表1可以看出，基于 Spark的分層協(xié)同過濾算法在準確率上比普通的協(xié)同過濾算法更高，并且大大節(jié)約了時間，提高了性能。

(2)性能表現(xiàn)

實驗二測試 Spark實現(xiàn)的分層協(xié)同過濾算法的擴展性，分析了在不同節(jié)點個數(shù)上的性能表現(xiàn)，如圖3所示。

圖3　算法擴展性

從圖中可以看到，當節(jié)點數(shù)量達到一定程度以后，其所消耗的時間并沒有減小得太厲害。接下來將會測試在不同大小的數(shù)據(jù)集上算法所表現(xiàn)出來的性能。

7　結(jié)束語

協(xié)同過濾是推薦算法中最為廣泛使用的推薦算法，研究協(xié)同過濾的并行化算法也非常多。本文在前人的基礎(chǔ)上，提出一種基于 Spark的分層協(xié)同過濾推薦算法，其核心是把用戶按不同的偏好特征劃分不同的用戶簇，之后針對不同的用戶簇作協(xié)同過濾推薦。另外，在Spark平臺上實現(xiàn)該算法并與MapReduce的算法比較。實驗結(jié)果表明，算法提高了推薦準確率與時間性能，并具有一定的拓展性。

[1]MALTONI D，MAIO D，JAIN.A handbook of fingerprint recognication[M].Berlin，Springer，2009.

[2]LINDEN G，SMITH B，YORK J.Amazeon.com recommendations：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-filtering recommendation 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(SERVICES).Washington：IEEE，2011：490-497.

[7]燕存，吉根林.Item-Based并行協(xié)同過濾推薦算法的設(shè)計與實現(xiàn)[J].南京師大學(xué)報(自然科學(xué)版)，2014，37(1)：71-76.

[8]王雪蓉，萬年紅.云模式用戶行為關(guān)聯(lián)聚類的協(xié)同過濾推薦算法[J].計算機應(yīng)用，2011，31(9)：2421-2426.

[9]任帥，王浙明，王明敏.基于用戶行為模型和蟻群聚類的協(xié)同過濾推薦算法[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.

Hierarchical collaborative filtering algorithm based on Spark

Che Jinqiang，Xie Hongwei
(College of Compute Science and Technology，Taiyuan University of Technology，Taiyuan 030024，China)

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.

collaborative filtering；Spark；EM；recommendation algorithm

TP3

A

10.16157/j.issn.0258－7998.2015.09.037

國家高科技研究發(fā)展計劃（863計劃）（2014AA015204）；山西省國際科技合作項目（2014081018－2）；山西省科技基礎(chǔ)條件平臺建設(shè)基金項目（2013091003－0103）

2015-05-06)

車晉強（1991-），男，碩士研究生，主要研究方向：人工智能、并行計算。

謝紅薇（1962-），通信作者，女，博士，教授，主要研究方向：人工智能、醫(yī)學(xué)信息學(xué)，E-mail：xiehongwei@tyut.edu.cn。

中文引用格式：車晉強，謝紅薇.基于 Spark的分層協(xié)同過濾推薦算法[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.