Asymptotics for The $k$-means

• URL: http://arxiv.org/abs/2211.10015v1
• Date: Fri, 18 Nov 2022 03:36:58 GMT
• Title: Asymptotics for The $k$-means
• Authors: Tonglin Zhang
• Abstract summary: The $k$-means is one of the most important unsupervised learning techniques in statistics and computer science. The proposed clustering consistency is more appropriate than the previous criterion consistency for the clustering methods. It is found that the proposed $k$-means method has lower clustering error rates and is more robust to small clusters and outliers.
• Score: 0.6091702876917281
• License: http://creativecommons.org/publicdomain/zero/1.0/
• Abstract: The $k$-means is one of the most important unsupervised learning techniques in statistics and computer science. The goal is to partition a data set into many clusters, such that observations within clusters are the most homogeneous and observations between clusters are the most heterogeneous. Although it is well known, the investigation of the asymptotic properties is far behind, leading to difficulties in developing more precise $k$-means methods in practice. To address this issue, a new concept called clustering consistency is proposed. Fundamentally, the proposed clustering consistency is more appropriate than the previous criterion consistency for the clustering methods. Using this concept, a new $k$-means method is proposed. It is found that the proposed $k$-means method has lower clustering error rates and is more robust to small clusters and outliers than existing $k$-means methods. When $k$ is unknown, using the Gap statistics, the proposed method can also identify the number of clusters. This is rarely achieved by existing $k$-means methods adopted by many software packages.

Related papers

• Are Easy Data Easy (for K-Means) [0.0]
  This paper investigates the capability of correctly recovering well-separated clusters by various brands of the $k$-means algorithm. A new algorithm is proposed that is a variation of $k$-means++ via repeated subsampling when choosing a seed.
  arXiv  Detail & Related papers  (2023-08-02T09:40:19Z)
• 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)
• Global $k$-means$++$: an effective relaxation of the global $k$-means clustering algorithm [0.20305676256390928]
  The $k$-means algorithm is a prevalent clustering method due to its simplicity, effectiveness, and speed. We propose the emphglobal $k$-meanstexttt++ clustering algorithm, which is an effective way of acquiring quality clustering solutions.
  arXiv  Detail & Related papers  (2022-11-22T13:42:53Z)
• 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)
• Differentially-Private Clustering of Easy Instances [67.04951703461657]
  In differentially private clustering, the goal is to identify $k$ cluster centers without disclosing information on individual data points. We provide implementable differentially private clustering algorithms that provide utility when the data is "easy" We propose a framework that allows us to apply non-private clustering algorithms to the easy instances and privately combine the results.
  arXiv  Detail & Related papers  (2021-12-29T08:13:56Z)
• Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
  Clustering is a fundamental primitive in unsupervised learning. Recent work has established lower bounds against the class of low-degree methods. We show that, perhaps surprisingly, this particular clustering model textitdoes not exhibit a statistical-to-computational gap.
  arXiv  Detail & Related papers  (2021-12-07T18:50:17Z)
• Distribution free optimality intervals for clustering [1.7513645771137178]
  Given data $mathcalD$ and a partition $mathcalC$ of these data into $K$ clusters, when can we say that the clusters obtained are correct or meaningful for the data? This paper introduces a paradigm in which a clustering $mathcalC$ is considered meaningful if it is good with respect to a loss function such as the K-means distortion, and stable, i.e. the only good clustering up to small perturbations.
  arXiv  Detail & Related papers  (2021-07-30T06:13:56Z)
• Fuzzy Clustering with Similarity Queries [56.96625809888241]
  The fuzzy or soft objective is a popular generalization of the well-known $k$-means problem. We show that by making few queries, the problem becomes easier to solve.
  arXiv  Detail & Related papers  (2021-06-04T02:32:26Z)
• K-expectiles clustering [0.0]
  We propose a novel partitioning clustering algorithm based on expectiles. We suggest two schemes: fixed $tau$ clustering, and adaptive $tau$ clustering.
  arXiv  Detail & Related papers  (2021-03-16T21:14:56Z)
• 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)
• Structures of Spurious Local Minima in $k$-means [20.155509538529568]
  We investigate the structures of spurious local solutions to the $k$-means problem. We prove that this is essentially the only type of spurious local minima under a separation condition.
  arXiv  Detail & Related papers  (2020-02-16T22:15:03Z)

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.