---
title: "Short note: Distance-based anomaly detection"
subject: "Data Mining"
chapter: 6
key: "semester_7/data_mining:distance-based-anomaly-note"
source: https://www.bctengineer.com/q/semester_7/data_mining/distance-based-anomaly-note
site: BCT Engineering
---

# Short note: Distance-based anomaly detection

Data Mining · Chapter 6: Anomaly / Fraud Detection

- Asked in: year not given
- Video: [28 Outlier Analysis, Types, Outlier Detection & Techniques |DM|](https://www.youtube.com/watch?v=aSwQjBS-Osg) — Trouble- Free
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_7/data_mining/distance-based-anomaly-note
- Whole chapter: https://www.bctengineer.com/md/semester_7/data_mining/chapter-6

## Question

Write a short note on distance based approaches for anomaly detection.

## Short answer

Distance-based anomaly detection flags objects far from most others using Euclidean distance. Methods include k-th nearest-neighbour distance, DB(p,D) outliers, and distance to cluster centroid. It is simple and distribution-free but costs O(n^2), depends on parameters, and fails with varying-density clusters or high dimensions.

## Answer

The **distance-based** (proximity-based) approach says that an object is an anomaly if it is **far away from most other objects**. It uses a distance (dissimilarity) measure such as Euclidean distance; no assumption about the data distribution is needed. It is simple and works for multi-dimensional data.

#### Methods
1. **Distance to the k-th nearest neighbour**: the outlier score of an object is its distance to its k-th nearest neighbour (or average distance to the k nearest neighbours). A large score means an outlier.
2. **DB(p, D)-outlier (Knorr and Ng)**: an object o is an outlier if at least a fraction *p* of the objects in the data set lie at a distance greater than *D* from o (i.e. fewer than (1 − p)·n objects are within D).
3. **Distance to the cluster centroid** (clustering-based): after clustering, an object far from the centroid of its cluster, or in a very small cluster, is an outlier.

#### Example
Points on a line: 1, 2, 2, 3, 3, 4, 20. The 1-nearest-neighbour distance of the value 20 is 16 while for the others it is 0 or 1, so 20 is the outlier.

#### Advantages
Simple, no distribution assumptions, can handle multi-dimensional data.

#### Disadvantages
- The cost is O(n²) because of computing all distances (indexing or sampling helps).
- Sensitive to the choice of the parameters k, p and D.
- Cannot detect outliers in data with **clusters of different density** (global threshold); density-based methods like LOF are better.
- Distances lose meaning in high dimensions.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. What is the basic idea of distance-based anomaly detection?
   A. An object is an anomaly if it is far from most other objects
   B. An object is an anomaly if it has low probability
   C. An object is an anomaly if it is in the largest cluster
   D. An object is an anomaly if it is in a dense region
   Answer: A. Proximity-based methods flag objects far from the rest, with no distribution assumption. (Key point: Core idea)

2. What is a DB(p, D)-outlier?
   A. An object with at least fraction p of objects at distance greater than D
   B. An object with D neighbours
   C. An object with distance D to the centroid only
   D. An object in the p-th cluster
   Answer: A. Knorr and Ng: at least a fraction p of data lies farther than D from the object. (Key point: DB(p, D))

3. In the data 1,2,2,3,3,4,20, why is 20 the outlier?
   A. Its 1-NN distance is 16 while others have 0 or 1
   B. It is the mean
   C. It is repeated
   D. It is smallest
   Answer: A. Its nearest neighbour is 4, at distance 16, much larger than the rest. (Key point: Example)

4. What is a disadvantage?
   A. Needs labels
   B. Cannot handle clusters of different density with a global threshold, and costs O(n^2)
   C. Assumes normal distribution
   D. Only works in 1D
   Answer: B. All-pairs distances cost O(n^2) and a global threshold fails with varying density (LOF is better). (Key point: Disadvantage)

## Related in Data Mining

- [Anomaly detection and importance](https://www.bctengineer.com/question.md?key=semester_7%2Fdata_mining%3Aanomaly-detection-intro) — Data Mining, chapter 6
- [Anomaly detection challenges and schemes](https://www.bctengineer.com/question.md?key=semester_7%2Fdata_mining%3Aanomaly-challenges-schemes) — Data Mining, chapter 6
- [Graphical drawbacks; statistical approaches](https://www.bctengineer.com/question.md?key=semester_7%2Fdata_mining%3Aanomaly-graphical-statistical) — Data Mining, chapter 6

## Related in other subjects

- [Natural resource management approaches and sustainability](https://www.bctengineer.com/question.md?key=semester_6%2Fenergy_resources%3Aenvironment-development-society-resource-management) — Energy Resources, chapter 8
- [Intersection sight distance numerical](https://www.bctengineer.com/question.md?key=semester_6%2Ftransportation_engineering_i%3An-81c-intersection-sd) — Transportation Engineering I, chapter 3
- [Redundancy, Hamming distance, linear vs cyclic](https://www.bctengineer.com/question.md?key=semester_5%2Fdata_communication%3Aredundancy-hamming-linear-cyclic) — Data Communication, chapter 8