7.1 Clustering, Distance, and Stability: Algorithms Find the Groupings Preferred by the Objective Function

Before clustering, define which features indicate similarity, how distance is computed, and what actions the grouping will support. The structure that algorithms uncover depends entirely on these choices.

Learning Objectives

Formulate clustering as clear objectives and assumptions about similarity;
Derive the objective function, assignment, and update steps of K-means;
Understand the impact of initialization, scaling, outliers, and cluster shape;
Distinguish the structural assumptions of K-means and DBSCAN;
Evaluate clustering using stability, external validation, and downstream utility.

1. First, Define "Similar"

Tasks from the same batch can be grouped by geography, resource requirements, failure modes, or thematic content. Differences in outcomes don’t mean someone made a mistake, they reflect fundamentally different problems.

A distance function encodes business assumptions into the model:

Euclidean distance takes the square root of the sum of squared coordinate differences;
Manhattan distance sums absolute coordinate differences; unlike squared Euclidean distance, it penalizes an individual deviation linearly;
cosine distance focuses on directionality, commonly used in sparse text representations;
mixed numeric and categorical data requires appropriate encoding or specialized dissimilarity measures;
time series may care about shape, phase, or dynamic alignment, and shouldn't be flattened directly into ordinary vectors.

The unit of measurement governs Euclidean distance. If distance is measured in kilometers for travel or degrees Celsius for temperature, unprocessed distances may effectively only reflect travel distance. Normalization, robust scaling, or domain-specific weighting all reshape the definition of "similarity", they are not merely harmless preprocessing steps.

2. What K-means Optimizes

Given $K$ clusters $C_{1}, \dots, C_{K}$ and their centers $μ_{k}$ , K-means minimizes the within-cluster sum of squares (inertia):

J = \sum_{k = 1}^{K} \sum_{x_{i} \in C_{k}} ‖ x_{i} - μ_{k} ‖_{2}^{2} .

Under Euclidean squared distance, when the cluster assignments are fixed, the center that minimizes the objective is the mean of the cluster points. When the centers are fixed, each point should be assigned to the nearest center. The Lloyd algorithm alternates between:

Assignment: assign each sample to the nearest center;
Update: update the center to the current cluster mean.

Each iteration does not increase the objective, so the algorithm converges to some local optimum or stable partition. Different initializations can lead to different final results. It does not guarantee a globally optimal solution.

For the one-dimensional points [0, 2, 8, 10] and initial centers [0, 8], assignment gives {0, 2} and {8, 10}. Updating the centers to [1, 9] reduces inertia from 8 to 4. The mean update optimizes each fixed group; it does not search all possible groupings.

3. Initialization, Empty Clusters, and Convergence

Randomly selecting centroids may place multiple initial points within the same region. K-means++ tends to choose new centroids farther from existing ones, typically improving the initial solution, though it still retains randomness.

In practice, you should:

Fix random_state to reproduce experiments consistently;
Explicitly set the number of initialization runs, rather than relying on default values that may change across versions;
Record the inertia and cluster stability from each run;
Handle empty clusters that result after updates;
Simultaneously verify the stopping tolerance, iteration count, and whether centroids are finite.

The Python 3 / scikit-learn 1.9.0 fragment below requires a finite dense matrix X_train, with at least four distinct rows. It produces labels and centers in standardized coordinates.

python

from sklearn.cluster import KMeans
from sklearn.pipeline import Pipeline
from sklearn.preprocessing import StandardScaler

clusterer = Pipeline([
    ("scale", StandardScaler()),
    ("kmeans", KMeans(
        n_clusters=4,
        init="k-means++",
        n_init=20,
        max_iter=500,
        random_state=42,
    )),
])

labels = clusterer.fit_predict(X_train)
centers_scaled = clusterer.named_steps["kmeans"].cluster_centers_

For sparse, high-dimensional text features, whether to center the data, which distance metric to use, and whether to apply standard K-means or spherical K-means must be justified on a case-by-case basis. The dense numerical pipeline described above cannot be directly applied.

4. How K-means Prefers Certain Clusters

K-means uses means and squared Euclidean distance, making it naturally suited to recover approximately convex, isotropic, and scale-consistent clusters. Common failure modes include:

Two concentric rings or crescent-shaped structures;
Clusters with vastly different densities or variances;
A large cluster adjacent to a small, genuine group;
A few extreme outliers pulling the mean away from the true center;
In high dimensions, distances become increasingly concentrated, weakening neighbor comparisons.

"The clusters must all be the same size" is not a strict model constraint, but the objective can still split large, spread-out clusters and merge small, closely grouped ones.

5. K Is Not an Automatic Truth Read from the Curve

The globally minimal inertia cannot increase as $K$ grows, and reaches zero at $K = n$ . Actual runs can break this apparent trend by finding different local solutions. An elbow is a useful diagnostic when one is visible, not an automatic answer for $K$ .

The silhouette score defines a value for each sample $i$ as:

s (i) = \frac{b (i) - a (i)}{max {a (i), b (i)}},

Here $a (i)$ averages distances to all other points in the same cluster. For each other cluster, average distances to all its points; $b (i)$ is the smallest of those averages. Values near 1 indicate separation under the chosen metric, values near 0 indicate a boundary, and negative values favor another cluster. In scikit-learn, singleton samples receive 0; the overall score requires between 2 and $n - 1$ labels.

It does not prove that the business domain actually contains these categories, and it may favor well-separated, convex clusters. Choosing $K$ should also consider:

Stability across different samples or random seeds;
Whether the clusters can be explained by independent features or downstream labels;
Whether the grouping leads to distinct, actionable strategies;
Minimum group sizes, operational capacity, and fairness risks;
Whether new data can be reliably assigned to existing clusters.

If external ground truth labels are available, metrics such as the adjusted Rand index or adjusted mutual information can be used to compare clusterings in a permutation-invariant way. However, using future labels during training and then claiming the process remains fully unsupervised is fundamentally flawed.

6. DBSCAN Using Density-Connected Samples

DBSCAN is given a neighborhood radius $ε$ and min_samples:

A core point: a sample whose neighborhood within radius $ε$ contains at least a specified number or weight of points, including the point itself;
A border point: a point that is not a core point but lies within the neighborhood of some core point;
Noise: points not reachable through density connectivity and thus not assigned to any cluster.

It can discover non-convex shapes and label some points as noise, and it does not require prior specification of the number of clusters. However, this comes at a cost:

$ε$ is tightly coupled with feature scales and the choice of metric;
Clusters of varying densities are difficult to recover using a single global $ε$ ;
In high dimensions, neighborhood regions lose discriminative power;
The assignment of border points may depend on sample order or implementation details;
In some implementations and parameter settings, the neighborhood graph can consume substantial memory.

Methods like OPTICS or HDBSCAN can alleviate some of the issues arising from a single density threshold, but they still require choices of metric, minimum cluster size, and cluster extraction rules.

7. How to Validate Clustering Results

Internal Metrics

Metrics like inertia, silhouette, and Davies–Bouldin assess only specific geometric properties. It's not surprising that a K-means objective selects a solution that K-means favors, these metrics don't guarantee meaningful or generalizable clusters.

Stability

Perform bootstrap or subsampling of the sample, vary initialization, and adjust time windows. Compare pairwise co-clustering or aligned labels across runs. Label numbers themselves carry no semantic meaning: a cluster labeled 0 in one run might correspond to cluster 3 in another.

External or Downstream Validation

Evaluate the independent outcomes of each cluster, conduct manual reviews, and assess the impact and benefits of downstream strategies. If clustering is used for stratified sampling, recommendations, or resource allocation, validate the entire strategy on held-out or future data, rather than by plotting a two-dimensional scatter plot alone.

Operability

For each cluster, write a verifiable definition, specify the number of people covered, highlight key differences, identify representative or boundary samples, and define actionable steps. Clusters that cannot be explained in terms of meaningful actions may simply be artifacts of data compression.

8. Training/Deployment Boundary

If clustering is merely a one-time exploration, it can be fitted on a clearly defined snapshot. However, if clustering is intended for new tasks, the following components must be frozen and versioned:

schema, imputation, scaling, and encoding;
feature window and cutoff points;
center/density models and cluster-to-action mappings;
new category handling and missing value strategies;
drift detection and rejection rules for instances that are far from all clusters.

K-means can assign new samples to their nearest frozen center. Standard DBSCAN in scikit-learn has no corresponding predict; a nearest-core assignment rule would be an additional deployment rule and need separate validation.

If clustering features are fed into a supervised model, all unsupervised transformations must also be fitted within the training fold. Unlabeled data does not imply immunity to leakage of distribution information from validation or test sets.

Common Misconceptions

Clustering reveals natural data categories: The results are defined by features, distance metrics, and the chosen objective, and do not establish a unique natural classification.
Elbow or silhouette methods determine the correct K: These provide only geometric evidence; they do not guarantee the optimal number of clusters.
Standardization is always appropriate: It effectively rescales feature weights, but should be guided by domain-specific semantics rather than applied universally.
DBSCAN requires no hyperparameter tuning: The outcome is governed by the eps, min_samples, and the chosen distance metric, these parameters define the behavior, not the algorithm's "default."
Unsupervised steps can be fitted on the full dataset: Leakage occurs when evaluation pipelines include data from the same full dataset used for training.

Exercise

Perform clustering on the same dataset without scaling, with standardization, and with domain-weighted features, then compare the results.
Compute co-clustering stability using multiple random seeds and bootstrap samples.
Compare K-means and DBSCAN on the two moons dataset, and explain the underlying assumptions of each algorithm.
For a given clustering application, define a cluster-to-action mapping and establish rejection rules.

Summary

Clustering doesn't extract a single definitive answer from unlabeled data, it constructs groups based on chosen representations, distance metrics, and objectives. K-means favors partitions with low inertia by centering clusters around means, while DBSCAN prefers dense, connectivity-based regions. Reliability must be validated through stability, external benchmarks, and downstream actions.

The next lesson explores another structural approach: instead of grouping samples, we seek a lower-dimensional coordinate system to compress, denoise, or visualize the data.

Chapter 1: Propositional Logic: From Requirement Sentences to Decidable Formulas

Chapter 2: Sets and Operations: Describing Object Scope via Membership

Chapter 3: Direct Proof, Contrapositive, and Case Analysis: Building Verifiable Reasoning Chains

Chapter 4: Recursive Definitions and Mathematical Induction: Proving Along the Construction Process

Chapter 5: Binary Relations: Properties, Composition, and Closure

Chapter 6: Counting Principles: Addition, Multiplication, Inclusion-Exclusion, and the Pigeonhole Principle

Chapter 7: Graph Models and Traversal: First Define Edges, Then Choose Representation

Chapter 8: Probability Space and Conditional Probability: First Build the Model, Then Update Your Judgment

Chapter 9: Divisibility, Congruence, and Euclid's Algorithm: The Fundamental Structure of Integers

Chapter 10: Vectors and Inner Products: Turning Objects into Comparable Coordinates

Chapter 11: Limits, Derivatives, and the Chain Rule: Describing Local Change

Chapter 12: Self-Information, Entropy, and Coding: How Uncertainty Becomes Bits