文档聚类可以作为多文档自动文摘等自然语言处理应用的预处理步骤，可以将重要新闻文本进行聚类处理，是一种处理文本信息的重要手段。
文本聚类开题报告
基于K―Mean文本聚类的研究
摘 要 文本聚类能够把相似性大的文本聚到同一类中。K-Means常用来聚类文本，但是由于聚类中心的选取对聚类结果有影响，导致聚类不稳定，因此采用一种基于聚类中心的改进算法分析文本，通过实验，验证算法的有效性。
中国论文网 http://www.xzbu.com/9/view-6244858.htm
关键词 文本聚类;k-means;相似性;度量准则
中图分类号：TP391 文献标识码：B
文章编号：1671-489X(20XX)18-0050-03
Research for Text Clustering based on K-Mean//ZHANG Yue， LI Baoqing， HU Lingfang， MENG Li
Abstract Text clustering can make the text similarity large clustered into the same class， K-Means usually is used in text clustering， because of impacting on the cluster center， which results in the clustering instability. Therefore， this paper uses a text analysis of improved algorithm based on the clustering center， through the experiment， it verifies the effectiveness of the improved algorithm.
Key words text clustering; k-means; similarity; measure criterion
文本聚类是把不同的文本分别聚在不同的类别中，是文本挖掘的重要技术，它是一种无监督的学习技术，每个类中包含的文本之间具有较大的相似性，不同类间的文本相似性比较小。文本聚类是数据挖掘的重要分支，它应用神经网络、机器学习等技术，能够自动地对不同文本进行分类。
在文本聚类分析中，文本特征表示一般采用向量空间模型[1]，这种模型能更好表现文本。在对文本聚类的研究中，Steinbach等人研究了基于划分的方法和基于层次的方法在文本聚类中的适用程度[2-3]，得出结论：采用K-Means算法进行聚类，不仅聚类结果较好，而且适用于数据量比较大的聚类场合。在文章中根据研究者对K-Means的发现，结合实际研究，采用一种基于K-Means的改进算法来聚类。Dhillod等人对文本聚类进行研究发现，采用余弦夹角作为相似性度量比采用欧氏距离度量的结果好很多[4]。
1 文本聚类
文本聚类的方法很多，主要分为基于层次的方法、基于划分的方法、基于密度的方法、基于模型的方法、基于网格的方法[5]。在这些聚类方法中，基于划分的K-Mean是最常用也是很多改进方法的基础，文章中采取的改进方法也是基于K-Mean的。
K-Mean首先由MacQueent[6]提出。它能在大数据集中广泛被使用，因为算法效率较高、算法执行过程理解容易。当前进行的很多研究都是以K-Mean为基础开展进行的，它的计算复杂度低，具有与文档数量成线性关系的特性，计算效率不仅高，而且伸缩性较强，适应大数据集的能力也很强。K-Mean以k为初始聚类数，然后把n个文本分到k个聚类中，这样类内的文本具有较高的相似度，不同类间的相似度较小。
K-Mean具体的算法过程如下：
1)首先给定n个数据文本，从其中任选k个文本，这k个数据文本初始地代表了k个类的数据中心;
2)对剩余的每个文本计算其到每个中心的距离，并把它归到最近的中心类中;
3)重新计算已经得到的各个类的中心，通常计算中心的准则函数采用平方误差准则，这个准则能够使生成的结果类尽可能地独立和紧凑;
4)迭代执行第二步和第三步的动作直至新的中心与原中心相等或小于指定阈值，直到算法结束。
具体的算法流程如图1所示。
2 改进的聚类算法
虽然使用K-Mean算法进行文本聚类时，具有计算复杂度低，计算效率不仅高，而且伸缩性较强，适应大数据集的能力也很强的优点，但是实验发现，不仅初始聚类中心的选取对聚类结果有影响，孤立点的存在对文本的相似性的判断也有很大的影响，这就导致聚类判断不稳定。基于此，文章采用一种改进的方法来进行文本聚类，改进关键点在于聚类中心的计算，用与原聚类中心相似的文本数据来计算平均值作为该聚类中心。
改进的K-Means算法描述如下所示：
1)首先给定n个数据文本，从其中任选k个文本，这k个数据文本初始地代表了k个类的数据中心;
2)对剩余的每个文本计算其到每个中心的距离，并把它归到最近的中心类中，记作means;
3)选择类中与类中心大于等于(1+a)*means的文本集合{D1，D2，...，Dk}，其中a[-0.31，0.31]，重新计算新文本集中的类中心;
4)迭代执行第2步和第3步的动作直至新的中心与原中心相等或小于指定阈值，直到算法结束。
3 相似度计算
文本聚类中涉及文本的相似性计算，只有相似性大的文本才能聚到同一类中，因此，相似性的度量对文本的聚类很关键。在文本聚类中，相似度度量方式一般有曼哈顿距离、Cosine距离、欧式距离，其中Cosine距离更能体现文本的相似性。本文主要采用Cosine距离，当两个文本之间的文本相似度越大，它们之间的相关性越强。文本集用向量空间模型表示后，文本的相似度采用向量之间距离表示：
(1) 4 评价标准
文本聚类的有效性需要进行验证，文章中主要采用F度量、平均纯度来对聚类结果进行评价。
1)F度量。F度量把召回率和评价标准准确率结合在一起。
准确率：P(i，r)=nir/nr (2)
召回率：R(i，r)=nir/ni (3)
其中nir是类别r中包含类别i中的文本的个数，nr是类别r中实际文本的数目，ni是原本类别i中应有的文本数，F值的计算公式：
(4)
由公式(4)最后得到评价函数为：
(5)
其中n为文本的总数。从公式看出F值越高，聚类效果越好。
2)平均纯度。除了用F度量来评价聚类，文章中还使用平均纯度来度量文本聚类质量好坏[7]。设类ci的大小为ni，则该类的纯度为：
(6)
其中nj表示类ci与第j类的交集大小，则平均纯度公式为：
(7)
其中k为最终的聚类数目。一般说来纯度越高聚类效果越好。
5 聚类实验结果分析
文章中采用的实验数据主要是搜狗语料库。搜狗语料库主要包括10种文本类别：军事、招聘、IT、文化、健康、汽车、体育、旅游、财经、教育。搜狗语料库包含了每一类的文件夹，在文件夹中都是txt文本。为了验证改进后的算法比原算法更有效，进行了多次实验，最终选取了其中一次实验结果为例子，对两种算法的F度量和纯度进行比较，分别如表1和表2所示。
从表1可以看出，改进聚类中心的K-Means算法在纯度方面相对有一些提高;从表2可以看到F值提高明显;从两个表中的实验结果可以看到改进的算法是有效的。
6 结论
基于文本的聚类分析能够对大量的文本进行聚类，分析中采用的聚类算法的改进能在很大程度上提高聚类的准确性。实验证明达到设计的效果，同时也为后期的各种数据挖掘工作打下基础。
参考文献
[1]Salton G， Wong A， Yang C S. A vector space model for automatic indexing[J].Comm. ACM，1975，18(11)：613-620.
[2]Steinbach M， KaryPis G， Kumar V. A comparison of document clustering techniques[C].Proceedings of KDD 2000 Workshop on Text Mining.2000：1-20.
[3]Ying Zhao， KaryPis G. Hierarchical Clustering Algorithms for Document Datasets[J].Proceedings of Data Mining and Knowledge Discovery，2005，10(2)：141-168.
[4]Dhillon I S， Modha D S. Concept decompositions for large sparse text data using clustering[J].Machine Learning，2001，
42(1)：143-175.
[5]邵峰晶，于忠清.数据挖掘原理与算法[M].北京：中国水利水电出版社，2003.
[6]MacQueen J. Some methods for classification and analysis
of multivariate observations[C]//Proceedings of 5th Berkeley
Symposium on Mathematics. Statistics and Science.1967：281-
296.
[7]Hammouda K， Kamel M. Collaborative document clu-stering[C]//2006 SIAM Conference on Data Mining (SDM06).
2006：453-463.
