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

<p>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.</p>

<p>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.</p>

<p>This allow you to find very nice looking clusters, such as <a href="http://www.google.co.il/url?sa=i&amp;rct=j&amp;q=&amp;esrc=s&amp;source=images&amp;cd=&amp;cad=rja&amp;docid=ogH1R431jJ1XLM&amp;tbnid=m7zD7fzjrmkL2M%3a&amp;ved=0CAUQjRw&amp;url=http://www.ml.uni-saarland.de/code/pSpectralClustering/pSpectralClustering.htm&amp;ei=RTkMU7e7IMnHtQa-9IC4Bg&amp;bvm=bv.61725948,d.bGQ&amp;psig=AFQjCNG0Zl4W0k2Q0wDQ4W3EwcfWaA4YqQ&amp;ust=1393396411836861" rel="nofollow">this</a> and <a href="http://www.umiacs.umd.edu/labs/cvl/pirl/vikas/projects/projec7.gif" rel="nofollow">that</a>.</p>

CC BY-SA 3.0
2014-02-25T06:34:59.150Z
2014-02-25T06:34:59.150Z
R B
<p>If I guessed really well, hyperspherical will mean that the clusters generated by <code>k-means</code> are all spheres and by adding more elements/observations to the cluster the spherical shape of <code>k-means</code> will be expanding in a way that it can't be reshaped with anything but a sphere.</p>

<p>Then the paper is wrong about that,</p>

<p>even that we use <code>k-means</code> 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 <code>observations</code> 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.</p>

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

<p>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, <code>k-means</code> needs a pre-processing before using it. Thus, we can play around with our <code>observations</code> to get any shape for our clusters. But once again, THIS IS NOT USEFUL IN ANY CASE. </p>

CC BY-SA 3.0
2013-09-26T07:37:35.013Z
2013-09-26T07:37:35.013Z
mamdouh alramadan
<p>Jain, Murty, and Flynn
state in their article <a href="http://www.cs.rutgers.edu/~mlittman/courses/lightai03/jain99data.pdf" rel="nofollow">Data Clustering: A Review</a>
all squared error based clustering methods like K-means 
tend to generate hyperspherical clusters. </p>

<p>However, they do not give a theoretical justification for this.</p>

<ol>
<li>Is a theoretical justification for this observation?</li>
<li>Can we change the K-means algorithm to generate rectangular clusters?</li>
</ol>

CC BY-SA 3.0
2013-05-20T05:02:31.817Z
Is the claim that squared error-based clustering measures generate clusters that look like spheres ? I'm not sure what that means.
Suresh Venkat
CC BY-SA 3.0
2013-05-20T13:56:15.033Z
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
<machine-learning><clustering>
Hyperspherical nature of K-means and similar clustering methods
rivu
# Hyperspherical nature of K-means and similar clustering methods

(Asked by: username_0 on 2013-05-20)

Jain, Murty, and Flynn
state in their article [Data Clustering: A Review](http://www.cs.rutgers.edu/~mlittman/courses/lightai03/jain99data.pdf)
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?

**Tags:** machine-learning, clustering

> **Comments:**
> **username_1**: Is the claim that squared error-based clustering measures generate clusters that look like spheres ? I'm not sure what that means.  
> **username_0**: 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.  

---

## 2 answers

### Answer by username_2 on 2014-02-25. Score: 1

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](http://www.google.co.il/url?sa=i&rct=j&q=&esrc=s&source=images&cd=&cad=rja&docid=ogH1R431jJ1XLM&tbnid=m7zD7fzjrmkL2M%3a&ved=0CAUQjRw&url=http://www.ml.uni-saarland.de/code/pSpectralClustering/pSpectralClustering.htm&ei=RTkMU7e7IMnHtQa-9IC4Bg&bvm=bv.61725948,d.bGQ&psig=AFQjCNG0Zl4W0k2Q0wDQ4W3EwcfWaA4YqQ&ust=1393396411836861) and [that](http://www.umiacs.umd.edu/labs/cvl/pirl/vikas/projects/projec7.gif).


---

### Answer by username_3 on 2013-09-26. Score: 0

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.


---

