Outlier Analysis

1. What is an Outlier?

An outlier is a data object that deviates significantly from the rest of the data, as if generated by a different mechanism. Alternative names: anomaly, aberration, surprise, discordant, exception.

Hawkins' definition: "an observation which deviates so much from other observations as to arouse suspicions that it was generated by a different mechanism."

Examples: a credit-card transaction of ₹5,00,000 when the customer's usual spend is ₹2,000; a sensor reading of 300°C in a room; a network packet burst (intrusion); a mis-typed age of 250.

2. Outliers vs Noise

Aspect	Noise	Outlier
Definition	Random error/variance in a measured variable	Genuine but unusual data object
Interest	Always unwanted	Often the most interesting object (fraud, fault)
Treatment	Remove / smooth	Remove or analyse as a class
Detection	Binning, regression, clustering	Statistical, distance, density, deviation methods

Categories of outliers: global (deviates w.r.t. the whole dataset), contextual / conditional (deviates only in a given context — 30°C in December vs June), collective (a group of objects deviates together — a sequence of wrong entries).

3. Applications

Fraud detection (cards, insurance, telecom), intrusion detection, medical/healthcare anomaly detection, industrial fault & defect detection, news/novelty detection, sports statistics, environment monitoring (climate, pollution).

4. General Approach — Three Steps

 (1) Build a PROFILE of "normal" behaviour  -->  (2) Detect objects that do NOT fit
        (statistical / distance / density model)          |
                                                          v
                              (3) Verify & use:  remove  |  investigate as a class  |  report/alert

5. Method 1 — Statistical (Distribution-Based) Approaches

Assume the data follows a model (e.g. normal distribution) and apply a discordancy test; an object is an outlier if the model does not fit it.

Univariate, normal distribution — detect with the z-score:

z = \frac{x-\bar{x}}{\sigma},\qquad |z| \ge 3 \Rightarrow \text{outlier}\ (0.13\%\ \text{expected under } N(\mu,\sigma^{2}))

IQR / boxplot rule (robust, no normality assumption):

IQR = Q_3 - Q_1,\qquad \text{outlier if } x < Q_1 - 1.5\,IQR \ \text{ or }\ x > Q_3 + 1.5\,IQR

Grubbs' test for the most extreme value:

G = \frac{\max_i |x_i - \bar{x}|}{s},\qquad \text{compare with } G_{crit}=\frac{N-1}{\sqrt{N}}\sqrt{\frac{t_{\alpha/2N,\,N-2}^{2}}{N-2+t^{2}_{\alpha/2N,\,N-2}}}

Multivariate — use the Mahalanobis distance (accounts for correlation between attributes):

D^{2}(x)= (x-\bar{x})^{T}\,S^{-1}\,(x-\bar{x}),\qquad \text{outlier if } D^{2} > \chi^{2}_{\alpha,\,p}

Numerical example — marks 45, 48, 50, 52, 51, 250; $\bar{x}=82.67$ , $s \approx 81.6$ → $z_{250}=2.05$ (borderline with $n=6$ ); with the IQR rule $Q_1=49.5$ , $Q_3=52.5$ , $IQR=3$ , fence $=52.5+4.5=57$ → 250 is a clear outlier.

Limitations: needs the correct distribution (many outliers may themselves distort $\bar{x}$ and $s$ ), hard for high-dimensional data (curse of dimensionality), and the test must know the number of outliers $k$ in advance. Mixture models (EM) and robust statistics (median, MAD, trimmed mean) partially fix this.

6. Method 2 — Distance-Based Approaches

An object is an outlier if at least $p$ fraction of the objects in the dataset lie further than $d$ away from it (Knorr & Ng). Parameters: distance threshold $d$ , fraction $p$ .

 Outlier: few neighbours within radius d.       Normal point: many neighbours inside d.
        o                                        (  (o) o ( (o
   o                 o                            ( o  (  o )  (
            X  (isolated)  o   o                  ( ( o ) o (  (

Index-based algorithm: use a k-d tree / R-tree / ball tree to count neighbours within $d$ ; if fewer than $p|D|$ → outlier. $O(n\log n)$ with an index.
Nested-loop algorithm: for each object, compare with others until $p|D|$ neighbours are found.

O(n^{2}) \text{ (naive)} \quad \longrightarrow \quad O(n\log n)\ \text{with spatial index}

Cell-based algorithm (with $d$ and $p$ ): partition space into cells of side $d/(2\sqrt{p})$ (only level-1 and level-2 neighbour cells must be examined). Efficient, but sensitive to the cell origin.

Advantages: no distribution assumption, works for any data type with a distance measure.
Disadvantages: parameter choice ( $d$ , $p$ ) is difficult; performance degrades to $O(n^2)$ in high dimensions; cannot find local outliers (a point may be an outlier w.r.t. its own cluster but not globally).

7. Method 3 — Density-Based Approaches (Local Outlier Factor)

Idea: compare the density around an object with the densities around its neighbours → finds local outliers even with clusters of different densities.

Definitions (for object $o$ , $k$ -distance = distance to its $k$ -th nearest neighbour $N_k(o)$ ):

$k$ -distance neighbourhood: $N_{k\text{-dist}}(o) = \{\,o' \mid d(o,o') \le k\text{-distance}(o)\,\}$
Reachability distance: $\text{reach-dist}_k(o,o')=\max\{\,k\text{-distance}(o'),\, d(o,o')\,\}$ (smooths statistical fluctuation)
Local reachability density:

\text{lrd}_k(o)=1\Big/\left(\frac{\sum_{o'\in N_k(o)}\text{reach-dist}_k(o,o')}{|N_k(o)|}\right)

Local outlier factor:

\text{LOF}_k(o)=\frac{\sum_{o'\in N_k(o)}\dfrac{\text{lrd}_k(o')}{\text{lrd}_k(o)}}{|N_k(o)|}

LOF value	Meaning
$\approx 1$	Similar density to neighbours → normal
$> 1$ (e.g. > 2)	Lower density than neighbours → outlier
$< 1$	Denser than neighbours → core of a cluster

Example — cluster of 20 points plus an isolated point: the dense cluster's points have LOF ≈ 1; the isolated point's LOF ≈ 5 → flagged. Its neighbours (also isolated, slightly less so) get LOF ≈ 1.5.

Numerical anchor: if $k$ -distance( $o$ ) = 2, $k$ -distance( $o'$ ) = 3, $d(o,o')=2.5$ , then reach-dist = max(3, 2.5) = 3.

Other density methods: OPTICS (ordering + reachability plot), DBSCAN noise points, DENCLUE (density function with influence), Isolation Forest (isolate points with random splits), One-Class SVM (learns a boundary around normal data).

8. Method 4 — Deviation-Based (Sequential-Exception) Approaches

Identify outliers by examining the differences in the main characteristics of objects in a group; an outlier is one whose removal improves the group's "smoothness" (compression).

\text{Removal of } o \text{ is good if } \text{Impact}(o) = SM\!E(R, D) - SM\!E(R, D\setminus\{o\}) \text{ is high}

where $SME$ = sequential exception smoothness measure of a group $R$ , e.g.

SME(R)=|R|\cdot\sum_{A \in \text{att}}\left(\frac{\text{variance of } R \text{ on } A}{\text{variance of } D \text{ on } A}\right)

Greedy search: at each step remove the object with the largest impact; stop when the impact becomes insignificant ( $< t$ , a user threshold). Advantages: finds outliers even if they are in low-density regions; no distribution assumption; disadvantage: needs a good smoothness function, and the brute-force search is exponential ( $\binom{n}{k}$ ).

9. Method Summary

Approach	Assumes	Finds local outliers?	Key parameters	Example methods
Statistical	A data distribution	No (usually global)	significance level $\alpha$ , $k$	Grubbs, $z$ -score, IQR, $\chi^2$
Distance-based	A distance metric	No	$d$ (radius), $p$ (fraction)	Knorr & Ng nested-loop, index-based, cell-based
Density-based	Density variation	Yes	$k$ (neighbours), threshold	LOF, OPTICS, DENCLUE, isolation forest
Deviation-based	A smoothness measure	Partly	$k$ (exceptions), threshold $t$	Sequence exception, OLAP data-cube deviation

10. Outlier Detection in High-Dimensional Data

Distance concentration makes all distances similar → unsupervised methods degrade; remedies: subspaces / projected clustering (find outliers in specific subspaces — e.g. the SPOT / angle-based approaches), feature selection, using angular/rank-based measures, sparse and one-class models.

11. Exam Points

Define outliers; explain types (global, contextual, collective) and applications — 5 marks.
Explain statistical, distance-based, density-based and deviation-based methods with formulas — 10 marks (very frequent).
Explain LOF with the lrd and reachability-distance formulas — 5-7 marks.
Numerical: detect outliers with z-score / IQR / Mahalanobis distance — 5 marks.
Why is outlier analysis useful in fraud and intrusion detection? — 3-5 marks.

Outlier Analysis