汪靜

【摘要】協(xié)同過濾推薦算法是目前在推薦系統(tǒng)中應(yīng)用最成功和廣泛的技術(shù)之一。本文詳細(xì)介紹了協(xié)同過濾推薦算法的分類和度量指標(biāo)。同時(shí)，分析了協(xié)同過濾推薦算法中的問題以及相應(yīng)的解決辦法。最后闡述了協(xié)同過濾推薦系統(tǒng)中仍需解決的問題和未來可能的發(fā)展方向。

【關(guān)鍵詞】推薦系統(tǒng)協(xié)同過濾推薦算法

一、引言

隨著信息技術(shù)的迅速發(fā)展，互聯(lián)網(wǎng)在為用戶提供越來越多信息的同時(shí)，其規(guī)模也變得越來越龐大，其結(jié)構(gòu)也變得越來越復(fù)雜。對(duì)于用戶來說，如何及時(shí)有效地在網(wǎng)絡(luò)上的海量信息中發(fā)現(xiàn)自己所需要的信息已經(jīng)變得相當(dāng)困難。推薦系統(tǒng)就是解決這一問題的最有效的途徑。推薦系統(tǒng)現(xiàn)已經(jīng)廣泛地應(yīng)用于很多領(lǐng)域，如電子商務(wù)，電影，音樂，社交網(wǎng)絡(luò)等等。在推薦系統(tǒng)中應(yīng)用最成功和廣泛的是協(xié)同過濾推薦算法，對(duì)該算法的研究已經(jīng)呈現(xiàn)了大量的研究和應(yīng)用成果。

二、協(xié)同過濾推薦算法的分類

在協(xié)同過濾推薦算法中，用戶評(píng)分?jǐn)?shù)據(jù)中包含m個(gè)用戶的集合U={ul，u2，……，um}和n個(gè)項(xiàng)目的集合I={il，12，……，in。用戶對(duì)項(xiàng)目的評(píng)分?jǐn)?shù)據(jù)可以采用用戶一項(xiàng)目評(píng)分矩陣來表示。根據(jù)推薦產(chǎn)生過程和采用技術(shù)的不同，通?？梢詫f(xié)同過濾推薦算法分為兩類：基于記憶和基于模型的算法[1]。

2.1 基于記憶的協(xié)同過濾推薦算法

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

2.2 基于模型的協(xié)同過濾算法

隨著用戶和項(xiàng)目的數(shù)量規(guī)模不斷擴(kuò)大，評(píng)分?jǐn)?shù)據(jù)越來越高維，傳統(tǒng)的基于記憶的協(xié)同過濾算法在計(jì)算量上也面臨可擴(kuò)展的問題，而且難以得到好的實(shí)時(shí)推薦效果。為了解決這些問題，一些學(xué)者提出了基于模型的推薦算法。這一類的算法首先利用統(tǒng)計(jì)技術(shù)和機(jī)器學(xué)習(xí)技術(shù)對(duì)用戶一項(xiàng)目的評(píng)分矩陣進(jìn)行訓(xùn)練，通過訓(xùn)練建立一個(gè)模型，然后再基于這個(gè)模型為目標(biāo)用戶進(jìn)行預(yù)測(cè)，進(jìn)而產(chǎn)生推薦結(jié)果。在基于模型的協(xié)同過濾推薦算法中主要采用的技術(shù)包括貝葉斯網(wǎng)絡(luò)[8]，聚類[9-10]，降維技術(shù)[11-12]，潛在語義[13-14]，本體模型[15]和云模型[16]等等。

三、協(xié)同過濾推薦算法的評(píng)估指標(biāo)

根據(jù)現(xiàn)階段推薦系統(tǒng)的任務(wù)，可以主要把對(duì)推薦算法的評(píng)估指標(biāo)分成3類：預(yù)測(cè)準(zhǔn)確度和分類準(zhǔn)確度。

3.1預(yù)測(cè)準(zhǔn)確度

預(yù)測(cè)準(zhǔn)確度主要用來度量算法預(yù)測(cè)的評(píng)分與真實(shí)評(píng)分之間的偏差。在那些要給用戶顯式預(yù)測(cè)評(píng)分值的場(chǎng)景中，預(yù)測(cè)準(zhǔn)確度尤其重要。在協(xié)同過濾推薦算法中最常用的預(yù)測(cè)準(zhǔn)確度指標(biāo)是平均絕對(duì)誤差[17]，該指標(biāo)主要用來度量預(yù)測(cè)的評(píng)分和真實(shí)的評(píng)分之間直接的數(shù)值差距。這個(gè)值越小，表明預(yù)測(cè)越準(zhǔn)確，推薦質(zhì)量越高。該指標(biāo)因其計(jì)算簡單、通俗易懂得到了廣泛的應(yīng)用。不過這個(gè)指標(biāo)也有一定的局限性，因?yàn)閷?duì)這個(gè)指標(biāo)貢獻(xiàn)比較大的往往是那種很難預(yù)測(cè)準(zhǔn)確的低分項(xiàng)目[1]。

3.2分類準(zhǔn)確度

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

四、協(xié)同過濾推薦算法面臨的問題

隨著網(wǎng)絡(luò)的發(fā)展，用戶和項(xiàng)目的數(shù)量迅猛增加，而網(wǎng)絡(luò)資源和站點(diǎn)結(jié)構(gòu)也變得越來越復(fù)雜，協(xié)同過濾推薦算法在實(shí)際的推薦系統(tǒng)的應(yīng)用中，仍然面臨著以下問題：

4.1稀疏性問題

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

4.2冷啟動(dòng)問題

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

4.3信任問題

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

4.4 多樣性問題

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

4.5大數(shù)據(jù)處理的問題

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

參 考 文 獻(xiàn)[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]除健，基于影響集的協(xié)作過濾推薦算法[J]軟件學(xué)報(bào)，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]鄧愛林，左子葉，朱揚(yáng)勇，基于項(xiàng)目聚類的協(xié)同過濾推薦算法[J]小型微型計(jì)算機(jī)系統(tǒng)，2004， 25（9）：1665- 1670[10]吳湖，王永吉，王哲.兩階段聯(lián)合聚類協(xié)同過濾算法[J].軟件學(xué)報(bào)，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，F(xiàn)altings 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]張光衛(wèi)，李德毅，李鵬，康建初，陳桂生.基于云模型的協(xié)同過濾推薦算法[J].軟件學(xué)報(bào)，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]許海玲，吳瀟，李曉東，閻保平，互聯(lián)網(wǎng)推薦系統(tǒng)比較研究[J]軟件學(xué)報(bào)，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]肖強(qiáng)，朱慶華，鄭華，吳克文.Hadoop環(huán)境下的分布式協(xié)同過濾算法設(shè)計(jì)與實(shí)現(xiàn)[J]，現(xiàn)代圖書情報(bào)技術(shù)，2013，（1）：83-89