On Thu, Jul 22, 2010 at 10:48 AM, Benjamin Root <span dir="ltr">&lt;<a href="mailto:ben.root@ou.edu" target="_blank">ben.root@ou.edu</a>&gt;</span> wrote:<br><div class="gmail_quote"><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">

<div class="gmail_quote"><div><div></div><div>On Wed, Jul 21, 2010 at 3:25 PM, alex <span dir="ltr">&lt;<a href="mailto:argriffi@ncsu.edu" target="_blank">argriffi@ncsu.edu</a>&gt;</span> wrote:<br><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">



Hi,<br><br>I want to nitpick about the scipy kmeans clustering implementation.  Throughout the documentation <a href="http://docs.scipy.org/doc/scipy/reference/cluster.vq.html" target="_blank">http://docs.scipy.org/doc/scipy/reference/cluster.vq.html</a> and code, the &#39;distortion&#39; of a clustering is defined as &quot;the sum of the distances
between each observation vector and its dominating centroid.&quot;  I think that the sum of squares of distances should be used instead of the sum of distances, and all of the miscellaneous kmeans descriptions I found with google would seem to support this.<br>




<br>For example if one cluster contains the 1D points (1, 2, 3, 4, 10) and the old center is 3, then the centroid updating step will move the centroid to 4.  This step reduces the sum of squares of distances from 55 to 50, but it increases the distortion from 11 to 12.<br>



<font color="#888888">
<br>Alex</font><br></blockquote></div></div><div><br>Every implementation of kmeans (except for SciPy&#39;s) that I have seen allowed for the user to specify which distance measure they want to use.  There is no right answer for a distance measure except for &quot;it depends&quot;.  Maybe SciPy&#39;s implementation should be updated to allow for user-specified distance measures (e.g. - absolute, euclidian, city-block, etc.)?<br>



<br>Ben Root<br></div></div></blockquote><div><br>While the best distance might depend on the application, I think that of all these distance measures only the sum of squares of Euclidean distances is guaranteed to monotonically decrease at each step of the algorithm.  If the scipy kmeans implementation depends on this monotonicity, which I think it currently does, then this assumption could be the source of subtle bugs when error measures like distortion are used.<br>
<br>Maybe I can nitpick more effectively if I frame it as &quot;scipy is doing something strange and possibly buggy&quot; instead of as &quot;scipy is not using the distance function I want&quot;.<br><br>For example:<br><br>
&gt;&gt;&gt; import numpy as np<br>&gt;&gt;&gt; from scipy import cluster<br>&gt;&gt;&gt; v = np.array([1,2,3,4,10])<br>&gt;&gt;&gt; cluster.vq.kmeans(v, 1)<br>(array([4]), 2.3999999999999999)<br>&gt;&gt;&gt; np.mean([abs(x-4) for x in v])<br>
2.3999999999999999<br>&gt;&gt;&gt; np.mean([abs(x-3) for x in v])<br>2.2000000000000002<br><br>The result of this kmeans call suggests that the center 4 is best with distortion 2.4.  In fact this is not the case because a center of 3 would have distortion 2.2.<br>

<br>Alex<br></div></div>