Tree-Guided $L_1$-Convex Clustering

• URL: http://arxiv.org/abs/2503.24012v1
• Date: Mon, 31 Mar 2025 12:39:48 GMT
• Title: Tree-Guided $L_1$-Convex Clustering
• Authors: Bingyuan Zhang, Yoshikazu Terada,
• Abstract summary: We develop a novel convex clustering algorithm called Tree-Guided- Clustering.<n>We develop an efficient cluster fusion algorithm that utilizes the tree of the weights to accelerate the optimization process.<n>Remarkably, our TGCC algorithm can construct a complete dengram in $mathbbR2 seconds on a laptop standard.
• Score: 1.0589208420411012
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Convex clustering is a modern clustering framework that guarantees globally optimal solutions and performs comparably to other advanced clustering methods. However, obtaining a complete dendrogram (clusterpath) for large-scale datasets remains computationally challenging due to the extensive costs associated with iterative optimization approaches. To address this limitation, we develop a novel convex clustering algorithm called Tree-Guided $L_1$-Convex Clustering (TGCC). We first focus on the fact that the loss function of $L_1$-convex clustering with tree-structured weights can be efficiently optimized using a dynamic programming approach. We then develop an efficient cluster fusion algorithm that utilizes the tree structure of the weights to accelerate the optimization process and eliminate the issue of cluster splits commonly observed in convex clustering. By combining the dynamic programming approach with the cluster fusion algorithm, the TGCC algorithm achieves superior computational efficiency without sacrificing clustering performance. Remarkably, our TGCC algorithm can construct a complete clusterpath for $10^6$ points in $\mathbb{R}^2$ within 15 seconds on a standard laptop without the need for parallel or distributed computing frameworks. Moreover, we extend the TGCC algorithm to develop biclustering and sparse convex clustering algorithms.

Related papers

• Graph Probability Aggregation Clustering [5.377020739388736]
  We propose a graph-based fuzzy clustering algorithm that unifies the global clustering objective function with a local clustering constraint.<n>The entire GPAC framework is formulated as a multi-constrained optimization problem, which can be solved using the Lagrangian method.<n>Experiments conducted on synthetic, real-world, and deep learning datasets demonstrate that GPAC not only exceeds existing state-of-the-art methods in clustering performance but also excels in computational efficiency.
  arXiv  Detail & Related papers  (2025-02-27T09:11:32Z)
• A Greedy Strategy for Graph Cut [95.2841574410968]
  We propose a greedy strategy to solve the problem of Graph Cut, called GGC.<n>It starts from the state where each data sample is regarded as a cluster and dynamically merges the two clusters.<n>GGC has a nearly linear computational complexity with respect to the number of samples.
  arXiv  Detail & Related papers  (2024-12-28T05:49:42Z)
• GBCT: An Efficient and Adaptive Granular-Ball Clustering Algorithm for Complex Data [49.56145012222276]
  We propose a new clustering algorithm called granular-ball clustering (GBCT) via granular-ball computing. GBCT forms clusters according to the relationship between granular-balls, instead of the traditional point relationship. As granular-balls can fit various complex data, GBCT performs much better in non-spherical data sets than other traditional clustering methods.
  arXiv  Detail & Related papers  (2024-10-17T07:32:05Z)
• Reinforcement Graph Clustering with Unknown Cluster Number [91.4861135742095]
  We propose a new deep graph clustering method termed Reinforcement Graph Clustering. In our proposed method, cluster number determination and unsupervised representation learning are unified into a uniform framework. In order to conduct feedback actions, the clustering-oriented reward function is proposed to enhance the cohesion of the same clusters and separate the different clusters.
  arXiv  Detail & Related papers  (2023-08-13T18:12:28Z)
• Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [69.15976031704687]
  We propose IAC (Instance-Adaptive Clustering), the first algorithm whose performance matches the instance-specific lower bounds both in expectation and with high probability.<n>IAC maintains an overall computational complexity of $ mathcalO(n, textpolylog(n) $, making it scalable and practical for large-scale problems.
  arXiv  Detail & Related papers  (2023-06-18T08:46:06Z)
• Hybrid Fuzzy-Crisp Clustering Algorithm: Theory and Experiments [0.0]
  We propose a hybrid fuzzy-crisp clustering algorithm based on a target function combining linear and quadratic terms of the membership function. In this algorithm, the membership of a data point to a cluster is automatically set to exactly zero if the data point is sufficiently'' far from the cluster center. The proposed algorithm is demonstrated to outperform the conventional methods on imbalanced datasets and can be competitive on more balanced datasets.
  arXiv  Detail & Related papers  (2023-03-25T05:27:26Z)
• 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)
• ParChain: A Framework for Parallel Hierarchical Agglomerative Clustering using Nearest-Neighbor Chain [6.824747267214373]
  We propose the ParChain framework for designing parallel hierarchical agglomerative clustering (HAC) algorithms. Compared to most previous parallel HAC algorithms, our new algorithms require only linear memory, and are scalable to large data sets. Our algorithms are able to scale to data set sizes with tens of millions of points, which existing algorithms are not able to handle.
  arXiv  Detail & Related papers  (2021-06-08T23:13:27Z)
• 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)
• 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)
• An Efficient Smoothing Proximal Gradient Algorithm for Convex Clustering [2.5182813818441945]
  Recently introduced convex clustering approach formulates clustering as a convex optimization problem. State-of-the-art convex clustering algorithms require large computation and memory space. In this paper, we develop a very efficient smoothing gradient algorithm (Sproga) for convex clustering.
  arXiv  Detail & Related papers  (2020-06-22T20:02:59Z)

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.