（计算机应用技术专业论文）基于web的中文文本挖掘技术的研究及实现.pdf

m st h e s i s ： i l 1ll iillll lli filli i y 1718 2 5 8 r e s e a r c ha n dr e a l i z a t i o no fc h i n e s et e x t m i n i n gt e c h n i q u e sb a s e d - - o i lw e b s p e c i a l t y ：一c o m p u t e ra p p l i c a t i o nt e c h n o l o g y p o s t g r a d u a t e ：h 丛! ! i 塾g s u p e r v i s o r ：! q i 塑g 翌堕i 鲨堡垒 s c h o o lo fi n f o r m a t i o ns c i e n c e & e n g i n e e r i n g c e n t r a ls o u t hu n i v e r s i t y c h a n g s h a ，h u n a np r o v i n c e ，c h i n a 原创性声明 木人声明，所呈交的学位论文足木人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除- 论文中特别加以标注和致谢 的地方外，论文中4 包含其他人已经发表或撰写过的研究成果，也彳 包含为挟得中南人学或三他单位的学位或证书而使用过的材料。与我 共i 一下作的i 一志对本研究所作的贡献均已在论文中作了明确的说明。 作者签名： 日期：丝年生月望日 学位论文版权使用授权书 本人了解中南人学有火保留、使用学位论文的规定，即：学校 有权保留学位论文并根据国家或湖南省有关部门规定送交学位论文， 允许学位论文被查阅和借阅；学校可以公布学位论文的伞部或部分内 容，可以采用复印、缩印或其它了段保存学位论文。同时授权中困科 学技术信息研究所将本学侮沦文收录到中国学位论文全文数据库， 并通过网络向社会公众提供信息服务。 嗍：埠年“月午日 l 摘要 随着i n t e r n e t 网络的商速发展，信息爆炸时代也随之到来。山于 i n t e r n e t 的开放性、动态性、异构性使得用户很难快速、准确的从 w w w 上抉取所需的信息，因此如何有效的从网络上抉取古价值的信 息成为当前研究的热点。w e b 义奉挖掘技术就是解决上述问题的一种 方法，它借鉴数据挖掘的丛本思想和理论方法，从人量半结构化、异 构的w e b 义档的集合中发现潜在、有价值的知识。本文主要研究中 文w 曲文本挖掘技术。 奉文首先介绍了w e b 文本挖掘的研究背景、研究意义、研究现 状以及相火的理论知识。 其次，研究了w e b 文本信息提取问题。本文根搬w e b 贞卣的特 征，在分析其结构的基础上，设计并实现了一种利用网页的d o m 树 结构基于统计的网贞有效信息提取方法。该方法有效地过滤掉了首贞 类型、图片类型以及框架类型的网页，并有效的剔除土题型网页中的 标签、广告、图片等内容，保留网页正文及相关信息。 接着，本文财传统的权重计算算法t f i d f 进行了分析，并针对 其不足之处，在综合考虑特征项的类分布信息和文本语义两个方面的 基础上对该算法进行了改进。并将t f i d f 算法以及改进后的算法应 用到k n n 分类中进行实验，实验结果t l f 明了该算法的有效性。 最后，在基于以上研究的基础上，构建j ：实现了一个中文w e b 文本挖掘系统的原型- - c w t m s ( c h i n e s ew e bt e x tm i n i n gs y s t e m ) 。 关键词：w e b 文本挖掘，信息提取，向量空问模型，特征权重， 插件 t a bs 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 e tt e c h n o l o g y , t i l ei n f o r m a t i o n e x p l o r i n ge r ai sc o m i n g q u i c k l ya n da c c u r a t e l yo b t a i n i n gw h a tu s e r s n e e do nw w wi sg e t t i n gm o r ea n dm o r ed i f f c u l tb e c a u s eo fi n t e r n e t s o p e n i n g a n d d y n a m i c a n d h e t e r o g e n e i t y , h o wt o o b t a i nv a lu a b l e i n f o r m a t i o nb e c o m e sar e s e a r c hh o t s p o tn o w w e bt e x tm i n i n gt e c h n o l o g y i sam e t h o dt os o l v et h ea b o v eq u e s t i o n i tc a l lf i n dl a t e n ta n dv a lu a b l e k n o w l e d g ef r o mag r e a td e a lo fs e m i s t r u c t u r e dh e t e r o g e n e o u sd a t ab yt h e m e t h o d so fd a t am i n i n g t h i st h e s i sm a i n l yi n t r o d u c e so u rr e s e a r c ho n c h i n e s ew e bt e x tm i n i n gt e c h n o l o g y f i r s t ，i ti n t r o d u c e st h er e s e a r c hb a c k g r o u n d ，r e s e a r c hp u r p o s e ，a n d s o m eb a s i ct h e o r i e so fw e bt e x tm i n i n g s e c o n d ，i td o e ss o m er e s e a r c hi nt h ew e bt e x ti n f o r m a t i o ne x t r a c t i o n o nb a s i so fa n a l y z i n gt h ef e a t u r e sa n ds t r u c t u r eo fw e bp a g e ，i td e s i g n a n di m p l e m e n tan e wm e t h o do fv a l i di n f o r m a t i o ne x t r a c t i o n , w h i c h u s i n gd o m t r e ea n db a s e do ns t a t i s t i c s t h em e t h o dc a nf i l t e rh u b t y p e ， p i e t y p ea n df r a m e - t y p eo fp a g e se f f e c t i v e l ya n de l i m i n a t eh t m lt a g s ， a d s ，p i c t u r e sa n do t h e ri r r e l a t i v ei n f o r m a t i o nf r o mt h e m e t y p ep a g e st o r e s e r v ec o n t e n ta n dr e l a t i v ei n f o r m a t i o n t h i r d ，i ta n a l y z e st h et r a d i t i o n a lt f i d fa l g o r i t h ma n dp o i n t so u ti t s d e f i c i e n c y , an e wi m p r o v e da l g o r i t h mo nf e a t u r ew e i g h t i n gc a l c u l a t i n g w h i c hc o n s i d e r e do fd i s t r i b u t i o ni n f o r m a t i o n a m o n gc l a s sa n dt e x t s e m a n t i ci n f o r m a t i o ni sp r e s e n t e d e x p e r i m e n t a lr e s u l t ss h o wt h a tt h e i m p r o v e da l g o r i t h mo u t p e r f o r m e d t h et r a d i t i o n a lm e t h o d si n c l a s s i f i c a t i o np r e c i s i o n a n dl a s t ，b a s e do nt h er e s e a r c h e so fh e r e i n b e f o r e ，i t sd e s i g n sa n d i m p l e m e n t st h ep r o t o t y p eo fc h i n e s ew e b t e x tm i n i n gs y s t e m k e yw o r d s ：w e bt e x tm i n i n g ，i n f o r m a t i o ne x t r a c t i o n ，v e c t o rs p a c e m o d e l ，t e r mw e i g h t i n g ，p lu g i n 目录 摘要1 a b s t r a c t h 第一章绪论1 1 1 课题研究背景及意义1 1 2 困内外研究现状2 1 3 研究内容和论文结构3 1 3 1 研究内容3 1 3 2 论文结构4 第二章w 曲文本挖掘综述5 2 1w e b 文本挖掘概述一5 2 1 1w e b 文本挖掘的定义一5 2 1 2w e b 文本挖掘的任务5 2 1 3w e b 文本挖掘的- 般过程一7 2 1 4 中文w e b 文本挖铩 的主要步骤7 2 2 数据顾处理技术8 2 2 1 中文w e b 文档采集8 2 2 2w e b 文本信息提取8 2 2 3w e b 文奉的特征表示8 2 2 4 中文分词1 0 2 2 5 特征顺取值1 1 2 2 6 特，征降维1l 2 3w e b 文本分类1 3 2 4w e b 文本聚类1 4 2 5 本章小结1 5 第三章w e b 文本信息提取1 6 3 1 网页文本信息抽取技术1 6 3 2 网页的基本结构、特点和表示1 7 3 3 预处理一1 9 3 3 1 过滤文档集中与主题无关的页面1 9 3 3 2 初步过滤网页中与主题无关的信息1 9 3 4 网页自效文本信息提取2 0 3 4 ，l 相关概念和定义2 1 3 4 2 网页有效文奉信息提取2 3 3 4 3 抽取结果2 7 3 5 小结2 8 第四章特征权重；| 算 4 1 常用的权重计算方法 4 2t f i d f 算法分析 9 9 0 2 2 3 4 3 熵与信息熵3 2 4 3 1 信息熵的基本概念3 2 4 3 2 信息熵的 三要性质3 2 4 4t f i d f 算法改进3 3 4 4 1 基于特征项的类分靠信息改进3 3 4 4 2 基十文本语义的改进3 4 4 5 实验结果与分析3 5 4 5 1 | l 练集与测试集3 5 4 5 2 实验过程及数据分析3 5 4 6 小结3 7 第五章中文w e b 文奉挖掘系统原型c w t m s 的构建与实现3 8 5 1 系统的总体设； o j 分析3 8 5 1 1 系统功能概述和结构框架3 8 5 1 2 系统具体设汁4 0 5 1 3 系统使用的开发环境和语言4 1 5 2 插件技术及其住c w t m s 中的应用4 l 5 2 1 插件技术4 1 5 2 2 插件技术在原型系统中的应用4 2 5 3 系统的总体实现4 3 5 3 1 数据采集模块4 4 5 3 2 文档内容提取模块4 4 5 3 3 词条抽取模块4 4 5 3 4 特征选择模块4 7 5 3 5 义本表示模块4 8 5 3 6 自动分类模块5 0 5 4 小结一5 1 第人萼总结与展望5 2 6 1 本文丁作总结5 2 6 23 - 作展望一5 2 参考义献5 4 致谢5 9 攻读学位期间主要的研究成果6 0 硕上学位论文 第一章绪论 1 1 课题研究背景及意义 第一章绪论 w e b 迅猛发展的同时，我们不能忽视“信息爆炸”的n 寸题，即信息极人丰富 而知识相对匮乏。据估计，w 曲已经发展成为拥有3 亿页面的分布式信息空间， 而且这个数字仍以每4 至6 个月的速度增加。在这些人孱、晃质的w e b 信息资源 中，蕴含着具有巨大潜在价值的知识。因此，i n t e r n e t 已经成为了世界性的图书 馆，变成了各行舞、i p 人们交流思想、获取信息的平台。但是面对w e b 如此丰富 的内容，海量的数据，万维网动态丌放的特点，人们想耍找到自己需要的数据犹 如人海捞针一般。因此迫切需要能够从w e b ：快速、有效地发现资源和知识的工 具。w e bl - _ 的搜索引擎部分地解决了资源发现问题，但由于精确度不高等原冈， 其效果远不能使人满意。而搜索引擎的目的在于发现w e b 土：的资源，就w e b 卜的 知识发现而言，即使枪索精度再高，搜索引擎也不能够胜任。为此，我们需要丌 发比信息检索层次更高的新技术。 为了从大量数据的集合中发现有效、新颖、有用、可理解的模式，数据库领 域采用了数据挖掘( d a t am i n i n g ) 技术。但是，数据挖掘的绝人部分工作所涉及 的是结构化数据库，很少有处理w e b 1 - 的异质、非结构化信息的工作。那么为了 解决w e bj ：知识发现的问题，将传统的数据挖掘技术和w e b 结合起来进行w e b 挖掘可以说是一个很好的途径，w e b 挖掘作为一个具有挑战性的新课题被提了出 来。 当前研究的w e b 挖掘般分为三大类：1 ) w e b 内容挖掘，它指从网页内容出 发，从中获取潜在的、有价值的知淡，以实现w e b 资源的高效率自动检索，提高 资源的利用率，通常可以分为w e b 文本挖掘和w e b 多媒体挖掘。2 ) w e b 结构挖掘， 它是指从w w w 组织结构及其链接关系中获取数据的过程。3 ) w e b 使用挖掘，它通 过从w e b 的访问信息的挖掘获取信息，分析用户和w e b 网页之间的交互结果，包 括w e b 日志、点击次数以及一组棚关嘲贞问的数据交换等。 有研究发现，在海量的w e b 信息资源中，有8 0 以上的信息足以文奉的形 式存在的，因此隶属于w e b 内容挖掘的w e b 文本挖掘显得允为重要1 2 l l3 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 w w 资源很钉帮助，可以使用户比较准确找到 需要的资料，节约检索时间，提高w e b 文档的利用价值等。利用w e b 文本挖掘可 以对搜索引擎的检索结果进行更合理的组织，按照主题将页丽分为若干类别，这 样用户可以选择浏览他所关心的类别；利用w e b 文本挖掘可以事先把近似程度高 的文本分在同一个类中，每个类都形成一个中心，检索的时候只需要和这些类中 心比较就可以了，这样会大大加速整个枪索过程。w e b 文本挖掘可以对w e b 上大 量文档集合的内容进行总结、分类、聚类、关联分析，以及利用w e b 文档进彳趋 势预测等1 4 l f 5 1 。由此可见对w e b 文本信息的挖掘是很有意义和价值的。 本文对中文w e b 文本挖掘的若干关键技术进行了研究，并构建和实现了一 个中文w 曲文本挖掘系统的原犁。 1 2 国内外研究现状 国外对于文本挖掘的研究开展比较旱，早先的信息抽取技术就足文本挖掘的 雏形。他们在文本挖掘中的文本分类技术、关键词的自动获取和半结构化信息提 取等相关的信息抽取领域进行了较为深入的研究，并取得了不少令人瞩日的研究 成果1 5 j 【6 j 1 7 1 。 国外学眷普遍认为文本挖掘的一般框架包括两个模块：一个是文本提炼，就 是把任意格式的文本转换为可以用来机器学习的内容格式：另一个是所谓的知识 蒸馏，就是从这种内容格式巾推导融模式或者知识。 近年来，国外的文本挖掘的研究进展比较快，已经有了比较成熟的文本挖掘 应用软件且已经在商、l k 领域得到了很好的应用。t b m 公司推潲的t n t e n g e n t m i n e rf o rt e x t1 8 1 ，该t 具提供了高效的文奉信息挖掘功能，可以实现全文搜索、 文本分析、w e b 文档查询和检索等；美围m e g a p u t e r 公司开发的t e x t a n a l y s t 、 t e x t r a c t o r 等f 9 1 ，可以为用广提供文本总结、分类、聚类、信息抽取等各种功能； 微软公司的数据库系统中不仅集成了数据挖掘功能，而且它的最近两个版本s q l s e r v e r 2 0 0 5 和s q ls e r v e r 2 0 0 8 i l o i 中还提供文本挖掘组件，文本挖掘( 也称为文 本分类) 涉及到识别、i p 务与文本数据( 单词和短语) 之问的关系，它允许在文本数 据中搜索关键字词，并且基r 此自动识别“感兴趣的文本，这能够进一步推动 “关闭循环”操作的实旌，从而实现、l t 务目标，如提高客户满意度及提高产品和 服务的质鼍。 相对于国外，国内对文本挖掘的研究起步比较晚，在2 0 世纪9 0 年代中后期， 国内的研究有了快速的发展，并取得了一定的成就。 2 硕上学位论文 第一章绪论 国内对文本挖掘技术的研究主要集巾在高等院校、科研院所和信息公司等机 构。如四川联合大学的徐代刚、唐常杰等在机译系统的支持下，结合数据挖掘和 文本分析技术，研究了从w e b 文本中挖掘语青知识的基本方法，提 了一个文本 挖掘系统的基本框架1 1 1 l 。南京大学的黄豫清，戚广志，张福炎等对w e b 文本的信 息抽取进行了研究，提出，对象交换模型( o b j e c te x c h a n g em o d e l ，简称o e m ) h 2 i ， 用以建立w e b 信息模型。其中的半结构化信息的抽取算法，可以抽取结构化和半 结构化的信息，比现有的抽取方法通用性更强。中圜科学院 | - 算技本研究所的宫 秀军、史忠植等，提出了基于b a y e s 潜在语义模犁的半监督w e b 挖掘算法l l 引。该 算法分为两个阶段：第一阶段利用贝叶斯潜在语义模型来标注禽白潜在类别主题 词变骨的网页的类别，第_ 阶段利用简肇贝叶斯模犁，在第一阶段类别标注的荩 础卜，通过酬( e x p e c t a t i o l lm a x ir a iz a t i o l 3 ) 算法对不禽有潜在类别主题词变量 的文本作类别标注。该算法具有很高的精度和召同率。哈尔滨工程人学的张健沛、 刘洋、杨静等提出了一种新的基子p a x 树的搜索引擎结果聚类算法l l4 1 。该算法 把p a t 树数据结构和s t c ( s u f f i xt r e ec l u s t e r i n g ) 算法结合起来用丁中文文本聚 类，它使用p a t 树数据结构克服s t c 算法处理中文信息的不足，使用s t c 框架 来保证聚类能有效地执行。总的来说，对于文本挖掘技术的研究主要集中在以下 几个方面：文本的特征表示方法；中文分词算法；文本分类算法；文本聚类算法； 特征选择算法；文奉挖掘系统的研究与实现l l ，1 1 1 6 l i l 7 i 等。 国内对于中文文本挖掘取得了最初成果，如中科院计算机语言信息工程研究 中心研究的内容是汉语分词、自然语言接n 、句法分析、语义分析、音字转换、 自动分词：清华大学电子t 程系的丁晓青、吴偌寿研究的内容是手写汉字识别( 动 态匹配) 、汉字识别多分类器集成( 综合识别法) 、名片自动录入系统的实现等i l 引。 北京拓尔思信息技术有限公司( 简称 i t s 公司) 有效结合臼然语言处理技术、 统计分析和机器学习技术以及语言知识库，推出了国内外第。一个实用化的中文文 本挖掘软件产品_ t r s 文本挖掘软件。 这些研究工作在一定程度上促进了文本挖掘的发展，然而，国内目前在文本 挖掘的研究特别是文奉挖掘软件的商q k 化麻用方面仍明显落后于困外。冈此，迫 切需要提高国内的文本挖掘的研究水平，丌发j i j 更多的文本挖掘软件并投入到商 、i k 应用当中去。 1 3 研究内容和论文结构 1 3 1 研究内容 本论文主要研究以卜- 内容； 1 研究如何时采集到的中文w e b 文本进行有效信息提取，酋先对现自的几 3 硕上学位论文 第一章绪论 种网页文本信息抽取技术进行分析，然后根据丽页的基本结构、特点和表示，设 计并实现了一种基于统计的网页正义内容和孝h 关链接提取方法。 2 研究分析传统的常用的特征权重算法( t f i d f ) ，从理论和实例两方面说明 其不足之处，然后根据其不足进行相应的改进。 3 在对战两项进行研究的基础卜，构建并实现了一个中文w e b 文本挖掘系 统的原犁。 1 3 2 论文结构 本论文共分六章进行论述： 第一章绪论，主要介绍课题研究背景，w e b 文本挖掘技术的嗣内外研究状 况以及本课题的主要研究内容。 第一二章w e b 文本挖掘综述，概述w e b 文本挖掘的定义、任务、一般处理流 程和中文w e b 文奉挖掘的步骤。详细介绍数掘预处理技术，并简要介绍了文奉 分类和文本聚类技术。 第三章w e b 文本信息提取，首先简单介绍了网页文本信息抽取技术和网页 的基本结构、特点及表示；然后详细介绍了w e b 文本信息提取的瓶个步骤：预 处理和有效文本信息提取，重点研究了网页正文内容和相天链接的获取。 第四章特征权重； 算，首先简单介绍了常用的权重计算方法，然后对 t f i d f 算法进行理论和实例分析并指出其不足之处，提出改进算法，最后给出 实验结果并对之进行分析。 第五章中文w e b 文本挖掘系统原犁c w t m s 的构建与实现，首先介绍了系 统的总体设计与分析，接黄介绍捅件技术及其在c w t m s 中的心用，最后详细 介绍了系统各子模块的具体实现。 第六章总结和展望，对本文所进行的研究工作进行总结，并对下一步的工 作进行了展望。 4 硕上学位沦文 第二奇w e b 文本挖掘综述 第二章w e b 文本挖掘综述 i n t e m e t 上人多数信息的表现形式为文本，如何在浩瀚的文本信息中挖掘到 满在的知识成为当前研究的热点，w e b 文本挖掘就是解决这问题的方法。w e b 文本挖掘的关键技术包括数据预处理、w e b 文本分类、w e b 文本聚类等。 2 1w e b 文本挖掘概述 数据挖掘技术只能处理结构化数据，不能直接麻朋于 南文本和警结构化的 h t m l 文本，但是w e b 文本大部分是自由文本和半结构化的h t m l 文本，此时， w e b 文本挖搦技术肫运而生。 2 1 1w e b 文本挖撬的定义 w e b 文本挖掘是以w e b 文档为对缘的一种数据挖掘技术，是一门交叉性学 科，它涉及到i 算机语言学、f 1 然语言处理、数据抽取、信息检索、人工智能、 神经网络、统计学、机器学习、数据挖掘等多个领域。 w e b 文本挖掘是指借鉴数据挖掘的基本思想和理论方法，从大量1 f 结构化、 异构的w e b 文档的集合d 中发现有效的、新颖的、潜在可用的及最终可理解的 知i ：只k ( 包括概念( c o n c e p t s ) 、模式( p a t t e r n ) 、规l 贝a j ( r u l e s ) 、规律( r e g u l a r i t i e s ) 、约 束( c o n s t r a i n s ) 、及可视化( s u a l i z a t i o n s ) 等形式) 的非平凡过程1 1 9 i 。如果将d 看作 输入，将k 看作输出的话，那么w e b 文本挖掘的过程就是从输入到输 的一个 映射毛：d k 。 这个橘述性的定义是借鉴了数据挖掘的定义丽给出的，在这晕我们将解释几 个概念：过程通常是指多阶段的个过程，涉及数据预处理、学习与知识模式的 生成、模型质星的评价以及反复的修改求精；该过程要求是 e 平凡的，意思是要 有一定程度的智能化，自主性( 仅仅给 l j 所有数据的总和不能算作是一个发现过 程) 。而以卜所提及的有效性、新颖性、潜在有用性和最终可理解性综合在一起 可称为兴趣。l 生( i n t e r e s t i n g n e s s ) 。 2 1 2w e b 文本挖掘的任务 根据挖掘的知识类型4 = 同，可以将w e b 文本挖掘任务分为：文本总结、文本 分类、文本聚类、关联分析和趋势预测等。 硕上学位论文 第二审w r e b 文本挖掘综述 文本总结足指从文档巾抽取关键信息，用简洁的形式对文档内容进行摘要或 解释，这样，用户不需要浏览全文就可以了解文档或文档集合的总体内容。文本 总结在有些场合十分有用，例如，搜索引擎在向用户返回查诲结果时，通常需要 给出文档的摘要。目前，绝大部分搜索引擎采用的方法是简单地截取文档的前几 行。p i r o l “等人提出了使用中心文档来代表文档集合，使用中心词汇来表示文 档的方法，并给出了求取中心文档和中心词汇的算法。在国内，已经实现了中文 自动文摘系统。利用自动文摘系统，自动为中文w e b 文本生成摘要，方便用户查 看自己所需要的文本，而不用将时间浪费在不满足自己需要的文本上。 文本分类是指按照预先定义的主题类别，为文档集合中的每个文档确定一个 类别。这样，用户不但能够方便地浏览文档，而且可以通过限制搜索范l 嗣来使文 档的查找更为容易。f t 前，y a h o o ! 通过人工来对w e b ：的文档进行分类，这人大 影响了索引的页而数目。利用文奉分类技术可以对人量文档进行快速、有效地自 动分类。目前，文本分类的算法自很多种，比较常用的有k n n 和n a i v eb a y e s 等方法。 文本聚类与分类的不同之处在于，聚类没自预先定义好的主题类别，它的目 标是将文档集合分成若干个簇，要求同一簇内文档内容的相似度尽可能地大，而 不同簇问的相似度尽可能地小。h e a r s t 等人的研究已经汪明了“聚类假设”， 即与用户杏淘相关的文档通常会聚类得比较靠近，而远离与用户奁淘不相关的文 档。冈此，我们可以利用文本聚类技术将搜索引擎的检索结果划分为若干个簇， 用广只需要考虑那些相- 火的簇，大大缩小了所需要浏览的结果数景。目前，有多 种文本聚类算法，大致可以分为两种类型：以g h a c 等算法为代表的层次凝聚法， 以k - m e a n s 等算法为代表的平面划分法有的方法则是将g 一 l a c 和k - m e a n s 集合 起来，具代表性的就是b u c k s h o t 方法和f r a c t o n a t i o n 方法。 关联分析是指从文档集合中找出不同词语之问的关联关系，即不同的几个词 语出现在同一篇文梢中的概率研究。b r i n 提出了一种从人量文档中发现一时词 语i “现模式的算法，并用来在w e b 一卜寻找作者和书名的出现模式，从而发现了数 千本在a m a z o n 网站卜找不到的新书籍。w a n g 等人以w e b ：的电影介绍作为测试 文档，通过使用o e m 模犁从这些半结构化的页面中抽取词语项，进而得到一些火 于电影名称、导演、演员、编剧的出现模式。 分布分析与趋势预测是指通过对w e b 文档的分析，得到特定数据在某个历史 时刻的情况或将来的取值趋势。f o d m a n 等人使用多种分布模型对路透社的两万 多篇新闻进行了挖掘，得到主题、国家、组织、人、股票交易之间的相对分布， 揭示了一些有趣的趋势。w t l t h r i c h 等人通过分析w e b t 出版的权威性经济文章， 对每天的股票市场指数进行预测，取得了良好的效果。 6 硕上学位沦文第二章w e b 文本挖掘综述 2 1 3w e b 文本挖掘的一般过程 基于w e b 的文本挖掘的一般处理过程可用图2 - i 来表示。 图2 - 1w c b 文夯挖掘的一般过程 1 特征的建寺：与数据库中的结构化数据相比，w e b 文档具有有限的结构， 或荇根本就没有结构。因此，需要对文本进行预处理，抽取粥代表其特征的元数 据，这些特征可以以结构化的形式保存，作为文档的中间表示形式。 2 特征黛的缩减：当将文梢转化为能反映文档氏容的文档特征向量后，该 文档特征向量的维数非常大，所以必须对特征集进行降维处理。 3 学习与知激模式的提取：在完成特征向量降维后，就可以利埔挖掘算法 ( 分类、聚类等) 获取面向特定应用目的的知识模式。 4 知识质量评价和输 最终知洪模式：在获得知识模式后，对挖掘的模式 进行分析评价，通过可视化、图形图像处理等技术显示符合一定标准的挖掘结果， 便于用户理解和应用。 2 1 4 中文w e b 文本挖掘的主要步骤 中文w e b 文本的整体挖掘过程跟上述w e b 文本挖掘的一般过程类似，但是在 一些具体处理步骤l ：要稍微复杂一些。例如，当在对中文文本进行特辑表示时， 若采用词作为特征项，则必须首先解决文奉分词问题。因为中文文本与英语等欧 美语系的文本不同，句子中各个词语之间没白明显的分隔符，汉语词汇也没有形 态变化，缺乏自然的分隔信息，所以对于中文文本的分词处理就成为中文文本挖 掘一个必不可少的步骤。 根据w e b 文本挖掘的一般过程，结合中文文本的特点，归纳中文w e b 文本挖 掘的主要步骤如下： 1 中文w e b 文档采集 2 w e b 文本信息提取( 获取对挖掘任务有效的中文文本信息) 3 中文文本自动分词 4 文本表示和特征降维 5 学习和知识提取( 主要通过分类聚类等方法) 6 知识质量评价j f jj 输粥最终知识模式 7 硕上学位论文 第二事w e b 文本挖掘综述 2 2 数据预处理技术 与数据库中的结构化数据相比，w e b 文本具有有限的结构，或行根本没有结 构。此外，w e b 文本的内容是人类所使用的自然语言，计算机很难处理其语义。 冈此，需要对w e b 文本进行预处理，抽取代表其特征的元数据，这些特征可以 用结构化的形式保存，作为文档的中间表示形式。在进行数据预处理后，就可以 进行学习和知识提取( 也就是采用聚类分类歧其他方法进行文本挖掘工作) ，最后 进行知识质量评价和输出最终知识模式。 在w e b 文本挖掘中，数据预处理过程有着至关重要的作用，得到的文本挖 掘结果的精度以及文本挖掘的效率都与文本预处理的结果密切相天，所以耍减少 需要处理的数据量以及提高挖掘对象对文本的表达能力，这个过程可能占据整个 系统的8 0 的工作晕。数据预处理技术包括中文w e b 文档采集、w e b 文本信息 提取、中文分词、文本特征表示、特征权值汁算、特征降维等。 2 2 1 中文w e b 文档采集 如果我们要实现w e b 文本挖掘，首先我们需要获取挖掘上作需要处理的数 据中文w e b 文本集，这个过程我们称之为w e b 文本采集。w e b 文本采集，主 要是指通过w 曲页面之问的链接关系，从w 曲上自动获取信息，并f j l 随着链接 不断向所需要的w e b 页面扩展的过程。一般是用w e b 文本抓取器来实现，人们 经常形象地将它比喻为网络蜘蛛1 2 0 i ( w e bs p i d e r 或r o b o t ) 。采集程序从一个网页 或多个网页出发，逐步遍历网 ：的文件。采集程序片先解析网页的h t m l 代码， 查找该页面内的超链接，然后通过递归或非递归的方法来不停的搜索本网页包含 的其他链接。网络蜘蛛这个技术已经：l f 常成熟了，因此本文不作详细的讨论。 2 2 2w e b 文本信息提取 w e b 文本信息提取足w e b 文本挖掘上作的一个必要前期处理过程，其目 的在于获取对挖掘任务有效的中文文本信息，w e b 文本分类或荷聚类等挖掘工 作是在此基础上进行的，具体的内容将在第i 章中进行详细介绍。 2 2 3w e b 文本的特征表示 文本的内容足人类所使用的自然语言，表达了丰富的信息，但是要把这些信 息编码为一种标准形式是： ：常困雉的。文本挖掘中的文本特征表示指的是以一定 的特征项来代表文档，在文本分类或者聚类时只需对这些特征项进行处理，从而 实现x , h f - 结构化的文本的处理，这是一个非结构化向结构化转化的处理步骤。文 8 硕上学位沦文 镐二章w e b 文本挖掘综述 本的特衍表碓：的模型常用的有：布尔逻辑模型( b ( ，0 l e a nm o d e l ) i 2 ，向量空间模型 ( v e c t o rs p a c em o d e l ，v s m ) 1 2 2 1 ，概率模型等。这些模型从不同的角度出发，使用 不f 司的方法处理特征加权、类别学习和相似计算等问题1 2 引，近年来应用较为广 泛且较好的特征表示方法是向量字问模型法。下而具体介绍向量窄间模型。 向量空间模型是由s a i t o n 等人提f 的关于文本表示的模型，使朋由词语构成 的向量表示文档信息，并成功地应用丁著名的s m a r t l 2 4 1 1 2 5 1 系统，因其简单及有 效性，在文本分类、自动标引、信息检索等许多领域得到了广泛的心用。 向犀空间模犁的荩本思想是将文本看作特征项的集合，并使用特征项的权 向量表示文本。这种表示法的一个关键假设，就是文章中特征项f 现的先后次 序是无关紧要的，每个特征项对应特征空间的一维，将文本的特征表示成欧氏 空间的一个向量，文档的内容被形式化为多维空问中的一个点。 向量空问模犁的概念： 1 文档( d o c u m e n t ) ：泛指一般的文献或文献中的片断( 段落、匈子组或勺子) ， 一般指一篇文章。 2 项( t e r m ) ：文本的内容被看作主要由一些特征项来表达，这些特征项 可以是字、词、句等语言单位。根据实验结果，普遍认为选取词作为特征项比 较好。当采用单淘来表示特征项时，文本就可以表示为d o c u m e m = d ( ，：，| ) ， 其中t 表示各个特征单词。换句话说，所有这些项构成了。个向量窄间，每个项 表示一个维度。 3 项的权重( t e r mw e i g h t ) ：在任何一个文本中，每个特征项都被赋予一 个权重w ，以表示这个特征项在该文本中的重要程度，权重都是以特钲项的频 率为基础进行计算的。 4 向量空间模型( v s m ) ：在舍弃了符个特征项之问的顺序信息之后，一 个文本就表示成一个向量，也就足特征项窄问中的一个点；而个文奉集就表 示成一个矩阵，如图2 2 所示。 d l d jd i i t iw l 。_ ( d i ) _ - _ ， l tw d d n ) 图2 - 2 向量空间模型下的文本表示 9 硕上学位论文第二章w e b 文本挖掘综述 5 文本特征向遥( f e a t u r ev e c t o r ) ；在向最空问模趟巾，每个文档都被视 为由一组正交词条矢量所组成的向量空问，每个义档d 都可映射为此空间中的 一个特 l f 向量。用d l 五，形。；r ：，彬：；，l ，形。) 来表示。其中l 为特征项阐条 形为特征词条的权重。可以将d 中m 现的所有单词作为t ，也可以用d 中的所 有短语作为f 。，从而提高内容表示的准确性。 该向量中的每一维的值表示了该词条_ 存此文奉中的比蘑，用以刻划该词条 在此文本内容中所起作用的重要程度。权值越人，表示该阋在文本中的份量越 大，即该词越能反映口的内容：权值越小，该词的份量越小，越不反映d f 的内 容。权值的取值范隔是【o ，l 】，这样文本信息的表示与匹配阎题就转化成为向量 空间的表示与匹配问题。 6 相似度：( s i m i l a r i t y ) ：对于所彳j 文档和用户日标都可映射到文本向量空 间中，从而将文档信息的疆配问题转化为向量窄间的向量匹配问题。n 维窄间中 点的距离用向量之问的余弦夹角来度最，也即表示了文奉、k 闻的相似程度。 相似度研究的是怎样衡量两个文档间的相似程度。最常用的标准是用它们 代表向量夹角的余弦，定义为： 跏( ) 2 赫 ( 2 1 ) v s m 模型通过将篇文奉表示为n 维的词条向最，能够有效地解决： f 结构 化文本数据的处理问题，大大提高文本处理的速度和效率。 2 2 4 中文分词 计算机没有类似人类的智能，人类阅读文章后可以产生自身对文章的理解， 而计算机却没有这样的能力。为了便于讨算机的处理，文本必须表示为；tg 机可 以识别的格式，目前文本挖掘的研究丰要采用向量空问模犁。在向量窄问模犁中， 文本被表示为一个高维向量，向量的每一维代表一个特征，通常是一个字或词， 而其取值则足相应的权值。与英文网页不同的是，中文网页使用汉字，词与词之 间没有问隔，不像英语单词之问存在空格符，所以需要对中文文本进行切词处理， 并且切词的准确与否将很大程度的影响挖掘的效果。那么我们首先要在文本中区 分冉每一个词或蕾是字，这样，分词是一个必要的步骤。 目前国内分词系统所采用的或者正在研究的中文分词方法基本上分为以下 几类： 1 机械式分词方法 机