一種有效緩解協(xié)同過濾推薦評價數(shù)據(jù)稀疏問題的算法

黃永鋒，覃羅春

（東華大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，上海 201620）

一種有效緩解協(xié)同過濾推薦評價數(shù)據(jù)稀疏問題的算法

黃永鋒，覃羅春

（東華大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，上海 201620）

在采用協(xié)同過濾算法構(gòu)建個性化推薦的系統(tǒng)中，經(jīng)常面臨用戶評價數(shù)據(jù)稀疏問題，這將嚴重降低個性化推薦的準確度.針對此問題，提出了一種混合加權(quán)預(yù)測填充算法，從用戶訪問的資源特征以及該資源在整個用戶群體中被訪問的熱度出發(fā)，對用戶訪過的但未給出評價的數(shù)據(jù)進行預(yù)測并填充，從而降低了由于用戶評價數(shù)據(jù)缺失所造成的評價矩陣稀疏程度，提高推薦準確度.在MoiveLense數(shù)據(jù)集上的試驗結(jié)果表明，該算法能夠明顯地提高推薦準確度.

個性化推薦；協(xié)同過濾；數(shù)據(jù)稀疏；預(yù)測填充；資源特征

在互聯(lián)網(wǎng)服務(wù)供應(yīng)商提供海量信息時，通過個性化推薦能夠更快、更準確地為用戶找到可能感興趣的信息資源，提供更加智能的服務(wù)，從而有效地提高用戶的忠誠度，擴大品牌影響力，提高企業(yè)銷售.個性化推薦目前廣泛地應(yīng)于互聯(lián)網(wǎng)各個領(lǐng)域，如電子商務(wù)、數(shù)字圖書館、網(wǎng)絡(luò)廣告定向投放、網(wǎng)絡(luò)新聞訂制等［1］.而基于協(xié)同過濾的個性化推薦是迄今為止使用最為廣泛也是最受歡迎的個性化推薦算法之一［2－3］.

協(xié)同過濾是利用擁有共同興趣偏好的群體來為用戶推薦感興趣資源的一種過濾算法，該算法假設(shè)推薦系統(tǒng)有m個用戶的集合U＝ ｛u1，u2，…，um｝以及n個資源的集合I＝ ｛i1，i2，…，in｝.對于推薦系統(tǒng)中的每一位用戶ui∈U，記錄ui訪問過的資源集合Iui＝ ｛iui，1，iui，2，…，iui，n｜iui，n∈I｝，Iui?I，并且用戶ui對集合Iui中的某些或者全部訪問過的資源給出表達其對這些資源偏好的反饋信息，推薦系統(tǒng)記錄用戶對訪問過資源的評價信息，構(gòu)成推薦系統(tǒng)的用戶 －資源評價矩陣.對于每一個需要給出個性化推薦資源的用戶ua，稱之為活動用戶.協(xié)同過濾算法通過以下兩個過程為活動用戶推薦其可能最感興趣的N個資源：

（1）預(yù)測：預(yù)測一個數(shù)值Puaij，該值表示活動用戶ua對未曾訪問過的資源ij的偏好程度，其中ij?Iua；

（2）推薦：推薦產(chǎn)生N個資源的集合Iua，r，Iua，r∈I，Iua，r∩Iua＝ ?，將這N個用戶最感興趣并且是用戶未曾訪問過資源推薦給用戶ua.

協(xié)同過濾個性化推薦通常分為兩種［4］，即基于用戶的以及基于項的.由于具有非常好的擴展性，基于項的協(xié)同過濾被更多地用來構(gòu)建個性化推薦系統(tǒng).全球最大的電子商務(wù)網(wǎng)站Amazon就采用了基于項的協(xié)同過濾構(gòu)建其個性化推薦系統(tǒng).

但是，無論采用基于項的還是基于用戶的協(xié)同過濾算法，其推薦準確度都會依賴于用戶－資源評價矩陣的稀疏程度，評價矩陣越稀疏則推薦準確度越低［5］.現(xiàn)有的緩解用戶－資源評價矩陣稀疏問題的方法，如基于資源特征預(yù)測填充算法和基于資源訪問熱度的預(yù)測填充算法都存在一些弊端.本文針對上述算法存在的弊端，提出了一種混合加權(quán)預(yù)測填充算法，該算法以資源訪問熱度為加權(quán)量，將基于資源特征和基于資源訪問熱度兩種算法融合起來，汲取每一種算法的優(yōu)點，同時有效地規(guī)避每一種算法的不足，對用戶訪問過但是未給出評價值的資源的評分進行預(yù)測，并用預(yù)測值填充未評價值，以降低用戶－資源評價矩陣稀疏程度，提高推薦準確度.

1 混合加權(quán)預(yù)測填充算法

1.1 現(xiàn)有預(yù)測填充算法的不足

基于資源特征的預(yù)測填充算法根據(jù)人們通常會對具有較高相似性的資源給出較為相似的評價值，通過提取資源在某些特征上的相似度，將最為相似的一些資源的評價值通過調(diào)和加權(quán)后，作為用戶訪問過但未給出的評價值.該算法可以有效地降低用戶－資源評價矩陣稀疏程度［6］，但也存在下述一些缺陷.

（1）未考慮整個用戶群體對資源的評價值對該用戶產(chǎn)生的主觀影響，用戶對訪問過的資源給出的評價值不僅受用戶自身對資源的偏好所決定，還受系統(tǒng)中用戶群體對資源的評價影響，而基于資源特征的預(yù)測填充算法只考慮了用戶對資源的自身偏好因素，未能考慮用戶群體的影響因素.

（2）依賴于用戶自身對其他資源的訪問并給出的評價值，基于資源特征預(yù)測填充算法未給出評價值的目標資源與目標用戶訪問過并且給出評價值的資源的相似度，當用戶訪問過并且給出的評價值較少的情況，該算法預(yù)測出來的評價值會嚴重地偏離用戶可能給出的真實評價值.

（3）資源的特征準確識別并提取困難，系統(tǒng)中的資源具有大量的特征，如何抽取資源合理的特征子集作為計算資源之間的相似度是該算法面臨的一個難題.若抽取的特征過多，則會嚴重影響算法的效率，但是提取的特征數(shù)量比較少，則無法表現(xiàn)該類資源在特征上的識別度，造成無法準確地計算資源之間的相似度，并對最終的預(yù)測準確度造成嚴重的影響.

基于資源訪問熱度的預(yù)測填充算法則是從整個用戶群體出發(fā)，依據(jù)資源在整個用戶群體中的受歡迎程度預(yù)測影響目標用戶對該資源的偏好程度.該算法通過統(tǒng)計待預(yù)測填充資源在整個群體的訪問評價情況，然后將均值加權(quán)修正，計算該資源的待預(yù)測評價值［7］.但是基于資源訪問熱度的預(yù)測填充算法存在一個較為明顯的缺陷，即無法滿足目標用戶的特殊偏好，群體用戶都喜歡的資源，該目標用戶不一定會喜歡，而群體用戶不喜歡的資源，目標用戶卻可能非常喜歡.

1.2 引入資源訪問熱度的混合加權(quán)預(yù)測填充算法

現(xiàn)有的基于資源特征以及基于資源訪問熱度的預(yù)測填充算法，雖然能有效地降低用戶評價矩陣的稀疏度，但兩種算法都存在明顯的缺陷.因此考慮引入一種加權(quán)因子，將上述兩種算法結(jié)合起來，以融合兩種算法的優(yōu)點，同時降低單獨一種算法的缺陷.

在協(xié)同過濾個性化推薦系統(tǒng)中，用戶群體訪問資源集合后給出的評價值會形成一個用戶－資源評價矩陣，如表1所示.

表1 用戶－資源評價矩陣Table 1 User－item rating matrix

表1中 ?表示用戶未曾訪問某個資源，或者目標用戶u訪問過資源i但是未給出評價值.資源i為待預(yù)測評價值的資源，簡稱為目標資源，定義資源i的訪問熱度為該資源在整個群體中被訪問次數(shù)在整個用戶群體中所占的比例，如式（1）所示.

其中：Pd表示目標資源i的訪問熱度；rui，d表示每個用戶訪問目標資源的次數(shù)；ui表示推薦系統(tǒng)中的每個用戶.資源訪問熱度可以很好地體現(xiàn)目標資源在整個用戶群體中的訪問特征.

為了克服上述基于資源特征以及基于資源訪問熱度的預(yù)測填充算法所面臨的不足，這里引入資源訪問熱度作為加權(quán)因子的混合加權(quán)預(yù)測填充算法，該算法以資源訪問熱度為加權(quán)值，因此，將基于資源特征預(yù)測的評價值和基于資源訪問熱度預(yù)測的填充值結(jié)合起來，最終產(chǎn)生對目標資源的預(yù)測評價值.

設(shè)系統(tǒng)中所有用戶集合為U，資源集合為I，目標用戶u存在訪問過但是未給出評價值的資源i，V表示用戶u訪問過并且給出評價值的資源集合，定義資源特征集合C＝｛c1，c2，…，cm｝.為了計算目標資源i與V中每個資源在特征集C上的相似度，定義歐幾里得距離為相似度計算方法，如式（2）所示.

其中：sim（i，j）Euclidean表示資源i和j的特征相似度；ri，，k，rj，k分別表示資源i和j在特征集C上的相應(yīng)取值.在資源特征向量的相似度基礎(chǔ)上，可以通過調(diào)和加權(quán)方法得到基于資源特征的預(yù)測評價填充值［8］，如式（3）所示.

其中：si表示對第i個資源的評價值；sim（d，si）表示待預(yù)測填充的資源d與資源i在特征上的相似度；N為目標用戶訪問過并且給出評價值的資源數(shù)量.由式（4）可以得到基于資源訪問熱度的預(yù)測填充值.

其中：表示待預(yù)測資源在整個群體中被訪問過并且給出評價值的均值.在得到基于資源特征預(yù)測評價值和基于資源訪問熱度預(yù)測評價值的基礎(chǔ)上，引入資源訪問熱度加權(quán)因子，由式（5）可以得到最終的混合加權(quán)預(yù)測評價值.

將最終得到的預(yù)測值Rd替換目標用戶u對資源i的評價值.

1.3 算法描述

根據(jù)上述分析，可以得到基于資源特征和基于資源訪問熱度的混合加權(quán)預(yù)測填充算法，具體描述如下：

2 試驗結(jié)果及分析

2.1 試驗數(shù)據(jù)集

本文使用GroupLens提供的MovieLense系統(tǒng)上的10kbytes數(shù)據(jù)集作為評價算法效果的試驗數(shù)據(jù)集［9］，該數(shù)據(jù)集由943個用戶、1 682部電影、共100 000條訪問評價記錄組成.每個訪問記錄由4個字段組成（uid，mid，rt，dt），其中uid表示用戶標識符，mid表示電影標識符，rt表示用戶uid對電影mid的評價值，其值范圍為［1，5］，dt表示Unix時間戳.抽取每部電影的發(fā)行日期、電影類型、發(fā)行國家、發(fā)行語言等信息作為每一部電影的特征向量.

本文把100 000記錄分為訓(xùn)練集和測試集，其中隨機將每個用戶訪問的15條記錄單獨保存起來作為測試集，剩下的記錄作為訓(xùn)練集，用來檢驗采用混合加權(quán)算法對推薦質(zhì)量的提升程度.

2.2 評價標準

用信息檢索領(lǐng)域評估系統(tǒng)效果的準確度作為評價標準［10］，如式（6）所示.

其中：H為推薦命中的數(shù)量；N為推薦的數(shù)量.

2.3 試驗結(jié)果和分析

為了比較基于資源特征預(yù)測填充的和無預(yù)測填充的基于項的協(xié)同過濾算法，在不同的用戶－資源評價矩陣稀疏程度下的推薦準確度，本文采用矩陣稀疏度來衡量用戶－資源評價稀疏程度，如式（7）所示.

其中：L表示評價矩陣稀疏度；rs表示推薦系統(tǒng)中目標用戶訪問過某個資源并且給出的評價值；Z表示推薦系統(tǒng)中所有用戶數(shù)量；X表示推薦系統(tǒng)中所有不重復(fù)資源的數(shù)量.L越小表示稀疏程度越高.試驗將訓(xùn)練集分別設(shè)置用戶評價矩陣稀疏度為0.41%，1.41%，2.41%，3.41%，4.41%，設(shè)計了 4 組試驗，分別采用無預(yù)測填充、基于資源訪問熱度的預(yù)測填充、基于資源特征預(yù)測填充和混合加權(quán)預(yù)測填充的評價矩陣，然后采用傳統(tǒng)的基于項的協(xié)同過濾算法進行推薦，比較4種情況的推薦效果，試驗結(jié)果如圖1所示.

圖1 4種推薦準確度對比效果Fig.1 Comparison effect of four kinds of recommendation accuracy

從圖1可以看出，無預(yù)測填充的基于項的協(xié)同過濾推薦曲線隨著矩陣稀疏程度不同，推薦準確度也隨之改變，評價矩陣稀疏度越小，則推薦準確度越低.基于資源訪問熱度預(yù)測填充算法無法解決用戶特殊偏好問題，雖然能夠提高評價矩陣稀疏度，但是與無預(yù)測填充的基于項的協(xié)同過濾相比，推薦準確度未見明顯提高.基于資源特征的預(yù)測填充算法能夠很好地根據(jù)資源自身的客觀屬性對稀疏矩陣進行預(yù)測填充，效果比基于資源訪問熱度的預(yù)測填充算法好，但是它只考慮資源本身的客觀屬性，沒能考慮人類隨眾心里以及整個用戶群體行為對個體行為的影響.混合加權(quán)預(yù)測填充算法能夠很好地融合基于資源特征和基于資源訪問熱度預(yù)測填充算法的優(yōu)點，并且也可以彌補兩者之間的不足，使得混合加權(quán)預(yù)測填充得到的推薦準確度要高于基于資源特征和基于資源訪問熱度的推薦準確度.與此同時，混合加權(quán)預(yù)測填充與無預(yù)測填充的推薦結(jié)果相比，在不同的評價矩陣稀疏程度下，推薦準確度平均提升39%.因混合加權(quán)預(yù)測填充算法具有較好的客觀性，可以在一定程度上修正用戶由于心情好壞等主觀情緒對給出評價值的影響，使得預(yù)測的填充值更加符合用戶真實的客觀評價值，進一步地提高最終個性化推薦的準確度.特別是在評價矩陣嚴重稀疏的情況，采用混合加權(quán)預(yù)測填充算法能夠提供很好的初始推薦準確度，一定程度上緩解了采用協(xié)同過濾算法構(gòu)建的個性化推薦中冷啟動問題.

3 結(jié) 語

本文針對在基于項的協(xié)同過濾推薦算法中，因數(shù)據(jù)稀疏嚴重降低推薦準確度的問題，將基于資源特征預(yù)測填充和基于資源訪問熱度預(yù)測填充算法有機地結(jié)合起來，形成混合加權(quán)預(yù)測填充算法.經(jīng)試驗表明，該算法能夠有效預(yù)測用戶訪問過但是未曾評價的資源的評價值，并采用此值對缺失值進行填充，降低用戶－資源評價矩陣的稀疏度，另外，基于協(xié)同過濾算法構(gòu)建的推薦系統(tǒng)在經(jīng)過混合加權(quán)預(yù)測填充算法對評價矩陣進行填充后，通常能夠獲得更好的推薦效果.但是該算法的時間復(fù)雜度高，還可以通過進一步優(yōu)化來提高算法的效率，并且基于資源特征預(yù)測依賴資源自身的特征區(qū)分度，如何選擇合適的特征也是下一步需要研究的問題.

參 考 文 獻

［1］ADOMAVICIOUS G，TUZHILIN A.Towards the next generation of recommender systems：A survey of the state－ofthe－art and possible extensions［J］.IEEE Transactions on Knowledge and Data Engineering，2005，17（6）：734－749.

［2］SU X Y，TAGHI M K.A Survey of collaborative filtering techniques［J］.Advances in Artificial Intelligence，2009，Article ID 421425，1－19.

［3］邢春曉，高鳳榮，戰(zhàn)思南，等.適應(yīng)用戶興趣變化的協(xié)同過濾推薦算法［J］.計算機研究與發(fā)展，2007，44（2）：296－301.

［4］SARWAR B，KARYPIS G，KONSTAN J，et al.Item－based collaborative filtering recommendation algorithms ［C］／／Proceedings of the 10th International Conference on World Wide Web.Hong Kong，China，2001：285－295.

［5］吳顏，沈潔，顧天竺，等.協(xié)同過濾推薦系統(tǒng)中數(shù)據(jù)稀疏問題的解決［J］.計算機應(yīng)用研究，2007，24（6）：94－97.

［6］LIU Z B，WANG H，QU W Y，et al.Sparse matrix prediction filling in collaborative filtering ［C］／／IEEE International Conferece on Scalable Computing and Communications：The Eighth International Conference on Embedded Computing.2009：304－307.

［7］MA H，KING I，LYU M R.Effective missing data prediction for collaborative filtering［C］／／Proceeding of the 30th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval.2007：39－46.

［8］SEGARAN T.Programming collective intelligence ［M］.Sebastopol：O'Reilly，2009.

［9］Group Lense Research.Project MoiveLense［EB／OL］（2007－05－01）［2011－09－15］.http：／／www.grouplens.org／.

［10］劉建國，周濤，郭強，等.個性化推薦系統(tǒng)評價方法綜述［J］.復(fù)雜系統(tǒng)與復(fù)雜性科學(xué)，2009，6（3）：1－10.

An Effective Algorithm for Relieving Sparse Data in Collaborative Filtering Recommendation

HUANGYong－feng，QINLuo－chun
（School of Computer Science and Technology，Donghua University，Shanghai 201620，China）

Personalized recommendation system based on collaborative filtering often faces the data sparsity which seriously reduces the recommendation accuracy.An efficient hybrid weighted prediction algorithm is presented，which predicts the data visited but not rated by the characteristics and the access frequency，and fills the user－item matrix with the predictions.In this way，the sparsity of the user－item matrix is reduced，and the accuracy of recommendation is improved accordingly.Experimental results on MoiveLense data set clearly indicate that the algorithm can significantly improve the recommendation accuracy.

personalized recommendation；collaborative filtering；data sparsity；prediction filling；item characteristic

TP 274＋.5

A

1671－0444（2013）01－0083－05

2011－10－28

國家自然科學(xué)基金資助項目（30770589）；中央高?；究蒲袠I(yè)務(wù)費專項資金資助項目（2011D11206）

黃永鋒（1971—），男，山東泰安人，副教授，博士，研究方向為數(shù)據(jù)挖掘、機器學(xué)習(xí)和模式識別.E－mail：yfhuang＠dhu.edu.cn