# Hyperspherical nature of K-means and similar clustering methods

Jain, Murty, and Flynn state in their article Data Clustering: A Review all squared error based clustering methods like K-means tend to generate hyperspherical clusters.

However, they do not give a theoretical justification for this.

1. Is a theoretical justification for this observation?
2. Can we change the K-means algorithm to generate rectangular clusters?
• Is the claim that squared error-based clustering measures generate clusters that look like spheres ? I'm not sure what that means. – Suresh Venkat May 20 '13 at 5:02
• I am guessing that means the clusters look like spheres. Typically, the illustrations for K means in this paper represents clusters by ellipses. Then again, it uses a term "hyperellipsoidal"(and tells that certain algorithms produce such cluster shapes, but not K means). Therefore, I am not sure. – rivu May 20 '13 at 13:56

K-means tends to create compact clusters, which means that geometrically, the distance between every two points is small.

K-means can create clusters which are ball-like if you use $L_2$ norm, pyramid if you use $L_1$ and hypercubes if $L_\infty$ is used.

As opposed to that there are clustering algorithms which first project the data into lower dimension (such as spectral clustering), which means not all of the points in a cluster has to be close, but rather "connected" via other points in the original space, which will make them close after the projection.

This allow you to find very nice looking clusters, such as this and that.

If I guessed really well, hyperspherical will mean that the clusters generated by k-means are all spheres and by adding more elements/observations to the cluster the spherical shape of k-means will be expanding in a way that it can't be reshaped with anything but a sphere.

Then the paper is wrong about that,

even that we use k-means with bunch of data that can be in millions, we are still able to create a cube or any other shape in a three-dimensional space or higher with this data. Let's say that I added a filter for the pre-processing step that will make the observations be filled up into two clusters withing 3D space accordingly to shape a cube for the first cluster and a pyramid for the second one. you can keep adding observations till you have the previous shapes embodied perfectly.

yes, this might seem extremely hard. However, it is still possible. Therefore, we can't say that k-means will only generates spheres' shapes.

What I want to point out here is that you can force-shape the clusters if you like. even that it is just useless to do so. but as any other data-mining algorithm, k-means needs a pre-processing before using it. Thus, we can play around with our observations to get any shape for our clusters. But once again, THIS IS NOT USEFUL IN ANY CASE.