Faster K-Means Cluster Estimation Siddhesh Khandelwal, Amit Awekar Indian Instituteof Technology Guwahati [email protected], [email protected] Abstract. Therehasbeenconsiderableworkonimprovingpopularclus- tering algorithm ‘K-means’ in terms of mean squared error (MSE) and 7 speed,both.However,mostofthek-meansvariantstendtocomputedis- 1 tance of each datapoint toeach cluster centroid for everyiteration. We 0 propose a fast heuristic to overcome this bottleneck with only marginal 2 increase in MSE. We observe that across all iterations of K-means, a n data point changes its membership only among a small subset of clus- a ters. Our heuristic predicts such clusters for each data point by looking J at nearby clusters after the first iteration of k-means. We augment well 7 known variants of k-means with our heuristic to demonstrate effective- 1 ness of our heuristic. For various synthetic and real-world datasets, our heuristic achieves speed-up of up-to 3 times when compared to efficient ] variants of k-means. G L Keywords: K-means,Clustering, Heuristic . s c [ 1 Introduction 1 K-means is a popular clustering technique that is used in diverse fields such v 0 as humanities, bio-informatics, and astronomy. Given a dataset D with n data 0 points in Rd space, K-means partitions D into k clusters with the objective to 6 minimize the mean squared error (MSE). MSE is defined as the sum of the 4 squared distance of each point from its corresponding centroid. The K-means 0 problemisNP-hard.Polynomialtimeheuristicsarecommonlyappliedtoobtain . 1 a local minimum. 0 One such popular heuristic is the Lloyd’s algorithm[6] that selects certain 7 initial centroids (also referred as seeds) at random from the dataset. Each data 1 : point is assigned to the cluster corresponding to the closest centroid. Each cen- v troid is then recomputed as mean of the points assigned to that cluster. This i X procedure is repeated until convergence. Each iteration involves n∗k distance r computations.Ourcontributionistoreducethiscostton∗k′,(k′ <<k)bygen- a ′ erating candidate cluster list (CCL) of size k for eachdata point. The heuristic is based on the observation that across all iterations of K-means, a data point changes its membership only among a small subset of clusters. Our heuristic considersonly a subsetof nearbycluster as candidatesfor deciding membership for a data point. This heuristic has advantage of speeding up K-means cluster- ing with marginal increase in MSE. We show effectiveness of our heuristic by extensive experimentation using various synthetic and real-worlddatasets. 2 Siddhesh Khandelwal, Amit Awekar 2 Our Work: Candidate cluster list for each data point Ourmaincontributionisindefiningaheuristicthatcanbeusedasaugmentation to current variants of k-means for faster cluster estimation. Let algorithm V be ′ a variantof k-means andalgorithmV be the same variantaugmentedwith our heuristic. Let T be the time required for V to converge to MSE value of E. ′ ′ ′ Similarly, T is the time required for V to converge to MSE value of E . We ′ should satisfy following two conditions when we compare V with V : – Condition 1: T′ is lower than T, and – Condition 2: E′ is either lower or only marginally higher than E. In short, these conditions state that a K-means variant augmented with our heuristic should converge faster without significant increase in final MSE. Major bottleneck of K-means clustering is the computation of data point to clustercentroiddistanceineachiterationofK-means.Foradatasetwithndata points and k clusters, each iteration of K-means performs n∗k such distance ′ computations. To overcome this bottleneck, we maintain a CCL of size k for ′ each data point. We assume that k is significantly smaller than k. We discuss theeffectofvariouschoicesforthesizeofCCLinSection4.WebuildCCLbased ′ ontopk nearestclusterstothe datapointafterfirstiterationofK-means.Now each iteration of K-means will perform only n∗k′ distance computations. Consider a data point p1 and cluster centroids represented as c1,c2...,ck. Initially all centroids are chosen randomly or using one of the seed selection ′ ′ algorithmsmentionedinSection3.Letusassumethatk =4,andk <<k.After first iteration of K-means c8,c5,c6, and c1 are the top four closest centroids to p1 in the increasingorder of distance.This is the candidate cluster list for p1. If werunK-meansforseconditeration,p1 willcomputedistancetoallk centroids. After second iteration, top four closest centroid list might change in two ways: 1. Members of the list do not change but only ranking changes among the members. For example, top four closest centroid list for p1 might change to c1,c6,c8, and c5 in the increasing order of distance. 2. Some of the centroids in the previous list are replaced with other centroids which were not in the list. For example, top four closest list for p1 might change to c5,c2,c9, and c8 in the increasing order of distance For many synthetic and real world datasets we observe that the later case rarely happens. That is, the set of top few closest centroids for a data point remainsalmostunchangedeventhoughorderamongthemmightchange.There- fore, CCL is a good enough estimate for the closest cluster when K-means con- verges [1]. For each data point, our heuristic involves computation overhead of ′ O(k.log(k)) for creating CCL and memory overheadof O(k ) to maintain CCL. For a sample dataset consisting 100,000 points in 54 dimensions and the value ′ of k=100 and k =40, this overhead is approximately 30MB. Faster K-Means Cluster Estimation 3 Table 1. Datasets used in experiment Name CardinalityDimensionalityDescription Birch 100000 2 10 by 10 grid of Gaussian clusters Covtype 150000 55 remote soil covermeasurements Mnist 60000 784 original NISThandwritten digit training data KDDCup 95412 481 KDDCup 1998 data Synthetic 100000 100 Uniform random dataset 3 Related Work In last three decades, there has been significant work on improving Lloyd’s al- gorithm [6] both in terms of reducing MSE and running time. The follow up work on Lloyd’s algorithm can be broadly divided into three categories: Better seedselection[2,5],Selectingidealvaluefornumberofclusters[8],andBoundson data point to cluster centroid distance[3,7,4]. Arthur et. al.[2] provided a better method for seed selection based on a probability distribution over closest clus- ter centroid distances for each data point. Likas et. al.[5] proposed the Global k-means method for selecting one seed at a time to reduce final mean squared error. Pham et. al.[8] designed a novel function to evaluate goodness of clus- tering for various potential values of number of clusters. Elkan[3] use triangle inequalitytoavoidredundantcomputationsofdistancebetweendatapointsand clustercentroids.PellegandMoore[7]andKanungoetal.[4]proposedsimilaral- gorithms that use k-d trees.Boththese algorithmsconstruct a k-dtree overthe dataset to be clustered. Though these approaches have shown good results, k-d trees perform poorly for datasets in higher dimensions. Seed selection based K-means variants differ from Lloyd’s algorithm only in the method of seed selection. Our heuristic can be directly used in such al- gorithms. K-means variants that find appropriate number of clusters in data, evaluate the goodness of clustering for various potential values of number of clusters. Such algorithms can use our heuristic while performing clustering for eachpotentialvalueofk.K-meansvariantsinthirdcategorycomputeexactdis- tancesonlytofewcentroidsforeachdatapoint.However,theyhavetocompute boundsondistancestorestofthecentroidsforeachdatapoint.Ourheuristiccan help such K-means variants to further reduce distance and bound calculations. 4 Experimental Results Our heuristic can be augmented to multiple variants of K-means mentioned in Section 3. When augmented to Lloyd’s algorithm, our heuristic provides a speedup of around 30 times with the error within 0.2% of that of Lloyd’s al- gorithm. However to show the effectiveness of our heuristic, we present results of augmenting it to faster variants of K-means such as K-means with triangle inequality(KMT)[3].Due to lackofspace,wepresentresultsofaugmentingour heuristic withonly this variant.Augmenting KMTwith ourheuristicis referred 4 Siddhesh Khandelwal, Amit Awekar Table 2. Effect of varyingk′ on HTperformance. The value of k = 100. RND= Random initialization ; KPP = Initialization using Kmeans++[2] k′ = 20 k′ = 30 k′ = 40 k′ = 50 k′ = 60 RNDKPPRNDKPPRNDKPPRNDKPPRNDKPP Birch PIM(%) -0.11 0 0.04 0 0 0 0 0 0 0 Speedup 3.05 3.14 2.48 2.26 2.01 1.93 1.68 1.67 1.41 1.31 Covtype PIM(%) 0.21 0.03 0.02 0 0 0 0 0 0 0 Speedup 2.32 2.02 1.81 1.82 1.61 1.63 1.55 1.38 1.42 1.20 Mnist PIM(%) 1.30 1.36 0.60 0.71 0.36 0.36 0.30 0.18 0.23 0.09 Speedup 1.89 1.47 1.60 1.44 1.42 1.26 1.38 1.19 1.37 1.15 KDDCupPIM(%) 0.81 0.70 0.11 0.15 0.08 0.02 -0.18 -0.01 0 0 Speedup 1.44 1.60 1.33 1.15 1.42 1.02 0.88 0.99 1.18 1.02 SyntheticPIM(%) 0.19 0.15 0.11 0.08 0.06 0.04 0.03 0.01 0.01 0.01 Speedup 2.90 2.45 2.28 1.97 1.87 1.71 1.51 1.35 1.36 1.17 as algorithm HT. Code and datasets used for our experiments are available for download [1]. During each iteration of KMT, a data point computes distance to the cen- troid of its current cluster. KMT uses triangle inequality to compute efficient lower bounds on distances to all other centroids. A data point will compute ex- act distance to any other centroid only when the lower bound on such distance is smaller than the distance to the centroid of its current cluster. During each iteration of HT, a data point will also compute distance to the centroid of its current cluster. However, HT will compute lower bounds on distances to cen- troids only in its CCL. A data point will compute exact distance to any other centroidinthecandidateclusterlistonlywhenthelowerboundonsuchdistance is smaller than the distance to the centroid of its current cluster. Experimental results are presented on five datasets, four of which were used by Elkan et. al.[3] to demonstrate the effectiveness of KMT and one is a syn- thetically generated dataset by us. These datasets vary in dimensionality from 2 to 784, indicating applicability of our heuristic for low as well as high dimen- sional data (please refer to Table 1). Our evaluation metrics are chosen based on two conditions mentioned in Section 2: Speedup to satisfy Condition 1 and PercentageIncreaseinMSE(PIM)tosatisfyCondition2.Speedupiscalculated as T/T′. PIM is calculated as (100∗(E′−E))/E. We tried two different meth- odsforinitialseedselection:random[6]andK-means++[2].Bothseedselection methods gavesimilar trends in results. To ensure fair comparison,the same ini- tial seeds are used for both KMT and HT. For some experiments, HT achieves smaller MSE than KMT (E′ ≤ E). This happens because our heuristic jumps the local minima by not computing distance to every cluster centroid. Only in suchcases,HT requiresmoreiterationsto convergeandruns slowerthanKMT. Effect of Varying k′:PleaserefertoTable2.Thevalueofthetotalnumber of clusters k is set to 100 for all datasets. Running time and MSE of KMT is ′ independent of value of k . Speed up of HT over KMT increases with reduction Faster K-Means Cluster Estimation 5 Table 3. Effect of varyingk on HT performance. The valueof k′ =0.4∗k. RND= Random initialization ; KPP = Initialization using Kmeans++[2] k = 50 k = 100 k = 500 k = 1000 RNDKPPRNDKPPRNDKPPRNDKPP Birch PIM(%) 0.31 0 0 0 0 0 0 0 Speedup 1.65 1.71 1.98 1.97 2.14 2.10 2.12 2.15 Covtype PIM(%) 0.01 0.02 0.26 0 0 0 0 0 Speedup 1.35 1.31 1.65 1.50 1.94 1.87 1.97 1.90 Mnist PIM(%) 0.94 0.87 0.38 0.52 0.09 0.23 0.13 0.07 Speedup 1.10 1.20 1.23 1.45 1.28 1.24 1.29 1.19 KDDCupPIM(%) 0.51 0.99 -0.06 0.15 0 0.03 0 0.02 Speedup 1.02 1.38 0.85 1.18 1.13 1.33 1.19 1.37 SyntheticPIM(%) 0.09 0.07 0.05 0.04 0.03 0.01 0.01 0.01 Speedup 2.03 1.63 1.76 1.56 1.75 1.45 1.56 1.51 ′ ′ in value of k . This is expected as for small value of k , HT can avoid many redundant distance computations using small CCL. Speed up of HT over KMT ′ is not same as the ratio k/k . Reason for reduced speed up is that KMT also avoids some distance computations using its own filtering criteria of triangle ′ inequality. Our heuristic achieves ideal speed of k/k when compared against ′ ′ basicK-meansalgorithm[1].E increaseswithreductioninvalueofk .However, ′ E is only marginally higher than E as PIM value never exceeds 1.5. Effect of Varying k: Please refer to Table 3. Here, we report results for valueofk′ setto0.4∗k.Withincreasingvalueofk,HTachievesbetterspeedup overKMT and difference between MSE ofHT and MSE of KMT reduces. With increasing value of k, most of the centroid to data point distance calculations become redundantas data-pointis assignedonly to the closestcentroid.Insuch scenario, our heuristic avoids distance computations with reduced PIM. This shows that our heuristic can be used for datasets having only few as well as large number of clusters. Effect of Seeding: Please refer to Table 2 and Table 3. For each value of ′ k in Table 2 and k in Table 3, we used two different initial seedings - random (RND) and Kmeans++ [2]. If we compare the results, we observe that better seeding (KMeans++) generally gives better results in terms of PIM. Randomly selected seeds are not necessarily well distributed across the dataset. In such cases,successive iterations of K-means causes significantchanges in cluster cen- troids. Improved seeding methods such as KMeans++ ensure that the initial centroids are spread out more uniformly. Thus centroids shift is less significant in successive iterations. In such scenario, CCL computed after first iteration is abetter estimate forfinalclustermembership.Thusourheuristic isexpectedto perform better with newer variants of K-means that provide improved seeding. Effect of Cluster Well-Separateness:Wealsoperformedexperimentson synthetic datasets in two dimensions. These datasets were generated using a mixtureofGaussians.TheGaussiancentersareplacedatequalanglesonacircle 6 Siddhesh Khandelwal, Amit Awekar 2π n ofradiusr(angle= ),andeachcenterisassignedequalnumberofpoints( ). k k Theexperimentwasdoneonsyntheticdatasetsof100000pointsgeneratedusing themethoddescribedabovewithvariancesetto0.25.Thevalueofkissetto100 ′ andthevalueofk issetto40.Wegeneratedninedatasetsbyvaryingtheradius from zero to forty in steps of five units. We ran KMT and HT over these nine datasetstocheckhowourheuristicperformswithchangeinwellseparatenessof clusters.Weobservedthatwhenclustersareclose,boththealgorithmsconverge quickly as initial seeds happen to be close to actual cluster centroids. With higher radius, initial seeds might be far off from the actual cluster centroids and KMT takes longer to converge. However, HT performs significantly better for higher values of radius as HT can quickly discard far away clusters. HT achieves a speedup of around 2.31 for higher radius values. For all experiments overthese syntheticdatasets,weobservedthatPIMvalueneverexceeds0.01[1]. This indicates that our heuristic remains relevant even with variation in degree of separation among the clusters. 5 Conclusion We presented a heuristic to attack the bottleneck of redundant distance com- putations in K-means.Our heuristic limits distance computations for eachdata pointtoCCL.OurheuristiccanbeaugmentedwithdiversevariantsofK-means to converge faster without any significant increase in MSE. With extensive ex- periments on real-world and synthetic datasets, we showed that our heuristic performs well with variations in dataset dimensionality, CCL size, number of clusters, and degree of separationamong clusters. This work can be further im- proved by making the CCL dynamic to achieve better speed up while reducing the PIM value. References 1. The code and dataset for the experimentscan befound at: https://github.com/siddheshk/Faster-Kmeans. 2. D. Arthur and S. Vassilvitskii. k-means++: The advantages of careful seeding. In ACM-SIAM symposium on Discrete algorithms, pages 1027–1035, 2007. 3. C. Elkan. Using the triangle inequality to accelerate k-means. In International Conference om Machine Learning, pages 147–153, 2003. 4. T. Kanungo, D. M. Mount, N. S. Netanyahu, C. D. Piatko, R. Silverman, and A.Y.Wu. Anefficientk-meansclusteringalgorithm:Analysisandimplementation. Pattern Analysis and Machine Intelligence, IEEE Trans. on, 24(7):881–892, 2002. 5. A. Likas, N. Vlassis, and J. J. Verbeek. The global k-means clustering algorithm. Pattern recognition, 36(2):451–461, 2003. 6. S. P. Lloyd. Least squares quantization in pcm. Information Theory, IEEE Trans. on, 28(2):129–137, 1982. 7. D. Pelleg and A. Moore. Accelerating exact k-means algorithms with geometric reasoning. In ACM SIGKDD, pages 277–281. ACM, 1999. 8. D. T. Pham, S. S. Dimov, and C. Nguyen. Selection of k in k-means clustering. Journal of Mechanical Engineering Science, 219(1):103–119, 2005.