基于圖和改進K近鄰模型的高效協同過濾推薦算法

孟桓羽 劉 真 王 芳 徐家棟 張國強

1(北京交通大學計算機與信息技術學院 北京 100044)2(北京交通大學信息中心 北京 100044)3 (南京師范大學計算機科學與技術學院 南京 210023)

?

基于圖和改進K近鄰模型的高效協同過濾推薦算法

孟桓羽1劉 真1王 芳2徐家棟1張國強3

1(北京交通大學計算機與信息技術學院 北京 100044)2(北京交通大學信息中心 北京 100044)3(南京師范大學計算機科學與技術學院 南京 210023)

(huanyum@bjtu.edu.cn)

在互聯網高速發展的今天，推薦系統已成為解決信息過載的有效手段，能夠緩解用戶在篩選感興趣信息時的困擾，幫助用戶發現有價值的信息.推薦系統中的協同過濾推薦算法，因其領域無關性及支持用戶發現潛在興趣的優點被廣泛應用.由于數據的規模過大且稀疏的特點，當前協同過濾在算法實時性、推薦精確度等方面仍有較大提升空間.提出了GK-CF方法，通過建立基于圖的評分數據模型，將傳統的協同過濾算法與圖計算及改進的KNN算法結合.通過圖的消息傳播及改進的相似度計算模型對用戶先進行篩選再做相似度計算；以用戶-項目二部圖的節點結構為基礎，通過圖的最短路徑算法進行待評分項目的快速定位.在此基礎上，進一步通過并行圖框架對算法進行了并行化實現及優化.在物理集群環境下進行了實驗，結果表明，與已有的協同過濾算法相比，提出的GK-CF算法能夠很好地提高推薦的準確度和評分預測的準確性，并具有較好的算法可擴展性和實時性能.

協同過濾；社會網絡；圖模型；K近鄰；最短路徑

隨著信息技術和互聯網的快速發展，大眾對社會化網絡的參與和關注程度也越來越高，全球最大的社交網站Facebook的日用戶數量在2015年第4季度已經突破10億，國內的社交網站新浪微博日活躍用戶數也達到1億.據中國電子商務研究中心監測數據顯示，截止2015年12月，國內著名電商網站年度活躍用戶數增長至1.536億，同比增長70%.人們逐漸從信息匱乏的時代走入了信息過載的時代，用戶在海量信息中選擇自己可能感興趣的信息的難度也逐日增加.為了緩解用戶在篩選信息時的困擾，社會網絡推薦系統應運而生.據世界最大電商亞馬遜的統計，推薦系統對亞馬遜銷售額貢獻率在20%～30%.社交網絡推薦主要是指通過挖掘分析用戶在社交網絡中的社會關系或歷史興趣，結合推薦系統算法，對用戶進行各種推薦.比如，通過挖掘用戶在社交網絡中的好友關系從而為用戶推薦新的可能感興趣的用戶或者項目.

隨著20世紀90年代協同過濾算法的提出，推薦系統已經成為用戶用來對過量互聯網信息過濾的一種重要手段[1].作為推薦系統最重要且應用最廣泛的一種推薦算法，協同過濾算法的基本思想是根據用戶對項目或信息的偏好，發現項目或內容本身的相關性或者是發現用戶的相關性.例如，用戶甲和用戶乙對某類項目恰巧有相同的偏好，那么，協同過濾在對用戶甲進行推薦的時候，就會更看重那些曾經被用戶乙選擇過而用戶甲還沒有注意到的那些項目.由于協同過濾算法主要利用用戶項目評分矩陣來計算項目或者用戶之間的相似度，并不要求用機器可以理解的語言來對項目進行詳細的描述，屬于領域無關的，所以，學術界和工業界經常將協同過濾算法應用到社會網絡推薦中.

但是，當前的社會網絡用戶-項目二部圖中，用戶基數大但活躍度有限，因此，用戶項目評分數據集的密度很小，即稀疏度高.采用降維的矩陣分解算法，算法的計算復雜度過高，計算效率低.在采用奇異值分解(singular value decomposition, SVD)等矩陣分解的方法時，也容易導致過度擬合[2].此外，大多數社會網絡推薦算法假設推薦的項目之間是相互獨立的，僅著眼于用戶，使得推薦的精確度不高.

近年來，隨著分布式并行圖框架的出現，學術界和工業界將圖模型應用于社會網絡數據關系建模，并在利用高效的分布式并行圖框架的基礎上運用圖算法來支持機器學習和數據挖掘.針對當前研究中，數據稀疏度高算法效率低，以及算法推薦精確度不高這2個問題，本文提出一種基于圖模型和K近鄰(K-nearest neighbor,KNN)模型的GK-CF算法.為了解決社會網絡推薦中數據過于稀疏的問題，本算法將原有的評分數據使用加權無向圖的方式進行數據建模，圖節點和邊表示用戶、項目及其之間的關系，以利用圖的拓撲性質和基本的圖算法.同時，基于文獻[1]的研究發現用戶更容易接受來自有相似項目購買偏好的用戶的推薦，在本文中我們采用改進的K近鄰算法結合無向有權圖中消息的傳播，以及改進的相似度計算模型來進行相似用戶的篩選，使所得到的相似用戶更加精準.進一步地，算法通過圖的最短路徑算法來進行帶評分項目的快速定位和篩選，也降低了計算的復雜性.最后利用并行圖框架對算法進行了優化，使得本文提出的方法具有較好的實時性.

1 相關工作

2006年，美國著名的DVD租賃網絡Netflix為了推動推薦系統中評分預測問題的研究，舉行了Netflix Prize比賽，伴隨著大量研究人員的深入研究推動了學術界對推薦系統的研究.近年來社會網絡快速興起使得推薦系統的發展有了新的動力和時機.社會網絡可以很好地模擬現實社會，學術界和工業界對于如何利用社會網絡給用戶進行個性化推薦及對社會化推薦過程的建模方法進行了廣泛的研究.

作為推薦算法的典型代表，協同過濾算法近年來受到工業界和學術界的廣泛關注.協同過濾算法不需要預先獲取用戶或項目的特征，僅依賴于用戶的歷史興趣顯式或隱式反饋對用戶興趣建模，再根據所建模型為用戶進行推薦.在協同過濾算法中，顯式反饋指的是用戶曾經對項目有過的歷史評分或者報告，隱式反饋指的是用戶群的歷史購買信息、瀏覽信息、搜索模式和鼠標停留信息等.以基于用戶的協同過濾算法為例，其主要關注點是根據相似用戶曾有的對項目的歷史評分預測出目標用戶u對項目i的興趣度.其中，用戶之間相似度的計算有很多種方法，比較常見和普遍使用的就是根據2個用戶對共同關注過的項目的歷史評分來進行皮爾斯相似度和余弦相似度[1]的計算.

學術界在余弦函數和皮爾斯函數的基礎上已經提出了大量的提高算法準確度和表現的算法，如用戶倒排評分、實例擴展[3]和主流加權預測[4].Park等人[5]提出了一種基于KNN圖的協同過濾算法.KNN圖的構建基于對項目的貪婪過濾，從而確定與每個項目最相似的前K′個項目列表.然后從當前用戶未評分項目中篩選出其K′個項目與目標用戶曾經評分項目集合的交集為K的項目，再計算目標用戶對其的評分.在降低計算復雜度的同時保持了算法的精度.但算法的主要關注點放在用K近鄰圖來提高尋找相似用戶的效率上，縮小了需要計算的未評分項目的范圍，而且此算法不能預測目標用戶對所有未評分項目的興趣度.Das等人[6]利用二叉樹剖分技術提出了一種將用戶所在區域分解后僅利用與用戶相關的特殊區域的數據為當前用戶進行推薦的推薦算法，從而降低了計算的復雜度.Liu等人[7]提出了一種結合了用戶評分的全局偏好信息和每對用戶共同評分的上下文信息的啟發式相似度計算模型，來提高評分預測的準確性.Xiang等人[8]引入時間窗口信息區分用戶不同時間段的行為，提高評分預測的準確性.Ding等人[9]根據項目加入系統的時間引入相應的衰減因子提高推薦的準確性.Koren[10]利用時序圖對用戶的長期興趣和短期興趣進行區分，旨在更準確地定義用戶當前興趣，提高推薦準確性.孫光福等人[11]通過衡量用戶之間的關系尋找相似的鄰居用戶，提出了一種對用戶間的時序行為進行建模的方法并將基于該方法發現的鄰居集合成功融入到基于概率矩陣分解的協同過濾推薦算法中，提升推薦精度.Matook等人[12]提出了一種結合了熟人之間的推薦和歷史評分的推薦算法.Jia等人[13]提出了一種基于雙層鄰居選取策略的協同過濾推薦算法.Qin等人[14]提出一種融合信任和用戶情感偏好的協同過濾算法.此外，為了提高推薦的準確性，Alami等人[15]提出了一種結合2種啟發式方法進行相似用戶選擇及使用矩陣分解的方法發現相似用戶或項目的潛在特征的混合協同過濾算法.Santos[16]提出一種將心理模型理論、積極心理學中的共同臨時想法與傳統的協同過濾算法結合的基于用戶好奇心的混合推薦算法.

在基于圖的模型中，用戶與項目或者用戶與用戶或者項目與項目之間的關系往往是通過有向權圖或者無向權圖的方式來表示.通常情況下，圖中的節點表示用戶或者項目，圖中的邊被賦予了權值，用來表示用戶間和項目間的相似度或者用戶對項目的評分.在這些模型中，標準的方法只是利用與用戶節點或者項目節點有邊相連的節點來預測用戶對于項目的評分.例如，通過統計用戶節點和項目節點之間的距離來直接估計用戶對項目的評分[17-18].在一些文獻中[19-21]，目標項目節點或者用戶節點往往也通過沿著圖中的邊對其消息進行廣播來影響那些未與其直接連接的節點.

隨著云計算時代的到來，Zhu等人[22]提出了一種適用于云計算分布式處理環境下基于協同過濾的個性化推薦機制RAC.

不斷增長的數據規模也驅動了分布式并行圖框架系統的出現[23-24]，這些系統可以優化數據在集群環境中的布局，并將復雜的迭代算法在有數百億的頂點和邊的圖上進行分布執行.在并行圖方式下的圖算法的迭代效率要比普通的數據并行系統下的執行效率有數量級的提高[23].

2 評分數據表示及系統建模

2.1 評分數據描述

用u表示用戶，p表示項目.用戶歷史評分記錄中的用戶集合用U={u1,u2,…,un}表示，項目集合用P={p1,p2,…,pm}表示，則用戶歷史評分記錄可以用一個n×m的矩陣R表示，矩陣中的每一個元素rij表示用戶ui對項目pj的已有評價分數，且i∈1,2,…,n，j∈1,2,…,m.如果用戶集合中的某個用戶ui對項目集合中的項目pj尚未有過評分，則在R評分矩陣中與其對應的矩陣元素rij為空，R評分矩陣為

其中，評分矩陣R中元素存在已知值和空值，已知值表示當前行所代表的用戶曾經對當前列所代表的項目有過歷史評分，空值表示當前行所代表的用戶尚未關注當前列所代表的項目或者還未給項目做過評分.推薦算法的工作就是基于R中已有的評分值和其他相關信息對矩陣R中的空值進行預測.

2.2 基于無向有權圖的數據表示及系統建模

本文中，我們引入圖結構來對用戶項目歷史評分數據進行建模，基于并行化圖模型的推薦系統框架如圖1所示：

Fig. 1 Recommendation system architecture based on parallel graph framework圖1 基于并行圖模型的推薦系統架構

圖1中，最底層是支持大規模數據處理的并行集群環境，通過分布式處理引擎支持流式計算和分布式存儲.用戶在參與社會化網絡活動中形成的各種數據，通過圖的生成、圖的分割加載到底層的集群環境中，通過圖的消息傳播和匯聚及基于圖的計算，可以對基于圖的用戶數據做進一步處理，包括用戶過濾、用戶相似度計算、確定候選項目以及對項目進行評分.最終將用戶可能感興趣的結果推薦給用戶.

本文中，我們用無向有權圖的方式對原始的評分矩陣進行建模，假設用圖G表示用戶評分的歷史記錄.G=(V,E).其中，V={v1,v2,…,vn,vn+1,vn+2,…,vn+m}，對應上文所提用戶列表U和項目列表P的并集.其中v1～vn代表用戶列表U中的用戶u1～un;vn+1～vn+m代表項目列表P中的項目p1～pm.E代表圖中邊的集合，〈vi,vj〉∈E(i=1,2,…,n;j=n+1,n+2,…,n+m)代表用戶vi曾經對vj有過歷史評分，歷史評分用來表示邊的權值.圖G如圖2所示.則給用戶ui推薦項目的問題可以定義為：在當前的無向有權圖中，預測從用戶頂點vi到與之沒有邊相連的某一項目頂點vj之間在圖上的相關性.

Fig. 2 The undigraph with weight based on the users- items historical ratings圖2 用戶-項目歷史評分無向有權圖

在這里給出基于圖的評分數據模型的幾個定義：

定義1. 目標頂點的2-度關聯頂點.目標頂點vi的2-度關系頂點可以表示為集合：

{vj|〈vi,vj〉?E∧(?k)〈vi,vk〉∈E∧〈vk,vj〉∈E}，

即從圖中該目標頂點vi出發，若存在1個中間節點vk，經過2條不重復邊〈vi,vk〉以及〈vk,vj〉能夠到達的頂點vj為目標頂點vi的2-度關聯頂點.

定理1. 若以用戶頂點為目標頂點，則其2-度關聯頂點一定是用戶頂點.因為本文針對的用戶-項目歷史評分是二部圖結構，所有的邊都代表某用戶對某項目的評分，用戶之間或項目之間不存在邊.

證明略.

定義2. 用戶的n-度關聯項目.若從圖中某一用戶頂點vi出發，沿圖中的邊能夠到達的項目頂點，稱其為用戶vi的關聯項目，n表示從vi到達關聯項目經過的邊數.

定義3. 用戶與關聯項目的最短路徑.若e1,e2,…,en∈E,其中，ei是關聯于節點vi-1，vi的邊，交替序列v0e1v1e2…envn稱為聯接v0到vn的路.邊的數目n稱作路的長度.若一條路中所有的節點v0,v1,…,vn均不相同，稱作通路.從圖中某一用戶頂點vi出發到其關聯項目vj存在多條通路，則從節點vi到節點vj路徑中邊數之和稱為vi到vj的路徑長度，長度最小的路徑稱為vi到vj的最短路徑.

3 基于圖和改進KNN的協同過濾算法GK-CF

在傳統K近鄰算法中，對每個目標用戶uactive進行相似度計算時，都是對其計算與系統中所有剩余用戶的相似度，使得計算量較大且復雜度高，或者由于相似用戶的過濾過于隨機使得推薦的精確度不高.

為了選出K個相似用戶，傳統的用戶近鄰模型直接通過皮爾斯公式和余弦公式來計算2個用戶之間的臨近程度.

本文對上述方法進行了改進，主要解決2個問題：

1)K個相似用戶的選取問題；

2) 相似好友用戶與目標用戶uactive之間的相似度計算問題.

3.1 基于圖的相似用戶選取

文獻[1]指出相比傳統的基于評分的推薦，用戶更容易接受來自有相似項目購買偏好的用戶的推薦，因此本文在傳統協同過濾算法的基礎上，結合共同評分的上下文信息，在計算用戶相似度之前，先進行目標用戶uactive的相似用戶篩選，僅考慮那些曾經與目標用戶uactive有過共同選擇和評分的用戶，將其看作目標用戶uactive的相似用戶組，然后在目標用戶uactive與其相似用戶組間計算相似度.

按照2.2節前述基于圖模型的定義1，與目標用戶uactive有共同選擇和評分的用戶即為2-度關聯用戶，因此，篩選相似用戶問題可以描述為求目標頂點的2-度關聯頂點問題.

為了確定目標用戶uactive的2-度關聯用戶，本文提出圖的消息傳播和聚合方法GraPA.

在GraPA方法中，圖中的頂點有3種狀態：1)未激活狀態，記為S0；2)被消息激活對消息進行廣播的狀態，記為S1；3)收到消息后對消息進行合并的狀態，記為S2.圖中每一個頂點vi維護的消息可表示為vList=(vidi，Li)，其中vidi表示頂點vi的ID，Li表示在傳播過程中到達頂點vi的其他頂點ID的集合，初始化為Li=(vidi).全圖頂點按照離散的等間隔時間序列在3個狀態間進行狀態轉換，完成消息的傳播和聚合.圖的信息傳播和聚合的方法GraPA流程如算法1所示：

算法1. 基于時間步序列的圖信息傳播和聚合方法GraPA.

輸入: 無向圖G=(V,E)；

輸出: 無向圖G中所有頂點的消息列表List[(vid,Li)].

① 初始時刻，將圖中的所有頂點的狀態初始化為S0.

② 在時間步T=2n-1，所有頂點均作為發布消息的源節點，沿著以當前廣播消息頂點vi為源頂點的邊e〈vi，vj〉廣播vi頂點的Li至頂點vj，這是圖的消息傳播.

③ 在時間步T=2n，所有頂點將時間步T=2n-1時收到的不同源頂點廣播來的頂點，如Lj,Lp,…,Lk合并起來，同時將合并后的集合L=Lj∪Lp∪…∪Lk作為頂點vi的更新后的Li.這是圖的消息聚合.

從圖的初始時刻開始，在經過1輪2個時間步后，每個用戶頂點所維護的Li即為該用戶的2-度關系用戶.

3.2 用戶相似度計算

在篩選出用戶的2-度關聯用戶后，接著計算2-度關聯用戶與目標用戶uactive之間的相似度.

如果用I來表示2用戶u和v曾經共同給過評分的項目集合，則傳統的皮爾斯公式計算用戶之間的相似度為

(1)

傳統的皮爾斯公式僅考慮2用戶曾經有過共同評分的項目，對于一方用戶曾經做過評分而另一方用戶尚未關注的項目不加考慮.但是這種擁有共同評分的項目數較少，使得用于計算2用戶之間相似度的數據過少，在一定程度上降低了用于推薦預測的信息量.因此，在本文中，我們考慮2用戶間一方有評分而另一方尚未評分的項目，假設用Iuv=Iu-Iv表示用戶u曾經有過評分而用戶v尚未評分的項目，并將用戶v對這一部分項目的評分統一賦值為常量C.同理用Ivu=Iv-Iu表示用戶v曾經有過評分而用戶u尚未評分的項目，同時將用戶u對這一部分項目的評分也統一賦值為常量C.將Iuv和Ivu這2個集合中的項目評分加入計算，則式(1)中，計算用戶評分與此用戶的評分均值的偏離度的平方和擴展為

(2)

式(1)中，除了計算I中項目涉及到的2個用戶評分與對應用戶的評分均值偏離度的乘積和

(3)

還將考慮Iuv和Ivu這2個集合中的項目，將式(3)擴展為

(4)

從而保證2用戶有足夠的評分項目信息量用于計算用戶之間的相似度.

(5)

(6)

綜上，本文提出用戶相似度的計算方法：

(7)

3.3 基于圖最短路徑的可推薦項目數計算

對于無向圖G=(V,E)中的一條路徑是指1個頂點序列P=v1v2…vk,其中每一對相鄰的頂點vi和vi+1之間都有1條邊,P也稱為從v1到vk的一條路徑.按照2.2節定義2和定義3，在一個無向圖中的節點vi到節點vi+1的最短路徑指的是從節點vi到節點vi+1路徑長度之和最小的路徑.

通過最短路徑尋找符合條件的項目的過程我們通過圖的消息傳播方式實現，此算法歸結為在無向圖G的拓撲節點中迭代執行特定的算法，shortPA算法流程如算法2所示：

算法2. 基于圖消息傳播的ShortPA算法.

輸入: 無向圖G=(V,E)、目標頂點的ID:TargetID；

輸出: 無向圖G中所有非目標頂點的頂點ID-屬性列表List[(VID,Vattribute)].

① forV-*初始化*-

② ifVid==TargetIDthen

changeVattr(Vid,0);

③ elsechangeVattr(Vid,∞);

④ end if

⑤ end for -*初始化各頂點的屬性為到目標頂點的距離，也即定義各非目標頂點到目標頂點的距離為無窮大，目標頂點到自身的距離為0*-

⑥ repeat；

⑦ begin Phase 1：并行化； -*圖中每條邊上的源節點沿著與其相連的邊向其目標頂點發送消息，當源頂點自身的距離屬性值加1小于目標頂點的屬性值時，設定源頂點的屬性值加1為當前要發送的消息，否則，設定要發送的消息值為空*-

⑧ ifsrcVattr+1

⑨ elsesentMessage(dstID,positiveInfitility)；

⑩ end if

由于評分數據圖的規模性，評分數據圖會進行分割得到評分數據子圖，為了保證對數據的并行處理，在算法2中，階段1、階段2及階段3均為可并行對各評分數據子圖進行分別處理的設計.

基于用戶的協同過濾推薦中用戶u對項目i的興趣度評分是通過綜合用戶u的其他相似用戶對項目i的評分而得到的：

ru,i=aggrsu∈Srsu,i，

(8)

其中，S表示用戶u的相似用戶中曾經給項目i做過評分的用戶的集合.為提高預測評分的精確度，在具體的算法[1]中，用戶u對項目i的評分ru,i通過式(9)進行計算：

(9)

其中，k是正則化因子，通常通過

求得，其中Isu代表用戶su曾經給過評分的項目的集合.

3.4 GK-CF算法及其并行化設計

本文提出的基于圖模型和改進K近鄰的協同過濾算法GK-CF，算法偽代碼描述如算法3所示：

算法3. 基于圖模型和改進K近鄰的協同過濾GK-CF算法.

輸入: 用戶-項目歷史評分數據ru,i；

輸出: 推薦項目列表List[Iid].

① 初始化:G:(V,E)←graphBuild(ru,i)；

-*G為無向有權圖，V={v1,v2,…,vn,vn+1,vn+2,…,vn+m},對應上文所提用戶列表U和項目列表P的并集.其中的v1～vn代表用戶列表U中的用戶u1～un.vn+1～vn+m代表項目列表P中的項目p1～pm.E代表圖中邊的集合.E〈vi,vj〉∈E代表vi所代表的用戶ui曾經對vj所代表的項目pj有過歷史評分*-

②U1={v1,vi,…,vn}←GraPA(G)； -*篩選出目標用戶uactive的2-度關系用戶*-

③unSortPearson={(v1,Pv1),(vi，Pvi),…,(vn，Pvn)}←improvedPearson(U1)； -*計算用戶集U1與目標用戶uactive之間的相似度*-

④U1′←SortByPearsonValueAndTakeTopK(unSortPearson,K)； -*根據其與目標用戶uactive之間的相似度進行排序后選出其前K個用戶作為目標用戶uactive的相似用戶集U1′*-

⑤I′={vm+1,vm+k,…,vm+n+1}←ShortPA(G,TargetID)； -*根據ShortPA算法篩選出符合條件的項目集*-

⑥unSortItemAttractive={(vm+1，Avm+1)，(vm+k，Avm+k+1),…,(vm+n+1，Avm+n+1)}←formulation(I′)； -*根據式(9)計算出目標用戶uactive對可推薦項目集I′={vm+1,vm+k,…,vm+n+1}中項目的興趣度*-

⑦List[Iid]={vm+1，vm+p,…,vm+n-2}←SortByAttractiveValueAndTakeTopN(unSortItemAttractive，K)； -*選擇預測值前top-N的項目作為推薦項目推薦給用戶*-

⑧ returnList[Iid].

GK-CF算法的輸入為根據用戶-項目歷史評分文件生成的基于并行計算框架Spark的彈性分布式數據集(resilient distributed dataset, RDD).RDD是不可變的帶分區的記錄集合，也是Spark中的編程模型，與并行計算框架Hadoop的MapReduce 2階段提交任務，任務間相互等待高時延不同，Spark提供了RDD上的2類操作：RDD本身的轉換(trans-formation)以及對RDD的動作(action).在Spark中，一段程序實際上就構造了一個由相互依賴的多個RDD組成的有向無環圖(directed acyclic graph， DAG)，將這個有向無環圖作為一個任務提交給Spark執行將完成在RDD上的各種操作.因此Spark任務之間不需要互相等待，對于迭代式數據處理性能好.并且Spark每次迭代的數據保存在內存中，使得Spark的性能相比Hadoop有很大的提升[23,25].

GK-CF算法中的每一步都進行了并行化設計，使得全圖數據得以并行化處理.其中，算法3中的步驟②和步驟⑤分別對應算法1和算法2,算法3中的步驟③(計算用戶集U1與目標用戶uactive之間的相似度)和步驟⑥(根據式(9)計算出目標用戶uactive對可推薦項目集I′={vm+1,vm+k,…,vm+n+1}中項目的興趣度)是另外2個重要步驟，對其并行化設計說明如下：

步驟③中，為了并行計算目標用戶uactive和其2-度關系用戶U1間的相似度，將計算相似度任務劃分為4個不同的子任務：

2) 通過對用戶-項目歷史評分RDD及用戶平均評分RDD進行連接(join)，map操作求出目標用戶uactive和其2-度關系用戶集U1={v1,v2,…,vn}中每個用戶vu的評分均值偏離度RDD及其評分均值偏離度平方和RDD；

3) 再通過map操作將評分均值偏離度RDD做鍵值對中的key-value值交換后通過join操作將與目標用戶uactive相關的評分偏離度RDD和與其2-度關系用戶集U1中用戶相關的評分偏離度RDD的笛卡兒積求出后，通過map操作求出目標用戶uactive與其對應的2-度關系用戶的評分均值偏離度的乘積RDD；

4) 通過對評分均值偏離度的乘積RDD及評分偏離度平方和的一系列join及map操作后獲取目標用戶uactive及其2-度關系用戶間的相似度RDD.

同理，步驟⑥中的任務也可以分為2個子任務：

1) 通過求和(sum)和map操作計算出式(9)中的正則化因子k；

2) 基于算法步驟③中計算出的目標用戶uactive與其2-度關系用戶間的評分偏離度RDD、相似度RDD、目標用戶平均評分RDD以及步驟⑥中計算出的正則化因子k通過join、過濾(filter)、map等一系列操作完成用戶u對項目i的評分ru,i.

3.5 算法復雜度分析

由于推薦算法涉及對海量數據的處理，除了推薦結果的準確性之外，算法本身的復雜度也是需要討論的.本文提出的GK-CF算法通過建立圖數據模型及子圖分割，實現了對原始海量數據的分布式并行處理，對其時間復雜度Ttime和空間復雜度Tspace分析如下：根據算法3的描述，算法3的主要步驟是計算目標用戶uactive的2-度好友集合(步驟②)、計算目標用戶uactive與其2-度好友間的相似度(步驟③)、基于圖的最短路徑計算可推薦項目(步驟⑤)及計算目標用戶uactive對可推薦項目的興趣度(步驟⑥).

1) 在計算目標用戶uactive的2-度好友集合過程中，根據算法1中圖的消息傳播和聚合算法GraPA，每個頂點均需向其鄰居頂點發送1次消息，假設圖中的頂點個數為N(N為用戶-項目評分文件中用戶U和項目數P之和)，邊的條數為E，則按鄰接表方式存儲圖的空間復雜度為O(N+E).1次消息傳播和聚合的時間復雜度為O(N)，2-度好友通過前后2次的消息傳播和聚合，時間復雜度仍然為O(N).眾所周知，用戶評分數據具有高稀疏性，通過無向有權圖對其建模后得到稀疏圖，不失一般性，1個稀疏圖其邊數和圖中節點數的關系表現為E≤(Nlog·N)-2.由于在此步驟中圖中的每一個頂點都要沿著它的鄰邊向它的鄰居頂點進行1次消息傳播，并在鄰居頂點進行存儲以完成聚合操作，因此需要在每個頂點開辟的額外存儲空間為2E≤Nlog·N.因此，此步驟中的空間復雜度為O(Nlog·N).

2) 在計算目標用戶uactive與其2-度好友間的相似度時，其時間復雜度主要表現為RDD進行1次map操作的時間，也即對圖中代表目標用戶uactive的2-度好友的頂點的屬性值進行1次變換修改操作的時間，因此，時間復雜度為O(N).在計算過程中需要將頂點數據的RDD存儲在內存中，RDD通常以〈目標用戶，2-度好友用戶，相關value〉的方式存在，則此步驟的空間復雜度為O(N).

3) 在基于圖的最短路徑計算可推薦項目中，由于尋找最短路徑需要進行3次消息傳播，因此此步驟的時間復雜度為O(N)，空間復雜度為O(Nlog·N).

① http:--grouplens.org-datasets-movielens-

4) 在計算目標用戶uactive對可推薦項目的興趣度中，此計算過程同樣需要將頂點的RDD以〈目標用戶，可推薦項目，興趣度〉形式存在內存中，其空間復雜度為O(N).此步驟時間復雜度與計算目標用戶uactive與其2-度好友間相似度的時間復雜度一樣為O(N).

綜合分析得出，GK-CF算法的時間復雜度為O(N),空間復雜度為O(Nlog·N+E).由于算法的每一步均為并行執行，在給定集群環境擁有多臺處理器數目的情況下，算法能夠在更短的時空范圍內完成計算.

通過具體的算法實現，對于同樣的社會網絡標準數據集MovieLens①，采用并行化方法設計實現的GK-CF算法在4.1節的實驗環境下運行效率為3.33·s，而串行方式下該算法的運行效率為31.53·s.本文提出的算法在6個節點的并行平臺上的運行效率較串行方式實現下的運行效率高出10倍.

上述2種算法的執行時間結果記錄如表1所示.本文同時以Wilcoxon秩和檢驗方法檢驗采用并行化方法設計實現的GK-CF算法較之串行方式的實現效率是否有顯著提升.

Table 1 The Descriptive Statistics of the Operation Efficiency of GK-CF and Serialized GK-CF

表1 GK-CF及其串行方式實現的運行時間的描述性統計

從表1中可以看出，GK-CF算法通過并行化的實現，其運行效率遠高于串行方法.基于Wilcoxon秩和檢驗方法對表1中數據進行了分析.

Wilcoxon秩和檢驗是一種非參數統計方法[26]，綜合了t_test和閾值誤判方法(threshold number of misclassification，TNOM)的良好特性，克服了t_test對于噪音敏感和TNOM會丟失數據中信息的缺點[27].Wilcoxon秩和檢驗法在檢驗樣本時，首先在符號檢驗的基礎上計算樣本的正、負號秩及其樣本秩的總和w及樣本的統計量概率p.如果樣本的統計量z的統計量概率p接近于0，則2配對樣本存在著顯著性的差異.其中，樣本統計量z計算為

z=[w-n1(n1+n2+1)-2]-

[n1n2(n1+n2+1)-12]1-2，

(10)

其中，n1為第1個樣本集的樣本容量，n2為第2個樣本集的樣本容量，w為第1個樣本集樣本的秩和.

檢驗結果如表2所示：

Table 2 The Wilcoxon Rank SumTest表2 Wilcoxon秩和檢驗

該結果顯示Wilcoxon統計量w和z皆拒絕GK-CF和其串行方式的算法運行效率相等的零假設.且樣本的統計量z的統計量概率p接近于0，2配對樣本存在顯著性差異，該檢驗表明，并行化設計實現的GK-CF較其串行方式的實現，在運行效率上有顯著提升.

4 實驗及結果分析

本節通過實驗繼續對本文提出算法的推薦效果進行驗證，討論了選取不同的用戶數和項目數對推薦結果的影響.并將本文提出的算法GK-CF同其他算法在真實的物理集群環境下進行了實現及對比.

4.1 數據集及實驗環境

實驗環境由6臺服務器組成云平臺集群，服務器運行的是Ubuntu14.04 64位系統，集群管理平臺為Spark1.1.0，每臺服務器節點包括一個4核CPU和8·GB內存.集群由1臺服務器作為Master節點，5臺作為計算節點.實驗中GK-CF算法與所有參與對比的算法均在Spark平臺上進行了并行化實現.

實驗采用大規模社會網絡標準數據集MovieLens①來驗證本文所提出的GK-CF算法能夠更好地進行社會網絡應用中對項目的推薦.

① http:--grouplens.org-datasets-movielens-

4.2 評價指標和實驗參數

為了使本文提出的算法能夠取得較好的推薦效果，我們分別對相似用戶數量和項目數量的選取進行了實驗.分別考慮了預測的均方根誤差(rmse)、準確率(precision)以及召回率(recall)三個評價指標.

(11)

令R(u)是根據用戶在訓練集上的行為為用戶做出的推薦列表，而T(u)是用戶在測試集上的行為列表，則推薦結果的準確率(precision)定義為

(12)

推薦結果的召回率(recall)定義為

(13)

表3對推薦的項目數不做限制的情況下，選取不同數量的相似用戶的實驗結果.通過表3可以看出，在重點考慮rmse的前提下，當用戶數取100時，能夠取得較好的rmse和recall，但precision略低.

Table 3 The Similar Users Number Choose Experiment表3 相似用戶數選取

Table 4 The Candidate Items Choose Experiment表4 候選項目數選取

1)rmse

評分預測的預測準確度一般通過rmse計算.

本文對4種算法進行了對比實驗，分別是：基于用戶的協同過濾算法(collaborative filtering algori-thm, CF)、基于評分數據矩陣及本文提出的改進KNN算法實現的K-CF算法、基于交替最小二乘的協同過濾算法(alternating least squares-collaborative filtering algorithm, ALS-CF)以及基于圖模型和改進KNN的GK-CF算法.在MovieLens①不同大小的數據集上分別運行上述算法.結果如圖3所示，GK-CF算法的rmse值遠低于基準CF算法、K-CF算法及ALS-CF，能夠達到0.89，比ALS-CF低8%.說明本文提出的算法在評分預測的準確度上是優于其他3種算法的.

Fig. 3 The rmse comparison of four algorithms圖3 4種算法的rmse對比

2)precision和recall

推薦結果準確率定義為推薦算法正確判定用戶對一個項目是否喜歡的比例.因此，當用戶只有二元選擇時，使用precision，recall指標來衡量推薦質量，比rmse更直觀.

① http:--grouplens.org-datasets-movielens-

② http:--webscope.sandbox.yahoo.com-catalog.php?datatype=r&did=3

本實驗除了前述4種算法CF，K-CF，ALS-CF，GK-CF，進一步加入了基于圖的隨機游走的算法(實驗中簡稱RW算法)參與對比.各算法在MovieLens①數據集上運行的precision和recall的實驗結果分別如圖4、圖5所示.從圖4可以看到，GK-CF的precision與ALS-CF相當，相對于其他3種方法優勢較為明顯，比基準CF算法precision提高25%.圖5中，GK-CF的recall相對于基準CF算法、ALS-CF算法，分別提高25%，14%.

Fig. 4 The precision comparison of five algorithms圖4 5種算法的precision對比

Fig. 5 The recall comparison of five algorithms圖5 5種算法的recall對比

本文也通過不同的標準數據集對GK-CF算法與其他算法進行了對比實驗.表5是GK-CF算法與ALS-CF算法在標準數據集Yahoo!Music 1·MB②上進行的對比實驗.實驗結果表明，GK-CF算法的recall仍高于ALS-CF算法的recall，并且GK-CF算法的precision比ALS-CF算法的precision提高了3%.

3) 算法運行效率

我們考察了在同樣節點規模的情況下，不同算法的運行效率.基準CF算法在前述實驗中犧牲precision，recall，rmse的情況下，運行效率較高.GK-CF與ALS-CF運行效率相當，說明，GK-CF在取得較好的rmse，precision，recall的情況下，并未以犧牲算法效率為代價.其實驗結果如圖6所示.

Table 5 TherecallandprecisionComparisons Between GK-CF and ALS-CF

表5 GK-CF 與ALS-CF算法的召回率及準確率對比 %

Fig. 6 The runtime comparison of five algorithms圖6 5種算法運行時間對比

GK-CF與ALS-CF在Yahoo!Music 1·MB②數據集上的算法運行效率如表6所示.GK-CF算法較ALS-CF算法運行效率高.

Table 6 The Algorithm Runtime Comparisons Between GK-CF and ALS-CF表6 GK-CF 與ALS-CF算法的運行時間對比 s

4) 加速比

在真實的物理集群環境下，節點的規模與并行算法的執行效率是相關的，本文通過GK-CF，RW及ALS-CF算法的加速比實驗，對算法在節點規模上的可擴展性進行了分析.如圖7在MovieLens①的1·MB規模數據集上，算法的加速效率較為明顯，當集群規模從1個節點變換到5個節點時，本文提出的GK-CF算法效率有近3倍的提升，與ALS-CF算法相當.說明本文提出的算法隨著節點規模的擴展有良好的可擴展性.RW算法的效率雖然比GK-CF和ALS-CF的算法效率低近15倍且當其運行于單個節點時算法效率過低，但其加速比有近7倍的提升，也說明對于基于圖模型的算法求解，適合于通過并行平臺來加速執行效率.

Fig. 7 The speedup experiment of three algorithms圖7 3種算法加速比實驗

5 總 結

現有的個性化推薦系統不僅需要處理海量、實時的數據，而且還要響應用戶多樣化的服務請求，如亞馬遜的個性化書籍推薦和YouTube的個性化視頻推薦.然而大多數推薦算法存在算法精確度不高、運行效率低等問題，導致推薦質量受限.本文提出了一種基于圖模型和改進KNN模型的GK-CF算法，并對算法進行了并行化的實現.通過建立圖數據模型及子圖分割，實現了對原始海量數據的分布式并行處理.利用圖拓撲結構及沿圖路徑信息傳播和聚合的方式提出了改進的KNN算法，用于對每個目標用戶的相似用戶篩選，并通過改進的皮爾斯公式處理由于用戶過多帶來相似度計算誤差，再利用圖的最短路徑算法對目標用戶的可推薦項目集合進行快速定位，最后根據目標用戶對項目的評分選出最終給用戶推薦的項目.我們在真實的集群環境下，利用標準數據集驗證了基于并行圖的GK-CF推薦算法的有效性.實驗結果表明，相對于基準CF算法、基于模型的ALS-CF算法以及基于圖結構的隨機游走RW算法，GK-CF算法有較好的rmse，precision，recall.同時并未以犧牲算法效率為代價.本文也通過算法復雜度分析、GK-CF算法的串行化和并行化的算法運行效率對比實驗和Wilcoxon秩和檢驗驗證了GK-CF由于其并行化設計實現具有較好的高效性，在未來的可擴展集群上也具有較好的算法可擴展性.

[1]Adomavicius G, Tuzhilin A. Toward the next generation of the recommender systems: A survey of the state-of-the-art and possible extensions[J]. IEEE Trans on Knowledge and Data Engineering, 2005, 17(6): 734-749

[2]Koren Y. Factorzation meets the neighborhood: A multifaceted collaborative filtering model[C] --Proc of the 14th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2008: 426-434

[3]Breese J S, Heckerman D, Kadie C. Empirical analysis of predictive algorithms for collaborative flitering[C] --Proc of the 14th Conf on Uncertainty in Artificial Intelligence. San Francisco, CA: Morgan Kaufmann, 1998: 43-52

[4]Delgado J, Ishii N. Memory-based weighted-majority prediction for recommender systems[C] --Proc of the ACM SIGIR’99 Workshop Recommender Systems: Algorithms and Evaluation. New York: ACM, 1999

[5]Park Y, Park S, Jung W. Reversed CF: A fast collaborative filtering algorithm using aK-nearest neighbor graph[J]. Expert Systems with Applications, 2015, 42(8): 4022-4028

[6]Das J, Aman A K, Gupta P, et al. Scalable hierarchical collaborative filtering using BSP trees[C] -- Proc of the Int Conf on Computational Advancement in Communication Circuits and Systems. Berlin: Springer, 2015: 269-278

[7]Liu Haifeng, Hu Zheng, Mian Ahmad, et al. A new user similarity model to improve the accuracy of collaborative filtering[J]. Knowledge-Based Systems, 2014, 56(1): 156-166

[8]Xiang Liang, Yuan Quan, Zhao Shiwan, et al. Temporal recommendation on graphs via long-and short-term preference fushion[C] --Proc of the 16th ACM Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2010: 723-731

[9]Ding Yi, Li Xue. Time weight collaborative filtering[C] --Proc of the 14th ACM Int Conf on Information and Knowledge Management, New York: ACM, 2005: 485-492

[10]Koren Y. Collaborative filtering with temporal dynamics[J]. Communications of the ACM, 2010, 53(4): 89-97

[11]Sun Guangfu, Wu Le, Liu Hong, el al. Recommendations based on collaborative filtering by exploiting sequential behaviors[J]. Journal of Software, 2013, 24(11): 2721-2733 (in Chinese )(孫光福, 吳樂, 劉洪, 等. 基于時序行為的協同過濾推薦算法[J]. 軟件學報, 2013, 24(11): 2721-2733)

[12]Matook S, Brown S A, Rolf J. Forming an intention to act on recommendations given via online social networks[J]. European Journal of Information Systems, 2015, 24(1): 76-92

[13]Jia Dongyan, Zhang Fuzhi. A collaborative filtering recommendation algorithm based on double neighbor choosing strategy[J]. Journal of Computer Research and Development, 2013, 50(5): 1076-1084 (in Chinese )(賈冬艷, 張付志. 基于雙重鄰居選取策略的協同過濾推薦算法[J]. 計算機研究與發展, 2013, 50(5): 1076-1084)

[14]Qin Jiwei, Zheng Qinghua, Tian Feng. Collaborative filtering algorithms integrating trust and preference of user’s emotion[J]. Journal of Software, 2013, 24(Suppl 2): 61-72 (in Chinese)(秦繼偉, 鄭慶華, 田峰. 一種融合信任和用戶情感偏好的協同過濾算法[J]. 軟件學報, 2013, 24(增刊2): 61-72)

[15]Alami Y, Nfaoui E, Beqqali O. Toward an effective hybrid collaborative filtering: A new approach based on matrix factorization and heuristic-based neighborhood[C] --Proc of the Intelligent Systems and Computer Vision(ISCV). Piscataway, NJ: IEEE, 2015: 51-58

[16]Santos A. A hybird recommendation system based on human curiosity[C] --Proc of the 9th ACM Conf on Recommender Systems. New York: ACM, 2015: 367-370

[17]Fouss F, Pirotte A, Renders J M, et al. Random-walk computation of similarities between nodes of a graph with application to collaborative recommendation[J]. IEEE Trans on Knowledge and Data Engineering, 2007, 19(3): 355-369

[18]Huang Zan, Chen Hsinchun, Zeng Daniel. Applying associative retrieval techniques to alleviate the sparsity problem in collaborative filtering[J]. ACM Trans on Information System, 2004, 22(1): 116-142

[19]Aggarwal C C, Wolf J L, Wu Kun-Lung, et al. Horting hatches an egg: A new graph-theoretic approach to collaborative filtering[C] --Proc of the 5th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 1999: 201-212

[20]Onuma K, Tong H, Faloutsos C. TANGENT: A novel, surprise me, recommendation algorithm[C] --Proc of the 15th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2009: 657-666

[21]Xiang Liang, Yuan Quan, Zhao Shiwan, et al. Temporal recommendation on graphs via long-and short-term preference fusion[C] --Proc of the 16th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2010: 723-732

[22]Zhu Xia, Song Aibo, Dong Fang, et al. A collaborative filtering recommendation mechanism for cloud computing[J]. Journal of Computer Research and Development, 2014, 51(10): 2255-2269 (in Chinese )(朱夏, 宋愛波, 東方, 等. 云計算環境下基于協同過濾的個性化推薦機制[J]. 計算機研究與發展, 2014, 51(10): 2255-2269)

[23]Xin R S, Crankshaw D, Dave A, et al. GraphX unifying data-parallel and graph-parallel analytics[DB-OL]. Computer Science Databases. 2014[2016-04-29]. https:--arxiv.org-abs-1402.2394

[24]Quick L, Wilkinson P, Hardcastle D. Using pregel-like large scale graph processing frameworks for social network analysis[C] --Proc of 2012 IEEE-ACM Int Conf on Advances in Social Networks Analysis and Mining. Piscataway, NJ: IEEE, 2012: 457-463

[25]Zaharia M, Chowdhury M, Das T, et al. Resilient distributed datasets: A fault-tolerant abstraction for in-memory cluster computing[C] --Proc of the 9th USENIX Conf on Networked System Design and Implementation. Berkeley, CA: USENIX Association, 2012: 15-28

[26]Deng lin, Pei Jian, Ma Jinwen, et al. A rank sum test method for informative gene discovery[C] --Proc of the 10th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2004: 410-419

[27]Xie Juanying, Gao Hongchao. Statistical correlation andk-means based distinguishable gene subset selection algorithms[J]. Journal of Software, 2014, 25(9): 2050-2075 (in Chinese)(謝娟英, 高紅超. 基于統計相關性與K-Means的區分基因子集選擇算法[J]. 軟件學報, 2014, 25(9): 2050-2075)

Meng Huanyu, born in 1990. Master. Her main research interests include recommender system, location-based social networks.

Liu Zhen, born in 1977. PhD, associate professor. Member of CCF. Her main research interests include recommender system, location-based social networks, cloud and virtualization.

Wang Fang, born in 1977. Associate professor. Member of CCF. Her main research interests include future network architecture, mobile and internet.

Xu Jiadong, born in 1991. Master. His main research interests include recommender system, location-based social networks.

Zhang Guoqiang, born in 1980. PhD, associate professor. Senior member of CCF. His main research interests include future network architecture, network science.

An Efficient Collaborative Filtering Algorithm Based on Graph Model and ImprovedKNN

Meng Huanyu1, Liu Zhen1, Wang Fang2, Xu Jiadong1, and Zhang Guoqiang3

1(SchoolofComputerandInformationTechnology,BeijingJiaotongUniversity,Beijing100044)2(InformationTechnologyCenter,BeijingJiaotongUniversity,Beijing100044)3(SchoolofComputerScienceandTechnology,NanjingNormalUniversity,Nanjing210023)

With the rapid development of Internet, recommender system has been considered as a typical method to deal with the over-loading of Internet information. The recommender system can partially alleviate user’s difficulty on information filtering and discover valuable information for the active user. Collaborative filtering algorithm has the advantages of domain independence and supports users’ potential interests. For these reasons, collaborative filtering has been widely used. Because the user item rating matrix is sparse and in large-scale, recommender system is facing big challenges of precision and performance. This paper puts forward a GK-CF algorithm. By building a graph-based rating data model, the traditional collaborative filtering, graph algorithms and improvedKNN algorithm have been integrated. Through the message propagation in the graph and the improved user similarity calculation model, candidate similar users will be selected firstly before the calculation of users similarity. Based on the topology of bipartite graph, the GK-CF algorithm ensures the quick and precise location of the candidate items through the shortest path algorithm. Under the parallel graph framework, GK-CF algorithm has been parallelized design and implement. The experiments on real world clusters show that: compared with the traditional collaborative filtering algorithm, the GK-CF algorithm can better improve recommendation precision and the rating accuracy. The GK-CF algorithm also has good scalability and real-time performance.

collaborative filtering; social network; graph model;KNN; shortest path

2016-04-26；

2016-10-20

國家重點研發計劃項目(2016YFB1200100)；國家自然科學基金項目(61202429,61572256)；中央高校基本科研業務費專項資金項目(2015JBM042)；江蘇省自然科學基金項目(BK20141454) This work was supported by the National Key Research and Development Program of China (2016YFB1200100), the National Natural Science Foundation of China (61202429, 61572256), the Fundamental Research Funds for the Central Universities (2015JBM042), and the Natural Science Foundation of Jiangsu Province of China (BK20141454).

劉真(zhliu@bjtu.edu.cn)

TP181