（计算机应用技术专业论文）搜索引擎检索结果聚类方法的研究与改进.pdf

摘要 摘要 目前，现有的搜索引擎虽然采用各种方法来提高检索结果的精度，但 相关文档和不相关文档仍然相互混杂，给用户带来了负担。将搜索引擎返 回结果进行聚类，将其分成若干个簇，同一簇内文档相关度尽可能的大， 不同簇间文档相关度尽可能的小，这样将大大缩小用户所需浏览的结果数 量，从而缩短用户查询所需要的时间。 首先，本文在特征项的抽取过程中，在短语层次上采用词典识别与统 计方法相结合的方式，这样既可以识别常用词汇，又可以识别专业术语、 缩略语、临时用语、新出现的用语等等往往不会在词典之中的词汇。对索 引结构进行改进，文档的顺序表与倒排表共同作为索引，以使其更加适应 对搜索引擎返回结果的聚类。 其次，给出一个快速聚类算法h p m c 。在此方法中首先计算返回结果 之间的相似性，然后使用层次聚类法产生初始种子点，利用k - m e a n s 与 s i n g l ep a s s 相结合的算法进行聚类形成基类，通过合并基类最终得到聚类 结果。 最后，对h p m c 算法从时间复杂度、空间复杂度、聚类质量、聚类数 目的形成、对孤立点的敏感程度等几个指标做了评估，并与已有的算法进 行了比较。 关键词搜索引擎；检索结果；聚类；关键短语：簇 燕山大学工学硕士学位论文 a b s t r a c t t o d a y ，a l t h o u g hm a n ys e a r c he n g i n es y s t e m sh a v eb e e nt r y i n gt oi m p r o v e t h er e t r i e v a lp r e c i s i o n , t h er e t r i e v e dr e s u l t ss t i l li n c l u d eal o to fi r r e l e v a n c e d o c u m e n t sm i x i n gw i t l lt h er e l e v a n c eo n e s s ot h i sb r i n g st h ew e b1 1 $ d 1 sah u g e b u r d e n c l u s t e r i n go ft h er e t r i e v e dr e s u l t so fs e a r c he n g i n e ，t h eg r o u p sw h i c h a r ef o r m e ds h o u l dh a v eah i g hd e g r e eo fa s s o c i a t i o nb e t w e e nm e m b e r so ft h e s a m eg r o u p sa n dal o wd e g r e eb e t w e e nm e m b e r so fd i f f e r e n tg r o u p s s ot h e u s e r sc a l lv i e wt h e i ri n t e r e s t e dg r o u p sa n ds ot h a ti tw i l ls a v et h e mm u c ht i m e f i r s t l y ，t h i sp a p e rg i v e sa ne x a c t i n gd o c u m e n t f e a t u r em e t h o dt h a t d i c t i o n a r yi d e n t i f i c a t i o nw o r kt o g e t h e rw i t hs t a t i s t i c sb a s e do nk e y - p h r a s e ，i t c a l ln o to n l yf i n dn o r m a lk e y - p h r a s e ，b u ta l s oc a nf i n dp r o f e s s i o n a lt e r m s ， w o r d sf o rs h o r t ，t e m p o r a r yw o r d s ，n e ww o r d sa n ds oo nw h i c ha r en o ti nt h e d i c t i o n a r y t h es t r u c t u r eo fi n d e xi si m p r o v e d b yu s i n gt h es e q u e n c ei n d e x a n df i l e sm v e r t e di n d e xo ft h es n i p p c t st o g e t h e r ，i ti sm o r ea d a p t i v et ot h e c l u s t e ro f s n i p p e t so f s e a r c he n g i n e s e c o n d l y ，af a s t c l u s t e ra l g o r i t h m ，h p m c ，i sp r e s e n t e d t h es i m i l a r d e g r e e so fs n i p p e t sa r ec a l c u l a t e d ，t h e nt h ei n i t i a l i z e dc l u s t e rc e n t e ri sc r e a t e d b yu s i n gh i e r a r c h i c a lc l u s t e r i n gm e t h o d a na l g o r i t h mb a s e do nk m e a n sa n d s i n g l ep a s si sp r e s e n t e da n dg e t t i n gt h ef u n c t i o nc l u s t e r s a tl a s t t h ec l u s t e r r e s u l t sa l eg o tb yu n i t i n gf u n c t i o n a lc l u s t e r sp r o p e r l y l a s t i y ，t h ep e r f o r m a n c eo fh p m ci s e v a l u a t e df r o mt h ea s p e c t so f t e m p o r a lc o m p l e x i t y ，s p e c i a lc o m p l e x i t y ，c l u s t e rq u a l i t y ，c l u s t e rn u m b e r s ，t h e s e n s i t i v i t yd e g r e et os i n g l ep o i o ta n di sc o m p a r e dw i t ha l g o r i t h mb e f o r e k e y w o r d ss e a r c he n g i n e ；r e t r i e v e dr e s u l t ；c l u s t e r i n g ；k e y - p h r a s e ；c l u s t e r 燕山大学硕士学位论文原创性声明 本人郑重声明：此处所提交的硕士学位论文搜索引擎检索结果聚类 方法的研究与改进，是本人在导师指导下，在燕山大学攻读硕士学位期间 独立进行研究工作所取得的成果。据本人所知，论文中除己注明部分外不 包含他人己发表或撰写过的研究成果。对本文的研究工作做出重要贡献的 个人和集体，均已在文中以明确方式注明。本声明的法律结果将完全由本 人承担。 作者签字孝姥霍q 一。 v 一日期：研嗍日 燕山大学硕士学位论文使用授权书 搜索引擎检索结果聚类方法的研究与改进系本人在燕山大学攻读 硕士学位期间在导师指导下完成的硕士学位论文。本论文的研究成果归燕 山大学所有，本人如需发表将署名燕山大学为第一完成单位及相关人员。 本人完全了解燕山大学关于保存、使用学位论文的规定，同意学校保留并 向有关部门送交论文的复印件和电子版本，允许论文被查阅和借阅。本人 授权燕山大学，可以采用影印、缩印或其他复制手段保存论文，可以公布 论文的全部或部分内容。 保密口，在 本学位论文属于 不保密吼 ( 请在以上相应方框内打“” 作者签名： 导师签名： 夺端 、撅，哦 年解密后适用本授权书。 ) 日期：川年仍枷 日期唧年伽冲 第1 章绪论 1 1 研究背景与意义 第1 章绪论 万维( w o r l d w i d e w e b ，简称w w w 或w e b ) 是为广大用户交换或共享 信息而发展起来的一种因特网应用【l 】，万维网信息量一直在迅速增长。人 们上网的主要目的就是获取信息，然而由于网上信息的海量性、动态性与 非结构性，使万维网信息检索( w e bi n f o r m a t i o nr e t r i e v a l ) 成为一个重要而 又困难的问题。 搜索引擎( s e a r c he n g i n e ) ，如g o o g l e 等等，是目前万维网信息检索的主 要工具【2 】，大约8 5 的用户通过搜索引擎发现自己需要的万维网信息【3 1 。搜 索引擎一般用关键词建立索引，查询含有关键词的网页的盯l 。然而这些搜 索引擎还存在一定的局限性，并不能完全解决万维网信息检索的问题。 有许多因素导致搜索引擎还难以令人满意。首先，搜索引擎无法覆盖 全部万维网信息。实际上没有一个搜索引擎能够索引超过1 6 的万维网信 息，而且由于万维网的动态性，搜索引擎的索引中包含许多断连接和过时 网页，更加削弱了搜索引擎的作用。另外，搜索引擎的搜索结果缺乏清晰 明了的结构，也是令人感到不好用的一个重要原因。目前的搜索引擎一般 将找到的相关万维网信息按照与查询的相关度从高到低排成一个线性列 表。但是，一个查询得到的搜索结果往往包含成千上万的万维网信息，所 以搜索引擎最后产生的线性列表一般很长。虽然搜索引擎已经采用了各种 方法来提高搜索精度，但是搜索结果中仍然包含了大量与用户的查询无关 的信息，其比例高达7 5 以上 4 1 。搜索结果中相关信息和无关信息混杂在 一起，用户不得不逐个浏览，找到自己真正需要的信息仍然很困难。为解 决这个问题，许多学者改进了检索排序算法【5 】。然而，由于在多数情况下 用户提出的查询往往不能清楚表达自己的需要，尤其是当他对所搜索的领 域不熟悉时。因此，仅仅靠改进排序算法是不够的。 燕山大学工学硕士学位论文 针对这种情况，近些年来开始了有关w e b 信息检索系统的聚类研究， 在传统搜索引擎工作的基础上，将文档集合自动分成若干个簇( c l u s t e r s ) ， 同一簇内文档相关度尽可能的大，不同簇之间文档相关度尽可能地小，用 户可以在自己感兴趣的簇中查看结果，或者根据聚类情况提出更精确的查 询，这样将会大大缩小用户所需浏览的结果数量，缩短用户查询所需要的 时间。 1 2 研究现状 信息检索领域中在聚类研究前首先出现了分类技术，使用分类技术的 系统有：n o r t h e m l i g h t ( h t t p ：w w w n o r t h e r l i g h t c o m ) 信息检索系统和早期用 于x e r o xp a r c 的信息检索系统s c a t t e r g a t h e r ，这两个系统都是在用户查询 信息前提前对文档进行分类。前者是由图书管理专家提前将文档集进行分 类，共分1 7 0 0 0 多个子类f 6 】，后者使用划分法对文档集进行分类【”。当用户 查询信息时，系统首先对查询条件进行分析，然后以簇的方式只返回与用 户查询条件相关主题的文档集合。这两个系统均属于检索前分类系统，不 属于真正意义上的聚类系统。 在聚类的研究中，聚类实现技术大致可分为两种：一种是事先聚类， 检索前预先对文档集进行聚类。由于这一聚类处理的文档集巨大，所以对 计算资源要求较高，多为脱机处理。另一种是事后聚类，对检索结果进行 聚类。由于事后聚类处理的文档集较小，所以可实现联机处理。w e b 信息 资源是时刻动态增加变化的，提前将文档进行聚类分类，不能满足信息及 时更新的需求，且处理的文档集巨大对计算资源要求较高，代价较大，所 以将检索结果进行聚类的技术更加能够满足w e b 信息灵活多变的需要。 目前，也已经出现了一些利用联机聚类实现的信息检索系统，如i b m a l m a d e n 研究中心在开发a t h e n a 系统时提出了部分聚类的方澍8 】；s t a n d f o r d 大学的s o n i a 系统( h t t p ：w w w v i v i s i m o c o r n ) 和用于波兰语的c a r r o t 系统是两 个将搜索引擎的返回结果进行聚类的信息检索系统，这两个系统采用了 s t c ( s u f f mt r e ec l u s t e r i n g ，后缀树) 聚类算法1 9 1 。然而s t c 算法比较适合用于 2 第1 章绪论 英语、波兰语等词与词之间有明显分割标志的语言，不适合于汉语的处理。 并且s t c 算法只对标题和文档片断进行了分析和聚类。g o o g l e 搜索引擎根 据网址特点提供了“类似网页”；最大的中文搜索引擎b a i d u 也在检索结果 中根据网址提供了同一网站下的“更多的结果”，这两个搜索引擎都在返 回结果文档链接的基础上实现了一定意义上的聚类。由于存在商业机密和 知识产权的问题，我们对于一些现有搜索引擎使用的聚类核心技术不能够 进行较为全面的了解。 国外的学术研究组织如：s i g i r ( s p e c i a li n t e r e s t i n gg r o u pi n f o r m a t i o n r e t r i e v a l ，美国计算机学会信息检索特别兴趣小组) ；t r e c ( t e x tr e t r i e v a l c o n f e r e n c e ，文本检索学术年会) ；m u c ( m e s s a g eu n d e r s t a n dc o n f e r e n c e ， 消息理解学术年会) ：t i p s t e r ( 美国国防部高级研究计划署i r 实践基地) 和 c i i r ( c e n t e ro fi n t e l l i g e n ti n f o r m a t i o nr e t r i e v a l 全国智能信息检索研究中 心) ，其中也有不少文档聚类的研究。微软亚洲研究院研究的基于相关性分 析的文档聚类是通过对用户的l o g 分析，在用户的信息浏览和查询行为进 行分析的基础上进行聚类【1 0 1 。 国内从九十年代中期开始自动文本分类领域的研究，复旦大学和中科 院计算所对t r e e 测试中的分类任务进行了长期的跟踪和研究，北京大学和 清华大学较早在搜索引擎“天网”和“网络指南针”上研究网页分类技术。 鉴于聚类算法的重要作用，人们提出了各种方法对聚类算法进行改进。 2 0 0 5 年，澳大利亚的y u ex u 提出j h h c a ( h y b r i dh i e r a r c h i c a lc l u s t e r i n g a l g o r i t h m ) 算法。这种算法首先将数据集分成n 个簇，然后计算内部相似性 最小的，采用将之分离，同时计算最相近的两个簇，将之合并，然后比较 原始簇，以及上述两种情况。哪种最合理，然后决定采用哪种方式，当簇 不再变化，则聚类过程结束1 。 同年，台湾的学者提出了一种层次k m e a n s 方法。在这种算法中，首先 对数据集采用k m e a n s 方法得到k 个簇，然后采用凝聚或分裂层次聚类二次 整理，从而得到最终结果i l ”。 2 0 0 5 年，h w ah s i ac o l l e g eo f t e c h n o l o g ya n dc o m m e r c e 大学的学者在 提出了一种新颖的方法，在该方法中首先用概率统计法得到关键短语，然 燕山大学工学硕士学位论文 后对关键短语进行聚类，从而大大减少了空间维数，提高最终聚类速度【1 3 】。 国内关于聚类的研究也很多。 2 0 0 5 年，上海交通大学的刘靖明等，提出了k - m e a n s 算法的改进算法粒 子群聚类算法。这种算法主要解决了k m e a n s 算法局部最优解的问题【1 4 】。 2 0 0 4 年，燕山大学的王志梅提出了一种基于相似性密度的快速聚类方 法。在这种方法中，首先计算返回结果的相似性，然后将检索结果及他们 的相似性关系影射到无向图，最后根据无向图中每个点的相似性密度形成 基类，通过合并基类得到聚类结果【1 5 】。 2 0 0 3 年，重庆大学的王伟提出了一种改进的遗传算法，这种算法在一 定程度上改进了遗传算法强选择性压力会降低种群多样性，导致遗传搜索 过早收敛，而强种群多样性导致遗传搜索效率低下的缺点i i “。 1 3 本文的主要研究工作 现有较为常用的信息结果聚类方法大都是根据文档内容进行聚类而展 开的，它们常常是根据搜索引擎返回的检索结果文档列表提供的链接将全 文检索出来进行聚类处理。而在1 9 9 8 年e t z i o n i 等人实验结果表明，使用一 些改进算法来对检索结果进行联机聚类不但是可行的，而且十分有效【1 7 1 。 本文的研究内容主要包括以下三个方面。 ( 1 ) 找到合理的特征抽取方法特征项的抽取是后续聚类的基础，只有 找到合理的特征抽取方法，才能够取得好的聚类结果。 ( 2 ) 对索引模型进行改进聚类系统建立索引的目的是抽取关键短语， 所以它的建立过程必须以适合进行特征抽取为核心。建立合理的索引结构， 以使其更加方便特征抽取。 ( 3 ) 对聚类算法进行改进给出了适合于中文信息处理聚类算法。 1 4 论文结构 本文第1 章为绪论，介绍基于w e b 检索结果的快速联机聚类研究的背 4 第1 章绪论 景、意义以及国内外研究现状，并简要介绍了本课题要解决的问题与本文 结构。 第2 章介绍了信息检索系统搜索引擎的工作原理以及所涉及到的关键 技术和相关技术。对向量空间模型，索引模型，聚类，文档聚类，文档相 似性矩阵等几个方面进行了比较详细的介绍，为聚类的研究打下基础。 第3 章首先介绍了利用短语做文档特征项的优势，然后采用了结合统计 法进行关键短语提取的方法进行特征项抽取。同时对索引模型进行了改进， 使其更方便相似性的计算。并以b a i d u 搜索结果为例，从检索结果页面的处 理、切词、建立索引、去除高频、低频词、计算单个词汇的独立语义能力 等环节对关键短语的抽取过程做了具体描述，完成了检索结果的特征抽取。 第4 章计算结果条之间的相似性，并对部分检索结果进行层次聚类得到 初始聚类中心，然后采用改进的划分法对所有文档进行聚类，形成基类， 通过合并基类最终得到聚类结果。并以b a i d u 的检索结果进行试验为例，得 到了较好的聚类结果。 第5 章本章首先对h p m c 从空间和时间复杂度、聚类数目的确定、簇 相关性与孤立点的处理等几个指标做了分析与评估，并与已有的算法进行 了综合性比较，从而体现了本方法的独特的优越性。 燕山大学工学硕士学位论文 第2 章搜索引擎及聚类分析 w e b 从1 9 9 1 年出现以来，经过短短几年已经发展成为一个巨大的全球 化信息空间。面对信息的海洋，用户试图通过浏览w e b 来寻找信息已经变 得非常困难，往往花费了很长时间却所获甚少。在这种情况下，如何有效 地检索w e b 信息，以帮助用户从大量文档信息集合中找到与给定查询请求 相关的文档子集，也就成为一项重要而迫切的研究课题。同时，快速、有 效的w e b 信息检索也是充分发挥w e b 在数字图书馆、电子商务、远程教学 等方面潜能的一个基础前提i l ”。 信息检索并不是w e b 所特有的一个研究课题，早在2 0 世纪5 0 年代， 当计算机被图书馆等部门用于存储和管理文档时，信息检索就作为一个研 究领域而诞生了【1 9 1 。到8 0 年代，信息检索领域已经在文档内容表示、索 引模型、匹配策略等方面取得了丰硕成果，并成功地开发了一些系统。例 如：c o m e l l 大学的s m a r t 系统 2 0 1 和m a s s a c h u s e t t s 大学的i n q u e r y 系 统【2 1 1 等。w e b 的出现为信息检索提供了一个前所未有的试验环境和应用情 景，许多w e b 信息检索系统应运而生，例如y a h o o 、a l t a v i s t a 、g o o g l e 、 b a i d u 等。同时，w e b 的大容量、异构性、分布性和动态性给信息检索领 域带来了新的挑战，需要在传统信息检索技术的基础上开展针对w e b 特点 的研究工作。 2 1 搜索引擎工作原理 搜索引擎是目前最常用的w e b 信息检索工具，只要在搜索引擎网页上 输入关键词组进行查询，用户就可以得到相关w e b 信息的列表，从而得到 自己需要的信息。 自从第一个搜索引擎w w w w ( w o r l dw i d ew e bw o r m ) 在c o l o r a d o 大 学开发成功以来，w e b 上的搜索引擎已经发展到上千个。虽然各个搜索引 6 笙：兰堡茎! ! 兰垄至鲞坌堑 擎的具体实现不尽相同，但一般包含5 个基本部分：r o b o t 、分析器、索弓 器、检索器和用户接口瞄，2 3 1 。如图2 1 所示。 图2 - 1 搜索引擎的基本组成部分 f i g u r e2 - 1t h eb a s i cp a r t so f s e a r c he n g i n e 机器人程序也称为网页抓取工具，它采用广度优先( 或者深度优先) 的 策略对w e b 进行遍历，将w e b 页面从互联网上取回到本地机器【2 4 1 。 分析器对r o b o t 下载的文档进行分析，抽取出特征项以用于索引，所谓 特征项是指能表征文档内容的一些特征属性描述。 索引器将文档表示为一种便于检索的方式存储在索引数据库中。索引 的质量是w e b 信息检索系统成功的关键因素之一，一个好的索引模型应该 易于实现和维护，检索速度快，空间需求低。搜索引擎普遍借鉴了传统信 息检索中的索引模型，包括：倒排文档【2 5 2 6 1 、签名文件、后缀树与后缀数 组【2 7 1 等。 检索器从索引中找出与用户查询请求相关的文档，采用与分析索引文 档相似的方法来处理用户查询请求。常用的检索模型有布尔模型、矢量空 间模型s m 向量空问模型v e c t o rs p a c em o d e l ) 、概率模型、概率推理网络 模型【2 8 】等。 2 2 向量空间模型 向量空间模型( v e c t o rs p a c em o d e l ) 是目前信息检索中最常用的数学模 型。在万维网信息检索方面，向量空间模型比布尔模型等传统模型更适合， 因为，布尔模型是最简单的检索模型，标准的布尔模型是二元逻辑，所检 索的页面要么与所键入的关键词组有关，要么无关，检索结果一般不进行 7 燕山大学工学硕士学位论文 相关性排序：而向量空间模型不仅可以方便地产生有效的检索结果，而且 能够提供相关页面的文摘，并进行检索结果分类，为用户提供准确的所需 信息。 基于向量空间模型的信息检索一般过程如下。 ( 1 ) 将各个文档和查询都表示为向量。 ( 2 ) 计算查询与各个文档之间的相似度。 ( 3 ) 按照查询与各个文档之间的相似度对相关的文档进行排序。 ( 4 ) 将排序后的文档以线性列表的形式返回给用户。 2 2 1向量空间 在向量空间模型中，各个文档( d o c u m e n t ) 和查询( q u e r y ) 的内容都表示 为向量。 定义2 1 ：权重。词组只在文档日中的权重( w e i g h t ) a ( i g ) 可定义为： a ( i j 3 = ( f 力g ( d 。其中，l ( i j ) 是局部权重( 1 0 c a lw e i g h t ) ，它体现了词组只 对文档d ，的重要程度；g ( 0 是全局权重( g l o b a lw e i g h t ) ，它体现了一个词组 区别各个文档的能力。 常见的局部权重三一如公式( 2 - 1 ) 与公式( 2 - 2 ) 所示。 t f ：l ( i j ? = 蛎( 2 - 1 ) l o g t f ：l ( i j 3 = l 0 9 2 ( 咿1 )( 2 - 2 ) 式中，观表示第i 个词组只在第，个文档历中的出现频率。 常见的全局权重g ( o 如公式( 2 3 ) 至公式( 2 6 ) 所示。 n o r m a l ：g ( f ) = 1 、观2 ( 2 - 3 ) g f * i d f ：g ( f ) = g f d f ,( 2 - 4 ) i d f ：g ( i ) = l 0 9 2 ( n a d 3 ) + 1( 2 - 5 ) e n t r o p y ：盼一军篙箸 吮傅 函6 ， 式中，颤表示第i 个词组只在所有文档中的出现频率，哳表示含有第i 个 词组的文i 档的数目，n d 表示所有文档的总数。 8 第2 章搜索引擎及聚类分析 定义2 2 ：词组文档关系矩阵。设有疗个文档，对所有文档进行词组 切分、过滤和转换之后，合适的朋个词组( p h r a s e ) 被提取出来，则可以构 造m x n 的词组文档关系矩阵( p h r a s e d o c u m e n tm a t r i x ) , 4 ，其中，4 中的元素 a ( i i ) 表示第“1 s f = 抑) 个词组只在第，个( 1 9 9 ) 文档d ，中的权重。 如上定义，每个词组就可以用爿中对应的行向量来表示，每个文档就 可以用彳中对应的列向量来表示。所有文档都是位于m 维空间中的向量， 查询也可以与文档一样表示为r f 维空间中的向量。 2 2 2 文档表示 在向量空间模型中最常用的权重计算方法是t f * i d f ( r r 以t f 为局部 权重三( f 力而以i d f 为全局权重g ( f ) ) ，因为它容易实现而且速度较快。也 即是采用t f * i d f 文档向量表示法，将文档集合表示成为文档特征向量集 合。具体的做法描述如下。 假设当前的文档集合为d ，其中包含的所有词组构成的集合为p ，文档 纳d 中的一个元素。d x 档特征向量的形式为d = ( d ( ”，d ( ”，d ”) 。其中 每一个分量d 的计算公式如公式( 2 7 ) 所示。 矛”= 7 匍 ，田x l d f ( p i )( 2 7 ) 式中，t f ( p 。，砂表示词组陆在文档d e e 出现的频率，i d f ( p ) 如公式( 2 8 ) 所示。 i d f ( p ，) = l 0 9 0 d d f ( p 。) ) ( 2 8 ) 式中，d 表示文档集合d e e 所包含的文档数量，d 砸j 表示词组肼在文档集 合d 中至少出现一次的文档数量。 t f * i d f ( v 为文档的表示方法，它表明如果一个词组在该篇文档中出现 的频率越高，并且在其它文档中出现的次数越少，则此词组对于区别该篇 文档的能力越强，相应在文档向量中的权值也越大。 2 2 3 相似性计算 把文档表示成向量的形式，主要是要将通过元搜索引擎检索到的文档 特征向量和用户的兴趣向量之间进行相关性的计算。检索得到的文档与用 户兴趣的相关度越高，则排列越靠前，越容易被用户看到。相关度针对两 9 燕山大学工学硕士学位论文 种不同的情况，分别采用两种不同的方法进行计算。一种是针对普通的情 况，还有一种针对科技文献。 第一种是针对最为普通的情况，主要采用向量之间点乘的方法，计算 向量之间的欧几里得距离，其计算结果是一个实数，可以根据大小进行排 序。具体的计算公式如公式( 2 9 ) 所示。 旭一卅砌。编2 ( d ( f ) j ( f ) ) ( 2 - 9 ) 第二种是针对科技文献而言的。任何一篇科技文献的最后都会列出参 考文献，如果两篇科技文献引用了大量相同的参考文献，则这两篇文献可 能是相关的。具体的计算方法为c c i d f ：假设c 是一个引用i 在一个文档集 合d 中出现的频率，令w ，= i c ，则表示频率的向量：表示一个布尔指 示值，用以表示文档d 是否包含了引用f ；肠表示结果的布尔向量。文档瘌 文档的兴趣度西之间的相关度如公式( 2 - 1 0 ) 所示。 r ( d , d t ) = t r ( x d x d f ) w df 2 一l o ) 式中，州) 是回溯函数。 2 3 索引模型 索引模型将文档表示为一种便于检索的方式存储在索引数据库当中。 索引的质量是w e b 信息检索系统成功的关键因素之一，一个好的索引模型 应该易于实现和维护，检索速度快，空间需求低。搜索引擎普遍借鉴了传 统信息检索中的索引模型，包括：倒排文档、签名文件、后缀树与后缀数 组等。 倒排文档模型是一种面向单词的索引机制，利用它可以提高网络检索 速度。倒排文档结构由词汇和出现情况两部分组成。对于每个单词，都有 一个列表( 称为词汇列表) 来记录单词在所有文本中出现的位置。由于倒排 索引要涉及文本中出现的每个单词，所以词汇出现情况的空间需求为d ( 胛) 。 l o 第2 章搜索引擎及聚类分析 在实际应用中，由于在存放词汇出现情况的过程中，还有一些描述信息， 因此词汇出现情况列表所占的空间要比整个信息库中的文本所占的空间多 出3 1 3 至1 j 4 0 1 2 9 。 这样，在对倒排文件进行搜索的时候总是从词汇表开始查询。因为一 般说来，词汇表可以与倒排文件分开存放，而且它的空间要求比较少，适 合于放置在内存中。对于单个词汇的查询来说，只要从词汇表中找到对应 的单词，就可以找到指向该单词的出现情况列表。因此在倒排文件中对于 单个的词汇查询来说，其查询的时间复杂度为d ( 枷? ) ( 其中聆为词汇表的长 度) 。对于单个词汇的查询，该词汇的出现情况列表可以直接作为搜索结果 返回给用户，而对于多个词汇的查询，还需要对这些列表进行一系列相关 的操作。 倒排文件将文本看成单词的序列，这对于解决其它复杂查询( 短语查询1 需要花费很大的代价。后缀树可以以较高的效率解决一些复杂查询。在实 际实现中，后缀树通过后缀树组来实现，后缀树的主要缺点在于其生成过 程比较复杂。 在后缀树中，它将文本看成一个长的字符串，文本中的每个位置都看 成一个文本后缀，( 从该位置到文本结束所包含的字符串) ，每个文本后缀 都由它在文本中的位置唯一确定。这些位置并不需要全部都建立索引，这 就涉及索引点的选择问题。如果所有索引点都选择为每个单词的开始，这 样该索引在功能上就与倒排文件类似。 后缀树的一个显著特点是能快速地对短语进行搜索。后缀树的生成过 程如下：首先将大文本分割成适合在内存中处理的块，然后对于每个块构 造后缀树，最后将这些构造好的后缀树进行合并。 2 4 聚类算法 “物以类聚，人以群分”，这是自然界的一个普遍现象。按照数据的 相似性和差异性，将数据划分为若干组，同组的尽量相似，不同组的尽量 相异，这种对数据进行自动组织的方法称为聚类( c l u s t e r i r 喀) 口0 1 。聚类是数 燕山大学工学硕士学位论文 据挖掘的基本形式之一。聚类与分类不同，分类是一种监督学习( s u p e r v i s e d l e a r n i n g ) ，其类别是根据应用的需要事先确定的，根据表示事物特征的数 据可以识别起类别：聚类是一种非监督学( u n s u p e r v i s e dl e a r n i n g ) ，其类别 不是人为指定的而是分析数据的结果，聚类是完全有计算机自动进行的， 不需要人工干预。聚类通过比较数据的相似性和差异性，能发现数据的内 在特征及分布规律，从而获得对数据更深刻的理解和认识。聚类算法根据 其产生的聚类结构可以分成两种：层次型和划分型”1 。 2 4 1 层次型聚类算法 层次型聚类算法产生的聚类结构是树状的，一般用树状 虱( d e n d r o g r a m ) 来表示。其中最常用的层次型聚类算法是分级凝聚类h a c ( h i e r a r c h i c a l a g g l o m e r a t i v ec l u s t e r i n g ) 算法。 例如，以h a c 算法对文档集合a 、b 、c 、d 、e 进行聚类，得到的聚类 结构如图2 2 所示，在此基础上，取不同的相似性阈值可以得到不同的文档 分类。 如果选l 1 作为相似性阂值，则文档将分成4 类：( a ，b ) 、( c ) 、( d ) 、( e ) 。 如果选l 2 作为相似性闽值，则文档将分成2 类：( a ，b ) 、( c ，d ，e ) 。 如果选l 3 作为相似性阂值，则文档将分成1 类：( a ，b ，c ，d ，e ) 。 abcde 图2 - 2h a c 树状图 f i g u r e2 - 2h a cd e n d r o g r a m h a c 算法以文档相似性矩阵作为输入，以自底向上的方法进行聚类， 第2 章搜索引擎及聚类分析 开始每个文档就是一个类，然后找出最相似的两个类合并起来，如此继续 直到满足预定的停止条件。 根据类相似性的定义不同，h a c 算法可以分成以下的具体形式：单连 通( s i n g l e - l i n k ) 算法、完全连通( c o m p l e t e l i n k ) 算法、平均连通( g r o u p a v e r a g e l i n k ) 算法、w r a d 算法。 单连通算法、完全连通算法、平均连通算法分别以两个类中所有的文 档对相似性的最小值、最大值、平均值作为两个类之间的相似性值。w a r d 算法也称最小方差( m i n i m u mv a r i a n c e ) 算法，它试图使各个类的方差总和为 最小。 因为单连通算法无须计算类的质一i ) * ( c e n t r o i d ) 或代表( r e p r e s e n t a t i v e ) ，而 且类之间的相似性可以直接从文档相似性矩阵得到，所以单连通算法的效 率较高。另外，单连通算法还具有优美的数学性质。这些特点使得单连通 算法成为h a c 算法最普遍的形式。 h a c 算法对异常数据( a b n o r m a l ) t 常敏感。对杂舌l ( n o i s y ) 的数据源， h a c 算法往往会得到一两个特大类和许多极小的类【3 2 1 ，这一般不是用户所 期望的。取某些相似性阈值时，h a c 算法可能得到几何形状狭长的类，也 就是一些相似性很低的文档被放入同一类。 h a c 算法对停止条件也非常敏感。虽然已经有多种h a c 算法的停止条 件被提出1 3 3 1 ，但在实践中一般只是预定类数( 例如在剩下5 个类的时候停 止) 。如果h a c 算法未在恰当的时候停止，好的类会被继续合并而产生没有 意义的差类。 2 4 2 划分型聚类算法 划分型聚类算法产生的聚类结构是平面的，一般用互不相交( d i s j o i n t ) 的集合来表示。 因为将个文档分成埘个互不相交集合的可能形式实在太多，所以通过 穷举得到最优解是不可行的。非树型聚类算法往往是先对数据做初步划分， 然后不断调整，直到满足某种约束，从而得到一个近似最优解。 常见划分型聚类算法有k m e a n s 算法、u n s u p e r v i s e dn a i v e b a y e s i a n 算 燕山大学工学硕士学位论文 法、s i n g l e p a s s 算法、b u c k s h o t 算法、f r a c t i o n a t i o n 算法等等。 k m e a n s 算法【3 4 l 是最基本的划分型聚类算法，它假设各个类都呈球状 ( s p h e r i c a l ) n 各个类大小几乎相等。k m e a n s 算法以“估计最优化”的方式 来寻找最合适的模型参数：开始时先随机确定类的质心( 类代表向量) ，如 此继续直到文档的划分不再变化。k m e a n s 算法速度较快，但它的结果受 随机确定的初始值影响很大。 u n s u p e r v i s e dn a i v e b a y e s i a n 算法【3 5 jl k k m e a n s 算法更加复杂，它能得 到不同大d x ( s i z e ) 、不同协方差( c o v a r i a n c e ) 、不同数据分布( d i s t r i b u t i o n ) 的 类。u n s u p e r v i s e dn a i v e b a y e s i a n s 算法也是以“估计最优化”的方式来寻 找最合适的模型参数。 s i n g l e p a s s 算法【3 6 l 与k 。m e a i l s 算法类似，它也是假设各个类都呈球状 且各个类大小几乎相等。s i n g l e p a s s 算法基于“贪婪”( g r e e d y ) 规则进行增 量式( i n c r e m e n t a l ) 的聚类：首先选择某文档作为第一个类，然后将其他的文 档逐一与当前所有类进行比较，找到与之最接近的类，如果该文档与其最 接近的类的相似性程度高于预先确定的阈值，该文档就被加入此类，否则 就将该文档作为一个新的类。s i n g l e p a s s 算法的缺点包括对数据的处理顺 序非常敏感，对预定的相似性阈值非常敏感，并且倾向于产生较大的类f 3 7 1 。 2 5 文档聚类 按照文档聚类是在检索之前还是之后进行，可以将文档聚类分为两种： 检索前聚类和检索后聚类。 检索前聚类是在检索之前对全部文档进行聚类。s a l t o n 曾经指出检索 前聚类的作用【3 s 】，在实践中将每个文档与查询进行比较往往是不可能的， 因为这样的操作需要太多的时间。为了减少文档与查询进行比较的次数， 人们提出过许多解决办法。其中很有效的一种方法是将文档在检索前聚类， 使相关的文档在同一类中。每个文档类以一个向量来表示。在检索过程中， 查询向量先与各个类向量逐一进行比较，得到相关度较高的类，然后只要 与这些类中的文档向量逐一进行比较就可以得到了结果。s a l t o n 也提出了 1 4 第2 苹搜索引擘及聚类分析 检索前聚类，虽然能够提高检索效率( e f f i c i e n c y ) ，但是难免会降低检索效 果( e f f e c t ) 。 检索后聚类是在检索之后对查询相关的文档进行聚类。与检索前聚类 相反，检索后聚类不仅不会降低检索效果，反而能够根据相关文档集合的 特征提高检索效果。值得提及的是，全部文档集合的特征不一定就是相关 文档集合的特征。不过，检索后聚类需要一定的时间，会降低检索效率。 检索前聚类与检索后聚类对检索效果的不同影响如图2 3 所示。 图2 - 3 检索前聚类与检索后聚类对检索效果的影响 f i g u r e2 - 3i n f l u e n c eo f p r e - r e t r i e v a la n dp o s t r e t r i e v a lc l u s t e r i n gt or e t r i e v a le f f e c t 总之，检索前聚类主要是为了提高检索效率，检索后聚类主要是为了 改善检索效果。 2 6 文档相似矩阵 文档聚类算法的根据是各个文档之间的相似性，文档聚类应该使同类 的文档尽量相似而不同类的文档尽量相异。 各个文档之间相似性可以记录在文档相似性矩阵( d o c u m e n ts i m i l a r i t y m a t r i x ) 之中。 设共有n 个文档，则可以构造胛”的文档相似性矩阵b ，矩阵b 的行和列 对应着各个文档，其中元素b ( f d 表示第f ( 1 s 盎抑) 个文档口与算移( 1 辎h ) 个文 档d ，的相似性( s i m i l a r i t y ) ，计算方法与前述文档与查询之间相关度的计算方 法是一样的。 显然，文档相似性矩阵是对称的，因此使用下三角矩阵即可。相似性 燕山大学工学硕士学位论文 矩阵表示如公式( 2 11 ) 所示。 式中，对角线上s t f l 。 2 7 本章小结 s = 墨。 s 2 i s 3 1 是2 马3 ( 2 - 1 1 ) 本章介绍了信息检索系统搜索引擎的工作原理以及所涉及到的关键技 术和相关技术，对向量空间模型，索引模型，聚类，文档聚类，文档相似 性矩阵等几个方面进行了比较详细的介绍，为聚类的研究打下基础。 1 6 第3 章关键短语的抽取 第3 章关键短语的抽取 本文给出的i - i p m c 方法是以搜索引擎的检索结果为研究对象的一种快 速聚类方法，在聚类过程中，从特征项抽取、索引模型的建立、相似性的 计算到聚类结果的形成等环节，都做了分析和简化。本章节的关键短语的 抽取是指检索结果的特征抽取过程，它是一种利用上下文单词之间的关联 性给出的一种适合中文处理的特征项抽取方法。 对搜索引擎的搜索结果而不是整个w e b 进行聚类分析，是因为w e b 数 据规模巨大质量却参差不齐，而且低质量的数据可能更多，导致信息与垃 圾混杂，知识与谬误共存，事先根据质量对w e b 的数据进行筛选与清理， 是保证聚类方法得到成功运用的前提条件。所以，对搜索引擎的搜索结果 进行聚类更有效、更可行。 在现有的检索结果聚类研究中，大都根据搜索引擎返回的文档列表提 供的链接将全文抓取出来，对文档内容进行聚类。而在19 9 8 年e t z i o n i 等人 实验结果表明，使用一些改进算法来对检索结果进行聚类不但是可行的， 而且十分有效。根据上面聚类过程