基于圖游走的并行協同過濾推薦算法

顧軍華，謝志堅，武君艷，許馨勻，張素琪

（1. 河北工業大學 人工智能與數據科學學院，天津 300401； 2. 河北工業大學 河北省大數據計算重點實驗室，天津 300401； 3. 天津商業大學 信息工程學院，天津 300134）

近年來隨著互聯網科技的發展，大數據在促進社會進步的同時，也帶來了“信息過載”問題。如何快速從海量數據中獲取有價值的信息成為當前大數據發展的關鍵性問題[1]。為滿足人們在大數據中快速獲取有價值信息的需求，推薦系統應運而生。推薦系統的目標是根據用戶的個性化需求將最符合用戶喜好的信息挑選出來并推薦給用戶，以減輕用戶的選擇負擔。協同過濾推薦算法是一種目前應用最廣泛的推薦算法[2]，可以在用戶沒有明確提出自己需求的情況下，根據用戶的行為對用戶進行推薦。但由于大數據環境下用戶和項目的數量不斷增長，協同過濾推薦算法面臨著嚴重的數據稀疏性和可擴展性問題[3]。

針對稀疏性問題，許多學者從不同角度進行了相關研究。SUN等[4]采用聚類和時間影響因子矩陣來監測用戶興趣漂移程度，更準確的預測項目的評分。彭宏偉等[5]提出一種基于矩陣分解的上下文感知POI推薦模型，有效地緩解稀疏性問題。WU等[6]將異構信息網絡建模為張量，并提出兩種隨機梯度下降方法同時進行分解。MA等[7]提出了一種局部概率矩陣分解的方法，降低稀疏性的同時有效地緩解了每個局部模型的過擬合問題。以上的方法均通過緩解數據稀疏性問題來提高推薦的準確度。

針對協同過濾推薦算法在處理大規模數據所遇到的可擴展性問題，許多學者在并行方法上進行了相關研究。楊志文[8]、LU F[9]、KUPISZ[10]等將協同過濾推薦算法部署在Hadoop和Spark并行平臺上，取得了良好的執行效率。

本文針對協同過濾推薦算法的數據稀疏性問題和可擴展性問題進行研究。針對稀疏性問題，在皮爾遜相關相似度的基礎上引入交占比系數來計算用戶的直接相似度，提出了一種基于圖游走的協同過濾推薦算法(GW_CF)，使用圖游走的方法計算用戶的間接相似度，然后根據直接相似度和間接相似度重建用戶的相似度矩陣，最后進行推薦。在Movielens-100k數據集和IPTV數據集上實驗，驗證GW_CF在提高推薦準確度上的有效性。針對可擴展性問題，在Spark平臺上實現GW_CF算法，并使用Movielens-1M和Movielens-100k數據集進行實驗，驗證GW_CF算法的可擴展性。

1 相關工作

1.1 問題定義

基于近鄰的協同過濾問題可以描述為[11]：已知用戶集合表示為，項目集合表示為，用戶-項目評分矩陣，表示用戶對項目的評分。基于近鄰的協同過濾推薦算法的流程：1)根據評分矩陣R計算用戶的相似度；2)計算目標用戶的近鄰用戶集合；3)根據近鄰用戶的評分預測目標用戶對未評分項目的評分，從而生成推薦列表。

1.2 用戶相似度

用戶相似度指用戶與用戶之間行為中表現出的相似程度，皮爾遜相關相似度是一種常用的計算相似度的方法，反映了兩個用戶的偏好信息的線性相關程度。用戶和用戶的皮爾遜相關相似度計算公式[12-13]如下：

1.3 近鄰用戶

近鄰用戶表示與目標用戶偏好信息最相似的一組用戶，可以通過式(1)計算用戶的相似度，然后計算目標用戶的近鄰用戶。目標用戶的多個近鄰用戶組成目標用戶的近鄰用戶集合，常用的計算近鄰用戶集合的方法分為兩類：基于數量的近鄰用戶集合和基于閾值的近鄰用戶集合。

基于閾值的近鄰用戶集合包含以目標用戶為中心，與目標用戶的相似度大于Value的用戶。基于數量的近鄰用戶集合包含與目標相似度最大的Top-K個近鄰用戶。

1.4 個性化推薦

首先計算目標用戶的近鄰用戶集合，然后對目標用戶進行推薦。目標用戶對未評分項目預測評分的計算公式[14]如式（2），最后將預測評分最大的K個項目推薦給目標用戶。

2 改進的皮爾遜相關相似度

皮爾遜相關相似度計算方法如式(1)，僅僅考慮了用戶的共同評分項，而忽視了共同評分項目與每個用戶所有評分項的比例關系。這會導致如果兩個用戶僅有極少數共同評分項目，并且兩個用戶對共同評分項目的評分極度相似，使用皮爾遜相關相似度計算得到的用戶的相似度，遠遠大于用戶的真實相似度，降低了推薦的準確度。例如，用戶曾對200個項目進行了評分，用戶對300個項目進行了評分，兩個用戶僅擁有10個共同評分項目，且兩個用戶對每個共同評分項目的評分均相同。使用傳統皮爾遜相關相似度計算兩者的相似度為1(兩個用戶完全相似)。但實際上，除了10個共同評分項目以外，用戶和用戶還各自擁有大量的非共同評分項目，兩個用戶的喜好并不完全相同，利用皮爾遜相關相似度得到的結果遠遠大于兩個用戶的真實相似度。針對這個問題，本文在皮爾遜相關相似度基礎上，引入交占比系數來緩解共同評分項占比的問題，交占比反映了兩個用戶的共同評分項在兩個用戶評分中的占比，加入交占比系數的皮爾遜相關相似度計算公式如下：

3 基于圖游走的協同過濾推薦算法(GW_CF)

相似度計算是協同過濾推薦算法的關鍵部分，得到用戶相似度之后可以確定用戶的近鄰用戶集合。但以往計算用戶的相似度時只考慮用戶的直接相似相似度，這樣將會遺失目標用戶的間接近鄰用戶[15-16]。例如圖1所示，、和表示3個用戶，表示用戶的評分項目，表示用戶的評分項目，表示用戶的評分項目。、、表示用戶、和的相似度。依據式(3)計算用戶和用戶的相似度，由于用戶和用戶沒有共同評分項，所以。但是用戶和擁有共同評分項目和，那么，同理。由于相似性具有傳遞性，因此用戶和可以通過共同的相似用戶建立間接相似度，使得。如果兩個用戶沒有共同評分項目，但間接相似度大于0，稱這兩個用戶為間接近鄰用戶。在數據稀疏時，為用戶尋找間接近鄰用戶能夠有效地提高推薦的準確度。本文提出了基于圖游走的方法，首先根據用戶的直接相似度矩陣建立用戶網絡圖，其次在用戶網絡圖上進行游走計算間接相似度，然后根據間接相似度和直接相似度重建用戶的相似度矩陣，最后進行推薦。

表 1 用戶評分示例表Table 1 User rating

圖 1 間接相似度關系圖Fig. 1 Indirect similarity diagram

3.1 構建用戶網絡圖

使用用戶網絡圖來說明用戶間的相似關系,從目標用戶開始游走后停留在某個用戶的概率越高意味著它與目標用戶更相似。為了建立用戶網絡圖，首先使用式(3)計算用戶間的直接相似度，然后根據直接相似度建立用戶近鄰矩陣。為每個用戶選擇T個直接近鄰用戶，其他非T用戶的相似度置0，得到的近鄰矩陣如式(4)所示：

3.2 基于用戶網絡圖游走

在用戶網絡圖中存在著與其他用戶的相似度都很低甚至可以忽略不計的特殊用戶節點。在用戶網絡圖中此類節點只有入度，沒有出度，如圖2中節點D，此時由于圖中D節點只有入度，沒有出度，用戶網絡圖演變為非強連通圖，以式(5)的方法游走到圖中節點D時將無法跳轉到其他節點。整個用戶網絡圖的游走最終停留在類似節點D的死節點，無法求得用戶的間接相似度，因此對式(5)進行變形如下：

圖 2 非強連通用戶網絡示例圖Fig. 2 Non-strong connected user network

3.3 重建相似度矩陣

3.4 生成推薦結果

以每個用戶頂點為起點進行游走查找其間接相似用戶，得到重建的用戶相似度矩陣，進一步得到目標用戶的近鄰用戶集合。然后利用式(2)對目標用戶的未評分項目進行評分預測，并將評分最高的Top-K個項目推薦給目標用戶。

4 基于圖游走的并行協同過濾推薦算法

4.1 Spark介紹

Spark是基于內存的分布式并行計算平臺[19]，它擁有Hadoop平臺和MapReduce框架的全部優點，并且Spark運算的中間結果能存儲在內存中，提高了并行計算的速度，因此Spark更適合進行數據挖掘與機器學習等需要迭代處理算法的實現[19-21]。Spark集群啟動時包括一個Master節點和若干個Worker節點，其中Master節點主要負責集群資源的管理，Worker節點主要負責數據的計算。當在Master節點使用spark-submit命令提交作業時，首先在本地客戶端啟動一個Driver進程；Driver進程會根據設置的參數向Master節點申請相應的集群資源，主要有Worker節點個數、每個Worker節點上Executor的內存和CPU數量；Master節點與Worker節點進行通信，通知Worker節點啟動Executor并向Driver進程注冊；Driver進程與Worker節點連接起來，將需要執行的任務分配給集群中的各個Worker節點，Worker節點按照任務分配從HDFS上讀取數據并緩存到內存中，Driver進程對各個Worker節點處理完的結果進行收集和匯總。在Spark平臺實現基于圖游走的協同過濾算法能夠有效地提高算法的時間效率。

4.2 相似性計算的并行化

由于皮爾遜相關相似度計算公式較為復雜，全局搜索較多，因此在實現本文方法并行化時引入中間變量，反映了用戶在項目上的相似度權重，計算公式如下：

4.3 基于圖游走的協同過濾算法并行化流程

基于圖游走的協同過濾推薦算法在Spark平臺上的并行化包括3部分，分別是讀入數據創建RDD、計算用戶的相似度以及生成推薦列表，該算法的并行化主要體現在計算用戶相似度和生成推薦列表。基于圖游走的并行協同過濾推薦算法示意圖如圖3所示。

具體過程如下：

1) 讀入用戶行為數據，構建RDD1；

2) 將 RDD1轉換成形式的 RDD2，按照用戶ID進行聚集得到RDD3，使用flatMap算子計算每個用戶的中間變量，并按照項目ID進行聚集得到RDD4；

3) 根據 RDD4計算用戶和用戶的，得到形如的RDD5,其中的1和toNum是為了便于計算交占比系數而設置的；

4) 將3)的RDD5使用ReduceByKey算子統計其共同評分項，計算結合交占比系數的相似度，得到形如的 RDD6；

5) 利用4)的相似度RDD6，構造用戶相似度矩陣userMatrixRDD，使用Spark中的線性代數庫Breeze，調用其庫函數 inv()計算userMatrixRDD的逆矩陣invMatrixRDD，進一步通過式(7)和(8)求得得間接相似度，重建相似度矩陣得到RDD7；

6) 根據RDD7按用戶劃分得到RDD8，并進一步得到目標用戶的近鄰用戶集合RDD9，最后進行推薦。

5 實驗與評價

實驗使用Movielens數據集和IPTV數據集[20]進行實驗。Movielens是一個基于Web的研究型推薦系統，用于接收用戶對電影的評分并提供電影的推薦列表，Movielens數據集在協同過濾研究領域得到了廣泛研究，也是使用最多的數據集之一。IPTV數據集來源于天津市IPTV電視用戶的收視日志數據，經過對日志數據進行預處理和隱式評分處理，形成IPTV數據集。相比于Movielens數據集，IPTV數據集應用性更高。Movielens-100k數據集包含943用戶，1 682項目，共10萬條評分記錄；Movielens-1M數據集包含6 040個用戶和3 952個項目， 共計100萬條評分記錄。IPTV數據集選取193用戶，8 200項目，共計43 175條評分記錄。

以加速比作為可擴展性的實驗指標，加速比為

5.1 相似度交占比系數的有效性驗證實驗

在原始的皮爾遜相關相似度的基礎上，為了比較加入交占比(YPCC)和未加入交占比(PCC)對預測評分誤差的影響進行本次實驗。此次實驗使用Movielens-100k數據集，共943用戶，1 682個項目，共10萬條評分記錄，稀疏度為94.12%，訓練集和測試集按8：2分割。實驗結果如圖4。

圖 4 交占比系數有效性驗證實驗Fig. 4 Trial ratio validity validation experiment

從圖4中可以看出，協同過濾推薦算法的預測評分誤差受到近鄰用戶個數Top-K的影響。隨著近鄰用戶個數Top-K的增加，PCC和YPCC曲線均呈現下降趨勢并最終趨于穩定，但是YP-CC曲線明顯低于PCC曲線，尤其Top-K在[40,60]時差距最明顯。實驗結果表明，無論近鄰用戶個數如何選取，在皮爾遜相關相似度上加入交占比系數均可以有效地減小評分預測誤差。

5.2 基于圖游走方法的有效性驗證實驗

5.2.1 Movielens數據集實驗

為了驗證基于圖游走方法在降低評分預測誤差和提高推薦準確率上的有效性，本次實驗使用Movielens-100k數據集，訓練集和測試集按8：2分割。先通過實驗確定用戶直接近鄰個數T的最優取值，然后比較在不同的推薦近鄰個數Top-K下，本文方法和基于用戶的協同過濾推薦算法(BSCF)與基于聚類的協同過濾推薦算法(kmeans_CF)的和。

圖5為選取不同直接近鄰個數時的評分預測誤差曲線，T表示直接近鄰用戶選取的個數。圖5表明，當T＞60時，趨于穩定。

圖 5 參數T測試圖Fig. 5 Parameter T test chart

圖6 的實驗中T=60。推薦時近鄰用戶個數Top-K作為單一變量，對基于圖游走的協同過濾推薦算法(GW_CF)、基于用戶的協同過濾推薦算法(BSCF)、基于聚類的協同過濾推薦算法(kmeans_CF)進行對比實驗。圖6Top-K表示推薦時近鄰用戶選取的個數，表示評分預測的平均絕對誤差。從圖中可以看出，隨著近鄰用戶個數Top-K的增加，3條曲線均呈下降趨勢，BSCF曲線和k-means_CF曲線比較接近，GW_CF曲線明顯低于另兩條曲線，當Top-K大于80時更加明顯。實驗結果表明：GW_CF算法在降低評分預測誤差方面是有效的。

圖7中虛線反映了使用GW_CF推薦的準確度，實線反映了使用BSCF推薦的準確度。生成推薦列表時推薦項目數為10，從圖中可以看出，隨著近鄰用戶個數Top-K的增加，兩條曲線呈上升趨勢，GW_CF準確率曲線高于BSCF曲線。實驗結果表明，基于圖游走的協同過濾推薦算法GW_CF可以有效地提高推薦準確率。

圖 6 圖游走效果圖Fig. 6 Random walk effect graph

圖 7 準確率對比圖Fig. 7 Accuracy comparison chart

5.2.2 IPTV隱式評分數據集實驗

為了驗證基于圖游走方法在降低評分預測誤差和提高推薦準確率上的有效性，本次實驗使用IPTV數據集，訓練集和測試集按8：2分割。先通過實驗確定用戶直接近鄰個數T的最優取值，然后比較在不同的推薦近鄰個數Top-K下，基于圖游走的協同過濾推薦算法(GW_CF)和基于用戶的協同過濾推薦算法(BSCF)的和。

圖8為選取不同直接近鄰個數時的評分預測誤差曲線。 圖8表明，當T＞20時，趨于穩定。

圖 8 參數T測試圖Fig. 8 Parameter T test chart

圖9 的實驗中T=20，推薦近鄰用戶Top-K作為單一變量，對基于圖游走的協同過濾推薦算法(GW_CF)和基于用戶的協同過濾推薦算法(BSCF)進行對比實驗。從圖9 中可以看出，隨著近鄰用戶個數Top-K的增加，兩條曲線均呈下降趨勢，GW_CF曲線明顯低于BSCF曲線。實驗結果表明：GW_CF算法在降低評分預測誤差方面是有效的。

圖 9 圖游走效果圖Fig. 9 Random Walk Effect Graph

圖10 中生成推薦列表時推薦項目數為10，隨著近鄰用戶個數Top-K的增加，兩條曲線呈上升趨勢，GW_CF準確率曲線趨勢更明顯并且高于BSCF曲線。實驗結果表明，在一般情況下，GW_CF比BSCF擁有更高的推薦準確率。

圖 10 準確率對比圖Fig. 10 Accuracy comparison chart

5.3 基于圖游走的并行協同過濾推薦算法可擴展性實驗

為了驗證基于圖游走的并行協同過濾推薦算法的可擴展性，使用Movielens-1M和Movielens-100k數據集在Spark平臺進行實驗。其中1M數據集包含6 040個用戶和3 952個項目，共計100萬條評分記錄；100k數據集包含943用戶，1 682項目，共10萬條評分記錄。實驗在Spark集群上實現，集群環境包括6個節點，一個Master節點，5個worker節點，每個節點的配置相同，且處在同一個局域網內，操作系統為CentOs6.5，CPU為E5-2620 v4，核心頻率2.10 GHz，節點內存32 GB。加速比結果如圖11。

圖 11 加速比示意圖Fig. 11 Speed-up ratio graph

從圖11中可以看出，隨著節點個數的增加，加速比呈現上升趨勢，100萬數據集更逼近線性加速比。實驗結果表明，并行協同過濾推薦算法在大規模數據集的情況下有較好的可擴展性。

6 結束語

本文針對協同過濾推薦算法中的數據稀疏性問題和可擴展性問題進行研究。針對稀疏性問題，在基于用戶的協同過濾推薦算法的基礎上，首先為傳統的皮爾遜相關相似度引入交占比系數來計算用戶的直接相似度，其次提出一種基于圖游走方法來計算用戶間接相似度，并重建相似度矩陣和進行推薦。針對可擴展性問題，在Spark平臺上實現本文方法的并行化。通過在Movielens數據集和IPTV數據集上進行實驗，先后驗證了加入交占比系數和基于圖游走的方法在提高推薦準確度上的有效性，以及本文方法的可擴展性。實驗結果表明，本文的方法在提高推薦準確度上是有效的，并且在大規模數據上擁有較好的可擴展性。