The k-means++ seeding algorithm is one of the most popular algorithms that is used for finding the initial @math centers when using the k-means heuristic. The algorithm is a simple sampling procedure and can be described as follows: Pick the first center randomly from the given points. For @math , pick a point to be the @math center with probability proportional to the square of the Euclidean distance of this point to the closest previously @math chosen centers. The k-means++ seeding algorithm is not only simple and fast but also gives an @math approximation in expectation as shown by Arthur and Vassilvitskii. There are datasets on which this seeding algorithm gives an approximation factor of @math in expectation. However, it is not clear from these results if the algorithm achieves good approximation factor with reasonably high probability (say @math ). Brunsch and Roglin gave a dataset where the k-means++ seeding algorithm achieves an @math approximation ratio with probability that is exponentially small in @math . However, this and all other known lower-bound examples are high dimensional. So, an open problem was to understand the behavior of the algorithm on low dimensional datasets. In this work, we give a simple two dimensional dataset on which the seeding algorithm achieves an @math approximation ratio with probability exponentially small in @math . This solves open problems posed by and by Brunsch and Roglin.
Arthur and Vassilvitskii @cite_10 showed that the sampling algorithm gives an approximation guarantee of @math in expectation. They also give an example dataset on which this approximation guarantee is best possible. Ailon al @cite_12 and Aggarwal al @cite_2 showed that sampling more than @math centers in the manner described above gives a constant pseudo-approximation . Here pseudo-approximation means that the algorithm is allowed to output more than @math centers but the approximation factor is computed by comparing with the optimal solution with @math centers. Ackermann and Bl " o mer @cite_1 showed that the results of Arthur and Vassilvitskii @cite_10 may be extended to a large class of other distance measures. Jaiswal al @cite_7 showed that the seeding algorithm may be appropriately modified to give a @math -approximation algorithm for the k-means problem. Jaiswal and Garg @cite_6 and Agarwal al @cite_3 showed that if the dataset satisfies certain separation conditions, then the seeding algorithm gives constant approximation with probability @math . Bahmani al @cite_5 showed that the seeding algorithm performs well even when fewer than @math sampling iterations are executed provided that more than one center is chosen in a sampling iteration. We now discuss our main results.
@cite_7 @cite_1 @cite_6 @cite_3 @cite_2 @cite_5 @cite_10 @cite_12
2154200889 1561129100 130123586 2204035083 1530581016 2073459066 2156499390
Given a set of points @math , the k-means clustering problem is to find a set of k centers @math , such that the objective function ? x?P e(x,C)2, where e(x,C) denotes the Euclidean distance between x and the closest center in C, is minimized. This is one of the most prominent objective functions that has been studied with respect to clustering. D 2-sampling (Arthur and Vassilvitskii, Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA'07, pp. 1027---1035, SIAM, Philadelphia, 2007) is a simple non-uniform sampling technique for choosing points from a set of points. It works as follows: given a set of points @math , the first point is chosen uniformly at random from P. Subsequently, a point from P is chosen as the next sample with probability proportional to the square of the distance of this point to the nearest previously sampled point. D 2-sampling has been shown to have nice properties with respect to the k-means clustering problem. Arthur and Vassilvitskii (Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA'07, pp. 1027---1035, SIAM, Philadelphia, 2007) show that k points chosen as centers from P using D 2-sampling give an O(logk) approximation in expectation. (NIPS, pp. 10---18, 2009) and (Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pp. 15---28, Springer, Berlin, 2009) extended results of Arthur and Vassilvitskii (Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA'07, pp. 1027---1035, SIAM, Philadelphia, 2007) to show that O(k) points chosen as centers using D 2-sampling give an O(1) approximation to the k-means objective function with high probability. In this paper, we further demonstrate the power of D 2-sampling by giving a simple randomized (1+∈)-approximation algorithm that uses the D 2-sampling in its core. The Bregman k-median problem is defined as follows. Given a Bregman divergence Dφ and a finite set @math of size n, our goal is to find a set C of size k such that the sum of errors cost(P,C)=∑p∈P min c∈C Dφ(p,c) is minimized. The Bregman k-median problem plays an important role in many applications, e.g., information theory, statistics, text classification, and speech processing. We study a generalization of the kmeans++ seeding of Arthur and Vassilvitskii (SODA '07). We prove for an almost arbitrary Bregman divergence that if the input set consists of k well separated clusters, then with probability @math this seeding step alone finds an @math -approximate solution. Thereby, we generalize an earlier result of (FOCS '06) from the case of the Euclidean k-means problem to the Bregman k-median problem. Additionally, this result leads to a constant factor approximation algorithm for the Bregman k-median problem using at most @math arithmetic operations, including evaluations of Bregman divergence Dφ. k-means++ [5] seeding procedure is a simple sampling based algorithm that is used to quickly find k centers which may then be used to start the Lloyd’s method. There has been some progress recently on understanding this sampling algorithm. [10] showed that if the data satisfies the separation condition that ( k-1 (P) (P) c ) (Δ i (P) is the optimal cost w.r.t. i centers, c > 1 is a constant, and P is the point set), then the sampling algorithm gives an O(1)-approximation for the k-means problem with probability that is exponentially small in k. Here, the distance measure is the squared Euclidean distance. Ackermann and Blomer [2] showed the same result when the distance measure is any μ-similar Bregman divergence. Arthur and Vassilvitskii [5] showed that the k-means++ seeding gives an O(logk) approximation in expectation for the k-means problem. They also give an instance where k-means++ seeding gives Ω(logk) approximation in expectation. However, it was unresolved whether the seeding procedure gives an O(1) approximation with probability ( ( 1 poly(k) ) ), even when the data satisfies the above-mentioned separation condition. Brunsch and Roglin [8] addressed this question and gave an instances on which k-means++ achieves an approximation ratio of (2 3 − e) ·logk only with exponentially small probability. However, the instances that they give satisfy ( k-1 (P) (P) = 1+o(1) ). In this work, we show that the sampling algorithm gives an O(1) approximation with probability ( ( 1 k ) ) for any k-means problem instance where the point set satisfy separation condition ( k-1 (P) (P) 1 + ), for some fixed constant γ. Our results hold for any distance measure that is a metric in an approximate sense. For point sets that do not satisfy the above separation condition, we show O(1) approximation with probability Ω(2− 2k ). The Lloyd’s algorithm, also known as the k-means algorithm, is one of the most popular algorithms for solving the k-means clustering problem in practice. However, it does not give any performance guarantees. This means that there are datasets on which this algorithm can behave very badly. One reason for poor performance on certain datasets is bad initialization. The following simple sampling based seeding algorithm tends to fix this problem: pick the first center randomly from among the given points and then for i ≥ 2, pick a point to be the i th center with probability proportional to the squared distance of this point from the previously chosen centers. This algorithm is more popularly known as the k-means++ seeding algorithm and is known to exhibit some nice properties. These have been studied in a number of previous works [AV07, AJM09, ADK09, BR11]. The algorithm tends to perform well when the optimal clusters are separated in some sense. This is because the algorithm gives preference to further away points when picking centers. [ORSS06] discuss one such separation condition on the data. Jaiswal and Garg [JG12] show that if the dataset satisfies the separation condition of [ORSS06], then the sampling algorithm gives a constant approximation with probability Ω(1 k). Another separation condition that is strictly weaker than [ORSS06] is the approximation stability condition discussed by [BBG09]. In this work, we show that the sampling algorithm gives a constant approximation with probability Ω(1 k) if the dataset satisfies the separation condition of [BBG09] and the optimal clusters are not too small. We give a negative result for datasets that have small optimal clusters. We show that adaptively sampled O (k ) centers give a constant factor bi-criteria approximation for the k -means problem, with a constant probability. Moreover, these O (k ) centers contain a subset of k centers which give a constant factor approximation, and can be found using LP-based techniques of Jain and Vazirani [JV01] and [CGTS02]. Both these algorithms run in effectively O (nkd ) time and extend the O (logk )-approximation achieved by the k -means++ algorithm of Arthur and Vassilvitskii [AV07]. The k-means method is a widely used clustering technique that seeks to minimize the average squared distance between points in the same cluster. Although it offers no accuracy guarantees, its simplicity and speed are very appealing in practice. By augmenting k-means with a very simple, randomized seeding technique, we obtain an algorithm that is Θ(logk)-competitive with the optimal clustering. Preliminary experiments show that our augmentation improves both the speed and the accuracy of k-means, often quite dramatically. We provide a clustering algorithm that approximately optimizes the k-means objective, in the one-pass streaming setting. We make no assumptions about the data, and our algorithm is very light-weight in terms of memory, and computation. This setting is applicable to unsupervised learning on massive data sets, or resource-constrained devices. The two main ingredients of our theoretical work are: a derivation of an extremely simple pseudo-approximation batch algorithm for k-means (based on the recent k-means++), in which the algorithm is allowed to output more than k centers, and a streaming clustering algorithm in which batch clustering algorithms are performed on small inputs (fitting in memory) and combined in a hierarchical manner. Empirical evaluations on real and simulated data reveal the practical utility of our method.