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

基于内容过滤的个性化搜索算法PersonalizedSearchAlgorithmUsingContent-BasedFilteringJournalofSoftware,2003,14(5):0000~0000.Abstract:Traditionalinformationretrievaltechnologiessatisfyusers’needtoagreatextent.However,fortheirall-purposecharacteristics,theycan’tsatisfyanyqueryfromdifferentbackground,withdifferentintentionandatdifferenttime.Thispaperpresentsapersonalizedsearchalgorithmusingcontent-basedfiltering.Theusermodelisrepresentedastheprobabilitydistributionoverthedomainclassificationmodel.Amethodofcomputingsimilarityandamethodofrevisingusermodelareprovided.Comparedwiththevectorspacemodel,theprobabilitymodelismoreeffectiveondescribingauser’sinterests.Keywords:personalization;content-basedfiltering;searchalgorithm;usermodel;recommendationsystem摘要:传统信息检索技术满足了人们一定的需要,由于其通用的性质,仍不能满足不同背景、不同目的和不同时期的查询请求.提出了一种基于内容过滤的个性化搜索算法.利用领域分类模型上的概率分布表达了用户的兴趣模型,然后给出了相似性计算和用户兴趣模型更新的方法.对比实验表明,概率模型比矢量空间模型更好地表达了用户的兴趣和变化.关键词:个性化;基于内容过滤;搜索算法;用户模型;推荐系统中图法分类号:TP393文献标识码:AWeb已成为人们获取信息的一个重要途径,由于Web信息的日益增长,人们不得不花费大量的时间去搜索浏览自己需要的信息.搜索引擎是最普遍的辅助人们检索信息的工具,比如传统的搜索引擎AltaVista(),Yahoo!()和新一代的搜索引擎Google()等.信息检索技术满足了人们一定的需要,但由于其通用的性质,仍不能满足不同背景、不同目的和不同时期的查询请求.个性化服务技术就是针对这个问题而提出的,它为不同用户提供不同的服务,以满足不同的需求.个性化服务通过收集和分析用户信息来学习用户的兴趣和行为,从而实现主动推荐的目的.个性化服务技术能充分提高站点的服务质量和访问效率,从而吸引更多的访问者.目前存在着许多个性化服务系统[1,2],它们提出了各种思路来实现个性化服务.个性化服务系统根据其所采用的推荐技术可以分为两种:基于规则的系统和信息过滤系统.信息过滤系统又可分为基于内容过滤的系统和协作过滤系统.基于规则的系统利用预定义的规则来过滤信息,它的优点是简单直接,缺点是规则质量很难保证,而且不能动态更新,此外,随着规则的数量增多,系统将变得越来越难以管理.基于内容过滤的系统利用资源与用户兴趣的相似性来过滤信息,它的关键问题是相似性计算,它的优点是简单有效,缺点是难以区分资源内容的品质和风格,而且不能为用户发现新的感兴趣的资源,只能发现和用户已有兴趣相似的资源.协作过滤系统利用用户之间的相似性来推荐信息,它能够为用户发现新的感兴趣的内容,它的关键问题是用户聚类,其缺点是需要用户的参与.由于基于内容过滤和协作过滤各有其优缺点,所以有些系统同时采用了这两种技术.本文提出了一种基于内容过滤的个性化搜索算法.基于内容过滤的基本问题包括用户兴趣的建模与更新,以及相似性计算方法.本文利用领域分类模型上的概率分布表达了用户的兴趣模型,然后给出了相似性计算和用户兴趣模型更新的方法.对比实验表明,概率模型比矢量空间模型更好地表达了用户的兴趣和变化.本文只关心文本资源,比如科技论文等,实际上,我们的方法还可以应用到其他领域.本文第1节讨论文档和用户兴趣模型的表达.第2节讨论用户兴趣模型的更新.第3节描述相似性计算方法和基于该方法的个性化搜索算法.第4节描述实验系统和分析实验结果.第5节总结全文并进行展望.1文档和用户兴趣模型的表达为了比较文档和用户兴趣,文档和用户兴趣模型的表达是一致的.文档的传统表达方式是矢量空间模型,其缺点是内容过滤时必须精确匹配文档,很难获得满意的结果.我们利用文档在不同领域中的概率分布来表达文档,其特点是避免文档间的精确匹配,从而极大地提高了搜索的精度.同样地,可以利用用户兴趣在不同领域中的概率分布来表达用户兴趣模型.1.1矢量空间模型表达文档和用户兴趣比较直接的做法是利用文档特征来表达.用户兴趣是多方面的,可以根据其浏览过的文档选取合适的主题词来表达用户兴趣[3].该方法需要一个训练的过程,首先从预定义好的主题词表中选取词来描述训练文档,为每个词都创建一个分类器,新文档将被每个分类器处理,对该文档有意义的词就赋给该文档.这样用户兴趣可以表示为一个主题词的矢量u=kw1,kw2,…,kwn,其中kwi表示第i个主题词出现的次数或权重.矢量的维数n一般是固定的,这样保证了文档和用户兴趣之间相似性计算的精度.不过,预先定义好主题词表需要大量的工作,而且其覆盖的范围也有限,更简单的做法就是直接利用从文档中抽取的词来表达用户兴趣[4,5].该方法不局限于预定义好的主题词表,矢量的维数一般是不固定的,当然也可以指定一个固定的大小.这种方法不能保证两个矢量之间存在很多相交的词,这样就很难保证矢量相似性计算的精度.基于简单考虑,本文对比的就是这种方法.1.2概率模型矢量空间模型只能表达用户感兴趣的主题词,不能很好地区别用户兴趣之间的差异.如果先建立一个领域分类模型,然后计算所有文档和用户兴趣在这个分类模型上的概率分布,用该概率分布来表达文档和用户兴趣就可以很好地体现用户兴趣的多样性,而且很容易实现.由于分类模型的类型个数远小于主题词的个数,这样一方面提高了算法的运算速度,另一方面也提高了算法的搜索精度,因为用户在领域分类上更容易产生相似性.因此,概率模型比矢量空间模型更好地表达了用户的兴趣和变化.我们采用NaïveBayes方法来进行分类模型的训练[6],这里我们讨论文档分类模型,用户兴趣和文档的表达是一致的.假定领域类型的集合为C={c1,c2,…,cn},其中n为模型的大小,cj表示第j个领域,则文档d表示为一个条件概率的矢量:d=p(c1|d),p(c2|d),…,p(cn|d),其中文档d对类型cj的后验概率为:)()()|()|(dpcpcdpdcpjjj,(1)这里p(d)表示为:njjjcpcdpdp1)()|()(,(2)p(cj)用下式估计:文档集中全部文档数中的文档数jjccp)(.(3)假定文档的所有特征都独立出现,则p(d|cj)可以表示为文档所有特征条件概率的乘积:dtjjctpcdp)|()|(.(4)假定n(cj,t)表示特征t在类cj中出现的次数,n(cj)为cj中全部特征出现的次数的和,|V|表示文档集中全部不同特征的数目,则根据Lidstone连续定律(它克服了Laplace连续定律对数目较大的分类产生较大偏差的问题),对一正数λ(λ一般取0.5,如果λ=1,则Lidstone定律与Laplace定律相同),p(t|cj)的估计值可以表示为:||)(),()|(Vcntcnctpjjj.(5)2用户兴趣模型的更新用户兴趣模型建立以后,可以允许用户主动更新,也可以通过跟踪用户的行为进行动态更新.这里讨论的是后者,即根据用户当前的动作产生不同的更新.用户的动作可以是添加书签、下载文档、浏览摘要、忽略文档和删除书签等,这些动作体现用户不同的兴趣,所以具有不同的意义[7],见表1.Table1Meaningofuseractions表1用户动作的意义UserActionMeaningAddabookmarkVeryhighpositiveDownloadapaperHighpositiveViewdetailsofapaperModeratepositiveIgnoreapaperLownegativeorsettozeroDeleteabookmarkHighnegative2.1矢量空间模型由于用户兴趣是用文档特征来表示的,所以当文档推荐给用户的时候,可以根据用户动作对应的文档来选取用户感兴趣的特征,并调整用户兴趣矢量中特征出现的次数或权重.假定用户u当前的动作为a,其对应的意义为wa,用户动作对应的文档为d,是学习率,是一个小的常量,则利用下式来调整特征出现的次数或权重:)()()(dkwwukwukwiaii.(6)2.2概率模型用户兴趣表示为领域分类模型上的概率分布,也就是一个条件概率的矢量,当文档推荐给用户的时候,可以根据用户动作对应的文档来修改矢量中对应每个分类的条件概率.首先计算文档d在分类模型上的概率分布,然后利用下式来修改用户兴趣矢量中对应每个分类的条件概率:ajajjwdcpwucpucp1)|()|()|(.(7)3基于内容的过滤在表示好文档和用户兴趣后,可以利用文档和用户兴趣的相似性来过滤文档,本节介绍矢量空间模型和概率模型的相似性计算方法,以及基于内容过滤的个性化搜索算法.3.1相似性计算方法对矢量空间模型来说,相似性计算的传统做法是计算矢量间的余弦相似度(cosinesimilarity),用户u和文档d的相似性可以定义如下:||||||||),(dududuSim.(8)而对概率模型来说,直接计算矢量间的余弦相似度是不合适的,为了体现用户兴趣的多样性,我们提出了下列命题[8].命题1.假定用户u在给定分类模型C={c1,c2,…,cn}时条件独立于文档d,则文档d推荐给用户u的概率可以表示为:njjjjcpdcpucpupdup1)()|()|()()|(.(9)证明:由全概率公式可知,njjjcpcdupdup1)()|,(),(.(10)根据假定,用户u在给定分类模型C时条件独立于文档d,所以有p(u|d,cj)=p(u|cj),进而得出p(u,d|cj)=p(u|cj)p(d|cj),因此,式(10)可以变换为:njjjjcpcdpcupdup1)()|()|(),(.(11)根据p(u|d)=p(u,d)/p(d),式(11)可以变换为:njjjjdpcpcdpcupdup1)()()|()|()|(.(12)由于p(u|cj)p(cj)=p(u)p(cj|u),且p(d|cj)/p(d)=p(cj|d)/p(cj),式(12)最后变换为式(9).□根据命题1的结论,我们可以计算一篇文档推荐给用户的概率,它的意义在于将概率模型的相似性计算问题转化为求条件概率的问题,体现了用户兴趣的多样性.3.2个性化搜索算法根据命题1的结论,如果对一个搜索引擎产生的结果集按推荐概率进行重新排序,就能实现基于内容过滤的个性化搜索.值得注意的是,式(9)中的p(u)是不用计算的,因为p(u)不影响推荐概率之间的比较.下面是基于该方法的个性化搜索算法的详细描述:算法1.基于内容过滤的个性化搜索算法输入:领域分类模型,用户兴趣模型,查询关键词,一个搜索引擎输出:个性化搜索的结果(1)根据查询关键词,利用搜索引擎产生初步的搜索结果集X.(2)置迭代次数i=0.(3)对集合X中的第i篇文档,利用式(1)计算其在领域分类模型上的概率分布.(4)利用式(9)计算文档i推荐