大部分的机器学习算法认为所有训练样本的重要程度是等同的,但是在用户兴趣建模任务中却并不是这样,因为用户的兴趣随时可能发生变化,过时的训练样本的重要程度会显著降低,这就是用户兴趣建模中不可避免的兴趣偏移问题。主要有两大类方法来缓和或避免兴趣偏移问题:第一种方法利用兴趣模型的自我更新来不断缓和兴趣偏移给系统带来的负面影响。第二种方法则是明确地检测出用户兴趣偏移发生的位置,然后根据检测结果再对用户兴趣进行建模。相对而言,前者不需要实际检测偏移,在计算量上有所节省,且由于兴趣偏移检测存在一定难度,因此大多用户兴趣模型在处理偏移问题时采用第一种方法。
这一类采用自我调整的方法大致可以分为以下四种:时间窗口法、遗忘算法、长期和短期兴趣法,还有一些其它的自适应方法。下面将对它们进行逐一的介绍。
1.时间窗口法
在给出一系列项的情况下,用户的目的是选择感兴趣的项。因此,用户的选择可以被看成是独立的尝试去寻找其感兴趣的项。Widmer 和 Kubat 认为用户只对最近访问的概念感兴趣,对用户兴趣进行建模时只需要依靠最新的观察数据,即通过移动固定大小的时间窗把过时的兴趣滤除[1]。所以,对用户最后行为的观察能更准确地反映出用户当前的兴趣。处理该问题的最常用方法就是时间窗口法(Time Window)。如图1所示,该方法维持一个观察窗口,用户兴趣模型仅根据窗口内的样本构建,窗口随时间向前移动,落在窗口后面的样本则变成陈旧的用户描述文件。例如:Grabtree和 Soltysiak 设计的系统只对最近的n个数据进行学习建模[2]。该方法易于实现,但是需要预先设定窗口大小,如果不能预知漂移类型和速度,固定大小的时间窗会导致分类错误率升高。针对该方法的这一问题,可以采用启发式算法进行改进,以调整观察窗口的大小。Widmer和Kubat在时间窗口方法的基础上进行了改进,使窗口的大小能随着系统预测精度的变化而自动调整[1]。
图1 时间窗口法框架模型
上面的方法完全忽略了那些观察窗口之外的数据。而有些窗口之外的数据可能无法反映出用户当时的最大兴趣,但能反映出用户在生活中的一种习惯爱好或常规需求,属于长期的通用兴趣,因此窗口之外陈旧的观察数据对这些兴趣的建模依旧是非常重要的。 因此,以上方法可能忽略了在某些情况下非常有价值的数据。为了避免有用知识的丢失,且能从陈旧数据中进行学习,Mitchell等人设计的系统[3]会保留那些与新规则具有同等竞争力的旧规则。
2.遗忘模型
为了恰当地利用被忽略的陈旧观察数据,人们试图给陈旧数据赋以较低权重,给新的数据赋以较高权重,并统一利用所有数据进行建模,从而避免时间窗口法的缺点。Koychev 和 Schwab 认为用户的兴趣消减与自然遗忘的规律相似,他们设计了用户兴趣的遗忘模型(Forgetting Model)。如图2所示,遗忘模型常常在旧模型基础上引入新样本,给新样本赋较高权值,给旧模型或旧样本赋较低权值(权值低于一定阈值则该样本被遗忘),重新组合成新模型。这种方法基于如下假设:对于学习算法来说,用户行为的最新观察数据比那些旧的观察数据要重要的多,且观察数据的重要性随时间推移逐渐减小[4,5]。也就是说用户目前最感兴趣的内容与用户最近的行为之间的联系最紧密。文献[4]中,他们在特征选择时为计算特征的出现频率定义了一个线性遗忘函数w= f(t),它可以根据时间来生成观察数据的重要性,即权重,并且遗忘的速度可以通过遗忘函数中的参数进行调节。Maloof 和 Michalski的研究[ 6,7]采用遗忘窗口算法,利用遗忘函数衰减学习样本。同时,他们采用部分记忆学习来重新抓取有用的陈旧样本。该算法的缺点是可能丢失对于学习用户长期兴趣有用的样本。Cheng和Qiu等人指出心理学家对于人类兴趣的两个普遍观点:(1)同记忆一样,人对某一事物的兴趣也会随着时间逐渐遗忘。(2)遗忘的速度逐渐变慢,并且积累下的兴趣变得更稳定。在这两个观点的基础上,他们提出了一个指数形式的遗忘函数来衰减兴趣(而非样本),根据博客日志及发布时间构建用户兴趣模型[8]。
图2 遗忘模型框架
这类方法的优点是符合人类的心理学规律,很容易被人们所理解,并且遗忘模型不需要设定观察窗口大小,能够利用可能还有用的过时数据,从而弥补了时间窗口法的不足。缺点是它们主要侧重遗忘的方法,即如何去除过时的兴趣,没有考虑主动发现用户的新兴趣。用户的兴趣类是不断变化的, 因此对用户新兴趣的发现和对原有兴趣的遗忘具有同样重要的作用。另外,当用户的兴趣发生突然性的变化时,模型无法做出及时的调整,往往需要经过较长一段时间才能正确反映出新的兴趣。
3.长期和短期兴趣模型
遗忘模型可以很好地处理用户兴趣在很长一段时间内的变化过程,但是很难处理短期内的兴趣突然变化。为了解决这一问题,人们提出了为一个用户同时建立长期兴趣(Long-Term Interest)模型和短期兴趣(Short-Term Interest)模型的双层建模方法。如图3所示,这种双层模型的方法必须同时维护两类兴趣:长期兴趣和短期兴趣。它从长期以来的样本中学习用户普通的、变化缓慢的兴趣模型,并从短期内的样本中学习用户专有的、变化迅速的短期兴趣。在某些领域(例如:新闻故事[9]、博客日志[8])用户的长期兴趣比较广泛和稳定,而短期兴趣可能发生频繁的变化时,这种方法就非常有用。
图3 长期和短期兴趣模型框架
Billsus 和 Pazzani 在文献[9]中提出了一个混合式的用户模型来预测用户对新闻故事的喜好,它由用户兴趣的长期模型和短期模型组成。短期模型的构建仅仅基于最近的观察数据,而长期模型则是利用长期的观察数据进行建模。他们首先使用短期模型对新闻故事进行分类,如果一个故事不能被短期模型分类,则采用长期模型进行分类。Widyantoro 和 Ioerger 的研究[10]分别为学习短期兴趣的权值和长期兴趣的权值设计了不同的迭代函数,根据用户的正面和负面反馈来学习用户兴趣。在研究[11]中,他们维护了一个长期兴趣的描述器和一个短期兴趣的描述器,分别用来获取用户的通用兴趣和近期的快速变化的兴趣。他们的方法对于描述用户长期兴趣具有很高的准确度,同时能迅速适应用户兴趣发生突然显著变化的情况。Chen 和 Gao 等人根据用户浏览web页面时的点击导航,利用马尔科夫模型发现用户喜好的网页,抽取这些网页的特征词并聚类,从聚类结果中挖掘用户感兴趣的主题并建立动态多层次用户兴趣模型。该多层次兴趣模型能同时表示用户长期时间段的普通兴趣(高层兴趣)和短期时间内的专有兴趣(低层兴趣)[12]。Li 和 Yang 等人在文献[13]中通过维护用户的长期和短期描述文件(profile)来追踪用户长期和短期兴趣,从而为用户提供个性化搜索服务。他们的方法为用户的长期和短期兴趣采用不同模型来构建用户描述文件。为长期兴趣,该描述文件包含了一个层次分类模型;为短期模型,该描述文件包含了一个近期访问网页缓冲模型。动态调整策略被设计来捕获用户喜好的积累和退化,并根据它们及时调整用户描述文件的内容和结构。Kim 和 Chan 设计了一个用户普通(长期)兴趣和特殊(短期)兴趣联合的统一模型,他们的方法不再为长期和短期兴趣分别构建模型,而是统一进行处理,能同时获取两种兴趣。他们从用户访问过的网页集合里面学习出用户兴趣等级(User Interest Hierarchy),然后采用聚类算法把主题(关键词)分等级,越大的关键词集合表示越普通的兴趣,反之亦然[14]。
这一类方法能很好地把握用户的普通兴趣和特殊兴趣,当用户兴趣发生突然性的变化时也能根据短期兴趣抓住兴趣偏移。但是,该方法需要维护两个兴趣模型,必须额外消耗一定的系统资源。
4.其它自适应方法
还有一些方法也不采用显式检测偏移,而是采用一种自适应的方法。Cetintemel 和 Franklin 沿用之前常用的方法采用兴趣向量作为profile表示用户兴趣,不过向量的数目、大小、元素会随用户访问的网页自适应地调整,以更精确地表示用户的复杂兴趣[15]。Koychev 的研究[16]提出了一个学习算法用以处理用户兴趣的偏移和再生。该算法使用了一个优先学习层(Prior Learning Level)来寻找当前的上下文(Current Context)。然后,它从过去的观察数据中搜索那些与当前上下文相关的数据,记住它们并忘掉其余那些不相关的。最终,算法只从这些相关的数据中学习用户兴趣。
参考文献:
[1] G. Widmer, M. Kubat. Learning in the Presence of Concept Drift and Hidden Contexts. In: Machine Learning, Vol.23 No.1, pp.69-101, April 1996.
[2] Grabtree, S. Soltysiak. Identifying and Tracking Changing Interests. In: International Journal of Digital Libraries, l998.
[3] T. Mitchell, R. Caruana, D. Freitag, et.al. Experience with a Learning Personal Assistant. In: Communications of the ACM 37.7 pp. 81-91. 1994.
[4] Koychev, I. Schwab. Adaptation to Drifting User’s Interests. In Proceedings of ECML Workshop: Machine Learning in New Information Age. Barcelona, Spain. 2000.
[5] Koychev. Gradual Forgetting for Adaptation to Concept Drift. In: Proceedings of ECAI 2000 Workshop Current Issues in Spatio-Temporal Reasoning. 2000.
[6] M. A. Maloof, R. S. Michalski. Selecting Examples for Partial Memory Learning. Machine Learning, Vol41, pp.27-52. 2000.
[7] M. A. Maloof, R. S. Michalski. Learning Evolving Concepts Using a Partial Memory Approach. In: Working Notes of the AAAI Fall Symposium on Active Learning,Cambridge, MA, November 10-12, 1995.
[8] Y. Cheng, G. Qiu, J. Bu, et.al. Model Bloggers' Interests Based on Forgetting Mechanism. In: Proceeding of the 17th international conference on World Wide Web, WWW’08, Pages: 1129-1130. 2008.
[9] D. Billsus and M. J. Pazzani. A Hybrid User Model for News Classification. In Kay J. (ed.), Proceedings of the Seventh International Conference on User Modeling (UM '99), Springer-Verlag, pp. 99-108. 1999.
[10]D.H. Widyantoro, T.R. Ioerger, J. Yen. An Adaptive Algorithm for Learning Changes in User Interests. In: Proceedings of the 8th International Conference on Information and Knowledge Management. Pages: 405-412. Kansas City, Missouri, USA. 1999.
[11]D.H. Widyantoro, T.R. Ioerger, J Yen. Learning User Interest Dynamics with a Three Descriptor Representation. In: Journal of the American Society for Information Science and Technology. Vol.52, Pages: 212-225. Dec. 2000.
[12]J.J. Chen, J. Gao, B.S. Liao, et.al. Dynamic Semantic Clustering Approach for Web User Interest. In: Lecture Notes In Computer Science. 2004.
[13]L. Li, Z. Yang, B. Wang et.al. Dynamic Adaptation Strategies for Long-Term and Short-Term User Profile to Personalize Search. In: Lecture Notes Ii Computer Science, APWeb/WAIM’07, LNCS 4505, pp. 228-240. 2007.
[14]H.R. Kim, P.K. Chan. Learning Implicit User Interest Hierarchy for Context in Personalization. In: Applied Intelligence, pp. 153-166. 2008.
[15]U. Cetintemel, M.J. Franklin, C.L. Giles. Self-Adaptive User Profiles for Large-Scale Data Delivery. In: Proceedings of the 16th International Conference on Data Engineering. Pages: 622-633. 2000.
[16]Koychev. Tracking Changing User Interests through Prior-Learning of Context. In: Lecture Notes In Computer Science. Pages: 223-232. 2002.
本文作者:杨杰