Fast and explainable clustering based on sorting

• URL: http://arxiv.org/abs/2202.01456v2
• Date: Thu, 15 Feb 2024 17:02:58 GMT
• Title: Fast and explainable clustering based on sorting
• Authors: Xinye Chen, Stefan G\"uttel
• Abstract summary: We introduce a fast and explainable clustering method called CLASSIX. The algorithm is controlled by two scalar parameters, namely a distance parameter for the aggregation and another parameter controlling the minimal cluster size. Our experiments demonstrate that CLASSIX competes with state-of-the-art clustering algorithms.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We introduce a fast and explainable clustering method called CLASSIX. It consists of two phases, namely a greedy aggregation phase of the sorted data into groups of nearby data points, followed by the merging of groups into clusters. The algorithm is controlled by two scalar parameters, namely a distance parameter for the aggregation and another parameter controlling the minimal cluster size. Extensive experiments are conducted to give a comprehensive evaluation of the clustering performance on synthetic and real-world datasets, with various cluster shapes and low to high feature dimensionality. Our experiments demonstrate that CLASSIX competes with state-of-the-art clustering algorithms. The algorithm has linear space complexity and achieves near linear time complexity on a wide range of problems. Its inherent simplicity allows for the generation of intuitive explanations of the computed clusters.

Related papers

• Self-Supervised Graph Embedding Clustering [70.36328717683297]
  K-means one-step dimensionality reduction clustering method has made some progress in addressing the curse of dimensionality in clustering tasks. We propose a unified framework that integrates manifold learning with K-means, resulting in the self-supervised graph embedding framework.
  arXiv  Detail & Related papers  (2024-09-24T08:59:51Z)
• Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [79.46465138631592]
  We devise an efficient algorithm that recovers clusters using the observed labels. We present Instance-Adaptive Clustering (IAC), the first algorithm whose performance matches these lower bounds both in expectation and with high probability.
  arXiv  Detail & Related papers  (2023-06-18T08:46:06Z)
• Convex Clustering through MM: An Efficient Algorithm to Perform Hierarchical Clustering [1.0589208420411012]
  We propose convex clustering through majorization-minimization ( CCMM) -- an iterative algorithm that uses cluster fusions and a highly efficient updating scheme. With a current desktop computer, CCMM efficiently solves convex clustering problems featuring over one million objects in seven-dimensional space.
  arXiv  Detail & Related papers  (2022-11-03T15:07:51Z)
• Cluster Explanation via Polyhedral Descriptions [0.0]
  Clustering is an unsupervised learning problem that aims to partition unlabelled data points into groups with similar features. Traditional clustering algorithms provide limited insight into the groups they find as their main focus is accuracy and not the interpretability of the group assignments. We introduce a new approach to explain clusters by constructing polyhedra around each cluster while minimizing either the complexity of the resulting polyhedra or the number of features used in the description.
  arXiv  Detail & Related papers  (2022-10-17T07:26:44Z)
• Adaptively-weighted Integral Space for Fast Multiview Clustering [54.177846260063966]
  We propose an Adaptively-weighted Integral Space for Fast Multiview Clustering (AIMC) with nearly linear complexity. Specifically, view generation models are designed to reconstruct the view observations from the latent integral space. Experiments conducted on several realworld datasets confirm the superiority of the proposed AIMC method.
  arXiv  Detail & Related papers  (2022-08-25T05:47:39Z)
• Enhancing cluster analysis via topological manifold learning [0.3823356975862006]
  We show that inferring the topological structure of a dataset before clustering can considerably enhance cluster detection. We combine manifold learning method UMAP for inferring the topological structure with density-based clustering method DBSCAN.
  arXiv  Detail & Related papers  (2022-07-01T15:53:39Z)
• Natural Hierarchical Cluster Analysis by Nearest Neighbors with Near-Linear Time Complexity [0.0]
  We propose a nearest neighbor based clustering algorithm that results in a naturally defined hierarchy of clusters. In contrast to the agglomerative and divisive hierarchical clustering algorithms, our approach is not dependent on the iterative working of the algorithm.
  arXiv  Detail & Related papers  (2022-03-15T16:03:42Z)
• Clustering Plotted Data by Image Segmentation [12.443102864446223]
  Clustering algorithms are one of the main analytical methods to detect patterns in unlabeled data. In this paper, we present a wholly different way of clustering points in 2-dimensional space, inspired by how humans cluster data. Our approach, Visual Clustering, has several advantages over traditional clustering algorithms.
  arXiv  Detail & Related papers  (2021-10-06T06:19:30Z)
• Clustering Ensemble Meets Low-rank Tensor Approximation [50.21581880045667]
  This paper explores the problem of clustering ensemble, which aims to combine multiple base clusterings to produce better performance than that of the individual one. We propose a novel low-rank tensor approximation-based method to solve the problem from a global perspective. Experimental results over 7 benchmark data sets show that the proposed model achieves a breakthrough in clustering performance, compared with 12 state-of-the-art methods.
  arXiv  Detail & Related papers  (2020-12-16T13:01:37Z)
• 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)
• Conjoined Dirichlet Process [63.89763375457853]
  We develop a novel, non-parametric probabilistic biclustering method based on Dirichlet processes to identify biclusters with strong co-occurrence in both rows and columns. We apply our method to two different applications, text mining and gene expression analysis, and demonstrate that our method improves bicluster extraction in many settings compared to existing approaches.
  arXiv  Detail & Related papers  (2020-02-08T19:41:23Z)

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.