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

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

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

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

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

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

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

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

1 算 法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.1 方 法

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

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

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

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

2.3 結(jié)果與分析

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

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

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

綜上，為使推薦結(jié)果更接近用戶(hù)的實(shí)際需要，本文提出的基于抽樣的近鄰選擇策略，不但理論上有合理性，且實(shí)際也符合用戶(hù)的行為.還可將該方法應(yīng)用在基于用戶(hù)的協(xié)同過(guò)濾算法中，提出了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ù)的用戶(hù)黏度.協(xié)同過(guò)濾算法在工業(yè)環(huán)境中應(yīng)用廣泛.針對(duì)特殊的推薦需求（實(shí)時(shí)推薦），如購(gòu)物車(chē)推薦、新聞推薦等［1］，需要根據(jù)用戶(hù)當(dāng)前的狀態(tài)產(chǎn)生最新的推薦，但基于內(nèi)存的協(xié)同過(guò)濾算法多數(shù)情況下需要預(yù)先計(jì)算用戶(hù)或項(xiàng)目間的相似性存入內(nèi)存中，使用時(shí)直接取值即可，導(dǎo)致產(chǎn)生的推薦具有一定的滯后性.

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

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