基于改进相似性度量的项目协同过滤推荐算法

于金明，孟 军，吴秋峰

(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