（信号与信息处理专业论文）基于k平均算法的文本聚类系统研究与实现.pdf

武汉理工人学硕+ 学位论文 摘要 随着国际互联网和企业内部互联网的飞速发展，各种电子文本数据的数量 急剧增加，如何快速有效的获取、管理和使用这些文本数据，已经成为信息系 统学科迫切需要解决的重要问题。近年来，作为解决这些问题的基本工具之一， 基于文本内容的自动文本聚类技术得到了空前的发展，引起了人们普遍的关注。 文本聚类的目标是将文档集合分成若干个簇，要求同一簇内文档内容的相 似度尽可能的大，而不同簇之间的相似度尽可能的小。作为文本挖掘的一个重 要应用，文本聚类已经成为一个研究热点。 本文以中文文本作为文本聚类的挖掘对象，并对中文文本聚类的全过程进 行了研究，包括中文文本预处理、文本聚类，对文中所述方法进行了实验分析， 并设计了一个系统，实现了文本聚类的功能。 本文首先介绍了文本挖掘的研究背景、研究意义、研究现状和相关基本理 论知识。 其次，分析研究了文本的预处理过程，重点研究了中文文本的分词问题。 本文采用基于词典的正向最大匹配法实现文本初切分，结合退一字回溯扫描的 方法发现歧义字段，对歧义字段的处理采取的是基于统计词频的方法。对文本 预处理的特征表示与特征选择进行了探讨，本文采用向量空间模型( v s m ) 对 文本进行表示；而文本的特征选择则采用t f i d f 评估函数。 接着，针对中文文本的聚类，本文采用了基于k 一平均算法的二次文本聚类 方法：先对文本集采用k 一平均算法进行聚类，其中，参数k 的确定是通过计算 在一定范围内，k 取不同值的情况下，使全体样本点的平均轮廓系数最大化的k 值实现的：而初始聚类中心的选择是通过基于样本密度的方法实现的。并且， 通过实验说明了采用这两种方法确定初始参数的可行性。对于首次聚类的结果， 若某个簇包含的样本个数大大超过其它簇的样本个数，则对该簇再次进行聚类。 最后，设计了一个文本聚类系统，测试了本文设计的中文文本二次聚类方 法的聚类效果。测试结果表明，该系统能够达到将同类文本聚类的目的。 关键词：文本聚类，正向最大匹配，k 平均算法，轮廓系数 武汉理工人学硕士学位论文 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 m e ta n di n t r a n e t as h a r pi n c r e a s ei nt h e n u m b e ro fav a r i e t yo fe l e c t r o n i ct e x td a t a h o wt oq u i c k l ya n de f f i c i e n t l ya c c e s s ， m a n a g ea n du s e t h e s et e x t s ，h a sb e c o m ea nu r g e n ta n di m p o r t a n ti s s u e si nt h ea r e a so f i n f o r m a t i o ns y s t e m s i nr e c e n ty e a r s ，a so n eo ft h eb a s i ct o o l st os o l v et h e s ep r o b l e m s ， a u t o m a t i ct e x tc l u s t e r i n gt e c h n o l o g yb a s e do nt h ec o n t e n to ft h et e x th a su n d e r g o n e a nu n p r e c e d e n t e d d e v e l o p m e n t ，w h i c hh a sa r o u s e dw i d e s p r e a dc o n c e r n t h e g o a lo ft e x tc l u s t e r i n gi st od i v i d i n gt h et e x to ft h ed o c u m e n tc o l l e c t i o ni n t o s e v e r a lc l u s t e r s ，w h i c hr e q u i r e st h es i m i l a r i t yo ft h es a m ec l u s t e r sw i t h i nt h ec o n t e n t o ft h ed o c u m e n ta sb i ga sp o s s i b l ew h i l et h es i m i l a r i t yb e t w e e nt h ed i f f e r e n tc l u s t e r s a ss m a l la sp o s s i b l e a sa ni m p o r t a n ta p p l i c a t i o ni nt e x tm i n i n g , t e x tc l u s t e r i n gh a s b e c o m eah o tr e s e a r c h t h i sp a p e rf i r s ti n t r o d u c e dt h eb a c k g r o u n do ft h et e x tm i n i n gr e s e a r c h ，r e s e a r c h s i g n i f i c a n c e ，a n dr e s e a r c hr e l a t e dt ot h eb a s i ct h e o r yo fk n o w l e d g e s e c o n d ，i ta n a l y z e da n ds t u d i e dt h et e x to ft h ep r e t r e a t m e n tp r o c e s s ，f o c u s e do n w o r ds e g m e n t a t i o np r o b l e m sf o rc h i n e s et e x t i ta d o p t e dt h em a x i m u mm a t c h a l g o r i t h mi nt h ew o r ds e g m e n t a t i o n ，w i t hb a c kt oaw o r da n dt h em e t h o db a s e do n w o r df r e q u e n c yt of i n da n dd i s p e lw o r da m b i g u i t y i td i s c u s s e dt h ec h a r a c t e r i s t i e so f e x p r e s s i o na n dc h o i c eo ff e a t u r e sf o rp r e t e x t ，u s e dv e c t o rs p a c em o d e l ( v s m ) p r e s e n t i n gt h et e x ta n du s e dt h ee v a l u a t e df u n c t i o nt f i d ft oc h o o s et h et e x tf e a t u r e s t h e n ，f o rt h ec h i n e s et e x te l u s t e r i n g , i tu s e dt w i c et e x tc l u s t e r i n gm e t h o db a s e d o nk m e a n sa l g o r i t h m f i r s t ，i ta p p l y e dk m e a n si nt e x t sc l u s t e r i n gw h i l ec h o o s et h e v a l u eo fkf r o mac e r t a i nr a n g et h a tm a x i m u mt h ea v e r a g es i l h o u s t t ec o e f f i c i e n ta n d t h es e l e c t i o no fi n i t i a lc e n t e ri sb yam e t h o db a s e do ns a m p l ed e n s i t y a tt h es a m e t i m e ，e x p e r i m e n ts h o w e dt h a tt h ef e a s i b i l i t yo ft h et w om e t h o d su s e dt od e t e r m i n et h e i n i t i a lp a r a m e t e r s f o rt h er e s u l to ff i r s tc l u s t e r i n g ，i fac l u s t e rc o n t a i n e dt h en u m b e ro f s a m p l e s m u c hh i g h e rt h a nt h en u m b e ro fs a m p l e st h a tt h eo t h e rc l u s t e r s c o n t a i n e d ，t h e nr e c l u s t e rt h ec l u s t e r f i n a l l y , t h i sp a p e rd e s i g n e dat e x tc l u s t e r i n gs y s t e m ，a n dt e s t e dt h et w i c e c l u s t e r i n ge f f e c tf o rc h i n e s et e x t i n t h i s p a p e r t c s tr e s u l t s s h o wt h a ta sa n e x p e r i m e n t a ls y s t e m ，t h em a i ni n d i c a t o ro ft h ep e r f o r m a n c eo ft h eb a s i cs a t i s f a c t o r y k e yw o r d s ：t e x tc l u s t e r i n g ，m a x i m u mm a t c h ，k m e a n s ，s i l h o u s t t ec o e f f i c i e n t 独创性声明 本人声明，所呈交的论文是本人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得武汉理工大学或其它教育 机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了谢意。 签名：鳖塑堕日期：型! 兰：堑 关于论文使用授权的说明 本人完全了解武汉理工大学有关保留、使用学位论文的规定，即学校有权 保留、送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部 或部分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：兰咝堕导师签名：圭丑 e t期：矽崆! 兰：丝 武汉理- 1 ：大学硕士学位论文 第1 章绪论 随着计算机技术和计算机网络技术的发展，信息化程度快速增长，人们利 用信息技术生产和搜索数据的能力大幅度提高。于是，信息过量几乎成为人人 需要面对的问题。有人称现在是信息爆炸的时代，人们面对着“被数据淹没， 却饥饿于知识”的挑战。“如何才能不被信息的汪洋大海所淹没，从中及时发现 有用的知识、提高信息利用率”是人们迫切需要解决的问题。数据挖掘技术就 是在这样的背景下应运而生和蓬勃发展，并越来越显示出强大的生命力。 数据挖掘就是从大量的、不完全的、有噪声的、模糊的、随机的数据中， 提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程。 一般来说，数据挖掘是一个利用各种分析方法和分析工具在大规模海量数据中建 立模型和发现数据间关系的过程，这些模型和关系可以用来作出决策和预测【1 2 l 。 数据挖掘是用于大规模数据处理的一种新的思维方法和技术手段，它是在 现实生活中各种数据量呈指数级不断增长，以及以数据库技术为核心的信息技 术逐渐成熟的背景下产生的。数据挖掘可以帮助用户发现隐藏在大型数据库中 的规律和模式，它融合了人工智能、统计、机器学习、模式识别和数据库等多 种学科的理论、方法与技术，已经在商业、企业、政府、科研及体育等多种不 同类型的组织机构和领域中获得了非常广泛的应用。即使在日常生活中，数据 挖掘技术也已经潜移默化的参与到人们生活质量的改善过程中【3 1 。 1 1 研究的背景 随着信息技术的高速发展，数据库应用的规模、范围和深度不断扩大， i n t e m e t 已经发展为当今世界上最大的信息库和全球范围内传播信息的最主要渠 道。在中国互联网络信息中心( c h i n ai n t e m e tn e t w o r ki n f o r m a t i o nc e n t e r ， c n n i c ) 2 0 0 8 年1 月公布的中国互联网络发展状况统计报告中显示，8 7 8 的网 络信息均文本形式出现l 引。如何从中获取特定内容的信息和知识成为摆在人们面 前的一道难题。文本挖掘已经成为数据挖掘中一个日益流行而重要的研究领域。 文本挖掘起源于2 0 世纪6 0 年代的信息检索技术，处理的是非结构化的文 武汉理工大学硕士学位论文 本信息，因此，检索、存取、分析和使用这些数据通常并不容易。文本挖掘以 文本型信息源作为分析的对象，利用定量计算和定性分析的方法，从中寻找信 息的结构、模型、模式等各种隐含的新颖知识，这种知识为用户检索、存取、 分析和使用文本信息带来便利【5 , 6 1 。 文本挖掘的主要目标是获得文本的主要内容特征，如文本涉及的主题、文 本主题的类属、文本内容的浓缩等。目前，这些技术在处理网络信息资源时非 常有效。文本挖掘的具体实现技术主要有以下几种： ( 1 ) 特征抽取。文本特征分为一般特征和数字特征，其中，一般特征主要 包括名词和名词短语；数字特征主要包括同期、时间、货币以及单纯数字信息。 特征是概念的外在表现形式，特征抽取是识别潜在概念结构的重要基础。 ( 2 ) 主体标引。利用传统的关键词标引技术来标引文本，影响文本标引的 质量，导致同义标引词的泛滥，影响检索的查全率。同时也会影响特征抽取的 准确度。利用主题词标引代替关键词标引可以提高标引的质量，对改善文本的 检索效果十分有益。 ( 3 ) 文本分类。文本分类的任务是基于内容将自然语言文本自动分配给预 定义的类别。文本分类技术类似于数据库挖掘中分类技术，不同之处在于它需 要预先对文本进行特征抽取，它利用文本特征向量对文本进行分类。 ( 4 ) 文本聚类。聚类就是将一个数据对象的集合分组成为多个类或簇。它 的分析并不依赖于已知类标记的数据对象。在通常情况下，聚类的训练数据样 本没有类标记，它要划分的类是未知的，通过聚类可以产生这种类标记。文本 聚类是对给定的文本集根据文本相似度进行聚类的方法。 ( 5 ) 自动摘要。自动摘要是利用计算机分析文章的结构，找出文章的主题 语句，然后经过整理、组合、修饰，构成摘要的过程。人工编制摘要复杂、量 大而且费时，特别是目前，对信息量巨大的w e b 资源进行人工编制摘要是很不 实际的。利用自动摘要技术，无需编辑、分类专家或网络管理员就可以自动完 成摘要的编制，从而可以节省大量的时间和费用，并且可以避免一些人为的错 误。因此，自动摘要对网络信息资源的处理具有重要的现实意义。 文本聚类技术是文本挖掘分析技术的一个重要的研究分支。它是在无类别 标记信息的情况下，根据事物的不同特征，将事物划分为不同的分组，使得不 同聚类中的数据尽可能的不同，而同一聚类中的数据尽可能的相似【7 l 。 2 武汉理工大学硕七学位论文 1 2 研究的意义 研究文本聚类的最初目的是为了提高信息检索系统的查准率和查全率，并 被作为寻找文本最近邻居的有效方式。近年来，文本聚类用于浏览文本、显示 文本集合，或者在响应用户查询时，用于组织搜索引擎返回的结果。文本聚类 也被应用于自动产生文本的多层次的类或者簇，并利用这些生成的类对新文本 进行效率较好的归类l 引。 文本聚类的应用很广泛，它的主要作用和意义在于1 8 j ： ( 1 ) 更好地发现文本集合内在的类别特性。文本聚类被用来发现无结构的 ( u n s t r u c t u r e d ) 文本集合中的“潜在概念”信息，这些信息可以有助于组织和 搜索数量庞大的文档集合。文本聚类技术可以对没有类别标识的文本集合进行 分析，发现其中应该具有的类别信息，并且对集合中的文档进行类别标识，分 析和标识文档的类别将有助于文档内容信息的发现。所以，更进一步来讲，文 本聚类技术也可以用来对文档集合提取摘要，消除文本集合之间的歧异，而且 文本聚类技术也能够帮助搜索引擎返回的结果进行定位。 ( 2 ) 文本聚类在文档处理过程中有效减少人为的因素影响和人力资源浪 费。围绕着文本信息这一资源开展的各个领域学术研究和业界应用非常活跃， 如近年出现的各种i n t e r n e t 搜索引擎、数字图书馆和电子商务等。这些领域的研 究者在信息检索和分类研究方面所取得的成果是喜人的，但是仍然存在着许多 需要解决的问题，即处理效果并不能让人满意。在一定程度上，许多工作还需 要人为的干预。这样就可能造成人为错误的可能性，另外也造成了大量人力的 浪费。而在数据挖掘领域中，聚类技术正是一种客观的无监督技术。将聚类技 术应用在文本分析处理上，可以最大程度上地减少信息检索工作中的人为因素， 并且能够节省复杂文本分析过程中的人力资源。 ( 3 ) 减少进行类别处理时的工作量。文本分类和聚类在文本分析中扮演着 同样重要的角色，他们在功能上相近，但从实现和用途上却有所不同。文本的 自动分类是在分析文本内容的基础上给文本分配一个或多个比较合适的类别。 它通常由两个阶段组成：训练阶段和分类阶段。在训练阶段，从训练文本中学 习分类知识，建立分类器( 类模型) ；在分类阶段，根据分类器将输入文本分配 到最可能的类别中。从这个过程可以看出，分类一般需要事先存在的人工分类 好的训练文档集，也就是说分类目录是在分类过程之前事先确定的。但是，现 3 武汉理工大学硕士学位论文 在的信息是不断变化的( 例如，万维网上文本信息不断动态更新，经常会出现 新的话题和信息类别) ，很难用已有的分类体系来刻画。如果为了适应变化而重 新进行分类，就必须首先重新建立分类好的训练文档集。而获得大量带有类别 标注的样本的代价是很大的，文本的聚类技术恰好能够弥补这方而的不足。因 此，文本聚类技术能够有效地减少类别处理时的时间开销。 1 3 研究现状 国外对文本挖掘的研究开展比较早，早期的信息抽取技术就是文本挖掘的 雏形。他们在文本挖掘中的文本分类技术、关键词的自动获取和半结构化信息 提取等相关的信息抽取领域进行了较为深入的研究，并取得了不少令人瞩目的 研究成果【9 , 1 0 , 1 。 近年来，国外的文本挖掘研究进展较快，许多技术已经进入实用化阶段， 在邮件分类、电子会议、信息过滤等方面取得了广泛的应用。一些研究机构的 研究成果即各种文本挖掘应用软件也已经在商业领域得到了很好的应用，例如 i b m 的文本智能挖掘机、a u t o n o m y 公司的核心产品c o n c e p ta g c n t s 和m e g a p u t e r 的t e x t a n a l y s t 等。 相对于国外，我国对文本挖掘的研究起步较晚。1 9 9 8 年，我国国家重点基 础研究发展规划首批实施项目中，将文本挖掘的研究列为“图像、语音、自然 语言理解与知识挖掘 中的重要内容。国内对文本挖掘技术的研究机构主要集 中在高等院校、科研院所和信息公司，并且也取得了不错的成果，例如： ( 1 ) 中科院计算机语言信息工程中心所研究的汉语分词、自然语言接口、 句法分析、语义分析、音字转换等； ( 2 ) 清华大学电子工程系研究的手写汉字识别、汉字识别多分类器集成； ( 3 ) 上海交通大学计算机系研究的语句语义、自然语言模型、构造解释模 型、范例推理等； ( 4 ) 哈尔滨工业大学计算机系研究的自动文摘、手写汉字识别、自动分词 等： ( 5 ) 东北大学的词性标注、中文信息自动抽取、汉语文本自动分类模型等。 4 武汉理i 丁大学硕士学位论文 1 4 本文的主要内容及组织 第一章为本文绪论，介绍了本文的研究背景、研究意义以及国内外的研究 现状。 第二章介绍了文本聚类关键技术的基本理论，包括自动分词、文本特征表 示模型、特征项的选择以及常用的聚类算法等。 第三章具体介绍文本预处理过程，重点研究了采用正向最大匹配法结合退 一字回溯发现歧义字段以及基于词频的字段消歧处理实现的汉语自动分词等。 第四章介绍了基于轮廓系数和样本密度的k 平均文本二次聚类算法，具体 探讨如何选择最佳聚类数目和初始聚类中心。 第五章介绍系统的实现以及测试的情况，并对结果进行分析。 第六章总结本文所作的工作，指出下一步努力的方向。 5 武汉理工大学硕士学位论文 第2 章文本聚类关键技术 文本挖掘过程一般包括文本准备、特征标引、词频矩阵降维，以及知识模 式的提取、知识模式的评价和知识模式的输出等过程，如图2 1 所示i 蜘。 文本 准备 特征 标引 词频 矩阵 降维 知识模 式的提 取 知识模 式的评 价 知识模 式的输 出 图2 - 1 文本挖掘的一般过程 ( 1 ) 文本准备阶段是对文本进行选择、净化和预处理的过程，用来确定文 本型信息源以及信息源中用于进一步分析的文本，具体任务包括词性的标注、 句子和段落的划分、文本过滤等。 ( 2 ) 特征标引是指给出文本内容特征的过程，通常由计算机系统自动选择 一组主题词或关键词可以作为文本的特征表示。 ( 3 ) 词频矩阵降维就是自动从原始特征集中提取出部分特征的过程，一般 通过两种途径：一是根据对样本集的统计分析删除不包含任何信息或只包含少 量信息的特征：二是将若干低级特征合成一个新特征。特征集包含过多的特征 会增加挖掘的难度，因此，需要在不影响挖掘精度的前提下减少特征项的个数。 ( 4 ) 知识模式的提取是发现文本中的不同实体、实体之间的概念关系以及 文本中其他类型的隐含知识。 ( 5 ) 知识模式评价阶段的任务是从提取出的知识模式集合中筛选出用户感 兴趣的、有意义的知识模式。 ( 6 ) 知识模式输出的任务是将挖掘出来的知识模式以多种方式提交给用 户。 本章主要介绍文本聚类的基本过程，以及聚类过程的各个步骤中常用的技 术和算法，为以后几章的进一步研究做准备。 6 武汉理工大学硕士学位论文 2 1 自动分词 由于汉语自身的特点，在对汉语文本进行特征项抽取时，需要对文本进行 分词处理。分词是中文信息处理从字符处理水平向语义处理水平迈进的关键， 它是中文自动标引的基础。 所谓分词，就是把一个句子按照其中词的含义进行切分。与英文不同，汉 语中最小的单位不是词，而是字，但是具有一定语义的最小单位却是词。且中 文文本在书面表达或计算机内部表示时，字与字之间、词与词之间并没有明显 的切分标志，因而在对汉语文本进行处理之前首先要进行分词处理。此外，汉 语语法的研究多源于印欧语法的研究，分析结果对分词有用的信息较少；汉语 的词序又极为灵活，相对的语法限制也较少。在词汇数量上，一般的印欧语种 的词汇量最多为几十万词，而汉语的词汇量高达几百万甚至上千万。一个汉字 序列可能有几种不同的切分结果，产生歧义现象，这些都给自动分词造成了极 大的困难1 1 2 1 。 分词问题的相关研究始于2 0 世纪8 0 年代初，经过众多专家学者的不断努 力，如今已经取得了重要进展，发展了各具特色的分词方法；但是由于自然语 言的复杂性，在实际运用中仍存在困难，具体表现在如下两个方面： ( 1 ) 歧义切分。歧义切分指的是对给定的一个汉语句子，有两种或两种以 上的划分方法。 ( 2 ) 未登录词识别。语言是不断发展的，会出现现在词典中所没有的新词。 另一方面，词典容量有限，不可能收录所有的词语。常见的未登录词包括人名、 地名、机构名、译名、缩略语、重叠词、品牌词、术语等。 目前中文处理技术比西文处理技术要落后很大一段距离，许多西文的处理 方法中文不能直接采用，就是因为中文处理必须有分词这道工序。 现有的分词算法可分为三大类：基于词典的分词方法、基于理解的分词方 法和基于统计的分词方法1 1 3 , 1 4 , 1 5 l 。 2 1 1 基于词典的分词方法 这种方法又叫做机械分词方法，它是按照一定的策略将待分析的汉字串与 一个“充分大的机器词典中的词条进行匹配，若在词典中找到某个字符串， 7 武汉理工大学硕士学位论文 则匹配成功( 识别出一个词) 。按照扫描方向的不同，串匹配分词方法可以分为 正向匹配和逆向匹配；按照不同长度优先匹配的情况，可以分为最大( 最长) 匹配和最小( 最短) 匹配：按照是否与词性标注过程相结合，又可以分为单纯 分词方法和分词与标注相结合的一体化方法。常用的几种机械分词方法如下： ( 1 ) 正向最大匹配法( 由左到右的方向) ： ( 2 ) 逆向最大匹配法( 由右到左的方向) ： ( 3 ) 最少切分( 使每一句中切出的词数最小) 。 最大匹配是指，从标引文本中顺序截取一个定长的字符串( 取词典中最长 词汇的长度) 去搜索词典。搜索命中即记下该词，再以该词的长度将标引文本 向后移动( 正向扫描) 或前移( 逆向扫描) 一个步长截取下一字符串继续匹配。 若搜索失败，则从某一端舍去一个字( 正向扫描舍去后端，逆向扫描舍去前端) 继续搜索，如果直到最后一字仍然匹配失败，那么，从标引信息的该字后部或 前部重新截取一个定长字符串进行搜索处理。 还可以将上述各种方法相互组合，例如，可以将正向最大匹配方法和逆向 最大匹配方法结合起来构成双向匹配法。由于汉语单字成词的特点，正向最小 匹配和逆向最小匹配一般很少使用。一般说来，逆向匹配的切分精度略高于正 向匹配，遇到的歧义现象也较少。统计结果表明，单纯使用正向最大匹配的错 误率为1 1 6 9 ，单纯使用逆向最大匹配的错误率为1 2 4 5 。但这种精度还远远不 能满足实际的需要。实际使用的分词系统，都是把机械分词作为一种初分手段， 还需通过利用各种其它的语言信息来进一步提高切分的准确率。 2 1 2 基于理解的分词方法 这种分词方法是通过让计算机模拟人对句子的理解，达到识别词的效果。 其基本思想就是在分词的同时进行句法、语义分析，利用句法信息和语义信息 来处理歧义现象。它通常包括三个部分：分词子系统、句法语义子系统、总控 部分。在总控部分的协调下，分词子系统可以获得有关词、句子等的句法和语 义信息来对分词歧义进行判断，即它模拟了人对句子的理解过程。这种分词方 法需要使用大量的语言知识和信息。由于汉语语言知识的笼统、复杂性，难以 将各种语言信息组织成机器可直接读取的形式，因此目前基于理解的分词系统 还处在试验阶段。 8 武汉理工人学硕士学位论文 2 。1 3 基于统计的分词方法 从形式上看，词是稳定的字的组合，因此在上下文中，相邻的字同时出现 的次数越多，就越有可能构成一个词。因此字与字相邻共现的频率或概率能够 较好的反映成词的可信度。可以对语料中相邻共现的各个字的组合的频度进行 统计，计算它们的互现信息。定义两个字的互现信息，计算两个汉字x 、y 的相 邻共现概率。互现信息体现了汉字之间结合关系的紧密程度。当紧密程度高于 某一个阈值时，便可认为此字组可能构成了一个词。这种方法只需对语料中的 字组频度进行统计，不需要切分词典，因而又叫做无词典分词法或统计取词方 法。但这种方法也有一定的局限性，会经常抽出一些共现频度高、但并不是词 的常用字组，例如“这一、“之一、“有的 、“我的 、“许多的 等，并且对 常用词的识别精度差，时空开销大。实际应用的统计分词系统都要使用一部基 本的分词词典( 常用词词典) 进行串匹配分词，同时使用统计方法识别一些新 的词，即将串频统计和串匹配结合起来，既发挥匹配分词切分速度快、效率高 的特点，又利用了无词典分词结合上下文识别生词、自动消除歧义的优点。 到底哪种分词算法的准确度更高，目前并无定论。对于任何一个成熟的分 词系统来说，不可能单独依靠某一种算法来实现，都需要综合不同的算法。 2 2 文本表示模型 现阶段的挖掘技术只能处理结构化的数据，因而需要将无结构的文本转换 为结构化的描述。文本表示是指用文本的特征信息集合来代表原来的文本。文 本特征是指关于文本的元数据，分为描述性特征( 例如文本的名称、日期、大 小、类型等) 以及语义性特征( 例如文本的标题、内容等) 。描述性特征易于获 得，而语义性特征则较难获得。特征表示是指以一定特征项( 如词条或描述) 来代表文档，在文本挖掘时只需对这些特征项进行处理，从而实现对非结构化 的文本进行处理，这是一个非结构化向结构化转换的处理步骤【1 6 1 。 一个有效的特征项集，必须具备以下三个特征： ( 1 ) 完全性：特征词条能够确实表示目标内容； ( 2 ) 区分性：根据特征向量，能将目标同其他文本相区分； ( 3 ) 精练性：特征向量的维数应该尽可能小。 9 武汉理工大学硕士学位论文 文本表示是文本聚类的第一步，该步骤的变化很多，对最终聚类效果的影 响也不尽相同。接下来介绍信息检索和文本分析处理中经常用到的几个模型。 2 2 1 布尔模型 布尔模型是基于集合论与布尔代数的一种简单模型。在布尔模型中，文档 d j 中索引特征t i 的权重w i ，j 是二值的，即w i 。i o ，1 ) ，即可以将单个文本表示 成为特征空间上的一个向量，向量中的每个分量权重为o 或者1 ，这种模型称为 布尔模型( b o o l e a na p p r o a c h ) 。由于权重的二值性，所以布尔模型只能用于信息 检索中计算用户查询与文档的相关性，而无法利用该模型计算两个文档更深层 面的相似度。在经典布尔模型基础上，研究人员又提出了扩展布尔模型( e x t e n d e d b o o l e a n a p p r o a c h ) ，使相关性可以成为【o ，1 】之间的数。布尔模型是基于集合论 与布尔代数之上的一种表示模型，其表示与计算可以转化为向量来等价实现， 是一种类向量的模型1 1 刀。 2 2 2 向量空间模型 向量空间模型( v e c t o rs p a c em o d e l ，v s m ) 是2 0 世纪6 0 年代末由g e r a r d s a l t o n 等人提出的，其中最为著名的应用该模型的检索系统是s m a r t 系统。它采 用简洁的特征向量来表示文档，在进行特征选择时，不使用大量的句法语法信 息，也无需对文档进行复杂的语义处理，这样做有两个好处【1 6 l ： ( 1 ) 对大规模的文本集合有较快的处理速度，能够保证许多应用中的时间 复杂性要求； ( 2 ) 不依赖于某个特定领域。 下面介绍v s m 模型的几个基本概念： 文档( d o c u m e n t ) ：泛指一般的文本或者文本中的片断( 段落、句群或句子) ， 一般指一篇文章。 项( t e r m ) ：当文档的内容被简单地看成是它含有的基本语言单位( 字、词、 词组和短语等) 所组成的集合时，这些基本的语言单位统称为项，即文档可 以用项集( t e r ml i s t ) 表示为d ( t 1 ，t 2 ，t n ) ，其中t k 是项，1 k n 。 项的权值( t e r mw e i g h t ) ：对于含有n 个项的文本d ( t l ，t 2 ，t n ) ，项t k 1 0 武汉理【大学硕十学位论文 常被赋予一定的权值w l 【，表示它们在文本d 中的重要程度，即d = d ( t l ，w l ；t 2 ，w 2 ；t n ，w n ) ，简记为d = d ( w 1 ，w 2 ，w n ) 。这时我们说项t k 的权重为w k ，1 k r l 。 向量空间模型( v s m ) ：给定一文档d = d ( t 1 ，w 1 ；t 2 ，w 2 ；t n ，w n ) 如果t k 在文本中既可以重复出现又应该有先后次序的关系，分析起来仍有一定的 难度。为了简化分析，可以暂时不考虑t k 在文档中的先后顺序并要求t k 互异，这时可以把t 1 ，t 2 , - - - , t 。看成一个n 维的坐标系，而w 1 ，w 2 ，w n 为 相应的坐标值，因而d ( w 1 ，w 2 ，、n ) 被看成是i l l 维空间中的一个向量， 称d ( w 1 ，w 2 , - - - , w n ) 为文本d 的向量表示。 文本特征向量( f e a t u r ev e c t o r ) ：在v s m 模型中，每一个文档都可以用一个 向量来表示。向量的元素是由项( 词条) 及其权重组成，该向量就称之为 此文本的特征向量。特征向量是文档的一个特征表示，在某种意义上可以 完全代表文档的特性。 文本相似度( s i m i l a r i t y ) ：两个文本d 1 和d 2 之间的内容相关程度( d e g r e eo f r e l e v a n c e ) 常常用他们之间的相似度s i r e ( d l ，d 2 ) 来衡量。当文本被表示 成向量空间模型时，可以借助向量之间的某种距离来表示文本之间的相似 程度，目前常用的相似度计算公式有： ( 1 ) 向量之间的内积： s i m ( d 1 ，d 2 ) 一罗宰l 缁 内积代数值越大，相似度越大。 ( 2 ) 夹角的余弦值： s i m ( d 1 ，d 2 ) 一c o s 0 一 罗睨。 矧 其中，w l k ，w 2 i 【是向量d 1 和d 2 中的元素。 2 2 3 概率模型 ( 2 1 ) ( 2 2 ) 概率模型( p r o b a b i l i t i cm o d e l ) 是信息检索领域另一比较成熟的模型，并在 武汉理工大学硕士学位论文 很多系统中应用取得不错的效果。概率模型是一系列模型的简称，它综合考虑 了词频、文档频率和文档长度等因素，把文档和用户兴趣( 查询) 按照一定的 概率关系融合，并在概率测度空间上通过概率来衡量两个文本的语义相似度i l 7 。 在信息检索中，主要计算p ( r e l e v a n c e l d o c u m e n t ，q u e r y ) ，并利用概率排序 原则p r p ( p r o b a b i l i s t i cr a n k i n gp r i n c i p l e ) 来判断不同文档与同一个查询相关的 程度。p ( r e l e v a n c e l d o c u m e n t ，q u e r y ) 表示对于查询q u e r y ，文档d o c u m e n t 与 该查询相关的概率。根据不同的假设得到的求p ( r e l e v a n c e d o c u m e n t ，q u e r y ) 的计算公式，可以衍生出不同的概率检索模型。概率检索模型包括b i r ( b i n a r y i n d e p e n d e n c er e t r i e v a l ) ，i n q u e r y 等。其中，应用最广的是o k a p i 模型，该 模型在信息检索领域取得了成功，并在多届的t r e c ( t e x tr e t r i e v a lc o n f e r e n c e ) 评测中都取得了很好的成绩。 2 3 特征项的选择 经过分词以后得到文本集的所有词汇，数量是相当大的，如果都作为特征 项，在进行相似度计算时，无疑会浪费大量的时间和资源，因此，必须对这些 词汇进行筛选，这样做的目的主要有两个：第一，为了提高程序的效率，提高 运行速度；第二，所有词汇对文本分类的意义是不同的，一些通用的、各个类 别都普遍存在的词汇对分类的贡献小，在某特定类中出现比重大而在其他类中 出现比重小的词汇对文本分类的贡献大，为了提高分类精度，对于每一类，应 去除那些表现力不强的词汇，筛选出针对该类的特征项集合。 有研究证明，在经过特征压缩后的特征空间中进行文本聚类不但不会降低 聚类性能，而且会有助于提高聚类精度。 为了提取特征信息，通常采取的方法是构造一个评价函数，针对每个特征 进行评估，然后按照特征词条的排序，选取预定数目的最佳特征作为结果的特 征子集。在文本处理中，常用的评价函数主要有以下几种1 1 2 , 1 8 ： 2 3 1 信息增益 信息增益( i n f o r m a t i o ng a i n ) 在机器学习领域被广泛使用。在信息论中，样 本属性的信息增益越大，其包含的信息量也越大。 1 2 武汉理工人学硕十学位论文 对于特征词条t 和文档类别c ，i g 考察c 中出现和不出现t 的文档频数来 衡量t 对于c 的信息增益，定义如下： i g ( t ) 一一薹p ( g ) l g 尸( g ) + p 仃) 善p ( c , l r ) l g p ( c , i t ) + p ( 于) 善以e 两l g p ( c ；l 亍) ( 2 - 3 ) 其中，p ( c i ) 表示c i 类文档在语料中出现的频率，p m 表示语料中包含特征 词条t 的文档的概率，p ( c i i d 表示文档包含特征词条t 时属于c i 类的概率， p ( r ) 表示语料中不包含特征词条t 的文档的概率，p ( c i 丁) 表示文档不包含特征 词条t 时属于c i 类的条件概率，m 表示文档类别数。 2 3 2 互信息 互信息( m u t u a li n f o r m a t i o n ) 在统计语言模型中被广泛应用。它是通过计算 特征词条t 和类别c 之间的相关性来完成提取的。 m i ( ；l g 丽p ( t a c ) ( 2 4 ) 如果用a 表示包含特征词条t 且属于类别c 的文档频数，b 为包含t 但是 不属于c 的文档频数，c 表示属于c 但不包含t 的文档频数，n 表示语料中文档 的总数，t 和c 的互信息可由下式计算： m 仃，c ) - l g 石丽a x n ( 2 5 ) 2 3 3x2 ( o hi ) 统计 c h i 统计方法具有和m i 方法基本相同的思想。它度量特征词条t 和文档类 别c 之间的相关程度，并假设t 和c 之间符合具有一阶自由度的矛分布。特征 词条对于某类的z 统计值越高，它与该类之间的相关性越大，携带的类别信息 也越多。反之，f 统计量也是反映属性t 和类别c 之间的独立程度。当# 的值 为0 时，属性t 与类别c 完全独立。 令n 表示训练语料中的文档总数，c 为某一特定类别，t 表示特定的词条， 1 3 武汉理工大学硕士学位论文 a 表示属于c 类且包含t 的文档频数，b 表示不属于c 但是包含t 的文档频数， c 表示属于c 但是不包含t 的文档频数，d 是既不属于c 也不包含t 的文档频 数。则t 对于c 的c h i 值是由下式定义： z 2 仃，c ) 一百丽n 面x ( a d 面- c b 而) 2 而 ( 2 6 ) 且n = a + b + c + d 。 2 4 特征项的权重计算 在向量空间模型中，每个特征项在文本中的作用和重要性是不一样的，即 词的权重不一样。特征项的权重综合反映了该特征项对标识文本内容的贡献度 和文本之间的区分能力。假设该特征词集规模为n ( 即有n 个特征词) ，将每个 文档d j 都映射到一个维数为n 的向量空间中，即v ( d j ) = ( ， ， ) ，其中，t i ( i 【1 ，n 】) 表示特征词集中的所有词语，w i j 表示词语t i 在文 本d j 中的权重【8 1 。 权重的经典定义是： 2 珥宰i d f j ( 2 7 ) 1 f 指t e r mf r e q u e n c y ，表示词语t i 在文档d j 中出现的次数，称为词频；i d f 指i n v e r s ed o c u m e n tf r e q u e n c y ，定义为 ， i d f j l o g f 一) ，l j ( 2 8 ) 在这个公式中，n 表示文档集合中所有的文档数目，n j 表示整个文档集合中 现过词语t i 的文档的总数，称为特征的文档频率。 另外，文档长度也是必须要考虑的因素，否则越长的文档越有可能被检索 到。因此将特征项权重归一化后得到： 一 t f tx l o g ( n n j + q 0 1 ) ( 2 9 ) 权重w o 刻画了词语区分文本内容属性的能力，一个词语在所有文档中出现 的范围越广，即n n i 越小，w i j 就越小，说明它区分文档属性的能力越低。如果 1 4 武汉理工大学硕士学位论文 一个词语在一个特定的文档中出现的频度越高，t i i 即越大，w 硒也越大，说明它 在区分该文档内容属性方面的能力越强。 这种公式是根据香农信息学理论，如果项在所有文本中出现的频率越高， 那么它所包含的信息嫡就越少；如果项的出现较为集中，只在少量文本中有较 高的出现频率，那么它就会拥有较高的信息嫡。上述公式就是基于这个思想的 一种实现。 这样，利用t f * i d f 进行计算，我们就可以得到全部特征词的权重，从而完 成文档集的特征表示。 多年实验表明，t f * i d f 是文本处理的一个有效工具。事实上，这一公式不 仅在文本分类中得到了成功应用，它对其它文本处理领域，如信息分发、信息 过滤和信息检索也有很好的借鉴意义。 2 5 中文文本聚类算法 聚类就是将数据对象组成不同的类( 或簇) ，使得不同类对象间的相似性尽 量小，而同类对象间的相似性尽量大。聚类不同于分类，分类问题是在已经知 道