Short note: Distance-based anomaly detection

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.