1
$\begingroup$

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?
Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ Is the claim that squared error-based clustering measures generate clusters that look like spheres ? I'm not sure what that means. $\endgroup$
    – Suresh Venkat
    May 20, 2013 at 5:02
  • $\begingroup$ 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. $\endgroup$
    – rivu
    May 20, 2013 at 13:56

2 Answers 2

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
0
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.