On Thu, Jul 22, 2010 at 12:12 PM, alex &lt;<a href="mailto:argriffi@ncsu.edu">argriffi@ncsu.edu</a>&gt; wrote:<br>&gt;&gt;<br>&gt;&gt;&gt; For example:<br>&gt;&gt;&gt;<br>&gt;&gt;&gt; &gt;&gt;&gt; import numpy as np<br>&gt;&gt;&gt; &gt;&gt;&gt; from scipy import cluster<br>

&gt;&gt;&gt; &gt;&gt;&gt; v = np.array([1,2,3,4,10])<br>&gt;&gt;&gt; &gt;&gt;&gt; cluster.vq.kmeans(v, 1)<br>&gt;&gt;&gt; (array([4]), 2.3999999999999999)<br>&gt;&gt;&gt; &gt;&gt;&gt; np.mean([abs(x-4) for x in v])<br>&gt;&gt;&gt; 2.3999999999999999<br>

&gt;&gt;&gt; &gt;&gt;&gt; np.mean([abs(x-3) for x in v])<br>&gt;&gt;&gt; 2.2000000000000002<br>&gt;&gt;&gt;<br>&gt;&gt;&gt; The result of this kmeans call suggests that the center 4 is best with<br>&gt;&gt;&gt; distortion 2.4.  In fact this is not the case because a center of 3 would<br>

&gt;&gt;&gt; have distortion 2.2.<br>&gt;&gt;&gt;<br>&gt;&gt;<br>&gt;&gt; I wonder if this is really a bug in the minimization code rather than an<br>&gt;&gt; issue with the distortion measure itself.<br>&gt;&gt;<br>&gt;&gt; Ben Root<br>

&gt;<br>&gt; The bug is in the _kmeans function in vq.py where it uses avg_dist[-2] -<br>&gt; avg_dist[-1] &lt;= thresh as a stopping condition.  This condition mistakenly<br>&gt; assumes that the distortion monotonically decreases.  One consequence is<br>

&gt; that when the distortion increases, avg_dist[-2] - avg_dist[-1] will be<br>&gt; negative, and the codebook and distortion associated with avg_dist[-1] are<br>&gt; returned.  This is where the 2.4 vs 2.2 error comes from.<br>

&gt;<br>&gt; I guess there could be a few ways to resolve the bug.  One way could be to<br>&gt; use the sum of squares of distances instead of the distortion; this would<br>&gt; guarantee that the error sequence monotonically decreases, and I suspect<br>

&gt; that this is what the author had originally intended.<br>&gt;<br>&gt; Another way to deal with the bug could be to report the second to last<br>&gt; codebook and distortion instead of the last codebook and distortion when the<br>

&gt; stopping condition is met.  This would probably fix the bug in the 2.2 vs.<br>&gt; 2.4 example, but it is kind of a kludge; if the sequence does not<br>&gt; monotonically decrease, then does it really make sense to use a small change<br>

&gt; as a stopping condition?<br>&gt;<br>&gt; Alex<br>&gt;<br><br>I have to search for some old code of mine, but if I remember correctly, it would seem that the latter solution is actually a better fix because it addresses the heart of the matter.  A minimization algorithm that doesn&#39;t return the most minimum value that it knows is buggy.  The stopping condition is another issue altogether.<br>

<br>There was a nice C-implemented, MIT-licensed kmeans algorithm that I used several years ago that had a much smarter stopping condition and several other useful features.  Let me see if I can find it and we can compare.<br>

<br>Ben Root<br><br><br>