Types of Clustering

Cluster analysis divides data into groups called clusters, where objects within a cluster are similar to each other and objects in different clusters are not. Its purpose is to identify patterns and meaningful groups in data, and it is sometimes used as a first step toward data summarization or further analysis.

Cluster analysis matters across many fields — biology, psychology, statistics, pattern recognition, machine learning, and data mining.

This lesson is about the different ways clustering can be done. The companion lesson on clustering in data mining covers what clustering is, how similarity is measured, and the major algorithm families (k-means, hierarchical, DBSCAN and so on). Here the focus is on the structural choices that sit underneath those algorithms: whether clusters nest, whether an object can belong to more than one, and whether everything has to be assigned at all.

What Is Cluster Analysis?

Cluster analysis groups data objects using only the information present in the dataset itself. The goal is straightforward to state:

• Objects within the same group should be similar
• Objects in different groups should be dissimilar

Defining what actually forms a cluster is less straightforward. The same set of points can legitimately be grouped several different ways depending on the method used, and none of them is wrong in isolation. The best clustering structure depends on the nature of the data and on what the analysis is for — which is why the choices described below are decisions to make, not defaults to accept.

Clustering vs Classification

Clustering is often compared with classification, but they are fundamentally different.

Because of this, clustering is sometimes called unsupervised classification.

Related Terms

Two terms are frequently used alongside clustering and are worth distinguishing:

Segmentation — dividing data into groups using simple, often predefined rules, such as grouping people by income band or segmenting an image by colour. The rules come from the analyst rather than from the data's structure.

Partitioning — dividing a dataset into smaller subsets. The term is also used in graph partitioning and other areas, where it may have nothing to do with similarity.

Three Ways of Categorizing Clustering

1. Hierarchical vs Partitional

Partitional clustering divides the dataset into non-overlapping clusters, where each object belongs to exactly one cluster and clusters contain no subclusters. If 100 customers are divided into 5 groups, each customer sits in exactly one group.

Hierarchical clustering organizes clusters into a tree, where clusters may contain subclusters:

• The root contains all objects
• The leaf nodes contain individual objects
• Moving down the tree splits clusters into progressively smaller groups

The practical link between the two is that a hierarchical clustering can be converted into a partitional one by cutting the tree at a chosen level. This is a real advantage: you don't have to commit to the number of clusters before running the algorithm, as you do with k-means. You build the tree once and choose the level afterward.

2. Exclusive vs Overlapping vs Fuzzy

Exclusive clustering — each object belongs to exactly one cluster. A student belongs to one class section.

Overlapping clustering — an object can belong to several clusters at once. A person can be both an employee and a student trainee at the same company. This suits data where objects genuinely hold multiple memberships.

Fuzzy clustering — every object belongs to every cluster, with a membership value between 0 and 1, and each object's memberships sum to 1. An object might be 70% in cluster A and 30% in cluster B.

The distinction between overlapping and fuzzy is easy to blur but real. Overlapping clustering makes several hard yes/no assignments; fuzzy clustering makes graded assignments across all clusters. Fuzzy is useful where cluster boundaries are genuinely unclear, and it carries useful information a hard assignment throws away — a point at 0.51/0.49 is flagged as borderline rather than confidently filed. Fuzzy C-Means is the standard algorithm here.

3. Complete vs Partial

Complete clustering assigns every object to a cluster — for example, grouping all documents in a dataset into topics.

Partial clustering allows some objects to belong to no cluster at all. Those objects may be noise, outliers, or simply irrelevant. Analyzing news articles, only those on significant topics might be grouped, with the rest left out.

Partial clustering is often the more honest choice on real data. Forcing every record into a cluster means genuine outliers get absorbed into groups they don't belong to, distorting those clusters. This is exactly what DBSCAN does by labelling low-density points as noise rather than assigning them.

Different Types of Clusters

Separately from how clustering is performed, methods differ in what they treat a cluster as fundamentally being.

1. Well-Separated Clusters

Every object in a cluster is closer to other objects in the same cluster than to any object outside it.

• Clear separation between clusters
• Clusters can be any shape

This is the ideal case, and it makes any reasonable algorithm work. It is also rare in practice — real data usually has clusters that touch or overlap.

2. Prototype-Based Clusters

Each cluster is represented by a single prototype, and objects are assigned to whichever prototype is closest:

• Centroid — the average of all points in the cluster. It need not be an actual data point.
• Medoid — the most representative actual data point in the cluster.

The medoid matters when an average would be meaningless — you cannot average two categorical records, but you can pick the most central real one. Medoids are also more robust to outliers, since one extreme value can drag a centroid but cannot become the medoid.

These are often called center-based clusters and tend to be spherical. Example algorithms: k-means (centroid) and k-medoids (medoid).

3. Graph-Based Clusters

Data is represented as a graph, with nodes as objects and edges as connections or similarity. A cluster is a connected component — a set of nodes reachable from each other.

A common variant is contiguity-based clustering, where objects are connected if they fall within a certain distance of one another.

The known weakness is chaining: a thin bridge of noise points connecting two genuine clusters merges them into one, because connectivity alone doesn't care how thin the link is.

4. Density-Based Clusters

Clusters are dense regions of points separated by sparse regions.

• Detects irregular, arbitrarily-shaped clusters
• Handles noise and outliers naturally, by leaving them unassigned

Example algorithm: DBSCAN. Density-based methods work well where clusters are complex in shape or where the data contains noise that other methods would force into groups.

5. Shared-Property (Conceptual) Clusters

Objects in a cluster share a common property or concept — documents discussing the same topic, or products in the same category.

These are discovered through conceptual clustering, which considers the meaning or concept behind the data rather than distance alone. This is the most general definition of a cluster and the hardest to compute, since the shared property may not correspond to closeness in any numeric space.

Choosing Between Them

These categories combine rather than compete — a given method makes one choice from each group. k-means is partitional, exclusive, complete, and prototype-based. DBSCAN is partitional, exclusive, partial, and density-based. Fuzzy C-Means is partitional, fuzzy, and complete.

Reading an algorithm this way is a quick diagnostic for whether it suits your data. If your records genuinely belong to several groups, any exclusive method is the wrong starting point regardless of its other merits.

Related Concepts

The algorithms behind these categories, along with distance measures and the requirements of a good clustering algorithm, are covered in this series' lesson on clustering in data mining. Graph-based clustering applied to social networks appears as community detection in the social media data mining methods lesson.