最大距离法选取初始簇中心的K-means文本聚类算法的研究  

K-means text clustering algorithm based on initial cluster centers selection according to maximum distance

作　　者：翟东海[1,2] 鱼江[1] 高飞[2] 于磊[1] 丁锋[2] 

机构地区：[1]西南交通大学信息科学与技术学院,成都610031 [2]西藏大学工学院,拉萨850000

出　　处：《计算机应用研究》2014年第3期713-715,719,共4页Application Research of Computers

基　　金：国家语委"十二五"科研规划项目(YB125-49);国家教育部科学技术研究重点项目(212167);中央高校基本科研业务费专项资金科技创新项目(SWJTU12CX096);西藏自治区大学生创新性实验训练计划项目(2011CX051)

摘　　要：由于初始簇中心的随机选择,K-means算法在聚类时容易出现聚类结果局部最优、聚类结果不稳定、总迭代次数较多等问题。为了解决K-means算法所存在的以上问题,提出了最大距离法选取初始簇中心的Kmeans文本聚类算法。该算法基于这样的事实:距离最远的样本点最不可能分到同一个簇中。为使该算法能应用于文本聚类,构造了一种将文本相似度转换为文本距离的方法,同时也重新构造了迭代中的簇中心计算公式和测度函数。在实例验证中,对分属于五个类别的1 500篇文本组成的文本集进行了文本聚类分析,其结果表明,与原始的K-means聚类算法以及其他的两种改进的K-means聚类算法相比,新提出的文本聚类算法在降低了聚类总耗时的同时,F度量值也有了明显提高。Due to the random selection of initial cluster centers, K-means clustering algorithm is prone to local optimal and in- stability of clustering results, and huge number of iterations. To overcome the above problems, this paper selected the initial cluster centers according to maximum distance, and it was based on the fact that the farthest samples were the least likely in the same cluster. To apply the improved algorithm into text clustering, it constructed a method to transform text similarity into text distance, and also reconstructed cluster center iteration formula and measurement function. It employed a text set which included 5 categories and 1 500 texts in the experiment. The experimental resuhs show that, compared with the original K- means algorithm and its two recently improved editions, the proposed method can improve the F-measure and reduce total con- suming time.

关 键 词：K-MEANS聚类算法 最大距离 文本聚类 文本距离 测度函数 F度量值 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]