Say we want to split a cube in $\mathbb{R}^{64}$ into 10 pieces. NN, nearest-neighbor or Voronoi splits, take 10 cluster centres $c_0, \ldots, c_9$ in the cube, e.g. from K-means, then classify a new data point $x$ by finding its nearest centre: $$\text{NN}( x, c_0, \ldots, c_9 ) \equiv \text{argmin}_j\ \| x - c_j \| \text.$$

Kmeans centres are averages of data points, so fall near the data.
Could allowing centres outside the data give better splits ?
Is there a variant of Kmeans which converges e.g. to SVM weights, viewed as points in the data space ?

As Suresh Venkat points out, "better" splitting, better classification, is hard to define.

  • $\begingroup$ I'm not sure the definitions are right here. In general I don't believe that the centres for the k-means problem will be data points. Perhaps you're confusing it with k-medoids? $\endgroup$ – James King Sep 12 '11 at 14:08
  • 2
    $\begingroup$ possibly the OP means "inside the hull defined by the data" rather than "at data points". Also, @Denis what does "better" mean in this context ? $\endgroup$ – Suresh Venkat Sep 12 '11 at 17:01
  • 2
    $\begingroup$ I feel like the question is still overly vague, and is conflating a vague discussion of splitting with possibly a more specific discussion on SVMs. I'd encourage you to think more about this in order to get better answers. $\endgroup$ – Suresh Venkat Sep 13 '11 at 10:49
  • $\begingroup$ Ok, thanks @Suresh, I'll try. (The goal is to improve Kmeans / bridge it to unsupervised SVM / understand the differences, but yes that's pretty vague.) $\endgroup$ – Denis Sep 13 '11 at 12:08
  • $\begingroup$ @Denis: Yes, and I think that makes sense (I've thought about that myself), but for this forum some specificity would help. $\endgroup$ – Suresh Venkat Sep 13 '11 at 12:58

Since k-means minimizes the within-cluster sum of squares, the cluster centers will always be the mean of the points within that cluster. If you use a different criterion, you are basically using a different method than k-means.

  • $\begingroup$ Rephrasing the question, is there a way of modifying the simple iterations of Kmeans to converge to e.g. SVM weights ? You're right, this would of course not be standard Kmeans. $\endgroup$ – Denis Sep 14 '11 at 8:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.