# X-means algorithm and BIC

I want to simulate X-means algorithm based on  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 ?

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

 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  for X-means algorithm.

X-mean algorithm BIC calculation question

Using BIC to estimate the number of k in KMEANS

• BIC is one criterion (not criteria). Q.3 is off-topic here: see the Help Center for advice on software-related questions. – Nick Cox Sep 1 '15 at 6:20
• This is discussed in the Help Center. As before, please read advice there. stats.stackexchange.com/help/on-topic – Nick Cox Sep 1 '15 at 7:44
• I read the [X-mean algorithm BIC calculation question] which is similar to my question.Could you please explain me how to calculate BIC for X-means algorithm? @Budric – Khatereh Sep 1 '15 at 11:06

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.

• Thank you for answering. You mean the distance to the edge of the cluster can be considered the average distance of points to the centroid and new centroids are defined 1/3 the distance to the edge of the cluster. Is that right? Why should be used EM instead of K-means? – Khatereh Aug 29 '15 at 18:49
• K-means assumes uniform density in each cluster, so all clusters are hyperspheres. Assuming Gaussian clusters lets the cluster model shrink-fit to the actual point distribution, and the cluster level curves are hyperellipsoidal. A cluster can have different sizes in different dimensions! The splitting trick for K-means can't take advantage of any symmetry in the data - hypersphere, remember. I'd just use the vector from the centroid to the farthest point in the cluster. Then split the cluster on that line into 3 parts by selecting new centroids 1/3 of the distance out. – Dr. James M. Coggins Aug 30 '15 at 22:28
• Thank you so much for your help. In the X-means algorithm,step (4), I use BIC criterion for deciding to retain or replace new clusters. If BIC for 2-clusters is greater than 1-cluster, I replace one cluster with two clusters. Now, the number of clusters K is updated to the current value of them. I continue untill the number of clusters did not change from K which is updated. Is this process right? – Khatereh Sep 1 '15 at 9:53
• Information Criteria looks for lowest, not hightest. mathworks.com/help/econ/aicbic.html k-means should be used only in the appropriate cases. It exists for a reason. – EngrStudent Sep 1 '15 at 11:26

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.

• @Khatereh, I love to help. I was thinking - you might get some interesting mileage by making this a search on a tree. – EngrStudent Sep 5 '15 at 13:30