License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2019.38
URN: urn:nbn:de:0030-drops-109826
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10982/
Go to the corresponding LIPIcs Volume Portal

Fluck, Eva

Tangles and Single Linkage Hierarchical Clustering

pdf-format:
LIPIcs-MFCS-2019-38.pdf (0.4 MB)

Abstract

We establish a connection between tangles, a concept from structural graph theory that plays a central role in Robertson and Seymour's graph minor project, and hierarchical clustering. Tangles cannot only be defined for graphs, but in fact for arbitrary connectivity functions, which are functions defined on the subsets of some finite universe, which in typical clustering applications consists of points in some metric space.
Connectivity functions are usually required to be submodular. It is our first contribution to show that the central duality theorem connecting tangles with hierarchical decompositions (so-called branch decompositions) also holds if submodularity is replaced by a different property that we call maximum-submodular.
We then define a natural, though somewhat unusual connectivity function on finite data sets in an arbitrary metric space and prove that its tangles are in one-to-one correspondence with the clusters obtained by applying the well-known single linkage clustering algorithms to the same data set.
The idea of viewing tangles as clusters has first been proposed by Diestel and Whittle [Reinhard Diestel et al., 2019] as an approach to image segmentation. To the best of our knowledge, our result is the first that establishes a precise technical connection between tangles and clusters.

BibTeX - Entry

@InProceedings{fluck:LIPIcs:2019:10982,
  author =	{Eva Fluck},
  title =	{{Tangles and Single Linkage Hierarchical Clustering}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{38:1--38:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Peter Rossmanith and Pinar Heggernes and Joost-Pieter Katoen},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10982},
  URN =		{urn:nbn:de:0030-drops-109826},
  doi =		{10.4230/LIPIcs.MFCS.2019.38},
  annote =	{Keywords: Tangles, Branch Decomposition, Duality, Hierarchical Clustering, Single Linkage}
}

Keywords: Tangles, Branch Decomposition, Duality, Hierarchical Clustering, Single Linkage
Collection: 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Issue Date: 2019
Date of publication: 20.08.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI