Hierarchical clustering with dot products recovers hidden tree structure

• URL: http://arxiv.org/abs/2305.15022v3
• Date: Fri, 1 Mar 2024 16:25:54 GMT
• Title: Hierarchical clustering with dot products recovers hidden tree structure
• Authors: Annie Gray, Alexander Modell, Patrick Rubin-Delanchy, Nick Whiteley
• Abstract summary: In this paper we offer a new perspective on the well established agglomerative clustering algorithm, focusing on recovery of hierarchical structure. We recommend a simple variant of the standard algorithm, in which clusters are merged by maximum average dot product and not, for example, by minimum distance or within-cluster variance. We demonstrate that the tree output by this algorithm provides a bona fide estimate of generative hierarchical structure in data, under a generic probabilistic graphical model.
• Score: 53.68551192799585
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this paper we offer a new perspective on the well established agglomerative clustering algorithm, focusing on recovery of hierarchical structure. We recommend a simple variant of the standard algorithm, in which clusters are merged by maximum average dot product and not, for example, by minimum distance or within-cluster variance. We demonstrate that the tree output by this algorithm provides a bona fide estimate of generative hierarchical structure in data, under a generic probabilistic graphical model. The key technical innovations are to understand how hierarchical information in this model translates into tree geometry which can be recovered from data, and to characterise the benefits of simultaneously growing sample size and data dimension. We demonstrate superior tree recovery performance with real data over existing approaches such as UPGMA, Ward's method, and HDBSCAN.

Related papers

• ClusterGraph: a new tool for visualization and compression of multidimensional data [0.0]
  This paper provides an additional layer on the output of any clustering algorithm. It provides information about the global layout of clusters, obtained from the considered clustering algorithm.
  arXiv  Detail & Related papers  (2024-11-08T09:40:54Z)
• Structured Generations: Using Hierarchical Clusters to guide Diffusion Models [12.618079575423868]
  This paper introduces Diffuse-TreeVAE, a deep generative model that integrates hierarchical clustering into the framework of Denoising Diffusion Probabilistic Models (DDPMs) The proposed approach generates new images by sampling from a root embedding of a learned latent tree VAE-based structure, it then propagates through hierarchical paths, and utilizes a second-stage DDPM to refine and generate distinct, high-quality images for each data cluster.
  arXiv  Detail & Related papers  (2024-07-08T17:00:28Z)
• Tree Variational Autoencoders [5.992683455757179]
  We propose a new generative hierarchical clustering model that learns a flexible tree-based posterior distribution over latent variables. TreeVAE hierarchically divides samples according to their intrinsic characteristics, shedding light on hidden structures in the data.
  arXiv  Detail & Related papers  (2023-06-15T09:25:04Z)
• Entailment Tree Explanations via Iterative Retrieval-Generation Reasoner [56.08919422452905]
  We propose an architecture called Iterative Retrieval-Generation Reasoner (IRGR) Our model is able to explain a given hypothesis by systematically generating a step-by-step explanation from textual premises. We outperform existing benchmarks on premise retrieval and entailment tree generation, with around 300% gain in overall correctness.
  arXiv  Detail & Related papers  (2022-05-18T21:52:11Z)
• Hierarchical clustering by aggregating representatives in sub-minimum-spanning-trees [5.877624540482919]
  We propose a novel hierarchical clustering algorithm, in which, while building the clustering dendrogram, we can effectively detect the representative point. Under our analysis, the proposed algorithm has O(nlogn) time-complexity and O(logn) space-complexity, indicating that it has the scalability in handling massive data.
  arXiv  Detail & Related papers  (2021-11-11T07:36:55Z)
• Exact and Approximate Hierarchical Clustering Using A* [51.187990314731344]
  We introduce a new approach based on A* search for clustering. We overcome the prohibitively large search space by combining A* with a novel emphtrellis data structure. We empirically demonstrate that our method achieves substantially higher quality results than baselines for a particle physics use case and other clustering benchmarks.
  arXiv  Detail & Related papers  (2021-04-14T18:15:27Z)
• Visualizing hierarchies in scRNA-seq data using a density tree-biased autoencoder [50.591267188664666]
  We propose an approach for identifying a meaningful tree structure from high-dimensional scRNA-seq data. We then introduce DTAE, a tree-biased autoencoder that emphasizes the tree structure of the data in low dimensional space.
  arXiv  Detail & Related papers  (2021-02-11T08:48:48Z)
• Scalable Hierarchical Agglomerative Clustering [65.66407726145619]
  Existing scalable hierarchical clustering methods sacrifice quality for speed. We present a scalable, agglomerative method for hierarchical clustering that does not sacrifice quality and scales to billions of data points.
  arXiv  Detail & Related papers  (2020-10-22T15:58:35Z)
• Structured Graph Learning for Clustering and Semi-supervised Classification [74.35376212789132]
  We propose a graph learning framework to preserve both the local and global structure of data. Our method uses the self-expressiveness of samples to capture the global structure and adaptive neighbor approach to respect the local structure. Our model is equivalent to a combination of kernel k-means and k-means methods under certain condition.
  arXiv  Detail & Related papers  (2020-08-31T08:41:20Z)
• Data Structures & Algorithms for Exact Inference in Hierarchical Clustering [41.24805506595378]
  We present novel dynamic-programming algorithms for emphexact inference in hierarchical clustering based on a novel trellis data structure. Our algorithms scale in time and space proportional to the powerset of $N$ elements which is super-exponentially more efficient than explicitly considering each of the (2N-3)!! possible hierarchies.
  arXiv  Detail & Related papers  (2020-02-26T17:43:53Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.