I'm really confused on what are the steps on how to perform k-means clustering algorithm on 1 dimension data. So suppose I have the following array of data and it should be clustered in two groups:

data = [40, 20, 30, 10, 22, 94, 66];

I have read the following site and it helped me get an idea on how to approach it but I'm still a little unsure. http://www.macwright.org/2012/09/16/k-means.html

My approach is:

  • I would first calculate the mean of the entire dataset.
  • then I would find calculate the euclidean distance between each point and the mean.
  • then I would cluster them in to two groups, one group that had the shortest distance to mean and the other that wasn't so close.

My question is are these steps correct and how would I perform k-means clustering on the dataset if k>2. I feel like my thinking is flawed, any help would greatly appreciated.


migrated from stackoverflow.com Jul 13 '15 at 1:54

This question came from our site for professional and enthusiast programmers.

  • $\begingroup$ If you want to look at an actual implementation you can check out my K-harmonic means implementation in MATLAB: iristoolbox.codeplex.com/SourceControl/latest#+irisoptim/…. Some of the code uses functions like bsxfun for performance reasons but it should be pretty readable given the comments. $\endgroup$ – Michael J Jul 12 '15 at 21:00
  • $\begingroup$ I'm just confused on how I would initially chose the cluster centre if k>2, since I can't hardcode any values. $\endgroup$ – beginnerCoder Jul 12 '15 at 21:11
  • $\begingroup$ I'm concerned about the close votes. Algorithm discussions are certainly on-topic. K-means is a very frequently used algorithm, not just for stats: machine learning and graphics for example. This is a reasonable (albeit simplistic) question. $\endgroup$ – Gene Jul 12 '15 at 22:51
  • $\begingroup$ May be in being overly simplistic, can median, mean, inter quartile range help find clusters? $\endgroup$ – forecaster Jul 13 '15 at 2:57

Given your points array (incidentally, your name clusters is not that great for it IMHO), k-means could work as follows:

  • Choose initial cluster centers; for the case of two clusters, say you randomly chose the initial cluster centers are [22, 60] (more on this below)

  • Now iterate; repeatedly:

    • For each point, assign it to the cluster with the nearest center.

    • Now you have your clusters. The centers are defined to be the means of the points within each cluster.

You can stop the iteration, e.g., the first time the assignment of points to clusters does not change.

How to choose the initial cluster centers? There are a number of methods:

  • The simplest is just to use uniform random assignment

  • A more sophisticated method is to use non-uniform random assignment, e.g., by using the k-means++ algorithm

Given that k-means (and the k-means++ variant) are so mainstream, there's really no reason to implement them (although it's always good to understand stuff). I suggest you search for a relevant package for your language.


Your Answer

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