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
2059651397 2134089414 1998905999 2110105238 2104837959
In this paper, we show that for several clustering problems one can extract a small set of points, so that using those core-sets enable us to perform approximate clustering efficiently. The surprising property of those core-sets is that their size is independent of the dimension.Using those, we present a (1+ e)-approximation algorithms for the k-center clustering and k-median clustering problems in Euclidean space. The running time of the new algorithms has linear or near linear dependency on the number of points and the dimension, and exponential dependency on 1 e and k. As such, our results are a substantial improvement over what was previously known.We also present some other clustering results including (1+ e)-approximate 1-cylinder clustering, and k-center clustering with outliers. Clustering is traditionally viewed as an unsupervised method for data analysis. However, in some cases information about the problem domain is available in addition to the data instances themselves. In this paper, we demonstrate how the popular k-means clustering algorithm can be protably modied to make use of this information. In experiments with articial constraints on six data sets, we observe improvements in clustering accuracy. We also apply this method to the real-world problem of automatically detecting road lanes from GPS data and observe dramatic increases in performance. For a partition of an n -point set (X ) into k subsets (clusters) S 1 ,S 2 ,. . .,S k , we consider the cost function ( i=1 ^k x S_i |x-c(S_i) |^2 ) , where c(S i ) denotes the center of gravity of S i . For k=2 and for any fixed d and e >0 , we present a deterministic algorithm that finds a 2-clustering with cost no worse than (1+e) -times the minimum cost in time O(n log n); the constant of proportionality depends polynomially on e . For an arbitrary fixed k , we get an O(n log k n) algorithm for a fixed e , again with a polynomial dependence on e . We present the first linear time (1 + spl epsiv )-approximation algorithm for the k-means problem for fixed k and spl epsiv . Our algorithm runs in O(nd) time, which is linear in the size of the input. Another feature of our algorithm is its simplicity - the only technique involved is random sampling. In this paper, we present "k-means+ID3", a method to cascade k-means clustering and the ID3 decision tree learning methods for classifying anomalous and normal activities in a computer network, an active electronic circuit, and a mechanical mass-beam system. The k-means clustering method first partitions the training instances into k clusters using Euclidean distance similarity. On each cluster, representing a density region of normal or anomaly instances, we build an ID3 decision tree. The decision tree on each cluster refines the decision boundaries by learning the subgroups within the cluster. To obtain a final decision on classification, the decisions of the k-means and ID3 methods are combined using two rules: 1) the nearest-neighbor rule and 2) the nearest-consensus rule. We perform experiments on three data sets: 1) network anomaly data (NAD), 2) Duffing equation data (DED), and 3) mechanical system data (MSD), which contain measurements from three distinct application domains of computer networks, an electronic circuit implementing a forced Duffing equation, and a mechanical system, respectively. Results show that the detection accuracy of the k-means+ID3 method is as high as 96.24 percent at a false-positive-rate of 0.03 percent on NAD; the total accuracy is as high as 80.01 percent on MSD and 79.9 percent on DED