一种改进的基于用户项目喜好的相似度度量方法

雷建云， 何 顺， 王淑娟

(中南民族大学 计算机科学学院，武汉 430074)

一种改进的基于用户项目喜好的相似度度量方法

雷建云， 何 顺， 王淑娟

(中南民族大学 计算机科学学院，武汉 430074)

针对传统的基于用户共同评分的相似度度量方法不能很准确地衡量用户间的相似性问题，提出了一种基于用户项目喜好的相似度度量方法.实验结果分析表明：使用新度量方法的协同过滤算法较使用传统度量方法的协同过滤算法有更小的平均绝对误差，证明了新的度量方法可以提高推荐的质量.

协同过滤；相似度；用户项目喜好；平均绝对误差

伴随互联网的发展，每天产生的信息量巨大，人们进入一个信息过载的时代.无论是生产者还是消费者都面临着挑战，推荐系统的出现可以很好地解决这个问题.协同过滤是应用最为广泛的推荐技术手段[1]，也是迄今为止应用最为成功的个性化推荐技术[2].目前电子商务平台都具有推荐功能，为用户提供便捷访问的高质量推荐，正是推荐系统研究领域的主要目标[3].从用户的历史数据中挖掘信息，完成资源的推荐，亚马逊是最为成功的案例.其思想是首先为目标用户寻找兴趣相似的邻近用户，然后把邻居用户感兴趣的项目推荐给目标用户.用户间相似性计算是协同过滤算法的关键[4]，现有的用户相似性度量方法是基于用户共同评分相似性来计算的，但因为每个用户对于项目的评价标准不同，并不能准确挖掘用户之间的相似性，导致选择最近邻集合的误差，从而影响推荐系统的精度.

为了提高用户相似性度量的精确度，本文提出一种基于用户对项目喜好度量相似度的方法，从而提高推荐的质量.

1 协同过滤算法

1.1 最近邻推荐

最近邻推荐是协同过滤最常用的推荐模式.对于一个目标用户产生推进列表需要3个步骤[5]：数据表述，发现最近邻集合和产生推荐列表.

(1) 数据表述.根据用户评分记录，表示成一个m×n的矩阵R,其中m表示用户数量，n表示项目数，Rij表示第i个用户对第j个项目的评分值.

(2) 发现最近邻集合.根据评分项目矩阵计算并找到与目标用户最为相似的前K个用户.

(3) 产生推荐列表.根据最近邻用户的项目评分，预测目标用户未评分项目的评分值，选出预测评分值较高的前N个项目进行推荐.项目的预测评分的计算方法如下：

(1)

1.2 用户相似性度量

用户相似性计算作为协同过滤算法的关键[2]，传统的相似性度量方法有Pearson方法，余弦相似度和Jaccard相似度.

1)Pearson相似性[6].

(2)

2) 余弦相似度.

(3)

3)Jaccard相似度.

(4)

公式(4)中‖表示集合中元素的个数，N(u),N(v)分别表示用户u,v的评分项目集合.

选择上面三种度量方法的任意一种计算得到相似度，利用⑴式即可求得项目的预测评分值.

2 改进相似度计算方法

传统的Pearson方法和余弦相似度是基于用户的共同评分，仅仅是通过数值计算而没有考虑到数据背后所隐藏的信息，计算到的相似度并不能很好地衡量用户间的相似性.Jaccard相似度是计算的用户间的结构相似度，没用充分利用评分所包含的信息量，得到的相似度准确度有待于提高.由于每个用户可能有自己的评价标准，而用户的评价标准可以从用户的历史评分数据中得到，因而这里提出一种基于用户对于项目的喜好情况来求解相似度的方法.

用户对于项目的喜好情况借助历史评分数据挖掘，其定义为：以用户当前已评分项目的平均分作为用户的喜好标准，当评分值大于或等于平均分表示喜爱项目；否则为不喜爱项目.

改进后相似度计算需要以下两个步骤：用户项目喜好矩阵和度量用户相似性.

1) 用户项目喜好矩阵.

(5)

由用户项目评分矩阵得到用户项目喜好矩阵，如表1和表2所示.

由表1可知User1的平均评分为2.5，User2的平均评分为3.75，User3的平均评分为4，按照⑸式计算得到用户项目喜好如表2.

2) 度量用户相似性.

由用户项目喜好矩阵可获取用户基于共同评分项的喜好向量，根据用户喜好向量计算相似度，计算公式如下.

(6)

其中Lu,Lv分别表示用户u,v的项目喜好向量，N(Lu),N(Lv)分别表示用户u,v喜好的项目集，‖表示项目个数.

3) 基于改进相似度的协同过滤算法复杂度分析.

分析算法有时主要关心像内存、通信带宽或计算机硬件这类资源，但通常想度量的是计算时间.而且随着科技发展，存储空间对于算法的影响也逐渐弱化，这里只讨论算法时间复杂度.若用户的数量级为n，项目的数量级为m，算法时间主要开销是计算用户间相似度度量，传统协同过滤算法的时间复杂度为O(n2m)，改进的协同过滤算法的时间复杂度分析如下:

算法运行时间为T(n)=c0(n+1)+c1(m(n+1))+c2(n+1)+c3(n(n+1))+c4(mn(n+1))+c5(n+1)+c6N0=(c3+c4m)n2+(c0+c1m+c2+c3+c4+c5)n+(c0+c1+c2+c3+c5+c6N0)，其中c0,c1,c2,c3,c5,c6,N0均为常数，可得T(n)=O(n2m)，基于改进相似度的协同过滤算法的时间复杂度和传统的协同过滤在同一数量级，未增加过多的时间开销.

4) 适用范围.

基于用户项目喜好的相似度度量方法，由于要挖掘用户评分背后的喜好情况，若在一个推荐系统中用户数量远远大于项目数量，从海量的用户中发现两个用户间的共同评分项目会很少，不利于挖掘用户对于项目的喜好情况的，以至于影响到喜好相似度的准确性，最终导致在最近邻选择时存在误差，影响推荐系统的精度.所以改进的度量方法更适用于用户数量不远大于项目数的数据集.

3 实验及分析

3.1 实验数据集及评价标准

实验数据集使用美国Minnesota大学GroupLens项目组提供的MovieLens数据集，该数据集有多种版本，在推荐系统的评测中得到广泛使用.实验中使用的数据集包含有943个用户对1682个电影超过100000条评分记录.每个用户至少对20部电影存在评分记录，评分分为5个等级，对应评分为1～5分，分数越高表示用户越喜爱电影.实验中选取80%数据作为训练集，其余20%作为测试集.

平均绝对误差(MAE)是常用的评价协同过滤算法的指标[7].本文将使用MAE作为评价标准，通过计算预测评分和实际评分值之间的偏差来度量预测的准确度.MAE越小说明推荐系统的推荐质量越高[8，9].若预测评分集合为{p1,p2,p3,…,pn}，实际评分集合为{r1,r2,r3,…,rn}，MAE定义如下[10]：

(7)

式中N表示预测评分的项目总数.

3.2 实验结果及分析

实验分别使用Pearson方法，余弦相似度，Jaccard相似度和新的方法度量用户间的相似度，对应的协同过滤算法分别记为PCF,CCF,JCF和NCF,选择的最近邻数目从5开始，每次递增5个，增至70，实验结果如表3和图1所示.

如表3和图1所示使用改进相似度度量方法的协同过滤算法NCF有着较低的MAE，MAE的值越小说明推荐系统的推荐精度高，则算法NCF较其他三种基于传统相似度度量方法的协同过滤算法效果更优；从实验结果数据中可以得知，最近邻的数量影响着推荐的效果，可以看出最近邻数量较少时，推荐质量往往很差，而基于评分相似性的两种算法PCF和CCF，由于相似度计算的误差较大，随着最近邻的数量增加，最近邻选取存在较大误差，导致推荐的精度依旧很差.基于结构相似度的协同过滤算法JCF，推荐效果虽然一定程度上优于上面两种算法，但次于改进算法的推荐效果.

4 结束语

本文主要介绍协同过滤算法的相似度计算方法，针对三种传统相似度度量方法的不足，提出一种改进的相似度计算方法，即结合用户项目喜好的度量方法，深入分析了基于改进方法的协同过滤算法的复杂度及其适用范围，并通过实验验证改进的方法明显优于传统的三种度量方法.改进的度量方法利用评分数据的潜在信息，获得用户项目的喜好情况，结合用户项目喜好矩阵应用新的计算方法衡量用户之间的相似性，使选择的最近邻误差减小，从而获得更好的推荐效果.

[1] Adomavicius G, Alexander Tuzhi lin. Toward the next generation of recommender systems: A survey of the state-of-the-art and possible extensions[C]// IEEE .Transactions on Knowledge and Data Engineering. New Jersey: IEEE,2005:734-749.

[2] 邢春晓, 高凤荣, 战思南,等. 适应用户兴趣变化的协同过滤推荐算法[J]. 计算机研究与发展, 2007, 44(2):296-301.

[3] 朱扬勇，孙 婧.推荐系统研究进展[J].计算机科学与探索，2015，9(5)：513-525.

[4] 嵇晓声, 刘宴兵, 罗来明. 协同过滤中基于用户兴趣度的相似性度量方法[J].计算机应用, 2010, 30(10):2618-2620.

[5] 刘芳先, 宋顺林. 改进的协同过滤推荐算法[J]. 计算机工程与应用, 2011, 47(8):72-75.

[6] 王 茜, 王均波. 一种改进的协同过滤推荐算法[J]. 计算机科学, 2010, 37(6):226-228.

[7] LU L,MEDO M,YEUNG H C, et al. Recommender systems[J]. Physics Reports，2012,519( 1) : 1-49．

[8] 马宏伟, 张光卫, 李 鹏. 协同过滤推荐算法综述[J]. 小型微型计算机系统,2009, 30(7):1282-1288.

[9] Sarwar B, Karypis G, Konstan J, et al. Item-based collaborative filtering recommendation algorithms[C]// ACM. Proceedings of the 10th international conference on World Wide Web. Texas: ACM, 2001:285-295.

[10] Herlocker J L, Konstan J A, Terveen L G, et al. Evaluating collaborative filtering recommender systems[J]. ACM Transactions on Information Systems, 2004, 22(1):5-53.

[11] 黄创光,印 鉴,汪 静,等. 不确定近邻的协同过滤推荐算法[J].计算机学报，2010,08:1369-1377.

An Improved Similarity Measurement Method
Based on Users′ Item Preference

Lei Jianyun, He Shun, Wang Shujuan

(College of Computer Science, South-Central University for Nationalities, Wuhan 430074,China)

In view of the fact that the traditional similarity measurement method based on users′ common score can′t measure the similarity between users accurately, a similarity measurement method based on users′ item preference is proposed. Through the experimental analysis, the collaborative filtering algorithm based on new measurement method has a smaller MAE than collaborative filtering algorithm based on traditional measurement method, and it is proved that the new method can improve the quality of recommendation.

collaborative filtering; similarity; user item preference; MAE

2015-09-10

雷建云(1972-)，男，教授，研究方向：信息安全，Email：leijianyun@mail.scuec.edu.cn

湖北省自然科学基金资助项目(2013CFB445)

TP393

A

1672-4321(2015)04-0094-04