Abstract
We introduce novel dissimilarity to properly measure dissimilarity among multiple clusters when each cluster is characterized by a probability distribution. This measure of dissimilarity is called redundancy-based dissimilarity among probability distributions. From aspects of source coding, a statistical hypothesis test and a connection with Ward’s method, we shed light on the theoretical reasons that the redundancy-based dissimilarity among probability distributions is a reasonable measure of dissimilarity among clusters.
This work was supported in part by Grant-in-Aids 18700157 and 18500116 for scientific research from the Ministry of Education, Culture, Sports, Science, and Technology, Japan.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Duda, R.O., Hart, P.E., Stork, D.G.: Pattern Classification, 2nd edn. John Wiley & Sons, New York (2001)
Xu, R., Wunsch-II, D.C.: Survey of clustering algorithms. IEEE Transactions on Neural Networks 16(3), 645–678 (2005)
Gokcay, E., Principle, J.C.: Information theoretic clustering. IEEE Transactions on Pattern Analysis and Machine Intelligence 24(2), 158–171 (2002)
Maulik, U., Bandyopadhyay, S.: Performance evaluation of some clustering algorithms and validity indices. IEEE Transactions on Pattern Analysis and Machine Intelligence 24(12), 1650–1654 (2002)
Webb, A.R.: Statistical Pattern Recognition, 2nd edn. John Wiley & Sons, New York (2002)
Yeung, D., Wang, X.: Improving performance of similarity-based clustering by feature weight learning. IEEE Transactions on Pattern Analysis and Machine Intelligence 24(4), 556–561 (2002)
Fred, A.L., Leitão, J.M.: A new cluster isolation criterion based on dissimilarity increments. IEEE Transactions on Pattern Analysis and Machine Intelligence 25(8), 944–958 (2003)
Yang, M.S., Wu, K.L.: A similarity-based robust clustering method. IEEE Transactions on Pattern Analysis and Machine Intelligence 26(4), 434–448 (2004)
Tipping, M.E.: Deriving cluster analytic distance functions from gaussian mixture model. In: Proceedings of the 9th International Conference on Artificial Neural Networks, Edinburgh, UK, vol. 2, pp. 815–820. IEE (1999)
Prieto, M.S., Allen, A.R.: A similarity metric for edge images. IEEE Transactions on Pattern Analysis and Machine Intelligence 25(10), 1265–1273 (2003)
Wei, J.: Markov edit distance. IEEE Transactions on Pattern Analysis and Machine Intelligence 26(3), 311–321 (2004)
Srivastava, A., Joshi, S.H., Mio, W., Liu, X.: Statistical shape analysis: Clustering, learning, and testing. IEEE Transactions on Pattern Analysis and Machine Intelligence 27(4), 590–602 (2005)
Österreicher, F.: On a class of perimeter-type distances of probability distributions. Cybernetics 32(4), 389–393 (1996)
Topsøe, F.: Some inequalities for information divergence and related measures of discrimination. IEEE Transactions on Information Theory 46(4), 1602–1609 (2000)
Endres, D.M., Schindelin, J.E.: A new metric for probability distributions. IEEE Transactions on Information Theory 49(7), 1858–1860 (2003)
Sanov, I.N.: On the probability of large deviations of random variables. Selected Translations in Mathematical Statistics and Probability 1, 213–244 (1961)
Dembo, A., Zeitouni, O.: Large Deviations Techniques and Applications, 2nd edn. Applications of Mathematics, vol. 38. Springer, New York (1998)
Han, T.S., Kobayashi, K.: Mathematics of Information and Coding. Translations of Mathematical Monographs, vol. 203. American Mathematical Society, Providence (2002)
Cover, T.M., Thomas, J.A.: Elements of Information Theory, 1st edn. Wiley series in telecommunications. John Wiley & Sons, Inc., New York (1991)
Ward, J.H.: Hierarchical grouping to optimize an objective function. Journal of the American Statistical Association 58(301), 236–244 (1963)
Ward, J.H., Hook, M.E.: Application of an hierarchical grouping procedure to a problem of grouping profiles. Educational Psychological Measurement 23(1), 69–82 (1963)
Gärtner, J.: On large deviations from the invariant measure. Theory of Probability and Its Applications 22, 24–39 (1977)
Ellis, R.S.: Large deviations for a general class of random vectors. The Annals of Probability 12(5), 1–12 (1984)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Iwata, K., Hayashi, A. (2006). Theory of a Probabilistic-Dependence Measure of Dissimilarity Among Multiple Clusters. In: Kollias, S., Stafylopatis, A., Duch, W., Oja, E. (eds) Artificial Neural Networks – ICANN 2006. ICANN 2006. Lecture Notes in Computer Science, vol 4132. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11840930_32
Download citation
DOI: https://doi.org/10.1007/11840930_32
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-38871-5
Online ISBN: 978-3-540-38873-9
eBook Packages: Computer ScienceComputer Science (R0)