（管理科学与工程专业论文）web文本挖掘系统.pdf

w e b 文本挖掘系统 摘要 互联网的迅速发展导致网上信息飞速增长，形成了我们不能忽视 “信息爆炸”的问题信息极大丰富却导致知识的难以查询。目前， w e b 已经发展成为拥有3 亿页面的分布式信息空间，而在这些异质的 3 亿w e b 页面的资源中，蕴含着大量的人们迫切需要的知识。本文 针对网页采集、网页净化、获取文档特征量、w e b 文本聚类这几部分 内容，进行了深入的研究，完成了以下工作： ( 1 ) 介绍了网页采集的基本原理，研究并且比较了目前常用的 几种网络信息采集算法。( 2 ) 为了有效对网络信息进行处理，必须对 采集进来的网页进行净化，本文介绍了网页净化基本原理，研究分析 了各种网页净化方法。( 3 ) 提出了一种新的网页净化算法基于 d o m 树的网页净化算法。该算法通过比较同一网站网页的d o m 树来净 化网页。( 4 ) 研究比较了国内当前比较流行的中文分词算法，比如基 于字典词库匹配的分词方法、基于词的频度统计的分词方法、基于知 识理解的分词方法。( 5 ) 介绍了如何通过向量空间模型建立w e b 文档 的特征向量。( 6 ) 研究了两种常用的w e b 聚类算法一k 平均算法和 s o m 算法。( 7 ) 提出了一种新的w e b 聚类算法，投影w e b 聚类算法。 关键词：w e b 文本挖掘，网页采集，网页净化，中文分词，w e b 聚类 硕士学位论文 w e b 文本挖掘系统 w e b m i n i n gs y s t e m a b s t r a c t t h er a p i dd e v e l o p m e n to ft h ei n t e r n e tl e dt ot h er a p i dg r o w t ho fo n l i n e i n f o r m a t i o n w ec a nn o ti g n o r et h e “i n f o r m a t i o ne x p l o s i o n p r o b l e ma n ym o r e , w h i c h h a sr e s u l t e di ne n o r m o u sp r o b l e m se s p e c i a l l yf o ri n a c c e s s i b l et o i n f o r m a t i o n k n o w l e d g e c u r r e n t l y , 3 0 0m i l l i o nw e bp a g e sh a v eb e e nd e v e l o p e di n t oah u g e d i s t r i b u t e di n f o r m a t i o ns p a c e , w h e r ea b u n d a n tk n o w l e d g er e s o u r c e sa r ec o n t a i n e d w e bi n f o r m a t i o nc o l l e c t i o n ，w e bp a g ep u r i f i c a t i o n ，t e x tc l u s t e r i n ga n dc h i n e s e w o r ds e g m e n t a t i o na r es t u d i e di nt h i sp a p e rs h o w n a sf o l l o w s ( 1 ) b a s e do nt h et h e o r yf o ra c q u i s i t i o no fw e b s i t ei n f o r m a t i o n , c u r r e n tu s e f u l a l g o r i t h m si nt h i sf i e l da r es t u d i e da n dc o m p a r e d ( 2 ) i no r d e rt oh a n d l et h en e t w o r k i n f o r m a t i o ne f f i c i e n t l y , i ti so f n e c e s s i t yt op u r i f yw e bp a g e s e l e m e n t a r yp r i n c i p l e s o fw e bp a g ep u r i f i c a t i o na r ee x p l a i n e di nt h i sp a p e r , a n dv a r i o u sp u r i f i c a t i o n t e c h n o l o g i e sa l ea n a l y z e d ( 3 ) ab a n dn e ww e bp a g ep u r i f i c a t i o na l g o r i t h mi s b r o u g h tu pb a s e do nd o mt r e e , w h i c hi sr e a l i z e dt h r o u g hc o m p a r i n g d o r at r e go f p a g e s i nt h es a m ew e b s i t e t h en o i s e so f p a g e si nt h es a m ew e b s i t ea r er e l a t i v e l ys i m i l a r ( 4 ) p o p u l a rd o m e s t i cs e g m e n t a t i o na l g o r i t h m s a r ec o m p a r e d i n c l u d i n gs e g m e n t a t i o n m e t h o do nb a s i so f m a t c h i n gt h et h e s a u r u sd i c t i o n a r y , s e g m e n t a t i o nm e t h o dg r o u n d e d o ns t a t i s t i c a lf r e q u e n c yo f w o r d ，a n ds e g m e n t a t i o nm e t h o db a s e do nk n o w l e d g eo f t h e w o r d ( 5 ) h o ww e b d o c u m e n te i g e n v e e t o re s t a b l i s h e db yw e bv e c t o rs p a c em o d e l i sd e s c r i b e di nd e t a i l ( 6 ) t w ot y p i c a lc l u s t e r i n ga l g o r i t h m s ，ka v e r a g ea l g o r i t h ma n d $ o t na l g o r i t h ma r ei m p l e m e n t e d ( 7 ) an o v dw e bc l u s t e r i n ga l g o r i t h mn a m e d p r o j e c t i o nw e bc l u s t e r i n ga l g o r i t h mi sp u tf o r w a r df i n a l l y k e y w o r d s ：w e bt e x tm i n i n g , p a g ec o l l e c t e d ，p a g ep u r i f y , c h i u 雠w o r d s e 掣n e n t a t i o n , w e bc l u s t e r i n g i i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究： 作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 本人为获得浙江工商大学或其它教育机构的学位或证书而使用过的 材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示谢意。 签名：盔趁日期：渺7 年3 月日 关于论文使用授权的说明 本学位论文作者完全了解浙江工商大学有关保留、使用学位论文 的规定：浙江工商大学有权保留并向国家有关部门或机构送交论文的 复印件和磁盘，允许论文被查阅和借阅，可以将学位论文的全部或部 分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制 手段保存、汇编学位论文，并且本人电子文档的内容和纸质论文的内 容相一致。 保密的学位论文在解密后也遵守此规定。 签名：名埏导师签名： 日期：刎1 年岁月日 8 8 - 硕士学位论文w e b 文本挖掘系统 1 。1 研究背景和意义 第一章引言 互联网的迅速发展，使得网上信息飞速增长，对此，我们称之为信息爆炸。 即互联网上充斥着大量的信息，而用户却很难在这信息海洋中找到有用的知识。 w e b 已经成为世界上最大的信息仓库，而这也意味着，随着信息量的增长，人 们有效使用w e b 信息也越来越困难。与传统的信息资源相比，i n t e r n e t 的开放 性使其具有以下显著的特点：1 ) 动态性，w e b 上的信息时刻都处于变化之中， 新的页面在不断出现，旧的页面也在不断更新和删除( 包括内容的改变位置的移 动等) ；2 ) 半结构化或无结构化w e b 上的信息通常是无组织的，没有关系数 据库中数据的结构化特性或者是只有有限的结构特性，这使得信息的索引变得很 困难；3 ) 异构性，信息分布在不同的平台上，站点结构各异，通过不同的协议 ( 如t c w i ph t t p 等) 相互连接。信息结构形式也各不相同，多语种、多类型的 信息交织在一起，杂乱无序。 这使得我们在使用互联网的同时也遇到了知识难以获得的问题，如何在庞大 的网络信息中高效地获得有价值的知识成为当前迫切需要解决的问题。 使用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 挖掘是一个具有极大潜力的研究方向。一些国际会议，例如k d d 79 7 、 i j c a i 9 9 等，已经或即将举行有关w e b 挖掘的专题讨论，并且对其理论、体 系结构、算法等展开研究。本文对w e b 挖掘的定义、任务、功能作了系统性的 研究。 硕士学位论文 w e b 文本挖掘系统 1 2 本文的研究内容 本文研究内容是如何构造一个w e b 挖掘系统。分以下内容：1 、w e b 挖掘 的定义。2 、w e b 信息的采集。研究网络信息采集原理与当前存在的各种采集算 法。3 、介绍了网页净化基本原理，研究分析了各种网页分块算法以及净化方法。 提出了一种新的网页净化算法基于d o m 树的网页净化算法。该算法的原理 是比较同一网站的不同网页，删除那些内容相似的噪声页面。4 、研究比较了国 内当前比较流行的中文分词算法。5 、介绍了如何通过向量空问模型建立w e b 文档的特征向量。6 、研究了两种常用的w e b 聚类算法k 平均算法和s o m 算法，提出了一种新的w e b 聚类算法投影w e b 聚类算法。 网页采集、网页净化和w e b 文档聚类是w e b 挖掘系统的重要组成部分。 网页采集可以从互联网站点中获取网页数据；网页净化可以去除噪音内容，更好 的满足客户需要；w e b 文档聚类有助于用户分类查询，提高精度【2 1 。本文研究 了如何构造一个w e b 挖掘系统，并且详细的叙述了系统各个组成部分的工作原 理和方法，因而本文的研究具有相当的实用价值和理论价值。 1 3 本文的组织结构 第一章是引言，主要介绍研究背景及其意义。 第二章叙述了w e b 挖掘的定义，并且研究了w e b 挖掘系统和搜索引擎的 区别和联系。 第三章介绍了w e b 采集的原理和工作机制，比较研究当前各种搜集算法。 第四章是网页净化，比较研究当前的各种网页分割算法及净化算法，在此基 础上提出一种新的网页净化算法一基于d o m 树的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 挖掘的定义 2 1w e b 挖掘的定义 w e b 挖掘是一项综合技术，涉及w e b 、数据挖掘、计算机语言学、信息学 等多个领域。w e b 文本挖掘技术研究一文对w e b 挖掘作如下定义：w e b 挖掘是指从大量w e b 文档的集合c 中发现隐含的模式。 w e b 挖掘从数据挖掘发展而来，其对象是大量、异质、分布的w e b 文档1 3 1 。 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 内容( c o n t e n t ) 的挖掘和w e b 结 构( s t r u c t u r e ) 的挖掘 ( 1 ) w e b 内容挖掘 w e b 内容数据挖掘是从w e b 数据中抽取知识，以实现w e b 资源的自动检 索，提高w e b 数据的利用效率。w e b 数据分布范围很广，有f t p 上、g o p h e r 中的、数字图书馆中的，还有企业自己w e b 网站上的，也有隐形的私人数据和 动态查询的结果。数据的形式也是多样，除了文本外还有图形、声音等。因此， 多媒体数据挖掘也是w e b 内容数据挖掘内容之一。这些都是非结构化的数据， 人们把数据挖掘技术用于从半结构化或非结构化文档发现有价值的信息称作 k d t ( k n o w l e d g ed i s c o v e r y i nt e s t s ) ，但是，文本只是w e b 数据的一种形式， 因此，k d t 也是w e b 内容挖掘的一个特例。 ( 2 ) 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 和h i t s 改进算法， 人们采用这些算法主要是计算w e b 页面之间的关联程度。这不仅可用于提高网 上搜索引擎搜索结果的准确性，在g o o g l e 和c l e v e r 等系统中已经有应用，还可 用于挖掘网站之间的通讯、相互参引关系。 本文所研究的着重点在于w e b 内容挖掘，所以文中w e b 挖掘一词一般指 w e b 的内容挖掘。文本挖掘研究的关键在于文本内容的量化表征，利用文本挖 掘，可以从i n t e m e t 上成千上万的w e b 网页中获取需要的实时数据、市场信息、 宏观经济环境、政策和法规等消息。w e b 文本挖掘可以很好的支撑企业进行信 息管理、决策分析，从而也极大的促进了w e b 文本挖掘技术的发展。 2 2w e b 挖掘系统和搜索引擎的异同 搜索引擎是一种能够通过i n t e m e t 接受用户的查询指令，并向用户提供符合 其查询要求的信息资源网址的系统。它是一些在w e b 中主动搜索信息( 通过关 键词) 并将其自动索引的w e b 网站，其索引内容存储在可供检索的大型数据库 中。一些搜索引擎搜索网页的每一个单词，而另一些搜索引擎则只搜索网页的前 二百至五百个单词。当用户输入关键词( k e y w o r d ) 查询时，该搜索引擎会告诉 用户包含该关键词信息的所有网址，并提供通向该网络的链接。搜索引擎既是用 于检索的软件又是提供查询、检索的网站。他和w e b 挖掘系统存在以下的区别 和联系。 1 、都是对w e b 空间的信息进行检索，所以他们都需要由网上机器人( s p i d e r 或r o b o t ) 自动在网页上按某种策略进行远程数据的搜索与获取。但是搜索引擎是 先由用户的命令驱动的，用户需要明确提出查询要求，然后根据用户的查询要求， 检索互联网上的匹配页面。搜索引擎的用户知道他们需要的大致搜索结果；而 w e b 挖掘系统结果对用户来说是一个未知数。 2 、他们的着重点不同，搜索引擎着重于文档中显式存储的字词和链接：而 w e b 挖掘系统试图更多地理解w e b 内容下隐藏的知识和模式。搜索引擎的工 作结果就是向用户提供匹配w e b 页面的链接，以使用户能非常方便的访问这些 硕士学位论文w e b 文本挖掘系统 资源。而w e b 挖掘系统的目的与数据挖掘类似，从大量的w e b 页面中识别有 效的、新颖的、潜在有用的模式和知识。 3 、使用场合不同。搜索引擎是当用户有明确的信息需求时候使用的，搜索引 擎将通过网上机器人( s p i d e r 或r o b o t ) 访问各类网站，返回匹配用户需求的链接。 而w e b 挖掘系统的用户，一般是没有明确的信息需求，他们希望通过w e b 挖 掘系统发现文档集合中所具有的结构、趋势、含义 4 1 。在这些场合下，就需要使 用w e b 挖掘技术。 综上所述，w e b 挖掘系统并不是用来取代搜索引擎，二者是相辅相成的。一 方面，这两种技术各有所长，有各自适用的场合；另一方面，我们可以利用w e b 挖掘的研究成果来提高搜索引擎的精度和效率，改善检索结果的组织，使搜索引 擎系统发展到一个新的水平。 2 3 国外的研究现状 w e b 内容数据挖掘和一直都存在的信息检索有较深的渊源，因此，许多技术 都是源自信息检索领域。互联网上信息量大，由于这些信息缺乏结构化、组织的 规整性，目前几乎所有的互连网查询工具( 搜索引擎) 都面临匹配的查准率低， 给出的查询结果大量冗余但是查全率却不高的问题。研究这个问题，学术界有两 派。 一是从信息检索角度研究这个问题，主要研究如何处理文本格式和超级链接 文档，这些数据是非结构化或者是半结构化的。数据以词组、短语、n - 维词元、 词包等形式表示，采用t f i d f 和变量、机器学习和词组统计包括自然语言的统 计( n l p ) 等研究方法对文档进行分类、聚类，研究抽取词组在文档中出现的规 律。g r a v e n 等研究了用关系原型表示文档内容，采用修改了的贝叶斯算法，给 超文本链接分类，寻求w e b 页面关系，抽取规则。c r i m m i s 研究了用短语、超 级链接和信息元表示文档内容，采用自动和非自动学习的分类算法，对文档进行 聚类和分层分类。f t m f l c r a n z 、j o a c h i m s 用词包和超级链接信息表示文档内容，采 用规则学习算法t f i d f ，对超级链接文档进行分类。m u s l e a 等用词包、标识和 词位信息表示文档，采用规则学习算法，训练抽取规则。 二是从数据库角度研究，主要处理半结构化的w e b 数据库，也就是超级链 硕士学位论文 w e b 文本挖掘系统 接文档，数据多采用带权图或者对象嵌入模型( o e m ) ，或者关系数据库表示， 应用p r o p r i e t a r y 算法、i l p 或者经过修改了的关联规则挖掘算法，从而寻找出网 站页面之间的内在联系。g o l d m a n 、n e s t o r o v 等人用o e m 表示文档，采用 p r o p r i e t a r y 算法，分别在半结构化数据中寻找标引字段和数据的层次结构。z a i a n e 和h a l l 用关系数据库表示数据，采用面向对象的推理方法，寻找多层次数据库 的构建策略，为文献标引提供决策依据。 硕士学位论文 w e b 文本挖掘系统 第三章网页采集 w e b 信息采集指通过网络机器人( r o b o t 或s p i d e r ) ，从w e b 上自动的获取 页面信息，并且随着链接不断向所需要的w e b 页面扩展的过程【7 1 。这种技术目 前已经非常成熟了。采集程序从一个网页或多个网页出发，逐步遍历网上的文件。 采集程序首先解析网页的h t m l 代码，查找该页面内的超链接，然后通过递归 或非递归的方法来不停地搜索本网页包含的其它链接。 考虑到递归算法每次要将本次未完成的代码压进程序代码栈，会在执行时要 耗费大量计算机资源，而且这种程序不能使用多线程技术。因此在本系统采取的 是非递归算法。 3 1w e b 采集的系统实现 为了提高系统采集信息的能力，我们使用多线程技术。实践证明，多线程机 制，能提高机器人的效率。多线程使机器人在处理网页时，可请求、等待其它网 页。在编写机器人程序时通常的做法是为每一个请求创建一个线程，但为每个请 求创建一个新线程的开销很大。而且在请求很多时，在创建和销毁线程上花费的 时间和消耗的系统资源要比花在处理网页上的时间和资源更多。我们可用线程池 来解决这个问题。 如果每当一个请求到达就创建一个新线程，开销是相当大的。在实际使用中， 每个请求创建新线程的服务器在创建和销毁线程上花费的时间和消耗的系统资 源，甚至可能要比花在处理实际的用户请求的时间和资源要多得多。除了创建和 销毁线程的开销之外，活动的线程也需要消耗系统资源。如果创建太多的线程， 可能会导致系统由于过度消耗内存或“切换过度”而导致系统资源不足。为了防 止资源不足，服务器应用程序需要一些办法来限制任何给定时刻处理的请求数 目，尽可能减少创建和销毁线程的次数，特别是一些资源耗费比较大的线程的创 建和销毁，尽量利用已有对象来进行服务，这就是“池化资源”技术产生的原因。 线程池主要用来解决线程生命周期开销问题和资源不足问题。通过对多个任 务重用线程，线程创建的开销就被分摊到了多个任务上了，而且由于在请求到达 时线程已经存在，所以消除了线程创建所带来的延迟。这样，就可以立即为请求 硕士学位论文w e b 文本挖掘系统 服务，使应用程序响应更快。另外，通过适当地调整线程池中的线程数目可以防 止出现资源不足的情况。 一个比较简单的线程池至少应包含线程池管理器、工作线程、任务队列、任 务接口等部分。其中线程池管理器( t h r e a d p o o lm a n a g e r ) 的作用是创建、销毁 并管理线程池，将工作线程放入线程池中；工作线程是一个可以循环执行任务的 线程，在没有任务时进行等待；任务队列的作用是提供一种缓冲机制，将没有处 理的任务放在任务队列中；任务接口是每个任务必须实现的接口，主要用来规定 任务的入口、任务执行完后的收尾工作、任务的执行状态等，工作线程通过该接 口调度任务的执行。 在系统中，我们设置了三个队列分别是等待队列、错误队列、完成队列。 1 ) 将初始u r l 存入到等待队列。2 ) 解析线程不停地访问等待队列的u d ，遍历该 页面，获取页面中的w l ，然后将u r l 和等待队列、错误队列、完成队列的u r l 进 行比较，如果该u d 不在这3 个队列中，那么将u r l 存入等待队列中。3 ) 如果解 析完成，那么该u d 从等待队列中删除，存入到完成队列；如果出错，则存入到 错误队列。4 ) 继续执行步骤2 ) 。程序的流程如图3 - 1 所示。 硕士学位论文w e b 文本挖掘系统 图3 - ! 网页采集模块系统结构图 一l o 硕士学位论文w e b 文本挖掘系统 w e b 中不同的网页具有不同的重要程度，有一些网页比较重要，另一些并 不是很重要。在采集网页时如何判别网页的重要度昵? p a g e r a n k 方法和h i t s 算法是两个比较著名的算法，它们都是基于链接结构评价的评价算法，只考虑页 面间的引用关系，但是却忽略了与主题的相关性。其中的p a g e r a n k 方法被g o o g l e 用来自动判断网页重要性，是g o o g l e 中表示网页重要性的综合性指标。 3 2p a g e r a n k 方法 p a g e r a n k 算法是1 9 9 8 年由斯坦福大学( s t a n f o r du n i v e r s i t y ) 的s e r g e yb r i n 和 l a w r e n c e p a g e 提出f 6 】，它借鉴了传统情报检索理论中的引文分析方法：当网页 1 有一个链接指向网页2 时，就认为网页2 获得了一定的分数，该分值的多少 取决于网页l 的重要程度，即网页1 的重要性越大，网页2 获得的分数就越高。 由于国际互联网上的链接相互指向的复杂程度，该分值的计算过程是一个迭代过 程，最终网页将依照所得的分数进行排序并将检索结果送交用户，这个量化了的 分数就是p a g e r a n k 值，其计算公式如下： e n ( 加r 寺”巾磊，器 。， 其中，t 为计算中的页面总量，y 1 【 1 f m = 1 ( 4 - 2 ) 1 代表元素节点e 的子类型节点的个数：p i 是网页使用e 节点的第i 个子类型的 概率，即出现第i 个子类型的网页个数与总网页个数的比值；s l 是e 的子类型节 点；f 是一个大于零的可调参数；另外 c o m p i m p ( e ，) c o m p l m p ( 墨) = 上l f 一 ( 4 - 3 ) c b 聆妒i m p ( 墨) 表示类型节点s i 的重要程度，与表示s i 中的元素节点，k 表示s j 中元素节点的个数。 对于s s t 树中的叶节点e ，重要程度计算公式如下， c o r n i m p ( d = ， t t ( a ，) 1 一型- 矿埘 1 ， 。 1 i f m亏1(4-4) 其中a l 表示节点e 中的特征项，如词语，图像文件，链接等；l 是节点e 中特征 项的个数；m 是含有e 节点的网页个数；h ( a i ) 是a i 的信息熵。h ( a 1 ) 计算公式如 下， h ( a ，) = 一p f l o 鳓 ，。1 ( 4 5 ) 其中p i i 表示含有节点e 的网页中出现a i 的概率。 噪声的判断：如果s s t 中元素节点e 的所有后继节点的重要程度以及自身 的重要程度小于某个阖值则认为e 是噪声。实验表明这种网页净化方法能有效 地提高网页分类系统的性能。 4 3 基于v ip s 的净化算法 该算法输入一个网站的所有网页，输出该网站网页中非噪声内容。 硕士学位论文 w e b 文本挖掘系统 步骤1 ：依据v i p s 算法，提取一个网站上的所有网页的内容结构，并将内 容结构中的叶结点存入数据库中。每一个网页块都包含一些属性，表4 1 列出了 部分属性及其含义。 表4 1 网页块的属性及其含义 属性名称含义 o r i g i n a l u r l原网页的u r l t a g n a m e 描述网页块在那一个标签里 l n n e r h t m l网页块中的h t m l 代码 c o n t e n t 网页块中的内容 i r m e r t e x t 网页块中的文本内容 t e x t l e n g t h 网页块中的文本内容的长度 d o c 网页块中内容的一致程度 l m g q u a n t i t y 网页块中包含的图片数量 i s i m g 该网页块是否是图片 l i n k q u a n t i t y 网页块中超链接的数量 l i n k t e x t l e n超链接文本的长度 o b j e c t r e c t l e f l 网页块的左位置 o b j e c t r e c t t o p 网页块顶端位置 o b j e e t r e c t w i d t h 网页块的宽度 o b j e c t r e c t h e i g h t 网页块的高度 i d 网页块的标识号 步骤2 ：从存放网页块的数据库中读取网页块，如果i s l m g = t r u e ，则该网页 块是图片，将该网页块作为噪声从数据库中删除。 步骤3 ：网页块权重 权重的计算基于以下几个考虑： a 、噪声一般在一个网站中多次出现，如版权信息； b 、噪声中的文字相对于整个网页来说比较少； c 、噪声一般位于网页的两侧和上下部； d 、网页的主题内容包含的链接较少，如1 6 3 中的新闻。 颈士学位论文w e b 文本挖掘系统 对应这几点考虑，有如下几个规则： a 、一个网页块在同一个网站中出现的次数越多越不重要。 b 、一个网页块中包含的文字越多越重要。 c 一个网页块距离网页的中部位置越近越重要。 d 、一个网页块链接文本的比重越小越重要。 具体权重计算过程如下： ( 1 ) 统计网页块的a m o u n t ( 网页块出现的次数) 根据v i p s 获得的整个网站的网页块中，有些是相同的，因为某一个内容可 能在多个网页中出现，例如版权信息。统计数据库中某一个网页块的a m o u n t 时， 就要判断哪些网页块是相同的。判断两个网页块之间是否相同，一方面要检查它 们的表现风格( 位置，颜色、大小以及通过其它h t m l 标签表现出来的风格) 是否相同，两一方面计算两个网页块中的i n n c r t e x t ( 网页块中的文本内容) 是 否在含义上或语义上相同。为什么同时考虑表现风格和含义呢? 一方面，多个网 页中都出现的含义相同的内容，即使外在表现风格不一样，也常常是噪声。另一 方面，如果只从风格上来判断是否相同，那么主题内容也可会被误认成噪声，因 为同一个网站中主题内容也常常有相同的表现风格。在判断网页块中的文本是否 相同时，先将两个网页块中的文本表示成向量的形式，然后计算两个向量之间的 距离，以此作为两个网页块中文本之间的相似度。如果相似度超过某个阈值，则 认为两个网页块中的文本在语义上是相同的。具体的计算方法如下： 特征项提取。这里有两种方法供选择。方法一，将所有网页块中的i n n c r t c x t 分词，去掉虚词、代词等，根据禁用词词表选取名词、动词、形容词和副词。根 据特征项提取方法提取信息量大的词语作为特征项。文献 9 】 1o 】总结了当前的特 征项提取方法，如i g ( i n f o r m a t i o ng a i n ) 、z 统计量( c h i ) 、文档频率方法、 c f ( c a t e g o r yf r e q u e n c y ) 一d f 方法、互信息( m i ) 、信息熵等。方法二，直接将中文 知识库“知网”( 1 q 中的词语作为特征项。第一种方法有点复杂，但能大大降低网 页块特征向量的维数，提高网页相似度比较的效率；第二种方法十分简单，但特 征向量的维数较高，影响相似度比较的速度。 将网页块中的i n n 盯t e x t 表示成特征向量。网页块d 的特征向量表示为： d ( w l ，w 2 ，w w ) 硕士学位论文w e b 文本挖掘系统 w i 由如下公式计算得到， t f ( t ，孑) l o g ( 马 w ( t ，d ) = ( 4 - 5 ) 其中，w ( t ，d ) 为特征项t 在网页块孑中的权重，而矿( f ，d ) 为t 在孑中的 词频，n 为网页块的总数，n t 为网页块中出现t 的网页块数量，分母为归一化 因子。 两网页块中文本的相似度计算。计算公式为： 材 s i r e ( g , ，d j ) = 其中，t 为数据库中第i 个网页块的特征向量，d ，为第i 个网页块的特征向量， m 为特征向量的维数，为向量的第k 维。 如果两网页块的文本相似度超过某个值c ，则认为这两个网页块在语义 上相同。c 的值要设的高一点，比如9 5 。 在判断两个网页块是否相同时，以语义相同为主，风格相同为辅，注重语义 上的相同。如果同一个网页块在同一个网页中多次出现，统计时以一次计算。 ( 2 ) 计算网页块相对于整个网页的文字长度 相对文字长度= 网页块的t e x t l e n g t h 整个网页的文字长度。 ( 3 ) 计算网页块的相对位置 从步骤1 可得知网页块的起始位置、宽和高，分别是：o b j c c t r e c t l c f i 、 o b j e c t r e e t t o p 、o b j e e t r e e t w i d t h 、o b j e e t r e e t h e i g h t 。网页块的中心位置为： o b j c c t c c n t x = o b j e c t r e c t i _ c f t + o b j e e t r e e t w i d t h