引用本文
徐洋, 王文生, 谢能付. 基于用户行为学习的元搜索结果聚类方法研究. 现代图书情报技术, 2010, 26(4): 53-58
Xu Yang, Wang Wensheng, Xie Nengfu. The Study of User Behavior Learning Based Results Clustering Method. New Technology of Library and Information Service, 2010, 26(4): 53-58  
Permissions
Copyright©2010, The modern information technology editorial office
This article is the open access journal literature, in the following situations are free to use: academic research and academic exchanges, scientific research and teaching, etc., but don't allow for commercial purposes.
基于用户行为学习的元搜索结果聚类方法研究
徐洋, 王文生, 谢能付
中国农业科学院农业信息研究所 北京 100081
基金:本文系中国农业科学院农业信息研究所基本科研业务费专项项目“基于语义Web的农业信息个性化服务研究”（项目编号：2008211）和国家科技重大专项课题“TD-SCDMA农业信息化应用方案开发及示范验证”（项目编号：2009ZX03001-019）的研究成果之一;
摘要

为解决搜索引擎结果繁杂而导致的浏览性不高的问题,提出一个基于用户行为学习的元搜索框架和结果聚类方法,并加以详细描述。利用该框架与方法,可以实时搜集用户行为进行推理学习,将学习到的有效知识存入知识库用以指导结果聚类,并随着用户的搜索过程不断调整完善。原型系统证明该方法是可行有效的。

关键词: 元搜索; 用户行为学习; 结果聚类
The Study of User Behavior Learning Based Results Clustering Method
Xu Yang, Wang Wensheng, Xie Nengfu
Institute of Agriculture Information, Chinese Academy of Agricultural Sciences, Beijing 100081, China
Abstract

In order to improve the legibility of searching results in current meta-search engines, an intellective meta-search engine framework and a results clustering method based on user behavior learning are set forth in a detailed description. Using this framework and method, the system can assemble the information of user behavior in real-time for reasoning and learning, accumulate the efficient knowledge into knowledge-base for the results cluster managing, adapt itself and be perfect continually as the users’ searching processes. The prototype system proves that the method is feasible and efficacious.

Keyword: Meta-search; User behavior learning; Results clustering
1 引 言

计算机技术和网络技术的飞速发展带来了Web信息量指数级的急剧增加,传统的综合性搜索引擎已经无法满足人们快速有效地寻找自己需要的信息的需求。据统计,任何一个搜索引擎索引的Web页面实际上都不到页面总数的三分之一,而且由于检索机制、范围、算法等的不同,导致同样一个查询请求在不同搜索引擎中的查询结果的重复率比较低[ 1]。元搜索引擎是解决此问题的主要方法之一,被称为搜索引擎之上的搜索引擎,它通过整合、处理各个成员搜索引擎的查询结果来提高系统的查询覆盖率。

但是,现有的元搜索引擎仍存在一定的问题。尽管通过对成员搜索引擎所递交的结果的分析处理,可以增大查询覆盖率,去除不必要的噪音,但是仍无法给用户以最精确的结果或者检索指导。聚类是将一个数据单位的集合分割成几个称为簇或类别的子集,每个类中的数据都有相似性,而不同聚簇中的对象具有尽可能大的相异性。通过聚类,用户可以方便地选择自己所需要结果的类别来查看结果,从而提高检索效率,优化搜索体验。

现实中,各大搜索引擎还没有加入聚类处理,但是通过Ajax实现的搜索提示可以算作聚类的提示。用户选择相应的提示可以作为直接搜索相应的结果类别,但是鉴于返回结果的数量依然比较大,所以深度的聚类仍是必要的。学术研究中,现有的聚类方法大都是基于一种算法,如基于关联规则的聚类算法[ 1]、准确描述所有配对方法(CAPP)[ 2]、基于特征名词(Salient Phrase)的聚类算法[ 3]等,但是这些算法都忽略了用户作为信息的最终使用者对信息如何有效分类具有决定作用。把用户纳入搜索体系,将其看作信息的挖掘者或提供者而不仅仅是使用者,利用用户在搜索过程中提供的信息对信息进行深加工才能最大限度地迎合用户的需求。因此,本文尝试设计并实现一个基于学习的元搜索框架,提出一种通过学习用户行为来对检索结果进行聚类的方法,以期从用户角度最大限度地提高信息结果的可浏览性,优化检索体验。

2 基于模块的元搜索体系及各模块设计
2.1 系统体系设计

系统总体设计如图1所示:

图1 系统总体设计图

该系统分为两层:基本流程层是一个改进的元搜索引擎框架,在基本框架的基础上添加了用户行为搜集模块;学习推理层是基于用户行为学习的聚类方法,其中的推理模块在规则库的指导下对用户行为搜集模块递交过来的信息进行推理学习,并将所得知识存入到知识库,用以指导后续结果处理模块对所搜集的成员搜索引擎的结果的处理。

2.2 具体模块设计

所有模块都有统一的整体架构,包括通信子模块、功能子模块和知识子模块三部分,具体如图2所示:

图2 模块基本架构

通信子模块负责所属模块主体同其他协作模块主体的通信交互,对外提供接受服务和请求服务的接口;功能子模块隐藏在通信子模块后,负责具体任务的处理;知识子模块负责本模块功能子模块的工作指导。各模块具体功能介绍如下:

(1)用户交互模块

负责整个系统同用户的交互,其任务包括:为用户提供统一的检索入口,并提供最终检索结果的展示,对用户对结果的类组选择做出具体反应。其知识子模块包括用户对结果类别选择相应的处理方法,可扩展包括注册用户的偏好信息等,用以指导提供给特定用户的制定信息组织方式的处理。

(2)用户行为搜集模块

负责搜集用户行为的初始信息,包括用户的检索输入和用户对类别标示的点击、删除操作行为两部分信息,并对信息进行初步加工。其知识子模块包含基本的分词方法,可扩展包含各种诸如最大左向匹配、基于统计的分词或者混合分词方法的知识。

(3)成员搜索引擎调度及结果收集模块

负责成员搜索引擎的调度和结果的收集及成员搜索引擎任务执行的生命周期控制,并负责成员搜索引擎所递交的结果的收集。其知识子模块包括各个成员搜索引擎针对不同搜索内容的能力差别和状态信息,用以指导对其调度。

(4)结果处理模块

负责成员搜索引擎所递交结果的处理。结合知识库的知识指导,需要完成去除无效链接、去重、相关度计算、排序、聚类等任务。其知识子模块包括除去聚类知识外的其他知识,包括无效链接和重复链接的排查方法、相关度算法、排序规则等。

(5)推理模块

对用户行为搜集模块所搜集的用户行为信息进行推理,主要负责处理关键词的相关关系、上下层次关系,并将知识存入到知识库。考虑到扩展性,其知识子模块独立为规则库。

(6)规则库

规则库实质为推理模块的知识子模块,为了扩展方便将其独立出推理模块,负责推理模块的推理学习过程的指导。

(7)知识库

负责存储推理模块所得的知识,作为后续的结果处理模块中对结果的聚类方法的指导方法来源。

3 基于用户行为学习的聚类方法

本方法基于以下假设:

(1)用户对信息的检索不是由单一的检索关键词确定。绝大多数情况下,用户所需要的结果由多个检索词细化范围来确定。用户可以一次输入多个检索词进行检索,也可以逐个输入检索词在结果中细化检索范围,找到所需的检索结果。因此,频繁被利用的不同检索关键词的组合标示着组合中任意一个检索关键词的结果都非常可能含有其他检索关键词的结果。

(2)对于确定的结果,关键词间的影响力不具有一对一映射关系。即对于两个关键词A和B,即使B关键词可以作为A关键词搜索结果的有效分组标示,但是A关键词作为B关键词检索结果的分组标示不一定有效。

i来表示,则φ]]>i来确定的结果范围。如果有n个关键词来确定最终结果,则最终结果的范围为ω=φ]]>j,Xk而言,它们的检索结果交集φ]]>j的检索结果φ]]>k的检索结果φ]]>k作为Xj的聚类标示可以圈定1/10结果,而Xj作为Xk的聚类标示只能圈定1/100的结果。因此,如果将任意一个0.01与0.1之间的值作为判定有效的阈值,则可以得出Xk作为Xj的聚类标示是有效的,而Xj作为Xk的聚类标示无效。]]>

为了便于方法的精确描述,本文作如下定义:

定义1:关键词的联系是指用户在检索过程或者对结果的选择过程中,有意识地将两个检索关键词集合到一起来搜索想要的结果,那么则称这两个关键词发生了一次联系。

定义2 :关键词相关度是指对于任意一个给定的查询关键词,其他查询关键词和该给定查询关键词的组合在多用户多次查询历史中被频繁使用的程度,用ni来表示,其大小等于两个关键词的联系数,关键词双方互称为相关关键词。

定义3 :上下义相关度是指对于给定的检索关键词A,其相关关键词B的上下义相关度单向地决定了B可以作为A的聚类标示的有效程度,用mi表示。mi越大,表示B作为A的分组标示越有效,其大小等于用户对给定结果聚类标示的确认或者删除操作来决定的联系数。

知识库以一个查询叙词表为主体,每个查询关键词都对应有自己的相关关键词队列。成员搜索引擎的检索结果递交到结果分析和处理模块后,结果分析和处理模块根据查询关键词的相关关键词队列对结果进行聚类,提供给用户进行选择。查询叙词表中每个词条的结构如下:

ID A: B (n1 m1) C (n2 m2) D (n3 m3) …… X (ni mi)

其中,ID为索引号,A为检索关键词,B、C、D等为检索关键词A的相关关键词,ni为对应的相关关键词与该检索关键词的关键词相关度,mi为对应的相关关键词与该检索关键词的上下义相关度。B、C、D等相关关键词队列按照关键词相关度ni由大到小排列。对于决定相关度的两个方面,用户在检索过程中的输入和用户对于所提供的结果聚类标示的点击或删除操作,关键词相关度ni由两者决定,上下义相关度mi由后者唯一决定。具体过程如下:

(1)当用户检索需求通过用户交互模块传递给分词模块时,分词模块将其规范化,剔除冗余的无意义虚词,提取出有效关键词,一方面传递给底层的成员搜索引擎使用;一方面传递给推理模块进行学习。推理模块会自动记录关键词间的联系,并将其录入到查询关键词叙词表中。具体规则如下:

①用户输入的检索需求被分解为单一关键词A,不做任何处理;用户的检索需求被分解为两个检索词A与B,转入②处理;用户的检索需求被分解为多个检索词,转入③处理。

②在A关键词的相关关键词队列查找B。若不能找到,则将B关键词插入到A的相关关键词队列尾,并计相关度ni为1;如果能找到,则将B关键词联系数,即相关度ni加1,并调整队列次序,使其按照ni由大到小排列;同理在B关键词的相关关键词队列中处理A关键词。

2)个关键词,]]>

④定期(时间过长或者过短都会影响实际分组效果,可人为设定或者基于统计方法动态调整)排查各检索关键词相关关键词队列,将位于前列(前t或r项)的相关关键词中上下义相关度mi最小者的相关度ni置为1并排至队尾,用以排除相关但是相对无效分组。

(2)结果处理模块先对结果进行去冗、相关度计算和排序的处理,最后的聚类处理需参照知识库相关知识进行,具体规则如下(假定人为设定最终结果需要t个分组):

①对于单一关键词检索,直接查找对应相关关键词队列,取前t项作为分组标示,依次对排序好的结果进行检索,将包含有相关关键词标示的结果归入到相应类别。

②对于多关键词检索,首先查找对应多个相关关键词队列,取其前r项(r≥t, r值过大或者过小都会影响类别和相应多个关键词的联系程度,可人为设定或者基于统计方法动态调整)中重合最多的相关关键词中前t项作为分组标示;若重合相关关键词数目少于t,则再取各相关关键词队列中关键词相关度最大的相关关键词补足t项。

③若所有相关关键词数目加和小于t,则可忽略t项限制。

(3)结果根据相关关键词来聚类呈现给用户后,为用户提供相应的类别标示,以供用户进一步缩小结果范围,提高检索精度。用户对所提供的相关关键词聚类标示的一次点击表示相关关键词和查询关键词产生了一次联系;用户对所提供的相关关键词聚类标示的一次删除表示相关关键词和查询关键词丢失了一次联系。推理模块可以根据此反馈,再次更新知识库。具体规则如下:

①用户点击一个类别,将该类别对应的关键词在当前所有检索关键词的队列中的对应相关度ni和mi加1,并调整相关关键词队列,使其按照ni由大到小排列;结果由用户交互模块进行相应处理。

②用户删除一个类别,将该类别对应的关键词在当前所有检索关键词的队列中的对应相关度ni和mi减1,并调整相关关键词队列,使其按照ni由大到小排列;结果由用户交互模块进行相应处理。

③当用户对于所提交的结果类别没有选择时,如果用户只选择查看结果,则不做任何处理;用户继续输入检索词进行检索作为新一次检索过程,按照过程(1)和(2)进行相应处理。

4 系统评测

在配置为Pentum 4 3.0GHz,512MB内存的Windows XP平台上,采用Python2.5.4 + Django1.0.2实现了一个原型系统,浏览器为Firefox3.5.3。受限于实验条件和方便系统调控,成员搜索引擎只选取了Google和百度,知识库的检索关键词词表由系统根据用户的输入动态生成,结果处理模块所需进行的搜集、去冗、排序和聚类等主要的处理过程完好。检索关键词选定为“苹果”、“论文”、“手机”三个,各选定两个成员搜索引擎的前20条结果。分析要点为功能的有效性和结果聚类方法的有效性两个方面。

4.1 功能有效性

模拟用户检索操作,根据Google和百度搜索时所给出的检索提示词在原型系统上进行搜索,装填知识库。知识装填完成后,在原型系统中搜索“苹果”时结果如图3所示:

图3 “苹果”检索结果页面

当点击第一个聚类“iPod”,所有归于“iPod”类的结果展示如图4所示:

图4 “iPod”类别点击后结果页面

按照左侧“结果类别”的顺序依次进行增量点击,排位靠后的类别点击次数多于排位靠前的结果,刷新后结果如图5所示,可以看到“结果类别”完全进行了反转,这说明该方法基于用户点击的类别调整是有效的。

图5 类别点击动态调整后的页面

4.2 结果聚类有效性

根据图4,点击“iPod”后所展示的结果都是和iPod产品相关的。与此类似,点击“范冰冰”后所展示的结果都是和电影《苹果》相关的结果,这说明本方法聚类是有效的。并且,本系统对于给定关键词后信息结果类别的判断采用的是完全匹配的方法,所以不会出现模糊算法所导致的结果归类错误的情况。理论上,本系统会出现结果遗漏,即有结果应属某个类别但是却未被该类别收录,这依赖于用户输入检索关键词的可靠性。假定通过大数量用户的搜索行为所获得的用户输入是可靠的,即有效信息大过于噪音,则结果聚类遗漏对用户搜索体验不会有影响。

各关键词的聚类结果如表1所示。

(1)从表1可以看出所有分类的数目加和大于去冗后的结果数,这是因为对于同一条结果,会含有多个关键词,因此会被归入不同的类别。考虑到实际系统运行时的效率,本原型系统选择成员搜索引擎所提供的结果摘要作为分析的依据,而不是分析全文。如果采用分析全文的方法,可以预见的是各个分类中的结果数目会有一定幅度的上升。

表1 实验聚类结果

(2)注意到“手机”聚类结果中有“苹果”一个组别标示,但是在装填“手机”关键词的时候并没有将“苹果”作为装填词。这是因为原型系统运行初期装填“苹果”时,“手机”曾作为一个有效类别进行装填而带来副作用。随着用户对该类别的忽略,执行第3节中过程(1)的规则④排查相关关键词的上下义相关度后,“苹果”作为“手机”类别将不会存在。这从反面说明本文方法所基于的假设(2)是合理的,“手机”可以作为“苹果”关键词的有效聚类标示,但是“苹果”作为“手机”关键词的聚类标示不一定是有效的,即相关关键词间存在上下义关系。

可以看到,该原型实现本文方法所得到的结果具有明显优势,且系统模拟运行初期所进行的知识装填是比照Google和百度的搜索提示来进行的,这样的聚类结果对比现有的搜索结果,证明该框架和方法可行有效,实现了预期效果。

5 结 语

基于将用户纳入搜索体系的想法,本文提出了一个改进的元搜索引擎系统框架和一个基于用户行为学习的结果聚类方法,并对其进行了详细的描述。原型系统运行实例证明了改进的系统框架结合基于用户行为学习的结果聚类方法是可行的,通过对用户行为的学习产生了有效的结果聚类标示并据此标示将结果进行了有效的聚类,同时实现了动态调整,提高了搜索结果的可浏览性。

受限于实验条件,该系统没有在多用户高负荷的条件下运行检测,以期达到最优的动态平衡状态。同时,如何更好地处理检索关键词的上下层次关系和如何标准化不同用户输入导致的聚类标示繁杂有待进一步研究。

参考文献
[1] 钱功伟, 倪林, 田甜, 等. 带聚类处理的元搜索引擎的设计与实现[J]. 计算机工程与应用, 2007, 43(22): 182-185. [本文引用:2]
[2] Valdéz-Pérez R E, Pereira F. Concise, Intelligible, and Approximate Profiling of Multiple Classes[J]. International Journal of Human-Computer System, 2000, 53(3): 411-436. [本文引用:1]
[3] Zeng H J, He Q C, Chen Z, et al. Learning to Cluster Web Search Results[C]. In: Proceedings of the 27th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, Sheffield, United Kingdom. New York, NY, USA: ACM, 2004: 210-217. [本文引用:1]
[4] 彭喜化, 张林, 余建桥. 基于Agent的元搜索引擎结果优化技术[J]. 计算机应用, 2003, 23(12): 68-69, 72. [本文引用:1]
[5] 刘炜, 陈俊杰. 一种基于Agent的智能元搜索引擎框架[J]. 计算机工程与应用, 2005, 41(3): 137-138, 211. [本文引用:1]
[6] 陈俊杰, 薛云, 宋翰涛, 等. 基于Agent的元搜索引擎的研究与设计[J]. 计算机工程与应用, 2003, 39(10): 33-36. [本文引用:1]
[7] 王浩鸣, 张曰贤, 吴志军, 等. 基于智能Agent的中文元搜索引擎模型研究[J]. 计算机工程与应用, 2005, 41(31): 154-156, 204. [本文引用:1]
[8] 徐科, 黄国景, 崔志明. 元搜索引擎中基于用户兴趣的个性化调度模型[J]. 清华大学学报: 自然科学版, 2005, 45(9): 1915-1919. [本文引用:1]
[9] 王津涛, 兰皓. 面向主题元搜索引擎的设计与实现[J]. 计算机工程, 2005, 31(7): 168-169, 173. [本文引用:1]
[10] 李四明, 陶兰, 王保迎. 面向智能Agent的元搜索引擎的设计与实现[J]. 计算机工程, 2004, 30(5): 147-149. [本文引用:1]
[11] 刘丽, 孙燕唐. 智能型元搜索引擎的设计与实现[J]. 计算机工程, 2003, 29(6): 118-121. [本文引用:1]