<p>Since k-means minimizes the within-cluster sum of squares, the cluster centers will <em>always</em> 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.</p>

CC BY-SA 3.0
2011-09-14T08:26:54.787Z
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.
Denis
CC BY-SA 3.0
2011-09-13T14:10:18.907Z
2011-09-13T14:10:18.907Z
johanvdw
<p>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 <a href="http://en.wikipedia.org/wiki/Kmeans" rel="nofollow">K-means</a>,
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.$$</p>

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

<p>As Suresh Venkat points out, "better" splitting,
better classification, is hard to define.</p>

CC BY-SA 3.0
2011-09-12T14:08:50.100Z
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
CC BY-SA 3.0
2011-09-12T17:01:11.377Z
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
CC BY-SA 3.0
2011-09-13T10:49:33.537Z
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
CC BY-SA 3.0
2011-09-13T12:08:06.637Z
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
CC BY-SA 3.0
2011-09-13T12:58:46.197Z
@Denis: Yes, and I think that makes sense (I've thought about that myself), but for this forum some specificity would help.
Suresh Venkat
<machine-learning><clustering><svm>
K-means with centres outside the data?
Denis
# K-means with centres outside the data?

(Asked by: username_0 on 2011-09-12)

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](http://en.wikipedia.org/wiki/Kmeans),
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.

**Tags:** machine-learning, clustering, svm
> **Comments:**
> **username_1**: 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?  
> **username_2**: 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 ?  
> **username_2**: 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.  
> **username_0**: 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.)  
> **username_2**: @Denis: Yes, and I think that makes sense (I've thought about that myself), but for this forum some specificity would help.  

---

## 1 answers

### Answer by username_3 on 2011-09-13. Score: 2

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.

> **Comments:**
> **username_0**: 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.  

---

