0
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • $\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, 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$
    – Suresh Venkat
    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$
    – Suresh Venkat
    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
    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$
    – Suresh Venkat
    Sep 13, 2011 at 12:58

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\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, 2011 at 8:26

Your Answer

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

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