Bisecting KMeans

It is a variation of generic KMeans.

Reference: http://www.siam.org/meetings/sdm01/pdf/sdm01_05.pdf

The steps of the algorithm are:

1. Initialize by randomly selecting a point, say then compute the centroid w of M and compute:

The centroid is the center of the cluster. A centroid is a vector containing one number for each variable, where each number is the mean of a variable for the observations in that cluster.

2. Divide M =[x1, x2, ... xn] into two, sub-clusters M_L and M_R, according to the following rule:

3. Compute the centroids of M_L and M_R, w_L and w_R, as in step 2.

4. If w_L = c_L and w_R = c_R, stop.

Otherwise, let c_L= w_L c_R = w_R , go to step 2.