The Clustering Based On Simulated Annealing With Convex Restriction

Current algorithms for k-means clustering suffer from that they converge to different local minima resulting from different initializations. To deal with this problem, some kinds of K-means Clustering based on Simulated Annealing (SA) have been presented, taking advantage of the global optimum feature of the SA. In these algorithms, the process of Local Search (LS) is stochastic and unrestrained entirely, which generates many bad solutions owing to Combination Disaster Problem, resulting in low probability of reaching better solutions, slow convergence speed and waste of computing time. In this paper, some LS strategies are studied based on the knowledge of Computing Geometry and Discrete Mathematics.Firstly, it's proved that, in geometrical aspect, the iterative process of K-means Clustering is continuous transition from one Voronoi Diagram to another terminating until the Central Voronoi Diagram(CVD) emerges and that the global optima of clustering based on "sum-of-squared-error criterion" is CVD too. Then one new clustering algorithm based on SA with Convex Restriction is presented relying on the knowledge of Convex Polygon and Delaunay Triangle. New algorithm requires that subclasses in generated neighborhood are unintersectant.The new Clustering algorithm only detects the neighborhoods which meet the convex restriction situation, distinctly reducing the region-searching and enhancing the ability of reaching global optima plus accelerating convergence speed.