Expanding the class of global objective functions for dissimilarity-based hierarchical clustering

DOI10.1007/S00357-023-09447-XMaRDI QIDQ6187790zbMATH OpenFDO

Authors Sebastien Roch

Publication date 1 February 2024

Published in Journal of Classification (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2207.14375

zbMATH Keywords

greedy algorithmshierarchical clusteringminimum evolution

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) General topics of discrete mathematics in relation to computer science (68R01) Problems related to evolution (92D15)

Abstract: Recent work on dissimilarity-based hierarchical clustering has led to the introduction of global objective functions for this classical problem. Several standard approaches, such as average linkage, as well as some new heuristics have been shown to provide approximation guarantees. Here we introduce a broad new class of objective functions which satisfy desirable properties studied in prior work. Many common agglomerative and divisive clustering methods are shown to be greedy algorithms for these objectives, which are inspired by related concepts in phylogenetics.

Cites work

• A cost function for similarity-based hierarchical clustering
• A signal-to-noise analysis of phylogeny estimation by neighbor-joining: Insufficiency of polynomial length sequences
• Approximate hierarchical clustering via sparsest cut and spreading metrics
• Approximating the balanced minimum evolution problem
• Combinatorics of least-squares trees
• Computational phylogenetics. An introduction to designing methods for phylogeny estimation
• Hierarchical clustering better than average-linkage
• Hierarchical clustering: objective functions and algorithms
• scientific article; zbMATH DE number 1865935 (Why is no real title available?)
• Likelihood Based Hierarchical Clustering
• Machine learning. A probabilistic perspective
• Minimum evolution using ordinary least-squares is less robust than neighbor-joining
• On the uniqueness of the selection criterion in neighbor-joining
• Phylogeny. Discrete and random processes in evolution
• The performance of neighbor-joining methods of phylogenetic reconstruction
• Toward extracting all phylogenetic information from matrices of evolutionary distances
• Why neighbor-joining works

This page was built for publication: Expanding the class of global objective functions for dissimilarity-based hierarchical clustering

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6187790)