基于抽樣近鄰的協(xié)同過濾算法

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

（1.吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，長春 130012；2.東北師范大學(xué)計(jì)算機(jī)科學(xué)與信息技術(shù)學(xué)院，長春 130117）

基于抽樣近鄰的協(xié)同過濾算法

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

（1.吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，長春 130012；2.東北師范大學(xué)計(jì)算機(jī)科學(xué)與信息技術(shù)學(xué)院，長春 130117）

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

協(xié)同過濾；稀疏矩陣；推薦精度；近鄰

本文以近鄰用戶／項(xiàng)目組的選擇作為切入點(diǎn)，充分利用現(xiàn)有評(píng)分矩陣提供的信息，以近鄰組質(zhì)量與推薦精度的關(guān)系為基礎(chǔ)，提出一種抽樣近鄰的協(xié)同過濾算法（sampling neighbor collaborative filtering，SNCF）.實(shí)驗(yàn)結(jié)果表明，該方法可有效提高推薦精度.

1 算 法

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

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

如果需要預(yù)測用戶u對(duì)項(xiàng)目p的評(píng)分情況，主要參數(shù)有：近鄰個(gè)數(shù)K和抽樣因子α.

1）找到一個(gè)集合User，該集合是所有對(duì)項(xiàng)目p有評(píng)分的用戶組成的集合；

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

4）將3）中的結(jié)果取出前k個(gè)用戶作為近鄰用戶組.

近鄰中有部分用戶可能并未對(duì)目標(biāo)項(xiàng)目評(píng)過分，在計(jì)算預(yù)測評(píng)分過程中，本文選擇用戶評(píng)分均值取整［5］的方法作為對(duì)目標(biāo)項(xiàng)目的評(píng)分.

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

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

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

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

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

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

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

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

2）計(jì)算出候選用戶集中的用戶與目標(biāo)用戶間的相似性；

3）相似性按降序排序，將前k個(gè)用戶添加到近鄰用戶組，由于近鄰用戶中有未對(duì)目標(biāo)項(xiàng)目評(píng)分的用戶，因此將用戶組分為對(duì)目標(biāo)項(xiàng)目評(píng)過分的用戶和未對(duì)目標(biāo)項(xiàng)目評(píng)過分的用戶兩類；

4）采用近鄰用戶組中的相似性和評(píng)分信息計(jì)算目標(biāo)用戶對(duì)目標(biāo)項(xiàng)目的預(yù)測評(píng)分.

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

2 實(shí) 驗(yàn)

2.1 方 法

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

2.2 評(píng)估指標(biāo)

協(xié)同過濾算法多采用打分機(jī)制衡量用戶對(duì)物品的興趣度，因此推薦的過程相當(dāng)于計(jì)算用戶對(duì)物品的興趣度分值，稱為評(píng)分預(yù)測推薦.對(duì)此模式的質(zhì)量評(píng)估，一般分析計(jì)算系統(tǒng)產(chǎn)生的預(yù)測分值與用戶對(duì)項(xiàng)目的實(shí)際分值間差值的大小，差值越小則推薦結(jié)果越準(zhǔn)確；反之則推薦結(jié)果準(zhǔn)確性越差.實(shí)驗(yàn)中采用MAE作為度量標(biāo)準(zhǔn)［10］評(píng)價(jià)算法的性能：

其中：Rui表示用戶u對(duì)項(xiàng)目i的評(píng)分；rui表示推薦系統(tǒng)的預(yù)測評(píng)分信息；T表示測試集合.

2.3 結(jié)果與分析

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

圖2 不同k值時(shí)的精度對(duì)比Fig.2 Accuracies at different kvalues

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

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

［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.

（責(zé)任編輯：韓 嘯）

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

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

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

10.13413／j.cnki.jdxblxb.2014.04.28

2014－05－14.

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

國家自然科學(xué)基金（批準(zhǔn)號(hào)：61272209）.