Direct Reading Algorithm for Hierarchical Clustering

Fionn Murtagh, Pedro Contreras

Research output: Contribution to journalArticle

Abstract

Reading the clusters from a data set such that the overall computational complexity is linear in both data dimensionality and in the number of data elements has been carried out through filtering the data in wavelet transform space. This objective is also carried out after an initial transforming of the data to a canonical order. Including high dimensional, high cardinality data, such a canonical order is provided by row and column permutations of the data matrix. In our recent work, we induce a hierarchical clustering from seriation through unidimensional representation of our observations. This linear time hierarchical classification is directly derived from the use of the Baire metric, which is simultaneously an ultrametric. In our previous work, the linear time construction of a hierarchical clustering is studied from the following viewpoint: representing the hierarchy initially in an m-adic, m = 10, tree representation, followed by decreasing m to smaller valued representations that include p-adic representations, where p is prime and m is a non-prime positive integer. This has the advantage of facilitating a more direct visualization and hence interpretation of the hierarchy. In this work we present further case studies and examples of how this approach is very advantageous for such an ultrametric topological data mapping.

LanguageEnglish
Pages37-42
Number of pages6
JournalElectronic Notes in Discrete Mathematics
Volume56
DOIs
Publication statusPublished - 1 Dec 2016
Externally publishedYes
Event1st Institute of Mathematics Conference on Theoretical and Computational Discrete Mathematics - University of Derby, Derby, United Kingdom
Duration: 22 Mar 201623 Mar 2016
https://ima.org.uk/1350/1st-ima-conference-theoretical-computational-discrete-mathematics/ (Link to Conference Website)

Fingerprint

Hierarchical Clustering
Wavelet transforms
Computational complexity
Visualization
Linear Time
Seriation
Hierarchical Classification
P-adic
Wavelet Transform
Dimensionality
Cardinality
Permutation
Computational Complexity
High-dimensional
Filtering
Metric
Integer

Cite this

@article{803d469324d243eb843280781e371499,
title = "Direct Reading Algorithm for Hierarchical Clustering",
abstract = "Reading the clusters from a data set such that the overall computational complexity is linear in both data dimensionality and in the number of data elements has been carried out through filtering the data in wavelet transform space. This objective is also carried out after an initial transforming of the data to a canonical order. Including high dimensional, high cardinality data, such a canonical order is provided by row and column permutations of the data matrix. In our recent work, we induce a hierarchical clustering from seriation through unidimensional representation of our observations. This linear time hierarchical classification is directly derived from the use of the Baire metric, which is simultaneously an ultrametric. In our previous work, the linear time construction of a hierarchical clustering is studied from the following viewpoint: representing the hierarchy initially in an m-adic, m = 10, tree representation, followed by decreasing m to smaller valued representations that include p-adic representations, where p is prime and m is a non-prime positive integer. This has the advantage of facilitating a more direct visualization and hence interpretation of the hierarchy. In this work we present further case studies and examples of how this approach is very advantageous for such an ultrametric topological data mapping.",
keywords = "analytics, hierarchical clustering, linear time computational complexity, p-adic and m-adic number representation, ultrametric topology",
author = "Fionn Murtagh and Pedro Contreras",
year = "2016",
month = "12",
day = "1",
doi = "10.1016/j.endm.2016.11.006",
language = "English",
volume = "56",
pages = "37--42",
journal = "Electronic Notes in Discrete Mathematics",
issn = "1571-0653",
publisher = "Elsevier",

}

Direct Reading Algorithm for Hierarchical Clustering. / Murtagh, Fionn; Contreras, Pedro.

In: Electronic Notes in Discrete Mathematics, Vol. 56, 01.12.2016, p. 37-42.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Direct Reading Algorithm for Hierarchical Clustering

AU - Murtagh, Fionn

AU - Contreras, Pedro

PY - 2016/12/1

Y1 - 2016/12/1

N2 - Reading the clusters from a data set such that the overall computational complexity is linear in both data dimensionality and in the number of data elements has been carried out through filtering the data in wavelet transform space. This objective is also carried out after an initial transforming of the data to a canonical order. Including high dimensional, high cardinality data, such a canonical order is provided by row and column permutations of the data matrix. In our recent work, we induce a hierarchical clustering from seriation through unidimensional representation of our observations. This linear time hierarchical classification is directly derived from the use of the Baire metric, which is simultaneously an ultrametric. In our previous work, the linear time construction of a hierarchical clustering is studied from the following viewpoint: representing the hierarchy initially in an m-adic, m = 10, tree representation, followed by decreasing m to smaller valued representations that include p-adic representations, where p is prime and m is a non-prime positive integer. This has the advantage of facilitating a more direct visualization and hence interpretation of the hierarchy. In this work we present further case studies and examples of how this approach is very advantageous for such an ultrametric topological data mapping.

AB - Reading the clusters from a data set such that the overall computational complexity is linear in both data dimensionality and in the number of data elements has been carried out through filtering the data in wavelet transform space. This objective is also carried out after an initial transforming of the data to a canonical order. Including high dimensional, high cardinality data, such a canonical order is provided by row and column permutations of the data matrix. In our recent work, we induce a hierarchical clustering from seriation through unidimensional representation of our observations. This linear time hierarchical classification is directly derived from the use of the Baire metric, which is simultaneously an ultrametric. In our previous work, the linear time construction of a hierarchical clustering is studied from the following viewpoint: representing the hierarchy initially in an m-adic, m = 10, tree representation, followed by decreasing m to smaller valued representations that include p-adic representations, where p is prime and m is a non-prime positive integer. This has the advantage of facilitating a more direct visualization and hence interpretation of the hierarchy. In this work we present further case studies and examples of how this approach is very advantageous for such an ultrametric topological data mapping.

KW - analytics

KW - hierarchical clustering

KW - linear time computational complexity

KW - p-adic and m-adic number representation

KW - ultrametric topology

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

U2 - 10.1016/j.endm.2016.11.006

DO - 10.1016/j.endm.2016.11.006

M3 - Article

VL - 56

SP - 37

EP - 42

JO - Electronic Notes in Discrete Mathematics

T2 - Electronic Notes in Discrete Mathematics

JF - Electronic Notes in Discrete Mathematics

SN - 1571-0653

ER -