郭 雷 張 琨 陳洪雁 嚴 霞

（南京理工大學計算機科學與工程學院 南京 210094）

基于相似度質量的混合協同過濾算法?

郭 雷 張 琨 陳洪雁 嚴 霞

（南京理工大學計算機科學與工程學院 南京 210094）

在傳統協同過濾算法中一直面臨著冷啟動和數據稀疏等問題，導致推薦信息不夠準確。通過分析基于用戶的協同過濾算法和基于物品的協同過濾算法的各自特點提出一種新的混合協同過濾算法。改進相似度的計算方式來提高相似度的精準度，從近鄰相似度的均值和標準差出發(fā)對兩種協同過濾算法進行加權結合，同時引入控制因子提高預測的精度。以Movie Lens數據集進行實驗驗證，以平均絕對誤差作為實驗的測試標準。實驗結果表明，在評分矩陣極度稀疏的條件下該算法提高了推薦的準確度。

推薦算法；協同過濾；相似度

1 引言

隨著當今社會互聯網的普及和信息技術的飛速發(fā)展，信息過載問題也隨之而來，如何從海量的信息中準確快速地獲取自己想要的信息顯得尤為重要。過往的搜索引擎在一定程度上可以滿足用戶對信息檢索的需求，但對于檢索的結果往往千篇一律，無法根據用戶的興趣和偏好主動提供個性化信息。在這種背景下推薦系統應運而生，與搜索引擎不同，個性化推薦系統可以基于個人的行為數據為用戶提供定制的信息［1］。

目前主流的推薦系統主要有基于內容的推薦系統和協同過濾推薦系統［2］?；趦热莸耐扑]算法是建立在物品的內容信息上做出推薦的，不需要依賴用戶對物品的評價意見，更多的需要用機器學習的方法從關于內容的特征描述和事例中得到用戶的興趣資料，因此該算法要求信息內容要容易抽取成有意義的特征，并且特征內容要具有良好的結構性。協同過濾推薦算法通過對用戶的行為進行分析來挖掘用戶的興趣，從用戶群中找出與目標用戶興趣相近的用戶并通過這些近鄰用戶對物品的評價值來預測目標用戶對該物品的喜好程度［3～4］。因為無需對物品內容進行分析，協同過濾在推薦圖片、音樂、電影等方面具有更好的優(yōu)勢，在推薦系統中被廣泛使用。

根據協同過濾的相關特性，將協同過濾分為兩類：基于用戶（User-Based）協同過濾算法和基于物品（Item-Based）協同過濾算法。基于用戶的協同過濾，通過用戶對不同物品的評分來計算物品之間的相似性，再通過物品之間的相似性預測評分做出推薦，但隨著用戶的增加會不斷地影響預測的結果導致預測偏差增大［5］。基于物品的協同過濾，通過不同用戶對物品的評分來計算物品之間的相似性，再通過用戶之間的相似性預測評分做出推薦，可能造成推薦的單一化導致預測結果不準確。目前，兩種協同過濾算法均存在數據稀疏、冷啟動和可擴展性差等問題［6～7］。通過對這些缺點的分析，提出一種基于用戶和物品的加權混合型協同過濾算法來提高預測的準確性。

2 傳統協同過濾算法

首先我們對基于用戶協同過濾算法和基于物品協同過濾算法進行詳細介紹。兩種基本的協同過濾算法均可分為四個步驟：創(chuàng)建用戶-物品評分矩陣，相似性計算，近鄰選擇，評分預測。

2.1 基于用戶協同過濾算法

基于用戶協同過濾推薦的主要思想可以簡述為：首先，給定一個用戶-物品的評分數據集，找出與當前用戶過去有相似偏好的其他用戶，這些用戶被稱為近鄰用戶；然后，對當前用戶沒有見過的物品，利用其近鄰對該物品的評分來計算預測值。這種算法的潛在假設有兩點：如果用戶過去有相似的偏好，那么他們未來也會有相似的偏好；用戶偏好不會隨時間而變化。

1）創(chuàng)建用戶-物品評分矩陣

推薦系統中包含m個用戶記為{u1，u2，…，um}和 n個物品記為{i1，i2，…，in}，則創(chuàng)建一個 m×n的用戶-物品評分矩陣 Rm×n。矩陣中的元素 Ri，j（1≤i≤m，1≤j≤n）表示用戶i對物品 j的評分，評分一般為1～5的整數，評分越高表示用戶對物品的興趣程度越高，如果Ri，j=0則表示用戶i未對 j進行評分。

2）相似性計算

目前計算相似度的方法主要有：皮爾森相關系數、余弦相似度、歐幾里得距離相似度、曼哈頓距離相似度。在基于用戶協同過濾中采用最常用的皮爾森相關系數進行計算，該方法可以反應出兩個變量之間的線性相關程度，取值范圍從-1（強負相關）到+1（強正相關），若取值為0則表明不存在線性相關關系。

將用戶u和用戶v共同評論過的物品集合記為 I(u)∩I(v)，用戶 u和用戶 v的相似度記為sim(u，v)，則皮爾森相關系數公式可以表示為

3）近鄰選擇

在得到用戶之間的相似度之后，對目標用戶與其他用戶之間的相似度進行篩選，挑選相似度最大的K個用戶組成近鄰集合記為N(u)。K值的大小會對預測的結果產生影響：當近鄰個數K太高時，會給預測帶來額外的“噪聲”；當K太小時，預測的結果可能出現負面影響。因此近鄰個數的選擇應控制在合理的范圍內。

4）評分預測

目標用戶u對物品i的預測評分記為pred(u，i)可以通過如下公式計算得出：

其中，ux為近鄰集合中的某一用戶；Rux，i為用戶u對物品i的評分；為用戶u對物品評分xx的均值；sim(u ，ux)為用戶u與用戶ux的相似度。

2.2 基于物品協同過濾算法

基于物品協同過濾的主要思想是利用物品之間的相似度來預測用戶對物品的興趣程度。

1）創(chuàng)建用戶-物品評分矩陣

和基于用戶協同過濾算法一樣，需要對數據進行相同的處理生成用戶-物品評分矩陣。

2）相似性計算

在基于物品協同過濾中，余弦相似度是比較常見的相似性計算方法。由于基本的余弦相似度算法沒有考慮用戶評分均值之間的差異，因此使用修正余弦相似度方法計算物品之間的相似度。將同時評論過物品i和物品 j的所有用戶集合記為U(i)∩U(j)，物品i和物品 j的相似度記為sim(i，j)，則有：

其中，u表示同時評分過物品i和物品 j的用戶；-Ru表示用戶u對物品評分的均值。

3）近鄰選擇

與基于用戶協同過濾的近鄰選擇類似，篩選出與目標物品相似度最大的K個物品組成近鄰集合記為N(i)。同樣近鄰的個數應控制在合理的范圍內。

4）評分預測

預測目標用戶u對物品i的評分公式如下：

其中，iy為近鄰集合中的某一物品；Ru，iy為用戶u對物品iy的評分；sim(i ， iy)為物品i與物品iy的相似度。

3 改進的協同過濾算法

在協同過濾算法中，基于用戶協同過濾通過橫向對比各用戶之間的興趣相似度可以找出目標用戶的興趣群組，從而使推薦的結果準確性高一些，更注重社會化而缺少一定的個性化；基于物品協同過濾是通過物品間的對比，根據用戶歷史行為推薦相似物品，更注重個性化，但是推薦的結果準確性較低一些［8］。為了使推薦的結果兼具個性化和更高的準確率，本文將兩種協同過濾算法結合起來［9］。

3.1 相似度計算的改進

在利用皮爾森相關系數或者修正余弦相似度計算相似度時雖然很直觀，但是沒有考慮到兩兩用戶（或物品）之間共同評分項目數目對預測結果的影響。由于數據稀疏性往往比較大，有時會出現兩個原本相似較小的用戶（或物品）恰好在較少的共同評分項上擁有較大的相似度，從而導致預測不準確［10］。如下表1中用戶u1與用戶u2的共同評分項只有1項，而用戶u1與用戶u3的共同評分項有3項，u1與u2的相似度為0.47，u1與u3的相似度為0.45，若直接判定用戶u1與用戶u2的相似度高于用戶u1與u3的相似度顯然是不合理的。

表1 皮爾森相關系數計算用戶間相似度

為了使用戶（或物品）之間的相似度計算更加合理，結合共同評分項數量對相似度的影響，本文使用加權型的相似度計算方式。用戶之間的相似度為用戶之間共同評分項數量與該用戶和其他用戶最大共同評分項數量的比值，再對皮爾森相關系數進行加權；物品之間的相似度為物品之間共同評分項數量與該物品和其它物品最大共同評分項數量的比值，再對修正余弦相似度進行加權。公式分別為

式中，| Iu∩Iv|代表用戶u與用戶v共同評分過物品的數量，max | Iu∩Ix|代表用戶u與其他用戶共同評分過物品的數量最大值；|Ui∩Uj|代表共同評分過物品i與物品 j的用戶的數量，max| Ui∩Uy|代表共同評分過物品i與其它物品的用戶的數量最 大 值 。 由 上 述 公 式 可 知 |sim'(u，v)|≤1 ，|sim'(i，j)|≤1成立。另外，在改進的相似度算法中，由于max | Iu∩Ix|不一定與max| Iv∩Ix|相等，因此會出現 sim'(u，v)≠sim'(v，u)的情況，所以用戶 u 與用戶v的相似度sim'(u，v)和用戶v與用戶u的相似度sim'(v，u)是兩種獨立的相似度，記為獨立的兩個值；同理，物品i與物品 j的相似度sim'(i，j)和物品 j與物品i的相似度sim'(j，i)也記為兩個獨立的值。

使用改進后相似度算法計算表1中用戶u1與其他用戶之間的相似度，并與改進前相似度進行對比，結果如表2所示。

表2 兩種方式計算相似度的對比

可以看出相似度算法改進后，u1與u2的相似度 sim'(u1，u2)=0.12 ，u1與 u3的 相 似 度sim'(u1，u3)=0.34 ， 通 過 比 較 可 以 得 出sim'(u1，u2)＜ sim'(u1，u3)，從而使近鄰的選擇更加符合實際要求，減小了共同評分項數量的差距對用戶（或物品）之間相似度的影響，有效降低了數據稀疏度對相似度計算的影響。

3.2 近鄰集合的選擇

在得出用戶（或物品）的相似度之后，通常有兩種方法來確定近鄰集合：一種是通過相似度閾值來選擇，凡是大于該閾值的用戶（或物品）都視為近鄰；另一種則是選取K個相似度最大的用戶（或物品）作為近鄰［11］。這兩種方法都有各自的局限性，本文使用兩種方法的混合，在相似度大于閾值γ的情況下選取最大的K個用戶（或物品）作為近鄰。

基于用戶的近鄰集合可以表示為

基于物品的近鄰集合可以表示為

3.3 評分預測

在混合協同過濾算法中，引入權重因子α（α∈[0，1]）來平衡基于用戶協同過濾和基于物品協同過濾的權重，使推薦結果具有更高的準確度，整體思路可以表示為

為了進一步提高預測結果的合理性和準確度，本文對權重因子α進行改進。在每個目標用戶或目標物品的近鄰集合中，K個近鄰的相似度大小會對預測的結果有著不同程度的影響，相似度的值越大一般會對預測結果有著更多積極性的影響，反之則反。因此文中再引入一個權衡因子β，β表示為

其中，E表示目標用戶或目標物品近鄰集合中各個近鄰相似度的平均值；σ則表示近鄰集合中各個近鄰相似度的標準差。E的值越大表明近鄰集合整體的相似度越大，但是在近鄰中也會出現個別相似度較低的用戶（或物品），雖然對整體的相似度影響不大，但是對評分的預測會有影響。因此，綜合標準差σ來評判近鄰集合整體相似度的大小和密集程度，進而衡量近鄰集合的整體質量。

對于基于用戶協同過濾的權衡因子記為βu，表示為

對于基于物品協同過濾的權衡因子記為βi，表示為

為了將兩種協同過濾的權衡因子結合起來，還需要引入一個控制因子 μ（μ∈[0，1]）使權重因子α控制在0到1之間，最終得到α的表達式為

權重因子α決定了混合算法對基于用戶協同過濾和基于物品協同過濾算法的依賴程度，當α=1時即為單純的基于用戶協同過濾算法，當α=0時即為單純的基于物品協同過濾算法。考慮到用戶評分數據的稀疏性，實際中一些用戶可能沒有足夠的相似用戶，即相似度數值大于閾值γ的近鄰個數不足K個，以往的算法會忽略這一問題依舊選擇最大的K個相似用戶來預測評分，導致預測的準確度大大降低。本文提出的新算法通過以下思路來解決這個問題：

當 ||N(u)=K且 ||N(i)=K時，預測評分由文中提出的混合協同過濾算法計算得出，此時0＜α＜1；

當 ||N(u)=K且 ||N(i)≠K時，預測評分相當于由基于用戶協同過濾算法計算得出，此時α=1；

當 ||N(u)≠K且 ||N(i)=K時，預測評分相當于由基于物品協同過濾算法計算得出，此時α=0；

當 ||N(u)≠K且 ||N(i)≠K時，意味著相似用戶和相似物品均不滿足要求，因此不予置評，pred( )u，i=0。

4 實驗及分析

4.1 實驗數據集介紹

本文使用Movie Lens數據集作為實驗數據來進行測試，數據集包含943個用戶對1682部電影的評分，評分的分數為1到5整數，評分記錄總共為100000條。由下式對數據集稀疏度的計算結果可以看出該數據集是非常稀疏的：

4.2 實驗評定標準

本文采用平均絕對誤差MAE來評價預測的質量，MAE可以衡量預測值和真實評分之間的平均偏離程度。MAE的值越低，表明預測的精度就越高，計算公式為

式中，Ru，i表示用戶u對物品i的預測評分；Ru，i表示用戶u對物品i的真實評分；N表示待預測評分的總數量。

4.3 實驗過程

為了減少評分的偶然性帶來的數據偏差，本文使用交叉驗證對數據集進行實驗，從100000條評分中隨機抽取20000條評分作為測試集，剩下的80000條評分作為訓練集，每次預測重復五次，選取適中的值作為預測結果。

在提出的混合協同過濾中控制因子μ對權重因子α有著直接影響的，因此確定控制因子μ的最佳取值是本實驗的重點，同時包括近鄰集合個數K的取值對實驗結果的影響。因為相似度閾值γ對權重因子α沒有直接影響，為了簡化實驗我們將γ置為0。

實驗中，控制因子μ∈[0，1]的取值間隔設置為0.1，將近鄰集合個數K分別設置為10、20、30、40、50。得到的實驗結果如圖1所示。

圖1 控制因子μ的取值對MAE的影響

從上圖中可以看出：通過縱向對比，隨著近鄰集合個數K的增加，MAE的變化會越來越小趨于穩(wěn)定；通過橫向對比，隨著控制因子μ的增加，MAE會先減小后增大?？傮w上，μ在0.1～0.3之間時MAE的變化趨于平緩，當μ=0.2時取得最優(yōu)值，近鄰集合個數K=50時MAE取得最小值。

在得出控制因子μ的最優(yōu)值后，進一步驗證文中提出的混合協同過濾算法的推薦精準度，將本文提出的混合協同過濾與兩種傳統的協同過濾進行對比，控制因子μ置為最優(yōu)值0.2，近鄰集合個數K同樣從10增加到50，得到的實驗結果如圖2所示。

圖2 三種不同協同過濾算法的MAE比較

可以看出文中提出的混合協同過濾的實驗結果MAE更低一些，因此有著更高的推薦準確度。

5 結語

本文在前人的基礎上，針對基于用戶協同過濾和基于物品協同過濾的不同優(yōu)勢和缺點，從混合模型的角度切入，對兩種基礎的協同過濾進行了改進。創(chuàng)新性的將近鄰集合中相似度的均值和標準差引入到混合算法中來平衡兩種基礎協同過濾算法的權重。最后通過實驗與兩種傳統的協同過濾算法進行對比，驗證了本文算法的確實提高了預測精度，使推薦更加準確。

［1］劉建國，周濤，汪秉宏.個性化推薦系統的研究進展［J］.自然科學進展，2009，01：1-15.LIU Jianguo，ZHOU Tao，WANG Bingcheng.Research progress of personalized recommendation system［J］.Progress in Natural Science，2009，01：1-15.

［2］王國霞，劉賀平.個性化推薦系統綜述［J］.計算機工程與應用，2012，07：66-76.WANG Guoxia，LIU Heping.Summary of personalized recommendation system［J］.Computer engineering and Applications，2012，07：66-67.

［3］李桃迎，李墨，李鵬輝.基于加權Slope one的協同過濾個性化推薦算法［J］.計算機應用研究，2016，08：1-6.LI Taoying，LI Mo，LI Penghui.Personalized collaborative filtering recommendation algorithm based on weighted Slope one［J］.Computer application research，2016，08：1-6.

［4］SCHAFER J B，KONSTAN J A，RIEDL J.E-commerce recommendation application［J］.Data Mining and Knowledge Discovery，2001，5（1/2）：115-153.

［5］范波，程久軍.用戶間多相似度協同過濾推薦算法［J］.計算機科學，2012，01：23-26.FAN Bo，CHENG Jiujun.collaborative filtering recommendation algorithm based on User's Multi-similarity［J］.Computer science，2012，01：23-26.

［6］LIU Qingwen，XIONG Yan，HUANG WenChao.Combining User-Based and Item-Based Models for Collaborative Filtering Using Stacked Regression［J］.Chinese Journal of Electronics，2014，04：712-717.

［7］劉慶鵬，陳明銳.優(yōu)化稀疏數據集提高協同過濾推薦系統質量的方法［J］.計算機應用，2012，04：1082-1085.LIU Qingpeng，CHEN Mingrui.Optimization of sparse data sets to improve quality of collaborative filtering systems［J］.Computer application，2012，04：1082-1085.

［8］BA Qilong，LI Xiaoyong，BAI Zhongying.Clustering Collaborative Filtering Recommendation System Based on SVD Algorithm［A］.Proceedings of 2013 IEEE 4th International Conference on Software Engineering and Service Science［C］，2013：5.

［9］黃瓊，馮軍煥.混合協同過濾個性化推薦算法研究［J］.計算機光盤軟件與應用，2014，04：111-113.HUANG Qiong，FENG Junhuan.Research on Personalized Recommendation Algorithm Based on hybrid collaborative filtering［J］.Computer CD software and application，2014，04：111-113.

［10］ZHANG Ye，SONG Wei.A Collaborative Filtering Recommendation Algorithm Based on Item Genre and Rating Similarity［C］//Proceedings of the 2009 International Conference on Computational Intelligence and Natural Computing（Volume 2），2009：4.

［11］查九，李振博，徐桂瓊.基于組合相似度的優(yōu)化協同過濾算法［J］.計算機應用與軟件，2014，12：323-328.ZHA Jiu，LI Zhenbo，XU Guiqiong.An optimized collaborative filtering algorithm based on combined similarity［J］.Computer applications and software，2014，12：323-328.

Hybrid Collaborative Filtering Algorithm Based on Quality of Similarity

GUO LeiZHANG KunCHENG HongyanYAN Xia
（School of Computer Science&Engineering，Nanjing University of Science and Technology，Nanjing 210094）

In the traditional collaborative filtering algorithm has been facing a cold start and data sparseness and other issues，resulting in the recommendation information is not accurate enough.A new hybrid collaborative filtering algorithm is proposed by analyzing the characteristics of user-based collaborative filtering algorithm and item-based collaborative filtering algorithm.This paper combines the weighted mean of two similar filtering algorithms with the mean and standard deviation of the similarity，and introduces the control factor to improve the precision of the prediction.Experiments are carried out with the Movie Lens dataset，and the average absolute error is used to measure the results.The experimental results show that the proposed algorithm improves the accuracy of the proposed algorithm when the scoring matrix is extremely sparse.

recommendation algorithm，collaborative filtering，similarity

TP301

10.3969/j.issn.1672-9722.2017.11.005

Class Number TP301

2017年5月9日，

2017年6月29日

郭雷，男，碩士研究生，研究方向：機器學習、數據挖掘。張琨，女，博士，教授，研究方向：復雜網絡理論與應用、可信計算、網絡與信息安全。陳洪雁，女，碩士，助理研究員，研究方向：信息化建設、網絡安全。嚴霞，女，碩士研究生，研究方向：復雜網絡，數據挖掘。