Linear Storage and Potentially Constant Time Hierarchical Clustering Using the Baire Metric and Random Spinning Paths

Fionn Murtagh; Pedro Contreras

doi:10.1007/978-3-319-25226-1_4

Linear Storage and Potentially Constant Time Hierarchical Clustering Using the Baire Metric and Random Spinning Paths

Fionn Murtagh, Pedro Contreras

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

4 Citations (Scopus)

Abstract

We study how random projections can be used with large data sets in order (1) to cluster the data using a fast, binning approach which is characterized in terms of direct inducing of a hierarchy through use of the Bairemetric; and (2) based on clusters found, selecting subsets of the original data for further analysis. In this work, we focus on random projection that is used for processing high dimensional data. A random projection, outputting a random permutation of the observation set, provides a random spanning path. We show how a spanning path relates to contiguity- or adjacency-constrained clustering.We study performance properties of hierarchical clustering constructed from random spanning paths, and we introduce a novel visualization of the results.

Original language	English
Title of host publication	Analysis of Large and Complex Data
Publisher	Kluwer Academic Publishers
Pages	43-52
Number of pages	10
ISBN (Print)	9783319252247
DOIs	https://doi.org/10.1007/978-3-319-25226-1_4
Publication status	Published - 4 Aug 2016
Externally published	Yes
Event	2nd European Conference on Data Analysis: Analysis of Large and Complex Data - Bremen, Germany Duration: 2 Jul 2014 → 4 Jul 2014 Conference number: 2 https://dblp.org/db/conf/ecda/ecda2014

Conference

Conference	2nd European Conference on Data Analysis
Abbreviated title	ECDA2014
Country/Territory	Germany
City	Bremen
Period	2/07/14 → 4/07/14
Internet address	https://dblp.org/db/conf/ecda/ecda2014

Access to Document

10.1007/978-3-319-25226-1_4Licence: Unspecified

Cite this

@inproceedings{1035e6f91b05434194c64ec443bd5b40,

title = "Linear Storage and Potentially Constant Time Hierarchical Clustering Using the Baire Metric and Random Spinning Paths",

abstract = "We study how random projections can be used with large data sets in order (1) to cluster the data using a fast, binning approach which is characterized in terms of direct inducing of a hierarchy through use of the Bairemetric; and (2) based on clusters found, selecting subsets of the original data for further analysis. In this work, we focus on random projection that is used for processing high dimensional data. A random projection, outputting a random permutation of the observation set, provides a random spanning path. We show how a spanning path relates to contiguity- or adjacency-constrained clustering.We study performance properties of hierarchical clustering constructed from random spanning paths, and we introduce a novel visualization of the results.",

author = "Fionn Murtagh and Pedro Contreras",

year = "2016",

month = aug,

day = "4",

doi = "10.1007/978-3-319-25226-1_4",

language = "English",

isbn = "9783319252247",

pages = "43--52",

booktitle = "Analysis of Large and Complex Data",

publisher = "Kluwer Academic Publishers",

address = "Netherlands",

note = "2nd European Conference on Data Analysis : Analysis of Large and Complex Data, ECDA2014 ; Conference date: 02-07-2014 Through 04-07-2014",

url = "https://dblp.org/db/conf/ecda/ecda2014",

}

TY - GEN

T1 - Linear Storage and Potentially Constant Time Hierarchical Clustering Using the Baire Metric and Random Spinning Paths

AU - Murtagh, Fionn

AU - Contreras, Pedro

N1 - Conference code: 2

PY - 2016/8/4

Y1 - 2016/8/4

N2 - We study how random projections can be used with large data sets in order (1) to cluster the data using a fast, binning approach which is characterized in terms of direct inducing of a hierarchy through use of the Bairemetric; and (2) based on clusters found, selecting subsets of the original data for further analysis. In this work, we focus on random projection that is used for processing high dimensional data. A random projection, outputting a random permutation of the observation set, provides a random spanning path. We show how a spanning path relates to contiguity- or adjacency-constrained clustering.We study performance properties of hierarchical clustering constructed from random spanning paths, and we introduce a novel visualization of the results.

AB - We study how random projections can be used with large data sets in order (1) to cluster the data using a fast, binning approach which is characterized in terms of direct inducing of a hierarchy through use of the Bairemetric; and (2) based on clusters found, selecting subsets of the original data for further analysis. In this work, we focus on random projection that is used for processing high dimensional data. A random projection, outputting a random permutation of the observation set, provides a random spanning path. We show how a spanning path relates to contiguity- or adjacency-constrained clustering.We study performance properties of hierarchical clustering constructed from random spanning paths, and we introduce a novel visualization of the results.

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

U2 - 10.1007/978-3-319-25226-1_4

DO - 10.1007/978-3-319-25226-1_4

M3 - Conference contribution

AN - SCOPUS:84981521246

SN - 9783319252247

SP - 43

EP - 52

BT - Analysis of Large and Complex Data

PB - Kluwer Academic Publishers

T2 - 2nd European Conference on Data Analysis

Y2 - 2 July 2014 through 4 July 2014

ER -

Linear Storage and Potentially Constant Time Hierarchical Clustering Using the Baire Metric and Random Spinning Paths

Abstract

Conference

Access to Document

Other files and links

Fingerprint

Cite this