（计算机系统结构专业论文）www上链接分析算法的若干研究.pdf

w w wi 链接分析算法的符叶宄：摘受 摘要 w w w 的出现对传统的信息检索技术提出t y l 战，在传统的信息检索技术没有突 破性进展的现状下，从w e b 数据本身的特点出发，充分地挖掘w e b 上最充足的资源 一一超锰接，通过超链接进行搜索，建立有效的w e b 信息检索的模型，找到我们需 要的信息，本文正是本着这样一个前提，对页面的链接分析算法作了深入细致的研究， 从理论，算法和应用三个层次上，发掘超链接在w e b 检索方面的作用，主要包括以l = j 儿个方而： 首先，在对当前已有的链接算法进行分析和实现的过程中我们发现：基于不同的 数据环境和检索要求，对不同类型的链接，算法所采用的预处理方法、迭代规则和迭 代的终止条件都会影响查询的结果。提出对于封闭数据集合链接分析算法的约束条 件，通过对比封闭数据集合和实际的w e b 环境中的超链接的分布，将这些约束扩展 到实际w e b 环境中，更准确地预测链接分析算法的作用：实验表明在此约束条件下， 链接分析算法能够有效地提高检索效率。 其次优化与查询无关的事前链接分析算法，得到优化的事前链接分析算法 m o d i l i n k ( ) ，该算法给出了超链接的预处理方法，调整的归一化方法，完备的迭代终 止判定规则，实验表明该算法可以从整体上提高算法的迭代效率。 提出了基于页丽质量因素扩展的与查询相关的事后链接分折算法q h a l ( q u a l i t y b a s e dh y p e r l i n ka n a l y s i sa l g o r i t h m ) ，该算法将算法m o d i l i n k 0 得到的结果作为评价负面 质最的因素引入超链接的权值指定算法中，使超链接能够比较客观地反映所链接的页 面之目互相影响的程度；此外，将超链接的来源也考虑到超链接的权值指定上，结合 页而质吊因素提出另外一个优化的事后链接分析算法q h a 2 。对于优化的事后链接分 析算法我们从理论上证明了算法的正确性和可行性，并在实验中验证了这些算法。 、借鉴潜在爵义分析，千1 的方法，本文将矩阵奇异值分解；f 入事后链接分折算法中， 提出慕p s v d 分解的滤噪算法，运用矩阵的奇异值分解的方法进行无关页断和超链接 的滤嵘，并将其应用于与查询相关的事后链接分析算法的初始基本集合的构造；提出 j 优化的寥后链接分析算法q h a 3 ，q h a 4 ，算法有效地控制了主题漂移现象的产生， 为准确的查找提供r 个很好的途径。 w w w 【：链接分析筲法的甘十训f 究：摘要 关键资源的发现是利用超链接米进行精确查找的一个很好的应用，我们提出了利 用事一j 链接分析算法提取关键资源的三种解决方案。通过对封闭的实验数据集合 ：的 实验结果的分析，我们发现链接分析算法对局部的准确查找卜分有效。链接分机司以 为哭键资源的发现提供算法支持。而关键资源的发现可以考虑在面向领域的搜索引擎 巾得到很好的应用。 基于链接分析的页面排名的探讨，本文选用了贝叶斯网作为基本框架，将超链接 这个因素合理地扩展进检索模型中，并且提出了多元特征组合的新的页面排名算法。 实验表明该页而排名算法可扩展性好，与传统的页面排名算法相比，能够更好地满足 用户的信息需求。 关键词：w e bi r ，超链接，链接分析算法， 事前链接分析算法，事后链接分析算法， 信息检索，p a g e r a n k 算法，h i t s 算法， 矩阵奇异值分解，b a y e s n 络，t r e c 。 w w wi 懈接分析算浊的若十研究：摘复 s t u d i e so ft h eh y p e r l i n ka n a l y s i sa l g o r i t h m si nw w w l i uy u e ( c o m p u t e ra r c h i t e c t u r e ) d i r e c t e db yp r o l 、e s s o rl ig u o j i e t i l ee m e r g e n c eo fw w wi n t r o d u c e dn e wc h a l l e n g e st ot h et r a d i t i o n a li n f o r m a t i o n r e t r i e v a l ( i r ) t e c h n o l o g i e s w e bs e a r c h i n gi n v o l v e si nt h et h e o r i e sa n dt e c h n o l o g i e so f a p p l i e dm a t h e m a t i c st h e o r y ( s u c ha sg r a p ht h e o r y , m a t r i xt h e o r ya n da n a l y s i s ) ，d a t am i n i n g a i n i 。p - e t c t h ec o r eo ft h es e a r c he n g i n et e c h n o l o g yi st of i n dab e t t e rs e a r c h i n g a l g o r i t h mf r o mt h ec h a r a c t e r i s t i c so ft h ew e bd a t a ，h y p e r l i n k sa m o n g t h ew e bp a g e sc o a l b eu s e dt om i n em o r eu s e f u li n f o r m a t i o n s e a r c h i n gw i t ht h eh y p e r l i n k sc a l lc r e a t em o r e e f f e c t i v ew e bi n f o r m a t i o nr e t r i e v a lm o d e l t h i sd i s s e r t a t i o ns t u d i e sh o wh y p e r l i n k sa f f e c t t h ew e bi rt h e o r i e s ，a l g o r i t l m a sa n da p p l i c a t i o n s f i r s t ，b yc o m p a r i n gt h eh y p e r l i n ka n a l y s i sa l g o r i t h m sa g a i n s t d i f f e r e n td a t a e n v i r o n m e n ta n dr e t r i e v a lr e q u i r e m e n t s ，ia n a l y z e dh o wt h es e a r c hr e s u l t sa r ea f f e c t e db y t h em e t h o d st op r o c e s sd i f f e r e n tt y p e so fl i n ka n dt h em e t h o d st os e tt h ei t e r a t i o nr u l e sa n d t e r m i n a t i n gc o n d i t i o n st h e nip r o p o s e dr e s t r i c t i n gc o n d i t i o n sf o rt h eh y p e r l i n ka n a l y s i s a l g o r i t h m si nc l o s e dd a t as e t b yc o m p a r i n gt h eh y p e r l i n kd i s t r i b u t i o n so ft h ec l o s e dd a t a s e ta n dt h er e a lw e be n v i r o n m e n t s ，ie x p a n d e dt h er e s t r i c t i n gc o n d i t i o n st ot h er e a lw e b e n v i r o n m e n t s i nt h i sw a yt h ee f f e c to ft h ea l g o r i t h mc a nb ep r e d i c a t e dq u a n t i t a t i v e l ya n d t h ee x p e r i m e n tr e s u l t ss h o wt h a tt h er e t r i e v a le f f i c i e n c yc a nb ei m p r o v e dg r e a t l y t h e n ，n e wo p t i m i z e dh y p e r l i n ka n a l y s i sa l g o r i t h m sa r ep r o p o s e d o n eo ft h e mi st h e m o d i l i n kt h i sq u e r y i n d e p e n d e n t a p p r o a c hi n t r o d u c e dn e wp r e p r o c e s s i n ga l g o r i t h m s a d j u s t i n gs t a n d a r d i z a t i o nm e t h o d sa n di t e r a t i v et e r m i n a t i n gc o n d i t i o n s i ta l s om o d i f i e dt h e i t e r a t i v et o r m u l ao fp a g e r a n ka l g o r i t h mt oi m p r o v et h ew h o l ei t e r a t i v ee f f i c i e n c yo ft h e a l g o r i d l m i h ce x p e r i m e n tr e s u l t ss h o wt h a tt h em o d i l i n kc a nc o n v e r g e n c et h s t e rt h a nt h e p a g e r a n ka l g o r i t h ma n du n d e rt h er e s t r i c t i n gc o n d i t i o n st h er e t r i e v a le f f i c i e n c yc a nb e i m p r o v e d o t h e ro p t i m i z e dh y p e r l i n ka n a l y s i sa l g o r i t h m sa r er e l a t i v et ot h eq u e r i e s c o n s i d e r i n g r e l a t i o n s h i pb e t w e e nt h ew e bp a g eq u a l i t ya n dt h ec h a r a c t e r i s t i c so ft h eh y p e r l i n ka n a l y s i s a l g o r i t h m ，ip r o p o s e dq h a l ，f lq u a l i t yb a s e dh y p e r l i n ka n a l y s i sa l g o r i t h mt h ec o r eo f t h i s a l g o ti t h mi st o t a k et h ev a l u ef r o mt h em o d i l i n ka st h ew e bp a g eq u a l i t yf a c t o l 。i nt h e 川 w w w 卜链接分析算法的打h 丌宄：摘受 w e i g h ta s s i g n i n go ft h eh y p e r l i n k s ，w h i c he x p r e s st h em u t u a l l yr e i n t b r c e m e n tb e t w e e nw e b p a g e so b j e c t i v e l y r 1 1 h e l i n k a g er e l m i o n s h i p sa m o n gt h ew e bp a g e sm o r eo rl e s sr e v e a lt h e i rm u t u a l s e m a n t i cc o n n e c t i o n s a ni n n o v a t i v em e t h o dt oe l i m i n a t en o i s ep a g e sf r o mt h es e to f r c t ti e v e dp a g e st a k e sa d v a n t a g eo fs i n g u l a rv a l u ed e c o m p o s i t i o no fm a t r i xa n dr e v e a l st h e r e l a t i o n s h i p sa m o n gc o n c e r n e dw e bp a g e sa tad e e p e rl e v e l t h en u m e r i c a le x p e r i m e n t r e s u l t ss h o wt h ee f f e c t i v e n e s sa n df e a s i b i l i t yo ft h ea l g o r i t h mt h i sa l g o r i t h mc a na l s ob e u s e ds o l e l yt of i l t e ru n n e c e s s a r yw e bp a g e sa n dr e d u c et h em a n a g e m e n tc o s ta n do v e r h e a d o fw e b b a s e dd a t am a n a g e m e n ts y s t e m s b a s e do nt h i sn o i s ef i l t e r i n ga l g o r i t h ma n d q h a1 ，o p t i m i z i n gh y p e d i n ka n a l y s i sa l g o r i t h m s ( q h a 3 ，q h a 4 ) t h a ta r er e l a t i v et ot h e q u e r i e sw e r cp r o p o s e d t h ee x p e r i m e n t s a r eo nt h et r e cd a t as e tm i dw eg o tb e r e tr e s u l t s t h a nt h eh i i 、sa n dd e c sa l g o r i t h m s a tl a s t ，ic o n s i d e ra p p l y i n gt h eh y p e r l i n ka n a l y s i sa l g o r i t h mi n t ot h en e x tg e n e r a t i o n i n t e l l i g e n ts e a r c he n g i n e ，a n de x p a n d i n gt h eb a s i cl i n k a g ea n a l y s i sa l g o r i t h m st o m o r e g e n e r a lw e br e t r i e v a ll i k ek e yr e s o u r c ed i s t i l l a t i o na n dn a m e dp a g ef i n d i n g t h er a n k i n g p r o b l e m sa r ea l s ow o r t hf u r t h e ri n v e s t i g a t i o n iu s eb a y e sn e t w o r kt ob r e a kl i m i t so ft h e t r a d i t i o n a li rr e t r i e v a lm o d e l sa n dc o m b i n et h ec o n t e n tf a c t o r sw i t ht h eh y p e r l i n kf a c t o r s w i t h i nt h eb a y e sm o d e l s e v e r a ln e wr e r a n k i n ga l g o r i t h m sc o m b i n i n gm u l t i c h a r a c t e r i s t i c s a r ep r o p o s e d c o m p a r i n gt ot h et r a d i t i o n a lr a n k i n ga l g o r i t h m ，t h ed e m a n d so ft h eu s e r s c a l 3b es a t i s f i e de a s i l y k e y w o r d s ：w e bi r ，h y p e r l i n k ，h y p e r l i n ka n a l y s i sa l g o r i t h m 、p a g e r a n ka l g o r i t h m ， h 1 1sa l g o r i t h m ，p r el i n ka n a l y s i sa l g o r i t h m ，p o s tl i n ka n a l y s i sa l g o r i t h m ，s v d ，b a y e s n c t w o r k ，7 i r e c 声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得 的研究成果。就我所知，除了文中特别加以标注和致谢的地方外，论文中 不包含其他人已经发表或撰写过的研究成果。与我一同工作的同志对本研 究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 作者签名：趔劫日期：。略， 关于论文使用授权的说明 中国科学院计算技术研究所有权处理、保留送交论文的复e | _ | 件，允许论 文被查阅和借阅；并可以公布论文的全部或部分f j 容，可以采用影印、缩 印或其它复制手段保存该论文。 作者龋乏哆翮虢归乏隰洲 第一章绪论 第一章绪论 因特网( i n t e r n e t ) 为全世界人民 辟了一个兆同的、全新的大地。人们在这个虚 拟的世界中，以一种全新的方式进行交流。 11 课题的来源吲9 9 8 0 3 0 4 1 3 本文的工作是国家9 7 3 课题“基于i n t e r n e t 超大规模知识榆索算法与应用”( 课题 编号：g 1 9 9 8 0 3 0 4 1 3 ) 的一部分。 该9 7 3 课题定位为研究对海量网卜信息进行高性能、高准确度知识检索的相关理 纶和方法，试图把传统的信息检索方法和传统的知识处理的方法相结合，借鉴囤际上 在许多领域行之有效的求解难解问题的高性能算法，探索超大规模知识检索的新理论 和新方法，以此为指导对i n t e r n e t 上火量结构化、半结构化以及非结构化的各类信息 提供一致化的知识表达、检索、挖掘等工具，并最终实现i n t e r n e t 上的海量信息高性 能、高准确度、智能化的知识检索。 课题研究主要定位在五个主要方向上，包括知识检索的计算模型和元信息演算、 模式推理与自然语言语义计算、网络结构化知识挖掘和网络社区分析、聚类分类信 息抽取和计算优化、分布式跨平台统一榆索等。在这血个方面的研究巾，关键的问题 是其中涉及到的n p h a r d 求解，包括超图的划分、超大规模数据的属性最小约减等。 本课题通过对五个方向上问题的研究，预期在以f 几个方面取得明显的效果：现 实的异构数据源的统一知识表示与快速推理，超大规模知识的快速索引、智能化标引、 高效率的信息查询与获取，自动化网络社医的抽取与智能化服务，筇三代高精确、个 性化、智能化搜索引擎。在此基础卜获得相弛u 新的、有实际心用价值的理论和算法， 从而带动整个i n t e r n e t 上大规模信息服务产、1 p 的真二质的飞跃。 课题总的目标是：建、l ：一套完整的超大规模知识榆索的理论乖t 方法体系，努力挑战其 巾主要的重大科学问题，实现日f 述关键技术的突破，形成完整的实用软件包，构成一 个能够针对真实的网上海量数据( 1 tb y t e s 以上) 进行实用化知识检索服务的实验i r 台系统，并把它的主要的实用的成熟功能初步发展成有竞争力的软件产品。 ，国科学院阱1 学化论文w w wl 链镁分析算法的符干研究 f l 刚络结构化知识挖掘和网络社区分析方面，结合文本语义信息和领域知识，对 网络联接的有向拓扑图，通过超链接的分析来挖掘深层隐藏的重要信息，重点在具有 网络应用背景的特征抽取研究和信息行为变化的分析。同时，研究大规模属性的约减 和划分等算法，有针对性地研究网络社区的聚集、c o r e 抽取等核心问题。相关的算 法和理论可以为网络社区自动划分、主动化信息服务、快速准确的网站信息检索等提 供底层计算平台。 1 2w w w 上链接分析算法产生的背景 信息检索是计算机科学的一个分支，它的主要目的就是对于个用户的查询，在 给定的文档集合中，能够找到所有与该查询相关联的文档，在w w w 出现以前，大 多数的信息检索系统都是安装在图书馆里的文献检索系统，而检索算法也基本上都是 基丁：文档的关键字的检索。然而w e b 的出现改变了这一切，它的数据有着与传统信 息检索所处理的数据截然不同的特点。 12 1w w w 上数据的特点 w w w 的发展要追溯到二十世纪八十年代，当时人们没有预料到它今天的影响。 对丁l | w e b 的规模，其增长之迅速已经是尽人皆知，截l l ：到2 0 0 3 年2 月2 7rg o o g l e 检索的页面数已经达到3 ，0 8 3 ，3 2 4 ，6 5 2 ，而g o o g l e 能检索到的页面数仅仅是整个w e b 的一部分。除了文本数据以外还有诸如图象，卢音等一些其它的媒体文件。这样，整 个w e b 可以看成个十分巨大，无结构但普遍存在的“数据库”，这就引发了寻找有 效的工具来管理、检索和过滤这些“数据库”犟的信息。然而，目前的榆索系统均存 在查准率、查全率不高的现象，这种现状无法适应用户时高质量的网络信息服务的需 求；同时电了商务以及各种网络信息服务迅速兴起，使原有的网络信息处理与组织技 术无法赶上这样的发展趋势，w e b 信息挖掘就是在这样一种环境i 、应运而生的，并迅 速成为网络信息检索、信息服务领域的热点之。 w e b 数据信息与经典i r ( i n f o n n a t i o nr e t r i e v a l ) 所处理的信息比较起来有它自己的 特点m m m 9 9 如w 1 叫9 8 】： 1 ) 分伽式的数掘：由于物理结构l 二的分布式的拓扑结构，使得数据分散在不同的计 一翌二奇塑一堕一 算、r 台1 。这些训算机之叫以没有预先定义的拓扑结构连接起来，刚络卜的有效带宽 经常发，| - 变化。 2 ) 火量的( 高百分比的) 巧i 稳定的数击噼：盯j 二i n t e r n c t 的动态性，新的计算机和数据 很容易被添加或移动( 4 0 j ) ，例如：当域名、文件名改变或者消失时，已经失效的 超链接我们还要处理。 3 ) 规模巨大：w e b 以指数级在增长，而且页面的数量巨大。 4 1 无结构的冗余数据：以h t m l 形式存在的w e b 页面，本身就没有良好的结构，包 括镜像和重复页面，内容的重复率大约有3 0 ，语义的重复率一j 。能会更高。 5 1 数据的质最差：我们可以把w e b 看成是一种新兴的出版媒体。与传统的出版媒体 不同的是，它的大部分出版过程不包括编辑的过程。所以就难免会有各种各样的编辑 错误的发生和存在( 包括印刷，语法，扫描等等错误) 。 6 ) 异构的数据：今天w e b 几乎覆盖了全球所有国家，内容基本上包括全部的学科、 领域、语言，跨越不同的政治派别、宗教信仰。w e b 上的各网站、页面分属不同的组 织机构，使用w e b 的目的从严肃的科学研究到政治宣传、谋求商业利润、娱乐消道 无所不有。w e b 页面的风格、创作方式也是五花八门的。这些异构数据的类型还在不 断地增加，而每一种数据类型需要不同的方法来处理。 w e b 数据的特点以及它的快速增长，一个直接的结果就是w e b 上信息的极大丰 富。目前，不管对什么事物感兴趣，都町以在w e b 上发现相关的页面。这极大地促 进了科技的进步和人们生活方式的转变。但是，另一方面，随着信息的泛滥成灾，人 们也发现，要想找到满足自己需要的站点越来越田难。大量的站点涌现出来，反而使 人们不知所措了。测此迫切需要更有效的w e b 信息处理技术。 2 2 w e b 信息处理概述m y 。“。“”坩“8 枞“2 。o 。1 w e b 信息处理一般分为如下四个步骤：( 1 ) 资源发现，即检索所需的文档；( 2 ) 信 息选择和预处理，即从检索到的w e b 网络资源中自动挑选和预先处理得到专门的信 息：( 3 ) 概括化，即从t 尊个的w e b 站点以及多个站点之问发现普遍的模式；( 4 ) 分析， 刘挖弛i 内模式进 j 确认或者解释。 人们在w e bl 访问信息的方式非常有限，般情况下，有特定信息需求刚，人们 ，闯科学院i 礴i 。学位论文w w w 上链接分析算法的若 ? 研究 最常川的就是分类日录和搜索引擎查找所需要的信息。 天予分类h 泶“4 2 1 1 w e b1 何日一多分类目录( d i r e c t o r y ) 站点，如y a h o o ! m ”，y e l l o wp a g e s 。早期 搜索引擎站j j i 和分类翻录站点是泾渭分明的，但今天的大型搜索引擎站点一般都同时 提供检索功能和分类f 1 录。 分类目录可以由以卜特点定义： 1 ) 分类| = ；_ | 录基本足树形结构。每个节点( u 1 节点除外) 有数量不等的若干予声点。 少数节点存在不i p 一个父节点，闪此不构成严格的树结构。节点依据知【 本体 论( k n o w l e d g eo n t o l o g y ) 划分。分类目录站点的主页一般只显示一、二级节点。 2 ) 节点命名。每个节点有一个简短的命名。非根节点的全名是从根节点到该节点 的路径上的所有节点的名称的顺序组合。 3 ) 节点内容。每个节点收集有若干u r i 。，除了叶节点之外，每个节点有若干予 节点。 4 ) 维护。分类目录的维护是人工进行的，一般由站点雇佣专人分别负责各个了类， 不断跟踪w e bt 的信息，这是大多数站点的主流作法。另一类作法是由志愿人 员维护，个别站点可以让用户自己定制子树。 5 ) 可检索。每个节点由维护人员进行了适当的标引，标引内容对用户是不可见的， 基于该标引对目录可以进行检索，输入关键词，目录检索系统将输出与该查询 匹配的目录节点，按相关程度，进行降序排列。例如，y a h o o ! 对如何查询提供 三类结果：匹配目录、匹配站j _ 和匹配页面。 w c b 目录的自动构造一点是一个未解决的难题( o p e np r o b l e m ) ，当前w e b 上的目 录都是人工进行分类和标注，尚无自动算法。谈到w e b 目录的缺点，首先是人工方 式的吲有缺点：昂贵、更新慢、覆盖范阳柯限。此外使用) i i 方便，必须顺着分类树逐 级深入，到达所需要的信息；这就也意味着用户必须明白目录建立者的分类思路，但 这也比想象- ，的困难，因为每个人有1 i 同的看法。 以“非叽”为例，要想找到这类的信息，y a h o o ! 给出的干阿荚刚站分类。f ，“二作 碘”的位簧为： 根结点，区域，j 蚓家与地区，中国火陆( 香港) 健康与医药 疾病与症状， 肺炎 堂韭型世盟塞，共给出了5 个类别的相关网站的信息。 而存搜索引擎g o o g l e 上用“非媳”进行查询，共返网了3 2 8 0 0 个查询结果，笔者埘 4 检索结粜进行 n _ r 钏查看，直到3 0 0 个 二右的结果页面质餐都是拱本不错的。所以这 枰再起水搜索- 0 i 警仍将是w e b i r ( w e b l n f o i m a t i o n r e t r i e v a l ) 的主要二j ：其。 关j ：馊索引擎技术陋“一9 1 虽然w e b 搜索引擎出现的时间只有短短几年，但是它对于w e bi r 的影响却是| _ = _ ! 大的。锼索引擎使用方便，拥有数量巨大的用户，无论是目前，还是未来一段时刚的 搜索引擎，只要网络技术和i r 技术没有突破性进展，其基本结构应浚是稳定的。从 而向对象的角度分析，整个系统可以划分为五个剥象： 采集器( s p i d e r ) 索引器( i n d e x e r ) 页而库知识库( k n o w l e d g eb a s e ) 搜索器( s e a r c h e r ) 用户代理( u s e r a g e n t ) 这五个对象的关系如图1 1 所示。 ， 、? ，一、， ?1 f)r挺*#夕 ( 索q i * *，j f “ 弋( “” 、 7 、 ， 7 厂一，7、 ，页ir l | 库知u h r ( k n o wl c d g c h r 】) i 、 、， ，、 ， 挫嶷拊 ( s 一| _ c h o r ) 、 ， 图1 1 、， ，、 ， 牡n ，r川叫 ri， r 、 川鲴科。、产院冉十学位论文w w wi ，链接分 ! i 算法的若于研究 这h 个埘致存系统i 的功能证如它们的名字代表的那样，职责是很分明的。在某些系 统r f i ，索引器的部分功能可能被放在搜索器中实现，但这种情况也可以认为是搜索器 涮j j 了索引搽的功能。无论足分类目录还是搜索引擎，它的背后都是信息检索技术在 起作用，f 仃w e bl ：的信息检索算法不但要考虑类似于传统的信息检索算法甲面的基 r 关键字的检索算法，还要考虑页面之问的超链接信息。 1 2 3 当前w e b 检索存在的不足 当我们住w e b 上查找某方面信息的时候，通常会使用上面提到的w e b 分类| = 1 录或搜索引譬，如y a h o o ! ，i n k t o m i ，新浪，天网等。这时搜索引擎往往返回成千t 万 甚至上百力的结果页面，每个结果页面都有与查询的相关度评分，检索结果以每页十 几个到几十个结果的方式，按照与查嘲的相关度，以降序排列提交给用户。 用，。1 在查看搜索引擎返回的结果时，一般只会看头几页的结果，很少有人会看排 名在1 0 0 或2 0 0 之后的结果页面，几乎没有人会穷尽数量庞大的检索结果。 人们在查看搜索引擎返回的这些结果时，往往会感觉到它们多少与查询是相关 的，但检索质量还不够好。深入分析这个“质量不好”问题，可以归纳为下述缺点： 低质量页面。 有的页面只有寥寥数语包含的信息量很少；有的页面提供的信息价值非常般。 小同主题的页而。 一词多义是自然语言的常见现象；在不同领域，同一个词也常有常规之外的特定含义， 例如作为专有学术词汇、商标等。在查询时，用户往往感兴趣的是奇询词的某一特定 含义代表的信息内容，但是关于该查询词其他含义的页面也糅和在一起提交给用户。 重复页面。 出于镜像、常用文档的j 泛传播等原凼，w e b 上有许多合法的重复页面。此外，些 著名的页丽被别的站点拷贝或“挪作己用”，最典型的是y a h o o ! 的分类目录。研究表 明，w e b 上约6 0 的贝面是重复页丽【k u ( 。) 9 9 9 1 。 欺骗问题( s p a m m i n g ) 。 由j ：大多数搜索引擎的相关度评价是采用了经验规则来列于网页进行排名，而经验规 i l ! f j 大多数又爿：和基1 二关键训的检索算法相关联的。一些人就是利用搜索引擎的州美皮 评价策峪，侄i ! 己的页面叶，用不正当的手段，提高检中时的排名，这类现琢称为 笫章绪沧 “s p a r n l l l i n g ”。 甚罕有一一些公司专门进行这方研究，通过出售检索绱- 2 - 的排名来 谋取利蕊。 找制存处婵原始w e b 页面时发现些页丽的标题k 达数干词，填内容只是将与 该贝丽仁题相关的热门词语大量重复，这也是典型的针对搜索引擎的欺骗行为，欺骗 行为也导致质量一般的页面被优先提交给用户。 12 4 超链接与w e b 上的搜索算法 无论是分类1 7 录还是搜索引擎，它们的搜索算法都要处理负面与页面之问的超链 接。超链接到底怎样发挥作用呢? 作为超链接本身，例如指向某一个页面b 的一个 超链接可能包含在页面a 中，这个超链接对于基_ 丁：关键字的信息检索来讲可能没有 什么直接的作用，然而页面作者f 是通过超链接给浏览者提供了除了页面内容之外的 很重要的一些信息，起码从页面作者自己的角度来讲，他们认为链接指出去的是对浏 览者有川的信息。例如，一些链接是指导着浏览者回到站点的主页，通过歪新选择入 口点，对于浏览的路径进行重新定位：另外一些链接是指导浏览者转到对当前的页面 内容进行评论的页面上去，这种类型的链接就有可能是和当前链接讨论同个主题， 而且是质龟非常好的页面。 在搜索引擎中，只要用户提交了自己的查询，就可以得到数以万计的返回结果， 传统观点认为，衡量搜索引擎的两个重要指标是查准与查全。但是，经过深入研究可 以发现，要求一个搜索引擎同时做到查准与查全是不科学的，也是不必要的。片面追 求奄全率，只会带给用户大量的质量水平不等的信息资源，浪费用户的时间和财力。 用户实际卜需要的是高质量的信息来源去解决他面临的问题。所以，我们应该努力 出缩返回给用户的结果，把相关资源中最有代表性的和最重要的一部分介绍给用，。r ， 这就足以满h ! 用户的需求1 r 。在搜索引擎技术中，相关度是个重要的概念。它描述了 个检索结果和捡索请求之问的相关程度。相天度可以按照不同的规则进行计算。汁 算结果用个，rj _ 以比较的数值束表示，数值越高则相关度越高，这个结果就应该被搜 索引擎排存。个比较靠前的位置，以便用户可以更容易发现它。 怎样，j 能够判断出相关度的高低? 最为可行的办法就足充分利用w e b 页面比纯 义本更) j l 阵宙的超链接结构信息。正是超链接把数以亿计的网页组织成个知以网 舅j ? 兰! 型t ! i 1 ：! 笪堡塞二二! 型型j ：鳞 塑! 堑堑堕塑苎业型 络。m 、- 通过这毡超链接浏览网络，凭超链接指针以及他们从未i ! ；l 过面的人的指点， 从f m 牛运地找剑何价值的信息。鉴十超链接所具有的独特的表达信息的方式，w e b 信息检索在基于关键词的传统的信息检索技术不会有根本性的进展的前提下，充分地 发掘链接信息，利用它们来精炼与查询相关的文档是 一分有意义的，所以优化的链接 分析算法是搜索引擎和w e b 信息检索系统提高其效率的关键和核心。 皋于链接分析的页而质量评价技术使得搜索引擎能够将质量更好的页面排在结 果的较d d 列，大幅度地提高了检索结果的相关度，同时也可以有效地避免w e b 上的欺 骗问题( s p a m m i n g ) 。从而使用户感觉检索效果提高。9 8 年出现了第一个成功应用该 技术的搜索引擎g o o g l e 出l 。g o o g l e 的检索效果确实出众，迅速取得了成功，成为我 门身边几乎每个人的h 用搜索引擎，用它查找指定题目的文献效果尤其好。从9 9 年丌 始，链接分析技术得到了几乎所有w e b 上著名搜索引擎的采用，包括国内的百度“、 北大天网【1 、帅2 0 0 0 1 。然而没有任何一个搜索引擎完全公丌它们的链接分析算 法。链接分析算法一时问成为搜索引擎技术的一个研究热点，人们希望能够找到从理 论f ：可行，从实际中又很有应用价值的算法。 文本检索会议( t e x tr e t r i e v a lc o n f e r e n c e ，t r e c ) 是目前国际上信息检索领域一 年一度的学术交流与系统评测活动。它为参加者提供标准的数据集合、测试数据和标 准答案，所有的参加者以共同的方式向会议提交自己的系统运行结果并接受评测。在 标准测试方法出现之前，信息检索方法之问很难进行有意义的横向比较。t r e c 通过 提供标准的数据集和测试集，并规定统一的运行方式，使公正的评测成为可能。通过 卜年问的研究与探索，一些优秀的算法表现出了很高的性能，逐渐被学术界广泛接受。 列工、1 p 界和政府束说，由于t r e c 任务很接近实际问题，所以t r e c 中应用的检索技 术对它们有重要的实用价值。在t r e c ( t e x tr e t r i e v a lc o n f e r e n c e ) w e bt r a c k 子任务中， 一个很重要的目标就是验证一一下：基于链接分析的w e b 检索算法是否比单纯基于内容 的检索算法的效果要好一些。我们的研究小组代表中国科学院参加了t r e c2 0 0 1 及 2 0 0 2 1 1 9 w e b + f r a c k 任务，伍2 0 0 2 年的评测中，我们的检索系统在自来1 8 个国家和地区 的著名人学和研究机构提交的7 0 多个系统中的w e bt r a c kt a s k 的评测中取得了第j 名。通过参加t r e c ，使得我们对于w e b 检索从理论，算法和应用一i 个角度进行了探 侧，特别是划于链接分析算法进行了深入细致的研究。 3 本论文的贡献和组织 本论文1 ：要在w e b 结构的挖捌方面作了蜷探索性的研究，尤其足存贝m l 的链拔 分析算法方面作了些深入细致的研究。列标就是从理论，算法和应用二二个腻次i ：研 究链接在w e b 检索方面的作用。研究二r ：作主要包括以下几个方面： i ) 刈j 胁i j 有的链接算法进行了分析和实现。存实验中我们发现：基于1 i 同的数抓 环境和怜索要求，对不同类型的链接，算法所采仃 的预处理方法、迭代舰n l , q g f 迭代的 终i t 条伺都会影响查询的结果。 2 1 分析圳仃数据集台以及未来可能应用的数据环境，预测并分析可能的检索要求， 存改进已确算法的i _ j 时，提出优化的链接分析算法，主要包括： 提 _ 对于封闭数据集合链接分折算法的约束条件，通过对比封c 4 j 数据集合_ = f l | 实际的w e b 环境中的超链接的分布，将这些约束扩展到实际w e b 环境。p ，更准 确地预测链接分析算法的作用；实验表明在此约束条件下，链接分析算法能 够有效地提高检索效率。 优化与查询无关的事前链接分析算法，得到优化的事前链接分析算法 m o d i l i n k 0 ，在该算法中给出了超链接预处理，调整的归一化方法，完备的迭 代终d 二判定规则，实验表明陔算法从整体上提高了算法的迭代效率； 提出，基于页面质量因素扩展的与查询相关的事后链接分折算法 q t t a ( q u a t i t y b a s e d _ h y p e r l i n k a n a l y s i s ) ，该算法将算 法m o d i l i n k 0 得到的结果 作为评价页面质量的因素引入到超链接的权值指定上，使超链接能够比较客 观地反映它所链接的页而之间的互相影响的程度；借鉴潜在语义分析中经其 的矩阡奇异值降维分解技术，本文将该技术引入到事j 亏链接分机算法的橄集 合的f 曝旨消除工作中，对于与查询相关的事后链接分析迭代运钟的初始撼小 饿合运用矩阵的奇异值分解的方法进行无关页【坷和超链接的滤i | 豢垓算洲、仃 效j a j ；- f l i 9ri 二题漂移现象的产生，为准确的查找提1 1 ：i i 了。个很灯的途径。 3 1 揍j 二链接分析的搜索引擎的页嘶排名的探讨；选j l j 了螅叶斯网作为瑟本框架，将 超链接闪臻合理地扩展进检索模型h 捉了多元特征组合的新的页而排名算 ：_ “填 验表圳j 法页_ _ f | 例私鳙法町扩展性好，j 传统的页瓶排名算法槲比，能够亚灯j e # i i 址川 j 。的f ：i ，熄j 焉求。 j j 十：l 中随时lj 堂j 窭婆文w w w1 链蠼j 型碴塑尊蕾j h 乡 4 ) j 、i 川川肪分析：l u 以为信息推送，而向如领域的精确的信息检索提供底层的刊 钾、l f 。j i ! l 过刈封i 4 j 的实验数据集合一l i i j 实验结果的分析，发现链接分析算法列埘邝 f i j7 1 i i f i 价找1 分仃效。链接分析可以为关键资源的发现提