The k-means method is one of the most widely used clustering algorithms, drawing its popularity from its speed in practice. Recently, however, it was shown to have exponential worst-case running time. In order to close the gap between practical performance and theoretical analysis, the k-means method has been studied in the model of smoothed analysis. But even the smoothed analyses so far are unsatisfactory as the bounds are still super-polynomial in the number n of data points. In this paper, we settle the smoothed running time of the k-means method. We show that the smoothed number of iterations is bounded by a polynomial in n and 1 , where is the standard deviation of the Gaussian perturbations. This means that if an arbitrary input data set is randomly perturbed, then the k-means method will run in expected polynomial time on that input set.
The problem of finding good @math -means clusterings allows for polynomial-time approximation schemes @cite_4 @cite_5 @cite_12 with various dependencies of the running time on @math , @math , @math , and the approximation ratio @math . The running times of these approximation schemes depend exponentially on @math . Recent research on this subject also includes the work by @cite_17 and @cite_1 . However, the most widely used algorithm for @math -means clustering is still the @math -means method due to its simplicity and speed.
@cite_4 @cite_1 @cite_5 @cite_12 @cite_17
2018165630 2770051797 2582351091 2133311553
We consider @math -median clustering in finite metric spaces and @math -means clustering in Euclidean spaces, in the setting where @math is part of the input (not a constant). For the @math -means problem, show that if the optimal @math -means clustering of the input is more expensive than the optimal @math -means clustering by a factor of @math , then one can achieve a @math -approximation to the @math -means optimal in time polynomial in @math and @math by using a variant of Lloyd's algorithm. In this work we substantially improve this approximation guarantee. We show that given only the condition that the @math -means optimal is more expensive than the @math -means optimal by a factor @math for some constant @math , we can obtain a PTAS. In particular, under this assumption, for any @math we achieve a @math -approximation to the @math -means optimal in time polynomial in @math and @math , and exponential in @math and @math . We thus decouple the strength of the assumption from the quality of the approximation ratio. We also give a PTAS for the @math -median problem in finite metrics under the analogous assumption as well. For @math -means, we in addition give a randomized algorithm with improved running time of @math . Our technique also obtains a PTAS under the assumption of that all @math approximations are @math -close to a desired target clustering, in the case that all target clusters have size greater than @math and @math is constant. Note that the motivation of is that for many clustering problems, the objective function is only a proxy for the true goal of getting close to the target. From this perspective, our improvement is that for @math -means in Euclidean spaces we reduce the distance of the clustering found to the target from @math to @math when all target clusters are large, and for @math -median we improve the largeness'' condition needed in the work of to get exactly @math -close from @math to @math . Our results are based on a new notion of clustering stability. The @math -means clustering algorithm is a ubiquitous tool in data mining and machine learning that shows promising performance. However, its high computational cost has hindered its applications in broad domains. Researchers have successfully addressed these obstacles with dimensionality reduction methods. Recently, [1] develop a state-of-the-art random projection (RP) method for faster @math -means clustering. Their method delivers many improvements over other dimensionality reduction methods. For example, compared to the advanced singular value decomposition based feature extraction approach, [1] reduce the running time by a factor of @math for data matrix @math with @math data points and @math features, while losing only a factor of one in approximation accuracy. Unfortunately, they still require @math for matrix multiplication and this cost will be prohibitive for large values of @math and @math . To break this bottleneck, we carefully build a sparse embedded @math -means clustering algorithm which requires @math ( @math denotes the number of non-zeros in @math ) for fast matrix multiplication. Moreover, our proposed algorithm improves on [1]'s results for approximation accuracy by a factor of one. Our empirical studies corroborate our theoretical findings, and demonstrate that our approach is able to significantly accelerate @math -means clustering, while achieving satisfactory clustering performance. The @math -Means clustering problem on @math points is NP-Hard for any dimension @math , however, for the 1D case there exists exact polynomial time algorithms. Previous literature reported an @math time dynamic programming algorithm that uses @math space. It turns out that the problem has been considered under a different name more than twenty years ago. We present all the existing work that had been overlooked and compare the various solutions theoretically. Moreover, we show how to reduce the space usage for some of them, as well as generalize them to data structures that can quickly report an optimal @math -Means clustering for any @math . Finally we also generalize all the algorithms to work for the absolute distance and to work for any Bregman Divergence. We complement our theoretical contributions by experiments that compare the practical performance of the various algorithms. In a clustering problem, the aim is to partition a given set of n points in d -dimensional space into k groups, called clusters, so that points within each cluster are near each other. Two objective functions frequently used to measure the performance of a clustering algorithm are, for any L 4 metric, (a) the maximum distance between pairs of points in the same cluster, and (b) the maximum distance between points in each cluster and a chosen cluster center; we refer to either measure as the cluster size. We show that one cannot approximate the optimal cluster size for a fixed number of clusters within a factor close to 2 in polynomial time, for two or more dimensions, unless P=NP. We also present an algorithm that achieves this factor of 2 in time O ( n log k ), and show that this running time is optimal in the algebraic decision tree model. For a fixed cluster size, on the other hand, we give a polynomial time approximation scheme that estimates the optimal number of clusters under the second measure of cluster size within factors arbitrarily close to 1. Our approach is extended to provide approximation algorithms for the restricted centers, suppliers, and weighted suppliers problems that run in optimal O ( n log k ) time and achieve optimal or nearly optimal approximation bounds.