k-Means Clustering
Let us say we have an image that is stored with 24 bits/pixel and can have up to
16 million colors. Assume we have a color screen with 8 bits/pixel that can
display only 256 colors. We want to find the best 256 colors among all 16 million
colors such that the image using only the 256 colors color quantization in the
palette looks as close as possible to the original image.
This is color quantization where we map from high to lower resolution. In the
general case, the aim is to map from a continuous space to a discrete space; this
process is called vector quantization.
Of course we can always quantize uniformly, but this wastes the colormap by
assigning entries to colors not existing in the image, or would not assign extra
entries to colors frequently used in the image.
For example, if the image is a seascape, we expect to see many shades of blue
and maybe no red. So the distribution of the colormap entries should reflect the
original density as close as possible placing many entries in high-density regions,
discarding regions where there is no data.
That is, instead of the original data value, we use the closest value we have in the
alphabet of reference vectors. mi are also called codebook vectors or code words,
because this is a process of encoding/decoding Going from xt to i is a process of
encoding the data using the codebook of mi, i = 1, . . . , k and, on the receiving
end, generating mi from i is decoding.
Quantization also allows compression: For example, instead of using 24 bits to
store (or transfer over a communication line) each xt , we can just store/transfer
its index i in the colormap using 8 bits to index any one of 256, and we get a
compression rate of almost 3; there is also the color map to store/transfer.
Prepared by [Link] Prince M.E,M.S,(Ph.D)(ISRO-IIT MADRAS)
Let us see how we can calculatemi : When xt is represented bymi , there is an
error that is proportional to the distance, ||xt – mi||. For the new image to look like
the original image, we should have these distances as reconstruction small as
possible for all pixels. The total reconstruction error is defined error as
The best reference vectors are those that minimize the total reconstruction error.
Bt i also depend on mi , and we cannot solve this optimization problem
analytically. We have an iterative procedure named k-means clustering for this:
First, we start with some mi initialized randomly.
Then at each iteration, we first use equation and calculate bt i for all xt , which
are the estimated labels; if bt i is 1, we say that xt belongs to the group of mi .
Then, once we have these labels, we minimize equation.
Taking its derivative with respect to mi and setting it to 0, we get
The reference vector is set to the mean of all the instances that it represents. Note
that this is the same as the formula for the mean in above equation except that we
place the estimated labels bt i in place of the labels r t
i.
Prepared by [Link] Prince M.E,M.S,(Ph.D)(ISRO-IIT MADRAS)
This is an iterative procedure because once we calculate the new mi , bt i change
and need to be recalculated, which in turn affect mi . These two steps are repeated
until mi stabilize
. The pseudocode of the k-means algorithm is given in figure .One disadvantage
is that this is a local search procedure, and the final mi highly depend on the initial
mi . There are various methods for initialization:
_ We can simply take randomly selected k instances as the initial mi .
_ The mean of all data can be calculated and small random vectors may
be added to themean to get the k initial mi .
We can calculate the principal component, divide its range into k equal intervals,
partitioning the data into k groups, and then take the means of these groups as the
initial centers.
After convergence, all the centers should cover some subset of the data instances
and be useful; therefore, it is best to initialize centers where we believe there is
data.
Prepared by [Link] Prince M.E,M.S,(Ph.D)(ISRO-IIT MADRAS)
There are also algorithms for adding new centers incrementally or deleting empty
ones. In leader cluster algorithm, an instance that is far away from existing
centers (defined by a threshold value) causes the creation of a new center at that
point
one of the two copies to make them different). Similarly, a center that covers too
few instances can be removed and restarted from some other part of the input
space.
k-means algorithm is for clustering, that is, for finding groups in the data, where
the groups are represented by their centers, which are the typical representatives
of the groups. Vector quantization is one application of clustering, but clustering
is also used for preprocessing before a later stage of classification or regression
Prepared by [Link] Prince M.E,M.S,(Ph.D)(ISRO-IIT MADRAS)