改进的K均值算法在中文文本聚类中的研究

随着信息时代的到来,各种电子文本数据急剧增加,如何对庞杂的数据进行有效的管理并快速的获取需要的信息,已成为一项亟待解决的重要课题。文本聚类和文本分类作为一个有效的管理和组织文本的工具,受到了越来越多的重视和研究。 本文以中文文本聚类为研究对象,对中文文本聚类全过程进行了较为深入的研究,包括文本预处理,文本聚类。针对K均值算法(KM)和二分K均值算法(BKM)在聚类分析存在的不足,基于合作聚类思想,提出了一种改进的文本聚类算法：合作二分K均值算法(CBKM)。 本文主要的工作和取得的成果如下： (1)对当前主要的文本聚类方法及代表性算法进行了深入分析和研究,指出了各种代表性算法的优缺点及适用范围。 (2)对文本聚类中文本表示模型、文本间距离的度量和文本预处理等关键技术问题进行了较为深入的探讨。 (3)K均值算法(KM),其聚类效果由于受初始聚类中心的影响,k值选择难以有统一标准,且初始聚类中心的选择会对聚类产生较大影响,孤立点的存在造成很难找到全局最优解。而二分K均值算法(BKM),其在聚类过程中产生的成员碎片难以通过其他方法来进行重新聚类。针对KM算法和BKM算法在聚类中存在的缺陷,作者基于合作聚类的思想,提出了一种合作二分K均值算法(CBKM)。该算法主要分为整体聚类、合作聚类和融合三个阶段。该算法是在BKM产生CF树的过程中与通过KM进行同步的中间合作来实现的。通过引入相似柱状图的概念,其能够直观的反应簇之间元素的粘合性。并根据子类相似的相似柱状图计算出两个子类的融合因子,将融合因子值最大的两个簇进行融合,更新聚类簇。此过程产生的聚类结果能够有效的避免聚类碎片的产生,并且由于是对子类的交集进行合并聚类,所以有效的改善了K均值算法受初始聚类中心影响,该算法得到的是全局最有解,而不是局部最优解。 (4) CBKM算法是建立在KM算法和BKM算法的融合基础上,从性能上来看,CBKM算法的时间复杂度高于KM算法和BKM算法,但低于两者的和。 (5)基于搜狗语料库,分别对KM算法、BKM算法和CBKM算法进行中文文本聚类实验。结果表明：在互信息、纯度、F度量这三个度量标准上,CBKM算法均高于其他两个算法；而在熵值这个度量标准上,CBKM算法明显低于其他两个算法。因此,CBKM的聚类性能优于BKM和KM算法。