A K-means clustering algorithm based on the maximum triangle rule

Being a measurable criterion of clustering quality for the classical K-means algorithm, the objective function always exists many local minimum values. The objective function may converge at some minimum values, when the initial clustering centers are dropped neighbor to the local minimum values, or the two data objects in the same cluster are regarded as two initial clustering centers which represent two clusters. Then, the problem of local optimal solution will happen. To this, a K-means clustering algorithm based on the maximum triangle rule (KMTR) is proposed in this paper. KMTR, which uses the rule of maximum triangle, selects appropriate initial clustering centers for the classical K-means algorithm. Experimental results on some UCI data sets show the validity of applying maximum triangle rule to the K-means algorithm.