Outlier Detection

Outlier Detection

Overview

Outlier detection, also called anomaly detection, asks which data objects behave so differently from what is expected that they may have been generated by a different mechanism. The central difficulty is that “different” is not absolute: it depends on the representation, the application, the context, the relationships among objects, and the model of normality. This chapter therefore develops several complementary views of abnormality rather than a single universal detector.

The progression is: first define what kind of outlier is sought; then choose a model of normal behavior. Statistical methods flag low-probability observations, proximity methods look for unusually isolated or low-density points, reconstruction methods exploit the fact that regular data admit concise representations, and clustering/classification methods use group structure or learned class boundaries. Contextual and collective outliers require extra structure beyond independent points. Finally, high-dimensional data motivate subspace search, ensembles, and learned embeddings because ordinary distance and density become unreliable.

Exam: ★★★★★

Foundations: What Counts as an Outlier?

Exam: ★★★★★

Assume a data-generating process produces a data set . An outlier is an object whose behavior deviates substantially from the rest of the data, as though it were generated by another mechanism. This viewpoint is intentionally model-dependent: an observation is not intrinsically anomalous until “expected behavior” and a meaningful deviation measure have been specified. Anomalies are usually rare relative to normal data. Typical applications include suspicious credit-card transactions, medical and industrial monitoring, public-safety and surveillance systems, image/sensor analysis, network intrusion detection, national security, and transaction auditing. A credit-card transaction can be suspicious because its amount is unusual or because several in-person transactions occur within minutes at geographically incompatible locations.

Outlier detection and clustering are related but have different objectives. Clustering organizes the majority patterns of a data set, whereas outlier detection targets the exceptional cases that depart from those patterns. Clustering is usually unsupervised; outlier detection can be supervised, semi-supervised, or unsupervised. Supervised methods model normality and abnormality directly but face severe class imbalance because anomalies are rare; when useful labels exist, they can also reduce false positives by distinguishing unusual-but-legitimate behavior from true anomalies. Semi-supervised methods exploit a small labeled set. Unsupervised methods commonly rely on the implicit assumption that normal objects form sufficiently coherent or clustered structure.

Noise must also be separated conceptually from outliers. Noise is random measurement error or ordinary variation and is usually nuisance variation, whereas an outlier is interesting because it may indicate a different mechanism. A useful anomaly claim therefore needs justification: one should state the assumptions describing normal data and show that the detected object violates them substantially.

Novelty detection is closely related but has a different temporal interpretation. A genuinely new topic or behavior may first appear anomalous; once confirmed as a new normal pattern, novelty detection typically updates the model so later instances are no longer treated as outliers.

Global, contextual, and collective outliers

The slides distinguish three types.

• A global outlier (point anomaly) deviates strongly from the data set as a whole. It is the simplest setting and is the target of many standard detectors. The crucial design choice is the application-appropriate deviation measure.
• A contextual or conditional outlier is anomalous only relative to a specified context. For example, a temperature of 86 degrees may be normal in a Toronto summer but exceptional in winter. Attributes therefore split into contextual attributes, which define the comparison context (such as date and location), and behavioral attributes, which are evaluated within that context (such as temperature, humidity, and pressure).
• A collective outlier is a group whose joint behavior is abnormal even though individual members may be ordinary. A single sick student may not be anomalous, whereas an abrupt day on which 10% of a class is sick may be. Detection therefore needs relationships or structure among objects, not only independent point scores.

A local outlier is a point whose density differs strongly from its local surroundings. Contextual outlier detection can be viewed as a broader framework because the context need not be spatial or density-based. Global detection is a limiting case in which no contextual attributes are used and the whole data set acts as the context. The quality of contextual detection therefore depends both on choosing meaningful contextual attributes and on measuring deviation appropriately in behavioral space. The three outlier types can coexist, and one object can satisfy more than one definition.

Practical challenges and method families

The main challenges are not merely computational. The boundary between normal and abnormal is often gradual rather than sharp; relationships and useful features are application-specific; noisy or low-quality data can create false alarms; and users often need an explanation of why an object is anomalous, not just a score.

The principal model families in the lecture are:

• Statistical/model-based: learn or estimate a probability model and flag observations in low-density or low-probability regions.
• Proximity-based: declare objects anomalous when their neighbors are too far away or when local density is low relative to nearby points.
• Reconstruction-based: learn a succinct representation of normal structure; high reconstruction error or long description length indicates abnormality.
• Clustering/classification-based: derive anomaly decisions from cluster membership, cluster size/density, or a learned boundary for the normal class.

Statistical Approaches

Exam: ★★★★☆

A statistical detector first models how normal objects are generated and then evaluates how plausible each observation is under that model. In a parametric approach, normality is described by a finite-dimensional parameter vector and a density ; smaller fitted density suggests greater outlierness. A nonparametric method estimates the distribution more directly from the observed data and avoids committing to a fixed parametric family.

Univariate Gaussian modeling

For a univariate Gaussian model, assume are generated by . The log-likelihood is

Maximum likelihood gives

The important distinction is that the MLE variance uses denominator , not the unbiased sample-variance denominator .

Robust summaries and Grubbs’ test

A boxplot summarizes a univariate distribution through the lower quartile , median , upper quartile , and the smallest and largest nonoutlying observations used as whisker endpoints. The interquartile range is . Tukey’s common rule flags

Grubbs’ test targets a single extreme observation under an approximately normal univariate model. Define

For a sample of size , the slide gives the critical value

An observation is flagged when , where denotes the relevant Student- critical value with degrees of freedom. The normality assumption is important; Grubbs’ test is not a general-purpose rule for arbitrary heavy-tailed data. The distribution has heavier tails for small degrees of freedom and approaches the standard normal distribution as the degrees of freedom increase, which is the qualitative point illustrated by the slide.

Multivariate data and mixtures

A standard multivariate reduction measures how far an object lies from the sample mean vector after accounting for covariance. The squared Mahalanobis distance is

where is the sample covariance matrix. Unlike Euclidean distance, this rescales correlated and unequal-variance directions through .

The next slide separately writes a Pearson-style statistic

where is the object’s value on dimension and is stated to be the mean on that dimension. A large value is claimed to indicate an outlier.

A single Gaussian can be too restrictive when normal data contain several regimes or clusters. A mixture model instead assumes several parametric components. For two components and ,

with nonnegative mixture weights. The component parameters and weights can be learned by the EM algorithm. Outlierness is again associated with low probability under the fitted mixture, but the model can now represent multimodal normal behavior.

Nonparametric density estimation

A histogram partitions the domain into bins and estimates how common different regions are. A point falling in an empty or very low-frequency bin is suspicious. In the slide example, a bin containing only of the transactions receives inverse-frequency score , whereas a bin receives . The key tuning problem is bin size: excessively wide bins hide local structure, whereas very narrow bins make normal sampling fluctuations appear anomalous.

Kernel density estimation (KDE) removes hard bin boundaries by centering a smooth kernel at every observation. A kernel is nonnegative, integrates to one, and in the lecture is assumed symmetric:

A common choice is the standard Gaussian kernel

Given i.i.d. samples from a random variable with density , the KDE with bandwidth is

The bandwidth controls smoothing: small preserves fine local structure but is noisy; large smooths more aggressively. The slide example uses , a Gaussian kernel, and , giving

Thus the estimate is the average of five Gaussian bumps centered at the observations.

Statistical methods have the advantage that anomaly decisions can be tied to explicit probabilistic assumptions or significance levels. Their weaknesses are model misspecification, potentially expensive inference, and increasing difficulty in high-dimensional spaces.

Proximity-Based Approaches

Exam: ★★★★★

Proximity-based methods replace an explicit probability model by geometry. Their core assumption is that normal points have enough nearby companions. Two versions are emphasized: distance-based detection asks whether a neighborhood contains enough points, while density-based detection asks whether an object’s local density is much lower than that of its neighbors. The latter is crucial when different normal clusters have very different densities.

Distance-based outliers

Let be a distance threshold and a fraction threshold. The lecture defines as a -outlier when

Thus only a small fraction of the database lies within radius of . The parameters encode the anomaly notion directly: larger demands a broader neighborhood, while smaller requires stronger isolation. The slide’s algorithm simply counts points satisfying the radius condition and can terminate once the count exceeds .

This criterion is fundamentally global. A point near a very dense cluster can be locally anomalous while still having many points within a moderate radius, which motivates density-relative methods.

k-distance, reachability distance, and LOF

For an object , the -distance is the distance to its th nearest neighbor, with ties handled so that

• at least other objects lie at distance at most ;
• at most objects lie at strictly smaller distance.

The -distance neighborhood is

Because ties are included, may exceed .

LOF stabilizes local density estimation using the reachability distance. In the slide’s arrow notation,

The quantity is generally asymmetric because the target point’s -distance appears in the maximum. For the local density of , each neighbor contributes the reachability distance from to that neighbor, namely . Hence

For example, if a target neighbor has while its ordinary distance to is only , the reachability distance is clipped to rather than . This prevents an extremely close pair from making the local density estimate artificially large. The local reachability density is the reciprocal of the average reachability distance: high means that sits in a crowded region. The local outlier factor compares the neighbors’ densities with ‘s density:

Therefore indicates a point whose density resembles its neighborhood, whereas indicates that the neighbors are much denser and is a local outlier.

The lecture also defines four reachability-distance extrema for an object :

They bound LOF as

For a point deep inside a cluster of roughly uniform density, direct and indirect scales are similar, making both bounds and the LOF itself close to one.

Reconstruction-Based Approaches

Exam: ★★★★☆

Reconstruction methods exploit regularity rather than explicit density. Normal samples share structure and can often be encoded in a more succinct representation from which their original features are reconstructed accurately. Samples that do not fit that shared structure reconstruct poorly and receive high anomaly scores. Every such method must answer three questions: how to obtain the succinct representation, how to reconstruct the original sample, and how to quantify reconstruction quality.

The lecture’s researcher example makes this concrete. Researchers publishing only in KDD/ICDM can be succinctly represented by “Data Mining,” and those publishing only in FSE/ICSE by “Software Engineering.” Carl publishes in ICDM, FSE, and ICSE; assigning him the succinct representation “Software Engineering” reconstructs only FSE/ICSE and misses ICDM. The discrepancy reveals cross-area behavior and makes Carl the outlier.

Matrix factorization for numerical data

Represent samples with numerical attributes by . A rank- factorization approximates

The rows of provide the succinct basis representation, while row contains coefficients for reconstructing sample :

A natural sample anomaly score is squared reconstruction error

The algorithm is therefore: construct ; learn a low-rank approximation; reconstruct every row; compute ; return the requested number of samples with the largest errors.

In the six-researcher binary example, the original four conference dimensions are compressed to two latent research-area dimensions. John reconstructs exactly as , whereas Carl’s original is reconstructed as , giving nonzero error only for Carl in the illustrated factorization.

A standard way to obtain a low-rank factorization is truncated singular value decomposition:

where the columns of and are left and right singular vectors and is diagonal with nonnegative singular values. For the two-factor form one may set and . SVD has an optimal low-rank approximation property under the usual Euclidean/Frobenius criteria. If is centered, the columns of are the corresponding principal-component directions.

Categorical data and pattern-based compression

One-hot encoding categorical values allows matrix factorization, but a categorical attribute with many values creates many binary columns. This increases computation and can make factor matrices difficult to interpret. Pattern-based compression instead builds a dictionary of reusable attribute-value patterns and encodes each data tuple using one or more code words. The code table records each pattern, its binary code, its usage (how many data tuples are represented using it), and its code length; for outlier detection, the code length rather than the particular bit string is the important quantity.

In the lecture example, common customers with can be represented by one two-bit code, as can the common all-low pattern. Tom with needs the code for plus a separate code for , giving total encoding length five; Jim similarly needs five bits. The longer description indicates that these tuples fit common patterns less economically, so Tom and Jim are flagged as outliers.

Clustering, Classification, and Semi-Supervision

Exam: ★★★☆☆

Clustering can be converted into an anomaly detector in three standard ways. An object is suspicious if it belongs to no cluster, if it lies far from the nearest or assigned cluster, or if it belongs to a very small or sparse cluster. These criteria use the majority structure discovered by clustering but should not be confused with the original clustering objective, which is to organize normal structure rather than explicitly search for rare exceptions.

Classification-based methods face a heavily imbalanced training set because normal samples usually dominate. A common response is one-class classification: learn a boundary describing only the normal class and classify samples outside that learned region as outliers. This avoids requiring a representative catalog of all possible anomaly types.

With a small amount of label information, semi-supervised detection can combine clustering and one-class learning. The lecture proposes the following heuristic:

• cluster the data;
• if a large cluster contains mainly labeled normal objects plus unlabeled objects, pseudo-label those unlabeled objects as normal and fit a one-class model to the cluster;
• if a small cluster contains known outliers together with unlabeled objects, treat the remaining members as outliers.

The procedure uses cluster structure to propagate scarce labels. Its reliability depends on the assumption that label composition is homogeneous within the relevant clusters.

Contextual and Collective Outliers

Exam: ★★★★☆

Global point detectors are insufficient when abnormality depends on context or on interactions among several objects. These cases require additional structure in the problem definition.

Contextual outliers: conditioning before detection

One direct strategy is to form explicit context groups and then apply an ordinary detector within each group. In the customer example, age group and postal code are contextual attributes, whereas number of transactions per year and annual total transaction amount are behavioral attributes. A customer is compared with others in the same context rather than with the entire population.

The slide also describes probabilistic context and behavior mixtures. Let denote contextual mixture components and behavioral components. Its score is written

This combines uncertainty about the object’s context with how compatible its behavior is with behavior expected in that context. If an explicitly defined context group is too small, nearby or similar contexts may be generalized, such as merging customers of similar ages in nearby areas.

Sometimes discrete contexts cannot be defined cleanly. Then one can learn expected behavior as a function of contextual attributes. Given context , predict behavioral attributes and examine the residual between observed and predicted . A sufficiently large deviation indicates a contextual outlier. The slides cite Markov models and finite-state automata as example models when the context has sequential structure.

Collective outliers: discovering anomalous structures

Collective detection evaluates a group as a unit. For example, one network packet or one stock transaction can be perfectly ordinary, while coordinated denial-of-service traffic among several machines or a large burst of repeated trades of the same stock among a few parties can be collectively suspicious. The structure depends on the data domain: contiguous segments or subsequences in temporal data, local regions in spatial data, and subgraphs in graph/network data. A critical difference from ordinary point detection is that these structures may not be given beforehand; discovering candidate groups is itself part of the anomaly-detection problem.

For an unlabeled graph, the lecture treats a subgraph as a structural unit and characterizes it by

• , its number of vertices;
• , the number of network subgraphs isomorphic to .

Two unusual regimes are highlighted: a small subgraph with very low frequency can represent a rare local structure, while a large subgraph that occurs surprisingly often can also be anomalous relative to the expected size-frequency relationship.

Outlier Detection in High-Dimensional Data

Exam: ★★★★☆

High dimensionality breaks many intuitions used by earlier methods. Data become sparse, pairwise distances are increasingly influenced by irrelevant/noisy dimensions, interpretable anomaly explanations become difficult, relevant structure may exist only in particular subspaces, and exhaustive exploration of all feature subsets is not scalable. The lecture develops four responses: adapt conventional proximity scores, search lower-dimensional subspaces, ensemble many low-dimensional detectors, and learn task-relevant embeddings.

Extending proximity methods: HilOut

HilOut scores each object by its nearest-neighbor distances. If is the th nearest neighbor,

Objects are ranked by decreasing , and the top are returned as outliers. In the four-point example , , , and with ,

so is the clear top-1 outlier.

Finding sparse subspaces

An object may be ordinary in the full space yet extreme in a meaningful subset of features. Detecting it in a low-dimensional subspace both improves sensitivity and explains why it is anomalous. The lecture’s customer example describes Alice as anomalous in the two-dimensional subspace of average transaction amount and purchase frequency: her transaction amount is unusually high while her purchase frequency is unusually low.

A grid-based method projects data onto candidate subspaces and discretizes every selected dimension into equal-depth ranges, each containing fraction

of the objects. Equal-depth binning is preferred to equal-width binning because different dimensions may have very different local scales or concentrations.

Consider a -dimensional grid cell . Under the simplifying assumption that the selected dimensions are independently distributed, the probability of landing in a particular cell is . With objects, the expected count and standard deviation are

The sparsity coefficient is the standardized count

If , the cell contains fewer objects than expected. More negative values indicate greater sparsity and stronger evidence that objects in the cell are subspace outliers. The slide proposes using a normal approximation for to assign a significance level.

Outlier-detection ensembles

Instead of choosing one subspace, an ensemble creates low-dimensional base detectors. For data matrix with rows and features, base detector works on a representation of dimension and produces an outlier-score vector of length . The vectors are normalized and aggregated into a final score vector , after which the highest-scoring tuples are flagged.

Two subspace constructions are distinguished:

• Feature bagging: randomly select actual input features.
• Rotated bagging: generate a -dimensional random subspace, typically represented by mutually orthonormal directions, and project the data onto it.

Two basic aggregation rules are

for mean aggregation, and elementwise

for max aggregation. Base scores must be placed on comparable scales first, for example by min-max or z-score normalization; otherwise one detector’s numerical range can dominate the ensemble independently of its quality.

Deep representations

Deep models such as autoencoders, feed-forward networks, CNNs, RNNs, and GNNs can map high-dimensional input tuples to lower-dimensional embeddings. Compared with linear factorization, learned nonlinear representations can capture more complicated feature interactions and may expose anomalies that are not separable in the raw space.

The simplest pipeline uses deep learning only as preprocessing: train an encoder, extract embeddings, and run a conventional detector such as LOF or a reconstruction-based method in the embedding space. This is flexible, but embedding learning and anomaly detection optimize separate objectives, so the learned representation may discard exactly the distinctions needed for anomaly detection.

A tighter approach learns the representation and detector jointly. The slide gives two examples.

• One-Class Neural Network (OC-NN) replaces a fixed hyperplane score such as with a feed-forward neural network. Its final hidden layer supplies the embedding and its output produces an anomaly-related score, allowing the representation to be tailored to the one-class objective.
• Deviation Networks (DevNet) learn an outlierness score directly from the raw feature vector . The score is standardized relative to the scores of normal tuples, replacing raw-feature z-normalization by z-normalization in score space using the normal-score sample mean and standard deviation.

The conceptual progression is therefore from representation first, detector second to jointly learning a representation whose geometry is explicitly optimized for anomaly detection. The latter can improve accuracy when sufficient training signal and an appropriate objective are available.