（计算机应用技术专业论文）基于多特征的web社区发现关键技术研究.pdf

博士学位论文 摘要 随着i n t e m e t 的广泛应用，w w w 已经成为了一个巨大的、分布 广泛的全球信息服务中心，提供了新闻、财经、广告、商务、文化、 教育等各种信息服务。如何利用w e b 快速、准确地获得信息及隐藏 在信息中的知识是人们的迫切需要。但互联网上存在的信息是海量 的，无组织的，这使得在w e b 上提取知识存在着很大的困难。 互联网上高度相关的页面聚集在一起形成的一个个具有共同主 题的页面集合是w e b 社区。根据w e b 社区从互联网中提取知识是一 种快速、有效的知识提取途径。社区发现是指在分散和无序的互联网 环境中发现潜在的和已定义的主题社区，并从互联网中抽取这些社区 的过程。本文主要围绕社区发现的三个部分：页面预处理、主题社区 发现和基于社区的信息检索模型进行了深入的研究。 在社区发现中，w e b 页面非线性结构和存在噪音的特点使得我们 容易对页面的主题产生歧义，降低社区发现的准确性。针对该问题， 本文在页面预处理部分提出了基于页面结构与内容特征相结合的页 面内容提取算法。该算法改进了v i p s 算法，根据页面块间的耦合度 与页面块内内聚度的关系定义页面块分割的目标函数。并且采用两层 过滤机制过滤噪音块对分割得到的各块进行了后处理，保留主题区域 与主题相关区域。并对主题区域与主题相关区域的块进行内容的合 并。 由于w e b 页面是一个多特征集表示的对象，使用单特征集进行 社区发现通常会导致在不同类型特征上得到不同的社区分布。因此本 文在主题社区发现中针对基于多特征的w e b 社区发现问题进行了研 究，提出了：1 ) 基于互信息的“软”聚类集成算法；2 ) 基于差异度 的互信息“软”聚类集成算法；3 ) 基于多视图聚类的w e b 社区发现 算法。 “软划分”的聚类集成是多特征w e b 社区发现的重要组成部分。 针对“软划分”的聚类集成，本文提出了一种基于互信息的“软”聚 类集成算法。该算法是将s t r e h l & g h o s h 提出的基于互信息的聚类集 成目标函数扩展到“软”划分集成中，并且提出了求解该目标函数的 新聚类集成算法。该算法不需要建立不同聚类间的对应关系。 由于聚类集成的质量不仅依赖于集成算法，同时也依赖于参加集 成的聚类成员本身的分布。通常聚类成员间较大的差异度能有效地提 博士学位论文 摘要 高集成的质量。本文主要通过差异度衡量聚类成员对集成的重要性， 对聚类成员赋予不同的权值，提出了一种基于差异度的加权互信息集 成算法。在聚类成员的差异度值分布不均匀或聚类成员的差异度均值 不大时，基于差异度的加权互信息集成算法能有效地提高对“软”划分 集成的准确性。 对于w e b 社区发现而言，在进行聚类集成前需要采用基本聚类 算法在各个特征集上获得多个聚类结果。信息瓶颈算法是一种有效的 文档聚类算法，但它是单视图( 即：单个特征集) 算法，没有考虑视 图间的关系。本文将多视图学习的思想引入信息瓶颈聚类算法中，并 且将其与w e b 页面的多视图表示，用于“软”划分集成的互信息聚 类集成算法结合在一起，提出了一种基于多视图聚类的w e b 社区发 现算法。该算法充分地利用了多视图学习中的两个重要条件：条件独 立性与兼容性，将最大化不同视图间的同意程度作为对多视图表示对 象聚类的兼容性约束。通过增加兼容性约束，在每个视图上获得能透 露更多正确假设信息的聚类结果，并且最终运用基于互信息的软聚类 集成算法对所有单视图上聚类结果进行集成，提高了w e b 社区发现 的准确性。该算法是基于多特征的w e b 社区发现的核心。 为了克服“一词多义”和“一义多词”带来的信息检索查全率和 查准率的降低，本文提出了一个基于社区的信息检索模型。该模型是 在用户与通用搜索引擎问定义了一个中间层。用户通过中间层访问一 个已发现的主题社区模型，明确所需的主题并且进一步精化检索需 求。同时该中间层根据精化的检索需求，产生一个“中间查询”指导 用户通过通用搜索引擎在互联网上搜索。 关键词：社区发现，内容提取，聚类集成，多视图学习，信息检索 a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fi n t e r n c t 。w w wh a sb e e nt h eg i a n t a n dd i s t r i b u t e di n f o r m a t i o nr e s o u r c ei nt h eg l o b a la n dp r o v i d e su s i n f o r m a t i o na b o u tn e w s ，f i n a n c e , a d v e r t i s e , b u s i n e s s ，c u l t u r ea n d e d u c a t i o ne t c h o wt oo b t a i nt h ei n f o r m a t i o ni nt h ew r e bo rd i s c o v e r k n o w l e d g eh i d d e ni nw - c bq u i c k l ya n da c c u r a t e l yi sp e o p l e su r g e n t d e m a n d c o m m u n i t yi sac o l l e c t i o no fw e bp a g e st h a ta l eh i g h l yr e l a t e d ， i n t e r c o n n e c t e d , a n ds h a r et h es a m et o p i c e x t r a c t i n gk n o w l e d g ef r o m c o m m u n i t y i saq u i c ka n de f f i c i e n tw a yt od i s c o v e rk n o w l e d g ei nt h ew 曲 c o m m u n i t yd i s c o v e r yi st od i s c o v e rt h eh i d d e nc o m m u n i t ya n dd e f i n e d c o m m u n i t yf r o mt h ed i s t r i b u t e da n dd i s o r d e r i n ge n v i r o n m e n to fi n t e m e t i nt h i s p a p e r , w ed e e p l yr e s e a r c ho ns e v e r a lk e yp r o b l e m so fw e b c o m m u n i t yd i s c o v e r y ：1 ) p r e - p r o c e s s i n go fw e bp a g e s ；2 ) t o p i c c o m m u n i t yd i s c o v e r yb a s e do nm u l 邱l et y p e so ff e a t u r e s ；3 ) t h em o d e l o fi n f o r m a t i o nr e t r i e v a lb a s e do nt o p i cc o m m u n i t y t h em a i nw o r ki nt h i s p a p e ri s ： f o r p r e - p r o c e s s i n go f w e bp a g e s ，w ep r o p o s ean e wa l g o r i t h mt o e x t r a c tt h ec o n t e n t so fw e b p a g e s i nt h i sa l g o r i t h m , w e bp a g ei s d i v i d e di n t ob l o c k sb yt h en e wo b j e c t i v ef u n c t i o nw h i c hi s e s t a b l i s h e da c c o r d i n gt ot h ed e g r e eo fc o u p l i n gb e t w e e nb l o c k s a n dt h ed e g r e eo fc o h e r e n c eo fb l o c k s t o p i c ”o r t o p i c r e l e v a n t b l o c k s c a nb e e x t r a c t e d b y t h eb l o c k s c o n t e n t sa n ds t r u c t u r ei n f o r m a t i o n m e r g i n gt h e s eb l o c k s c o n t e n t s ，t h em a i nc o n t e n to fw e bp a g ec a nb ea v a i l a b l e e x p e r i m e n to n t h ew e bp a g e so ft h r e es i t e si n d i c a t e st h e a l g o r i t h m se f f e c t i v e n e s sf o re x t r a c t i n gc o n t e n t so fa n yt y p eo f w e b p a g e s c l u s t e r i n ge n s e m b l e i st h em a i np a r to ft o p i c c o m m u n i t y d i s c o v e r i n gb a s e do nm u l t i p l et y p e so ff e a t u r e s i nt h i sp a p e r , t h e o b j e c t i v ef u n c t i o nb a s e do nm u t u a li n f o r m a t i o ni n t r o d u c e db y s t r e h l & g h o s hi se x t e n d e da n dan e we n s e m b l ea l g o r i t h mi s p r o p o s e d t o c o m b i n e s o f t ”p a r t i t i o n s e x p e r i m e n t s o nf o u r 1 1 1 r e a l w o r l dd a t as e t si n d i c a t et h a to u ra l g o r i t h mp r o v i d e ss o l u t i o n s w i t hi m p r o v e d q u a l i t y t h eq u a l i t yo fc l u s t e r i n ge n s e m b l ed o e sn o to n l yd e p e n do n c o n s e n s u sf u n c t i o n ，b u ta l s od e p e n d so nt h ed i s t r i b u t i o no f p a r t i t i o n sp a r t i c i p a t i n gi ne n s e m b l e s t h el a r g e rd i v e r s i t yt h e s e p a r t i t i o n sh a v e ，t h eh i g h e rq u a l i t yt h ee n s e m b l eh a s i nt h i sp a p e r , c o n s i d e r i n gt h ei n f l u e n c eo fd i v e r s i t y , aw e i g h t e dc l u s t e r i n g e n s e m b l e a l g o r i t h mb a s e d o i l d i v e r s i t y t oc o m b i n e “s o f t p a r t i t i o n si sp r o p o s e d w h e nt h ed i v e r s i t yd i s t r i b u t i o ni st m e v e n l y o rt h ee x p e c t a t i o no f d i v e r s i t yd i s t r i b u t i o ni sl o w e r , t h i sa l g o r i t h m c a l li m p r o v et h eq u a l i t yo f t h ee n s e m b l e f o rw e b c o m m u n i t yd i s c o v e r i n g w es h o u l du s eb a s i cc l u s t e r i n g a l g o r i t h mo i ld i f f e r e n tf e a t u r es e t so fw e bp a g et op r o d u c et h e p a r t i t i o n sb e f o r ec l u s t e r i n ge n s e m b l e h e r e ，w ea d o p ti n f o r m a t i o n b o t t l e n e c ka l g o r i t h ma n de x t e n dt h ei n f o r m a t i o nb o t t l e n e c k a l g o r i t h m t om u l t i - v i e w s e t t i n g b yc o m b i n i n gm u l t i - v i e w i n f o r m a t i o nb o t t l e n e c kw i t ht h em u l t i - v i e wr e p r e s e n t a t i o no fw e b p a g ea n dt h ee n s e m b l ea l g o r i t h mb a s e do nm u t u a li n f o r m a t i o n ， w ep r o p o s eam u l t i - v i e ww e bc o m m u n i t yd i s c o v e r ya l g o r i t h m e x p e r i m e n t si n d i c a t et h ee f f i c i e n c yo f t h en e w a l g o r i t h m t h em o d e lo fi n f o r m a t i o nr e t r i e v a lb a s e do nt o p i cc o m m u n i t yi s p r o p o s e di nt h i sp a p e r t h i sm o d e ld e f i n e st h em e d i a t e dl a y e r b e t w e e nu s e ra n dg e n e r a ls e a r c h e n g i n e u s e r s a c c e s st h e p r e d e f i n e dc o m m u n i t ym o d e lt h r o u g ht h em e d i a t e dl a y e ra n d i d e n t i f yt h en e e d e dt o p i c t h em e d i a t e dl a y e rr e f m e st h eq u e r yb y t h en e e d e dt o p i c ，g e n e r a t e sam e d i a t eq u e r yt h a th e l p su ss e a r c h i n f o r m a t i o ni nw e bt h r o u g hg e n e r a ls e a r c he n g i n e k e yw o r d s ：c o m m u n i t yd i s c o v e r y , c o n t e n te x t r a c t i o n ，c l u s t e r i n g e n s e m b l e ，m u l t i v i e wl e a r n i n g ，i n f o r m a t i o nr e t r i e v a l 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究工作 及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得中南 大学或其他单位的学位或证书而使用过的材料。与我共同工作的同志对本 研究所作的贡献均已在论文中作了明确的说明。 作者签名： 关于学位论文使用授权说明 本人了解中南大学有关保留、使用学位论文的规定，即：学校有权 保留学位论文，允许学位论文被查阅和借阅；学校可以公布学位论文的全 部或部分内容，可以采用复印、缩印或其它手段保存学位论文；学校可根 据国家或湖南省有关部门规定送交学位论文。 作者签名：叠盗导师签名量! 圣日期：竺翌年二月覃日 中南大学博士学位论文 第一章绪论 1 1 研究背景 第一章绪论 自从2 0 世纪9 0 年代之后，随着网络技术的发展，尤其是i n t e m e t 的广泛应 用，w w w 已经成为了一个巨大的、分布广泛的全球信息服务中心，提供了新闻、 财经、广告、商务、文化、教育等各种信息服务。因此，如何利用w e b 快速、 准确地获得信息及隐藏在信息中的知识是人们的迫切需要。 与传统的数据源比较，w e b 本身具有很多不同特性： w e b 存在许多无组织的、海量的信息，而只有很小的一部分对用户来说 是相关的或有用的据说9 9 的w e b 信息对于9 9 的用户是无用的。 通常，用户会淹没在很多无用的信息中。 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 是无序和分散的，但是他们仍然存在着一些规律。从宏观上看i l 】 ( 见图1 - l a ) ，w e b 是一个“b o w - t i e ”形状，由一个巨大的“强链接部件”与一个 连接到“强链接部件”的“i n ”部件，一个被“强链接部件”连接的“o u t ”部 件，和其他页面组成的“t e n d r i l ”部件。根据出链接确定的平均最短路径长度为 1 6 1 2 ，根据入链接确定的平均最短路径长度为：1 6 1 8 ，无向的最短路径长度为 6 8 3 。每个页面拥有入出链接数的概率符合幂率分布。 从微观上看【2 j ，w e b 由根据“主题”聚集在一起的多个社区组成( 图1 - l b ) 。 中南大学博士学位论文 第一章绪论 w e b 社区可以松散地被定义为基于某个特定主题的，相互连接的w e b 页面集。 每个社区的核心是一个二分图【4 1 ( 图1 - i t ) 。同时，在同一社区中的页面内容上 具有一定的相似性。 ( a ) 宏现的结构图 ( b ) 中闻层结构( c ) 微观结构 图1 - 1w e b 的结构图 利用w e b 上提供的信息( 包括内容信息与结构信息) ，我们可以在极度分散 和无序的互联网环境中，发现潜在的未被发现和定义的互联网社区，并且从互联 网中系统地抽取这些社区。这种过程我们称为社区发现。 社区的发现对从互联网中提取知识有着重要的意义： 门户网站通过识别和区分这些社区，可以更有效地组织它们的目录层次 ( 因为很多潜在的社区以很快的速度在增长，而很多已经清晰出现的社区 又在逐渐消失) 。这同时意味着互联网的自动分类成为可能。 搜索引擎可以根据社区知识收集大量的、高质量的，某一主题的网页。 同时在使用搜索引擎查询的过程中，可以利用w e b 社区缩小查询范围， 快速定位到用户所需的知识，以便为互联网用户提供了有价值的，甚至是 最及时、最可靠的信息。 这些社区展现了互联网社会学( s o c i o l o g yo f w e b ) ，研究和发现这些社区 可以深入了解互联网的进化过程。 本文，我们主要针对w e b 社区发现的若干关键问题进行了深入的研究，并 且利用已发现的社区提高信息检索的查全率与查准率。 1 2 研究现状 当前w e b 社区发现主要是基于w e b 挖掘技术。w e b 挖掘是利用数据挖掘技 中南大学博士学位论文 第一章绪论 术在w e b 文档和服务器中自动发现和提取有用信息。w e b 挖掘可以对文档的内 容、可利用资源的使用以及资源之间的关系进行分析。而w e b 挖掘的研究对象 是半结构化和无结构文档为中心的w e b 页面，这些数据没有统一的模式，数据 的内容和表示互相交织，数据内容基本上没有语义信息进行描述，仅仅依靠 h t m l 语法对数据进行结构上的描述。为了对这种半结构化数据进行分析和处 理，w e b 挖掘必须和其研究手段结合起来。由于涉及到很多的知识领域，w e b 挖掘现在是多个研究方向的交汇点，包括数据库、信息获取、人工智能、机器学 习、模式识别、统计学、自然语言处理等 如图1 2 描述，w e b 挖掘主要通过3 种不同的数据挖掘任务来获取有用的知 识： 内容挖掘网： 是从i n t e r n e t 上的内容数据文档中发现有用信息。 结构挖掘【琊9 1 ：挖掘w e b 潜在的链接结构模式。这种思想源于引文分 析，即通过分析一个网页链接和被链接数量以及对象来建立w e b 自身的 链接结构模式。w e b 结构挖掘是对w e b 页面超链关系、链接描述文字、 文档内部结构、文档u r l 中的目录路径结构的挖掘。 日志挖掘【1 0 1 1 1 1 1 2 1 ：通过对w e b 上用户的使用日志记录的挖掘获取知识， 了解用户的网络行为所具有的意义。 图1 - 2w e b 挖掘 当前基于w e b 挖掘的w e b 社区发现的两种主要技术是：基于结构挖掘的社 区发现方法和基于内容挖掘的社区发现方法。 1 2 1 基于结构挖掘的社区发现方法 基于w e b 结构挖掘的社区发现方法主要思想是在由页面和链接组成的w e b 中南大学博士学位论文 第一章绪论 图上分析页面间的关系，确定w e b 社区。最著名四个社区发现算法是：基于完 全二分图核的社区发现算法1 4 ，p a g e r a n k m ，h i t s 堋，基于最大流的社区发现 算法f 嘲。 基于完全二分图核的算法 k u m a r 等人从二分有向图的角度对互联网上的社区给出了一种明确的定义 描述。首先考虑如下的图结构磁，图中的节点分为f 和c 两个集合，集合f 中 有i 个节点，集合c 中有j 个节点，并且每个集合f 中的节点和所有在集合c 中 的节点都存在一条有向边。这种图结构酶被称为完全二分有向图硒。根据随机 二分图的理论，一个足够大而稠密的随机二分图将以很高的概率包含一个完全二 分有向图。如果将某个社区的链接结构看作一个大而稠密的二分有向图，那么社 区的核就可以用一个完全二分有向图磁来表示具体到互联网环境中，可以对上 述概念有如下直观的理解：如果在互联网上存在一个某种主题的社区，那么这种 二分核必将包含在其中。为了适应互联网庞大的规模，k u m a r 等人为枚举社区的 核开发了专门的算法澉称为消去产生法( e l i m i n a t i o n - g e n e r a t i o n ) p a g e r a n k 算法 它是由s b r i n 和l p a g e 提出的，是基于重要度传递关系构造的随机游动模 型。它的描述如下：某一w e b 文档的p a g e r a n k 值等于所有包含指向该文档的源 文档的p a g e r a n k 值与源文档链接总数之比的和，即： p r ( v ) = s n + ( 1 一) 艺p r ( u ) o u t l i n k ( u ) ( u ，v ) e g 其中是衰减因子，一般取0 1 一o 2 ；n 为有向图g 中节点的数量；o u t l i n k ( u ) 为节点u 包含的超链接数量。 每个页面的p a g e r a n k 值实际上代表了w e b 页面被用户随机点击的概率，这 种随机过程属于m a r k o v 过程，从一个页面到另一个页面的跳转形成了m a r k o v 链。 p a g e r a n k 算法本身是一个著名的页面排名算法，且与主题无关。但t a h e r h h a v e l i w a l a | 训将其改造为与主题相关的算法，且可以发现与主题相关的社区： p r ( v ) = ( n ) p o ( v ，1 ) + ( 1 一) 芝p r ( u ) o u t l i n k ( u ) ( u ，v ) a g 其中p o ( v , t ) 表示v 与主题t 的相关度。通过p r ( v ) 大于阀值确定v 是否为主 题t 的社区成员。 h i t s 算法 根据k l e i n b e r g ，w e b 页面可分为两种类型：中心页面( h u b ) 和权威页面 ( a u t h o r i t y ) 。权威页面是指人们公认的在某一主题上内容权威的页面。中心页 4 中南大学博士学位论文第一章绪论 面是指页面上有很多指向权威页面链接的页面。中心页面与权威页面因此形成一 个相互加强关系：好的中心页面指向许多好的权威页面，而好的权威页面被许多 好的中心页面所指。这种关系将w e b 页面描述成一个稠密的二分图。 若将a 表示为c 中链接关系的矩阵，即：a i j = l ，如果c 中有从页面i 指向 页面j 的链接，那么h i t s 算法将每个页面的a u t h o r i t y 值收敛于a r a 的主特征向 量，h u b 值收敛于a a t 的主特征向量。a r a 表示了页面问的共引用关系，( a t a ) 自表示有多少页面即指向页面i 又指向页面j 从1 表示了页面间的共耦合关系， ( a a t ) 表示有多少页面同时页面i 和页面j 指向 根据h i t s 算法中a r a ( 或a o ) 的每个非主特征向量的向量元素值能确定 w e b 社区中的重要页面【2 n 。 基于最大流的社区发现方法 假设有向图g v ：e ， 是从节点u 到v 的有向边。假定s ，t 是v 中固 定的点，并且每一条边( 1 w ) 都有一个已被分配的容量“l l ，v ) 才，从s 到t 的流 量是一个非负的整数函数：蜓f 【l l ，n 沁v ) ，并且对于所有的v 有： k ，坶f ( u t ，v ) = 【冲“v ，u 。) 即从s 中流出的流量等于流入t 的流量。最大流算法是指发现图的最大流量 的算法。图中的最大流的流量等于图中最小截集的截型埘 在w e b 社区内，页面间的链接比与社区外的页面链接要多。f l a k d 2 4 h 正明了 经过最大流算法后提取的w e b 页面恰好满足w e b 社区的这一性质，并设计 了基于最大流的w e b 社区发现算法。 2 2 基于内容挖掘的社区发现方法 w e b 内容挖掘是从w e b 文档的内容或其描述中提取知识的过程。w e b 挖掘 可以对w 曲上大量的文档集合内容进行总结、分类、聚类、w e b 数据建模，可 以协助用户搜索信息或者根据用户的配置文件为用户过滤无用的信息。w e b 页面 是信息的载体，主要包括文本和多媒体数据，基于w e b 文档的文本挖掘( t e x t m i n i n g ) 是w e b 内容挖掘的主要研究内容。 w e b 文本分类是按预先定义的主题类别，为w e b 文档集合中的每个页面确 定一个或几个主题类别，这样不但可以方便浏览，而且可以通过限制搜索范围使 搜索更加准确、高效。目前有的网站是通过人工对w e b 上的文档进行分类，这 大大影响了索引的页面数，同时也耗费大量的人力资源。利用分类技术可以对大 量文档集进行快速、有效的自动分类。经典的算法有s v m 2 5 1 、n a v eb a y e s 2 6 】、 中南大学博士学位论文 第一章绪论 k n n 算法等【2 6 】。 w e b 文本聚类与w e b 文本分类的不同，它是没有指导的学习，不依赖于预 先定义的主题类别和学习实例，w e b 文本分类要预先定义好主题类别，而聚类没 有预先定义好主题类别。聚类要求相似度大的文档放在同一簇内，相似度小的文 档放在不同簇中。经典的算法有：k m e s a l s ，e m ， 层次凝聚算法等1 2 6 1 。 根据社区内的页面是基于同一主题的特性，通常通过w e b 文档聚类与w e b 文档分类而抽取的同一主题的页面集合可以成为一个社区 1 3 论文工作 尽管，上述方法都能较好地发现w e b 上的主题社区了，但是仍然存在着一 些问题： w e b 页面上有多个功能区域，有“噪音”区域( 如：广告，版权，装饰， 导航区域等) ，也有主题内容区域，以及与主题内容相关的区域。噪音 的出现往往会降低基于页面处理的各种算法效率，这也包括各种社区发 现算法。因此，如何删除页面的噪音，从非线性结构中提取页面中的主 要内容是我们研究的关键问题l 。 w e b 社区是根据主题紧密联系在一起的w 曲页面集合。w 曲页面有很 多类型的特征，包括内容，链接文字，谢等。这些类型的特征都表示 了与“主题”的相关性。当前的社区发现算法大多是单纯地依赖于w e b 页面的某一类特征，但每类特征都包含了很多“噪音”，如：页面内容 中的“垃圾”关键字和页面间“垃圾”链接。这些噪音降低了各种不同 类型特征上的社区发现算法准确性，使得根据不同特征类型发现的社区 是不同的。因此，如何有效地利用这些不同类型的特征，提高社区发现 算法的准确性，生成正确的主题社区是我们研究的关键问题2 。 由于当前的搜索引擎大多是基于关键字查询的。通常用户的查询关键字 是简短的，且不能完全准确描述用户的查询需求，这就导致了检索性能 的降低，用户找不到自己所要的信息。因此，如何利用已发现的主题社 区来提高信息检索的查全率与查准率是我们研究的关键问题3 。 本文针对w e b 社区发现的上述关键性问题进行了研究，提出了一个基于多 特征的w e b 社区发现框架。该框架首先是提取页面特征，然后考虑多个特征集 间的关系，采用多视图聚类算法得到各个视图上的聚类结果，最后采用聚类集成 算法对聚类结果进行合并得到最终的社区分布。对已发现的社区建立社区主题标 识，生成主题社区模型。同时利用己发现的主题社区模型，建立一个基于主题社 6 中南大学博士学位论文 第一章绪论 区的信息检索模型。 l h t m i 页面 i 链接描述文页面内容其他类型 字抽取 提取 特征提取 、 分词处理分词处理 ll 特征提取 jl li 上上， i 学习嚣，ii 学习8 2 i = ：= l 学习謇tl l t ll t0和和、j j ，多视圈聚类 一l 幂哭粟麟 一l 女 f 一 i f 主最社区标引 l 特征融台的主题社区发现 i 主晨社区检素模型 图1 - 3 基于多特征的w e b 社区发现框架 图1 3 描述了论文的主要工作：基于多特征的w e b 社区发现框架。针对该 框架，本文主要做了下列5 点工作： 针对w e b 页面非线性结构和存在噪音的特点，提出了基于页面结构与页 面内容特征相结合的页面内容提取算法。该算法改进了v i p s 算法，根 据页面块间的耦合度与页面块内内聚度的关系定义分割的条件，并且该 算法采用两层过滤机制过滤噪音块对分割得到的各块进行了后处理。第 中南大学博士学位论文第一章绪论 一层是根据块的结构信息，第二层块则是根据块的内容信息，对块进行 过滤，保留主题区域与主题相关区域，并对主题区域与主题相关区域的 块进行内容的合并。 聚类集成是基于多特征的w e b 社区发现过程的重要组成部分。本文针对 聚类集成提出了一种基于互信息的“软”聚类集成算法。该算法是将 s t r e h l & g h o s h 提出的基于互信息的聚类集成目标函数进行了扩展使其 能对“软”划分集成，同时用类似于序列k - m e a n s 的算法求解该目标函 数。该算法不仅能对“软”聚类划分进行集成，并且该算法还不需要建立 不同聚类划分间的对应关系。 聚类集成的质量不仅依赖于集成算法本身，同时也依赖于参加集成的聚 类成员本身的分布。通常聚类成员间较大的差异度能有效地提高集成的 质量。本文主要通过差异度衡量聚类成员对集成的重要性，对聚类成员 赋予不同的权值，提出了一种基于差异度的加权互信息集成算法。在聚 类成员的差异度值分布不均匀或所有聚类成员差异度均值不大时，基于 差异度的加权互信息集成算法能有效地提高对“软”划分集成的准确性。 对于w e b 社区发现而言，在进行聚类集成前我们需要采用基本聚类算法 在各个特征集上获得多个聚类结果。信息瓶颈算法是一种有效的文档聚 类算法，但它是单视图( 即：单个特征集) 算法，没有考虑视图间的关 系。本文将多视图学习的思想引入信息瓶颈聚类算法，并且将其与w e b 页面的多视图表示，基于互信息的“软”聚类集成算法结合在一起，提 出了一种基于多视图聚类的w e b 社区发现算法。该算法充分地利用了多 视图学习中的两个重要条件：条件独立性与兼容性，将最大化不同视图 问的同意程度作为对多视图表示对象聚类的兼容性约束。通过增加兼容 性约束，在每个视图上获得能透露更多正确划分信息的聚类结果。并且 最终运用基于互信息的软聚类集成算法对所有单视图上聚类结果进行 集成，提高了w 曲社区发现的准确性。 提出了一个基于社区的信息检索模型。该模型是在用户与通用搜索引擎 间定义了一个中间层。用户通过中间层访问一个预先定义好的主题社区 模型，明确所需的主题并且进一步精化检索需求。同时该中间层根据精 化的检索需求，产生一个“中间查询”指导用户通过通用搜索引擎在互联 网上搜索。基于预先定义好的主题社区模型，使得该模型能克服了传统 的基于关键字检索模型中因“一词多义”和“一义多词”降低检索的查全 率与查准率的缺陷。同时将扩展的查询关键字提交给通用搜索引擎，使 得该模型能充分利用通用搜索引擎的索引页面数量多的特点，克服了传 中南大学博士学位论文 第一章绪论 统的基于社区的检索模型是受索引页面数量的影响，查全率较低的缺 陷。 1 4 论文的主要结构 第一章。绪论”，介绍论文的研究背景、研究目的、研究现状、工作以及论 文结构。 第二章。基于结构与内容特征结合的页面内容提取算法”，在这一章中提出 了一个基于结构与内容特征结合的页面内容提取算法，该算法能够有效地剔除页 面噪音，提取页面的主要内容 第三章“基于互信息的软聚类集成”，在这一章中对聚类集成问题与算法进 行了详细的分析，提出了一种基于互信息的。软”聚类集成算法。同时考虑差异 度的影响，提出加权的互信息。软”聚类集成算法。 第四章“基于多视图聚类的w e b 社区发现”，在这一章中多视图学习的思想 引入信息瓶颈聚类算法，并且将其与w e b 页面的多视图表示，与第三章提出的 基于互信息。软”聚类集成算法结合在一起，提出了一种基于多视图的w e b 社 区发现算法。 第五章“基于主题社区的信息检索模型”，在这一章中提出了一个基于主题 社区的信息检索模型。根据用户输入的关键字，该模型可以返回用户感兴趣的主 题内容。 第六章“结束语”，在这一章中对本论文工作进行了总结，同时指出了尚需 进一步研究的问题。 9 中南大学博士学位论文第二章基于结构与内容特征结合的页面内容提取算法 第二章基于结构与内容特征结合的页面内容提取算法 2 1 前言 随着因特网的不断普及和发展网络上存储的数据与信息以前所未有的速 度剧烈膨胀w w w ( w o r l dw i d ew e b ) 可以看作为一个巨大的信息库，其中包含 了大量不同类别的信息，但是它没有合适的索引目录，也没有标准的组织结构。 用户在进行w e b 信息检索的过程中。很难找到自己所需要的信息。根据“主 题”，在因特网上将w c b 页面组织成一个个基于“主题”的社区是解决这一问题 的一种方法。它可以帮助用户恰当地，快速地定位在所需要的信息中。 社区是一组主题相关的页面集合。社区的确定是基于页面间主题的相关性。 如何确定两个页面间主题的相关性? 传统的文档通常是根据文档的内容信息。同 样w 曲页面也可以根据内容信息，但与传统的文档也有很多不同之处。 首先，由于h t m l 本身不具备自描述的特性，页面在书写时负责显示和承 担主题描述的信息混在一起，并且设计者可随意把各类内容加入到页面中因此 网页中充满与主题无关的噪音是个常见的现象通常网页的噪音可以从整个w e b 和单一页面本身来加以定义在对w e b 上得到的一组页面集进行挖掘时，若一 个网页所存留的副本，如镜像网站，复制的页面，及旧版本的页面也在此页面集 中，这些副本是全局噪音。一个页面内，与页面主题无关的区域是局部噪音，这 些噪音包括广告栏，导航条，修饰作用的图片等。噪音的出现往往会导致页面主 题表达的不准确性，使得人们对页面主题产生歧义。 其次，传统的文档遵循语意相近原则，即在一个文档中，相近的文字是在语 义上相互关联的。但在w 曲页面上不是。它是非线性的，嵌入到d o m 树中。 由于页面的内容嵌入到d o m 树，使得页面内容不是线性的。相近的文字与链接 不一定相关。 为了更精确地描述页面间的相关性，我们需要消除“噪音”区域和“导航” 区域，提取“主题内容”区域和相关主题区域。同时将在d o m 树中不相近但相 关的内容合并在一起。 在本章中，我们主要是针对单一页面删除局部噪音。因此今后文中所指噪音 为局部噪音。当前，对页面内的噪音进行删除的方法主要有两种。一种是基于一 1 0 主亘盔堂蔓堂笪迨塞箜三童薹王绫塑芝凼查壁笙缱坌笪亟亘凼查堡塑蔓鎏 个或多个网站中的页面集进行页面的模板检测，把为生成页面而在网站中使用的 模板作为噪音从页面中去除。另一种是基于单一页面的处理，根据所处理页面的 d o m 结构，可视信息等应用一些启发性规则去除页面内的噪音。基于模板检测 的算法有：s h i a n - h u al i n 等【5 2 】提出了以页面中t a b l e 标记作为处理元素，提取信 息块的方法；l i u 等 5 卅根据页面的d o m 结构，构造s t y l et r e e ，进行同一网 站内页面模板的检测，以排除各页面内的噪音。这种方法很容易对从任意网站下 载的页面无效。为了能对任意页面进行噪音删除，通常采用第二种方法删除页面 的噪音。第二种方法的主要算法有：基于d o m 树的页面提取算法【辄明是将页 面解析为d o m 树，根据“t a b l e ”等表示块的标签进行分块，并且采用启发式规 则删除噪音块，但d o m 树表示的是布局信息，不能很好地提取语义块。同时根 据块内链接分布情况定义的启发式规则使得文献 5 5 】的算法不仅不适合分析h u b 页面，而且还会删除非h u b 页面中与主题相关的链接列表。基于布局信息的分 块算法【蚓是将页面分成5 个区域：上、下、左、右、中，提出处于中间的区域 是页面的主要内容。这种划分不适应于所有的页面，并且这种分块粒度太粗。 v i p s 算法 5 7 1 ( 全称：av i s i o nb a s e dp a g es e g m e n t a t i o n ) 是充分地使用了w e b 页面的视觉提示，并结合d o m 树进行页面语义分块，弥补了仅使用d o m 树所 带来的一些缺憾。该算法以预定义的p d o c 值( p e r m i t t e dd e g r e eo f c o h e r e n c e ) 作为迭代的终止条件，当各块的内聚度值大于p d o c 值时迭代终止。预定义的终 止条件影响了分块的效果，并且该算法并未对噪音数据进行进一步的处理。 针对上述算法缺陷，本章提出了一个基于结构与内容特征结合的页面内容提 取算法。该算法改进了v i p s 算法，根据页面块间的耦合度与页面块内的内聚度 的关系定义分割的目标函数，并且根据新的分割目标函数对页面进行分块。同时 该算法对分割得到的各块进行了后处理，采用两层过滤机制。根据内容与结构信 息对块进行重要性估计