hyperspherical nature of K means (and other squared error clustering method)

This famous paper points out that any squared error based clustering method (K means being the most common example) tends to generate hyperspherical clusters. However, it does not point to a theoretical justification.

I would like to know: 1. If there is a theoretical justification for this observation. 2. If the K-Means algorithm can be changed to generate rectangular clusters.

Well, mathematically, k-means clusters are not spherical, but Voronoi cells.

However, the claim is not invalid, as the actual data usually does not fill the whole cell, but if you'd take the convex hull of the data it indeed is somewhat spherical in nature.

The reason probably is that when minimizing variance (and k-means minimizes the in-cluster variance, aka: sum of squares) you do also minimize euclidean distances: the squared euclidean distance is the sum of squares. And since the square root does not change ordering (it's monotone!) the assignment rule of k-means definitely prefers spherical clusters, by implicitly preferring Euclidean distance assignment.

Yes, k-means can be changed. Use k-medoids/PAM with maximum norm then (don't just exchange the norm - you may lose convergence. K-medoids/PAM is guaranteed to converge with arbitrary distances!)

Still, the result will not enforce a rectangular shape of clusters. They may still overlap in unexpected ways. The result will likely look like this (actually, rotated by 45 degree, but obviously this does not change the nature much - a strong preference for 45 degree angles):

• Thanks. Can you please point me to a paper which explains this a bit formally? – rivu May 20 '13 at 14:03
• No, I don't know any. There are way too many papers on k-means, unfortunately, despite it being actually a quite boring optimization task. And too many just repeat things they read somewhere, often without giving the sources themselves. – Has QUIT--Anony-Mousse May 20 '13 at 14:08

Here is one way that one might think of k means in terms of hyperspheres. A point $x$ belongs to the cluster centered at $c \in CENTERS$ if there exists a radius $r$ such that $x$ belongs to the ball centered at $c$ of radius $r$ but does not belong to the ball radius $r$ centered at any $c' \neq c \in CENTERS$. What this means, intuitively, is that clusters gobble up points by looking around themselves in a sphere. As pointed out elsewhere, this does not imply that the shape of the cluster is a sphere, but this is an artifact of the fact that we make a discrete cutoff for membership in a cluster. If one considers the undiscretized membership scores (which are basically just the $L_2$ distances) as the real metric of interest, then clusters will look like a ball, in the sense that the set of all points that are at least $l$ "like" a cluster center is a ball.

• @user20160 This definition exactly corresponds to a voronoi tesselation of space. Proof left as exercise for the reader. :) – Him Apr 5 '18 at 15:13
• Yes, I misread your post. Cheers and +1 – user20160 Apr 5 '18 at 15:40