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

k-means是目前常用的文本聚类算法,针对其最终搜索的局部极值与全局最优解偏差较大的缺点,采用一种基于局部搜索优化的思想来改进算法,并推导出目标函数的变化公式。根据目标函数值的改变对聚类结果作再次划分后,继续k-means迭代,拓展其搜索范围。理论分析和实验结果表明修改后的算法能有效地提高聚类的质量,且计算复杂度仍与数据集文本总数呈线性变化。

An improved k-means algorithm for document clustering

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.