Clustering Problem Formulation

Imagine you're a biologist examining thousands of cell samples under a microscope, a market researcher analyzing millions of customer transactions, or an astronomer cataloging billions of celestial objects. In each case, you face a fundamental challenge: how do you organize vast collections of unlabeled data into meaningful groups?

This is the essence of clustering—one of the most fundamental and widely-used techniques in unsupervised machine learning. Unlike supervised learning where we have labels to guide us, clustering ventures into the territory of discovering hidden structure in data where no ground truth exists.

Clustering sits at the intersection of statistics, computer science, and domain expertise. It's simultaneously straightforward in concept—group similar things together—and remarkably subtle in execution. The question of what makes a "good" cluster has no universal answer, making clustering as much an art as a science.

Clustering is the task of partitioning a set of data points into groups (called clusters) such that points within the same cluster are more similar to each other than they are to points in other clusters. This deceptively simple definition conceals layers of complexity that have occupied researchers for decades.

Formal Definition:

Given a dataset $X = {x_1, x_2, \ldots, x_n}$ where each $x_i \in \mathbb{R}^d$, clustering seeks to assign each point to one of $k$ clusters $C = {C_1, C_2, \ldots, C_k}$ such that:

$$\bigcup_{j=1}^{k} C_j = X \quad \text{and} \quad C_i \cap C_j = \emptyset \text{ for } i eq j \text{ (hard clustering)}$$

In hard clustering, each point belongs to exactly one cluster. In soft (fuzzy) clustering, each point has a degree of membership to multiple clusters, represented as probabilities: $p(x_i \in C_j)$ for all $j$.

The Fundamental Question:

What makes two points "similar" and what makes a "good" cluster? These questions have no universal answers because they depend entirely on:

1. The domain — Similarity for images differs from similarity for documents or financial transactions
2. The purpose — Clustering for customer segmentation has different goals than clustering for anomaly detection
3. The scale — What's meaningful at 1,000 points may differ from what's meaningful at 1,000,000 points

This context-dependence is both clustering's greatest strength (flexibility) and its greatest challenge (ambiguity).

Despite the inherent ambiguity in clustering, two fundamental objectives guide virtually all clustering algorithms. These dual objectives form the conceptual backbone of clustering and provide the foundation for both algorithm design and evaluation.

Mathematical Formalization:

Let $\mu_j$ denote the centroid (mean) of cluster $C_j$. The most common objective function for clustering is the within-cluster sum of squares (WCSS), which measures cohesion:

$$\text{WCSS} = \sum_{j=1}^{k} \sum_{x_i \in C_j} |x_i - \mu_j|^2$$

Minimizing WCSS directly optimizes for compactness—we want each point to be close to its cluster center.

For separation, we might consider the between-cluster sum of squares (BCSS):

$$\text{BCSS} = \sum_{j=1}^{k} |C_j| \cdot |\mu_j - \mu|^2$$

where $\mu$ is the global mean of all data points and $|C_j|$ is the number of points in cluster $j$.

The Total Variance Decomposition:

A fundamental identity in clustering connects these quantities:

$$\text{TSS} = \text{WCSS} + \text{BCSS}$$

where TSS (Total Sum of Squares) is the total variance in the data. Since TSS is fixed for a given dataset, minimizing WCSS is equivalent to maximizing BCSS. This elegant relationship shows that cohesion and separation are two sides of the same coin.

Viewing clustering through the lens of optimization reveals both its mathematical structure and its computational challenges. Most clustering algorithms can be understood as attempting to optimize some objective function, though the specific objectives vary significantly.

General Optimization Framework:

$$\min_{C_1, \ldots, C_k} \mathcal{L}(C_1, \ldots, C_k; X)$$

where $\mathcal{L}$ is a loss function measuring the quality of the clustering. Different choices of $\mathcal{L}$ lead to different clustering algorithms:

Computational Hardness:

A sobering reality of clustering is that finding the globally optimal solution is typically NP-hard. The k-means problem, despite its simplicity, was proven NP-hard even for $k=2$ clusters in general dimension. This means:

1. No polynomial-time algorithms exist for finding the true optimal clustering (unless P=NP)
2. All practical algorithms are heuristics that find local optima, not global optima
3. Results depend on initialization and may vary across runs
4. Approximation guarantees are often the best we can achieve

Why is clustering hard? The search space is combinatorially vast. For a dataset of $n$ points and $k$ clusters, the number of possible partitions is given by the Stirling number of the second kind:

$$S(n, k) = \frac{1}{k!} \sum_{j=0}^{k} (-1)^{k-j} \binom{k}{j} j^n$$

For $n=100$ and $k=5$, this is approximately $10^{68}$—more than the number of atoms in the observable universe!

While the within-cluster sum of squares is the most famous clustering objective, it represents just one perspective on what makes a good cluster. Different applications and data characteristics call for different objectives.

Density-Based Objectives:

Instead of measuring compactness around centroids, density-based clustering defines clusters as regions of high point density separated by regions of low density. The objective becomes:

• Maximize within-cluster density — Points in a cluster should be surrounded by many neighbors
• Minimize density at boundaries — Clear "valleys" of low density should separate clusters

This leads to algorithms like DBSCAN and OPTICS, which can discover clusters of arbitrary shape—a significant advantage over centroid-based methods.

Probabilistic Objectives:

Gaussian Mixture Models (GMMs) take a fundamentally different approach: they view clustering as density estimation where each cluster corresponds to a probability distribution. The objective is to maximize the likelihood that the data was generated by a mixture of Gaussians:

$$\mathcal{L}(\theta) = \sum_{i=1}^{n} \log \left( \sum_{j=1}^{k} \pi_j \cdot \mathcal{N}(x_i | \mu_j, \Sigma_j) \right)$$

where $\pi_j$ are mixing weights, and $\mu_j, \Sigma_j$ are the mean and covariance of component $j$.

This probabilistic view offers:

• Soft cluster assignments — Each point has a probability of belonging to each cluster
• Natural uncertainty quantification — We know how confident we are in each assignment
• Principled model comparison — Using information criteria like AIC/BIC

Information-Theoretic Objectives:

Some clustering methods optimize information-theoretic quantities:

• Minimize information loss — How much information is lost by summarizing data with cluster assignments?
• Maximize mutual information — How much do cluster assignments tell us about the data?
• Rate-distortion framework — Balance compression rate with reconstruction quality

Perhaps the most important—and most frequently overlooked—aspect of clustering is that no clustering algorithm can tell you what a cluster "should" be. This is a fundamental philosophical point that separates practitioners who use clustering effectively from those who don't.

The No Free Lunch Theorem for Clustering:

Kleinberg (2002) proved a striking result: there is no clustering function that simultaneously satisfies three intuitive properties:

1. Scale-Invariance — Multiplying all distances by a constant shouldn't change the clustering
2. Richness — Any partition of the data should be achievable by some distance function
3. Consistency — Shrinking within-cluster distances and stretching between-cluster distances shouldn't change the clustering

This impossibility theorem tells us that clustering must involve trade-offs. There's no "correct" universal clustering—only clusterings that are appropriate for specific purposes.

How Domain Knowledge Enters Clustering:

1. Choice of features — Which attributes matter for similarity? Domain experts know that some features are relevant and others are noise.

2. Choice of distance metric — Euclidean? Cosine? Edit distance? The right metric depends entirely on what "similarity" means in your domain.

3. Choice of algorithm — Different algorithms impose different assumptions about cluster shape, size, and density. Match the algorithm to what you expect to find.

4. Choice of k (number of clusters) — Often, domain knowledge suggests a reasonable range. Customer segments might naturally be 3-7, not 50.

5. Interpretation and validation — Do the discovered clusters make sense? Are they actionable? Only domain experts can answer these questions.

Case Study: Customer Segmentation

Consider segmenting retail customers:

• Without domain knowledge: Cluster on all available features, get groups that correlate with database IDs or entry dates
• With domain knowledge: Select features like purchase frequency, average order value, product categories, recency—features known to drive business decisions

The algorithm doesn't know that customer lifetime value matters. You do.

While mathematical objectives provide theoretical foundations, practical clustering is driven by real-world goals. Understanding these practical objectives helps you choose the right approach and evaluate results meaningfully.

Common Practical Objectives:

Objective Alignment:

A critical step in any clustering project is aligning your mathematical objective with your practical objective. Misalignment leads to technically correct but practically useless results.

Example of misalignment:

• Practical goal: Find customer segments for personalized marketing
• Mathematical objective used: Minimize WCSS with Euclidean distance on raw features
• Problem: Raw features may be on different scales, irrelevant features dilute signal, Euclidean distance may not capture "marketing similarity"

Aligned approach:

• Normalize features appropriately (z-scores or domain-specific)
• Select features based on marketing relevance (RFM: Recency, Frequency, Monetary)
• Consider distance metrics that match marketing similarity
• Validate clusters by their predictive power for marketing outcomes

Before diving into specific clustering algorithms, it's essential to understand the inherent challenges that make clustering difficult. These challenges will recur throughout our study of clustering methods.

The Exploration-Confirmation Tension:

Clustering is often used for exploration—discovering unknown structure. But we also need to validate that discovered structure is real, not an artifact of the algorithm or noise. This creates a fundamental tension:

• Exploration mode: Run multiple algorithms, vary parameters, look for unexpected patterns
• Confirmation mode: Test stability, evaluate on held-out data, validate with domain experts

Good clustering practice involves iterating between these modes, using exploration to generate hypotheses and confirmation to validate them.

The Replicability Challenge:

Because clustering results depend on:

• Choice of algorithm
• Choice of parameters
• Random initialization (for stochastic algorithms)
• Choice of distance metric
• Feature selection and preprocessing

...results are often difficult to replicate. Two analysts working on the same data with slightly different choices can get vastly different clusters. This isn't a bug—it's an inherent feature of unsupervised learning that requires careful documentation and sensitivity analysis.

We've established the conceptual foundation for understanding clustering. Let's consolidate the key insights:

What's Next:

With clustering objectives understood, we now turn to a foundational concept that underlies all clustering: similarity and distance. The next page explores how we quantify "how similar are these two points?" through various distance metrics and similarity measures. This seemingly simple question has remarkably nuanced answers that profoundly affect clustering outcomes.