基于選擇性預(yù)測(cè)策略的協(xié)同過(guò)濾推薦算法

劉旭東，崔 蕾，陳德人

(1．煙臺(tái)職業(yè)學(xué)院信息工程系，山東 煙臺(tái) 264670;2．浙江大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，浙江 杭州 310027)

隨著信息技術(shù)和互聯(lián)網(wǎng)的快速發(fā)展，信息過(guò)載已經(jīng)逐漸成為目前互聯(lián)網(wǎng)用戶所面臨的嚴(yán)峻問(wèn)題之一。一方面，用戶很難快速在電子商務(wù)網(wǎng)站找到自己喜歡的商品;另一方面，電子商務(wù)網(wǎng)站也難以及時(shí)向用戶提供其感興趣的商品，從而提高網(wǎng)站銷售能力。推薦系統(tǒng)作為解決這一問(wèn)題的有效手段，已經(jīng)應(yīng)用到國(guó)內(nèi)外各大知名電子商務(wù)網(wǎng)站中。它通過(guò)發(fā)掘用戶的行為，找到用戶的個(gè)性化需求，從而將其感興趣但很難發(fā)現(xiàn)的商品準(zhǔn)確地推薦給用戶［1］。

協(xié)同過(guò)濾推薦技術(shù)作為當(dāng)前電子商務(wù)推薦系統(tǒng)中應(yīng)用最廣泛的個(gè)性化推薦技術(shù)之一［2］，得到了越來(lái)越多學(xué)者、專家的關(guān)注和研究。但隨著系統(tǒng)中信息數(shù)據(jù)急劇增長(zhǎng)，數(shù)據(jù)稀疏性問(wèn)題成為了傳統(tǒng)協(xié)同過(guò)濾推薦系統(tǒng)面臨的挑戰(zhàn)之一［3］。針對(duì)稀疏性問(wèn)題，文獻(xiàn)［4－5］提出了采用用戶對(duì)項(xiàng)目評(píng)分均值的方法來(lái)填充用戶－項(xiàng)目矩陣中的空值，該方法雖然能在一定程度上緩解系統(tǒng)的稀疏性問(wèn)題，但由于用戶不可能對(duì)所有的項(xiàng)目持同一態(tài)度，用均值填充后忽視了用戶的偏好和興趣，其推薦效果不是很理想。文獻(xiàn)［6］提出了一種基于k－means聚類的填充方法，該方法雖然一定程度上能夠提高推薦效果，但其預(yù)先設(shè)定好的k值產(chǎn)生的聚類結(jié)果，抹殺了用戶的部分偏好和興趣，在解決稀疏性問(wèn)題上也具有一定的局限性。文獻(xiàn)［7］提出了一種利用奇異值分解(SVD)的方法來(lái)減少用戶－項(xiàng)目評(píng)分矩陣的維度，該方法在解決同義詞問(wèn)題的同時(shí)，對(duì)可擴(kuò)展性有一定的改善，但降維容易導(dǎo)致原始信息丟失，使得系統(tǒng)推薦精度有所降低。

筆者從個(gè)性化角度出發(fā)，針對(duì)用戶評(píng)分?jǐn)?shù)據(jù)極端稀疏的情況，在分析傳統(tǒng)協(xié)同過(guò)濾推薦算法的基礎(chǔ)上，提出了一種基于選擇性預(yù)測(cè)策略的協(xié)同過(guò)濾推薦算法，算法通過(guò)引入高相似度閾值，生成用戶最近鄰集和項(xiàng)目最近鄰集，利用用戶間和項(xiàng)目間的雙向信息來(lái)對(duì)用戶－項(xiàng)目矩陣進(jìn)行協(xié)同預(yù)測(cè)、填充，以增加用戶－項(xiàng)目矩陣的稠密度?；贛ovielens數(shù)據(jù)集的實(shí)驗(yàn)表明，新算法可以有效解決傳統(tǒng)協(xié)同過(guò)濾算法中的數(shù)據(jù)稀疏性和擴(kuò)展性問(wèn)題，并能有效提高系統(tǒng)推薦質(zhì)量。

1 傳統(tǒng)的協(xié)同過(guò)濾推薦算法及其分析

傳統(tǒng)的協(xié)同過(guò)濾推薦主要是根據(jù)用戶的行為(用戶注冊(cè)信息、用戶歷史購(gòu)買(mǎi)記錄、評(píng)分?jǐn)?shù)據(jù)等)信息來(lái)建立用戶行為模型，并利用行為模型來(lái)向用戶推薦有價(jià)值商品的過(guò)程。整個(gè)推薦過(guò)程可以分為數(shù)據(jù)表示、最近鄰查詢和推薦產(chǎn)生這3個(gè)階段。主要算法有User－based協(xié)同過(guò)濾算法和Item－based協(xié)同過(guò)濾算法兩種［8］。Userbased協(xié)同過(guò)濾算法的基本思想是在用戶－項(xiàng)目評(píng)分矩陣上通過(guò)相似性計(jì)算找到與目標(biāo)用戶u興趣偏好相似的最近鄰用戶集合，然后再根據(jù)各最近鄰用戶對(duì)未知項(xiàng)目i的評(píng)分來(lái)預(yù)測(cè)目標(biāo)用戶u對(duì)i的評(píng)分值，并最終形成Top－N推薦。該算法以前應(yīng)用得非常成功，但隨著系統(tǒng)規(guī)模的不斷擴(kuò)大，其推薦算法也面臨一系列挑戰(zhàn)，最突出的是數(shù)據(jù)稀疏性問(wèn)題和“冷開(kāi)始”問(wèn)題。Item－based協(xié)同過(guò)濾算法的基本思想是預(yù)先根據(jù)所有用戶的歷史偏好數(shù)據(jù)計(jì)算項(xiàng)目之間的相似性，然后把與目標(biāo)用戶喜歡的項(xiàng)目相類似的前N個(gè)項(xiàng)目推薦給目標(biāo)用戶。該算法在一定程度上緩解了Userbased協(xié)同過(guò)濾推薦中的數(shù)據(jù)稀疏性問(wèn)題，但它不能挖掘用戶的潛在興趣，做出不同類型的推薦，只能推薦用戶感興趣的同類項(xiàng)目［9－10］。

User－based和Item－based兩種協(xié)同過(guò)濾推薦算法僅利用了用戶－項(xiàng)目評(píng)分矩陣中用戶或項(xiàng)目單個(gè)維度信息來(lái)進(jìn)行商品推薦，在預(yù)測(cè)推薦過(guò)程中沒(méi)有考慮項(xiàng)目間的關(guān)聯(lián)或用戶間的關(guān)聯(lián)，因而在實(shí)際應(yīng)用中，推薦效果不是很理想。

2 選擇性預(yù)測(cè)策略下的協(xié)同過(guò)濾推薦

2．1 算法思想及基本理論

為了克服傳統(tǒng)User－based和Item－based兩種協(xié)同過(guò)濾算法各自的不足，使產(chǎn)生的推薦結(jié)果更加符合用戶的實(shí)際需求，提出了一種基于選擇性預(yù)測(cè)策略的協(xié)同過(guò)濾推薦算法。算法的核心是結(jié)合User－based和Item－based協(xié)同過(guò)濾算法，通過(guò)引入高相似度閾值來(lái)生成用戶最近鄰和項(xiàng)目最近鄰，并利用最近鄰來(lái)對(duì)評(píng)分矩陣中未評(píng)分項(xiàng)進(jìn)行協(xié)同預(yù)測(cè)、填充，以達(dá)到緩解數(shù)據(jù)稀疏性，改善系統(tǒng)推薦質(zhì)量的目的。

定義1 設(shè)用戶相似度閾值為η，則對(duì)于用戶－項(xiàng)目評(píng)分矩陣中每一個(gè)未評(píng)分元素ru，i，目標(biāo)用戶u的最近鄰集表示為:

其中，sim(ua，u)為用戶ua與u之間的相似性，可采用 Pearson相關(guān)系數(shù)公式進(jìn)行計(jì)算［11－12］。

定義2 設(shè)項(xiàng)目相似度閾值為θ，則對(duì)于用戶－項(xiàng)目評(píng)分矩陣中每一個(gè)未評(píng)分元素ru，i，目標(biāo)項(xiàng)目i的最近鄰集表示為:

其中，sim(ik，i)為項(xiàng)目ik與i之間的相似性，可采用Pearson相關(guān)系數(shù)公式進(jìn)行計(jì)算。

定義3 對(duì)于用戶－項(xiàng)目評(píng)分矩陣中給定的未評(píng)分的元素 ru，i，根據(jù)式(1)和式(2)，可得 ru，i的預(yù)測(cè)值為:

其中:pu，i為目標(biāo)用戶u對(duì)未評(píng)分項(xiàng)i的預(yù)測(cè)評(píng)分;λ∈［0，1］為加權(quán)因子，可動(dòng)態(tài)調(diào)整和分別為目標(biāo)用戶u獲得的平均評(píng)分和目標(biāo)項(xiàng)目i獲得的平均評(píng)分為目標(biāo)用戶u的最近鄰集的平均評(píng)分為目標(biāo)項(xiàng)目i的最近鄰集的平均評(píng)分。

2．2 算法描述

輸入為用戶－項(xiàng)目評(píng)分矩陣R(m，n)，加權(quán)因子λ，用戶相似度閾值η和項(xiàng)目相似度閾值θ。

輸出為目標(biāo)用戶u的TOP－N推薦集。

具體算法步驟如下:

(1)在用戶－項(xiàng)目評(píng)分矩陣R(m，n)中隨機(jī)選取一個(gè)用戶u和一個(gè)項(xiàng)目i分別作為目標(biāo)用戶和目標(biāo)項(xiàng)目。

(2)基于用戶－項(xiàng)目評(píng)分矩陣R(m，n)，利用Pearson相關(guān)系數(shù)公式來(lái)計(jì)算其他任一用戶ua(ua≠u(mài))與目標(biāo)用戶u的相似性sim(ua，u)，選取sim(ua，u)＞η的用戶作為目標(biāo)用戶u的最近鄰集S(U)。

(3)基于用戶－項(xiàng)目評(píng)分矩陣R(m，n)，利用Pearson相關(guān)系數(shù)公式來(lái)計(jì)算其他任一項(xiàng)目ik(ik≠i)與目標(biāo)項(xiàng)目 i的相似性 sim(ik，i)，選取 sim(ik，i)＞θ的項(xiàng)目作為目標(biāo)項(xiàng)目的最近鄰集S(I)。

(4)利用式(3)來(lái)計(jì)算目標(biāo)用戶u對(duì)所有未評(píng)分項(xiàng)i的預(yù)測(cè)評(píng)分，并對(duì)R(m，n)進(jìn)行填充，將預(yù)測(cè)評(píng)分最高的前N項(xiàng)推薦給目標(biāo)用戶u，完成Top－N推薦。

3 實(shí)驗(yàn)及結(jié)果分析

3．1 實(shí)驗(yàn)數(shù)據(jù)集及評(píng)價(jià)標(biāo)準(zhǔn)

實(shí)驗(yàn)從MovieLens站點(diǎn)提供的943位用戶對(duì)1 682部電影的10萬(wàn)條評(píng)分記錄中隨機(jī)抽取300位用戶對(duì)1 486部電影的29 826條評(píng)分?jǐn)?shù)據(jù)(5分制)作為數(shù)據(jù)集，該用戶評(píng)分?jǐn)?shù)據(jù)的稀疏等級(jí)［13］為 1 －29 826/(300 ×1 486)=0．933 1，數(shù)據(jù)非常稀疏。該實(shí)驗(yàn)是基于該數(shù)據(jù)集進(jìn)行的，實(shí)驗(yàn)方法采用五折交叉驗(yàn)證來(lái)進(jìn)行，把實(shí)驗(yàn)數(shù)據(jù)集按照80%和20%的比例劃分為訓(xùn)練集和測(cè)試集。

實(shí)驗(yàn)采用平均絕對(duì)誤差MAE(mean absolute error)來(lái)對(duì)該系統(tǒng)評(píng)分預(yù)測(cè)的準(zhǔn)確度進(jìn)行評(píng)價(jià)，通過(guò)計(jì)算推薦算法的預(yù)測(cè)評(píng)分與用戶實(shí)際的評(píng)分間的誤差來(lái)評(píng)價(jià)其準(zhǔn)確性。令pi為推薦算法給出的用戶預(yù)測(cè)評(píng)分集合(i=1，2，…，n)，qj為預(yù)測(cè)評(píng)分對(duì)應(yīng)的實(shí)際用戶評(píng)分集合(j=1，2，…，n)，則平均絕對(duì)誤差MAE定義為:

MAE越小，預(yù)測(cè)的精度越高，推薦質(zhì)量越好。

3．2 實(shí)驗(yàn)過(guò)程及分析

(1)實(shí)驗(yàn)1。λ的討論。λ為設(shè)定的可動(dòng)態(tài)調(diào)整的加權(quán)因子，其取值對(duì)MAE的值可能會(huì)有影響，因此在該實(shí)驗(yàn)中，取η=θ=0．5，最近鄰集分別取 5、10、15，λ 取值從 0 到 1，每次增加 0．1，觀察MAE的變化。實(shí)驗(yàn)結(jié)果如圖1所示。

圖1 數(shù)據(jù)集u300下λ對(duì)MAE的影響

從圖1中可以看出λ的取值對(duì)MAE有明顯的影響。當(dāng)λ=0．7時(shí)，MAE值最小，推薦質(zhì)量最好。因此在實(shí)驗(yàn)2中λ取值為0．7。

(2)實(shí)驗(yàn)2。η和θ的討論。令η=θ，并使η和θ的值從0變化到1，每次增長(zhǎng)0．1，觀察MAE的變化。實(shí)驗(yàn)結(jié)果如圖2所示。

圖2 數(shù)據(jù)集u300下η與θ對(duì)MAE的影響

從圖2中可以看出，當(dāng)η=θ=0．5時(shí)，改進(jìn)算法取得了比較好的推薦效果。

(3)實(shí)驗(yàn)3。各種算法性能的比較。為了驗(yàn)證提出的改進(jìn)算法(PCF)對(duì)解決數(shù)據(jù)稀疏性問(wèn)題的有效性，把改進(jìn)算法與基于奇異值分解的協(xié)同過(guò)濾算法(SVD)、基于均值填充的協(xié)同過(guò)濾推薦算法(SCF)、基于k－means聚類的協(xié)同過(guò)濾推薦算法(Cluster－CF)進(jìn)行比較，在實(shí)驗(yàn)中，用Pearson相關(guān)系數(shù)公式方法計(jì)算用戶間的相似性，最近鄰數(shù)從4遞增到32，觀察MAE的變化。實(shí)驗(yàn)結(jié)果如圖3所示。

圖3 各種算法的推薦精度比較

從圖3中可以看出，改進(jìn)算法在各種實(shí)驗(yàn)條件下，MAE性能值要好于SCF協(xié)同過(guò)濾算法和基于k－means的協(xié)同過(guò)濾算法，當(dāng)最近鄰個(gè)數(shù)超過(guò)20時(shí)，改進(jìn)算法的性能也要優(yōu)于SVD協(xié)同過(guò)濾算法。由此可見(jiàn)，改進(jìn)的算法能較好地解決系統(tǒng)數(shù)據(jù)稀疏性問(wèn)題，能有效避免數(shù)據(jù)稀疏性帶來(lái)的用戶間相似度計(jì)算不準(zhǔn)確問(wèn)題，具有較好的推薦效果。

4 結(jié)論

針對(duì)傳統(tǒng)協(xié)同過(guò)濾推薦系統(tǒng)的數(shù)據(jù)稀疏性問(wèn)題，結(jié)合User－based和Item－based協(xié)同過(guò)濾算法，提出了一種基于選擇性預(yù)測(cè)策略的改進(jìn)算法，算法通過(guò)利用生成的用戶高相似度最近鄰和項(xiàng)目高相似度最近鄰來(lái)對(duì)評(píng)分矩陣中未評(píng)分項(xiàng)目進(jìn)行協(xié)同預(yù)測(cè)和平滑處理，更加符合用戶的實(shí)際需求。實(shí)驗(yàn)結(jié)果表明，新算法能有效解決系統(tǒng)的數(shù)據(jù)稀疏性和擴(kuò)展性問(wèn)題，顯著提高系統(tǒng)的推薦質(zhì)量。

［1］ 項(xiàng)亮．推薦系統(tǒng)實(shí)踐［M］．北京:人民郵電出版社，2012:21－72．

［2］ BREESE J，HECHERMAN D，KADIE C．Empirical analysis of predictive algorithms for collaborative filtering［C］∥Proceedings of the 14th Conference on Uncertainty in ArtificialIntelligence(UAI－ 98)．［S．l．］:［s．n．］，1998:43 －52．

［3］ 孫小華．協(xié)同過(guò)濾推薦系統(tǒng)的稀疏性與冷啟動(dòng)問(wèn)題研究［D］．杭州:浙江大學(xué)圖書(shū)館，2005．

［4］ TH R，KJ O，HAN I．The collaborative filtering recommendation based on SOM cluster－indexing CBR［J］．Expert Systems with Applications，2003，25(3):413－423．

［5］ WU B，SHI Z Z．A clustering algorithm based on swarm intelligence［C］∥Proceedings of the IEEE International Conference on Info－tech and Infonet Proceeding．［S．l．］:［s．n．］，2001:58 － 66．

［6］ OYANAGI S，KUBOTA K，NAKASE A．Application of matrix clustering to Web log analysis and access prediction［C］∥Proceedings of the Fourteenth Conference on Uncertainty Collaborative Filtering．［S．l．］:［s．n．］，1998:65 －70．

［7］ SARWAR B，KARYPIS G，KONSTAN J，et al．Application of dimensionality reduction in recommender system:a case study［C］∥Proceedings of the ACM Web KDD Workshop on Web Mining for E－commerce．New York:ACM Press，2000:82 －90．

［8］ SARWAR B，KARYPIS G，KONSTAN J，et al．Item－based collaborative filtering recommendation algorithms［C］∥Proceedings of the Tenth International World Wide Web Conference．［S．l．］:［s．n．］，2001:285－295．

［9］ 王惠敏，聶規(guī)劃．融合用戶和項(xiàng)目相關(guān)信息的協(xié)同過(guò)濾算法研究［J］．武漢理工大學(xué)學(xué)報(bào)，2007，29(7):160－163．

［10］ 聶規(guī)劃，羅跡，陳冬林．面向Web服務(wù)組合推薦的關(guān)聯(lián)規(guī)劃研究［J］．武漢理工大學(xué)學(xué)報(bào):信息與管理工程版，2012，34(5):588 －591．

［11］ 成桂蘭，劉旭東，陳德人．基于混合聚類的個(gè)性化推薦算法［J］．武漢理工大學(xué)學(xué)報(bào):信息與管理工程版，2011，33(3):379 －381．

［12］ 夏培勇．個(gè)性化推薦技術(shù)中的協(xié)同過(guò)濾算法研究［D］．青島:中國(guó)海洋大學(xué)圖書(shū)館，2011．

［13］ 鄧愛(ài)林，朱揚(yáng)勇，施伯樂(lè)．基于項(xiàng)目評(píng)分預(yù)測(cè)的協(xié)同過(guò)濾推薦算法［J］．軟件學(xué)報(bào)，2003，14(9):1621－1628．