Anomaly detection methods

2.5.13 · AI-ML › Unsupervised Learning

Ek Point Anomalous Kyu Hota Hai?

YEH KYUN MATTER KARTA HAI: Real systems mein, anomalies rare hoti hain (<1% data) lekin high-impact hoti hain. Ek fraudulent transaction paise barbad karta hai; ek network breach security compromise karta hai. Humein automated methods chahiye kyunki human inspection scale nahi hoti.

Method 1: Statistical (Gaussian) Anomaly Detection

First Principles Se Derivation

KYA: Normal data ko multivariate Gaussian distribution follow karta hua model karo. Jo points bahut low probability density par hain, woh anomalies hain.

KYUN: Agar normal behavior ek mean ke around kuch spread ke saath cluster karta hai, toh is cluster se door ke points suspicious hain. Gaussian "typical" ko mean aur variance ke terms mein capture karta hai.

KAISE:

Step 1 - Distribution Fit Karo: Training data $\{x^{(1)},..,x^{(m)}\}$ diya hua hai jahan $x^{(i)}\in {\mathbb{R}}^n$:

$\mu =\frac{1}{m}{\sum }_{i=1}^m{x}^{(i)}$

Yeh step kyun? Mean $\mu$ squared loss ke under "normal behavior ke center" ka hamara best estimate hai.

$\Sigma =\frac{1}{m}{\sum }_{i=1}^m(x^{(i)}-\mu )(x^{(i)}-\mu {)}^T$

Yeh step kyun? Covariance $\Sigma$ capture karta hai ki features ek saath kaise vary karte hain. Yeh hume normal data ki "shape" batata hai — kaunsi directions mein high/low variance hai.

Step 2 - Probability Density Compute Karo: Ek naye point $x$ ke liye, compute karo:

$p(x)=\frac{1}{(2\pi {)}^{n/2}|\Sigma {|}^{1/2}}\exp \left(-\frac{1}{2}(x-\mu {)}^T{\Sigma }^{-1}(x-\mu )\right)$

Yeh formula kyun?

• Term $(x-\mu {)}^T{\Sigma }^{-1}(x-\mu )$ Mahalanobis distance hai: $x$ kitna door hai $\mu$ se, $\Sigma$ ke units mein measure kiya hua.
• Exponential distance badhne ke saath decay karta hai: door wale points → low probability.
• Normalization constant ensure karta hai ki $\int p(x)dx=1$.

Step 3 - Anomalies Flag Karo: Agar $p(x)<ϵ$, toh $x$ ko anomaly flag karo.

Yeh step kyun? Hum threshold $ϵ$ set karte hain desired false-positive rate ke basis par. Lower $ϵ$ = stricter detection = kam false alarms lekin kuch anomalies miss ho sakti hain.

Equivalently, flag karo agar Mahalanobis distance $>k$ jahan $k=\sqrt{-2\ln (ϵ\cdot (2\pi {)}^{n/2}|\Sigma {|}^{1/2})}$.

Naya observation: $x=[80,90{]}^T$

Step 1: Mahalanobis distance compute karo: $x-\mu =[50,40{]}^T$ ${\Sigma }^{-1}=\frac{1}{25\cdot 36-100}\left[\begin{array}{cc}36& -10\\ -10& 25\end{array}\right]=\frac{1}{800}\left[\begin{array}{cc}36& -10\\ -10& 25\end{array}\right]$

Yeh step kyun? Hum covariance ko invert karte hain taaki distance ko data ke natural coordinate system mein measure kar sakein.

$(x-\mu {)}^T{\Sigma }^{-1}(x-\mu )=[50,40]\cdot \frac{1}{800}\left[\begin{array}{cc}36& -10\\ -10& 25\end{array}\right]\left[\begin{array}{c}50\\ 40\end{array}\right]$ $=\frac{1}{800}[50,40]\cdot [1400,-500+1000]=\frac{1}{800}[1400\cdot 50+500\cdot 40]=\frac{9000}{800}=112.5$

Step 2: $p(x)$ compute karo: $|\Sigma |=900-100=800$ $p(x)=\frac{1}{2\pi \sqrt{800}}\exp (-112.5/2)\approx \frac{1}{177.6}\exp (-56.25)\approx 10^{-26}$

Yeh step kyun? Probability astronomically small hai — yeh server bilkul normal jaisa behave nahi kar raha.

Step 3: Agar $ϵ=10^{-5}$, toh yeh anomaly hai (possible CPU/memory leak).

Method 2: Isolation Forest

First Principles Se Derivation

KYA: Random decision trees banao jo points ko isolate karein. Anomalies ko isolate karna normal points se aasaan hota hai (kam splits chahiye).

KYUN: Normal points "crowd ke andar gehre" hote hain — unhe separate karne ke liye bahut saare questions chahiye. Anomalies "akele bahar" hote hain — ek ya do questions unhe isolate kar dete hain.

KAISE:

Step 1 - Isolation Trees Banao: Har tree ke liye:

1. Randomly feature $q$ aur split value $p$ select karo, $q$ ke min/max ke beech mein
2. Data partition karo: $\{x:x_q<p\}$ vs $\{x:x_q\ge p\}$
3. Recurse karo jab tak points isolated na ho jayein ya max depth na aa jaye

Random splits kyun? Hum classify nahi kar rahe — bas space partition kar rahe hain. Random splits "normal" structure mein overfitting se bachate hain aur naturally outliers ko jaldi isolate karte hain.

Step 2 - Path Length Compute Karo: Ek point $x$ ke liye, uska path length $h(x)$ ek tree mein leaf tak pahunchne ke liye splits ki sankhya hai.

Yeh step kyun? Short path = isolate karna aasaan = likely anomaly. Normal points ko neighbors se separate karne ke liye zyada splits chahiye.

Step 3 - Trees Par Aggregate Karo: $t$ trees par average path length: $\bar{h}(x)$

Anomaly score: $s(x)=2^{-\bar{h}(x)/c(n)}$

jahan $c(n)=2H(n-1)-2(n-1)/n$ $n$ points ke liye average path length hai (normalization ke liye).

Yeh formula kyun?

• $c(n)$ ek Binary Search Tree mein unsuccessful search ki expected depth hai — yeh "normal" ke liye hamara baseline hai
• Hum $c(n)$ se normalize karte hain taaki scores alag dataset sizes mein comparable hon
• Exponential $2^{-\cdot }$ [0,1] par map karta hai: 1 ke near scores = anomaly, 0 ke near = normal

Agar $s(x)>0.6$, typically anomaly flag karo.

Normal transaction: $45 dopahar 2 baje user ke sheher mein → average path length $\bar{h}=7.2$ Kyun? Bahut saari similar transactions exist karti hain; neighbors se isolate karne ke liye ~7 splits lagte hain.

Anomalous transaction: $9,999 raat 3 baje foreign country mein → $\bar{h}=2.1$ Kyun? Aise bahut kam transactions hain; ~2 splits mein isolate ho jata hai (shayad ek amount par, ek location par).

Scoring: $c(1000)\approx 2\ln (1000)=18.4$ $s(\text{normal})=2^{-7.2/18.4}\approx 0.77$ $s(\text{anomaly})=2^{-2.1/18.4}\approx 0.92$

Decision: 0.92 > 0.6 threshold → fraud review ke liye flag karo.

Method 3: One-Class SVM

First Principles Se Derivation

KYA: Feature space mein ek hypersphere (ya hyperplane) dhundho jo normal data ko tightly enclose kare. Bahar ke points anomalies hain.

KYUN: Hum ek aisi decision boundary chahte hain jo normal data ko baki space se separate kare, margin maximize karke "normal" ko compactly capture kare.

KAISE:

Step 1 - Kernel Mapping: Data ko high-dimensional space mein map karo kernel $K(x,x^{\prime })=\varphi (x{)}^T\varphi (x^{\prime })$ ke zariye. Common choice: RBF kernel $K(x,x^{\prime })=\exp (-\gamma \Vert x-x^{\prime }{\Vert }^2)$.

Yeh step kyun? High dimensions mein, woh data jo input space mein linearly separable nahi hai, woh aksar separable ho jaata hai. Kernel trick explicit computation se bachata hai.

Step 2 - Optimization Problem: Hyperplane $w^T\varphi (x)=\rho$ dhundho jo data ko origin se maximum margin ke saath separate kare:

${\min }_{w,\rho ,\xi }\frac{1}{2}\Vert w{\Vert }^2-\rho +\frac{1}{\nu m}{\sum }_{i=1}^m{\xi }_i$ subject to: $w^T\varphi (x^{(i)})\ge \rho -{\xi }_i,{\xi }_i\ge 0$

Yeh objective kyun?

• $\frac{1}{2}\Vert w{\Vert }^2$: minimize karo (margin $1/\Vert w\Vert$ maximize karo)
• $-\rho$: hyperplane ko origin se door push karo (bada normal region)
• $\frac{1}{\nu m}\sum {\xi }_i$: training data mein kuch outliers ke liye slack allow karo
• $\nu \in (0,1]$: trade-off control karta hai (outliers ke fraction ka upper bound)

Step 3 - Decision Function: Naye point $x$ ke liye: $f(x)=\text{sign}\left({\sum }_{i=1}^m{\alpha }_{i}K(x,x^{(i)})-\rho \right)$

jahan ${\alpha }_i$ dual problem solve karne se aaye Lagrange multipliers hain.

Yeh step kyun? $f(x)<0$ matlab $x$ "origin side" par hai — normal region ke bahar, isliye anomaly.

jahan support vectors (${\alpha }_i>0$) boundary define karte hain.

Normal packet: size=512, duration=0.5s, protocol=HTTP → $f(x)=+0.23>0$ ✓ Kyun? Typical HTTP traffic ki seekhi hui boundary ke andar hai.

Suspicious packet: size=6535, duration=0.01s, protocol=ICMP → $f(x)=-0.87<0$ ✗ Kyun? Tiny duration ke saath max-size ICMP normal se bilkul alag hai; sabhi support vectors se kernel distance bada hai, $f(x)$ ko negative push karta hai.

Method 4: Autoencoder-Based Detection

First Principles Se Derivation

KYA: Ek neural network train karo jo normal data ko compress karke phir reconstruct kare. Anomalies mein high reconstruction error hoti hai kyunki network ne unhe kabhi encode karna seekha hi nahi.

KYUN: Agar ek network normal data ka manifold seekh le, toh woh normal points ko faithfully reproduce kar sakta hai lekin anomalies ke saath struggle karta hai (woh off-manifold hote hain).

KAISE:

Step 1 - Architecture: Encoder: $h=f_e(x)$ $x\in {\mathbb{R}}^n$ ko code $h\in {\mathbb{R}}^k$ mein map karta hai jahan $k\ll n$ Decoder: $\hat{x}=f_d(h)$ code se reconstruct karta hai

Bottleneck kyun? Low $k$ tak compression force karna ensure karta hai ki network essential structure seekhe, har point memorize na kare.

Step 2 - Training Objective: Normal data par reconstruction loss minimize karo: $L=\frac{1}{m}{\sum }_{i=1}^m\Vert x^{(i)}-f_d(f_e(x^{(i)})){\Vert }^2$

Squared error kyun? Yeh Gaussian noise assumption ke under maximum likelihood estimate hai. Dusre losses (absolute, perceptual) bhi kaam karte hain.

Step 3 - Anomaly Detection: Test point $x$ ke liye, compute karo: $\text{Reconstruction Error: }E(x)=\Vert x-\hat{x}{\Vert }^2$

Agar $E(x)>\tau$ (threshold jo validation set par set ki gayi ho), toh anomaly flag karo.

Yeh kyun kaam karta hai? Autoencoder ke weights $p(\text{normal})$ encode karte hain. Jab anomaly dikhaya jata hai, decoder "nearest normal point hallucinate" karne ki koshish karta hai, jo large error deta hai.

Normal board: Input pixel patterns training se match karte hain → $E(x)=120$ (low error, faithfully reconstruct hota hai) Kyun? Network ne solder joints, traces, components ke features seekhe. Woh unhe accurately regenerate kar sakta hai.

Defective board: Missing component, short circuit → $E(x)=3400$ (high error) Kyun? Defect out-of-distribution hai. Decoder wahan component "imagine" karne ki koshish karta hai (seekhe hue prior se), lekin actual pixels drastically different hain.

Decision: Agar $\tau =500$, defect flag hoga (3400 > 500).

Methods Ki Comparison

Method	Strengths	Weaknesses	Best For
Gaussian	Fast, interpretable, acha kaam karta hai agar data ~Gaussian ho	Gaussian assume karta hai, multi-modal ya skewed data ke saath break hota hai	Low-dimensional numerical data, jab explain-ability chahiye
Isolation Forest	Distribution assumption nahi, high-dim handle karta hai, fast	Interpret karna mushkil, tree count tuning chahiye	High-dimensional data, mixed feature types

Concept Map