二階有向相似性對協同過濾算法的影響

石珂瑞， 劉建國

（上海理工大學 復雜系統科學研究中心，上海 200093）

協同過濾算法是應用最廣泛的一種推薦算 法［1－6］.它的核心思想是利用朋友的歷史選擇信息預測目標用戶的喜好程度.由于其具有較好的準確率，因此，得到了廣泛的應用，成為電子商務系統中解決信息超載的有效工具之一［7－8］.最近，基于物質擴散和熱傳導的方法已經被成功地引入到個性化推薦算法的研究中，用來度量用戶之間的相似性行為，并且取得了不錯的效果［3，9－10］.Liu等通過改變用戶相似度方向，提出了一種有向相似性的協同過濾算法［11］，該算法發現，增加度小用戶向度大目標用戶推薦的強度，可以極大地提高算法準確性和推薦列表多樣性.已有的統計結果表明，用戶的二階相似性可以大幅度提高推薦準確性［10］.本文構造二階有向相似推薦算法，綜合考察用戶的有向相似性和二階信息的影響，實驗的數值結果表明，利用鄰居用戶到目標用戶的二階相似性可以為目標用戶提供更加準確的推薦結果.

1 經典協同過濾算法

協同過濾算法的思想是：首先，計算用戶之間的相似性；其次，根據用戶之間的相似選擇行為對目標用戶進行推薦.定義產品集合為用戶集合為那么，推薦系統可以表示為矩陣其中，aij＝1，表示用戶ui選擇了產品oj；否則，aij＝0.在經典的協同過濾算法中，用戶ui和用戶uj的相似性根據夾角余弦系數或Pearson系數進行計算.受到物質擴散過程的啟發，Liu等［12］提出了基于用戶－產品二部分圖的用戶ui和uj相似性Sij的計算方法.

式（1）表示的就是從鄰居用戶uj到目標用戶ui的相似性.對于用戶－產品來說，如果ui沒有選擇產品oα（即aiα＝0），那么，目標用戶ui對產品oα的預測打分

式中，Sji表示從鄰居用戶uj到目標用戶ui的相似性，即利用目標用戶ui指向鄰居用戶uj的相似性來預測ui對產品oα的喜好程度.

2 改進的協同過濾算法

在考慮了二階相似信息的協同過濾算法中，用戶ui和用戶uj的二階相似性可以用如下形式來表示：

式中，H 是目標用戶ui和其鄰居用戶uj的二階相似性矩陣是由式（1）所得到的一階相似性定義；λ 是一個可調參數.

考慮二階相似性和用戶相似性方向，作者設計一種改進的算法.對于一個給定的用戶ui，改進的協同過濾算法可以描述為：首先利用式（3）計算用戶之間的二階有向相似性，進而對目標用戶進行推薦.

3 數值實驗

使用標準數據集Movielens測試新算法的性能表現.該數據集包括943個用戶和1 682個產品（電影）.用戶會對自己看過的產品按照5 分制進行打分，1分表示最不喜歡，5分表示最喜歡.在此假設用戶打分大于2 分的就看作他選擇了該產品，進而構建用戶－產品二部分圖.刪除部分連邊后數據集剩余943個用戶，1 574個產品和82 520條邊.將數據集分為訓練集和測試集這兩部分.利用數據集的90%作為訓練集預測用戶對未選擇產品的喜好程度，利用其余10%作為測試集度量算法的表現.

3.1 評價指標

a.準確度.一個好的算法應該是要將訓練集中已知的用戶喜歡的產品排在比較靠前的位置，本文采用平均排序打分度量推薦算法的準確性.若有Li＝100個產品沒有被ui選擇，而oα在推薦列表中排名第10個，即oα的位置是10／100，其排序打分記為riα＝0.1.平均排序打分〈r〉越小，說明產品在推薦列表中的位置越靠前，算法的準確性就越高，反之亦然.

b.流行性和多樣性.推薦產品的平均度〈k〉是評價推薦算法的重要指標.如果算法趨向于推薦流行的產品，那么，被推薦產品的平均度會很高；反之，如果算法趨向于推薦不太流行的產品，則其平均度會很低.此外，利用平均海明距離度量推薦列表的多樣性.用戶ui和uj推薦列表的平均海明距離被定義為pij＝1－Qij／L.其中，L 為推薦列表的長度，Qij為推薦給用戶ui和uj的2個推薦列表中相同產品的個數.推薦列表的多樣性定義為pij的平均值P，S＝pij.P 越大，算法可以提供更多樣化的推薦，反之亦然.

3.2 結果分析

當采用90%的數據作為訓練集時，從圖1中可以看出，在Movielens數據集上，經典的二階協同過濾算法的平均排序打分〈r〉在λ 為－0.815 附近達到最小值0.083，而本文算法的〈r〉在λ 為－0.726附近可以達到0.080 8.圖2表示推薦產品的平均度和推薦列表的多樣性隨著參數λ 的變化趨勢.從圖2中可以得到，推薦產品的平均度〈k〉和λ 正相關，也就是說降低用戶所選擇主流產品的影響會給不太流行產品更多的被推薦機會，當推薦列表長度L＝50時，在最優點λopt＝－0.726處，產品的平均度〈k〉＝191，相對于經典的基于物質擴散的協同過濾（CF）算法，流行性降低了10.32%.從圖2中也可以發現，算法的平均海明距離P 和λ 負相關，表明考慮了鄰居用戶對目標的二階相似性后使得推薦列表更為離散，并且當推薦列表長度L＝50時，在λopt＝－0.726處，產品的平均海明距離P 大約為0.775，多樣性提高了10.87%.因此，這種新算法在增加CF算法的精確性方面具有很大優勢，并且也可以較好地幫助目標用戶發現一些隱藏的暗信息，為目標用戶提供更為多樣化的推薦.

圖1 Movinlens數據集上平均排序打分隨參數λ 的變化趨勢圖Fig.1 Correlation between the parameterλand the average ranking score〈r〉

圖2 Movielens數據集上推薦產品的平均度〈k〉及推薦列表的多樣性P 隨參數λ 的變化趨勢Fig.2 Correlation between the parameterλand the average object degree〈k〉as well as the diversity P on dataset Movielens

4 結束語

首先提出了二階有向協同過濾算法，并且研究了用戶的二階有向相似性對協同過濾算法的影響.在標準數據集Movielens上的試驗結果表明，利用鄰居用戶到目標用戶的二階相似信息可以提高推薦的準確性.當訓練集的比例為90%時，算法的準確度可以達到0.080 8，該結果較經典的CF 提高了22.08%，這是已有的協同過濾算法中準確性效果最好的.

除準確性外，被推薦產品的平均度以及推薦列表的多樣性也是量化推薦算法性能表現的2個重要指標，而數值結果顯示，新算法在這2種指標下比經典的CF算法都要好.作者下一步的工作，將關注在二階有向相似性下產品的度信息與產品打分的關系.

［1］Herlocker J L，Konstan J A，Terveen L G，et al.Evaluating collaborative filtering recommender system［J］.ACM Trans Inform Syst，2004，22（1）：5－53.

［2］Konstan J A，Miller B N，Maltz D，et al.GroupLens：applying collaborative filtering to Usenet news［J］.Commun ACM，1997，40（3）：77－87.

［3］Liu J G，Wang B H，Guo Q.Improved collaborative filtering algorithm via information transformation［J］.Int J Mod Phys C，2009，20（2）：285－293.

［4］宣照國，苗靜，黨延忠.基于擴展鄰居的協同過濾算法［J］.情報學報，2010，29（3）：443－448.

［5］潘紅艷，林鴻飛，趙晶.基于矩陣劃分和興趣方差的協同過濾算法［J］.情報學報，2006，25（1）：49－54.

［6］張子柯.社會化標簽系統的結構、演化和功能［J］.上海理工大學學報，2011，33（5）：444－451.

［7］Adomavicius G，Tuzhilin A.Toward the next generation of recommender systems－a survey of the state－of－the art and possible extensions［J］.IEEE Trans Know and Data Eng，2005，17（6）：734－749.

［8］Liu J G，Chen M Z Q，Chen J，et al.Recent advances in personal recommendation systems［J］.Int J Info ＆Sys Sci，2009，5（2）：230－247.

［9］Zhou T，Ren J，Medo M，et al.Bipartite network projection and personal recommendation［J］.Phys Rev E，2005，76（4）：046115，1－4.

［10］Liu J G，Zhou T，Che H A，et al.Effects of high－order correlations on personalized recommendations for bipartite networks［J］.Physica A，2010，389（4）：881－886.

［11］Liu J G，Shi K R，Guo Q.Solving the accuracydiversity dilemma via directed random walks［J］.Phys Rev E，2012，85（1）：016118，1－4.

［12］Liu J G，Guo Q，Zhang Y C.Information filtering via weighted heat conduction algorithm［J］.Physica A，2011，390（12），2414－2420.