基于項目相似度計算改進的協同過濾算法

[摘要] 本文通過對傳統相似度計算的分析，對傳統相似度計算進行了改進，試驗結果表明本文提出的相似度計算能夠極大提高相似度計算的精確性，改善推薦精度。

[關鍵詞] 電子商務 推薦系統 協同過濾 相似度計算 數據挖掘

一、引言

電子商務推薦系統是模擬銷售人員向網絡客戶推薦商品的系統，推薦精度的高低直接影響了用戶的購買量，也影響著用戶對該系統的信任度，信任程度的高低決定了用戶對該系統的使用率，從而影響用戶瀏覽實現了推薦功能的網站進行物品購買的次數。

當前的信息推薦技術主要有：協同過濾推薦、基于內容推薦、基于人口統計信息推薦、基于效用推薦、基于知識推薦、基于規則推薦。

二、協同過濾算法介紹

1.基于項的協同過濾算法介紹

基于項的協同過濾是通過相似度的計算，找出當前用戶未評分項目的前k個相似項目，根據用戶對這k個項目的評分預測當前用戶對未評分項目的評分值，按照評分值大小進行推薦。推薦分為兩個步驟:①找出當前用戶（這里指系統進行項目推薦的對象）的未評分項目的相似項目;②根據每個未評分項目的相似項目評分預測當前用戶對未評分項目的評分，根據預測評分的高低，推薦前N個評分較高的項目給用戶。

（1）項目相似度的計算

計算方法主要包括三種方法:

①基于余弦的相似度計算

(1)

其中，表示項目i，j的相似性，和表示對于項目i和j存在有共同用戶對此兩項評分的分別的評分集合。

實際應用中，該公式存在如下問題：因為，數據稀疏性是協同過濾使用中遇到的一個問題， 尤其是推薦系統初次使用時，數據庫中的用戶評分極其稀少，所以在這種情況下，存在兩個項目之間只有1～2個共同的用戶，如果這1～2個共同用戶對這兩個項目的品質認為是無差異的，則用余弦相似性進行計算時得出的結果也是認為兩者很相似。事實上，基于項目的協同過濾算法是認為如果絕大多數用戶對兩項目的感覺是無差異的，則證明這兩項目具有相同的品質，那么具有相同品質的兩項目對于待推薦用戶來說也是無差異的。可是，當兩項目只有一兩個共同評分用戶，項目相似性的計算僅僅是反映了這一兩個用戶所關注的項目特征在這兩個項目中是否相同，而這一兩個用戶所關注的項目特征并不一定是待推薦用戶所關注的特征，并且一兩個特征的相似也不能真正反映兩個項目之間的相似性。

②基于相關性的相似度計算

(2)

其中，U表示對項目i和j都有評分的用戶集合，和分別表示用戶u對i與j的評分，和表示集合U中所有用戶對i和j評分的平均值。

相關性的相似度計算是將用戶對項目i、j的打分看作是一個兩個隨機變量，通過計算兩個隨機變量分布的相似性得出兩項目的相似性。

③調整余弦的相似度計算

(3）

其與余弦相似性不同在于：將不同用戶的打分規?？紤]進去，其中表示用戶u的平均打分。余弦相似性沒有考慮不同用戶的打分規模會造成平均打分較高的用戶對相似度計算作用大于其余用戶，使得每個用戶的打分對相似度計算的貢獻率不相等，造成相似度計算不如調整余弦相似度的計算精確。

在實際應用中，在數據庫中打分數據分布極其稀疏的情況下，調整余弦的相似度的度量也會遇到在余弦相似性計算中所遇到的情況，即當項目只有一兩個共同評分用戶，項目相似性的計算僅僅是反映了這一兩個用戶所關注的項目特征在這兩個項目中是否相同，而這一兩個用戶所關注的項目特征并不一定是待推薦用戶所關注的特征，并且一兩個特征的相似也不能真正反映兩個項目之間的相似性。另外，在進行算法精度測試試驗中，發現調整余弦的相似度計算有出現分母為0的情況。在程序測試過程中發現，分母為0有兩種情況：

a)兩項目只有一個共同打分的用戶，該用戶對很少的項目打分且打分值相同，即且。這種情況，按照余弦相似性的思想，可以認為兩項目的相似度值為1。

b)兩項目有為數很少的共同評分用戶，且出現或的情況。在這種情況下，調整余弦無法正確計算出兩項目之間的相似度，因此在數據極其稀疏的條件下，不宜采用調整余弦相似度進行度量。

2.評分預測公式

（1）權重和法

(4）

其中，表示項目i和j的相似度，表示用戶u對項目j的評分，n表示選出n個數目的最近鄰項目。該預測公式適用于用戶評分數目相當大的情況。（基于項目相似度計算經典算法）當用戶評分數目較少的情形下，相似度的計算本身就不精確，而該公式對未評分項目的預測，完全依賴于不精確的相似度值選擇的相似項目的打分進行預測，精度很低。

（2）線性回歸法

目標項目i對應向量為，相似項目N對應向量為，則線性回歸模型為(5)

其中，的值由目標向量與相似向量確定，為誤差項。

三、基于項目相似度計算改進算法

在第2節中，提到余弦相似度和調整余弦相似度都會碰到的問題：當兩項目只有一兩個共同評分用戶，項目相似性的計算僅僅是反映了這一兩個用戶所關注的項目特征在這兩個項目中是否相同，而這一兩個用戶所關注的項目特征并不一定是待推薦用戶所關注的特征，并且一兩個特征的相似也不能真正反映兩個項目之間的相似性。

基于上述問題，本節提出了對這兩種相似度計算的改進公式。本節認為，兩項目分別的評分用戶越多，則這兩項目的共同評分項目也應該越多，因為一用戶對一個項目感興趣且有打分，則他對該項目的相似項目也應感興趣且應有打分?；谶@種觀點，本節對余弦相似度和調整余弦相似度公式進行改進，并用基于改進的余弦相似度公式和傳統余弦相似度公式計算項目間相似性來進行實驗。由于在第2節中提到在數據稀疏的條件下，調整余弦相似度公式計算中會遇到分母為零的可能，且對調整余弦相似度公式的改進與余弦相似度公式改進方式是相同，故可以認為基于余弦相似度公式和改進公式的對比試驗結果可以代表調整余弦改進公式的改進效果。

1.改進的相似度計算公式

（1）改進的余弦相似度計算公式

(6）

其中，mutual_num為對項目i、j都評分的用戶數目，item_num表示對項目i、j中任何一個有評分的用戶集合的數目。

（2）改進的調整余弦相似度計算

(7)

2.本文提出的對基于項的評分預測的公式

（1）提出的評分預測公式

(8）

其中，為用戶u所有評分的平均值，為i和j項目的相似度，n為選擇前n個最近鄰。當時，令。

（2）說明

①從用戶對相似項目評分的相似性考慮，相似項目評分與該用戶平均評分的偏差和預測項目的評分與該用戶平均評分的偏差也相似。

②與基于向量評分不同在于：基于向量的評分只適合于評分數目十分大的用戶，當用戶評分數量小時，最相似的幾個項目可能用戶沒有評分，因此導致預測精度降低；另外，當每個項目的評分數量很少時，項目相似性預測精度下降，使得預測精度降低，而本文提出的預測公式可以降低相似項目對預測項目評分的貢獻率。

③在計算中若，即當用戶u對相似項目j沒有評分時，令，消除沒評分時，的影響。

實驗證明，在數據極其稀疏條件下，本文提出的預測公式有很好的預測效果。

四、實驗過程及結果分析

1.數據來源

本文采用Movielens站點提供的數據集，該數據集包括943個用戶對1682部電影的100000條評分，評分取值為（1，2，3，4，5）中任一個數，值越大說明用戶喜好程度越高，每個用戶至少評價了20部電影。

2.測試方法

本文隨機抽取其中80000條評分作為訓練集，剩余20000條數據作為測試集，分別采用余弦相似性（公式1）和本文提出的改進地余弦相似性（公式6）進行相似度度量，并都采用本文提出的評分預測公式進行預測。

3.評測標準

本文采用平均絕對誤差MAE作為評測標準，它是常用的推薦算法質量評價標準。

(9）

num為算法評分項目數目，為基于算法預測的評分，測試集中用戶原始打分。

4.試驗結果

圖

五、結論

從上圖可以看到，本文提出的改進算法的精度明顯優于傳統算法，這證明改進的余弦相似度計算方法比傳統余弦相似度算法準確度高，因為它將每個項目的被評分規模考慮進去，排除了傳統余弦相似度算法因為某些項目的打分用戶數目大導致與其他并非很相似的項目計算結果很相似的可能。圖中顯示，當最近鄰數目為10時，改進算法的精度最高；當最近數目大于10時，隨著最近鄰數目的增多，預測精度反而降低，從10以后的最近鄰的相似度開始降低。在傳統算法中，最近鄰數目從40到50之間時，預測精度反而上升，這說明最近鄰從40到50之間的存在著可能更相似的用戶。通過這些對比，證明了本文的改進算法的有效性。

參考文獻:

[1]劉瑋:電子商務系統中的信息推薦方法研究.情報科學.2006，2

[2]Badrul Sarwar，George Karypis，Joseph Konstan，etc.Item-Based Collabrative Filtering Recommendation Algorithms.WWW10.2001

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。