Clustering

Clustering (or cluster analysis) is the process of organizing a collection of data points into groups, referred to as clusters, such that points within the same cluster are more similar to each other than to points in other clusters. Clustering is one of the classic tools of exploratory data analysis, because it can help us detect structure in data even when we do not yet know exactly what we are looking for.

In practice, clustering can be useful in many different situations. It can help us explore data, summarize large datasets, identify subgroups, support anomaly detection, and sometimes serve as a preprocessing step for later analyses. At the same time, clustering is not a single, clearly defined task with one universally correct solution. Different clustering algorithms define clusters in different ways.

Introduction¶

What is clustering?¶

Clustering aims to divide data points into groups in a meaningful way. Usually, we hope that points within the same cluster share important properties or are close to one another according to some notion of similarity. In some simple examples, this can look almost trivial. In Figure 1, most people would probably agree that the points fall naturally into three groups. At least so far, I have not yet had a student answer anything other than “three” when asked how many clusters they see in this dataset.

Still, even in such apparently simple situations, there is already an important conceptual point hiding in the background: what exactly counts as a cluster? Is it a dense cloud of points? A group around a center? A region separated by empty space from other regions? Different clustering algorithms answer these questions differently.

To make this concrete, let us first create a simple synthetic dataset with three clusters.

We visualize the dataset using pyplot. The dataset contains three visually distinct clusters.

Assigning the three clusters in this case does not exactly feel like rocket science. We could all do this manually with a pen in no time. So why do we need clustering algorithms at all?

There are at least two important reasons. First, real datasets often do not form such clean and clearly separated groups. Second, and even more importantly, most data is not two-dimensional. The number of features determines the dimensionality of the data, and in practice that is often much larger than two. Once data lives in 5, 10, 50, or 500 dimensions, visual inspection is no longer enough.

This is why we need algorithms: to cluster data systematically, reproducibly, and at a scale that would be impossible to handle manually.

Why do we want to cluster data?¶

Clustering is useful for several reasons. One important use is data exploration. Clustering can reveal subgroups, structures, and patterns that are not immediately obvious. In many real datasets, this can already provide valuable first insights.

Another common use is summarization. A large dataset may be difficult to understand point by point, but easier to reason about when it is divided into a few representative groups. This can be helpful in reporting, visualization, or later model building.

Clustering can also support anomaly detection. If most observations form coherent groups, then points that do not fit well into any cluster may deserve special attention. In some applications, those points correspond to errors, fraud, rare events, or otherwise interesting cases. We will see more on this in Outlier Detection.

And finally, clustering can sometimes serve as a preprocessing step. Once data has been organized into groups, later analyses may become easier or computationally cheaper.

A classic example is customer segmentation. Customers with similar behavior or preferences may form useful groups for recommendation systems, communication strategies, or product development. But similar ideas also occur in biology, medicine, document analysis, image processing, and many other fields.

Hard and Soft Clustering¶

The most common type of clustering is hard clustering, where each data point is assigned to one cluster only. O, in some methods, possibly to no cluster at all if it is treated as noise. In soft clustering, by contrast, a data point can belong to several clusters with different degrees of membership. An example of soft clustering is shown in Figure 2.

In this introductory chapter, unless stated otherwise, we will mainly focus on hard clustering. Later, in the next chapter, we will return to soft clustering with Gaussian mixture models.

Mini-exercise¶

Team up with your neighbor (if in class), or try on your own: Look again at the data shown in Figure 1. How would you design an algorithm that automatically assigns each data point to a cluster?

Think about questions such as:

• How could we decide whether two points are “close enough” to belong together?

• Would you look for cluster centers, cluster boundaries, or dense regions?

• How should the algorithm deal with isolated points?

Make a few notes and try to sketch a simple clustering rule or algorithm.

What did you come up with?

When I ask this question in class, students usually come up with a variety of good ideas. Some propose grouping points by distance, some by drawing boundaries, and others by looking for dense regions. That is exactly the point: there is no single universal notion of what a cluster is. Different clustering algorithms formalize different intuitions.

In the following, we will start with one of the most common and intuitive clustering algorithms: K-means.

KMeans¶

K-means is a centroid-based clustering algorithm. Its central idea is simple: each cluster is represented by a center point, called a centroid, and every data point is assigned to the nearest centroid.

How K-means works¶

To build an intuition, imagine that we want to sort fruits based on two features such as sweetness and size. Each fruit is a data point, and our goal is to divide the fruits into a fixed number of groups.

The basic K-means procedure looks like this:

The basic K-means procedure looks like this:

1. Choose the number of clusters First, we decide how many clusters we want. This number is called $K$.

2. Initialize the centroids We start with $K$ initial center points. In simple versions of the algorithm, these may be chosen randomly from the data (Figure 3 A).

3. Assign each point to the nearest centroid Every data point is assigned to the cluster whose centroid is closest. Often, this closeness is measured using the Euclidean distance (Figure 3 B).

4. Update the centroids For each cluster, we compute the average position of all points assigned to it. This new average becomes the new centroid (Figure 3 C).

5. Repeat We repeat the assignment and update steps until the assignments no longer change much, or until the centroid positions stabilize.

The result is a partition of the data into $K$ clusters.

In more technical terms, K-means tries to find cluster assignments that minimize the distances between data points and their assigned cluster centers.

K-means on the simple toy dataset¶

In the following sections, we will make use of the Scikit-Learn implementations of several different clustering algorithms. The workflow will therefore look very similar in all cases, with the most notable difference being the main parameters that each algorithm requires. More information on the code implementations can be found on the Scikit-Learn documentation.

We can apply K-means to our synthetic three-cluster dataset as follows:

We visualize the resulting clustering. Each cluster is shown with a different color.

This works very well here. But of course, this is still a very friendly example.

A slightly more difficult example¶

The next synthetic dataset is already a bit more realistic. The clusters are less cleanly separated, and the task becomes less obvious.

Once the clusters have been found (using the .fit() method as done above), we can also use a k-means model to make predctions on unknown datapoints.

We can also check the found cluster center points:

Strengths of K-means¶

K-means is popular for good reasons. It is relatively easy to understand, easy to implement, and often computationally efficient. For many practical problems, it is a very reasonable first clustering method to try.

It often works well when:

• clusters are compact,

• clusters are roughly round or isotropic,

• and clusters are of similar size.

Limitations of K-means¶

K-means is useful, but it comes with important assumptions and limitations.

The first major limitation is that we must specify the number of clusters beforehand. In many real problems, we do not know this number in advance. We can try several values of $K$ and compare the results, but there is no universally perfect method for choosing the right value.

A second important limitation is more subtle: K-means works best when clusters are roughly spherical, similarly sized, and not too different in density. In other words, it has a fairly specific built-in idea of what a cluster should look like. The scikit-learn example Demonstration of k-means assumptions illustrates this point very nicely: K-means works well on simple blob-like clusters, but can struggle when clusters are stretched, have very different variances, or have very unequal sizes ^[1].

The following variation shows the same idea.

This illustrates three important points:

• K-means works very well on simple blob-like clusters.

• It struggles when clusters are stretched rather than round.

• It can also struggle when clusters differ strongly in variance or size.

A further limitation is that K-means is sensitive to outliers, because cluster centers are based on averages. A few unusual points can pull a centroid away from where it would otherwise be.

Finally, the result can depend on the initial placement of the centroids. Modern implementations reduce this problem, for example through better initialization methods such as K-means++, but the issue does not disappear completely.

So K-means is a great first method to know and use, but it clearly cannot solve every clustering problem (spoiler: no single method can do that!).

DBSCAN (Density-Based Spatial Clustering of Applications with Noise)¶

K-means defines clusters through centers. DBSCAN takes a very different approach. It is a density-based clustering algorithm. Instead of looking for centroids, it looks for dense regions of points.

The full name is Density-Based Spatial Clustering of Applications with Noise, usually shortened to DBSCAN.

How DBSCAN works¶

The central idea is that points inside a dense region should belong to the same cluster, while isolated points may be treated as noise.

DBSCAN uses two key parameters:

• eps (epsilon): the maximum distance within which points are considered neighbors

• min_samples: the minimum number of neighboring points required to define a dense region

The algorithm then works roughly as follows:

1. Select a point
   Pick a data point and look at all points within distance eps.

2. Check whether it is a core point
   If at least min_samples points lie within that neighborhood, the point is a core point.

3. Expand the cluster
   Starting from this core point, DBSCAN expands the cluster by including neighboring points. If those neighboring points are themselves core points, the cluster grows further.

4. Add border points
   Some points may lie close to a cluster without being dense enough to be core points themselves. These can still belong to the cluster as border points.

5. Label noise
   Points that do not belong to any dense region are labeled as noise.

This makes DBSCAN especially attractive when clusters are not nicely round or when the data contains clear outliers.

DBSCAN on the same toy dataset¶

Using scikit-learn, DBSCAN can be applied very easily:

The role of the parameters¶

For DBSCAN, the choice of eps and min_samples has a very strong effect on the result. In practice, eps is often especially influential.

This shows an important lesson: DBSCAN can work very well, but only if its parameters match the scale and density structure of the data reasonably well.

Strengths of DBSCAN¶

DBSCAN has several attractive properties.

First, it does not require us to specify the number of clusters in advance. The clusters emerge from the data, depending on the density pattern. Second, it can identify clusters of arbitrary shape, which makes it much more flexible than K-means in many situations. Third, it can naturally identify noise points or outliers, rather than forcing every point into a cluster.

Limitations of DBSCAN¶

DBSCAN also has important limitations.

Its biggest weakness is that it struggles when different clusters have very different densities. A single choice of eps and min_samples may work well for one part of the data and poorly for another.

The following example illustrates this problem.

Here we see the central problem. With a small eps, the sparser clusters may be fragmented or partly labeled as noise. With a larger eps, denser and sparser regions may be merged too aggressively. In the example shown here, for instance, we cannot find an eps-setting able to properly detect both the two more distributed clusters and the two very dense clusters. This shows that DBSCAN can work very well when the density structure is suitable, but is generally less reliable when densities vary strongly across the dataset.

A second limitation is that DBSCAN becomes more difficult in high-dimensional spaces, where distance relationships become less informative. Like many clustering methods, it works best when the feature space has been chosen and scaled carefully.

Clustering on real data¶

So far, we have mainly used toy datasets to understand how clustering algorithms behave. Real datasets are usually messier. Before clustering them, we often need to think carefully about preprocessing, feature selection, scale, and the actual meaning of the variables.

Data preprocessing¶

Preprocessing is especially important for clustering because many clustering algorithms depend directly on distance calculations. If the features are not prepared in a meaningful way, the clustering result may become misleading. The following example shows what can go wrong if the data is not processed in the correct way.

In the scatter plot, we clearly recognize three clusters, but K-Means apparently fails.

The underlying reason is the feature scale of the data we used here. As we see on the x and y-axis, one feature ranges from 0 to 1, while another ranges from -10000 to 10000. If we cluster the raw data directly, the second feature will dominate most distance calculations, whether or not that is actually justified. This is why methods such as K-means often require standardization.

After standardizing the data, K-Means indentifies the three clusters as we would expect.

Another important preprocessing step is dealing with missing values. Most clustering algorithms cannot handle missing entries directly. Depending on the situation, we may need to remove incomplete rows, impute missing values, or drop variables with too many missing entries.

We also need to think carefully about outliers. For K-means in particular, outliers can have a strong influence because cluster centers are based on means. DBSCAN is often more robust here, but even DBSCAN can be affected if the scale of the data is distorted by extreme values.

Data preprocessing for clustering also includes checking data types and feature meaning. A variable that is technically numeric is not automatically suitable for Euclidean-distance-based clustering. Postal codes, IDs, and arbitrary category encodings are classic examples: they may look numeric, but treating them as continuous distances can be highly misleading.

Finally, preprocessing sometimes includes dimensionality reduction. In high-dimensional spaces, many points start to appear similarly far away from one another, which can make distance-based clustering much harder. Methods such as PCA can help reduce dimensionality while retaining important structure. We will return to this in later chapters (see Dimensionality Reduction).

Choosing meaningful features¶

Feature selection is especially important in clustering because clustering is an unsupervised task. There is no target variable telling the algorithm what we actually care about. So the choice of features strongly shapes what kind of clusters we will find.

If we cluster customers by age and income, we may get very different groups than if we cluster them by product preferences and website behavior. Neither result is automatically “wrong.” They simply reflect different questions. This is why clustering is often best understood as a dialogue between the data, the algorithm, and the question we ask.

A small real-data example¶

In practice, clustering is often applied not to synthetic point clouds, but to real tabular datasets with many variables. This brings us back to a recurring theme in data science: before applying a sophisticated method, we usually need to understand and prepare the data first.

For example, on a real customer dataset we might first:

• remove or impute missing values,

• choose only meaningful behavioral variables,

• standardize numerical features,

• and possibly reduce dimensionality.

Only then does clustering really become informative.

More on Clustering¶

Clustering is one of the central exploratory tools in data science. It helps us organize data into groups, uncover hidden structure, summarize complex datasets, and sometimes identify anomalies.

In this chapter, we looked at two important clustering methods.
K-means is a centroid-based method that is simple, intuitive, and often computationally efficient. It works especially well when clusters are compact, roughly spherical, and of similar size. But it requires choosing the number of clusters in advance and can struggle when clusters are elongated, unevenly sized, or strongly affected by outliers.

DBSCAN is a density-based method that can find irregularly shaped clusters and naturally identify noise points. It does not require choosing the number of clusters beforehand. However, it depends strongly on its parameters and can struggle when clusters differ strongly in density.

The main lesson is not that one of these algorithms is “best.” The main lesson is that different clustering algorithms define clusters differently. Good clustering therefore depends not only on running an algorithm, but on understanding the data, the assumptions of the method, and the purpose of the analysis.

K-means and DBSCAN are only two of many clustering approaches. In the next chapter, we will extend the picture by looking at Gaussian mixture models, which allow soft cluster membership, and hierarchical clustering, which builds a tree-like structure of nested groups.

For a broader overview of clustering methods, the scikit-learn clustering documentation is an excellent place to explore further examples and compare algorithms.

If you want a more general review article, one useful starting point is:

• “A review of clustering techniques and developments” by Amit Saxena and Mukesh Prasad and Akshansh Gupta and Neha Bharill and Om Prakash Patel and Aruna Tiwari and Meng Joo Er and Weiping Ding and Chin-Teng Lin, 2017, Neurocomputing, Vol.267, Saxena et al. (2017) Saxena et al. (2017)