I read on the cluster analysis page of wikipedia:

For example, k-means clustering can only find convex clusters, and many evaluation indexes assume convex clusters. On a data set with non-convex clusters neither the use of k-means, nor of an evaluation criterion that assumes convexity, is sound.

I can't see how an evaluation index assumes convex clusters. Can anyone illustrate this idea?


1 Answer 1


The easiest way to see why the clusters are convex in $k$-means is by appealing to the corresponding Voronoi diagram. If we have $k$ clusters, then there will be $k$ corresponding cells. Let us see how each cell is defined. Let's say that the cluster centers (means) are $\mu_1, \mu_2, \ldots, \mu_k$, all in $\mathbb{R}^d$. Recall that $k$-means uses Euclidean distance. Now, any point that is in cluster 1 must be closer to $\mu_1$ than $\mu_2$. Hence, it must belong to the set $$ A_{1,2} = \{x \in \mathbf{R}^d: \|x - \mu_1\|^2 \leq \|x - \mu_2\|^2\} , $$ which is equivalent to $$ A_{1,2} = \{x \in \mathbf{R}^d: \|x\|^2 - 2 \langle x, \mu_1 \rangle + \|\mu_1\|^2 \leq \|x\|^2 - 2 \langle x, \mu_2 \rangle + \|\mu_2\|^2\} . $$ But this is just $$ A_{1,2} = \{x \in \mathbf{R}^d: \langle x, 2(\mu_2 - \mu_1) \rangle \leq \|\mu_2\|^2 - \|\mu_1\|^2 \} , $$ which is a closed half-space.

Now, any point is in cluster 1 if and only if it is in $A_{1,2}, A_{1,3}, \ldots, A_{1,k}$ (where the latter sets are defined analogously). So, the set of points in cluster 1 is an intersection of half-spaces and therefore convex (and the same holds for any other cluster).


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.