k-Means - how to choose k

After you understood how the basics of the  k-Means-Algorithm works, you will be wondering:
Into how much clusters should I devide the data, or in other words, how should I choose k?

Unfortunately there is no general approach to choose k.
Consider the following data:

If I choose k=2 the result could look like this:

If I choose k=3, it could look like that:

The higher you choose k the smaller will be the distortion (except the case the algorithm stucks in some local minimum for the distortion). So the lowest distortion will be creating a cluster for every point. But this would obvious not solve any problem. So when should I stop?
This depends a lot on the business scenario. In general you will be able to estimate borders for k in the description of the usage of your analysis, typical examples are market segmentations in which the requirement is e.g. to find different customer profiles, so k is usually a small number (2-7).

k-Means - How to initialize

When you study the k-Means-Algorithm and understand, how it works, a natural question that ariese is:

How can you choose the starting points in order to get the best fit into k clusters?

In order to answer the question, it is important to define, what a "good fit" means. In the context of k-Means the best fit is the distribution of the data into k different clusters so that the sum of the distances to the corresponding cluster centers (the so called "distortion") is minimal.

For up to 10 Clusters the common way to find the best fit is the following:
Choose k different points of the dataset randomly as initial cluster centers. Then run the algorithm and calculate the upper mentioned distortion.

Run the k-Means-Algorithm often (100-1000 times, providing that you have enough data points) and choose the one with the lowest distortion.


By this approach, you can also avoid the situation in which no point is assigned to a cluster center (in this case you could randomly initialize the center again or directly remove it).

The k-Means Algorithm - Basics

Unsupervised Learning tries to find structures in datasets, one method to do so is by clustering the data. The most popular and widely used algorithm therefore is the k-Means-Algorithm.
k thereby stands for the number of clusters in which the data to be analyzed is to be devided. Lets start with an 2-dimensional example, imagine that we have the following set of data:

Suppose we want to cluster this data into different groups. On the first sight we see two separate clusters:

So this is what we want to achieve for general set of data, therefore we use the k-Means-Algorithm with K = 2. Now how does it work:

First of all initialize the data, therefore we choose two random points in the test area (for a better choice see this post), lets say those two points indicated by a "X":

Now run the following two steps in a loop:

1. Assign each point to the cross that lies nearest to it (in general this is not unique, in such cases just select one)

2. Move each cross to the center of the average (means) of the assigned points

Going on with step 1...

... and step 2 ...

...brings us into this situation:

Now further steps will not change the assignment of the cluster centers anymore => the k-Means-Algorithm converged.

Note that the algorithm is continuously improving the sum of the distances between the center and the data points by choosing the assignments with the smallest distance (step 1) and moving the centers (step 2). However the assignments on a converged k-Means-Algorithms do not have to be the same for every run (depending on the starting points). 

Two questions arise (click to see the answer): 

• How do I initialize the data?
• How should I choose k?