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.