Robust Cut for Hierarchical Clustering and Merge Trees
No Thumbnail Available
Date
2024
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
The Eurographics Association
Abstract
Hierarchical clustering arrange multi-dimensional data into a tree-like structure, organizing the data by increasing levels of similarity. A cut of the tree divides data into clusters, where cluster members share a likeness. Most common cutting techniques identify a single line, either by a metric or with user input, cutting horizontally through the tree, separating root from leaves. We present a new approach that algorithmically identifies cuts at multiple levels of the tree based on a metric we call robustness. We identify levels to maximize overall robustness by maximizing the height of the shortest branch of the hierarchical tree we must cut through. This technique minimizes the variation within clusters while maximizing the distance between clusters. We apply the same approach to merge trees from computational topology to find the most robust number of connected components. We apply the multi-level robust cut to two datasets to highlight the advantages compared to a traditional, single-level cut.
Description
CCS Concepts: Mathematics of computing → Algebraic topology; Information systems → Clustering and classification
@inproceedings{10.2312:evs.20241070,
booktitle = {EuroVis 2024 - Short Papers},
editor = {Tominski, Christian and Waldner, Manuela and Wang, Bei},
title = {{Robust Cut for Hierarchical Clustering and Merge Trees}},
author = {Banesh, Divya and Ahrens, James and Bujack, Roxana},
year = {2024},
publisher = {The Eurographics Association},
ISBN = {978-3-03868-251-6},
DOI = {10.2312/evs.20241070}
}