浅谈基于特征选择的文本聚类方法

浅谈基于特征选择的文本聚类方法以Text Clustering with Feature Selection by Using Statistical Data为例摘 要: 基于特征选择的文本聚类方法不仅能够降低文本数据空间的维度，而且能够显著提高文本聚类的性能。以Text Clustering with Feature Selection by Using Statistical Data为例，对基于特征选择的文本聚类方法进行典型分析，并在此基础上，对Text Clustering with Feature Selection by Using Statistical Data进行简要评价，认为如何在实际应用中更好地引入学习机制，将特征选择融入到文本聚类中，从而提高文本聚类效率是一个好的研究方向。关键词: 特征选择；文本聚类；K-means算法1引言文本聚类是文本挖掘和信息检索领域的核心问题之一。它完全根据文本文档的内容相关性来组织文档集合，将整个集合聚集成若干个类，并使得属于同一类的文档尽量相似，属于不同类的文档差别明显。文本聚类方法可以分为等级聚类法和动态聚类法，主要应用于自动摘要、文本的自动组织、搜索结果聚类等方面1。文本聚类是一种无监督的学习方法，文本缺少有监督特征选择所必须的类别信息。因此，有监督的特征选择方法在文本分类上取得了成功，但是却很少用于文本聚类中。然而，若能够有效将有监督的特征选择方法应用在文本聚类上，则能够显著提高文本聚类的性能。因此，如何将有监督的特征选择方法应用于文本聚类成为了一个新的研究热点。目前，国外学者在此方面进行了大量研究，并取得了较为丰厚的结果。如Jos Martnez Sotoca2，Yanjun Li3，P.Santhi4等。相较而言，国内学者的研究热点还主要集中在单独对特征选择方法改进或聚类算法改进上。如樊东辉，王治和5等提出了一种利用特征词的熵函数加权的权值的计算方法，考察特征词的文档频数和在文档中出现的次数，使选出的特征子集更具有较好的代表性，从而改善聚类结果。胡玉娴6则提出基于知网特征词合并算法，通过合并具有高度相似性的特征词，有效降低特征向量维度，使得聚类结果较为稳定。诚然，国内也有少数学者对基于特征选择的文本聚类进行研究，比较具有代表性的有刘涛、吴功宜和陈正7的一种高效的用于文本聚类的无监督特征选择算法。 下面，笔者以国外学者Yanjun Li，Congnan Luo，Chung, S.M的Text Clustering with Feature Selection by Using Statistical Data为代表，进行典型分析，并在此基础上进行简评，以期为今后学术界在文本聚类上的研究提供一定的参考。2典型分析从文本数据收集与处理、特征项选择、聚类算法实现、聚类结果分析等四个方面对Yanjun Li，Congnan Luo，Chung, S.M所写的Text Clustering with Feature Selection by Using Statistical Data进行分析。2.1文本数据收集、处理与表示2.11文本数据收集与处理Yanjun Li等从CACM and MEDLINE 摘要文本和Reuters-21578 Distribution 1.0两个不同类型的数据库中提取了5个用于测试的数据集，其中2个数据集来自于前者，另外三个数据集来自Reuters-21578 Distribution 1.0中的EXCHANGE、PEOPLE、TOPIC分类集。在进行聚类实验之前，利用停用词表删除了文本数据集中出现的停用词。各文本数据集中的文档都已经提前被分类到了某一个唯一类中，但是，在聚类的过程中，这些信息是被隐藏的，提前分类的结果仅仅用于后面对聚类结果准确度的评价。2.12文本数据的表示 文本聚类面临的首要问题是如何将文本内容表示为使用计算机可以分析处理的形式，即文本数据的表示方法。目前国内外学者通常采用的是向量空间模型，从文本中提取特征词构成特征向量，并计算出每个特征词在各个文档中的权重。如果把特征列表看作一个 维的坐标系，那么坐标值就对应为各维的权重，文本集中的每一个文档就可以看作是 维空间中的一个向量，这样就把文档表示成为计算机可以处理的形式了。Yanjun Li等采用的正是向量空间模型。2.2特征项选择常用的特征选择方法有信息增益、互信息、x2 统计量、期望交叉熵、单词权、单词贡献度1。但是在众多的特征选择方法中，有学者指出IG（信息增益）和CHI（x2 统计量）的效果最好8，而IG计算量相对其它几种方法较大，因此Yanjun Li等针对目前特征选择方法中效果最好2统计方法进行研究和改进。他们在研究中发现了以下两个问题：其一，CHI降低了低频词的权重。2统计方法不能准确地保留往往是某类特有的，具有很强代表性的低频词。这里的低频词是指文档频数，但某些低频词往往是某类特有的特征词，这些特征词具有很强的代表性，虽然只出现在指定类的少量文章中，但在这少量文章中频繁的出现，因此对分类的贡献很大，需要被保留下来；其二，提高了很少在指定类中出现但普遍存在于其他类的特征在该类中的权重。在整个训练集语料库中一些出现频率较高的词，而这些词语在指定类中出现得很少甚至几乎是不出现的，显然这些词是不能很好地代表该指定类，应该被过滤掉。针对以上两个缺陷，Yanjun Li等对CHI方法进行了改进，提出了一种新的分类方法CHIR。针对缺陷一，把特征项在具体的文档中出现的频度作为权重值考虑进2统计的计算公式。因此，某一特征向量与类的关系计算公式为：其中：p(RW, Cj)是 的权重： 针对缺陷二，改进的方法主要体现在对Rw,c的判断上。Rw,c=(a*d-b*c)/(a+b)(a+c) +1，当 Rw,c小于1时，即在整个语料库出现频繁，而在指定类出现较少。当 大于 1 时，即在指定类出现较多。2.3聚类算法实现 Yanjun Li等基于EM算法，将有监督的特征选择方法CHIR与K-means算法进行结合，形成了一种新的聚类算法TCFS。TCFS算法的详细步骤如下：1执行第一遍K-means算法，获得初始聚类和各类的聚类中心；2对步骤1生成的数据集，利用CHIR，进行特征选择。被选择的特征将继续保持在表示文本集的向量空间中，而没有被选择的那些特征，其乘以一个特定的权重值f，f为提前设定的一个因子，取值范围为（0,1），从而减少他们对于文本聚类的影响力。紧接着，在新的向量空间中，重新计算K个类的聚类中心。3文档集中的每一篇文档都要利用聚类标准函数来与新的向量空间中各个类的中心进行比较，从而将每一篇文档划分到与其最为相似的类别中。4反复迭代步骤2和步骤3，直到簇中心不发生改变。2.4聚类结果分析2.41特征选择的评价Yanjun Li等利用凝聚度对CHIR、CHI、CC、SCHI等四个特征选择方法进行比较，使用的数据库为CACM数据库。研究结果显示，当选择前20%的词作为特征量时，CHIR能够比CHI、CC、SCHI更有效删除非相关特征。通过比较各凝聚度值的大小，可以知道，在同一百分比的特征选择下，CHIR的凝聚度值均大于其他三个的凝聚度值，且特征选择的百分比越小，即选择的特征越少，CHIR的凝聚度与其他三个的凝聚度值相差越大，CHIR在特征选择上的表现越优异。2.42聚类方法的评价Yanjun Li等利用纯度和F-Measure来评价聚类算法的准确性。纯度是度量类簇在多大程度上包含单个类的成员的另一种度量。类簇 i的纯度通过式Purity = Max(Pij )求得 ，聚类的总纯度通过式计算得到。总纯度越高，聚类性能就越好9。F-Measure是将准确率（Precision）与召全率（Recall）综合起来的另外一个常用指标。对于每一个主题类别T和对应的聚类C中，统计出:N1:在聚类C中且主题类别为T的文档数；N2:在聚类C中但不属于主题类别T的文档数；N3:属于主题类别T但没有分到聚类C中的文档数；Precision(C,T)=N1/(N1+N2); Recall(C,T)=N1/(N1+N3); F-measure=2PR/(P+R)10。 Yanjun Li等将聚类方法的评价实验分成两个部分。一方面，他们比较了K-means算法、基于TS的K-means算法、基于CHIR的TCFS算法、基于CC的TCFS算法和基于CHI的TCFS算法等5个算法的准确性。将这五种算放运行与EXE数据库，运行结果显示：由于特征选择方法能够有效移除非相关或冗余特征，因此，将特征选择的方法溶于文本聚类中，能够有效改善文本聚类的结果；将有监督的特征选择方法运用于TCFS算法中（如基于CHIR的TCFS算法、基于CC的TCFS算法和基于CHI的TCFS算法），得到的F-measure值比基于TS的K-means算法要更好，可见，若将有监督的特征选择方法运用于聚类过程中，更够提高聚类的准确性；当特征向量的选择百分比发生变化时，基于TS的K-means算法所得到的聚类结果并不是一直都比K-means算法要优异，基于TS的K-means算法并不能够一直选出最合适的特征集，在某些时候，TS会移除一些相关特征而保留一些非相关特征；在不同的测试数据集中，基于CHIR的TCFS算法得到的F-measure值和纯度值都要高于其他算法，基于CHIR的TCFS算法优于其他四个算法。另一方面，他们对TCFS与IF（迭代特征选择算法）进行了比较。IF算法与TCFS算法的主要区别在于以下两点，其一，在IF中，一旦某一个特征没有被选择，这个特征将立即被移除，从而不会出现在接下来的聚类中；其二，在IF中，特征选择的过程时独立与K-means算法的。实验结果显示：在大多数情况下，TCFS的聚类结果优于IF的聚类结果；随着迭代次数的增加，IF算法并不能够一直提高其聚类效果。究其原因，Yanjun Li等认为，在初始时期，通过有监督特征选择方法得到的特征向量并不一定是真正能够代表各类的特征向量，有些没有被选择的向量很有可能才是真正能够代表某类的特征向量，但是，这些向量需要在接下来的运行过程凸显出来。因此，如果在初始时期就将没有被选择的向量移除，将对接下来的特征选择结果和聚类结果产生不好的影响。由此可见，降低将未被选中的特征在向量空间中的权重而非直接将其删除的TCFS算法能够对早起所犯下的错误进行纠正，从而获得一个更好的聚类结果。3简评接下来，笔者将从两个层面对Yanjun Li，Congnan Luo，Chung S.M的Text Clustering with Feature Selection by Using Statistical Data进行简单评论。这两个层面分别是自身层面和比较层面。3.1自身层面Yanjun Li，Congnan Luo，Chung S.M的Text Clustering with Feature Selection by Using Statistical Data阐述了有监督的特征选择方法在文本聚类中的研究与应用过程。新特征选择方法和聚类算法的提出为今后在特征选择方法和有监督的文本聚类算法等多个方面的研究奠定较好的基础。但是，笔者认为，Text Clustering with Feature Selection by Using Statistical Data也存在一些不足之处：其一，评价指标的客观性不强。对于同一种算法，不同的评价指标，得到的评价结果是具有差异性的。在Text Clustering with Feature Selection by Using Statistical Data中，笔者仅仅通过凝聚度一个指标对特征选择方法进行了评价，而在算法的评价中，同一种算法在F-measure和纯度两个指标中表现的结果也不尽相同。由此可见，是否仅仅用一个或两个评价指标就能够很好地说明问题还有待探究；其二，存在算法对数据库的依赖性问题。同一算法运行与不同数据库中，产生的结果不尽相同，甚至差异性极大。在Text Clustering with Feature Selection by Using Statistical Data中，作者并非将各个算法在五个数据库中运行的结果都展现出来了，而是选择了其中的两个数据库运行结果进行展示，剩余的三个数据库的运行结果无从得知。有理由怀疑TCFS在未展示的数据库中运行得到的结果并不尽如人意；其三，f值的取值问题。在聚类算法中，未被选中的特征向量将乘以f来降低其在向量空间中所占有的权重。不可否认的是，相较于直接删除未被选择的特征向量，这确实是一个好的想法，但是，在Text Clustering with Feature Selection by Using Statistical Data中，作者并没有指出f值究竟应该取多少为合适。在实验中，作者选取的f值为0.5，而其选取的原因无从而知。会不会有可能存在，当f值取其他值时，得到的实验结果与现有的实验结果差别较大呢？其四，新的聚类算法并没有改进K-means算法固有的缺陷。现有的研究成果显示，K-means算法具有初始聚类中心不确定、初始类数量自定义、只能发现球状簇等缺陷。但是，对于这些缺陷，新的聚类算法TCFS并没有提出有效的改进方法，改进K-means算法固有的缺陷依旧任重而道远。3.2比较层面以刘涛、吴功宜和陈正的一种高效的用于文本聚类的无监督特征选择算法为比较对象，对这两种基于特征选择的文本聚类算法进行比较研究。刘涛、吴功宜和陈正的一种高效的用于文本聚类的无监督特征选择算法中描述的文本聚类算法如下：从最大聚类数和最小聚类数的集合中，随机选择一个数K为聚类个数并随机选择K个初始中心点；利用K-means聚类得到聚类结果P；在P的结果上使用特征选择算法如CHI、IG等为每一个单词求得重要性值；更新每一个单词的重要性，即每一个单词新的重要性等于本次聚类前的重要性加上此次聚类后得到的新的重要性；按照重要性对单词数组进行排序，在此基础上，开始新一轮的聚类；在聚类开始前就设置好聚类次数M，重复执行步骤-M次，聚类结束。通过比较两种算法，可以两种之间既有共同点又有差异性。共同点体现在：两种聚类算法都是在聚类结果上使用特征选择方法，改变单词权重（重要性）；在计算单词权重时，不是仅根据一次聚类结果就将某些单词删除（权重为零），而是，采用累积的方法，结合多次聚类结果，逐渐改变单词权重；两种聚类算法都没有改进K-means算法固有的缺陷。差异性体现在：一套完整的K-means算法的执行次数不同，Yanjun Li等设计的聚类算法在时间和空间上优于刘涛等设计的聚类算法。Yanjun Li等设计的文本聚类算法只进行一轮的完整K-means算法，而刘涛等设计的聚类算法则要根据最初设置的参数M，进行M轮完整的K-means算法；特征选择发生的时间不同。在Yanjun Li等设计的文本聚类算法中，特征选择是在每一次聚类结果上进行的，而在刘涛等设计的聚类算法中，特征选择是在每一轮聚类结果上进行的；需要人为设置的参数不同。在Yanjun Li等设计的文本聚类算法中，需要人为设置参数f为控制单词权重的变化，而在刘涛等设计的聚类算法中，需要人为设置的参数是完整的K-means算法执行次数M；单词权重改变的方法不同。Yanjun Li等是根据单词的选择情况，用小于零的参数f乘以未被选择的单词，以此来实现单词权重的改变，而刘涛等则是采用逐轮累加的方法来实现单词权重的改变。采用的特征选择方法不同。Yanjun Li等提出了一种新的特征选择方法CHIR，而刘涛等采用的是那些常规的特征选择方法，如CHI、IG等。通过以上比较可知，特征选择与文本聚类的融合形式虽然是不尽相同的，但是，却是万变不离其宗。它们都是在聚类结果上使用特征选择的思想，将那些非常有效但无法直接应用到文本聚类上的有监督的特征选择方法成功地应用到文本聚类上。现有的研究成果也一再说明，基于特征选择的文本聚类方法不仅能够极大地降低文本数据空间的维度，而且使文本聚类的性能有了显著的提高。因此，笔者相信，如何在实际应用中更好地引入学习机制，将特征选择融入到文本聚类中，从而提高文本聚类效率是一个好的研究方向。同时，探索新的特征选择方法和聚类算法，改进现有算法的缺陷仍然是学术界在文本聚类分类上的研究热点之一。参考文献：1苏新宁.信息检索理论与技术，2004，北京：科学技术文献出版社.2Jos Martnez Sotoca,Filiberto Pla.Supervised featureselection by clustering using conditional mutual information-based distancesJ.Pattern Recognition,2010,43(6):20682081.3Yanju