Abstract: 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.

Key words: cluster analysis, k-means algorithm, I-k-means-+ algorithm, min-max criterion, region division