协同过滤
![本页使用了标题或全文手工转换](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
协同过滤(collaborative filtering)是一种在推荐系统中广泛使用的技术。该技术通过分析用户或者事物之间的相似性(“协同”),来预测用户可能感兴趣的内容并将此内容推荐给用户。这里的相似性可以是人口特征(性别、年龄、居住地等)的相似性,也可以是历史浏览内容的相似性(比如都关注过和中餐相关的内容),还可以是个人通过一定机制给予某个事物的回应(比如一些教学网站会让用户对授课人进行评分)。比如,用户A和B都是居住在北京的年龄在20-30岁的女性,并且都关注过化妆品和衣物相关的内容。这种情况下,协同过滤可能会认为,A和B相似程度很高。于是可能会把A关注B没有关注的内容推荐给B,反之亦然。
发展简史
以下就“协同过滤”发展历史上几个重要的里程碑做相关阐述:
Tapestry(1992)
这是最早应用协同过滤系统的设计,主要是解决Xerox公司帕罗奥多研究中心资讯重载的问题。这个研究中心的员工每天会收到非常多的电邮却无从筛选分类,于是研究中心便发展这项实验性的邮件系统来帮助员工解决这项问题。 其运作机制大致如下:
- 个人决定自己的感兴趣的邮件类型;
- 个人随机发出一项资讯需求,可预测的结果是会收到非常多相关的文件;
- 从这些文件中个人选出至少三笔资料是其认为有用、会想要看的;
- 系统便将之记录起来成为个人邮件系统内的过滤器,从此以后经过过滤的文件会最先送达信箱;
以上是协同过滤最早的应用,接下来的里程碑为GroupLens。
GroupLens(1994)
这个系统主要是应用在新闻的筛选上,帮助新闻的阅听者过滤其感兴趣的新闻内容,阅听者看过内容后给一个评比的分数,系统会将分数记录起来以备未来参考之用,假设前提是阅听者以前感兴趣的东西在未来也会有兴趣阅听,若阅听者不愿揭露自己的身份也可以匿名进行评分。 和Tapestry不同之处有两点,首先,Tapestry专指一个点(如一个网站内、一个系统内)的过滤机制;GroupLens则是跨点跨系统的新闻过滤机制。再来,Tapestry不会将同一笔资料的评比总和起来;GroupLens会将同一笔资料从不同用户得到的评比加总。 GroupLens具有以下特点:
- 开放性:所有的新闻阅听者皆可使用,虽然系统委托Better Bit Bureau设计给分的系统,但若有不同的评分机制也适用于GroupLens。
- 方便性:给分并不是一件困难的事情且沟通上非常方便,评分结果容易诠释。
- 规模性:有可能发展成大规模的系统,一旦发展成大规模,存储空间与计算成本问题显得相当棘手。
- 隐密性:如果用户不想让别人知道他是谁,别人就不会知道。
由此可以看出,现今网络各个推荐系统的雏形已然形成,在GroupLens之后还有性质相近的MovieLens,电影推荐系统;Ringo,音乐推荐系统;Video Recommender,影音推荐系统;以及Jster,笑话推荐系统等等。乃至于今日的YouTube、aNobii皆是相似性质的网络推荐平台,较不同的是经过时间推移,网络越来越发达,用户越来越多,系统也发展得越来越严密。
电子商务的推荐系统
最著名的电子商务推荐系统应属亚马逊网络书店,顾客选择一本自己感兴趣的书籍,马上会在底下看到一行“Customer Who Bought This Item Also Bought”,亚马逊是在“对同样一本书有兴趣的读者们兴趣在某种程度上相近”的假设前提下提供这样的推荐,此举也成为亚马逊网络书店为人所津津乐道的一项服务,各网络书店也跟进做这样的推荐服务如台湾的博客来网络书店。 另外一个例子是Facebook的广告,系统根据个人资料、周遭朋友感兴趣的广告等等对个人提供广告推销,也是一项协同过滤重要的里程碑,和前二者Tapestry、GroupLens不同的是在这里虽然商业气息浓厚同时还是带给用户很大的方便。 以上为三项协同过滤发展上重要的里程碑,从早期单一系统内的邮件、文件过滤,到跨系统的新闻、电影、音乐过滤,乃至于今日横行互联网的电子商务,虽然目的不太相同,但带给用户的方便是大家都不能否定的。
分类应用
基于存量(Memory - based)的协同过滤
基于用户(User-based)的协同过滤
用相似统计的方法得到具有相似爱好或者兴趣的相邻用户,所以称之为基于用户的协同过滤。方法步骤:
- 收集用户资讯:收集可以代表用户兴趣的资讯。一般的网站系统使用评分的方式或是给予评价,这种方式被称为“主动评分”。另外一种是“被动评分”,是根据用户的行为模式由系统代替用户完成评价,不需要用户直接打分或输入评价资料。电子商务网站在被动评分的资料获取上有其优势,用户购买的商品记录是相当有用的资料。
- 最近邻搜索(Nearest neighbor search, NNS):以用户为基础(User-based)的协同过滤的出发点是与用户兴趣爱好相同的另一组用户,就是计算两个用户的相似度。例如:查找n个和A有相似兴趣用户,把他们对M的评分作为A对M的评分预测。一般会根据资料的不同选择不同的算法,目前较多使用的相似度算法有Pearson Correlation Coefficient、Cosine-based Similarity、Adjusted Cosine Similarity。
- 产生推荐结果:有了最近邻集合,就可以对目标用户的兴趣进行预测,产生推荐结果。依据推荐目的的不同进行不同形式的推荐,较常见的推荐结果有Top-N 推荐和关系推荐。Top-N 推荐是针对个体用户产生,对每个人产生不一样的结果,例如:透过对A用户的最近邻用户进行统计,选择出现频率高且在A用户的评分项目中不存在的,作为推荐结果;关系推荐是对最近邻用户的记录进行关系规则(association rules)挖掘。
基于项目(Item-based)的协同过滤
基于用户的协同过滤在用户总数较多的情况下会导致漫长的计算时间。在2001年,Sarwar提出了基于项目的协同过滤。该技术所依据的基本假设是“能够引起用户兴趣的项目,必定与其之前评分高的项目相似”,即通过计算项目之间的相似性来代替计算用户之间的相似性。方法步骤:
- 收集用户资讯:同以用户为基础(User-based)的协同过滤。
- 针对项目的最近邻搜索:先计算已评价项目和待预测项目的相似度,并以相似度作为权重,加权各已评价项目的分数,得到待预测项目的预测值。例如:要对项目 A 和项目 B 进行相似性计算,要先找出同时对 A 和 B 打过分的组合,对这些组合进行相似度计算,常用的算法同以用户为基础(User-based)的协同过滤。
- 产生推荐结果:以项目为基础的协同过滤不用考虑用户间的差别,所以精度比较差。但是却不需要用户的历史资料,或是进行用户识别。对于项目来讲,它们之间的相似性要稳定很多,因此可以离线完成工作量最大的相似性计算步骤,从而降低了在线计算量,提高推荐效率,尤其是在用户多于项目的情形下尤为显著。
基于模型(Model- based)的协同过滤
以存量为基础(Memory based)的协同过滤的缺点是资料稀疏,难以处理大资料量,这会影响即时结果。另一大类的协同过滤,即以模型为基础的协同过滤,可以在一定程度上缓解这个问题。 以模型为基础的协同过滤(Model-based Collaborative Filtering)是先用历史资料得到一个模型,再用此模型进行预测。以模型为基础的协同过滤广泛使用的技术包括隐语义模型、贝叶斯网络…等,根据对一个样本的分析得到模型。
优缺点
优点
以用户的角度来推荐的协同过滤系统有下列优点:
- 能够过滤机器难以自动内容分析的资讯,如艺术品,音乐等。
- 共享其他人的经验,避免了内容分析的不完全或不精确,并且能够基于一些复杂的,难以表述的概念(如资讯质量、个人品味)进行过滤。
- 有推荐新资讯的能力。可以发现内容上完全不相似的资讯,用户对推荐资讯的内容事先是预料不到的。可以发现用户潜在的但自己尚未发现的兴趣偏好。
- 推荐个性化、自动化程度高。能够有效的利用其他相似用户的反馈资讯。加快个性化学习的速度。
缺点
虽然协同过滤作为一推荐机制有其相当的应用,但协同过滤仍有许多的问题需要解决。整体而言,最典型的问题有
- 新用户问题(New User Problem) 系统开始时推荐质量较差
- 新项目问题(New Item Problem) 质量取决于历史资料集
- 稀疏性问题(Sparsity)
- 系统延伸性问题(Scalability)。
未来发展
Item-based的推荐算法能解决User-based协同过滤的一些问题,但其仍有许多问题需要解决,最典型的有稀疏问题(Sparsity)和冷启动问题(Cold-start),冷启动时效果较差。此外还有新用户问题和算法健壮性等问题。协同过滤作为一种典型的推荐技术有相当的应用,目前很多技术都是围绕协同过滤而展开研究的。在资讯种类、表达方式越来越多的时代,旧式的资讯分类过滤系统无法满足的地方,期许未来能用协同过滤的方法来解决。
参考文献
- Paul Resnick, Neophytos Iacovou, Mitesh Suchak, Peter Bergstrom, John Riedl, GroupLens: an open architecture for collaborative filtering of netnews, Computer Supported Cooperative Work, pp175-186, Chapel Hill, North Carolina, 1994.
- Balabanovic & Shoham, 1997; Mobasher et al., 2000; Yang et al., 2004
- F. Heylighen, Collaborative Filtering, http:/pespmc1.vub.ac.be/COLLFILT.html
- Breese, J.S., Heckerman, D., Kadie, C.: Empirical analysis of predictive algorithms for collaborative filtering. In: Fourteenth Conference on Uncertainty in Artificial Intelligence,Madison, WI (1998)
- 郑秀华、廖婉菁、吴肇铭,在线商品推荐系统之研究 -协同过滤机制之应用A Study for On-line Commodity Recommendation System:A Case of Collaborative Filtering,中原资管所
- Jung, Seikyung, Designing and understanding information retrieval systems using collaborative filtering in an academic library environment, Oregon State University, 2007.
- David Goldberg, David Nichols, Brian M. Oki, and Douglas Terry, Using collaborative filtering to weave an information tapestry, Communications of the ACM, Volume 35, Issue 12, pp61-70, 1992.
- 韩双福,应用协同过滤机制于商机撮合电子报之研究 - 以食品业电子市集为例,中原大学资讯管理学系硕士论文,民国92年7月。
- 彭恺翔,以语音为基础之情境认知虚拟行动设群,天主教辅仁大学资讯管理学系硕士论文,民国91年6月。
- 冯文正,合作式网站推荐系统,国立交通大学资讯学研究所,民国89年。
- 蔡登、卢增祥、李衍达,资讯协同过滤,电脑科学,第29期,页1~页4,2002年。
|