LIPIcs.MFCS.2020.32.pdf
- Filesize: 0.58 MB
- 13 pages
Document
The Mergegram of a Dendrogram and Its Stability
Authors
-
Part of:
Volume:
45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Mathematical Foundations of Computer Science (MFCS) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2020-08-18
Cite As Get BibTex
Yury Elkin and Vitaliy Kurlin. The Mergegram of a Dendrogram and Its Stability. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 32:1-32:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.MFCS.2020.32
Abstract
This paper extends the key concept of persistence within Topological Data Analysis (TDA) in a new direction. TDA quantifies topological shapes hidden in unorganized data such as clouds of unordered points. In the 0-dimensional case the distance-based persistence is determined by a single-linkage (SL) clustering of a finite set in a metric space. Equivalently, the 0D persistence captures only edge-lengths of a Minimum Spanning Tree (MST). Both SL dendrogram and MST are unstable under perturbations of points. We define the new stable-under-noise mergegram, which outperforms previous isometry invariants on a classification of point clouds by PersLay.
Subject Classification
ACM Subject Classification
- Theory of computation → Computational geometry
Keywords
- clustering dendrogram
- topological data analysis
- persistence
- stability
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Gunnar Carlsson and Facundo Memoli. Characterization, stability and convergence of hierarchical clustering methods. Journal of machine learning research, 11:1425-1470, 2010.
-
Mathieu Carriere, Frederic Chazal, Yuichi Ike, Theo Lacombe, Martin Royer, and Yuhei Umeda. Perslay: A neural network layer for persistence diagrams and new graph topological signatures. AISTATS, arXiv:1904.09378, 2020.
-
Frédéric Chazal, Vin De Silva, Marc Glisse, and Steve Oudot. The structure and stability of persistence modules. Springer, 2016.
-
David Cohen-Steiner, Herbert Edelsbrunner, and John Harer. Stability of persistence diagrams. Discrete & Computational Geometry, 37(1):103-120, 2007.
-
Sara Kalisnik, Vitaliy Kurlin, and Davorin Lesnik. A higher-dimensional homologically persistent skeleton. Adv. App. Maths, 102:113-142, 2019.
-
Vitaliy Kurlin. Auto-completion of contours in sketches, maps and sparse 2d images based on topological persistence. In Proceedings of SYNASC 2014 workshop CTIC: Computational Topology in Image Context, pages 594-601. IEEE, 2014.
-
Vitaliy Kurlin. A fast and robust algorithm to count topologically persistent holes in noisy clouds. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 1458-1463, 2014.
-
Vitaliy Kurlin. A homologically persistent skeleton is a fast and robust descriptor of interest points in 2d images. In LNCS, Procedings of CAIP: Computer Analysis of Images and Patterns, volume 9256, pages 606-617, 2015.
-
William B March, Parikshit Ram, and Alexander G Gray. Fast euclidean minimum spanning tree: algorithm, analysis, and applications. In Proceedings of SIG KDD: Knowledge discovery and data mining, pages 603-612, 2010.
-
Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Russ R Salakhutdinov, and Alexander J Smola. Deep sets. In Advances in neural information processing systems, pages 3391-3401, 2017.