基于加权处罚的K-均值优化算法

An Optimal K-means Algorithm Based on Weighted Penalty

在各种聚类算法中,基于目标函数的K-均值聚类算法应用最为广泛,然而,K-均值算法对初始聚类中心特别敏感,聚类结果易收敛于局部最优。为此,提出基于加权处罚的K-均值优化算法。每次迭代过程中,根据簇的平均误差的大小为簇分配权值,构造加权准则函数,把样本分给加权距离最小的簇中。限制簇集中出现平均误差较大的簇,提高聚类准确率。实验结果表明,该算法与K-均值算法、优化初始聚类中心的K-均值算法相比,在含有噪音的数据集中,表现出更好的抗噪性能,聚类效果更好。

In a variety of clustenng algorithms, K-means clustering algorithm which is based on the objective function has the most widely used, However, K-means is sensible to the initial seeds, poor local optima can be easily obtained. To tackle the initialization problem of K-means, an optimal K-Means algorithm based on weighted penalty is proposed. In each iteration process, the weights are assigned for the clusters relative to their average variance; a weighted version of K-means objective is constructed; the samples are taken to the clusters of minimum weighted distance. The emergence of large average variance clusters is limited and the clustering accuracy is improved. The effectiveness of the approach is verified in experiments and the immune property with noises is got in its clustering, as it is compared favorably with both K-means and other methods from the literature that consider the K-means initialization problem.