Kmeans Algorithm

k-means clustering [15] partitions a group of samples into K groups. The objective function to be reduced is the sum of square errors. The algorithm iterates as following:

Notes a: temperature cooling rate d: perturbation

R: threshold value to eliminate repeated centroids

Update critical temperature: The critical temperature 7 for each cluster at temperature T is calculated as in Tc=2^max,

Figure 6.3: Flow chart for implementing mass-constrained deterministic annealing (DA).

Eliminate repeated centroids*: discard centroids that coincide at the same location in one cluster: For i = 1:K,

If ||yt-y(.||/||yi||< R, then eliminate y, py.=py. +ypJt j = 1:K End

Figure 6.4: Mass-constrained deterministic annealing (DA) centroid update.

1. Compute the mean of each cluster as the centroid of that cluster.

2. Assign each sample to its closest cluster by calculating distances among the sample and all cluster centroids.

3. Keep iterate over the above two steps till the sum of square error of each cluster can no longer be reduced.

The initial centroids can be random; however, the choice of initial centroids is crucial and may result in incorrect partitioning. The iteration drives the objective function toward a minimum. The resultant grouping of the objects is geometrically as compact as possible around the centroids in each group.

0 0

Post a comment