（计算机应用技术专业论文）基于时间链接分析的页面排序优化算法研究.pdf

江苏大学硕士学位论文 摘要 w ，e b 结构挖掘是从w w w 的组织结构、w 曲文档结构和链接关系中推导 知识的过程。目前基于网络的组织结构和链接关系进行挖掘的算法主要有两种， 其中有代表性的算法主要是l a r r yp a g e 等人设计的p a g e r a n k 算法。通过分析和 研究p a g e r a i l l 【、h i t s ，n m e d p a g r a n k 等基于链接结构的搜索结果排名算法，发 现传统的页面排序算法偏重于旧网页，使得一些旧的页面经常出现在检索结果的 前面。本文引入时间链接分析，使用爬虫抓起页面时h t r p 协议反馈回来的修改 时间作为页面和链接的时间，并综合考虑页面的出入链接个数和时间来计算页面 的权重值。所开发出的w 耶r 算法，能使新网页集在排序中上升，同时，高质量 的旧网页比普通的旧网页能获得较高的排序值。 本文研究页面排序算法，主要做了如下工作： 首先介绍w e b 结构数据挖掘，对w e b 链接分析的工作原理及相关定义进行了 详细的介绍，分析了w e b 链接分析的研究现状和主要工作，为下面章节介绍基于 超链接分析的页面排序算法打下了坚实的基础。 其次针对p a g e r a n k 算法存在的这些缺陷，引入时间链接分析，通过分析爬虫 w 曲s p l l l l 仅抓起页面时唧协议反馈回来的网页最后修改时间来表示网页年龄， 并在此基础上对网络的组织结构和链接质量以及时间序列进行挖掘。根据网页年 龄，提出了基于网页年龄衰减的页面排序算法a g e 姗r ，并进行了实验验证。 继而针对静态网页年龄不能满足当前网络的动态变化，以及页面时间的不确 定性，本文提出了兴趣区间的概念，并具体定义了动态网络环境下节点和链接的 时间戳，并在此基础上提出了新鲜度概念，以区分新旧页面，然后结合网页节点 质量因子开发出w t p r 算法，从而克服现有w r e b 超链接分析中的不足。 最后概要介绍了j a v a 版页面排序模块的实现过程，并给出了p a g e r a n k 计 算的大体思路，最终根据改进的页面排序算法对网页快照数据进行实验验证， 通过本程序验证，确定了w t p r 算法中的权重因子，并且这些优化策略改进了 搜索引擎的页面排序结果，同时保证了新旧两种页面的排序优化。 关键词：w r e b 结构数据挖掘，w e b 链接分析，p a g e r a j l l 【算法，兴趣度，w 1 1 p r 算法 江苏大学硕士学位论文 a b s t r a c t w r e bs t m c t u r em i n i n gt r i e st od i s c o v e rm ek n o 、l e d g en d mm el i r 出s t mc t | 【l r eo f r w wo fm eh y p e r l i l l l 【s ，w 曲d o c 岫e n ta l l di i l t e r l i i l k a g ea tt i l ei i l t e 卜d o c u m e n t l e v e l a t p r e s e n tm e r ea r em a i l l l y 帆om “n ga l g o r i m m sb a s e do nm ew e b sl i n k s t m c t u r ea n di i l t e r l i n k a g e ，a n dt h et y p i c a lo n eo fw h i c hi sp a g e r a i l kd e s i 印e db y l a r r ) ，p a g e e t c a f c e ra i l a l y z i i l gt h e s ea l g o r i t h m so fr 锄k i n gs e a r c hr e s u l t s l i k e p a g e r a i l j 【，h r r sa i l dt i m e d p a g r a n k 、m c ha r eb 硒e do nt h el i i 止s t m c t u r e ，o n e d e f e c tf o u n di st h a tm e 仃a d i t i o n a lr a n ka l g o r i t h m sf a v o u rt h eo l dp a g e sw r h i c hm a d e s o m eo i d p a g e s l i s t e do nt h e t o p 0 f廿l e s e a r c h i n g r e s u l t s s ot h e t e m p o r a l l i i l k - a n a l y s et e c h n o l o g yi s 劬d u c e d i n t 0t i l i s p a p e r ，u s i n g t h e l 弱t - m o d i f i e d 廿m e s t 锄pr e s p o i l s e db ym eh 兀pp r o t o c 0 1w r h e ns p i d e r 训i i 培t h e w e ba st h et i m e s 伽印o ft h ep a g e sa n dl i i l k s t h en e wi l p r o v e da l g o r i t l l mn m r c 孤m a k et l l en e wp a g e s 弱c e n di t sr a n ki i lt h er e s u l t ，w h i l em eo l dp a g e s 丽t hl l i 曲 q u a l i t yg e tl l i g e rr a i 止v a l u e st h a nc o m m o no l dp a g e s t h em a i l lc o n t r i b u t i o n so ft h ep a p e ra r ef o l l o w i i l g ： f i 俗tt h ew 曲s t m c t u r em m i i l gi sb r i e n yi n t r o d u c e d ，觚dt l l ep r i n c i p l e 姐dm e r e l a t e dd e f 埘t i o no ft h ew 曲l i n k a 1 1 a l y s ea r ep r e s e n t e di i ld e t a j l t h e nt h ew 曲 l i n k - a j l a l l y s e ss t a t eo ft h ea n 锄di t sm a j o rc o n t r i b u 廿o ni ss t i l d i e d ，w h i c hm a k e sa g o o df b u i l d a t i o nt oi i l t r o d u c et h ep a g e r 柚l 【i i l ga l g o r i t b a u s e d0 nm el i i 止- a n a l y s e s e c o n m y f o r t h e l i m i t a t i o no f p a g e r 加k m e1 e m p o r a l l i i 止a n a l l y s e t e c h n o l o g yi si i l t r o d u c e di i lo r d e rt 0i m p r o v ei t ，n l el 嬲tm o d i f i e dt i 】 n eo ft l l ep a g p s ， 恤c hi s r e s p o n s e db yt h e 舯p r o t o c o lw h e nt l l es p i d e rw r e b s p t l i l 政i sc r a w l i n g t h ew e b ，i su s e d 雒t l l ea g eo ft h ep a g e s0 nt h ew e b ，a n d0 nt l l i sb a s i st 0m i l l et h e w c bl i i 止s t m c t u r e ，l i n kq u a l i 哆觚dm et i m es e r i a l b 硒e do nt h ew e ba g et h e p a g e r a n k i n ga l g o r i t h ma g e - 1 帅ri sd e s i g n e d ，a l s ot h ee x p e r i m e n ti sv e r i f i e d f u n h e 咖o r ef o rt l l ef a c tt h a tt h es 嘶cp a g ea g ec 锄n o tm e e tm ed y n 锄i c c h a n g e so ft h e 、v e ba n dt h ew e bp a g e s u n c e r t a i n 劬t h ep a p e rp r o p o s e dm ed e f 埘t i o n o fi n t e r e s ti n t e a l ，a n dg i v ead e t a i l e dd e f i n i t i o no ft h en o d e sa n dl i n k s t i i i l e s t 锄p 江苏大学硕士学位论文 i i lt h ed v i l 锄i cw e be i i r o i 蚰e m b 舔e do nt h i st h er 1 0 v e l 哆v a l u ei sp r o p o s e di i l o r d e rt 0d i f f e r e n t i a t et l l eo l da i l dn e wp a g e s 1 l l e n i n b i i l e dw i t ht l l el i i l l 【q u a l i 哆t h e a l g o r i t h mw 耶r i sd e s i 印e d ，、h i c ho v e r c o m e st h ed e f i c i e n c yo ft h el i n k 。a n a l y s ea t p r e s c n t l 弱t l ym ed e s i g n 锄di m p l e m e n t a t i o no ft i l ep a g e r a i l k i n gs y s t e mi i lj a v ai s i n t r o d u c e d ，a n d l eg e n e r a l m p u t a t i o ns t e p i s g i v e na c c o r d i n g l y f i n a j l y l e h p r o v e dp a g e 聊1 k j n ga l g o r i t h mi sv e r i f i e dt h r o u 曲t e s t i n gt h ew e bp a g ss n 印s h o t a n dm ew e i g h tf a c t o r so ft h e 、 ，r 1 1 p ra r et h e r e f o r cd e t e 肌i i l e d 1 1 l ee x p e r i m e n t i m p r o v e dt h a tt h eo p t i n l 娩i 1 1 9s t r a t e g yu s e db yt h ew 1 p ra l g o r i t h md e v e l o p e d c a i l m a k et h eo l dp a g e sd e d i n e 锄dn e wp a g e sr o s ei i lt h er 幽gr e s u l t ，w l m e l eo l d p a g e so f h i 曲- q u a l i 锣g e th i 曲e r r a i l kv a l u e t h a l lc o m m o no l dp a g e s k e yw o r d s ：w ，e bd a t am i n i n g ，w e bl m k a l a l y s e ，p a g e r 砌【a l g o r i t h m ，i i l t c r e s t v 乱u e ，w 皿r g o r i t l u n 独创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究工作所取得的成果。除文中己注明引用的内容以外， 本论文不包含任何其他个人或集体已经发表或撰写过的作品成果。 对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式 标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：王厶高 日期：渺8 年月s 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校 保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和 借阅。本人授权江苏大学可以将本学位论文的全部内容或部分内容编入有关数 据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 保密口， 在年解密后适用本授权书。 本学位论文属于 不保密囹a 学位论文作者签名： 久妙3 年6 月箩日 互壤 指导教师签名：稻胪芭 九卯占年6 月；日 江苏大学硕士学位论文 1 1引言 第一章绪论 当前万维网仍在高速发展，其中蕴含了海量的信息可供我们利用。根据文献 【1 】最新的调查，目前整个w e b 超过了2 0 0 ，0 0 0 t b 的信息量，而且仍在快速的增长。 每周网络上大约有8 的新网页出现，网页的更新率超过1 5 ，以及增加的新链接 达2 5 左右【3 】。网络信息呈现爆炸式大幅度增长。网上的资源得到极大丰富，但 也充斥着大量的无用信息，人们迫切需要能从这些纷繁芜杂的信息中找到有用 知识的工具。如何有效地利用如此浩瀚的网络信息，成为信息工作者研究的热点 问题。 而万维网环境的复杂性( 分布、自治、异构、动态) 和万维网数据的复杂性( 不 规则、不精确、不稳定、半结构化或非结构化) 这些特点，决定了不能简单地用 传统挖掘技术处理w e b 数据。we b 信息检索是一个从we b 海量数据中检索用 户感兴趣信息的综合技术，它从一定程度上满足了用户对信息的需求，但返回 页面的数量依然十分巨大，其中很大一部分与用户的要求无关，用户不能快速、 准确地得到所需的有价值的信息，就w e b 上的知识发现而言，即使检索精度再 高，搜索引擎也不能够胜任。如面对浩瀚的网络信息资源，传统的文献计量学方 法就显得力不从心，因此，需要开发比信息检索层次更高的新技术相应地网 络信息计量学( w e b m e t r i c s o r c y b e r m e t r i c s ) 就应运而生，用新的研究方法 如链接分析法来描述和组织网络信息世界。 目前，w e b 用户主要是使用搜索引擎在互联网上检索信息，但目前的搜索引 擎往往返回给用户成千上万个检索到的页面，且其中很大一部分是重复的或与用 户检索要求不相关的内容。每个结果页面都有与查询的相关度评分，检索结果以 每页十几个到几十个结果的方式，按照与查询的相关度，以降序排列提交给用户。 查看搜索引擎返回的结果时，一般只会看头几页的结果，很少有人会看排名在 1 0 0 或2 0 0 之后的结果页面，几乎没有人会穷尽数量庞大的检索结果。人们在查 看搜索引擎返回的这些结果时，往往会感觉到它们多少与查询是相关的，但检索 质量还不够好。 1 2w e b 结构挖掘技术 w e b 挖掘是目前网络信息检索发展的一个关键，我们多数的人都是通过搜 索相关网页获得信息。中国互联网络信息中心( c n n i c ) 近r 发布2 0 0 7 年中国搜 江苏大学硕士学位论文 索引擎市场调查报告显示，搜索市场高度集中，网民的搜索依赖性呈现增强趋势。 w e b 结构挖掘的目的是发现页面之间内在的有趣的联系、用户的访问模式 与访问习惯，以便更好的组织页面和使用页面。最近，有很多团体和科研机构对 w e b 上超文本系统的链接结构进行研究，并提出了许多有关w e b 结构挖掘的算法， 如p i t k o w 在他的博士论文中对大量的超链接进行了分析和研究【4 j ；w e i s s 用聚类 的方法对链接结构进行了分析【5 】；s p e r t u s 通过将链接结构对应成标准关系数据 库中的信息，用s q l 语句实现对w e b 的查询【6 j ；k l e i n b e r g 通过对w e b 对应关联 矩阵的特征向量计算寻找a u t h o r i t i e s 页和h u b s 页【7 1 ；b r i n 和p a g e 利用页面的 i n l i n k 和o u t l i n k 计算w e b 页的p a g e r a n k 值，并以此为根据寻找权威页i l i j ； l e m p e l 和m o r a n 则利用马尔可夫链的概念，对k l e i n b e r g 的算法进行了改进， 淡化了a u t h o r i t i e s 页和h u b s 页之间的关系，提出了一种分析超链接结构的随 机算法s a l s a 。 1 2 1w e b 数据的特点 w o r l dw i d ew e b 由许许多多的w e b 站点构成，而每个w e b 站点又包含许多 的w e b 页，w e b 页与普通文档不同，它所包含的信息由以下3 个部分组成：网页 正文，网页所含的超文本标记以及网页间的超链接。 实际上，w e b 的结构不仅仅包含网页间的超链接，从广义上讲，w e b 结构所 包含的信息有： ( 1 ) u r l 字符串中的目录路径结构信息； ( 2 ) 网页内部内容的可以用h t m l 、) 【m l 表示成的树形结构； ( 3 ) 网页之间的超链接结构。 w e b 上有海量的数据信息，如何对这些数据进行复杂的应用成为现今数据库 技术的研究热点。数据挖掘就是从大量的数据中发现隐含的规律性内容，解决数 据的应用质量问题。充分利用有用数据，废弃无用数据，是数据挖掘技术的最重 要应用。w e b 数据的主要特点有： 1 异构数据库环境 从数据库的研究角度出发，w e b 中的信息可以看作一个更大、更复杂的数据 库，每一个站点就是一个数据源，由于站点之间的信息和组织不同，因而构成一 个巨大的异构数据库环境。如果要利用这些数据进行挖掘，首先必须研究站点之 间异构数据的集成问题，只有集成这些站点的数据，为用户提供一个统一的视图， 才有可能从巨大的数据资源中获取所需的内容；其次，还要解决w e b 上的数据查 询问题，因为如果所需的数据不能很有效的得到，则分析、集成并处理这些数据 就无从谈起。 2 江苏大学硕士学位论文 2 半结构化的数据结构 所谓半结构化是相对于结构化和非结构化而言的，w e b 上的数据最大特点就 是半结构化，但是w e b 上的数据与传统的数据库中的数据不同传统的数据库都 有一定的数据模型，可以根据模型来具体描述特定的数据，而且按照一定的组织， 有规律的集中或者分布存放结构性很强。而w e b 上的数据非常复杂，没有特定 的模型描述。每一站点的数据都各自独立设计，并且数据本身具有自述性和动态 可变性，因而w e b 上的数据不是强结构性的，但与此同时w e b 页面又是有描述 层次的。单个网站也是按照各自的结构构架的，从而具有一定的结构性，因此我 们认为w e b 上存在的数据既不是完全结构化的，也不是完全非结构化的，而是 介于两者之间，一般称之为半结构化数据。半结构化是w e b 上数据的最大特点 显然面向w e b 的数据挖掘比面向单个数据仓库或者其他结构化数据集的数据挖 掘要复杂得多。 3 解决半结构化的数据源问题 w e b 数据挖掘技术首先要解决半结构化数据源模型及其查询和集成问题，解 决这个问题必须要有一个模型清晰地描述w e b 上的数据，查询一个半结构化的数 据模型是关键所在。除定义这个模型外，还需要一种自动地从现在数据中抽取半 结构化模型的技术。面向w e b 的数据挖掘必须以半结构化模型和半结构化数据模 型抽取技术为前提。 1 2 2w e b 挖掘概述 w e b 数据挖掘是数据挖掘在w e b 上的应用，它是一项综合技术，采用较为一 般的定义：w e b 数据挖掘就是针对包括w e b 页面内容、页面之间的结构、用户访 问信息、电子商务信息等在内的各种w e b 数据源，在一定基础上应用数据挖掘的 方法以发现有用的隐含知识的过程。随着信息技术的发展，计算机、网络和通信 三者的相互结合，已经产生了数据挖掘的新方向。就基于w e b 数据挖掘的确切 定义，到目前为止还没有很明确而权威的说法。国外有人认为：w e b 挖掘就是利 用数据挖掘技术，自动地从网络文档以及服务中发现和抽取信息的过程【4 5 1 。国内 则众说纷坛。文献m j 将w e b 挖掘定义为：针对包括w e b 页面内容、页面之间的结 构、用户访问信息、电子商务信息等在内的各种w e b 数据，应用数据挖掘方法以 发现有用的知识来帮助人们从w w w 中提取知识，改进站点设计，更好地开展电子 商务。南京大学的王继成、张福炎等则进一步将这一概念形式化为： 定义1 1 ：w e b 挖掘是指从大量w e b 文档的集合c 中发现隐含的模式p 。如 果将c 看作输入，p 看作输出，那么w e b 挖掘的过程就是从输入到输出的一个映 3 江苏大学硕士学位论文 铽 ：cj p o 今天由于在w e b 卜信息资源的急剧增加，该领域的研究越来越广泛。一般地， 根据挖掘的对象不同我们可以把基于w e b 的数据挖掘分为三大类：图1 1 给出 了we b 挖掘的分类图。 基于w e b 内容的挖掘( w e bc o n t e n tm i n i n g ) 基于w 阻结构的挖掘( w e bs t r u c t u r em i n i n g ) 基于w e b 使用的挖掘( w e bu s a g em i n i n g ) 图】1w e b 挖掘框架图 w e b 挖掘是当今世界上的热门研究领域，其研究具有广阔的应用i j 景；w e b 挖掘的技术和工具也在不断发展，同时具有巨大的市场潜力。w e b 挖掘尚有许多 问题有待于进一步的研究和深化。目前，在国内外w e b 挖掘的研究处于刚起步阶 段，是前沿性的研究领域。将来几个非常有用的研究方向是： 1 ) w e b 数据挖掘中内在机理的研究： 2 ) w e b 知识库( 模式库) 的动态维护、更新，各种知识和模式的融合、 提升，以及知识的评价综合方法： 3 ) 半结构、非结构化的文本数据、图形图像数据、多媒体数据的高效挖 掘算法： 4 ) w e b 数据挖掘算法在海量数据挖掘时的适应性和时效性： 5 ) 基于w e b 挖掘的智能搜索引擎的研究： 6 ) 智能站点服务个性化和性能最优化的研究： 7 ) 关联规则和序列模式在构造自组织站点的研究： 8 ) 分类在电子商务市场智能提取中的研究 本文的研究方向主要放在w e b 挖掘在搜索引擎方面的应用。 4 江苏大学硕士学位论文 1 2 3w e b 结构挖掘的定义和应用 在w e b 挖掘中，w e b 结构挖掘是w e b 数据挖掘的一个重要方面，其重点在于 信息检索。虽然随着万维网规模上的迅速增长，其复杂性也大大的增加，以致于 我们己经无法继续掌握其全貌。然而，在一些较小的、本地的领域里，w e b 表现 的仍然是有序的、结构化的，因为网页的超链接结构是建立在人们努力进行注释 的基础上的。w e b 网页的作者往往会在其网页中添加指向相关主题网页的链接。 通过利用这些链接信息，就可以针对某一主题对网页进行提取和分组。搜索引擎 可以帮助人们尽快地找到所需要的信息，但是目前多数搜索引擎是基于分类或关 键词逻辑组配的检索方式，用户的一个查询请求往往会检索出庞大的结果集，而 用户所需要的信息却只是其中一小部分，面对如此多的结果，用户仍然不知所措， 因此，如何提供一些有效的工具和方法，帮助人们高效地获取所需信息，搜索所 需领域的权威网页就成为了研究者们所面临的重大课题。 定义1 2w e b 结构挖掘是指通过分析不同网页之间的超链接结构以及文 档u r l 中的目录路径结构等，从w e b 的组织结构和链接关系中发现页面之间内 在的联系、用户的访问模式等等。 w e b 结构挖掘的应用实例主要有： 1 指导网页采集【9 ，1 0 1 1 】，采集网页是搜索引擎机器人爬行网页的过程。它一 般是根据网页之间的链接信息来采集网页，采集效率低。为了采集“高质量”的 网页，就应按照网页质量的高低依次来进行采集，使得采集少量的网页而获得 最好的网页。网页链接分析为判断网页的质量提供了一种方式。 2 帮助结果排序【7 ，9 ，8 】 因为网页数量巨大，不可能对全部的页面进行链接分析。所以实际的工作过 程如下：先用基于关键词的搜索引擎得到一个集合( 取前面n 个) 。然后对这n 个页面应用p a g e r a n k 或h i t s 算法，得到最终的排序结果。对该算法的评价可 以参考文献1 2 f 13 1 。 3 检索结果聚类4 j 目前搜索引擎结果还不是令人满意。与基于词或短语的文本聚类算法不同， 有学者使用超链分析来对结果进行聚类。它是基于c o c i t a t i o n 和c o u p l i n g 分 析来过滤无关文档，将质量高的文档进行聚类，提供给用户进行浏览和访问。例 如用户检索“j a g u a r ，将结果聚类如下：j a g u a rc a r 、j a g u a rc l u b 、m a g a z i n e o nj a g u a rc a r 、j a g u a rg a m e 等，从而方便用户浏览。 。一4 查找相关网页( q u e 巧b ye x 锄p l e s ) 9 ”】根据实例查找，或称之为找相关网 5 江苏大学硕士学位论文 页( f i n dr e l a t e dp a g e s ) 。根据用户需要查找的某一实例，例如一个网页，找 出与之相关类似的网页。在g o o g l e 和n e t s c a p e 中支持这种服务。传统的信息检 索技术是采用文本相似度，而在w e b 环境中，可以充分挖掘链接结构来实现。 k 1 e i n b e r g 声称将h i t s 算法稍加修改也可以用来实现实例查找。d e a n 和 h e n z i n g e r 提出了两种算法：c o m p a n i o n 算法、c o c i t a t i o n 算法。基于链接分析 的算法总体上优于基于文本相似度算法。 5 消除重复网页【9 ，1 6 】 网页路径是u r l 的一部分。例如：u r l ：h t t p ：g o o g l e c o m a b o u t h t m l ，w w w g o 0 9 1 e c o m 就是主机地址，a b o u t h t m l 是路径。两台主机 h 2 和h 1 是镜像网站，当且仅当h 2 中的文档，在h 1 中具有相同路径的相似文 档，反之亦然。镜像网站具有相似的超链结构。通过超链分析可以检测出近似的 镜像网站，从而节省索引空间和存储空间。 6 确定w 曲影响因子m bi i i l p 砌f a c t o r ) 【1 7 1 9 】 w e b 影响因子是从期刊影响因子发展过来的。它的基本原理是：越多网页通 过链接指向某一站点或区域，它就越有影响力。但是这些链接也需要进行分析： 有些链接是导航：链源网页的重要性也影响链宿页面的重要性：可能一个链源 指向一个站点的几个网页等。目前w e b 影响因子能否应用到实际当中还有待进 一步研究。 目前这一领域的主要研究集中在利用w e b 页面的链接结构来挖掘权威页面【2 j 。 要对页面之间的结构进行挖掘，并通过搜索引擎将权威页面提供给用户就需要用 到页面排序算法。发现许多蕴涵在w e b 内容之外的对我们有潜在价值的模式和 知识的过程【1 9 j 。 在w e b 上进行信息检索面临的最大问题是如果对获得的大量搜索结果进行 整理和排序，从而快速的定位最符合检索要求的文档，剔除掉与检索内容不相关 的文档集合。超链接作为超文本文档的一个重要特征，为w e b 信息获取提供了 有价值的信息。近来以超链接分析为基础的w e b 检索算法，如p a g e r a n k 在提 高检索精度方面与传统搜索引擎使用的基于单词的方法相比有了大幅度的提高。 本文当中主要应用到的是w e b 结构挖掘在页面排序算法上面的应用，而w e b 结构挖掘中主要用到的技术是w e b 链接分析，下面详细解释w e b 链接分析的原 理和方法。 6 江苏大学硕士学位论文 1 3w e b 链接分析在w e b 结构挖掘的应用 随着互联网的迅猛发展，互联网上的网页数量呈几何级数快速增加，造成早 期的简单的关键字匹配算法所得到的搜索结果出现数量大、结果不精确、有效结 果少、结果排序无规律等问题，使得使用搜索引擎来查找信息的目的难以达到。 为解决这些问题，搜索引擎技术在许多方面有了进一步的发展，超链分析就是其 中用于解决搜索结果排序的一种技术思路。的确，许多搜索引擎( 如g o o g l e ， c 1 e v e r 等) 通过这种超链接的分析来发现高质量或重要的w e b 页，并取得了良好 的效果。 网络从整体上可以看作是由网页和链接所形成的巨大的数据库，然而它的分 布性、多样性和动态变化的特点使得知识发现的实现变得更为困难。但是，也正 是这些特性，使知识发现具有了更为丰富的资源，为产生事先无法预测的重大发 现提供了条件。目前，对w e b 知识发现的研究主要从三个方面入手，即网页内容、 链接结构和用户的行为。 w e b 结构包括不同网页之间的超链接结构和一个网页内部的可以用h t m l ， ) ( m l 表示成的树开结构，以及文档u r l 中的目录路径结构等。链接将网络文档联 系在一起，形成一个复杂的结构化的超文本集。正如网络缔造者b e m e r s l e e 所 说的，开发网络是为了揭示“t h ec o m p l e xw e bo fr e l a t i o n s h i p sb e t w e e n p e o p l e ，p r o g r a m s ，m a c h i n e sa n di d e a s ”，因而，链接结构包含了大量能用于知 识发现的固有信息。通过对链接结构的分析和挖掘，我们能分辨不同的网络群体、 确定权威网页、提炼主题和改进搜索引擎检索结果相关度排序算法。在此研究领 域，图论方法得到了广泛的应用。 1 3 1w e b 链接分析的工作机理 一般来说链接类型大致分为两种：首先它为用户提供了浏览w e b 的导航信 息，如合作链接( 被链接网站和链接网站之间存在合作关系) 、友情链接( 网站 之间可能由于在资源或其它相关方面有关系) ，可以起到网络导航的作用，常用 的导航条用来指引访问者在各页面之间跳转大大方便用户在网上冲浪；其次，页 面中的超链接往往是文档作者对于某一文档的推荐，推荐链接( 被推荐网站由于 质量好、人气旺、访问用户多或是热门网站等原因链接) ，被推荐的目的文档往 往与该文档有相似内容而且被作者所认同，内容链接( 被链接网站和链接网站在 内容上存在着互补或相通关系等) 。后者构成了链接分析的基础，即某一文档的 重要性不由文档的内容决定而取决于被其他文档链接( 或者引用) 的次数 2 0 。 7 江苏大学硕士学位论文 图1 2 文献的引用与被引用关系 g o o g l e 1 r r 蜘酗k 嚣觞硼撕堋s 协嗍嘲e 翱i l i i 图1 3 网站的引用与被引用关系 这种评价机制类似于科学论文中的参考文献：被别人引用次数越多的论文其 重要性比引用次数少的论文要高。在w e b 检索中，除了被其他文档链接的次数 外，链接源文档的质量也是评价被链接文档质量的一个参考因子：被高质量文档 链接或者推荐的文档往往具有更高的权威性【2 1 1 。这种对w e b 页面进行链接分析 的方法就是w e b 结构挖掘。 w e b 页之间的超链接结构中包含了许多有用的信息，当网页a 到网页b 存在 一个超链接时，则说明网页a 的作者认为网页b 的内容非常重要，且两个网页的 内容具有相似的主题。因此，指向一个文档的超链接体现了该文档的被引用情况。 如果大量的链接都指向了同一个网页，我们就认为它是一个权威页。这就类似于 论文对参考文献的引用，如果某一篇文章经常被引用，就说明它非常重要。这种 思想有助于对搜索引擎的返回结果进行相关度排序。从w w w 的组织结构和链接关 系中推导知识。通过对w e b 站点的结构进行分析、变形和归纳将w e b 页面进行 8 江苏大学硕士学位论文 分类，分析一个网页链接和被链接数量以及对象来建立w e b 自身的链接结构模 式，确定不同页面间的相似度和关联度信息。定位相关主题的权威站点，可以极 大的提高检索结果的质量。mrh e n z i n g e r 认为目前的w e b 超链接分析大多基 于以下两条基本假设【州： 假设1 ：从w e b 网页a 指向网页b 的超链接是网页a 作者对网页b 的推 荐。 假设2 ：如果一条超链接将网页a 和网页b 相互链接起来，则网页a 和网 页b 可能有共同的主题( t o p i c ) 。 基于上面的两个基本假设，还可以引申出以下几个假设【7 。9 ，1 4 ，1 51 ： 假设3 ：一个页面被多次引用，即很多页面有指向它的链接，则这个页面 很重要。 假设4 ：一个页面尽管没有被多次引用，但被一个重要页面引用，则这个 页面也可能很重要。 假设5 ：一个页面的重要性被均匀分布并传递到它所引用的页面。 假设6 ：如果页面p 和q 同被引，则它们可能是相关的，同被引度越大， 相关度越大。 假设7 ：如果页面p 和q 耦合，则它们可能是相关的，耦合度越大，相关 度越大。 1 3 2w e b 链接分析的定义 如果将页面看作顶点，连接看作有向边，真个网络可以看作是一个有向图， 称为w e b 图( w e bg r a p h ) ，可以利用复杂网络理论来进行研究分析。 图1 4w 曲有向图 9 江苏大学硕士学位论文 为了能更清楚地描述算法思想，在这一节中我们对于一些基本概念先作一下 说明。在本论文中，首先应该提出来的是，如果没有特别说明，我们提到的w e b 图都是指w w w 从图论的角度看作一个规模巨大的有向图( 如图1 4 所示) ，具体定 义如下： 定义1 3 ：有向图g ( n ，e ) 称为w e b 图，若n 表示有限页面顶点集合，e 是 由n 中不同元素组成的有序对的集合，它表示页面之间的超链接。 1 ，胗， v v ，w ，且v w ，v e 表示从页面v 指向页面w 的一个超链接。 。 ， i 。* * _ 。 ： ， 一 ，i蕊。j 。10 三三舔j ? _ ，纛雾：。一。e ，。：l 。瀚- - ：一。+ 。l _1 一。：_ 4 * ， 。 。 图1 5 ：处理后不i 司网络站点不l 司的w 曲有向图 定义1 4 ：链接分析( h y p e r l i n ka n a l y s i s ) 又称为结构分析( s t r u c t u r e a n a l y s i s ) ，是指以超链接作为主要输入研究w e b 的性质，尤其是隐藏的宏观性 质对链接数量和质量的评估及分析。 简而言之，链接分析方法，就是运用网络数据库、数学分析软件等工具，利 用数学( 主要是统计学和拓扑学) 和情报学方法，对网络链接自身属性、链接对 象、链接网络等各种对象进行分析，以便揭示其数量特征和内在规律，并用以解 决各方面问题的一种研究方法【2 引。 1 3 3 搜索引擎检索质量的改进 自2 0 0 0 年以来，搜索引擎用户的年度增加速度基本稳定在1 2 左右，而进 入2 0 0 6 年后，搜索引擎用户的增速开始放缓降到1 1 3 2 ，截至2 0 0 7 年9 月， 2 0 0 7 年的搜索引擎新增用户数是7 7 。参与搜索服务市场的有多家实力企业， 如g o o g l e 、雅虎( y a h o o ! ) 及微软( m ic r o s o f t ) 等巨头企业，以及若干规模较小 但有特定市场区隔或技术者如d t s e a r c h 、c o p e r n i c 等。近期全力开发搜索技术 的还包括i b m 【9 】，i b m 所采用的搜索技术不同以往，最早的搜索引擎以单纯的关 1 0 ，o t 。- ，； 0 袋棼，黪零 江苏大学硕士学位论文 键词为唯一条件，但可能搜索不到相关的网页。 传统的信息检索系统，检索结果相关度排序是依据t f ( t e r mf r e q u e n c y ) xi d f ( i n v e r s e d oc u r n e n tf r e q u e n c y ) 。1 9 9 7 年j e r o m yc a r r i e r e 和r i c kk a z m a n 开发出基于节点被链接数排序的w e b q u e r y 系统。然而，这个系统的缺陷也是显 而易见的。诸如，为了提高某个节点的位置，可以创建大量的重复文档和链接指 向该节点，网站之间的链接交流也会对其产生显著影响。虽然w e b q u e r y 系统有 缺陷，但其意义在于使网络链接分析成为提高搜索引擎检索质量的重要思路。围 绕这一问题展开了许多研究，主要在于解决如何给不同的链接赋予不同的权重。 在搜索引擎收集信息的过程中，j k l e i n b e r g 认为搜索引擎的r o b o t s 直接 访问w e b 提取出权威页( a u t h o r i t yp a g e ) 。但是如何提取出权威页，这需要一 个原始积累和评价过程。先给出一批起始网页，r o b o t 从这些源网页开始收集， 可以按照深度优先或广度优先的算法进行。当网页提取回来后，采用链接分析技 术( 具体用递归算法) 来计算出权威页。有了权威网页，r o b o t 在收集w e b 信息 时，就有针对性地、高效率地访问w e b 网页。搜索引擎检索结果排序方面也运用 了链接分析技术，由于索引数据库容量大，若用户输入一个关键词，有可能会有 成千上万条记录相匹配，搜索引擎对如此庞大的结果如何排序，如何把最相关的 几十条记录显示出来? 搜索引擎按记录号的顺序提取结果集中的前几十条记录， 再按邻近图( n e i g h b o rg r a p h ) 算法对这几十条记录排序，最先显示给用户。 这种检索结果排序就是利用链接分析技术，大大减轻了搜索引擎的负担，y a h o o 、 g o o g l e 等搜索引擎就采用了超链接分析技术来对检索结果排序。 1 4w e b 链接分析的研究现状 1 4 1网络信息计量的发展 是在网络信息环境下迅速形成和发展起来的，作为信息计量学的一个新的发 展和重要的研究领域，它的出现使传统的基于文献和信息的文献计量学、信息计 量学面临着新的变革。关于其定义主要有：网络计量学是一门计算机科学，是一 门研究互联网上数据相互引用的科学，是一门对网络文献规律进行统计分析的科 学，基于w e b 和软件计量分析工具，集计算机技术、网络技术、计量学方法、统 计学方法于一体，其应用范围覆盖了所有基于网络通信技术的信息测度。网络计 量学是综合采用文献计量、信息计量、统计学方法、计算机技术和网络技术对网 络文献规律进行统计分析的一门科学。网络信息计量学是采用数学、统计学的各 种定量方法，对网络信息的组织、存储、分布、传递、相互引证和开发利用进行 一定量描述和统计分析，借以揭示网络信息的数量特征和内在规律的一门新兴学 1 1 江苏大学硕士学位论文 科。它主要是由网络技术、网络管理、信息资源管理与信息计量学等相互结合、 交叉渗透而形成的门交叉性边缘学科。 1 9 9 7 年丹麦学者阿曼德( t c a 1 m i n d ) 等人首次提出了“w e b m e t r i c s ”这一 概念，认为文献计量学的各种方法完全可以用于互联网的信息计量分析中。此后， 许多学者在不同方面对网络信息计量学问题进行了探讨。例如，r o u s s e a u ， m c k i e r n a n 根据文献计量学引文( c i t a t i o n ) 的含义，提出了“s i t a t i o n ”的概念， 对网页的引用行为进行分析；w e b s i t e n e t 仿照科学引文索引( s c i ) 的做法 编制了一个“网络引证分析索引”( w e bc i t a t i o ni n d e x ，w c i ) ，用来统计分析 网页的引用情况研究网页链接之间的关系和规律，监视网页链接的变化情况等； i n g w e r s e n 提出可以把文献计量学的期刊影响因子应用到网页的评价中去，提出 了“网络影响因子 ( w e b i m p a c tf a c t o r ，w i f ) 的概念，可以用来分析一定时期 内相对关注的网页平均被引情况；b r i n 等提出了“p a g e r a n k ”算法，根据一个 网页链接其它网页的数量和质童来判断一个网页的质量和权威性：英国南安普顿 大学的“开发期刊计划”( o p e nj o u r n a lp