一种用于文本聚类的改进k-means算法  

An improved k-means algorithm for document clustering

作　　者：索红光[1] 王玉伟[2] 

机构地区：[1]北京理工大学计算机科学技术学院,北京100081 [2]中国石油大学计算机与通信工程学院,山东东营257061

出　　处：《山东大学学报（理学版）》2008年第1期60-64,共5页Journal of Shandong University(Natural Science)

摘　　要：k-means是目前常用的文本聚类算法,针对其最终搜索的局部极值与全局最优解偏差较大的缺点,采用一种基于局部搜索优化的思想来改进算法,并推导出目标函数的变化公式。根据目标函数值的改变对聚类结果作再次划分后,继续k-means迭代,拓展其搜索范围。理论分析和实验结果表明修改后的算法能有效地提高聚类的质量,且计算复杂度仍与数据集文本总数呈线性变化。The k-means algorithm is a popular method for document clustering, but it often gets stuck at a local maximum far from the optimal solution. A procedure based on local search was used to improve this algorithm. The formula about object function change was also deduced, which can be used to again partition the clustering. This procedure makes appropriate iterations to enlarge the search space. Theory analysis and experimental results show that the improved algorithm efficiently improves k-means clustering and its computation is also linear in the size of document collection.

关 键 词：文本聚类 K-MEANS 向量空间模型 局部迭代 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]