協同過濾推薦算法研究綜述

汪靜

【摘要】協同過濾推薦算法是目前在推薦系統中應用最成功和廣泛的技術之一。本文詳細介紹了協同過濾推薦算法的分類和度量指標。同時，分析了協同過濾推薦算法中的問題以及相應的解決辦法。最后闡述了協同過濾推薦系統中仍需解決的問題和未來可能的發展方向。

【關鍵詞】推薦系統協同過濾推薦算法

一、引言

隨著信息技術的迅速發展，互聯網在為用戶提供越來越多信息的同時，其規模也變得越來越龐大，其結構也變得越來越復雜。對于用戶來說，如何及時有效地在網絡上的海量信息中發現自己所需要的信息已經變得相當困難。推薦系統就是解決這一問題的最有效的途徑。推薦系統現已經廣泛地應用于很多領域，如電子商務，電影，音樂，社交網絡等等。在推薦系統中應用最成功和廣泛的是協同過濾推薦算法，對該算法的研究已經呈現了大量的研究和應用成果。

二、協同過濾推薦算法的分類

在協同過濾推薦算法中，用戶評分數據中包含m個用戶的集合U={ul，u2，……，um}和n個項目的集合I={il，12，……，in。用戶對項目的評分數據可以采用用戶一項目評分矩陣來表示。根據推薦產生過程和采用技術的不同，通常可以將協同過濾推薦算法分為兩類：基于記憶和基于模型的算法[1]。

2.1 基于記憶的協同過濾推薦算法

基于記憶的協同過濾推薦算法類似于機器學習中的懶惰學習算法，是直接對整個用戶一項目評分矩陣進行計算，找到相似的用戶或項目來產生推薦結果。根據相似性計算的對象的不同，又可以分為基于用戶的算法和基于項目的算法。基于用戶的協同過濾算法的主要思想是利用興趣偏好相似的用戶的評分來產生推薦列表[2-3]。而基于項目的算法，則利用相似項目進行推薦。根據這類算法的基本原理，可以把算法的實施分為四個階段：（1）相似性計算。常用的度量用戶或者項目的相似性的方法主要包括如下三種：余弦相似性，皮爾遜相關系數和約束的皮爾遜相關系數[4]。此外，項目的相似性還可以基于條件概率來計算[5]。（2）選擇相似近鄰。在基于用戶的算法中，通常采用K最近鄰方法[6]和基于閾值的方法[7]為目標用戶選擇興趣偏好最相似的鄰居。而基于項目的算法，則選擇所有相似項目作為近鄰。（3）預測評分。這個環節主要根據相似用戶或者項目的評分，來預測目標用戶對目標項目的評分。（4）推薦。常用的推薦方法是全局排序方法，即選擇預測評分最高的前N個項目，即top-N推薦方法。

2.2 基于模型的協同過濾算法

隨著用戶和項目的數量規模不斷擴大，評分數據越來越高維，傳統的基于記憶的協同過濾算法在計算量上也面臨可擴展的問題，而且難以得到好的實時推薦效果。為了解決這些問題，一些學者提出了基于模型的推薦算法。這一類的算法首先利用統計技術和機器學習技術對用戶一項目的評分矩陣進行訓練，通過訓練建立一個模型，然后再基于這個模型為目標用戶進行預測，進而產生推薦結果。在基于模型的協同過濾推薦算法中主要采用的技術包括貝葉斯網絡[8]，聚類[9-10]，降維技術[11-12]，潛在語義[13-14]，本體模型[15]和云模型[16]等等。

三、協同過濾推薦算法的評估指標

根據現階段推薦系統的任務，可以主要把對推薦算法的評估指標分成3類：預測準確度和分類準確度。

3.1預測準確度

預測準確度主要用來度量算法預測的評分與真實評分之間的偏差。在那些要給用戶顯式預測評分值的場景中，預測準確度尤其重要。在協同過濾推薦算法中最常用的預測準確度指標是平均絕對誤差[17]，該指標主要用來度量預測的評分和真實的評分之間直接的數值差距。這個值越小，表明預測越準確，推薦質量越高。該指標因其計算簡單、通俗易懂得到了廣泛的應用。不過這個指標也有一定的局限性，因為對這個指標貢獻比較大的往往是那種很難預測準確的低分項目[1]。

3.2分類準確度

推薦系統的主要任務就是向用戶推薦喜歡的項目，也可以看作一個分類問題。分類準確度指標就是衡量推薦系統是否能夠正確預測用戶喜歡或者不喜歡某個項目的能力[18]。常用的度量分類性能的指標是查準率和查全率。查準率和查全率指標往往是負相關的而且依賴于推薦列表長度。為了同時考察查準率和查全率，Pazzani等把二者綜合考慮提出了Fl指標[19]。Fl指標的值越大，說明推薦的準確度越高。

四、協同過濾推薦算法面臨的問題

隨著網絡的發展，用戶和項目的數量迅猛增加，而網絡資源和站點結構也變得越來越復雜，協同過濾推薦算法在實際的推薦系統的應用中，仍然面臨著以下問題：

4.1稀疏性問題

現在的推薦系統中，數據規模都非常龐大，兩個用戶之間選擇的重疊非常少。例如在淘寶上的商品數量有近10億，平均而言一個用戶很少能對超過1000件商品進行評分，數據嚴重稀疏。評分數據的稀疏性問題，嚴重地影響了算法的推薦質量。這個問題本質上是無法解決的，但是可以通過一些辦法，在相當程度上緩解這個問題。比如，對原始數據集的空缺值，可以預先填充一些評分，這樣就可以提高相似性度量的準確度，從而提高算法的準確度[20]。但是預先填充計算量往往比較大，耗費時間，而且可能填充值本身會帶來誤差，反而后會影響推薦的質量。

4.2冷啟動問題

冷啟動問題是指新用戶和新項目問題。新用戶剛加入到推薦系統時，系統并沒有新用戶在系統的任何信息，如評分或者瀏覽、購買記錄等。對新用戶問題的處理，常常需要利用用戶的個人統計信息來改進推薦結果[21]。但是，由于涉及個人隱私，用戶一般不愿意公開提供詳細的個人信息，所以推薦效果會受到一定的限制。同理，當新項目加入到推薦系統中后，由于沒有用戶對其進行過評分，瀏覽或者購買，所以一開始它將無法被推薦。對新項目問題的處理，需要結合基于內容的推薦方法來解決。

4.3信任問題

傳統的推薦系統對用戶來說，推薦系統是個“黑盒”，用戶只能看到系統推薦的結果，但是用戶完全不知道自己有哪些相似用戶，以及如何得出最終的推薦結果。另外，由于數據的稀疏性與冷啟動等問題，造成推薦的結果出現很大偏差的時候，用戶也無法知道出現這樣情況的原因，和怎么去修正這個推薦結果。如果能夠更好地向用戶說明并提供推薦的原因，也可以有效地改善用戶體驗，提升用戶的滿意度和忠誠度。要解決這個問題，就要利用當前用戶所信任的用戶來產生推薦結果。用戶之間的信任關系可以直接利用用戶明確提供的信任值來度量[22]，也可以利用用戶的行為數據，如用戶對項目的評分來計算獲得。如何合理地度量用戶之間的信任關系，以及在系統內的用戶群之間進行信任傳遞都是推薦技術面臨的重要問題。

4.4 多樣性問題

近年來大量的研究結果表明，推薦系統不但要為用戶提供準確的推薦結果，還應該為用戶推薦多樣化的項目，這樣才能吸引用戶的興趣，提高用戶對系統的滿意度和忠誠度。另一方面，應用推薦系統的商家，也希望在推薦結果中出現更多種不同類別的商品，這樣才能激發用戶產生新的購物需求，提高商品銷售額。Adomavlclus在預測評分的基礎上，提出了幾種排序技術來改進推薦結果的集合多樣性[23]。Hurley等把推薦多樣性和推薦質量作為一個二元優化問題進行分析，即在提高推薦多樣性和不降低推薦準確率這兩方面得到—個折衷的方案[24]。盡管上面提到的這些方法效果很好，但是都是從算法本身的角度去考慮，還沒有辦法就相關結果而提供合理的解釋。推薦的多樣性和精確性兩者之間矛盾，到目前為止還是一個無法解決的難題。

4.5大數據處理的問題

隨著互聯網的發展，新項目還在不斷加入系統，新用戶也在不停地進入系統，用戶和項目之間還不停地產生新的關聯。數據量不僅非常龐大，而且數據本身還不斷地在動態變化，數以億計的海量數據給數據的存儲和計算的速度帶來極大的挑戰。要解決這個問題，首先考慮的就是算法的并行化。已有研究者在Hadoop平臺設計分布式的協同過濾推薦算法，實驗結果表明，這一方法能有效提高響應時間，但是在數據稀疏的情況下，算法的推薦精度較低[25]。針對大數據處理的問題，對分布式算法的研究剛剛起步，還有很多的不足，但是將會成為推薦算法研究中的一個新的熱點方向。

參 考 文 獻[l]Goldberg D，Nichols D，Oki B， Terry D.Using collaborative filtering to weavean information tapestry [J]. Communications of the ACM， 1992， 35（12）：61-70[2]Liu J G，Zhou T， Wang B H.The research progress of personalized recommendation system [J]. Progress in Natural Science， 2009， 19（1）：1-15[3]Adomavicius G and Tuzhilin A.Towards the next generation of recommender

systems：A survey of the state-of-the-art and possible extensions [J].IEEE Transactions on Knowledge and Data Engineering， 2005， 17（6）：734 - 749[4]除健，基于影響集的協作過濾推薦算法[J]軟件學報，2007， 18（7）： 1685-1694[5]Herlocker L J，Konstan A J and Riedl T J.Empirical analysis of design choices in neighborhood-based collaborative filtering algorithms [J].Information Retrieval，

2002， 5（4）：287-310[6]Chen M C，Chen L S，Hsu H，et al.A profitability based recommender system[C].//In： Proceedings of the IEEE International Conference on IndustrialEngmeenng and Engineering Management， Singapore， 2007：219-223[7]Shardanand U，Maes P. Socialinformation filtering： algorithms for automating "word of mouth"[C].，，In Proceedings of ACM CHI' 95 Conference onHuman Factors in Computing Systems. New York： ACM Press， 1995， 210-217[8]Pennock D M，Horvitz E， Lawrence S， and Giles C L Collaborative filtering by personality diagnosis：a hybrid memory- and model-based approach[C].In：

Proceedings of the 16th Conference on Uncertainty in Artificial Intelligenc，e， 2000：473 - 480[9]鄧愛林，左子葉，朱揚勇，基于項目聚類的協同過濾推薦算法[J]小型微型計算機系統，2004， 25（9）：1665- 1670[10]吳湖，王永吉，王哲.兩階段聯合聚類協同過濾算法[J].軟件學報，2010， 21（5）： 1042-1054[ll]Koren Y，Park F. Fac，torization Meets the Neighborhood：a Multifaceted Collahorative Filtering Model[C].// In： Proceedings of the 14th ACM SICKDDInternational Conference on Knowledge Discovery and Data Mining， New York， NY， USA， 2008：426-434[12]Ma H，Zhou D，Liu C， Lyu M R，King I. Recommender systems with social regularization[C]. //In： Proceedings of the 4th ACM InternationalConference on Web Search and Data Mining， ACM Press，NewYork，2011：287 - 296[13lHofmann T. Latent semantic models for collahorative filtering [J]. ACM Transactions on Information Systems， 2004， 22（1）： 89 -1 15[14]Blei D M，Ng A Y，and Jordan M I.Latent dirichlet allocation [J]. Journal of Machine Learning Research， 2003，3（4一5）：993 - 1022[15]2uher V S，Faltings B.Using hierarc，hic，al clustering for learning the ontologies used in recommendation systems[Cl.//In： Proceedings of the 13th ACMSIGKDD Int'1

Conference on Knowledge Discovery and Data Mining， New York： ACM Press， 2007：599-608[16]張光衛，李德毅，李鵬，康建初，陳桂生.基于云模型的協同過濾推薦算法[J].軟件學報，2007，18（10）：2403-2411[17]Linden G，Smith B，and York J. Amazon.com recommendations： item-to-item collaborative filtering [J]. IEEE Internet computing， 2003， 7（1）：76-80[18]許海玲，吳瀟，李曉東，閻保平，互聯網推薦系統比較研究[J]軟件學報，2009， 20（2）：350-362[19]Mooney R J，Roy I¨Content-based book recommending using learning for text categorization[C]. //In： Proceedings of Sth ACM Conference on DigitalLibraries. ACM Press， San Antonio， 2002：195-204[20lEsslimani I， Brun A，Boyer A.Densifying a hehavioral recommender system by social networks link prediction methods[J].Social Network Analysisand Mining， 2011， 1：159-172[21]Yu K，Schwaighofer A， Tresp V，Xu X，Kriegel HP. Probabilistic memory-hased collahorative filtering[J]. IEEE Transactions on Knowledge and DataEngineering， 2004，16（1）：56- 69[22]Massa P and Avesani P. Trust metrics on controversial users： balancing between tyranny of the majority and echo chambers [J]. International Journalon Semantic. Web and Information Systems， 2007， 3（1）：39 - 64[23lAdomavicius G，Kwon Y 0.Improving aggregate recommendation diversity using ranking-based technique [J].IEEF. Transactions on Knowledge andData Engineering， 2012， 24（5）：896-911[24]Hurley N，

Zhang Mi. Novelty and diversity in top-N recommendation-analysis and evaluation [J]. ACM Transactions on Internet Tec，hnology，2011， 10（4）：14：1-14：30[25]肖強，朱慶華，鄭華，吳克文.Hadoop環境下的分布式協同過濾算法設計與實現[J]，現代圖書情報技術，2013，（1）：83-89