X-means algorithm and BIC

Question

I want to simulate X-means algorithm based on [1] in MATLAB. I have some questions about this algorithm.

X-means Algorithm Steps:

(1) Initialize K = Kmin.

(2) Run K-means algorithm.

(3) FOR k = 1,. . . ,K: Replace each centroid μk by two centroids μ(1) and μ(2).

(The two new centroids for the initialization of each of the K-means algorithms are obtained by perturbing an original centroid in two opposite directions along a randomly chosen vector by an amount proportional to the size of the respective cluster.)

(4) Run K-means algorithm with K = 2 over the cluster k.

Replace or retain each centroid based on the model selection criterion.

(the algorithm performs a model selection test BIC to determine whether the two new clusters are a better model than the original single cluster in each of the cases. BIC_{k}=-2*logL+klogN which N is number of observations and k is number of clusters and logL is the log-likelihod)

(5) IF convergence condition is not satisfied, go to Step (2). Otherwise Stop.

Question 1: In step (3) how can I determine new centroids?

Question 2: In step (4) how can I use the model selection criterion to replace or retain new centroids based on [2]?

[1] X-means: Extending k-means with efficient estimation of the number of clusters

[2] Notes on BIC for X-means Clustering

There are two other questions about BIC calculation in X-Means, but I don't know how can I use BIC based on [2] for X-means algorithm.

X-mean algorithm BIC calculation question

Using BIC to estimate the number of k in KMEANS

Answer 1

The new centroids are creating a new structure hypothesis, basically that the existing cluster should be split into two. Define the new centroids along a random vector about 1/3 the distance to the edge of the cluster. If you are using K-means, the average distance of points to the centroid would be a suitable criterion. The real problem is that K-means should not be used for anything. You should use EM, which is the same algorithm but with Gaussian distribution assumptions instead of uniform distribution assumptions. The counterpart of this for Gaussian distributions is easier to apply and more intuitively sensible besides. Try splitting the Gaussian along its principal axis, about 1.2 standard deviations out from the mean vector.

Answer 2

You sound like you are asking for elaboration on steps 3-5.

I would do it as follows:

• subset the cluster of interest from the field of points
• perform k-means with N=2 within that subset and compute AIC
• compare then N=2 AIC with the N=1 AIC that came with the cluster

• whichever model (N=2, N=1) over those points is associated with the lowest AIC, retain it.

• When you are done with all of your clusters, check your stopping criteria. If the criteria is met then stop, otherwise continue.

Personally, as I would use AICc because sample sizes can get sparse, and I would stop when I had reached minimum AICc for all the clusters.

Knowing k-means as I do I would also do the following:

• I would not run this just once over a data-set. I would want to make sure that I had consistent results, so I would run it several times.
• I would start with a "toy" dataset appropriate to the method. There are some good "textbook" sets. (UCI clustering subset link) See how your algo compares to "true" against data for which "true" is known, and other algorithms are benchmarked.
• Sometimes k-means doesn't want to stop. I like to add a "learning rate" so move the new centroid only a portion of the distance to the new location and re-compute.
• Having something like AIC as well, and retaining that can augment proper stopping of k-means. I would let k-means run a little while first, it does have EM of a sort built in, but that EM is in the limit of infinite samples so k-means tends to get "funky" because of single or few sample phenomena.
• If you start iterations with cluster membership not reset, then you are doing something different than computing only the number of clusters. Classic K-means is like Gaussian Mixtures when all the mixtures have the same, constant, variance. In this, the sub-mixtures are splitting the variance as well as the sample. Instead of packing canonballs of the same size, you turn each into two smaller. If you retain your membership at the next iteration instead of throwing it away, or if you do something clever (whatever it is), then you might be able to retain the speed of k-means but have clusters with non-uniform variances. You might approach Gaussian Mixtures without the compute overhead.

UPDATE:

I think that you should try N=2 on the subset, then N=3, up to N=m/5 where m is the number of samples in the subset. This allows more than 2 sub-spheres per cluster. Pick the best for that cluster. Iterate throughout all major clusters, and store the overall AICc.

Then, increment the major cluster count by 1 and repeat k-means, then for each subsample repeat.

This will give you a tree whose first branches are the counts of k-elements and whose second branches are the counts of sub-clusters, and whose leaf-tips are the AICc.

I think then you could argue that you have a much more optimal clustering - with non-uniform variances.

You might try sub-sub cluster splitting.

If you randomly sub-sampled before making the algorithm run, and you repeated it hundreds of times - then you could make the k-means (weak learner) analog of a random forest. You could then pick a point in the space and get the ensemble estimate of within-cluster neighborhood or multiple scales of out-of-cluster neighborhood.