Determining the Number of Clusters Using the Elbow and the Knee Techniques

Two techniques to determine the number of clusters in a dataset are called the elbow technique and the knee technique. They’re really just slight variations of the same idea. Here’s an example.

First of all, let me note that there is no practical, purely analytic technique to determine the number of clusters in a dataset. All techniques to determine the number of clusters are subjective.

To demonstrate the knee and elbow techniques, I created a simple dataset with 20 items, where each item has 2 elements (the dimension). The data was constructed so that there are clearly 3 clusters. In a realistic scenario, where data has 3 or more dimensions, you can’t easily graph the data like this.

My demo dataset has 3 clear clusters. Real-life data usually isn’t so nice.

The elbow and knee techniques are based on within-cluster sum of squares (WCSS) which is a measure of variability. Suppose you have a cluster that has 4 data points with dimension 2:

(0.20, 0.60)
(0.30, 0.90)
(0.40, 0.50)
(0.70, 0.80)

The cluster mean is (0.40, 0.70). The sum of squared deviations for the first data item in the cluster and the mean is (0.20 – 0.40)^2 + (0.60 – 0.70)^2 = 0.04 + 0.01 = 0.05. The SS for the other three data items are 0.05, 0.04, 0.10 and so the WCSS for the cluster is 0.05 + 0.05 + 0.04 + 0.10 = 0.24. If you have several clusters, the total WCSS is just the sum of the WCSS for each cluster.

For a given dataset, the more clusters there are, the smaller the value of the total WCSS will be. In the extreme, if you have the same number of clusters as there are data items, then the WCSS for each cluster will be 0.00 and the total WCSS will be 0.00. Or if you have just one cluster, the total WCSS is the largest it can be for the dataset.

The idea of the elbow technique is to compute the total WCSS for k = 1, k = 2, k = 3, and so on. When you graph the total WCSS values, the values will get smaller very quickly at first, but at some value of k there won’t be much improvement. This value of k, at the point that looks like the bend of an elbow, indicates the number of natural clusters in the data.

The elbow technique and the knee technique to determine the number of clusters in a dataset are pretty much the same.

The knee technique is exactly the same but instead of graphing the total WCSS for each value of k you graph the percent of variability explained (which is exactly equivalent to the percent of variance explained). The motivation is that the magnitudes of WCSS values depend on the dataset but percent of variability is just percentages and so those values can be more easily compared when looking at different datasets. Put another way, percentage of variability explained is sort of like normalized WCSS.

For the demo data the total WCSS values for k = 1 through 9 are:

k      WCSS
1      0.1111
2      0.0317
3      0.0072
4      0.0053
5      0.0039
6      0.0026
7      0.0021
8      0.0017
9      0.0015

The 0.1111 is the total variability in the data. The percent of variability explained by k = 2 is (0.1111 – 0.0317) / 0.1111 = 71.47%. The percent of variability explained by k = 3 is (0.1111 – 0.0072) / 0.1111 = 93.52%. And so on. Notice that the variability explained by k = 1 is zero which makes sense if you think about it. When graphed, the percentages of variability explained look like a bent leg and a good value for the number of clusters in the dataset is at the knee.

The variance is just the variability divided by the degrees of freedom = n-1 = 19. But if you divide all the WCSS values by 19 or by any constant, the percent values won’t change. So percent of variability explained is the same as the percent of variance explained.

For the example data, by looking at either graph you can see there are 3 clusters. Unfortunately, the elbow / knee technique isn’t magic – most elbow and knee graphs from real-life data aren’t so clear.

I absolutely love magic! Here are three of my favorite magic shops. Left: Houdini’s has four stores in Las Vegas. This one is in the Venetian Hotel shopping area. Center: The Main Street Magic Shop has been in Disneyland in Anaheim since 1957. I worked at Disneyland when I was a college student and got to walk by the Magic Shop every day. Right: The Market Magic & Novelty Shop is in the Pike Place Market in downtown Seattle. It’s fantastic. I live in the city of Issaquah which is about 20 miles away from Seattle.