# K-means with centres outside the data?

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.

• 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? – James King Sep 12 '11 at 14:08
• 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 ? – Suresh Venkat Sep 12 '11 at 17:01
• 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. – Suresh Venkat Sep 13 '11 at 10:49
• 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.) – Denis Sep 13 '11 at 12:08
• @Denis: Yes, and I think that makes sense (I've thought about that myself), but for this forum some specificity would help. – Suresh Venkat Sep 13 '11 at 12:58