（计算机应用技术专业论文）基于相似度的文本聚类算法研究及应用.pdf

江苏大学硕士研究生学位论文 摘要 文本聚类是文本挖掘的一项重要技术，可广泛应用于文本挖掘与信息检索 等方面，在大规模文本集的组织与浏览、文本集层次归类的自动生成等方面都 具有重要的应用价值。但是，传统的文本聚类算法忽略了文本中单词之间的语 义相关性，存在聚类结果不稳定等问题。论文主要针对以上问题对文本聚类进 行研究。 论文先论述了文本挖掘的相关知识，分析了文本聚类的必要性及国内外研 究现状，并介绍了传统的文本聚类算法，并对其进行比较和分析。重点对文本 表示方法及d b s c a n 算法做了深入研究，对相关算法进行改进，并在此基础上 设计一个文本聚类系统。本文主要工作如下： ( 1 ) 介绍常用文本聚类算法，并从伸缩性、多维性、处理高维数据的能力等 方面对常用文本聚类算法进行分析和比较。 ( 2 ) 提出一种基于语义列表的文本聚类算法，该算法利用语义相似度计算文 本的相似度，获得文本的语义相关性，采用语义列表中的同义词近义词指针降 低单词的冗余度，降低了文本数据的维度，最后采用基于划分聚类算法对文本 聚类。实验表明此算法提高了聚类结果的正确性。 ( 3 ) 对聚类算法d b s c a n 进行改进，提出一种阈值优化的文本密度聚类算 法。该算法首先使用k 近邻距离对对象进行排序，并通过分位数区分密度不同 的各序列，找到与其对应的优化，根据优化闽值使用密度聚类方法对对象进行 聚类。改进后的聚类算法克服了阈值选取对聚类结果的影响，提高了聚类精确 度和时间效率。文章采用树形结构存储聚簇，增加了聚簇的可读性。实验结果 证明了该算法的有效性。 ( 4 ) 在理论研究的基础上，将本文提出的文本聚类算法应用于文本数据集 中，设计一种文本聚类系统，该系统提供了预处理模块、语义列表模块、聚类 算法模块、结果评估模块，分析系统各个模块的主要功能及其应用，结果表明 该系统具有良好的可扩展性、灵活性。 关键词：文本挖掘；文本聚类：文本表示；语义列表；相似度计算；聚簇表示； d b s c a n 算法；t d c a o t v 算法；分位数 江苏大学硕士研究生学位论文 a b s t r a c t t e x tc l u s t e r i n gi sa l li m p o r t a n tb r a n c ho ft e x tm i n i n g ，w h i c hh a sg e tm o r e d e p t hr e s e a r c hb e c a u s eo fi t su n i q u ek n o w l e d g ed i s c o v e r yf u n c t i o n s t o d a y , t h e r ea r e l o t so fe f f i c i e n tt e x t c l u s t e r i n ga l g o r i t h m sw h i c hh a v eb e e nw i d e l yu s e di n t h e a u t o m a t i cd o c u m e n tf i n i s h i n g ，t h eo r g a n i z a t i o no fs e a r c hr e s u l t sa n dd i g i t a ll i b r a r y s e r v i c e s h o w e v e r , w i t he x p a n s i o no fd o c u m e n ts e t s ，t r a d i t i o n a l t e x tc l u s t e r i n g a l g o r i t h me n c o u n t e r e dan u m b e ro f i n s u r m o u n t a b l ed i f f i c u l t i e s f o ri n s t a n c e ， a l g o r i t h mi g n o r e st h es e m a n t i cc o r r e l a t i o nb e t w e e nw o r d s ，t h ei n s t a b i l i t yo fr e s u l t t h e s e p a p e r sm a i n l yf o r t h ea b o v ep r o b l e m sd os o m er e s e a r c ho nt e x tc l u s t e r i n g i nt h ef i r s tp l a c e ，t h i sp a p e rd i s c u s s e ss o m ek n o w l e d g eo ft e x tm i n i n g ，a n d a n a l y z e st h en e c e s s i t yo f t e x tc l u s t e r i n ga n dt h er e s e a r c ha c t u a l i t yo ft e x tc l u s t e r i n ga t h o m ea n da b r o a d t h e nt h et r a d i t i o n a lt e x tc l u s t e r i n ga l g o r i t h m sa r ei n t r o d u c e d ，a n d w h i c ha r ec o m p a r e da n da n a l y z e d i tp u t sm o r ee m p h a s e so nt h ed e e ps t u d yo f d o c u m e n tr e p r e s e n t a t i o na n dd b s c a na l g o r i t h ma n dm a k e st h ei m p r o v e m e n t t o w a r d sr e l a t e da l g o r i t h m s ，m e a n w h i l ed e s i g n sat e x tc l u s t e r i n gs y s t e mb a s e do nt h e p r e v i o u st h e o r i e s t h ew o r k s i nt h i sp a p e ri sa sf o l l o w s ： ( 1 ) i n t r o d u c e dt o t h et r a d i t i o n a lt 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 yw e r e c o m p a r e da n da n a l y z e df r o mt h es c a l a b i l i t y , m u l t i d i m e n s i o n a l ，d e a l i n gw i t hh i g h d i m e n s i o n a ld a t aa n ds oo n ( 2 ) i no r d e rt or e p r e s e n td o c u m e n t s ，t h i sp a p e rp r e s e n t s t h ec h i n e s et e x t c l u s t e r i n ga l g o r i t h mu s i n gs e m a n t i cl i s t f i r s to fa l l ，t h ea l g o r i t h mu s eo fs e m a n t i c s i m i l a r i t yt oc o m p u t et e x ts i m i l a r i t y , a c c e s st ot e x ts e m a n t i cr e l e v a n c eb e t w e e nt e x t s ， a n dt h e nm a k eu s eo fs y n o n y mo rn e a r - s y n o n y mo ft h es e m a n t i cl i s tt or e d u c e r e d u n d a n c yo ft h ew o r d st h a tr e d u c e dd i m e n s i o no ft e x t s f i n a l l y , u s e dp a r t i t i o n i n g c l u s t e r i n ga l g o r i t h m e x p e r i m e n t ss h o w e dt h a tc t c a u s la l g o r i t h mi m p r o v et h e a c c u r a c yo fc l u s t e r i n gr e s u l t s ( 3 ) at e x td e n s i t yc l u s t e r i n ga l g o r i t h mw i t ht h eo p t i m i z e dt h r e s h o l dv a l u e si s p r o p o s e dt os o l v et h ep r o b l e mo fr e d u c e dc l u s t e r i n gp e r f o r m a n c eo ft h ed b s c a n 江苏大学硕士研究生学位论文 a l g o r i t h mb e c a u s eo fg l o b a lt h r e s h o l dv a l u e s t h ep r o p o s e da l g o r i t h ms o r t so b j e c t s w i t hk - n e i g h b o rd i s t a n c e ，a n dd i s c e r n sa r r a y sw i t hd i f f e r e n td e n s i t i e sb yq u a n t i l e ，a n d f i n d st h ec o r r e s p o n d i n go p t i m i z a t i o n ，t h e nc a r r i e so u tc l u s t e r i n go fo b j e c t su s i n g d e n s i t yc l u s t e r i n ga l g o r i t h mb a s e do no p t i m i z e dt h r e s h o l dv a l u e s t h ea d v a n c e d c l u s t e r i n ga l g o r i t h mh a so v e r c o m et h ep r o b l e mo fr e d u c e dc l u s t e r i n gp e r f o r m a n c e c a u s e db yt h r e s h o l dv a l u e ss e l e c t i o n ，a n dh a si m p r o v e dc l u s t e r i n ga c c u r a c ya n d e f f i c i e n c y t h ep a p e rs t o r e sc l u s t e r sw i t ht r e es t r u c t u r e ，a n dh a sm a d ec l u s t e r sm o r e l e g i b l e t h ee x p e r i m e n t a lr e s u l t ss h o wt h ee f f e c t i v e n e s so f t h ea l g o r i t h m ( 4 ) o nt h eb a s i so fs t u d y i n gt h e o r y , t h ea l g o r i t h m sp r e s e n t e di nt h i sa r t i c l ea re u s e di nt h et e x tc o l l e c t i o n ，a n dd e s i g no fat e x tc l u s t e f i n gs y s t e m ，w h i c hp r o v i d e p r e t r e a t m e n tm o d u l e ，s e m a n t i c l i s tm o d u l e ，t e x tc l u s t e r i n gm o d u l ea n dr e s u l t e v a l u a t i o nm o d u l e f r o mt h ea n a l y s i so ft h em a i nf u n c t i o n so fe a c hm o d u l eo fs y s t e m a r c h i t e c t u r ea n di t sa p p l i c a t i o n ，i ts h o w st h a tt h es y s t e mh a sg o o de x t e n s i b i l i t ya n d f l e x i b i l i t y k e yw o r d s ：t e x tm i n i n g ；t e x tc l u s t e r i n g ；t e x tr e p r e s e n t a t i o n ；s e m a n t i cl i s t ； s i m i l a r i t yc a l c u l a t i o n ；c l u s t e rr e p r e s e n t a t i o n ；d b s c a na l g o r i t h m ； t d c a o t v a l g o r i t h m ；q u a n t i l e 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，。 同意学校保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权江苏大学可以将本学位论文的全部 内容或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。 保密口， 在年解密后适用本授权书。 本学位论文属于 l 不保密圈。 学位论文作者签名：勇 手、终导师签名： 移巩 签字日期：加p 年g 月丫日签字日期：伽产年6 月7 日 独创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进 行研究工作所取得的成果。除文中已经注明引用的内容以外，本论文 不包含任何其他个人或集体已经发表或撰写过的作品成果。对本文的 研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人 完全意识到本声明的法律结果由本人承担。 学位论文作者签名： 另糸终 日期：伽步年f 月丫e t 江苏大学硕士研究生学位论文 1 1 研究背景及意义 第一章绪论 随着i n t e m e t 的快速发展，无论是网络信息、企业信息还是个人信息都在急 剧膨胀，其中文本作为最重要的信息载体，增长速度更是飞速。目前，网上资 源以指数速度增长，其信息量无论是在数量上还是在种类上都是人们难以想象 的，人们要获取所需的全部信息要花费大量的时间和精力。因此，如何快速而 有效地获取“更多 、“更准”的信息已成为人们关注的焦点。 。在现实世界中，文本是最重要的信息载体。2 0 0 8 年1 月最新公布的中国互 联网络发展状况统计报告中显示，8 7 8 的网络信息均以文本形式出现。特别是 在互联网上，文本数据广泛地存在于各种形式中，如新闻报道、电子图书、研 ： 究论文、数字图书馆、网页、电子邮件等等。面对大量无序的文本数据，如何 对文本进行分类、比较评估文本的相关性和重要性，以及发现众多文本的模式 与趋势等，都可以归结到文本挖掘这个具体领域当中。文本挖掘的主要任务是 分析文档数据库的内容，发现文档数据集中概念、文档之间的相互关系和相互 作用，抽取有效、新颖、有用、可理解的、散布在文本文件中的有价值知识， 并利用这些知识更好地组织信息。文本挖掘处理的是非结构化的文本信息，而 不是通常数据挖掘中采用的结构化数据信息。文本挖掘的主要研究内容包括关 联分析、文本分类、文本聚类等。 文本挖掘，就是从这种半结构或无结构化的文本数据中发现潜在的概念以 及概念间的相互关系。 文本挖掘过程主要分为三个阶段：预处理阶段、挖掘分析阶段、结果展示 阶段，如图1 1 所示。预处理阶段主要包括s t e m m i n g ( 英语) 分词( 中文) 、 噪音词处理、特征表示和特征提取等技术。挖掘分析阶段常用的文本挖掘分析 技术有：文本结构分析、文本摘要、文本分类、文本聚类、文本关联分析、分 布分析和趋势预测等。挖掘结果可通过数据可视化( d a t av i s u a l i z a t i o n ) 技术来 展示，该技术是指运用计算机图形学和图像处理技术，将数据转换为图形或图 像在屏幕上显示出来，并进行交互处理的理论、方法和技术。 江苏大学硕士研究生学位论文 l ； ，一+： 浏览 一 f一+： l 一 i o - ；_ h i ；：，- ， ；苫昙i ； 糍詈争：1 二： 查弼 图1 1 文本挖掘过程 文本聚类技术是文本挖掘分析技术的一个重要研究分支。 文本聚类技术作为一项基础性研究，对已有的网络信息资源的组织以及搜 索引擎性能的改善都将起到很大的帮助作用。而且，对于所有的档案资料，过 去我们都是通过人工方法进行分类，这项工作需要耗费专业人员大量的时问和 精力去完成。并且由于主观性的差异，有可能在花费了大量的人力物力后，分 类加工的结果还存在不小的差异。因此利用计算机进行文本自动归类将是一个 行之有效的办法。综上所述，文本聚类技术是随着信息时代的到来而得到重视 和发展的，也因计算机技术和相应数学应用技术的发展而不断发展。文本聚类 技术也将成为人工智能领域一个重要的研究课题。本文主要对中文文本聚类进 行较为深入的研究。 1 2 文本聚类的研究现状 国外对文本聚类的研究比较早也比较深入，己经将文本聚类应用在文本挖 掘和信息检索领域，例如，将文本聚类用来改善信息检索系统中的查准率和查 全率。最近，文本聚类用于浏览文本集以及重新组织查询引擎【5 4 l 。此外，文本 聚类还可以用于提供对一个大文本集的内容进行概括、识别隐藏的共同点等。 文本聚类应用的一个典型例子是对顾客进行分析，找出不同用户群的购物特点， 为商业决策提供支持。一些研究机构的研究成果已经在商业领域得到了很好应 用，如i b m 开发的t e x t m i n e r ，m e g a p u t e r 公司的t e x t a n a l y s t ，x t r a m i n d 公司 2 江苏大学硕士研究生学位论文 的x m m i n d s e t 等。其中i b m 开发的t e x t m i n e r 主要功能包括特征抽取、文档 聚集、文档分类和检索。m e g a p u t e r 公司的t e x t a n a l y s t 是一个智能文本挖掘和 语义信息搜索系统，它采用了独特的神经元网络技术，实现了对自然语言文本 的结构化处理，可以用来创建知识库、搜索语义信息和自动抽取文本。x t r a m i n d 公司研发的大型模块集x m m i n d s e t 集成了多项核心智能技术，其中就包括了 文本聚类的功能模块( x m c l u s t e r i n g ) 。它在模块精度( 查准、查全) 、时间效率、 广义化、鲁棒性、动态移植性等方面都表现卓越。 与国外相比，国内对文本聚类的研究起步比较晚。国内对文本聚类技术的 研究机构主要集中在高校和研究所，如中国科学院计算技术研究所智能信息处 理丌放实验室、上海交通大学电脑应用研究所、哈尔滨工业大学信息检索研究 室及清华大学等。中国科学院计算技术研究所智能信息处理开放实验室研制的 多策略数据挖掘平台，支持特征抽取、分类、聚类、预测、关联规则发现、统 计分析等数据挖掘功能。哈尔滨工业大学信息检索研究室也开发出了中文多文 档自动文摘系统和中文文本聚类系统。除科研院外还有一些公司致力于这个领 域的研发，如北京拓尔思( t b s ) 信息技术有限公司等。北京拓尔思( t b s ) 信息技 术有限公司研发的t r s 中文知识管理工具包为中文文本应用提供了开放的开发 工具箱，它集成了t r s 公司最新推出的多项中文处理技术，其中包括了文本聚 类。少数单位j 下从事中文文本聚类算法的研究及其应用，如中国科技大学的姜 宁等人，解放军理工大学的李家福等人和中国科学院计算所的卜东波等人。 1 2 1 文本聚类简介 文本聚类是无指导的机器学习，它没有预先定义好主题类别。文本聚类的目 标是将文档集合分成若干个簇，要求同一簇内文档内容的相似度尽可能大，而不 同簇间的相似度尽可能小【1 】【2 】【3 1 。文本聚类可以用于提供对一个大的文本集的内 容进行概括，识别文本集内隐藏的共同点，同时，也能够使那些找到相近或相关 的浏览程序简单化。 文本聚类根据文档的某种联系或相关性对文档集合进行有效的组织、摘要 和导航，方便人们从文档集中发现相关的信息。文本聚类方法通常先利用向量 空间模型把文档转换成高维空间中的向量，然后对这些向量进行聚类。由于中 文文档没有词的边界，所以一般先由分词软件对中文文档进行分词，然后再把 江苏大学硕士研究生学位论文 文档转换成向量，通过特征抽取后形成样本矩阵，最后再进行聚类。文本聚类 的输出一般为文档集合的一个划分，其形式可以是一个层次结构( 如a h c 算法) 或者二维平面图( 如s o m 神经网络) 。聚类由于不需要训练过程，也不需要预先 对文档手工标注类别，因此具有一定的灵活性和较高的自动化处理能力，已经 成为对文本信息进行有效地组织、摘要和导航的重要手段。 1 2 2 文本聚类存在的问题 要进行文本聚类，首先要做的就是对文本数据进行数学描述，其中最常用 的数学模型就是向量空间模型。在该模型中，每一个不同的单词都作为特征空 间中的一维，每一个文本是特征空间中的一个向量。这种描述存在高维稀疏问 题，因为在通常情况下，即使是一个中等规模的文本数据集也具有几万个单词， 这种维度对很多算法来说实在是太高了，事实上只有少数几种神经网络的算法 能处理这么高的维度，而对于像贝叶斯神经网络这类算法来说，其计算简直是 不可能的。另一方面，每一个文本通常只包含所有单词中的极小部分单词，这 也就是说，一个文本向量在文本空问中绝大部分的维度上都足0 ，这使得文本 空间异常稀疏，其稀疏程度通常达9 5 一9 9 1 4 j 1 5 l 。高维稀疏问题给文本聚类造 成了相当大的影响，不仅使得文本聚类具有相当高的时间复杂度，而且会极大 地降低文本聚类和文本分类的性能1 6 】【7 1 。 另外，文本数据还存在大量的多词同义、一词多义的现象。近义词现象指 的是可以用多种不同的方式来描述同一个主题或者内容。这是因为人们在不同 的时间、地点下，或者因为知识水平、周围环境、语言习惯、特定需求等因素 往往会使用不同的文字来表达相同的内容【羽。据f u m a s 等9 1 的统计发现，两个 人在使用相同的词语来表达同一件事物的概率不超过2 0 ，这个数据说明了近 义词现象的普遍性。然而近义词的存在极大地降低了信息检索的性能，因为在 精确匹配的方式下，使用“足球 是无法找到“世界杯”、“f i f a ”、“中国甲a 等内容。多义词现象指的是同一个单词有多重不同的含义【l o l 。多义词最大的损 害在于极大降低信息检索的精确度，因为检索“苹果牌电脑所返回的结果中 可能既包含介绍苹果特性的文章，又包含苹果电脑、苹果牛仔等文章。近义词 和多义词现象的存在极大地干扰了文本聚类和文本分类的准确度，使得文本分 类和文本聚类变得非常困难l l 。 4 江苏大学硕士研究生学位论文 1 3 研究内容及安排 目前文本聚类技术正处于发展阶段，许多学者对文本聚类技术进行了大量 的研究，但这些研究大部分是在英文环境下进行的，对中文的研究为数不多。 另外，他们大部分用向量空问模型来表示文本，而基于向量空间模型的中文文 本聚类算法，存在高维稀疏及同义词近义词的问题。针对以上问题，本文主要 做了以下几点工作： ( 1 ) 对传统的中文文本聚类算法进行研究； ( 2 ) 对文本表示模型进行研究，并针对基于向量空间模型的聚类算法存在 高维稀疏及同义词近义词等问题提出基于语义列表的中文文本聚类算法，该算 法采用语义列表表示文本，一个文本的语义列表中的词是该文本中出现的词， 从而降低了数据维数，且不存在稀疏问题；同时利用词语问的相似度计算，解 决了同义词近义词的问题；最后用语义列表对聚簇进行描述，增加了聚类结果 的可读性； ( 3 ) 详细介绍基于密度的聚类算法，对d b s c a n 算法中参数影响聚类结果 的问题，提出一种阈值优化的文本密度聚类算法，该算法使用k 近邻距离对对 象进行排序，并通过分位数区分密度不同的各序列，找到与其对应的优化，根 据优化阈值使用密度聚类方法对对象进行聚类； ( 4 ) 对聚类实验结果进行评价及分析； 本文的结构组织如下： 第一章绪论 本章首先介绍了文本聚类的研究背景与研究意义，其次介绍了文本聚类技 术及其存在的问题，最后介绍了文章的主要研究内容及组织架构。 第二章中文文本聚类算法综述 本章主要介绍了文本聚类领域里的文本预处理、文本表示模型中的向量空 间模型及其它文本表示模型、文本相似度度量中的词间相似度计算及文本间相 似度的计算、现有各种文本聚类算法及其代表算法。另外，本章还介绍了文本 聚类效果的评价指标。 第三章基于语义列表的中文文本聚类算法 对文本表示模型进行研究分析，对向量空问模型进行详细描述，并针对基 江苏大学硕士研究生学位论文 于向量空问模型聚类算法存在高维稀疏及同义词近义词的问题，提出基于语义 列表的中文文本聚类算法。 第四章一种阈值优化的文本密度聚类算法 本章对d b s c a n 算法进行研究和分析，针对d b s c a n 聚类算法中参数选 择对聚类结果造成影响的问题，提出一种闽值优化的文本密度聚类算法。 第五章聚类算法实验结果评价及分析 对第三章和第四章提出的聚类算法的实验所用的实验数据及实验环境进行 描述，对实验结果进行评价及分析。 第六章总结与展望 本章对全文工作进行总结，并对下一步工作进行了展望。 6 江苏大学硕士研究生学位论文 第二章中文文本聚类算法及分析 本章主要介绍了常用文本聚类算法过程中的文本预处理、文本表示模型、 文本相似度度量、各种文本聚类算法及效果评价指标。 2 1 文本预处理 在文本上进行挖掘与在传统数据库上进行挖掘的一个重要区别就是，文本 是非结构化的数据，在进行文本挖掘之前，需要对文本集进行预处理，使文本 最终表示为一种结构化的形式，同时需要保证这种结构化的形式能够充分体现 出文本对象自己的特点，突出文本对象间的差异，以便于区分文本。 文本的预处理技术对于文本挖掘来说是一个非常重要的环节。可以说，预 处理的质量直接影响到最终的挖掘结果。同时，针对不同的挖掘目的，预处理 的方法也存在不同。但是其预处理过程基本包括以下几个步骤。 2 1 1 分词 中文文本的知识发现难度较大，主要体现为汉语分词问题，这一问题在英 文文本处理中不存在。汉语与英语不同，在英语文本中词与词之间是明显分隔 开的，而在中文文本中则没有这种分隔标记，因此在进行中文信息处理时，要 根据应用并按一定的规范进行分词切分，即分词1 1 2 l 。汉语自动分词是信息提取、 信息检索、机器翻译、文本分类、自动文摘、自然语言理解等中文信息处理领 域的基础研究课题。传统的分词方法采用词典和基于规则的启发式搜索算法， 但在目前不具备完备的词典，这类方法难以适应各种应用领域的变化。而基于 统计的词语抽取方法不受文本领域的限制，可以不依靠词典把文档中的词提取 出来1 n 17 1 。它的主要思想是利用每个汉字结合模式在文档中重复出现的次数来 判断该结合模式是否构成一个词。 现有的分词算法可分为三大类1 1 8 】：基于字符串匹配的分词方法、基于理解 的分词方法和基于统计的分词方法。 ( 1 ) 基于字符串匹配的分词方法 这种方法又叫做机械分词方法，机械分词方法的基本思想是事先建立一个 7 江苏大学硕士研究生学位论文 词库，其中包含所有可能出现的词。它是按照一定的策略将待于分析的汉字串 与一个“充分大的”机器词典中的词条进行匹配，若在词典中找到某个字符串， 则匹配成功( 识别出一个词) ，继续分割剩余部分，直到剩余部分为空。否则该 字符串不是词，重新切取字符串进行匹配。 按照扫描方向的不同，串匹配分词方法可以分为正向匹配和逆向匹配；按 照不同长度优先匹配的情况，可以分为最大( 最长) 匹配和最小( 最短) 匹配； 按照是否与词性标注过程相结合，又可以分为单纯分词方法和分词与标注相结 合的一体化方法。常用的几种机械分词方法如下： 正向最大匹配法是最早提出的中文分词方法。基本思想为：设d 为词库， m a x 为d 中最大词长，s t r 为待切分字符串。由左至右地从s t r 里获得长度 为m a x 的字符串，并与词库匹配。匹配成功，则作为一个词语切分开来；反 之，将长度为m a x 的字符串的最后一个字符删除，再与词库匹配，直至匹配 出一个词语为止。对s t r 里的剩余部分重复此工作，直至所有的词语都被切分 开来为止。 逆向最大匹配法与正向最大匹配法大同小异。不同的是：逆向最大匹配 法是由右至左地从s t r 里获得长度为m a x 的字符串。 双向匹配法是正向最大匹配法和逆向最大匹配法的组合。 就目前阶段而言，j 下向最大匹配法和逆向最大匹配法切分技术较为成熟， 思路清晰，算法比较简单，易于计算机实现。但是因为完全依赖于词库，故分 词效率和准确性受到了词库容量的束缚，并且对于分词中出现的歧义问题也无 法很有效的消除。 实际使用的分词系统，都是把机械分词作为一种初分手段，还需通过利用 各种其它的语言信息来进一步提高切分的准确率。 ( 2 ) 基于理解的分词方法 这种分词方法是通过让计算机模拟人对句子的理解，达到识别词的效果。 其基本思想就是在分词的同时进行句法、语义分析，利用句法信息和语义信息 来处理歧义现象。它通常包括三个部分：分词子系统、句法语义子系统、总控 部分。在总控部分的协调下，分词子系统可以获得有关词、句子等的句法和语 义信息来对分词歧义进行判断，即它模拟了人对句子的理解过程。这种分词方 法需要使用大量的语言知识和信息。由于汉语语言知识的笼统、复杂性，难以 8 江苏大学硕士研究生学位论文 将各种语言信息组织成机器可直接读取的形式，因此目前基于理解的分词系统 还处在试验阶段。 ( 3 ) 基于统计的分词方法 从形式上看，词是稳定的字的组合，因此在上下文中，相邻的字同时出现 的次数越多，就越有可能构成一个词。因此字与字相邻共现的频率或概率能够 较好的反映成词的可信度。可以对语料中相邻共现的各个字的组合的频度进行 统计，计算它们的互现信息。互现信息体现了汉字之间结合关系的紧密程度。 当紧密程度高于某一个值时，便可认为此字组可能构成了一个词。这种方法只 需对语料中各个字的组合频度进行统计，不需要切分词典，因而又叫做无词典 分词法或统计取词方法。但这种方法也有一定的局限性，会经常抽出一些共现 频度高、但并不是词的常用字组，并且对常用词的识别精度差，时空开销大。 实际应用的统计分词系统都要使用一部基于分词词典的常用词词典进行串匹配 分词，同时使用统计方法识别一些新的词，即将串的频度统计和串匹配结合起 来，既发挥匹配分词切分速度快、效率高的特点，又利用了无词典分词结合上 下字识别生词、自动消除歧义的优点。 到底哪种分词算法的准确度更高，目前并无定论。对于任何一个成熟的分 词系统来说，不可能单独依靠某一种算法来实现，都需要综合不同的算法。 2 1 2 停用词过滤 在文本中都存在一些对文本内容识别意义不大的词，在文本挖掘中，称之 为停用词。这些词没有什么实际意义，而且在各类文本中出现的频率都很高， 在特征选择或者计算相似度的过程中会引入很大的误差，可以看作是一种噪声。 最简单的例子是汉语中“的 、“了”、“所”、“到”、“可”、“能 、“由”等词。 他们没有具体的意义，不能体现文本所表示的内容，但在几乎所有的文本中都 会出现，如果在聚类过程总是考虑到这些词，那么文本之间的相似性就不能表 现出内容的相似性，而是一些无意义的相似性，这不是我们所希望的。根据z i p 定律：在一个文本集中，任一词的频率乘以自身的序号约等于常数。这个定律 表明中等频率的词汇其表现能力最强。因此，为了提高文本挖掘的准确性，就 必须去掉那些在所有文档中都有很高出现频率，而本身对文本内容又贡献不大 的词，如“的地得”等；去掉稀有词，稀有词在中文文档中出现的次数 都很少，如“分爨”等。 9 江苏大学硕士研究生学位论文 停用词自动抽取方法为了找出噪声词，需要一些标准用于估计词的有效性， 常用的评估因子有f 1 9 l ：文档频数( d f ) 、词频( t f ) 、熵、联合熵。 ( 1 ) 文档频数d f ( d o c u m e n tf r e q u e n c y ) d f 是一种简单的评估函数，其值为训练集合中包含此单词的文本数。d f 评估函数的理论假设是当一个词在大量文本中出现时，这个词通常被认为是噪 声词。 ( 2 ) 词频t f ( t e r mf r e q u e n c y ) t f 是一种简单的评估函数，其值为训练集合中此单词发生的词频数。t f 评估函数的理论假设是当一个词大量出现时，通常被认为是噪声词。 ( 3 ) 熵计算e c ( e n t r o p yc a l c u l a t i o n ) 根据信息论，定义基于单词在文本中出现的平均信息量形( w ) ： 叭w ) _ l + 矗丙善以w ) l n 防( w ) 】 ( 2 j ) 式中p ( w ) 为单词w 在文本，中出现的概率。 熵( w ) 的值越大，说明单词w 所表示的平均信息量越大，单词w 就越普通， 就可以当作是噪声词。 ( 4 ) 联合熵u e ( u n i o ne n t r o p y ) 考虑到当一个词在句子中出现的平均信息量和包含该词的句子在文本中的 平均信息量都较大时，表示该词较为普通。定义两者之和为联合熵肜( w ) ： ( 叻= h ( w ) + h ( siw ) 单词w 在句子中出现的平均信息量日( 们： ( 2 2 ) n ( w ) = - z g ( s l w ) l o g ( s 1w )( 2 3 ) = i 包含该单词w 的句子在文本中的平均信息量h ( sl 叻 h ( s lw ) = 一p i ( s l w ) l o g p l ( s l w ) 1 = 1 单词w 在句子，中发生的概率e ( w ) l o ( 2 4 ) 江苏大学硕士研究生学位论文 f ( w ) ：掣 ( 2 5 ) 。 z y , c w ) 1 = 1 包含单词w 的句子在文本，中发生的概率异( siw ) ： 删w ) ：掣 f , ( s lw ) j 一 ，= l ( 2 6 ) 式中厂( w ) 为单词w 在句子，中出现的频率，力为句子数，彳( 51w ) 为包含 单词w 的句子s 在文本，中出现的频率，m 为文本数。 2 1 3 特征选择 构成文本的词汇，数量是相当大的，因此，表示文本的向量空间的维数也 相当大，可以达到几万维，很显然需要进行维数压缩的工作，这样做的目的主 要有两个，第一，为了提高程序的效率，提高运行速度。第二，所有词汇对文 本分类的意义是不相同的，一些通用的、各个类别都普遍存在的词汇对聚类的 贡献小，在某特定类中出现比重大而在其他类中出现比重小的词汇对文本聚类 的贡献大，为了提高聚类精度，对于每一类，应去除那些表现力不强的词汇， 筛选出针对该类的特征项集合。 特征抽取的输入是原始样本，领域专家决定使用哪些特征来深刻地刻画样 本的本质性质和结构。特征抽耿的结果是输出一个矩阵，每一行是一个样本， 每一列是一个特征指标变量。 选取特征的优劣将直接影响以后的分析和决策。如果第一步就选择了和聚 类意图根本无关的特征变量，企图得到良好的聚类结果则无异于缘木求鱼。因 为无论后续步骤采用多么优良的聚类算法和阈值选择方案，都不可能计算出执 行者的意图。合理的特征选取方案应当使得同类样本在特征空间中相距较近， 异类样本则相距较远。 文本的特征选择主要有两种思路：种是基于阈值的统计方法，该方法计 算复杂度低，速度快；另一种是基于映射的方法也叫做w r a p p e r 方式。 ( 1 ) 基于阈值的特征选择方法 基于阈值的特征选择的基本思想是对每一个特征，计算出某种统计度量值， 从中抽取一定数量的词作为特征项，用抽取出的特征项作为文档的向量表示， 江苏大学硕士研究生学位论文 从而实现维度的降低。一般是设定一个阈值丁，将计算的统计度量值按照从大 到小的顺序排列，把度量值小于r 的那些特征过滤掉，剩下的便是有效的特征。 常见的方法有特征频度方法、文档频度方法、反文档频率权重法、互信息量方 法、z 2 统计量方法、期望交叉熵、信息增益方法、文本证据权等。 特征频度也叫做词频，指出特征在一篇文本中出现的次数。这是一种 最简单的特征选择方法。 文档频度是指在文本集合中含有特征乙的文本数目在整个文本集合中出 现的概率。它依据的假设是稀有词汇和高频词汇对聚类的贡献不大，有可能是 噪声或者是停用词，因此可以删除。但是，如果某一稀有词汇主要是在某个文 本中出现的话，就有可能把这一类的显著特征过滤掉了。该方法能够去掉低频 词和高频词，从而减少特征空间的维数。当低频词是噪声时这种方法很好，可 以提高聚类效果。有时候低频词也会带有大量的有用信息，这个时候去掉低频 词就会影响聚类的效果。 反文档频率权重法，即t f i d f 方法。该方法是根据某个词的词频t f 和 出现过的文本的频率d f 计算该词在整个文本集合中的权重，然后依据权重来 进行特征选择。权重越高，说明该特征对文本类别的区分能力越好。t f i d f 实 际是t f * i d f ，t f 是词频，i d f 是反文档频率。t f 表示特征乙在该文档中出现 的频率。z 叩= 1 。g ( 叱) ，表示文本集合中所有的文本数，胛表示包含特征 的文档数。i d f 的基本思想是：如果包含某个特征的文档越少，i d f 就越大， 说明特征有很好的类别区分能力。t f i d f 方法的计算公式如下所示： t f i d f ( t k ) 琊( t d i d f ( t k ) 羽纯：! l o 甙南 ( 2 7 ) 为了使t f 值对权重的影响进一步降低，公式( 2 8 ) 对t f 值的计算做出调整。 2 卜甏等 1 0 9 c 高， 仁酌 期望交叉熵方法是通过计算每个特t k 的期望交叉熵，选取预定数目的 最佳特征作为结果的特征子集。计算公式如下： 1 2 江苏大学硕士研究生学位论文 f ( t k m t ) 喜粥l o g 黜 ( 2 9 ) 其中，p ( t 。) 为特征气出现的概率，p ( eh ) 为类别g 在特征气出现情况下 的概率，尸( c ) 为c 的出现概率。 信息增益方法是通过计算特征的信息增益，t k 信息增益大于给定值 时作为特征项。计算公式如下： 整个特征集，的熵为： m ) = p , x l o gp ， 其中，门为特征集中的维数，只为当前特征词条的出现概率。 特征气的熵为： l ( t ) = p k l o g p k 针对特征气的信息增益为： g a i n ( t ，f i ) = ，( ，) 一i ( t ，气) 川刖= 喜南州 ( 2 1 0 ) ( 2 1 1 ) ( 2 1 2 ) ( 2 1 3 ) 互信息量方法是通过计算特征，。的互信息量，当互信息量大于给定值 时作为特征项。特征气和类别c f 的互信息体现了特征与类别的相关程度。特征气 的互信息量为： m i ( t k ) = 喜鹏) l o g ( p ( t , i ( 气)七= l ，r 、。七7 ( 2 1 4 ) ( 2 ) 基于映射的特征选择方法 基于映射的方法是通过空间转换将原始高维空间上的数据映射到一个新 的低维空间上，低维空间上每一维的值是由原空间经过线性或非线性转换得到。 与前面所述方法最大的不同之处在于该方法并不是直接通过判断单词的重要性 然后决定是否保留作为最终的特征，而是保证提取的效果。其主要方法有1 8 j ： 江苏大学硕士研究生学位论文 奇异值分解、主成份分析、因子分析、独立成份分析、随机映射等。 首先，通过一个例子来演示s v d 分解是如何在实际中被巧妙的使用。假设 本来用一个大矩阵 a = 口l l q 口l ” a j l o qn i n a i a 啊n m n ( 2 1 5 ) 来描述一个百万篇文章和五十万词的关联性。这个矩阵中，每一行对应一 篇文章，每一列对应一个词。 在公式( 2 1 5 ) 中，m = l ，0 0 0 ，0 0 0 ，n = 5 0 0 ，0 0 0 。f r , n a o 是字典中第个词在第， 篇文章中出现的加权词频。因此，这个矩阵非常大，有一百万乘以五十万，即 五千亿个元素。 奇异值分解可以把矩阵彳这样一个大矩阵，分解成三个小矩阵相乘如公式 ( 2 1 6 ) 所示。l i - , o n 把a 分解成一个一百万乘以一百的矩阵u ，一个一百乘以一百