Introduction
Plato (yes, that Plato) used to talk about cutting the world at its joints. The phrase refers to a butcher that finds the natural places at which to separate an animal. When separating anything, you could hack it into arbitrary groups — or you could try to find the seams, the intrinsic divisions.
Clustering is like trying to cut data at its joints, i.e. trying to find the natural divisions.
More formally, clustering is a family of unsupervised machine learning methods for assigning groupings to populations of data. This means that there are no predetermined groupings, and there’s no set of correctly grouped examples from which we try to learn. We simply take the data, look at its intrinsic similarities and patterns, and assign groupings (clusters) that are meant to help explain the data as well as facilitate decision making and action taking.
There are countless applications for clustering algorithms: pattern recognition, data mining, image and signal processing, customer segmentation, recommendation systems, anomaly detection, genomic data analysis, social network analysis, and plenty more. A solid understanding of clustering is as relevant as an understanding of virtually any other machine learning technique.
In this project, I’ll discuss the data generically, just as data with two variables. For a practical interpretation, we can think of this clustering in the context of customer segmentation. We’ll try to divide customers with regard to two of their features: the number of orders in the past twelve months, and the size of those orders.
The most common clustering algorithm is called k-means and is a simple and efficient way of grouping data based on similarity. Gaussian mixture modeling is about finding the right set of normal (Gaussian) distributions that can account for generating the data. DBSCAN is in search of relatively dense portions of the data, i.e. points that are more similar to each other relative to the overall data set. This might all sound complicated, but don’t worry! The following explanation will break it down in a simple way!
The plot on this page lets you play around with these algorithms and the data sets below for yourself. The buttons throughout set it up to match the discussion.
Different shapes of data
If all data was the same, then we wouldn’t need multiple methods. (Well, we wouldn’t really need methods at all.) But it isn’t, so we do. Below are four different data sets. They are generated in ways that highlight (at least some of) the features of the methods. So while they are not real world data sets, they provide the understanding you need for making decisions on real world data sets.
Clustering methods
K-means clustering
The k-means method is all about k (surprise, surprise). The goal is to find k clusters, and this is done by identifying k centers of the clusters. The rest of the points are grouped by which center they are closest to.
The centers are found with a simple loop. Start with k centers, assign each point to its closest center, move each center to the average of its points, and repeat until no point changes clusters. Each pass can only shrink (or keep) the total squared distance between the points and their centers, so the members of each cluster become more alike. Where the loop ends up can depend on where the centers start, which is what the “New starting centers” button is for.
This method is great for data sets like the first one. The subsets are each evenly distributed around a well defined center. Use the k slider to see what happens with other values of k.
The second data set is also fairly well naturally separated. Clusters 3 and 4 (on the right) meet at a natural border. However cluster 1 (the long diagonal group) is a bit less defined. This often happens when there aren’t clear divisions in the data, i.e. it is continuous. In those cases, there isn’t a clean split, and a line in the sand must be drawn (like where clusters 1 and 2 meet).
The clustering of the third data set has some benefits as well as limitations. It misses that there are four naturally occurring groups that are pretty clearly separated by blank space. Instead, it breaks each of those in half and combines them. There may be some contexts where this is relevant, but it will be useful to find an algorithm that captures the more natural grouping.
The clustering of the fourth data set is similar to that of the third. The data points within groups are indeed more similar to each other than members of other groups, but again, the apparent sine waves are ignored.
Gaussian mixture modeling
Gaussian mixture modeling assumes that the data in question is generated by normal distributions, i.e. a bunch of bell curves. The clustering is determined by which bell curve most likely generated which data point.
The bell curves are found with a loop much like the one k-means uses (this one is called expectation-maximization). Each point gets a probability of having come from each bell curve, and then each bell curve is re-fit to the points, weighted by those probabilities. The ellipses on the plot outline each bell curve at 1 and 2 standard deviations, and paler points are the ones the model is less sure about.
The number of bell curves is chosen using the Bayesian information criterion (BIC), a score that rewards fitting the data well but penalizes using more bell curves. You can also set the number yourself.
Notice how this does just as well at the first data set. This is because the data is well separated, non-overlapping, and indeed generated by normal distributions.
The real value of GMM can be seen with the second data set. Notice how each of the clusters captures a normal distribution. Notice how cluster 1 now extends past where k-means drew its line, reaching down toward cluster 2. The scattered points at the bottom right don’t form a group of their own, but are seen as extremes of cluster 4’s bell curve.
Similar to k-means, the distributions break the intended clusters at the joint, but without combining them. In fact, the clustering finds precisely the 8 distributions which were used to generate the data. But like k-means, for better or worse, it doesn’t recognize that groups like 1 and 2 are connected.
Likewise, the fourth data set is also clustered into somewhat reasonable breaks, and depending on the situation, may be the right option. It may be relevant to consider the rise of a wave as a separate group from the fall that follows it. But again, it will be useful to see a method that is able to capture these misshapen clusters, separated by open areas.
While sometimes the members of a cluster are spread out (like the tail of cluster 4 in the second data set), there is an important sense in which finding the normal curves captures the natural divisions in a data set. This is especially true when the data is created by normal distributions, but also when analyzing things like sine waves. Notice how the clusters each capture a distinct correlation between the variables. If this is behavior over time, the clusters are separated by up swings and down turns.
That said, it is still useful to be able to form clusters regardless of the shape.
Density-based clustering (DBSCAN)
DBSCAN (density-based spatial clustering of applications with noise) is about, well, finding particularly dense regions of the data. The two parameters are epsilon (ε) and minPts, which together determine whether a set of data points constitute a cluster. The idea is that if there are enough points (minPts) within a certain distance (ε) of a point, then that point sits in a dense region and is called a core point. Core points within ε of each other are chained together into one cluster, along with any points close enough to the chain. This means that some points, if they aren’t close enough to others, don’t belong to any cluster. For labelling purposes, we put them in “cluster 0.” The idea is that we can think of these points as outliers, not belonging to any natural category.
Notice how DBSCAN doesn’t find four clusters in the first data set. This depends on the parameters, but it’s difficult for it to fully combine the right points and only the right ones. Increasing epsilon too much makes it quickly collapse into a smaller number of clusters, while too small of an epsilon leaves everything as noise (nothing is close enough). The same is true for the minimum points. Be sure to play around with how the parameters work!
These limitations are more prevalent on the second data set. Notice how the method doesn’t acknowledge the bell curves in the data: three of the four groups become one big cluster, because dense stretches of points connect them. If there is a dense enough portion of data, a cluster is formed, no matter the shape.
This ability to find clusters of any shape allows it to have unique benefits for the last two data sets. Notice how the third data set has four main clusters that each have a distinct angle in them. But that doesn’t stop the data on either side of that angle from being part of the same cluster. Also note that there are a few outliers (cluster 0).
The same is true for the sine waves in the fourth data set. The algorithm is able to separate the data into three main clusters along with outliers. It doesn’t matter the shape of the clusters, just whether or not there are enough neighbors close by (i.e. whether the data is dense enough in a particular region).
With this in mind, sometimes DBSCAN is a great interactive tool to understand one’s data. Not merely for finding distinct clusters, but for actively scanning for where the dense portions of the data are.
Conclusion
Unlike how Plato thought of finding natural divisions, there is no one specific clustering that will be perfect for all situations. Each of these methods has pros and cons. I have mainly focused on the shapes of data that each can capture, but there are other considerations like computation time and resource usage. For large data sets, these start to be significant concerns. But still, the most important thing to understand about these methods is how they work and what they presume about the data.
K-means is about finding groups of similar points. Similarity is what’s most important — that the members of the groups are as alike as possible. GMM assumes that the data is generated by normal distributions, and its goal is identifying them. Like we saw with the second data set, a cluster can stretch out to include far-off points, so long as they plausibly come from the same distribution. Finally, DBSCAN is about finding thick areas of the data points, ignoring portions where the data is too sparse.
To decide which method is right for a situation, consider what you’re trying to figure out about the data, what you want to do with it. For instance, clumping together data points that are more similar (k-means) can be useful for things like customer segmentation, where targeted strategies work more efficiently the more homogeneous the subgroup is. GMM is great for gaining a better understanding of the underlying causes of the data. While its groupings don’t minimize the variance within clusters the way k-means does, they do present an idea of the natural joints in nature that are producing the data. Finally DBSCAN can be great for finding signal through noise or otherwise just finding particularly interesting combinations of variables.
It’s best to try multiple methods and play around with each of their parameters. In addition to yielding an actionable grouping for whatever the task, the process itself provides invaluable insight into the data.