基于用户情景的协同过滤推荐

摘 要:为提高基于项目的协同推荐算法的预测效果,引入用户情景因素。首先计算用户情景因素的相异度矩阵,然后按照用户间相异度大小,采用基于等价相异度矩阵聚类算法对用户进行聚类。在聚类后的用户簇中,选取与目标项目相异度小的项目作为近邻,为用户对目标项目进行评分预测。最后,在标准的MovieLens数据集上进行实验。通过对改进的推荐算法与经典的基于项目的协同推荐算法Slope One进行比较,实验数据表明改进后算法的推荐结果有较大提高。

关键词:用户情景;协同推荐;相异度矩阵;等价相异度矩阵;聚类

中图分类号: TP311

文献标志码:A

User context based collaborative filtering recommendation

ZHOU Tao, LI Hua

(

College of Computer Science, Chongqing University, Chongqing 400044, China

)

Abstract:

In order to improve the result of item-based collaborative filtering recommendation algorithm, an approach is proposed in the paper, which incorporates user context factors. Firstly the user context factors dissimilarity degree matrix is created. Then the Clustering Based on the Equivalent Dissimilarity Degree Matrix is adopted to cluster users by dissimilarity value between user and user. After Clustering, items that have small dissimilarity value are chosen as neighbors of target item in each user group. These neighbors are used to predict rating of target item for user. Finally, an experiment is given to evaluate our approach and to compare it with a typical item-based Slope One Algorithm using Movielens dataset. The experiment results suggest that our approach provides better quality than Slope One.

In order to improve the prediction effect of item-based collaborative filtering recommendation algorithm, user context factor was introduced. Firstly the dissimilarity degree matrix of the user context factor was calculated. Then the clustering based on the equivalent dissimilarity degree matrix was adopted to cluster users by dissimilarity value between user and user. After clustering, items that had small dissimilarity value were chosen as neighbors of target item in each user group. These neighbors were used to predict rating of target item for user. Finally, an experiment was given to evaluate the presented approach and to compare it with a typical item-based Slope One algorithm using Movielens dataset. The experimental results suggest that this approach has better performance than Slope One.

Key words:

user context;Collaborative Filtering (CF);dissimilarity degree matrix;equivalent dissimilarity degree matrix;clustering

0 引言

随着互联网技术的发展,网络资源总量也呈爆炸式增长。为了在海量数据中方便快捷地获取所需信息,推荐系统应运而生。它根据用户的兴趣爱好推荐符合用户兴趣的对象,也称个性化推荐系统。研究者提出多种推荐方法:基于内容的推荐、协同过滤推荐和混合推荐等,并结合先进的技术,如聚类、关联规则、贝叶斯网、神经网络和图模型等实现这些方法[1-2]。协同推荐(Collaborative Filtering,CF)是一种常用的减少信息过载的技术,己经成为了个性化推荐系统的一种主要工具[3]。传统的协同过滤被称为基于用户的协同推荐,其基本思想是:通过比较用户之间的相似性来推荐资源。这种推荐方法存在扩展性差的问题,推荐效率随用户数目、项目数目的增多而明显降低。为解决这一问题,有研究者使用聚类缩小相似用户的搜索范围[4],或通过奇异值分解减少项目空间的维数[5-6]。基于项目的协同过滤则解决了相似计算相似用户所引起的时间复杂度随用户增长而指数上升的问题[7-8]。因为项目之间的相似性相对稳定,可以离线计算并在较长时间间隔更新一次,明显改善了系统的扩展性问题。但基于项目的协同过滤的预测结果并没有得到明显的提高。

本文将静态用户情景因素与基于项目的协同过滤相结合,在传统协同推荐的基础上,提出了基于静态用户情景的协同推荐。其基本思想是:通过按用户静态情景因素聚类,缩小相似用户的范围,在同一范围内,用户对项目的评分可以通过项目之间的相似性以及用户已有的评分进行预测。实验结果表明新算法能有效提高推荐质量。

1 协同推荐

协同推荐技术是推荐系统中应用最早和最成功的技术之一。协同推荐技术的理论基础是人们的从众行为,其强调一种人与人之间的合作。它是基于这样的假设:为一用户找到他真正感兴趣的内容的好方法是首先找到与此用户有相似兴趣的其他用户,然后将他们感兴趣的内容推荐给此用户。

大多数协同过滤推荐算法都是基于用户―项目评分矩阵R进行的。R是一个m×n阶矩阵,其中m代表用户,n代表项目,矩阵中的值ru,i是用户u对项目i的评分。目前,协同过滤主要包括基于用户的协同推荐和基于项目的协同推荐。

1.1 基于用户的协同推荐

基于用户的协同推荐时通过测算用户间的相似性,选取相似性高的用户作为目标用户的近邻,通过近邻对目标项目的评分预测目标用户的评分。测算相似性的传统方法,目前主要有修正的余弦相似性和皮尔森相关系数法等[9],计算方法如式(1)、(2)所示。其中u和v表示用户,sim(u,v)表示u和v的相似性,I(u)表示u的已知评分项,I(u)∩I(v)表示u和v评分项的交集。目标用户u对项目i的评分预测方法式(3)所示。其中:ru是用户u所有评分的平均值,sim(u)表示u的相似用户集合,pu,i表示目标用户u对项目i的评分预测。

sim(u,v) = ∑i∈I(u)∩I(v)(ru,i *rv,i )∑i∈I(u)∩I(v)r2u,i ∑i∈I(u)∩I(v)r2v,i (1)

sim(u,v)=

∑i∈I(u)∩I(v)(ru,i-ru)(rv,i-rv)∑i∈I(u)∩I(v)(ru,i-ru)2∑i∈I(u)∩I(v)(rv,i-rv)2(2)

pu,i=ru+∑v∈sim(u)sim(u,v)(rv,i-rv)∑v∈sim(u)sim(u,v)(3)

1.2 基于项目的协同推荐

基于用户的协同推荐存在两个很难解决的问题:1)稀疏性,亦即在系统使用初期,由于系统资源还未获得足够多的评价,系统很难利用这些评价来发现相似的用户。2)可扩展性,亦即随着系统用户和资源的增多,系统的性能会越来越低,严重影响推荐的实时性。基于项目的协同过滤可以解决这些问题[8]。

在大多数个性化推荐系统中,项目信息的更新速度远比用户的更新慢,项目之间的关系也相对稳定。所以可以利用用户浏览过的资源内容来预期用户对其他资源的评价,这样可以增加资源评价的密度,并利用这些评价再进行协同推荐,从而提高协同推荐的性能。

┑4期 芴蔚:基于用户情景的协同过滤推荐

┆扑慊应用 ┑30卷

文献[8]中提出了基于项目的协同过滤推荐算法,介绍了基于项目之间相似性进行计算的思想,计算方法与基于用户的协同计算方法相似。目前经典的算法是Slope One算法[10]。该算法先用式(4)计算项目之间的相异性,然后按照式(5)进行评分预测。其中|U(i)∩U(j)|是同时对i和j进行评分的用户个数,Ru是用户u除对i之外的所有已知评分。由于Slope One算法简单实用、效率高,预测结果不比其他算法差,得到了研究者的广泛关注。

devi,j=∑u∈U(i)∩U(j)(ru,i-ru,j)|U(i)∩U(j)|(4)

pu,i=ru+∑j∈Rudevi,j|Ru| (5)

虽然基于项目的协同推荐有很多优点,但其预测准确率还有待于进一步提高。本文分析用户个性化情景,将静态用户情景因素与基于项目的协同过滤结合,有效地提高推荐质量。

2 基于用户情景的协同推荐

情景信息是指人的行为或事件发生影响的上下文信息或者场景信息[11]。在一个系统中会同时存在多个情景信息,用户情景是指对用户选择有较大影响的多个因素的集合。

2.1 情景信息的重要性

虽然协同推荐有相当的应用,但传统的推荐都很少考虑情景因素。目前协同推荐中寻找相似用户都是基于用户对资源项目的评分,但我们应该注意到个人的兴趣爱好与其职业、年龄、教育水平等一系列自身的因素有密不可分的联系。有相似属性的人群也容易产生相似的爱好。因此,从用户自身的因素出发来寻找相似用户将会更准确地为用户推荐处感兴趣的资源。

2.2 基于情景的用户间相异度矩阵的生成

假设用户的情景数据集包含p个不同类型的变量,用户i和用户j之间的相异度d(i,j)定义为:

d(i,j)=∑pf=1δ(f)ijd(f)ij∑pf=1δ(f)ij(6)

其中,如果xif或xjf缺失(即用户i或者用户j没有变量f的度量值),或者xif=xjf=0,且变量f是不对称的二元变量,则指示项δ(f)ij=0;否则,指示项δ(f)ij=1。变量f对i和j之间的相异度的计算方式与其具体的类型有关。

1)如果f是二元变量或者标称变量:如果xif=xjf,d(f)ij=0;否则d(f)ij=1。

2)如果f是区间标度变量:d(f)ij=|xif-xjf|┆maxhxhf-┆minhxhf ,这里的h遍取变量f的所有非空缺对象。

3)如果f是序数型变量:计算秩rif和zif=rif-1Mf-1,并将zif作为区间标度对象指待。

对于二元变量,当对象i和对象j取不同的二元变量的值时,得到的可能性表如表1所示。

表格(有表名)

表1 二元变量取值可能性表

对象i对象j

10求和

1qrq+r

0sts+t

求和q+sr+tp

在表1中,q是对象i和对象j的值都为1的变量的数目,r、s、t的含义与q相似。变量的总数是p,p=q+r+s+t。

对于对称的二元变量,它的两个状态是具有相同权重的,并且具有相同的价值,即当一些或者全部二元变量的编码改变时,计算结果不会发生改变。此种情况下,评价对象i和对象j的相异度可以使用简单匹配系数。其定义如下:

d(i,j)=r+sq+r+s+t(7)

标称变量可以看出是二元变量的推广,它的状态取值可以多于两个。它的相异度可以使用简单匹配方法来计算:

d(i,j)=p-mp(8)

其中m是匹配数目,即对象i和对象j取值相同的变量的个数,p是全部变量的数目。

对于区间标度变量,它的相异度是基于对象间的距离来计算的。最常见的距离度量方法是欧几里德距离,其定义如下:

d(i,j)=

|xi1-xj1|2+|xi2-xj2|2+…+|xip-xjp|2 (9)

一个离散的序数型变量类似与标称变量,但是它的M个状态是以有意义的序列排列的。各个状态的相对顺序是必要的,而各状态的实际取值大小却不重要。

假设f是描述n个对象的一组序数变量之一,它有Mf个状态,对应于序列1,2,…,M。由于一个序数型变量的值可以映射为秩,所以可以采用以下步骤计算f的相异度:

1)对象i的f值为xif,变量f有Mf个有序状态,对应于序列1,2,…,M。用对应的秩rif代替相应的xif,rif∈{1,2,…,Mf}。

2)由于每个序数变量的状态数目可以是不同的,所以需要先将每个变量的值域映射到[0.0,1.0]上,以确保每个变量都具有相同的权重。这个映射可以通过用zif代替rif来实现:

zif=rif-1Mf-1 (10)

3)相异度计算可以使用任意一种距离度量方法,采用zif作为对象i的f值。

2.3 基于相异度矩阵的用户聚类

根据文献[12]的结论可知,相异度矩阵具有如下两个性质。

性质1 相异度矩阵[d(i,j)]n×n是传递的当且仅当[d(i,j)]2n×n[d(i,j)]n×n。

性质2 设[d(i,j)]n×n是相异度矩阵,则[d(i,j)]n-1n×n是等价的。

由于相异度矩阵[d(i,j)]n×n和[d(i,j)]n-1n×n等价,所以可以采用相异度矩阵来表示用户之间自身因素的差异,运用基于等价相异度矩阵的聚类算法就可以对不同的用户进行聚类。同一类中的用户具有较高的相似度,因此也就有较近的兴趣爱好;不同类中的用户自身因素差异较大,因此兴趣爱好也就会有较大的不同。

基于相异度矩阵的用户聚类步骤[12]如下:

1)选定相异度度量方式,计算d(i,j)(i=1,2,…,n;j=1,2,…,n);

2)利用逐次平方法,计算:

[d(i,j)]n×n[d(i,j)]2n×n…[d(i,j)]2kn×n

直至首次出现2k≥n-1,此时[d(i,j)]n-1n×n=[d(i,j)]2kn×n;

3)给定相异度水平α,如果d(n-1)(i,j)≤α,则用户i和用户j归为一类。

2.4 基于用户情景的协同推荐算法

输入:用户u,待推荐项j, 用户表U,评分表D。

输出:目标用户对待推荐项目的评分pu,j。

1) 针对用户表U,按照式(6)计算用户之间的相异度矩阵[d(i,j)]n×n;

2) 按照2.3中的步骤对[d(i,j)]n×n进行聚类,获得同一类中用户的用户―资源项目评分矩阵Dk;

3) 在Dk中,按照式(4)计算项目间相异性devi,j;

4) 根据devi,j,按照式(5)计算目标用户对待推荐项目的评分pu,j。

3 实验结果及分析

3.1 实验数据集与评价标准

本文对所设计的算法在Matlab上进行了性能测试。实验数据采用MovieLens(movielens.umu.edu)提供的数据集,它包含943个独立用户对1B682部电影作的10B000次评分的数据,每个用户评分的电影不少于20部。数据集将这10B000次评分按照80%∶20%的比例随机抽取数据,分别形成训练集和测试集两个文件。而且在u.user文件中记录了用户的人口统计学信息。由于数据集中并不含有时间、地点等信息,只包含用户信息和项目信息,因此在算法中,采用用户类别信息作为项目的情境集合。

实验采用统计精度度量方法中广泛使用的平均绝对误差(Mean Absolute Error, MAE)作为评价标准。MAE是一种常用的推荐质量度量方法,通过计算预测用户评分与实际用户评分之间的偏差来度量预测的准确性,MAE越小,推荐的质量就越高。MAE定义为:

MAE=1n∑ni=1|fi-yi|

其中:n为测试集大小;fi为预测评分;yi为真实评分。

3.2 实验过程及结果分析

本文在u.user的用户集中计算用户间相异度矩阵,并对该矩阵聚类,获得同一类中用户的用户―资源项目评分矩阵。在同一类的评分矩阵中计算项目间相异性,最后得到目标用户对待推荐项目的评分。

3.2.1 基于情景的用户间相异度

如果不考虑情景,则无法度量用户间的相异度,计算的项目间相异度矩阵也是对整个用户集进行的。如果考虑情景,则可以按照用户的相异程度聚类,计算相异度较小的用户间项目相异度矩阵,从而提高预测精度。式(11)是考虑用户情景后得到的用户相异度矩阵。矩阵中的行和列是各个用户,例如0.146B5是用户1和用户2的相异度。

[d(i,j)]n×n=00.146B50.338B4…0.146B500.151B5…0.338B40.151B50…ぁ…… (11)

根据用户相异度矩阵,对用户进行聚类,获得各类的用户―资源项目评分矩阵Dk,计算Dk中项目的相异性并预测目标用户对目标项目的评分。

3.2.2 预测结果的分析

把本文基于用户情景和项目的协同推荐算法与经典的基于项目的协同推荐算法Slope One进行比较,结果见图1。图中横坐标是用户聚类时所取得的不同相异度。纵坐标是对应项目在测试集中预测评分与真实评分比较后的MAE值。图中每组柱状线,左侧是改进算法的MAE值,右侧是Slope One算法预测值的MAE值。MAE值越小,说明算法预测的准确率越高。可见,本文算法的MAE值比Slope One算法好。

图片

图1 推荐算法的平均绝对偏差比较

同时,图1给出了用户相异度与预测值之间的关系。

1)当取较小的用户相异度时,MAE值较大,预测质量不高。这是因为用户相异度小,导致同类中的用户数目少,获得的评分矩阵较稀疏。

2)随着用户相异度取值的增大,MAE值不断下降,预测质量较高。当相异度在0.020B2时,本文算法达到最优值,接近0.73。

3)当用户相异度在0.025B3以上时,MAE反弹。原因是

当用户相异度逐渐增大时,其聚类中的用户数目也会随之增多,当达到最优后,各类中用户数目的增多反而降低了项目相异度的真实性。

4 结语

本文提出了一种结合用户情境和基于项目的协同推荐方法。本方法从用户自身作为出发点,按照对用户的情境因素进行聚类后,在同类中的用户进行资源得分预测并推荐,取得了优于传统协作推荐算法的性能,为现有的推荐技术提供了一种新的思路。

同时,由于人的情景因素是在不断发生变化的,而本文研究的是相对静止的情景因素,所以在以后的研究中应该着重考虑构建一个用户情景因素的模型,可以随着各种外部条件的改变而动态的修改用户自身的情景因素值,以达到对用户正确分类的目的。

参考文献:

[1]李聪,梁昌勇,马丽.基于领域最近邻的协同过滤推荐算法[J].计算机研究与发展,2008,45(9):1532-1538.

[2]张光卫,康建初,李鹤松,等.面向场景的协同过滤推荐算法[J].系统仿真学报,2006,18(z2):595-601.

[3]王磊.协同推荐技术及其在科技文献个性化推荐系统中的应用研究[D].南京:南京理工大学,2007.

[4]邓爱林,左子叶,朱扬勇.基于项目聚类的协同过滤推荐算法[J].小型微型计算机系统,2004,25(9):1665-1670.

[5]赵亮,胡乃静.个性化推荐算法设计[J].计算机研究与发展,2002,39(8):986-991.

[6]SARWAR B, KARYPIS G, KONSTAN J, et al. Incremental singular value decomposition algorithms for highly scalable recommender systems [EB/OL].[2009-07-01]./papers/pdf/sarwar_SVD.pdf.

[7]邓爱林,朱扬勇,施伯乐.基于项目评分预测的协同过滤推荐算法[J].软件学报,2003,14(9):1621-1628.

[8]SARWAR B, KARYPIS 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]ADOMAVICIUS G, TUZHILIN A. Toward the next generation of recommender systems: A survey of the state-of-the-art and possible extensions [J]. IEEE Transactions on Knowledge and Data Engineering, 2005,17(6):734-749.

[10]LEMIRE D, MACLACHLAN A. Slope one predictors for online rating-based collaborative filtering [C]// Proceedings of the SIAM Data Mining Conference. Newport Beach: Society for Industrial Mathematics, 2005: 21-25.

[11]姚忠,吴跃,常娜.集成项目类别与语境信息的协同过滤推荐算法[J].计算机集成制造系统,2008,14(7):1449-1456.

[12]赵明清,蒋昌俊,陶树平.基于等价相异度矩阵的聚类[J].计算机科学,2004,31(7):183-184.