改進的協同過濾算法及其并行化實現

李 嵩，李書琴，劉 斌

(西北農林科技大學 信息工程學院，陜西 楊凌 712100)

0 引 言

為了及時準確地獲取有效信息，推薦系統不斷地發展。其中，協同過濾推薦算法應用最為廣泛[1]。然而，隨著時代發展，數據量極速膨脹，推薦系統中的數據稀疏性和可擴展性等問題在很大程度上影響著推薦的效果[2,3]，因此，國內外相關學者從不同的角度出發，采用不同的方法來解決這些問題。楊興耀等[4]提出一種基于信任模型填充的協同過濾推薦模型；Guo等[5]提出使用用戶信任的鄰居評分填充和代表用戶偏好；針對算法的可擴展性優化，李華等[6]提出一種基于用戶情景模糊聚類，并用Slope One算法填充評分的方法；Wang等[7]通過融合遺傳算法改進K-均值聚類，生成推薦；許偉等[8]提出基于聚類與矩陣分解技術結合的方式進行協同過濾推薦；李淋淋等[9]提出用聚類方式生成最近鄰居集，并用加權的Slope One算法進行推薦。

上述文獻中提出的算法仍存在填充后信息缺失或者聚類提取的信息量不夠的問題，也有的算法由于考慮因素過多，導致算法本身較為復雜，執行時間過長。且這些算法往往都忽略了用戶興趣與項目類別之間潛在的偏好關系，沒有充分挖掘用戶興趣。同時，以上大部分算法都側重于單節點實現，隨著數據量的指數級增長，單節點計算已經不能滿足需求。如今是大數據與云計算的時代，海量數據的多機并行化計算是一個不可避免的趨勢。因此，本文提出了基于GROUSE和用戶聚類的協同過濾算法，充分考慮用戶與項目類別之間的潛在關系，引入類別加權度的概念改進相似度計算，并在Spark大數據計算平臺上對算法進行設計與實現。

1 基于項目的協同過濾算法

傳統基于項目的協同過濾算法(item-based CF)以評分相似性程度為核心，以最近鄰集合為載體進行推薦。算法實現過程主要分為3個階段，首先構建用戶項目評分模型，然后計算項目之間的相似度以產生最近鄰集合，最后預測評分產生推薦。具體步驟如下。

(1)建立用戶項目評分模型

本文構建矩陣Rmn表示用戶對項目的評分，每一個行向量表示一位用戶的評分集合，共m個，每一個列向量表示一個項目的被評分集，共n個。矩陣中元素ru,i則表示用戶u對項目i的評分。評分矩陣可表示為

(2)計算相似度

相似度計算是協同過濾算法最重要的一步，其目的是為了描述項目間相似程度，產生最近鄰集合，其計算結果對推薦精度起著決定性作用。在常見的相似性計算模型中，皮爾遜相關系數因效果較好，最為常用[10]，其描述如式(1)所示

(1)

(3)預測評分

最終依據目標未評分項目與其最近鄰中的項目間相似性計算用戶對其的預測評分。預測評分模型可用式(2)進行計算

(2)

得到預測評分后，按照Top-N原則對用戶進行推薦。

2 基于GROUSE和用戶聚類的改進協同過濾算法

本文利用矩陣填充與對用戶做模糊聚類的思想，解決上述提到的數據稀疏性和可擴展性問題，并結合兩步的處理結果構造目標用戶簇類的評分模型；同時，在算法中考慮用戶對不同項目類別的偏好不同，提出類別加權度的概念，用以改進相似度計算，在減少計算規模的基礎上，有效地提高了推薦精度。本文算法處理流程如圖1所示。

圖1 基于GROUSE和用戶聚類的改進協同過濾推薦

2.1 格拉斯曼秩1更新子空間估計法(GROUSE)

矩陣填充(matrix completion)是一個是通過尋找近似矩陣來逼近原缺失矩陣的技術。在強不相干條件下恢復低秩矩陣所要求的采樣數目是m>Crnlogn，其中m為可觀測元素數，r為矩陣的秩，n為矩陣階數，C是正常數[11]。由于一個用戶評價過的項目相比較項目總數來說極其有限，因此用戶評分矩陣中可觀測元素非常少，可以認為評分矩陣是一個低秩矩陣，具有用矩陣填充的方法解決數據稀疏性問題的可行性。

Balzano等[12]提出的格拉斯曼秩1更新子空間估計法(Grassmannian rank-one update subspace estimation，GROUSE)在相同的采樣下，對于高維低秩的數據矩陣，性能比IALM等常用的矩陣填充算法要好[13]。GROUSE算法基于代價函數的最小化，函數定義如式(3)所示

(3)

其中，S是觀測到的有缺失點的矩陣的一個子空間。由于GROUSE算法是一個追蹤子空間的算法，要適用于整個缺失矩陣的填充，還需要對算法做些改變。填充具體算法流程見表1。

表1 基于格拉斯曼秩1更新子空間估計的矩陣填充算法

(4)

2.2 用戶聚類

不同用戶對不同項目類別喜好程度不同，為了深入挖掘用戶興趣與項目類別間潛在關系，本文構造m×l的用戶項目類別矩陣，并基于該矩陣對用戶進行聚類。矩陣可表示為

該矩陣由n個l維的向量ti(i=1,…,n)構成，其中n和l分別是用戶和項目類別的數目，矩陣中元素ti,g表示用戶i對類別g中項目的評分次數。

在此基礎上，本文使用FCM(fuzzy C-Means)算法對用戶聚類。該算法的基本思想是同一個用戶可以以不同的隸屬度屬于多個類別，其價值函數表達式如式(5)所示

(5)

(6)

(7)

本文中用戶聚類的FCM算法描述見表2。

表2 FCM算法

本文通過FCM算法做用戶聚類，有兩個優點：其一，通過挖掘用戶興趣與項目類別之間的模糊特性，從本質上體現出兩者的潛在關系；其二，在做推薦時，只需要判定目標用戶所屬簇類，并在簇類內部做協同過濾推薦即可，這種方式能夠大幅降低用戶項目評分矩陣的維度，減少協同過濾搜索鄰居用戶的范圍，從而減少計算復雜度，有效提高可擴展性。

2.3 類別加權度的概念

傳統協同過濾算法僅僅以可觀測到的評分數值為依據進行計算，并沒有從其它角度挖掘用戶興趣，這種處理方式則會忽略一些有價值的潛在信息。以現實情況而言，用戶的興趣會有所偏好，對于不同的項目類別，用戶的偏好程度也不一樣。基于該實際情況，本文提出了類別加權度的概念，來表示用戶u對項目類別g的喜愛程度。具體的計算步驟如下：

步驟1 計算用戶u對項目類別g的評分權重

(8)

步驟2 計算用戶u對項目類別g的評分次數權重

(9)

步驟3 計算用戶u對項目類別g的類別加權度

(10)

其中，α是類別加權因子。

2.4 基于類別加權度改進的相似度計算

(11)

(12)

根據式(1)和式(12)并結合用戶聚類的結果，改進后的項目間相似度計算如式(13)所示

(13)

其中，Ui,j是用戶u所屬的簇類中對項目i和j都評價過的用戶集合。由此可見，類別加權度分別作用在原始評分與填充評分上使得用戶對不同類別的電影的評分有了不同的權重，考慮了用戶的興趣偏好，符合實際意義，且將用戶集合縮小為目標用戶所屬的簇類，大大減少了相似度計算量，提高了算法的運行效率，有效提高了算法的可擴展性。

2.5 本文算法的流程

基于上述分析，本文提出基于GROUSE和用戶聚類的改進協同過濾算法CF-GUC，結合圖1，算法流程如下：

(1)構建用戶項目評分矩陣R和用戶項目類別矩陣T。

(2)利用表1算法對原始矩陣R進行填充，得到近似矩陣R+。并用R+中元素補充R中相應位置的不可觀測元素，R中已有的元素不變，形成完整的評分矩陣R*。

(3)利用表2算法基于用戶項目類別矩陣T對用戶進行聚類，產生目標用戶所屬簇類，并與R*中的所有行向量取交集，得到類內評分矩陣R′。

(4)對于矩陣R′，利用式(11)基于類別加權度加權進行計算，得到加權后的類內評分矩陣記為R″。

(5)基于矩陣R″，利用式(13)計算項目間相似性，并產生目標項目的最近鄰居集Ki。

(6)根據步驟(5)的計算結果，利用式(2)做評分預測，得到項目評分預測值pu,i。

2.6 算法特性總結

綜合上述對本文所提出算法的描述，該算法具有以下優秀的特性：

(1)采用GROUSE算法矩陣填充，每次迭代時更新子空間的時間復雜度極小[13]，所需運行時間大大減少，有效地緩解了數據稀疏性；

(2)對用戶基于類別權重矩陣進行聚類，充分考慮了用戶興趣的偏好，且在目標用戶的所屬簇類內進行相似度計算，避免了一些無意義的運算，極大減少了計算復雜度，提高了算法的運行時效；

(3)對于不同用戶對不同類別的項目在選擇時有偏好這一實際情況，本文引入了類別加權度的概念，深入挖掘用戶興趣與項目類別之間的潛在關系，并從評分高低與評分次數兩個角度將權值作用于矩陣填充的結果之上，從而在一定程度上減少直接使用填充值計算所帶來的計算誤差。

3 基于GROUSE和類別加權度的協同過濾算法在Spark上并行實現

3.1 Spark大數據計算平臺

Spark是一個處理海量數據的快速、通用的并行計算框架，其核心是彈性分布式數據集(resilient distributed datasets,RDD)。RDD的最大特點是基于內存計算，可以降低硬盤I/O的帶來開銷，提高執行效率。理論上利用Spark平臺可以突破因為海量數據造成的存儲困難與計算復雜度高等限制，是提高系統可擴展性的有效方式。基于Spark實現的推薦算法有以下優點：

(1)所有的運算都基于RDD，其基于內存計算和懶加載的特性，對于諸如相似度計算等需要大量迭代的算法，優勢更加明顯，能夠大大減少推薦算法的執行時間。

(2)Spark支持多種分布式存儲結構，如HDFS、S3等，這為推薦系統在數據存儲上的無限擴展提供了理論上的可能性，使得推薦系統據可擴展性問題得到有效改善。

3.2 并行算法實現

3.2.1 矩陣填充的處理流程

GROUSE算法在進行矩陣填充時，需要依次對子空間進行迭代，盡管每次更新子空間的代價較小，但是在數據量極大的情況下依然會耗費大量的時間，由于子空間相互獨立，因此算法可以在Spark平臺上進行并行化的實現，以提高填充速度。本文參考吳文波等[14]關于奇異值分解的并行處理方法的研究，并結合GROUSE算法更新子空間代價函數每次只優化一列的特點，采用如下的填充過程：首先根據數據集構建轉置評分矩陣RT；然后將RT按列進行分片，形成多個小的子矩陣；之后利用GROUSE算法分別對各個子矩陣進行填充；最后合并各個填充子矩陣，生成填充矩陣，并與原始矩陣按照式(4)的規則進行整合。

首先讀入評分數據到RDD中，通過map操作將RDD中的每條記錄轉為鍵值對形式，其中鍵是用戶ID，值是一個Tuple(元組)，存儲形式為。然后通過groupByKey操作歸并，得到同一用戶ID的數據，放到新的RDD中，實現矩陣的分塊，在計算時Spark會把分塊派發給不同的節點，并根據GROUSE算法對矩陣進行填充。由于后續步驟需要的是填充矩陣與原始評分矩陣的融合，因此還需要將填充后的各RDD與初始讀入文件形成的RDD進行join與union操作，用填充數據來取代原本位置上沒有的數據，形成無缺失的數據矩陣，其輸出為新的評分數據文件output1。

3.2.2 用戶聚類的處理流程

首先構造用戶項目類別矩陣，讀入項目文件和評分文件，構建的存儲結構，其中genre表示項目類別，times表示用戶對該類別中項目的評分次數，通過accumulator函數創建累加器變量來實現統計，形成用戶項目類別的RDD。然后根據表2的算法描述，對該RDD進行聚類操作，聚類過程中借助Spark的broadcast(廣播變量)對共享變量廣播到各節點，通過map、reduceByKey等操作進行距離、隸屬度與類中心的計算與合并，聚類過程中用兩次迭代的價值函數的變化值來確定聚類是否結束。算法結束時，生成最終的隸屬度RDD，存放所有用戶對于各簇類的隸屬度，格式為，命名為uRDD。

聚類完成后還需要獲得目標用戶的所屬簇類。按照FCM算法最大隸屬度原則，找到目標用戶最大可能性歸屬的簇類以及該簇類中的用戶集合，并與output1文件生成的RDD通過join操作形成簇類內的評分RDD，命名為c_rRDD。

3.2.3 協同過濾推薦的處理流程

對目標用戶進行協同過濾推薦的過程，分為兩個階段：一是對簇類內的評分數據加權；二是進行協同過濾的相關計算。這樣在計算的時候就將所有用戶數據集縮小為目標用戶所屬簇類的數據集，達到了降維的目的，避免了一些無意義的計算，處理流程如下：

第一階段，構造類別加權度，對目標用戶所屬簇類中的評分數據進行加權。首先，對于評分權重w_ru,j，根據數據集構造的RDD，存儲用戶對該項目類別下項目的總評分，通過累加器與map操作得到用戶對每個項目類別的評分權重，生成新的RDD，存儲格式為，命名為w_rRDD；對于評分次數權重t_ru,j，采取同樣的處理方式得到RDD，存儲格式為，命名為w_tRDD。然后將w_rRDD和w_tRDD用類別加權因子α加權求和，生成格式為的RDD。最后通過該RDD中的類別加權度對c_rRDD中對應的評分進行加權計算，生成簇類內加權評分的RDD，格式為，命名為c_w_rRDD。

第二階段，進行協同過濾相關的計算。首先，計算項目間相似度，在式(13)的基礎上對c_w_rRDD進行轉換操作，計算元組中每個項目的評分均值以及評分與評分均值的差值，輸出為平均評分文件output2，用flatMap和aggregateByKey操作進行項目間配對與歸并，并通過mapValues進行配對項目間的相似度計算，形成simRDD。然后，計算最近鄰，轉換simRDD格式為，通過map操作對列表中的值進行排序，選出項目的k近鄰集合為kNeiRDD。最后，預測評分，在kNeiRDD中過濾出目標項目的近鄰集合，在c_w_rRDD中過濾出用戶對項目的實際評分，并將兩RDD做join操作，結合output2中的平均評分基于式(2)計算最終的預測評分。

4 實驗與分析

4.1 實驗數據集

本文實驗數據集來自MovieLens推薦系統(http://movielens.org)，其近似數據量描述見表3。每條評分記錄包括用戶ID、項目ID、評分、時間戳等4個屬性，評分為1到5，評分越高表示用戶對該電影的喜愛度越高[15]。

表3 MovieLens數據集描述

4.2 度量標準和實驗環境

本文用統計方法中的平均絕對誤差MAE(mean absolute error)度量指標來描述推薦質量，MAE值越小，則推薦精度越高。該指標的計算方法如式(14)所示

(14)

其中，pi為預測評分，ri為實際評分。

本文實驗所需的Spark環境分為單節點的本地模式和多節點集群模式，Spark版本1.6.1，Linux版本Cent OS 6.5。實驗環境硬件配置見表4。

4.3 實驗結果及分析

實驗1：選取最優類別加權因子α。本文以數據量為100 k的數據集為樣本確定參數α，訓練集取其中80%，測試集取其中20%。參數確定的原則是通過控制變量，來比較不同α取值時MAE值的大小。圖2的實驗結果是設置最近鄰個數k為50時取得，可以看到，當α=0.4時，本文算法得到最小的MAE值。

表4 實驗環境硬件配置

圖2 不同α取值下本文算法的MAE比較

實驗2:算法對比實驗

為了驗證本文算法的推薦效果，將本文改進算法與以下幾種常見的協同過濾推薦算法進行對比實驗：

(1)CF-mean：基于評分均值填充的CF算法；

(2)CF-UC：基于簡單用戶聚類的CF算法；

(3)Pearson-CF：基于皮爾遜相關系數的CF算法；

(4)CF-GUC：本文提出的改進算法。

按照實驗1中參數選取的結果，CF-GUC算法設置類別加權因子α=0.4，圖3描述了不同鄰居數下以上幾種算法的MAE值對比。可見在k>40時，基本所有的算法都趨于穩定。由于本文算法能夠有針對性地解決數據矩陣稀疏性問題，且將用戶關于電影類別的興趣進行了更深層次的挖掘，并依照用戶興趣對相似度計算進行了改進，可以看到在實驗范圍內的鄰居數目下，CF-GUC算法相比于其它算法推薦效果要好。當最近鄰居數k取30到40時，CF-GUC算法相比于CF-mean算法、CF-UC算法、Pearson-CF算法，MAE值分別降低了約3.31%，3.02%，6.48%。

圖3 不同鄰居數目下各算法的MAE比較

實驗3:算法執行效率測試。實驗環境如表4中所描述，比較表3中不同數據集在3種實驗環境下的執行時間。實驗結果如圖4所示。

圖4 不同環境下本文算法運行時間比較

圖4中，縱軸表示本文算法的運行時長，單位為分鐘，橫軸表示3種規模不同的數據集。從圖4中可以觀察到，在數據量較小的時候，單節點與兩種Spark集群運行時間基本差不多，這是因為Spark集群在計算的時候需要進行任務拆分與合并，這種資源調度消耗了較多的運行時間，因此在數據量較小的時候，集群的優勢并不能體現出來，甚至有時候會比單節點執行效率更低。隨著數據集規模的增大，集群的優勢逐漸凸顯出來，特別是Spark基于內存迭代計算的高效性也愈加明顯。在ml-1m的數據集上，3節點的Spark集群執行效率比單節點高約40.6%，4節點的Spark集群執行效率比單節點高約58.4%。可以看到，由于ml-10m的數據集規模太大，在單機狀態下已經無法進行計算，故沒有數據，而Spark集群依然能高效地完成計算任務，且4節點的Spark集群相較于3節點的Spark集群，計算效率仍有提高。但是，這并不能說明集群中節點數越多越好，在數據規模一定的情況下，節點數多了，反而會因為資源調度、網絡通信等過程降低執行效率。在實驗過程中，筆者還發現，大規模用戶聚類以及獲得目標用戶簇類等過程會耗費大量時間，因此從實際應用的角度出發，對于諸如矩陣填充、用戶聚類等可以離線計算的過程，可以放在離線部分處理，能夠進一步保證算法的執行效率。

通過上述3個實驗可以看出，本文提出的CF-GUC算法在推薦質量上有很大提高，且算法在Spark集群上的并行化執行，極大地縮短了其運行時間，大大提高了系統的可擴展性。

5 結束語

本文以解決傳統協同過濾推薦算法中存在的數據矩陣稀疏性問題和可擴展性問題為出發點，提出了基于GROUSE和用戶聚類的改進協同過濾推薦算法。算法首先通過GROUSE算法對評分矩陣做填充，以解決數據矩陣稀疏性問題，并引入類別加權度，對評分進行加權；其次，構造用戶電影類別矩陣，對用戶進行聚類；再次，在協同過濾推薦階段，在目標用戶所屬的簇類內進行相似度計算；最后實現了算法在Spark集群上的并行化，通過聚類技術和借助Spark計算平臺解決系統的可擴展性問題。

實驗結果表明，在同等條件下本文算法在推薦質量方面表現優秀，且通過聚類和算法在Spark集群上實現的手段，使得算法的執行效率也有了大幅提高。但是聚類參數是影響推薦精度的重要條件，Spark的分片以及代碼分發等也是影響計算效率的重要因素，這些參數的調優與配置有待進一步實驗與深入研究。