Hierarchical clustering using the arithmetic-harmonic cut: complexity and experiments.

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 pr...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Romeo Rizzi, Pritha Mahata, Luke Mathieson, Pablo Moscato
Formato:	article
Lenguaje:	EN
Publicado:	Public Library of Science (PLoS) 2010
Materias:	Medicine R Science Q
Acceso en línea:	https://doaj.org/article/3d1c06c6ca0b43f78298ded6d8916924
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:3d1c06c6ca0b43f78298ded6d8916924
record_format	dspace
spelling	oai:doaj.org-article:3d1c06c6ca0b43f78298ded6d89169242021-11-18T07:02:10ZHierarchical clustering using the arithmetic-harmonic cut: complexity and experiments.1932-620310.1371/journal.pone.0014067https://doaj.org/article/3d1c06c6ca0b43f78298ded6d89169242010-12-01T00:00:00Zhttps://www.ncbi.nlm.nih.gov/pmc/articles/pmid/21151943/?tool=EBIhttps://doaj.org/toc/1932-6203Clustering, 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.Romeo RizziPritha MahataLuke MathiesonPablo MoscatoPublic Library of Science (PLoS)articleMedicineRScienceQENPLoS ONE, Vol 5, Iss 12, p e14067 (2010)
institution	DOAJ
collection	DOAJ
language	EN
topic	Medicine R Science Q
spellingShingle	Medicine R Science Q Romeo Rizzi Pritha Mahata Luke Mathieson Pablo Moscato Hierarchical clustering using the arithmetic-harmonic cut: complexity and experiments.
description	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.
format	article
author	Romeo Rizzi Pritha Mahata Luke Mathieson Pablo Moscato
author_facet	Romeo Rizzi Pritha Mahata Luke Mathieson Pablo Moscato
author_sort	Romeo Rizzi
title	Hierarchical clustering using the arithmetic-harmonic cut: complexity and experiments.
title_short	Hierarchical clustering using the arithmetic-harmonic cut: complexity and experiments.
title_full	Hierarchical clustering using the arithmetic-harmonic cut: complexity and experiments.
title_fullStr	Hierarchical clustering using the arithmetic-harmonic cut: complexity and experiments.
title_full_unstemmed	Hierarchical clustering using the arithmetic-harmonic cut: complexity and experiments.
title_sort	hierarchical clustering using the arithmetic-harmonic cut: complexity and experiments.
publisher	Public Library of Science (PLoS)
publishDate	2010
url	https://doaj.org/article/3d1c06c6ca0b43f78298ded6d8916924
work_keys_str_mv	AT romeorizzi hierarchicalclusteringusingthearithmeticharmoniccutcomplexityandexperiments AT prithamahata hierarchicalclusteringusingthearithmeticharmoniccutcomplexityandexperiments AT lukemathieson hierarchicalclusteringusingthearithmeticharmoniccutcomplexityandexperiments AT pablomoscato hierarchicalclusteringusingthearithmeticharmoniccutcomplexityandexperiments
_version_	1718424033845837824

Hierarchical clustering using the arithmetic-harmonic cut: complexity and experiments.

Ejemplares similares