Adapting the right measures for K-means clustering

ABSTRACT

Clustering validation is a long standing challenge in the clustering literature. While many validation measures have been developed for evaluating the performance of clustering algorithms, these measures often provide inconsistent information about the clustering performance and the best suitable measures to use in practice remain unknown. This paper thus fills this crucial void by giving an organized study of 16 external validation measures for K-means clustering. Specifically, we first introduce the importance of measure normalization in the evaluation of the clustering performance on data with imbalanced class distributions. We also provide normalization solutions for several measures. In addition, we summarize the major properties of these external measures. These properties can serve as the guidance for the selection of validation measures in different application scenarios. Finally, we reveal the interrelationships among these external measures. By mathematical transformation, we show that some validation measures are equivalent. Also, some measures have consistent validation performances. Most importantly, we provide a guide line to select the most suitable validation measures for K-means clustering.

REFERENCES

• 1: A. Ben-Hur and I. Guyon. Detecting stable clusters using principal component analysis. In Methods in Molecular Biology. Humana press, 2003.
• 2: Marcel Brun , Chao Sima , Jianping Hua , James Lowey , Brent Carroll , Edward Suh , Edward R. Dougherty, Model-based evaluation of clustering validation measures, Pattern Recognition, v.40 n.3, p.807-824, March, 2007 [doi>10.1016/j.patcog.2006.06.026]
• 3: Thomas M. Cover , Joy A. Thomas, Elements of Information Theory (Wiley Series in Telecommunications and Signal Processing), Wiley-Interscience, 2006
• 4: M. DeGroot and M. Schervish. Probability and Statistics (3rd Edition). Addison Wesley, 2001.
• 5: E.B. Fowlkes and C.L. Mallows. A method for comparing two hierarchical clusterings. Journal of the American Statistical Association, 78:553--569, 1983.
• 6: L.A. Goodman and W.H. Kruskal. Measures of association for cross classification. Journal of the American Statistical Association, 49:732--764, 1954.
• 7: Maria Halkidi , Yannis Batistakis , Michalis Vazirgiannis, Cluster validity methods: part I, ACM SIGMOD Record, v.31 n.2, June 2002 [doi>10.1145/565117.565124]
• 8: L. Hubert. Nominal scale response agreement as a generalized correlation. British Journal of Mathematical and Statistical Psychology, 30:98--103, 1977.
• 9: L. Hubert and P. Arabie. Comparing partitions. Journal of Classification, 2:193--218, 1985.
• 10: Anil K. Jain , Richard C. Dubes, Algorithms for clustering data, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
• 11: G. Karypis. Cluto -- software for clustering high-dimensional datasets, version 2.1.1. Oct. 2007.
• 12: M.G. Kendall. Rank Correlation Methods. New York: Hafner Publishing Co., 1955.
• 13: Bjornar Larsen , Chinatsu Aone, Fast and effective text mining using linear-time document clustering, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.16-22, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312186]
• 14: J. MacQueen. Some methods for classification and analysis of multivariate observations. In BSMSP, Vol. I, Statistics. University of California Press, 1967.
• 15: MathWorks. K-means clustering in statistics toolbox.
• 16: Marina Meilǎ, Comparing clusterings: an axiomatic view, Proceedings of the 22nd international conference on Machine learning, p.577-584, August 07-11, 2005, Bonn, Germany [doi>10.1145/1102351.1102424]
• 17: B. Mirkin. Mathematical Classification and Clustering. Kluwer Academic Press, 1996.
• 18: W.M. Rand. Objective criteria for the evaluation of clustering methods. Journal of the American Statistical Association, 66:846--850, 1971.
• 19: C. J. Van Rijsbergen, Information Retrieval, Butterworth-Heinemann, Newton, MA, 1979
• 20: Michael Steinbach, George Karypis, and Vipin Kumar. A comparison of document clustering techniques. In Workshop on Text Mining, KDD, 2000.
• 21: A. Strehl, J. Ghosh, and R.J. Mooney. Impact of similarity measures on web-page clustering. In Workshop on Artificial Intelligence for Web Search, AAAI, pages 58--64, 2000.
• 22: TREC. Text retrieval conference. Oct. 2007.
• 23: Stijn Dongen, Performance criteria for graph clustering and Markov cluster experiments, CWI (Centre for Mathematics and Computer Science), Amsterdam, The Netherlands, 2000
• 24: Junjie Wu , Hui Xiong , Jian Chen , Wenjun Zhou, A Generalization of Proximity Functions for K-Means, Proceedings of the 2007 Seventh IEEE International Conference on Data Mining, p.361-370, October 28-31, 2007 [doi>10.1109/ICDM.2007.59]
• 25: Hui Xiong , Junjie Wu , Jian Chen, K-means clustering versus validation measures: a data distribution perspective, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150503]
• 26: Ying Zhao , George Karypis, Empirical and Theoretical Comparisons of Selected Criterion Functions for Document Clustering, Machine Learning, v.55 n.3, p.311-331, June 2004 [doi>10.1023/B:MACH.0000027785.44527.d6]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

Additional Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.3 Clustering

General Terms:
Experimentation, Measurement

Keywords:
cluster validation, external criteria, k-means