Kmeans clustering and vector quantization (scipy.cluster.vq
)¶
Provides routines for kmeans clustering, generating code books from kmeans models, and quantizing vectors by comparing them with centroids in a code book.

Normalize a group of observations on a per feature basis. 

Assign codes from a code book to observations. 

Performs kmeans on a set of observation vectors forming k clusters. 

Classify a set of observations into k clusters using the kmeans algorithm. 
Background information¶
The kmeans algorithm takes as input the number of clusters to generate, k, and a set of observation vectors to cluster. It returns a set of centroids, one for each of the k clusters. An observation vector is classified with the cluster number or centroid index of the centroid closest to it.
A vector v belongs to cluster i if it is closer to centroid i than any other centroids. If v belongs to i, we say centroid i is the dominating centroid of v. The kmeans algorithm tries to minimize distortion, which is defined as the sum of the squared distances between each observation vector and its dominating centroid. The minimization is achieved by iteratively reclassifying the observations into clusters and recalculating the centroids until a configuration is reached in which the centroids are stable. One can also define a maximum number of iterations.
Since vector quantization is a natural application for kmeans, information theory terminology is often used. The centroid index or cluster index is also referred to as a “code” and the table mapping codes to centroids and vice versa is often referred as a “code book”. The result of kmeans, a set of centroids, can be used to quantize vectors. Quantization aims to find an encoding of vectors that reduces the expected distortion.
All routines expect obs to be a M by N array where the rows are the observation vectors. The codebook is a k by N array where the i’th row is the centroid of code word i. The observation vectors and centroids have the same feature dimension.
As an example, suppose we wish to compress a 24bit color image (each pixel is represented by one byte for red, one for blue, and one for green) before sending it over the web. By using a smaller 8bit encoding, we can reduce the amount of data by two thirds. Ideally, the colors for each of the 256 possible 8bit encoding values should be chosen to minimize distortion of the color. Running kmeans with k=256 generates a code book of 256 codes, which fills up all possible 8bit sequences. Instead of sending a 3byte value for each pixel, the 8bit centroid index (or code word) of the dominating centroid is transmitted. The code book is also sent over the wire so each 8bit code can be translated back to a 24bit pixel value representation. If the image of interest was of an ocean, we would expect many 24bit blues to be represented by 8bit codes. If it was an image of a human face, more flesh tone colors would be represented in the code book.