Outlier Analysis

What Is an Outlier?

• An outlier (anomaly) is a data object that deviates so much from other objects that it raises suspicion it was generated by a different mechanism.
• "One person's noise is another's treasure": outliers can be errors to discard or the most valuable signal (fraud, intrusion, fault, rare disease).
• Outlier analysis = finding objects that are markedly dissimilar from the majority.

Categories of Outliers

1. Point outliers: a single object anomalous (most common).
2. Contextual (conditional) outliers: anomalous only in a specific context (e.g., temperature 35°C is normal in summer but anomalous in winter). Need context attributes + behavioral attributes.
3. Collective outliers: a collection of related objects anomalous as a group (e.g., a subsequence of a signal), even if each point alone is normal.

Challenges

• What is "normal" depends on application; outliers are rare ⇒ imbalanced classes.
• High dimensionality makes distance unreliable (concentration of distance).
• Outliers may be the target (fraud) rather than noise to remove.

Approaches Overview

Approach	Basis	Needs labels?	Strength
Statistical / model-based	parametric/non-parametric distribution	no	principled, interpretable
Distance-based	distance to neighbors	no	simple, general
Density-based	local density vs neighbors	no	finds local outliers (LOF)
Angle-based (ABOD)	variance of angles	no	good in high-D
Deviation-based (subspace, HiCS)	high-contrast subspaces	no	high-dim outliers
Proximity / clustering by-product	distance to cluster	no	reuses clustering

1. Statistical (Model-Based) Methods

• Assume data follows a distribution $f(x;\theta )$; flag points with very low probability.
• Parametric: e.g., Gaussian — point is outlier if it lies beyond $z$ standard deviations:$$z=\frac{|x-\mu |}{\sigma }>\tau (\text{e.g., }\tau =3\Rightarrow 99.7\mathrm{\%}\text{ rule})$$
• Grubbs' test: detects a single outlier maximizing the standardized deviation.
• Non-parametric: use boxplot / IQR rule: outlier if $x<Q_1-1.5IQR$ or $x>Q_3+1.5IQR$.
• Histogram / mixture models: fit mixture, low-likelihood points = outliers.
• Limitations: assumes a (often unimodal) distribution; masking (multiple outliers hide each other); struggles in high-D and with multimodal/complex data.

2. Distance-Based Methods (Knorr & Ng)

• An object is an outlier if few points are within distance $D$ (i.e., it is far from most others).
• DB(pct, D) outlier: a point $p$ is an outlier if at most pct% of points lie within distance $D$ of $p$:$$|\{q\mid dist(p,q)\le D\}|\le \frac{pct}{100}\cdot n$$
• k-NN distance / k-distance: distance to the $k$-th nearest neighbor; large k-distance ⇒ outlier. A simple, model-free detector.
• Nested-loop / cell-based algorithms speed up distance outlier detection.
• Limitations: fails when normal regions have varying density (a sparse-but-normal region looks outlier-ish); distance degrades in high-D (curse of dimensionality).

3. Density-Based: LOF (Local Outlier Factor)

LOF (Breunig et al.) measures outlier-ness by comparing an object's local density to that of its neighbors — detects local outliers that global density/distance miss.

Definitions

• k-distance(p) = distance to the $k$-th nearest neighbor.
• k-distance neighborhood $N_k(p)$ = points within k-distance of $p$ (includes ties).
• Reachability distance:$$reach\text{-}dis{t}_k(p,q)=max(k\text{-}dist(q),dist(p,q))$$(smooths small fluctuations; never below $q$'s k-distance).
• Local reachability density (LRD) of $p$:$$lr{d}_k(p)=\frac{1}{\frac{1}{|N_k(p)|}\sum _{q\in N_k(p)}reach\text{-}dis{t}_k(p,q)}$$Higher LRD ⇒ denser neighborhood.
• Local Outlier Factor:$$LO{F}_k(p)=\frac{1}{|N_k(p)|}\sum _{q\in N_k(p)}\frac{lr{d}_k(q)}{lr{d}_k(p)}$$
  • $LOF\approx 1$: similar density to neighbors ⇒ normal.
  • $LOF\gg 1$: sparser than neighbors ⇒ local outlier.
  • $LOF<1$: denser than neighbors (insider).

Properties

• Detects local outliers (a point can be an outlier even inside a globally dense region if it is sparser than its local surroundings).
• Choice of $k$ matters (too small → unstable, too large → global measure).
• Variants: LOCI, COF (connectivity-based), INFLO (using reverse k-NN), LoOP (local probability).

Method	Detects	Weakness
Statistical	global, distributional	assumes distribution
Distance (k-dist)	far-from-all	uniform-density assumption
LOF	local density	needs $k$, distance-based

4. Angle-Based: ABOD (Angle-Based Outlier Degree)

• In high-D, distance concentrates, so use angles instead. An outlier has high variance of angles to other points (its neighbors lie in a narrow cone vs. spread out for normal points).
• ABOD: variance of $\cos$-angle between vectors to pairs of other points; high variance ⇒ outlier.
• More robust in high dimensions than distance/LOF; variants FastABOD sample points for efficiency.

5. High-Dimensional: Subspace / Deviation (HiCS)

• Global distance fails in high-D because all pairwise distances become similar (concentration of distance).
• Outliers often appear only in a subset of dimensions (subspace).
• Subspace outlier detection: search subspaces where a point is anomalous.
  • Feature bagging / outlier ensembles: run a detector on many random subspaces and aggregate scores.
  • HiCS (Highest Contrast Subspaces): identifies subspaces with high contrast (where the point's local density is much lower than expected from marginal distributions). Uses the contrast $c=\frac{P_{subspace}(p)}{P_{marginals}(p)}$; low $c$ ⇒ outlier in that subspace.
• Grid-based / projected outlier methods (e.g., on CLIQUE dense cells) find deviations in subspaces.

6. Clustering-Based (By-Product) Outliers

• Run a clustering algorithm (k-means, DBSCAN); objects far from any centroid / labeled NOISE are outliers.
• Simple, reuses existing pipeline, but depends on clustering quality.

7. Deviation-Based & Time-Series Outliers

• Sequential / transform: Fourier, wavelets to find anomalies in signals.
• Markov / HMM models for sequence anomalies; distance to nearest neighbor in time series.

Statistical Method — Worked Example

Heights (cm) of 10 people: $\{160,162,165,166,168,170,171,172,174,200\}$. Mean $\mu =172.8$, std $\sigma \approx 10.9$.

• For 200: $z=(200-172.8)/10.9\approx 2.49$ — above a typical $3\sigma$ or even $2.5\sigma$ threshold ⇒ candidate outlier, but note itself inflates $\sigma$ (masking). A robust approach (median=169.5, MAD≈5.2) gives modified $z=(200-169.5)/(1.4826\times 5.2)\approx 3.96$ ⇒ clearly an outlier.
• Boxplot rule: Q1=165, Q3=172, IQR=7 ⇒ upper fence $=172+1.5\times 7=182.5$; 200 > 182.5 ⇒ outlier. Lower fence $=165-10.5=154.5$ (none below).

Distance-Based — Worked Example

Points in 2-D: $A(0,0),B(0.1,0),C(0,0.1),D(10,10)$. With $D=2$, $pct=10\mathrm{\%}$ (n=4 ⇒ at most 0.4 points nearby, i.e., ≤0 neighbors within 2):

• A,B,C each have 2 neighbors within 2 ⇒ normal.
• D has 0 neighbors within 2 ⇒ outlier by DB(10%, 2). This matches intuition; but if the normal cluster were itself sparse (points 5 apart), distance alone would falsely flag them.

LOF — Worked Example

Consider $p$ inside a dense cluster: its $k$-neighbors are ~1 unit away ⇒ $lrd(p)$ high; neighbors have similar $lrd$ ⇒ $LOF(p)\approx 1$ (normal). Now $q$ sitting alone between two clusters, $k$-neighbors 5 units away ⇒ $lrd(q)$ low; but those neighbors are in dense regions with high $lrd$ ⇒ $LOF(q)=avg(lrd(neighbors)/lrd(q))\gg 1$ ⇒ local outlier. A global density method would miss $q$ if the surrounding average density is moderate; LOF catches it because it compares locally.

Choosing k for LOF

• Small $k$ (e.g., 5–10): captures fine local structure but noisy.
• Large $k$: LOF approaches a global measure (loses locality).
• Practical: try several $k$, look for points consistently with high LOF.

HiCS / Subspace Outliers (Detail)

• In $d$ dimensions, the expected distance to the $k$-th neighbor concentrates around a constant for all points ⇒ distance/LOF lose power.
• HiCS searches subspaces where a point's contrast $c(S)=P_S(x)/P_{marginals}(x)$ is very small (its local density in that subspace is far below what marginals predict) — i.e., it is anomalous only along those dimensions.
• Outlier ensembles (e.g., feature-bagging): run a base detector on many random subspaces, average scores ⇒ robust to irrelevant dimensions and the curse of dimensionality.

Model-Based & Time-Series Outliers (More)

• Autoencoder / reconstruction error: train a neural net to reconstruct normal data; high reconstruction error ⇒ outlier (great for high-D/images).
• One-Class SVM: learns a boundary around normal data in feature space; points outside ⇒ outliers.
• Time series: window + z-score, Seasonal-Hybrid ESD, or compare to forecast (ARIMA) residuals.

Method Selection Guide

Data characteristic	Recommended
clean parametric, low-D	statistical (z / boxplot)
general, uniform density	distance (k-dist)
varying density, local	LOF / LoOP
high-dimensional	ABOD / subspace (HiCS) / ensemble
streaming	incremental / windowed
need probability	One-Class SVM / GMM

Evaluating Outlier Detectors

• Unsupervised detectors have no ground truth; rank outputs and inspect top scores (human-in-the-loop).
• With labels, use Precision@k (fraction of true outliers among top-$k$ flagged), ROC-AUC on the outlier-score ranking, or Recall at a fixed alert budget.
• Compare methods by AUC; beware that a method tuned to one data type may fail on another (use the selection guide below).

Real-World Applications

• Fraud detection: credit-card transactions, insurance claims, click fraud.
• Intrusion / anomaly detection: network traffic, system logs, IoT sensors.
• Fault / predictive maintenance: vibration, temperature deviations.
• Medical: rare diseases, adverse drug reactions.
• Data cleaning: duplicate / entry-error detection as a by-product.

Method Selection (Recap)

• clean parametric, low-D → statistical.
• general, uniform density → distance (k-dist).
• varying density / local → LOF, LoOP.
• high-dimensional → ABOD, subspace (HiCS), ensembles, autoencoders.
• need probability bound → One-Class SVM, GMM.

Contextual (Conditional) Outliers — Worked

Temperature 35°C is normal in summer but anomalous in winter. Model the context (season) separately, then detect deviation within that context: $z_{summer}(35)$ small ⇒ normal in summer; $z_{winter}(35)$ large ⇒ outlier in winter. Requires the context attributes to be known and used.

Collective Outliers

A set of points each "normal" alone but anomalous together — e.g., a sustained low-amplitude oscillation in a sensor, or a burst of otherwise-normal transactions forming a fraud pattern. Detect via sequence models (HMM, Markov), window statistics, or collective/subspace deviation methods.

Outlier Detection Pipeline

1. Profile "normal" (distribution, density, or model).
2. Score every object by deviation from normal.
3. Rank; alert top-$k$ or those above threshold.
4. Validate (human / labels) and tune parameters ($ϵ,k,\tau$).

Summary

Outliers are objects generated by a different mechanism; they may be noise or the key finding (fraud, faults). Point / contextual / collective are the three kinds. Statistical methods flag low-probability points under an assumed distribution (masking & high-D are weaknesses). Distance-based (DB(pct,D), k-distance) flag far-from-most points but assume uniform density. Density-based LOF compares local reachability density to neighbors, catching local outliers via $LOF\gg 1$. In high dimensions, prefer angle-based (ABOD) or subspace methods (HiCS, ensembles) that exploit contrast in relevant subspaces. Clustering by-products (DBSCAN noise) give a quick outlier flag as a side effect.