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

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

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

3、汇相关度的个性化元搜索引擎的原型系统。2.相关工作目前对个性化信息检索技术的研究比较很广泛,已经出现了很多关于个性化搜索的服务系统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 词汇相关度定义约定:用户对检索结果的反馈有三种情况:好结果、坏结果和不好不坏结果。系统取显示反馈的好结

6、果和坏结果两种情况。定义:1“#”代表相关度运算,是一个二元运算符;对于词汇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=(-

7、1×Bad_A_B/Bad_A ,取值在闭区间-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

10、m。通过查询词汇相关度网可以获得各个关键词与检索词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

11、2、t m ,每一个关键词与各个检索词之间都有一个相关度。在只考虑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

13、,1,.,1211,1,12,1.1(.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区间上,以上

14、三种策略计算出来的权重也在-1,1区间上,并且权重与相关度的计算顺序无关。得出摘要中的关键词t i 的权重w(t i 之后,可以通过这些权重来计算整条结果的评估值。由于在个性化元搜索引擎中,所评估的对象为网页的摘要,长度基本相当,因此,可以直接使用各个关键词的权重之和来作为整条结果文本的评估值,不必考虑归一化问题。此时计算W(D的公式如下:(5=ni it w D w 1(4.3 个性化搜索算法对于底层搜索引擎产生的结果文本集合R(D中的每一个文本D i ,首先按照确定好的策略来计算公式5的结果w(D i 。最终,所有依据w(D i 的大小对R(D进行排序输出。算法描述如下:算法1:基于词汇相

15、关度的个性化搜索算法。输入:确定好的一个策略(策略1、2、3中的某一个,词汇相关度网,搜索关键词,一个搜索引擎。输出:个性化搜索排序结果。(1 根据查询关键词,利用搜索引擎产生初步的搜索结果集R(D; (2 置迭代次数 i=0;(3 对集合R(D中的第 i 篇文档D i ,利用词汇相关度网找出D i 中每个关键字t m 与每个查 询关键词qn之间的相关度wmn； (4 利用确定好的策略所指定的公式来计算Di 中每个关键字tm 的权重w(tm。 (5 利 用 公 式 公 式 5 计 算 文 档 Di 推 荐 给 用 户 的 评 估 值 w(Di ， 加 入 推 荐 列 表 recommend(i

16、； (6 如果Di是集合R(D中最后一篇文档，转(7；否则，置 i=i+1，返回(3。 (7 根据列表 recommend 中的值由大到小对 R(D进行排序并输出。 5原型系统设计 本文所设计的基于词汇相关度模型的个性化元搜索引擎原型系统体系结构，如图 4 所 示。 Google 网络信息搜集 结果缓存 分词 查询 界面 Altavista excite 偏好 管理 用户 反馈 过滤 结果 合并 结果 浏览 服务器 客户端 baidu Internet 图 4 个性化元搜索引擎体系结构图 总体来讲， 个性化元搜索引擎除了需要包括一般元搜索引擎所必需有的信息收集、 结果 缓存、结果合并、查询界面

17、、结果浏览等组件之外，还要包括分词过滤模块、用户反馈模块 和偏好管理模块。 （1）信息收集模块负责从各个外部搜索引擎收集数据。并把查询结果转交给用户、缓 存模块以及分词过滤模块。 （2）结果缓存模块负责缓存查询结果。当用户再次发起同样的查询请求时，系统就可 以直接通过混存模块找到查询结果，提高系统的执行效率。 （3）分词过滤模块负责对信息收集模块所收集的内容进行分词处理，并且过滤掉页面 内容中的终止词和其他一些无意义的符号。 然后， 将处理好的页面内容发送给偏好管理模块。 （4）偏好管理模块主要负责对用户的偏好信息（用户模型信息）进行自动提取、存储、 读取以及管理。 （5）个性化元搜索引擎的结

18、果合并模块必须能够依据偏好管理模块所生成的用户模型 重排结果次序，以提高检索结果质量。这需要对每一条检索结果计算出一个评估值。然后根 据评估值的高低对检索结果进行排序。最后将排序好的结果送至用户界面模块显示给用户。 （6）用户界面模块主要提供系统功能与用户之间的界面。 （7） 用户反馈模块用来收集用户在使用元搜索引擎的过程中对系统做出的反馈， 并且， 通过对这些反馈信息进行挖掘来收集用户偏好信息、调整用户模型的能力。 -6- 图 5 是原型系统的一个快照。 图 5 个性化元搜索原型系统快照 6测试结果 6.1 试验评价标准 本文主要通过考察原型系统的个性化算法的灵敏度、 个性化算法的抗干扰性、

19、 个性化算 法语义相关性这 3 个指标来测试个性化 Web 信息检索原型系统的性能以及其正确性。 （1）个性化算法灵敏度 灵敏度也就是系统捕获用户偏好信息的速度。用户对一条排名不在最前的查询结果做 出 g 次好评，使得该条结果的排名升至第一。则定义灵敏度： S=1/g 少。 （2）个性化算法抗干扰性 即系统抵抗用户偏好信息之间相互干扰的能力。用户在完成一次的检索之后，又进行 了一次其他检索，之后，用户重复第一次检索，发现总共 J 个检索结果中，前 K 条检索结 果的排名没有发生变化，则定义抗干扰性： A=K/J 息所干扰。 （3）个性化算法语义相关性 即系统对语义上与用户个性偏好相近的检索结果

20、进行识别的能力。 用户对某条结果进行 了一次好评价，使得这条结果的排名升至第一，并且，在结果中，与这条结果属于同一类的 结果共有 M 个，其中，有 N 个结果在用户的这次好评之后，排名没有后退，则定义相关性： R=N/M 性偏好相近的检索结果进行重排，将其排名提前。 （8） 语义相关性强， 意味着系统可以充分利用从用户收集来的偏好信息， 对语义上与用户个 （7） 抗干扰能力越强， 意味着系统过去收集到的个性化信息， 越不易被后续的其他个性化信 (6 灵敏度越高，系统将用户所指定的网页排在结果列表的前面所需要的用户反馈数就越 6.2 试验结果 我们主要测试原型系统在用户输入单个检索词和多个检索词

21、进行查询的时候，该系统 -7- 的上述 3 个指标。 并对本文第四节中的 3 种策略分别进行测试和比较。 试验数据及结果如表 1 所示。 表 1 测试结果 灵敏度 剩余项加权和 单检索词 多检索词 单检索词 平均值 连乘积 多检索词 单检索词 多检索词 S=1/1=100% S=1/1=100% S=1/1=100% S=1/1=100% S=1/1=100% S=1/4=25% 抗干扰性 A=2/23=8.7% A=0/20=0% A=2/23=8.7% A=0/20=0% A=2/23=8.7% A=0/20=0% 语义相关性 R=6/8=75.0% R=7/15=46.7% R=6/8=

22、75.0% R=6/15=40.0% R=6/8=75.0% R=6/15=40.0% 上述实验的抗干扰性均不高，这主要是因为本文上述实验中所使用的干扰查询与原查 询极为相似，查询结果之间存在比较严重的相互干扰。为了证明抗干扰性，特意又作了抗干 扰性补充实验：用户先后搜索两个不相关的查询，原始查询搜索“象棋”并对其结果中的 1 条 结果进行“好”评价，干扰查询搜索“足球”并对其结果中的 1 条结果进行“好”评价。“象棋”与 “足球”这两个词在语义上并不相关（或者说相关度比较小） 。实验结论：对“足球”的查询以 及对其结果进行“好”评价，不会影响到检索词“象棋”的查询的结果。由于实验中所涉及到的

23、 两个查询都仅含有 1 个检索词。在这种情况下，3 种策略的结果相同： A=22/22=100.0%。 6.3 结论 由上述实验可以得出如下结论。 （1）当用户使用单个检索词进行查询的时候，本文所介绍的 3 种词汇评估计算策略是 等价的。 （2）当用户输入多检索词进行查询的时候，在算法灵敏度上，连乘积策略性能较差， 这是因为连乘积考虑低相关度群体， 导致结果向 1 收敛较慢； 而在语义相关性上 3 种策略相 差不大，连乘积算法稍稍差一点。结果比较如图 6 和图 7 所示。 图6 三种策略的灵敏度比较 图7 三种策略的语义相关性比较 （3）当用户搜索语义上不太相关的检索词时，这 3 种策略都能够

24、很好的抵抗不同检索 词之间的干扰。 综合上述结论， 可以看出本文所提出的 3 种计算权重的策略最终会影响到网页的排序。 这些测试同时表明，本文所描述的词汇相关度模型可以很好的表示词汇之间相关联的信息， 在这一方面，比向量空间模型要进步很多。笔者认为，该模型可以填补向量空间模型在词汇 相关度方面的空白，是个性化搜索引擎领域的一个新的智能方向。 -8- 参考文献 1 Hsieh-Chang Tu, Jieh Hsiang. An architecture and category knowledge for intelligent information retrieval agents J, D

25、ecision support Systems, 2000, 28: 255-268. 2 Christopher C. Yang, Jerome Yen, Hsinchun Chen. Intelligent Internet searching agent based on hybrid simulated annealing J, Decision Support Systems, 2000, 28: 269-277. 3 Zeng C, Xing CX, Zhou LZ. A survey of personalization technology. Journal of Softwa

26、re, 2002,13(10: 1952-1961 (in Chinese with English abstract. 4 Pretschner A. Ontology based personalized search MS. Thesis. Lawrence, KS: University of Kansas, 1999. 5 Adele E. Howe, Daniel Dreilinger. SavvySearch: A MetaSearch Engine that Learns Which Search Engines to Query J, AI Magazine, 1997, 1

27、8 (2: 19-25. 6 陈伟雄. 基于元搜索的中文搜索引擎研究与实现D, 清华大学, 2004. 7 B. Yuwono and D. Lee. Server Ranking for Distributing Text Resource Systems on the Internet J, DASFAA97, 1997, 391-400. 8 Michael Chiu-Lung Chau. Searching and Mining the Web for Personalized and Specialized Information D, The University of Arizo

28、na, 2003. 9 Mladenic D. Turning Yahoo into an automatic Web-page classifier. ECAI 98. In: 13th European Conference on Artificial Intelligence. John Wiley & Sons Ltd, 1998. 473-474. 10 陈伟雄. 基于元搜索的中文搜索引擎研究与实现D, 清华大学, 2004. 11 张晓冬. 张书杰等. 关于信息过滤模型的探讨J, 计算机工程与应用, 2002, 5: 99-100. 12 于振雷. 基于相关度模型的个性化元搜索引擎设计与实现D，东北大学