Clustering

Clustering is an unsupervised machine learning technique used in data mining to group similar data objects together. Data points are divided into groups called clusters, based on how similar they are to each other.

Unlike supervised learning, clustering requires no labeled data. The algorithm works only from the input data itself, using it to identify patterns, similarities, and unusual data points. Nobody tells it what the groups should be  it finds them.

This makes clustering especially useful for organizing large datasets into meaningful groups, turning an undifferentiated mass of records into something a person can actually reason about.

What Is a Cluster?

A cluster is a group of data objects that are similar to one another. In simple terms:

• Objects inside a cluster are close to each other.
• Objects in different clusters are far apart.

A cluster can also be understood as a dense region of data points in a multi-dimensional space an area where records bunch together, separated by sparser space from other such areas.

How "Similarity" Is Actually Measured

Descriptions of clustering lean heavily on words like "similar" and "close," which raises an obvious question: close by what measure? A computer needs a number, not an intuition.

Clustering algorithms measure similarity as distance between data points, where each attribute becomes a dimension. The most common measures are:

• Euclidean distance — straight-line distance between two points. For two customers described by age and annual spend, it's the distance between their two positions on that two-dimensional plot. This is the default for most numeric clustering.
• Manhattan distance — the sum of the absolute differences along each dimension, as though travelling along a grid rather than diagonally.
• Cosine similarity — measures the angle between two points rather than the gap between them, which makes it useful for text, where the proportions of words matter more than the raw counts. Two documents of very different lengths on the same topic are far apart by Euclidean distance but close by cosine similarity.

One practical consequence follows directly from this: attributes measured on larger numeric scales dominate the distance calculation. If one column holds annual income in the tens of thousands and another holds age in years, income will effectively decide every cluster unless the data is normalized first. This is why normalization during data preparation matters so much to clustering results  a point covered in this series' lessons on the KDD process and data preparation.

An Example

Consider a company preparing to launch a new product. It has a large customer database, but not every customer is a likely buyer, and marketing to all of them equally wastes budget.

Using clustering, the company can group customers by shared characteristics purchasing behaviour, interests, demographics. Once those groups exist, the marketing team can identify which cluster best matches the new product and target that group specifically.

Note what the algorithm did and did not do here. It grouped customers by similarity; it did not know which group is the right one to target. Interpreting the clusters and deciding what to do about them remains human work.

What Makes a Good Cluster

A clustering result is judged on two properties:

1. High intra-cluster similarity — data points within the same cluster should be very similar to each other.

2. Low inter-cluster similarity — data points from different clusters should be clearly different from each other.

Together these ensure each cluster represents a genuinely distinct group rather than an arbitrary slice of a continuum. A result where every cluster looks much like its neighbours has technically produced groups but discovered nothing.

Main Types of Clustering Methods

No single algorithm suits every dataset, and the major families work in fundamentally different ways:

Partitioning methods divide the data into a number of clusters specified in advance, then iteratively refine which points belong to which. k-means is the best-known example: you tell it to find k clusters, and it repeatedly assigns each point to the nearest cluster centre and recalculates those centres until they stop moving. Fast and widely used, but you must choose k yourself, and it tends to find roughly spherical clusters of similar size.

Hierarchical methods build a tree of clusters instead of a flat set. Agglomerative approaches start with every point as its own cluster and repeatedly merge the closest pair; divisive approaches start with one cluster and split it. The result is a dendrogram, a tree you can cut at any level to get more or fewer clusters useful when you don't know in advance how many groups exist.

Density-based methods define clusters as dense regions separated by sparse ones. DBSCAN is the common example: it grows clusters outward from points that have enough neighbours nearby. Because it doesn't assume any particular shape, it can find irregular, arbitrarily-shaped clusters, and it labels points in sparse regions as noise rather than forcing them into a group which also makes it useful for outlier detection.

Grid-based methods divide the data space into a finite grid of cells and cluster the cells rather than individual points, which makes processing time depend on the grid size rather than the number of records an advantage on very large datasets.

Model-based methods assume the data was generated by a mixture of underlying statistical distributions and try to recover them, assigning each point a probability of belonging to each cluster rather than a hard assignment.

The differences matter in practice: k-means on data with elongated or nested cluster shapes will produce confident, tidy, and wrong results, while DBSCAN on that same data may recover the real structure.

Requirements of a Good Clustering Algorithm

1. Scalability. The algorithm should handle large datasets efficiently. This is a question of computational complexity, not just speed: an algorithm whose running time grows with the square of the number of records becomes impractical long before the dataset gets truly large, which is a major reason k-means remains popular despite its limitations.

2. Interpretability. Results should be understandable and usable for decision-making. Clusters nobody can characterise or explain rarely lead to action.

3. Ability to discover different cluster shapes. Clusters come in many shapes and sizes, not just spherical ones, and a good algorithm should be able to detect arbitrarily-shaped clusters.

4. Handling different types of data. The algorithm should work with numerical, binary, and categorical data. This is less trivial than it sounds — distance between two numbers is obvious, but the "distance" between two categories such as red and blue has to be defined deliberately.

5. Handling noisy data. Real-world data contains missing, incorrect, or noisy values, and a good algorithm should tolerate them without its results being significantly distorted.

6. Handling high-dimensional data. The algorithm should work on both low- and high-dimensional data. High dimensionality is genuinely difficult: as the number of attributes grows, distances between all pairs of points tend to converge, making "nearest" progressively less meaningful an effect known as the curse of dimensionality.

Applications of Clustering

Market research — grouping customers by buying behaviour, preferences, and demographics.

Pattern recognition — identifying patterns in speech recognition, handwriting recognition, and image analysis.

Document grouping — organizing large collections of online documents into topic groups for easier discovery. (Note that this is clustering, not classification: the topics are discovered from the documents themselves rather than assigned from a predefined list.)

Fraud detection — identifying unusual patterns in financial transactions that don't fit any normal cluster of behaviour, which is a common route to detecting credit card fraud.

Biology — classifying plants and animals, grouping genes with similar functions, and studying population structures.

Geographic analysis — identifying regions with similar characteristics, such as grouping housing areas by price, type, and location.

Clustering is applied across image processing, computational biology, medicine, mobile communications, and economics, because it can analyze large, complex datasets and reveal patterns that are not visible on inspection.

Where Clustering Fits in a Data Mining Project

Clustering can serve as a standalone analysis method, producing insight in its own right, or as a preprocessing step for other techniques segmenting data before separate models are trained on each segment, or reducing a large dataset to a set of representative groups. It helps in understanding the natural structure of data, identifying hidden patterns, and preparing data for other machine learning algorithms.

Related Concepts

Clustering is one of the seven techniques covered in this series' lesson on data mining techniques, where it's contrasted with classification. Applied to graph structure rather than attribute values, the same idea becomes community detection, covered in the lesson on social media data mining methods.