K mean clustering algorithm on 1D data

Question

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.

Answer 1

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.