Local Outlier Factor (LOF)
- Introduced by
- Breunig, M. M.; Kriegel, H.-P.; Ng, R. T.; Sander, J.
- Year
- 2000
- Type
- Density-based anomaly detection (unsupervised)
What does it do?
Local Outlier Factor (LOF) is a density-based, unsupervised anomaly detection algorithm introduced by Breunig, Kriegel, Ng, and Sander in 2000.
It assigns each data point a continuous outlier score that quantifies how isolated that point is relative to its local neighborhood, enabling detection of anomalies that global methods miss because they blend into dense clusters elsewhere in the space.
The intuition behind the method
Imagine a city map where most people live in dense urban districts. A house sitting alone in the countryside is obviously isolated. But LOF goes further: it can also flag a house that sits in a moderately dense suburb when all its immediate neighbors are packed into an even denser cluster. Instead of asking 'is this point far from everything?', LOF asks 'is this point's neighborhood much sparser than the neighborhoods of its own neighbors?' A point whose neighbors all live more tightly together than the point itself gets a high LOF score — signaling that it is a local outlier even if globally it is not in an empty region.
History
LOF was introduced by Markus Breunig, Hans-Peter Kriegel, Raymond Ng, and Jörg Sander at the ACM SIGMOD 2000 conference. It addressed a recognized limitation of existing outlier methods — that they relied on global distance thresholds and therefore confused local anomalies with normal points in less dense regions. The paper introduced the concept of local reachability density and the LOF score, which quickly became a cornerstone reference in anomaly detection. It has since been extended by numerous variants, including LoOP (local outlier probabilities), LOCI, and COF, and is included in major machine-learning libraries. The ACM SIGMOD 2000 paper has accumulated thousands of citations and is treated as one of the foundational works in density-based data mining.
When to use it
LOF is appropriate when anomalies are expected to occur in clusters of varying density and when a global distance threshold would either miss outliers hidden in sparse regions or incorrectly flag points in legitimately sparse but consistent clusters. It works on any continuous feature space with a meaningful distance metric and does not require labeled anomaly examples (fully unsupervised). It suits applications such as fraud detection, network intrusion detection, manufacturing quality control, and medical anomaly screening. The main assumptions are that inliers form reasonably cohesive local neighborhoods and that meaningful pairwise distances can be computed. LOF performs best when n is at least in the tens to low hundreds; for very high-dimensional data (the curse of dimensionality) distances become less discriminative and dimensionality reduction or feature selection is advisable first.
Limitations and considerations
- Quadratic time complexity in the naive implementation makes it slow on large datasets without approximate nearest-neighbor indexing.
- Sensitive to the choice of k: too small a k yields noisy scores; too large a k blurs local structure.
- Performance degrades in very high-dimensional spaces due to the curse of dimensionality.
- Does not scale naturally to streaming or online data without recomputation.
- Provides no model that can be directly applied to score new points without access to the training set.
Source conditions do not replace independent scientific review or validation by an analysis engine.
Strengths
- Detects local outliers in datasets with clusters of varying density, where global methods fail.
- Produces a continuous, interpretable score rather than a hard binary label, allowing flexible threshold choice.
- Fully unsupervised: no labeled anomaly data are required.
- Applicable to any feature space with a computable distance metric, including non-Euclidean distances.
- Robust to the scale of individual features when distances are computed on standardized data.
Applications
- Fraud detection in financial transactions where fraudulent activity creates locally sparse patterns.
- Network intrusion detection by flagging traffic records whose local neighborhood is much sparser than its surroundings.
- Manufacturing quality control to identify defective items in sensor-rich production data.
- Medical anomaly screening — detecting unusual patient profiles relative to similar patient cohorts.
- Spatial anomaly detection in geographic and environmental data with heterogeneous density.
How it works
How it works
For each point p the algorithm first computes the k-distance: the distance to p's k-th nearest neighbor. This defines the reach of p's local neighborhood. All points within that distance form the k-neighborhood N_k(p). The choice of k controls the scale at which locality is assessed — small k captures fine-grained local structure, larger k smooths over it.
Formula
k\text{-dist}(p) = \text{distance to the } k\text{-th nearest neighbor of } pThe reachability distance from p to a neighbor o is defined as the maximum of the k-distance of o and the actual Euclidean (or other metric) distance between p and o. This smoothing prevents instability when two points are extremely close together: it replaces tiny distances with the broader footprint of o's own neighborhood, making density estimates more robust.
Formula
\text{reach-dist}_k(p, o) = \max\{k\text{-dist}(o),\, d(p, o)\}The local reachability density of p (lrd) is the inverse of the average reachability distance from p to all its k neighbors. A point surrounded by tightly packed neighbors has a small average reachability distance, and therefore a high lrd. A point in a sparse region has a large average reachability distance and a low lrd.
Formula
\text{lrd}_k(p) = \left(\frac{\sum_{o \in N_k(p)} \text{reach-dist}_k(p,o)}{|N_k(p)|}\right)^{-1}The LOF score of p is the average ratio of its neighbors' lrd values to p's own lrd. If p's neighbors all have substantially higher lrd than p itself — meaning they live in denser subregions — the ratio exceeds 1, indicating that p is a local outlier. A score near 1 indicates that p has roughly the same density as its surroundings. Scores much greater than 1 flag increasingly anomalous points. This locality-aware comparison is what distinguishes LOF from distance-only methods.
Formula
\text{LOF}_k(p) = \frac{\sum_{o \in N_k(p)} \frac{\text{lrd}_k(o)}{\text{lrd}_k(p)}}{|N_k(p)|}Common pitfalls
- Forgetting to standardize or normalize features before computing distances, causing high-variance features to dominate.
- Using a single value of k without sensitivity analysis; best practice is to evaluate several k values.
- Treating the LOF score as a probability — it is a relative measure without a fixed probabilistic interpretation.
- Ignoring the curse of dimensionality in high-dimensional data and expecting LOF to work without prior dimensionality reduction.
- Setting an arbitrary LOF threshold (e.g., score > 1.5) without inspecting the score distribution for the specific dataset.
Frequently asked questions
How do I choose the right value of k?
There is no universally optimal k. Common practice is to evaluate a range of values — typically 5 to 50 — and inspect how the score distribution and flagged outliers change. A sensitivity analysis across k values gives confidence that detected anomalies are robust to the choice. Domain knowledge about the minimum expected cluster size can also guide the lower bound.
What does a LOF score of 1 versus 3 mean?
A score close to 1 means the point has roughly the same local density as its neighbors and is considered an inlier. A score significantly greater than 1 — often interpreted as above 1.5 or 2 depending on the dataset — indicates that the point's neighborhood is much sparser than its neighbors' neighborhoods. There is no universal cutoff; the threshold should be chosen by inspecting the distribution of LOF scores for the specific dataset.
Can LOF score new, unseen points without retraining?
LOF is a transductive method: it requires the training set to be present to compute neighborhoods and densities for any new point. To score new observations, the training set must be retained and each new point must be inserted to recompute its k-neighborhood against stored training points. Some implementations offer this functionality, but it differs fundamentally from parametric models that learn a compact scoring function.
How does LOF compare to Isolation Forest for anomaly detection?
LOF uses density estimation based on local neighborhoods and is stronger when anomalies cluster in locally sparse regions of a heterogeneous space. Isolation Forest uses random partitioning and tends to be faster and more scalable to large datasets. For high-dimensional or very large datasets, Isolation Forest is often preferred; for moderate-dimensional data with density variation, LOF frequently offers finer discrimination.
Related methods
Sources
Breunig, M. M., Kriegel, H.-P., Ng, R. T., & Sander, J. (2000). LOF: Identifying density-based local outliers. Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data, 93–104.
Open DOI referenceCopied.Aggarwal, C. C. (2017). Outlier Analysis (2nd ed., Ch. 4). Springer.
ISBN: 978-3-319-47577-6Copied.Hastie, T., Tibshirani, R., & Friedman, J. (2009). The Elements of Statistical Learning (2nd ed., Ch. 14). Springer.
ISBN: 978-0-387-84857-0Copied.