（模式识别与智能系统专业论文）基于som算法的中文文本聚类.pdf

硕士论文基于s o m 算法的中文文本聚类 摘要 文本挖掘是数据挖掘领域中一个热门的研究方向。在文本挖掘领域中，文本聚类技 术有助于缩小数据搜索空间，提高查询精度。作为一种无监督的机器学习方法，文本聚 类技术已经成为对文本信息进行有效地组织、摘要和导航的重要手段，为越来越多的研 究人员所关注。可以说，文本聚类的研究具有重要的理论意义和实际使用价值。 自组织特征映射神经网络s o m 在聚类应用中具有自组织映射、可视化好、计算效 率高、聚类效果好等良好特性。因此，本文将s o m 神经网络应用到中文文本聚类中， 研究其在文本聚类中的有关特性。 本文首先介绍了中文文本聚类中几项预处理关键技术：分词、数据清洗、特征词选 取、文本向量表示。在此基础上，本文实现了文本的预处理模型：从已知词汇库中根据 词性构造了一个初步的中文停用词表，用来对已分好词的文章进行停用词筛选。在剩下 的那些词中，根据词的有效性评价，选取出一定数量的特征词。基于这些特征词，利用 向量空间模型v s m ，把每篇文章表示成计算机能够处理的实数向量。 本文继而研究了对于类别已知的文本，利用s o m 网络和已知类别标注方法，实现 先验类别知识指导下的文本聚类。针对传统s o m 算法聚类效果不佳的情况，本文使用 核s o m 算法进行改进，并且通过实验比较了传统s o m 算法和核s o m 算法在文本聚类 中的聚类精度和鲁棒性。 如果文本的类别事先是未知的，单纯使用s o m 算法是无法实现自动聚类的。因此， 本文将s o m 网络和k 均值聚类算法相结合，研究了类别未知文本的两阶段自动聚类。 相比k 均值聚类模型：前者聚类速度快，聚类结果可视化好，但聚类精度依赖于第一阶 段s o m 网络在特定训练样本集上的训练效果。 关键词：聚类，文本聚类，s o m 算法，核s o m 算法，k 均值 硕士论文 a b s t r a c t t e x tm i n i n gi sa ，p o p u l a rr e s e a r c hb r a n c ho fd a t am i n i n gd o m a i n t e x tc l u s t e r i n gh e l p st o r e d u c et h es e a r c hs p a c eo fd a t aa n di m p r o v et h eq u e r ya c c u r a c yi nt h ed a t am i n i n gd o m a i n a s a nu n s u p e r v i s e dm a c h i n el e a r n i n gm e t h o d ，t e x tc l u s t e r i n gt e c h n i q u eh a sb e c o m ea ni m p o r t a n t m e t h o dt oo r g a n i z ea n ds u m m a r i z et e x ti n f o r m a t i o n m o r ea n dm o r er e s e a r c h e r sh a v ef o c u s e d o nt e x tc l u s t e r i n gb e c a u s eo fi t sg r e a tv a l u ei nb o t ht h e o r ya n da p p l i c a t i o n t h es e l fo r g a n i z i n gm a pn e u r a ln e t w o r k ( s o m ) h a s m a n ya d v a n t a g e si ns e l f - o r g a n i z i n g ， c l u s t e r i n gv i s u a l i z a t i o n ，c o m p u t i n ge f f i c i e n c ya n dc l u s t e r i n gp r e c i s i o n t h e r e f o r e ，w eu s e s o mn e t w o r ki nc h i n e s et e x tc l u s t e r i n ga n da n a l y z et h ec h a r a c t e r i s t i co fs o mi nc l u s t e r i n g w ef i r s t l yi n t r o d u c es o m ek e yt e c h n i q u e si nt e x tp r e p r o c e s s i n g ：w o r ds e g m e n t a t i o n ， w o r df i l t r a t i o n ，c h a r a c t e rw o r de x t r a c t i o na n dt e x te x p r e s s i n g a f t e rt h a t ，w ec a r r yo u tat e x t p r e p r o c e s s i n gm o d e l ：f i r s t l y , w em a k eas t o p w o r dl i s tf r o ma ne x i s t e dv o c a b u l a r ya c c o r d i n g t op a r to fs p e e c h t h e n ，w er e m o v es t o pw o r d sf r o ma l lt h ew o r d so ft e x t sa n dc h o o s ea n u m b e ro fc h a r a c t e rw o r d sa c c o r d i n gt os o m em e a s u r e m e n t a tl a s t ，w eu s ev e c t o rs p a c e m o d e l ( v s m ) t oe x p r e s se v e r yt e x ti n t or e a lv e c t o r s a f t e rt h ep r e p r o c e s s i n g ，w eu s es o mn e t w o r ka n dc l a s sl a b e lm e t h o df o rt e x tc l u s t e r i n g u n d e rt h ek n o w ni n f o r m a t i o no ft e x tc l a s s w eu s et h ek e r n e l s o mt oi m p r o v ec l u s t e r i n g e f f e c t t h e nw ed os e v e r a le x p e r i m e n t st oc o m p a r ec l u s t e r i n gp r e c i s i o na n dr o b u s t n e s s b e t w e e nt h eo r i g i n a ls o ma n dk e r n e l s o m h o w e v e r , i ft h ei n f o r m a t i o no ft e x tc l a s si su n k n o w nb e f o r e h a n d , w ec a n td ot e x t c l u s t e r i n ga u t o m a t i c a l l y s o ，w ei n t e g r a t es o mn e t w o r ka n dk - m e a n sc l u s t e r i n gm e t h o dt o c a r r yo u tat w o - p h a s et e x tc l u s t e r i n g t h i st w o p h a s em o d e lh a ss o m ea d v a n t a g e so v e r k - m e a n sm o d e li nc l u s t e r i n gv i s u a l i z a t i o na n dc o m p u t i n ge f f i c i e n c y b u tt h ef i n a lc l u s t e r i n g r e s u l td e p e n d so nt h et r a i n i n ge f f e c to ft h es o mn e t w o r k k e yw o r d ：c l u s t e r i n g ，t e x tc l u s t e r i n g ，s o m ，k e r n e l - s o m ，k - m e a n s 声明 本学位论文是我在导师的指导下取得的研究成果，尽我所知，在 本学位论文中，除了加以标注和致谢的部分外，不包含其他人已经发 表或公布过的研究成果，也不包含我为获得任何教育机构的学位或学 历而使用过的材料。与我一同工作的同事对本学位论文做出的贡献均 已在论文中作了明确的说明。 2 0 0 3 年月哆日 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅 或上网公布本学位论文的全部或部分内容，可以向有关部门或机构送 交并授权其保存、借阅或上网公布本学位论文的全部或部分内容。对 于保密论文，按保密的有关规定和程序处理。 研究生签名：二孳单 。孵 占月 哆 日 硕士论文基于s o m 算法的中文文本聚类 第1 章绪论 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 ) ，又称为数据库中的知识发现( k n o w l e d g ed i s c o v e r yi n d a t a b a s e ，k d d ) 1 1 ，就是从大量数据中获取有效的、新颖的、潜在有用的、最终可理解 的模式的非平凡过程。简单的说，数据挖掘就是从大量数据中提取或“挖掘”知识。它 是一门很广义的交叉学科，汇聚了数据库、人工智能、机器学习、统计学、模式识别、 可视化、并行计算和神经网络等不同学科和领域，近年来受到各界的广泛关注。在各种 形式的信息中，大部分信息还是以文本形式存在的，所以文本挖掘成为数据挖掘中很重 要的一个分支。 聚类是根据数据的不同特征，将其划分为不同的数据类。它的目的是使得属于同一 类别的个体之间尽可能相似，而不同类别上的个体间尽可能不同。聚类技术是数据挖掘 领域的重要分析手段之一，文本聚类技术是文本挖掘领域的重要研究方向。特别是在 w e b 文本挖掘中，研究文本的聚类技术可以缩小搜索空间，提高查询精度。文本聚类技 术已经成为对文本信息进行有效地组织、摘要和导航的重要手段，为越来越多的研究人 员所关注。 1 2 国内外文本聚类研究现状 国外对英文文本聚类已经进行了大量的研究，并已将文本聚类应用在文本挖掘和信 息检索等领域，典型应用如下 4 3 1 ： ( 1 ) 文档聚类可以作为多文档自动文摘等自然语言处理应用的预处理步骤。其中比 较典型的例子是哥伦比亚大学开发的多文档自动文摘系统n e w s b l a s t e r 。n e w s b l a s t e r 将 每天发生的重要新闻进行聚类处理，并对同主题文档进行冗余消除、信息融合、文本生 成等处理，从而生成一篇简明扼要的摘要文档。 笫1 章绪论硕士论文 ( 2 ) 对搜索引擎返回的结果进行聚类，使用户迅速定位到所需要的信息。比较典型 的系统有v i v i s i m o ( h t t p ：w w w v i v i s i m o c o r n ) 和i n f o n e t w a r e ( h t t p ：w w w i n f o n e t w a r e c o m ) 等。系统允许用户输入检索关键词，而后对检索到的文档进行聚类处理，并输出各个不 同类别的简要描述，从而可以缩小检索的范围，用户只需关注比较感兴趣的主题。 ( 3 ) 对用户感兴趣的文档( 如用户浏览器c a c h e 中的网页) 聚类，从而发现用户的兴趣 模式并用于信息过滤和信息主动推荐等服务。 ( 4 ) 数字图书馆服务。通过s o m ( 自组织映射) 等方法，可以将高维空间的文档向量 拓扑保序地映射到二维空间，使得聚类结果可视化和便于理解，如s o m l i b 系统。 ( 5 ) 文档集合的自动整理。如s c a t t e r g a t h e r 是一个基于聚类的文档浏览系统。而微 软的j i - r o n gw e n 等人则利用聚类技术对用户提出的查询记录进行聚类，并利用结果更 新搜索引擎网站的f a q 。 文本聚类算法有很多，其中基于自组织神经网络( s o m ) 的文本聚类算法是一种对大 规模文档进行聚类特别适合的方法。由s o m 的创始人t k h o n e n 教授带领的一批学者提 出了一种基于s o m 的网络信息组织方法w e b s o m 2 1 。w e b s o m 是一种基于s o m 神经网络算法的文本信息组织与检索的方法。它根据一定的语义关系对特定数据库中的 纯文本文献进行自动组织，形成一个有序的数据空间，并将该空间的元素关系投影到一 个二维平面上，形成一个可视地图，供用户浏览查询。如有兴趣，可参考w e b s o m 网 上测试系统，网址是：h t t p ：w e b s o m h u t f f f w e b s o m 。 这种基于s o m 的文本聚类算法应用于英文文本的研究较多，中文文本的研究方面 相对较少d s , 4 2 1 。基于s o m 的文本聚类改进算法的研究也较多，d m e r k l 等人提出 l a b e l s o m 方法 3 7 1 和张毓敏【3 8 】提出用关键词标注法对文本聚类中生成的映射图进行标 注，傅伟鹏【4 2 】提出结合多层s o m 和模糊聚类方法进行多层次文本聚类，同时采用关键 字对映射图进行标注，增加地图的可读性。另外，很多学者针对s o m 算法本身的不足， 也提出了不少改进后的s o m 变体算法【2 7 。2 9 ，3 3 1 。 1 3 本文工作及结构安排 1 3 1 本文工作 本文研究了基于自组织神经网络s o m 的中文文本聚类，主要包括两方面的工作： 第一，对于类别已知的文本，利用s o m 算法和类别标注方法，实现文本聚类； 第二，对于类别未知的文本，利用s o m 算法和k 均值算法，实现文本的两阶段自动聚 类。 另外，使用s o m 算法的改进算法核s o m 算法改善上述文本聚类的效果，并 通过实验讨论了s o m 算法和核s o m 算法在文本聚类中的鲁棒性。 2 硕士论文基于s o m 算法的中文文本聚类 1 3 2 章节安排 第一章：绪论。介绍了论文的选题背景及意义，国内外文本聚类的研究现状。 第二章：聚类综述。综合介绍了聚类的相关概念聚类的定义及应用，聚类的主 要方法，聚类中相似性度量，聚类有效性。 第三章：文本聚类的关键技术。介绍了文本聚类的一般模型，阐述了文本聚类的关 键技术分词、数据清洗、特征词选取、文本表示，介绍了文本聚类的有效性评价 标准。 第四章：自组织特征映射神经网络s o m 。详细介绍了s o m 网络的结构，s o m 算 法的工作原理，s o m 具体算法描述，s o m 网络的性能度量，s o m 网络的特点及应用。 第五章：核s o m 算法( k e r n e l s o m ) 。简要介绍了核方法和核函数的相关知识， 详细阐述了核s o m 算法，并从能量函数的角度对其进行了详细推导。 第六章：s o m 算法和核s o m 算法在文本聚类中的实验讨论。详细阐述了本文具 体的文本预处理过程，s o m 算法和核s o m 算法的具体实现步骤及实验结果讨论。 第七章：文本的两阶段聚类。简要介绍了文本两阶段聚类方法，详细阐述了本文 的两阶段聚类系统工作流程，并进行实验分析。 第八章：结论与展望。对本文工作进行总结，指出其中不足与可改进之处，展望下 一步的工作。 3 第2 章聚类综述硕士论文 第2 章聚类综述 2 1 聚类定义及应用 聚类是数据挖掘的基本形式之一，聚类与分类不同：分类是一种监督学习，其 类别是根据应用的需要事先确定的，根据表示事物特征的数据可以识别其类别；聚 类是一种非监督学习，其类别不是人为指定的而是分析数据的结果，聚类完全由计 算机自动进行，不需要人工干预。聚类通过比较数据的相似性和差异性，能发现数 据的内在特征及分布规律，从而获得对数据更深刻的理解与认识。 聚类的结果是将数据对象分组成为多个类或簇，目标是使得在同一个簇中的对 象之间具有较高的相似度，而不同簇中的对象差别较大。 簇( c l u s t e r ) ：一个数据对象的集合。在同一簇中，对象具有相似性，不同簇中， 对象之间是相异的。 聚类是数理统计中研究“物以类聚”的一种方法，它是多元分析的一个分支， 目前己被广泛地应用于信息检索、模式识别、机器学习、图象处理等研究领域。在 各种领域，可以从时间上聚类，也可以从地域上聚类，还可以从性质、成因或形态 上进行聚类。 2 2 聚类主要方法 现有的聚类方法主要分为六类：分层法、分割法、密度法、网格法、基于模型 的方法、基于模糊的方法。 2 2 1 分层聚类法 把类别看作是有层次的，即随着类别层次的变化，类别中的对象也相应发生变 化。分层聚类结果形成一棵类别树，每个类结点还包含若干子结点，兄弟结点是对 其父结点的划分，因此该方法允许在不同的粒度上对数据进行分类。按照类别树的 生成方式，可将分层聚类法分为两种：一种是融合方法( 自底向上法) ，另一种是分 裂方法( 自顶向下法) 。融合方法从每个单个对象出发，先将一个对象看成单独一类， 然后反复合并两个或多个合适的类别。分裂方法则恰恰相反，从整个集合出发看成 一类，然后反复将结点分裂出新的子结点。分层聚类法循环进行直至满足停止条件， 分层聚类法不必事先输入聚类类别数。 优点：第一，适用于任意形状；第二，适用于任意形式的相似度或距离形式； 第三，固有的对聚类粒度的灵活性。 缺点：第一，终止条件不很精确；第二，一旦聚类结果形成，一般不再重新构 建来提高聚类性能；第三，难以适应动态数据集。 4 硕士论文 基于s o m 算法的中文文本聚类 2 2 2 分割聚类法 一般是通过优化一个评价函数把数据集分割成k 个部分。由于在计算上不可能 搜索全部可能子集空间，因此往往采用一定迭代优化的启发式方法，这就意味着反 复在k 类之间重新定位每类的类别中心，以及重新分配每类中的对象。与分层聚类 法不同的是这类算法反复调整聚类结果来进行聚类优化。 主要有两种方法：k - m e a n s 聚类法和k m e d o i d 聚类法【3 1 。 k m e a n s 方法的优点：第一，对数值属性有很好的几何和统计意义：第二，对 顺序不太敏感；第三，对凸型聚类有较好结果；第四，平行运行；第五，可在任意 范围内进行聚类。 k - m e a n s 方法的缺点：第一，对初始聚类中心选取较敏感，往往得不到全局最 优解，而常常得到的是次优解；第二，关于k 值的确定没有可行的依据；第三，该 算法容易受到异常点的干扰；第四，缺少可伸缩性；第五，聚类结果有时会失衡。 2 2 3 基于密度的方法 利用数据密度函数进行聚类。这种算法认为，类别是向任意方向按相同密度扩 张的连通区域。因此基于密度的聚类算法可以发现任意形状的类别，同时此算法对 噪声有自然的抵制作用。这种算法主要需要考虑数据空间的密度、连通性与边界区。 其中典型的基于密度的算法是d b s c a n 算法【4 】，其基本思想是：对于一个类 中的每一对象，在其给定半径( 用r 表示) 的领域中包含的对象数目不小于某一给 定的最小数目，即在d b s c a n 中，一个类被认为是密度大于一个给定的阈值的一 组对象的集合，能够被其中的任意一个核心对象所确定。 d b s c a n 存在如下缺点：一是随着数据量的增大，需要有很大的内存支持与 i o 开销。二是没有考虑数据密度和类别距离大小的不均匀性，很难得到高质量的 聚类结果。 2 2 4 基于网格的方法 利用空间量子化方法把数据分到有限个单元进行聚类，效率高，与数据大小无 关，仅与单元数有关。s t i n g 5 j 就是这样一种方法。为了减少搜索复杂度，需要考 虑多边形分段区域。一个分段区域就是空间中的一个划分的小的超立方体，而利用 划分空间进行聚类的方法通常就称为网格聚类算法。每一个分段区域就称为一个单 元。网格聚类算法把对数据的分割转换成对空间的分割。数据分割是通过数据点之 间的关系导致空间的分割而产生的，但是空间分割则是基于输入数据累加的空间小 超立方体( 网格) 。本质上，它经过了如下的转换过程：数据一网格数据一空间分割 一数据分割。这样不直接对数据进行处理的优点是网格数据的增加使得基于网格的 聚类技术不受数据次序的影响。基于网格的聚类算法适用于各种类型属性的数据， 不像基于密度的聚类算法仅对数值属性的数据有较好的效果。 5 第2 章聚类综述硕士论文 2 2 5 基于模型的方法 基于模型的方法主要有两类：统计学方法和神经网络方法。 概念聚类1 6 是一种统计学方法。概念聚类是机器学习中的一种聚类方法，给出 一组未标记的对象，它产生对象的一个分类模式。与传统的聚类不同，概念聚类除 了确定相似对象的分组外，还向前走了一步，为每组对象发现了特征描述，即每组 对象代表了一个概念或类。因此，概念聚类是一个两步的过程：首先进行聚类，然 后给出特征描述。概念聚类的绝大多数方法采用了统计学的途径，在决定概念或聚 类时使用概率度量。 神经网络方法将每个类描述为一个标本，标本作为聚类的原型，不一定对应一 个特定的数据实例或对象。根据某些距离度量，新的对象可以被分配给标本与其最 相似的类，被分配给一个类的对象的属性可以根据该类的标本的属性来预测。 基于模型的方法为每个簇假定了一个模型，寻找数据对给定模型的最佳拟合。 一个基于模型的算法可能通过构建反映数据点空间分布的密度函数来定位聚类。它 也基于标准的统计数字自动决定聚类数目，考虑“噪声”数据或孤立点，从而产生 健壮的聚类方法。 2 2 6 基于模糊的方法( f u z z yc l u s t e r i n g ) 传统的聚类把每个样本严格地划分到某一类。随着模糊集理论的提出，传统聚 类被推广为模糊聚类。在模糊聚类中，每个样本不再仅属于某一类，而是以一定的 隶属度属于每一类。换句话说，通过模糊聚类分析，得到了样本属于各个类别的不 确定性程度，即建立起了样本对于类别的不确定性的描述，这样就更能准确地反映 现实世界。基于目标函数的模糊聚类方法首先由r u s p i n i 提出【7 】，但真正有效的算法 f c m 却是由d u l l l l 【8 】给出的，由b e z d e k 9 】将其进一步扩展，建立起了模糊聚类理论。 从此，模糊聚类蓬勃发展起来，目前已经形成了庞大的体系。 综上所述，在聚类分析研究领域存在各种各样的算法，它们采用了不同的模型 对数据进行了假定，并选择不同的最优判定准则来寻找聚类，因而它们针对不同的 数据分布各有所长。在实际应用中，往往要针对某种聚类算法中的不足进行改进， 或者结合几种聚类算法灵活使用。 2 3 聚类相似性度量 2 3 1 距离函数 聚类分析按照样本在性质上的亲疏远近的程度进行分类。为了使类分得合理， 必须描述样本之间的亲疏远近的程度。设使用m 个指标特征变量来描述样本，那么 我们就可以把每个样本点看作m 维空间中的一个点，进而使用某种距离函数来表示 样本点之间相似性，距离较近的样本点性质较相似，距离较远的样本点则差异较大。 6 硕士论文 基于s o m 算法的中文文本聚类 但是，只有满足特定条件的函数才能成为距离函数。设o 是样本点集合，如果 函数d ：q q 寸r 满足以下条件，我们都称之为距离函数【捌。 正定性：d ( x ，y ) 0 d ( x ，x ) = 0 对称性：d ( x ，) ，) = d ( y ，x ) 三角不等式：d ( x ，y ) + d ( y ，z ) d ( x ，z ) 聚类分析中常常采用以下3 种距离函数： ( 1 ) 明氏( m i n k o w s l d ) 距离 广m- l u q d 。( 石，y ) - - i ( x ，一k ) 9i l 瑚j ( 2 3 1 1 ) 当q 取1 、2 、无穷大时，则分别得：绝对值距离，欧式( e u e l i d ) 距离，切比雪夫 ( c h e b y s h e v ) 距离。 因为明氏距离直观，计算简便，是实际应用中采用最多的一类距离函数。其中 欧式距离则更为常用。但是，当各变量的测量值相差悬殊时，采用明氏距离并不合 理( 会产生“大数吃掉小数 的现象) ，需要先对数据标准化，然后用标准化后的数 据计算距离。 ( 2 ) 马氏( m a h a l a n o i s ) g 臣离 d ( x ，即= 一d r 一幸一即 ( 2 3 1 2 ) 其中，是样本矩阵的协差阵，是总体分布的协差估计量。 马氏距离是明氏距离的一个推广，它对于一切线性变换是不变的，非常适合解决 协方差不相等以及特征之间相互联系的情况。但由于计算复杂，实际应用并不是那 么广泛。 ( 3 ) 兰氏( l a n e e ) 距离 她功2 喜潲渤 2 3 2 相似系数函数 聚类分析中不仅要将样本点聚类，在有些场合还需要对特征变量进行聚类。特 征变量之间的相似性测度除了可以使用上述的距离函数之外，更常用的是相似系数 函数。 如果一个函数c ：v x v 专【一1 ，l 】满足以下条件，我们就称之为相似系数函数【1 1 】。 ic ( x ，y ) l 1 c ( x ，x ) = 1 c ( x ，y ) = c ( l n 7 第2 章聚类综述硕士论文 c ( x ，y ) 越接近1 ，两个特征变量间的关系越密切，越相似。 经常采用的相似系数有以下两种： a 夹角余弦 叫肛一x o y = 高斋2 ， 这是受相似形的启发而来的，夹角余弦函数忽略各个向量的绝对长度，着重从 形状方面考虑它们之间的关系。当两个向量的方向相近时，夹角余弦值较大，反之 则较小。特殊地，当两个向量平行时，夹角余弦值为1 ；而正交时余弦值为0 。 b 相关系数 e l ( x , 一_ ) 木( z 一勒 c ( z 耻苊零丽 ( 2 - 3 2 2 相关系数是对向量做标准差标准化后的夹角余弦。它表示两个向量的线性相关程 度。 2 4 聚类有效性 评判聚类结果优劣的过程，称为聚类的有效性分析。对聚类有效性的评价分为 两个方面：耦合性和紧凑型【1 2 1 。耦合性是指不同聚类之间的相似程度，不同聚类之 间相似程度越小，耦合性越好。紧凑性是指同一个聚类的文本之间的相似度，同一 个聚类中文本之间的相似度越大，紧凑性越好。一般来讲，耦合性和紧凑型都好的 聚类才是最优聚类。 对于聚类的有效性分析，通常有三大评判标准【1 2 1 ：内在标准只根据聚类对 象内在的特征属性来检验聚类结果；外在标准检验聚类结果与已知的分类模型 的吻合程度；相对标准上述两类标准都是以统计检验为基础的，其计算量较大。 相对标准不要求统计检验，其基本思想是根据预先定义的标准来寻找最佳的聚类方 式。 2 4 1 内在标准 下面，内在标准下的评价函数也称作聚类有效性函数。近些年来提出的聚类有 效性函数主要用来评价聚类效果的优劣和判断簇的最优个数。而理想的聚类效果是 具有最小的簇内距离和最大的簇间距离。聚类有效性函数可分成两类： 第一类为基于密度的有效性函数：主要思想是计算每个簇的密度，代表函数有 分裂函数( p c ) u 引。 8 硕士论文 基于s o m 算法的中文文本聚类 第二类基于距离的有效性函数f 1 2 】：主要思想是计算簇内距离和簇外距离的比例。 这类包括d b 函数，d u n n 函数( d i ) ，i 函数，c a l i n s k ih a r a b a s z 函数( c h ) 。 以下介绍效果较为显著的c h 函数和i 函数： ( 1 ) c h 函数 c h = 垒塑二1 2 唧( n j j ) ( 2 4 1 1 ) k o n ：簇间距离度量，= 乃i l 竹- u1 1 2 - 簟l k o w ：簇内距离度量，c r w = | l 薯心0 2 | li f f i l ( 2 4 1 2 ) ( 2 4 1 3 ) n j ：第歹个簇中的元素个数， 捍：整个数据集中的元素个数，k ：簇的个数 ，：第，个簇的均值 ， ：整个数据集的均值 c h 函数计算簇间距离和簇内距离唧的比例，c h 值越大，代表聚类效果越 好。 ( 2 ) i 函数 妖幼：晕争， 髟& ( 2 4 1 4 ) k 砬2 嘴帆一刚 ( 2 4 1 5 ) 巨鳓| | 毛一一0 扭1 闰 ( 2 4 1 6 ) k ：簇的个数，”：整个数据集中的元素个数，a ：常数 p ：调整不同的簇结构的对比p = 1 ，2 ， 随着k 值增大，1 ( k x 最) 减小，而4 值增大。这两项一个增加，一个减少， 而q 增加的幅度大1 ( k x 最) 减少的幅度。使聚类有效性函数，( 七) 最大的k 值， 就是最优的簇个数。 2 4 2 外在标准 下面，介绍外在标准常用的评价系数【1 4 】：j a c c a r d 系数、f m 系数、f 1 聚类系数。 设数据集实际的聚类结果p = 丑，最只) ，已知的分类集合 c = 进行划分，从而得到k 个 簇的集合c = q ，乞，气) 。文本聚类的一般流程如图所示： ，、 l i 分 特征词文本聚类 聚类 未分词 入 、 卜、 叫 词 提取 向量表示 工具 爿 结果 文本集 ，_ 图3 1 文本聚类流程图 3 1 分词 3 1 1 分词含义 分词技术从语言文本结构上来讲大致有两类：一类以英文为代表的西方语言文本， 其文本中的词组以空格作为自然间隔，从语义准确性及技术复杂度来讲都比较简单。另 一类是以汉语为代表的东亚语言文本，由于文本是由连续文字组成，缺乏有效的间隔， 虽有句、段分隔，但在进行机器语言学习、文本语义理解分析过程中都需以词组为最小 单位。因此东亚文本语言实现分词技术相对西方文本语言来讲，更加的复杂和困难。 中文分词技术是一种将连续的汉语文本序列按一定规则拆分为具有独立语义的词组 的过程。中文分词技术是语言文本处理技术的基础，其广范应用于互联网信息检索、数 据库信息查询、智能聊天机器人、文本校对、自动翻译、自动摘要、自动分类及信息加 工处理等各个领域。 3 1 2 分词方法 现有的分词方法可以分为三大类型：机械分词方法、基于理解的分词方法和基于统 计的分词方法。 ( 1 ) 机械分词方法 又称为字符串匹配的分词方法，它是按照策略将待分析的汉字字符串与一个“充分 大的机械词典的词条进行匹配，如果在词典中找到某个字符串，则匹配成功。机械分 词方法很简单，容易实现，但是由于自然语言表达的方式丰富多彩，汉语语句结构的复 杂性，新的词汇不断出现，这使得机械分词方法面临着很多问题。例如：一词多义问题、 歧义问题和新出现词识别的问题，这些问题直接影响了分词的准确率。 ( 2 ) 基于理解的分词方法 通过让计算机模拟人对句子的理解，达到识别词的效果。基本思想就是在分词的同 第3 章文本聚类关键技术硕士论文 时进行句法、语义分析，利用语法信息和语义信息来处理歧义现象。它通常包括三个部 分：分词子系统、句法语义子系统、总控部分。在总控部分的协调下，分词子系统可以 获得有关词、句子等的句法和语义信息来对分词歧义进行判断，即它模拟了人对句子的 理解过程。这种分词方法需要使用大量的语言知识。但是由于汉语语言知识的复杂性， 难以将各种语言信息组织成机器可以直接读取的形式，所以目前基于理解的分词系统还 处于试验阶段。 ( 3 ) 基于统计的分词 又称为是无词典分词，该方法是通过大规模真实文本的统计，让计算机自己判断什 么是词，它的主要思想是词是稳定的字的组合。该方法有一定的局限性，会经常抽出一 些共现频度高、但不是词的常用字组。 以上三种方法哪一个分词算法准确度高，目前尚无定论。对于一个成熟的分词系统 来说，不可能单独依靠某一个算法来实现，都需要综合不同的算法，在实际的应用中， 要根据具体的情况来选择不同的分词方案。 3 2 数据清洗( 停用词处理) 3 2 1 介绍 无论在汉语还是在英语中，都存在一些对文本内容识别意义不大的词，在文本挖掘 中，称之为停用词( s t o pw o r d ) 。这些词没有什么意义，而且在各类文本中出现的频率都 很高，在特征选择或者计算相似度的过程中会引入很大的误差，可以看作是一种噪音。 最简单的例子是汉语中“的 这个字，以及英语中“a 这个词。他们没有具体的意义， 不能体现文本所表示的内容，但在几乎所有的文本中都会出现，如果在聚类过程中考虑 到这些词，那么文本之间的相似性不能表现出内容的相似性，而是一些无意义的相似性， 这不是我们所希望的。 英文停用词的研究取得了一些研究成果，目前已经有了一些公开发表的英文停用 词表，其中比较著名的是v 趾r i j s b e r g e n 发表的停用词表【1 5 】以及b r o w nc o r p u s 停用词 表【1 6 】。但中文词汇量比英文词汇量要大的多，再加上歧义词的影响，使得中文停用词表 的构造非常困难。因此，关于中文停用词的研究成果还非常少，目前还没有一个被广泛 认可的中文停用词表，往往需要自己手工构造适合特定词语集的停用词表。 3 2 2 停用词选取方法 停用词自动抽取方法为了找出噪声词，需要一些标准用于估计词的有效性。常用的 评估因子有：文档频数( d f ) 、词频( t f ) 、熵、联合熵。 文档频数d f ( d o c u m e n tf r e q u e n c y ) d f 是一种简单的评估函数，其值为训练集合中包含此单词的文本数。d f 评估函 1 2 硕士论文 基于s o m 算法的中文文本聚类 数的理论假设是当一个词在大量文本中出现时，这个词通常被认为是噪声词。 词频t f ( t e r mf r e q u e n c y ) t f 同样是一种简单的评估函数，其值为训练集合中此单词发生的词频数。t f 评估 函数的理论假设是当一个词大量出现时，通常被认为是噪声词。 熵计算e c ( e n t r o p yc a l c u l a t i o n ) 根据信息论，定义基于单词在文本中出现的平均信息量形( 们： 形( w ) = l + 南善只) 埘鼻( 叻】 ( 3 2 21 ) 式中只( 川为单词w 在文本f 中出现的概率。 熵形( w ) 的值越大，说明单词w 所表示的平均信息量越大，单词w 就越普通，就可 以当作是噪声词。 联合熵u e ( u n i o ne n t r o p y ) 考虑到：当一个词在句子中出现的平均信息量和包含该词的句子在文本中的平均信 息量都较大时，表示该词较为普通。 定义两者之和为联合熵矿( 们： 形( 叻= 日( 叻+ 日( ji 们( 3 2 2 2 ) 单词w 在句子中出现的平均信息量抒( 叻： i _ 日( 川= 一p ( w ) l o g p j ( w ) ( 3 2 2 3 ) 包含该单词w 的句子在文本中的平均信息量h ( si 叻： 日0 i 叻= 一0 0 1 w ) l o g p z ( s l w ) ( 3 2 2 4 ) l = l 单词w 在句子，中发生的概率弓( 叻： ( 忉：堕 ( 3 2 2 5 ) 乃( 叻 j = l 包含单词w 的句子在文本，中发生的概率丑( s i 忉： 丑0 1w ) ：孚盟生( 3 2 2 6 ) f , ( s l w ) ，毒l 式中：乃( w ) 为单词w 在句子中出现的频率， n 为句子数； 石( s1w ) 为包含单词w 的句子占在文本z 中出现的频率，m 为文本数。 1 3 第3 章文本聚类关键技术硕士论文 3 3 特征选取 3 3 1 介绍 一般，构成文本的词汇数量是相当大的，如果在此基础上构造文本向量，维数也相 当大，可以达到几万维，很显然需要进行维数压缩的工作，这样做的目的主要有两个： 第一，为了提高程序的效率，提高运行速度。第二，为了提高最终分类或聚类的精度。 因为每个词汇对区分不同文本的贡献是不同的，我们需要筛选出区分能力较强的词作为 特征词。有几个筛选原则供参考：一是应当选取包含语义信息较多，对文本的表示能力 较强的词；二是文本在这些特征词上的分布应当有较为明显的统计规律性，这样将适用 于信息检索、文档分类等应用系统；三是特征词选取过程应该容易实现，其时间和空间 复杂度都不太大。 目前存在多种筛选特征项的算法，但是由于大部分的筛选特征项的算法【1 8 】，例如信 息增益( i n f o r m a t i o ng a i n ) 、期望交叉熵( e x p e c t e dc r o s se n t r o p y ) 、互信息( m u t u a l i n f o r m a t i o n ) 等，都是基于这样一个前提：己知分类信息。而聚类算法是不可能在聚类前 给出已知的分类信息的，所以我们需要一些标准用于估计词的有效性。 3 3 2 特征词选取方法 参考停用词的抽取方法，特征词的选取方法也基于两个评价因子：词频t f 和文档 频数d f ，主要有下面几种方法： ( 1 ) 词频排序法 矿叮) - - e ：( r ，9 3 f 在整个文本集中统计每个词丁的总出现频数矿仃) ， 为特征词。 ( 3 3 2 1 ) 选取其中频数最高的n 个词作 ( 2 ) 词权重排序法 它依据某个词的词频t f 和其出现过的文本频数d f ，来计算该词在整个文本集合中的 权重，依据权重来进行特征选取的。权重越高，说明该词对文本的区分能力越强，否则 其区分能力则越弱。 ( a ) t f * i d f 法 t f l d f ( t ) = 勿r ( t ) x l o g 布( 3 3 2 2 r 矿仃) 词t 在整个文本集中的总频数， 1 0 甙历象_ ) ：称作词t 的倒文档率， d f ( t ) ：包含词t 的文本数， ：整个文本集中文本数。 ( b ) 改进的t f * i d f 法 1 4 硕士论文 基于s o m 算法的中文文本聚类 为了防止某些词总频数过高带来的负面效应( 淹没倒文档率的影响) ，在实际应用 中往往对矿仃) 进行弱化处理，比如开平方、取对数等，得到如下公式： 3 4 文本表示 嬲( 耻x l o g ( 尚 卿( z ) = l o g ( 1 + 们) ) x l o g ( 蒜) ( 3 3 2 3 ) ( 3 3 2 4 ) 前面几个小节的介绍可以看作是文本的预处理过程，其目的之一就是把半结构化或 者是非结构化的文本对象，转换成便于计算机处理的结构化数据。通过分词、特征选取等 步骤的处理，接下来就可以对文本进行具体表示了。 3 。4 1 向量空间模型v s m 向量空间模型s m ) f 1 明是近年来应用最多且效果较好的方法之一。它的基本思想是 用词袋法( b a go