Information-theoretic distance measures for clustering validation: Generalization and normalization

Ping Luo, Hui Xiong, Guoxing Zhan, Junjie Wu, Zhongzhi Shi

Research output: Contribution to journalArticlepeer-review

17 Scopus citations

Abstract

This paper studies the generalization and normalization issues of information-theoretic distance measures for clustering validation. Along this line, we first introduce a uniform representation of distance measures, defined as quasi-distance, which is induced based on a general form of conditional entropy. The quasi-distance possesses three properties: symmetry, the triangle law, and the minimum reachable. These properties ensure that the quasi-distance naturally lends itself as the external measure for clustering validation. In addition, we observe that the ranges of the distance measures are different when they apply for clustering validation on different data sets. Therefore, when comparing the performances of clustering algorithms on different data sets, distance normalization is required to equalize ranges of the distance measures. A critical challenge for distance normalization is to obtain the ranges of a distance measure when a data set is provided. To that end, we theoretically analyze the computation of the maximum value of a distance measure for a data set. Finally, we compare the performances of the partition clustering algorithm K-means on various real-world data sets. The experiments show that the normalized distance measures have better performance than the original distance measures when comparing clusterings of different data sets. Also, the normalized Shannon distance has the best performance among four distance measures under study.

Original languageEnglish (US)
Article number4633356
Pages (from-to)1249-1262
Number of pages14
JournalIEEE Transactions on Knowledge and Data Engineering
Volume21
Issue number9
DOIs
StatePublished - Sep 2009

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics

Keywords

  • Clustering validation
  • Entropy
  • Information-theoretic distance measures
  • K-means clustering

Fingerprint

Dive into the research topics of 'Information-theoretic distance measures for clustering validation: Generalization and normalization'. Together they form a unique fingerprint.

Cite this