基于級聯二部圖的動態(tài)推薦算法

蔣宗禮，陸 晨

（北京工業(yè)大學 計算機學院，北京100124）

0 引 言

推薦系統(tǒng)的研究已經有了20多年的歷史[1]。很多系統(tǒng)都提供了推薦功能，努力向用戶推薦用戶可能感興趣的某類對象。例如，Google給用戶推薦新聞；Netflix、Youtube等視頻網站為用戶推薦他們可能喜歡的視頻[2]；Facebook和Twitter為用戶推薦他們的潛在好友；豆瓣向用戶推薦他們感興趣的圖書和資料。這些推薦不僅給用戶提供了方便，而且也給運營商帶來收益。特別在電子商務領域，推薦系統(tǒng)具有良好的發(fā)展和應用前景[3]。例如，Amazon公司將推薦引入到電子商務后，其銷售額提高了30%之多。另外，研究人員還研究過推薦系統(tǒng)對YouTube網站所產生的影響[4]。

目前，推薦領域已經有了一些較成熟的方法:

Content Based （基于內容的推薦）算法[5，6]認為用戶會喜歡和他之前喜歡的物品類似的物品。算法會根據物品的屬性，找到與用戶喜歡的物品相似的一系列物品來推薦給用戶。推薦的根據是物品屬性的相似性。

Collaborative Filtering （協(xié)同過濾，以下稱CF）[7]不依賴于物品本身的屬性，而是通過分析大量的行為數據，從中找出特定的行為模式，根據用戶的興趣進行預測，并為用戶做出推薦。CF分為基于用戶的CF（以下稱User Based CF）和基于物品的CF （以下稱Item Based CF）[8]。

社會化過濾算法認為用戶的興趣和他的好友興趣存在共同點，從而通過對好友興趣的分析來預測用戶的興趣。

時間對于推薦系統(tǒng)是非常重要的。隨著時間的推移，用戶的興趣很容易發(fā)生變化。例如，一個用戶小時候喜歡看動畫片，長大后會更傾向于看動作片或體育片；物品受歡迎的程度也會隨時間變化，一個剛剛上映的電影往往要比上映很久的電影更受歡迎；某些社會焦點事件也會對特定物品的受關注程度產生影響。另外，任何在線系統(tǒng)也都是動態(tài)變化的。每天都有新用戶加入，老用戶離開，新內容被加入，老內容被移除。不僅如此，用戶的年齡、興趣、社會關系、所處的環(huán)境等也是時刻變化的。甚至是物品的流行程度、用戶對物品的評價也不是一成不變的。但是絕大多數推薦算法，都只考慮了靜態(tài)的屬性和關系，沒有將時間這一重要信息考慮進去，而時間與用戶的興趣有很大的相關性。

為了更好的刻畫時間對推薦準確度的影響，更準確地反映用戶對物品行為的時間效應，本文采用級聯二部圖來描述用戶和物品之間的關系。

1 基于二部圖的協(xié)同過濾

推薦的基本目標是向用戶推薦他可能感興趣的對象，這種 “興趣”就是用戶與被推薦對象 （物品、新聞……）之間的關聯關系。圖是表達這種關聯關系的基本數據結構，可以很好的刻畫用戶和物品之間的關系。因此圖模型常常被用來解決推薦領域內的很多問題[9，10]。

在圖中，用戶、對象均作為頂點。如果用戶A對物品B感興趣，則從頂點A到頂點B有一條邊，表現用戶對物品的興趣。在這里，我們可以忽略邊的方向，如此便得到了一個二部圖。

定義1 二部圖G＝（V1∪V2，E），其中V1∪V2是頂點的有窮集合，且V1∩V2＝Φ，E是邊的有窮集合。

例如，圖1就是表示3個用戶和4種物品的二部圖。這里V1＝｛用戶A，用戶B，用戶C｝，V2＝｛物品A，物品B，物品C，物品D｝。該圖表現出的是3個用戶對4種物品的不同的興趣。

圖1 面向User Based CF的二部圖

對推薦系統(tǒng)來說，可以以用戶為中心考慮問題，如圖1所示。這種User Based CF的方法通過分析用戶對物品的歷史行為信息，找到與該用戶興趣相似的用戶集合。然后，基于這些相似用戶的歷史偏好信息，為當前用戶進行推薦。

這種推薦算法的主要數據結構是用戶－物品關聯矩陣。該矩陣為0、1矩陣。矩陣的每一行代表一個用戶，每一列代表一個物品。如果用戶對物品有過歷史行為，則在矩陣的相應位置上記1，反之記0。

算法計算矩陣中每兩行之間的相似度，即計算用戶之間的相似度。在計算用戶之間相似度的時候，將矩陣中的每一行看作一個用戶對所有物品的偏好向量，使用式 （1），用Cosine相似度計算用戶之間的相似度

對于每一個用戶，利用與該用戶相似度最高的前N個用戶的歷史數據對其進行物品的推薦。

觀察圖1得知，用戶A對物品A、C感興趣，用戶B對物品B有過歷史行為，用戶C則喜歡物品A、C、D；通過圖1所示的二部圖，我們發(fā)現用戶A和C的興趣比較相似，就可以將用戶C喜歡而用戶A沒有喜歡的物品D推薦給用戶A。

也可以以物品為中心考慮問題，如圖2所示。

圖2 面向Item Based CF的二部圖

這種Item Based CF的方法是分析用戶的歷史行為，找到與該用戶所感興趣的物品類似的物品集合，隨后對用戶進行個性化推薦。這種算法的主要數據結構依然是用戶－物品關聯矩陣。

算法計算矩陣中每兩個列向量之間的相似度，即計算物品之間的相似度。在計算物品之間相似度的時候，我們將矩陣中的每一列看作所有用戶對特定物品的偏好向量，使用式 （1）的Cosine相似度方法計算物品之間的相似度。

對于每一個用戶，找到與該用戶歷史數據中的物品相似度高的物品進行推薦。

在圖2中，用戶A對物品A、C感興趣，用戶B對物品A、B、C均有過歷史行為，用戶C則喜歡物品A。從圖2我們又可以發(fā)現物品A與物品C都被同樣的用戶群體所喜歡，進而推斷出物品A和C的相似度比較高?；谶@個數據推斷，喜歡物品A的用戶C很可能也物品C感興趣，于是對用戶C做出推薦。

2 基于級聯二部圖的協(xié)同過濾

定義2 級聯二部圖G＝｛G1，G2，…，Gn｝，其中Gi＝（Vi，1∪Vi，2，Ei），且對于1≤i＜n，Vi，2＝Vi＋1，1，n稱為圖的級數。在Gi＝（Vi，1∪Vi，2，Ei）中，Ei表示Gi中頂點集合Vi，1到Vi，2的權重的集合。權重的大小刻畫了Vi，1與Vi，2的緊密程度。

一個級聯二部圖是n個二部圖的并。其第i個二部圖的第二部分頂點是第i＋1個二部圖的第一部分頂點。圖3是一個二級級聯二部圖。

圖3 二級級聯二部圖

二級級聯二部圖就是將兩個二部圖相連。通過圖3可以看出，原本用戶和物品之間的單一關系，經過二部圖的組合，用戶之間便通過物品中間節(jié)點關聯起來:注意到分列在級聯二部圖左右的兩組不同用戶頂點，都有可能指向同樣的物品，由此可以得到用戶與用戶之間的關系。通過用戶之間的關系，就可以得到用戶之間的相似度，進而對用戶進行推薦。在圖3中，用戶A和用戶D、F都對物品A有過行為，因而用戶A與用戶D、F很可能是有一定相似度的，而與用戶E的相似程度比較低。

可以通過以下的步驟來計算左右兩側頂點之間的相似度:

首先，為了保證每個用戶對物品行為的合理性，要對Gi＝（Vi，1∪Vi，2，Ei）中邊的集合Ei進行權重歸一化處理，如圖4所示。

圖4 歸一化權重

圖4 中左右兩側邊的權重分別是使用式 （2）所示的兩種歸一化方法得到的

其中Ei，v表示Gi中以頂點v為起點的邊的集合。還可以根據具體需要使用其他的歸一化方法。

其次，推薦領域中有一個經典的 “哈利波特問題”，即有一些物品是非常大眾化的，沒有區(qū)分度。比如哈利波特的小說有成千上萬人看過，奧運會也幾乎人人都看，但這些都不能明確代表一個人的喜好，如圖5所示。

圖5 計算中間節(jié)點懲罰值

在圖5中，物品A被所有的用戶喜歡，因此物品A對于判別用戶之間的相似度作用不大。因此，我們需要對中間節(jié)點做一個適當的懲罰，以得到更好的推薦效果。

定義3G＝｛G1，G2｝的二級級聯二部圖中，G1的V1，2，也就是G2的V2，1所含的頂點為G的中間節(jié)點。中間節(jié)點懲罰值P為

其中，Ei，v＇表示Gi中以頂點v＇為終點的邊的集合。

接著，利用之前兩步得到的結果，計算左右兩側頂點之間單條路徑的距離。單條路徑如圖6中虛線所標注，圖中有兩條連接用戶B和用戶F的路徑，其中每條路徑的距離由3部分組成:左側邊權重，右側邊權重和中間節(jié)點的懲罰值。計算時，將三部分進行連乘，得到的結果就是整個路徑的距離

圖6 計算單條路徑權重

利用上面的式 （4）、式 （5）可以計算出圖6中用戶B到用戶F兩條路徑的長度，分別為0.33×PA×0.707和0.33×PC×0.707。

最后，可以計算左右兩側頂點的相關度了。為此，引出頂點相關度的定義。

定義4G＝｛G1，G2｝是一個二級級聯二部圖，G1的V1，1的頂點A與G2的V2，2的頂點B之間的相關度為

兩個頂點的相關度可以用連接這兩個頂點的所有路徑的權重之和來表示。如圖6所示，用戶B和用戶F的相關度就是圖中兩條虛線的權重之和。

總結上面的推薦步驟，可以得到基于級聯二部圖的協(xié)同過濾算法。

算法 基于級聯二部圖的協(xié)同過濾

（1）對級聯二部圖中連接用戶頂點到物品頂點的邊的權重進行歸一化，保證用戶對物品行為的合理性。

（2）計算中間節(jié)點的懲罰值，保證推薦的結果更加真實準確。

（3）計算出級聯二部圖中左側節(jié)點到右側節(jié)點的路徑的距離。

（4）將相同起止節(jié)點的距離相加得到級聯二部圖中左側節(jié)點和右側節(jié)點的相關性。

（5）取出前N個最相似的用戶或物品進行協(xié)同過濾推薦。

對于經典的User Based CF，可以首先使用User－Item－User的級聯二部圖計算User－User的相似度，然后再使用User－User－Item的級聯二部圖計算User－Item的相似度，將前N個與User最相似的Item推薦給該User。

對于Item Based CF，類似地，先使用Item－User－Item級聯二部圖得到Item－Item的相似度，然后使用User－Item－Item的級聯二部圖得到User－Item的相似度，同樣將前N個與User最相似的Item推薦給該User。

下面我們以User Based CF為例，具體加以說明。

圖7 User－Item－User級聯二部圖

可以通過User－Item－User的級聯二部圖，計算出User－User的相似度。圖7所示，可以計算出用戶A和用戶D與用戶F的相似度。同理，也可以得到所有其他用戶之間的相似度。

利用上一步得到的User－User相似度，我們可以構造出新的級聯二部圖，User－User－Item級聯二部圖。如圖8所示。

圖8 User－User－Item級聯二部圖

其中，左邊的User－User二部圖是根據上面圖7中計算的User－User相似度得到的。而User和User頂點之間邊的權重就是上一步所計算出來的相似度的值。右半邊二部圖是根據用戶的歷史記錄生成的，邊的權重為歸一化結果。以用戶A為例，用戶A和用戶D與F相似，通過用戶D與F，用戶A可以與物品A、B、C相連，而用戶A本身對A和C有過行為，因此系統(tǒng)會將物品B推薦給用戶A。當然，值得注意的是，這里只是用3個物品進行舉例說明，如果物品數量比較大，我們要找到與用戶相似度最高的前N個物品進行推薦，即所謂的Top－N推薦。

實驗證明，這種級聯二部圖的方法非常適合解決推薦問題，推薦的正確率達到了比較高的水平。

3 時間因素

對于推薦系統(tǒng)來說，越高的推薦準確率就意味著越好的用戶體驗，更強的用戶黏度甚至是更高的收益。前面已經提到，時間因素對于推薦系統(tǒng)的重要性不言而喻。但是由于時間信息難以捕捉和量化，絕大多數的推薦算法并沒有將時間因素考慮在內。近些年來，隨著一些商業(yè)網站（如Netflix等）對帶有時間信息的用戶行為數據的公開，研究人員開始研究如何在推薦系統(tǒng)中加入時間因素[10－13]，以使得推薦系統(tǒng)具有更好的動態(tài)特性。

通過對時間因素的分析，不妨假設用戶最近的行為，往往價值大于用戶很久以前的行為。

在二級級聯二部圖G＝｛G1，G2｝中，對于G中的Gi＝（Vi，1∪Vi，2，Ei），在不考慮時間時，Ei集合中的所有權重的值是通過歸一化來得到的。當考慮時間信息時，就不能簡單的為所有的邊賦予相等的權重，而是根據時間的遠近進行權重分配。為了更加真實地描述時間和用戶興趣的關系，采用下面的式 （7）來計算時間相關的權重

通過式 （7）可以看到:時間間隔T越大，et的值越小。經過時間權重分配后，級聯二部圖的各條邊權重被賦予了不同的值。如圖9所示。

圖9 利用時間間隔分配邊的權重

在對Ei進行了時間上的加權處理后，利用上面提到的級聯二部圖方法進行推薦的實驗。通過對推薦結果的分析發(fā)現，這種基于級聯二部圖的動態(tài)推薦在推薦的準確率上比靜態(tài)推薦又有了不少的提高。

4 實驗驗證

4.1 數據集

采用CiteULike論文數據集作基本的實驗數據集。這是一個隱性反饋的數據集，用戶可以收藏自己喜歡的論文并為論文打上標簽。這個數據集比較龐大，有124263個用戶，3997844篇論文，用戶和論文的關系數為5211046。之所以選擇這個數據集，最重要的原因是該數據集提供了收藏的時間信息，可以用來做時間相關的推薦。但是這個數據集比較稀疏，因此本實驗從中抽取了一個相對稠密的數據集，抽取的標準是收藏論文數大于5篇的用戶，以及被5個以上用戶收藏的論文。這樣，就將數據集精簡為用戶數45193，論文數68359篇，用戶與論文收藏關系數1530037個的數據集。

4.2 評價標準

衡量一個推薦系統(tǒng)的優(yōu)劣，有很多種評測的方法和角度[14，15]，本文使用推薦的命中率 （hit ratio）來對 Top－N 推薦進行評測。將整個的數據集分成訓練集Utrain和測試集Utest。對于每個用戶，把這個用戶最后一次對物品的行為取出放入測試集中，其他行為放入訓練集中。

給每個用戶推薦N（N＝20）篇論文，論文集合記為R（u，t）。如果在R（u，t）中剛好有一個物品在測試集中，我們就記一次命中

其中，I（Tu∈R（u，t））是一個示性函數，Tu是測試集中用戶行為針對的物品。

4.3 實驗結果

圖10給出了使用User Based CF，Item Based CF，結合時間的User Based CF與結合時間的Item Based CF的推薦命中率以及加入時間因素后，推薦準確率提高的比例。

圖10 4種推薦方式準確率

4.4 結果分析

從圖10可以看出，基于級聯二部圖的推薦方法很好地刻畫了協(xié)同過濾中用戶和物品之間的關系。無論是User Based CF還是Item Based CF，在推薦的準確率上的表現都是相當不錯的。不僅如此，相比于傳統(tǒng)的協(xié)同過濾中用戶物品矩陣向量相似度計算的方法，這種方法的效率大大提高，并不需要計算每一對用戶或物品的相似度，大大提高了開發(fā)和運行維護的效率。

另外，無論是User Based CF還是Item Based CF，在加入時間因素后，其推薦的準確率都有或多或少的提升。而User Based CF在加入時間后，其命中率更是提高了19.04%之多，效果還是非常明顯的。這也很好的驗證了我們前面的假設。

此外，Item Based CF的推薦效果要優(yōu)于User Based CF，很可能是由于該系統(tǒng)中，論文的數量和分類比較穩(wěn)定，而用戶的興趣和對論文的專注度變化比較頻繁所導致的。

4.5 結論和以后的研究工作

實驗表明，時間因素在真實系統(tǒng)中確實起著至關重要的作用，不能忽視。由此，也會自然的聯想到，除了時間，地點，動機等因素的變化，也會對用戶的真實意圖產生影響。因此要想對用戶進行精準的智能推薦，僅僅靠用戶的歷史數據和靜態(tài)屬性是遠遠不夠的，還要考慮時間，地點，動機等其他主觀和客觀因素，綜合對推薦結果產生影響。這也應該是未來推薦系統(tǒng)研究的一個目標和方向。

此外，在推薦系統(tǒng)中，推薦的準確率并不是衡量推薦系統(tǒng)的唯一指標。近年來，推薦的多樣性、驚喜度等其他指標也是推薦系統(tǒng)研究的熱點。在推薦準確率越來越高的基礎上，增加推薦的多樣性和驚喜度，無疑會使推薦系統(tǒng)更加人性化。

5 結束語

推薦系統(tǒng)是用戶和內容提供者之間的橋梁和紐帶，推薦系統(tǒng)的終極目標就是達到這兩者的雙贏和平衡。推薦系統(tǒng)的主要方法是通過用戶的歷史行為來預測用戶未來可能的行為。而在影響用戶行為的因素中，時間很少被考慮進來。本文使用一種全新的級聯二部圖的方法對推薦系統(tǒng)進行建模，并且合理的加入了時間這一動態(tài)因素。實驗證明:級聯二部圖的方法簡單、有效，時間的加入也對推薦的準確率起著一定的促進作用。

[1]LIU Jianguo，ZHOU Tao，WANG Binghong.The research progress of personalized recommendation system[J].Progress in Natural Science，2009，19 （1）:1－15 （in Chinese）.[劉建國，周濤，汪秉宏.個性化推薦系統(tǒng)的研究進展[J].自然科學進展，2009，19 （1）:1－15.]

[2]James Davidson，Benjamin Liebald，Liu Junning.The YouTube video recommendation system[C]／／RecSys Proceedings of the fourth ACM conference on Recommender Systems，2010:293－296.

[3]CAO Yi，LUO Xinxing.Research on recommending system of primary technologies in E－commerce[J].Journal of Xiangnan University，2008，29 （5）:63－66 （in Chinese）.[曹毅，羅新星.電子商務推薦系統(tǒng)關鍵技術研究[J].湘南學院學報，2008，29 （5）:63－66.]

[4]ZHOU Renjie，Samamon Khemmarat，GAO Lixin.The impact of YouTube recommendation system on video views[C]／／IMC Proceedings of the 10th ACM SIGCOMM conference on Internet measurement，2010:404－410.

[5]Raymond J Mooney，Loriene Roy.Content－based book recommending using learning for text categorization[C]／／The Fifth ACM Conference on Digital Libraries，2000，195－240.

[6]Souvik Debnath，Niloy Ganguly，Pabitra Mitra.Feature weighting in content based recommendation system using social network analysis[C]／／Proceeding of the 17th international conference on World Wide Web，2008:1041－1042.

[7]Yehude Koren.Factorization meets the neighborhood:A multifaceted collaborative filtering model[C]／／Proceeding of the 14th ACM SIGKDD International Conference on Knowledge Discovery And Data Mining，2008:426－434.

[8]Mukund Deshpande，George Karypis.Item based top－n recommendation algorithms[J].Journal ACM Transactions on Information Systems TOIS Homepage archive，2004，22 （1）:143－177.

[9]Shumeet Baluja，Rohan Seth，Sivakumar D，et al.Video suggestion and discovery for youtube:Taking random walks through the view gragh[C]／／Proceeding of the 17th international conference on World Wide Web，2008:895－904.

[10]Xiang Liang，Yuan Quan，Zhao Shiwan.Temporal recommendation on graphs via long－and short－term preference fusion[C]／／Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，2010:723－732.

[11]CONG Xiaoqi，YANG Huaizhen，LIU Meilian.On collaborative filtering algorithm based on time weight[J].Computer Applications and Software，2009，26 （8）:121－140 （in Chinese）.[叢曉琪，楊懷珍，劉枚蓮.基于時間加權的協(xié)同過濾算法研究[J].計算機應用與軟件，2009，26 （8）:121－140.]

[12]He Liang，Wu Faqing.A time－context－based collaborative filtering algorithm[C]／／IEEE International Conference Granular Computing，2009:209－213.

[13]Andreas T，Michael Jahrer，Bell R M.The bigchaos solution to the netflix grand prize，2009:1－52.

[14]Oscar Celma，Perfecto Herrera.A new approach to evaluating novel recommendations[J].In RecSys，New York，NY，USA:ACM.2008:179－186.

[15]LIU Jianguo，ZHOU Tao，GUO Qiang，et al.Overview of the evaluated algorithms for the personal recommendation systems[J].Complex Systems and Complexity Science，2009，6 （3）:1－10（in Chinese）.[劉建國，周濤，郭強，等.個性化推薦系統(tǒng)評價方法綜述[J].復雜系統(tǒng)與復雜性科學，2009，6 （3）:1－10.]