改进的K均值算法在中文文本聚类中的研究-计算机软件与理论专业论文.docxVIP

摘要 摘要 III III IV IV 摘要 随着信息时代的到来，各种电子文本数据急剧增加，如何对庞杂的数据进 行有效的管理并快速的获取需要的信息，已成为一项亟待解决的重要课题。文 本聚类和文本分类作为一个有效的管理和组织文本的工具，受到了越来越多的 重视和研究。 本文以中文文本聚类为研究对象，对中文文本聚类全过程进行了较为深入 的研究，包括文本预处理，文本聚类。针对 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 算法。 关键词： 合作聚类 ，K 均值算法，二分 K 均值算法 ，向量空间模型 摘要 摘要 V V VI VI Abstract Along with the information time, various statistics of electronic texts increased sharply. How to manage the complex statistics validly and achieve needed information has become an imperative topic which needs to be tackled immediately. As efficient tools for manage and organize texts, text clustering and categorization have attracted more and more attention and research. In this paper ,the main research target is Chinese texts, we do deep research on the whole process of text clustering ,which including two steps：texts pre-processing and clustering. On the analyze the shortcomings of K-means(short for KM) algorithm and bisecting k-means clustering(short for BKM) algorithm, we proposed a novel improved clustering algorithms on the basis of cooperative clustering: cooperate bisecting k-means clustering algorithm (short for CBKM). The main work of this paper is present