（计算机应用技术专业论文）元搜索引擎结果聚类优化的研究与实现.pdf

元搜索引擎结果聚类优化的研究与实现 中文摘要 中文摘要 在网络应用服务发展的今天，信息获取已成为网民使用i n t e m e t 的主要目的之 一。由于传统搜索引擎存在不足及自身的局限性，限制了人们对资源的获取。为提 高用户查询信息的覆盖面和检索结果的准确性，一种建立在搜索引擎之上的元搜索 引擎成为目前研究与开发的热点。但现存的大多数元搜索引擎以线性列表的方式为 用户返回检索结果，其规模仍相当庞大，这使得用户可能用很多时间才能找到自己 需要的结果。产生上述问题的主要原因是没有对检索结果进行分类处理和按照人们 的查询习惯及检索经验进行再组织。因此，对检索结果进行聚类处理成为提高用户 查找速度和快速定位所需信息的一个有效解决方案。 本文通过对元搜索引擎技术和数据挖掘技术研究的基础上，结合关联规则与聚 类分析设计并实现了一个带聚类处理的元搜索引擎系统c m e s ( t h ec l u s t e r i n gm e t a s e a r c he n g i n e ) ，详细介绍了该系统的具体实现。 通过建立搜索引擎参数库，实现了检索请求向目的搜索引擎查询指令的转换， 并实现了对目的搜索引擎返回的结果页面相关内容的自动提取；将结果记录中的标 题和摘要进行分词处理后提取主要关键词集，用于建立关联词矩阵以及基于布尔函 数和t f i d f 函数表示结果特征向量，并对这两种表示方法在不同聚类算法下进行对 比测试与分析；分别以k - m e a n s 和f c m 算法为基础提出基于关联词矩阵的 k - m e a n s ( k m e a n s 和结果聚类优化方案，并对它们进行对 比测试与分析，选a 择w 其m 中) 较f 好c 者m 用( f c 于m 检a 索w 结m 果) 聚类；给出了系统的应用实例并对系 统的性能进行了分析；最后对本文所做的工作进行了总结，并提出系统需要进一步 完善的地方及下一步研究工作的方向。 关键字：元搜索引擎；关联规则；聚类；数据挖掘；关联词矩阵 作者：王琼 指导老师：徐汀荣 a b s t r a c tr e s e a r c ha n di m p l e m e n t a t i o no nr e s u l t sc l u s t e r i n go p t i m i z a t i o no fm e t as e a r c he n g i n e a b s t r a c t n o w a d a y s ，、 ，i t l l t h ed e v e l o p m e n to fa p p l i c a t i o ns e r v i c ei nn e t w o r k ，i n f o r m a t i o n r e t r i e v a lh a sb e c o m eo n eo ft h em a i np u r p o s e so fn e t i z e n su s ei n t e m e ts e r v i c e b e c a u s et h e t r a d i t i o n a ls e a r c he n g i n eh a ss o m es h o r t c o m i n g sa n di t so w n l i m i t a t i o n s ，r e s t r i c t i n gu s e rt o o b t a i nt h er e s o u r c e s t oi m p r o v et h ec o v e r a g eo fu s e rs e a r c hi n f o r m a t i o na n dt h ea c c u r a c y o ft h es e a r c hr e s u l t s ，p e o p l es t a r tt op a ys p e c i a la t t e n t i o nt om e t as e a r c he n g i n eb a s e do n s e a r c he n g i n e b u tn o wm o s to ft h e mp r e s e n tt h es e a r c hr e s u l t st ot h ee n du s e r 、柝t l ll i n e a r l i s t , a st h e r ea r et h o u s a n d so ft h es e a r c hr e s u l t s ，i tm a k eu s e rs p e n dm u c ht i m et of i n dw h a t t h e yr e a l l yw a n t t h em a i nr e a s o ni st h a tt h es e a r c hr e s u l t sa r e a tc l a s s i f i e da n dr e f r a m e d a c c o r d i n gt ou s e r sq u e r yc u s t o ma n dr e t r i e v a le x p e r i e n c e a c c o r d i n g l y , c l u s t e r i n gt h e s e a r c hr e s u l t si so n ee f f i c i e n ts o l u t i o nt oi m p r o v et h el o o k u ps p e e da n df a s tl o c a t et h e r e q u i r e di n f o r m a t i o n t h et h e s i sd e s i g n sa n di m p l e m e n t sam e t as e a r c he n g i n es y s t e mw i t l lc l u s t e r i n g c a l l e dc m e s ( t h ec l u s t e r i n gm e t as e a r c he n g i n e ) c o m b i n i n gw i t l la s s o c i a t i o nr u l e sa n d c l u s t e r i n ga n a l y s i sb yr e s e a r c h i n go nm e t as e a r c he n g i n et e c h n i q u ea n dd a t am i n i n g t e c h n i q u e ，a n di ti l l u s t r a t e st h es p e c i f i ci m p l e m e n t a t i o ni nd e t a i l b u i l d i n gu ps e a r c he n g i n ep a r a m e t e rd a t a b a s er e a l i z e st h et r a n s f o r mf r o mr e t r i e v a l r e q u e s t st ot a r g e ts e a r c ho r d e r sa n dt h ea u t o m a t i ce x t r a c to fr e l a t e dc o n t e n t s ，t h e nt h e s y s t e me x t r a c t st h em a i nk e y w o r ds e t sa f t e rs e g m e n t i n gt h es u b j e c ta n da b s t r a c to ft h e s e a r c hr e s u l t st ob u i l du paa w m ( a s s o c i a t e dw o r dm a t r i x ) a n de x p r e s st h er e s u l tf e a t u r e v e c t o rb a s e do nb o o l e a nf u n c t i o na n dt f i d ff u n c t i o n ，t h e nt e s t i n ga n da n a l y z i n gt h et w o v e c t o r su n d e rt h ed i f f e r e n tc l u s t e r i n ga r i t h m e t i c s b a s i n go nk - m e a n sa n df c ma r i t h m e t i c ， t h et h e s i sp r e s e n t sk m e a n sa n df c m o p t i m i z i n gm e t h o d so fr e s u l t sc l u s t e r i n gb a s e do nt h e a w m ( k - m e a n s _ a w ma n df c m _ a w m ) ，t h e nt e s t i n ga n da n a l y z i n gt h e m a f t e r w a r di t c h o o s e sb e t t e ro n et oc l u s t e r i n gt h es e a r c hr e s u l t s i tg i v e ss o m ep r a c t i c a le x a m p l e sa n d a n a l y z e st h ep e r f o r m a n c eo ft h es y s t e m f i n a l l y ，i ts u m m a r i z e st h ep r e s e n ts t u d ya n d s u g g e s t st h es y s t e ms h o u l db ef u r t h e ri m p r o v e d ，a l s oi tg i v e sad i r e c t i o nf o rf u r t h e rs t u d y k e y w o r d s ：m e t as e a r c he n g i n e ；a s s o c i a t i o nr u l e s ；c l u s t e r i n g ；d a t am i n i n g ；a w m i i w r i t t e nb y ：w a n gq i o n g s u p e r v i s e db y ：x ut i n g r o n g 图表目录 图2 1 一般元搜索引擎总体框架7 图2 2k - m e a n s 算法16 图2 3f c m 算法17 图3 1 构建关联词矩阵2 2 图3 2k m e a n sa w m 算法2 7 图3 3f c ma w m 算法2 8 图3 - 4k m e a n s b e a n 类的u m l 图3 0 图3 5f c m b e a n 类的u m l 图3 1 图3 - 6t f i d f b e 锄类的u m l 图3 2 图3 7 不同参数取值在k - m e a n sa w m 下的平均迭代次数比较。3 3 图3 8 不同参数取值在k m e a n sa w m 下的平均错误函数比较。3 3 图3 - 9 不同参数取值在f c ma w m 下的平均迭代次数比较3 4 图3 1 0 不同参数取值在f c ma w m 下的平均聚类有效性比较3 4 图3 1 l 不同结果特征向量在k m e a n sa w m 下的平均迭代次数比较3 5 图3 1 2 不同结果特征向量在k - m e a n sa w m 下的平均错误函数比较p 3 6 图3 1 3 不同结果特征向量在f c ma w m 下的平均迭代次数比较3 7 图3 1 4 不同结果特征向量在f c ma w m 下的平均聚类有效性比较3 7 图3 1 5 不同距离与相似系数公式在k - m e a n sa w m 下的平均迭代次数比较3 8 图3 1 6 不同距离与相似系数公式在f c ma w m 下的平均迭代次数比较，3 9 图3 1 7 不同距离与相似系数公式在k - m e a n sa w m 下的平均错误函数比较3 9 图3 1 8 不同距离与相似系数公式在f c ma w m 下的平均聚类有效性比较4 0 图4 1c m e s 系统总体框架4 2 图4 2 乱码页面4 6 图4 3 查询请求转换及转发4 7 图4 4 百度中搜索“韩寒”返回的一条记录4 8 图4 5 提取结果记录。4 9 图4 6 提取主要关键词集5 0 图4 7 构造关联词矩阵51 图4 - 8 结果特征向量表示5 1 图4 9 检索结果聚类5 1 图4 - 10j d b c - o d b cb r i d g e 5 3 图4 11j d b cn a t i v eb r i d g e 5 4 图4 1 2j d b c - n e t w o r kb r i d g e 5 4 图z i 1 3p u r ej a v aj d b cd r i v e 5 4 图5 1m v c 模式5 5 图5 2s t r u t s i 1 的处理流程图5 6 图5 3s e a r c h e n g i n e 类的u m l 图5 9 图5 4r e c o r d 类的u m l 图6 0 图5 5c h a i n 类的u m l 图6 2 图5 - 6r e c o r d p r e t r e a t b e a n 类的u m l 图6 3 图5 7t f i d ff c m b e a n 类的u m l 图6 3 图5 8c m e s 查询界面6 5 图5 - 9c m e s 搜索“手机”的返回页面6 5 图5 1 0 经再搜索“手机 后的返回页面6 6 图5 1 1s e e k l e 搜索“手机”的返回页面6 7 图5 1 2 成员搜索引擎与c m e s 的平均相对查全率比较分析6 8 表1 1 四大中文搜索引擎检索情况2 表2 1 不同元搜索引擎之间性能比较1 0 表2 2 三类聚类有效性的总体比较18 表3 1 不同搜索关键词返回的结果记录及分词情况汇总3 0 表3 2k m e a n s b e a n 类的属性方法及其说明3 1 表3 3f c m b e a n 类的部分属性方法及其说明3 2 表3 - 4t f i d f b e a n 类的方法及其说明一3 2 表4 1 搜索“韩寒”时返回结果页面的第一页u r l 4 5 表4 2 搜索“韩寒时返回结果页面的第二页u r l 4 5 表4 3 不同搜索引擎的检索请求分析汇总。4 6 表4 4 百度的结果页面参数标识4 9 表4 5 搜索引擎查询参数特征表5 2 表4 6 搜索引擎结果参数特征表5 2 表5 1d b c o n n e c t i o n b e a n 类的方法及其说明5 8 表5 2s e a r c h e n g i b e 类的属性及其说明6 0 表5 3c h a i n 类的属性方法及其说明_ 6 2 表5 - 4r e c o r d p r e t r e a t b e a n 类的方法及其说明6 3 表5 5t f i d ff c m b e a n 类属性方法及其说明6 4 表5 - 6 不同元搜索引擎与c m e s 性能比较6 7 苏卅l 大学学位论文独创性声明及使用授权的声明 学位论文独创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进 行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不含 其他个人或集体己经发表或撰写过的研究成果，也不含为获得苏州大学 或其它教育机构的学位证书而使用过的材料。对本文的研究作出重要贡 献的个人和集体，均已在文中以明确方式标明。本人承担本声明的法律 责任。 研究生签名：童4 廷日期： 塑星：生! 翌 学位论文使用授权声明 苏州大学、中国科学技术信息研究所、国家图书馆、清华大学论文 合作部、中国社科院文献信息情报中心有权保留本人所送交学位论文的 复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本 人电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文 外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分 内容。论文的公布( 包括刊登 授权苏州大学学位办办理。 研究生签名： 壶望塾 日期： 壁垒：笙：! 导师签名： 元搜索引擎结果聚类优化的研究与实现第一章绪论 第一章绪论 本章主要介绍论文的研究背景及元搜索引擎在国内外的研究现状，通过对比了解 到国内元搜索引擎与国外的相比还存在一定的差距，在分析现有技术不足的基础上旨 在说明本文研究的意义和主要工作，最后给出本文的组织结构。 1 1 论文研究背景 自上个世纪9 0 年代以来，互联网得到了迅猛发展，其功能不断扩展，已成为当 今世界人们获取所需资源和信息交流的主要场所。然而，由于网络中浩如烟海的信息 具有内容庞杂、结构异样、组织松散等特点，也使得人们面临着“信息爆炸而知识匮 乏的问题。因此，对于上网查找信息的用户来说，需要一种功能更先进、效率更高 的信息检索工具显得极其重要。而搜索引擎的出现极大地提高了人们收集和定位信息 的能力，它是一种利用网络自动搜索技术，通过收集众多的网络站点来提供全局性网 络资源控制与检索机制，从而帮助用户方便快捷地在网络中寻找到自己所需的信息， 已成为互联网上不可或缺的工具和基础应用之一。 截至2 0 0 7 年1 2 月，根据第2 1 次中国互联网络发展状况统计调查显示【l 】，中国 网民数增长迅速，已增至2 1 亿，位于世界第二位。其中这2 1 亿网民中使用搜索引 擎的比例是7 2 4 ，位列网络应用中网络音乐、即时通信、网络影视和网络新闻之后 的第5 位，而高于电子邮件。在中国这样一个网民快速增长和以年轻网民主导的国家， 搜索引擎用户将会继续增长。近年来，在i n t e m e t 上出现了许多方便和帮助用户查找 所需信息的搜索引擎1 2 ，为人们提供i n t e m e t 信息导航服务，如l y c o s 、y a h o o 、 a l t a v i s t a 、e x c i t e 、g o o g l e 、百度、中搜、有道等。 不容置疑，这些搜索引擎在为人们的信息检索请求时提供了极大的帮助，大大提 高了用户的检索效率。然而伴随着网络信息量的爆炸式增加，各种搜索引擎使用的检 索方式日益复杂，所采用的算法及其数据库的覆盖范围存在许多差异，它们在信息维 护、信息重复、网络及站点负载等方面暴露出越来越多的缺陷，使其检索能力受到越 来越严峻的考验。事实上，没有一个搜索引擎能1 0 0 的涉及整个i n t e m e t 资源。据 清华大学i t 可用性实验室【3 】于2 0 0 5 年9 月再次对中文搜索引擎进行了较为全面的对 比研究后发现，具有中文网页样本覆盖率最高的百度只有3 2 5 3 的网络资源覆盖率。 第一章绪论元搜索引擎结果聚类优化的研究与实现 同时，不同搜索引擎的检索结果的重复率仅仅在1 0 3 0 之间，这样导致同一个检索 请求在不同搜索引擎中获得的查询结果的重复率较低。因此，通常当一个搜索引擎不 能找到用户需要的所有信息时，用户需要在多个搜索引擎之间进行切换，并且可能花 费很多时间才能找到所需结果。此外，对于一个普通的查询，搜索引擎往往返回成千 上万项的检索结果，并按照与查询请求的相关性从高到低排列成一个较长的有序列 表。如表1 1 为在四个国内知名的中文搜索引擎( 即百度、g o o g l e 、搜狗、中搜) 中分 别输入关键词“韩寒 、“q q ”、“超级女声、“武林外传”及“m p 3 ”后所检索到的 结果记录条数，它们中部分结果标题的超链接无效且不相关信息所占的比例高达7 5 以上【4 】。用户想从中找到自己真正需要的信息如同大海捞针一样困难，若再加上用户 缺乏搜索领域知识，则情况会更糟。 表1 1 四大中文搜索引擎检索情况 懒敞- l 3 ： 韩寒、q q 超级女生 武林外传 m p 3 接索关键词 百度 7 ，6 4 0 ，0 0 09 1 ，4 0 0 ，0 0 0 3 ，8 4 0 ，0 0 0 2 6 ，5 0 0 ，0 0 0 10 0 ，0 0 0 ，0 0 0 g o o g l e 2 9 0 ，0 0 07 2 5 ，0 0 0 ，0 0 03 2 2 ，0 0 05 1 6 ，0 0 01 , 4 7 0 ，0 0 0 ，0 0 0 搜狗 15 ，3 5 7 ，0 2 23 31 ，3 9 0 ，8 2 4 8 , 6 9 6 ，1 2 16 1 ，3 6 9 ，2 6 24 3 0 ，4 5 0 ，3 4 5 中搜 4 ，1 5 0 ，0 0 0 10 0 ，0 0 0 ，0 0 0 3 , 3 0 0 ，0 0 03 , 2 6 0 ，0 0 05 5 ，4 0 0 ，0 0 0 然而，用户有时并不十分关注返回检索结果的多少，而是看检索结果是否满足自 己的需求，他们一般只挑选列表中最前面的几十条结果进行查看。传统搜索引擎存在 的不足之处及自身的局限性，限制了人们对资源的获取。鉴于上述原因，一个能集成 多个搜索引擎的检索结果并能对其进行再处理的检索工具一一元搜索引擎( m e t a s e a r c he n g i n e ) 出现了【5 1 。 自1 9 9 5 年世界上第一个元搜索引擎m e t a c r a w l e r 4 】被推出以来，这一新型的网络 搜索工具异军突起、发展迅速。与传统搜索引擎相比，元搜索引擎以其丰富的资源、 相对全面、准确的搜索结果等优点受到用户的青睐，已渐渐成为一种不可或缺的极具 潜力的新型网络搜索工具。然而，现存的大多数元搜索引擎以线性列表的方式为用户 返回检索结果，其规模仍相当庞大，而用户又通常缺乏足够的耐心、精力和时间去遍 历所有的命中文档，使得最终结果不尽人意。产生上述问题的主要原因是没有对检索 结果进行分类处理和按照人们的查询习惯及检索经验进行再组织。因此，对检索结果 进行聚类处理成为提高用户搜索行为和快速定位所需信息的一个有效解决方案。 2 元搜索引擎结果聚类优化的研究与实现 第一章绪论 1 2 国内外研究现状 元搜索引擎建立在多个现有的搜索引擎之上，提供对这些搜索引擎进行统一访问 的服务，其特点是用户只需递交一次查询请求，由它将检索结果统一处理，并以统一 的格式提供给用户。因此，元搜索引擎不需要对所有文件的索引进行维护，也不需要 拥有庞大的网页数据库，其主要精力集中在提高搜索速度、优化检索结果和增强用户 查询界面的友好性上等方面。尤其是在结果合成方面，现有的绝大多数元搜索引擎所 采用的结果合成方法主要有以下几种：( 1 ) 直接结果合并法；( 2 ) 将响应速度最快的成 员搜索引擎的检索结果优先返回；( 3 ) 相关度排序法( 主要包括摘要排序法、位置排序 法、摘要位置排序法) 1 6 j 。 然而，随着数据挖掘技术的广泛应用，为了方便用户尽快地发现自己真正需要的 资源，以聚类的描述思想替代传统采用的数据全部被罗列技术，自动组织来自目的搜 索引擎返回的部分检索结果，聚类研究已被广泛地运用到元搜索引擎中r 卜1 1 】。对检索 结果进行有效地聚类将有利于用户更容易地在检索结果中浏览与查找、更容易地以合 适的新关键词来细化搜索，进而使每次检索结果得到充分地展示与利用【1 2 1 。 目前，国内外对检索结果的聚类研究已有了一定的基础【1 3 1 ，不少研究者投身于该 方面的研究并取得了显著的成果。国外将聚类技术引入搜索引擎的开发应用较早，最 早尝试对搜索结果进行聚类的系统是s c a t t e r g a t h 一1 4 】，它主要使用对大文本集合进行 聚类的算法，将文档组织到一组类中，每个类有一个主题，相关的文档被归入到对应 的主题中。该系统比传统的搜索结果线性陈列具有更友好的用户界面，能够提高用户 的查询效率。s n a k e t ”】是第一个完整地实现了搜索结果聚类各项功能的系统，向用 户提供了可读性很好的标签、层次型结构的类别组织和良好的交互响应。g r o u p e r 1 6 j 是第一个特别为搜索结果聚类而设计的后检索( p o s t r e t r i e v a l ) 系统，也是第一个针对文 档摘要而不是文档本身进行聚类的系统。该系统使用后缀树聚类( s t c ，s u f f i xt r e e c l u s t e r i n g ) 算法，将具有共同短语的文档归到一类中，因此在对文档本身和文档摘要 进行聚类时都表现出了良好的性能。v i v i s i m o 1 7 】是一个具有自动对检索结果进行聚类 功能的元搜索引擎，其基本原理是将所有的类别成对地进行比较，找出能够将每一对 类别区分开来的特征，然后对那些特征进行组织，形成最后的描述。s h o c 1 8 】是用来 处理中文查询的搜索结果聚类系统，它利用后缀数组( s u f f i xa r r a y ) 进行关键短语的发 现，并采用s v d ( s i n g u l a rv a l u ed e c o m p o s i t i o n ) 方法来发现短语之间的语义，进而获得 第一章绪论 元搜索引擎结果聚类优化的研究与实现 层次型分类的结果。l i n g o t l 9 j 提出了先确定类名再将文档归类的方法，也使用t s v d 方法来寻找类的标签，然后再使用类似分类的方法将文档与标签联系起来，这样能够 降低文档出现在无关类别中的可能性，能够为用户呈现描述性更好的标签以及更精确 的类别。s e r g i o 2 0 1 提出一个元搜索引擎，将收集到的来自两个目的搜索引擎的n 个结 果页面保存在数据库中，并对它们提取特征后利用改进的k m e i l i i s 进行聚类处理。 w h a t s o n w e b 2 q 是利用拓扑驱动( t o p o l o g y - d r i v e n ) 方法设计的元搜索引擎聚类系统，采 用经典的图聚类算法( g r a p h c l u s t e r i n ga l g o r i t h m s ) 获得类别与其相关标签的计算量，该 系统采用图形可视化技术支持用户处理无意义的标签，改善了传统文本层次聚类的描 述策略。n e s r e c t 2 2 l 是专门用于新闻检索的元搜索引擎结果聚类系统，它执行用户的 查询请求并收集来i 刍a l t a v i s t a 新闻搜索引擎返回的新闻摘要，并能在较短的时间内实 现基于新闻主题的内容层次聚类，为用户提供基于新闻摘要的标签。 国内在元搜索引擎中引入聚类技术的研究起步较晚，该类元搜索引擎为数不多， 如b b m a o ( 比比猫) 田】是国内最典型的聚类元搜索引擎之一，在它的检索结果页面左侧 呈现聚类结果的类别标签，这样能有效地帮助用户关注所需的信息类别而不用为不相 关的结果浪费时间。w a n g 2 4 基于f c m ( f u z 巧c o g n i t i v em a p ) 算法提出将文档划分到一 系列预先确定的类中，其中f c m 能实现文档的关键词之间的语义关系。p i n k y s e a r c h 2 5 】 是一个基于聚类的元搜索引擎，它能同时调用5 个独立的搜索引擎，并且可以对检索 结果使用后缀树聚类算法及相同词聚类( s w ) 算法进行聚类处理。董晨【2 6 】针对现有搜 索引擎召回率和准确率低的情况，提出了一种基于改进后的模糊聚类算法 g v f c m d d ( v a r i e df u z z y cm e d i o db a s e do ng e n e r a t i o n ) 的个性化智能搜索引擎方案。 该算法利用遗传算法能够得到全局最优解的特点来优化f c m d d 算法对初始中心点敏 感的缺点，并且由遗传算法得到模糊聚类块数c ，从而得到更加优化的聚类结果。张 伟【2 7 】提出了一种基于遗传算法的聚类新方法m g a ( am o d i f i e dg e n e t i ca l g o r i t h m ) ，该 方法通用性强，并且能够有效地提高数据挖掘的效率和质量。i c c l 2 9 】是一个交互式中 文检索结果聚类系统，为用户的交互响应和个性化设置提供较好的可视化搜索页面， 以更紧凑和专题的形式方便用户浏览中文页面。同时，用户可以选择与其查询意义最 匹配的聚类，或者对查询请求做进一步地精炼。 目前，英文元搜索引擎发展较快，而中文元搜索引擎发展较缓慢，与之相比还存 在较大差距。因此，如何借鉴英文元搜索引擎的技术和经验来发展中文元搜索引擎就 显得尤为迫切和重要。 4 元搜索引擎结果聚类优化的研究与实现 第一章绪论 1 3 本文的研究意义和主要工作 与传统搜索引擎相比，元搜索引擎的出现能在一定程度上提高用户查询信息的覆 盖面，也能在一定范围内提高检索结果的准确性，但在面对检索结果的排序上却存在 一定的局限性：( 1 ) f l j 于不同的搜索引擎之间存在收集信息的数量及范围、采用的索 引方法、使用的相似度评价等方面的巨大差异；( 2 ) 元搜索引擎的设计者不能获取这 些搜索引擎的很多技术细节，有时又不能正确地认识到用户的查询习惯和搜索经验， 导致最终返回的结果没能从真正意义上满足用户的查询需求；( 3 ) 从现有的大多数元 搜索引擎提供的结果显示方式上分析，传统的线性列表式罗列技术存在许多不足之 处，因此在一定程度上不能满足目前大多数用户对信息资源的获取。 鉴于上述原因，在探索如何将数据挖掘技术领域的知识应用到搜索引擎技术领域 中的同时，本文通过对元搜索引擎技术和数据挖掘技术研究的基础上，结合关联规则 与聚类分析设计并实现了一个带聚类处理的元搜索引擎系统c m e s ( t h ec l u s t e r i n g m e t as e a r c he n g i n e ) ，该系统能实现对检索结果进行有效地聚类，旨在帮助用户能快 速地定位所需信息和提高其满意度。本文主要完成以下几个方面的工作： 1 分析现有的元搜索引擎技术和文档信息处理技术。 2 分析现有的数据挖掘技术，即聚类分析和关联规则。 3 基于t f i d f 函数表示结果特征向量，并通过相关测试确定该向量中参数的取 值，进而与基于布尔函数的结果特征向量作比较。 4 结合关联规则构造关联词矩阵，并基于该矩阵提出了一个计算分类对象与聚 类中心的距离公式，通过对不同聚类算法和不同距离与相似系数计算公式的 对比测试，实现基于关联词矩阵的元搜索引擎结果聚类优化。 5 设计与实现了带聚类处理的元搜索引擎系统c m e s ，并对其性能进行分析。 1 4 本文的组织结构 本文共包括六章，各章的主要内容如下： 第一章绪论。简要介绍研究背景，说明在信息爆炸性增长的时代，传统搜索引擎 在检索结果上存在的不足及自身的局限性，指明了研究元搜索引擎的重要性和本文的 研究意义，最后介绍了本文的主要工作及组织结构。 第二章元搜索引擎概述及相关知识。首先简要介绍元搜索引擎技术及其相关知 5 第一章绪论元搜索引擎结果聚类优化的研究与实现 识，包括元搜索引擎的分类、工作原理等；其次简要介绍文档信息处理技术，包括中 文分词、文档表示模型及其常用的表示方法，重点介绍了向量空间模型；最后简要介 绍聚类分析技术及其主要分类，重点介绍k 均值( k m e a n s ) 算法和基于目标函数的模糊 c 均值聚类( f c m ) 算法，并给出判断f c m 有效性的主要方法。 第三章基于a w m 的结果聚类优化。首先详细介绍如何构建关联词矩阵( a w m ， a s s o c i a t e dw o r dm a t r i x ) ，并基于a w m 提出计算分类对象与聚类中心的距离公式；其 次简要介绍基于布尔函数和t f i d f 函数的结果特征向量表示，并提出两个基于a w m 的结果聚类优化过程，即k m e a n s a w m 和f c ma w m ，并对它们进行相关测试及 分析，从而为c m e s 选择最佳聚类方案提供主要依据。 第四章元搜索引擎c m e s 的设计。简要介绍c m e s 总体框架及其主要模块的功 能，详细分析了各模块的关键技术并给出相应的设计方案，最后介绍数据库设计方面 的相关知识及内容，重点介绍了有关搜索引擎参数库方面的设计。 第五章c m e s 的实现及系统性能测试与分析。简要介绍c m e s 实现框架，详细 阐述了系统中各模块的主要实现过程，并具体给出了各模块的主要类的u m l 图及关 键代码段。接着详细介绍系统应用过程中的主要运行界面，并在一定范围内将其性能 与其他中文元搜索引擎，以及其成员搜索引擎之间进行比较与分析。 第六章总结与展望。总结本文所做的主要工作，并讨论了系统需要进一步完善的 地方及进一步研究工作的方向。 6 元搜索引擎结果聚类优化的研究与实现 第二章元搜索引擎概述及相关知识 第二章元搜索引擎概述及相关知识 本章首先主要介绍元搜索引擎技术及其相关知识，包括元搜索引擎的分类、工作 原理，以及它与传统搜索引擎相比所带来的优势，并给出了一般情况下评价一个元搜 索引擎的主要指标；其次简要介绍文档信息处理技术，包括中文分词、文档表示模型 及其常用的表示方法，重点介绍了向量空间模型；最后简要介绍聚类分析技术及其主 要分类，重点介绍k 均值( k m e a n s ) 算法和基于目标函数的模糊c 均值聚类( f c m ) 算法， 并给出判断f c m 有效性的主要方法。 2 1 元搜索引擎技术 元搜索引擎是一种调用其它独立搜索引擎的引擎，也被称为“搜索引擎之母 。 它是用户同时使用多个搜索引擎进行网络检索的中介，而被调用的独立搜索引擎称为 目的搜索引擎或成员搜索引擎。元搜索引擎通过整合、调用及优化利用等操作对多个 独立搜索引擎进行控制。 2 1 1 元搜索引擎的工作原理 元搜索引擎通过调用下层多个搜索引擎提供的服务从而向用户提供统一的检索 服务，与独立搜索引擎相比，它无需维护庞大的索引数据库，也不需要设计和实施网 络蜘蛛程序去采集网页。一般来说，元搜索引擎主要由三部分组成 2 9 1 ，如图2 1 所示， 包括请求提交代理、检索接口代理及结果显示代理。 l 查询请求卜1 1 i 上? i 结果显示ll _ 丽 。i ；享七坦而f p ：1 1 1= 喟水凭x 1 毪r 卜知识库 结果显示代理 上 一 一 检索接口代理 上 广j 互联网、搜索引擎索引；。、； 、h 一j 一 图2 - 1 一般元搜索引擎总体框架 “请求提交代理 接收来自用户的查询请求，负责实现用户的“个性化检索设 置要求，包括调用哪些搜索引擎、检索时间限制、结果数量限制等；“检索接口代理 7 第二章元搜索引擎概述及相关知识元搜索引擎结果聚类优化的研究与实现 负责将用户的查询请求“翻译成满足不同目的搜索引擎要求的格式并转发；“结果 显示接口 负责收集来自所有源搜索引擎的检索结果，并实施去重、去死链接等操作， 最后采用特定的排序算法将结果合并后输出到用户端。 2 1 2 元搜索引擎的分类 元搜索引擎具有多种分类方式【2 9 , 3 0 1 ，可以根据用户的使用模式或调用独立搜索引 擎的方式等进行分类。一般情况下，元搜索引擎按功能划分如下： 1 集成搜索引擎( a 1 1 i n o n es e a r c hp a g e ) 。也称为“多引擎同步检索系统 ，它 没有统一的全局外部模式，而是在一个w e b 页面上链接若干种独立的搜索引 擎，并且对检索结果也不做处理，直接将来自多个搜索引擎的检索结果排列 在一个页面上。例如搜星、搜索之家、p r o t e u s 、q u e r y s t e r 等都属于该类范畴。 2 多线索式元搜索引擎。它是一种具有实现检索指令转换功能，利用统一的检 索界面，实现对多个独立搜索引擎的索引数据库进行检索，并将检索结果以 统一格式显示的网络检索工具。该类元搜索引擎的典型代表有万纬搜索、 m e t a f i s h e r 、m e t a c r a w l e r 、d o g p i l e 等。 3 桌面型元搜索引擎。以程序的方式提供给用户，运行在用户的机器上，相当 于用户自己拥有一个元搜索引擎。它直接将用户的检索请求由用户端转发给 被调用的成员搜索引擎，并对返回的检索结果进行合成后以特定的方式显 示。该类元搜索引擎的典型代表有飓风搜索通、s e a r c h w o l f , b e e l i n e 等。 4 基于w e b 的元搜索引擎。以w e b 的方式为用户提供元搜索服务，用户的查 询请求经服务器的请求提交代理和检索接口代理将其分发到多个被调用的 独立搜索引擎，服务器端的结果显示代理将这些独立搜索引擎返回的检索结 果经处理后再返回给用户。多线索式元搜索引擎基本上都属于基于w e b 的元 搜索引擎，如万纬搜索、d a t a w a r e 、i x q u i c k 、d o g p i l e 、p r o f u s i o n 等。 2 1 3 元搜索引擎的优势 为解决传统搜索引擎所带来的种种局限而产生的元搜索引擎是建立在独立搜索 引擎基础之上，以全局外模式的方式接受来自用户的检索请求并给予结果显示。与独 立搜索引擎相比，元搜索引擎具有以下优点【冽： 1 信息的覆盖面更广。独立搜索引擎的索引数据库更新需要一定的周期，且搜 元搜索引擎结果聚类优化的研究与实现第二章元搜索引擎概述及相关知识 集的信息也各有一定的侧重点。由于元搜索引擎集成了来自多个独立搜索引 擎的检索结果，因此从一定程度上弥补了独立搜索引擎的缺陷，扩大了检索 范围，也使检索的结果更具全面性，查全率也相对有了较大提高。 2 提供统一的检索界面。用户无需了解各独立搜索引擎的语法结构、语义规则、 字符转换功能等方面，在使用时与一般通用的搜索引擎一样方便，只需一次 输入查询串，元搜索引擎将会整合来自不同独立搜索引擎的检索结果提供给 用户查看，避免了用户在不同独立搜索引擎之间切换所带来的麻烦。 3 检索结果更具可靠性和权威性。若相同的检索结果在多个独立搜索引擎中同 时出现，则说明该检索结果比较重要，因此可避免有些独立搜索引擎由于人 工干预而造成的排名缺陷，而使得检索结果的排序更加公正。有些元搜索引 擎还检查检索结果链接的存在性，从而保证了用户得到结果的可靠性。 4 具有容易被维护的优点。对元搜索引擎的管理者而言，只需要了解独立搜索 引擎的调用接口，无需建立庞大的索引数据库，省去了收集和存储网页、建 立和存储索引的工作，同时也省去了维护的代价。 若需要尽快查询到一个独特的术语或某个课题的概述，或者当使用其他独立搜索 引擎查询但得不到所需文件时，或者又当对其他搜索引擎不是很熟悉的情况下，为了 提高搜索效率和质量，可以选择使用元搜索引擎作为通向其他搜索引擎的工具。 2 1 4 元搜索引擎