[ namelywe wish to "quantizeor "encodethe vectors in in such way that each vector is represented by one of source vectors ck such that the loss ( of this representation is minimized most well-known clustering and vector quantization methods update the vector of centersstarting from some initial choice and using iterative (typically gradient-basedprocedures it is important to realize that in this case ( is seen as function of the centerswhere each point is assigned to the nearest centerthus determining the clusters it is well known that this type of problem -optimization with respect to the centers -is highly multiextremal anddepending on the initial clustersgradient-based procedures tend to converge to local minimum rather than global minimum centroids -means one of the simplest methods for clustering is the -means method it is an iterative method wherestarting from an initial guess for the centersnew centers are formed by taking sample means of the current points in each cluster the new centers are thus the centroids of the points in each cell although there exist many different varieties of the -means algorithmthey are all essentially of the following formalgorithm -means inputcollection of points { xn }number of clusters kinitial centers ck outputcluster centers and cells (regions while stopping criterion is not met do rk (empty sets for to do [dist(xi )dist(xi ck )/distances to centers argmin rk rk {xi /assign xi to cluster for to do xrk ck |rk /compute the new center as centroid of points return {ck }{rk thusat each iterationfor given choice of centerseach point in is assigned to its nearest center after all points have been assignedthe centers are recomputed as the centroids of all the points in the current cluster (line typical stopping criterion is to stop when the centers no longer change very much as the algorithm is quite sensitive to the choice of the initial centersit is prudent to try multiple starting valuese chosen randomly from the bounding box of the data points we can see the -means method as deterministic (or "hard"version of the probabilistic (or "soft"em algorithm as follows suppose in the em algorithm we have gaussian mixtures with fixed covariance matrix sk id kwhere should be thought of as being infinitesimally small consider iteration of the em algorithm having obtained the expectation vectors ( - and weights ( - keach point xi is ask (tsigned cluster label zi according to the probabilities pi ( ) given in (