Sketch-and-solve approaches to k-means clustering by semidefinite programming

• URL: http://arxiv.org/abs/2211.15744v1
• Date: Mon, 28 Nov 2022 19:51:30 GMT
• Title: Sketch-and-solve approaches to k-means clustering by semidefinite programming
• Authors: Charles Clum, Dustin G. Mixon, Soledad Villar, Kaiying Xie
• Abstract summary: We introduce a sketch-and-solve approach to speed up the Peng-Wei semidefinite relaxation of k-means clustering. If the data is appropriately separated we identify the k-means optimal clustering. Otherwise, our approach provides a high-confidence lower bound on the optimal k-means value.
• Score: 14.930208990741132
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We introduce a sketch-and-solve approach to speed up the Peng-Wei semidefinite relaxation of k-means clustering. When the data is appropriately separated we identify the k-means optimal clustering. Otherwise, our approach provides a high-confidence lower bound on the optimal k-means value. This lower bound is data-driven; it does not make any assumption on the data nor how it is generated. We provide code and an extensive set of numerical experiments where we use this approach to certify approximate optimality of clustering solutions obtained by k-means++.

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)
• Rethinking k-means from manifold learning perspective [122.38667613245151]
  We present a new clustering algorithm which directly detects clusters of data without mean estimation. Specifically, we construct distance matrix between data points by Butterworth filter. To well exploit the complementary information embedded in different views, we leverage the tensor Schatten p-norm regularization.
  arXiv  Detail & Related papers  (2023-05-12T03:01:41Z)
• A One-shot Framework for Distributed Clustered Learning in Heterogeneous Environments [54.172993875654015]
  The paper proposes a family of communication efficient methods for distributed learning in heterogeneous environments. One-shot approach, based on local computations at the users and a clustering based aggregation step at the server is shown to provide strong learning guarantees. For strongly convex problems it is shown that, as long as the number of data points per user is above a threshold, the proposed approach achieves order-optimal mean-squared error rates in terms of the sample size.
  arXiv  Detail & Related papers  (2022-09-22T09:04:10Z)
• A sampling-based approach for efficient clustering in large datasets [0.8952229340927184]
  We propose a simple and efficient clustering method for high-dimensional data with a large number of clusters. Our contribution is substantially more efficient than k-means as it does not require an all to all comparison of data points and clusters.
  arXiv  Detail & Related papers  (2021-12-29T19:15:20Z)
• K-Splits: Improved K-Means Clustering Algorithm to Automatically Detect the Number of Clusters [0.12313056815753944]
  This paper introduces k-splits, an improved hierarchical algorithm based on k-means to cluster data without prior knowledge of the number of clusters. Accuracy and speed are two main advantages of the proposed method.
  arXiv  Detail & Related papers  (2021-10-09T23:02:57Z)
• Robust Trimmed k-means [70.88503833248159]
  We propose Robust Trimmed k-means (RTKM) that simultaneously identifies outliers and clusters points. We show RTKM performs competitively with other methods on single membership data with outliers and multi-membership data without outliers.
  arXiv  Detail & Related papers  (2021-08-16T15:49:40Z)
• Determinantal consensus clustering [77.34726150561087]
  We propose the use of determinantal point processes or DPP for the random restart of clustering algorithms. DPPs favor diversity of the center points within subsets. We show through simulations that, contrary to DPP, this technique fails both to ensure diversity, and to obtain a good coverage of all data facets.
  arXiv  Detail & Related papers  (2021-02-07T23:48:24Z)
• 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)
• Too Much Information Kills Information: A Clustering Perspective [6.375668163098171]
  We propose a simple, but novel approach for variance-based k-clustering tasks, including in which is the widely known k-means clustering. The proposed approach picks a sampling subset from the given dataset and makes decisions based on the data information in the subset only. With certain assumptions, the resulting clustering is provably good to estimate the optimum of the variance-based objective with high probability.
  arXiv  Detail & Related papers  (2020-09-16T01:54:26Z)
• K-bMOM: a robust Lloyd-type clustering algorithm based on bootstrap Median-of-Means [3.222802562733787]
  We propose a new clustering algorithm that is robust to the presence of outliers in the dataset. We build on the idea of median-of-means statistics to estimate the centroids, but allow for replacement while constructing the blocks. We prove its robustness to adversarial contamination by deriving robust rates of convergence for the K-means distorsion.
  arXiv  Detail & Related papers  (2020-02-10T16:08:08Z)

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.