（计算机软件与理论专业论文）文本挖掘中聚类技术的研究.pdf

中山大学硕士学位论文 【4 刁 【4 3 】 【4 4 】 【4 5 】 ( s i g i r t 9 2 ) ，p p 318 3 2 9 ，l9 9 2 m a r t i l le s t e r ，h a l l s p e t e rk r i e g e l ，j o r gs 髓d e r ，x i a 0 、e ix u ad e l l s i t y - b a s e d a l g o r i t u nf o rd i s c o v e r i n gc l u s t e r si l ll a r g es p a t i a ld a ta _ b a s e sw i t hn o i s e i np r o c e e d i n g so ft h e2 “oi n t e m a t i o n a lc o n f e r e n c eo nk n o w l e d g ed i s c o v e f y a i l dd a t am i l l i i l g ( k d d 9 6 ) ，p p 2 2 6 - 2 31 ，l9 9 6 张猛文本聚类中参数自动设置技术的研究与实现东北大学硕士学位 论文2 0 0 5 t 色u v ok o h o n e n s e l f o r g a n 泣e df o r m a t i o no ft o p o l o g i c a l l yc o r r e c tf e a t 瑚墨 m a p s b i o l o g i c a lc y b e m e t i c s ，4 3 ：5 9 - 6 9 ，l9 8 2 o r e nz a m 远o r e ne t z i o m ，o 而dm a d a n i ，砥c h a r dm 妇r p f a s ta n d i n t u i t i v ec l u s t e r 讪go fw r e bd o c u m e n t s ，i np m c e e d i n g so ft h e3 ma c m s i g k d di 1 1 t e m a t i o n a lc o n f e r e i l c eo nk i l o w l e d g ed i s c o v e r yi l ld a t am i l 血培 ( k d d 9 7 ) ，p p 2 8 7 - 2 9 0 ，19 9 7 【4 6 】 o r e nz a m 记o r e ne t z i o m w _ e bd o c u m e mc l u s t e r i n g ：af e a s i b i l i t y d e m o n s t r a t i o n ，i np r o c e e d i i l g so ft h e2 1 “a i l i l u a li n t e m a t i o n a la c ms i g i r c o n 诧r e n c eo nr e s e a r c ha 1 1 dd e v e l o p m e n tmi n 南瑚a t i o nr e t r i e v a l ( s i g ir 9 8 ) 。p p 4 6 5 4 ，19 9 8 【4 7 】y 删u nl i ，s o o nm c h m g ，j o h nd h o l t t e ) ( td o c u i n e mc l u s t e r i l l gb a s e d o nf r e q u e n tw r o r dm e 锄i n gs e q u e n c e s d a t a & k o w l e d g ee n g i l l e e r 协v 0 1 6 4 ，d d 3 81 4 0 4 ，2 0 0 8 中山大学硕士学位论文 论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究 工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人 或集体已经发表或撰写过的作品成果。对本文的研究作出重要贡献的个人和集 体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：丝是 日期：停厂月孑日 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学校有权保留 学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版，有权将学 位论文用于非赢利目的的少量复制并允许论文进入学校图书馆、院系资料室被查 阅，有权将学位论文的内容编入有关数据库进行检索，可以采用复印、缩印或其 他方法保存学位论文。 学位论文作者签名：逐值 日期：乎五9 日 导师签名： 日期：谱厂月占日 中山大学硕士学位论文 信业的开放和计算机、通信技术的发展，电信市场也正在迅速扩张并越发竞争激 烈。数据挖掘在电信行业中的应用有助于理解商业行为，确定电信模式，捕捉盗 用行为，更好地利用资源和提高服务质量。此外，数据挖掘在金融系统和生物医 学等方面的研究与应用也获得了很大成功，并促进了这些行业的发展【1 1 。数据挖 掘在各行各业中几乎都可以应用，这与数据挖掘功能众多是密不可分的。归纳起 来，数据挖掘的功能主要包括关联分析、有监督的数据分类、无监督的数据聚类、 序列模式分析、趋势预测、时间序列中的相似性搜索等等。总的来说，作为一项 正在发展中的技术，数据挖掘正日益得到各界的重视并被广泛应用。 尤其是网络技术迅速发展的今天，人们越来越感受到了大量数据信息的冲 击，而这些数据大部分都是以文本形式存在、以电子文档作为载体来传播。有统 计数据表明，人们日常生活中所接触到的信息有8 0 左右是以文本的形式存在。 文本挖掘就这样应运而生了，它作为数据挖掘的一个分支，专注于分析以文本形 式存在的数据信息，通过定量计算和定性分析的方法，发现文本数据中的概念、 文本之间的相互关系和相互作用，为用户提供有用的知识和信息。与传统数据挖 掘最大的不同点就是，文本挖掘处理的是一种半结构化的文本信息，而不是传统 数据挖掘中采用的结构化数据信息。这种数据可能包括标题、作者等结构化的数 据，也包括了文本内容等很多非结构化的数据，因此在文本挖掘中很多时候都需 要自然语言理解的支持。 随着大量文本数据的获得，传统的信息检索技术已经越来越不适应日益增加 的大量文本数据处理的需要。在如今这个信息激增的年代，网上的搜索引擎动辄 返回成千上万条相关的检索结果，而且对于同一关键字检索出来的结果有可能对 应于多个不同的主题。在这些可以获得的大量文本数据中，其实只有很少一部分 是用户真正所需要的。人们已经不再满足于数据资源的获取，如何对这些数据进 行有效的分析和管理正成为日益迫切的需求。聚类分析作为一种重要的数据分析 与挖掘技术，能够很好地满足这方面的需求。 文本聚类是文本挖掘研究的主要方法和手段之一，能够从大量的文本数据中 发现潜在有趣的知识和规律。文本聚类通过对文本内容进行分析，将原始的文本 集分成若干个簇，同时要求簇内文本内容的相似性尽可能大，而簇之间的相似度 尽可能小。因此，对文本数据进行聚类分析，能够帮助用户把具有相同主题的文 2 文本挖掘中聚类技术的研究 档分到同一个类中，不同主题的文档分到不同的簇中，这样可以协助人们更好地 对大规模文本进行管理和理解。同时，文本聚类也能作为一种有效的文本预处理 步骤，为进一步的文本分析提供初步的语料结构。随着信息检索的发展，文本聚 类已被成功地应用到提高信息检索的质量、话题的自动发现、文档摘要等各方面， 在文本挖掘领域扮演着日益重要的角色。 在文本聚类的应用方面【2 】，比较典型的例子有哥伦比亚大学开发的多文档自 动文摘系统n e w s b l a s t e r 。n e w s b l a s t e r 将每天发生的重要新闻进行聚类处理，并对 同主题的文档进行冗余消除、信息融合、文本生成等处理，从而生成一篇简明扼 要的摘要文档。另一个典型的应用就是对搜索引擎返回的结果进行聚类，使用户 迅速定位到所需要的信息，这方面比较成功的系统有v i v i s i n 的 ( h t t p ：价嗡啊v ：i v i s i m o c o m ) 和i n 南n e t 、 ，a r e ( 1 l t t p ：肌啊i i 面n e t 眦鹏c o m ) 等，这 些系统允许用户输入检索关键词，然后对检索到的文档进行聚类处理，并输出系 统对各个不同类别的简要描述，从帮助用户缩小检索的范围，让用户只需关注比 较感兴趣的主题。 1 2 国内外研究现状 国外对于文本挖掘的研究开展较早，已经有几十年的历史。到目前为止，国 外的文本挖掘研究已经从最初的可行性基础研究到试验性研究进入到了实用化 阶段，并在邮件分类、电子会议、信息过滤、w e b 文本挖掘方面取得了较为广泛 的应用。同时，国外出现了很多融合文本挖掘思想和技术的应用的企业，s e m i o 公司研发的s e m i o m a p 工具可以提供自动的文本处理，i b m 公司出品的智能化文本 挖掘器( i n t e l l i g e n tm i n e rf o rt e x t ) 适合大型软件公司的开发人员使用， b r i g h t w a r e 公司的产品b r i g h t w a r e 是一个自动的电子邮件阅读和解释系统例。 国内进行文本挖掘的研究较晚，在2 0 世纪9 0 年代中、后期国内的研究发展较 为迅速，并取得了一定的成就，如中科院计算机语言信息工程研究中心研究的内 容是汉语分词、自然语言接口、句法分析、语义分析、自动分词等等，清华大学 电子系的丁晓青、吴佑寿研究的是手写汉字识别( 动态匹配) 、汉字识别多分类器 集成( 综合识别法) 等1 3 j 。 文本挖掘作为数据挖掘领域中的一个重要课题，近年来也得到了很多机构和 3 中山大学硕士学位论文 第2 章文本聚类相关知识 文本挖掘是近几年来数据挖掘领域的一个新兴分支，也是当前一个非常活 跃的一个研究领域。从技术上层面上来讲，它可以说是数据挖掘和信息检索这两 门学科的交叉。文本挖掘与传统数据挖掘的差别主要两者所处理的数据之间的巨 大差异。传统数据挖掘所处理的数据是结构化的，如关系数据库中的数据、事务 数据、数据仓库的数据，这些数据的特征数目一般不会超过几百，而文本数据是 没有结构的或者是一种半结构化的，在转换为特征矢量后特征数通常都达到成千 上万甚至几十万。所以，文本挖掘在采用传统数据挖掘技术的同时，又具有自己 鲜明的特性。 文本聚类过程主要由文本预处理，文本模型表示，文本相似度计算，文本聚 类和聚类结果评价这几个步骤组成。其中文本聚类主要是应用聚类算法对文本进 行无监督的分类，本文将在第三章对一些常用的聚类方法进行介绍。 2 1 文本预处理 由于文本数据的特殊性，在对其进行分析、挖掘之前进行一些相关的预处理 工作。经过预处理后，文本被表示成一种结构化的形式，这样就可以把数据挖掘 中的一些算法应用到文本数据之上。当然，对于预处理后的文本，需要保证这种 结构化的形式能够充分体现出文本数据自身的特点，同时又能突出不同文本数据 间的差异，以便于文本的区分。 总之，文本的预处理技术对于文本挖掘来说是一个不可忽视的重要环节。也 可以说，预处理的质量好坏将直接影响到最终的挖掘效果。本节将主要介绍和文 本聚类相关的几个预处理步骤。 2 1 1 分词 文本预处理的第一个关键问题就是分词，也就是将一整个文档的内容拆分成 许多词所组成的集合。在英文的分词中，分词的方法比较简单，一般直接根据文 本中词的连接标志( 如空格，t a b 符、换行符等) 把文本拆分成一个一个的单词。 对一个包含多个文本的文本集进行分词后，这些不同的单词所组成的集合就构成 8 文本挖掘中聚类技术的研究 了文本集的字典。对于中文的分词来讲，分词的过程相对来说就比较复杂了，因 为中文文本中除了句子之间的标点符号之外，所有字符都连接在一起，而且中文 的语法又是灵活多变的。关于中文的分词方法在相关文献中也有很多的介绍，由 于本文所使用的数据都是基于英文的文本，所以本文主要介绍和英文相关的一些 预处理技术。 2 1 2 词根还原 所谓词根还原【3 4 1 ，主要是针对英文中单词的不同词形而言的，其目的就是把 本质上是同一个单词的不同单词表示形式进行归一化处理。英文中的一词多形比 较常见的主要有这样几种情况：其一，动词有现在分词、过去分词、第三人称单 数等不同形式；其二，名词有单数和复数形式；其三，同一词根所对应的形容词 和副词等不同形式。虽然一个单词在不同的语义背景下以不同的形式出现，但其 实际上表达的是同一意思，如果不将这些不同的词形进行还原为其基本形式，则 在文本的表示模型中是将它们作为不同的单词对待的，这样就很可能导致那些具 有相同主题的文本却只有很低的相似性，从而影响文本聚类的质量。比如有如下 的两个文本： 文才1 ： ”iu s ec o m p u t e rt od e s i g ns o m e t h i n g ” 文本2 ：”c o m p u t e r sc a nb eu s e df o rd e s i g n i n gb ym e ” 我们可以很明显的看出上面的两个文本所要表达的意思是完全一致的，但是 对这两个文本进行分词后就会发现这样一个事实：两个文本中没有一个相同的单 词。也就是说，在计算机看来这两个文本是完全无关的。之所以会出现这样一种 情况，就是因为在两个文本中，同一个单词使用了不同的形式进行描述。如果对 着两个文本中的单词进行词根还原处理，即把“c o m p u t e r s ”词根还原为 “c o m p u t e r ”，“u s e d 词根还原为u s e ，“d e s i g n i n g ”词根还原为“d e s i g n ， 则两个文本就非常相似了。 至于词根还原的方法，普遍都是使用s t u a r tj b 提出的p o r t e r 方法。在 本文所使用的用于文本预处理的d r a g o nt o o l k it 工具包中，也使用了p o r t e r 方 法进行词根还原。总的来说，词根还原不但可以让使用不同形式的单词但是表达 相同主题的文本具有更高的相似性，从而得到更好的文本聚类的结果，还可以大 9 中山大学硕士学位论文 大减少字典中词的数量，从而提高文本聚类的性能。 2 1 3 停用词过滤 停用词是指那些与文本所包含的内容关系不大但又在文本中出现频率很高 的词。如果不对停用词进行处理，则计算机将它们与一般的单词同等对待。由于 停用词在每个文档中几乎都具有很高的出现频率，因此在进行文本相似度计算或 者训练模型求参数的过程中会引入很大的误差，从而影响文本聚类的质量。为了 减少停用词对聚类结果的影响，一般都是将它们作为文本中的噪声数据，在文本 预处理时直接从字典中去掉【3 4 1 。 本文使用了一个包含4 2 0 个停用词的文本文件，其中主要包括了一些英文 文本中最常见的词，比如“a b o u t ，a n d ，a 1 1 ，i ，m e ，m a n y ，y o u ，t h e ，o f ，t o ， f o r 等。如果字典中有某个词在停用词文件中，那么在预处理时将把这个单词 从字典中去掉。 2 1 4 文本降维技术 文本集中所有词的数目一般来说都非常巨大，如果直接使用向量空间模型对 文本进行聚类，会极大影响文本聚类算法的执行效率，因此很多时候在文本聚类 前会进一步降低文本的维度。已经有研究表明，必要的文本维度缩减不但能提高 文本聚类算法的效率，而且还能提高其精确度【3 5 1 。在文本挖掘中，使用比较多的 降维技术主要有特征选择( f e a t u r es e l e c t i o n ) 和特征提取( f e a t u r e e x t r a c t i o n ) 。 特征选择是从文本的原始特征空间中，选择一小部分能够反映文本主题的特 征子集来表示文档，从而在不损失文本信息的情况下达到文本降维的目的。从某 种意义上来说，特征选择可以看成是一个启发式的搜索过程，其目标是从原始的 特征空间中搜索出一个最优的子空间。在现有的文本数据的特征选择的研究中， 一般都是通过一些衡量单词重要性的评价函数来进行文本特征选择。使用评价函 数进行特征选择的过程比较简单，它首先根据这个评价函数来给每一个单词计算 出衡量其重要性的评估分，然后对所有的特征按照评估分大小进行排序，最后依 据从大到小的顺序选取一定数目的特征作为文本的特征子集。在文本聚类研究 1 0 中山大学硕士学位论文 模型作为文本的表示很不精确，不能反映特征项对于文本的重要性，而且缺乏定 量的分析。 2 2 2 向量空间模型 向量空间模型( v e c t o rs p a c em o d e l ，v s m ) 是s a l t o n 在2 0 世纪6 0 年代提出来 的，也是近年来应用较多而且效果也比较好的一个模型，现在已经被广泛的应用 在各大搜索引擎中对文本进行表示。在布尔逻辑模型中，向量中每个元素的取值 为o 或者1 ，它体现不出一个词在文档中的重要程度。向量空间模型也是将文档映 射为一个特征向量，但是对于每一个词f ；，都会根据其在文档中的重要程度赋以 一定的权值嵋( d ) ，其表示形式为：y ( d ) = ( 川( j ) ，w 2 ( d ) ，( d ) ) 。 权值的计算方法主要有两种。最先是使用词频t f ( t e 硼f r e q u e n c y ) 方法来 计算词的权值，它用词在文档中出现的次数来反映其在文档中的重要程度，词t 在文档d 中的权值w ( d ) 一般表示为斫( d ) 。但在实际的文本中，往往并不是一个 词出现得越多就越重要，如果一个词在整个文本集中都出现的非常频繁，那么它 对单个文档来说就应该不是很重要，所以更为普遍有效的词的权值表示法是采用 t f 宰i d f ( t e r mf r e q u e n c yi n v e r s ed o c u m e n tf r e q u e n c y ) 方法。t f 术i d f 综合考 虑了词在单个文本中出现的频率和该词在整个文本集中出现的频率，它定义一个 词的权值与其在该文档中的出现频率成正比，而与其在整个文本集中的出现频率 成反比。公式( 2 一1 ) 是t 融i d f 方法的权值计算公式。 矿毙彰( d ) = 顷( d ) 宰比彰( d ) ( 2 一1 ) 其中，彰( d ) 表示字典中第f 个词在在文本d 中出现的次数，颂( d ) 表示这个词在 文本集中区分不同文本的能力，可通过公式( 2 2 ) 来计算。 磁( d ) = l o g ( ) ( 2 2 ) 其中，绝表示文本集中包含字典中第f 个词的文本数目，而则表示文本集中所 有文本的数目。 公式( 2 一1 ) 虽然简单，但它没有考虑文本的长度对词权值的影响，因此很 多情况下都会对公式( 2 一1 ) 进行规范化处理，减少文本的长度对词的权值的影 1 2 文本挖掘中聚类技术的研究 响，改进后的计算见公式( 2 3 ) 。 删( 俨毒丝丝 蔷似p 州嘞2 其中，嚣为文本矗中词项的个数。 ( 2 3 ) 根据t 胁i d f 权值表示法，文档集中包含某一特征词项的文档越多，说明它区 分文档类别属性的能力越低，其权值也越小；另一方面，某一文档中某一词条出 现的频率越高，说明它区分文档内容属性的能力越强，其权值也越大。 向量空间模型的最大优点在于它在知识表示方法上的巨大优势。在该模型 中，文本被形式化为多维空间中的一个点，通过向量的形式给出，把对文本的处 理简化为向量空间中的向量运算，使问题的复杂性大为降低。虽然如此，向量空 间模型也还是存在一些不足之处。首先，使用向量空间模型对文本进行表示时， 文本的维数会非常高，这无疑会增加向量运算的复杂性；其次，向量空间模型一 个重要的假设就是字典中的词与词之间是相互独立的，这样一个词所在的上下文 环境和前后词之间的语义关系都被丢失了。目前已经有一些改进词的权重计算的 方法，但是效果都不是非常的明显，其主要原因在于自然语言中包含了丰富的语 义信息，仅采用简单的向量运算来代替对文本的操作，总是会存在误差的。在文 本挖掘领域，如何减少文本内容映射到单个的词时大量有效信息的损失依然是今 后值得关注和需要解决的一个问题。 2 3 相似度度量 在文本聚类中，具有相同主题的文本能够自动聚到同一个类中，就是因为相 同主题的文档的内容具有比较强的相关性，而不同主题的文档的内容具有比较弱 的相关性。因此，在对文本进行聚类前，必须首先计算各文档之间的相关性，然 后再根据相关性决定哪些文档属于同一类。文本之问相关性的度量是自然语言处 理、信息检索、文本挖掘和w r e b 挖掘等领域中的非常重要的一种技术，也一直 受到广大研究人员的关注。在实际的文本挖掘中，通常根据文本的表示模型( 如 最常用的向量空间模型) ，采用基于相似度计算的方法来衡量不同文本之间的相 关性，因此文档之间的相关性一般都根据文档之间的相似度来衡量。两个文档之 1 3 中山大学硕士学位论文 间的相似度越大，则说明这个两个文档之间越相关。 不同的文本聚类方法，在文本聚类过程中会涉及到不同类型的相似度度量方 法。归纳起来，文本聚类时所使用到的相似度的度量主要有三种类型：文档问的 相似度度量、簇间的相似度度量、文档与簇间的相似度度量。在聚类过程中，不 同的相似度度量方法也往往会产生不同的聚类结果。在本文的研究中，主要是针 对使用向量空间模型表示的文本，因此下面的相似度度量方法都是基于v s m 上 的。此外，最近有些研究者针对现有基于相似度度量的文本聚类方法精确度不高 的问题，提出基于语义模型的文本聚类方法，这些方法使用基于模型的方法来衡 量文档和簇之间的相似性，本文也在后面单独作为一节介绍。 2 f 3 1 文档间的相似度度量 在向量空间模型中，文本被表示成多维空间中的一个向量，文档之间相似度 的度量也就转化成其对应向量的计算。文档之间相似度的度量方法主要有两种， 一种是使用欧几里得距离( e u c l i d e a nd i s t a n c e ) ，其计算如公式( 2 4 ) 所示。 几一 如，g 力= 、( 一) 2 ( 2 4 ) yt 司 其中，如f ( f ，) 表示两个文档f 和之间的距离( 距离越大，相似度则越小) ，和 w 膻分别表示字典中第七个词在文档f 和歹中所占的权值，刀表示字典中词的个 数。此外还有其他一些距离度量，如m a n h a t t a n 距离、m i n k 0 w s k i 距离等。 另外一种衡量两个文本f 和，之间相似性的方法就是通过余弦相似度来度 量，其计算如公式( 2 5 ) 所示。 s 砌c “，= 喜止喜面 c 2 5 ) 其中，s 砌( f ，力表示文本f 和歹之间的余弦相似度值，和w 成分别表示词后在文 档f 和，中所占的权值，刀表示字典中词的个数。 使用向量空间模型对文档内容表示时，每个文本所对应的向量都会具有 高维稀疏的特点。一般来说，单个文档中通常只包含字典中很少的一部分词。由 1 4 文本挖掘中聚类技术的研究 示类巧中的对象个数，刀表示文本集中总的文本个数。在评估结果中，n m i 值的 范围是0 1 ，其值越大，表示聚类精度越高。当n m i 的值接近1 的时候说明聚类结 果中的簇标记接近原有的类别标记，当n m i 的值接近o 的时候则说明聚类过程只是 进行了一个随机的类别划分。 2 5 本章小结 本章主要介绍了与文本聚类相关的背景知识。文本数据与传统数据挖掘中的 数据不同，它是一种半结构化的数据，在对文本进行聚类等挖掘前必须先对文本 数据集中的文本进行分词、特征选择等预处理，得到用来表示文本内容的词项。 向量空间模型是实际中最常使用的一种文本表示模型，它将文本数据用词项所构 成的特征向量表示，方法简单，容易被计算机所理解。在对文本进行聚类分析时， 需要度量文档、簇间的相似度，以便将相似的文档聚到同一个类中；此外，在得 到聚类结果后，还要对结果进行评估，衡量所用聚类算法的有效性。这些都为后 续工作的展开提供了一个良好的基础。 2 l 中山大学硕士学位论文 据集的分布情况比较熟悉。 其次，k - m e a n s 算法在开始执行时会初始化k 个簇中心，不同的簇中心初始 值也经常会导致不同的聚类结果。 第三，艮m e a i l s 算法对于数据集中的噪声和孤立点非常敏感，很容易受例外 情况的影响。因此，该算法适用于发现球状簇，但不适合发现非凸面形状的簇， 也不适合大小差别较大的簇。 最后，针对文本数据高维稀疏性的特征，k - m e a l l s 算法也会存在一些局限性。 因为算法将簇的中心作为相似性的评比标准，这样可能导致被划分到同一个均值 表示的簇中的某两个对象有较大的差异。 最近，s t e 湖) a c h 等对几种文本聚类算法进行了比较【3 5 1 ，并在此基础上提出 了k - m e a n s 算法的一种改进算法b i s e c t 啦k - m e a l l s 。他们通过在几个数据集上 的实验，说明b i s e c t i l l gk m e a n s 算法在大多数情况下能取得比k - m e a n s 和层次 聚类算法更好的聚类结果。该算法依然以簇的数目k 为参数，但是每次都递归 地从已有的簇中根据某个原则选择一个簇将其划分为两个簇，直到生成k 个簇 为止。图3 2 给出了b i s e c t 咄k - m e a n s 算法的描述。 算法：b i s e c t i i l gk - m e a l l s 输入：簇的数目后，文本数据集d 输出：尼个簇的集合 算法过程： ( 1 ) 将整个文本集作为一个初始的簇； ( 2 ) 聆p e a t ( 3 ) 选择一个用于划分的簇； ( 4 ) 对被选择的簇中文本使用k - m e a n s 算法将其聚类成两个簇； ( 5 ) 硼t i l 所要的簇数为止； 图3 2b i s e c t i n gk _ m e a n s 算法 b i s e c t i i l gk - m e a l l s 算法的关键是如何从当前的簇中选择被继续划分的簇，这 可以根据簇中对象的数目，或者是簇的整体相似度来判断，也可以把各种因素综 合起来进行选择。但是从各种策略的实验看来，各种判定策略的差别很小，所以 中山大学硕士学位论文 会根据两个簇之间的相似度或距离来判断。三种广泛被采用的簇之间距离的度量 方法是单连接法、全连接法、平均连接法。其中，单连接法采用两个簇间距离最 近或最相似的对象来定义其距离，而全连接法刚好相反，采用两个簇间距离最远 或相似度最小的对象来定义其距离。因此，单连接法和全连接法代表了簇间距离 的两个极端，它们都会对数据集中的孤立点或噪声数据过分敏感。平均连接法则 是属于单连接法和全连接法之间的一种折中方法，它可以减少或克服孤立点或噪 声数据对簇间距离的影响。因此，在凝聚层次的文本聚类算法中，平均连接法是 普遍所使用的一种文本簇间距离的度量方法。 算法：h a c 输入：簇的个数后，z 个文本的数据集d 输出：尼个簇的集合 算法过程： ( 1 ) 将d 中的每一个文本碣看作只包含一个对象的簇q = 碱 ，产生初始聚类 c = k ，) ； ( 2 ) 他p e a t ( 3 ) 计算c 中每两个簇之间的相似度s 砌( q ，c ，) ； ( 4 ) 选取具有最大相似度的两个簇q 和勺，即a f g m a ) 【j 砌( q ，巳) ，并将q 和巳合 并成一个簇= qu c ，从而构成d 的一个新的聚类c = c 1 ，一。 ； ( 5 ) u n t i lc 中只剩下后个簇为止； 图3 4h a c 文本聚类算法 h a c 算法尽管比较简单，但是在进行簇的合并时需要检查和估算大量的对 象或簇，因此时间复杂度比较高，达到了d 仰2 ) ，这也导致了该算法不具有很好 的可伸缩性，对于大规模的文本集合，有其不适用性。此外，h a c 算法经常会 遇到选择合并簇的困难，因为一旦选择了两个簇进行合并，下一步的处理将是针 对新生成的簇。已作的合并处理不能被撤销，簇之间也不能交换对象。这样的合 并操作，如果在某一步没有很好地选择的话，就可能会导致低质量的聚类结果。 改进层次聚类算法的一个方法就是将层次聚类和其他的聚类技术进行集成， 形成多阶段聚类。s c 甜e r g a t h e r 【4 1 l 是一个为大众所熟知的文档浏览系统，它就是 文本挖掘中聚类技术的研究 3 5 基于后缀树的方法 基于划分的方法、基于层次的方法、基于密度的方法和基于神经网络的方 法等都是数据挖掘中传统的聚类方法。这些方法在文本聚类中都是使用向量空间 模型，把文本看作词的集合，而没有考虑词与词之间的序列联系，这样就丢失了 文本中和语义相关的很多有价值的信息。为了充分利用文本中的词信息，文献h 5 】 提出了使用词序列( w r o r ds e q u e n c e ) 进行文本聚类的思想，在此基础上文献【4 6 l 对基于词序列的方法进行了总结和完善，并提出了一种基于后缀树的文本聚类算 法s t c ( s u 伍x1 r e ec l u s t e r ) 。与传统的那些算法不同，s t c 算法把文本看作 一个由所有词的有序序列组成的字符串( s t r i i l g ) ，其基本思想就是使用后缀树结 构对字符串进行表示，然后对共享公共的词或短语( 短语被认为是一个或多个词 的有序序列) 的文本进行聚类。 s t c 算法主要包括了两个步骤：基本簇的识别、合并基本簇。下面以s t c 算法为例介绍基于后缀树的文本聚类方法。 一、基本簇的识别 在这个过程中，算法首先根据文本集构造一棵后缀树。由后缀树的定义可知， 后缀树中每个节点与标识其的某个词或短语相关联，而这个词或短语为某些字符 串所共享。因此，在后缀树中每个节点都代表了一些文档的集合，如果集合中的 文档数超过了某个阈值，就认为这个节点对应一个基本的簇，这样就可以根据后 缀树找出所有的基本簇，每个簇都可以由标识该节点的词或短语来表述。图3 8 是一棵包含三个字符串的后缀树，表3 1 是根据图3 8 所得到的基本簇表( 最小 支持度为2 ) 。 二、合并基本簇 文本集中的文本可能共享多个词或短语，因此所得到的基本簇可能是唯一 的，也可能和其它的基本簇共享多个文本。如果两个基本簇之间所包含的文本重 叠过多，则认为这它们是相似的，应该合并成一个簇。s t c 采用一种二元相似度 的方法衡量两个簇是否相似，即如果两个基本簇之间共享的文本数超过了各自的 一半，则认为这两个基本簇是相似的，相似度取值为1 ；否则认为它们不是相似 3 l 文本挖掘中聚类技术的研究 信息在其它簇的形成过程中也起了非常重要的作用，不能简单的通过这种删除来 避免簇之间文本的重叠。 针对f t c 算法的不足，本文提出一种新的基于频繁项集的文本聚类算法， 我们把它称为f i t c ( f r e q u e n ti t e m b a s e dt e x tc l u s t e 血g ) 。本文提出该算法的主 要思路就是在根据初始文本簇形成聚类时，同时从文本簇和文本两方面考虑。具 体的说，就是首先从初始文本簇中选择出一些质量比较好的簇，同时这些簇能够 覆盖文本集中所有的文本，然后再根据频繁项集中的项来评估簇与文档之间的相 关性从而确定每个文本所属的簇。 4 2 挖掘文本集中的频繁项集 基于频繁项集进行文本聚类的首要步骤就是从文本集中找出同时频繁出现 的词的集合，这也是它与传统文本聚类方法的一个主要区别。本节主要介绍文本 聚类中和频繁项集相关的几个概念，以及所采用的挖掘频繁项集的算法。 4 2 1 基本概念 定义l ：事务 事务指文本集中的文本，每个事务对应一个文本。 定义2 ：项 项指文本中的词项，每个项对应一个词项。 定义3 ：项集 项的集合称为项集。包含七个项的项集称为后项集。 定义4 ：频繁项集 设，= ，厶，厶 是项的集合，事务丁是，中项的集合， 丁= ( ， ，f 2 ，乙 ) ，其中，( 1 f 朋) ，仍是事务的唯一标志符。给定一个 数据库d 和一个最小支持度值m 泐印，找出所有，的子集，这些子集在d 的事 务中出现频率大于或等于聊觚印与d 中事务总数的乘积。每个子集称为一个频 繁项集。 3 7 文本挖掘中聚类技术的研究 所使用的a p r i o r i 算法的描述。 算法：a p r i o r i 输入：事务数据库d ，最小支持度m 吣妒 输出：d 中所有的频繁项集三 算法过程： ( 1 ) 厶2 缅d - 舭q u e n t _ 1 一i t e l l l s e t s ( d ) ； ( 2 ) 如r ( k _ 2 ；厶一l ；k 十+ ) ( 3 )q = a p r i o 衄e n ( 厶一1 ) ； ( 4 ) 南re a c ht r a n s a c t i o nr d s c a l ld 旬rc o u n t s ( 5 )c ，= s u b s e t ( q ，f ) ；g e t t h es u b s e t so f ，t h a ta r ec a n d i d a t e s ( 6 ) 向r e a c hc a n d i d a t ec c f ( 7 )c c d 材力f + + ； ( 8 )厶2 c gi c r d 溯f l i l i n _ s u p ( 9 ) r e t 啪三= u t 厶； p r o c e d u r ea p r i o r i _ g e n ( 厶一l ，l l l i n s u p ) ( 1 ) 南re a c hi t e m s e t ，1 厶一l ( 1 ) 如re a c hi t e m s e t 乞厶一1 ( 2 )i f ( 【1 】= 如【1 】) 人( 厶【七一2 】= ，2 【七一2 】) t h e n ( 3 )c = 冈乞； ( 4 )i f l l a s _ i i l 舭q u e n t - s u b s e t ( c ，厶一1 ) t h ( 5 ) d e l e t e c ； ( 6 ) e ka n d dct 0g ( 7 ) r e t u mq ； p r o c e d u r e1 1 a s _ i n 6 e q u e n l s u b s e t ( c ：c a l l d i d a t ek - i t e m s e t ；厶一l ：i i l 丘e q u e n t ( k - 1 ) - i t e m s e t ) ( 1 ) 硒re a c h ( k 1 ) - s u b s e t so fc ( 2 ) i fs 诺厶一lt h e n ( 3 )r e t u n l 豫； ( 4 ) r e 觚剐三胚； 图4 1a p ri o ri 算法 3 9 中山大学硕士学位论文 4 3 基于频繁项集进行文本聚类 在使用a p r i o r i 算法挖掘出文本集中所有的频繁项集后，每个文本都可以用 它所包含的频繁项集来表示，这样就避免了文本的高维性和稀疏性给文本聚类带 来的影响。因为一个文本中所包含的频繁项更能代表该文本的内容，以及用来区 分它与其它不同的文本，所以接下来的文本聚类过程就是以这些频繁项集为基 础。根据频繁项集进行文本聚类的过程主要包含了三个基本步骤：建立初始文本 簇；对初始簇进行选择；确定每个文本所属的簇，形成聚类结果。下面本文将对 这三个步骤分别进行说明。 4 3 1 建立初始文本簇 频繁项集中包含了一个或多个频繁项，它们同时在事务数据库中出现的频率 是不小于某个阈值的。也就是说，文本集中有一定数量的文本包含了频繁项集中 的所有项。f i t c 算法以频繁项集为中心建立初始文本簇，每个频繁项集对应一 个初始簇，簇由包含该频繁项集中所有频繁项的文本组成。频繁项集中的项在其 所对应簇的文本中都是频繁出现的，它们代表了簇中文本的共同特征，可以认为 是对该簇中所有文本的一个比较好的描述。 下面本文以一个实例来说明由文本集建立初始簇的过程。该实例使用的文本 数据是从c l a s s i c 4 中抽取的1 2 篇短文本，对文本进行预处理后共得到6 个特征项， 所有文本分属于3 个类别，由名称的前半部分指示。对该文本集建立其对应的事 务数据库，如表4 一l 所示，表中单元的内容是每个项在对应事务中的出现频率。 假定最小支持度的值为3 5 ，则可以使用上一节介绍的a p r i o r i 算法挖掘出事务数 据库中的频繁项集，如表4 2 所示。根据表4 2 中的频繁项集，可以为文本集建立 8 个相应的初始文本簇，每个文本簇都与一个频繁项集对应，并且把频繁项集中 的所有项作为其对应簇的标签。表4 3 是根据表4 2 所得到的初始文本簇的信息， 其中第一列是簇的标签，第二列是簇的信息，最后一列是下一节所要介绍的簇的 标准重叠信息。 在这个由频繁项集建立初始文本簇的过程中，本文没有涉及到传统聚类算法 中的文本向量空间模型和相似度的计算，主要就是使用a p r i o r i 算法发现文本集中 文本挖掘中聚类技术的研究 的频繁项集。 表4 - 1与文本集对应的事务数据库 d 0 c f 裁l n 】r e 、7 r e c t o r 舱m en o w觚 l a y e r删i e n t r e s u l t 仃e a t m e n t c i s 主10looo0 c r a n 111l0o0 c r a n 220100o c r a n 3212o3o c r a n 4203000 c r a n 51o20oo m e d 1oo0812 m e d 201o43l m e d 30o0302 m e d 4000633 m e d 5 olo400 m e d 6ooo9l1 表4 _ 2 事务数据库中的频繁项集及其支持度 f r e q u e n tn e m s e ts u p p o n n o w 4 2 f o r m ) 4 2 l a y e r ) 4 2 p a t i e m ) 5 0 r e s u l t ) 4 2 仃e a t n 圮n t ) 4 2 妇a w ，l a y e r ) 4 2 呻i e n t ，仃i e a t m e i l t ) 4 2 4 1 中山大学硕士学位论文 表4 - 3 初始文本簇 c l u s t e r ( 1 a b e l ) c 1 0 c u m e n t si nc l l 】s t e fc o c ( f l o w )c m 1 ，a 觚2 ，c m 3 ，c r 觚4 ，c 瑚1 5 2 6 c ( 氨”m )c i s i 1 ，c m n 1 ，c r a l l 3 ，m e d 2 ，m e d 5 2 c ( 1 a y e r ) c r a n 1 ，c 豫n 2 ，c r a n 3 ，c r a n 4 ，c r a m 5 2 6 c ( p a t i e n t ) m e d 1 ，m e d 2 ，m e d 3 ，m e d 4 ，m e d 5 ，m e d 6 2 6 7 c ( r e s u l t )咖1 3 ，m e d 1 ，m e d 2 ，m e d 4 ，m e d 6 3 4 c ( t r e a t m e n t ) m e d 1 ，m e d 2 ，m e d 3 ，m e d 4 ，m e d 6 3 c ( f l o w ，l a y e r ) c m n 1 ，c 瑚1 2 ，c r a l l 3 ，c m 4 ，c m n 5 0 6 c ( p a t i e n t ，t r e a t m e n t ) m e d 1 ，m e d 2 ，m e d 3 ，m e d 4 ，m e d 6 1 4 3 2 对初始簇进行选择 文本数据的维度非常高，因此从文本集中挖掘频繁项集时，得到的频繁项集 的数量往往是数量巨大。如在前面的麓妊髦露墓邕雾；墓鳗霎雾雾泰裂鍪雾逵i 囊蠢粝翎鲤弦媳型霉蔓琴贮劐刊毒增零签名! 溪蕊裂曼磊萎翥霎虱蜥鞭露酲塑， 蓁橇霸j 露饕滞鋈篓雾裂理香髯琨尘f 蓁獬型藕薹萧带萎萄蓁霸羹鲈；徊簿篡蓁 狮羹不i 列隔繇垂 实验中使用的这四个 测试数据集的维度信息如表4 6 所示。 表4 - 6 测试数据集的维度信息 肜妒 2 0 n g4 0 02 0 n g_ 1 0 0 02 0 n g _ 2 0 0 0 维度 8 05 07 25 01 63 4 l2 92 3 l 4 5 3 结果与分析 中山大学硕士学位论文 表4 4 对初始的文本簇进行选择后的结果 c l u s t e r ( 1 a b e l ) 【l o c u n l e n t si nc l u s t e r c ( 矗n )c i s i 1 ，c r a n 1 ，c 啪3 ，m e d 2 ，m e d 5 c ( f l o wl a y e r )c r a l n 1 ，c r a 【n 2 ，c r a n 3 ，c r a n 4 ，c r a n 5 c ( p a t i e m ，h e a t m e n t ) m e d 1 ，m e d 2 ，m e d 3 ，m e d 4 ，m e d 6 4 3 3 确定每个文本所属的簇 对初始簇进行选择后，一些对聚类结果而言属于多于的簇都被去掉了，剩下 的簇基本上代表了文本集中所有文本的一