An Empirical Evaluation of K-Means Clustering Algorithm Using Different Distance/Similarity Metrics

摘要

k-means is an effective and efficient clustering algorithm. It uses distance/similarity metric to find out the distance/similarity among the data objects. The objects which are closer/similar to each other are assigned to the same cluster where as distant/dissimilar objects are assigned to different clusters. Most of the implementations of k-means are based on Euclidean/Squared Euclidean distance metrics. In order to find out the possibility of different distance/similarity metrics to be used with k-means algorithm, an empirical evaluation has been performed. In this paper, accuracy, performance and reliability of 13 different distance/similarity measures over 6 different variations of data using k-means algorithm have been compared based on empirical evaluation on well-known benchmark IRIS data set. Accuracy is measured in terms of similarity of cluster assignment between ground truth and machine clustering. Performance is measured in terms of the number of iterations used for convergence of the final cluster assignment. Reliability is measured on the basis of correctness of the cluster assignment.