基于内容过滤的个性化搜索算法

Personalized Search Algorithm Using Content-Based Filtering

Journal of Software, 2003,14(5):0000~0000.

Abstract: Traditional information retrieval technologies satisfy users’ need to a great extent. However, for their all-purpose characteristics, they can’t satisfy any query from different background, with different intention and at different time. This paper presents a personalized search algorithm using content-based filtering. The user model is represented as the probability distribution over the domain classification model. A method of computing similarity and a method of revising user model are provided. Compared with the vector space model, the probability model is more effective on describing a user’s interests.

Key words: personalization; content-based filtering; search algorithm; user model; recommendation system

摘要: 传统信息检索技术满足了人们一定的需要,由于其通用的性质,仍不能满足不同背景、不同目的和不同时期的查询请求.提出了一种基于内容过滤的个性化搜索算法.利用领域分类模型上的概率分布表达了用户的兴趣模型,然后给出了相似性计算和用户兴趣模型更新的方法.对比实验表明,概率模型比矢量空间模型更好地表达了用户的兴趣和变化.

关键词: 个性化;基于内容过滤;搜索算法;用户模型;推荐系统

中图法分类号: TP393　　　文献标识码: A

Web已成为人们获取信息的一个重要途径,由于Web信息的日益增长,人们不得不花费大量的时间去搜索浏览自己需要的信息.搜索引擎是最普遍的辅助人们检索信息的工具,比如传统的搜索引擎AltaVista (www.altavista.com),Yahoo! (www.yahoo.com)和新一代的搜索引擎Google (www.google.com)等.信息检索技术满足了人们一定的需要,但由于其通用的性质,仍不能满足不同背景、不同目的和不同时期的查询请求.个性化服务技术就是针对这个问题而提出的,它为不同用户提供不同的服务, 以满足不同的需求.个性化服务通过收集和分析用户信息来学习用户的兴趣和行为,从而实现主动推荐的目的.个性化服务技术能充分提高站点的服务质量和访问效率,从而吸引更多的访问者.

目前存在着许多个性化服务系统^[1,2],它们提出了各种思路来实现个性化服务.个性化服务系统根据其所采用的推荐技术可以分为两种:基于规则的系统和信息过滤系统.信息过滤系统又可分为基于内容过滤的系统和协作过滤系统.

基于规则的系统利用预定义的规则来过滤信息,它的优点是简单直接,缺点是规则质量很难保证,而且不能动态更新,此外,随着规则的数量增多,系统将变得越来越难以管理.基于内容过滤的系统利用资源与用户兴趣的相似性来过滤信息,它的关键问题是相似性计算,它的优点是简单有效,缺点是难以区分资源内容的品质和风格,而且不能为用户发现新的感兴趣的资源,只能发现和用户已有兴趣相似的资源.协作过滤系统利用用户之间的相似性来推荐信息,它能够为用户发现新的感兴趣的内容,它的关键问题是用户聚类,其缺点是需要用户的参与.由于基于内容过滤和协作过滤各有其优缺点,所以有些系统同时采用了这两种技术.

本文提出了一种基于内容过滤的个性化搜索算法.基于内容过滤的基本问题包括用户兴趣的建模与更新,以及相似性计算方法.本文利用领域分类模型上的概率分布表达了用户的兴趣模型,然后给出了相似性计算和用户兴趣模型更新的方法.对比实验表明,概率模型比矢量空间模型更好地表达了用户的兴趣和变化.本文只关心文本资源,比如科技论文等,实际上,我们的方法还可以应用到其他领域.

本文第1节讨论文档和用户兴趣模型的表达.第2节讨论用户兴趣模型的更新.第3节描述相似性计算方法和基于该方法的个性化搜索算法.第4节描述实验系统和分析实验结果.第5节总结全文并进行展望.

1 文档和用户兴趣模型的表达

为了比较文档和用户兴趣,文档和用户兴趣模型的表达是一致的.文档的传统表达方式是矢量空间模型,其缺点是内容过滤时必须精确匹配文档,很难获得满意的结果.我们利用文档在不同领域中的概率分布来表达文档,其特点是避免文档间的精确匹配,从而极大地提高了搜索的精度.同样地,可以利用用户兴趣在不同领域中的概率分布来表达用户兴趣模型.

1.1 矢量空间模型

表达文档和用户兴趣比较直接的做法是利用文档特征来表达.用户兴趣是多方面的,可以根据其浏览过的文档选取合适的主题词来表达用户兴趣^[3].该方法需要一个训练的过程,首先从预定义好的主题词表中选取词来描述训练文档,为每个词都创建一个分类器,新文档将被每个分类器处理,对该文档有意义的词就赋给该文档.这样用户兴趣可以表示为一个主题词的矢量u=ákw₁,kw₂,…,kw_nñ,其中kw_i表示第i个主题词出现的次数或权重.矢量的维数n一般是固定的,这样保证了文档和用户兴趣之间相似性计算的精度.

不过,预先定义好主题词表需要大量的工作,而且其覆盖的范围也有限,更简单的做法就是直接利用从文档中抽取的词来表达用户兴趣^[4,5].该方法不局限于预定义好的主题词表,矢量的维数一般是不固定的,当然也可以指定一个固定的大小.这种方法不能保证两个矢量之间存在很多相交的词,这样就很难保证矢量相似性计算的精度.基于简单考虑,本文对比的就是这种方法.

1.2 概率模型

矢量空间模型只能表达用户感兴趣的主题词,不能很好地区别用户兴趣之间的差异.如果先建立一个领域分类模型,然后计算所有文档和用户兴趣在这个分类模型上的概率分布,用该概率分布来表达文档和用户兴趣就可以很好地体现用户兴趣的多样性,而且很容易实现.由于分类模型的类型个数远小于主题词的个数,这样一方面提高了算法的运算速度,另一方面也提高了算法的搜索精度,因为用户在领域分类上更容易产生相似性.因此,概率模型比矢量空间模型更好地表达了用户的兴趣和变化.

我们采用Naïve Bayes方法来进行分类模型的训练^[6],这里我们讨论文档分类模型,用户兴趣和文档的表达是一致的.假定领域类型的集合为C={c₁,c₂,…,c_n},其中n为模型的大小,c_j表示第j个领域,则文档d表示为一个条件概率的矢量:d=áp(c₁|d),p(c₂|d),…,p(c_n|d)ñ,其中文档d对类型c_j的后验概率为:

, (1)

这里p(d)表示为:

, (2)

p(c_j)用下式估计:

. (3)

假定文档的所有特征都独立出现,则p(d|c_j)可以表示为文档所有特征条件概率的乘积:

. (4)

假定n(c_j,t)表示特征t在类c_j中出现的次数,n(c_j)为c_j中全部特征出现的次数的和,|V|表示文档集中全部不同特征的数目,则根据Lidstone连续定律(它克服了Laplace连续定律对数目较大的分类产生较大偏差的问题),对一正数λ(λ一般取0.5,如果λ=1,则Lidstone定律与Laplace定律相同),p(t|c_j)的估计值可以表示为:

. (5)

2 用户兴趣模型的更新

用户兴趣模型建立以后,可以允许用户主动更新,也可以通过跟踪用户的行为进行动态更新.这里讨论的是后者,即根据用户当前的动作产生不同的更新.用户的动作可以是添加书签、下载文档、浏览摘要、忽略文档和删除书签等,这些动作体现用户不同的兴趣,所以具有不同的意义^[7],见表1.

Table 1 Meaning of user actions

表1 用户动作的意义

User Action	Meaning
Add a bookmark	Very high positive
Download a paper	High positive
View details of a paper	Moderate positive
Ignore a paper	Low negative or set to zero
Delete a bookmark	High negative