結合相似度量和反饋調節(jié)的推薦算法

王慶慶， 吳共慶， 李 磊

（合肥工業(yè)大學 計算機與信息學院，安徽 合肥 230009）

迄今為止應用最廣泛的推薦算法是協(xié)同過濾算法［1－7］，它通過挖掘用戶的歷史評分數(shù)據(jù)對用戶喜好進行建模。隨著社交網(wǎng)絡的興起，一些基于社交信任的推薦系統(tǒng)也相繼被提出［8－11］。其背后共同的動機是，在社交網(wǎng)絡中，一個用戶的品味與其信賴的朋友的品味相似或受其影響［12］。

推薦系統(tǒng)雖已在商業(yè)中廣泛應用，但多數(shù)算法都存在固有弱點。首當其沖的是數(shù)據(jù)稀疏性帶來的問題。在商用推薦系統(tǒng)中可用數(shù)據(jù)的密度通常低于1%［9］，無論是協(xié)同過濾還是基于信任的算法都無法規(guī)避此類問題。協(xié)同過濾很難處理評分稀少的用戶。而基于信任的算法中，新連入社交網(wǎng)絡的用戶，直接信任的鄰居寥寥可數(shù)，意味著很多物品無法預測。這迫使算法要去考慮用戶的間接鄰居（即鄰居信任的用戶）。但是將間接鄰居納入考慮后，部分用戶的鄰居規(guī)模會陡增，有限相似的鄰居會帶來長尾噪音的干擾問題［5］。

此外，目前已有算法都基于這樣一個假設，即所有評分數(shù)據(jù)客觀真實，卻忽略了某些可能異常的評分數(shù)據(jù)。例如，對于某物品，多數(shù)用戶給出高評分，卻有極少數(shù)給出了低評分。

為了克服上述問題，本文提出了一種新的用戶相似度量方法，從用戶信任的鄰居中識別出相似度較高的K個鄰居，進行第1次預測評分；利用一次預測結果，反饋檢查并修正原評分數(shù)據(jù)中的異常評分，然后進行第2次評分預測，以期提高推薦準確度。本文的相似度量依據(jù)是，鄰居評過分的物品集與目標用戶的物品集重疊度越高，則該鄰居和目標用戶的相似度越高。

1 相關工作

傳統(tǒng)的協(xié)同過濾可分為2類，即 Memorybased方法和 Model－based方法。前者在Amazon等商用推薦系統(tǒng)中應用較為普遍［13］，典型模型有基于用戶的［2，7］和基于物品的［4，5］協(xié)同過濾。此類方法推薦結果直觀、易理解；但數(shù)據(jù)稀疏性使得模型很難計算物品間或用戶間的相似度，因為它／他們之間的共同項太少。后者的典型模型有隱語義模型 LFM［14－16］。LFM 利用矩陣分解技術［16］將一個高維矩陣分解成2個或多個低維矩陣的乘積［14］，通過特定系數(shù)線性組合物品因子向量來對用戶的偏好建模。LFM雖能更好地為評分數(shù)較少的用戶提供推薦，但是需要反復迭代才能獲得較好的性能，且不能對推薦結果進行解釋。

上述方法均基于一個假設，即用戶是獨立同分布的，忽略了用戶間的社交聯(lián)系。真實世界中，對于未知物品，人們一般會先向身邊信任的朋友咨詢，收集他們對物品的評價，而各人的喜好也容易受朋友影響。出于此動機，許多研究者開始研究基于社交信任的推薦。文獻［8］提出了信任感知的推薦系統(tǒng)，它通過信任網(wǎng)絡中的信任傳播來度量用戶的信任值，以此代替相似度權值；文獻［10］提出了一種基于topk推薦的最近鄰算法，利用信任網(wǎng)絡中的鄰居和矩陣分解的用戶潛在特征空間中的鄰居，形成“聯(lián)合鄰居”來代替觀察值的加權平均；文獻［17］中不僅考慮信任的鄰居對目標商品的評分，還考慮相似商品的評分，通過隨機游走模型求得兩者間的折衷。上述模型都需要計算用戶間的相似度和信任值，因而不能擴展到大規(guī)模數(shù)據(jù)集上；文獻［12］提出用戶在不同分類上信任不同朋友，為此將原社交網(wǎng)絡分成多個子網(wǎng)絡，每個子網(wǎng)絡對應單個分類，單個分類中的朋友根據(jù)專業(yè)知識分配不同的信任值。但在數(shù)據(jù)稀疏時，信任網(wǎng)絡按分類劃分后，數(shù)據(jù)稀疏性會隨之增大，推薦的覆蓋率和準確度將大大降低。

2 方 法

2.1 用戶重合相似度量

協(xié)同過濾的關鍵步驟之一就是相似度量。常見的有余弦相似度、皮爾遜相關系數(shù)和調整后的余弦相似度［5］。但是面對稀疏的數(shù)據(jù)，2個用戶間的共同評分物品集本來就小，經(jīng)常僅一兩個物品，在這些小集合上非常相似，并不能肯定2個用戶的相似度就高。為了解決這一問題，提出了新的相似度量。

定義1 用戶重合相似度，是指用戶u和v之間評分重合的數(shù)目占自身評分總數(shù)的比重，即

其中，Ru表示用戶u的評分物品集合。

例如，用戶u對n1個物品評過分，用戶v對n2個物品評過分，設u和v同時評過分的物品為n3個，則用戶u對v的重合相似度為n3／n1，而用戶v對u的重合相似度為n3／n2。顯而易見，用戶的相似度矩陣為非對稱矩陣。對于用戶u和v，當共同評分物品數(shù)n3較小時，若n1較大，則用戶u對v的重合相似度不會很高；若n1也不大時，恰好能反映出用戶u對v的重合相似度較高。

2.2 鄰居的挑選

從信任網(wǎng)絡中可以得到目標用戶直接申明信任的鄰居，即直接鄰居。通過廣度優(yōu)先檢索可得到直接鄰居信任的用戶，即間接鄰居。兩者組成了用戶的初始鄰居。通過觀察，發(fā)現(xiàn)不同用戶的初始鄰居數(shù)目差別很大。為了避免有限相似的鄰居的長尾噪音干擾，為鄰居數(shù)目設置一個閾值，即鄰居數(shù)的最大值K。對于鄰居數(shù)多的用戶，從初始鄰居中挑選出與用戶聯(lián)系更密切的K個鄰居；而對于鄰居數(shù)不多的用戶，從第3層鄰居中選取部分補足。具體操作是按用戶對鄰居的重合相似度遞減排序，取前K個鄰居作為用戶的近鄰。

2.3 評分預測與反饋調節(jié)

本文算法中涉及2次評分預測，過程相同。即挑選出目標用戶u的鄰居集合ONu后，利用鄰居對目標物品i的評分預測用戶u對物品i的評分＾r(nóng)u，i，計算公式如下：

其中，ONu，i表示用戶u的鄰居對物品i評過分的用戶集合，rv，i表示用戶v對物品i的評分。

對于目標物品i，存在以下情況：多數(shù)人給出高評分，卻有極少數(shù)用戶給出差別較大的低分；反之亦然。稱這些與多數(shù)評分差別較大的評分為異常評分項，對于用戶u和物品i，本文算法對于異常評分項的識別和修正的過程如下。

（1）求得鄰居評分中大于一次預測值的評分所占比例pu，i，計算公式為：

其中，f（x）定義如下：

（2）若高分比例pu，i＜α∈［0，0.5），即高分所占比例較小，則認為高分評分為異常評分項，將高分鄰居的評分標記為－1，表明其評分值需要下調ε（本文中取ε＝1）；反之若低分比例1－pu，i＜α，即低分所占比例較小，則認為低分評分為異常評分項，將低分鄰居的評分標記為1，表明其評分值需要上調ε，計算公式為：

（3）修正評分矩陣，計算公式為：

在修正后的評分數(shù)據(jù)newR上，重復評分預測過程，見（1）式，得到二次預測結果，即為最終結果。

2.4 算法流程與性能分析

算法流程如下：

在SCFA算法中，用戶間相似度的時間復雜度O（n2），n為用戶個數(shù)。通過設置鄰居數(shù)閾值，可以有效控制鄰居數(shù)為常量K，因此生成預測的時間復雜度為O（n）。綜上，整個SCFA算法的時間復雜度為O（n2）。

3 實驗結果與分析

3.1 數(shù)據(jù)集

采用文獻［18］的數(shù)據(jù)集Epinions，包括22 166個用戶，296 277個物品，912 441個評分，直接申明的信任關系355 727個。對于用戶，選取信任人數(shù)不小于5的用戶（共計9 282人）；對于物品，選取評分數(shù)目不小于15的物品（共計8 594個），組成了新的實驗數(shù)據(jù)集。新數(shù)據(jù)集的評分矩陣稀疏度為0.997 9，信任矩陣稀疏度為0.996 4。其中，評分矩陣將會被分割為2個子集，即訓練集和測試集。從評分數(shù)少于5個的用戶的評分物品中，隨機選擇1個評分放入測試集中；從評分數(shù)不少于5個的用戶的評分物品中，隨機選擇10%，向上取整（即用戶評分個數(shù)為5時，5×0.1＝0.5，向上取整，隨機選擇1個）評分放入測試集中。

3.2 評價標準

使用均方根誤差RMSE和平均絕對誤差MAE作為評價標準。兩者通過計算預測的用戶評分與真實的用戶評分之間的偏差度量預測的準確性，RMSE或MAE值越小，推薦的質量越高。

其中，＾r(nóng)u，i為預測的用戶u對物 品i的評 分；ru，i為用戶u對物品i的真實評分；Rtest為測試集中的用戶 －物品對（u，i）。

3.3 對比實驗和實驗參數(shù)

采用的對比模型是經(jīng)典的基于物品的協(xié)同過濾算法，算法簡稱如下所述。

IBCF：實現(xiàn)的是文獻［5］中以皮爾遜相關系數(shù)作為相似度量的基于物品的協(xié)同過濾。

SC：本文中利用用戶重合相似度優(yōu)化鄰居后進行一次預測的算法。

SCFA：利用SC預測結果反饋修正評分數(shù)據(jù)后，進行二次預測的算法。其中的參數(shù)取α＝0.2，ε＝1，均為經(jīng)驗值。

3.4 實驗結果

在Epinions實驗數(shù)據(jù)集上，在IBCF算法和本文的SC算法、SCFA算法上針對所有用戶在RMSE和MAE 2個評價指標上進行對比，見表1所列。其中，SC、SCFA的RMSE和 MAE值選取的是以50為步長從K＝50到K＝1 000進行的20組實驗的均值。通過比較，發(fā)現(xiàn)在RMSE上SCFA算法比IBCF提高了6.0%，在MAE上提高了12.4%。因此，對于所有用戶，實驗結果好于傳統(tǒng)的IBCF算法的實驗結果。

表1 IBCF與SCFA關于所有用戶的RMSE和MAE值對比

對于SC和SCFA算法，以50為步長從K＝50到K＝1 000進行了20組實驗，如圖1所示。結果顯示，在RMSE上SCFA比SC提高了0.9%，如圖1a所示；在 MAE上提高了4.4%，如圖1b所示。對比結果顯示修正評分數(shù)據(jù)中的異常項有助于算法精度的提高。

將評分數(shù)少于10的用戶視為冷啟動用戶，比較IBCF和SCFA在這些冷啟動用戶上預測結果的RMSE和MAE值，如圖2所示。

由圖2結果可知，本文算法在RMSE上提高了12.4%，在MAE上提高了15.4%。這說明只要冷啟動用戶連接到了信任網(wǎng)絡中，基于信任的方法能更加有效地解決冷啟動用戶的推薦問題。

將初始鄰居（即直接鄰居加間接鄰居）的數(shù)目大于K的視為多鄰居的用戶，比較IBCF和SCFA預測結果的RMSE和MAE值，如圖3所示。

通過觀察圖3結果，發(fā)現(xiàn)本文算法在RMSE上提高了6.0%，在 MAE上提高了12.4%。這說明利用用戶相似度過濾掉有限相似的鄰居能夠有效提高推薦的精度。

通過上述實驗結果的對比，不難發(fā)現(xiàn)無論是在所有用戶，還是冷啟動用戶和多鄰居用戶上，相比傳統(tǒng)的基于物品的協(xié)同過濾算法，本文的SCFA算法都可以獲得更低的RMSE和MAE值，因此推薦的效果更好。

圖1 IBCF、SC和SCFA不同K值上所有用戶的RMSE和MAE值的比較

圖2 IBCF和SCFA不同K值上冷啟動用戶的RMSE和MAE值的比較

圖3 IBCF和SCFA不同K值上多鄰居的用戶的RMSE和MAE值的比較

4 結束語

本文提出了新的用戶相似度量方法，并通過一次預測結果反饋調節(jié)異常評分項。在真實數(shù)據(jù)集Epinions上進行實驗，結果顯示該方法比傳統(tǒng)的基于物品協(xié)同過濾算法具有更好的準確度。

［1］ Niemann K，Wolpers M.A new collaborative filtering approach for increasing the aggregate diversity of recommender systems［C］／／ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，2013：955－963.

［2］ Bellogin，Parapar J.Using graph partitioning techniques for neighbour selection in user－based collaborative filtering［C］／／ACM Conference on Recommender Systems，2012：213－216.

［3］ Koren Y.Factorization meets the neighborhood：a multifaceted collaborative filtering model［C］／／ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，2008：426－434.

［4］ Deshpande M，Kapypis G.Item－based top－N recommendation algorithms［J］.ACM Transactions on Information Systems，2004，22（1）：143－177.

［5］ Sarwar B，Karypis G，Konstan J，et al.Item－based collaborative filtering recommendation algorithms［J］.ACM International Conference on World Wide Web，2001，4（1）：285－295.

［6］ Karypis G.Evaluation of item－based top－N recommendation algorithms［C］／／International Conference on Information and Knowledge Management，2001：247－254.

［7］ Goldberg D，Nichols D，Oki B M，et al.Using collaborative filtering to weave an information tapestry［J］.Communications of the ACM，1992，35（2）：61－70.

［8］ Massa P，Avesani P.Trust－aware recommender systems［C］／／ACM Conference on Recommender Systems，2007：17－24.

［9］ Ma H，Yang H，Lyu M R，et al.SoRec：social recommendation using probabilistic matrix factorization［C］／／International Conference on Infornation and Knowledge Management，2008：931－940.

［10］ Yang X，Steck H，Guo Y，et al.On top－k recommendation using social networks［C］／／ACM Conference on Recommender Systems，2012：67－74.

［11］ Konstas I，Stathopoulos V，Jose J M.On social networks and collaborative recommendation［C］／／ACM SIGIR Conference on Research and Development in Information Retrieval，2009：195－202.

［12］ Yang X，Steck H，Guo Y，et al.Circle－based recommendation in online social networks［C］／／ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，2012：1267－1275.

［13］ Linden G，Smith B，York J.Amazon.com recommendations：item－to－item collaborative filtering［J］.IEEE Internet Computing，2003，4（1）：76－80.

［14］ Jamali M，Ester M.A matrix factorization technique with trust propagation for recommendation in social networks［C］／／ACM Conference on Recommender Systems，2010：135－142.

［15］ Koren Y，Bell R，Volinsky C.Matrix factorization techniques for recommender systems［J］.Computer，2009，42（8）：30－37.

［16］ Salakhutdinov R，Mnih A.Probabilistic matrix factorization［C］／／NIPS，2007：1257－1264.

［17］ Jamili M，Ester M.TrustWalker：a random walk model for combining trust－based and item－based recommendation［C］／／ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，2009：397－406.

［18］ Tang J，Gao H，Liu H，et al.eTrust：understanding trust evolution in an online world［C］／／ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，2012：253－261.