Average Sensitivity of Hierarchical $k$-Median Clustering

• URL: http://arxiv.org/abs/2507.10296v1
• Date: Mon, 14 Jul 2025 14:02:31 GMT
• Title: Average Sensitivity of Hierarchical $k$-Median Clustering
• Authors: Shijie Li, Weiqiang He, Ruobing Bai, Pan Peng,
• Abstract summary: We focus on the hierarchical $k$ -median clustering problem, which bridges hierarchical and centroid-based clustering.<n>We propose an efficient algorithm for hierarchical $k$-median clustering and theoretically prove its low average sensitivity and high clustering quality.
• Score: 9.107341310040155
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Hierarchical clustering is a widely used method for unsupervised learning with numerous applications. However, in the application of modern algorithms, the datasets studied are usually large and dynamic. If the hierarchical clustering is sensitive to small perturbations of the dataset, the usability of the algorithm will be greatly reduced. In this paper, we focus on the hierarchical $k$ -median clustering problem, which bridges hierarchical and centroid-based clustering while offering theoretical appeal, practical utility, and improved interpretability. We analyze the average sensitivity of algorithms for this problem by measuring the expected change in the output when a random data point is deleted. We propose an efficient algorithm for hierarchical $k$-median clustering and theoretically prove its low average sensitivity and high clustering quality. Additionally, we show that single linkage clustering and a deterministic variant of the CLNSS algorithm exhibit high average sensitivity, making them less stable. Finally, we validate the robustness and effectiveness of our algorithm through experiments.

Related papers

• Accelerating Spectral Clustering under Fairness Constraints [56.865810822418744]
  We present a new efficient method for fair spectral clustering (Fair SC) by casting the Fair SC problem within the difference of convex functions (DC) framework.<n>We show that each associated subproblem can be solved efficiently, resulting in higher computational efficiency compared to prior work.
  arXiv  Detail & Related papers  (2025-06-09T18:46:27Z)
• K*-Means: A Parameter-free Clustering Algorithm [55.20132267309382]
  k*-means is a novel clustering algorithm that eliminates the need to set k or any other parameters.<n>It uses the minimum description length principle to automatically determine the optimal number of clusters, k*, by splitting and merging clusters.<n>We prove that k*-means is guaranteed to converge and demonstrate experimentally that it significantly outperforms existing methods in scenarios where k is unknown.
  arXiv  Detail & Related papers  (2025-05-17T08:41:07Z)
• 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)
• Fuzzy K-Means Clustering without Cluster Centroids [21.256564324236333]
  Fuzzy K-Means clustering is a critical technique in unsupervised data analysis. This paper proposes a novel Fuzzy textitK-Means clustering algorithm that entirely eliminates the reliance on cluster centroids.
  arXiv  Detail & Related papers  (2024-04-07T12:25:03Z)
• 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)
• Envelope Imbalance Learning Algorithm based on Multilayer Fuzzy C-means Clustering and Minimum Interlayer discrepancy [14.339674126923903]
  This paper proposes a deep instance envelope network-based imbalanced learning algorithm with the multilayer fuzzy c-means (MlFCM) and a minimum interlayer discrepancy mechanism based on the maximum mean discrepancy (MIDMD) This algorithm can guarantee high quality balanced instances using a deep instance envelope network in the absence of prior knowledge.
  arXiv  Detail & Related papers  (2021-11-02T04:59:57Z)
• Unsupervised Clustered Federated Learning in Complex Multi-source Acoustic Environments [75.8001929811943]
  We introduce a realistic and challenging, multi-source and multi-room acoustic environment. We present an improved clustering control strategy that takes into account the variability of the acoustic scene. The proposed approach is optimized using clustering-based measures and validated via a network-wide classification task.
  arXiv  Detail & Related papers  (2021-06-07T14:51:39Z)
• DAC: Deep Autoencoder-based Clustering, a General Deep Learning Framework of Representation Learning [0.0]
  We propose DAC, Deep Autoencoder-based Clustering, a data-driven framework to learn clustering representations using deep neuron networks. Experiment results show that our approach could effectively boost performance of the KMeans clustering algorithm on a variety of datasets.
  arXiv  Detail & Related papers  (2021-02-15T11:31:00Z)
• 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)
• Differentially Private Clustering: Tight Approximation Ratios [57.89473217052714]
  We give efficient differentially private algorithms for basic clustering problems. Our results imply an improved algorithm for the Sample and Aggregate privacy framework. One of the tools used in our 1-Cluster algorithm can be employed to get a faster quantum algorithm for ClosestPair in a moderate number of dimensions.
  arXiv  Detail & Related papers  (2020-08-18T16:22:06Z)
• Simple and Scalable Sparse k-means Clustering via Feature Ranking [14.839931533868176]
  We propose a novel framework for sparse k-means clustering that is intuitive, simple to implement, and competitive with state-of-the-art algorithms. Our core method readily generalizes to several task-specific algorithms such as clustering on subsets of attributes and in partially observed data settings.
  arXiv  Detail & Related papers  (2020-02-20T02:41:02Z)

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.