（计算机应用技术专业论文）基于向量空间模型的文本聚类算法研究.pdf

摘要 文本聚类在文本挖掘和信息检索系统中发挥着重要的作用。这种技术可以改 善检索性能、提供导航浏览机制、发现相似文本等。因此，文本聚类已成为一种 处理和研究文本的重要技术。 文本聚类的首要问题是如何将文本内容这种半结构或无结构化的数据表示成 为结构化数据。目前多数文本聚类算法都是以向量空间模型( v s m ) 为基础的。 这种文本表示方法非常简单，但却引发了高维稀疏的问题。而且，基于向量空间 模型的聚类算法都没有很好地解决文本数据所特有的两个自然语言问题：近义词 和多义词。所有这些问题都极大干扰了文本聚类算法的效率和准确性，使文本聚 类的性能下降。虽然人们提出通过向量空间权重调整和降维技术来解决上述问题， 但是这些方法都有自身的缺点。向量空间权重调整法实际上并没有解决以上问题， 它只能非常有限地提高文本聚类的性能。降维法虽然解决了高维稀疏问题，但是 降维的代价一般都非常大。为了避免上述问题的产生，本人做了以下工作：一。 第一：提出了一种优化初始聚类中心的舡平均聚类算法。该算法从传统缸平 均算法对初始聚类中心的敏感性分析出发，结合一种改进的遗传算法和网络中心 数学模型对初始聚类中心进行优化，有效的解决了算法对初始聚类中心的敏感性 问题。 第二：在向量空间模型中，由于文档集所对应的是一个高阶的稀疏矩阵，因 此计算量巨大；同时由于词间多义性和同义性的存在，因而会使不相关的文档被 聚类在一起，而相关的文档不能聚类在一起。因此本文提出了一种基于词关联语 义的双向文本聚类迭代算法来解决这一问题，该算法先以句子为单位建立词之间 的关联矩阵，考虑了词条本身所蕴含的含义以及词与词之间的关系，然后分别对词 及文挡进行聚类，通过词的聚类来调整文档的聚类，反过来也通过文档聚类来调 整词的聚类，经过如此反复迭代来调整聚类结果。经实验证明调整之后的聚类簇 内聚性更强，类间区分度更大，聚类结果更为准确，能有效的消除同义词带来的 问题。 【关键词】尽平均聚类算法，文本聚类，向量空间模型，聚类中心 a b s t r a c t t e x td o c u m e n tc l u s t e r i n gp l a y sa ni m p o r t a n tr o l ei nt e x tm i n i n ga n di n f o r m a t i o n r e t r i e v a ls y s t e m s i tc a ni m p r o v et h er e s u l to fq u e r i e s ；p r o v i d ei n t u i t i v en a v i g a t i o na n d b r o w s i n gm e c h a n i s m s ；a n df i n ds i m i l a rt e x t s i nt e x tc l u s t e r i n ga p p l i c a t i o n s ，t h et e x to rd o c u m e n ti sa l w a y sr e p r e s e n t e du s i n g v e c t o rs p a c em o d e l t h i sr e p r e s e n t a t i o ni sv e r ys i m p l e ，b u tr a i s e so n es e v e r ep r o b l e m ： t h eh i 曲d i m e n s i o n a l i t yo ft h ef e a t u r e sp a c ea n dt h ei n h e r e n td a t as p a r s e l y i na d d i t i o n ， t h i sr e p r e s e n t a t i o na l s oc a n ts o l v et e x td a t a sp o l y s e m yp r o b l e ma n ds y n o n y mp r o b l e m a l lt h e s ep r o b l e m si n t e r f e r ew i 也c l a s s i f i c a t i o no rc l u s t e r i n gl e a r n i n gp r o c e s s e sg r e a t l y a n dm a k et h e i rp e r f o r m a n c e sb ed r a m a t i c a l l yd r o p p e d t h em a i nt e c h n o l o g i e st os o l v e t h ep r o b l e ma r ew e i g h ta d j u s t m e n ta n dd i m e n s i o n a l i t yr e d u c t i o n ，b u tt h e s em e t h o d s h a v et h e i ro w nd e f e c t s w e i g h ta d j u s t m e n td o e s n ts o l v et h o s ep r o b l e m se f f e c t i v e l y , s o i ti m p r o v e st h eq u a l i t yo fc l u s t e r i n gal i a l e a l t h o u g hd i m e n s i o n a l i t yr e d u c t i o ns o l v e s 1 1 i g hd i m e n s i o n a l i t y , i tc o s th i g h l y t oa v o i dt h e s ep r o b l e m s ，id i d s o m ej o ba s f o l l o w i n g ： 1 w ep r o p o s e do n ek i n do fo p t i m i z e di n i t i a lc l u s t e rc e n t e rk - m e a n sc l u s t e r i n g a l g o r i t h m t h i sa l g o r i t h mc o m b i n e dt h ei m p r o v e m e n t t h eg e n e t i ca l g o r i t h ma n dt h eh u b m a t h e m a t i c a lm o d e lc a r r i e so nt h eo p t i m i z a t i o nt ot h ei n i t i a lc e n t e r , e f f e c t i v es o l u t i o n t h eq u e s t i o nt h a tc l u s t e r i n ga l g o r i t h mt oi n i t i a lc l u s t e rc e n t e rs e n s i t i v e 2 i nv e c t o rs p a c em o d e l ，b e c a u s et h ed o c u m e n t sc o l l e c t i o nc o r r e s p o n d sah i g h e r o r d e rt h es p a r s em a t r i x ，t h e r e f o r et h ec o m p u t a t i o nl o a di sh u g e ；s i m u l t a n e o u s l yb e c a u s e t h ed o c u m e n t si n c l u d e st h e p o l y s e m ya n d t h es y n o n y m ，t h u st h en o n c o r r e l a t e d d o c u m e n t sw i l lb ea c c u m u l a t e dt h es a m ec l u s t e r , b u tt h er e l a t e dd o c u m e n t sw i l ln o t t h e r e f o r et h i sa r t i c l ep r o p o s e dac l u s t e r i n ga l g o r i t h mb a s e do nt h ew o r ds e m a n t i c s c o n n e c t i o n sb i d i r e c t i o n a lt e x tc l u s t e r i n gi t e r a t i v em e t h o d f i r s t ，t h i sa l g o r i t h mb u i l d s t h ew o r dc o n n e c t i o nm a t r i xw i t ht h es e n t e n c ea st h eu n i t ，t h i sn o to n l yt a k ei n t o c o n s i d e r a t i o nt h ef e a t u r ew o r d st h e m s e l v e s ，b u ta l s ot h ei n f o r m a t i o ni n v o l v e da n dt h e r e l a t i o n s h i pb e t w e e nt h ew o r d s t h e ns e p a r a t e l yc l u s t e r i n gt ot h ew o r da n dt h ea r t i c l e ， a d j u s t st h ed o c u m e n t sc l u s t e r i n gt h r o u g ht h ew o r dc l u s t e r i n g ，a l s oa d j u s t st h ew o r d c l u s t e r i n gt h r o u g ht h ed o c u m e n t sc l u s t e r i n g ，a d j u s t st h ec l u s t e r i n gr e s u l tr e p e a t e d l yb y t h ei t e r a t i o n t h ea d j u s t e dc 1 u s t e rh a ss t r o n g e rc o h e s i o na n dm o r ea c c u r a t e k e yw o r d s k - m e a n sc l u s t e r i n ga l g o r i t h m ；t e x tc l u s t e r i n g ；v e c t o rs p a c em o d e l ； c l u s t e rc e n t e r 2 独创性声明 本人声明所呈交的论文是我个入在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了文中特别加以标注和致 谢的地方外，论文中不包含其他人已经发表或撰写的研究成果， 也不包含为获得江西财经大学或其他教育机构的学位或证书所 使用过的材料与我_ 阿工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意 签名：立：l 丝日期：丝丝：里 关于论文使用授权的说明 本人完全了解江西财经大学有关保留、使用学位论文的规 ， 定，层p ：学校有权保留送交论文的复印件j 允许论文被查阅和借 ， 阅；学校可以公布论文的全部或部分内容，可以采用影印、缩印 或其他复制手段保存论文 ( 保密的论文在解密后遵守此规定) 签名：粗导师签名：装至笕目期迎：! 兰 1 绪论 1 绪论 随着计算机的广泛应用和i n t e m e t 的普及，各类信息都在急速地膨胀。信息量 的增长给人们带来了方便，同时也带来了信息过载的问题。面对浩如烟海、纷繁 芜杂的信息，人们越来越希望能够在数据分析的基础上进行科学研究、商业决策 和企业管理。而文本是最重要的信息载体。因此对文本文档的处理和分析成为当 今数据挖掘和信息检索技术的热点之一。处理和研究文本文档的技术有很多，其 中最为重要的一个技术就是文本聚类。 1 1 文本聚类的研究背景 网络的发展使网络的信息量高速膨胀，目前已经很难准确估计总的信息量。 网络信息量虽然巨大，但是对9 9 的用户来说9 9 的信息都是无用信息，所以准 确定位所需的信息无异于大海捞针。另一方面，随着办公自动化、电子商务、企 业资源管理等的不断发展，企业中的电子数据也飞速增长。例如，到2 0 0 5 年，m 专利服务器上就已经拥有超过4 千万个专利的数据。如果没有对这些数据进行分 类，而让用户一一浏览所有的数据，那简直是不可能的事。最后，随着用户对计 算机和网络使用的日益频繁，用户的个人数据也在飞速增长。三年前，我国网民 就已经达到9 4 0 0 万【1 1 。越来越多的网络用户意味着网络活动日益频繁，用户的个 人信息，比如e - m a i l 、电子文档、所浏览的网页等也飞速增长。以e - m a i l 为例， 根据国家互联网相关管理部门2 0 0 3 年上半年在我国互联网出入口端的一些数据流 量抽样统计，仅仅邮件报文三天的总流量就达到1 0 0 t b 以上，如果这个数据扩展 到我国所有骨干网络上，然后再扩展到整个国际互联网，则每天在网上流动的邮 件信息量粗略估算将达到p ( 1 0 1 5 ) b 规模。所以如果这些邮件都放在一起，没有 进行良好的组织和管理，那么从中寻找一个特定的e m a i l 将非常困难。 综上所述，不论是网络信息、企业信息还是个人信息，它们的信息量都在急 剧膨胀，而文本作为信息的主要载体，其信息量的增长更是飞速。因此迫切需要 有更为先进的技术来管理和组织这些信息，而这些技术中最为重要的一个就是文 本聚类。 1 2 文本聚类概述 作为一种无监督的机器学习方法，聚类技术已经成为对文本信息进行有效地组 织、摘要和导航的重要手段，为越来越多的研究人员所关注。文本聚类( t e x t 基于向量空间模型的文本聚类算法研究 c l u s t e r i n g ) 主要依据是假设同类的文档相似度较大，非同类的文档相似度较小【2 1 。 聚类技术作为一种无监督的机器学习方法，不需要训练过程，以及不需要预先对 文档手工标注类别，因此具有较高的灵活性和自动化处理能力，成为对文本信息 进行有效组织、摘要和导航的重要手段。文本聚类的具体过程如图1 1 所示。 - 图1 1 文本聚类过程 文本聚类有多种应用，不同的应用对聚类质量、效率以及结果可视化程度等方 面往往都有特定的要求，因此要根据应用场合和目的选用适合的聚类算法。在论文 的第三个章节具体分析了各种聚类算法的性能及优缺点。 文本聚类的首要问题是如何将文本内容这种半结构或无结构化的数据表示成 为结构化数据，即建立文本特征，以一定的特征项( 如词条或描述) 来代表目标 文本信息，使得数学上可以进行分析处理。在将文本内容表示成数学上可分析处 理的形式后，接下来的工作就是在此数学形式的基础上，对文本进行聚类处理。 1 3文本聚类的研究意义 文本聚类针对大量的文本信息内容为分析以及深层次的“知识检索 提供了 有效手段，在多项研究或系统中都有很好的应用。因此，文本聚类作为文本挖掘 的一个研究分支，被越来越多的研究人员所关注。 文本聚类的主要应用点包括： ( 1 ) 自然语言处理应用的预处理步骤 文本聚类可以作为多文档自动文摘等自然语言处理应用的预处理步骤，在对大 量文档进行聚类处理后，再针对同类别的文档集合进行自然语言处理的后续步骤。 这方面应用中，比较典型的例子是哥伦比亚大学开发的多文档自动文摘系统 n e w s b l a s t e r t 2 i ( h t t p ：l l w w w l c s c o l u m b i a e d u r d p n e w s b l a s t e r ) 。该系统将新闻进行聚 类处理，并对同主题文档进行冗余消除、信息融合、文本生成等处理，从而生成一篇 2 1 绪论 简明扼要的摘要文档。 ( 2 ) 检索结果的组织 这方面的应用主要体现在对于搜索引擎检索结果的组织上。使用者在输入一 些关键词后，得到的一般都是成千上万条的检索结果，而且其中大部分都是不需 要的无关资料。虽然有一些技巧试图给那些有较多关键词或者罕见关键词的页面 赋予更大的权重，却仍然不能保证和用户意图最相关的页面一定被排在前列以方 便用户查看。因此，我们迫切需要对搜索引擎返回的结果进行聚类，以使得用户 迅速定位到所需要的信息。这方面比较典型的系统有i n f o n e t w a r er e a lt e r m s e a r c h ( h t t p ：w w w i n f o n e t w a r e c o r n ) 。i n f o n e t w a r e 具有强大的对搜索结果进行主题 分类的功能。另外，由c a r r o ts e a r c h 开发的基于j a v a 的开源c a r r o t 2 搜索结果聚合 聚类引擎2 0 版【3 】也是这方面的利用，c a r r o t 2 可以自动把自然的搜索结果归类( 聚 合聚类) 到相应的语义类别中，提供基于层级的、同义的、标签过滤的等功能。 ( 3 ) 个性化信息推送 传统的获取信息的技术中用户是主动方，因此可以称之为“拉 ，与之相反的 另一种方式则称为“推 ，由信息发布方主动地将信息推送给感兴趣的用户。要想 快速完成信息分发步骤，可以通过文本聚类将用户分为对不同事物感兴趣的小团 体，以向有相同兴趣方向的用户提供类似的信息。用户的兴趣可以使用用户自己 提交的，或者用户访问过的文本集合来描述。 1 4 文本聚类面临的挑战 要进行文本聚类，首先要做的就是对文本数据进行数学描述，其中最常用的 数学模型就是向量空间模型。在这种描述模型中，每一个不同的单词都作为特征 空间中的一维，每一个文本是特征空间中的一个向量。这种描述方法引发了一个 非常严重的问题，那就是高维稀疏问题。因为在通常情况下，即使是一个中等规 模的文本数据集也具有几万个单词，这种维度对很多学习算法来说实在是太高了， 事实上只有少数几种神经网络的算法能处理这么高的维度，而对于像贝叶斯信念 网络这类算法来说，其计算简直是不可能的。另一方面，每一个文本通常只包含 所有单词中的极小部分单词，这也就是说，一个文本向量在文本空间中绝大部分 的维度上都是0 ，这使得文本空间异常稀疏，其稀疏程度( 为0 的比例) 通常高达 9 5 9 9 【4 1 1 5 1 。高维稀疏性给文本聚类造成了相当大的影响，不仅使得文本聚类具 有相当高的时间复杂度，而且会极大降低文本聚类和文本分类的性能【6 】【7 1 。 除了高维稀疏之外，文本数据还有近义词和多义词两个特有的语言现象。近 义词现象指的是可以用多种不同的方式来描述同一个主题或者内容。这是因为人 基于向量空间模型的文本聚类算法研究 们在不同的时间、地点下，或者因为知识水平、周围环境、语言习惯、特定需求 等因素往往会使用不同的文字来表达相同的内容【8 】。比如在网上检索足球比赛时， 有的人使用“足球游戏”，而另一些人使用“世界杯”或者“f i f a 2 0 0 8 ”。据f u m a s 等【9 】的统计发现，两个人在使用相同的词语来表达同一件事物的概率不超过2 0 ， 这个数据说明了近义词现象的普遍性。然而近义词的存在极大地降低了信息检索 的性能，因为在精确匹配的方式下，使用“足球”是无法找到“世界杯 、“f i f a 、 “中国甲a 等内容的。 多义词现象指的是同一个单词具有多重不同的含义【l0 1 。比如英文单词”c h i n a ”， 它既指我们的国家“中国”，又有“瓷器”的意思。多义词最大的损害在于极大降 低信息检索的精确度，因为检索“苹果”牌电脑所返回的结果中可能既包含介绍 苹果特性的文章，又包含苹果电脑、苹果牛仔等文章。近义词现象和多义词现象 的存在极大地千扰了文本聚类和文本分类的准确度，使得文本分类和文本聚类变 得非常困难【l 。 综上所述，高维稀疏、近义词和多义词三个文本数据所特有的问题不仅使得 文本聚类和文本分类具有相当高的时问复杂度，而且极大于扰了聚类和分类学习 算法的准确性，使文本分类和文本聚类的性能急剧下降，因此急需新的技术来提 高文本聚类的性能。 1 5 本文的工作 基于划分的尽平均聚类算法，聚类速度快、易于实现，而且还适合于文本、 图像特征等多种数据的聚类分析。然而，肛平均算法目的是通过在完备数据空间的 不完全搜索，使得目标函数取得最大值。由于局部极值点的存在以及启发算法的 贪心性，传统的肛平均算法对初始聚类中心敏感，从不同的初始聚类中心出发，得 到的聚类结果也不一样，并且一般不会得到全局最优解。在实际应用中，由于初 始输入不同而造成结果的波动是不能接受的。因此，怎样找到一组较优的初始中 心点，从而获得一个较好的聚类效果并消除聚类结果的波动性对缸平均算法具有重 要意义。本文以该问题为出发点，先采用文献【1 2 】中提出的一种改进的遗传算法来 获取近似最优聚簇数k ，然后采用一种数学模型来获得一组优化初始中心点。在群 平均聚类算法中除了具有对初始聚类中心敏感这一问题外，文本表示矩阵的数据 稀疏性是影响聚类结果准确性的另一问题【1 3 ，1 4 - 1 5 m1 7 1 ，因此本文提出了种基于 词关联语义的双向文本聚类迭代算法来解决这一问题。该算法先以句子为单位建 立词之间的关联矩阵，考虑了词条本身所蕴含的含义以及词与词之间的关系，然后 分别对词及文挡进行聚类，通过词的聚类来调整文档的聚类，反过来也通过文档 4 1 绪论 聚类来调整词的聚类，经过如此反复迭代来调整聚类结果，调整之后的聚类簇内 聚性更强，类间区分度更大，聚类结果更为准确，有效解决了同义词引发的问题。 1 6 论文大纲 本文共分为六章，内容安排如下： 第一章是绪论。这一章主要讨论本文聚类的研究背景、定义、应用和所面临 的挑战。 第二章介绍了文本聚类中各个阶段的关键技术，在这一章里首先讨论了文本 预处理的一般过程，这是文本信息数学表示的第一步。其次给出了几种常用的文 本表示法，如向量空间模型、概率模型等。再者简单描述了几种基于向量空间模 型的文本距离度量方法。 第三章介绍了各种文本聚类算法和聚类质量评测，在这一章中分析了实际应 用对聚类算法的典型要求，也对各种聚类算法的优缺点进行了分析，如基于划分 的聚类算法，基于密度的聚类方法等。在这一章中，还对各种聚类算法的性能进行 了比较并介绍了几种常用的聚类算法质量评测指标。 第四章提出了一种优化初始聚类中心的尽平均聚类算法，该算法针对传统尽 平均聚类算法对聚类中心的敏感性这一不足进行优化。先通过一种改进的遗传算 法来获取近似最优聚簇数k ，然后采用一种数学模型来获得一组优化初始中心点。 以优化后的中心点聚类得到的聚类结果更为准确。 第五章提出了一种基于词关联语义的双向文本聚类迭代算法。由于大多聚类 算法中的文本表示是基于向量空间模型的，都存在高维稀疏、近义词和多义词的 问题。为解决这一问题，我们通过一种双向聚类迭代算法来实现。先以句子为单 位建立词之间的关联矩阵，然后分别对词及文挡进行聚类，通过词的聚类来调整 文档的聚类，反过来也通过文档聚类来调整词的聚类，经过如此反复迭代来调整 聚类结果。 第六章总结了本文的所有工作，分析了本文的贡献和不足，同时提出了若干 进一步研究的方向。 基于向量空訇模型的文本聚娄算法研究 2 文本聚类的关键技术 中文文本聚类r r i ，在进行聚类之前要进行中文文本的表示，然后再进行聚类。 最常用的文本表示法就是向量空司表示法，这种方法非常简单，但是易引发高维 稀疏的问题。文本表示又分为分词、特征提取及特征提取后的调整等几个步骤。 首先将中文文档集分词，得到特征集合：然后用特征提取算法根据特征评价 函数，从全部特征集中提取一个最优的特征子集对特征提取后的特征词进行微调， 突出聚类重要词，之后利用文本聚类算法，得到聚类结果并且展示出来。 21 分词 文本聚类涉及到大规模的文本处理，需要处理大量真实的i 三【自然语言形式出 现的文本，计算机不具有人类的智慧，不像人类那样能根据上下文以及其他一些 信息，对自然语言文本产生模糊的认识 文本，理想状态是计算机自己能够识别 要使计算机能够高效准确地处理大量的 并对文本产生准确的理解，根据当前的 机器智能化程度，显然还选不到这个层次【l2 i 。因此我们有必要对文本进行形式化 和量化处理，以使计算机可以更好地识别和操作。在大规模的文本分类、聚类或 者文本检索中，选择合适的文本表示方法，是个非常重要的问题。在英文文本处 理中文本表示显得相对简单，因为在文本表示中经常使用词作为基本单位，而且 英文文本中的词与词之间有分隔符，在汉语中词与词之间无空格因此词的切分 问题就成了计算机处理汉语的首要问题。而中文词的切分又涉及到自然语言的理 解问题，从而使中文文本的表示比英文文本复杂得多。 ! 蔓i i 鬻! i 臻_ ：i 童! 一三= 二童鐾蔓乏i 。t 一 叠二蔓追i s 瓣 ! 嚣”# 焉；a “z ：“莉：” l 。g ，。2 i ：，。5 2 ；，：“二茹j 7 o 6 翌委；：寥笥，。4 ：；霉；乎辈蓑。g 册；：“月三元“羔l # 尹7 ：。i 名他；：1 戳糍麓豢：豢d 窈鳙鲈彰，”慌，d 钱，| _ 0 * “f ；7氟，d + ! j 6 目”j “ 爵二孰攫；：自；：船，。锄，。? 嚣静看雾：一翥：。i ；z ，。“觚i 鏊e 二。箕i 黜，：2 鼢，。j “二；哲7 ；，j 7 ；，。7 甜2 窆z “* ；! ? 7 ：x ，。：”窖舅，n i 7 ；，。”鹾，。2 i ￥，n 日h ，。4 * ，一 图2 - i 分词后的文档界面 本文实验语料库词的切分是在e c l i p s e 中调用中科院的i c t c l a s 的j a v a 接 口编程实现的。切分后文档界面如图2 1 所示。 2 文本聚类的关键技术 分词后发现，很多词性的词没有意义，比如副词、连词、形容词，而语义含 量最多的词性就是名词，所以本文实验只取名词作为最后的特征词。经过切分后， 文本的特征集得到的特征项数目是通常很大，假如用所有特征项表示文本，那么 文本的特征向量的维数就很高，过多的特征项一方面会导致聚类算法代价过高， 同时也会导致无法准确地提取文档的类别信息，从而造成聚类的效果不佳，因此 有必要在不牺牲聚类质量的前提下进行特征集缩减。特征选择是文本聚类中一个 重要的问题，其主要任务是从原始特征集中选择一个特征子集以降低特征项的数 目。 2 2 文本特征提取 特征词条的选择，主要根据特征词条的权重，权重越大词重要程度越高，在 信息检索和文本机器学习领域中频繁地被采用的是一种称为t f * i d f 的方法。在该 方法中，特征词条的权重一般考虑两个因素： ( 1 ) 词语频率t f ( t e r mf r e q u e n c y ) ：词语在文档中出现的次数，意味着一个单词 在一个文本中出现得越多，它的权重就越高。t f 刻画了单词的局部权重。 ( 2 ) 词语倒排文档频率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 ) ：表示该词语在文档集 合中分布情况的一种量化，常用的计算方法是l o g ( n n 。+ o 0 1 ) ，其中为文档集 合中的文档数目，刀。为出现该词语的文档数目。这力。取得是倒数，也就意味着一 个单词在越多的文本中出现，它的重要性越低。极端情况下，如果一个单词在所 有的文本中都出现，那么它的重要性将变为0 。相对于t f ，i d f 刻画的是单词的 全局权重。 根据以上两个因素，可以得出权重计算公式为： =公式( 2 1 ) 其中f 为第i 篇文档，k 为第k 个词。另外，考虑到不同文本之间的差异很大， 有的文本可能会很长，比如好几十页，而有的文本却很短，只有一两句话。所以 为了使不同长度的文本具有可比性，t f * i d f 还需要对每一个文本向量进行规一 化，即使文本向量的长度都规范化为1 。公式( 2 1 ) 是根据香农信息学理论，如果项 在所有文本中出现的频率越高，那么它所包含的信息嫡就越少；如果项的出现较 为集中，只在少量文本中有较高的出现频率，那么它就会拥有较高的信息嫡。通 过这个公式，就可以提取出在文档中比较重要的特征词。， 在本文提出的基于词关联语义的双向聚类迭代算法中对词矩阵特征选择，先 7 基于向量空间模型的文本聚类算法研究 由公式( 2 1 ) 计算词的权重，再计算每个词在文档集中的平均权重，然后再计算每个 词对文档分类的支持度，选取支持度和平均权重大于给定阈值的词作为关键词来 构造词矩阵，具体步骤见本文的第五章。 2 3 文本的表示模型 文本表示模型也称为文本特征的表达。文本特征是指关于文本的元数据，分为 描述性特征( 如文本的名称、日期、大小、类型等) 和语义性特征( 如文本的作者、 机构、标题、内容等) 。特征表示是指以一定特征项( 如词条或描述) 来代表文档，在 文本挖掘时只需对这些特征项进行处理，从而实现对非结构化的文本进行处理，这 是一个非结构化向结构化转换的处理步骤。在实际的文本聚类分析研究中，将文 本内容变成计算机内部表示结构的方法多种多样，可以用词、字、短语、n g r a m 、 显著性短语【1 9 】等形成向量、树等结构。文本表示是文本聚类的第一步，该步骤的 变化很多，对最终聚类效果的影响也不尽相同。本节接下来主要介绍信息检索和 文本分析处理中经常用到的几个模型。 2 3 1 布尔模型 布尔模型是基于集合论与布尔代数的一种简单模型【2 0 1 。在布尔模型中，文档 d ，中索引特征互的权重彬，是二值的，即彤， o ，1 ) ，即可以将单个文本表示称为 特征空间上的一个向量，向量中的每个分量权重取0 或者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 】之间的数。布尔模型是基于集合论与布 尔代数之上的一种表示模型，其表示与计算可以转化为向量来等价实现，是一种 类向量的模型。 2 3 2 向量空间模型 1 9 6 9 年，g e r a r ds a l t o n 提出的向量空间模型v s m ( v e c t o rs p a c em o d e l ) 是信 息检索领域中经典的检索模型。该模型的主要思想是：将每一文档都映射为一组 规范化正交词条矢量张成的向量空间中的一个点【2 l 】。在用向量表示文档时，需要 对文档集进行切分、停用词处理等步骤。在经过这些步骤后；。基本上就可以得到 一系列词或词素，将这些词或词素作为文档的特征。此时，所有的这些词就构成 了一个“空间”，每个词对应着空间中的一维。 2 文本聚类的关键技术 表2 - 1v s m 模型中文本与空间的映射表【1 8 】 ! 鬻磐蠢麓薹耍档视磋乏鏊j 囊ij ：? i j 每冬譬：t 向量空峨型概角誊毒誊；蠹 文档向龄、空间中的点 词或词素空间中的一个维度 文档集合分布在空间中的一组点集 词的权重 空间中点的坐标值 对于每个文档d ；都可以用文档中的词来表示，这些词及其对应的权重就构成 了“空间 中的一个向量( 彬形，蜕，) 。其中形为文档q 中词条i 的权重。 2 3 3 概率模型 概率模型试图在概率的框架下解决信息检索问题。到目前为止，概率模型已经 成为信息检索领域内比较成熟的模型，并在很多系统中应用取得不错的效果。概 率模型是一系列模型的简称，它综合考虑了词频、文档频率和文档长度等因素， 把文档和用户兴趣( 查询) 按照一定的概率关系融合，并在概率测度空间上通过 概率来衡量两个文本的语义相似度。在信息检索中，主要计算 p ( r e l e v a n c e id 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 g p r i n c i p l e ) t 2 2 】【2 3 】来判断不同文档与同一个查询相关的程度。 p ( r e l e v a n c eld 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 id o c u m e n t ，q u e r y ) 的计算公 式，可以衍生出不同的概率检索模型。概率检索模型包括b i r ( b i n a r yi n d e p e n d e n c e r 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 4 语言模型 语言模型【2 4 】本质上也是一种基于概率和统计的模型。在语言模型中，每个文 档、整个语料库、相关查询都被看作是语言模型，通过计算语言模型之间的距离 来衡量查询与文档的相关性及文档与文档之间的相关性。语言模型就其研究方向 而言，一般分为两类。一类是基于语言学知识的规则文法，另一类是基于统计的 语言模型。目前，以语料库为基础的统计语言建模方法成为潮流。这种方法通过 对语料库进行深层加工、统计和学习，来获取大规模真实语料中的语言知识。统 计语言模型认为语言就是字母表上的一种概率分布，通过概率分布计算任何一个 字母序列成为该语言一个语言单元( 句子、段落、文章等) 的可能性。特征集合 在某个文档d ，中形成一个分布，这个概率分布就称为一个语言模型。 在语言模型研究方面，卡内基梅隆大学( c a r n e g i em e l l o nu n i v e r s i t y ，c m u ) 的 9 基于向量空间模型的文本聚类算法研究 语言技术研究所( l a n g u a g et e c h n o l o g i e si n s t i t u t e ) 和马萨诸塞大学( u n i v e r s i t yo f m a s s a c h u s e t t s ，u m a $ $ ) 的智能信息检索中心( c e n t e rf o ri n t e l l i g e n t i n f o r m a t i o n r e t r i e v a l ) 合作开发的l e m u r 系统是实现语言模型的信息检索系统，在t r e c 中 取得过很好的成绩，该系统也是研习语言模型的有用工具。 2 4 文本相似度度量 由于聚类算法是给予数据自然上的相似划法，要求得到的聚类是每个聚类内 部数据尽可能的相似而聚类之间要尽可能的大差异。所以定义一种尺度来衡量相 似度就显得非常重要了。 在文本聚类中，除了对文本进行表示外，还必须对文本进行相似度度量。相 似度度量是影响聚类效果的一个重要方面。相似度是用来衡量两个对象之间相似 程度的度量。同时，我们也可以使用距离的概念来衡量两个对象之间的不相似程 度。相似度和距离是两个相对的概念，在聚类分析中这两个概念经常一起使用。 2 4 1定义距离的方法 定义距离有如下几种方法： ( 1 ) e u c l i d e a n 距离：采用传统的距离的概念，适合于2 、3 维空间。 畋( 五，一) = ( ( 一瓢) 2 ) “2 = 忙一勺0 ： 公式( 2 2 ) k - 1 其中d 为向量的维度。 ( 2 ) m i n k o w s k i 距离：是e u c h d e a n 距离的扩展，可以理解为n 维空间的距离。 d p ( 而，乃) = ( ( 该一瓢) p ) “，= 恢一_ 虬 公式( 2 3 ) 七= i 。 当p 取2 时，就是e u c l i d e a n 距离。 ( 1 3 ) m a h a l a n o b i s 距离：基于属性间的协方差矩阵给予每个维不同的权值来定义 距离。 九( 而，- ) = ( 而一_ ) 。1 ( 而- x j ) r 公式( 2 4 ) ( 4 ) 相互邻接距离：这是一种非测度的距离，距离的值取决于数据的上下文。 m n d ( x f ，工，) = ( 西，x ，) + 删( 工，薯) 公式( 2 5 ) 其中( 而，石，) 指再相对于x ，的邻接次序。 ( 5 ) 还有特殊领域的距离表示，如字符串处理领域的基于最小数目原子操作的 编辑( e d i t ) 距离和基于词根的全纯q o l o m o r p l l i c ) 距离【2 5 1 。 公式( 2 2 ) ，( 2 3 ) ，( 2 4 ) 中定义的三种距离的都是基于测度的距离定义。一个距 离定义是基于测度的需要满足以下3 个条件：对称，到自己距离为0 ，满足三角不 l o 2 文本聚类的关键技术 等式。 2 4 2 定义相似度的方法 定义相似度的方法一般有如下几种： ( 1 ) 基于距离的方法：距离d 描述的是数据的差异性，而相似度s 描述的是数据 的相似程度。相似度和距离的关系可以看为：d = 1 s 一1 ，即s = 1 “d + 1 ) 。可以使 用上- - d , 节介绍的基于测度的3 种距离来计算d 。如使用m i n k o w s k i 距离，则有： 一2 南2 葡瑟而1 公式q 石 ( 2 ) 余弦测量的方法：也可以用两个数据矢量之间的角度或角度的余弦来定义 相似度。 蹦) 2 翻2 丽x r , 翥：9 馘( 2 7 ) ( 3 ) j a c c a r d 相似度：给出了两个数据公共特征在总特征的比值。这种方法可以 应用在超市购物数据。 2 磊糯公式( 2 8 ) 在具体应用的时候不管是距离还是相似度都可以用于计算矩阵表示，预先计 算好刀个数据的以( 刀一1 ) 2 个距离，然后在矩阵的基础上进行聚类算法。 2 5小结 本章详细介绍了在进行中文文本聚类之前的几个重要预处理步骤。包括文本分 词、特征提取、选择模型对文本进行表示、以及文本相似度度量的方法。本文在 实验过程中，在e c l i p s e 平台下调用中科院的i c t c l a s 的j a v a 接口编程实现的， 文本表示采用向量空间模型并采用余弦相似度来度量文本相似度。 基于向量空间模型的文本聚类算法研究 3 文本聚类算法及质量评测 聚类( c l u s t e r i n g ) 就是按照某个特定标准( 一般为距离准则) 把一个数据集分割 成不同的类或簇( c l u s t e r ) ，使得在同一个簇内的数据对象的相似性尽可能的大，同 时不在同一个簇中的数据对象的差异性也尽可能的大。也就是说，聚类后同一类 别的数据尽可能的聚集在一起，而不同的数据尽量分离。聚类问题的研究不仅仅 局限于上述硬聚类( h a r dc l u s t e r i n g ) ，即每一个数据只能被归为一类，模糊聚类也 是聚类分析中研究较为广泛的一个分支。模糊聚类通过隶属函数来确定每个数据 隶属于各个簇的程度，而不是将一个数据对象硬性的归类到某一簇中。目前已有 很多关于模糊聚类的算法，如著名的f c m 算法等。 现有的聚类算法大致可以分为：划分聚类算法、层次聚类算法、密度聚类算法、 网格聚类算法以及模型聚类算法【2 6 】【2 7 】，如图3 1 所示。本章将介绍聚类分析的基 本概念、实际应用对聚类算法的典型要求以及各种基本聚类算法。 l 聚合聚类：s i n g l e l i n k ，c o m p l e t e - l i n k , a v e r a g e l i n k 1 分解聚类 基于密度的聚类 基于网格的聚类 基于图论的聚类 基于平方误差的迭代重分配聚类：概率聚类、最近邻聚类、k - m e d o i d s 、k m e a n s 类算法 聚类算法 全季萎蓑星耄磊霎法：模拟退火、遗传算法 i 基于进化理论的方法：模拟退火、遗传算法 的聚类算法j 三孝竺考类 i 联合聚类 图3 - 1 聚类算法分类示意图 3 1 对聚类算法的典型要求 聚类分析是一个具有很强挑战性的领域，它的一些潜在的应用对聚类分析算 法提出了各自的特殊要求。对聚类算法的典型要求如下【2 6 】： ( 1 ) 可伸缩性：许多聚类算法对于小于2 0 0 个数据对象的较小数据集能够很好 地进行聚类，但是，一个大型数据集中可能包含有几百万、几千万乃至更多的对 象。虽然通过抽样可以减少要处理的数据量，但是抽样会对聚类的结果带来影响 甚至会产生错误的结果。因此，我们需要具有高度可伸缩性的聚类算法。 ( 2 ) 处理混合型数据的能力：许多算法是设计来对数值型( n u m e r i c a l ) 数据进行聚 1 2 3 文本聚类算法及质量评测 类的。然而，在许多应用中待聚类的数据可能是二值型( b i n a r y ) ，、枚举型 ( c a t e g o r i c a l n o m i n a l ) 、序数型( o r d i n a l ) ，或者这些数据类型的混合。聚类算法需要 具有处理这些数据类型的能力。 ( 3 ) 发现任意形状