Fast Distributed k-Means with a Small Number of Rounds
- URL: http://arxiv.org/abs/2201.13217v1
- Date: Mon, 31 Jan 2022 13:27:10 GMT
- Title: Fast Distributed k-Means with a Small Number of Rounds
- Authors: Tom Hess, Ron Visbord, Sivan Sabato
- Abstract summary: We propose a new algorithm for k-means clustering in a distributed setting, where the data is distributed across many machines.
Our algorithm guarantees a cost approximation factor and a number of communication rounds that depend only on the computational capacity of the coordinator.
- Score: 19.495806969497583
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We propose a new algorithm for k-means clustering in a distributed setting,
where the data is distributed across many machines, and a coordinator
communicates with these machines to calculate the output clustering. Our
algorithm guarantees a cost approximation factor and a number of communication
rounds that depend only on the computational capacity of the coordinator.
Moreover, the algorithm includes a built-in stopping mechanism, which allows it
to use fewer communication rounds whenever possible. We show both theoretically
and empirically that in many natural cases, indeed 1-4 rounds suffice. In
comparison with the popular k-means|| algorithm, our approach allows exploiting
a larger coordinator capacity to obtain a smaller number of rounds. Our
experiments show that the k-means cost obtained by the proposed algorithm is
usually better than the cost obtained by k-means||, even when the latter is
allowed a larger number of rounds. Moreover, the machine running time in our
approach is considerably smaller than that of k-means||. Code for running the
algorithm and experiments is available at
https://github.com/selotape/distributed_k_means.
Related papers
- A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
We present a scalable algorithm for the individually fair ($p$, $k$)-clustering problem introduced by Jung et al. and Mahabadi et al.
A clustering is then called individually fair if it has centers within distance $delta(x)$ of $x$ for each $xin P$.
We show empirically that not only is our algorithm much faster than prior work, but it also produces lower-cost solutions.
arXiv Detail & Related papers (2024-02-09T19:01:48Z) - Fast Optimal Locally Private Mean Estimation via Random Projections [58.603579803010796]
We study the problem of locally private mean estimation of high-dimensional vectors in the Euclidean ball.
We propose a new algorithmic framework, ProjUnit, for private mean estimation.
Our framework is deceptively simple: each randomizer projects its input to a random low-dimensional subspace, normalizes the result, and then runs an optimal algorithm.
arXiv Detail & Related papers (2023-06-07T14:07:35Z) - 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) - Using MM principles to deal with incomplete data in K-means clustering [0.0]
K-means clustering algorithm is widely used because of its simple algorithm and fast convergence.
We mainly apply MM principles to restore the symmetry of the data, so that K-means could work well.
arXiv Detail & Related papers (2022-12-23T14:50:57Z) - An enhanced method of initial cluster center selection for K-means
algorithm [0.0]
We propose a novel approach to improve initial cluster selection for K-means algorithm.
The Convex Hull algorithm facilitates the computing of the first two centroids and the remaining ones are selected according to the distance from previously selected centers.
We obtained only 7.33%, 7.90%, and 0% clustering error in Iris, Letter, and Ruspini data respectively.
arXiv Detail & Related papers (2022-10-18T00:58:50Z) - Communication-Efficient Adam-Type Algorithms for Distributed Data Mining [93.50424502011626]
We propose a class of novel distributed Adam-type algorithms (emphi.e., SketchedAMSGrad) utilizing sketching.
Our new algorithm achieves a fast convergence rate of $O(frac1sqrtnT + frac1(k/d)2 T)$ with the communication cost of $O(k log(d))$ at each iteration.
arXiv Detail & Related papers (2022-10-14T01:42:05Z) - 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) - List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
We study the fundamental task of list-decodable mean estimation in high dimensions.
Our algorithm runs in time $widetildeO(ndk)$ for all $k = O(sqrtd) cup Omega(d)$, where $n$ is the size of the dataset.
A variant of our algorithm has runtime $widetildeO(ndk)$ for all $k$, at the expense of an $O(sqrtlog k)$ factor in the recovery guarantee
arXiv Detail & Related papers (2020-11-19T17:21:37Z) - 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) - Relational Algorithms for k-means Clustering [17.552485682328772]
This paper gives a k-means approximation algorithm that is efficient in the relational algorithms model.
The running time is potentially exponentially smaller than $N$, the number of data points to be clustered that the relational database represents.
arXiv Detail & Related papers (2020-08-01T23:21:40Z)
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.