Hierarchical clustering using the arithmetic-harmonic cut: Complexity and experiments

Romeo Rizzi, Pritha Mahata, Luke Mathieson*, Pablo Moscato

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

9 Citations (Scopus)

Abstract

Clustering, particularly hierarchical clustering, is an important method for understanding and analysing data across a wide variety of knowledge domains with notable utility in systems where the data can be classified in an evolutionary context. This paper introduces a new hierarchical clustering problem defined by a novel objective function we call the arithmeticharmonic cut. We show that the problem of finding such a cut is NP-hard and APX-hard but is fixed-parameter tractable, which indicates that although the problem is unlikely to have a polynomial time algorithm (even for approximation), exact parameterized and local search based techniques may produce workable algorithms. To this end, we implement a memetic algorithm for the problem and demonstrate the effectiveness of the arithmetic-harmonic cut on a number of datasets including a cancer type dataset and a corona virus dataset. We show favorable performance compared to currently used hierarchical clustering techniques such as k-MEANS, Graclus and NORMALIZED-CUT. The arithmetic-harmonic cut metric overcoming difficulties other hierarchal methods have in representing both intercluster differences and intracluster similarities.

Original languageEnglish
Article numbere14067
JournalPLoS ONE
Volume5
Issue number12
DOIs
Publication statusPublished - 2010

Fingerprint

Dive into the research topics of 'Hierarchical clustering using the arithmetic-harmonic cut: Complexity and experiments'. Together they form a unique fingerprint.

Cite this