Skip to content
Tutorials Center
My learning

Topics

Lesson 32 of 39 ยท Anomaly Detection

Distance and Density Anomaly Detection

Detect anomalies with distance (k-NN), density (Local Outlier Factor), isolation (Isolation Forest), clustering and One-Class SVM; learn contamination, scoring and how to evaluate rare-event detectors.

Statistical tests assume a distribution. When the data has no clean distribution, you can use geometry instead. An anomaly is a record that is far from its neighbors, sits in an unusually sparse region, or is easy to isolate. Each idea gives a family of algorithms.

Distance-based: k-nearest-neighbor score

Score every record by the distance to its k-th nearest neighbor (or the average of the k distances). Normal records have close neighbors; anomalies do not. Take the highest scores as outliers.

Python k-NN distance scores

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The three injected points get the top scores. A weakness: a single global threshold treats a point near a dense cluster the same as a point near a sparse cluster, which leads to density-based scoring.

Density-based: Local Outlier Factor (LOF)

LOF compares the local density around a record with the local densities of its neighbors. If the record is in a much sparser area than its neighbors, its LOF is well above 1. A LOF near 1 means "as dense as my neighborhood"; 1.5 and above is suspicious. Because it is relative, LOF works when clusters have different densities.

Python LOF with clusters of different density

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The suspect point scores far higher than its dense neighbors even though a plain distance score would rate the sparse blob's ordinary points as equally "far".

Isolation-based: Isolation Forest

Isolation Forest flips the question: instead of describing normal data, it tries to isolate each record with random splits (pick a random feature, pick a random cut value, repeat). Anomalies are few and different, so a few cuts isolate them; normal records need many. The average path length over many random trees becomes the anomaly score. It is fast, needs no distance computation and works in many dimensions.

Python Isolation Forest and contamination

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

contamination is your prior guess of the anomaly share; it sets the decision threshold. If you do not know it, rank by score and review the top of the list instead of using a hard cut.

One-Class SVM and clustering-based detection

  • One-Class SVM learns a boundary around the normal data (in a kernel-induced space); records outside it are anomalies. Use it when you have only normal examples (novelty detection) and scale the features first.
  • Clustering-based: run a clustering such as k-means and flag records far from their centroid, or tiny clusters, or points DBSCAN labels as noise (see density clustering).
  • Reconstruction-based: compress the data (PCA, autoencoders) and flag records that reconstruct badly.
Python One-Class SVM and PCA reconstruction error

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Which method when?

Situation Good starting point
Few features, one density k-NN distance, Mahalanobis
Clusters of different density LOF
Many features, large data Isolation Forest
Only normal data available One-Class SVM, autoencoder or PCA reconstruction
Time-ordered data Rolling statistics, seasonal decomposition residuals

Evaluating an anomaly detector

Accuracy is useless when anomalies are 0.1% of the data. If you have even a few labeled cases, use precision, recall and the area under the precision-recall curve; ROC AUC can look too good on rare events. Also useful: precision at top-k ("of the 20 records I would send to an analyst, how many are real?"). Without labels, inject synthetic anomalies, check that the detector finds them, and have a domain expert review the top-ranked records.

Python Precision at k and average precision

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Average precision should be compared with the base rate (0.01 here), which is what a random ranking would achieve.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does a LOF value near 1 mean?

    LOF compares local densities; values around 1 mean the record is as dense as its surroundings.
  2. 2. How does Isolation Forest score a record?

    Anomalies need fewer random splits to be isolated, giving them a short average path length.
  3. 3. When is a One-Class SVM appropriate?

    It learns the boundary of normal data and flags anything outside it.
  4. 4. With 0.1% anomalies, why is accuracy a poor metric?

    A useless detector scores nearly perfectly, so use precision, recall and precision-recall measures.

Summary

  • Distance methods score by neighbor distance, LOF by relative local density, Isolation Forest by how easily a record is isolated.
  • One-Class SVM and reconstruction error handle cases where only normal data exists.
  • Set contamination or rank by score and review the top results; evaluate with precision, recall, average precision and precision@k.

Next: Text Mining Basics