title: Hierarchical clustering using the arithmetic-harmonic cut: complexity and experiments.
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 arithmetic-harmonic 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 hierarchical methods have in representing both intercluster differences and intracluster similarities.
authors.affiliation: Dipartimento di Matematica ed Informatica, University of Udine, Udine, Italy.
authors.forename: Romeo
authors.initials: R
authors.lastname: Rizzi
authors.forename: Pritha
authors.initials: P
authors.lastname: Mahata
authors.forename: Luke
authors.initials: L
authors.lastname: Mathieson
authors.forename: Pablo
authors.initials: P
authors.lastname: Moscato
mesh_terms: D000465:Algorithms; D045744:Cell Line, Tumor; D016000:Cluster Analysis; D003110:Colonic Neoplasms / Q000378:metabolism; D019295:Computational Biology / Q000379:methods*; D020869:Gene Expression Profiling; D015972:Gene Expression Regulation, Neoplastic; D006801:Humans; D007938:Leukemia / Q000378:metabolism; D008545:Melanoma / Q000378:metabolism; D015233:Models, Statistical; D008962:Models, Theoretical