（计算机软件与理论专业论文）web社区结构挖掘的研究与应用.pdf

摘要 摘要 w e b 是一个复杂超文本所组成的巨大信息源，而且以很快的速度在不断的 扩大，w e b 在发展过程中存在着大量的社区，这些社区是w e b 组织中非常重要 的信息，社区可以为用户提供有价值的、可靠的、及时的信息，社区反映了w e b 中普遍存在的、复杂的聚团关系和层次关系。如何利用和发现w e b 中的社区， 是w e b 挖掘的一个研究方向。 本文在分析了w 曲社区的定义、社区的发展、w e b 数据挖掘的概念与分类、 链接分析技术等基础理论的基础上，对w e b 社区结构挖掘的典型算法：基于重 要度分析的p a g e r a n k 算法、基于有向二分图的t r a w l i n g 算法、基于主题提取的 h i t s 算法进行了详细的分析和比较。重点研究了传统最大流算法和基于h i t s 算法的边容量分配最大流算法的实现过程及在社区挖掘中存在的问题。传统最大 流算法虽然能较好的解决主题漂移问题，但对社区的质量和数量也会带来许多不 利的影响。而基于h i t s 算法的边容量分配最大流算法因为采用两个结点的中心 值和权威值的简单加和平均作为边容量，从而有可能增加噪音页面被提取到社 区。为解决上述算法中存在的问题，本文提出了基于传递概率的边容量分配最大 流改进算法，该算法将节点连接度和节点相关度这两个不同角度的属性特征量化 地融合到连边的传递概率中，根据传递概率分配边的容量，传递概率的计算综合 考虑了节点之i n j 的多种因素，对原算法进行了优化。 本文最后设计了一个w e b 社区结构挖掘系统，该系统利用本文提出的改进 算法进行w e b 社区挖掘，经过大量的实验证明，该系统能较好的解决传统算法 在社区挖掘中存在的一些问题，进一步提高了w e b 社区挖掘的准确性。 关键词：w e b 社区，w e b 数据挖掘，h i t s ，最大流，传递概率 a b s t r a c t a b s t r a c t w e bi st h eh u g ei n f o r m a t i o ns o u r c ec o n s t i t u t e d b yac o m p l e xh y p e r t e x t c o m p o s e s ，a n du n c e a s i n g l ye x p a n d e di naf a s ts p e e d m a n yc o m m u n i t i e sa r ee x i s t e d i nt h ew e bd u r i n gt h ed e v e l o p m e n tp r o c e s s t h e s ec o m m u n i t i e sb e c o m et h ev e r y i m p o r t a n ti n f o r m a t i o no ft h ew e bo r g a n i z a t i o n t h ev a l u a b l e ，r e l i a b l ea n dp r o m p t i n f o r m a t i o nc a nb ep r o v i d e dt ot h ec u s t o m e r sb yt h ec o m m u n i t y t h ec o m m u n i t y r e f l e c t e dt h eu n i v e r s a l e x i s t e n c e ，c o m p l e x t o g a t h e r t h e g r o u pr e l a t i o n s a n d h i e r a r c h i c a lr e l a t i o no nw e b h o wt ou s ea n dd i s c o v e rt h ec o m m u n i t yi nw e bi sa r e s e a r c hd i r e c t i o no fw e b m i n i n g t h i sp a p e rh a sa n a l y z e dt h ed e f i n i t i o na n dd e v e l o p m e n to fw e bc o m m u n i t y , c o n c e p ta n dc l a s s i f i c a t i o no ft h ew e bd a t am i n i n g ，a n dt h el i n kp a r s i n gt e c h n i q u e i t h a sc a r r i e do nt h ed e t a i l e d a n a l y s i sa n dt h ec o m p a r i s o nf o r t h ec l a s s i c a lw e b c o m m u n i t ys t r u c t u r em i n i n ga l g o r i t h m ，b a s e do np a g e r a n ka l g o r i t h mo fi m p o r t a n c e a n a l y s e s ，t r a w l i n ga l g o r i t h mo fb i p a r t i t eg r a p h s ，a n dh i t sa l g o r i t h mo fs u b j e c t e x t r a c t i o n t h et r a d i t i o n a lm a x i m u mf l o wa l g o r i t h ma n dt h em a x i m u mf l o wa l g o r i t h m b a s e do nt h eh i t sa l g o r i t h m ss i d ec a p a c i t ya s s i g n m e n th a v eb e e nm a i n l ya n dd e e p l y r e s e a r c h e d ，a n dp o i n t e do u tp r o b l e m se x i s t e dd u r i n gt h ec o m m u n i t ym i n i n g a l t h o u g h t h es u b j e c td r i f t i n gp r o b l e mc a nb ew e l ls o l v e db yt h et r a d i t i o n a lm a x i m u m f l o w a l g o r i t h m ，b u ti tw i l la l s ob r i n gal o to fd i s a d v a n t a g ei n f l u e n c e st ot h ec o m m u n i t y s q u a l i t ya n dq u a n t i t y t h em a x i m u mf l o wa l g o r i t h mb a s e do nh i t sa l g o r i t h m ss i d e c a p a c i t ya s s i g n m e n tu s i n gh u bv a l u e sa n da u t h o r i yv a l u es i m p l ya d d e da ss i d e c a p a c i t y ，w h i c hh a sap o s s i b i l i t yt h a tt h en o i s ep a g em i g h tw o u l db ee x t r a c t i no r d e r t os o l v et h e a l g o r i t h me x i s t i n gp r o b l e m m e n t i o n e da b o v e ，a n i m p r o v e d m a x i m u m f l o wa l g o r i t h mw a s p o i n t e do u tb a s e do nt h et r a n s m i s s i o np r o b a b i l i t y ss i d e c a p a c i t ya s s i g n m e n ti nt h i sp a p e r t h i sa l g o r i t h mm a k e st w od i f f e r e n ta n g l e sa t t r i b u t e p r o p e r t yq u a n t i f i c a t i o nf u s e st h ej o i n tc o n n e c t i o nc o n t i n u a l l yo fn o d el i n k i n ga n d n o d er e l e v a n c ei n t ot h et r a n s m i s s i o np r o b a b i l i t y t h es i d ec a p a c i t yd i s t r i b u t e db a s e d o nt h et r a n s m i s s i o n p r o b a b i l i t y t h ec o m p u t a t i o no f t r a n s m i s s i o np r o b a b i l i t y i l a b s t r a c t c o n s i d e r a t i o nn o d ea n dn o d em a n yk i n d so ff a c t o r s ，t h ea l g o r i t h mh a sb e e no p t i m i z e d o no r i g i n a la l g o r i t h m a tl a s t ，aw e bc o m m u n i t ys t r u c t u r em i n i n gs y s t e mh a sb e e nd e s i g n e di nt h i s p a p e lw h i c hd i s c o v e r i e dw e bc o m m u n i t i e sw i t ht h ei m p r o v e da l g o r i t h m i ti sp r o v e d w i t hn u m b e r so fe x p e r i m e n tt h a tt h es y s t e mc a nw e l ls o l v es o m et r a d i t i o n a la l g o r i t h m p r o b l e m se x i s t e dd u r i n gt h ec o m m u n i t ym i n i n g t h ea c c u r a c yo ft h ew e bc o m m u n i t y m i n i n gi sm o r ei m p r o v e d k e yw o r d s ：w e bc o m m u n i t y , w e bd a t am i n i n g ，h i t s ，m a x i m a l f l o w , t r a n s m i s s i o n p r o b a b i l i t y i i i 西北大学学位论文知识产权声明书 本人完全了解西北大学关于收集、保存、使用学位论文的规定。 学校有权保留并向国家有关部门或机构送交论文的复印件和电子版。 本人允许论文被查阅和借阅。本人授权西北大学可以将本学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。同时授权中国科学技术信息研 究所等机构将本学位论文收录到中国学位论文全文数据库或其它 相关数据库。 保密论文待解密后适用本声明。 学位论文作者签名：孥坠生室 指导教师签名： 计年2 7 月彤日力夕譬年多月8 日 西北大学学位论文独创性声明 本人声明：所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究 成果。据我所知，除了文中特别加以标注和致谢的地方外，本论文不包含其他人已经 发表或撰写过的研究成果，也不包含为获得西北大学或其它教育机构的学位或证书而 使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明确 的说明并表示谢意。 学位论文作者签名： 别丧 沙学年易月8 曰 第一章绪论 1 1 研究背景 第一章绪论帚一早殖化 随着互联网的飞速发展，人们越来越多地在互联网上发布和获取信息。w e b 已经成为信息制造、发布、加工和处理的主要平台，其涵盖的信息面之广阔、信 息量之丰富、都使得它毫无疑问地成为当前最大的信息资源库。随着海量信息涌 入万维网，互联网中特有的许多问题，诸如超大规模的非结构化文档数量、良莠 不齐的网页质量，包含在文档中的大量多媒体信息【1 1 ，甚至相当含糊或不规范的 用户查询表示等，必然给检索数据带来很大的困难，著名搜索引擎营销公司 i p r o s p e c t 的调查报告表明【2 】：2 0 0 6 年6 2 的用户只点击搜索结果页第一页的结 果，而高达9 0 的用户只点击搜索结果页的前三页罩的结果。而在2 0 0 2 年，这 两个数字分别为4 8 及8 1 。 因此，在w e b 信息检索中，如何能够提取出与某个主题信息相关的网页变 得异常重要。整个w 曲图中大约有9 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 结合起来，进行w e b 挖掘活动将更有效的从 w e b 中抽取感兴趣的、潜在的、有用的信息。w e b 挖掘是一项综合技术，涉及 了统计学、人工智能、模式识别、并行计算、机器学习、数据库等多个领域。 w e b 结构挖掘作为w e b 数据挖掘的一个重要方面，主要挖掘w e b 潜在的链接结 构模式，通过分析一个网页链接和被链接数量以及对象来建立w e b 自身的链接 结构模式，可以用于网页归类，并且可以由此获得有关不同网页间相似度及关联 度的信息，有助于用户找到相关主题的权威站点和网络社区。 第一章绪论 1 2 国内外发展现状 1 2 1 国外发展现状 数据挖掘是一种新兴的信息处理技术，在信息的利用和提取中发挥着日益重 要的作用。w e b 社区挖掘是数据挖掘的一个方向，也是近几年众多研究者关注的 研究领域，许多研究还处于起步阶段，还需研究者更加深入地认识和探讨。 w a t t s 和s t r o g a t z l 4 j 于1 9 9 8 年提出了小世界网络w s 模型，比较合理地反映 了既不完全规则也不完全随机的w e b 网络的统计特性；1 9 9 9 年f a l o u t s o s l 5 j 等人 发现了w e b 拓扑结构中度的幂定律分布现象；随后b r o d e r l 6 】等人对w 曲图的连 通性进行了研究，提出了“蝴蝶结”状的w e b 连通域结构图，并指出这些连通 域的规模同样服从幂数定律分布；k u m a r1 7 j 等人基于互联网拓扑特征就w e b 图 进行了数学建模研究，并提出了一种随机拷贝的机制来模拟w e b 超链接的创建 过程；此外，h u b e r m a n 和a d a m i c1 8 】提出了网站规模分布服从幂数定律的h a 模型，b a r a b a s i 9 】等人提出了网页节点的度分布服从幂数定律的b a 模型，并用 偏好性依附解释了幂数分布形成的机制等，为人们对w e b 社区的理解提供了理 论依据。w e b 社区是一种很自然的网络群体，也是一种很重要的网络资源，目的 发现w e b 社区的方法大都基于链接结构和w e b 图模型的思想。通过w e b 图来研 究w e b 社区将会有更好的效果，所以很多的研究工作关注通过w e b 的超链接结 构关系来挖掘w e b 社区资源。 斯坦福大学的l a r r yp a g e 和s e r g e yb r i n f l o j 在1 9 9 8 年发明了p a g e r a n k ，是 一项利用威望值改善w e b 搜索结果的技术。斯坦福大学计算机科学系t a h e r h a v e l i w a l a 【1 1 j 提出了主题敏感( t o p i c s e n s i t i v e ) p a g e r a n k 算法，这些改进的 p a g e r a n k 算法可以用来发现与主题相关的w e b 社区，但在发现社区数量上还需 进一步研究。美国康奈尔大学教授k l e i n b e r g 和g i b s o n l l 2 】等人提出的h i t s 算 法模型提供了一种很自然的方式，将链接的结构用一组中心性网页和权威性网页 展现出来，尽管这些中心性网页和权威性网页之问并不知道相互的存在，但是可 将这一组中心性网页和权威性网页理解为一个w e b 社区。k l e i n b e r g 等人认为需 要通过用一小部分高权威性的相关网页来表示社区的主题。利用h i t s 算法除了 2 第一章绪论 依赖于主题的广泛性之外，同时还依赖于w e b 知识结构，那些在w e b 上存在更 多甚至更合理链接的主题，利用h i t s 具有较好的结果。k u m a r1 1 3 】等人从二分有 向图的角度对w e b 社区给出了一种明确的定义描述。根据随机二分图的理论， 一个足够大而稠密的随机二分图将以很高的概率包含一个完全二分有向图。如果 将某个社区的链接结构看作一个大而稠密的二分有向图，则社区的核就可以用一 个完全二分有向图来表示。即如果在w e b 上存在一个某种主题的社区，那么这 种二分的核必包含在其中，即指出w e b 的创建过程虽然是分布的、无计划的过 程，但决不是随机的，经历了从经验假设到客观分析，从单纯的计算机网络研究 到复杂系统特征化研究的的过程，新超链接的创建与w e b 中已存在的超链接具 有某种依赖关系。但对于如何确定核的参数，以及采用怎样的方法从整个w e b 结 构图中枚举出所有社区的核，k u m a r 等人并没有为核参数声明特定的值。 f l a k e 1 4 , 1 5 】最先提出通过最大流算法来抽取w e b 社区，采用分配给各边一个相同 的容量值的办法来解决h i t s 算法存在的主题漂移问题，但对社区的质量和数量 也会带来许多不利的影响，而且随着w e b 图中节点的增加，噪音页面也会增加。 i b ma l m a d e n 实验室在w 曲社区研究方面取得了一些重要的进展【1 6 】，开发了 a r c 系统和c l e v e r 系统，其研究基础仍然起源于w e b 结构挖掘的h i t s 算法。 1 2 2 国内发展现状 与国外相比，国内的研究起步较晚，目前国内从事该领域研究的人员主要集 中在大学，也有部分在研究所或公司。一般集中于学习算法的研究、实际应用以 及有关理论方面的研究。大多数研究项目是由政府资助进行的，如国家自然科学 基金、8 6 3 计划、“九五”计划等。中国人民大学信息学院对w e b 社区发现技术 进行了综述，对社区的发现技术做了较为全面的分析，并提出了w e b 社区未 来的研究趋势。复旦大学计算机与信息技术系，提出基于图论的频繁模式挖掘 w e b 权威页面和社区【1 8 】，选择了惟一标号图进行分析，集图论和频集生成 a m g m 算法和s f p 算法，有效地挖掘简单图中连通频繁子图，但在如何从惟一 标号图中产生连通频繁图方面还需要更进一步的研究。复旦大学还运用s f p 算 法构造了e s f p 算法，完成从复杂的网络拓扑结构中提取权威页面和社团1 9 j ，该 3 第一章 绪论 算法减轻了用户需要花费大量时间过滤搜索引擎返回的不满意的结果问题，但在 具有相同结点的权重处理上还需要更加数学化或接近实际含义的计算方式。中南 大学信息科学与工程学院也开展了w e b 社区的相关研究1 2 0 ，指出了基于链接结 构的社区发现算法的缺陷和改进方向。中科院计算技术研究所对文本聚类及其在 w e b 社区搜索中的应用进行了研究【2 l 】，利用文本聚类重新组织搜索结果以提高 w e b 社区信息检索效率，并且利用聚类验证评估了文本聚类算法的性能。 1 3 选题的意义 随着互联网的不断发展，人们越来越多地在互联网上发布和获取信息，海 量信息涌入力维网，这种增长给社会许多阶层都带来了有用信息，但检索数据必 然会成为一个很大的问题，如何利用和发现w e b 中的有用信息变得具有挑战性。 在w e b 的发展过程中存在着大量的社区，这些社区可以为用户提供有价值 的、可靠的、及时的信息。社区代表了w e b 的社会活动，对社区的深入研究具 有重要的理论和应用价值：可以纵观w e b 全貌，深入了解w e b 的进化过程；了 解w e b 中知识信息及组织结构；提高w e b 搜索的性, 日a 匕n 和精确性；进一步理解 w e b 拓扑关系，分析w e b 拓扑所对应的功能或语义内涵；实现更有效的网络路 由，研究网络的鲁棒性。 虽然国内外许多学者对w e b 社区挖掘进行了大量的研究，也取得了较好的 效果，但由于社区的数量巨大，其中许多社区还处于形成阶段，现有的社区也在 不断更新。因此，需要采用更多高级、复杂的社区挖掘方法，发现那些潜在的、 即将形成的有价值的社区。在此背景下，本文对w e b 社区挖掘算法进行了深入 研究，提出了基于传递概率的边容量分配最大流改进算法，传递概率的计算综合 考虑了节点属性之间的连接度、节点之问的相关度、节点之间发生信息传递等多 种因素。利用该算法进行w e b 社区挖掘，能较好的解决社区挖掘过程中产生的 主题漂移、噪音页面等问题，同时也能发现更多有价值的社区。 1 4 本文主要研究内容 本文深入研究了w e b 社区结构挖掘的典型算法，主要对传统最大流算法和 4 第一章绪论 基于h i t s 算法的边容量分配最大流算法作了详细分析，并对其算法中所存在的 问题作了深入研究：g f l a k e 采用边容量分配最大流算法虽然可以较好地解决 h i t s 算法存在的主题漂移问题，但对社区的质量和数量也会带来许多不利的 影响，随着w e b 图节点的增加，噪音页面相应也会增加，在很多情况下边的容 量提升得越大，主题漂移的问题就越易显现出来。而i m a f u j i 等人提出了基于h i t s 算法的边容量分配最大流算法，即利用一条边的两个端点的中心值和权威值来计 算分配边的容量，虽然能较好的解决传统最大流算法中存在的问题，但也会产生 一些噪音页面，原因是只使用了一条边所关联的两个结点的中心值和权威值的简 单加和平均作为边容量，当其中一个结点具有高权威值或高中心值的时候，会对 边容量产生较大的影响，即使另一个结点是不相关页面，也会给该条边分配较大 的容量，从而增加噪音页面被提取到社区中的可能性。 为了更好地解决上面算法中存在的问题，本文提出了一种更好的分配边容 量的方法基于传递概率的边容量分配最大流改进算法，即不是给每条边分 配一个相同的常量值，也不是用两个端点的中心值和权威值计算结果分配边的容 量，而是依据节点之间连接度、节点之间相关性等因素进行综合度量，将节点连 接度和节点相关度这两个不同角度的属性特征量化地融合到连边的传递概率中， 根据传递概率为不同的边分配不同的边值。最后，本文根据改进的最大流算法设 计了w e b 社区结构挖掘系统，进行了大量实验，对实验结果进行了分析和评价， 通过实验证明了改进后的算法较原算法更加优化，能进一步提高w e b 社区挖掘 的准确性。 第二章w e b 挖掘概述 2 1w e b 社区概述 第二章w e b 挖掘概述 自2 0 世纪9 0 年代之后，随着网络技术的发展，尤其是i n t e m e t 的广泛应用， w e b 已经成为一个巨大的、分布广泛的全球信息服务中心。因此，如何利用w e b 快速、准确地获得信息及隐藏在信息中的知识是人们迫切需要的。由于w e b 数 据具有海量的、无组织的、异构等特征，使得如何有效地利用w e b 上的数据成 为难题。尽管w e b 数据存在无组织、海量的特点，但是w 曲仍存在一些规律【2 2 】。 从宏观上看【2 3 】，w e b 是一个“b o w t i e ”形状，由一个巨大的“强链接部件与 一个连接到“强链接部件”的“i n ”部件，一个被“强链接部件连接的“o u t 部件，和其他页面组成的“t e n d r i l ”部件。从微观上看，它是根据“主题 聚集 在起的多个社区。 互联网社区是一些具有共同兴趣的单位和个人所组成的独特小组，这些小组 的兴趣通常表现为某个主题下的若干子题，他们通过共同认可的网页实现相互间 的联系。这些小组可以被一些公开页面所引用，称为“c y b e r 社区”、“w 曲社区” 或者直接称为“社区”。社区可以为用户提供有价值的、可靠的、及时的信息， 社区代表了w e b 中的社会活动，对社区的深人研究可以了解w e b 中知识信息及 其组织结构的发展状况。发现这些社区可以帮助我们对于w e b 知识性和社会性 做出评估，也可以研究某个方面感兴趣用户的组成形式。因此，采用将w e b 信 息以社区的形式组织，为信息查询提供了有效和便捷的途径。w e b 中存在着大量 的知名的、明确定义的社区，这些社区基本表现为新闻组( n e w s g r o u p ) 、网圈 ( w e b r i n g ) ，或者如y a h o o ! 和l n f o s e e k 中目录形式的资源集合，以及如g e o c i t y 中的社民等。 知名的社区是靠人工发现和维护的，如y a h o o ! 和l n f o s e e k 中的目录，可以请 一些分类专家对信息进行分类组织成为树形结构。用户可以通过信息结构树方式 浏览页面。虽然人工维护的结构树对于许多主题的搜索非常有效，但是该树的建 立一般都是主观的。结构树的建立和维护极为昂贵，不但更新缓慢，而且无法覆 6 第二章w e b 挖掘概述 盖窄范围的主题。另外，在数量巨大的社区中，许多社区处于形成阶段，或者在 不断更新。因此，通过人工的方式去跟踪这些社区是非常困难的。由于这些潜在 社区的数量大大超过明确定义社区，人工明确定义的社区无法识别出这些潜在的 社区。因此，需要自动化或半自动化的社区挖掘技术，挖掘那些潜在的，即将形 成的社区。 2 2w e b 数据挖掘概述 2 2 1w e b 数据挖掘的定义 w e b 数据挖掘起源于数据挖掘，数据挖掘( d a t am i n i n g ) 是指从大型数据库 的数据中提取人们感兴趣的知识，而这些知识是隐含的、事先未知的、潜在的有 用信息。如股票经纪人需要从日积月累的大量的股票行情变化的历史记录中发现 其规律，以供预测未来趋势之用。超级市场的经理人员希望能从过去几年的销售 记录中，分析出顾客的消费习惯和行为，以便及时变换营销策略等等。数据挖掘 的提出最初是针对大型数据库的，但是从更广泛的角度来讲，数据挖掘意味着在 一些事实或观察数据的集合中寻找模式的决策支持过程。因而，数据挖掘的对象 不仅仅可以是数据库，还可以是任何组织在一起的数据集合，如w w w 信息资 源等。w w w 以超文本的形式给用户提供了包含从技术资料、商业信息到新闻报 道、娱乐信息等多种类别和形式的信息，可以说是w e b 当今世界上最大的电子 信息仓库，蕴含着巨大潜在价值的知识。然而，i n t e r n e t 是一个具有开放性、动 态性、异构性的全球分布式网络，资源分布分散，没有统一的管理和结构，这就 导致了信息、知识获取的困难，即所谓的r i c hd a t ap o o ri n f o r m a t i o n 的问题。因 此，运用现有数据挖掘技术对分布的、异构的w e b 信息资源进行挖掘，就成为 了数据挖掘技术的挑战和未来的发展方向，由此产生了基于w e b 的数据挖掘。 w e b 数据挖掘( w e bd a t am i n i n g ) ，简称w e b 挖掘，是一项综合技术，涉及 w e b 、数据挖掘、计算机语言学、信息学、数据库技术等多个领域。w e b 数据挖 掘是针对包括w e b 页面内容、页面之间的结构、用户访问信息、电子商务信息 等在内的各种w e b 数据源，在一定基础上应用数据挖掘的方法以发现有用的隐 含的知识的过程1 2 4 j 。 7 第二章w e b 挖掘概述 一般地将w e b 挖掘定义为： 定义1 ：w e b 数据挖掘是指从大量w e b 文档的集合c 中发现隐含的模式p 。 如果将c 看作输入，p 将看作输出，那么w e b 挖掘的过程就是从输入到输出的 一个映射c - p 。 w e b 挖掘的处理流程为： ( 1 ) 查找资源 任务是从目标w e b 文档中得到数据，值得注意的是有时信息资源不仅限于 在线w e b 文档，还包括电子邮件、电子文档、新闻组，或者网站的同志数据甚 至是通过w e b 形成的交易数据库中的数据。 ( 2 ) 信息选择和预处理 任务是从取得的w e b 资源中剔除无用信息和将信息进行必要的整理。例如 从w e b 文档中自动去除广告连接、去除多余格式标记、自动识别段落或者字段、 并将数据组织成规整的逻辑形式甚至是关系表。 ( 3 ) 模式发现 自动进行模式发现，可以在同一个站点内部或在多个站点之间进行。 ( 4 ) 模式分析 验证、解释上一步骤产生的模式。可以是机器自动完成，也可以是与分析人 员进行交互来完成。w e b 挖掘作为一个完整的技术体系，在进行挖掘之前的信息 获得i r ( i n f o r m a t i o nr e t r i e v a l ) 和信息抽取i e ( i n f o r m a t i o ne x t r a c t i o n ) 相当重要。 信息获得( i r ) 的目的在于找到相关w e b 文档，而信息抽取( i e ) 的目的在于从文 档中找到需要的数据项目。模式分析的一个重要任务就是对数据进行组织整理并 适当建立索引。 w e b 社区挖掘的研究也是k d d ( k n o w l e d g ed i s c o v e r yd a t a b a s e s ) 的一个研 究方向，k d d 的模型如图2 1 所示。 8 第二章w e b 挖掘概述 图2 1k d d 模型 行动和实现 在图2 1 中，目标定义的主要目的是清楚地说明需要完成什么，应将总目标 以具体的小目标的形式陈述出来，一组可行的资源数据对任何一个成功的数据挖 掘项目来说都是最重要的，数据预处理是数据清理的一种形式，它包括解决噪声 问题和处理缺失的信息。由于诸多原因，数据转换是非常必要的，它可以采用多 种形式，知识发现的实验性和迭代性在知识发现过程中表现得非常明显，数据挖 掘完成后，就会对模型进行评估。解释和评估的目的是确定学习者模型是否是可 接受的，而且可以用于解决检验环境领域以外的难题，如果取得了可接受的结果， 就到了将所获得知识转换为用户可以理解的术语的阶段。数据挖掘的最终目标是 应用所学到的东西，由知识挖掘过程的成功应用而可以采取的一组可能的行动， 用在知识发现过程中学习到的知识推动新的科学研究。 2 2 2w e b 数据挖掘的分类 在逻辑上可以把w e b 看作是位于物理网络之上的一个有向图g = ( y ，e ) ，其 中节点集y 对应于w e b 上的所有文档，而有向边集e 则对应于节点之间的超链 接( h y p e r l i n k ) 。对节点集作进一步的划分，v - - k ，k ) 所有的非叶节点是h t m l 9 第一二章w e b 挖掘概述 文档，其中除了包括文本以外，还包含了标记以指定文档的属性和内部结构，或 者嵌入了超链接以表示文档间的结构关系。叶节点k 可以是h t m l 文档，也可 以是其他格式的文档。w e b 上信息的多样性决定了w 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 bc o n t e n tm i n i n g ) 、w e b 结构挖掘( w e bs t r u c t u r em i n i n g ) 、w e b 使用挖掘( w e b u s a g em i n i n g ) 三大类【2 5 1 ，w e b 数据挖掘分类结构图如图2 2 所示： w 曲挖掘 内容挖掘 il 结构挖掘ii 使用挖掘 文本 挖掘 多媒体 挖掘 超链接 挖掘 页面结li 用户访问i1 分析定制 构挖掘li 模式分析iw e b 站点 图2 2w e b 挖掘 ( 1 ) w e b 内容挖掘( w e bc o n t e n tm i n i n g ) w e b 内容挖掘是从网络的内容数据文档中发现有用信息的过程。网络信 息资源类型众多，从网络信息源的角度看，大量的网络信息资源可以直接从网上 抓取、建立索引、实现检索服务，但是还有一些网络信息是“隐藏”的，如由用 户的提问而动态生成的结果，或是存在d b m s 中的数据，或是那些私人数据， 它们无法被索引，从而无法提供对它们有效的检索方式。从资源形式看，网络信 息内容是由文本、图像、音频、视频、元数据等形式的数据组成的，因此，网络 内容挖掘是一种多媒体数据挖掘形式。这个领域的研究经常包括其它学科的技 术，比如信息检索( i n f o r m a t i o nr e t r i e v a l ，i r ) 和自然语言处理( n a t u r el a n g u a g e p r o c e s s i n g ，n l p ) 。 w e b 内容挖掘主要应用于超文档的分类、学习w e b 文档之间的关系、学习 模式或规则、半结构查询语言与模式抽取( l o r e l 、d i p r e 迭代算法等) 、半结构 1 0 第二章w e b 挖掘概述 化模式( s c h e m a ) 抽取、w e b 异构数据集成( i n f o r m a t i o ni n t e g r a t i o n ) 、基于o n t o l o g y 的语义w e b 和半结构化文档的信息获取、文本挖掘中文本分类和归类、决策树 算法和贝叶斯网络的应用、主题抽取和文本分类、文本数据库的知识发现、定制 化的内容过滤。 ( 2 ) w 曲结构挖掘( w 曲s t r u c t u r em i n i n g ) w e b 结构挖掘即挖掘w e b 潜在的超链接结构模式，通过分析一个网页链接 和被链接数量以及对象来建立w e b 自身的链接结构模式。这种模式可以用于网 页归类，并且由此可以获得有关不同网页间相似度及关联度的信息，帮助用户找 到相关主题的权威站点。 w e b 结构挖掘的主要内容在于超链接分析，即通过分析页面的链接关系来研 究网页的引用关系。超链接分析最早被用于搜索引擎，它的基本原理就是通过统 计分析互联网上哪些页面被链接的次数多，那么该网页就被认为是比较重要的页 面或者权威页面( a u t h o r i t yp a g e s ) 。与传统的搜索引擎使用的基于词频统计的查 询结果排序算法相比，基于超链接分析的算法的优势在于它提供了一种客观的、 不容易作弊( 一些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 算法和p a g e r a n k 算法。他们的 共同点是使用一定方法计算w 曲页面的权重。著名的c l e v e r 和g o o g l e 搜索引擎 就采用了该类算法。 ( 3 ) w e b 用法挖掘( w e bu s a g em i n i n g ) w e b 使用挖掘是指采用数据挖掘的技术，通过对w e b 服务器日志中大量的 用户访问记录深入分析，发现用户的访问模式和兴趣爱好等有趣、新颖、潜在有 用以及可理解的未知信息和知识，用于分析站点的使用情况，从而辅助管理和支 持决策。不同用户对同一网站的兴趣存在差异，但多少会有某些相同之处，这能 够从他们在服务器同志中留下的访问记录反映出来，因此通过对日志的挖掘，可 以发现用户的共同偏好和交叉兴趣。另一方面，同一用户在不同时期可能有不同 第二章w e b 挖掘概述 的访问模式，但从长期来看，也会表现出一定的规律和趋势，能够反映用户的兴 趣。统计数据表明大多数用户在网站上的活动范围是很有限的，因而他们的活动 中必然包含了许多重复的动作，也就是说，用户的行为是有规律可循的，w e b 使用挖掘能够发现这些规律。此外，由于w e b 服务器日志中记录了该服务器被 外部访问的所有过程信息，通过对这些过程信息的分析，可以客观地反映服务器 的内部结构、组成、内容、访问频度等有关该服务器的重要信息，对于评价和改 进网站的服务质量来说是非常宝贵的资源，同时，在任何一个服务器上都可以很 方便的得到它的日志文件。数据的来源很方便、文件结构较为良好、数据挖掘技 术的日趋成熟使得对不断增长的巨大数据文件的处理变得可能【26 1 。因此，w e b 使用挖掘是有效的，也是可行的。 2 3 链接分析理论基础 2 3 1 链接分析 链接分析( h y p e r l i n ka n a l y s i s ) 也称结构分析( s t r u c t u r ea n a l y s i s ) ，它是以超链 接为主要输入，对网络链接的自身属性、链接对象、链接网络等各种现象进行分 析，以便揭示其数量特征和内在规律的一种研究方法。超链分析的思想起源于引 文分析理论。科学计量学认为科学文献之间并不是孤立的，而是通过参考文献存 在着相互引证的关系，并形成交流、借鉴的轨迹和网络。引文分析是科学计量学 用来研究这种引证关系的方法，通过各种数学方法对科学期刊、论文、著作等各 种分析对象的引用或被引用现象进行分析研究，以便揭示其数量特征的内在规 律，以达到评价、预测科学发展趋势的目的。每一篇被引文献对于论文作者来说 是一篇参考文献，而对于被引用文献的作者来说，则是一篇引文，如图2 3 所示： 图2 3 文献引用 论文r 参考了论文c ，论文r 就有了一篇参考文献c ，而论文c 则有了一 篇引文r ，如果将所有具有引用关系的论文连结起来，就形成了引文网络。在该 网络中，存在着两种主要的引用关系同时引用同一篇文章“文献耦合”，或 1 2 第二章w e b 挖掘概述 是被别的文献共同引用“文献同引”，如图2 4 所示： 文献耦合关系 图2 。4 文献引用关系 文献同引关系 文献耦合和文献同引两种引文关系可以有效揭示科学文献之间的某种内在 联系，可以客观地反映科学活动过程中的许多隐藏在深层次的相关关系，其中， 文献同引关系在揭示文献之间的相关关系上比文献耦合关系更为有效。 2 3 2w e b 图表示 在超链分析中，w e b 看成是一个超文本集，且页面间的超链接是有方向的。 根据图的定义，把w e b 上错综复杂的网页作为有向图g 来处理，即g = ( ”e ) ，其 中y 是页面集合，e 是页面之问的超链接集合。页面抽象为图中的顶点，页面之 间的链接抽象为图中的有向边，具体可以定义如下： ( 1 ) 以由网页构成的节点集合，p ，目p 匈； ( 2 ) e ：由网页间的超链接构成的有向边集合：p - q e ； ( 3 ) p 一 日：p 节点有一条超链接指向q ，其中p 为口的链入网页，称为链源， g 为p 的链出网页，称为链宿； ( 4 ) 出链：p 指向其它节点的超链接； ( 5 ) 入链：其它节点指向p 的超链接； ( 6 ) f 白) ：节点p 所指向的节点集合； ( 7 ) b ( p ) ：指向p 的节点集合； ( 8 ) 节点出度：节点的出链数量； ( 9 ) 节点入度：节点的入链数量。 用矩阵表示w e b 图对研究图的性质及应用常常是比较方便的，有权矩阵、 雠柑篓、震嚣篇篆删幽汕渺 网络g ：( n e ) ，其边( v f ，v j ) 有秘w l j 1 ”一 刚称矩阵么为图g 的邻 如w e b 图2 5 的邻接矩阵是 ( v f ，v j ) e( 2 1 ) 其他 12 3 4 0 1 1 0 0 1 00 0 0 01 ( 2 2 ) 一v o w ，气、0 l 中 其 印 黼 一 妒果 州 涨 她 a ， 。陬 1 o 阵矩， 。、l斛帐弋 的膛 牙 g 构 a 络 ， 蹦西 为 a 文 腊鄙 称哥她对 阵 矩 接 ) 1 0 o ，t ，0、ii、 l 2 3 4 ， 一一一一榭燃。 一一一一一一 一一一一一一一