Functorial hierarchical clustering with overlaps

DOI10.1016/J.DAM.2017.10.015zbMATH Open1377.05028arXiv1609.02513OpenAlexW2518738319MaRDI QIDQ1693136FDOQ1693136

Authors: Jared Culbertson, Dan P. Guralnik, Peter F. Stiller 

Publication date: 11 January 2018

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: This work draws inspiration from three important sources of research on dissimilarity-based clustering and intertwines those three threads into a consistent principled functorial theory of clustering. Those three are the overlapping clustering of Jardine and Sibson, the functorial approach of Carlsson and M'{e}moli to partition-based clustering, and the Isbell/Dress school's study of injective envelopes. Carlsson and M'{e}moli introduce the idea of viewing clustering methods as functors from a category of metric spaces to a category of clusters, with functoriality subsuming many desirable properties. Our first series of results extends their theory of functorial clustering schemes to methods that allow overlapping clusters in the spirit of Jardine and Sibson. This obviates some of the unpleasant effects of chaining that occur, for example with single-linkage clustering. We prove an equivalence between these general overlapping clustering functors and projections of weight spaces to what we term clustering domains, by focusing on the order structure determined by the morphisms. As a specific application of this machinery, we are able to prove that there are no functorial projections to cut metrics, or even to tree metrics. Finally, although we focus less on the construction of clustering methods (clustering domains) derived from injective envelopes, we lay out some preliminary results, that hopefully will give a feel for how the third leg of the stool comes into play.

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

Recommendations

• Classifying clustering schemes
• An order theoretic framework for overlapping clustering
• Towards an axiomatic approach to hierarchical clustering of measures
• Fixed points approach to clustering
• scientific article; zbMATH DE number 431953

zbMATH Keywords

hierarchical clusteringtree metricinjective envelopenon-expansive mapA-spacecut metricclustering domainclustering with overlapsfunctorial clusteringsieving functor

Mathematics Subject Classification ID

Trees (05C05) Distance in graphs (05C12) Metric spaces, metrizability (54E35) Extension of maps (54C20)

Cites Work

• Computational topology. An introduction
• Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups: A note on combinatorial properties of metric spaces
• A course in metric geometry
• A canonical decomposition theory for metrics on a finite set
• An order theoretic framework for overlapping clustering
• Six theorems about injective metric spaces
• Ordinal and relational clustering. With CD-ROM.
• An Algorithm for Computing Virtual Cut Points in Finite Metric Spaces
• Geometry of cuts and metrics
• Cluster Analysis
• Injective hulls of certain discrete metric spaces and groups.
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Classification of six-point metrics
• Persistence-based clustering in Riemannian manifolds
• Extension of uniformly continuous transformations and hyperconvex metric spaces
• Characterization, stability and convergence of hierarchical clustering methods
• Weak hierarchies associated with similarity measures - An additive clustering technique
• Statistical properties of the single linkage hierarchical clustering estimator
• A comparison between two distinct continuous models in projective cluster theory: The median and the tight-span construction
• Some variations on a theme by Buneman
• Totally split-decomposable metrics of combinatorial dimension two
• Set systems and dissimilarities
• Weak Hierarchies: A Central Clustering Structure
• The tight span of an antipodal metric space. II: Geometrical properties
• The tight span of an antipodal metric space. I: combinatorial properties
• Classifying clustering schemes
• Obtaining splits from cut sets of tight spans
• Enhanced topology-sensitive clustering by Reeb graph shattering
• One-to-One Correspondence Between Indexed Cluster Structures and Weakly Indexed Closed Cluster Structures

Cited In (5)

• Classifying clustering schemes
• Functorial manifold learning
• Preventing overlaps in agglomerative hierarchical conceptual clustering
• Hypergraph co-optimal transport: metric and categorical properties
• Edge erasures and chordal graphs

This page was built for publication: Functorial hierarchical clustering with overlaps

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