Local outlier factor

In anomaly detection, the local outlier factor (LOF) is an algorithm proposed by Markus M.

Uses your system voice; voice and rate in settings.

Snapshot

≈ 3 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

In anomaly detection, the local outlier factor (LOF) is an algorithm proposed by Markus M. Breunig, Hans-Peter Kriegel, Raymond T. Ng and Jörg Sander in 2000 for finding anomalous data points by measuring the local deviation of a given data point with respect to its neighbours. LOF shares some concepts with DBSCAN and OPTICS such as the concepts of "core distance" and "reachability distance", which are used for local density estimation. \text{reachability-distance}_k(A,B)=\max\{k \text{-distance}(B), d(A,B)\} In words, the reachability distance of an object A from B is the true distance between the two objects, but at least the k\text{-distance} of B. Objects that belong to the k nearest neighbors of B (the "core" of B, see DBSCAN cluster analysis) are considered to be equally distant.

The reason for this is to reduce the statistical fluctuations between all points A close to B, where increasing the value for k increases the smoothing effect. Note that this is not a distance in the mathematical definition, since it is not symmetric.

(While it is a common mistake to always use the k\text{-distance}(A) , this yields a slightly different method, referred to as Simplified-LOF ) The local reachability density of an object A is defined by \text{lrd}_k(A) := \frac {\sum_{B \in N_k(A)} \text{reachability-distance}_k(A, B)} which is the inverse of the average reachability distance of the object A from its neighbors. Note that it is not the average reachability of the neighbors from A (which by definition would be the k\text{-distance}(A) ), but the distance at which A can be "reached" from its neighbors.

With duplicate points, this value can become infinite. The local reachability densities are then compared with those of the neighbors using \text{LOF}_k(A) := \frac{1} \sum_{B \in N_k(A)} \frac{\text{lrd}_k(B)}{\text{lrd}_k(A)} = \frac{1}{|N_k(A)| \cdot \text{lrd}_k(A)} \sum_{B \in N_k(A)} \text{lrd}_k(B) which is the average local reachability density of the neighbors divided by the object's own local reachability density.

A value of approximately indicates that the object is comparable to its neighbors (and thus not an outlier). A value below indicates a denser region (which would be an inlier), while values significantly larger than indicate outliers. \text{LOF}_k(A) \sim 1 means Similar density as neighbors, \text{LOF}_k(A) means Higher density than neighbors (Inlier), \text{LOF}_k(A) > 1 means Lower density than neighbors (Outlier).

Text derived from https://en.wikipedia.org/w/index.php?oldid=1374372579 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

4 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.