Data ultrametricity and clusterability

The increasing needs of clustering massive datasets and the high cost of running clustering algorithms poses difficult problems for users. In this context it is important to determine if a data set is clusterable, that is, it may be partitioned efficiently into well-differentiated groups containing similar objects. We approach data clusterability from an ultrametric-based perspective. A novel approach to determine the ultrametricity of a dataset is proposed via a special type of matrix product, which allows us to evaluate the clusterability of the dataset. Furthermore, we show that by applying our technique to a dissimilarity space will generate the sub-dominant ultrametric of the dissimilarity.

• Publication year

  2019

• Venue

  Journal of Physics: Conference Series

• Publication date

  2019-08-28

• Fields of study

  Biology, Mathematics, Physics, Computer Science

• Identifiers
  DOI 10.1088/1742-6596/1334/1/012002arXiv 1908.10833
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• To Cluster, or Not to Cluster: An Analysis of Clusterability Methods

  2018cited by this paper
• An Effective and Efficient Approach for Clusterability Evaluation

  2016influential reference
• Computational Feasibility of Clustering under Clusterability Assumptions

  2015cited by this paper
• Clustering is difficult only when it does not matter

  2012cited by this paper
• In Advances in Neural Information Processing Systems

  2011cited by this paper
• Weighted Clustering

  2011cited by this paper
• Towards Property-Based Classification of Clustering Paradigms

  2010cited by this paper
• Clusterability: A Theoretical Study

  2009cited by this paper
• A discriminative framework for clustering via similarity functions

  2008cited by this paper
• Mathematical Tools for Data Mining: Set Theory, Partial Orders, Combinatorics

  2008cited by this paper
• Measures of Clustering Quality: A Working Set of Axioms for Clustering

  2008cited by this paper
• Identifying and Exploiting Ultrametricity

  2007cited by this paper
• Clustering in Very High Dimensions

  2005cited by this paper
• A Stability Based Method for Discovering Structure in Clustered Data

  2001cited by this paper
• Clusterability Detection and Initial Seed Selection in Large Data Sets

  1999cited by this paper
• Description combinatoire des ultramétriques

  1981cited by this paper

• CUDA and OpenMp Implementation of Boolean Matrix Product with Applications in Visual SLAM

  2023cites this paper
• Sparse clusterability: testing for cluster structure in high dimensions

  2023cites this paper
• Widening the Time Horizon: Predicting the Long-Term Behavior of Chaotic Systems

  2022cites this paper
• The Concept of Reverse Clustering

  2021cites this paper
• Unclusterable, underdispersed arrangement of insect-pollinated plants in pollinator niche space

  2020cites this paper