基于改進相似性度量的項目協同過濾推薦算法

于金明，孟 軍，吳秋峰

(1.東北農業大學 工程學院，哈爾濱 150030； 2.東北農業大學 理學院，哈爾濱 150030)

基于改進相似性度量的項目協同過濾推薦算法

于金明1，孟 軍2*，吳秋峰2

(1.東北農業大學 工程學院，哈爾濱 150030； 2.東北農業大學 理學院，哈爾濱 150030)

(*通信作者電子郵箱15204677362@163.com)

針對傳統協同過濾推薦算法遇到冷啟動情況效果不佳的問題，提出一種基于項目相似性度量方法(IPSS)的項目協同過濾推薦算法(ICF_IPSS)，其核心是一種新的項目相似性度量方法，該方法由評分相似性和結構相似性兩部分構成：評分相似性部分充分考慮兩個項目評分之間的評分差、項目評分與評分中值之差，以及項目評分與其他評分平均值之差；結構相似性部分定義了共同評分項目占所有項目比重, 并懲罰活躍用戶的逆項目頻率(IIF)系數。在Movie Lens和Jester數據集下測試算法準確率。在Movie Lens數據集下，當近鄰數量為10時， ICF_IPSS的平均絕對偏差(MAE)和均方根誤差(RMSE)分別比基于Jaccard系數的均方差異系數的項目協同過濾算法(ICF_JMSD)低3.06%和1.20%；當推薦項目數量為10時，ICF_IPSS的準確率和召回率分別比ICF_JMSD提升67.79%和67.86%。實驗結果表明,基于IPSS的項目協同過濾算法在預測準確率和分類準確率方面均優于基于傳統相似性度量的項目協同過濾算法，如ICF_JMSD等。

協同過濾;推薦算法；相似性度量；評分相似性；結構相似性；冷啟動

0 引言

個性化推薦系統是一種基于大規模數據挖掘的智能平臺，可以為用戶提供完整的個性化決策支持和信息服務。其主流算法包括：協同過濾推薦、基于內容推薦、基于關聯規則推薦、基于效用推薦、基于知識推薦、組合推薦等[1]。

協同過濾推薦算法是個性化推薦系統中應用最早和最為成功的算法之一。協同過濾推薦算法主要有兩類：基于用戶的協同過濾推薦算法和基于項目的協同過濾推薦算法。協同過濾推薦算法主要通過獲取用戶的偏好信息，計算用戶間(或項目間)的相似性和根據相似度預測目標用戶對目標項目的評分來實現[2]。

協同過濾推薦算法的關鍵步驟是計算用戶間(或項目間)的相似性。國內外學者圍繞協同過濾算法中相似性度量方面開展了一系列的研究。如Ahn[3]提出修正余弦相似性度量方法(Ajusted Cosine Correlation, ACC)，部分改進了余弦相似性的缺陷; Shardanand等[4]考慮到評分的正負性，提出了約束皮爾遜相關系數(Constrained Pearson Correlation Coefficient, CPCC); Herlocker等[5]提出了權重皮爾遜相關系數(Weighted Pearson Correlation Coefficient, WPCC)，將共同評分項目數量考慮在內; Jamali等[6]提出了將傳統的皮爾遜相關系數與Sigmoid函數相結合形成一種基于Sigmoid函數的相似性度量方法(Sigmoid-based Pearson Correlation Coefficient, SPCC)能減弱共同評分項目少的用戶(或項目)之間的相似性; Bobadilla等[7]提出了將均值平方差異函數(Mean Square Difference, MSD)與Jaccard系數結合形成基于Jaccard系數的均方差異系數(Jaccard-based Mean Square Difference, JMSD)。上述方法遇到冷啟動問題(即新用戶和新項目的評分信息少的情況)時，其準確性受到影響。

本文僅圍繞協同過濾推薦算法中項目相似性度量進行分析與改進，提出一種新的項目相似性度量方法，該度量方法能夠解決冷啟動問題。該項目相似性度量方法由評分相似性和結構相似性兩部分構成，其中，評分相似性部分充分考慮兩個項目評分之間的評分差(用Proximity記，詳見1.3節 )、項目評分與評分中值之差(用Significance記，詳見1.3節)，以及項目評分與其他評分平均值之差(用Singularity記，詳見1.3節)；結構相似性部分定義共同評分項目占所有項目比重并懲罰活躍用戶的IIF(Inverse Item Frequency)系數，形成一種新的項目相似性度量方法(IIF-based Proximity-Significance-Singularity, IPSS)。將IPSS度量方法融入到基于項目的協同過濾推薦算法，提出基于IPSS-ITEM的協同過濾推薦算法(IPSS-based Item Collaborative Filtering, ICF_IPSS)。為了驗證該協同過濾推薦算法的有效性，在Movie Lens和Jester等2個數據集測試，該算法在預測準確率和分類準確率方面面對冷啟動情況時均表現出較好效果。

1 基于IPSS-ITEM的協同過濾推薦算法

1.1 基于項目的協同過濾推薦算法

基于項目的協同過濾推薦算法是基于此類假設：若大多數喜歡項目i的用戶也喜歡項目j，則i和j就有較高相似度。算法步驟[8]如下：

步驟1 目標項目最近鄰搜尋。在計算項目之間的相似性基礎上，根據相似性由高到低找出目標項目i的前k個最近項目構成最近鄰集合。

步驟2 產生推薦。根據目標用戶對目標項目的最近鄰項目的評分及其之間相似性加權計算預測評分(式(1))，以此構建Top-N推薦列表。

假設項目i有k個最近項目，S是最近鄰集合，融合項目間相似性sim(i,j)計算目標用戶u對目標項目i的預測評分：

(1)

其中：sim(i,j)代表項目i和最近項目j的相似度，Ruj代表用戶u對項目j的評分。

1.2 傳統項目相似性度量方法分析

用于度量項目間相似性的方法有很多，這些方法多是從余弦相關性(Cosine Correlation, CC)和皮爾遜相關性(Pearson Correlation Coefficient, PCC)方法變形而來，本文以這兩種最傳統的相似性度量方法為例，分析其缺點。

1)余弦相關性(CC)。

將n個用戶對項目i和項目j的評分視為n維向量，項目i和項目j的相似性即為相應兩個n維向量的夾角余弦，定義[9]為:

(2)

其中Rui代表用戶u對項目i的評分。

2)皮爾遜相關性(PCC)。

該方法通過計算兩個項目之間的皮爾遜相關系數來確定項目間相似性，定義為:

(3)

在實際推薦系統中，會出現冷啟動情況，即共同評分過項目i與項目j的用戶量很少甚至沒有，因此，傳統項目間相似性度量方法存在一定的弊端。如果共同評分過項目i與項目j的用戶數量為1，不管該用戶對項目i與項目j的評分值為多少，用式(2)計算的結果總為1，擴大了項目間的相似性(即本來相似性較低的兩個項目的相似性度量結果較高)。而對于式(3)，分子分母總為0，公式沒有意義，不能計算項目間相似性。傳統的相似性度量方法在計算項目相關性時都會存在一定的誤差，計算結果可能會擴大或縮小項目間相關性(即本來相似性較高的兩個項目的相似性度量結果較低)。

1.3 IPSS的項目相似性度量方法

基于項目的協同過濾推薦算法的關鍵步驟是計算項目間相似性，以此搜索目標項目的k個最近項目。本文提出了一種新的項目相似性度量方法(IPSS)，能夠有效解決其他協同過濾推薦算法遇到冷啟動情況效果不佳的問題。

IPSS相似性度量方法由評分相似性和結構相似性兩部分構成，其中，評分相似性部分充分考慮兩個項目評分之間的評分差、項目評分與評分中值之差，以及項目評分與其他評分平均值之差；結構相似性部分定義共同評分項目占所有項目比重并懲罰活躍用戶的IIF系數，形成一種新的項目相似性度量方法。

在評分相似性部分，融合了兩個項目評分之間的評分差(Proximity)、項目評分與評分中值之差(Singularity)，以及項目評分與其他評分平均值之差(Significance)等3個因素，項目i和j間的評分相似性PSS(i,j)定義為：

(4)

其中:Uij為所有評價過項目i和j用戶的集合。PSSu(Rui,Ruj)為用戶u對項目i和j間的評分相似性。

用戶u對項目i和j間的評分相似性PSSu(Rui,Ruj)定義為:

PSSu(Rui,Ruj)=Proximity(Rui,Ruj)·

Significance(Rui,Ruj)·Singularity(Rui,Ruj)

(5)

其中:Proximity(Rui,Ruj)反映兩個項目評分之間的評分差，其定義為:

(6)

Significance(Rui,Ruj)反映項目評分與評分中值之差，其定義為:

Significance(Rui,Ruj) =

(7)

其中:Rmed代表評分范圍的評分中值，若評分范圍為{1,2,3,4,5}，則Rmed=3。

Singularity(Rui,Ruj)反映用戶u對項目i和j的評分平均值與用戶u對所有項目評分平均值之差，其定義為:

Singularity(Rui,Ruj)=

(8)

IIF系數定義為：

(9)

其中:Nu(i,j)代表既評價過項目i又評價過項目j的用戶數，N(i)和N(j)分別代表評價過項目i和項目j的用戶數。

IPSS相似性度量函數是由評分相似性和結構相似性組成，由式(4)和式(9)共同定義IPSS相似性度量函數為：

IPSS(i,j)=PSS(i,j)·IIF(i,j)

(10)

1.4 基于IPSS-ITEM的協同過濾推薦算法

基于IPSS-ITEM的協同過濾推薦算法步驟如下：

輸入 用戶-項目-評分數據集；

輸出 預測評分矩陣，推薦列表。

步驟1 將用戶-項目-評分數據集轉換為用戶-項目評分矩陣Rm×n，其中m為用戶數量，n為項目數量；

步驟2 在評分矩陣R上計算項目i和項目j的評分相似性PSS(i,j)(見式(4))，結構相似性IIF(i,j)(見式(9))，將PSS(i,j)和IIF(i,j)結合形成項目i和項目j的相似性(見式(10))，以此產生項目相似性矩陣Sim_Matrixn×n；

步驟3 對于目標項目，根據相似性大小選取相似性最高的前k個項目作為最近鄰集，用式(1)計算目標用戶對目標項目的預測評分，并得出推薦列表。

該算法計算項目間相似性時，以Sigmoid函數作為基礎進行項目間相似性的計算，能夠有效解決冷啟動情況下，傳統的相似性度量方法在計算項目間相似性時計算結果可能會擴大(即本來相似性較低的兩個項目的相似性度量結果較高)或縮小(即本來相似性較高的兩個項目的相似性度量結果較低)項目間相似性的問題。該算法需要計算所有n個項目間的相似度，每對項目相似度的計算又需要在維度為用戶數m的向量之間計算，所以時間復雜度為O(m×n)，而m和n的數量級相同，所以時間復雜度為O(n2)。

2 實驗結果與分析

為了評估IPSS相似性度量方法對協同過濾推薦算法的影響，本文在Movie Lens和Jester數據集上比較基于IPSS-ITEM的協同過濾推薦算法(ICF_IPSS)和基于其他相似性度量函數的協同過濾推薦算法(如基于余弦相關性的項目協同過濾算法(Cosine Correlation-based Item Collaborative Filtering, ICF_CC)[9]、基于皮爾遜相關性的項目協同過濾算法(Pearson Correlation Coefficient-based Item Collaborative Filtering, ICF_PCC)[10]、基于修正余弦相關性的項目協同過濾算法(Adjusted Cosine Correlation-based Item Collaborative Filtering, ICF_ACC)[3]、基于約束皮爾遜相關性的項目協同過濾算法(Constrained Pearson Correlation-based Item Collaborative Filtering, ICF_CPCC)[4]、基于加權皮爾遜相關性的項目協同過濾算法(Weighted Pearson Correlation-based Item Collaborative Filtering, ICF_WPCC)[5]、基于Sigmoid函數的相關性的項目協同過濾算法(Sigmoid-based Pearson Correlation-based Item Collaborative Filtering, ICF_SPCC)[6]、基于Jaccard系數的均方差異系數的項目協同過濾算法(Jaccard-based Mean Square Difference-based Item Collaborative Filtering, ICF_JMSD)[7])的預測準確率和分類準確率，以此驗證IPSS相似性度量方法的有效性。

2.1 實驗數據集和性能評價指標

本文比較ICF_IPSS與其他協同過濾推薦算法在Movie Lens(http://www.grouplens.org)和Jester(http://eigentaste.berkeley.edu/dataset/)兩個數據集進行測試，以此評估ICF_IPSS的性能。Movie Lens和Jester數據集的概述見表1。

表1 Movie Lens和Jester數據集概述Tab. 1 Movie Lens and Jester data sets overview

一般地，評估協同過濾推薦算法的性能，主要采用預測準確率和分類準確率兩個指標。預測準確率分為平均絕對偏差(Mean Absolute Error, MAE)和均方根誤差(Root Mean Square Error, RMSE)，MAE和RMSE的值越小，預測的準確率越高。通常情況下網站會為用戶返回一個推薦列表，叫作Top-N推薦[12]。Top-N推薦的分類準確率經常用兩個常用的指標衡量：準確率和召回率[13]，見表2。

表2 性能評估指標表Tab. 2 Performance evaluation indicators

2.2 實驗結果與討論

2.2.1 預測準確率

預測準確率反映算法對于未評分項目的預測結果的準確程度，最近鄰居數量的不同會導致預測準確率存在一定差異，將最近鄰數量K作為自變量，分析基于不同相似性度量方法的協同過濾算法的推薦效果。實驗結果顯示，與傳統的協同過濾推薦算法比較，ICF_IPSS可以顯著提高推薦的有效性。

圖1給出了在Movie Lens數據集下，不同鄰居數情況下，基于各種相似性度量方法(圖例中各算法名稱中的“ICF_”省略)的協同過濾的推薦準確度比較。

圖1 Movie Lens數據集下不同相似性度量方法對應的MAE和RMSEFig. 1 MAE and RMSE values of different similarity measures under Movie Lens data set

在圖1中， MAE和RMSE的值隨著K的增多而減少。可以看出，ICF_IPSS的MAE值比其他基于經典相似性度量方法的協同過濾推薦的MAE值低，在K=10時，ICF_IPSS的MAE值分別比ICF_CC，ICF_PCC，ICF_ACC， ICF_CPCC，ICF_WPCC， ICF_SPCC， ICF_JMSD低10.83%，14.24%，7.20%，1.39%，1.94%，15.52%，3.06%。ICF_IPSS的RMSE值比大多數基于經典相似性度量方法的協同過濾推薦的RMSE值低，只有當最近鄰個數大于等于10以后，ICF_IPSS的RMSE值略大于ICF_CPCC的RMSE值(K=10時，RMSEIPSS=1.098 5,RMSECPCC=1.096 5)。在K=10時，ICF_IPSS的RMSE值分別比 ICF_CC，ICF_PCC， ICF_ACC，ICF_CPCC，ICF_WPCC，ICF_SPCC，ICF_JMSD低7.37%，9.42%，4.90%，-0.18%，1.12%，10.51%，1.20%。

圖2給出了在Jester數據集下預測準確率的實驗效果。可以看出在鄰居數量從5到50的情況下，基于傳統相似性度量的推薦算法的MAE≥3.628 7，RMSE≥4.575 8，相比之下，ICF_IPSS的MAE和RMSE值(MAE≥3.483 9，RMSE≥4.497 4)明顯小于傳統方法。在K=10時，ICF_IPSS的MAE值分別比ICF_CC，ICF_PCC，ICF_ACC，ICF_CPCC， ICF_WPCC，ICF_SPCC，ICF_JMSD低11.01%，5.26%，6.97%，10.93%，5.26%，5.26%，17.07%。在K=10時，ICF_IPSS的RMSE值分別比ICF_CC，ICF_PCC，ICF_ACC， ICF_CPCC， ICF_WPCC， ICF_SPCC，ICF_JMSD低9.42%，3.76%，4.00%，9.33%，3.76%，3.76%，13.80%。

圖2 Jester數據集下不同相似性度量方法對應的MAE和RMSEFig. 2 MAE and RMSE values of different similarity measures under Jester data set

2.2.2 分類準確率

在Top-N推薦中，不同的推薦數量會有不同的推薦效果。將推薦項目數量N作為自變量，分析基于不同相似性度量方法的協同過濾算法的推薦效果。

圖3顯示了Movie Lens數據集下不同推薦項目數量對應的準確率和召回率。從圖3中可以看出，ICF_IPSS可以得到最好的推薦分類準確率，而且與其他方法相比效果非常明顯; 此外，可以看出，準確率將會隨著推薦數量的增加而下降。ICF_WPCC和ICF_JMSD是推薦效果最好的兩種傳統方法，然而，與ICF_JMSD相比，當N=10時，ICF_IPSS的準確率提升67.79%; 召回率會隨著推薦數量的增加而上升，與ICF_JMSD相比，當N=10時，ICF_IPSS的召回率提升67.86%。

圖4顯示了在Jester數據集下不同推薦項目數量對應的準確率和召回率，同樣地，基于ICF_IPSS能夠得到最好的推薦效果。從圖中可以看出，ICF_ACC是ICF_IPSS的有力競爭者，然而，與ICF_ACC相比，當N=10時，ICF_IPSS的準確率提升7.46%，召回率提升7.45%。可以看出，ICF_IPSS可以比其他經典方法得到更好的推薦效果。

圖3 Movie Lens數據集下不同推薦項目數量對應的準確率和召回率Fig. 3 Precision and recall values of different recommendation items under Movie Lens data set

圖4 Jester數據集下不同推薦項目數量對應的準確率和召回率Fig. 4 Precision and recall values of different recommendation items under Jester data set

3 結語

協同過濾推薦算法是個性化推薦系統中應用最廣泛、效果最好的算法之一，但傳統協同過濾推薦算法遇到冷啟動情況效果不佳。有效地改進與修正項目間相似性度量方法，能夠有效解決冷啟動情況下項目協同過濾算法的效果不佳問題。本文提出一種新的項目相似性度量方法。該項目相似性度量方法由評分相似性和結構相似性兩部分構成，其中，評分相似性部分充分考慮兩個項目評分之間的評分差、項目評分與評分中值之差，以及項目評分與其他評分平均值之差；結構相似性部分定義了評分項目占所有項目比重并懲罰活躍用戶的IIF系數，形成一種新的項目相似性度量方法——IPSS度量方法。將IPSS度量方融合在項目協同過濾推薦算法，提出基于IPSS的項目協同過濾算法(ICF_IPSS)，其在冷啟動情況下具有較好的表現。在Movie Lens和Jester數據集的測試實驗結果表明基于IPSS的項目協同過濾算法在預測準確率和分類準確率方面均優于基于其他相似性度量的項目協同過濾算法(如ICF_CC、ICF_PCC、ICF_ACC、ICF_CPCC、ICF_WPCC、ICF_SPCC、ICF_JMSD)。算法的時間復雜度為O(n2)。如何有效提高算法復雜度將是今后研究的重點。

References)

[1] RESNICK P, VARIAN H R. Recommender systems[J]. Communications of the ACM, 1997, 40(3): 56-58.

[2] BOBADILLA J, ORTEGA F, GUTIRREZ A. Recommender systems survey[J] .Knowledge-Based System, 2013,46(1): 109-132.

[3] AHN H J. A new similarity measure for collaborative filtering to alleviate the new user cold-starting problem[J]. Information Science, 2008, 178(1): 37-51.

[4] SHARDANAND U, MAES P. Social information filtering: algorithms for automating "word of mouth"[C]// Proceedings of the IEEE/WIC/ACM International Conference on Web Intelligence Agent Technology. New York: ACM, 2009:548-551.

[5] HERLOCKER J L, KONSTAN J A, BORCHERS A. An algorithmic framework for performing collaborative filtering[C]// Proceedings of the Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. New York: ACM, 1999: 230-237.

[6] JAMALI M, ESTER M. TrustWalker: a random walk model for combing trust-based and item-based recommendation[C]// Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2009:397-406.

[7] BOBADILLA J, HEMANDO A, ORTEQA F, et al. Collaborative filtering based on significances[J]. Information Sciences, 2012,185(1): 1-17.

[8] SARWAR B, KARPIS G, KONSTAN J, et al. Item-based collaborative filtering recommendation algorithms[C]// Proceedings of the 10th International Conference on World Wide Web. New York: ACM, 2001:285-295.

[9] SALTON G, MCGILL M J. Introduction to Modern Information Retrieval[M]. New York: McGraw-Hill, 1983: 305-306.

[10] SCHAFER J B, DAN F, HERLOCKER J, et al. Collaborative filtering recommender systems[J]. ACM Transactions on Information Systems, 2004, 22(1):5-53.

[11] BREESE J S, HECKERMAN D, KADIE C. Empirical analysis of predictive algorithms for collaborative filtering[C]// Proceedings of the 14th Conference on Uncertainty in Artificial Intelligence. San Francisco, CA: Morgan Kaufmann Publishers, 2013:43-52.

[12] DESHPANDE M, KARYPIS G. Item-based top-Nrecommendation algorithms[J]. ACM Transactions on Information System, 2014, 22(1):143-177.

[13] BOBADILLA J, HEMANDO A, ORTEQA F. A framework for collaborative filtering recommender systems[J]. Expert Systems with Applications, 2011,38(12): 14609-14623.

This work is partially supported by the Public Welfare Industry (Agriculture) Scientific Research Special Projects Level-2 (201503116-04-06), the Postdoctoral Foundation of Heilongjiang Province (LBH-Z15020), the National Science and Technology Support Plan Thematic Mandate (2014BAD12B01-1-3), the Key Laboratory Open Fund of Agricultural Water Resources Efficient Utilization in Ministry of Agriculture (2015004), the Philosophical and Social Science Research Plan Annual Project of Heilongjiang Province (16YB17).

YU Jinming, born in 1992, M. S. candidate. Her research interests include data mining, machine learning.

MENG Jun, born in 1965, Ph. D., professor. His research interests include data mining, machine learning.

WU Qiufeng, born in 1979, Ph. D., associate professor. His research interests include data mining, machine learning.

Item collaborative filtering recommendation algorithm based on improved similarity measure

YU Jinming1, MENG Jun2*, WU Qiufeng2

(1.CollegeofEngineering,NortheastAgriculturalUniversity,HarbinHeilongjiang150030,China;2.CollegeofScience,NortheastAgriculturalUniversity,HarbinHeilongjiang150030,China)

Traditional collaborative filtering algorithm can not perform well under the condition of cold start. To solve this problem, IPSS-based (Inverse Item Frequence-based Proximity-Significance-Singularity) Item Collaborative Filtering (ICF_IPSS) was proposed, whose core was a novel similarity measure. The measure was composed of the rating similarity and the structure similarity. The difference between the ratings of two items, the difference between the item rating and the median value, and the difference between the rating value and the average rating value of other items were taken into account in the rating similarity. The structure similarity defined the IIF (Inverse Item Frequence) coefficient which fully reflected common-rating ratio and punished active users. Experiments were executed on Movie Lens and Jester data sets to testify the accuracy of the ICF_IPSS. In Movie Lens data set, when the nearest neighbor number was 10, the Mean Absolute Error (MAE) and Root Mean Square Error (RMSE) was 3.06%, 1.20% lower than ICF_JMSD (Jaccard-based Mean Square Difference-based Item Collaborative Filtering) respectively. When the recommendation item number was 10, the precision and recall was 67.79%, 67.86% higher than ICF_JMSD respectively. The experimental results show that ICF_IPSS is superior to other traditional collaborative filtering algorithms, such as ICF_JMSD.

Collaborative Filtering (CF); recommendation algorithm; similarity measure; rating similarity; structure similarity; cold start

2016-10-08;

2016-11-28。 基金項目:公益性行業(農業)科研專項二級任務(201503116-04-06); 黑龍江省博士后基金資助項目(LBH-Z15020); 國家科技支撐計劃專題任務(2014BAD12B01-1-3); 農業部農業水資源高效利用重點實驗室開放基金資助項目(2015004); 黑龍江省哲學社會科學研究規劃年度項目(16YB17)。

于金明(1992—)，女，黑龍江牡丹江人，碩士研究生，主要研究方向：數據挖掘、機器學習； 孟軍(1965—)，男，黑龍江哈爾濱人，教授，博士，主要研究方向：數據挖掘、機器學習； 吳秋峰(1979—)，男，黑龍江雙鴨山人，副教授，博士，CCF會員，主要研究方向：數據挖掘、機器學習。

1001-9081(2017)05-1387-05

10.11772/j.issn.1001-9081.2017.05.1387

TP391

A