基于Canopy+K-means的中文文本聚类算法*

张 琳，牟向伟

0 引言

互联网的普及使得在线电子文本资源剧增，也使文本成为信息传播的主要载体。文本数据是一种半结构化数据，具有高维、数据量大、与上下文相关，甚至存在一词多义或多词一义等特点。所以，与结构化数据相比，文本数据大大增加了数据处理和知识发现的难度。因此，如何对网上的文本数据进行快速、有效的分析，并挖掘其中隐藏的价值是一个亟待解决的问题。文本聚类是解决这个问题的一种可行方法。

文本聚类是文本挖掘过程的一项关键技术，它根据一定的标准通过将文本划分到有意义的几个簇中，使同一个簇中文本之间的相似度高于不同簇间文本之间的相似度[1]，从而实现对文本信息的有效组织和管理。有效的文本聚类可以帮助人们更好地理解和导航信息检索工具的检索结果[2]，例如在信息检索领域，Scatter/Gather[3]系统通过采用非监督式的聚类方法(如K-m eans)对搜索结果进行划分来帮助用户理解和消化检索结果；可以为用户根据实际需要深入挖掘某一特定主题提供自由[4]；可以促进引文分析，自动文摘，科技信息检索等研究的发展[5]，等等。

文本聚类技术发展迅速，相应地产生了很多聚类算法。这些算法大致可分为两类：基于划分的方法和基于层次的方法[6]。在这些聚类方法中，应用最广泛的是以划分为基础的K-m eans算法。K-m eans算法在聚类时需要事先指定簇的个数k和k个初始中心点，但往往我们无法预先确定簇的个数并选择合适的初始聚类中心，这会导致K-m eans聚类的误差很大，甚至可能陷入局部最优。针对K-m eans算法这两方面的不足，不同学者从不同角度对其进行了改进。

例如，针对K-m eans初始聚类中心随机选择的问题，文献[7]提出了一种基于LDA主题概率模型的初始聚类中心选择算法，即先从文本集中选择m个主题，并在这m个主题所在的维度上对文本集进行初步聚类，得到k个聚类中心后，再以这k个聚类中心为初始聚类中心对文本集在所有维度上进行聚类；文献[8]通过不断寻找最大聚类(即包含数据对象最大的一个类)，并利用最大聚类中距离最大的两个数据对象作为聚类中心对数据集进行划分，如此反复，直到找出k个聚类中心为止；文献[9]则通过引入密度和最近邻的思想，提出了初始聚类中心选择算法，该算法提高了K-m eans算法的聚类质量和稳定性。针对K-m eans无法预先确定k值的问题，文献[10]通过样本数据分层来确定算法的聚类范围，并利用类内、类间夹角余弦值的比值作为聚类有效性指标，从而在聚类数范围内获得最佳聚类数。与同类算法相比，该算法的运行效率较高，能够得到良好的聚类效果；文献[11]根据类内相似度最大差异度最小和类间差异度最大相似度最小的原则，提出了一种基于距离评价函数的k值检验方法，并通过实验验证了算法的有效性；文献[12]利用二分思想递归分裂簇内相似度大于给定阈值的簇，通过合并簇间相似度小于给定阈值的簇来获得最终聚类数目。

上述研究都是针对K-m eans某一方面的问题进行的改进。为了提高K-m eans算法的聚类效果，本文在对中文文本进行聚类时，采用Canopy和K-m eans相结合的聚类算法，将Canopy聚类作为K-m eans聚类的前奏，为K-m eans提供k值和初始聚类中心点。

1 文本预处理

1.1 基于Word2vec的词语相似度计算

W ord2vec是谷歌在2013年开源的一款语言建模工具，它以文本集为输入，通过训练生成每个词对应的词向量。这些词向量可以作为词的特征应用到一些自然语言处理问题中，比如中文分词、寻找同义词、进行词性分析，等等[13]。W ord2vec实现了两种训练模型CBOW(Continuous Bag-O f-W ords)和Skip-gram模型[14]，如图1所示。其中，CBOW模型是通过上下文来预测当前词出现的概率；Skip-gram模型与CBOW模型相反，它是通过当前词来预测其上下文词语出现的概率。为了提高词向量的训练效率，W ord2vec提供了两种词向量优化模型，分别是Hierarchy Softm ax模型和Negative Sam pling模型。

本文采用搜狗实验室提供的全网新闻语料(http：//www.sogou.com/labs/resource/ca.php，该语料包含若干新闻站点2012年6～7月间国内、国际、体育、社会和娱乐等18个频道的新闻数据)训练Word2vec模型，并利用训练好的模型获得某一个词语的同义词或近义词。具体步骤包括：

(1)获取所有新闻＜content＞＜/content＞标签之间的内容。

(2)采用 NLPIR2016工具(http：//ictclas.nlpir.org/)进行分词，并对分词结果进行停用词过滤和词性标注，保留名词、动词和形容词，同时删除分词结果中仅有一个字的词语，最后将得到的所有词语以空格隔开。

(3)执行w ord2vec-train命令，采用Skipgram训练模型和Hierarchy Softm ax优化模型对分好词的训练语料进行训练，得到词向量，进而得到词典D的词汇相似矩阵。

(4)利用训练好的Word2vec模型，获得某一个词语的同义词或近义词。方法是：输入词语，获得该词语在词典D中的词向量表征，然后遍历词典D，通过向量夹角余弦公式计算该词向量与词典D中其他词向量之间的相似度，从而可以得到词典D中与该词语最相似的top N个词语。

1.2 特征词权重计算

TF-IDF(Term Frequency-Inverse Docum ent Frequency)[15]是一种应用较为广泛的权值计算方法。其中，TF指的是词频，IDF指的是逆向文档频率。TF-IDF的基本思想是：如果某个词项或短语在某篇文档中频繁出现(TF很高)，但是在文本集的其他文档中甚少出现(IDF很高)，那么这个词项或短语对这篇文档具有很好的辨识能力。对于这样的词项、短语，我们应该赋予较高的权重。相反，如果某个词项或短语在文本集的大多数文档中出现的频率都很高，那么根据这个词项或短语很难将包含它的多篇文档区分开来。因此，对于这样的词项或短语，我们应该赋予较低的权重。

TF-IDF的基本形式如式(1)所示：

其中，wt，D表示词项t在文档D中的权重；tft，D表示词项t在文档D中出现的频次；N表示文档集的大小；dft表示包含词项t的文档总数。本文根据式(2)对出现频次tf进行归一化表示，其中，doc_length表示文档长度。

1.3 文本表示

最常用的文本表示方法是基于向量空间模型的方法。向量空间模型的基本思想[16]是：每一篇文档都可以被表示成一个由预先规定好词序的多个词项组成的高维空间的一个向量。规定好次序的词项可以看作是向量空间的维度，词项的个数决定向量的维数，词项的权重则表示词项在文档中的重要程度，可以看作是向量在高维空间某一维上的取值。

基于向量空间模型可以将每一篇文档表示成如式(3)所示的向量形式：

其中，D表示一篇文档；m表示向量的维数，其大小由文本集中不同的词项个数决定；ti表示文本集中的一个词项；W ti，D表示词项ti在文档D中的权重(即重要性)。

2 Canopy+K-means算法

2.1 Canopy算法

Canopy算法是一种快速近似的聚类技术。它的优势在于得到簇的速度非常快，只需遍历一次数据即可得到结果，正因为如此，Canopy算法无法给出精准的簇结果[17]。

Canopy算法的基本流程如下[18]：

(1)确定Canopy的两个距离阈值，即T1和T2，其中T1＞T2。

(2)从数据集中任取一个数据对象，计算它与所有Canopy中心之间的距离。

(3)如果当前不存在Canopy，则把该数据对象作为一个Canopy中心，并将它从数据集中删除。否则，转(4)。

(4)如果该数据对象到某个Canopy中心的距离在T2以内，则把它添加到这个Canopy中，同时将它从数据集中删除。因为该数据对象与此Canopy距离很近，因此它不可以再作为其他 Canopy中心。

(5)如果该数据对象到某个Canopy中心的距离在T2以外T1以内，同样把该数据对象添加到这个Canopy中，但是此时并不从数据集中删除这个数据对象。也就是说，这个数据对象将参与下一轮的聚类过程。

(6)如果该数据对象到所有Canopy中心的距离都在T1以外，则把它作为一个Canopy中心，同时将它从数据集中删除。

(7)重复迭代(2)到(6)，直到数据集中所有数据对象都划分到了相应的Canopy。

2.2 K-means算法

K-m eans算法的核心思想是，通过迭代把所有数据对象划分到k个不同的簇中，以使簇内对象具有较高的相似度，而各个簇之间的对象具有较低的相似度。

K-m eans算法的基本流程如下[19]：

(1)输入数据集D和要划分的簇的数目k。

(2)从D中任意选择k个对象作为初始簇中心。

(3)计算簇中任一对象到各个簇中心的距离，将其分配到距离最近的簇中心所在的簇。

(4)重新计算每个簇中所有数据对象的平均值，将其作为新的簇中心。

(5)重复(3)(4)，直到簇心不发生改变或者达到最大迭代次数。

2.3 Canopy+K-means算法

图2 Canopy+K-means算法的聚类流程

在基于向量空间模型将文本表示成一个由特征词TF-IDF权值表示的特征向量后，本文采用余弦公式衡量文本之间的相似度。在进行Canopy“粗”聚类时，设定T1＜T2，且设置T1和T2的取值都与文本集中所有文本的平均相似度相关。另外，为了防止Canopy中心点选取过密而导致算法陷入局部最优，本文选择离所有样本点的中心最近的一个样本作为第一个Canopy中心。Canopy+K-m eans算法的聚类流程如图2所示。

总的来说，在对中文文本进行聚类时，为了解决K-m eans算法无法预先确定聚类数目和随机选择初始聚类中心点的问题，本文先使用Canopy算法对数据集进行“粗”聚类，在得到k值后，再使用K-m eans算法进行“细”聚类，并且将Canopy算法选择出来的每个Canopy的近似中心位置作为K-m eans的初始中心点，以此来提高K-m eans算法的聚类效果。

3 文本聚类结果评价

对聚类算法进行评价主要可以采用三类有效性评价准则[20]：内部准则、外部准则和相对准则。本文主要采用四种外部评价准则[21]对聚类结果进行评价。

(1)纯度(purity)：是一个简单、明晰的评价指标，它将每个簇分配给该簇中出现数目最多的文档所在的类别，并通过正确分配的文档数除以文档总数N得到聚类的精度。purity的计算方法如式(4)所示。

其中，Ω={W1，W2，…，WK}是聚类的结果，C={C1，C2，…，CJ}是类别集合，Wk(k=1，2，…，K)和Cj(j=1，2，…，J)是由文档组成的文档集合。

(2)准确率(precision)：衡量的是每个簇中某一特定类别的对象所占的比例。其计算方法如式(5)所示。

其中，TP(True-positive，真阳性)指的是将两篇相似文档正确归入同一个簇的决策；FP(False-positive，假阳性)指的是将两篇不相似文档错误归入同一簇的决策。

(3)召回率(recall)：衡量的是每个簇包含某个特定类别的所有对象的程度。其计算方法如式(6)所示。

其中，FN(False-negative，假阴性)指的是将两篇相似文档归入不同簇的决策。

(4)F-M easure：是一种综合准确率和召回率的聚类评价指标，其计算方法如式(7)所示。

其中，β为调和系数，一般取β=1。

4 基于Canopy+K-means的中文文本聚类流程

本文采用NLPIR2016对中文文本集进行分词和词性标注，并剔除了分词结果中对文档主旨没有任何提示作用的停用语，如“为何”“与其”“人们”等，以及一些数字和符号。一般而言，名词、动词和形容词是句子的重要组成成分。因此，为了抽取能够表征文档主要内容的词语，对于停用词过滤后的分词结果，本文只保留名词、动词和形容词三种词性的词语，去重之后将它们作为候选特征词。

中文词语之间有时会存在“多词一义”的情况，因此，为了降低文本向量的维度，避免给文本向量的计算造成困难，本文基于W ord2vec生成词向量，获得候选特征词之间的同义词或近义词，同时合并同义词或近义词在同一篇文档中出现的词频及在文本集中出现的文档列表。

在对文本集进行上述预处理之后，采用向量空间模型将每一篇文档表示成一个由特征词TFIDF权重组成的向量形式；然后使用Canopy+K-m eans算法对文本集进行类别划分；最后基于纯度、准确率、召回率和Fvalue对聚类效果进行评价。基于Canopy+K-m eans的中文文本聚类流程如图3所示。

5 实验

为了验证Canopy+K-m eans算法的有效性，本文选取了两个文本数据集，分别利用Canopy+K-m eans和K-m eans算法对它们进行类别划分，并基于purity、precision、recall和F值对这两种算法的聚类结果进行评价。

图3 基于Canopy+K-means中文文本聚类流程

在基于Canopy+K-m eans算法进行文本聚类时，本文设置T2为文本集中所有文本的平均相似度，T1=1/2*T2。在基于传统K-m eans算法进行文本聚类时，由于K-m eans算法需要预先确定k值，在实验中本文设定k为文本集的实际类别数。另外，由于K-m eans算法的聚类效果与初始中心点的选取有关，因此为了更好地体现K-m eans算法的性能，本文在基于传统K-m eans算法进行文本聚类时，重复运行该算法100次，取100次聚类评价指标的平均值作为K-m eans算法的性能评价。

实验一：搜狗文本分类语料(http：//www.sogou.com/labs/resource/tce.php)是一个包含汽车、财经、IT、健康、体育等18类新闻的数据集。本文从该数据集中选取了汽车、娱乐、体育、教育、IT和财经六个类别3600篇新闻(每个类别各600篇)作为实验数据集。实验数据集中每篇新闻的字数在300～2000之间，较多集中于500字左右。Canopy+K-m eans算法和K-m eans算法对该数据集的聚类结果评价如表1所示。

表1 搜狗文本分类语料Canopy+K-m eans算法和K-means算法的聚类效果评价

实验二：网易分类文本数据(http：//www.datatang.com/data/11965)是一个包含运动、汽车、经济、医药、体育和文化六个类别的文本数据集，该数据集的每一个文本为一篇新闻，字数在300～3000之间，较多集中于1000字左右。本文从该数据集每一个类别的新闻中各选取100条数据作为实验数据集。两种算法对该数据集的聚类结果评价如表2所示。

表2 网易分类文本数据Canopy+K-m eans算法和K-means算法的聚类效果评价

上述两个实验在设置了T1和T2后，Canopy算法将数据集划分成了六类，为K-m eans算法提供了k值和初始聚类中心点。从表1和表2可以看出，无论是purity、precision、recall，还是F值，Canopy+K-m eans算法的聚类效果要明显优于K-m eans算法。这说明，相比于传统的K-m eans算法，Canopy+K-m eans算法除了可以自动产生k值外，Canopy聚类也可以为K-m eans提供较好的初始聚类中心点，从而使Canopy+K-m eans算法的聚类结果更接近文本的真实类别。

6 结论

本文针对传统K-m eans算法在聚类时需要预先确定k值和聚类效果受初始聚类中心影响的问题，将Canopy算法和K-m eans算法进行结合得到Canopy+K-m eans算法，并将其应用于中文文本分类中；阐述了Canopy+K-m eans算法的实现流程及基于Canopy+K-m eans算法的中文文本聚类步骤，并通过具体的实验分析了基于该算法进行中文文本聚类的可行性。由于Canopy算法在聚类时需要确定阈值T1和T2，而T1和T2的大小会直接影响分类的准确率，因此如何更好地确定T1和T2取值是本文接下来的研究重点。另外，实验也将选取更大的数据集并基于Hadoop平台实现对大规模文本集的类别划分。

[1]曹晓.文本聚类研究综述[J].情报探索，2016（1）：131-134．

[2]Zeng，H J，He，Q C，Chen，Z，et al.Learning to cluster web search results[C]//Proceedings of the 27th annual international ACM SIGIR conference on Research and development in information retrieval.ACM，2004：210-217.

[3]Cutting，D R，Karger，D R，Pedersen JO，etal.Scatter/gather：A cluster-based approach to browsing large document collections[C]//Proceedingsof the 15th annual international ACM SIGIR conference on Research and development in information retrieval，1992：318-329.

[4]王小华，徐宁，谌志群.基于共词分析的文本主题词聚类与主题发现[J].情报科学，2011，29（11）：1621-1624.

[5]刘远超，王晓龙，徐志明，等.文档聚类综述[J].中文信息学报，2006，20（3）：55-62.

[6]赵世奇，刘挺，李生.一种基于主题的文本聚类方法[J].中文信息学报，2007，21（2）：58-62.

[7]王春龙，张敬旭.基于LDA的改进K-means算法在文本聚类中的应用[J].计算机应用，2014，34（1）：249-254.

[8]陈光平，王文鹏，黄俊.一种改进初始聚类中心选择的K-means算法[J].小型微型计算机系统，2012，33（6）：1320-1323.

[9]张文明，吴江，袁小蛟.基于密度和最近邻的K-means文本聚类算法[J].计算机应用，2010，30（7）：1933-1935.

[10]王勇，唐靖，饶勤菲，等.高效率的K-means最佳聚类数确定算法[J].计算机应用，2014，34（5）：1331-1335.

[11]韩凌波.K-均值算法中聚类个数优化问题研究[J].四川理工学院学报（自然科学版），2012，25（2）：77-80.

[12]张忠平，王爱杰，柴旭光.简单有效的确定聚类数目算法[J].计算机工程与应用，2009，45（15）：166-168.

[13]李跃鹏，金翠，及俊川.基于word2vec的关键词提取算法[J].科研信息化技术与应用，2015，6（4）：54-59.

[14]周练.W ord2vec的工作原理及应用探究[J].科技情报开发与经济，2015，25（2）：145-148.

[15]Salton，G Buckley，C.Term-weighting approachesin automatic text retrieval[J].Information Processing&Management，1988，24（5）：513-523.

[16]郭庆琳，吴克河，吴慧芳，等.基于文本聚类的多文档自动文摘研究[J].计算机研究与发展，2007，44（2）：140-144.

[17]Sean O，Robin A，Ted D，etal.Mahout实战[M].北京：人民邮电出版社，2014：134-138.

[18]M cCallum A， Nigam K， Ungar L H.Efficient clustering ofhigh-dimensionaldata setswith application to reference matching[C]//Proceedings of the sixth ACM SIGKDD international conference on Know ledge discovery and datam ining，2000：169-178.

[19]Han JW，Kamber M，Pei J.数据挖掘：概念与技术[M].北京：机械工业出版社，2012：293-295.

[20]Xu R，W unsch D C.C lustering[M].IEEE Press，2008：265-277.

[21]Manning C D，Raghavan P，Schütze H.信息检索导论[M].北京：人民邮电出版社，2010：246-249.