Fast, linear time hierarchical clustering using the Baire metric

DOI10.1007/S00357-012-9106-3zbMATH Open1360.62322OpenAlexW3102052320MaRDI QIDQ263340FDOQ263340

Authors Pedro Contreras, F. Murtagh

Publication date 4 April 2016

Published in Journal of Classification (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1106.2229

zbMATH Keywords

\(k\)-meanshierarchical clustering\(m\)-adic\(p\)-adicBairelongest common prefixredshiftultrametric

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30)

Abstract: The Baire metric induces an ultrametric on a dataset and is of linear computational complexity, contrasted with the standard quadratic time agglomerative hierarchical clustering algorithm. In this work we evaluate empirically this new approach to hierarchical clustering. We compare hierarchical clustering based on the Baire metric with (i) agglomerative hierarchical clustering, in terms of algorithm properties; (ii) generalized ultrametrics, in terms of definition; and (iii) fast clustering through k-means partititioning, in terms of quality of results. For the latter, we carry out an in depth astronomical study. We apply the Baire distance to spectrometric and photometric redshifts from the Sloan Digital Sky Survey using, in this work, about half a million astronomical objects. We want to know how well the (more costly to determine) spectrometric redshifts can predict the (more easily obtained) photometric redshifts, i.e. we seek to regress the spectrometric on the photometric redshifts, and we use clusterwise regression for this.

Recommendations

• Direct reading algorithm for hierarchical clustering
• Hierarchical Clustering of Massive, High Dimensional Data Sets by Exploiting Ultrametric Embedding
• Hierarchical clustering
• scientific article; zbMATH DE number 1124646
• The remarkable simplicity of very high dimensional data: application of model-based clustering

Cites work

• scientific article; zbMATH DE number 1824109 (Why is no real title available?)
• scientific article; zbMATH DE number 3969923 (Why is no real title available?)
• scientific article; zbMATH DE number 3615363 (Why is no real title available?)
• scientific article; zbMATH DE number 1748069 (Why is no real title available?)
• scientific article; zbMATH DE number 2109363 (Why is no real title available?)
• scientific article; zbMATH DE number 877297 (Why is no real title available?)
• Algorithm AS 136: A K-Means Clustering Algorithm
• An Order Theoretic Model for Cluster Analysis
• Degenerating families of dendrograms
• Hierarchical Clustering of Massive, High Dimensional Data Sets by Exploiting Ultrametric Embedding
• Hierarchical clustering schemes
• On ultrametricity, data coding, and computation
• Ordinal and relational clustering. With CD-ROM.
• Symmetry in data mining and analysis: a unifying view based on hierarchy
• Thinking ultrametrically, thinking \(p\)-adically

Cited in

(7)

• Ultrametric diffusion equation on energy landscape to model disease spread in hierarchic socially clustered population
• Sparse \(p\)-adic data coding for computationally efficient and effective big data analytics
• Direct reading algorithm for hierarchical clustering
• Versatile linkage: a family of space-conserving strategies for agglomerative hierarchical clustering
• Fast, linear time, \(m\)-adic hierarchical clustering for search and retrieval using the Baire metric, with linkages to generalized ultrametrics, hashing, formal concept analysis, and precision of data measurement
• Ultrametricity of dissimilarity spaces and its significance for data mining
• Thinking ultrametrically, thinking \(p\)-adically

Describes a project that uses

Uses Software

• AS 136

This page was built for publication: Fast, linear time hierarchical clustering using the Baire metric

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q263340)