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
    Commented Sep 12, 2011 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$ Commented Sep 12, 2011 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$ Commented Sep 13, 2011 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
    Commented Sep 13, 2011 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$ Commented Sep 13, 2011 at 12:58

1 Answer 1


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
    Commented Sep 14, 2011 at 8:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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