Clustering and Segmentation

Introduction

Clustering is the process of discovering groups of similar objects without using predefined class labels. Unlike supervised classification, clustering is an unsupervised learning task: the algorithm receives observations and attempts to reveal structure already present in the data. Segmentation is the application-oriented use of clustering to divide a population, market, image, network, document collection, or scientific dataset into meaningful subgroups.

Clustering is central to exploratory data mining. It supports customer segmentation, image analysis, document organization, anomaly investigation, biological discovery, recommender systems, geographical analysis, and network science. However, a clustering algorithm does not automatically discover objectively “real” groups. Results depend on how similarity is defined, how variables are scaled, which algorithm is selected, and how the resulting clusters are interpreted.

A scientifically defensible clustering study therefore involves more than running an algorithm. It requires data preparation, representation, similarity selection, algorithm design, determination of the number of clusters, validation, visualization, interpretation, and responsible use.

Learning Objectives

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

1. Explain the purpose and assumptions of clustering and segmentation.
2. Select suitable representations, scaling methods, and similarity measures.
3. Apply partitioning, hierarchical, density-based, and model-based clustering methods.
4. Determine and justify an appropriate number of clusters.
5. Evaluate cluster quality using internal, external, and stability-based evidence.
6. Interpret clusters for scientific, operational, and managerial decisions.
7. Identify limitations, ethical risks, and best practices in segmentation projects.

1. Foundations of Clustering

Let a dataset contain n observations and p measured attributes. Observation i can be represented by a vector xᵢ = (xᵢ₁, xᵢ₂, …, xᵢₚ). Clustering seeks a partition or grouping of observations such that objects within the same group are more similar than objects in different groups.

A hard partition assigns each observation to exactly one cluster. A soft or fuzzy clustering allows an observation to have degrees of membership in several clusters. Some methods also identify noise or outlier observations that do not belong convincingly to any cluster.

Important terms include:

• Object or observation: an entity being grouped, such as a customer or image.
• Feature or attribute: a measured property of an object.
• Cluster: a collection of observations with a specified pattern of similarity.
• Centroid: the mean vector of observations in a cluster.
• Medoid: an actual observation chosen as the representative of a cluster.
• Prototype: a representative parameter or point for a cluster.
• Noise: observations treated as insufficiently associated with any cluster.
• Partition: an assignment of observations to clusters.
• Segmentation: the interpretation and use of clusters as meaningful subpopulations.

The meaning of “similar” is domain-dependent. Two customers may be similar by annual spending but different by product preference. Two documents may be similar by word usage but not by topic if the representation is poor. Consequently, feature engineering and similarity measurement are as important as algorithm choice.

2. Data Representation and Similarity

2.1 Variable types and preprocessing

Clustering methods generally operate on numerical representations. Common variable types require different treatment:

Variables measured on large numerical scales can dominate a distance calculation. A common standardization is

where xᵢⱼ is the value of feature j for observation i, μⱼ is the sample mean of feature j, and σⱼ is its sample standard deviation. This transformation produces dimensionless values with mean approximately 0 and standard deviation approximately 1, provided σⱼ > 0. It is appropriate when relative deviations from the mean are meaningful and extreme outliers are not overwhelming. Robust alternatives use the median and interquartile range.

Missing values should not silently be converted to zero. They may be imputed, handled through a distance measure that ignores unavailable components, or used to exclude unreliable observations. The chosen strategy can alter the clusters and should be documented.

2.2 Distance and similarity measures

The Euclidean distance between two p-dimensional numerical vectors is

It is appropriate for continuous variables when dimensions have comparable scales and straight-line separation is meaningful. Squared Euclidean distance is often used computationally because it preserves the ordering of distances while avoiding square roots.

The Manhattan distance is

It can be more robust than Euclidean distance when differences accumulate additively or when moderate coordinate deviations are preferable to one very large deviation.

For nonnegative count or frequency vectors, cosine similarity measures angle rather than magnitude:

where x · y is the dot product and ||x|| is the Euclidean norm. Cosine distance is commonly defined as 1 − cos(θ). It is useful for text, where document length should not dominate topic similarity, provided neither vector is the zero vector.

For binary variables, the Jaccard similarity is

where a is the number of attributes equal to 1 for both objects, b is the number equal to 1 for A only, and c is the number equal to 1 for B only. Joint zeros are ignored, making Jaccard similarity suitable when shared absence is uninformative, such as product-purchase data.

A distance measure should satisfy the needs of the data and algorithm. Mixing categorical and numerical variables may require a composite measure such as Gower dissimilarity. The analyst must also decide whether features should receive equal, domain-informed, or learned weights.

3. Partitioning Methods

Partitioning algorithms choose a specified number k of clusters and optimize an objective function. They are efficient for many datasets but usually require k in advance.

3.1 K-means clustering

K-means represents each cluster by its centroid and minimizes the within-cluster sum of squared Euclidean distances:

Here Cᵣ is cluster r, μᵣ is its centroid, k is the number of clusters, and ||xᵢ − μᵣ||² is squared Euclidean distance. The objective is appropriate for numerical features when compact, approximately spherical clusters are plausible.

The standard iterative procedure is:

1. Select k initial centroids.
2. Assign each observation to its nearest centroid.
3. Recalculate each centroid as the mean of observations assigned to it.
4. Repeat assignment and recalculation until assignments stabilize or improvement becomes negligible.

For cluster Cᵣ with nᵣ observations, its centroid is

K-means converges to a local optimum, not necessarily the global optimum. Therefore, multiple initializations are recommended. K-means is sensitive to outliers because both squared distances and means are affected strongly by extreme observations. It also performs poorly for elongated, nested, or differently sized clusters.

Worked example. Consider one-dimensional observations 1, 2, 3, 10, 11, and 12 with k = 2. If the initial clusters are C₁ = {1, 2, 3} and C₂ = {10, 11, 12}, the centroids are μ₁ = 2 and μ₂ = 11. The squared-error objective is

(1−2)² + (2−2)² + (3−2)² + (10−11)² + (11−11)² + (12−11)² = 4.

This is a strong partition because the observations form two compact separated groups. A different initialization may temporarily produce a poorer partition, which is why repeated starts are important.

3.2 K-medoids

K-medoids resembles k-means but uses actual observations as representatives. Because a medoid is not an arithmetic mean, the method can be more robust to outliers and can operate with arbitrary dissimilarity measures. Its disadvantages include greater computational cost, especially for very large datasets.

3.3 Choosing k

No single method determines the correct number of clusters in all applications. Useful evidence includes:

• Elbow method: plot within-cluster sum of squares against k and look for a point after which improvement diminishes.
• Silhouette analysis: assess whether observations are closer to their own cluster than to neighboring clusters.
• Gap statistic: compare observed within-cluster dispersion with a reference null distribution.
• Stability: repeat clustering on resampled or perturbed data and measure agreement.
• Domain utility: assess whether the segments support a real decision or scientific interpretation.

The elbow is a heuristic rather than a theorem. A visually clear elbow may not exist, and a statistically attractive k may be operationally useless.

4. Hierarchical Clustering

Hierarchical clustering produces a nested sequence of groupings represented by a dendrogram. It does not require selecting the final number of clusters before constructing the hierarchy.

4.1 Agglomerative procedure

Agglomerative hierarchical clustering begins with every observation as a separate cluster:

1. Start with n singleton clusters.
2. Find the two closest clusters.
3. Merge them.
4. Recalculate intercluster distances.
5. Continue until one cluster remains.

A horizontal cut through the dendrogram produces a selected number of groups.

4.2 Linkage criteria

The linkage rule defines distance between clusters:

• Single linkage: minimum pairwise distance. It can identify chain-shaped structures but is vulnerable to chaining.
• Complete linkage: maximum pairwise distance. It favors compact clusters but can be sensitive to outliers.
• Average linkage: average pairwise distance, offering a compromise.
• Ward’s method: merges clusters causing the smallest increase in total within-cluster squared error. It is primarily appropriate for numerical data and squared Euclidean geometry.

Hierarchical clustering is interpretable because the dendrogram shows relationships at multiple resolutions. However, early merges cannot normally be undone, and computational and memory requirements can be substantial for large datasets.

5. Density-Based Clustering

Density-based methods define clusters as regions of high observation density separated by low-density regions. They can discover irregular shapes and identify noise, advantages that k-means lacks.

5.1 DBSCAN

DBSCAN uses two parameters: ε, the neighborhood radius, and MinPts, the minimum number of observations required to form a dense neighborhood. An observation is a core point if its ε-neighborhood contains at least MinPts points, according to the implementation’s counting convention. Points reachable through connected core points form clusters; nearby non-core points may be border points; points not assigned to a cluster are noise.

DBSCAN is effective when clusters have comparable density and when ε can be selected meaningfully. It struggles with clusters whose densities differ substantially and with high-dimensional data, where distances become less discriminative. Scaling and parameter diagnostics are essential.

5.2 Related methods

OPTICS orders observations to expose density structure across multiple scales and can be useful when one ε value is inadequate. HDBSCAN builds a hierarchy of density-based clusters and can select stable groups across density levels. These methods are powerful but require careful interpretation of parameters and stability outputs.

6. Model-Based Clustering

Model-based clustering assumes that data are generated by a mixture of probability distributions. The most common example is a Gaussian mixture model (GMM):

Here πᵣ is the mixing proportion of component r, with πᵣ ≥ 0 and ∑πᵣ = 1; 𝒩(x | μᵣ, Σᵣ) is a multivariate normal density with mean vector μᵣ and covariance matrix Σᵣ. The model assumes that observations arise from one of k latent components and that the selected distribution is a reasonable approximation.

Parameters are commonly estimated using expectation–maximization (EM):

1. Expectation step: calculate each observation’s posterior probability of belonging to each component.
2. Maximization step: update mixing proportions, means, and covariance matrices using those probabilities.
3. Repeat until the likelihood improvement is small.

The posterior responsibility of component r for observation xᵢ is

The responsibilities satisfy 0 ≤ γᵢᵣ ≤ 1 and ∑ᵣγᵢᵣ = 1. They provide soft membership rather than a forced hard assignment.

Model selection can use the Bayesian information criterion (BIC):

where L is the maximized likelihood, q is the number of estimated parameters, and n is the number of observations. Smaller BIC is preferred among comparable fitted models. BIC balances fit against complexity under regular model-selection assumptions; it should not be treated as an absolute proof that a clustering is meaningful.

7. Cluster Validation and Interpretation

7.1 Internal validation

Internal indices use only the data and cluster assignments. The silhouette coefficient for observation i is

where a(i) is the mean distance from i to points in its own cluster and b(i) is the smallest mean distance from i to another cluster. Values range from −1 to 1. A value near 1 indicates good separation, a value near 0 indicates overlap, and a negative value suggests possible misassignment.

The mean silhouette is useful for comparison, but it favors certain geometries and may penalize legitimate unequal-density structures. Other measures include the Calinski–Harabasz index and Davies–Bouldin index; each encodes particular assumptions.

7.2 External validation

If trusted reference labels exist, cluster assignments can be compared with them using adjusted Rand index, normalized mutual information, purity, or domain-specific agreement. External labels should not automatically be regarded as ground truth: they may be noisy, biased, or based on a different concept from the clustering objective.

7.3 Stability and practical validity

A credible cluster should be reasonably stable under resampling, small perturbations, and plausible preprocessing choices. Practical validity asks whether clusters predict outcomes, support differentiated actions, or correspond to scientifically meaningful mechanisms. Statistical separation without usable interpretation is not sufficient.

Interpretation should include cluster sizes, feature summaries, uncertainty, representative cases, and comparisons with the overall population. Labels such as “high-value loyalists” are hypotheses about meaning, not facts established by the algorithm.

8. A Professional Clustering Workflow

A defensible workflow is:

1. Define the purpose. Specify the decision, scientific question, or operational use.
2. Construct the analytical population. Avoid leakage from future information and document inclusion rules.
3. Inspect and prepare data. Address missingness, outliers, duplicates, skew, and scale.
4. Select features. Use domain knowledge and avoid redundant variables that unintentionally overweight one concept.
5. Choose representations and distances. Match them to variable types and the intended notion of similarity.
6. Fit several plausible algorithms. Compare partitioning, hierarchical, density-based, or model-based alternatives where appropriate.
7. Assess cluster number and parameters. Combine quantitative diagnostics, stability, and domain judgment.
8. Validate and visualize. Use projections such as PCA cautiously; a two-dimensional plot may distort high-dimensional relationships.
9. Profile clusters. Report distributions, uncertainty, size, representative observations, and distinguishing variables.
10. Deploy and monitor. Reassess drift, fairness, usefulness, and stability over time.

9. Illustrative Case: Retail Customer Segmentation

Background

A fictional online retailer wants to tailor retention and communication strategies. It has twelve months of customer-level data including purchase frequency, monetary value, average order value, discount usage, and days since last purchase.

Problem

The retailer currently sends the same promotion to all customers. Management wants segments that are interpretable, sufficiently large for action, and not based on sensitive personal characteristics.

Analysis

The analyst first excludes customers with incomplete account histories and defines a fixed observation window. Monetary variables are highly right-skewed, so a justified transformation is considered. Features are standardized after transformation. The team compares k-means, k-medoids, and a Gaussian mixture model. A range of candidate k values is evaluated using silhouette values, resampling stability, cluster size, and campaign usefulness.

Suppose a four-segment solution is selected after review:

These names summarize observed patterns; they do not explain why customers behave that way. The team checks whether clusters remain similar under alternative scaling, feature subsets, and random seeds. It also tests whether segment membership predicts future retention without using future outcomes in the clustering construction.

Outcome

The retailer pilots differentiated campaigns on a randomized basis. It evaluates incremental retention and profit rather than merely response rates. If the “at-risk” segment responds poorly, the result may indicate that the segment is not actionable or that the intervention is unsuitable—not necessarily that the clustering is mathematically incorrect.

Learning points

The case demonstrates that segmentation is a decision system, not just an algorithmic output. Feature definitions, temporal leakage, stability, ethical restrictions, experimental evaluation, and managerial interpretation all affect value.

10. Challenges, Ethics, and Governance

Clustering can reproduce historical inequality. If sensitive attributes or close proxies are used, segments may enable discriminatory pricing, exclusion, or unequal access. Even when sensitive attributes are omitted, location, browsing behavior, language, or purchasing patterns may act as proxies.

Important governance practices include:

• define a legitimate purpose and data-minimization policy;
• document features, preprocessing, algorithms, parameters, and validation;
• assess whether segments create disparate impacts across protected groups;
• restrict high-risk uses such as insurance, employment, credit, or essential services unless legally and ethically justified;
• provide appropriate transparency and avenues for review;
• protect personal data through access controls, retention limits, and secure processing;
• monitor model and population drift after deployment.

A cluster label should not be treated as an immutable identity. People and organizations change, measurements are incomplete, and uncertainty should be communicated. In high-stakes settings, human review and contestability are essential.

11. Contemporary Developments and Best Practices

Modern systems increasingly combine clustering with representation learning. Embeddings from language, vision, or recommendation models can capture complex relationships, but they may be difficult to interpret and can encode biases from training data. Applying a clustering algorithm to an embedding does not remove the need for validation.

Scalable implementations use approximate nearest-neighbor search, distributed computation, mini-batch k-means, and sampling. Streaming applications require monitoring because cluster centers and densities may drift. Deep embedded clustering methods jointly learn representations and clusters, but optimization may become less transparent and sensitive to initialization.

Best practice is to prefer the simplest method that meets the purpose, compare multiple reasonable representations, report sensitivity analyses, and distinguish descriptive segmentation from causal explanation. Clustering reveals association and structure; it does not by itself establish that changing a feature will cause a desired outcome.

Chapter Summary

Clustering discovers groups without predefined labels, while segmentation interprets and applies those groups. Reliable results depend on data representation, preprocessing, similarity measurement, algorithm assumptions, and validation. K-means is efficient for compact numerical clusters; k-medoids is more robust and supports general dissimilarities; hierarchical methods reveal nested structure; density-based methods detect irregular groups and noise; and model-based methods provide probabilistic soft membership.

The number of clusters should be selected using complementary evidence, including internal indices, stability, model criteria, and domain usefulness. Silhouette analysis and BIC are informative but assumption-dependent. A professional workflow defines the purpose, prevents leakage, prepares data, compares methods, validates stability, profiles segments, and monitors deployment. Ethical governance is essential because segmentation can amplify bias, enable discrimination, or obscure uncertainty.

Key Terms

Clustering: Unsupervised grouping of observations according to similarity.

Segmentation: Application of clustering to define and act on meaningful subpopulations.

Partition: Assignment of observations to clusters.

Hard clustering: Assignment of each observation to one cluster.

Soft clustering: Assignment using degrees or probabilities of membership.

Centroid: Mean vector representing a numerical cluster.

Medoid: Actual observation representing a cluster.

Euclidean distance: Straight-line distance between numerical vectors.

Manhattan distance: Sum of absolute coordinate differences.

Cosine similarity: Similarity based on the angle between vectors.

Jaccard similarity: Binary similarity based on shared presences.

K-means: Partitioning algorithm minimizing within-cluster squared error.

Hierarchical clustering: Method producing nested groupings and a dendrogram.

Linkage: Rule defining distance between clusters.

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

Noise: Observations not assigned to a meaningful density-based cluster.

Gaussian mixture model: Probabilistic mixture model for soft clustering.

Silhouette coefficient: Internal measure of cohesion and separation.

Cluster stability: Consistency of clusters under perturbation or resampling.

Data leakage: Use of information unavailable at the intended prediction or decision time.

Review Questions

Short Answer Questions

1. What is the difference between clustering and classification?
2. Why should numerical features often be standardized before clustering?
3. State one strength and one limitation of k-means.
4. What does a dendrogram represent?
5. What is the purpose of the silhouette coefficient?

Long Answer Questions

1. Compare k-means, hierarchical, density-based, and model-based clustering with respect to assumptions, outputs, strengths, and limitations.
2. Explain how Euclidean, Manhattan, cosine, and Jaccard measures differ and identify a suitable application for each.
3. Describe a complete workflow for developing a responsible customer segmentation system.
4. Explain the expectation–maximization approach for Gaussian mixture clustering and interpret posterior responsibilities.
5. Discuss why selecting the number of clusters is both a statistical and a domain-specific problem.

Analytical / Application Questions

1. A dataset contains income, purchase count, and product categories encoded as binary variables. Propose a preprocessing and similarity strategy, and justify your choices.
2. A DBSCAN analysis labels 35% of observations as noise while k-means produces four compact groups. Design a validation plan before choosing either result.
3. A bank proposes using clusters of applicants to assign different interest rates. Identify ethical, legal, methodological, and governance questions that must be addressed before deployment.

Multiple Choice Questions with Answers

Question 1

Which objective does standard k-means minimize?

A. The maximum distance between any two observations

B. The within-cluster sum of squared Euclidean distances

C. The number of observations treated as noise

D. The average cosine similarity between all observations

Correct Answer: B. The within-cluster sum of squared Euclidean distances

Question 2

Which distance is especially appropriate when the direction of two text-frequency vectors matters more than their magnitude?

A. Cosine distance

B. Manhattan distance

C. Hamming distance

D. Maximum distance

Correct Answer: A. Cosine distance

Question 3

What is a principal advantage of density-based clustering such as DBSCAN?

A. It always identifies the globally optimal partition

B. It requires no parameter choices

C. It can identify irregular shapes and label some observations as noise

D. It assumes every cluster is spherical

Correct Answer: C. It can identify irregular shapes and label some observations as noise

Question 4

In agglomerative hierarchical clustering, what happens at the beginning?

A. All observations begin in one cluster

B. Each observation begins as its own cluster

C. The number of clusters is fixed at two

D. Only outliers are assigned to clusters

Correct Answer: B. Each observation begins as its own cluster

Question 5

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

A. Closer to another cluster than to its own cluster

B. Equally distant from 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 6

Which statement about k-means is correct?

A. It is guaranteed to find the global optimum from one initialization

B. It is usually sensitive to feature scaling and outliers

C. It requires categorical variables only

D. It always detects clusters of unequal density

Correct Answer: B. It is usually sensitive to feature scaling and outliers

Question 7

In a Gaussian mixture model, the value γᵢᵣ represents:

A. The standardized value of feature r

B. The posterior membership probability of observation i in component r

C. The number of clusters in the model

D. The distance between two centroids

Correct Answer: B. The posterior membership probability of observation i in component r

Question 8

According to the BIC expression used in the chapter, increasing model complexity is penalized by:

A. Removing the likelihood term

B. Adding q log(n) to the criterion

C. Dividing the sample size by the number of features

D. Setting all mixing proportions to zero

Correct Answer: B. Adding q log(n) to the criterion

Question 9

Why are joint zeros ignored in the Jaccard similarity?

A. Because Jaccard is defined only for continuous data

B. Because shared absence is treated as uninformative

C. Because zeros cannot be stored in a binary vector

D. Because the measure requires negative values

Correct Answer: B. Because shared absence is treated as uninformative

Question 10

Which practice best reduces the risk of temporal leakage in customer segmentation?

A. Using future purchases to define segments for an earlier campaign

B. Defining features only from information available during the observation window

C. Replacing missing values with future outcomes

D. Selecting clusters solely by campaign response after deployment

Correct Answer: B. Defining features only from information available during the observation window