（应用数学专业论文）基于web文本挖掘的研究.pdf

中文摘要 摘要 我们生活在一个信息化的时代，各种信息急剧膨胀，为了有效利用这些信息，数据 挖掘和知识发现技术应运而生，并显示出强大的生命力。本文对w e b 数据挖掘技术， 尤其是w e b 文本挖掘的关键技术特征词的抽取和聚类分析进行了较为系统地分析和研 究。 聚类分析在数据挖掘研究中占有重要的位置。所谓聚类，就是将物理或抽象对象的 集合划分成为由类似的对象组成的多个类的过程。聚类分析依据的原则是使同一类中的 对象具有尽可能大的相似性，而不同类中的对象相似性较小。 由于聚类分析的重要性和特殊性，近年来该领域的研究取得了长足的发展，涌现 出了许多聚类分析的方法，如基于划分( p a r t i t i o n b a s e d ) 的聚类方法、基于模型 ( m o d e l b a s e d ) 的聚类方法等等。 本文首先对we b 文本聚类中的数据表示方法、特征表示、分词技术、特征项的抽 取进行了系统的研究，随后对文本聚类算法进行了研究，主要是对典型的聚类算法( 如： km e a n s 、c u r e 、d b s c a n 、s o m 、f c m 等1 进行了详细的研究与比较，并提出了两 种改进算法：一个是对s o m 算法进行改进，另一个是基于s o m 和k m e a n s 的聚类组 合算法。 关键字：数据挖掘；聚类分析；文本挖掘；k - m e a n s ；s o m 英文摘要 a b s t r a c t w en o wh a v el i v e d i na l li n f o r m a t i o ns o c i e t y e a c hk i n do fi n f o r m a t i o ni n f l a t e s s u d d e n l y 1 1 把d a t am i n i n ga n dt h ek n o w l e d g ed i s c o v e r e da r i s e sa tt h eh i s t o r i cm o m e n t , a n d d i s p l a y st h ef o r m i d a b l ev i t a l i t y , w h i c hc a r lh e l pp e o p l eu s et h ei n f o r m a t i o ne f f e c t i v e l y t l l i s p a p e rs y s t e m a t i c a l l ys t u d i e sa n da n a l y s e st h em i n i n gt e c h n i q u e ，d o c u m e n tm i n i n ga n d c l u s t e r i n ga n a l y s i s c l u s t e r i n ga n a l y s i si sa l li m p o r t a n tp a r to ft h ed a t am i n i n gr e s e a r c h c l u s t e r i n gi st h e l 竹o c e s so fg r o u p i n gt h ep h y s i c a lo rt h ea b s t r a c to b j e c ts e ti n t oc l a s s e so rc l u s t e r s ，s ot h a tt h e o b j e c t sw i t h i nt h es a m ec l u s t e rh a v eh i g l ls i m i l a r i t yi nc o m p a r i s o nt oo n ea n o t h e r , b u tl o w s i m i l a r i t yi nd i f f e r e n tc l u s t e r s b e c a u s eo f t h ei m p o r t a n c ea n ds p e c i a l i z a t i o no f t h ec l u s t e ra n a l y s i si nd a t am a n a g e m e n t , t h er e s e a r c hi nt h i sf i e l dh a v eg o tag r e a ta d v a n c e m e n ti nr e c e n ty e a r s ，a n dan u m b e ro f c l u s t e r i n ga l g o r i t h m sh a v eb e e nf o u n d e d ，f o re x a m p l e ：p a r t i t i o n i n gm e t h o d s ；m o d e l m e t h o d s ， e t c a tf i r s t ，t h i sp a p e rr e s e a r c h e dd a t ae x p r e s s ，c h a r a c t e r i s t i ce x t r a c t i o na n dp a r t i c i p l e t e c h n o l o g yi nw e bt e x tc l u s t e r i n g t h e n , t h ep a p e rh a v eb e e ns t u d i e da b o u tt h et e x tc l u s t e r i n g a r i t h m e t i c ，m o s t l ya b o u tt h et y p i c a lc l u s t e r i n ga r i t h m e t i c ( f o re x a m p l ek - m e a n s 、c u r e 、 d b s c a n 、s o m 、f c m ) ，a tl a s t , t h ep a p e rg i v e st w oi m p r o v e da l g o r i t h m s ，o n ei sa l li m p r o v e d o f s o m ，t h eo t h e ri sah y b r i dc l u s t e r i n gm e t h o dt h a tc o m b i n e ss o ma n dk - m e a n sa l g o r i t h m k e yw o r d s ：d a t am i n i n g ；c l u s t e r i n ga n a l y s i s ；k - m e a n s ；s o m 原创性声明 本人郑重声明：所呈交的学位论文，是本人在指导教师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本论文 不包含其他个人或集体已经发表或撰写过的科研成果。对本文的研究 作出重要贡献的个人和集体，均已在文中以明确方式标明。本声明的 法律责任由本人承担。 论文作者签名： 殖浊i 蓬 日期： 纳：! ! 关于学位论文使用权的说明 本人完全了解中北大学有关保管、使用学位论文的规定，其中包 括：学校有权保管、并向有关部门送交学位论文的原件与复印件； 学校可以采用影印、缩印或其它复制手段复制并保存学位论文； 学校可允许学位论文被查阅或借阅；学校可以学术交流为目的，复 制赠送和交换学位论文；学校可以公布学位论文的全部或部分内容 ( 保密学位论文在解密后遵守此规定) 。 签 名：墨豳i 霞 日期： 导师签名：日期： 多一) f3 。 中北大学学位论文 第一章绪论 1 1 本文研究背景 2 0 世纪9 0 年代以来，随着i n t e m e t 和w e b 技术的飞速发展和普及，信息获取己经 从手工获取，到计算机获取，以及到现在的通过网络进行信息获取。要想在这浩如烟海 的网络世界中找到所需信息，传统的数据分析工具己不能满足要求，因为传统的数据分 析工具只能进行一些表层的处理( 如查询、插入、统计等) ，而不能获得数据之间的内在 关系和隐含的信息。人们被数据淹没，但对知识又非常贫乏，为了摆脱这种困境，人们 迫切需要一种能够发现数据库内部之间的、隐含的信息的工具，数据挖掘技术应运而生。 数据挖掘( d a t am i n i n g ：d m ) 是一门很广义的交叉学科，汇聚了数据库、人工智能、 机器学习、统计学、模式识别、可视化、并行计算和神经网络等不i 司学科和领域，近年 来受到各界的广泛关注。 聚类分析是数据挖掘研究领域中一个非常重要的研究课题。聚类与分类的根本不同 在于：分类问题中我们知道训练集的分类属性，而聚类问题则需要我们从数据集中找这 个分类属性。所谓聚类，就是对数据集中的数据应用某种方法进行分组，使得每组内部 的数据尽可能相似而不同组之间的数据尽可能不同，即“物以类聚”，从而发现数据集 内在的结构。 聚类可以帮助人们更快的找到所需要的信息，因此，聚类在现实生活中有着很重要 的意义。现在，聚类分析己成为一个非常活跃的研究课题。 1 2 研究意义 w e b 文本挖掘对我们充分利用w w w 资源很有帮助，可以使用户比较准确找到需 要的资料；可以帮助用户节约检索时间，可以提高w e b 文档的利用价值等。 l 、可以对搜索结果进行有效的组织 搜索引擎的搜索结果并不尽如人意，使用者输入一些关键词，一般都会得到成千上 万的检索结果，而且其中大部分页面都是不需要的无关资料。虽然有一些技巧试图给那 些有较多关键词或者罕见关键词的页面赋予更大的权重，却仍然不能保证和用户意图最 相关的页面一定被排在最前面。因此用户别无选择，只能把检索到的页面一个一个再筛 选一遍。利用w e b 文本挖掘可以试图更合理的组织搜索结果，按照页面彼此之间的相 中北大学学位论文 似程度分为若干组，每组都有一个比较明确的主题，用户可以迅速地扫描每一组并选择 那些和他的目标最相关的组。 2 、可以加快搜索时间 自然语言中词形和词义并不是一一对应的，有很多一词多义和多词一义的现象，这 种现象使得仅仅依靠关键词的比较不足以获得满意的检索结果。利用w e b 文本挖掘， 事前对原始文本进行聚类，在大规模文本集合中提取出隐含的概念，进而使用在概念空 间中的投影表示文本。把那些近似程度较高的文本分在同一个组内，每个组都形成一个 中心，检索时只需和这些类中心比较就可以了，这会大大加速整个搜索过程。 1 3 国内外研究的现状 数据挖掘，也可以称为数据库中的知识发现( k n o w l e d g ed i s c o v e rd a t a b a s ek d d ) 。 1 9 9 5 年在加拿大蒙特利尔市召开了第一届k d d 国际学术会议1 ，以后每年召开一次。 近年来，k d d 在研究和应用方面发展迅速，在电信、银行、商业等领域得到了广泛的 应用，s a s ，s p a s s 等很多软件都提供了数据挖掘的功能。 聚类分析作为数据挖掘中的一个重要研究热点，目前，国外己提出了很多种算法， 比如：k - m e a n s 算法 2 1 、b i r c h 算法 3 1 ，d b s c a n 算法 4 1 等。 国内对聚类算法的研究也取得了不少有意义的成果，如杨燕等对蚁群算法进行改 进，提出了一种多蚁群聚类组合算法m a c c a 5 】；马帅等提出一种基于参考点和密度的 快速聚类算法嗍；王建会等提出了一种实用高效的聚类算法【7 1 ；谢立宏等提出了一种无 距离函数聚类方法嘲等等。 1 4 本文研究的内容 本论文的主要研究工作包括几个方面： 第1 章为本文绪论部分。首先分析了本文的选题背景和研究意义，然后介绍了国内 外研究现状。 第2 章对数据挖掘的概念进行了系统的介绍。并对文本挖掘中的数据表示方法、特 征提取、权值计算进行了详细的总结。 第3 章是有关聚类的研究。对聚类分析的概念、产生和发展进行了简要的归纳和总 结，同时对主要聚类算法进行了详细的研究与比较，并提出了对s o m 算法进行改 进，提出了基于s o m 和k m e a n s 的聚类组合算法。 2 中北大学学位论文 第二章w e b 文本挖掘 2 1 w e b 挖掘 w e b 挖掘就是数据挖掘与w e b 技术相结合的一种技术，这里首先给出其详细的定 义和其分类。 2 1 1w e b 挖掘的定义 数据挖掘是一个交叉学科领域，是人工智能、机器学习与数据库技术相结合的产物， 受数据库系统、统计学、机器学习、可视化和信息科学等多个学科影响，它作为知识发 现过程的一个特定步骤，是对数据及数据间关系进行考察和建模的方法集，应用一序列 技术从大量数据中提取人们感兴趣的、隐含的、潜在有用的信息和知识，表示为概念 ( c o n c e p t s ) 、规女1 1 ( r u l e s ) 、规律( r e g u l a r i t i e s ) 、模式( p a t t e r n s ) 等形式。 w 曲挖掘是数据挖掘在w e b 上的应用，它也是一门综合性学科，涉及数据挖掘、 机器学习、模式识别、人工智能、统计学、自然语言处理、计算机网络技术、信息检索 等领域。 w e b 挖掘是指从大量非结构化、异构的w e b 信息资源( 包括w e b 页面内容、页面 之间的结构、用户访问信息、电子商务信息等) 中应用数据挖掘方法以帮助人们从w w w 中提取有效的、新颖的、潜在可用的及最终可理解的知识( 包括概念、模式、规则、规 律、约束及可视化等形式) 的非平凡过程。 这里需要提到的是，w 曲挖掘与传统的数据挖掘有许多相似之处，但相比之下也 有许多独特之处。首先，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 页面提取出我们需要的有用的知识，得到 关于群体用户访问行为和方式的普遍知识，用以改进w e b 服务方设计，还可以从用户 访问行为、频度、内容中提取用户的特征，为用户定制个性化的界面，从而展开有针对 性的电子商务活动等等。 2 1 2w e b 挖掘的构成和方法 w e b 挖掘可认为由四部分组成的，如图2 1 所示。 l 、信息检索o r ) 信息检索i r 或者叫资源发现就是自动检索相关文档，同时尽可能排除不相关文档。 i r 处理主要包括文档表示、索引化和查找文档。 蒜h 糍翥h 薹燃；选h 糍识1 1 。验勰释，冀 图2 1w 曲挖掘予任务 索引，一般来说，是用特征词集指针来协助查找文档。然而，对w e b 网页进行索 引以促进检索是很复杂和困难的事情。网页数量巨大，而且是动态的，经常更新，索引 几乎是不可能的。目前，有四类主要的索引方法应用比较广，人工或手工索引，自动索 引，智能或基于代理索引和基于元数据索引。 搜索引擎就是用来在，w e b 上查找和检索存储在数据库中的数据、h t m l 网页、 自由文本的程序。w e b 机器人如a l t av i s t a 和w e bc r a w l e r ，采用了比较流行的索引技术， 它们扫描数百万网页，并存储文档的索引词。一般搜索引擎都有上十个工作索引，每个 索引有一个数据库，存放w e b 上不同类型的信息。如m e t a c r a w l e r 提供统一的w e b 文档 检索界面，它并行提交查询到9 个索引器，然后汇集结果并进行剪枝处理。m e t a c m w l e r 不直接处理w e b 网页，而是处理搜寻器获得的索引。未来的资源发现系统将利用自动文 本分类技术把w e b 文档分类，建立自动w e b 路径，就象y a h o o 搜索其手工分类文档一 样。 2 、信息提取o e ) w e b 文档被检索出来，下一步就是如何在没有人太多干预的情况下自动提取知识和 其他有用信息。信息提取是对每个文档找到代表其核心语义内容的部分。到目前止，大 4 中北大学学位论文 多数砸方法都涉及编写“包装袋”( w r i t i n gw r a p p e r s ) ( 用手工编码) ，将文档映射成某种 数据模型。信息集成系统把许多站点翻译成知识资源，并从中提取信息。 一些智能w e b 代理，利用特定的资源特征( 如用户注册记录) 来组织和解释信息， 从不熟悉的资源中动态提取信息。卡内基梅隆大学研制的了一个从计算机学院老师主页 上提取研究课题、指导老师、邮箱和研究兴趣的i e 系统。 3 、概括( g e n e r a l i z a t i o n ) 和分析( a n a l y z e ) 由于w 曲是一个交互媒体，入在w e b 信息和知识发现过程中扮演十分重要角色， 特别在概括和分析数据挖掘结果阶段，更需要人的主观参与。一旦模式被挖掘出来，需 要用合适的工具进行分析，验证和解释挖掘出的模式，具体分析w e b 挖掘的知识特征。 2 1 3w e b 挖掘与数据挖掘、信息检索的关系 w r c b 挖掘是对数据挖掘的一种新的发展和应用，但又不同于传统的数据挖掘 嘲【1 0 1 “j 。其区别在于： 1 、w 曲挖掘的对象是海量、分布、动态、异质的w e b 文档，与传统的存储于数据 库中的结构化的数据不同； 2 、w e b 在逻辑上是一个由文档节点和超链接构成的图，因此w e b 挖掘所得到的模 式可能是关于w e b 内容的，也可能是关于w e b 结构的； 3 、w e b 数据具有半结构化或非结构化特征，使得这些信息数据难以清晰地用数据 模型加以表示，且缺乏机器可理解的语义，而数据挖掘的对象局限于数据库中的结构化 数据。因此有一部分数据挖掘技术并不适用于w e b 挖掘，即使可用也需要建立在对w 曲 文档进行预处理的基础上。因此w e b 挖掘需要用到更多的有别于传统数据挖掘的技术。 从原理上讲w e b 文本挖掘属于检索一类，但有别于信息检索。w e b 数据挖掘与 w 曲信息检索是两种不同的技术。其区别主要表现在以下几个方面： l 、方法论不同。信息检索是目标驱动的，用户需要明确提出查询要求；而挖掘是 随机的，其结果独立于用户的信息需求，也是用户无法预知的。 2 、目的不同。信息检索的目的在于帮助用户发现资源，即从大量文档中找到满足 其查询请求的文档子集；而挖掘是为了揭示文档中隐含的知识。 3 、着眼点不同。信息检索着重于文档中显式存储的字词和链接；而挖掘试图更多 地理解其内容和结构。 中北大学学位论文 4 、评价方法不同。信息检索使用精度( p r e c i s i o n ) 和召回率( r e c a l l ) 来评价其性能要 求返回尽可能多的相关文档，同时不相关的文档尽可能少。而挖掘采用收益( o a i n ) 、置 信度( c e r t a i n t y ) 、简洁性( s i m p l i c i t y ) 等来衡量所发现知识的有效性、可用性和可理解性。 5 、使用场合不同。有时信息检索系统返回太多的结果以致用户无法一一浏览，有 时用户没有明确的信息需求，有时用户希望发现文档集合中所具有的结构、趋势、含义， 在这些场合下，就需要使用挖掘技术。尽管w e b 挖掘是比信息检索层次更高的技术， 但它并非用于取代信息检索技术，二者相辅相成，各有所长，各有适用的场合。同时利 用w e b 挖掘的研究成果可提高信息检索的精度和效率，改善检索结果的组织，使信息 检索系统发展到一个新的水平。 2 1 4w 曲挖掘的数据环境 w e b 上有海量的数据信息，怎样对这些数据进行复杂的应用成了现今数据库技术的 研究熟点。数据挖掘就是从大量的数据中发现隐含的规律性的内容，解决数据的应用质 量问题。充分利用有用的数据，废弃虚伪无用的数据，是数据挖掘技术的最重要的应用。 相对于w e b 的数据而言，传统的数据库中的数据结构性很强，即其中的数据为完全结 构化的数据，而w e b 上的数据最大特点就是半结构化。所谓半结构化是相对于完全结 构化的传统数据库的数据而言。显然，面向w e b 的数据挖掘比面向单个数据仓库的数 据挖掘要复杂得多。 1 、异构数据库环境 从数据库研究的角度出发，w e b 网站上的信息也可以看作一个数据库，一个更大、 更复杂的数据库。w e b 上的每一个站点就是一个数据源，每个数据源都是异构的，因而 每一站点之间的信息和组织都不一样，这就构成了一个巨大的异构数据库环境。如果想 要利用这些数据进行数据挖掘，首先，必须要研究站点之间异构数据的集成问题，只有 将这些站点的数据都集成起来，提供给用户一个统一的视图，才有可能从巨大的数据资 源中获取所需的东西。其次，还要解决w e b 上的数据查询问题，因为如果所需的数据 不能很有效地得到，对这些数据进行分析、集成、处理就无从谈起。 2 、半结构化的数据结构 w e b 上的数据与传统的数据库中的数据不同，传统的数据库都有一定的数据模型， 可以根据模型来具体描述特定的数据。而w e b 上的数据非常复杂，没有特定的模型描 6 中北大学学位论文 述，每一站点的数据都各自独立设计，并且数据本身具有自述性和动态可变性。因而， w 曲上的数据具有一定的结构性，但因自述层次的存在，从而是一种非完全结构化的数 据，这也被称之为半结构化数据。半结构化是w e b 上数据的最大特点。 3 、解决半结构化的数据源问题 w e b 数据挖掘技术首要解决半结构化数据源模型和半结构化数据模型的查询与集 成问题。解决w e b 上的异构数据的集成与查询问题，就必须要有一个模型来清晰地描 述w e b 上的数据。针对w e b 上的数据半结构化的特点，寻找一个半结构化的数据模型 是解决问题的关键所在。除了要定义一个半结构化数据模型外，还需要一种半结构化模 型抽取技术，即自动地从现有数据中抽取半结构化模型的技术。面向w e b 的数据挖掘 必须以半结构化模型和半结构化数据模型抽取技术为前提。 2 1 5w e b 挖掘分类 w e b 挖掘是一个具有挑战性的课题，它实现对w e b 存取模式、w 曲结构和规则， 以及动态的w e b 内容的查找。一般地，w e b 挖掘可以简单的分为三类：w e b 内容挖掘( w e b c 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 h a n g ) 和w e b 使用记录的挖掘( w e bu s a g e m i n i n g ) 。如图2 2 图2 2w 曲挖掘分类图 l 、w 曲内容挖掘 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 页面的聚类是指在没有给定主题类别的情况下，将w e b 页 面集合聚合成若干个簇，并且同一簇的页面内容相似性尽可能大，而簇问相似度尽可能 7 中北大学学位论文 小 2 、w 曲结构挖掘 w e b 结构挖掘是挖掘w e b 内的超链接，它主要任务是揭示文档内容之外的蕴涵信 息。页面的指入链接越多，说明它越有权威：指出的链接越多，说明它的主题越丰富。 页面分级和聚焦爬行( f o c u s e dc r a w l i n g ) 都利用了该思想。识别权威w e b 网页和h u b 的方 法研究，产生了网页分级( p a g e - r a n k ) 和h i t s 算法。一些有效商业w e b 搜索引擎，比如 g o o g l e ，就使用h i t s 算法。通过分析w e b 链接和上下文信息，系统可以产生比基于关 键字索引搜索引擎如a l t av i s t a 和基于本体论生成主题路径的搜索引擎如y a h o o 。质量 更好的搜索结果。聚焦爬行( f o c u s e dc r a w l i n g ) 选择性发现预定义主题的相关w e b 页面， 它不是收集和索引所有可能访问的w e b 文档，而是分析爬行边界发现尽可能相关的链 接，避开不相关领域w e b 文档。 3 、w 曲使用记录挖掘 w e b 使用记录挖掘是指通过挖掘w e br 志记录，来发现用户访问w e b 页面的模式。 挖掘的对象是在服务器上的包括s e r v e rl o gd a t a 等同志。挖掘的手段是：路径分析、关 联规则和序列模式的发现、聚类和分类。w e b 访问信息挖掘可以从w e b 服务器那里自 动发现用户存取w e b 页面的模式，得出群体用户或单个用户的访问模式和兴趣。 2 2 w e b 文本挖掘 2 2 1w 曲文本挖掘定义 文本挖掘是以计算语言学、统计数理分析为理论基础，结合机器学习和信息检索 技术，从文本数据中发现和提取独立于用户信息需求的文档集中的隐含知识。 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 曲文本。其次，w e b 在逻辑上是一个由文档集合超链接构成的图，因此，w e b 文本挖掘所得到的模式可能是关于w 曲内容的，也可能是关于w e b 结构的。由于w e b 8 中北大学学位论文 文本是一个半结构化或无结构化的，且缺乏机器所能理解的语义，从而使有些数据挖掘 技术并不适用于w e b 挖掘。因而，开发新的w e b 文本挖掘技术以及对w e b 文本进行预 处理，以提取该文本的特征，便成为w e b 文本挖掘研究的重点。 2 2 2w e b 文本挖掘主要研究内容 以w e b 文本文档为对象的文本挖掘被称为是w 曲文本挖掘。w e b 文本挖掘属于w 曲 内容挖掘的范畴，可以对w e b 上大量文档集合的内容进行文本检索、概括、分类、聚 类、关联分析、趋势预测和网络导航等。 l 、文本检索主要研究对整个文档文本信息的表示、存诸、组织和访闯，即根据用 户的检索要求，从数据库中检索出相关的信息资料。这种检索方法有三种：布尔模型是 简单常用的严格匹配模型，如清华大学的中国学术期刊( 光盘版) ；概率模型利用词条 间和词条与文档间的概率相关性进行信息检索，如美国马萨诸塞大学开发的i n q r e r y 。 文本检索系统；向量空间模型在于将文档信息的匹配问题转化为向量空间中的矢量匹配 问题处理，如美国康乃尔大学基于向量空间模型开发了s m a r t 文本检索系统。 2 、文本概括是指从w e b 文档中抽取主要的信息，从而形成关于文本内容的简洁摘 要，这属于自动摘要的技术。例如，搜索引擎在向用户返回查询结果时，通常需要给出 文档的摘要，使用户在浏览全文之前可以快速了解文档的主要内容。目前，绝大部分搜 索引擎采用的方法是截取文档中出现检索词频次最高的几行或者几句话作为摘要，并不 考虑检索词位置和匹配长度问题，因此摘要的效果很差。 3 、文本分类是w e b 文本挖掘的一项重要技术，是指将w e b 文档集合中每个文档归 入个预先定义的类别之中。这样，用户在浏览w e b 文档时，就不会因为纵横交错的 超链接两“迷路”，而是基于一种主题分类的指导。目前，y a h o o 通过人工来对w e b 上的 文档进行分类，这大大影响了索引的页面数目，不能适应于w e b 上文档高速膨胀的需 要。近年来涌现出了大量的适合于不同应用的分类算法，如：基于归纳学习的决策树( d l t ， d e c i s i o nt r e e ) f 埘、基于向量空间模型的k 最近邻( k n n ，kn e a 佗s tn e i g h b o r ) 、基于概率 模型的b a y e s 分类器f 1 4 】【1 6 j 【1 7 】、神经网络q n ，n e u r a ln e t w o r k ) t l s l 、基于统计学习理论的支 持向量机( s v m ，s u p p o r t v e c t o r m a c h i n e ) 方法) 1 1 4 】【1 9 】【捌等。 4 、文本聚类与分类的不同之处在于，聚类没有预先定义好的主题类别，它的目标 是将文档集合分成若干个簇，要求同一簇内文档内容的相似度尽可能地大，而不同簇间 9 中北大学学位论文 的相似度尽可能地小。h e a r s t 【z 1 1 等人的研究已经证明了“聚类假设”，即与用户查询相关 的文档通常会聚类得比较靠近，而远离与用户查询不相关的文档。 5 、关联分析最早被应用于“货篮子”的研究，这里是指文档之间以及文档集合中不 同词语之间的关联关系，即不同的几个词语出现在同一篇文档中的概率研究。例如， b r i n 2 1 】提出了一种从大量文档中发现一对词语出现模式的算法，并用来在w e b 上寻找作 者和书名的出现模式，从而发现了数千本在a m a z o n 网站上找不到的新书籍。 6 、趋势预测( 也称为分布分析) 是指通过对w e b 文档的分析，得到特定数据在某个 历史时刻的情况或将来的取值趋势。f e l d m a n l 2 2 1 等人使用多种分布模型对路透社的几万 多篇新闻进行了挖掘，得到主题、国家、组织、人、股票交易之间的相对分布，揭示了 一些有趣的趋势。还可以通过分析w e b 上出版的权威性经济文章，对每天的股票市场 指数进行预测，取得了良好的效果。 7 、网络导航：文本挖掘技术可以通过分析用户的网络行为等，帮助用户更好地寻 找有用信息，一个典型的例子是c m u 的w e bw a t c h e r l 2 3 1 。这是一个在线用户向导，可 以根据用户的实际点击行为分析用户的兴趣，预测用户将要选择的链接，从而为用户进 行导航。 2 3 文本特征表示 与数据库中的结构化数据相比。w e b 文档具有有限的结构，或者根本就没有结构。 即使具有一些结构，也是着重于格式，而非文档内容。不同类型文档的结构也不一致。 此外，文档的内容是人类所使用的自然语言，计算机很难处理其语义。文本信息源的这 些特殊性使得现有的知识挖掘技术无法直接应用于其上。我们需要对文本进行预处理， 抽取代表其特征的元数据。这些特征可以用结构化的形式保存，作为文档的中间表示形 式。 文本特征指的是关于文本的元数据，分为描述性特征，例如文本的名称、日期、大 小、类型等：以及语义性特征。例如文本的作者、机构、标题、内容等。描述性特征易 于获得，而语义性特征则较难得到。w 3 c 制定的x m l 。r d f 等规范提供了对w e b 文档 资源进行描述的语言和框架。在此基础上，我们可以从半结构化的w e b 文档中抽取作 者、机构等特征。 对于内容这个难以表示的特征，我们首先要找到一种能够被计算机所处理的表示方 l o 中北大学学位论文 法。由s a r o n 提出的向量空间模型f 2 4 】【2 5 l ( v s m ，v e c t o rs p a c em o d e l ) 是近年来应用较多且 效果较好的方法之一。 向量空间模型( v s m ) 是6 0 年代末由g e r a r ds a k o n 等人提出的。该模型是关于文档 表示的一个统计模型，该模型以特征项作为文档表示的基本单位。其中，最为著名的应 用该模型的检索系统是s m a r t 系统。在空间向量模型中，文档的内容被形式化为多维空 间中的一个点，通过向量的形式给出。正是因为把文档以向量的形式定义到实数域中， 极大地提高了自然语言文档的可计算性和可操作性。可以看出向量空间模型文档表示的 形式化方法是文档处理的各种应用得以形式化的基础和前提。 定义1 文档( d o c u m e n t ) 泛指一般的文献或文献中的片段( 段落、句子组或句子) ，一般指一篇文章。 定义2 项( t e r m ) 当文档的内容被简单地看成是它含有的基本语言单位( 字、词、词组、或短语等) 所组成的集合时，这些基本的语言单位统称为项，即文档可以用项集( t e r ml i s t ) 表示为 d ( l ，l ，乙) ，其中瓦是项，1 后玎。 定义3 项的权重( t e r mw e i g h t ) 对于含有n 个项的文档d ( i ，t 2 ，0 ) ，项瓦常常被赋予一定的权重。，表 示它们在文档中的重要程度，即d ( t i ，w 。；t 2 ，矽2 ；，l ，w ) ，简记为 d = d ( ，w 2 ，形。) 。 定义4 向量空间模型侧( v s m ) 给定一个文档d ( 正，矽；2 ，矽：；，l ，形。) ，由于瓦在文档中既可以重复出现又 应该有先后次序的关系，分析起来仍有一定的难度。为了简化分析，可以暂不考虑瓦在 文档中的先后顺序并要求瓦互异( 即没有重复) 。这时可以把兀，r ：，l 看成一个疗维 的坐标系，而矽，：，。为相应的坐标值，因而d ( 矽。，矿：，) 被看成是疗维空 间中一个向量，我们称d ( 矿。，矿：，矿。) 为文档d 。 定义5 文本特征向量( f e a t u r ev e c t o r ) 中北大学学位论文 在v s m 模型中，每一个文档都可以用一个向量来表示。向量的元素是由项( 词条) 及其权重组成。该向量我们称之为此文本的特征向量。特征向量是文档的一个特征表示， 在某种意义上可以完全代表文档的特性。 规范化特征向量( s t a n d a r d i z e df e a t u r ev e c t o r ) ：遵循规范化准则，经过规范化处理的 特征向量，即为规范化特征向量。 规范化准则：对特征向量有必要进行规范化处理，使其具有相同的长度。设特征 向量v e c t o r 1 , 1 ，屹，h ， ，对v e c t o r 中的每个 y ，一争 其中v = 定义6 相似度( s i i i l i l a r i 助 两个文档d l 和d 2 之间的( 内容) 相关程度( ( d e g r e eo fr e l e v a n c e ) 常常用它们之问的 相似度s i m ( d , ，d 2 ) 来度量。当文档表示为v s m ，我们可以借助于向量之间的某种距离 来表示文档间的相似度。设向量d l 和d 2 ，且d = ( 矽，矿。：，形，。) ， d ：= ( 矿：。，形：，：。) 目前常用的相似度计算公式有： 1 、向量之间的内积： si m ( d 1 ，d 2 ) = 矿l i 矿2 i ( 2 1 ) t = l 2 、夹角的余弦： 矽。矽：。 s i m ( d l ，d 2 ) = c o s 0 = 酉硒 ( 2 2 ) 其中矿。，矿：i 为向量d l ，d 2 中的元素。 在v s m 模型中，空间文档被看作是由一组正交词条所组成的矢量空间，每个文档 d 表示为其中的 一 个规范化特征矢量 矿( d ) = ( f l ，w l ( d ) ；t ，w ，( d ) ；t 。，w 。( d ) ) ，其中f ，为词条项，w 。( d ) 2 中北大学学位论文 为f i 在d 中的权值。可以将d 中出现的所有单词作为rf ，也可以要求tf 是d 中出 现的所有短语，从而提高内容特征表示的准确性。m ( d ) 一般被定义为tj 在d 中出 现频率斫( d 的函数，即w ，( d ) ：霍( 矾( d ) ) 。常用的皿有：布尔函数 皿= ：荔 三；三：；平方根函数皿= 而：对数函数 雪：| o g ( t f ，( d ) + 1 ) ；t f i d f 函数皿= 矿( d ) l o g ( 竺) ，其中，n 为所有文档的 行f 数目，甩f 为含有词条t i 的文档数目。 2 4 文本的分词技术 众所周知，英文是以词为单位的，词和词之间是靠空格隔开，而中文是以字为单位， 句子中所有的字连起来才能描述一个意思。例如，英文句子i 锄as t u d e n t ，用中文则为： “我是一个学生”。计算机可以很简单通过空格知道s t u d e n t 是一个单词，但是不能很容 易明白“学”、“生”两个字合起来才表示一个词。把中文的汉字序列切分成有意义的词， 就是中文分词，有些人也称为切词。我是一个学生，分词的结果是：我是一个学生。 在这里，我们主要介绍的是中文分词技术。 中文分词技术属于自然语言处理技术范畴，对于一句话，人可以通过自己的知识来 明白哪些是词，哪些不是词，但如何让计算机也能理解? 其处理过程就是分词算法。 现有的分词算法可分为三大类：基于字符串匹配的分词方法、基于理解的分词方法 和基于统计的分词方法。 l 、基于字符串匹配的分词方法 这种方法又叫做机械分词方法，它是按照一定的策略将待分析的汉字串与一个“充 分大的”机器词典中的词条进行配，若在词典中找到某个字符串，则匹配成功( 识别出 一个词) 。按照扫描方向的不同，串匹配分词方法可以分为正向匹配和逆向匹配；按照 不同长度优先匹配的情况，可以分为最大( 最长) 匹配和最小( 最短) 匹配：按照是否与词 性标注过程相结合，又可以分为单纯分词方法和分词与标注相结合的一体化方法。常用 的几种机械分词方法如下： 中北大学学位论文 1 ) 正向最大匹配法( 由左到右的方向) ； 2 ) 逆向最大匹配法( 由右到左的方向) ； 3 ) 最少切分( 使每一句中切出的词数最小) 。 还可以将上述各种方法相互组合，例如，可以将正向最大匹配方法和逆向最大匹 配方法结合起来构成双向匹配法。由于汉语单字成词的特点，正向最小匹配和逆向最小 匹配一般很少使用。一般说来，逆向匹配的切分精度略高于正向匹配，遇到的歧义现象 也较少。统计结果表明，单纯使用正向最大匹配的错误率为1 1 6 9 ，单纯使用逆向最大 匹配的错误率为1 2 4 5 。但这种精度还远远不能满足实际的需要。实际使用的分词系统， 都是把机械分词作为一种初分手段，还需通过利用各种其它的语言信息来进一步提高切 分的准确率。 一种方法是改进扫描方式，称为特征扫描或标志切分，优先在待分析字符串中识别 和切分出一些带有明显特征的词，以这些词作为断点，可将原字符串分为较小的串再来 进机械分词，从而减少匹配的错误率。另一种方法是将分词和词类标注结合起来，利用 丰富的词类信息对分词决策提供帮助，并且在标注过程中又反过来对分词结果进行检 验、调整，从而极大地提高切分的准确率。 对于机械分词方法，可以建立一个一般的模型，在这方面有专业的学术论文，这里 不做详细论述。 2 、基于理解的分词方法 这种分词方法是通过让计算机模拟人对句子的理解，达到识别词的效果。其基本思 想就是在分词的同时进行句法、语义分析，利用句法信息和语义信息来处理歧义现象。 它通常包括三个部分：分词子系统、句法语义子系统、总控部分。在总控部分的协调下， 分词子系统可以获得有关词、句子等的句法和语义信息来对分词歧义进行判断，即它模 拟了人对句子的理解过程。这种分词方法需要使用大量的语言知识和信息。由于汉语语 言知识的笼统、复杂性，难以将各种语言信息组织成机器可直接读取的形式，因此目前 基于理解的分词系统还处在试验阶段。 3 、基于统计的分词方法 从形式上看，词是稳定的字的组合，因此在上下文中，相邻的字同时出现的次数越 多，就越有可能构成一个词。因此字与字相邻共现的频率或概率能够较好的反映成词的 1 4 中北大学学位论文 可信度。可以对语料中相邻共现的各个字的组合的频度进行统计，计算它们的互现信息。 定义两个字的互现信息，计算两个汉字x 、y 的相邻共现概率。互现信息体现了汉字之 间结合关系的紧密程度。当紧密程度高于某一个闽值时，便可认为此字组可能构成了一 个词。这种方法只需对语料中的字组频度进行统计，不需要切分词典，因而又叫做无词 典分词法或统计取词方法。但这种方法也有一定的局限性，会经常抽出一些共现频度高、 但并不是词的常用字组，例如“这一”、“之一”、“有的”、“我的”、“许多的”等，并且 对常用词的识别精度差，时空开销大。实际应用的统计分词系统都要使用一部基本的分 词词典( 常用词典) 进行串匹配分词，同时使用统计方法识别一些新的词，即将串频统计 和串匹配结合起来，既发挥匹配分词切分速度快、效率高的特点，又利用了无词典分词 结合上下文识别生词、自动消除歧义的优点。 2 5 文本特征项的抽取 通常构成文本的词条的数目很大，从而表示文本的向量空间的维数也非常高，可以 达到几万维，因此在我们对文本进行挖掘之前，还要对文本进行降维，以提高挖掘结果 和减少计算复杂度。降维方法主要有两种：特征选择和特征重构。特征选择是指去除无 用词，既去除对文档区分度贡献比较小的词；特征重构一般是采用潜在语义索引的方法 构造出文本词频矩阵，利用奇异值分解技术来减少频数矩阵并保留最重要的行，这样就 可以去除原来文本词频矩阵中那些不重要的信息，选取出有效的特征词条。 一般来讲，特征词条集应具备以下三个特征： l 、完全性：特征词条能够确实表示目标内容； 2 、区分性：根据特征矢量，能将目标同其它文