With clustering objectives, distance measures, and cluster definitions now understood, we can survey the landscape of clustering approaches. Just as there are many ways to define a cluster, there are many ways to find clusters. Understanding this taxonomy helps you navigate the dozens of clustering algorithms and recognize their fundamental similarities and differences.

Clustering algorithms can be categorized along multiple dimensions: How do they partition data? Do they assign points definitively or probabilistically? Do they handle all points or allow for noise? Do they operate on raw data or transformed representations? Each dimension represents a design choice that affects the algorithm's behavior, strengths, and limitations.

This page provides a comprehensive taxonomy of clustering types, preparing you to understand how specific algorithms (K-means, hierarchical clustering, DBSCAN, spectral clustering, GMMs) fit into the broader landscape.

The most fundamental distinction in clustering is between methods that find a single partition versus those that find a hierarchy of partitions.

Partitional Clustering:

Partitional (or "flat") clustering divides data into a fixed number of non-overlapping groups. The output is a single set of clusters ${C_1, C_2, \ldots, C_k}$.

Key characteristics:

• Requires specifying $k$ (number of clusters) in advance
• Each point belongs to exactly one cluster
• Optimizes some objective function (e.g., WCSS for k-means)
• No inherent relationship between clusters

Examples: K-means, K-medoids, GMM (can be), spectral clustering

Hierarchical Clustering:

Hierarchical clustering creates a tree (dendrogram) of nested cluster relationships. Every partition at every granularity is encoded in a single structure.

Key characteristics:

• No need to pre-specify $k$
• Produces a hierarchy: clusters within clusters
• Can extract any number of clusters by cutting the tree
• Relationships between clusters are explicit

Agglomerative vs. Divisive Hierarchical:

Hierarchical clustering comes in two flavors:

• Agglomerative (bottom-up): Start with n clusters (each point is a cluster), iteratively merge the two most similar clusters. More common in practice.

• Divisive (top-down): Start with one cluster (all points), recursively split. Less common; harder to decide how to split.

Hybrid Approaches:

Some modern methods combine aspects of both:

• Bisecting K-means: Hierarchical structure via recursive partitional calls
• HDBSCAN: Density-based hierarchy extracted for flat clustering
• BIRCH: Hierarchical data summary followed by partitional clustering

Should a point belong to exactly one cluster, or can it have partial membership in multiple clusters?

Hard Clustering:

Each point is assigned to exactly one cluster: $$\forall x_i: \quad x_i \in C_j \text{ for exactly one } j$$

Cluster assignments are deterministic—no ambiguity in which cluster owns each point.

Soft (Fuzzy) Clustering:

Each point has a degree of membership to each cluster: $$\forall x_i: \quad \mu_j(x_i) \in [0, 1] \text{ for each cluster } j$$

where $\sum_j \mu_j(x_i) = 1$ (memberships sum to 1).

In probabilistic clustering (GMMs), these are posterior probabilities: $P(\text{cluster } j | x_i)$.

Fuzzy C-Means (FCM):

The classic soft clustering algorithm generalizes k-means:

$$J_{FCM} = \sum_{i=1}^{n} \sum_{j=1}^{k} \mu_{ij}^m |x_i - \mu_j|^2$$

where:

• $\mu_{ij}$ = membership of point $i$ in cluster $j$
• $m > 1$ = fuzziness parameter (typically 2)
• Higher $m$ = softer assignments

The membership update rule: $$\mu_{ij} = \frac{1}{\sum_{l=1}^{k} \left( \frac{|x_i - \mu_j|}{|x_i - \mu_l|} \right)^{\frac{2}{m-1}}}$$

When Soft Assignments Matter:

1. Overlapping populations: Customers may belong to multiple segments
2. Uncertainty quantification: Want to know confidence in assignments
3. Downstream modeling: Soft assignments can be features for supervised learning
4. Boundary analysis: Understanding transition zones between clusters

Must every data point be assigned to a cluster?

Complete Clustering:

Every point is assigned to exactly one cluster. The clusters form a complete partition of the data: $$\bigcup_{j=1}^{k} C_j = X$$

Most clustering algorithms produce complete clusterings. K-means, hierarchical clustering (with fixed cut), and GMM with hard assignments all assign every point.

Partial Clustering:

Some points may not be assigned to any cluster. These points are classified as noise, outliers, or background: $$\bigcup_{j=1}^{k} C_j \subset X$$

Density-based methods (DBSCAN, HDBSCAN) naturally produce partial clusterings. Points in sparse regions are declared noise rather than forced into inappropriate clusters.

Making Complete Methods Partial:

You can convert complete clustering to partial by post-processing:

1. Distance threshold: Remove points farther than threshold from cluster center
2. Silhouette filtering: Remove points with negative silhouette scores
3. Probability threshold: In GMMs, unlabel points with max posterior below threshold

Making Partial Methods Complete:

To assign noise points:

1. Nearest cluster: Assign to closest cluster
2. Separate cluster: Create a "noise" cluster
3. Soft assignment: Give noise points soft membership based on proximity

The Design Choice:

Choosing between complete and partial depends on your application:

• Classification preprocessing: Complete (need labels for all training points)
• Customer segmentation with anomaly detection: Partial (some customers are outliers)
• Latent class modeling: Complete (assume every observation has a class)
• Quality control: Partial (flag unusual items rather than force-classify)

Can a point belong to multiple clusters simultaneously?

Exclusive Clustering:

Each point belongs to at most one cluster: $$C_i \cap C_j = \emptyset \quad \forall i eq j$$

This is the standard assumption in most clustering. The clusters partition the data into non-overlapping groups.

Overlapping Clustering:

Points can belong to multiple clusters: $$C_i \cap C_j eq \emptyset \text{ for some } i eq j$$

This is different from soft clustering: in overlapping clustering, a point can have full membership in multiple clusters, not partial membership in each.

Why Overlapping Clusters?

Many real-world groupings overlap naturally:

• Document clustering: A paper about "machine learning for healthcare" belongs to both "ML" and "healthcare" clusters
• Social networks: People belong to multiple communities (work, family, hobbies)
• Biological pathways: Genes participate in multiple biological processes
• Product categories: A laptop bag belongs to both "electronics accessories" and "bags"

Algorithms for Overlapping Clustering:

From Soft to Overlapping:

Soft clustering can approximate overlapping by using a threshold:

• If $\mu_j(x_i) > \tau$ for multiple $j$, assign $x_i$ to all those clusters

This converts degree-of-membership to binary multi-membership.

Does the algorithm always produce the same result, or does randomness play a role?

Deterministic Clustering:

Given the same data and parameters, the algorithm always produces the same clustering:

$$\text{Algorithm}(X, \theta) \rightarrow C \quad \text{(same every time)}$$

Examples:

• Hierarchical clustering (agglomerative)
• DBSCAN (parameter-dependent but deterministic given ε, minPts)
• Spectral clustering (deterministic eigendecomposition, then potentially stochastic k-means)

Stochastic Clustering:

Results vary across runs due to random initialization or sampling:

$$\text{Algorithm}(X, \theta) \rightarrow C_1, C_2, C_3, \ldots \quad \text{(may differ)}$$

Examples:

• K-means (random centroid initialization)
• GMM with EM (random parameter initialization)
• Monte Carlo sampling methods

Handling Stochasticity:

When using stochastic algorithms:

1. Set random seed for reproducibility:

   np.random.seed(42)
   kmeans.fit(X)
   

2. Run multiple times and select best:

   best_inertia = float('inf')
   for _ in range(10):
       km = KMeans(n_clusters=k).fit(X)
       if km.inertia_ < best_inertia:
           best_km = km
   

3. Assess stability: If different runs give very different results, the clustering may not be stable.

4. Use consensus clustering: Combine multiple runs to find robust clusters.

Smart Initialization:

K-means++ initialization dramatically reduces the impact of randomness by choosing initial centroids that are spread apart. This makes k-means more reproducible while keeping the efficiency benefits of the algorithm.

A fundamental distinction in the algorithmic approach to clustering:

Distance-Based (Metric) Clustering:

Clustering is based on pairwise distances between points. The algorithm uses distances directly to determine similarity and cluster membership.

Characteristics:

• Requires a distance function $d(x_i, x_j)$
• No probability model assumed
• Objective: minimize within-cluster distances, maximize between-cluster distances
• Examples: K-means, hierarchical clustering, DBSCAN

Model-Based (Probabilistic) Clustering:

Data is assumed to be generated from a probabilistic model. Clustering involves inferring the model parameters that best explain the data.

Characteristics:

• Assumes a generative process (e.g., mixture of distributions)
• Uses likelihood/posterior for inference
• Provides probability of cluster membership
• Examples: GMM, Latent Dirichlet Allocation, Hidden Markov Models

K-Means as a Special Case:

Interestingly, k-means can be derived from both perspectives:

1. Distance view: Minimize WCSS = sum of squared Euclidean distances to centroids

2. Model view: Maximum likelihood estimation for a GMM with spherical, equal-variance Gaussians and hard assignments

This duality shows how the paradigms connect. GMM generalizes k-means by:

• Allowing different covariances per cluster
• Allowing soft assignments
• Providing a proper likelihood for model comparison

Practical Implications:

Choose distance-based when:

• You need to use custom distance metrics
• Data doesn't follow standard distributions
• Interpretability of distances matters more than probabilities

Choose model-based when:

• You want principled uncertainty quantification
• You need to compare different numbers of clusters rigorously
• You want a generative model (sample new data)
• Data approximately follows a known distribution family

How does the algorithm handle data: all at once, or point by point?

Batch Clustering:

The algorithm sees all data before beginning and processes it as a whole:

$$\text{Cluster}({x_1, x_2, \ldots, x_n}) \rightarrow {C_1, C_2, \ldots, C_k}$$

Most clustering algorithms are batch algorithms: k-means, hierarchical, spectral, GMM.

Online (Incremental) Clustering:

Data arrives one point at a time, and the clustering is updated incrementally:

$$\text{Cluster}_{t+1} = \text{Update}(\text{Cluster}t, x{t+1})$$

The algorithm maintains a current clustering that evolves as new data arrives.

Why Online Clustering?

Batch clustering is insufficient when:

1. Data is too large: Can't fit in memory; must process in chunks
2. Data is streaming: Data arrives continuously (sensor readings, user events)
3. Distribution changes: Clusters evolve over time; need to adapt
4. Real-time requirements: Can't wait for batch processing; need immediate assignments

Online K-Means (Mini-Batch K-Means):

Samples small batches randomly and updates centroids incrementally:

for batch in stream:
    assign points to nearest centroid
    update centroids using learning rate: 
    μ_j = (1-η)μ_j + η * mean(batch points in C_j)

Converges to similar solution as batch k-means but much faster for large data.

BIRCH (Balanced Iterative Reducing and Clustering using Hierarchies):

Builds a CF (Clustering Feature) tree incrementally:

• Summarizes data in compact structures
• Can process arbitrarily large data in one pass
• Final clustering on CF summaries

What if we have some prior knowledge about which points should (or shouldn't) be together?

The Semi-Supervised Setting:

Pure unsupervised clustering uses only feature data. But often we have partial knowledge:

• Some pairs of points are known to be in the same cluster
• Some pairs are known to be in different clusters
• Some points have known labels

Constraint-based clustering incorporates this knowledge.

Types of Constraints:

Must-Link (ML): Points $x_i$ and $x_j$ must be in the same cluster. $$\text{ML}(x_i, x_j): \text{cluster}(x_i) = \text{cluster}(x_j)$$

Cannot-Link (CL): Points $x_i$ and $x_j$ must be in different clusters. $$\text{CL}(x_i, x_j): \text{cluster}(x_i) eq \text{cluster}(x_j)$$

These constraints are transitive: if ML(a,b) and ML(b,c), then ML(a,c).

Algorithms for Constrained Clustering:

COP-Kmeans: K-means with hard constraints

• Rejects assignments that violate constraints
• May fail to find feasible solution if constraints are inconsistent

PCKMeans: Penalized Constraint K-means

• Adds penalty for constraint violations to objective: $$J = \sum_i |x_i - \mu_{c_i}|^2 + w_{ML} \sum_{\text{ML}(i,j)} \mathbb{1}[c_i eq c_j] + w_{CL} \sum_{\text{CL}(i,j)} \mathbb{1}[c_i = c_j]$$

Metric Learning:

• Learn a distance metric that respects constraints
• Must-link pairs should be close; cannot-link pairs should be far
• Then cluster using learned metric

When to Use Constraints:

Constraint-based clustering is valuable when:

• You have some supervision but not enough for classification
• Domain experts can provide pairwise guidance
• You want to steer clustering toward business-relevant groupings
• Initial clustering is wrong in known ways and you want to correct it

We've surveyed the major dimensions along which clustering approaches vary. Let's consolidate:

What's Next:

With the full taxonomy understood, we turn to the challenges of evaluating clustering—a notoriously difficult problem because there's typically no ground truth. The next page explores internal and external validation metrics, stability analysis, and the fundamental difficulties of assessing unsupervised learning.