Several Remarks on Dissimilarities and Ultrametrics

Published in Volume XXV, Issue 1, 2015, pages 155-170, doi: 10.7561/SACS.2015.1.155

Authors: D. A. Simovici

Abstract

We investigate the relationships between tolerance relations, equivalence relations, and ultrametrics. The set of spheres associated to an ultrametric space has a tree structure that rejects a hierarchy on the set of equivalences associated to that space. We show that every ultrametric defined on a finite space is a linear combination of binary ultrametric and we introduce the notion of ultrametricity for dissimilarities, which has applications in many data mining problems.

Full Text (PDF)

References

[1] Y. Amice. Les nombres p-adiques. Presses Universitaires de France, Paris, 1975.

[2] P. Contreras and F. Murtagh. Fast, linear time hierarchical clustering using the Baire metric. Journal of Classification, 29(2):118–143, 2012. http://dx.doi.org/10.1007/s00357-012-9106-3 .

[3] M. M. Deza and M. Laurent. Geometry of Cuts and Metrics. Springer, Heidelberg, 1997. http://dx.doi.org/10.1007/978-3-642-04295-9 .

[4] A. D. Gordon. Classification. Chapman and Hall, London, 1981.

[5] A. D. Gordon. A review of hierarchical classification. Journal of the Royal Statistical Society, Series (A), 150(2):119–137, 1987. http://dx.doi.org/10.2307/2981629 .

[6] N. Jardine and R. Sibson. Mathematical Taxonomy. Wiley, New York, 1971.

[7] M. Kimura. The Neutral Theory of Molecular Evolution. Cambridge University Press, Cambridge, UK, 1983.

[8] B. Leclerc. La comparaison des hiérarchies: indices et métriques. Mathématiques et sciences humaines, 92:5–40, 1985.

[9] I. C. Lerman. Classification et Analyse Ordinale des Données. Dunod, Paris, 1981.

[10] J. Ninio. Molecular Approaches to Evolution. Princeton University, Princeton, NJ, 1983.

[11] R. Rammal, G. Touluse, and M. A. Virasoro. Ultrametricity for physicists. Reviews of Modern Physics, 58:765–788, 1986. http://dx.doi.org/10.1103/RevModPhys.58.765 .

[12] W. H. Schikhof. Ultrametric Calculus. Cambridge University Press, Cambridge, UK, 1984.

[13] D. A. Simovici and C. Djeraba. Mathematical Tools for Data Mining. Springer, London, second edition, 2014. http://dx.doi.org/10.1007/978-1-4471-6407-4 .

[14] D. A. Simovici, R. Vetro, and K. Hua. Ultrametricity of dissimilarity spaces and its significance for data mining. In Proceedings of EGC 2015, Luxembourg. EGC, 2015. (to appear).

Bibtex

@article{sacscuza:simovici2015srodau,
  title={Several Remarks on Dissimilarities and Ultrametrics},
  author={D. A. Simovici},
  journal={Scientific Annals of Computer Science},
  volume={25},
  number={1},
  organization={``A.I. Cuza'' University, Iasi, Romania},
  year={2015},
  pages={155--170},
  doi={10.7561/SACS.2015.1.155},
  publisher={``A.I. Cuza'' University Press}
}