0 引言

　　互聯(lián)網(wǎng)和電子商務(wù)的迅猛發(fā)展已經(jīng)把人們帶入了一個信息爆炸的時代,，商品種類和數(shù)量的快速增長,，使得顧客花費了大量的時間瀏覽無關(guān)的信息，個性化推薦系統(tǒng)作為解決信息過載的方法應(yīng)運而生,，被廣泛的應(yīng)用到了當(dāng)前的電子商務(wù)系統(tǒng)[1],。而基于協(xié)同過濾的推薦算法無疑是最廣泛使用的算法[2]，其主要分為基于用戶（User-based）和基于商品(Item-based)的推薦算法[3],?；谟脩舻膮f(xié)同過濾算法主要通過計算用戶之間的相似性,，通過對與目標(biāo)用戶相似性較高的用戶對商品的評價信息從而推薦給目標(biāo)用戶?；陧椖康膮f(xié)同過濾算法則是查找項目之間的相關(guān)性,。但是在電子商務(wù)網(wǎng)站當(dā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都保留有計算至當(dāng)前數(shù)值的全部歷史記錄，而且其他進程無法對其作出更改,。因此,，當(dāng)某個節(jié)點丟失數(shù)據(jù)時，只需要對該節(jié)點的RDD重新計算即可,，并不影響其他節(jié)點的運行,。RDD機制如圖1所示,。

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

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

　　2 用戶偏好模型

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

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

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

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

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

　　通過以上方法便可計算出用戶偏好模型中每一種偏好特征的權(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)準(zhǔn)備：搭建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 實驗及分析

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

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

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

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

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

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

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

7 結(jié)束語

　　協(xié)同過濾是推薦算法中最為廣泛使用的推薦算法,，研究協(xié)同過濾的并行化算法也非常多。本文在前人的基礎(chǔ)上,，提出一種基于Spark的分層協(xié)同過濾推薦算法,，其核心是把用戶按不同的偏好特征劃分不同的用戶簇，之后針對不同的用戶簇作協(xié)同過濾推薦。另外,，在Spark平臺上實現(xiàn)該算法并與MapReduce的算法比較,。實驗結(jié)果表明，算法提高了推薦準(zhǔ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é)同過濾推薦算法的設(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.