Fast, Linear Time Hierarchical Clustering using the Baire Metric

Pedro Contreras, Fionn Murtagh

Research output: Contribution to journalArticle

16 Citations (Scopus)

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 partitioning, 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.

Original languageEnglish
Pages (from-to)118-143
Number of pages26
JournalJournal of Classification
Volume29
Issue number2
DOIs
Publication statusPublished - 1 Jul 2012
Externally publishedYes

Fingerprint

Hierarchical Clustering
Cluster Analysis
Linear Time
Metric
know how
Astronomical Objects
regression
Linear Complexity
K-means
Clustering Algorithm
Partitioning
Computational Complexity
Regression
Clustering
Predict
time
Hierarchical clustering
Evaluate

Cite this

@article{03cbd44bd8224f679914e03a24a6b5c3,
title = "Fast, Linear Time Hierarchical Clustering using the Baire Metric",
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 partitioning, 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.",
keywords = "Baire, Hierarchical clustering, k-means, Longest common prefix, m-adic, p-adic, Redshift, Ultrametric",
author = "Pedro Contreras and Fionn Murtagh",
year = "2012",
month = "7",
day = "1",
doi = "10.1007/s00357-012-9106-3",
language = "English",
volume = "29",
pages = "118--143",
journal = "Journal of Classification",
issn = "0176-4268",
publisher = "Springer New York",
number = "2",

}

Fast, Linear Time Hierarchical Clustering using the Baire Metric. / Contreras, Pedro; Murtagh, Fionn.

In: Journal of Classification, Vol. 29, No. 2, 01.07.2012, p. 118-143.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Fast, Linear Time Hierarchical Clustering using the Baire Metric

AU - Contreras, Pedro

AU - Murtagh, Fionn

PY - 2012/7/1

Y1 - 2012/7/1

N2 - 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 partitioning, 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.

AB - 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 partitioning, 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.

KW - Baire

KW - Hierarchical clustering

KW - k-means

KW - Longest common prefix

KW - m-adic

KW - p-adic

KW - Redshift

KW - Ultrametric

UR - http://www.scopus.com/inward/record.url?scp=84863004563&partnerID=8YFLogxK

U2 - 10.1007/s00357-012-9106-3

DO - 10.1007/s00357-012-9106-3

M3 - Article

VL - 29

SP - 118

EP - 143

JO - Journal of Classification

JF - Journal of Classification

SN - 0176-4268

IS - 2

ER -