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

中文摘要 i n t e m e t 作为一个开放的、分布式的信息平台，近年来得到了飞速的发展， 其信息总量也出现了爆炸性增长。面对这些海量信息，人们很难迅速、有效地从 中得到自己真正所需。为此，为了更好的组织和管理这此信息，文本分类和聚类 的研究就显得越来越重要了。 本文对基于向量空间模型的文本聚类技术进行了研究和探讨，主要内容有： 向量空间模型，文本聚类算法、聚类结果评价等。 向量空间模型是进行大规模文本处理最简便、高效的模型之一。本文对向量 空间模型中的基本原理进行了研究，包括：文本表示，文本预处理、特征项的选 取、权重计算、文本相似度的度量及特征选择等。并对向量空间模型的优缺点做 了深入的分析。 本文研究和分析了现有的几种常用的聚类算法：k - m e a n s 、凝聚层次法和 d b s c a n 。对于它们的性质和特点进行了详细分析。而且论述了文本聚类的结果 评价方法。 然后，针对k m e a n s 算法的缺点，结合局部搜索算法，本文提出了一个基 于局部搜索的k m e a n s 算法l s k m ，对它的性质进行了深入的分析，从理论上 说明了它的有效性及特点。 为了验证我们算法的有效性，在随后的实验中，以几个不同的标准测试集为 基础，对l s k m 和k - m e a n s 算法进行了对比实验，证明了我们的理论分析。对 于实验中出现一些问题，本文也从理论和进一步的实验中做出了分析说明。 关键词：文本聚类向量空间模型k - m e a n s 算法局部搜索l s k m a b s t r a c t a sa l lo p e n , d i s t r i b u t e di n f o r m a t i o np l a t f o r m , i n t e r a c th a sm a d ear a p i dp r o g r e s s i nr e c e n ty e a r s w i t l lt h ee x p l o s i v eg r o w t ho fi n f o r m a t i o n ，p e o p l eh a v ed i f f i c u l t yi n f i i l d i n gw h a tt h e yr e a l l yr e q u i r eq u i c k l ya n de f f e c t i v e l yf r o mt h em a s s i v ei n f o r m a t i o n i no r d e rt oo r g a n i z ea n dm a i l a g et h ei n f o r m a t i o nm o r ee f f i c i e n t l y , t e x tc l a s s i f i c a t i o n a n dc l u s t e r i n gh a db e c o m ea p r o m i s i n gr e s e a r c hs u b j e c t t h ek e yt e c h n i q u e so ft e x tc l u s t e r i n gb a s e do nv e c t o rs p a c em o d e l ( v s m ) w i l l b ed e s c r i b e di nt h es t u d y , i n c l u d i n gv e c t o rs p a c em o d e ，t e x tc l u s t e r i n ga l g o r i t h m , e v a l u a t i o no f c l u s t e r i n gr e s u l t sa n ds oo n v s mi so n eo ft h em o s ts i m p l ea n de f f e c t i v em o d e l sf o rl a r g es c a l et e x t p r o c e s s i n g i nt h i sp a p e r , t h eb a s i cp r i n c i p l eo fv s m w i l lb ea n a l y z e d ，i n c l u d i n gt e x t r e p r e s e n t a t i o n , t e x tp r e p r o c e s s i n g ，t e r mw e i g h t i n g ，c o m p u t a t i o no fs i m i l a r i t yb e t w e e n t e x t sa n df e a t u r es e l e c t i o n a n dt h em e r i t sa n df a u l t so f v s mw i l la 1 8 0b ea s s e s s e d t h i sp a p e rd i s c u s s e sa n da n a l y s e ss e v e r a le o i l m o nc l u s t e r i n ga l g o r i t h m ss u c ha s k - m e a n s ，a g g l o m e r a t i v eh i e r a r c h i c a lc l u s t e r i n ga n dd b s c a n t h en a t u r e a n d c h a r a c t e r i s t i co f t h e ma r ee x p l o r e di ng r e a td e t a i l sa n dt h ee v a l u a t i o no f t e x tc l u s t e r i n g r e s u i t si sa l i n e l u d e d i no r d e rt oa v o i dt h ef a u l t so fk - m e a n s ，t h i sp a p e rp r e s e n t san e wt e x t c l u s t e r i n ga l g o r i t h mb a s e do nl o c a ls e a r c ha n dk - m e a n s 皿s k m ) a n de x p l a i n st h e c h a r a c t e r i s t i co f t h i sa l g o r i t h mt h e o r e t i c a l l y t h ee x p e r i m e n t a lr e s u l t so ft h r e es t a n d a r dt e s tc o l l e c t i o n ss h o wt h a t0 1 1 1 n e w a l g o r i t h mi sb e t t e rt h a nk - m e a n sa n da l s ot e s t i f yt h et h e o r e t i c a la n a l y s i s a n dt h e f u r t h e ra n a l y s i so fs o m ei s s u e si nt h ee x p e r i m e n tt h e o r e t i c a l l ya n de x p e r i m e n t a li s a l s os h o w e di nt h i sp a p e r k e yw o r d s ：t e x tc l u s t e r i n g , v e c t o rs p a c ev e c t o r , k - m e a n s ，l o c a ls e a r c h , ls _ k m 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得鑫注盘堂或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：后寸詈窗彳签字日期： 咿年，月7 日 学位论文版权使用授权书 本学位论文作者完全了解鑫凄盘茎有关保留、使用学位论文的规定。 特授权苤注盘茔可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者躲斛鲁蛔 签字日期：缸p f 年2 月印日 导师签名： 签字日期： 土 版互够 刎f 年工月刃日 天津大学硕士学位论文第一章绪论 1 1 选题背景和研究意义 第一章绪论 i n t e m e t 作为一个开放的，分布式的信息平台，近年来得到了飞速的发展，其 信息总量爆炸性增长。在各种电子信息日益丰富的同时，信息的多元化和复杂化 使信息检索、分类和相关技术领域的研究成了新的挑战性的课题。 面对i n t e m e t _ l ：浩瀚纷繁的信息海洋，人们常常会陷入窘迫的境地：一方面由 于收到太多的信息无从选择和消化，从而淹没在繁杂的信息中；另一方面是信息 迷失，人们难于找到自己真正所需的信息。目前处理互联网上海量信息的最广泛 的手段是g o o g l e 、y a h o o 等综合搜索引擎。但是由于搜索引擎以关键词为基本的 检索单位，因而它反馈给用户的结果是包含这些关键词的所有网页，而这些网页 经常是跨越多个领域的，其中的许多内容根本不属于用户感兴趣的范围。为了得 到真正有用的信息，用户只能按照搜索引擎列出的页面顺序，花费很多时间来浏 览大量网页。为了向用户提供更有效的信息，提高搜索引擎的准确性，迫切需要 研究出更为先进的技术对这些信息进行有效的管理和组织。这些技术中最为重要 的两个技术就是文本分类和文本聚类【l “。 文本分类是在分析文本内容的基础上给文本分配一个或多个比较合适的类 别。它通常由两个阶段组成：训练阶段和分类阶段。在训练阶段，从训练文本中 学习分类知识，建立分类器类模型；在分类阶段根据分类器将输入文本分到最可 能的类别中。从这个过程可以看出，分类需要事先存在的人工分类好的训练文本 集，也就是说，分类目录是事先确定的。 但是，互联网上信息是动态变化的，经常会出现新的、很难用现有的分类模 型来刻画的主题。如果要建立分类模型，就必须重新建立分类好的训练文本集， 而获得大量带有类别标注的样本的代价是很大的。这时无监督的文本聚类就显得 很重要。文本聚类是文本挖掘重要的手段之一，在文本信息处理系统中，它的应 用价值主要表现在： ( 1 ) 发现与某个文本相似的一批文本，以帮助用户发现相关知识； ( 2 )将一个文本集聚成若干个类，提供一种组织和浏览大规模文本集的方 法： ( 3 )作为一种文本分类的辅助技术，即使用聚类技术可以生成用于文本自 天津大学硕士学位论文第一章绪论 动分类的分类模型。 因此文本聚类技术成为信息检索过程中具有较大实用价值的关键技术。为此 本文将文本聚类作为主要研究内容。 1 2 文本聚类概述 文本聚类是完全根据文本内容的自身的特性来组织文本集合，通过特定的处 理和相应的算法将整个集合聚成若干个类，并使得属于同一类的文本尽量相似 ( 即内容相关) ，属于不同类的文本差别明显( 即内容无关) 。由于事先没有关于 这些文本信息的分类知识或可以使用的分类表，因此，文本的聚类处理是一种无 监督的学习( u n s u p e r v i s e dl e a r n i n g ) ，其特点可概括为“先有文本后有类”。 文本聚类研究所依据的思想和方法起源于数值分类学的“聚类分析” ( c l u s t e r i n ga n a l y s i s ) 。早期的文本聚类分析主要依靠专业知识和经验，局限在定 性的范围内。后来随着学科的发展与信息量的激增，分类越来越细，需要分类的 文本对象也越来越多，这时仅仅依靠文本的一些特性进行定性划分也变得越来越 困难。于是，作为数值分类学的主要分支，聚类分析技术就被引入到文本聚类领 域。 设s = 码，吐，以) 代表一个文本集，s 代表s 的一个子集，则文本聚类的 任务就是将s 分割为k 个子集，并且满足： s = k - ) 1 h x 墨( 1 1 ) 这个条件很容易满足，但是仅仅这个条件是不够的，因为文本聚类更重要的 是使类内的文本在语义上尽可能相似，而与其他类中的文本尽可能“相隔”较远 或者不同，即： m a x ( s i m ( d ，墨) ) 当d 墨时( 1 2 ) m i n ( s i m ( d ，s ) ) ，当d 叠s 时 ( 1 - 3 ) 不同于文本分类，文本聚类没有训练数据，所以没有训练步骤。文本聚类的 过程相对简单，如图1 1 所示，它首先对原始的文本数据进行预处理，进而表示 成文本特征向量，然后采用聚类算法进行聚类，最终得到多个文本类。 天津大学硕士学位论文第一章绪论 文本聚类的一般过程 图1 - 1 文本聚类的过程 1 文本预处理 由于文本数据不同于数据库中的结构化数据，必须把文本表示成为计算机能 够处理的、可体现文本本质特征的形式。文本的内容是人类所使用的自然语言， 计算机并不具有人类的特有智能，因此很难处理其语义。由于文本信息源的这些 特殊性，所以我们需要对文本进行预处理，抽取代表其特征的元数据，这些特征 可以用结构化的形式保存，作为文本的中间表示形式。空间向量模型( v e c t o r s p a c em o d e l ，v s m ) 5 1 是近年来应用最多且效果较好的方法之一。 2 生成文本特征向量 当我们选择表示文本的特征后，就可以依据一定的原则将文本数据表示为特 征空间内的特征向量；同时根据文本数据的特点一一高维、稀疏，还要进行相应 的特征选择和抽取【6 】，这样不但可以降低特征向量的维数，使聚类算法的计算复 杂度大大降低，而且可以去除由于同义词及多义词所产生的噪声和歧义，进而大 幅度提高文本聚类系统的性能。 4 聚类 当生成文本的特征向量后，文本数据就表示成为便于计算机处理的结构化形 式，即可应用所选择的聚类算法对文本进行聚类处理，生成相应的聚类结果。 1 3 本文的主要研究工作及组织结构 本文首先讨论了将无结构的文本数据转化为聚类算法可以处理的结构化数 据的方法一向量空间模型，以及这种方法的优缺点。随后分析介绍了在文本聚 类时常用的几种聚类算法，并针对k - m e a n s 算法的问题提出一个基于局部搜索 ( l o c a ls e a r c h ) 的k m e a n s 聚类算法( l s ：m ) ，对它的性质进行了深入的理论 分析。最后对它在静态文本集上的聚类结果进行实验分析，结果表明该算法同 k - m e a n s 相比具有较高的聚类质量。 本文的组织结构如下： 第一章为绪论，介绍文本聚类课题的研究背景、研究价值以及文本聚类的概 天津大学硕士学位论文第一章绪论 述，然后列出文本的主要研究工作和组织结构。 第二章深入分析和研究了向量空间模型的关键技术，包括文本的表示、预处 理、特征项的选取，权重的计算和特征选择，并对向量空间模型优缺点做出了一 个深入分析。 第三章介绍几种常用的文本聚类方法，并讨论了聚类结果的评价方法。 第四章研究了划分的聚类算法，并给提出一个基于局部搜索( l o c a ls e a r c h ) 的k m e a n s 聚类算法( l s k m ) ，对它的有效性进行了理论上的分析和研究。 第五章是实验结果及分析。首先，用实验数据证明了特征算法应用于文本聚 类的有效性；接下来的实验则证明了第四章所提出的算法在实验应用的效果，并 对实验中所出现的一些问题进行了说明和分析。 第六章总结本文的研究工作，并展望未来的研究工作。 天津大学硕士学位论文 第二章向量空间模型及相关技术 第二章向量空间模型及相关技术 文本聚类的目标就是要将语义相近的文本聚成一类，使得同一类内的文本之 间的相似度大，而类间的文本之间的相似度小。然而文本都是非结构化的，因此 必须建立文本模型，将非结构化文本转换为计算机可以识别的格式，这种模型应 能尽可能多的反映文本所蕴涵的语义信息，同时又要便于计算机处理。 目前在信息检索领域，存在着许多文本模型，具有代表性的有布尔模型 ( b o o l c a nm o d e l ) ，向量空间模型( v e c t o rs p a c em o d e l ，v s m ) ，概率模型 ( p r o b a b i l i s t i em o d c l ) 等。这些模型从不同的角度出发，使用不同的方法处理特征 加权、类别学习和相似计算等问题。 在这几种模型中，gs a l t o n 教授于2 0 世纪6 0 年代末提出，并成功的应用到 s m a r t 系统中的向量空间模型( v e c t o rs p a c em o d e l ，v s m ) i s ，是最简便有效的文 本表示模型之一。该模型及其相关技术，包括特征项的选择、权重的计算，以及 采用相关反馈进行优化查询等在文本分类、自动索引、信息检索等许多领域得到 广泛的应用，并且取得了较好的效果。 2 1 向量空间模型 2 1 1 向量空间模型概述 向量空间模型是文本表示的一个统计模型，该模型将任意一篇文本表示成向 量空间中一个向量，并以特征项作为文本表示的基本单位，向量的每一维对应文 本中的一个特征项，而每一维的值则表示了其对应的特征项在该篇文本中的权 重，它代表了这个特征项相对于这篇文本的重要程度，即该特征项表示文本内容 的能力。这样一个文本d 可以表示为： d = “，m ) ，( ，2 ，w 2 ) ，( f 3 ，嵋) ，以，) )( 2 1 ) 其中表示第i 个特征项，嵋表示个特征项在文本d 中的权重。因此，所 有的文本向量都可以组成文本集的一个特征空间。 天津大学硕士学位论文 第二章向量空间模型及相关技术 2 1 2 特征项的选取 特征项通常用文本所包含的基本语义单位( 字，词，词组或短语等) 来表示， 也可以用相应词语或者短语的语义概念类来表示。特征项的选择由处理速度，精 度，存储空间等方面的具体要求来决定。选出的特征项越具有代表性，语言层次 越高，所包含的信息就越丰富，但是分析的代价就越大，而且受分析精度( 如句 法分析的正确率) 的影响就越大。由于词是组成文本基本元素，并且在不同内容 的文本中，它的出现频率呈现一定的统计规律，不同的特征词可以区分不同内容 的文本，因此可以认为选择词作为特征项是比较合理的。它也是于文本检索与分 类领域常采用的方法。但是选用词作为文本特征项时要考虑以下问题： ( 1 )文本中存在一些使用频率很高但没有实际意义的虚词和功能词，如 英语中的“t h e 、a 、o f ，汉语中的“的、这、那、得”等。它们几乎出现在该语 言的每一个文本中，但是它们对于这个文本所表达的意思却几乎没有任何贡献。 所以如果以这些单词作为文本特征的话，即使是内容上完全不同的两个文本也会 因为这些共有的特征而很难被区分开来。因此，非常有必要将这些停用词从原始 的文本中过滤出去，即停用词过滤。停用词过滤还可以显著提高文本分类和文本 聚类的效率，包括存储空间和时间。有研究指出英文中最常出现的1 0 个单词通 常占整个文本所有词条量的2 0 0 0 3 0 7 1 。因此删除这些停用词也就相应地节省了 相同比例的存储空间，自然后续的处理时问也就节省好多。 ( 2 )在英语及其他西方语言中，单词有复杂地词尾变化和派生现象。比 如英文单诃“l l s e ”，可以有“u s i n g ”、“u s e d ”、“u s e s ”等不同的形式出现，如果 将它们看做不同的词的话，即使相同主题的文本也可能只有很低的相似性。所以， 非常有必要将不同形式的单词都作为相同的单词来对待，即词干抽取 ( s t e m m i n g ) 。词干抽取所解决的问题就是将具有相同词根但不同形式的单词还 原为词根，作为同一个词条来进行处理。首先，可以使使用不同形式的单词但是 表达相同主题的文本具有更高的相似性，从而使文本分类或者文本聚类的结果更 为优秀。其次，词干抽取可以极大较少词条的数量，从而在存储空间和时问上极 大提高文本分类或者文本聚类的性能。 2 1 , 3 权重的计算 最简单的权重的计算方法是使用0 和1 来表示一个单词是否出现在一个文本 当中。但是这种计算方法忽略了不同单词对一个文本的重要程度，认为所有出现 的单词对一个文本来说同等重要的。然而很显然的是，不同的单词对一个文本来 天津大学硕士学位论文第二章向量空问模型及相关技术 说其重要性是不一样的，因此需要使用其他的一些技术或者方法来使重要的单词 具有更高的权重，不重要的单词具有较低的权重。 权重计算要考虑因素有很多，主要包括词频和文档频数。词频指的是一个单 词在一个文本中出现的次数。通常情况下，对于一个文本来说，如果一个单词在 这个文本中出现得频率非常高，那么它就很可能与这个文本的主题密切相关，也 就是说有重要性很高；反之，如果一个单词在这个文本中只出现很少的次数，那 么它很可能只是起语法修饰、语言辅助作用的单词，与文本的主题无关，所以重 要性就很低。 单词的重要性除了与这个单词在文本中出现的频率密切相关之外，还有个 非常重要的考虑因素，那就是单诃的文档频数，即这个单词在整个文本集中出现 的频率。因为一个单词除了表达一个文本的主题之外，还有一个重要的功能就是 区分这个文本与其他文本。如果个单词出现在文本数据集中大部分的文本中， 那么通过这个单词是无法区分一大批与之相关的文本的。并且如果使用这个单词 进行检索的话，将返回所有包含这个单词的文本，即文本数据集中大部分的文本。 另一方面，如果一个单词只出现少数几个文本中，那么它的特殊性就很高，区分 与之相关和不相关文本的能力就很强。所以从这个角度来说，一个单词的重要性 与这个单词在一个文本数据集中出现的频率成反比，即一个单词在越多的文本中 出现，它的重要性就越低，在越少的文本中出现，它的重要性就越高。 考虑到这些因素，1 9 8 8 年s a l t o n 和b u c k l e y 提出了矿x i d f 方法h j ，它已经被公 认为是一种标准的文本向量表示方法。矿x i d f 的典型计算公式如下： 以，d = t f 以，d ) xl o g ( 珥+ o 0 1 ) ， ( 2 2 ) 其中w ，表示词t ，在文本d 中的权重，矿也，d ) 表示的词频，即f 。在文本d 中的出现频率，n 为全部文本的数量，啊为包含词t 的文本个数。 公式( 2 - 2 ) 的第一个因子代表了词在文档中出现的频率( t e r mf r e q u e n c y , 矿) ，它针对单一文本的统计，表示了一个词在该文本中的重要程度，刻画了词 的局部特征；第二个因子则被称为反转文档频率( i n v c r s e dd o c u m e n tf r e q u e n c y , i d f ) ，它度量了词在文本集中的分布，由上面定义可知，一个单词在越多的文本 中出现，它的重要性越低。极端情况下，如果一个单词在所有的文本中都出现， 那么它的重要性将变为0 。相对于矿，i d f 刻画的是单词的全局特征 因而。使用矿i d f 来计算权重就意味着，最能插述特定文本是那些在该文本 中足够频繁，并且在极少出现其它文本中的词。也就是说，文本集中适当比例的 文本中所包含的适当比例的词是重要的，会得到较高的权重，而那些在任何文本 中极少出现及几乎出现在所有文本中的词是不重要的，会得到较低的权重。 另外，考虑到不同文本之间的长度差异对于权重的影响，还需要对每一个文 天津大学硕士学位论文第二章向量空问模型及相关技术 本向量进行规一化，即使文本向量的长度都规范化为i ，规一化的计算如公式( 2 3 ) 所示： 毗，d ：1 丝；尘丝丝! 垒三! ：! 坠， 窆 f ( t k , d ) x l o g ( n n k + 0 0 i ) 2 ( 2 。) 多年的实验研究表明，上述公式是文本处理中的一个有效工具。事实上，这 一公式不仅在信息检索中得到了成功应用，它对于其他文本处理领域，如信息分 发、信息过滤和文本分类也有很好的借鉴意义，本文研究聚类系统也是以它作为 文本表示模型而实现的。 2 1 4 文本相似度的度量及相关定义 对于向量空间模型表示的文本向量，最常用的是向量之间的角度衡量，两个 文本向量之间的角度越小，则文本之间的相似度越大，角度越大，则相似度越小。 角度度量通常用向量夹角余弦值来表示，定义如下： 砌 码) - c o s 码卜龋 ( 2 4 ) 其中4 t 表示两个向量的点积，棚表示向量d 的长度。 由于文本向量的长度被归一化为单位向量，因而在计算文本相似度是这个公 式可以简化为： s i r e ( d , ，d | ) = c o s q l ，d i ) = d 。djp 5 ) 此外文献【9 】还讨论了几种适用了向量空间模型的文本相似度的度量方法， 如d i c e 、j a c c a r d 系数等。w i l l e t t 研究表明，这几种相似度度量方法对聚类结果没 有本质的影响，重点在于聚类算法的选择1 0 】。 下面给出文本聚类中会使用到的文本向量的相关性质。 在本文中，我们使用符号n 、研、k 分别表示文本集中的文本数、文本向 量的维数和聚成类的个数；使用符号s 表示这个由个文本所组成的文本集， s ，最，表示聚成的x 个类，啊，吩，表示相应的类的大小。 给定一个文本集s 及它所包含文本的向量表示，我们定义文本集s 的复合向 量( c o m p o s i t ev e c t o r ) 喀为： 岛= d( 2 6 ) 文本集s 的中心( 概念) 向量( c o n c e p t v e c t o r ) c s 为： 天津大学硕士学位论文 第二章向量空间模型及相关技术 铲而(2-7) 向量的性质： 当使用余弦相似度来度量文本相似度的时候，可以利用文本集的复合向量和 中心概念向量的许多性质。一般的，如果墨和马是两个包含一和n ，个文本的文 本集，并且口、q 和q 、0 是两个文本集的复合向量及中心向量，我们有： 文本集置和量中的文本两两相似度之和等于口与q 的点积，l i p c o s ( a , ，嘭) = 西t 如巩小巧 ：莹趁哆嘞q ( 2 - 8 )= 西哆= 口q a t d i 4 i t d i 文本集s 内的文本的两两相似度之和等于8 口n 即： c o s ( a , ，t ) = ，三，c l , d j - d l q = d j f( 2 9 ) d l i t d t4 1 4 i e 珥 、 。 应当注意的是公式( 2 9 ) 包含了文本同自己的相似度。 2 1 5 特征选择 当使用向量空间模型来表示文本时，每一个不同的单词都作为特征空间中的 一维，每一个文本是特征空间中的一个向量。这种描述方法使得文本向量空间变 得非常的高维而且稀疏。这种高维稀疏的向量存在着很大的缺点，使文本聚类的 性能急剧的下降： ( 1 ) 影响了聚类速度； ( 2 ) 其中的一些噪声特征会损害聚类算法的精确性1 1 l l ； ( 3 ) 无论使用何种相似度函数，任意两个文本特征向量之间的相似度都倾向 于一个常数，从而无法区分文本之间的差异【m 。 因此，还需要对文本特征进行进一步地选择，以降低特征空间的维数。即在 文本集中，需从中选取一部分最具代表性的特征。 目前存在多种特征项选择的算法j 如信息增益( i n f o r m a t i o ng a i n ) 、互信息 ( m u t u a li n f o r m a t i o n ) ，z 2 统计量( c m ) 、文档频率( d o c u m e n tf r e q u e n c y ) 、单词权 ( t e r ms t r e n g t h ) 、单词熵( t e r me n u o p y ) 冬 1 6 1 3 1 0 但是由于大部分的筛选特征项的 算法都是有监督的，即通过计算类与特征之间的关系来重返最有区分力的特征子 集。由于在聚类前类信息往往是未知的，因而有监督的特征选择算法只能用于文 本分类而无法用于文本聚类。所以本文中选择了无监督的特征选择算法。 天津大学硕士学位论文第二章向量空问模型及相关技术 文档频率( d o c u m e n tf r e q u e n c y , d f ) 是最为简单的一种特征选择算法，它指的 是在整个数据集中有多少个文本包含这个单词文档频数有一个基本的假设，那 就是认为对一个类来说，出现次数过少的单词是没有意义的，它们的删除对分类 的结果不仅不会造成不利的影响，相反可能会有所提高，特别是当那些稀有的单 词刚好是噪声单词的时候。 文档频数最大的优势就是速度快，它的时间复杂度和文本数成线性关系，为 o ( ) ，所以非常适合于超大规模文本数据集的特征选择。不仅如此，文档频数 还非常地高效，在删除9 0 单词的时候，它的性能与信息增益和矿统计的性能 还不相上下，但是当更多的单词被移走的时候，它的性能会明显差于信息增益和 z 2 统计的性甜1 3 】。另外，文档频数常被集成在文本预处理中用来删除出现次数 过少或者出现次数过多的单词以提高后续处理的效率。 但是文档频率只考虑一个单词在多少个文本中出现，而忽略了个单词对不 同的文本来说其重要性可能是非常不同的。所以在这种情况下，文档频率很容易 受那些出现次数很多但是却平均分布在各个类中的单词的影响而变得很糟。为 此，有人提出了单词贡献度( t e r mc o n t r i b u t i o n ，t c ) 算法【1 4 】它认为一个单词的 重要性取决于它对整个文本集相似性的贡献程度。由文本相似度的计算公式 ( 2 - 5 ) ，整个文本集的相似度可以由公式( 2 1 0 ) 所推导，它可以看成是所有单词对 整个数据集相似度贡献的累加： s i r e ( d ) = s i m ( d l ，力) 日，d j e z ) o d , , d j = 。善w ( t ，4 ) w ( t ，t ( 2 - 1 0 ) t d i 一 e d n d l “ = w ( t ，z ) 川，嘭) t d 1 e o o d j “i 因此一个单词的贡献度即被定义为这个单词对整个文本数据集相似性的贡 献程度，如公式( 2 - 1 1 ) 所示： r c ( t ) = 。w ( t ，z ) 。w ( t ，乃)(211)d 4 ，e d a d j d t 、- 可以注意到，在计算权重时i d f 的使用提升了文档频数低的单词的权重，同 时降低了文档频数较高的单词的权重，而公式( 2 1 1 ) 又意味着文档频数越高的单 词将具有越多的累加次数，所以单词贡献度使得一个单词在权重和文档频数这对 矛盾之间达到了一个平衡：那些出现次数过少( 只出现在1 个文本中) 和出现过于 频繁( 出现在所有文本中) 的单词都将取得最小的单词贡献度值0 ，而那些相对出 现较多但又具有较高权重的单词将具有较高的单词贡献度。 天津大学硕士学位论文第二章向量空间模型及相关技术 单词贡献度是一种非常高效的特征选择算法，如果采用反向索引技术，它的 时间复杂度只有d ( m ) ，其中肘是所有单词的平均文档频数，它远小于文本 总数n 。 本文采用t c 算法进行特征选择。 2 2 向量空间模型小结 向量空间模型的最大优点在于它在知识表示方法上的巨大优势。在该模型 中，文本内容被形式化为多维空间中的一个点，通过向量的形式给出，把对文本 内容的处理简化为向量空间中向量运算，使问题的复杂性大为降低。也正是因为 把文本以向量的形式定义到实数域中，才使得模式识别和其他领域中的各种成熟 的计算方法得以应用，极大提高了自然语言文本的可计算性和可操作性。 但向量空间模型也存在一些问题，主要表现在以下几个方面： ( 1 )向量空间模型关于词间关系相互独立的基本假设( 正交假设) 在实际 环境中很难满足。在文本中所出现的词语之间往往存在一定的相关性， 即出现“斜交”情况，这对计算结果的可靠性会造成一定的影响； ( 2 )文本中有些信息以不同的形式出现。如“计算机”和“电脑”，指的是 同一个事物，而向量空间模型会认为它们是两个独立的单元，这样在 处理的时候很可能会丢失大量有用的信息； ( 3 ) t f i 矽是一种统计方法，只有当语料库具有一定规模，句子中包含的 词语数量足够多时，相关词语才会重复出现，这种统计方法的效果才 能体现出来； ( 4 )通过向量空间模型建立的文本向量中存在大量的零项，导致数据稀疏 现象。这会造成两方面的问题：存储开销和计算开销都会相应增加。 尽管如此，向量空间模型仍因为计算简单、检索速度快而在信息检索技术中 得到了非常广泛的应用。 天津大学硕士学位论文 第三章文本聚类常用算法及评价方法 第三章文本聚类常用聚类算法介绍 文本聚类是完全根据文本内容的相关性来组织文本集合，通过特定的处理和 相应的算法将整个文本集聚成若干个类，并使得类内的文本之间尽可能相似( 即 内容相关) ，而类间的文本尽可能差别明显( 即内容无关) 。文本聚类是文本分类 的种，是一种无指导的分类方法，即指原始文本库中的文本该分为几类以及其 相应的类别均是未知的。 文本聚类研究所依据的思想和方法起源于数值分类学的“聚类分析” ( c l u s t e r i n ga n a l y s i s ) 。早期的文本聚类分析主要依靠专业知识和经验，局限在定 性的范围内。后来随着学科的发展与信息量的激增，分类越来越细，需要分类的 文本对象也越来越多，这时仅仅依靠文本的一些特性进行定性划分也变得越来越 困难。于是，作为数值分类学的主要分支，聚类分析技术就被引入到文本聚类领 域。 文本聚类己经被广泛地应用在很多地方，比如b u c k l e y 等将其应用在信息检索 系统中用以提高信息检索的效率口5 1 ；z a m i r 等用文本聚类来组织搜索引擎返回的 结果t 1 6 1 ；c u t c i n g 等用文本聚类来帮助用户浏览超大规模的文本数据【1 _ 7 】；k o l l e r 通 过文本聚类来生成w 曲文本的分类层次树”s 】；还有用文本聚类来帮助用户管理和 组织个人e m a i l 、电子文档等。 聚类算法的研究早在2 0 世纪6 0 年代就开始了，但是受当时各方面条件的限 制并没有太大的发展，直到2 0 世纪9 0 年代才引起了广泛的关注，并取得非常重 大的突破，包括k - m e a n s 、c l a r a n s 、e m 、b i r t h 、d b s c a n 、s t i n g 、c l i q u e 等在内一大批新的聚类算法被陆续提出，目前仍j 日是一个非常热点的问题1 1 9 j 。 大体上，聚类算法可以划分为划分聚类算法、层次聚类算法、基于密度的聚 类算法、基于网格的聚类算法、基于模型的聚类算法以及其他算法等几大类，每 一大类中都拥有很多代表性的聚类算法。 ( 1 ) 划分方法( p a r t i t i o n i n gm e t h o d ) ： 给定一个疗个对象或元组的数据库，一个划分方法构建数据的七个划分，每 个划分表示一个类，并且k s 玎。也就是说，它将数据划分为七个组，同时满足 如下的要求：( i ) 每个组至少包含一个对象；( i i ) 每个对象必须属于且只属于一个 组。注意在某些模糊划分技术中第二个要求可以放宽。 给定要构建的划分的数目k ，划分方法首先创建一个初始划分。然后采用一 天津大学硕士学位论文第三章文本聚类常用算法及评价方法 种迭代的重定位技术，尝试通过对象在划分问移动来改进划分。一个好的划分的 一般准则是；在同一个类中的对象之间尽可能“接近”或相关，而不同类中的对 象之间尽可能“远离”或不同。还有许多其他划分质量的评判准则。 为了达到全局最优，基于划分的聚类会要求穷举所有可能的划分。由于这是 一个n p - h a r d 的问题，因此在实际应用时，绝大多数应用采用了以下两个比较流 行的启发式方法：( i ) k - m e a n s 算法，在该算法中，每个类用该类中对象的平均值 来表示。( i i ) k - m e d o i e s 算法，在该算法中，每个类用接近聚类中心的一个对象来 表示。这些启发式聚类方法对在中小规模的数据库中发现球状类很适用。为了对 大规模的数据集进行聚类，以及处理复杂形状的类，基于划分的方法需要进一步 的扩展。 ( 2 ) 层次的方法( h i e r a r c h i c a lm e t h o d ) ： 层次的方法对给定数据对象集合进行层次的分解。根据层次的分解如何形 成，层次的方法可以分为凝聚的和分裂的。凝聚的方法，也称为自底向上的方法， 一开始将每个对象作为单独的一个类，然后相继地合并相近的对象或类，直到所 有的组合并为一个( 层次的最上层) ，或者达到一个终止条件。分裂的方法，也称 为自顶向下的方法，一开始将所有的对象置于一个类中。在迭代的每一步中，一 个簇被分裂为更小的类，直到最终每个对象在单独的一个类中，或者达到一个终 止条件。 层次的方法的缺陷在于，一旦一个步骤( 合并或分裂) 完成，它就不能被撤销。 这个严格规定是有用的，由于不用担心组合数目的不同选择，计算代价会较小。 但是，该技术的一个主要问题是它不能更正错误的决定。有两种方法可以改进层 次聚类的结果：( i ) 在每层划分中，仔细分析对象间的“联接”，例如c u r e 和 c h a m e l e o n 中的做法。( i i ) 综合层次凝聚和迭代的重定位方法。首先用自底向上的 层次算法，然后用迭代的重定位来改进结果。例如在b i r c h 中的方法。 ( 3 ) 基于密度的方法( d e n s i t y - b a s e dm e t h o d ) ： 绝大多数划分方法基于对象之间的距离进行聚类。这样的方法只能发现球状 的簇，而在发现任意形状的类上遇到了困难。随之提出了基于密度的另一类聚类 方法，其主要思想是：只要临近区域的密度( 对象或数据点的数目) 超过某个阈值， 就继续聚类。也就是说，对给定类中的每个数据点，在一个给定范围的区域中必 须至少包括某个数目的点。这样的方法可以用来过滤“噪声”孤立点数据，发现 任意形状的簇。 d b s c a n 是一个有代表性的基于密度的方法，它根据一个密度阈值来控制 簇的增长。o p t i c s 是另一个基于密度的方法，它为自动的和交互的聚类分析计 天津大学硕士学位论文第三章文本聚类常用算法及评价方法 算一个聚类顺序。 ( 4 ) 基于网格的方法( g r i d - b a s e dm e t h o d ) ： 基于网格的方法把对象空间量化为有限数目的单元，形成了一个网格结构。 所有的聚类操作都在这个网格结构( 即量化的空间) 上进行。这种方法的主要优点 是它的处理速度很快，其处理时间独立于数据对象的数目，只与量化空间中每一 维的单元数目有关 s t i n g 是基于网格方法的一个典型例子。c l i q u e 和w a v e c l u s t e r 这两种算 法既是基于网格的，又是基于密度的。 ( 5 ) 基于模型的方法( m o d e l b a s e dm e t h o d ) ： 基于模型的方法为每个类假定了一个模型，寻找数据对给定模型的最佳拟 合。一个基于模型的算法可能通过构建反映数据点空间分布的密度函数来定位聚 类。它也基于标准的统计数字自动决定聚类的数目，考虑“噪声”数据或孤立点， 从而产生健壮的聚类方法。这类算法主要分为两类：统计学方法和神经网络方法。 上述的这些算法基本上都是不针对文本数据而提出的，但是它们其中一些己 经被广泛应用于文本聚类，主要包括k - m e a n s 、层次凝聚法和d b s c a n ，这三个 算法同时也是划分聚类算法、层次聚类算法和基于密度的聚类算法的典型代表。 k - m e a n s 、层次凝聚法和d b s c a n 都有一个共同的特征就是建立在距离或者说相 似度计算的基础之上，但是文本数据因为其高维稀疏、近义词和多义词等属性使 得文本数据之间的距离在任何一种距离计算方式下都不准确，所以这些算法在某 些情况下会产生不理想的聚类结果，比如层次凝聚法中的s i n g l e l i n k n - j 能产生链 式聚类结果【，d b s c a n 可能产生一个大类加上许多只包含一个文本的小类的 结果。为此，也有很多不基于距离的聚类算法被提出并应用于文本聚类。比如f u n g 等提出了使用关联规则中的频繁项集来进行文本层次聚类的方法【2 0 j ，z a m i r 等提 出了名为“s u f f i x t r e ec l u s t 翻n g ( s t c ) ”的文本聚类方法，这个方法通过寻找多 个文本之间的共有词组来创建文本簇1 2 i j ，d h i l l o n 使用双向光谱图分割技术来同 时聚类单词和文本等等【2 2 】。 总的来说，最常用于文本聚类的还是k - m e a n s 、s i n g l e - l i n k 和d b s c a n 三 种经典算法，所以下面就对它们进行进一步的介绍。 3 1k - m e a n s 算法 k m e a n s l 2 3 1 是最早也是最典型的划分聚类算法，它己经被广泛地应用于文本 天津大学硕士学位论文 第三章文本聚类常用算法及评价方法 聚类。k - m e a n s 的基本思想为：对于给定的聚类数目置，首先随机选择阶文本作 初始的类中心，然后根据每个文本与各个类中心的相似度，将它赋给最相似的类 然后重新计算每个类