1
$\begingroup$

I am using k-means clustering algorithm to cluster one-dimensional numeric data set. As far as I know k-means is sensitive to the initialization of the centroids. However, in my case I get the same result, no matter which centroids have been chosen.

Is it because I am clustering one-dimensional dataset ?

Is it safe to say that k-means is not sensitive in case of one-dimensional clustering ?

$\endgroup$
  • $\begingroup$ are you sweeping cluster count (k) and using something like AICc to compare fits? $\endgroup$ – EngrStudent Oct 29 '17 at 23:12
2
$\begingroup$

It could also be because your clusters are particularly well separated. Plot your data to see the clusters. With one dimension that's very intuitive (to the point that you almost don't need an algorithm).

$\endgroup$
0
$\begingroup$

Even in 2d and 3d it is fairly common to see the same result repeatedly on well behaved data.

But in 1d, the problem does get much simpler. There are algorithms to find the optimum clustering in 2d, that won't work in higher dimensionality.

For k=2, after sorting the data (in O(n log) ), I can even enumerate all possible solutions in just O(n) additionally to sorting - and sorting is cheap. This will not work in higher dimensional data. But in particular outliers can be much more problematic in multiple dimensions.

$\endgroup$
  • $\begingroup$ this is maybe a silly question but by 1 dimensional data do you mean a point(or vector) in n dimensions? i.e the data can be represented as one column vector of size (n x 1). $\endgroup$ – atomsmasher Oct 29 '17 at 23:05
  • $\begingroup$ One one row data, you can't cluster except the trivial (cluster 1 = row 1) solution. $\endgroup$ – Anony-Mousse Oct 30 '17 at 7:59
0
$\begingroup$

The answer is no, because it's easy to construct an example that is sensitive to the initial centroid guesses. For example, suppose your data has some points with values close to 1, a similar-sized bunch of values close to 5, and a single point at 3. For k=2, whichever initial centroid is closest to 3 will initially claim the point at 3, and will retain it in the next iteration and the algorithm will terminate.

That's enough to answer the question, but I'd also suspect that in any situation where the "actual" number of clusters differs from the chosen k, you'd get this type of behavior as well. For instance, if there are "really" 3 clusters but k=2, the closest initial centroid guess to the middle cluster will grab and keep the biggest number of those, maybe all of them because the initial "losing" centroid will keep moving towards the extreme, and the initial "winning" centroid will move closer to the middle.

So, your data may naturally always converge to the same answer, but that's not necessarily always the case.

$\endgroup$
0
$\begingroup$

It obviously depends on data, as pointed by gms. I only have one additional comment - one dimensional data have less degrees of freedom (well...), so intuitively (and maybe naively) there are less places where 'middle' points can be - so for example random data would be more likely to be stable for some k. I have no idea how formally correct is this, but it just seems natural to me.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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