文獻標識碼： A
DOI：10.16157/j.issn.0258-7998.2015.09.037
中文引用格式： 車晉強，謝紅薇. 基于Ｓpark的分層協同過濾推薦算法[J].電子技術應用，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 引言
互聯網和電子商務的迅猛發展已經把人們帶入了一個信息爆炸的時代，商品種類和數量的快速增長，使得顧客花費了大量的時間瀏覽無關的信息，個性化推薦系統作為解決信息過載的方法應運而生，被廣泛的應用到了當前的電子商務系統[1]。而基于協同過濾的推薦算法無疑是最廣泛使用的算法[2]，其主要分為基于用戶（User-based）和基于商品(Item-based)的推薦算法[3]?；谟脩舻膮f同過濾算法主要通過計算用戶之間的相似性，通過對與目標用戶相似性較高的用戶對商品的評價信息從而推薦給目標用戶?；陧椖康膮f同過濾算法則是查找項目之間的相關性。但是在電子商務網站當中，用戶評分數據不會超過項目總數的百分之一[4]，稀疏性以及實時性都是急需解決的問題。
針對推薦實時性問題，文獻[5]在Hadoop平臺上實現了User-based并行協同過濾推薦算法；文獻[6]在Hadoop平臺上實現了Item-based協同過濾推薦算法，其時間復雜度為O(n2m2)；燕存[7]針對其時間復雜度過高的問題，提出了一種改進的Item-based協同過濾推薦算法。針對數據稀疏性問題，王雪蓉[8]研究了將用戶行為關聯聚類以實現更好的推薦效果，任帥[9]基于用戶行為模型和蟻群聚類以實現更合理的推薦。Spark作為一個新的開源集群計算框架，其基于內存計算以及粗粒度的RDD機制非常適合于迭代型的計算。本文針對推薦實時性以及數據稀疏性問題，基于Spark平臺，提出一個分層的協同過濾推薦算法。
1 Spark相關技術
Spark作為一個分布式框架，它支持內存計算、多迭代處理、流處理與圖計算多種范式，非常適合于各種迭代算法和交互式數據分析，Spark的核心抽象模型是RDD（彈性分布式數據集），基于RDD，Spark提供了一個非常容易使用的編程接口。
1.1 彈性分布式數據集
RDD是不可變的，RDD一旦創建就沒有辦法對其進行更改，但是卻能創建出新的RDD。其次，RDD的不可變性使得Spark提供了高效的容錯機制，由于每個RDD都保留有計算至當前數值的全部歷史記錄，而且其他進程無法對其作出更改。因此，當某個節點丟失數據時，只需要對該節點的RDD重新計算即可，并不影響其他節點的運行。RDD機制如圖1所示。
1.2 Spark應用程序框架
Spark Application的運行架構由兩部分組成：driver program(SparkContext)和executor。Spark Application一般都是在集群中運行，如standalone、yarn、mesos等。在這些集群當中提供了計算資源和資源管理，這些資源即可以給executor執行，也可以給driver program運行。根據driver program 是否在集群中，SparkContext又可以分為cluster與client模式。Spark應用程序框架如圖2所示。
2 用戶偏好模型
定義1(用戶偏好集合)將用戶在網站瀏覽行為中的平均訪問時間、點擊數目、購買數目、點擊收藏比、點擊加入購物車、平均收藏與購買間隔以及平均點擊與購買間隔7種特征構成用戶偏好集和：IA={A1，A2，A3，…，A7}。
為了構建用戶偏好模型，需要為用戶偏好集合中不同的特征賦予不同的權值，以便區分不同特征對模型的貢獻程度，如表1。
表1中的7種偏好特征從不同程度上代表了用戶的行為習慣，為每一種偏好特征賦予一個權值，從而得出的用戶偏好模型如下：
使用熵權法[10]來確定每一個偏好特征的權值，它通過統計的方法處理后獲得權重。將用戶ui的偏好特征表示成n×7階矩陣B=(bij)n×7，其中bij表示用戶i第j個特征的值。熵權法的計算過程如下：
(1)標準化數據處理，如式（2）、式（3）：
通過以上方法便可計算出用戶偏好模型中每一種偏好特征的權值。
3 并行化EM算法
期望最大化（EM）算法是在模型中尋找參數的最大似然估計或者最大后驗估計的算法，它從一個最初的假設開始，迭代計算隱藏變量的期望值。再重新計算極大似然估計，直到收斂于一個局部最大似然估計。算法的實現過程如下：
(1)估計參數：利用式（5）將每個對象xi指派到對應的用戶簇中。
其中，p(xi|Ck)=N(k，E(xi))服從方差為E(xi)、期望為k的正態分布，參數估計是對每一個用戶簇計算對象的隸屬概率。
(2)最大化：利用上一步驟的結果重新估計參數以使針對給定數據的分布似然最大化。
(3)重復以上步驟直到參數收斂，聚類過程完成。
為了實現EM算法的并行化，首先將用戶偏好模型數據劃分到集群上的每一個節點，即將用戶劃分成 M個組：U1，… UM，每一組用戶為一張二維關系表，行為用戶實例，列為偏好特征值，并行化算法如下：
(1)Combine users，分別在不同的結點計算任意兩個用戶的相似度，并將相似度高的兩個類別合并成一個類別；
(2)Compute similarity，根據式（6）計算每一個類別的相似性；
(3)Shufflle，全局hash劃分類別；
(4)Checkpoint，將不同類別緩存到內存中；
(5)Recycle ,根據式（7）對參數求精，并重復此過程，直到完成聚類；
(6)Clean,清除中間數據，并將結果按類別存儲在不同計算節點上。
4 并行化協同過濾算法
Item-based協同過濾將一個用戶所購買的商品推薦其匹配的相似商品，即將所有用戶對購買的商品的評價作為一個向量，通過向量計算物品之間的相似度。用U對商品i與商品j共同評價的用戶集合，則它們之間的相似度sim(i，j)可通過Pearson相關系數計算：
將用戶評分數據文件存放在HDFS上，每一行數據代表一個用戶的歷史購買項目記錄，詳細算法如下：
(1)data=sc.textFile(“hdfs://”)，加載數據，每行數據代表一個用戶的歷史購買項目記錄；
(2)getItemsAndRatings(data，items，ratings，len)，劃分數據，獲取到所有項目及評分存入items數組與ratings數組中；
(3)(item_a，item_b)=zip(items 1 to len)，將項目兩兩組成對；
(4)(ratings_a，ratings_b)=zip(ratings 1 to len)；
(5)shuffle ,全局hash劃分數據，將相同項目對劃分到同一個結點；
(6)Compute Pearson()，由式(8)計算兩項目之間的相似度；
(7)readItem(key，item1，item2)，從項目對中解析出兩個項目；
(8)Shuffle，將包含某一項目的所有項目劃分到同一個結點中；
(9)Cache(key，value)，緩存項目及其相似度列表；
(10)Prediction()，預測未購買商品的評分；
(11)saveAsTextFile()，輸出并存儲用戶推薦商品列表。
5 基于Spark分層協同過濾推薦算法
在執行算法之前，首先需要將數據集加載到HDFS文件系統中，首先Spark會生成一個SparkContext全局常量，將基于SparkContext從HDFS上讀取數據，textFile()這個函數有助于從HDFS上讀取數據并形成一行一行為基礎的RDD。可以使用cache將數據加載到內存以便重復使用。詳細算法實現如下：
(1)準備：搭建Hadoop與Spark集群，并將數據存放到HDFS；
(2)由用戶行為計算偏好特征權值；
(3)存儲用戶偏好特征數據；
(4)并行EM算法對用戶聚類；
(5)將不同用戶簇存放不同結點；
(6)將用戶－評分數據存入相同用戶結點，數據本地性；
(7)并行運行協同過濾算法；
(8)預測用戶－商品評分；
(9)形成推薦列表并保存。
6 實驗及分析
在實驗集群當中，有一個master節點、3個slaves節點，每個節點的內存為8 GB，2核。集群當中安裝的是Hadoop2.4.1與Spark1.3.0版本。程序采用IntelliJ集成開發環境完成，本實驗主要實現了基于Spark的分層協同過濾算法并與基于MapReduce的并行算法的對比。
(1)準確率、時間復雜度分析
實驗一數據采用阿里巴巴云平臺的天池數據，總共十萬多條行為記錄，MapReduce使用并行Item-based協同過濾算法，Spark使用分層協同過濾推薦算法，實驗結果如表2所示。
從表1可以看出，基于Spark的分層協同過濾算法在準確率上比普通的協同過濾算法更高，并且大大節約了時間，提高了性能。
(2)性能表現
實驗二測試Spark實現的分層協同過濾算法的擴展性，分析了在不同節點個數上的性能表現，如圖3所示。
從圖中可以看到，當節點數量達到一定程度以后，其所消耗的時間并沒有減小得太厲害。接下來將會測試在不同大小的數據集上算法所表現出來的性能。
7 結束語
協同過濾是推薦算法中最為廣泛使用的推薦算法，研究協同過濾的并行化算法也非常多。本文在前人的基礎上，提出一種基于Spark的分層協同過濾推薦算法，其核心是把用戶按不同的偏好特征劃分不同的用戶簇，之后針對不同的用戶簇作協同過濾推薦。另外，在Spark平臺上實現該算法并與MapReduce的算法比較。實驗結果表明，算法提高了推薦準確率與時間性能，并具有一定的拓展性。
參考文獻
[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，FRANKOWSKI 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并行協同過濾推薦算法的設計與實現[J].南京師大學報(自然科學版)，2014，37(1)： 71-76.
[8] 王雪蓉，萬年紅.云模式用戶行為關聯聚類的協同過濾推薦算法[J].計算機應用，2011，31(9)：2421-2426.
[9] 任帥，王浙明，王明敏.基于用戶行為模型和蟻群聚類的協同過濾推薦算法[J].微型電腦應用，2014，30(3)：5-9.
[10] COVER T M，THOMAS J A.Elements of information theory[M].[S.1.]：Wiley-Interscience，2006.