tag:blogger.com,1999:blog-6555947.post110686186908681100..comments2024-04-08T04:56:51.603-06:00Comments on The Geomblog: SODA Outtakes: Lloyd's algorithm and analysing heuristicsSuresh Venkatasubramanianhttp://www.blogger.com/profile/15898357513326041822noreply@blogger.comBlogger4125tag:blogger.com,1999:blog-6555947.post-1109360865064770822005-02-25T12:47:00.000-07:002005-02-25T12:47:00.000-07:00BTW, this work is hopefully a first step on this p...BTW, this work is hopefully a first step on this problem. Although me & Bardia went with it as far as we could, there is still a huge gap between the lower bound and the upper bound. It would be really nice to close it or just improve it, but I think it would require a new idea. A super linear (resp. quadratic) lower bound would be (resp. very) exciting even in high dimensions.<br /><br />My intuition is that SinglePnt dominates the k-means method. So, my intruition is that our analysis in fact would also hold for this case. However, proving this connection I am afraid is going to be very painful, since the behavior of k-means seems to be intricate.<br /><br />In fact, in the talk, I said that I "conjecture" that there is such a realtionship. The double quatation is because we want credit for this conjecture only if it is correct. <br /><br />In short, this paper is wide open for further improvement... <br /><br /><A></A><A></A>Posted by<A><B> </B></A><A HREF="http://www.uiuc.edu/~sariel" REL="nofollow" TITLE="sariel at gmail dot com">Sariel Har-Peled</A>Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-1109357621474425112005-02-25T11:53:00.000-07:002005-02-25T11:53:00.000-07:00The gap IMO rests in the experimental setup. I don...The gap IMO rests in the experimental setup. I don't say that the paper is deficient in this regard, but that any modification of k-means that claims to provide intuition about how it works should behave in the same way. They have some experimental evidence supporting this, but more is needed.<br /><br />Maybe I should have relaxed my statement. There is some progress that has been made (which is why I mentioned this paper in the first place), but it is still unclear how to connect SinglePnt (which seems the more natural of the two alternates) and k-means. <br /><br />At first cut, it appears that k-means is much more efficient because of the multiple misclassifications it fixed in each iteration. The results on SinglePnt suggest that this might be an illusion. Can some kind of dominance be proved ? Moving many points is not much better than moving one etc ?  <br /><br /><A></A><A></A>Posted by<A><B> </B></A>SureshAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-1109357314328601662005-02-25T11:48:00.000-07:002005-02-25T11:48:00.000-07:00Suresh says "It is not clear to me that their pape...Suresh says "<I>It is not clear to me that their paper answers to any degree the question of why Lloyd's algorithm works as well as it appears to.</I> "<br /><br />It seems to me that your evaluation above is much<br />more negative than warranted. Why isn't the analysis<br />a large step towards asnwering things about Lloyd's<br />algorithm? They are presenting a worst case<br />lower bound. The modified algorithm<br />retains the intuition of the original algorithm<br />while giving performance bounds. A more refined<br />analysis would need understanding in some sense<br />the average case and here there can be many<br />interpretations. At the end of the day one<br />might still not "understand" why Lloyd's algorithm<br />works.<br /> <br /><br /><A></A><A></A>Posted by<A><B> </B></A>Chandra ChekuriAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-1109357239330488322005-02-25T11:47:00.000-07:002005-02-25T11:47:00.000-07:00test 
Posted by Sureshtest <br /><br /><A></A><A></A>Posted by<A><B> </B></A>SureshAnonymousnoreply@blogger.com