Fast, linear time hierarchical clustering using the Baire metric

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

F. Murtagh, Pedro Contreras

Publication date: 4 April 2016

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

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.

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

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

zbMATH Keywords

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

Mathematics Subject Classification ID

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

Cites Work

• Algorithm AS 136: A K-Means Clustering Algorithm
• Hierarchical clustering schemes
• Title not available (Why is that?)
• Symmetry in data mining and analysis: a unifying view based on hierarchy
• Title not available (Why is that?)
• Ordinal and Relational Clustering
• Hierarchical Clustering of Massive, High Dimensional Data Sets by Exploiting Ultrametric Embedding
• An Order Theoretic Model for Cluster Analysis
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Thinking Ultrametrically, Thinking p-Adically
• Degenerating families of dendrograms
• On ultrametricity, data coding, and computation

Cited In (8)

• Thinking Ultrametrically, Thinking p-Adically
• 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
• Ultrametric diffusion equation on energy landscape to model disease spread in hierarchic socially clustered population
• Direct reading algorithm for hierarchical clustering
• Sparse \(p\)-adic data coding for computationally efficient and effective big data analytics
• Toward a unified theory of sparse dimensionality reduction in Euclidean space

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)