I am working on VQ and I have designed my code book based on the following steps:
1. Take mean of the whole data.
2. Add/subtract some random value to the mean thus it results in M1 and M2
3. Now calculate the Euclidean distance of all points (one by one) from M1 and then M2, lets call it E1 and E2, respectively.
4. If E1
Dear Rabya Khan,
just to be clear, it is not correct to say that "K-mean will help". You are already using the k-means algorithm. Clerot Fabrice has clearly pointed that you are using a 2-means.
What you are missing is a good initialization strategy for the algorithm. K-means++ is exactly that: an initialization strategy which you can plug in your algorithm which will help in getting a good solution.
The fact that your loop "executes for infinite times" is a clear sign that your implementation is wrong (at least at some level). In fact k-means is always decreasing the objective function, and this guarantees convergence. You should check when this is not happening and that could be caused by the way you use to handle ties. Check that carefully.
Try to use the moving average to reduce the fluctuation in the vector + Root mean square.
Indeed, the problem is in step 2. How do you choose the range for your random values ?
Your problem is that of initializing the k-means algorithm (that is the algorithm you are using). This is an NP-complete problem. Look at K-means++ (http://en.wikipedia.org/wiki/K-means%2B%2B), which has some guarantee on the quality of the solution. Source code is available at http://en.wikibooks.org/wiki/K-Means%2B%2B
.
for a start with VQ, you might want to look at k-means++ (as pointed by Costantino just above, it is an improvement on the k-means which you are using (indeed you describe a 2-means)), kohonen maps (aka self organizing map) or neural gas ( http://en.wikipedia.org/wiki/Neural_gas ).
(kmeans++ improves over k-means by its initialization strategy ; with reasonable parameters, the last two techniques are quite insensitive to their initialization)
as a side point, i cannot see why your algorithm would "diverge" when the initialization sends the initial centers far from the distribution : what may happen then is that all points will be closer to one of the centers only and at the end you have only one group (or two groups, with one empty group !). well, this is not such a problem, resart with a smaller random initialization (i mean, less noise) and iterate until you get two clusters.
.
.
I agree with Fabrice regarding the divergence problem. That is why, in my previous post, I have asked about the range being used to generate the random numbers in step 2.
@Clerot & @Lehtihet yes you are very right....but other than that issue the loops stucks at times and executes for infinite times
@Costantino Grana & @ys Suni think your are right K-mean will help
.
i would suspect a problem in the exit test of your loop ... the k-means algorithm always converges (but not necessarily to a global optimum !) when the exit test is made on the objective function (RSS ; see http://nlp.stanford.edu/IR-book/html/htmledition/k-means-1.html for instance) since the algorithm always decreases the value of RSS and there are only a finite (large ! ... but finite) number of possible values for the RSS (only a finite number of clusterings).
on the other hand, testing the exit on the population of the clusters (as seems to be your case) may lead to spurious effects in some rather artificial cases, for you may have multiple clusterings with the same RSS value and breaking ties arbitrarily may lead your algorithm to iterate forever between these (equally optimal) solutions ; as stated in the link above :
"Since there is only a finite set of possible clusterings, a monotonically decreasing algorithm will eventually arrive at a (local) minimum. Take care, however, to break ties consistently, e.g., by assigning a document to the cluster with the lowest index if there are several equidistant centroids. Otherwise, the algorithm can cycle forever in a loop of clusterings that have the same cost. "
.
Dear Rabya Khan,
just to be clear, it is not correct to say that "K-mean will help". You are already using the k-means algorithm. Clerot Fabrice has clearly pointed that you are using a 2-means.
What you are missing is a good initialization strategy for the algorithm. K-means++ is exactly that: an initialization strategy which you can plug in your algorithm which will help in getting a good solution.
The fact that your loop "executes for infinite times" is a clear sign that your implementation is wrong (at least at some level). In fact k-means is always decreasing the objective function, and this guarantees convergence. You should check when this is not happening and that could be caused by the way you use to handle ties. Check that carefully.
actually i was tryng to implement k- mean clustering (to be specific for 2 classes) on my own. However, due to the intialization issue i was not getting well to the point.
However, i used the kmeans function i.e. is builtin function of Matlab. Now the issue is resolved for the time being.
But i would like to correct my own code as well.....
@Fabrice
thank u so much for such a detailed explanation. What you just mentioned is exactly the kind of problem i am facing....
.
repeating from my preceeding post :
"Since there is only a finite set of possible clusterings, a monotonically decreasing algorithm will eventually arrive at a (local) minimum. Take care, however, to break ties consistently, e.g., by assigning a document to the cluster with the lowest index if there are several equidistant centroids. Otherwise, the algorithm can cycle forever in a loop of clusterings that have the same cost. "
or, more flatly, test the exit on the RSS value (reaches a minimum, therefore does not change between two iterations) and not on the stability of the clusters.
.
- Badges
- Science topic