quick look at machine learning -means clustering -means clustering is probably the most widely used clustering method its goal is to partition set of examples into clusters such that each example is in the cluster whose centroid is the closest centroid to that exampleand the dissimilarity of the set of clusters is minimized unfortunatelyfinding an optimal solution to this problem on large dataset is computationally intractable fortunatelythere is an efficient greedy algorithm that can be used to find useful approximation it is described by the pseudocode randomly choose examples as initial centroids while true create clusters by assigning each example to closest centroid compute new centroids by averaging the examples in each cluster if none of the centroids differ from the previous iterationreturn the current set of clusters the complexity of step is ( * * )where is the number of clustersn is the number of examplesand the time required to compute the distance between pair of examples the complexity of step is ( )and the complexity of step is (khencethe complexity of single iteration is ( * *dif the examples are compared using the minkowski distanced is linear in the length of the feature vector of coursethe complexity of the entire algorithm depends upon the number of iterations that is not easy to characterizebut suffice it to say that it is usually small one problem with the -means algorithm is that it is nondeterministic--the value returned depends upon the initial set of randomly chosen centroids if particularly unfortunate set of initial centroids is chosenthe algorithm might settle into local optimum that is far from the global optimum in practicethis problem is typically addressed by running -means multiple times with randomly chosen initial centroids we then choose the solution with the minimum dissimilarity of clusters figure contains straightforward translation of the pseudocode describing -means into python it uses random sample(exampleskto get the initial centroids this invocation returns list of randomly chosen distinct elements from the list examples though -means clustering is probably the most commonly used clustering methodit is not the most appropriate method in all situations two other widely used methodsnot coverd in this bookare hierarchical clustering and em-clustering the most widely used -means algorithm is attributed to james mcqueenand was first published in howeverother approaches to -means clustering were used as early as the unfortunatelyin many applications we need to use distance metrice earthmovers distance or dynamic-time-warping distancethat have higher computational complexity