基于抽樣近鄰的協同過濾算法

董立巖，劉晉禹，蔡觀洋，李永麗

（1.吉林大學計算機科學與技術學院，長春 130012；2.東北師范大學計算機科學與信息技術學院，長春 130117）

基于抽樣近鄰的協同過濾算法

董立巖1，劉晉禹1，蔡觀洋1，李永麗2

（1.吉林大學計算機科學與技術學院，長春 130012；2.東北師范大學計算機科學與信息技術學院，長春 130117）

針對實時推薦過程中實際數據的稀疏性，滿足條件的項目或用戶較少，導致推薦精度較低的問題，提出一種采用抽樣近鄰的協同過濾算法.該算法充分利用評分用戶矩陣提供的信息，增加了參與到預測評分計算過程中的用戶或項目，從而解決了傳統協同過濾算法在實際應用中的不足.實驗結果表明，在增加在線計算時間較少的情況下所給算法可有效提高推薦精度.

協同過濾；稀疏矩陣；推薦精度；近鄰

本文以近鄰用戶／項目組的選擇作為切入點，充分利用現有評分矩陣提供的信息，以近鄰組質量與推薦精度的關系為基礎，提出一種抽樣近鄰的協同過濾算法（sampling neighbor collaborative filtering，SNCF）.實驗結果表明，該方法可有效提高推薦精度.

1 算 法

1.1 基于抽樣的近鄰查找策略

傳統協同過濾算法在計算目標用戶的預測評分時，一般直接從內存中讀取過去某段時間計算過的其與所有其他用戶間的兩兩相似性，由于數據量較大，且數據稀疏，一般僅篩選出最相似的K個用戶作為近鄰，導致曾經計算過的大部分相似性都不會參與到實際預測評分計算過程中，即很多計算是無用的，這種模式也導致了相似性的延遲性.而實時推薦中僅選擇那些與目標用戶有共同評分信息的用戶計算相似性，有效減少了計算相似性的時間開銷，但也會引入很多非正相關的用戶到近鄰用戶組中.考慮到兩種模式的不足，本文提出一種新的抽樣近鄰組查找策略.近鄰查找策略步驟如下.

如果需要預測用戶u對項目p的評分情況，主要參數有：近鄰個數K和抽樣因子α.

1）找到一個集合User，該集合是所有對項目p有評分的用戶組成的集合；

3）分別計算出用戶u與候選集User中每個用戶元素間的相似性，將結果從大到小排序；

4）將3）中的結果取出前k個用戶作為近鄰用戶組.

近鄰中有部分用戶可能并未對目標項目評過分，在計算預測評分過程中，本文選擇用戶評分均值取整［5］的方法作為對目標項目的評分.

1.2 基于抽樣的近鄰查找算法分析

初始數據中，由于用戶集合項目集都較大，導致用戶－項目評分矩陣過于稀疏，通過上述近鄰選擇方式選出的候選用戶集則比原用戶集小很多；新候選用戶集的稀疏程度與抽樣因子α成正比，由于實驗中α的值過小，抽樣后的用戶集極大降低了稀疏度.此外，由于實際環境中對目標項目有評分信息的用戶較少，新策略中本文將這些用戶都添加到樣本空間中，使這項歷史行為信息能在預測評分過程中發揮一定作用；該方法還使一些沒有對目標項目做出評分、但實際卻和目標用戶在一定程度上相似的用戶參與到最終評分預測過程中的概率提高了.

如圖1所示，左側的“所有列”表示參與評分的所有用戶，標記為集合U，其中對項目p有過評分記錄的用紅色記號標注，分別為U1，U2，U3，U4.計算“所有列”的稀疏率為1－4／14＝71%.由于這些有評分信息的用戶等概率的在用戶集合中分布，本文假設用戶集合按相似性降序以有評分信息的用戶為界均分為（4＋1）個桶，用戶所在桶的編號越小，越與目標用戶相似.按照上述策略，將｛U1，U2，U3，U4｝4個用戶添加到“抽樣列”集合中，設定抽樣因子α＝1，還需從a～j中再額外隨機選擇4個用戶添加到“抽樣列”中，因此“抽樣列”集合的稀疏率為1－4／8＝50%.“相關列”中所有用戶都對目標項目評過分，因此稀疏率為0%.設近鄰用戶個數為4，假設集合都已按與目標用戶的相似性降序排過序，則從抽樣列選擇未對目標項目評分但與目標用戶很相似的用戶和對目標項目有評分信息的用戶各兩個作為近鄰用戶，雖然相關列是對目標項目有評分信息的用戶，但從所有列的排序中可見，有些用戶的相關性與目標用戶相差較遠，如果他們加入到近鄰用戶組會影響近鄰的質量.

圖1 不同策略下的候選用戶集Fig.1 Candidate set of users under different polices

由算法的時間復雜度可見，抽樣近鄰方法［6］比局部最優近鄰法所需時間更多，這是因為選擇用戶數量增多的原因，選擇用戶數量增多則需花更多時間計算他們與目標用戶間的相似性，但抽樣近鄰方法可提高推薦的精度，使用戶獲取正感興趣的推薦.隨著計算機科學的發展，可通過硬件資源的提高及算法的優化降低時間上的開銷，使兩種方法在時間復雜度上的差異越來越小，因此該方法以犧牲少量的計算時間為代價提高了推薦的準確性.

1.3 基于抽樣近鄰的用戶協同過濾算法

由上述理論分析可知，新的近鄰選擇策略可對推薦結果產生有益影響，因此本文將這種近鄰選擇策略應用到傳統基于用戶協同過濾算法中，提出一種新的基于抽樣近鄰的用戶協同過濾算法（sample neighbor user－based collaborative filtering，SN－UBCF）.SN－UBCF算法除了應用近鄰選擇策略外，其他部分與UBCF算法相似，如用戶間相似性計算、計算預測得分的方式等.主要步驟如下：

1）采用抽樣近鄰選擇策略選出候選用戶集；

2）計算出候選用戶集中的用戶與目標用戶間的相似性；

3）相似性按降序排序，將前k個用戶添加到近鄰用戶組，由于近鄰用戶中有未對目標項目評分的用戶，因此將用戶組分為對目標項目評過分的用戶和未對目標項目評過分的用戶兩類；

4）采用近鄰用戶組中的相似性和評分信息計算目標用戶對目標項目的預測評分.

上述算法的關鍵步驟是如何計算用戶間的相似性，本文采用性能較好的Pearson相關相似性計算.文獻［7－8］研究表明，通過增加相關重要性權重因子可降低共同評分信息少的用戶間的相似性在計算評分中的權重，從而提高推薦精度，因此本文使用該相似性計算公式計算用戶間的關系.用戶u和v間的相似性為

2 實 驗

2.1 方 法

考察不同種類近鄰選擇策略應用到基于用戶的協同過濾算法中對個性化推薦精度的影響.協同過濾算法要求用戶設定某些參數，實驗中測試多個參數對算法性能的影響.實驗采用對折交叉驗證方法［9］，將MovieLens數據集5等分，依次選出其中的4份作為訓練集，1份作為測試集.

2.2 評估指標

協同過濾算法多采用打分機制衡量用戶對物品的興趣度，因此推薦的過程相當于計算用戶對物品的興趣度分值，稱為評分預測推薦.對此模式的質量評估，一般分析計算系統產生的預測分值與用戶對項目的實際分值間差值的大小，差值越小則推薦結果越準確；反之則推薦結果準確性越差.實驗中采用MAE作為度量標準［10］評價算法的性能：

其中：Rui表示用戶u對項目i的評分；rui表示推薦系統的預測評分信息；T表示測試集合.

2.3 結果與分析

圖2給出了傳統協同過濾算法和SN－UBCF算法在不同近鄰個數情況下推薦精度的變化情況.由圖2可見，在不同近鄰個數下，SN－UBCF算法都比UBCF算法的MAE值約低0.01，所以新算法可有效提高推薦精度.實驗還度量了算法的計算時間，時間消耗在兩部分：1）找到候選用戶集所需的時間，即找出那些沒有對目標項目評分的用戶；2）計算出候選用戶集中每個用戶與目標用戶間相似性所需時間.算法用時結果列于表1.由表1可見，SN－UBCF算法所需時間比UBCF算法高近1倍.算法采用Python實現，算法的執行效率較低，因此表1中的時間數據僅作說明使用，與實際應用環境中計算評測分值所用時間有較大差距.在實際工業環境中，可采用并行化算法實現核心部分，以減少算法的時間開銷.由于計算相似性的用戶集增大，所以在線時間一定會比原算法高，且該值與用戶選擇的抽樣比例成正比，抽樣用戶越多，計算相似性需花費的時間越多；但由于選擇的用戶可能與目標用戶沒有共同評分項目，兩者的相似性為0，不需計算，所以這種比例關系不是恒定的常量值，因此本算法在犧牲一定時間的開銷下獲得了較高的精度.

圖2 不同k值時的精度對比Fig.2 Accuracies at different kvalues

表1 不同算法所用時間Table 1 Run time by different algorithms

綜上，為使推薦結果更接近用戶的實際需要，本文提出的基于抽樣的近鄰選擇策略，不但理論上有合理性，且實際也符合用戶的行為.還可將該方法應用在基于用戶的協同過濾算法中，提出了SN－UBCF算法.實驗結果表明，該算法在以增加少許的運算時間為代價的同時可極大提高算法的推薦精度.

［1］ SONG Yang，ZHUANG Ziming，LI Huajing，et al.Real－Time Automatic Tag Recommendation［C］／／Proceeding of the 31st Annual International ACM SIGIR Conference on Research and Development in Information Retrieval.New York：ACM，2008：515－522.

［2］ Sarwar B M，Karypis G，Konstan J，et al.Item－Based Collaborative Filtering Recommendation Algorithm［C］／／Proceedings of the 10th International Conference on World Wide Web.New York：ACM Press，2001：285－295.

［3］ Sarwar B M，Karypis G，Konstan J，et al.Recommender Systems for Large－Scale E－Commerce：Scalable Neighborhood Formation Using Clustering［C］／／Proceeding of the Fifth International Conference on Computer and Information Technology.New York：ACM Press，2002.

［4］ Sarwar B M，Karypis G，Konstan J，et al.Application of Dimensionality Reduction in Recommender Systems：A Case Study［C］／／Proceedings of ACM Web KDD Workshop.Minneapolis：University of Minnesota，2000：114－121.

［5］ Xue G R，Lin C，Yang Q，et al.Scalable Collaborative Filtering Using Cluster－Based Smoothing［C］／／Proceedings of the 28th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval.New York：ACM Press，2005：114－121.

［6］ SHI Yue，Larson M，Hanjalic A.Exploiting User Similarity Based on Rated－Item Pools for Imprrved User－Based Collaborative Filtering［C］／／RecSys’09：Proceedings of the Third ACM Conference on Recommender Systems.New York：ACM Press，2009：125－132.

［7］ ZAHNG Jiyong，Pu P.A Recursive Prediction Algorithm for Collaborative Filtering Recommender Systems［C］／／Proceedings of the 2007ACM Conference on Recommender Systems.New York：ACM Press，2007：57－64.

［8］ Koren Y.Factor in the Neighbors：Scalable and Accurate Collaborative Filtering［J］.ACM Transactions on Knowledge Discovery from Data，2010，4（1）：1－24.

［9］ Yehuda K.Collaborative Filtering with Temporal Dynamics［C］／／Proceedings of the 15th ACM SIGKOD International Conference on Knowledge Discovery and Data Mining.New York：ACM，2009：447－456.

［10］ Symeonidis P，Nanopoulos A，Papadopoulos A N，et al.Collaborative Filtering：Fallacies and Insights in Measuring Similarity［C／OL］.2013－03－04.http：／／delab.csd.auth.gr／papers／WEBMINING06.pdf.

（責任編輯：韓 嘯）

Collaborative Filtering Algorithm Based on Sampling Neighbor

DONG Liyan1，LIU Jinyu1，CAI Guanyang1，LI Yongli2
（1.College of Computer Science and Technology，Jilin University，Changchun130012，China；2.School of Computer Science and Technology，Northeast Normal University，Changchun130117，China）

Since the user－item matrix is sparse，and there are less users or items satisfying the conditions，the precision of the algorithm can’t be high.By sampling neighbor collaborative filtering algorithms，users take full advantage of score matrix provided information to increase the users or projects participated in the calculation process，so as to solve the shortage of traditional collaborative filtering algorithms in real application.Experiment results show that the new algorithm can effectively improve the precision in recommendation along a small increasing of runtime.

collaborative filtering；sparse matrix；precision of recommendation；neighbor

TP301.6

A

1671－5489（2014）04－0779－04

個性化推薦算法在Web服務中應用廣泛，如電子商務、搜索引擎、多媒體服務中的個人影音和個性化閱讀等，它可以提高服務的用戶黏度.協同過濾算法在工業環境中應用廣泛.針對特殊的推薦需求（實時推薦），如購物車推薦、新聞推薦等［1］，需要根據用戶當前的狀態產生最新的推薦，但基于內存的協同過濾算法多數情況下需要預先計算用戶或項目間的相似性存入內存中，使用時直接取值即可，導致產生的推薦具有一定的滯后性.

Sarwar等［2］為了減少在線運算的復雜性，在運算過程中僅選擇了對最終項目有評分信息的用戶，計算出這些用戶與最終用戶間的相似性，挑選出近鄰用戶組.但該方法可用的用戶或項目較少，信息量較少導致推薦精度不高.文獻［3］提出了基于模型的協同過濾算法，可有效減少在線計算時間，但也存在推薦滯后的問題.奇異值分解的矩陣分解算法［4］可降低用戶項目評分矩陣的維度及計算相似性所用的時間，但推薦精度不高.

10.13413／j.cnki.jdxblxb.2014.04.28

2014－05－14.

董立巖（1966—），男，漢族，博士，教授，從事數據挖掘的研究，E－mail：dongly＠jlu.edu.cn.通信作者：李永麗（1965—），女，漢族，博士，副教授，從事信息安全的研究，E－mail：Liyl603＠nenu.edu.cn.

國家自然科學基金（批準號：61272209）.