Clustering and Segmentation

Introduction and Context

Clustering is an unsupervised learning task in which observations are grouped so that members of the same group are more similar to one another than to members of other groups. Unlike classification, clustering generally begins without predefined class labels. The aim is not simply to divide a dataset, but to discover useful structure, explain similarity, support decisions, and generate hypotheses.

Segmentation is the practical use of clustering to divide a population, market, process, image, network, or scientific dataset into meaningful subgroups. In customer analytics, segmentation may distinguish price-sensitive customers from premium customers. In operations, it may reveal groups of machines with similar failure patterns. In science, it may identify ecological regions, gene-expression profiles, or astronomical objects.

Clustering is inherently dependent on representation and purpose. The same observations may form different clusters when different variables, distance measures, transformations, or algorithms are used. Consequently, a cluster is not automatically a natural fact; it is an analytical result that must be validated and interpreted in context.

Learning Objectives

By the end of this chapter, students should be able to:

1. Explain the purpose, assumptions, and terminology of clustering and segmentation.

2. Select appropriate data preparation methods and distance or similarity measures.

3. Apply partitioning, hierarchical, density-based, and probabilistic clustering methods.

4. Interpret cluster-quality measures and recognize their limitations.

5. Design segmentation analyses for customer, operational, and scientific applications.

6. Evaluate ethical, governance, scalability, and reproducibility issues in clustering projects.

Foundations of Clustering

Objects, features, and cluster structure

An object is an entity being grouped, such as a customer, transaction, machine, patient, or geographic location. Features are measurable attributes of objects. A dataset can be represented by a matrix in which rows are objects and columns are features.

A clustering algorithm uses a notion of proximity. Similarity increases as two objects become more alike; distance increases as they become less alike. A cluster may be:

• Compact: observations are close together.
• Separated: different groups are far apart.
• Connected: observations form a chain or density-connected region.
• Probabilistic: observations share a high probability of belonging to a common distribution.

No single definition is universally correct. K-means favors compact, approximately spherical groups; density-based methods favor dense regions separated by sparse areas; hierarchical methods provide a multiscale view; probabilistic models describe uncertainty and overlapping membership.

Data preparation

Clustering is highly sensitive to input preparation. Numerical variables measured in large units can dominate smaller-scale variables. Standardization commonly transforms a feature x into a z-score:

z = (x - mean(x)) / standard deviation(x).

Here, mean(x) and standard deviation(x) are calculated from the chosen reference dataset. Standardization is useful when variables have different units and comparable variation is intended. It may be inappropriate when original units have substantive meaning or when scale itself should determine importance.

Robust scaling, based on the median and interquartile range, can reduce the influence of extreme values. Logarithmic transformation may be appropriate for strongly right-skewed positive variables such as income, sales, or counts. Missing values must be handled deliberately because imputation can create artificial similarity. Categorical variables require suitable representations, such as one-hot encoding, binary dissimilarities, or methods designed for mixed data.

Feature selection is also essential. Including irrelevant variables can obscure meaningful structure, while including duplicate or highly correlated variables may give one underlying concept excessive influence. Domain knowledge should guide the selection of variables and their weights.

Distance and Similarity Measures

Euclidean distance

For two observations x and y with p numerical features, Euclidean distance is

d(x,y) = sqrt(sum from j=1 to p of (xj - yj)^2).

It assumes numeric features on a meaningful common scale and is especially compatible with standardized continuous data. Squared Euclidean distance is often used computationally because it avoids the square root, while preserving the ordering of distances.

Manhattan distance

Manhattan distance is

d(x,y) = sum from j=1 to p of |xj - yj|.

It can be less sensitive than Euclidean distance to a single large coordinate difference and is useful when movement along dimensions is additive. Its appropriateness still depends on scaling and feature meaning.

Cosine similarity

For nonzero vectors x and y, cosine similarity is

cos(x,y) = (x dot y) / (||x|| ||y||).

It measures the angle between vectors rather than their magnitude. It is useful for text-document representations and other high-dimensional sparse data, where direction may matter more than total volume. Zero vectors require special handling because the expression is undefined.

Binary, categorical, and mixed data

For binary variables, a Jaccard similarity can be useful when shared presences matter and shared absences are uninformative. For mixed numerical and categorical data, a combined dissimilarity such as Gower’s approach scales individual variables and combines their contributions. The selected measure must reflect the data-generating context. Treating nominal categories as numerical values, for example assigning “red = 1” and “blue = 2,” creates a false order.

Partitioning Methods

Partitioning methods create a specified number, k, of groups. The most familiar method is k-means.

K-means clustering

K-means seeks k centroids that minimize within-cluster squared Euclidean error:

J = sum over clusters r=1 to k of sum over xi in Cr of ||xi - μr||²,

where Cr is cluster r, μr is its centroid, and xi is an observation assigned to that cluster. The centroid is the arithmetic mean of the observations assigned to the cluster.

The standard algorithm is iterative:

1. Select k initial centroids.

2. Assign each observation to the nearest centroid.

3. Recalculate each centroid as the mean of its assigned observations.

4. Repeat assignment and recalculation until assignments stabilize or improvement becomes negligible.

Each iteration does not increase the objective under the standard assignment and update steps, so the algorithm converges to a local optimum. It is not guaranteed to find the global optimum. Different initializations can therefore produce different solutions. K-means++ initialization and multiple restarts generally improve reliability.

K-means works best when clusters are roughly spherical, similarly scaled, and reasonably similar in size. It is sensitive to outliers because means and squared distances give extreme observations substantial influence. It also requires k to be selected in advance.

Worked example: one-dimensional k-means

Consider the values 1, 2, 3, 10, 11, and 12, and choose k = 2. Suppose initial centroids are 2 and 11. Values 1, 2, and 3 are closer to 2; values 10, 11, and 12 are closer to 11. The updated centroids are:

μ1 = (1 + 2 + 3) / 3 = 2,

μ2 = (10 + 11 + 12) / 3 = 11.

The assignments and centroids are unchanged, so the algorithm has converged. The within-cluster squared error is (1−2)² + (2−2)² + (3−2)² + (10−11)² + (11−11)² + (12−11)² = 4. This solution is intuitively strong because the two groups are compact and well separated.

K-medoids

K-medoids resembles k-means but uses an actual observation, called a medoid, as the representative of each cluster. It can use arbitrary dissimilarity measures and is usually more robust to outliers. Its computational cost may be higher, especially for large datasets. K-medoids is useful when a representative real customer, document, or machine is more interpretable than an artificial centroid.

Choosing k

The elbow method plots within-cluster error against k and looks for a point beyond which additional clusters provide diminishing improvement. The silhouette coefficient is another option. For observation i, let a(i) be its average distance to observations in its own cluster, and let b(i) be the smallest average distance to observations in another cluster. The silhouette is

s(i) = [b(i) - a(i)] / max(a(i), b(i)).

Values range from -1 to 1 when distances are nonnegative. Higher values generally indicate better separation, although the measure can favor particular shapes and cluster counts. Selection should combine numerical evidence, stability, interpretability, and the decision objective rather than relying on one plot.

Hierarchical Clustering

Hierarchical clustering creates a nested sequence of groupings represented by a dendrogram. In agglomerative clustering, each observation begins as its own cluster. The two closest clusters are repeatedly merged until one cluster remains. A desired number of groups is obtained by cutting the dendrogram at a selected level.

The definition of distance between clusters is called a linkage criterion:

• Single linkage: minimum pairwise distance; can identify elongated chains but is vulnerable to chaining.
• Complete linkage: maximum pairwise distance; tends to produce compact groups.
• Average linkage: average pairwise distance; provides a compromise.
• Ward’s method: merges clusters to minimize the increase in within-cluster squared error; it is generally associated with Euclidean numerical data.

Hierarchical clustering does not require k at the start and can reveal structure at multiple resolutions. However, early merges are usually irreversible, and the dendrogram can be affected by scaling, linkage choice, noise, and small perturbations. For large datasets, storing and processing pairwise distances can become expensive.

Divisive methods begin with one cluster and split it recursively. They are conceptually useful but may be computationally more demanding depending on implementation.

Density-Based Clustering

Density-based methods define clusters as regions of high point density separated by regions of low density. DBSCAN uses two principal parameters: ε, the neighborhood radius, and MinPts, the minimum number of observations required to define a dense neighborhood. A core point has at least MinPts observations within its ε-neighborhood, according to the implementation’s counting convention. Points reachable from core points are assigned to clusters; points not assigned to a cluster are labeled noise.

DBSCAN can discover non-spherical clusters and identify outliers without forcing every observation into a group. It is useful for spatial data, geolocation, anomaly-oriented analysis, and irregular shapes. Its limitations include sensitivity to ε and MinPts, difficulty when clusters have very different densities, and reduced effectiveness in high-dimensional spaces where distances become less discriminating.

OPTICS extends the density-based idea by producing an ordering that represents clustering structure across a range of density levels. HDBSCAN builds a hierarchy of density-based clusters and can be more flexible when density varies, although parameter interpretation remains important.

Probabilistic Clustering

Probabilistic clustering treats observations as generated from a mixture of probability distributions. A Gaussian mixture model (GMM), for example, assumes that each observation is generated by one of k Gaussian components. Each component has a mean vector and covariance matrix, and a mixing proportion. Unlike hard clustering, a GMM assigns a probability of membership to every component.

The expectation-maximization algorithm is commonly used:

1. Expectation step: calculate each observation’s posterior probability of belonging to each component.

2. Maximization step: update component parameters using those probabilities as weights.

3. Repeat until the likelihood or parameter changes satisfy a stopping rule.

GMMs can represent elliptical clusters and uncertainty in membership. They require distributional assumptions and can be sensitive to initialization, covariance specification, and the number of components. A component in a statistical mixture is not always equivalent to a substantively meaningful segment. Model selection may use information criteria such as AIC or BIC, but interpretability and validation remain necessary.

Evaluating Cluster Quality

Cluster validation has three complementary perspectives.

Internal validation uses only the data and assignments. Examples include within-cluster error, silhouette coefficient, Calinski–Harabasz index, and Davies–Bouldin index. These measures evaluate compactness and separation but may prefer the geometry favored by their formulas.

External validation compares clusters with an external variable or known labels. Adjusted Rand index and normalized mutual information are examples when reference labels exist. External variables should not be used uncritically: a high association may reflect leakage, circular analysis, or a label that the clustering was designed to reproduce.

Stability validation examines whether clusters persist under resampling, perturbation, alternative initializations, or modest changes in preprocessing. A cluster that disappears when a small sample is removed should be interpreted cautiously.

A useful segmentation should also have business, scientific, or operational validity. It should be sufficiently large to act upon, distinguishable on relevant outcomes, and connected to a feasible intervention. Statistical separation alone does not establish usefulness.

A Practical Clustering Workflow

A defensible project generally follows these stages:

1. Define the decision or scientific question.

2. Specify the unit of analysis and observation period.

3. Audit data quality, missingness, outliers, leakage, and sampling bias.

4. Select, transform, and scale features using a documented rationale.

5. Choose candidate algorithms based on data type, shape, size, and purpose.

6. Run sensitivity analyses across parameters and initializations.

7. Evaluate internal, external, and stability evidence.

8. Profile clusters using variables not used to create them where possible.

9. Give clusters clear, evidence-based descriptions rather than arbitrary labels.

10. Deploy, monitor, and periodically reassess the segmentation.

Data used for profiling should be distinguished from variables used to construct clusters. Otherwise, reporting a variable as an independent validation may be misleading.

Applied Case: Retail Customer Segmentation

Background

The following is an illustrative case. A retailer wants to improve campaign targeting while reducing excessive promotional messages. It has twelve months of customer-level data, including purchase frequency, monetary value, product-category proportions, return rate, and discount usage.

Problem

The marketing team currently uses a single “high-value customer” rule based on annual spending. This rule overlooks customers who spend moderately but purchase frequently, customers who are highly discount-dependent, and customers with high return rates.

Analysis

The analytics team defines the customer as the unit of analysis and aggregates transactions over a fixed twelve-month period. Monetary variables are log-transformed because of strong right skew. Features are standardized. Customers with insufficient activity are retained but flagged, rather than silently removed. The team compares k-means, k-medoids, hierarchical Ward clustering, and a Gaussian mixture model.

Internal validation suggests that four or five groups are plausible. Stability analysis shows that a five-cluster k-means solution is unstable for a small segment, whereas a four-cluster solution is more reproducible. The final choice is therefore based not only on the highest internal score but also on stability and campaign feasibility.

Approach and solution

The four segments are profiled using construction variables and separate outcome variables:

1. Frequent moderate-value customers: frequent purchases, moderate spend, low return rate.

2. Premium customers: high spend, broad category participation, low discount dependence.

3. Promotion-responsive customers: high discount usage and strong response during sales periods.

4. At-risk or costly customers: declining recent activity and relatively high return rates.

These labels describe observed patterns; they do not assert permanent identities. Marketing actions are differentiated: loyalty benefits for frequent customers, service and exclusivity for premium customers, controlled promotional experiments for discount-responsive customers, and service-recovery analysis for at-risk customers.

Outcome and monitoring

A randomized campaign test compares the segmented strategy with the previous single-rule strategy. The evaluation includes incremental revenue, profit after discounts, contact frequency, unsubscribe rate, and fairness checks across protected or sensitive groups where legally and ethically appropriate. The clusters are recomputed periodically because customer behavior changes.

Learning points

The case demonstrates that segmentation requires a decision objective, careful feature design, comparison of algorithms, stability testing, interpretable profiling, and outcome-based evaluation. A mathematically attractive clustering is not necessarily an effective marketing strategy.

Applications Beyond Marketing

In operations, clustering can group machines by vibration signatures, energy consumption, or maintenance history. The resulting groups can support differentiated inspection schedules, but engineers must ensure that clusters do not conceal rare safety-critical failures.

In scientific research, clustering can organize gene-expression profiles, climate regimes, land-cover types, or particle measurements. Scientists should distinguish exploratory grouping from causal explanation. A cluster may suggest a hypothesis but does not prove that a common mechanism caused it.

In data warehousing and business intelligence, clustered segments can be stored as slowly changing analytical attributes, linked to customer, product, or asset dimensions. Because assignments may change, the warehouse design should record effective dates, versioning, model parameters, and the data snapshot used for assignment.

Challenges, Ethics, and Governance

High dimensionality can make distances concentrate, reducing the contrast between near and far observations. Dimensionality reduction may help visualization, but clustering on a two-dimensional projection can distort relationships. Missing data and measurement error can create artificial groups. Outliers may represent errors, rare but important cases, or genuinely distinct populations.

Clusters can reproduce historical discrimination when features encode unequal access or biased institutional practices. Sensitive attributes should not automatically be included or excluded without analysis: excluding them may conceal disparate impact, while including them may enable prohibited targeting. Teams should document purpose, legal basis, feature provenance, retention, access controls, and the consequences of automated decisions.

Cluster labels can stigmatize people. Operational users should receive descriptive, non-pejorative definitions and guidance about uncertainty. Probabilistic membership or low stability should prevent overconfident decisions. Human review is especially important when segmentation affects eligibility, pricing, employment, healthcare, credit, or public services.

Contemporary Developments and Best Practices

Modern clustering increasingly addresses streaming data, large-scale distributed computation, graph structure, mixed data, and representation learning. Embeddings from language, vision, or recommender systems can support clustering, but their semantic meaning and inherited biases must be examined. Deep clustering methods can be powerful but may be difficult to interpret and validate.

Best practice is to treat clustering as an iterative analytical process rather than a one-click algorithm. Use domain-informed representations, compare multiple methods, record preprocessing and random seeds, test stability, inspect small clusters, and connect results to measurable outcomes. Maintain a model card or analytical record describing purpose, data, parameters, limitations, validation, and monitoring responsibilities.

Chapter Summary

Clustering groups observations according to a chosen concept of similarity, while segmentation applies those groups to practical or scientific decisions. Partitioning methods such as k-means are efficient and effective for appropriately scaled, compact numerical groups, but require choices about k and initialization. Hierarchical methods reveal nested structure through dendrograms, while density-based methods identify irregular shapes and noise. Probabilistic models provide soft membership and uncertainty but depend on distributional assumptions.

Distance measures, transformations, feature selection, and missing-value treatment strongly influence results. Cluster quality should be assessed through internal metrics, external evidence when available, stability, interpretability, and decision value. A complete workflow defines the purpose, prepares data, compares algorithms, validates robustness, profiles segments, and monitors change. Ethical governance is essential because clusters can encode bias, stigmatize people, or influence consequential decisions.

Key Terms

Clustering: Unsupervised grouping of observations according to similarity.

Segmentation: Practical division of a population into meaningful subgroups.

Feature: A measurable attribute used to represent an observation.

Distance measure: A rule for quantifying dissimilarity between observations.

Euclidean distance: Square-root distance based on summed squared coordinate differences.

Manhattan distance: Distance based on summed absolute coordinate differences.

Centroid: Arithmetic mean vector representing a cluster in k-means.

Medoid: Actual observation selected as a cluster representative.

K-means: Partitioning method minimizing within-cluster squared Euclidean error.

Hierarchical clustering: Method producing nested groupings represented by a dendrogram.

Linkage: Rule defining distance between clusters in hierarchical clustering.

Density-based clustering: Clustering based on dense regions separated by sparse areas.

DBSCAN: Density-based algorithm using neighborhood radius and minimum point parameters.

Gaussian mixture model: Probabilistic model representing data as a mixture of Gaussian components.

Silhouette coefficient: Measure comparing an observation’s within-cluster and nearest-other-cluster distances.

Internal validation: Evaluation using the clustering data and assignments themselves.

External validation: Comparison with independent labels or outcomes.

Stability: Persistence of a clustering solution under perturbations or resampling.

Outlier: Observation unusually distant from typical observations or cluster structure.

Feature scaling: Transformation that places variables on a comparable numerical scale.

Review Questions

Short Answer Questions

1. Why is feature scaling often important before applying k-means?

2. State one strength and one limitation of hierarchical clustering.

3. What is the purpose of the ε parameter in DBSCAN?

4. How does probabilistic clustering differ from hard assignment clustering?

5. Why should cluster stability be examined?

Long Answer Questions

1. Explain the k-means algorithm, its objective function, assumptions, and major limitations.

2. Compare k-means, hierarchical clustering, DBSCAN, and Gaussian mixture models for customer segmentation.

3. Explain how Euclidean, Manhattan, cosine, and binary similarity measures differ in application.

4. Discuss internal, external, and stability validation, including why no single metric is sufficient.

5. Describe a complete, ethically responsible workflow for deploying an operational segmentation system.

Analytical / Application Questions

1. A dataset contains annual income, transaction count, and average order value, all with highly different scales. Design a preprocessing and clustering plan and justify each step.

2. A DBSCAN analysis labels 18% of observations as noise, while k-means forces all observations into three groups. Explain how you would determine whether the noise represents errors, rare cases, or meaningful structure.

3. A retailer obtains a stable four-cluster solution, but one cluster has only 0.5% of customers and no feasible intervention. Should it be retained? Develop a reasoned decision using statistical, business, and ethical criteria.

Multiple Choice Questions with Answers

Question 1

Which clustering method minimizes within-cluster squared Euclidean error?

A. K-means

B. DBSCAN

C. Single-linkage clustering

D. Gaussian mixture modeling

Correct Answer: A. K-means

Question 2

What does a medoid represent?

A. The mean of every observation in the dataset

B. An actual observation selected to represent a cluster

C. The maximum distance between two clusters

D. A probability assigned to a cluster

Correct Answer: B. An actual observation selected to represent a cluster

Question 3

Which distance is based on the angle between two nonzero vectors?

A. Euclidean distance

B. Manhattan distance

C. Cosine similarity

D. Squared Mahalanobis distance

Correct Answer: C. Cosine similarity

Question 4

In DBSCAN, a core point is identified primarily using which information?

A. A neighborhood radius and a minimum point count

B. The number of requested clusters only

C. A dendrogram cut height only

D. A Gaussian covariance matrix only

Correct Answer: A. A neighborhood radius and a minimum point count

Question 5

What is a major advantage of hierarchical clustering?

A. It always finds the globally optimal partition

B. It reveals nested groupings across different levels

C. It is unaffected by feature scaling

D. It requires no distance or similarity definition

Correct Answer: B. It reveals nested groupings across different levels

Question 6

A silhouette value close to 1 generally indicates that an observation is:

A. Closer to another cluster than to its own cluster

B. Equally close to all clusters

C. Well matched to its own cluster and separated from others

D. Automatically an outlier

Correct Answer: C. Well matched to its own cluster and separated from others

Question 7

Why can k-means be strongly affected by outliers?

A. It uses medoids rather than means

B. Its centroids and squared errors give extreme values substantial influence

C. It labels all points as noise

D. It requires categorical variables

Correct Answer: B. Its centroids and squared errors give extreme values substantial influence

Question 8

What is a key characteristic of Gaussian mixture models?

A. They provide probabilistic membership in components

B. They can only identify chain-shaped clusters

C. They do not require any distributional assumptions

D. They always assign every observation to exactly one fixed cluster

Correct Answer: A. They provide probabilistic membership in components

Question 9

Which is an example of stability validation?

A. Checking whether clusters persist after resampling the data

B. Calculating only the mean of each feature

C. Renaming clusters after deployment

D. Removing all small clusters without inspection

Correct Answer: A. Checking whether clusters persist after resampling the data

Question 10

Why should clustering labels be monitored after deployment?

A. Cluster assignments can change as behavior and data distributions change

B. Clustering permanently determines a person’s identity

C. Monitoring eliminates the need for validation

D. Labels cannot be affected by new data

Correct Answer: A. Cluster assignments can change as behavior and data distributions change