（计算机软件与理论专业论文）基于知识粒度的web文档聚类研究.pdf

基于知识粒度的网贞聚类研究 摘要 飞速发展的互联n ( w w w ) 极大地改变了人们的生活，它已经成为人们交流思想和获取 信息的主流性的渠道。在这浩瀚无边的网络数据的海洋中潜藏着大量有价值的知识，从这个 海量数据源中快速高效地获取有用知识是包括企业、个人等在内的所有用户必须要面临并解 决的问题。 丁是，运用数据挖掘( d a t am i n i n g ) 技术进行w e b 数据挖掘( w e bd a t am i n i n g ) 成为数据分 析领域中的一个重要研究热点，引起了专家学者们的广泛关注。经过近十年的成长，w e b 数据挖捌取得了丰硕的成果，许多相关技术已经趋于成熟稳定并在实际生产和生活中得到了 很盘，的应用，例如搜索引擎给信息猎取的人们带来极人的便利，电子商务已为 ：业企业界提 供了一种全新的经营方式。 与传统数据相比较，网络数据具有结构复杂、形式多样与内容厂泛等特点，而且用户对 w e b 数据挖掘的功能需求是五花八fj 的，这对数据分析领域提出了更大的挑战。w e b 数据 挖掘可以粗略地分为三个部分：内容挖掘、使用挖掘和结构挖掘。它”j 采用的主要技术有： 关联分析、时序分析、聚类分析等。其中，w e b 数据聚类分析是w e b 数据挖掘的一个核心的 基础研究课题。聚类分析具有压缩搜索空间、加快检索速度等多方面的作用。它能帮助知识 f 作者高效而准确的发现与某个文档最相似的文档；提高信息检索系统的返同率( r e c a l l ) n i 精度( p r e c i s i o n ) ：很好地提高搜索引擎的个性化程度。在网络上最常见的也是最重要的一种 数据形式就是以标记语言表示的w e b 文档。因此，对w e b 文档进行聚类分析是一项1 f 常重 要并且很有价值的工作。 本文在深入理解现有的w e b 数据挖掘技术，尤其是w e b 文档聚类分析技术的基础之上， 分析了传统文本表示模型与文本聚类算法，分析了现有表示模型与现有聚类算法的优点与缺 陷。为了克服现有聚类算法的不足，本文将引入知识粒度理论，提出了基于知识粒度的w e b 文档聚类方法。本论文的研究工作主要包括以下几个方面： ( 1 ) 传统的w e b 聚类方法主要基于“文档特征词”二级知识粒度的，这样会导致“假 相关”的聚类结果，因此，本文提出了基丁多级粒度的w e b 文档表示机制及理论，并给出 一个具体的基丁多级粒度的w e b 文档表示模型：“文档一段落特征词”三级粒度表示模型 ( 简称为“d p t ”表示模型1 ； ( 2 ) 在这种表示模型中，我们注意到，基于v s m 的相似度量计算一般采用“特征词一 特征词”、“文档一文档”等方法，这会导致大量“零相似”的产生，基于这些问题，我们引 入容差粗集理论，提出了基于粗集的文本表示扩展模型：e v s m ： ( 3 ) 在聚类算法的选择过程中，既考虑到传统k - 1 t l e a n s 聚类方法适合海量文档集的处 理，又考虑到它对孤立点数据比较敏感( 这对非球形数据的聚类放果不够理想) ，冈此，我们 在传统k m e a n s 的基础上提出了一种改进的k m e a n s 聚类算法：n k - m e a n s 。 ( 4 ) 最后- 我们提出并实现了一个用丁w e b 数据分析的平台w e b a n a l y s e r , 弗进一步在 此平台实现了用于w e b 文档聚类分析的w c b g k 算法。 i i i 甚于知识粒度的嘲页聚类研究 实验表明，本论文提出的w c b g k 算法比传统的聚类算法具有更高的分类精度和更好 的可解释性。 关键词：数据挖掘；w e b 挖掘；w e b 文档聚类；粗糙集：知识粒度 基于知识粒度的网页聚类研究 a b s t r a c t w i t hr a p i d l ya d v a n c e d ，i n t e r n e t ( o rw w m h a se n o r m o u s l yc h a n g e dp e o p l e sl i f e m o d e n o w a d a y s w w wh a sb e c o m eam a i ni n f c ) r m a t i o nc h a n n e lt h a tm a k e sf o r b e t t e rc o m m u n i c a t i o nm a di n f o r m a t i o na c q u i s i t i o n t h e r ei sam u l t i t u d eo fv a l u a b l e k n o w l e d g ec h a r a c t e r i z e da sl a t e n c yi nt h el a r g e ，d i s t r i b u t e dd a t ar e p o s i t o r yo nt h e i n t e r n e t a nu s e r s i n d i v i d u a l so re n t e r p r i s e s m u s tc o n f r o n tt h ec h a l l e n g i n gi s s u e ： h o wt oe f f i c i e n t l ya n de f f e c t i v e l ya c q u i r ep o t e n t i a l l yu s e f u lk n o w l e d g ef r o mi n t e m e t w e bd a t am i n i n gd e r i v e df r o mt h ed a t am i n i n gh a sb e e nah o ta n di m p o r t a n t t o p i ci nd a t aa n a l y s i st h a th a sa t t r a c t e dg r e a tm a n ye x p e r t sa n dr e s e a r c h e r s i n1 a s t t e ny e a r s w e bd a t am i n i n gh a sb e e nw i d e l ys t u d i e da n da c h i e v e dag r e a tp r o g r e s s m a n y 、 ，e bm i n i n gt e c h n o l o g i e sh a v ea d v a n c e dt oam a t u r es t a g e a n dh a v eb e e n s u c c e s s f u l l ya p p l i e dt or e a lw o r l da p p l i c a t i o n s f o re x a m p l e ，s e a r c he n g i n e sm a k e g o o dt h ei n f o r m a t i o na c q u i r i n gf r o mi n t e r a c t ；e - b u s i n e s sp r o v i d e san o v e lb u s i n e s s m o d ef o rb e n e f i t i n ge n t e r p r i s e s u n l i k et r a d i t i o n a ld a t a w e bd a t ai sc h a r a c t e r i z e da sc o m p l i c a t e ds t r u c t u r e ， v a r i o u sf o r m sa n dr i c hc o n t e n t s ，a n du s e r s r e q u i r e m e n t sc a nb ed i v e r s e t h i sl e a d st o w e bd a t am i n i n gm u c hm o r ec h a l l e n g i n g t h em o s tc o m m o ny e ti m p o r t a n td a t ai so f t h ef o r m ：w e bp a g e sr e p r e s e n t e db ym a r k u pl a n g u a g e e x i s t i n gw e bd a t am i n i n gc a n b er o u g h l yc l a s s i f i e di n t ot h r e ec a t e g o r i e s ：c o n t e n tm i n i n g ，u s a g em i n i n ga n ds t r u c t u r e m i m n g d o m i n a t i n gt e c h n o l o g i e su s e di nw e bd a t am i n i n ga r ea s s o c i a t i o na n a l y s i s ， t i m es e q u e n c ea n a l y s i s ，a n dc l u s t e r i n ga n a l y s i s w e bd a t ac l u s t e r i n gi sak e yt a s ki n w e bd a t am i n i n g c l u s t e r i n ga n a l y s i sa s s i s t si nr e d u c i n gs e a r c hs p a c ea n dd e c r e a s i n g i n f o r m a t i o nr e t r i e v i n gt i m e i ti sh e l p f u lf o re f f i c i e n t l yd i s c o v e r i n gd o c u m e n t sl i k e l y s i m i l a rt oa n o t h e ro n e i ti sa l s ou s e f u lt oi m p r o v et h er e c a l la n dp r e c i s i o no fi r s y s t e m sa n dp e r s o n a l i z es e a r c he n g i n e se f f e c t i v e l y t h e r e b y , w e bc l u s t e r i n gi sak e y t a s ki nw e bm i n i n g i nt h i st h e s i s ，b a s e do nd e e p e ru n d e r s t a n d i n go ft h ee x i s t i n gd a t am i n i n ga n dw e b d o c u m e n tc l u s t e r i n gm e t h o d s ，w ef i r s ta n a l y z et h et r a d i t i o n a lt e x tr e p r e s e n t a t i o n m o d e l s ，t e x tc l u s t e r i n ga l g o r i t h m s ，a n dt h e i r l i m i t a t i o n s a n dt h e nw ea d o p t k n o w l e d g eg r a n u l a r i t yt ob u i l dw e bd o c u m e n t sc l u s t e r i n gt h e o r ya n da l g o r i t h m t h e m a i nc o n t r i b u t i o n sa r ea sf o l l o w s ( 1 ) t r a d i t i o n a lw e bc l u s t e r i n ga l g o r i t h m sa r eb a s e do nt w o l e v e lk n o w l e d g e g r a n u l a r i t y , i e d o c u m e n ta n dt e r m i tc a nl e a dt ot h a tc l u s t e r i n gr e s u l t sa r e “f a l s e r e l e v a n t ”t h i st h e s i sp r o p o s e san e wm e t h o df o rw e bd o c u m e n tr e p r e s e n t a t i o nt h a ti s o f m a n y l e v e lk n o w l e d g eg r a n u l a r i t y , r e f e r r e dt oac o n c r e t em o d e l ： “d o c u m e n t p a r a g r a p h t e r m ”( a b b r e v i a t e da s “d p t 、m o d e l ( 2 ) a sw e l lk n o w n ，t r a d i t i o n a lv s ms i m i l a r i t ym e a s u r e sc a nr e s u l t i nl o t so f z e r os i m i l a r i t y t os o l v et h i sp r o b l e m ，w eu s et o l e r a n c er o u g hs e tt h e o r yt od e s i g n v 基于知识粒度的嘲页聚类研究 a ne x t e n d e dv s m ( a b b r e v i a t e da se v s m ) s i m i l a r i t y ( 3 ) w eu s ek m e a n sa so u rc l u s t e r i n ga l g o r i t h m h o w e v e r , a l t h o u g hk m e a n s c l u s t e r i n gi sg o o df o rd e a l i n gw i t hh u g ed o c u m e n t s ，i ti so u t l i e r - s e n s i t i v e ( t h i sc a l l g e n e r a t e ap o o ro u t p u tw h e nc l u s t e r i n gn o n s p h e r i c a ld a t a ) f o rt h i s ，w ei n n o v a t e u p o nt h ek m e a n sc l u s t e r i n g n a m e da sn k - m e a n sa l g o r i t h m ( 4 ) f i n a l l y , w ed e v e l o pap l a t f o r mf o rw e bd a t aa n a l y s i s ，n a m e dw e b a n a l y s e r t h ec o r ep a r ti saw e b c l u s t e r i n ga l g o r i t h mw c b g k i th a sb e e n e x p e r i m e n t a l l ye v a l u a t e d ，a n dd e m o n s t r a t e s t h a to u r a p p r o a c h w c b k gc o m p a r e dw i t ht r a d i t i o n a lw e bd o c u m e n tc l u s t e r i n ga l g o r i t h m s ，h a sb o t h h i 曲e rc l a s s i f i c a t i o na c c u r a c ya n db e t t e ru n d e r s t a n d a b i t i t y k e y w o r d s ：d a t am i n i n g ；w e bm i n i n g ；w e bd o c u m e n tc l u s t e r i n g ；r o u g hs e t ； k n o w l e d g eg r a n u l a r i t y 基于知识粒度的刚贞聚类研究 第1 章前言 1 - 1w e b 挖掘概述 随着互联网的普及，网上信息正在呈指数级增长，1 9 9 9 年全球网页总数揖不n 3 0 亿，2 0 0 0 年达到r 近5 0 亿，预计j ! d 2 0 0 3 年，这一数字将达到惊人的1 5 0 亿以上，返就意味着全球平均 每人拥有两个以上的w e b 页面 1 如今互联网已经成为人们获得信息、取得服务的重要渠道 之一。如何从动态变化的茫茫数据世界中检索到期望的目标显得极为必要，但由于网络信息 多数是通过半结构化或无结构化的形式来组织起米的，这使得仅仅依靠数据库的查询检索机 s u s n 统计学方法已经不能满足现实需要了，它迫切要求自动智能地将海量数据转化为有用的 信息和知识，从而达到各种与信息知识相关服务的目的。w e b 数据挖掘正是为了满足这种需 要而迅速发展起来的一种新的数据处理技术。 1 1 1w e b 挖掘的定义 互联网拥有巨大信息资源，许多在线信息服务已在互联网上迅速发展起来。互联网业已 成为一个巨大的、分布式、全球信息服务中心，它提供新矧、广告、商业信息发布、教育、 电子商务等服务。且联网不仅拥有巨大的文档资料，还拥有动态的网页链接信息与网页读取 和使用信息等。这就为数据挖掘提供了一个巨大的信息数据源。但是互联网也为有效进行其 中的知识发现提出了以下的问题 2 3 儿4 儿5 6 7 ： 1 ) 互联网的规模之人使得无法有效地构造数据仓库与进行数据挖掘。互联网的规模是 以数百万米计算弗且还在迅猛地增加。许多组织和团体都将它们的人多数公兆信息放到了互 联网上。不太可能创建一个数据仓库来复制、保存或集成互联网上所有的数据。 2 )网页的复杂性要远远大丁任何传统的文本文档。网页缺乏统一的结构。与图书和其 它基于文本的传统文档比较，网页具有更多的编写风格和内容描述方法。若将互联网看成是 一个巨大的数字图书馆，那么这个图书馆中的文档就并没有按照某种顺序进行组织。它没有 目录索引、没有标题、作者、目录等，在这样图书馆寻找信息，对用户米说就是一个挑战。 3 ) 互联网是一个高度动态的信息源。不仅互联网在迅速发展，而且其中的信息也在迅 速增加。新闻、股票市场、公司广告等都在不断地定期更新它们的网页内容。信息的链接和 谈取记录也在不断地更新。 4 ) 互联网的服务用户群体具有极大的多样性。互联网目前联接着成亿数的电脑：用户 基于知识粒度的网贞聚类研究 群体也在不断的扩大。这些用户具有不同背景、兴趣和使用目的。人多数用户都不太了解信 息网络的结构，因而很容易在信息的海洋中迷失方向。 5 )互联网上的信息只有- - 4 , 部分是真正有用的或相关的。也就是说互联网上有9 9 的 信息对9 9 用户而言是无用的。一个用户往往只对互联网上一个1 r 常小的部分感兴趣，但互 联网上充斥着大量无用或不想要的东西，那么如何才能发现真正有用的东西? 如何才能搜索 到真正高质量的有关某一个土题的网页呢? 这些问题促使了有效发现和利用互联网信息资 源的相关研究t 作开展。目前已经有了许多基于索引的互联网搜索引擎，这些搜索引擎搜索 互联网、对互联网网页进行索引、建立并保存巨大的基于关键字的索引，以此来帮助确定包 含特定关键字的网页。利用这类搜索引擎，有经验的用户可以通过提供约束较紧的查询条件 ( 关键字或短语) ，很快找到自己所需要的网页。但是目前基于关键字的全文搜索引擎存在 几点不足：首先是查准率问题，一个主题可能包含成千上万文档，从而导致搜索引擎的查询 返回结果常常也是非常巨大，而其中只有较少一部分与用户相关。其次是查全率问题，许多 与主题相关的文档或许没有包含相戍( 准确) 的关键字。例如：利用“w e bm i n i n g ”关键字， 可能会发现与“m i n i n gi n d u s t r y ”有关的网页，而不是与网络数据分析有芙的论文。道理 很简单，因为文档中没有包含“w e bm i n i n g ”关键字。 由上述问题的分析，可以得出这样一个结论：w e b 数据挖掘就是发现网页的读取模式、 互联网结构和互联网内容的规律和动态特点。互联网挖掘( w e bm i n i n g ) 就是完成上述任务 以帮助人们发现互联网结构和动态特点；从网页的海洋中发现高质量的信息。w e b 数据挖掘 是k d d t w e b 数据领域中的延伸，它是数据库、信息检索、人： 智能、机器学习与闩然语言处 理等几个相关研究领域的聚合，其目的就是要从网页的海洋中发现网页的读取模式、且联网 结构和互联网内容的规律和动态特点以帮助人们解决在w e b j 1 识发现中出现的问题。 1 _ 1 2 w e b 挖掘的分类 目前比较盛行的分类就是根据其挖掘对象将其人致分为三类：w e b p q 容挖掘，w e h 结构挖 掘，w e b 使用挖掘( 图1 ) f 面分别对此三类挖掘分别进行简单介绍。 2 基于知识粒度的| = 。9 页聚类研究 图11w e b 数据挖掘分类 第、w e b 内容挖掘 8 9 1 0 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 t j 容挖掘一部分的多媒体数据挖掘在近几年来受到许多的研究人员的 关注。w e b 内容挖掘的一般过程如图1 2 所示。 图1 2w e b 内容挖掘基本过程 第二、w e b 结构挖掘 i1 1 2 1 3 w e b 文档不但包括文档内容，而且包括页面之间的链接。然而大多数w e b r j 识获取一r 具仅 仅利用网页上的内容，却忽视了页面链接所包含的有价值信息。w e b 结构不仅含有不同页面 之间的超级链接，还包括以h t m l 或x m l 表示的树形结构，文档u r l 的目录路径结构。通过挖掘 这种网页结构信息可以获得能有助于加深对w e b 文档内容理解的模式，这些模式能展示大鼙 有用的隐龠信息。比方说，指向一个文档的链接体现了该文档的被引用情况，而从一个文档 发出的链接则体现了该文档所覆盖的主体的种类。这可以同文献的引用情况相比较，如果某 篇文章经常被引用，说明它非常重要。通过分析网页的u r l 信息，可以找到已经改变位置的 网页。还可以通过分析文档的内存结构可以找到相似网页。c l e v e r 6 中的方法正是利用了 基于知识粒度的网页聚类研究 文档间的链接信息来奁找相关的网页。 第三、w e b 使用挖掘 1 4 1 5 1 6 用户进行网页访问时会产生大量的数据，这些数据主要包括服务器端访问日志，代理端 访问日志和客户端访问目志。w e b 使用挖掘就是要通过分析这些数据米快速发现用户的访问 模式，诸如频繁访问路径和频繁访问页集。根据应用的不同，可以将w e b 使用挖掘分为两种 主要倾向，即：一般的访问模式跟踪与定制的访问模式跟踪。一般的访问模式跟踪通过分析 w e b 访问日志来理解访问模式与倾向，利用这些分析可以清楚地给出较好的w e b 结构及资源提 供者的分组情况。把数据挖掘技术应用 - w e b 访问日志可以获得有趣的访问模式，这有助于 网站的重构与广告位置的选取。定制使片j 跟踪可以分析个人的嗜好与倾向，在显示的信息， 网站的结构与资源的格式等方面进行动态地定制以为每个用户构建符合其个人特色的w e b 站 点。 w e b 使用挖掘基本过程可以分为四个阶段，即：数据采集，预处理，模式发现，模式分析， 其基本流程如图1 3 所示。 1 1 3w e b 挖掘的研究现状 图1 3 w e b 使用挖掘基本过程 1 w e b 挖掘的典型技术分析1 1 7 1 1 8 1 1 1 9 11 2 0 1 w e b 挖掘使用复杂的统计分析和建模技术米发现w e b 数据中隐藏的模式与关系，而使用 普通的数据分析方法很难发现这些内容，因而它需要高级的数据分析技术：概念描述、关联 分析、分类聚类、时序分析、异常分析等。 ( 1 ) 概念描述 概念描述是描述性数据挖掘中的一种最简单类型。作为一种数据分析技术，概念描述不 是数据的简单枚举而是用来产生数据的特征和比较描述。通过概念描述可以对与数据相关 的类和概念用汇总的、简洁的、精确的方式进行描述，这种描述可咀通过卜- 述方法得到( i ) 数据特征化，一般地汇总所研究类( 通常称为目标类) 的数据，或( 2 ) 数据区分，将目标 类与个或多个比较类( 通常称为对比类) 进行比较。数据特征是目标类数据的一般特征或 4 基于知识粒度的划页聚类研究 特性的汇总。通常，用户指定类的数据通过数据库查询收集。例如，为研究上一年销售增加 i o 的软件产品的特征，可以通过执行一个s o l 查询收集关于这些产品的数据。数据区分是 将目标类对象的一般特性与个或多个对比类对象的一般特性比较。目标类利对比类由用户 指定，而对应的数据通过数据库查询提取。例如，你可能希望将上一年销售增加1 0 的软件 产品与同- t 寸期销售至少r 降3 0 的那些进行比较。崩于数据区分的方法与用于数据特征的 那些类似。 ( 2 ) 犬联分析 关联分析是用以发现揭示数据项的内在关联的关联规则，一般有如下形式： i fat h e nb 它表示当a 发生时，b 也可能发生。般用支持度( s u p p o r t ) 和置信度( c o n f i d e n c e ) 来描述 关联规则。 ( 3 ) 分类聚类 分类是数据挖掘中使用得最频繁的一种方法，它是对一个类别的内涵进行描述，对类内 本质性特征和类间区别性特征进行表示。与分类相比较，聚类是一种无监督的学习方法，它 的基本准则是使得属于同一类别内的个体间距离尽可能小，不同类别问的距离尽可能大。 ( 4 ) 时序分析 根据数据随时问变化的趋势，发现某一时间段内数据的相关处理模型，预测将来可能出 现值的分布。它可以看成是种特定的关联模型，但它在关联模型中增加了时间属性。 ( 5 ) 异常分析 数据库中可能包含一些数据对象，它们具有与其它数据对象不同的特征或行为模式，这 些数据对象称异常( o u t , 1 i e r ) 。这些异常包含有大量潜在有价值的知识：分类中的反常实例， 不满足规则的特例等。对这些异常数据进行分析可以发现令人感兴趣的非平凡知识。 2 w e b 挖掘的主要研究方向 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 挖掘研究的主要方向有： 基十知识粒度的网页聚类研究 ( 1 ) 在数据预处理方面多种w e b 数据的收集、结构转换等处理技术方面的研究 ( 2 ) w e b 挖掘方法以及模式识别技术在构造自适应站点以及智能站点服务的个性化和性 能优化方面的研究： ( 3 ) w e b 知识库的动态维护、更新，各种知识和模式的评价综合方法的研究： ( 4 ) 基丁- w e b 挖掘和信息检索的、高效的、具有自动导航功能的智能搜索引擎相关技术 的研究 2 1 儿2 2 2 3 ： ( 5 ) 研究和开发基丁w e b 的多层数据体系结构和智能集成系统，提供相应的查询语言，优 化和维护机制： ( 6 ) 现有的数据挖掘方法与技术的改进及其向w e b 数据的扩展，挖掘算法的适应性和时 效性的研究： ( 7 ) w e b 文档内的模式发现及其在信息提取、文本分析中的应用研究等： ( 8 ) w e b 挖掘的相关技术在电子商务领域的应用研究等。 1 2w e b 文档聚类分析的研究现状 随着互联网的迅速增长w e b 文档聚类技术显得越来越重要，它能帮助知识工作者高效 而准确的发现与某个文档最相似的文档它能提高信息检索系统的返回率( r e c a l l ) 和精度 ( p r e c i s i o n ) ，它能很好地提高搜索引擎的个性化程度 2 2 ，正是这种重要性引起研究者们的 注意，关于w e b 文档聚类的研究工作开展的如火如荣，涌现出了形形色色的w e b 文档聚类方 法，这些方法大体上可分为两大类： ( 1 ) 脱机聚类 这类方法主要是针对大批_ 晕：的网页数据集( 这些网页数据往往是能通过网络机器人 ( r o b o t s ) 或者网络蜘蛛( s p i d e r ) 采用一定的爬行策略从各个网站上采集过来的) 而言的，它 根据一定的度量措施对网页数据进行聚类，其中比较典型的是根据造句法( s y n t a c t i c ) 来给 出一种网页相似度量 2 4 儿2 5 ( 2 ) 联机聚类 6 基于知识粒度的嘲页聚类研究 这类方法主要是针对查询结果( 根据用户的查询请求，从单个或多个搜索引擎返回的结 果) ，它主要是以主题为依据进行聚类，著名的搜索引擎v j v is i m o 2 6 就采用联机聚类的方 法对返同结果进行了处理还有相关的研究1 = 程g r o u p e r 2 7 与c a r r o t 2 8 。 无论是采用脱机聚类方法还是联机聚类方法，现在研究者都在努力尝试利片jw e b 内容挖 掘、w e b 结构挖掘与w e b 使t h j 挖掘来获得对w e b 更加深入的认识与理解，将w e b 本身所具有 的内容、结构特征与用户浏览w e b 使用模式相结合起来，进而对w e b 进行聚类，这是当前 w e b 聚类的总体特点。 许多研究都致力丁将内容信息，_ e f j 户浏览信息，甚至超文本文档结构信息与链接拓扑结 构信息加以整合，提出了各种更为一般化的聚类模型m u k h e r j e a 等人 1 0 提山了一种同时 利用结构和内容的交互式超文本聚类算法在他们的模型中，用户可以精确地描述他们的信 息需求，而所有的节点都包含一些内容及其子图结构的信息但是，这种聚类的算法是半自动 的w e i s s 等人 9 和m o d h a 等人 2 9 分别提出了两种将文档内容和链接结构整合在一起的全 自动聚类算法这两种算法的基本出发点比较接近，都是将文本信息和结构信息分别表示为 独立的向量，再通过算法模型对它们加以整合但在算法模型的选择，相似性的度量以及聚类 的表示上，上述两种算法仍存在较人的芳别p i r o l l i 等人 1 3 不仅考虑了文档的内容信息 和链接的结构信息，而且还将用户的浏览信息整台剑聚类算法中，不同丁文献 2 9 ，文献 1 3 将超文本的文本特征，链接特征以及用户的浏览特征通过一个单一的向最米加以表 示c h e n 3 0 还提出了一种一般化的相似度分析方法，用以整合超文本的内容信息、链接特征 以及浏览模式 1 3 本论文的主要研究内容 本文在理解w e b 数据挖掘技术以及分析传统文本表示模型与文本聚类算法的基础之上， 指出了现有表示模型的缺陷。针对知识t 作者感觉现有w e b 聚类方法所产生的聚类结果的可 理解性较筹这一现象，我们将知识粒度理呛引入，提出了基于知识粒度的w e b 文档聚类方法。 本文首先介绍了w e b 挖掘的相关技术及其在网页聚类的运用现状然后详细分析当前 w e b 文档聚类中所采用的文本表示模型与文本聚类算法，接着引入知识粒度原理，在此基础 之上，我们从以下几个方面来展开研究上作： 娃于知识粒度的嘲页聚类研究 ( 1 ) w e b 聚类方法主要基于“文档一特征词”二级知识粒度的，会产生“假相关”的聚 类结果，基 二此，我们提出了一个多级粒度的w e b 文档表示机制：“d p t ”逻辑表示模 型： ( 2 ) w e b 聚类算法中的相似度量一般采用“特征词特征词”、“文档文档”等，这 样会导致大最“零相似”的产生，基于此，我们提出了基于容著粗集的文本扩展表示模型： e v s m ； ( 3 ) 传统k - m e a n s 聚类方法适合海茸：文档集的处理，但它对孤立点数据比较敏感，对非 球形或非凸形数据的聚类效果不够理想，基丁此，我们提出了一种改进的k - m e a n s 聚类算法 n k m e a n s 。 ( 4 ) 我们提山并实现了一个用于w e b 数据分析的平台w e b a n a l y s e r ，并进一步在此平台 实现了抖j 于f e b 文档聚类分析的w c b g k 算法。 基于知识粒度的网页聚类研究 第2 章传统文本表示模型与常用文本聚类算法 2 1 传统的文本表示模型 对查询如何表示，对文本如何表示，如何计算查询与文本的相关性等一系列问题的解决 方案直接影响到一个信息检索系统的性能，因此如何对文本进行建模表示在信息检索研究领 域中备受关注，本节简单介绍信息检索领域中的三种典型的文本表示模型。 2 1 1 布尔模型 布尔( b o o l e a n ) 模型是基丁集合论和布尔代数的一种简单检索模型，在六、七十年代得 到了较人发展。由丁集合的定义是非常直观，b o o l e a n 模型提供了一个用户容易掌握的信息 检索系统框架。布尔模型通过文本标识与用户给山的检索式进行逻辑比较米检索文档。心户 表述式是把用户给出的检索词用“与”( a n d ) 、“或”( o r ) 、“非”( n o t ) 等布尔运算符连接 起来的式子a 设文档集d = ( d ，d 2 ，d 3 d 。) ，d f ( f = 1 , 2 ，3 n ) 为文本集d 中一篇文档； 又设l = ( t l ，t ：，f 3 t 。) 为文档d l 的索引词集，对于形如q = 彬 a 岷的查询表 述式，如果彬l ，i ，w o i ，则d 为检索到的文档。我们称d 为命中文档，否 则称之为不命中文档。而对于q = 彬v v v 呒的查询表述式，如果至少存在某个 乃( 七= 1 , 2 ) ，则d ，为命中文档，若不存在正( 厅= 1 , 2 m ) ，则d ，为不命中文 档。对于q = 一彬的查询表达式t 如果若不存在暇7 ：( = 1 , 2 m ) ，则d - 为命中文档。 实现布尔检索，首先耍对文档集中每个文档进行标识，索引词可咀采用关键词、自由词、 作者、篇名等能反映文档特征的词，其实，要对文档进行合理的组织，建立文档的索引，通 常把文档组织成倒排文档结构，就是把与某索引词有关的所有文档的索引号通过索引集中在 一起，当通过该索引词查找文档时，可以立即找到文档所在的位置，从而检索刮文档。 布尔检索具有简单，易理解，容易在计算机上实现且检索速度快等优点，故在许多检索 系统中等到应用，例如y a h o o ，g o o g l e 等搜索引擎均采用布尔检索技术。但它也存在一些明 显的缺陷： 、 ( 1 ) 布尔逻辑式的构造方式不易全面反映用户的需求； 9 基十知识粒度的网页聚类研究 ( 2 ) 匹配标准存在某些不合理的地方，例如，在响应某个用“与”连接的检索时，系统 把只含有检索式中的一个或数个但非全部检索词的文档看作与那些不含有检索式中的 任何一个检索词的文档一样无用，同样加排除； ( 3 ) 检索结果不能按照用户定义的重要性排序输山。系统检索输出的文档中，排位靠前 的文档并不一定是文档集中最适台用户需要的文档，用户只能按照检索结果的顺序浏览 才能找到自己最想要的文档。 为了克服上述缺点，人们对布尔检索理论进行了改造，其中目前用得最广且较为成功的 一种方法就是加权布尔检索，它是对索引词给以适当的权重，权值的大小用以反映索引词在 文档中的重要程度。 2 1 2 概率模型 概率模型是基于查询词在相关和1 f 相关文献中的分布概率的，其基本思想就是根据关键 词在相关文档中出现的概率和无关文档中出的概率来判断该关键词的权重。其计算公式如 p ： 2 l o g ( r r 一，) ) ( ( n r ) ( n n r + r ) ) ( 21 ) 其中，w ，。是索引词i 在查询j 中的权重，r 是查询j 所得到的相关文献中包含索引词i 的文献数量，r 是与奇询j 相关的文献总数，n 是用于检索的所有文献中包含索引词i 的文 献数量，n 是文献总集包含的文献数目。 相关反馈机制的研究表明：利用少量相关文献计算调格索引词权重可以促使检索性能显 著改进，在此方法中就采用i d f 度量，这表明概率模型对于相关反馈中调整词权这一方面是 很有用的。索引词的权重计算公式如下： w e i g h t * = ( 1 0 92 ( f r e q * + 1 ) i d f i ) l l 0 9 2m ( 2 2 ) 其中w e i g h t m 是素引词i 在文献k 中的权重，f r e q * 是词i 在文献k 中的i u 现频率m 女 是文献k 中的词的总量。 r d f , = l 0 9 2 ( n n u m d f ) + 1 ( 2 3 ) 1 0 基于知识粒度的网页聚类研究 其中n 是文档集合的文档总数，n u m d 是文档集合中包含索引词i 的文献总数。以上描 述了仅对用户给山的查询词的重新加权算法，另一种较为复杂的做法是对查询进行扩展。 概率模型具有如f 优点： ( 1 ) 采用严格的数学理论为依据，为人们提供了一种数学理论基础来进行检索： ( 2 ) 采用相关反馈原理，可开发出理论上更为坚实的方法。 它的主要不足是： ( 1 ) 增加存储和计算资渊的开销； ( 2 ) 参数估计难度较人。 2 1 3 向量空间模型 向量空间模型( v e c t o rs p a c em o d e l ，简写为v s m ) 由s a l t o n 等人于2 0 世纪6 0 年代末 提出，是一种简便而高效的文本表示模型，其理论基础是代数学 3 1 。与布尔模型不同，向 量空间模型把用户的查询要求和数据库文档信息表示成由检索项构成的向量空间中的点。而 通过计算向揖之间的距离来判定文档和查询之间的相似程度。然后，根据相似程度排列查询 结果。向量空间模型的关键在于特征向量的选取和特征向最的权值计算两个部分。用向量空 间模型计算向量距离时，一般采用向量的夹角余弦来表示，两个文档之间相同的词越多且这 些词的权重越高，则其距离越近。计算权重的目的是要止确突出每个索引项在文章中的重要 程度，一般米讲，某个词在某文本中经常出现且在其他文本中不常出现，就说明该词对该文 本或该类文本更具有代表性应具有更高的权重。另一方面，如果一个索引项在很多文档中 都出现，那么这个索引项则不能很好地代表某一类文档，其权重应较小。 v s m 的基本概念： ( 4 ) 文档( d o c u m e n t ) ：泛指一般的文档或文档片断。 ( 5 ) 特征项( t e r m ) ：当文档的内容被简单看成是基本语言单位集台时，这些基本的语言 单位被称为特征项，即文档可用项集来表示为d ( t 1 ，t 2 ，t 3 f 。) ，其中f i 是第i 个特征 项1 f 。 基十知识粒度的网页聚类研究 ( 6 ) 特征项权值( t e r mw e i g h t ) ：对于含有n 个项的文档d ( t 1 ，t 2 , t 3 t 。) ，特征项t f 常 被赋以一定的权重彬来表示它在文档中的重要程度， 即 d = ( ， ， ) ，也可以简记为d = ( w i ，w 2 ，w 。) ( 7 ) v s m ：给定一个文档d = ( ， ， ) ，可以将t l ，t 2 ，f 。 看成是一个n 维的坐标系，而，为相应的坐标值，因而d ( 嵋，w o ) 可 以看成是r l 维空间中的一个向量。我” 称( 彬，) 为文档d 的向量表示。 向量空间模型最主要的优点在于： ( 1 ) 该模型的权重计算方法能够提高系统的检索性能 ( 2 ) 模型中使用的部分匹配方法能检索出与用户的查询输入条件“近似”的文档 ( 3 ) 在模刑中用余弦方法进行距离度量，因此可以根据检索出的结果与查询条件的相关 程度对结果进行排序。 向昔空间模型也有缺点。住该模型中有一个假定：所有的索引项之间是相互独立的。在 权重计算公式中就没有考虑索引项之间的相互关系，但人们发现在实践中，这些检索项的 相互依赖性对系统的性能将造成影响。闪为在某些文档中，很多索引项都是相互依赖的如 果将它们不加选择地应用于语料库所有的文档中，必将损害系统的性能。 2 2 常