劉旭東，崔 蕾，陳德人

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2．2 算法描述

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

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

具體算法步驟如下:

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

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

(3)基于用戶－項(xiàng)目評分矩陣R(m，n)，利用Pearson相關(guān)系數(shù)公式來計算其他任一項(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)來計算目標(biāo)用戶u對所有未評分項(xiàng)i的預(yù)測評分，并對R(m，n)進(jìn)行填充，將預(yù)測評分最高的前N項(xiàng)推薦給目標(biāo)用戶u，完成Top－N推薦。

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

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

實(shí)驗(yàn)從MovieLens站點(diǎn)提供的943位用戶對1 682部電影的10萬條評分記錄中隨機(jī)抽取300位用戶對1 486部電影的29 826條評分?jǐn)?shù)據(jù)(5分制)作為數(shù)據(jù)集，該用戶評分?jǐn)?shù)據(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)證來進(jìn)行，把實(shí)驗(yàn)數(shù)據(jù)集按照80%和20%的比例劃分為訓(xùn)練集和測試集。

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)論

針對傳統(tǒng)協(xié)同過濾推薦系統(tǒng)的數(shù)據(jù)稀疏性問題，結(jié)合User－based和Item－based協(xié)同過濾算法，提出了一種基于選擇性預(yù)測策略的改進(jìn)算法，算法通過利用生成的用戶高相似度最近鄰和項(xiàng)目高相似度最近鄰來對評分矩陣中未評分項(xiàng)目進(jìn)行協(xié)同預(yù)測和平滑處理，更加符合用戶的實(shí)際需求。實(shí)驗(yàn)結(jié)果表明，新算法能有效解決系統(tǒng)的數(shù)據(jù)稀疏性和擴(kuò)展性問題，顯著提高系統(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é)同過濾推薦系統(tǒng)的稀疏性與冷啟動問題研究［D］．杭州:浙江大學(xué)圖書館，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é)同過濾算法研究［J］．武漢理工大學(xué)學(xué)報，2007，29(7):160－163．

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

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

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

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