9. Clustering, Segmentation and Anomaly Detection

Introduction and Context

Much of data mining is concerned with labelled prediction: a model is trained from examples for which the outcome is already known. Many important organizational problems, however, do not provide such labels. A retailer may know the purchasing history of customers but not their natural market groups; a bank may possess millions of transaction records but only a small number of confirmed fraud cases; and a manufacturer may collect sensor readings without knowing in advance which combinations indicate equipment failure. Clustering and anomaly detection address these situations by discovering structure in data rather than relying entirely on predefined classes.

Clustering groups observations so that members of the same group are more similar to one another than to members of other groups. Segmentation is the broader business and analytical activity of dividing a population, market, image, document collection, network, or operational process into meaningful subgroups. Anomaly detection identifies observations, events, or patterns that depart substantially from expected behaviour. Although these tasks are related, they are not interchangeable. A cluster represents a recurring pattern, whereas an anomaly may be rare, isolated, or located in a low-density region.

This chapter examines partitioning, hierarchical, density-based, and probabilistic clustering, together with similarity measures, cluster-validation criteria, segmentation practice, novelty detection, and anomaly detection. The emphasis is not merely on algorithms, but on selecting and interpreting methods in real data-mining systems.

Learning Objectives

After studying this chapter, the reader should be able to:

1. Distinguish clustering, segmentation, classification, novelty detection, and anomaly detection.

2. Select appropriate distance or similarity measures for different data types.

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

4. Evaluate clustering results using internal, external, and stability-based criteria.

5. Design segmentation workflows for business and technical applications.

6. Identify global, contextual, and collective anomalies and select suitable detection strategies.

7. Interpret the ethical, operational, and governance risks associated with unsupervised analytics.

The Logic of Similarity

Every clustering method depends on a representation of similarity. A clustering algorithm does not discover similarity in an abstract sense; it discovers groups according to the variables, transformations, and metric supplied by the analyst. Consequently, feature engineering and distance selection may affect results more strongly than the choice between two sophisticated algorithms.

For numerical vectors, Euclidean distance is commonly defined as

\[

d(x,y)=\sqrt{\sum_{j=1}^{p}(x_j-y_j)^2}.

\]

It is appropriate when variables are comparable in scale and differences have meaningful magnitude. Manhattan distance, \(\sum_j|x_j-y_j|\), is often less sensitive to extreme coordinate differences. Standardization is usually necessary when income, age, and transaction count are combined; otherwise, a variable measured in large units can dominate the distance. Robust scaling may be preferable when distributions contain extreme values.

Cosine similarity compares the angle between vectors and is useful for sparse, high-dimensional representations such as document-term matrices. It focuses on orientation rather than magnitude. Jaccard similarity is appropriate for binary presence–absence data, particularly when shared absences are uninformative. Gower’s coefficient can combine numerical, ordinal, categorical, and binary variables, although its variable weighting must be justified. Correlation-based similarity is useful when the shape of a time profile matters more than its absolute level.

Categorical variables require care. Arbitrarily coding “urban,” “rural,” and “suburban” as 1, 2, and 3 introduces a false order. Missing values also require explicit treatment. Imputation, missingness indicators, or distance rules that ignore unavailable coordinates may be used, but each choice changes the resulting geometry. In text, images, graphs, and time series, domain-specific representations often precede clustering: embeddings, frequency features, wavelet coefficients, or graph structural features may be more meaningful than raw data.

Families of Clustering Methods

Partitioning Methods

Partitioning methods divide a dataset into a specified number, \(k\), of non-overlapping groups. The best-known example is k-means. It minimizes within-cluster squared Euclidean error:

\[

J=\sum_{i=1}^{n}\|x_i-\mu_{c(i)}\|^2,

\]

where \(\mu_{c(i)}\) is the centroid of the cluster assigned to observation \(x_i\). The familiar iterative procedure alternates between assigning each observation to its nearest centroid and recalculating centroids until assignments stabilize or improvement becomes negligible.

K-means is computationally efficient and works well for compact, approximately spherical clusters with comparable variance. It is sensitive to initialization, outliers, feature scaling, and the selected value of \(k\). Multiple starts, k-means++, and a deliberate treatment of extreme values improve reliability. K-medoids replaces centroids with actual observations and is more robust to outliers and some non-Euclidean distances, but is generally more computationally expensive.

The objective optimized by k-means should not be confused with a universal definition of a good cluster. K-means can partition data even when no meaningful grouping exists. A low objective value may simply reflect a large value of \(k\), and a visually convincing business segment may not be spherical in feature space.

Hierarchical Methods

Hierarchical clustering produces a nested structure represented by a dendrogram. In agglomerative clustering, every observation begins as a separate cluster; the closest pair is repeatedly merged. The analyst may cut the dendrogram at a selected height or number of groups. Divisive procedures begin with one cluster and recursively split it, although they are less common in routine applications.

The definition of distance between clusters is determined by linkage. Single linkage uses the nearest pair and can identify elongated chains, but is vulnerable to chaining. Complete linkage uses the farthest pair and tends to create compact groups. Average linkage uses the average pairwise distance. Ward’s method merges groups while producing the smallest increase in within-cluster variance and is often effective with standardized numerical variables.

Hierarchical methods are useful when the analyst wants to inspect cluster structure at several resolutions or does not wish to commit to one value of \(k\) initially. Their disadvantages include sensitivity to early merging decisions, metric choice, and computational cost for very large datasets. A dendrogram is an exploratory representation, not proof that every branch corresponds to a substantively real population.

Density-Based Methods

Density-based clustering defines clusters as regions of relatively high observation density separated by low-density areas. DBSCAN uses two parameters: a neighbourhood radius, \(\varepsilon\), and a minimum number of points, MinPts. A core point has at least MinPts observations within its \(\varepsilon\)-neighbourhood. Points density-reachable from core points form clusters; remaining points may be labelled noise.

DBSCAN can discover irregularly shaped clusters and identify noise without assigning every observation to a group. This is especially valuable in spatial analysis and equipment monitoring. Its weaknesses include difficulty when clusters have very different densities and sensitivity to the scale of the variables. Choosing \(\varepsilon\) through a k-distance plot and using domain knowledge can help.

OPTICS creates an ordering that reveals density structure across a range of scales, while HDBSCAN extends density-based reasoning through a hierarchy and can handle variable density more effectively in many applications. These methods are useful when a single global density threshold is inappropriate, although their outputs still require careful interpretation.

Probabilistic and Model-Based Clustering

Probabilistic clustering assumes that observations arise from a mixture of underlying probability distributions. A Gaussian mixture model (GMM), for example, represents the density as

\[

p(x)=\sum_{k=1}^{K}\pi_k\mathcal{N}(x\mid\mu_k,\Sigma_k),

\]

where \(\pi_k\) is the mixing proportion, and each component has a mean vector and covariance matrix. The expectation–maximization algorithm alternates between estimating the probability that each observation belongs to each component and updating component parameters.

Unlike hard clustering, GMM provides soft assignments. An observation may belong to cluster 1 with probability 0.72 and cluster 2 with probability 0.28, which is useful when segment boundaries are gradual. Covariance assumptions determine whether components are spherical, diagonal, or capable of representing correlated ellipses. Model-selection criteria such as AIC or BIC can help compare different numbers of components, but statistical fit does not guarantee business usefulness.

Probabilistic models also support anomaly scoring through low likelihood. Nevertheless, a low-probability observation is not automatically erroneous or malicious. It may represent a valuable emerging segment, a seasonal event, or a legitimate but rare customer.

Choosing the Number and Shape of Clusters

The appropriate number of clusters is a modelling and interpretation decision, not merely an algorithmic output. The elbow method examines how within-cluster error decreases as \(k\) increases and looks for a point at which additional clusters provide diminishing improvement. The silhouette coefficient compares an observation’s average distance from its own cluster with its distance from the nearest alternative cluster. Values near one indicate separation, values near zero indicate overlap, and negative values suggest possible misassignment.

The Calinski–Harabasz index rewards high between-cluster dispersion relative to within-cluster dispersion. The Davies–Bouldin index summarizes similarity between each cluster and its most similar competitor, with lower values generally preferred. These internal indices are useful when labels are unavailable, but they encode geometric assumptions and may disagree.

When trusted labels or known group memberships exist, external measures such as adjusted Rand index, normalized mutual information, precision, recall, or purity can be used. However, using labels from a later business outcome to judge an exploratory segmentation can accidentally turn clustering into disguised supervised modelling.

Stability is often more informative than a single score. The analyst can resample records, perturb features, rerun the algorithm with different seeds, and compare assignments using adjusted Rand similarity or co-clustering frequencies. A solution that changes substantially under small perturbations should not support high-stakes decisions. Subject-matter interpretability is also essential: segments should have distinct profiles, adequate size, operational relevance, and a plausible explanation.

From Clusters to Segments

A cluster becomes a segment only after it is interpreted and connected to an action. A sound segmentation workflow therefore includes four linked stages. First, define the decision problem: retention, product design, resource allocation, fraud investigation, or another purpose. Second, construct a population and feature set that reflect the decision period and avoid leakage from future information. Third, experiment with representations, metrics, algorithms, and validation. Fourth, profile the resulting groups, name them cautiously, test their stability, and connect them to differentiated interventions.

For example, a customer segmentation may use purchase frequency, recency, monetary value, category diversity, service interactions, and channel preference. Demographic variables should not be included simply because they are available. They may add little predictive value, create unfair treatment, or encourage stereotypes. Segment labels such as “high-value loyal customers” should be supported by measurable profiles rather than intuition.

Segmentation is iterative. New campaigns change customer behaviour; products alter demand; and a previously rare group may become significant. Production systems should monitor segment sizes, feature distributions, assignment confidence, and business outcomes. A cluster model trained once on historical data can become stale even if its mathematical implementation continues to run correctly.

Anomaly Detection and Novelty Detection

An anomaly is an observation that is inconsistent with a reference pattern. A point anomaly is unusual by itself, such as an exceptionally large withdrawal. A contextual anomaly is unusual only under particular conditions, such as high electricity consumption at night but not during a factory shift. A collective anomaly is a sequence or set whose combined pattern is abnormal even when individual records appear ordinary.

Novelty detection differs in its training assumption. In novelty detection, the training data are presumed to represent normal behaviour, and the model identifies future observations that depart from it. In unsupervised anomaly detection, the training data may contain an unknown mixture of normal and abnormal cases. This distinction affects algorithm choice, thresholds, and evaluation.

Simple statistical methods use z-scores, robust medians and median absolute deviation, quantiles, or parametric distributions. They are transparent but can fail in multivariate settings, where each variable is individually normal while their combination is unusual. Mahalanobis distance accounts for covariance, though it is sensitive to covariance estimation and distributional assumptions.

Isolation Forest detects anomalies by randomly partitioning features. Anomalies tend to be isolated in fewer splits than ordinary observations. Local Outlier Factor compares local density with that of neighbouring points and can identify observations that are unusual relative to their immediate context. One-class support vector machines learn a boundary around normal observations. Autoencoders learn to reconstruct common patterns; high reconstruction error can be used as an anomaly score, provided the model has not learned to reconstruct anomalies equally well.

Anomaly scores usually require a threshold. A fixed percentile, a cost-sensitive threshold, a control-limit procedure, or analyst review may be appropriate. Threshold selection should reflect false-positive investigation costs and false-negative consequences. In fraud detection, a very low threshold may overwhelm investigators; in safety monitoring, missing a dangerous event may be unacceptable.

Applied Case: Segmenting and Monitoring an Industrial Cold-Chain Network

Background

Consider an illustrative case involving a food-distribution company operating refrigerated vehicles. Each vehicle transmits temperature, humidity, door status, location, battery voltage, and compressor-current readings at five-minute intervals. The company wants to improve maintenance planning and detect conditions that could spoil products.

Situation and Problem

The existing system uses a single temperature limit. It generates many alerts during loading, when doors are open, but sometimes fails to identify gradual compressor degradation. Vehicles operate in different climates, routes, and loading patterns, so a common threshold does not represent normal behaviour equally well.

Analysis

The analytics team first defines operating contexts: loading, transit, delivery, and parked. It removes impossible sensor readings, records missingness, aligns timestamps, and creates window-level features such as mean temperature, temperature variability, recovery time after door opening, compressor-current trend, and frequency of excursions. Features are standardized within appropriate contexts, and future measurements are excluded from training to prevent leakage.

A hierarchical exploration suggests two broad operating regimes, but the team uses a Gaussian mixture model to represent overlapping patterns: stable cooling, high-intervention delivery, and weak recovery behaviour. Soft assignments are useful because a vehicle may move gradually from one regime to another. Stability testing across weeks shows that the regimes are reproducible, while interviews with maintenance engineers confirm that the profiles are operationally meaningful.

For anomaly detection, an Isolation Forest is trained primarily on verified healthy windows. Local density scoring is added because a temperature increase that is normal during loading may be abnormal during transit. A sequence rule detects collective anomalies: repeated short excursions followed by progressively slower recovery. Alerts are ranked by anomaly score, product exposure, and confidence rather than sent as an undifferentiated stream.

Approach and Solution

The company deploys a two-layer system. The segmentation layer assigns each vehicle-window to an operating profile and provides a baseline appropriate to that profile. The anomaly layer detects deviations from the baseline. Maintenance staff receive explanations including the relevant time window, contributing variables, comparison with similar vehicles, and whether the event is isolated or recurrent.

Outcome

In this illustrative case, the important improvement is not the selection of one algorithm but the integration of context, segmentation, anomaly scoring, and human review. The system reduces nuisance alerts while making gradual deterioration visible earlier. Its performance is monitored using confirmed maintenance events, alert-review time, missed-event analysis, and drift in vehicle operating profiles.

Learning Points

The case demonstrates that anomaly detection is relational: the same value can be normal in one context and abnormal in another. It also shows why unsupervised outputs require domain validation, why temporal features matter, and why operational adoption depends on explanations and workflow integration.

Risks, Limitations, and Professional Judgement

Clustering can produce apparently coherent groups from random variation. High-dimensional data suffer from distance concentration, making nearest-neighbour relationships less informative. Dimensionality reduction may improve visualization but can distort distances. Outliers can pull centroids, while removing them blindly may eliminate the very cases an anomaly system should discover.

Another danger is circular interpretation. If analysts inspect many possible clusterings and report only the most attractive one, the apparent discovery may be a result of selection bias. Validation should therefore be planned, documented, and, where possible, confirmed on new data. Business labels should not be assigned solely from algorithmic output.

Fairness is central when segments influence pricing, credit, employment, insurance, or access to services. Unsupervised methods can reproduce historical inequality even when protected attributes are omitted, because proxy variables may remain. Organizations should assess disparate impact, provide human oversight, document purposes and features, and avoid treating a cluster membership as a moral or fixed characteristic.

Privacy risks arise because clustering can reveal sensitive communities or infer attributes that individuals did not disclose. Data minimization, access controls, retention limits, secure computation, and clear governance are therefore relevant. In regulated settings, records of feature definitions, model versions, thresholds, validation results, and review decisions support auditability.

Technology and Emerging Directions

Modern platforms provide scalable implementations of k-means, hierarchical approximations, DBSCAN variants, mixture models, and streaming anomaly detection. Distributed processing is valuable for large datasets, while approximate nearest-neighbour indexes support high-dimensional similarity search. Embedding-based clustering is increasingly used for text, images, and multimodal data, but embeddings can encode social and cultural biases and may be difficult to interpret.

Streaming systems treat clustering and anomaly detection as continuously updated processes. Concept drift occurs when the underlying data-generating process changes; concept evolution occurs when new types of behaviour appear. Adaptive thresholds, sliding windows, online models, and drift detectors can address these changes, but they may also absorb emerging anomalies into the definition of normal. Human review and periodic revalidation remain necessary.

Explainable anomaly detection is another important direction. Rather than reporting only a score, systems identify contributing features, comparable reference cases, temporal context, and uncertainty. In high-stakes settings, calibrated uncertainty and a clear escalation procedure are more valuable than an opaque ranking with impressive average accuracy.

Best-Practice Framework

A defensible clustering or anomaly-detection project should:

• define the decision and the meaning of similarity before selecting an algorithm;
• inspect distributions, missingness, outliers, scale, and temporal structure;
• use representations and metrics appropriate to the data type;
• compare more than one plausible method and document parameter choices;
• evaluate geometry, stability, interpretability, and operational usefulness;
• separate development, validation, and post-deployment monitoring;
• use soft assignments or confidence information where boundaries are uncertain;
• set anomaly thresholds according to consequences and investigation capacity;
• involve domain experts in labelling, validation, and alert design; and
• review fairness, privacy, security, drift, and governance throughout the lifecycle.

Chapter Summary

Clustering discovers structure without requiring predefined labels, while segmentation converts discovered groups into interpretable and actionable populations. Partitioning methods are efficient but depend on the number and geometry of clusters; hierarchical methods reveal nested structure; density-based methods handle irregular shapes and noise; and probabilistic models provide soft memberships and likelihood-based interpretations. Similarity measures must match the data representation, and scaling, missing values, and feature construction are fundamental modelling decisions.

Cluster validity requires more than one internal score. Elbow analysis, silhouette, distributional checks, stability testing, external evidence, and domain interpretation should be considered together. Anomaly detection identifies point, contextual, and collective departures from expected behaviour. Novelty detection assumes a predominantly normal training set, whereas unsupervised detection faces possible contamination. Statistical, density-based, isolation, boundary, and reconstruction methods each make different assumptions. Successful professional systems combine technical methods with context, threshold governance, explanations, human review, fairness assessment, privacy protection, and monitoring for drift.

Key Terms

Similarity measure: A rule for quantifying resemblance or dissimilarity between observations.

Euclidean distance: The straight-line distance between numerical vectors.

Cosine similarity: A measure based on the angle between two vectors.

Partitioning clustering: Clustering that directly divides observations into a selected number of groups.

Centroid: The mean vector representing a cluster in methods such as k-means.

K-medoids: A partitioning method whose cluster representatives are actual observations.

Hierarchical clustering: A method that creates a nested sequence of cluster mergers or divisions.

Dendrogram: A tree-like diagram representing hierarchical cluster relationships.

Linkage: The rule used to calculate distance between clusters.

Density-based clustering: Clustering that defines groups as dense regions separated by sparse regions.

Core point: In DBSCAN, a point having at least the required number of neighbours within a specified radius.

Gaussian mixture model: A probabilistic model representing data as a mixture of Gaussian components.

Soft assignment: Membership expressed as probabilities rather than a single fixed cluster label.

Silhouette coefficient: An internal measure comparing within-cluster cohesion with nearest-cluster separation.

Point anomaly: An individual observation that is unusual in isolation.

Contextual anomaly: An observation that is abnormal under a particular context.

Collective anomaly: A group or sequence that is abnormal as a combination.

Novelty detection: Detection of departures from a model trained primarily on normal data.

Concept drift: Change over time in the data-generating process or behavioural relationship.

Cluster stability: The consistency of clustering results under resampling, perturbation, or reruns.

Review Questions

Short Answer Questions

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

2. Distinguish a cluster from a business segment.

3. What is the purpose of linkage in hierarchical clustering?

4. Differentiate point, contextual, and collective anomalies.

5. What distinguishes novelty detection from unsupervised anomaly detection?

Long Answer Questions

1. Explain k-means, including its objective, procedure, assumptions, and limitations.

2. Compare hierarchical, density-based, and probabilistic clustering in terms of cluster shape, noise handling, and interpretability.

3. Discuss internal, external, and stability-based approaches to cluster validation.

4. Explain how similarity measures should be selected for numerical, categorical, binary, text, and temporal data.

5. Describe a complete workflow for developing a production segmentation system.

Analytical / Application Questions

1. A retailer’s data contain purchase frequency, monetary value, product categories, and channel indicators. Recommend a representation, similarity strategy, clustering approach, and validation plan, giving reasons for each choice.

2. A bank receives many fraud alerts during holiday periods but misses coordinated low-value transactions. Explain how contextual and collective anomaly detection could improve the system.

3. A factory’s anomaly model produces different clusters each week despite similar operating conditions. Diagnose possible causes and propose a technically and organizationally defensible response.

22. Multiple Choice Questions with Answers

Question 1

Which situation is most suitable for density-based clustering rather than standard k-means?

A. Compact spherical groups with similar variance and a known value of k

B. Irregularly shaped groups containing substantial noise and no requirement to assign every point

C. A dataset in which every observation has a trusted class label

D. A dataset containing only one numerical variable with no outliers

Correct Answer: B. Irregularly shaped groups containing substantial noise and no requirement to assign every point

Question 2

Why can unstandardized numerical features distort k-means results?

A. They prevent the algorithm from recalculating centroids

B. They force every cluster to contain the same number of observations

C. Variables with larger measurement scales can dominate distance calculations

D. They convert hard assignments into probabilistic assignments

Correct Answer: C. Variables with larger measurement scales can dominate distance calculations

Question 3

What is the main interpretive advantage of a Gaussian mixture model over ordinary k-means?

A. It always discovers the globally optimal number of clusters

B. It provides probabilistic, or soft, cluster memberships

C. It is unaffected by covariance among variables

D. It automatically removes all anomalous observations

Correct Answer: B. It provides probabilistic, or soft, cluster memberships

Question 4

A point has a normal temperature value individually, but that value is abnormal for a night-time operating context. What type of anomaly is this?

A. Point anomaly

B. Contextual anomaly

C. Collective anomaly

D. Sampling anomaly

Correct Answer: B. Contextual anomaly

Question 5

Which criterion primarily evaluates whether clustering results remain similar after resampling or rerunning the algorithm?

A. Cluster stability

B. Euclidean scaling

C. Purity alone

D. Centroid magnitude

Correct Answer: A. Cluster stability

Question 6

What is a major weakness of single-linkage hierarchical clustering?

A. It cannot create a dendrogram

B. It requires probability distributions for all variables

C. It may produce chaining through successive nearest-neighbour links

D. It can only be used with labelled data

Correct Answer: C. It may produce chaining through successive nearest-neighbour links

Question 7

In the cold-chain case, why was a context-sensitive anomaly system preferable to one universal temperature threshold?

A. Temperature has no relevance to refrigerated transport

B. The same reading may be normal during loading but abnormal during transit

C. Universal thresholds always require categorical variables

D. Context-sensitive systems do not require validation

Correct Answer: B. The same reading may be normal during loading but abnormal during transit

Question 8

Which statement best describes novelty detection?

A. It assumes the training data are primarily representative of normal behaviour

B. It requires every training observation to have a different class label

C. It only identifies anomalies in categorical variables

D. It is identical to supervised classification with balanced classes

Correct Answer: A. It assumes the training data are primarily representative of normal behaviour

Question 9

Why should a low probabilistic model likelihood not automatically be treated as proof of fraud or error?

A. Low likelihood is impossible in a mixture model

B. Rare observations may be legitimate, valuable, seasonal, or emerging behaviour

C. Probabilistic models cannot process numerical data

D. Likelihood scores are always equal for all observations

Correct Answer: B. Rare observations may be legitimate, valuable, seasonal, or emerging behaviour

Question 10

Which practice best supports responsible use of clustering in high-stakes decisions?

A. Treat cluster membership as a permanent personal characteristic

B. Remove all unusual observations before modelling

C. Document features and validation, assess fairness, and retain human oversight

D. Select the model solely according to the largest number of clusters

Correct Answer: C. Document features and validation, assess fairness, and retain human oversight