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
130123586 2154200889 2204035083 2089135543
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 ). 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 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 give efficient algorithms for volume sampling, i.e., for picking @math -subsets of the rows of any given matrix with probabilities proportional to the squared volumes of the simplices defined by them and the origin (or the squared volumes of the parallelepipeds defined by these subsets of rows). In other words, we can efficiently sample @math -subsets of @math with probabilities proportional to the corresponding @math by @math principal minors of any given @math by @math positive semi definite matrix. This solves an open problem from the monograph on spectral algorithms by Kannan and Vempala (see Section @math of KV , also implicit in BDM, DRVW ). Our first algorithm for volume sampling @math -subsets of rows from an @math -by- @math matrix runs in @math arithmetic operations (where @math is the exponent of matrix multiplication) and a second variant of it for @math -approximate volume sampling runs in @math arithmetic operations, which is almost linear in the size of the input (i.e., the number of entries) for small @math . Our efficient volume sampling algorithms imply the following results for low-rank matrix approximation: (1) Given @math , in @math arithmetic operations we can find @math of its rows such that projecting onto their span gives a @math -approximation to the matrix of rank @math closest to @math under the Frobenius norm. This improves the @math -approximation of Boutsidis, Drineas and Mahoney BDM and matches the lower bound shown in DRVW . The method of conditional expectations gives a algorithm with the same complexity. The running time can be improved to @math at the cost of losing an extra @math in the approximation factor. (2) The same rows and projection as in the previous point give a @math -approximation to the matrix of rank @math closest to @math under the spectral norm. In this paper, we show an almost matching lower bound of @math , even for @math .