Computer Science and Application 计算机科学与应用, 2011, 1, 128-133 http://dx.doi.org/10.12677/csa.2011.13026 Published Online December 2011 (http://www.hanspub.org/journal/csa) Copyright © 2011 Hanspub CSA A Weighted Set-Based Implicit Feedback Algorithm for Search Engine Hui Zhang*, Yan Chen State Key Lab. of Software Development Environment, Beihang University, Beijing Email: {hzhang, chy}@nlsde.buaa.edu.cn Received: Oct. 7th, 2011; revised: Oct. 29th, 2011; accepted: Nov. 19th, 2011. Abstract: With the quick development of the Internet, online information recourses are becoming richer and richer. However, traditional search engines are becoming hard to acquire the users’ retrieval intention because of the short keywords user inputted, so it is difficult to satisfy the needs of the user. In this paper, we proposed a Weighted Set-based implicit feedback algorithm to improve accuracy of the search engines effectively. Th- rough analyzing the characteristics of the snippets of Web pages search engine returned, we present a kind of Weighted-Set for representing Web page snippets and a method for calculating the weight of elements in this Set. In addition, we design an approach to calculate the intersection between any two Weighted-Sets, which can obtain users’ implicit search intention automatically, so that we can improve search accuracy in the way of query expansion. Query expansion experiments on the popular Google search engine show that our algo- rithm can improve search accuracy effectively. Keywords: Weighted-Set; Search Engine; Implicit Feedback; Intersection Operation 一种基于带权集合的搜索引擎隐式反馈算法 张 辉*,陈 岩 北京航空航天大学软件开发环境国家重点实验室,北京 Email: {hzhang, chy}@nlsde.buaa.edu.cn 收稿日期:2011 年10 月7日;修回日期:2011年10 月29 日;录用日期:2011年11 月19 日 摘 要:随着Internet 的迅速发展,网络信息资源开始爆炸式增长。传统的搜索引擎很难从用户输入的 检索词中获知其检索意图,只能返回大量匹配结果供用户选择。为了有效的提高搜索引擎的查准率, 本文提出了一种基于带权集合的隐式反馈算法。本文通过分析搜索引擎返回结果页面的特点,提出了 一种描述网页摘要的带权集合以及相应元素的权重计算方法,并设计了一种带权集合的交集运算方法, 通过该运算可以获取用户 隐含的检索意图,最后 以查询扩展的方式提高 搜索引擎的准确性。本 文在 Google 搜索引擎上做了本算法的若干实验,验证了本算法的有效性。 关键词:带权集合;搜索引擎;隐式反馈;交集运算 1. 引言 随着互联网上Web信息的激增,搜索引擎已成为 人们在信息海洋中获取有效信息不可或缺的工具。然 而,搜索引擎并未尽如人意,比如当用户输入“PC 价 格”时,搜索引擎 Google 会返回“PC塑料价格”、 “PC 电脑价格”等语义截然不同的结果,而且结果总 数为 105,000,000 之多[1],使得用户还需花费许多时 间筛选他真正需要的东西,有时也会因找不到理想的 结果而感到失望。有研究表明大约有50 %的检索无法 得到理想的结果[2]。造成这个问题的原因有两个方面: 一方面是人们输入的检索词一般很短,如 Web检索词 的平均个数为 2.4,近一半的用户在检索时只输入 1 个检索词[3],寥寥几个检索词往往词不达意,不能准 确表达用户意图;另一方面,搜索引擎无法从仅有的 几个检索词中获知用户真实需求,只能采用关键词匹 张辉等一种基于带权集合的搜索引擎隐式反馈算法 129 q 配的方式返回大量结果供用户选择[4,5]。 如果搜索引擎具有一定智能并能自动识别用户的 检索意图,那么只需把最符合用户意图的检索结果返 回即可,从而大大提高检索效率。如何使得搜索引擎 能够自动感知用户的搜索意图呢?有关研究人员提出 了一种“相关反馈”(Relevance Feedback)方法,并证 明了其在信息检索中的有效性与准确性[6-9]。其设计思 想是,在信息检索过程中通过用户交互来提高最终的 检索效果[9]。相关反馈需要用户明确指出哪些文档是 符合本人要求的相关文档,但实际上很少有用户愿意 做这种额外的操作[1]。“隐式反馈”已成为当前相关 研究的热点[1,9,10],其主要思想是记录用户在检索信息 时的交互行为(如输入的关键词、点击的网页、停留的 时间等),通过分析从中自动获取隐含的用户检索意 图。 本文分析了搜索引擎返回结果页面的特点,提出 了一种描述网页摘要的带权集合以及相应元素的权重 计算方法,并设计了一种带权集合的交集运算方法, 通过该运算可以获取用户隐含的检索意图,最后以查 询扩展的方式提高搜索引擎的准确性。 本文其余章节安排如下:第2章讨论该领域的相 关研究;第3章详细介绍该算法模型的建立和工作流 程;第 4章对算法的实验结果进行分析;第 5章算法 总结。 2. 相关研究 相关反馈的一个经典算法为 Rocchio算法[8],其 基本思想可以用下面公式表示 =argmax ,, optr nr simsim C q qqC (1) 即最优反馈向量与相关结果向量 r相似度 最大,与不相关结果向量相似度nr 最小。文献[11] 是Rocchio 算法的一个实例,主要基于反馈信息中的 文档与初次检索结果中文档之间的距离,利用相关文 档与不相关文档作为反馈信息来提高搜索引擎查准 率。文献[12]给出了一种利用海量用户点击行为的记 录进行网页内容相关性挖掘的方法,在此基础上给出 了一种反馈式搜索引擎框架及相关算法;文献[13]以 Web2.0 中用户行为作为研究对象,通过发掘用户反馈 方式,提出了用户反馈分值的概念,并通过用户反馈 影响搜索结果排名的具体方式以及相应实现进行研 究,提出了一种基于神经网络的网页排序算法。 opt qC C 以上文章提出的算法均是在具有大量用户访问行 为基础上的学习算法,通过提取反馈信息实现对搜索 结果排序的优化。本文算法以单个用户在浏览检索结 果时的点击行为作为反馈信息,在对反馈信息的描述 上, 并没有选取当前流行的向量空间模型 VSM[14],而 是采用集合论的集合概念;在对反馈信息的处理上, 采用集合交集运算提取不同网页摘要的共性信息,把 共性信息作为用户的反馈,这样对提高反馈算法的时 效性及准确性起到了重要作用。 3. 算法模型的分析与建立 3.1. 设计思想 3.1.1. 设计分析 人的认知模式表明:用户判断一条信息的相关性 比清晰地表达其需求更容易一些[9]。即用户不一定能 清楚地表达出所他需要的信息是什么,但是能够容易 地判别一条信息是否满足其要求。下面看一个场景: 用户 A想要了解电脑价格信息,于是他在 Google 搜索引擎上输入关键词“电脑价格”进行查询,搜索 引擎返回大量结果项,如图1( 摘取其中两条)所示: 如图 1所示,搜索引擎返回的结果项一般包含两 部分:网页标题与网页摘要。用户在浏览搜索结果项 时,往往倾向于查看排名靠前的网页[15],也就是说如 果用户 A浏览了排名靠前的网页标题和摘要,但最终 点击查看了排名靠后的网页,这正好说明排名靠前的 网页不是他的最佳选择,而被点击查看的结果项反而 能表达 A的真实意图。 Figure 1. Search engine result items 图1. 搜索引擎结果项(网页标题与网页摘要) Copyright © 2011 Hanspub CSA 张辉等一种基于带权集合的搜索引擎隐式反馈算法 130 假定在 Google 返回的前十条结果项中,有 5条被 用户 A点击浏览,那么这 5条结果项的共性信息(共 同出现的词语)恰恰体现了用户A的检索意图。一般 情况下,为了得到更多相关信息,用户 A根据自己的 需求不断修正输入的关键词信息,如:“电脑报价”、 “电脑厂商报价”等,经过多次的修正查询,终于得 到了自己期望的信息。 通过对该场景的分析及对人们浏览行为习惯的总 结,可以得到如下结论: 1) 用户浏览检索结果项时对标题的关注度要高 于对摘要的关注度,所以查询结果项的标题信息更能 体现用户的关注点; 2) 用户点击顺序与查询结果项中所包含的信息 重要性成反比[16],即:被用户查看的查询结果项越靠 后,其中包含的信息越可能是用户所需要的东西; 3) 通过对每次被点击的检索结果项做集合交集 运算,可以快速提取交集中的共性信息,这些共性信 息即为用户的意图,也是对搜索引擎的反馈信息。 3.1.2. 基本假设 为了保证算法的可行性,根据以上得出的结论, 在建立本算法模型前,做出如下四个假设: 1) 搜索引擎返回的搜索结果项和检索词具有一 定的相关性,并且一次检索能返回多个搜索结果项; 2) 搜索结果项与检索词的相关度大小已进行排 序,即越相关的结果项排序越靠前; 3) 搜索结果项包括网页标题和网页摘要两部分 信息(如图 1所示),这两部分信息能反映该网页的关 键内容,并且标题信息的权重要大于摘要信息的权重; 4) 用户点击浏览搜索结果项的行为是用户的有 意选择,被选中浏览的结果项内容与用户的检索意图 是相符合的,能够体现用户的需求。 在以上四个假设中,实际上搜索引擎都能够满足 前三个假设,第四个假设也是符合人们在信息检索时 的行为习惯的。 3.1.3. 设计思想 根据 3.1.1.中的分析与 3.1.2.中的假设,针对Web 搜索引擎,本文设计实现了一种基于带权集合运算的 隐式反馈算法,其基本思想为: 用户在浏览搜索引擎返回的结果项时,对自己感 兴趣的结果项往往会点击查看具体的网页。因此,该 算法可以记录用户的点击行为,并为每个结果项提取 关键词并生成对应的集合,考虑被用户点击的结果项 排名、关键词词频、关键词所 处位置(标题还是摘 要) 等因素,为每个关键词生成相应的权重,从而为每个 搜索结果项生成对应的带权集合。同时,使用带权集 合的相交运算从多次点击的结果项中抽取共性信息, 然后选择权重较大的共性信息作为新的关键词进行扩 展查询,从而缩小搜索结果的范围。如此往复,直到 满足用户的检索需求为止。 3.2. 模型符号系统的定义和说明 这里首先定义算法中用到的两个概念,并定义其 运算规则。 定义 1 关键词三元组 _ ,, K Gkwc,表示带有 权值信息的关键词元组,其中 k表示关键词,w表示 关键词的权重,c表示关键词被用户浏览的次数。 设A, B分别为任意关键词三元组,a, b为任意常 数,用 A k表示 A的关键词; A w表示 A的关键 词权重; A c表示 A的关键词被用户浏览的次数, 则有: ,,aAAkaAwaAc (2) 即:对关键词三元组 A乘系数 a,三元组中“关 键词”项不变,“权重”与“浏览次数”乘相应系数 a。 ,, ,0,0, aA bB , A kaAwbBw aAcbBc A kB k AkBk 若 若 (3) 即:关键词三元组A与B做“+”运算,若 A与 B“关键词”项相同,分别对其“权重”与“浏览次 数”项做代数相加元素;否则,结果为空。 推论 1 相等关系: AB 当且仅当 A kB k, A wB w且 A cB c 推论 2 等价关系: A B 当且仅当 A kB k 例1 设关键词三元组:A = (电脑, 0.1, 1), B = (电 脑, 0.2, 2), C = (价格, 0.3, 3)。 Copyright © 2011 Hanspub CSA 张辉等一种基于带权集合的搜索引擎隐式反馈算法 131 不妨假设常数: a = 2, b = 3; 则:aA = (电脑, 0.2, 2); aA + bB = (电脑, 0.8, 8); aA + bC = (, 0, 0); 定义 2 带权集合:表示带有权重信息的关键词集 合,本文指集合元素为关键词三元组的集合。 带权集合元素要满足互异性,互异性指集合中任 意元素两两之间均不满足关键词三元组等价关系。 如果 M, N分别为任意带权集合,带权集合 M, N 的相交运算可表示为 M + N,对, , 若 ,则,, mn ; 否则,nM 。 mM N nN M N mn mM mMN N nM N 例2 设关键词三元组:A = (电脑, 0.1, 1), B = (电 脑, 0.2, 2), C = (价格, 0.3, 3)。 则:带权集合 R1 = {A, C}, R2 = {B, C} R1与R2交集(带权集合的加运算)可表示为: R1 + R2={A + B, C} = {(电脑, 0.3, 3), (价格, 0.3, 3)}。 3.3. 模型的建立 假设用户经过了 m次的关键词搜索得到了满意的 结果,针对第 i次(1)查询操作,有: im 1) 向搜索引擎发送的关键词集合为: Keyword_1_ ,2_ ,3_1_ikikiki kn i (4) 其中表示第 i次查询的关键词数; 1_ni 2) 用户点击的结果项集合为: selectedResult _1_,2 _,3_2 _iriririrni (5) 其中表示第 i次查询用户点击浏览的结果 数; 2_ni 若 _ selectedResult_1_2 _rj iij ini WeightedSet __ij WeightedSet __ ,取 对应结果项的带权集合 ,集合中的 每个关键词三元组对应着结果项中的一个关键词,对 A ij ,则: A k= 关键词名称; 1Ac; 2 sub subsum sum logRank __Aw ij WFAkWF Ak (6) 其中:Ra 为当前结果项的搜索结果排序,nk__ij 、 为调节因子,保证权重与排序成反比,并使排 序对最终权重的影响控制在一定的范围内。一般 1Rank__ 100ij ,故可取 , 0.1,0 0,1 sum W ; sub W subsum 1WW 为结果项中网页标题部分所占权重, 为 结果项中网页摘要部分所占权重,且有 ,根据经验值一般 sub 0.6,0.8W; sub F Ak表示 A中关键词在标题中出现的频数, sum F Ak WeightedSet _ WeightedS 表示 A中关键词在摘要中出现的频数; 这样,用户第i次查询的关键词带权集合计算公式为: 2_ 1 ni j WeightedSet _ii Keyword _ _ 1i j (7) 3) 选择 中用户点击次数较多,权重 较高的关键词作为新的关键词集合 et_ i 。 3.4. 算法流程 该算法具体的算法流程如下: 步骤一 用户通过关键词集合 12 3 ,, j kkkKk 在搜索引擎中检索信息,其中 j k表示用户输入的第 j 个关键词;搜索引擎返回结果项集合 123 ,, i Rrrrr,其中 表示搜索引 擎返回的第 I条结果项的特征词(图2), 12iii ij k k, i rk j K 为 的 i r第j 个特征词。 步骤二 假如用户查看了结果项集 R中的m条结 果项,对每条结果项进行关键词提取,获取 m个关键 词集合: 12 ,m K KK; 步骤三 通过对 12 ,m K KK ' 集合的带权集合交集 运算,获取新的关键词集合 K (图3),即用户选择的 m条结果项的共性信息,同时计算出集合中关键词的 权重。 Figure 2. The set of search engine result items 图2. 检索结果项集合 Figure 3. Intersection operation model figure of keywords 图3. 关键词交集运算模型图 Copyright © 2011 Hanspub CSA 张辉等一种基于带权集合的搜索引擎隐式反馈算法 132 Figure 4. Algorithm process figure 图4. 算法流程示意图 从步骤三中得到的关键词集合 ' K 中选择权重较 大的关键词组成新的关键词集合,跳转到步骤一重 复执行,从而达到快速缩小检索范围的目的,直到满 足用户的检索需求为止(图4)。 K 4. 算法的检验与参数优化 4.1. 实验一 为了验证基于带权集合的隐式反馈算法的有效 性,进行了如下实验: 实验一 选择50 名不同用户进行测试,每位用户 执行 20 次查询任务,查询内容按照他们各自的兴趣自 由选择。这 50 名用户平均分成两组,A组使用 Google 搜索引擎进行查询,B组使用建立在 Google 搜索引擎 基础上的本算法进行查询。 在本次实验中,统计了每位用户在每次查询操作 中需要浏览的结果项数、平均每页(每页 10条)查询结 果项的满意数(表1)以及前 5页每页结果项的平均满 意数(图5): 如表 1、图 5所示,可以看到,基于带权集合的 隐式反馈算法显著的提高了查准率,并且减少了用户 的浏览次数。 4.2. 实验二 在模型的分析与建立过程中,影响关键词权重的 因子主要有三个,即:公式(3)中的 sub W ,以及 ,为 了选择合适的影响因子,最大限度的提高搜索引擎的 查准率,进行了如下实验: 实验二 选择50 名用户进行跟踪测试,每位用户 执行 20 次查询任务,查询内容按照他们各自的兴趣自 由选择。这 50名平均分成五组(A、B、C、D、E), 每组反馈模型中 sub W ,, 取值如表 2所示: 通过本次实验,统计了每位用户每页查询结果的 满意数,如表 3、图6所示。 Table 1. Experiment 1 results 表1. 实验一结果 分组 用户达到满意的点击浏览总计次数 每页结果项的满意数 A组 14 5.8 B组 11 7.0 Figure 5. The average number of satisfaction per page of top 5 pages 图5. 前5页每页结果项的平均满意数 Table 2. The value of of each group in experiment 2 sub ,,αβW 表2. 实验二每组取值情况 sub ,,αβW 分组 sub W A组 B组 C组 D组 E组 –0.05 –0.05 –0.05 –0.05 –0.05 1 1 1 1 1 0.6 0.65 0.7 0.75 0.8 Table 3. Experiment 2 results 表3. 实验二的结果 分组 每页结果的平均满意数 A组 B组 C组 D组 E组 7.3 7.6 7.1 6.8 6.8 Figure 6. The average number of satisfaction of each group in experiment 2 图6. 实验二各组每页结果的平均满意数示意图 Copyright © 2011 Hanspub CSA 张辉 等 一种基于带权集合的搜索引擎隐式反馈算法 Copyright © 2011 Hanspub CSA 133 当 不变,选取不同的 sub W ,取值进行比较实验 时,结果变化并不明显。 根据实验二,发现选取一定的的取值可以提 高算法的查准率;当 时,查准率最高; sub W sub 0.65W , 在一定范围内的取值对算法的查准率影响不大,故实 际操作中可以取 0.05 1 ,。 本算法的时间花费主要在共性信息的提取上,即 结果项集合的交集运算,假设用户在一次查询中点击 了m条结果项信息,每条信息的平均特征词为 n个, 对其做交集运算,时间复杂度为 O(mn),由于用户一 次查询中点击浏览的结果项 m条与其特征词数 n均较 小,所以本算法在一次查询中消耗的时间是很小。 5. 总结及未来工作 本文提出了一种基于带权集合的隐式反馈算法, 该算法通过实时记录用户的点击行为,通过带权集合 交集运算获取用户的查询意图,并自动进行扩展查询, 直到用户满意为止,达到了快速提高搜索引擎查准率 的目的,给用户带来了便利。 5.1. 算法的创新 本文在处理从搜索引擎结果项中获取共性信息 时,提出了一种带权特征词集合的生成算法以及带权 集合的相交算法,利用带权集合的相交运算进行快速 提取用户隐含的检索意图。此外,本文在估计特征词 权重时,将贝叶斯条件概率和最大似然估计有机结合 起来,并综合考虑了特征词位置、关键词频率、结果 项排名的影响因素,从而提高了搜索引擎的查准率。 5.2. 下一步工作 1) 在对 参数优化中,通过参与实验的几组数 据进行离散型设计,尚有优化的空间,包括将离散数 据连续化,取其极值,得到更优的参数; sub W 2) 如何在进行搜索时有效结合近义词、同义词进 行扩展查询,如何更有效地去除一些无意义的虚词等 都需要进一步优化; 3) 用户浏览结果项时的滞留时间也是影响权重 的重要因素,如果能充分考虑该因素,也能够提高反 馈模型的精确度。 参考文献 (References) [1] D. Kelly, J. Teevan. Implicit feedback for inferring user pre- ference: A bibliography. SIGIR Forum, 2003, 37(2): 18-28. [2] T. Joachims. Optimizing search engines using clickthrough data. In Proceedings of SIGKDD 2002, 2002: 133-142. [3] X. H. Shen, B. Tan and C. X. Zhai. Implicit user modeling for personalized search. Bremen: Proceedings of the 14th ACM Inter- national Conference on Information and Knowledge Management, 2005. [4] 周博, 岑荣伟等. 一种基于文档相似度的检索结果重排序方 法[J]. 中文信息报, 2010, 25(3): 19-23. [5] 侯越先, 张鹏, 于瑞国等. 基于内容相关性挖掘的反馈式搜 索框架[J]. 天津大学学报, 2008, 41(8): 941-945. [6] Z.-L. Wu, C.-H. Li. Topic detection in on-line discussion using non-negative matrix factorization. Silicon Valley: IEEE/WIC/ACM International Conferences on Web Intelligence and Intelligent Agent Technology, 2007: 272-275. [7] A. Spink, D. Wolfram, M. B. J. Jansen, T. Saracevic. Searching the web: The public and their queries. Journal of the American Society for Information Science and Technology, 2001, 52 (3): 226-234. [8] G. Salton, C. Buckley. Improving retrieval performance by re- trieval feedback. Journal of the American Society for Informa- tion Science, 1990, 41(4): 288-297. [9] C. D. Manning, P. Raghavan and H. Schutze. Introduction to In- formation Retrieval. Cambridge: Cambridge University Press, 2008. [10] J. J. Rocchio. Relevance feedback in information retrieval. The SMART Retrieval System: Experiments in Automatic Document Processing, Prentice-Hall Inc., 1971: 313-323. [11] J. Allan, C. Wade and A. Bolivar. Retrieval and novelty dete- ction at the sentence level. Toronto: Proceedings of the 26th Annual International ACM SIGIR Conference on Research and Develop- ment in Information Retrieval, 2003: 314-321. [12] 金祖旭, 李敏波. 基于用户反馈的搜索引擎排名算法[J]. 计 算机系统应用, 2010, 19(11): 60-65. [13] T. Moon, L. H. Li, W. Chu, C. Y. Liao, Z. H. Zheng and Y. Chang. Online learning for recency search ranking using real-time user feedback. ACM, New York, 2010. [14] G. Salton, A. Wong and C. S. Yang. A vector space model for information retrieval. Communications of the ACM, 1975, 18(11): 613-620. [15] E. Agichtein, E. Brill and S. Dumais. Improving web search ranking by incorporating user behavior information. Proceedings of the 29th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, 2006. [16] T. Joachims, L. Granka, B. Pan, H. Hembrooke and G. Gay. Accurately interpreting clickthrough data as implicit feedback. Proceedings of the 28th Annual International ACM SIGIR Con- ference on Research and Development in Information Retrieval, 2005: 154. |