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

摘要 目前，搜索引擎存在着冗余信息过载和索引数据库信息覆盖率低的问题，发展个性 化的元搜索引擎是解决这两个问题的一个重要途径，由于元搜索引擎可以同时调用多个 独立搜索引擎，提高了搜索引擎的查全率；面对数量众多的检索结果，采用个性化的结 果处理方法，可以提高用户检索的效率和返回结果的质量。 本文研究并设计了一个针对元搜索引擎返回结果的个性化排序算法。算法的主要思 路是将元搜索引擎返回的结果网页预处理后，通过聚类的方法，将结果网页集合划分为 不同的类别。计算每个类别与用户兴趣模型的相似度，根据相似度对类别进行宏观排序， 从而确定用户的兴趣类别，并对兴趣类别中的结果进行基于查询关键词与结果内容相关 性的微观排序。文章中同时也给出了建立用户兴趣模型的方法和步骤。 在个性化排序算法的结果预处理步骤中采用了一种改进的基于超链接文本分析的 网页正文提取方法；在排序步骤中提出了宏观排序和微观排序的概念，给出了两种排序 的具体实现方法；在聚类处理中，为了提高算法的性能，采用了一种改进的聚类算法。 根据元搜索引擎结果个性化排序算法，本文设计了一个基于客户端的个性化元搜索 引擎系统( p m s ) ，系统采用了模块化的设计，具有友好的人机交互界面。文中给出了系 统的测试数据，并对数据进行了分析和处理。实验表明，本文的基于个性化排序算法的 个性化元搜索引擎系统( p m s ) 具有理想的查全率与查准率，能够达到方便用户检索和提 供高质量检索结果的目的，同时该系统也存在着很多不足之处，有待于进一步的改进。 关键词：元搜索引擎，个性化排序，文本聚类，用户兴趣模型 r e s e a r c ha n di m p l e m e n to ft h ep e r s o n a l i 锣s o r to nr e t r i e v er e s u i t so ft h e m e t as e a r c he n g i n e s u i lx i n ( c o i n p u t e r a i p p l i c a t i o nt e c l l i l o l o g y ) d i r e c t e db ya s s o c i a t ep r o s u oh o n g g u a n g a b s t r a c t a tp r e s e n t 龇s e a r c he n g i n eh a v et l l ep r o b l e mo fr e d 眦d a n ti n f o 舳a t i o n0 v e r l o a da 1 1 d t l l el o wc 0 v e r a g eo ft h ei n f o n i l a t i o no ni n t e m e t d e v e l o p i n gt h ep e r s o n a l i 够m e t as e a r c h e n g i n ei s a 1 1i m p o r t 觚t 、a yt 0r e s o l v em e 咖p r o b l e m s t h em e t as e a r c h e n g i n ec a l l s i m u l t a l l e o u s l y 咖1 s f e rm a l l yi n d 印e n d e n ts e a r c he n g i n e s ，s 0t h em e t as e 盯c he n g i n et h eh a v e l l i g h e rr e c a l lr a t e t h em e m o do fd e a l i n gw i t ht h er e t r i e v a lr e s u l t so fm e t as e a r c he n g i n e p e r s o m u yc 锄i m p r o v et h ee f n c i e n c yo fu s e r sr e t r i e v ea i l dt h eq u a l i t ) ro ft h er e t r i e v er e s u l t s i nt l l i sp 印e r ，ap e r s o n a l i 够s o r ta l g o r i t l l mb a s e do nt h er e t r i e v er e s u l t so fm e t as e a r c h e n g i n e si sr e s e a r c h e d 觚dd e s i 舯e d t h em a i ni d e ao fm em g o r i l mi sn l a tt 1 1 er e t r i e v er e s u l t s o fm e t as e a r c he n g i n e sa r ed i v i d e di m od i 恐r e n tc l a s s e su s i n gac l u s t e m ga l g o r i t m 抵r p r e 仃e a t m e n t t h es i m i l a r i 够o fu s e ri n t e r e s tm o d e la n dt l l ec h a r a c t e r i s t i c so fc l a s s e sa r e c a j c u l a t e d a c c o r d i n gt 0m es i m i l a r i 劬am e t h o do f m a c r o s o ni su s e dt or a n km ec l a s s e s 龇l d n l ec l 嬲s e s l a tu s e ri i l t e r e s t e di nd e t e n i l i n e d am “h o do fm i c r o s o nb a s e d0 nr e l e v 锄c eo f n l e 胁i e v er e s u l t s 锄dt l l ek e yw o r d su s e dt 0 础【l l ( t h er e t r i e v er e s u l t si nc l a s s e st h a tu s e r i n t e r e s t e di n m 猢e r sa 1 1 ds t e p sa r ea l s oi n t r o d u c e d a ni m p r o v e dm e m o do fe x 吮t i n gt e x tc o n t e n t 舶mw e b p a g eb a s e do nh y p e r l i n k st e x t a i l a l y s i si su s e di i lm ew e bp a g ep r e 仃e a ：c i i l e n ts t 印o f ：屺p e r s o n a j 时s o r ta l g o r i t h m 1 k c o n c e p to fm a c r o - s o r ta i l dm i c r 0 - s o r ta i l d 恤c o n c r e t er e a l i z a t i o np r o c e s sa r ei i 帅d u c e d a n i m p r 0 v e dc l u s t e r i n ga j g o r i t l l i l lt h a ti su s e dt 0i i n p r o v et l l ep e 墒咖a i l c ei si m p l e m e n t e di n 此 p e r s o n a l i t ) ，s o r ta l g o d t 髓 a p e r s o r l a l i t ) rm e t as e a r c he n g i n es y s t e m ( p m s ) b a l s e d0 nt h ep e r s o n a l 时s o r ta 1 9 0 r i t h m i sd e s i g n e di nt l l i sp a p e r m o d u l a rd e s i g i li su s e di nt h es y s t e m ，觚dm e s y s t e mh a sa 衔e n d l y m 锄。m a c l l i n ei n t e r f i a c e 1 kt e s td a _ t ao ft h es y s t e mi si n t r o d u c e di nt h i sp a p e r t e s td a ：t aa n d 恤a n a l y s i so f 龇t e s td a t as h o w s 眦m ep e r s o n a l 时m e 协s e a r c he n g i n es y s t e m ( p m s ) b a s e do np e r s o 叫i t ys o r ta 1 9 0 r i t h mb a s e do nt h er e t r i e v er e s u l t so ft h em e t as e a r c he n g i n eh a s i d e a lr e c a l lr a t e 孤dp r e c i s i o nm t e ，觚da c h i e v e dm e ：p u 印o s eo fu s e r - 衔e n d l ys e a r c ha n d p r o v i d i n gm 曲一q u a l i 够r e t r i e v er e s u l t s t h es y s t e ma l s oh a sm a l l yd e f e c t s ，s oi tm u s tb e i m p r o v e di nt h e 如t u r e k e y w o r d s ：m e t as e a r c he n 舀i l e ，p e r s o n a l i t ys o r t ，t e x tc l u s t e r i n g ，u s e ri n t e r e s tm o d e l 关于学位论文的独创性声明 本人郑重声明：所呈交的论文是本人在指导教师指导下独立进行研究工作所取得的 成果，论文中有关资料和数据是实事求是的。尽我所知，除文中已经加以标注和致谢外， 本论文不包含其他人已经发表或撰写的研究成果，也不包含本人或他人为获得中国石油 大学( 华东) 或其它教育机构的学位或学历证书而使用过的材料。与我一同工作的同志 对研究所做的任何贡献均已在论文中做出了明确的说明。 若有不实之处，本人愿意承担相关法律责任。 学位论文作者签名翻象日期；拯年，月髟日 学位论文使用授权书 本人完全同意中国石油大学( 华东) 有权使用本学位论文( 包括但不限于其印刷版 和电子版) ，使用方式包括但不限于：保留学位论文，按规定向国家有关部门( 机构) 送交学位论文，以学术交流为目的赠送和交换学位论文，允许学位论文被查阅、借阅和 复印，将学位论文的全部或部分内容编入有关数据库进行检索，采用影印、缩印或其他 复制手段保存学位论文。 保密学位论文在解密后的使用授权同上。 学位论文作者签名：l 坠笠 指导教师签名：垄互鱼誊 日期：懈年，月石日 日期：瑚年j ，月西日 中国石油大学( 华东) 硕士学位论文 1 1 研究背景 第1 章引言 随着i n t e r n e t 的迅速发展，网络信息总量急剧膨胀，每天都有近百万的新网页出现 i n t e r n e t 上【l 】，网络逐渐深入到人们工作生活的方方面面，然而面对浩如烟海且内容庞 杂，组织松散的百亿网页，用户需要花费更多时间在i n t e m e t 上查找需要的资料和信息。 为了帮助用户查找所需信息，g o 0 9 1 e ，y a h o o ! ，b a i d u ，e x c i t e ，l y c o s 等一批高性的搜 索引擎应运而生，它们大大提高了人们信息检索的能力和寻找信息的效率。这些商业化 的通用w e b 搜索引擎在某种程度上己经解决了w e b 信息检索问题。 虽然搜索引擎的巨大成功带来了搜索技术的不断提高，但搜索引擎服务提供商决定 了显示的信息内容，对个人用户而言，这些都是无权选择的，同时，面对动辄返回的数 百万搜索结果，对用户也是一个极大的挑战。另外，在大量的搜索结果里边包括了相当 数量的与用户的查询不关的网页，造成了信息过载【2 1 。在百度里搜索关键词“电影毕 业生 可以得到2 1 8 ，0 0 0 个相关网页，在g o o g l e 里搜索可以得到3 8 3 ，0 0 0 个相关网页， 表面看来，如此多的网页可以展现出这些搜索引擎的强大功能，但是通过具体分析搜索 返回的结果会发现，在这些网页中存在着大量的与关键词不相关的结果网页，以及不能 链接的无效网页等等，也就是说结果网页的数量并不能说明某个搜索引擎的性能。同时 由于各种搜索引擎在结果排序方面不同的算法，使得用户需要的信息在结果网页中的位 置不同，另一方面，由于单个搜索引擎的索引数据库对互联网覆盖面有限，又可能漏掉 很多用户需要的信息。搜索引擎的这些问题是出于自身的局限性： 1 冗余无效的信息量大。几乎每个搜索引擎返回的结果中都会出现大量的无关信 息和无效链接，给用户查找信息带来了极大的困难。 2 索引数据库大，更新周期长。由于i n t e m e t 信息的爆炸性增长，独立搜索引擎要 跟上这种信息的增长速度以满足用户的需求，索引数据库的规模就会不断增大。对大规 模索引数据库的更新和维护比较困难，而且1 1 1 t e m e t 上信息的更新快，经常会导致索引 的失效，同时对大容量的、非结构化或者半结构化的信息进行增加、删除和修改，也是 信息检索中的一个难解决的问题。 3 客观条件对搜索引擎的限制。随着i n t e m e t 上信息的快速增长，传统搜索引擎的 数据库的覆盖率、索引机器人的能力、索引数据库的大小以及系统维护开销等，都限制 第l 章引言 了单个搜索引擎的发展。 4 一般搜索引擎的索引数据库信息覆盖范围很低，而i n t e r n e t 上的信息资源是动 态变化的，主要表现为信息量呈指数级增长，任何一个独立搜索引擎都不可能覆盖 i n t e r n e t 上的所有网页信息。调查表明独立搜索引擎的平均网页覆盖率仅为5 一2 0 由表1 1 可以看出，即使所有搜索引擎的覆盖率加起来，也只有4 2 【3 j 而且最近的调 查表明，传统搜索引擎的索引数据库网络覆盖率正在逐步下降，因为索引的建立速度跟 不上1 1 1 t e m e t 上信息的增长速度。在这样低的覆盖率下，查全率自然也是非常低的。 表卜l 搜索引擎网络覆盖率比较n 1 t h b i e l 1t h ec o m p a r i s o no nn e t w o r kc o v e r a g eo fs e a r c he n g i n e s 排名 搜索引擎网络覆盖率( ) ln o n h e ml i 曲t1 6 2a l t av i s t a1 5 5 3 i n k t o m i ( s n a p ! ) 1 5 5 4 i n k t o m i ( h o t b o t ) 1 1 3 5 i n k t o m i ( m s ns e a r c h ) 8 5 6i n f 0 s e e k8 0 7 g o o g l e 7 8 8 i n k t o m i ( y 曲o o ! ) 7 4 9e x c i t e5 6 1 0 l y c o s 2 5 l le u m s e e k2 2 元搜索引擎的发展，在一定程度上解决了上述的问剐4 1 。自从1 9 9 5 年华盛顿大学 硕士生e r i cs e l b e r g 和o r e ne t z i o n i 推出第一个元搜索引擎，这一新型的网络检索工 具异军突起，发展迅速，目前可用的元搜索引擎已近百种，其中著名的元搜索引擎有： i n f 0 嘶d ( 嗍i n f o 酣d c o m ) ，m e 协c r a w l e r ( w w w m e t a c r a w l e r c o m ，i t h a k i ( 、7 l n ) i ，w i 1 1 l l a 玉【i n e ， b 【q u i c k ( w w w i x q u i c k c o m ) ，p r o f u s i o n ( w w w p r o m s i o n c o m ) ，m 锄：l m a ( w 、w m a l i l i i l a c o m ) ， s a v 、侈s e a r c h ( w w w s a v 、7 s e a r c h c o m ) 等。 元搜索引擎具有服务多样化的特性，它提供内部“黑箱操作 和外部“人性化 服 务模式，根据用户个性化需求进行灵活的结果输出。元搜索引擎的搜索界面实现了用户 选择和利用适合的独立搜索引擎进行信息检索的目标。由于元搜索引擎可以同时调用多 个独立搜索引擎进行关键词的查询，相当于调用多个索引数据库，大大提高了搜索结果 的查全率，同时根据不同的独立搜索引擎的调度算法，还可以根据用户的偏好有选择的 使用独立搜索引擎。 元搜索引擎集成多个独立搜索引擎，可以一次在多个独立的搜索引擎中并发查询， 2 中国石油大学( 华东) 硕士学位论文 增加了检索的范围，扩大了查询的区域，信息覆盖显著增加，因而能够获得高的查全率， 同时利用人工智能技术，根据用户需求对各独立引擎的查询结果进行过滤，或者改进排 序算法对独立引擎的检索结果做过滤，去重的处理，并对结果按照相关度排序，通过这 种方式，可以提高结果的查准率。元搜索引擎依靠其较强的扩展能力，可以集成多个独 立的搜索引擎，突破单个独立引擎的组织边界。不同的搜索引擎有不同的搜索内容侧重 点，可以结合当前查询的具体情况，对各个独立引擎进行评估，选取最适合当前查找的 引擎进行检索。 在另一方面，随着下一代i n t e r n e t 技术的飞速发展与应用，未来的w e b 将更加的丰 富多彩。面对内容，形式多元化的网络资源，如何利用网络信息挖掘技术将用户复杂、 散乱且隐蔽的知识快速的从信息库中抽取出来是现代信息服务需要解决的问题。网络的 个性化信息服务则是以用户的兴趣需求为根本出发点，依据用户的知识结构，心理和行 为方式的个性差异，主动引导用户提取个性化的信息。 个性化是一个非常活跃和广阔的研究领域，其目标是就领域知识表示用户的信息需 要和兴趣，向用户提供个性化的信息服务和主动信息服务。用户模型用于提高查找、推 荐、过滤和排序及推荐能力，因而能更好地满足用户的信息需要。个性化服务和信息检 索相结合的产物，即个性化信息检索技术是当前w e b 技术研究的一个热点。用户的个性 化信息需要利用w e b 个性化挖掘的方法抽取用户感兴趣的潜在有用模式与信息，将这些 信息和模式通过不同的方法可以建立用户兴趣模型。实现i n t e r n e t 上搜索引擎的个性化 智能检索是当今信息检索领域的重要研究课题。 1 2 研究意义 搜索引擎对检索结果的组织检索结果与检索语句的相关性判断与排序是系统 运行和性能评价的关键技术。近年来一直是国际上搜索引擎界的研究热点，甚至会成为 搜索引擎技术发展的里程碑。g o o g l e 正是因为开发并应用了有关检索结果组织的专利技 术p a g e r a n k 而一跃成为搜索引擎界的霸主，占据了搜索引擎市场四分之三的份额，而 我国在这方面的研究和实践相当滞后。 由于元搜索引擎介于用户和独立搜索引擎之间，无需建立大型索引数据库，因而维 护起来比较容易，而且任何一个成员搜索引擎的更新，都会反映到元搜索引擎上，因而 更易于实现个性化的信息检索。 在元搜索引擎的研究中，如何将来自不同独立搜索引擎的搜索结果整合起来，通过 第l 章引言 合理算法处理后返回给用户一个便于查找的检索结果序列是研究元搜索引擎的关键问 题。对面大量的w e b 用户，搜索引擎的统一搜索接口不能满足每个用户的需求，需要 针对不同的用户采用个性化的方式来处理用户的查询要求，因此，元搜索引擎结果的个 性化排序研究就显得尤为重要。元搜索引擎弥补了传统搜索引擎覆盖率低和不相关信息 过载等问题上的不足，而个性化元搜索引擎则是弥补了元搜索引擎因不考虑用户个人信 息差别而出现的缺陷。个性化元搜索引擎是为用户提供个性化搜索服务，因此，需要一 个算法来将用户的个人信息与元搜索引擎结果的处理相结合，使元搜索引擎的结果处理 能根据不同用户的信息而返回不同的检索结果序列。这个问题就是本文要解决的本质问 题。 1 3 研究内容 本文研究的主要内容是元搜索引擎结果个性化排序算法。 主要研究了基于改进的聚类算法，通过采用改进的k m e a n s 算法，算法具有了更好 的聚类效果，应用于个性化排序后，提高了个性化算法的性能。 提出了宏观排序与微观排序的概念，并给出了相应的排序方法。通过将聚类处理后 划分的检索结果类别与用户兴趣向量的相似性匹配，来确定用户的兴趣信息，对于用户 感兴趣的类别中的结果记录，采用一种基于查询关键词与检索结果内容相关性的方法来 对类别内的结果进行微观排序。 在网页的预处理方面，给出一种改进的基于超链接文本分析的网页正文提取方法。 最后，文章给出了基于算法的个性化元搜索引擎系统( p s m ) ，并对系统进行了测试， 同时给出了测试数据。通过对数据的分析，客观评价了系统的优缺点，并指出了个性化 排序算法的改进方向。 1 4 论文结构 论文的第一章分析了当前搜索引擎发展面临的问题，以及研究个性化信息检索技术 的背景和意义并给出本文的研究内容。 第二章对元搜索引擎进行了概述，主要包括元搜索引擎的原理与结构，元搜索引擎 结果的处理方法、以及元搜索引擎发展的优势与面临的问题。 第三章对个性化信息检索技术的理论与技术进行了详细的介绍，其中包括个性化理 论、个性化信息检索的分类，以及用户兴趣模型的获取与表示等，并分别介绍了信息检 4 中国石油大学( 华东) 硕士学位论文 索的基本技术。 第四章给出了元搜索引擎结果个性化排序算法的具体设计，包括网页的预处理、聚 类、宏观排序方法、微观排序方法等方面的详细叙述，并给出了创新点以及相应的实验 与数据。 第五章介绍了基于元搜索引擎结果个性化排序算法的个性化元搜索引擎系统( p s m ) 的设计情况，介绍了该系统各个模块的功能。对系统进行了测试，并给出了测试数据和 数据分析。同时，也指出了系统存在的问题，给出了系统今后改进的思路和方向。 第六章是对全文的总结以及对未来研究的展望。 第2 章元搜索引擎概述 第2 章元搜索引擎概述 元搜索引擎( m e t as e a r c he n 西n e ) 被称之为搜索引擎之上的搜索引擎。1 9 9 5 年华 盛顿大学硕士生e r i cs e l b e r g 和o r e ne t z i o n i 推出了第一个元搜索引擎，这一新型的网络 检索工具从此异军突起，发展迅速。这类搜索引擎没有自己的索引数据库，自身并不能 收集网页的信息，而是将用户提交的检索请求通过转换处理后提交给多个选定的独立搜 索引擎，并将所查询的结果通过整合处理后以统一的格式返回给用户。由于采用了优化 机制，元搜索引擎可以提供全面，准确的检索结果，与独立搜索引擎相比，具有信息覆 盖率高、扩展性能强，以及服务多样化的优点。元搜索引擎的研究特别是中文元搜索引 擎的研究是当前信息检索研究的一大热点。 2 1 元搜索引擎的原理与结构 元搜索引擎是一个五元组【5 1 ，m s e 吨，q m ，h m ，r m ，t m ，其中，e m 是成员搜索引 擎的集合，q m 查询条件集，h m 是查询条件变换集，r m 是排序方法，t r n ( t f i l 0 ) 是查询 结果选择的标准。所谓元搜索引擎，就是指在统一的用户查询界面与信息反馈的形势下， 共享多个独立搜索引擎的资源库为用户提供信息服务的系统，它充当着一个中间代理的 角色。图2 1 给出的是一个元搜索引擎的结构图： 图2 1 元搜索引擎的结构图 f i 9 2 一l t h es t 邝c t i l 北o fm e t as e a r c he n g i n e 6 中国石油大学( 华东) 硕士学位论文 元搜索引擎的工作原理是将多个独立搜索引擎作为一个整体，提供一个面向用户的 统一查询接口，用户的查询请求首先由元搜索引擎翻译成适应独立搜索引擎的查询语 法，分别发送给成员搜索引擎，由成员搜索引擎负责完成实际的信息检索任务，元搜索 引擎将返回的结果收集起来，通过比较分析，以一定的相关度算法对结果进行排序，最 终以统一的格式返回给用户。 元搜索引擎是一个具有双层客户机服务器结构的系统。用户向元搜索引擎发出检 索请求，然后元搜索引擎再根据发送请求向多个独立搜索引擎发出实际的检索请求，独 立搜索引擎执行检索请求后将结果传送给元搜索引擎，最后，元搜索引擎将多个独立引 擎的搜索结果整理排序后再传送给用户。元搜索引擎的基本结构由三部分【5 】组成： 1 检索请求预处理部分：负责用户的检索设置要求，包括独立引擎的调用，检索 时间的限制，结果数量的限制。用户也可以使用类似g o o g l e 等传统搜索引擎中的高级 检索功能，来定制个性化检索。 2 成员搜索引擎调度部分：负责把用户的检索请求“翻译 成符合独立引擎搜索 的格式。并且根据知识库中关于各个独立引擎的性能参数，结合当前的查询需要，找到 最适合此次查询的独立引擎。 3 检索结果处理部分：将各个独立引擎的查询结果整合处理。首先，将各个独立 引擎送来的结果中重复冗余的、无效的结果去除，根据用户的历史查询和使用记录，对 结果所链接的文档进行评分，最后给出一个符合用户要求的结果序列。 2 2 元搜索引擎结果的处理方法 2 2 1 元搜索引擎结果处理约束条件 结果的集成处理作为元搜索引擎的一部分，对于为用户提供高质量的结果序列，起 到了非常重要的作用。根据研究人员近年来的研究表明，元搜索引擎在结果的合成上， 具有一般性的约束条件【6 】。 根据元搜索引擎( m s e ) 中各个独立引擎的结果集合之间的关系，我们可以把m s e 的 结果合成划分为四种基本类型：对等，包含，不相交和交搭。根据m s e 中独立引擎的 查询结果序列中文档之间次序的关系，可以把m s e 的查询结果合成划分为另外两种基 本类型：相容和冲突。对于给定的查询条件q ，假设s e i _ 和s e j = 是任意两个成员搜索引擎，r i ( q ) 和鹦( q ) 分别是s e i 和s e j 查询结果集合，如果对任意两 个同时属于r i ( ( 1 ) 和玛( q ) 的x ，y 有r i ( x ，q ) q ( y q ) ，当且仅当i ：j ( x ，q ) ，u = q = d ，使得对每一个v 4 ( 4 d ) ， 2 l 第3 章个性化信息检索 j q ，( q c ) ，z q ，同时还要使得目标函数q ( c ) 达到最值，其中行为文本的总数 目，七为聚类最终的个数，且qnc ，= ，j l 。 在计算文档间相似度时，一般采用余弦值法；两个文本的d l ，d 2 是相似度可以表示 成 跏( 叱畋) - c o s ，畋) = 编 ( 3 - 1 ) 由于文档向量的长度对相似度的计算影响比较大，因此，文档向量的长度必须相同。 d = d 删d 8 = ( 扩( d ，) ，矿k 纩( d ，f 2 ) ，易信矿( d ，_ ) o f ? 矽( d ，1 ) 2 + f 琵纩( d ，2 ) 2 + + 疗( d ，庸) 2( 3 - 2 ) 其中，= l ，其余弦相似度即为两文本向量的点积，即跏( 4 ，畋) = 西。畋 聚类的质量的高低通常取决于聚类算法所使用的相似度测量的方法和实现方式，同 时也取决于该算法能否发现部分或者全部的隐藏的模式。 图3 一l 文档聚类的一般体系结构哺1 f i 9 3 lt h ea k h i t t l i 聆o fd o c u m e n tc l u s t e r i n g 文档聚类【2 8 l 算法的输出一般为文档集合的一个划分。这种划分的形式也有可能是 一个层次结构( 如a h c 算法) 或者二维平面图( 如s o m 神经网络) 。文档聚类一般采用图 3 1 所示的体系结构。系统首先需要构造聚类特征空间，并将所有文档表示为特征空间上 的向量。由于聚类迭代过程中经常需要根据文档( 或者中间类) 之间的相似度来进行合并 或者划分等操作，因此为提高运行效率，可以预先生成文档之间的相似度矩阵。系统运行 过程中，可以到矩阵中检索任何两个文档的相似度。作为一种自然语言处理应用，文档聚 类具有高维和与语义相关的特点，因此影响文档聚类结果的因素除了文档聚类算法的选 中国石油大学( 华东) 硕士学位论文 择以外，还包括语义问题的处理和降维问题。这些问题也是目前文档聚类研究中的难点 和热点。 聚类的应用领域很多，主要包括以下几个领域： 用于数字图书服务，通过s o m ( 自组织映射) 等方法，可以将高维空间的文档向量拓 扑保序地映射到二维空间，使得聚类结果可视化和便于理解； 用于用户兴趣模型的建立。通过对用户的浏览记录以及收藏夹里的记录通过聚类的 方法对这些信息进行挖掘，以此来发现用户的兴趣信息，通过兴趣模型来对提供信息过 滤和信息主动推荐服务； 用于搜索引擎返回结果的处理。比较典型的系统有v i v i s i m o ( h t t p ： r 、 r 、v v i v i s i m o c o m ) 和i n f o n e t 姗睇( n p ：、硼mi n f o n e m a r e c o m ) 等。系统允许用户输入检索关键词， 而后对检索到的文档进行聚类处理，并输出各个不同类别的简要描述，从而可以缩小检索 的范围，用户只需关注比较有希望的主题： 作为多文档自动文摘等自然语言处理应用的预处理步骤。例如，哥伦比亚大学多文 档自动文摘系统n e ws b l a s t e r 。n e w sb l a s t e r 将每天发生的重要新闻进行聚类处理，并 对同主题文档进行冗余消除、信息融合、文本生成等处理，从而生成一篇简明扼要的摘 要文档； 用于文档的自动整理，利用聚类技术对用户提出的查询记录进行聚类分析，根据聚 类结果来对搜索引擎的f a q ( 常见问题解答) 进行更新。 几种常见的聚类算法 k m e a i l s 【2 9 1 算法是一种典型的基于划分的方法。其基本原理是首先选择k 个文档为 初始化据聚类点，然后根据簇中对象的平均值，将每个文档赋给最类似的簇，并更新的 平均值，然后重复这一过程，直到簇的划分不再发生变化。k m e a n s 的算法复杂度为 d ( k l n ) ，其中l 迭代次数，n 为文档个数，k 为类别个数。 k m e a n s 算法本质上是一种贪心算法。可以保证局部最小，但是很难保证全局最小。 另外该方法需要预先指定k 值和初始划分，从而容易使聚类结果受到影响。为此人们提 出了一些相应的解决方法。如可以将算法执行多次，取最好的一次作为最终结果。采用 遗传算法来优化k 值，也有人提出一种基于自动发现类别个数的聚类算法。同时，k - i n e a i l s 算法中，在已知k 值的情况下，如何获得初始聚点也是需要解决的问题。有人提出的 g l o b a ll 【2 m e a i l s 方法【3 0 1 对初始聚点的选择提出了新的方案，而不是随机选择聚点。 基于s o m 神经网络的文本聚类方法是由t k o h o n e n1 3 l 】首先提出的。使用s o m 神 第3 章个性化信息检索 经网络聚类的基本流程是： 1 首先对输出层各个神经元所代表的权值向量赋小的随机数，并归一化处理。神 元的向量维数与输入文档向量的维数相同； 2 从训练集中随机选取文档向量，作为s o m 网络的输入； 3 计算输入文档向量与各神经元向量的相似度，相似度最大的神经元将获胜； 4 获胜神经元及其邻域内的神经元调整权值，权值调整的幅度一般采用随时间单 调下降的退火函数； 5 通过调整权值，获胜者及其邻域内的神经元和输入文档模式更加接近，因此使 这些神经元以后对相似输入模式的响应得以增强。通过使用大量训练文本训练网络，最 后使输出层各节点成为对特定模式类敏感的神经细胞，对应的向量成为各个输入模式类 的中心向量。 表3 1 聚类算法性能比较嘲1 i a b i e 3 - 1p e r f o m a n c ec o m p a r i s o no fc i u s t e r i n ga i g o r i t h m s 对脏数据和异常数据对数据输入顺序 聚类算法算法效率聚类形状 高维性 的敏感性的敏感性 k m e a n s 一般凸形或球形敏感不敏感一般 c u r e 较高任意形状不敏感不敏感好 b i r c h 高凸形或球形不敏感不敏感一般 d b s c a n一般任意形状敏感敏感 一般 c l i q u e较低 凸形或球形一般 不敏感好 基于密度的方法( d e n s i t ) r - b 嬲e dm e m o d s ) ：是把具有足够高密度的区域划为簇，因 而可以得到任意形状的聚类结果。基于密度的方法与其它方法的一个根本区别是：它不 是基于各种各样的距离的，而是基于密度的。这样就能克服基于距离的算法只能发现“类 圆形 的聚类的缺点。这个方法的指导思想是，只要一个区域中的点的密度大过某个阀 值，就把它加到与之相近的聚类中去。d b s c a n 算法通过不断生长足够高密度区域来进 行聚类，能从含有噪声的空间数据库中发现任意形状的聚类。其中这种方法将一个聚类 定义为一组“密度连接 的点集。 表格3 1 给出了几种典型聚类算法的性能比较。 中国石油大学( 华东) 硕士学位论文 3 2 3l u c e n e l u c e n e 是印a c h e 软件基金会j 蜘项目组的一个子项目，是一个开放源代码的全 文检索引擎工具包，它并不是一个完整的全文检索引擎，而是一个全文检索引擎的架构， 提供了完整的查询引擎和索引引擎，以及部分文本分析引擎。l u c e n e 的目的是为软件开 发人员提供一个简单易用的工具包，以方便的在目标系统中实现全文检索的功能，或者 是以此为基础建立起完整的全文检索引擎。 l u c e n e 已经在许多搜索引擎技术项目中得到了广泛的应用和研究。它提供了灵活的 a p i 函数接口和可以定制的数据存储结构，可以方便的嵌入到各种应用中，以实现具体 的全文检索系统。 在本文中，l u c e n e 被设计为一个试验工具，通过对l u c e n c 工具进行基于中文的改 装，使得l u c e n e 具有了有效处理中文的能力，应用于下文中测试特征词选取方法的性 能。 基于中文处理l u c e n e 的改进策略 在l u c e n e 中，需要对索引文档和检索关键词进行切分处理，由于l u c e n e 只能对中文 采用单字切分或者双字切分，而不是中文真正意义上的根据词语的含义进行的分词，因 此会严重影响检索的精确度。比如检索关键词“人民 时，需要首先将“人民 切分成 “人”和“民”，然后在索引中查找这两个字，如果某个文档中，仅仅含有“人 和“民： 两个汉字，而不是“人民”这个词语，同样会被当作检索结果返回给用户。 为了避免上述情况的发生，采用的办法是将中文分词接口添加到l u c e n e 中，从而 提高了检索的精度。同时，相对于单字切分，对关键词分词处理得到的词条数量远远小 于字的个数，因此可以降低关键词与文档相似度计算的时间复杂度，使得检索具有更高 的效率。 在加入分词模块后，虽然提高了检索精度和检索效率，但是由于词条的数量巨大， 使得索引变成了单字与词的混合索引，相对于单字切分( 索引中最大的词条个数不会超 过2 l 0 0 0 ，即汉字的总个数) 失去了对索引中词条数量的有效控制，因此还需要针对 中文文档，采用某种策略来对文档进行预处理，过滤掉文档中冗余的字和词，使得建立 的索引可以对词条有效的控制。 基于中文处理l u c e n e 的改进方法 l u c e n e 对各种语言的处理都是由内部的分析器( a n a l y z e r ) 完成的b 朝。分析器由两 个部分组成：分词器( t o k e n i z e r ) 和过滤器( t o k e n f i l t e r ) 。分词器负责对文档和关键词 第3 章个性化信息检索 切分，过滤器负责对切分的词进行过滤处理，比如去除敏感词、转换大小写等。 添加中文分词接口和文档预处理接口就是分析l u c e n e 分析器的结构，对分析器和 过滤器的改进过程。通过重新编写分析器基类a n a l y z e r 的子类，使得字符流通过分词器 ( ，r o k e n i z e r ) 和过滤器( t 0 k e n f i l t e r ) 时不是被单字切分，而是真正意义上的分词处理，同时 通过在过滤器( t o k e i l f i l t e r ) 中添加文档预处理操作，来达到去除索引冗余的目的。图3 2 给出了优化后的l u c e n e 的结构图。 图3 2 优化后的l u c e n e 的结构图 f i 9 3 2 t h ei m p m v e da m h i t e c t u mo fl u c e n e 图3 3d 1 和d 2 的检索耗时 f i 9 3 - 3t i 啪一c o n s 岫i n g0 fs e a r c h i n go nd 1a i l dd 2 通过对一批文档采用单字切分建立索引和中文分词优化后建立索引，然后采用1 0 中国石油大学( 华东) 硕士学位论文 个双字关键词来对两种索引检索。对检索时间进行统计。 如图3 3 所示，在图中，d l 代表单字切分建立索引，d 2 代表中文分词优化后建立 的索引，k 表示检索关键词( 索引文档中一定含有这个词) 。由于采用双字检索关键词， 同时这个词在索引中存在，因此在检索d 2 时，关键词与文档的相似度是只需要计算一 次即可，而检索d l 时，需要首先将关键词切分成两个汉字，因此需要计算两次，因此 d 2 的检索效率在这次检索耗时实验中是d 1 的两倍，同图3 3 给出的实验统计数据是一 致的。 2 7 第4 章元搜索引擎结果个性化排序算法的设计 第4 章元搜索引擎结果个性化排序算法的设计 4 1 元搜索引擎结果个性化排序算法的设计思路 4 1 1 元搜索引擎结果个性化排序算法的意义 由于独立搜索引擎普遍存在着索引数据库对网络的覆盖率比较低的问题，因此用户 在查找信息时，需要经常切换搜索引擎来满足查找信息的要求，同时搜索引擎返回的结 果中存在着大量的与检索关键词不相关的结果造成信息过载( i n f o m a t i o no v e r l o a d ) 问 题，使得搜索引擎的精确度较低。个性化的搜索引擎可以有效解决信息过载问题，而个 性化元搜索引擎则可以同时解决信息过载和独立搜索引擎网络覆盖率低的问题。 个性化元搜索引擎的研究有两个主要方向：独立搜索引擎的个性化调度研究与元搜 索结果的个性化排序研究。本文研究的是基于元搜索结果的个性化排序算法。元搜索引 擎结果个性化排序算法的关键是依据用户的兴趣对元搜索引擎返回的结果进行处理，使 整合后的结果具有更高的质量，并且更符合用户的查询意图和用户的需求。 4 1 2 个性化排序算法解决的具体问题 目前检索结果的排序问题面临着两个主要问题： 1 由于用户的查询关键词对用户的查询意图描述不清晰，造成了检索结果的种类 多样化。 用户在检索信息时，仅靠几个关键词很难描述清楚用户的真正查询意图，使得搜索 引擎返回结果的内容往往包含很多类别。比如在检索关键词“电影毕业生 时，返回的 结果中，包含了电影的简介、电影的影评，电影的下载等几个类别，而用户的真正查询 意图可能只是其中一两个类别的信息，在返回的结果序列中，不同类别的结果记录会混 合在一起，非常不利于用户的查找。 2 符合用户兴趣的检索结果不被重视。 往往用户查询自己感兴趣的信息的机率比较大，或者出于工作的需要，对某些类别 的信息会长时间的重复检索，因此，符合用户兴趣的信息对用户来说是非常重要的信息， 在对检索结果排序时，需要对用户感兴趣的结果特殊对待。 针对上述的问题，采用个性化的结果排序算法是一个重要的解决途径。 在以往的研究中，个性化排序算法是将用户的兴趣模型与结果记录逐一计算相 似度，根据相似度降序排列检索结果，最后形成一个基于用户兴趣的结果序列。这种方 中国石油大学( 华东) 硕士学位论文 法的缺点是： 1 检索结果与用户兴趣的相似度只是一个度量值，依靠兴趣度不能客观的确定哪 些结果是用户感兴趣的结果记录，用户只能主观的来判定，而没有一个定量的标准。 2 由于用户感兴趣的往往是某一类的信息，而且在这一类别中的结果对用户来说 往往都是重要的，而不需要再分清对哪一条结果记录更感兴趣。在这种情况下，单纯的 逐一计算用户与结果记录的兴趣度，没有实际意义，只会增加算法的时间复杂度。 针对这些问题，本文设计的个性化排序算法首先对检索结果进行聚类。将结果自动 划分为不同的类别，即同一类别的结果记录放置一个集合中，用户根据检索的需要直接 定位于某个类别，而不必在数量众多的结果序列中逐一查找。 为了找到用户感兴趣的结果记录，本文的个性化排序算法设计思路是，首先构建用 户兴趣模型来描述用户的兴趣信息，然后将用户兴趣模型与结果集合聚类处理后形成的 每个类别进行相似度的计算，根据相似度来对类别进行排序，同时也确定了用户感兴趣 的一类结果，而不是以往个