（计算机应用技术专业论文）web结构挖掘中hits算法的优化与实现.pdf

河南大学硕士研究生学位论文第1 页 摘要 i n t e r n e t 是一个巨大、分布广泛、全球性的信息服务中心，它提 供了各种各样的信息服务。与此同时，如何从i n t e r n e t 所提供的浩如 烟海的信息中获取所需信息或是从中提取有用知识便成为一个急需解 决的问题。搜索引擎是目前最主要的w e b 检索工具，然而搜索引擎返回 的文档质量参差不齐，难以满足用户对高质量检索结果的需求。 将传统的数据挖掘技术和w e b 结合起来，进行w e b 挖掘成为解决这 一问题的重要途径。结构挖掘是w e b 挖掘的一个重要方面，研究表明 w e b 上的链接结构含有非常丰富和重要的信息，链接分析技术已经被成 功的用于分析w e b 超链接数据来确定权威信息源。在各种对网页进行链 接分析并提取主题的算法中，h i t s ( h y p e r l i n k - i n d u c e dt o p i cs e a r c h ) 算法是最典型的。通过对h i t s 算法的深入研究发现，该算法存在一定 的不足。h i t s 算法在扩展根集阶段对页面的不合理选取导致无效链接 过多，直接影响最终权威信息源的质量；给不同的w e b 站点作者规定了 不平等的影响权重，导致了链接间不合理的相互加强关系；w e b 链接结 构的自组织性导致迭代分析往往收敛于链接结构图中与查询主题不太 相关的紧密连接区域( t k c ) ，从而导致主题偏移。针对以上不足，本 文提出了一种结合内容分析与链接分析的主题精选算法一一w h i t s 算 法，并开发了实验系统，对该算法进行了验证，通过对实验结果的分析 讨论证明改进后的算法较原算法更合理有效。 本文的主要贡献有以下几点： ( 1 ) 提出了更有效的获取基集的方法，赋予了文档作者间平等的 影响权重，使精选出的权威和中心网页更为客观合理； ( 2 ) 通过内容分析给信息源赋予了主题相关度权重，并运用加权 的i o 操作进行链接分析，使主题相关度较高的信息源得到较高的排序 分值； ( 3 ) 对主题相关度很低的信息源进行修剪，排除他们对排序分值 计算的干扰，进一步保证了主题精选结果是真正的查询主题下的权威 中心源； ( 4 ) 提出了验证该算法有效性的实验方案，并开发了实验系统， 对该算法进行了验证，并对实验结果进行了分析讨论。 关键词：w e b 挖掘；链接结构；主题提取；h i t s ；内容分析 河南大学硕士研究生学位论文第1ii 页 a bs l ：ra c t k n o w l e d g ef r o mt h eg r e a td e a l0 fi n f o r m a t i o f tp r o v i d e db yi n t e r n e t h a st h e nb e c o m eap r o b l e mr e q u i r e d1 ；ob es 0 1 v e da l ；o n c e s e a r c h e n g i n e i st h em o s t c o m m o n l yu s e dt o o lf o rw e bi n f o r m a t i o n r e t r i e v a l b u tt h eq u a l i t yo fd o c u m e n t sr e t u r n e db yt h es e a r c h e n g i n eisn o ts og o o da n dcann o ts a t is f yt h eu s e s r e q u i r e m e n - t s f o rh i g hq u a l i t yd o c u m e n t s i tisav e r yi m p o r t a n ti l l e t h o dt o i m p l e m e n tw e b d a t am ir l i n g b yc o m b i n i n gt r a d i t i o n a ld a t am i n i n gt e c h n o l o g ya n dw e b w e b s t r u c t u r em i n i n gi sai m p o r t a n td i m e n s i o ni nw e b d a t am i n i n g r e s e a r c h e r sd is c o v e t h a tr i c ha n di m ! o o r t i n f o r m a t i o i 2is c o n t a i n e da m o n gl i n ks t r u c t u r eo fw e bp a g e ，h y p e r l i n ka n a l y s i s h a sb e e ns u c c e s s f u ll yu s e di na n a l y z i n gt h eh y p e r li n kd a t ao fw e b p a g e st 0e x t r a c ta u t h o r i t a t i v ei n f o r m a t i o ns o u r c e 。a m o n gv a f i o u s h y p e r l i n ka n a l y s i sm e t h o d s ，h i t s( t - y p e r l i n k i n d u c e d t o p i c s e a r c h ) a l g o t i t h mi st h em o s tt y p i c a l b ys t u d y i n gt h ec l a s s i c a l w e bs t r u c l ；u r em i 2 i n ga l g o r it h mh i t si nd e p t h w ed is c o v e l t h a t t h e r eares o m es h o r t c o m i n g si nh i t s h i t sa l g o t i t h ms e l e c t e dt ；o o m a n yi n v a li dli n k si nt h es r a g eo fe x p a n d i n gh a s er o o t ，d i r e c t l y a f f e c t t h eq u a l i t yo fu l t i m a t ea u t h o r i t yi n f o r m a t i o r l s o l l i c e s ： p r o v id esu n e q u a ii m p a c tw eig h tt od if f e r e n t w e bsi1 ；e a u t h o r ， 1 e a d i n gt ou r l r e a s o n a b l em u t u a l l ys t r e n g t h e nr e l a t i o n s h i po ft h e li n k s w e b1i n ks t r u c t u r eo ft h e s e l f o r g a n i z i n gn a t u r eo f t e n l e a d1 ；oi t e r a t i v ea n a l y s i sc o n v e r g e st ot h el i n kc h a r tw i t ht h e i n q u i r ys u b j e c l ；n o t1 ；o or e l a t e dt i g h t l y k n i tc o m m u n i t y ( t k c ) ， t h u s c a u s e st h es u b j e c td i s p l a c e m e n t i nv i e wo ft h ea b o v e i n s u f f i c i e n c y ，t h i sp a p e rp r o p o s e sa ni m p r o v e da l g o r i t h mw - h i t s w i t hc o m b i n a t i o no fc o n t e n ta n a l y s isa n dl i n ka n a ly s is a n dh a s 第l v 页 河南大学硕士研究生学位论文 一一 d e v e l o p e d t h ee x p e r i m e n t a ls y s t e m ，h a s c a r r i e d o n t h e c 。n f i r m a t i o nt o t h i sa l g o r i t h m b a s e d o nt h ea n a l y s ls o f e x d e r i m e n t a lr e s u l t s ，d e m o n s t r a t e dt h ei m p r o v e da l g o n t h mt h a n t h eo r i g i n a la l g o r i t h mm o r e r e a s o n a b l ea n de f f e c t i v e t h em a i nc o n t r i b u t i o n s a r ea sf o l l o w s ： ( 1 ) p r o p o s e dt h em o r ee f f e c t i v em e t h o do fg a i n i n gb a s er o o t , a n dg i v et h ed o c u m e n ta u t h o r se q u a l i t yi nt h ei m p a c tw e i g h t ，t o m a k et h ea u t h o r i t y a n dt h eh u bp a g e s a r em o r eo b j e c t l v e a n d r e a s o n a b l e ( 2 ) t h r 。u g hc o n t e n ta n a l y s i s g i v e t h es o u r c ei n f o r m a t l o n r e l e v a n c ew e i g h tt ot h eg i v e ns u b j e c t ，a n da p p l i e sw e i g h t e di o o d e r a t i o n si nt h ei t e r a t i o n ，e n a b l eas u b j e c tc o r r e l a t l o nh l g n e r i n f o r m a t i o ns o u r c e t or e c e i r eh i g h e rs c o r e s ( 3 ) p r u n i n gl o w e r r e l e v a n c en o d e s ，r e m o v e t h e l rr a n k i n g s c o r e sc a i c u l a t e d i n t e r f e r e n c e ，f u r t h e r e n s u r i n g t h et h e m e s e l e c t e dr e s u l t s o ft h ei n q u i r y ist h er e a l t h e m eo ft h e a u t h o r i t y h u bs o u r c e ， ( 4 ) p r o p o s e s a ne x p e r i m e n tp l a nt o c o n f i r mt h i sa l g o r l t h m v a l i d ，a n dh a sd e v e l o p e dt h ee x p e r i m e n t a ls y s t e mt oc o n 士i r mt h i s a i g o r i t h m a n dt h ee x p e r i m e n t a l r es u l t s a r ea n a l y z e d a n d d is c u s s e d k e y w o r d s ：w e b d a t am i n i n g ：li n k s t r u c t u r e ：t o p l c d i s t i l l a t i o n ：h i t s ：c o n t e n ta n a l y s l s 河南大学硕士研究生学位论文第1 ii 页 关于学位论文独立完成和内容创新的声明 本人向河南大学提出硕士学位申请。本人郑重声明：所呈交的学位论文是 本人在导师的指导下独立完成的，对所研究的课题有新的见解。据我所知，除 文中特别加以说明、标注和致谢的地方外，论文中不包括其他人已经发表或撰 写过的研究成果，也不包括其他人为获得任何教育、科研机构酌学住或证书而 使用过的材料。与我一同工作的同事对拳研窥所做酌任何贡献均已在论文中作 了明确的说明并表示了谢意| ： 一 ：， 、 、 二 jj j 1 ，j， 学住申请氏i _ _ ( 学位论表蠓袭) 凑：夏一邀 = - i ? 一j i 参薯d。年月：。臼 、。，、 l 、一l l j + 一p f 、 匕i - ji。享毙0 ￥ 孓 。磐 ，i ：、卜鼻 j 蠢 c i ：j j 。、t，謦强r j笏 ! 獬薯囊誉。 。 爹。关干攀俸沦黛著作权1 羲穰营受叔书，i j j ，爱一搿j i i 。移、5j ：逢 、1 。 一 爱 、。 ? 、量砖澎慧0 囊蕊冬? ： 露j ；。、 、 j 本人经河噫、大学声核 嘎囊孽霪瓣蓦鲮蕊篡晏篡砻学位论文紫作者，本人完全 了解并同意河南瓷学有关保留獭鬻爨鬻豢潮要求，即孽南大学有权向国家 图书馆、科研信息槐构、数据收集机构和奉檬图书馆等提供学位论文( 纸质文 本乖电子文本) 以供公纨捻索、聋阅i i 本入拣枳河南j 失学出于宣扬、展览学校 学术发展和进行学术交流等“阉i 的，0 可麒采取影印、缩印、扫描和拷贝等复制手 段保存、汇编学位论文( 纸质文本和电子文本) 。 ( 涉及保密内容的学位论文在解密后适用本授权书) 学位获得者( 学位论文作者) 签名： 殳盛 2 0年 月 臼 学位论文指导教师签名： 金垫 2 0年 月 目 河南大学硕士研究生学位论文第1 页 第一章绪论 1 1 课题背景和研究意义 w e b 是为广大用户交换或共享信息而发展起来的一种i n t e r n e t 应 用，近年来得到了飞速发展，其信息量呈几何级数增长。每天都有数以 百万计的网页加入到w e b 中。它已经成为了一个涉及教育、政府、电子 商务、新闻、广告、消费信息、金融管理和许多其它信息服务的、巨大 的、分布广泛、全球性的信息服务中心。 i n t e r n e t 的普及和发展为人们带来了巨大的社会效益，与此同时， 它也为信息科学的研究带来了巨大的机遇和挑战。虽然网络可以迅速便 捷的为人们带来大量信息，但是，w e b 所具有的海量数据、复杂性、极 强的动态性、用户的多样性等特点给w e b 资源发掘造成了相当的难度。 在实际应用中，当需要从网络上获取信息时，有用信息往往会被大量的 无用信息所淹没，使用户处于无所适从的境地，搜索特定主题的少量权 威信息源成为用户普遍又迫切的需求。 解决这些问题的一个有效途径，就是将传统的数据挖掘【i ，2 】技术和 w e b 结合起来，进行w e b 挖掘【1 6 a 7 a 9 。w e b 挖掘是一项综合技术，涉及 了统计学、人工知识、模式识别、并行计算、机器学习、数据库等多个 领域。一个较为一般的定义是：w e b 数据挖掘就是从与w w w 相关的资源 与行为中抽取感兴趣的、潜在的有用模式和隐含信息。 w e b 结构挖掘作为w e b 数据挖掘的一个重要方面，越来越受到广大 研究机构和科研团体的重视。随着万维网规模上的迅速增长，其复杂性 也大大的增加，以至于我们已经无法掌握其全貌。然而，在一些较小的、 本地的领域里，w e b 表现的仍然是有序的、结构化的，因为网页的超链 接结构是建立在人们努力进行注释的基础上的。w e b 网页的作者往往会 在其网页中添加指向相关主题网页的链接。通过利用这些链接信息，就 可以针对某一主题对网页进行提取和分组。搜索引擎可以帮助人们尽快 地找到所需要的信息，但是目前多数搜索引擎是基于分类或关键词逻辑 组配的检索方式，用户的一个查询请求往往会检索出庞大的结果集，而 用户所需要的信息却只是其中一小部分，面对如此多的结果，用户仍然 不知所措，因此，如何提供一些有效的工具和方法，帮助人们高效地获 第2 页河南大学硕士研究生学位论文 取所需信息，搜索所需领域的权威网页就成为了研究者们所面临的重大 课题。 为了达到自动识别权威网页的目的，首先必须要能对网页价值进行 合理的评估，而计算网页价值的一种切实有效的途径就是利用万维网链 接结构本身所包含的丰富信息。链接分析技术在这一领域中扮演着重要 的角色，己经被成功地用于分析w e b 超链接数据来确定权威信息源，并 成为当前主流i n t e r n e t 搜索引擎的基础。 j k l e i n b e r g 在参与i b m 的c 1 e v e r 研究项目中，首先提出了一种 主题提取算法一一h i t s ( h y p e r t e x ti n d u c e dt o p i cs e a r c h ) 算法【j j 。 h i t s 算法利用w w w 上的链按信息来检索最符合查询主题的网页信息， 以增加高相关主题网页的选取，减少不必要的人工筛选、浏览工作，提 高检索的效率和质量。而传统的w e b 检索只考虑w e b 上的超文本文档的 内容，忽视了其中的链接信息，仅从w e b 页面本身的文本内容中难以找 到文档的质量信息，因此仅通过i r 的基本方法一一内容分析无法达到 以上过滤的目的。h i t s 算法是一个经典的主题提取算法，并由此开创 了主题提取的研究热潮，但进一步研究表明h i t s 算法作为一种基于纯 链接分析的主题提取算法存在不足，如容易发生主题偏移问题、产生不 合理的结果等。本文对h i t s 算法进行了深入细致的分析并提出了改进 方法，以期更好的实现权威网页的查找。 1 2w e b 结构挖掘算法的发展和研究现状 许多支持w e b 的软件和网络底层结构都是在w e b 出现以前就已经发 展了很长时间的，因此，当研究w w w 的结构性质时，我们就可以使用己 经比较完善了的离散数学模型( 主要和图的组合性质与代数性质有关) 。 w e b 可以很自然的被看作是一个由一组抽象节点( 网页) 和有向边( 超链 接) 组成的离散图，由于超链接提供了大量关于网页聚集的潜在信息， 因此这个离散图的结构可以有助于我们对其内容作进一步有意义的理 解和研究。 与此同时，我们也应该清楚的认识到，w w w 的极其复杂性给其结构 研究工作也带来了很大挑战。w e b 上的内容是由成百上千万的自主参与 者添加进去的，其中包括公司、政府机构、研究学者、学生以及大量的 个人用户，其多样性远远超过了我们以往所接触过的任何其它传统媒 河南大学硕士研究生学位论文第3 页 体。通过对引用分析和社会网络的研究，在面对这些问题时，我们般 可基于这样一种观点：对于一个复杂的网络，只有先对其重要显著的节 点进行确认鉴定，才可以有效的对其加以认识与理解。那么，怎样才能 利用算法自动识别重要节点呢? 这一方面的工作和成果最初来自于对社 会网络和文献引用 4 j 关系的研究。 社会网络、文献引用关系图和万维网一样，都可以表示成图 g = ( 矿，e ) 。在社会网络理论中，图中的节点代表论域中的实体，有向 边代表实体之间的关系；而文献引用中，图中的节点代表每一篇论文， 论文之间如果存在引用关系则存在一条有向边，从引用者指向被引用 者。有向图可以以一个邻接矩阵的形式被定义出来。即存在n 个实体的 社会网络图可以用一个九以的矩阵a 来表示，当实体i 到实体，存在一 个关系时，4 】= 1 。 上个世纪5 0 年代，k a t z i 9 1 在研究社会网络的基础上，提出了一种 计算名望( s t a n d i n g ) 的基于路径的方法：力表示从f 到_ ，的长度为， 的路径的数目，衰减系数b 为小于1 的常数，岛= 矿巧7 ) 表示f 与的 ，l l 耦合度，- = g 表示_ ，点的名望。通过矩阵变换可以得到一个比较直 接的矩阵公式：( ，一鲋) _ 1 一j ，其中第，列和就是s ，。 接下来，在6 0 年代，h u b b e l l1 0 】又提出了网络节点的权值传播模 型，给定一组节点p ，u = l ，2 ，月) ，e ，表示对于节点，权值5 ，的一个 初步估计，则节点乃的最终权值可以通过够1 = 勺+ 呜杉这一公式反复 ， 迭代计算得出，通过矩阵变换可以得到向量3 5 ( ，一a 2 ) 。1 e 。该算法实现 了这样一种思想一一即如果某个节点具有较大的权值，则该节点所指向 的节点也会趋向于具有较大的权值。 第4 页河南大学硕士研究生学位论文 另一方面，在对引用分析的研究过程中，一系列用以确定科学期刊 权威性的算法也被陆续提出，其中以g a r f i e l d 所提出的影响力因子 ( i m p a c tf a c t o r ) 算法】应用最为广泛。而影响力因子也因此一直成为 了科学期刊权威性和影响力的评判标准。影响力因子一般通过引用关系 来计算。比较简单的是计算某份期刊中论文被引用次数的平均值，这纯 粹是对图中节点入度的计算。具体做法是根据给定期刊在过去两年里平 均每一页被引用的次数来给该期刊赋予一个量化的分数值。此算法基于 这样一种思想：即如果某一期刊被引用的次数越多，则说明该期刊在其 领域的影响力越大，相应得也就越权威。 针对g a r f i e l d 所提出的影响力因子( i m p a c t f a c t o r ) 的算法，p i n s k i 和n a r i n 【12 】于7 0 年代提出了一种改进方法，在新方法中使用了不同的 数学模型，对权威性权值这一概念作了进一步的发展。首先，他们定义 了从期刊i 到期刊，的连续的初始权值w ? 的大小为期刊i 中对期刊，的 引用占其全部引用的百分比；然后，期刊j 的最终权值就等于所有引用 7 的期刊的权值与其到期刊，的连续权值的乘积之和，表示成算法的形 式即为谚1 = y 4 ，w ：，于是，对权值向量w 有“= a 7 w ，由此可得，w jj j 为的主特征向量。在该算法中，我们同样可以发现这样一种思想： 如果某个期刊从另一个具有较大权威性权值的期刊中获得定的引用， 则该期刊也会获得较大的权值。 在处理w w w 时，我们遇到的问题是类似的。通过统计指向给定网页 的超链接个数可以帮助我们对该网页的重要性做一个大致的估计，当 然，指向某网页的超链接个数少并不意味着该网页肯定无足轻重，假如 有来自y a h o o ，g o g g l e 等著名搜索引擎的超链接指向它，则该网页仍然 很可能是非常重要的。 有了这些分析，接下来的问题就是怎样去具体确定或是量化“权威 性”这个抽象的概念，而这可以通过使用迭代算法来实现，该算法基于 这样一种思想：如果一个节点被其他权威节点所链接，则该节点也是一 个权威节点。迭代算法的具体实现可以有很多种形式。 1 9 9 2 年，b o t a f o g o 】等人，定义了在超文本环境下的i n d e x 节点 ( 入度大于平均值) 和r e f e r e n c e 节点( 入度小于平均值) 。1 9 9 7 年， 河南大学硕士研究生学位论文第5 页 c a r r i e r e 和k a z m a n ”】提出了一种网页排名思想：即网页的排名由他的 出度和入度之和决定，但还是没有利用到万维网的有向特性。 1 9 9 8 年，b r i n 和p a g e 对p i n s k i n a r i n 影响力因子算法加以改进， 提出了p a g e r a n k 算法【l ”，并应用于w l i 】f w 中，从而形成了g o o g l e 的算 法基础一一p a g e r a n k 算法，这是类似于p i n s k i - n a r i n 计算权威性权值 的权值传播模型的网页排名方法。由于许多优秀的网站没有链向外部的 链接，因此b r i n 和p a g e 采取了一种相对“平滑”一点的算法，对于每 个网页，赋予它和它所链向的每一个网页之间的链接一个较小的，正 的链接权值，然后根据这些链按权值反复迭代计算其均衡后的权值。 这里所说的均衡是指：那些被重要网页所链向的网页往往也是重要 的网页。然而，在很多情况下，网页之间还有许多其他不同的关系模型 在起作用。例如，一些主要的搜索引擎主页，尽管就某一个搜索关键字 来说，它们都应该算是该主题下的重要网页，但是这些搜索引擎主页互 相之间却不存在任何链接。原因很简单，这些搜索引擎之间存在着相互 竞争，他们各自都在尽可能的留住用户。有一种处理方式是通过收集大 量的作为资源列表或向导的网页来获取相关的搜索引擎，并将这些搜索 引擎统一作为一组特殊的重要网页对待，这些网页本身并不需要获取大 量的链接，它们之所以重要是因为它们包含了大量链向其它重要网页的 链接。 在此基础上，k l e i n b e r g 提出了h i t s 算法【3 】，主张将网页分成h u b 网页和a u t h o r i t y 网页，通过迭代最终可以得到排名最高的h u b 网页和 a u t h o r i t y 网页。 1 ，3 本文主要研究工作和创新点 本文深入研究了w e b 结构挖掘的典型算法，主要对主题提取算法 一一h i t s 算法作了详细分析，并在对其算法中所存在的问题作了深入 研究的基础上提出了结合网页内容和链接结构的改进算法一一w h i t s 算法，最后设计了一个实验方案，并开发了实验系统对该算法进行验证， 对实验结果进行了分析讨论，证明了改进后的算法较原算法更合理有 效。 本文的创新点主要有以下几点： 1 、提出了更有效的获取基集的方法，赋予了文档作者间平等的影 第6 页河南大学硕士研究生学位论文 响权重，使精选出的权威和中心网页更为客观合理。 2 、通过内容分析给信息源赋予了主题相关度权重，并运用加权的 i o 操作进行链接分析，使主题相关度较高的信息源得到较高的排序分 值。 3 、对主题相关度很低的信息源进行修剪，排除他们对排序分值计 算的干扰，进一步保证了主题精选结果是真正的查询主题下的权威中 心源。 4 、提出了验证该算法有效性的实验方案，并开发了实验系统，对 该算法进行了验证，并对实验结果进行了分析讨论。 1 4 论文结构 本文共六章，各章节内容安排如下： 第一章是绪论，介绍了本文的研究背景和意义，w e b 结构挖掘算法 的发展和研究现状，本文的主要工作和论文结构安排。 第二章介绍了w e b 挖掘的概念和分类，对w e b 挖掘的关键技术做了 总结。介绍了w e b 挖掘的实现流程。 第三章分析了链接分析的产生背景和主要模型，总结了w e b 链接的 结构和特点，介绍了w e b 结构挖掘的典型算法，讨论了w e b 链接结构分 析在信息检索中的应用。 第四章介绍了h i t s 算法的基本思想，对h i t s 算法进行了详细描述， 深入分析了其不足之处及产生原因，介绍了现有的一些改进算法。 第五章详细介绍了改进思路和改进方法，从网页内容着手，提出了 结合网页内容和链接结构的改进算法一一w h i t s 算法，分析了该算法 的合理性和有效性，介绍了该算法的应用范围。 第六章提出了验证该算法有效性的实验方案，并开发了实验系统， 对该算法进行了验证，并对实验结果进行了分析讨论。 河南大学硕士研究生学位论文第7 页 第二章w e b 数据挖掘 数据挖掘【l z 】是从海量的数据中自动高效地提取有用知识的一种新 兴的数据处理技术。在数据挖掘发展的最初阶段，研究者更多地把注意 力集中在对存放在数据库中的数据进行挖掘，k d d ( k n o w l e d g e d i s c o v e r yi nd a t a b a s e ，从数据库中获取知识) 的概念就是在这种情 况下提出的。近年来，因特网的飞速发展与广泛使用，使得w e b 上的信 息量以惊人的速度增长，目前信息资源已经成为一个天文数字。人们如 何从这海量的数据中获取对自己有用的数据和信息，这一切都急需要 一种能自动地从w e b 资源中发现、获取信息，不至于在资料的海洋中迷 失方向的新技术，因此w e b 挖掘技术应运而生。 2 1w e b 挖掘的定义 w e b 数据挖掘 1 6 , 1 7 , 1 9 起源于数据挖掘，但是传统的数据挖掘对象 大多是针对关系数据库或数据仓库的，所处理的数据具有完整的结构。 而w e b 信息数据具有如下特点： ( 1 ) 大规模海量数据信息。目前w e b 上的资料以t b 数量级计算，且 在迅速地增长和更新。 ( 2 ) 分布广泛。w e b 是一巨大、分布广泛，全球性的信息服务中心。 ( 3 ) 异质、动态的信息源。w e b 及其数据的更新、增长速度极快，也 无固定的模式。w e b 上的信息几乎都是隐藏的、潜在的、未知的。 ( 4 ) 信息具有丰富的内涵。既有涉及经济、文化、教育、新闻、娱 乐、电子商务等丰富的信息服务，又蕴涵着访问页面特性、访问路径特 性、访问时间特性这些潜在的访闯信息。 w e b 是一个巨大的、广泛分布的、异构的、半结构的、超文本超 媒体的、相互联系并且不断变化的信息仓库，其中包括链接信息、访问 使用信息等。这大量的非结构化数据是无法使用现有数据库管理系统来 处理和管理的，这就对w e b 进行有效的信息抽取和知识发现带来了极 大的挑战，也使得w e b 数据挖掘更加复杂。 w e b 挖掘是一项涉及w e b 技术、数据库、机器学习、数据挖掘、统 计学、计算机语言等多学科的综合技术，是从w e b 文档和w e b 活动中抽 取感兴趣的、潜在的有用模式和隐藏信息( 或知识) 的过程。我们对 第8 页河南大学硕士研究生学位论文 w e b 挖掘一般的定义为：从与w e b 相关的资源和行为中抽取感兴趣的、 有用的模式和隐含信息。不同的研究者从不同的角度出发，对w e b 挖掘 有着不同的理解。研究搜索引擎的人着重于w e b 页面上文本资料的分 析；而设计w e b 站点结构的人则着重于用户对w e b 站点访问模式的研究。 南京大学的王继成、张福炎等对w e b 挖掘做如下定义 2 0 】： w e b 挖掘是指从大量的w e b 文档集合c 中发现隐含模式p 的过程。 如果将c 看作输入，将p 看作输出，那么w e b 挖掘的过程就是从输入到 输出的一个映射：；l 斗p 。 2 2w e b 挖掘的分类 当前w e b 上的信息主要分为三类：1 ) w e b 页面中的内容，包括文 本信息和各种多媒体信息；2 ) w e b 页面中超链接之间相互引用的数据； 3 ) w e b 服务器上的用户登录网站的访问日志数据。由此w e b 挖掘主要 分为三类：w e b 内容挖掘，w e b 结构挖掘，w e b 访问日志挖掘。w e b 挖 掘分类结构图如图2 - 1 所示： w e b 挖掘 w e b 内容挖掘 iiw e b 结构挖掘ilw e b 使用挖掘 基于w e b 的 文本挖掘 基于w e b 的 多媒体挖掘 2 2 1w e b 内容挖掘 一般访问 模式追踪 个性化的 使用追踪 文档结构挖掘il 站点结构挖掘 图2 - 1w e b 挖掘分类 w e b 内容挖掘是一种基于网页内容的w e b 挖掘，是从大量的w e b 数据中发现信息、抽取有用知识的过程。w e b 内容挖掘针对的对象是 河南大学硕士研究生学位论文第9 页 w e b 文档信息和多媒体信息，就其挖掘内容而言，可将其分为对w e b 文本文档( 包括t e x t 、h t m l 等格式) 和多媒体文档( 包括i m a g e 、a u d i o 、 v i d e o 等媒体类型) 的挖掘。基本的w e b 内容挖掘是一种文本挖掘。 w e b 文本挖掘【18 过程如图2 2 所示： 图2 2w e b 文本挖掘过程 2 2 2w e b 结构挖掘 w e b 结构挖掘是从网页的超链接中发现其结构及其相互关系。通 过找到隐藏在一个个页面之后的链接结构模型，就可以利用这个模型 对网页分类或者为网页建立相似性度量，有助于用户找到相关主题的 权威站点。w e b 结构挖掘和内容挖掘有着紧密的联系，二者都是对w e b 上原始数据进行挖掘，在一项应用中通常要结合这两种挖掘任务。 2 2 3w e b 使用挖掘 w e b 使用挖掘是从用户“访问痕迹”中获取有价值的信息，是对 w e b 上日志数据及相关数据的挖掘。w w w 中的每个服务器都保留了访问 日志( w e b8 c c e s sl o g ) ，记录了关于用户访问和交互的信息。分析这 些数据可以帮助理解用户的行为，从而改进站点的结构，或为用户提 供个性化的服务。这方面的研究主要有两个方面：一般的访问模式追 踪和个性化的使用记录追踪。一般的访问模式追踪通过分析使用记录 第1 0 页河南大学硕士研究生学位论文 来了解用户的访问模式和倾向，以改进站点的组织结构。而个性化的 使用记录追踪则倾向于分析单个用户的偏好，其目的是根据不同用户 的访问模式，为每个用户提供定制的站点。 我们对上述w e b 挖掘总结如表2 - i 所示： 表2 1w e b 挖掘总结 w e b 内容挖掘w e b 结构挖掘w e b 使用挖掘 处理i r 方法数据库方法 数据无结构数据、w e b 结构数据用户访问w e b 类型半结构化数 半结构化数数据 据据 自由化文本、w e b 文档内及 s e r v e r1 0 9 、 主要h t m l 标记的h t m l 标记的超文文档间的超 p r o x y s e r v e t 数据超文本本链 l o g 、 c l je n t1 0 9 词集、概念、 表示段落、i r 的o e m 关系 图关系表、图 方法三种经典模 型 t f i d f 、统计、机器学习、专 处理机器学习、自数据库技术有算法如统计、机器学 方法然语言理解h i t s 、习、关联规则 p a g e r a n k 模式发现、数据向页面权重、用户 主要分类、聚类、导、多层数据库、分类聚类、p r o f i l e 、自适 应用模式发现站点创建与维护模式发现应w e b 站点、 商业决策 2 3w e b 挖掘中的关键技术 w e b 挖掘中常用的技术有w e b 使用的特有的路径分析技术，数据 挖掘领域常用的关联规则、序列模式、分类聚类技术等。 河南大学硕士研究生学位论文第11 页 2 3 1 路径分析技术 用路径分析技术进行w e b 数据挖掘时，最常用的是图。因为w e b 可以用一个有向图来表示，g = ，e ) ，v 是页面的集合，e 是页面之 间的超链接集合，页面定义为图中的顶点，而页面之间的超链接定义 为图中的有向边。顶点v 的入边表示对v 的引用，出边表示v 引用了其 它的页面，这样形成网站结构图，从图中确定最频繁的访问路径。 2 3 2 关联规则挖掘技术 关联规则挖掘技术主要用于从用户访问序列数据库的序列数据库 的序列项中挖掘出相关的规则就是要挖掘出用户在一个访问期间 ( s e s s i o n ) ，从服务器上访问的页面文档之间的联系，这些页面之间 可能并不存在直接的参引( r i f e r e n c e ) 关系。最常用的是用a p r i o r 算法，从事务数据库中挖掘出最大频繁访问项集，这个项集就是关联 规则挖掘出来的用户访问模式。 2 3 3 序列模式挖掘技术 序列模式数据挖掘就是要挖掘出交易集之间的有时间序列关系的 模式。它与关联挖掘技术都是从用户访问下的日志中寻找用户普遍访 问的规律，关联挖掘技术更注重事务内的关系，序列模式技术则注重 事务间的关系。 2 3 4 聚类分类技术 分类规则可以挖掘出某些共同的特性，这个特性可以用来对新添 加到数据库里的数据项进行分类。在w e b 资料挖掘中，分类技术可以 根据访问这些用户而得到个人信息或共同的访问模式得出访问某一服 务器文档的用户特征。聚类技术则是对符合某一访问规律特征的用户 进行用户特征挖掘。最后进行模式分析，挖掘出人们可理解的知识的 模式解释。 第1 2 页河南大学硕士研究生学位论文 2 4 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 3 , 2 6 流程如图2 3 所示： 图2 - 3w e b 挖掘实现流程 第一步：确立目标样本，即由用户选择目标文本，作为提取用户 的特征信息； 第二步：提取特征信息，即根据目标样本的词频分布，从统计词 典中提取出挖掘目标的特征向量并计算出相应的权值； 第三步：网络信息获取，即先利用搜索引擎站点选择待采集站点， 再利用r o b o t 程序采集静态w e b 页面，最后获取被访问站点网络数据 库中的动态信息，生成w e b 资源索引库； 第四步；信息特征匹配，即提取索引库中的源信息的特征向量， 并于目标样本的特征向量进行匹配，将符合阈值条件的信息返回给用 户。 河南大学硕士研究生学位论文第1 3 页 第三章w e b 链接结构分析 w e b 是一个超文本的文档集合，文档( 页面) 之间的超链接 ( h y p e r l i n k ) 是w e b 的最大特点之一，页面之间相互链接并形成了一 定的链接结构( h y p e r l i n ks t r u c t u r e ) f 2 ”。链接结构中隐含着大量的 人类判断，充满了丰富的资源和信息，分析和利用链接结构信息的过 程被称为w e b 链接结构分析。w e b 链接结构分析在w w w 的很多研究领 域起着越来越重要的作用。w e b 信息检索、w e b 数据挖掘等w e b 上数据 管理的研究都需要对w e b 的链按结构进行分析和研究。 3 1w e b 链接结构分析产生的背景 在传统上，人们对w e b 信息的分析和获取主要是依靠对网页内容的 分析和处理来进行的。例如，传统的搜索引擎对网页上的文本信息进行 分析、索引，并将处理后的信息存储在数据库中，然后根据用户查询输 入进行分析，获得查询结果。然而单一依据网页文档信息进行信息分析 和获取具有局限性：首先，网页的文本信息一般是由自然语言组成，对 其的分析处理不可能十分精确；其次，w e b 规模正在迅速增长，w e b 信 息量随着网页数目的急剧增加而迅速增大，而现在对w e b 信息进行分析 获取的程序一般是中央化的( 不是分布式的) ，其只具有有限的处理能力 和存储能力，不能满足w e b 信息量迅速增大的需要。 近年来，随着人们对w e b 信息检索研究的不断深入，人们发现w w w 上大量的网页之间相互链接并形成了一定的w e b 链接结构，这种链接结 构中隐含着丰富的信息和资源。w e b 上网页之间的链接关系有点类似于 引文分析( c i t a t i o n a n a l y s i s ) 中的引用关系：在科学引文索引中，如果 一篇文章被引用的次数越多，则认为该文章的学术价值越高。w e b 上网 页用超链接来“推荐”一些信息质量较高的网页，如果一个网页被其它 网页链接得越多，则说明它越重要。当然，网页之间的链接关系远较引 文分析中的引用关系复杂，如w e b 上的有些超链接可能是为了辅助导航 ( 如同一站点之间的超链接) 、商业广告、赞助商、友情交换链接或指向 c o l 脚本而设置的，但大多数超链接则是属于信息链( i n f o r m a t i v e 1 i n k ) ，其提供了一种信息存取的途径，它往往指向与当前页面主题相同 或相关的高质量页面。研究发现，通过分析和利用w e b 上的链接结构信 第14 页河南大学硕士研究生学位论文 息，可以挖掘出许多有用的信息，可极大地提高w e b 信息检索的质量。 3 2w e b 链接结构分析模型 大多数链接分析的研究都会有一个基本的w e b 结构的表示模型，各 种度量和算法都基于这个模型衍生而来。不同类型的模型包括图结构模 型，马尔可夫模型，最大流模型、概率关系模型等。 3 2 1 图模型 图论( g r a p ht h e o r y ) 是数学的一个分支，它是以图为研究对象，研 究节点和边组成的图形的数学理论和方法随着科学技术的不断发展， 图论的应用越来越广泛，图论在解决运筹学、网络理论、信息论、控制 论、博弈论，尤其是计算机科学等各个领域的问题时显示出越来越大的 优越性。 图论中的基本元素是图。图是由若干给定的点及连接两点的线( 边) 所构成的图形。这种图