A Deterministic k-means Initialization Method

  • O. Kettani
  • F. Ramdani
Keywords: k-means, clustering, KKZ, initialization


The most prominent clustering algorithm k-means has a major drawback: it's sensitivity to the initial clustering centers. To overcome this problem, we propose to initialize k-means by using the Agglomerative Clustering Method (ACM) introduced by the authors in a previous work. The complexity of the proposed approach is O(nk), where n is the number of objects in the input dataset and k the number of clusters. We evaluated its performance by applying on various benchmark datasets and comparing with the related Katsavounidis, Kuo and Zhang (KKZ) O(nk) algorithm. Experimental results have demonstrated that the proposed approach produces more consistent clustering results in term of average Silhouette index.