基于min-max准则与区域划分的I-k-means-+聚类算法

I-k-means-+Clustering Algorithm Based on min-max Criterion and Region Division

针对I-k-means-+算法聚类结果不稳定、求解精度较低的问题,提出一种基于min-max准则与区域划分的I-k-means-+聚类算法.首先,提出min-max准则,计算每个数据点到最近中心的距离,优先选择距离最大的数据点作为新的聚类中心,避免多个初始中心聚集在同一个簇中的情况;其次,将分裂簇中的数据点分割到不同区域,在每个区域中选取一个数据点作为候选中心,以增加候选中心的多样性;最后,对于配对失败的簇,通过增益重新选择新的分裂簇与原删除簇再次配对,以提高配对成功率,进一步降低目标函数值.实验结果表明,与I-k-means-+算法相比,本文算法在运行效率基本相当的前提下,求解精度平均提高6.47%,且聚类结果更稳定;与k-means、k-means++算法相比,本文算法的求解精度更高.

Aiming at the problem of unstable clustering results and low solving accuracy of I-k-means-+algorithm,we proposed I-k-means-+clustering algorithm based on min-max criterion and region division.Firstly,the min-max criterion was proposed to calculate the distance from each data point to the nearest center,and the data point with the largest distance was preferentially selected as the new clustering center to avoid multiple initial centers gathering in the same cluster.Secondly,the data points in the split cluster were divided into different regions,and a data point was selected as the candidate center in each region to increase the diversity of the candidate center.Finally,for the clusters that failed to pair,the new split cluster was re-selected by gain to pair with the original deleted cluster again,so as to improve the pairing success rate and further reduce the objective function value.The experimental results show that compared with the I-k-means-+algorithm,the proposed algorithm improves the accuracy of the solution by 6.47%on average while maintaining similar operational efficiency,and the clustering results are more stable.Compared with k-means and k-means++algorithms,the proposed algorithm has higher solving accuracy.