基于词汇相关度的个性化搜索算法

1、 基于词汇相关度的个性化搜索算法1谭振华1,2,程维1,2,常桂然,1,高晓兴1,21东北大学信息科学与工程学院,沈阳(1100042东北大学软件学院,沈阳(110004摘要:本文提出了一种基于词汇相关度的个性化搜索算法。提出使用词汇之间的“相关度”来存储单个用户的个性化信息,并提出了能够在用户进行检索的过程中利用用户偏好自动建立针对该用户的“词汇相关度网”的方法,以及三种不同的利用词汇相关度对底层搜索引擎所返回的结果进行重新评估并进行个性化排序的策略。关键词:信息检索,个性化,词汇相关度1.引言普通的Web搜索引擎,由于其使用的页面评估技术并不考虑各个不同用户的使用习惯和偏好,导致搜索结果中

2、的绝大多数文档内容不是用户所需要的,查准率和查全率都无法达到用户的要求。对这个问题的一种解决办法就是建立个性化的Web搜索引擎。所谓的“个性化”,也就是搜索引擎会根据单个用户的习惯自动调整自己的设置,以使检索结果尽量满足该用户的需求。从某种意义上说,个性化搜索引擎就好像为每一个用户单独量身定做了一个搜索引擎。本文中提出使用词汇之间的“相关度”来存储特定用户的个性化信息。并提出了能够在用户进行检索的过程中自动建立针对该用户的“词汇相关度网”的方法,以及3种不同的利用词汇相关度对底层搜索引擎所返回的结果进行重新评估并进行个性化排序的策略。最后我们设计了基于词汇相关度的个性化元搜索引擎的原型系统。2

3、.相关工作目前对个性化信息检索技术的研究比较很广泛,已经出现了很多关于个性化搜索的服务系统3,4 ,提出了很多思路以及实现。如:在文献1中,提出了一种基于智能代理(Intelligent Agent技术的智能化信息检索体系结构;文献2中所提到的Autonomy智能代理系统使用神经元网络来识别信息模式;文献9提出了对Yahoo进行基于层次聚类式重组和检索方式的改造方法,并实现了基于特征矢量空间模式检索方法。个性化搜索引擎一般都基于元搜索引擎来进行个性化服务。元搜索引擎5,6指的是搜索引擎之上的搜索引擎,可以将用户的检索词转发给多个底层的搜索引擎,使用户不必直接跟底层的各个搜索引擎交互,相当于增加

4、了搜索引擎的信息覆盖面。搜索引擎中最关键的部分是文档建模技术,目前的众多文本模型一般可以分为向量空间模型、布尔逻辑模型和概率推理模型11。人们普遍认为向量空间模型是一种非常有效的文本模型7。它使用一个多维的向量来表示一个文档,每一个维度对应于文档中的一个关键词,维度上的值是对应关键字的权值。只要通过某种策略计算出每一个字项的权值,就可以将文档D表示成一个向量。这里假设每一个字项的权值分别用W1、W2、W3W m表示,则文档D的向量表示为:D=(W1, W2, W3, W m但是,向量空间模型有一个固有的缺点,即假设所有的索引项都是独立的,而事实上信1本课题得到高等学校博士学科点专项科研基金(项

5、目编号:20030145017的资助。 息的索引项之间常常是具有某种内部关联的。为了描述文本词汇之间的相关联的程度,本文提出了一种新的文本建模技术,即词汇相关度模型。3.词汇相关度模型3.1 词汇相关度模型中文档的表示在词汇相关度模型中,一个包含m 个词汇的文档D 被表示成m 个二元组的集合:,(,.,(,(2211m m w t w t w t D =其中,t i 表示词汇,w i 表示t i 在文本D 中的权重(重要程度,取值范围为-1,1。3.2 词汇相关度定义约定:用户对检索结果的反馈有三种情况:好结果、坏结果和不好不坏结果。系统取显示反馈的好结果和坏结果两种情况。定义:1“#”代表相

6、关度运算,是一个二元运算符;对于词汇A 和B ,A#B 代表A 、B 之间的相关度;通常情况下,#运算不可交换。2Good_A 表示用户检索词汇A 时反馈好结果的个数;Bad_A 表示用户检索词汇A 时反馈坏结果的个数。3Good_A_B 表示用户检索词汇A 的“好结果”中,出现词汇B 的好结果的个数;Bad_A_B 则表示相应的坏结果的个数。4GoodA#B=Good_A_B/Good_A ,取值在闭区间0,1之间,表示在用户反馈的“好结果”中两词汇同时出现在文本中的概率,我们称此为正相关度。正相关度对词汇之间总的相关度有正面影响。5BadA#B=(-1×Bad_A_B/Bad_A

7、 ,取值在闭区间-1,0之间,表示在用户反馈的“坏结果”中两词汇同时出现在文本中的概率,我们称此为负相关度。负相关度对词汇之间总的相关度有负面影响。6A#B = GoodA#B + BadA#B,表示A 与B 之间总的相关度,取值在闭区间-1,1之间。词汇相关度反映了在特定用户眼中词汇与词汇之间的相关联的程度。对于不同的用户和不同的搜索,词汇之间的相关度是不同的。如:对喜欢音乐下载的用户来说“音乐”#“下载”值会比较高,而对喜欢音乐软件的用户“音乐”#“软件”值会比较高。3.3 用户偏好信息的存储在词汇相关度模型中,我们使用一个逻辑上的相关度网来表示用户的偏好信息。这个相关度网中的每一个节点代

8、表一个词汇,两个节点之间的连线代表了两个词汇之间的关系,连线上方的数值代表了这两个词汇之间相关度。如图1所示,是一个简单的相关度网。 图1 简单的词汇相关度网图1中,词汇之间的连线表示词汇之间的关系,这个关系是单向的。连线上的数值表示两个词汇之间的相关程度。例如图1中“t1”与“t2”之间的相关度是v1,也就是说明该用户搜索“t1”的时候,与“t2”相关的程度为v1。在相关度网中,箭头一般都是单项箭头,表示词汇相关程度不可交换。对于某个特定的用户,在他使用个性化信息检索系统的过程中,会不断地向系统发出一些反馈信息。系统就可以利用这个反馈信息自动构造或更新相应的相关度网。由于词汇关系网是在用户反

9、馈过程中建立起来的,关系网就好像“指纹”一样,各不相同。有了这样的一个相关度网,就可以通过查询这个网来得到任意给定的两个词汇的相关度。4.个性化评估算法个性化元搜索引擎依赖于底层搜索引擎的搜索结果,系统必须对底层返回的结果文本集按一定算法进行重新评估,最后排序输出。根据用户输入的检索词,系统可以通过词汇相关度网查询关键字与摘要关键词中的每一个词汇的相关度,来计算文本中二元组里的词汇权重。4.1 单检索词的文本评估计算模型我们首先考虑用户只输入单个检索词q时文本评估值的计算,如图2所示。假定底层搜索引擎根据q返回的结果文本D中包含m个关键词t1、t2、t m。通过查询词汇相关度网可以获得各个关键

10、词与检索词q的相关度,分别用w1、w2w m表示。此时,相关度就是二元组中的权重。 图2 单个检索词时文本评估值的计算 那么,(,.,(,(2211m m w t w t w t D =的评估值为各个权重(相关度之和(w 1+w 2+w m 归一化之后的结果,我们用w(D表示结果文本D 的评估值。(1=ni i w D w 1(4.2 多检索词的文本评估计算模型假如用户输入n 个检索词,可以按照单个检索词类似的方式单独处理每一个检索词。如图3所示。 图3 n 个检索词时文本评估值的计算假设根据n 个检索词检索得到的结果文本D 包含m 个关键词t 1、t 2、t m ,每一个关键词与各个检索词之

11、间都有一个相关度。在只考虑q 1检索词的情况下可以计算出文本中各个关键词与q 1之间的相关度;同样,在只考虑q n 检索词的情况下,可以计算出文本中各个关键词与q n 之间的相关度。我们用w i1、w i2、w im 来表示各个关键词与检索词q i 之间的相关度。显然,对于文本D 中的任意关键词t i 都有n 个检索词与之相关,形成n 个相关度,此时必须使用一定的策略来计算t i 的最终权重,我们用w(t i 来表示这个最终权重。本文采用如下3种策略来计算w(t i 。策略1:剩余项加权和在这种策略中,我们将数值1与关键词当前权重之差称作剩余项。每当计算出关键词与检索词之间的一个权重,就在关键

12、词当前权重的基础之上加上当前剩余项与新计算出的相关度的积。这种策略主要考虑到关键词与检索词的相关度中的高相关度群体的利益,计算的结果主要靠近高相关度群体。用w j 表示q j 与t i 的相关度: w j =q j # t i (j 1,n,i 1,m 则:w(t i = w 1+ (1- w 1×w 2+ (1- w 1-(1- w 1×w 2×w 3检索词文本关键词 + (1- w 1-(1- w 1×w 2-(1- w 1-(1- w 1×w 2×w 3×4 + 化简得:+=,1,1,.,1211,1,12,1.1(.

13、1(n i iik n ik i i i k ji n j i jin i ij ww w w ww wt w (且互不相等(2可以看出,公式2就是容斥定理,因此我们也可以把该策略叫做容斥策略。策略2:平均值即关键词的最终权重等于各个相关度的平均值。该策略的出发点在于平衡相关度之间的值差。(3=nj ji n w t w 1/(策略3:连乘积该策略中,关键词的最终权重等于它的各个相关度的连乘积。与剩余加权和不同的是,该策略主要考虑到低相关度群体的利益,计算结果将靠近低相关度群体。(4=n j jww 1i t (容易验证,只要相关度在-1,1区间上,以上三种策略计算出来的权重也在-1,1区间上,并且权重与相关度的计算顺序无关。得出摘要中的关键词t i 的权重w(t i 之后,可以通过这些权重来计算整条结果的评估值。由于在个性化元搜索引擎中,所评估的对象为网页的摘要,长度基本相当,因此,可以直接使用各个关键词的权重之和来作为整条结果文本的评估值,不必考虑归一化问题。此时计算W(D的公式如下:(5=ni it w D w 1(4.3 个性化搜索算法对于底层搜索引擎产生的结果文本集合R(D中的每一个文本D i ,首先按照确定好的策略来计算公式5的