摘 要:针对传统的协同过滤(Collaborative Filtering,CF)算法没有考虑用户兴趣变化、导致其推荐质量较差的问题,借鉴心理学遗忘规律,提出非线性逐步遗忘协同过滤算法. 该算法依据评价时间减小每项评分的重要性,并在此基础上确定用户间的相似度.最后基于MovieLens数据集对本算法进行测试,实验结果表明该算法在准确性方面优于传统的协同过滤算法.
关键词:协同过滤; 兴趣变化; 非线性逐步遗忘
中图分类号:O415.2;TP301.6 文献标志码:A
Non-lineal gradual forgetting collaborative filtering algorithm
capable of adapting to users’ drifting interest
ZHENG Xiaong1, TANG Zeying2, CAO Xianbin1
(1. Dept. of Computer Sci. & Tech., Univ. of Sci. & Tech. of China,Hefei 230027, China;
2. College of Sci., National Univ.of Defense Tech., Changsha 410073, China)
Abstract: Since the traditional Collaborative Filtering (CF) algorithm often leads to bad recommendation when users’ interests are changed, and inspired by the forgetting law of psychology,a non-lineal gradual forgetting collaborative filtering algorithm is developed which diminishes the importance of each rate with time and then determines similarities between different users. The experiment using MovieLens dataset shows that the algorithm is more accurate than the traditional collaborative filtering algorithms.
Key words: collaborative filtering; interest drift; non-lineal gradual forgetting
0 引 言
因特网的迅速发展和电子商务的出现导致推荐系统的产生.[1]推荐系统是一种个性化的信息过滤技术[2],它被用来预测某个特定用户是否会喜欢某个特定的商品(预测问题),或被用来确定N件用户感兴趣的商品(TOP-N推荐问题).
协同过滤(Collaborative Filtering,CF)是建立推荐系统最成功的技术,其优点是能够基于信息的质量和品位进行过滤并推荐用户意想不到的有用信息.[3]很多电子商务网站都使用该技术,如Amazon,CDNOW和eBay.
目前主要有两种方法建立协同过滤推荐系统[4,5]:(1) 基于用户的(User-based).先利用统计方法得到具有相似兴趣的邻居用户,然后综合邻居的评价为当前用户预测或推荐.(2) 基于项目的(Item-based).系统通过分析历史信息确定不同项目之间的关系,然后利用这些关系推荐项目.该方法基于这样的认识:如果用户曾对某些项目感兴趣,那么与之相类似的项目用户也会感兴趣.
实际上经常变化的用户兴趣导致传统协同过滤系统的推荐质量显著下降,因为它只适合用户兴趣稳定的情况.本文提出一种新的协同过滤算法,对用户评分的重要性使用非线性逐步遗忘策略.实验结果表明该策略可有效提高用户兴趣变化情况下的推荐质量.
1 相关工作
Tapestry[6]是第一个使用协同过滤思想的系统,用于过滤电子邮件,其作者GOLDBERG认为人们应该彼此合作完成信息过滤工作.GroupLens[7]是基于用户评分的自动推荐系统,用于推荐电影和新闻.为处理用户变化的兴趣,KOYCHEV等[8]引入逐步遗忘的思想并使用线性遗忘函数,即对学习算法而言,最近的观察应比过去的重要,观察的重要性应随时间减小.KUKAR[9]建议使用核函数学习用户的兴趣.
用户兴趣不但是多方面的,而且还是动态变化的,因此跟踪和学习用户兴趣是最基本且难以解决的问题.[10]通过组合基于用户的和基于项目的协同过滤方法,基于相似项目的邻居用户协同过滤算法[11]能够处理用户多兴趣下的个性化推荐问题.
协同过滤算法尽管获得很大成功,但尚有两大主要缺陷[2]:(1) 稀疏性问题.在很多推荐系统中关于每个用户和项目的历史信息往往相当有限,因此协同过滤系统不能准确地确定用户的邻居和推荐项目,进而导致推荐质量下降;(2) 扩展性问题.基于用户协同过滤算法的计算复杂性随着用户和项目数量的增加成线性增长,由于典型的推荐系统中本身就存在大量的用户和项目,因此现有的推荐系统面临严重的扩展性问题.上述缺陷已有一些解决办法,如基于项目评分预测的协同过滤方法[12]、降维方法[13]和聚类技术[14]等.
2 基于用户CF算法
2.1 基于用户CF的思想
基于用户的CF是目前建立推荐系统最成功的技术.其思想是每个人都属于某个特定的群体,该群体中的成员具有相似的兴趣,因此被该群体中不同成员喜欢的项目可以用来形成候选的推荐项目.算法主要包括3个部分.
2.2 基于用户CF的问题
传统CF算法利用兴趣相似的邻居用户对某项目兴趣的大小,预测当前用户对该项目的喜好程度.显然,这里的邻居用户选择方法非常关键,但是通常的邻居选择方法没有考虑用户兴趣变化问题,从而影响算法的准确性.例如,过去喜欢体育类电影的用户A现在喜欢军事类电影,用户B喜欢体育类电影,用户C喜欢军事类电影.由于A和B过去的兴趣相似并且他们对项目的评分也相近,所以A和B的相似度要比A和C的相似度高.在确定A的邻居用户时,传统的CF算法就会选择B而不是C,最终系统向A推荐的仍是体育类电影而不是军事类电影,尽管A和C的最近兴趣相似且A已显示出对军事类电影的兴趣.上面的情况可以通过表1来说明.
3 逐步遗忘CF算法
3.1 用户兴趣变化问题的解决思路
对于上面的例子,如果在确定用户间的相似度时,给与A最近兴趣相似的用户以较大的相似度,给与A仅过去兴趣相似的用户以较小的相似度,那么系统就会把C作为A的邻居用户,以C作为邻居用户预测A对M2的评分也将更准确.
综上所述,为了捕捉用户兴趣变化,推荐系统需要为当前用户选择与他最近兴趣相似的邻居用户,同时淘汰仅与他过去兴趣相似的邻居用户.因此本文对传统的协同过滤算法进行改进:首先赋予每项评分1个按时间衰减的权重,即最近的评分权重大,过去的评分权重小,然后按加权后的评分确定用户间的相似度.
确定用户间的相似度.遗忘函数h(t)的作用是增加最近评分重要性的同时降低过去评分的重要性.
遗忘函数h(t)的选择非常关键,因为其遗忘能力直接影响推荐系统的性能.一般而言,h(t)的遗忘速度快,系统学习用户兴趣的过程就快;反之系统学习用户兴趣的过程就慢.
推荐系统是1种Web智能系统,它利用机器学习和数据挖掘的方法从历史数据库中发现用户的兴趣,然后进行个性化信息推荐.为了提高其智能性,推荐系统需要从不同的学科汲取有价值的思想和方法,包括机器学习、数据挖掘、统计学和心理学等.
人的遗忘过程不是简单的逐步遗忘.德国心理学家艾宾浩斯(EBBINGHAUS)首先对遗忘现象作了系统的研究[16],得到的遗忘规律表明:在识记后的短时期内遗忘进行得较快,经过足够长的时间间隔后遗忘进行得比较缓慢,即遗忘过程是先快后慢,是非线性的.受遗忘规律的启发,本文设想:如果在推荐系统中使用非线性逐步遗忘策略,那么系统的准确性应该更好,即按时间t对评分的重要性进行不同速度的衰减,t越小衰减得越快,反之越慢.
3.3.3 算法说明
在传统的CF算法中,所有评分的重要性都相同.虽然在用户兴趣未变化时上述做法是合理的,但是当用户兴趣发生变化时情况就有所不同.由于受用户旧兴趣的影响,推荐系统中旧评分的积极作用不大,因此应降低旧评分的重要性.非线性逐步遗忘CF算法依据评价时间减小每项评分的重要性,然后在此基础上确定用户间的相似度,使得计算出的邻居用户比较准确,因此在准确性方面高于传统的CF算法.
实验结果表明,当用户兴趣变化时非线性逐步遗忘CF算法在准确性方面优于传统的CF算法.
4 实验结果及分析
4.1 数据集
MovieLens数据集(http://movielens.umn.edu)含有本文必需的时间属性.MovieLens是著名的基于CF的研究型推荐系统,目前提供的电影超过5 000部,用户已超过70 000人.本文从中提取4 666条记录,涉及51个用户和264部电影,其中每个用户至少评价50部电影,每部电影至少被50个用户评价过.实验中本文将其中90%的数据作为训练集,剩下的10%作为测试集.
4.2 评价标准
采用平均绝对误差(Mean Absolute Error,MAE)作为评价标准,MAE用项目预测评分和实际评分间的偏差度量算法的准确性.为了测试算法能否跟踪用户的最近兴趣,选择的预测项目都是用户最近评分过的
(1) 随机选择若干用户,比较不同用户下非线性逐步遗忘CF算法和传统CF算法的MAE值,其中邻居大小k=10,遗忘速度m=0.6.实验结果表明,非线性逐步遗忘CF算法在准确性方面优于传统的CF算法,见图1.
图 1 不同用户下的推荐算法精度比较
从图1可以看出:对于不同用户,总体上非线性逐步遗忘CF算法的MAE值小于传统CF算法,但是对于个别用户(如UserID=62),前者的MAE值却比后者大,原因可能是这些用户的兴趣变化较慢,不适合采用非线性逐步遗忘策略.
(2) 对于上面的用户(UserID=127),比较不同邻居数量下非线性逐步遗忘CF算法和传统的CF算法的MAE值,其中遗忘速度m=0.6.实验结果表明,非线性逐步遗忘CF算法在准确性方面优于传统CF算法,见图2.
从图2可以看出:对于不同的邻居大小k,非线性逐步遗忘CF算法的MAE值均小于传统的CF算法,但是对于不同的k,非逐步遗忘CF算法的优势不一样,有些情况下的优势明显(如k=15时,准确性提高35%),有些情况下的优势不明显(如k=5时,准确性提高2%),显然它受邻居用户大小k的图 2 不同邻居大小下的推荐算法精度比较影响.此外,两种算法的MAE值总体上随k的增大而逐步减小.
(3) 对于上面的用户(UserID=127),比较不同遗忘速度m下非线性和线性逐步遗忘CF算法的MAE值(见表2),其中邻居大小k=10,这里使用的线性逐步遗忘函数如下:
4.4 结 论
根据上面的实验结果可以得出如下结论:总体上非线性逐步遗忘CF算法在准确性方面优于传统CF算法和线性CF算法.
但是,并非在所有情况下都适合使用非线性逐步遗忘算法.多数情况下的用户兴趣是逐渐改变的,适合使用线性逐步遗忘策略,而不适合使用非线性逐步遗忘策略,因为后者通常用于用户兴趣变化较快的场合.以后将继续研究不同变化速度的用户兴趣对两种算法的影响.
5 结束语
研究协同过滤中的用户兴趣变化问题,提出非线性逐步遗忘CF算法,该算法依据评价时间减小每项评分的重要性,然后在此基础上确定用户间的相似度.实验结果表明,非线性逐步遗忘CF算法在准确性方面总体上优于传统CF算法和线性逐步遗忘CF算法.
参考文献:
[1] RESNICK P, VARIAN H R. Recommender systems [J]. Communications of ACM, 1997, 40(3):56-8.
[2] KARYPIS G. Evaluation of item-based top-Nrecommendation algorithms:[Technical Report #00-046] [R]. Dept of Computer Sci, Univ of Minnesota, Minneapolis, 2000.
[3] 蔡登, 卢增祥, 李衍达. 信息协同过滤[J]. 计算机科学, 2002, 29(6):1-4.
[4] SARWAR B, KARYPIS G, KONSTAN J, et al. Item-based collaborative filtering recommendation algorithms [C]//Proc Tenth International World Wide Web Conference, 2001: 285-295.
[5] DESHPANDE M, KARYPIS G. Item-based top-Nrecommendation algorithms [J]. ACM Trans on Info Systems, 2004, 22(1): 143-177.
[6] GOLDBERG D, NICHOLS D, OKI B M, et al. Using collaborative filtering to weave an information tapestry [J]. Communications of ACM, 1992, 35(12):61-70.
[7] RESNICK P, IACOVOU N, SUCHAK M, et al. Grouplens: an open architecture for collaborative filtering of netnews [C]//Proc ACM CSCW 94. Chapel Hill, NC, 1994.
[8] KOYCHEV I, SCHWAB I. Adaptation to drifting user’s interests [C]//Proc ECML’ 2000. Barcelona, Spain, 2000.
[9] KUKAR M. Drifting concepts as hidden factors in clinical studies [C]// Proc 9th Conf on Artificial Intelligence in Medicine. Europe, Protaras, Cyprus, 2003.
[10] 曾春, 邢春晓, 周立柱. 个性化服务技术综述[J]. 软件学报, 2002, 13(10): 1 952-1 961.
[11] 余力, 刘鲁, 李雪峰. 用户多兴趣下的个性化推荐算法研究[J]. 计算机集成制造系统, 2004, 10(12): 1 610-1 615.
[12] 邓爱林, 朱扬勇, 施伯乐. 基于项目评分预测的协同过滤推荐算法[J]. 软件学报, 2003,14(9):1 621-1 628.
[13] SARWAR B, KARYPIS G, KONSTAN J, et al. Application of dimensionality reduction in recommender system - a case study [C]//ACM WebKDD Workshop, 2000.
[14] UNGAR L, FOSTER D. Clustering methods for collaborative filtering [C]//Proc Workshop on Recommender Systems. Menlo Park, Calif: AAAI Press, 1998.
[15] 郑先荣,曹先彬. 线性逐步遗忘协同过滤算法的研究[J].计算机工程,2007(1):72-73.
[16] 袁耿清. 医用心理学[M]. 南京: 东南大学出版社, 1995.
(编辑 廖粤新)
“本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文”。