Clustering on Manifolds with Dual-Rooted Minimal Spanning Trees

Laurent Galluccio (1) , Olivier J.J. Michel (2) , Pierre Comon (1)

1 Laboratoire d'Informatique, Signaux, et Systèmes de Sophia-Antipolis (I3S) / Equipe SIGNAL
2 GIPSA-CICS - GIPSA - Communication Information and Complex Systems

In this paper, we introduce a new distance computed from the construction of dual-rooted minimal spanning trees (MSTs). This distance extends Grikschat's approach, exhibits attractive properties and allows to account for both local and global neighborhood information. Furthermore, a function measuring the probability that a point belongs to a detected class is proposed. Some connections with diffusion maps are outlined. The dual-rooted tree-based distance (DRPT) allows us to construct a new affinity matrix for use in a spectral clustering algorithm, or leads to a new data analysis method. Results are presented on benchmark datasets.

Mots clés: clustering; minimal spanning tree; distance measure

Domaines: Machine Learning [stat.ML]

Laurent Galluccio, Olivier J.J. Michel, Pierre Comon. Clustering on Manifolds with Dual-Rooted Minimal Spanning Trees. EUSIPCO 2010 - 18th European Signal Processing Conference, Aug 2010, Aalborg, Denmark. ⟨hal-00492745v2⟩