DEV Community

Devanshu Biswas
Devanshu Biswas

Posted on

Local Outlier Factor: Why a Global Distance Cutoff Fails and a Local Density Ratio Wins

#python #datascience #statistics #machinelearning

Every distance-based outlier detector before LOF asks one global question: "how far is this point from the bulk?" That question breaks the instant your data has regions of different density. A point sitting a perfectly normal distance from its neighbours inside a loose cluster looks, to a global cutoff, exactly like a genuine anomaly hovering just outside a tight one. Set the threshold low enough to catch the real anomaly and it condemns the whole loose cluster; set it high enough to spare them and it sails past a fringe point on the dense cluster.

The Local Outlier Factor (Breunig et al.) fixes this by making the comparison local: score each point by how its own neighbourhood density compares to the density of its neighbours' neighbourhoods. It's a stack of four small quantities, each a few lines.

k-distance and the reachability distance

Start with brute-force kNN — for each point, every other point sorted nearest-first. The k-distance is the distance to the k-th nearest neighbour: a per-point notion of "how far is near here." Then the reachability distance floors the raw distance by the neighbour's own k-distance:

// reach-dist_k(A, B) = max( k-distance(B), d(A,B) )  — floored by B's k-distance
function reachDist(i, j, pts, kdist) {
  return Math.max(kdist[j], dist(pts[i], pts[j]));
}
Enter fullscreen mode Exit fullscreen mode

That floor is a smoothing trick: if A falls almost on top of B, the raw distance would spike the density estimate, so we pretend it's exactly B's k-distance. It's deliberately asymmetric — reach(A,B) ≠ reach(B,A) in general.

Local reachability density, then the ratio

A point's density is the inverse of its average reachability distance to its neighbourhood — small average means crowded means high lrd; big average means lonely means low lrd.

function localReachDensity(i, Nk, pts, kdist) {
  const nb = Nk[i];
  let s = 0;
  for (const j of nb) s += reachDist(i, j, pts, kdist);
  const avg = s / Math.max(1, nb.length);
  return avg > 1e-12 ? 1 / avg : 1e12;   // crowded → big, lonely → small
}
Enter fullscreen mode Exit fullscreen mode

lrd is still an absolute local density. The score itself is the step that makes densities comparable across regions — divide the average lrd of your neighbours by your own:

// LOF(i) = mean( lrd(neighbour) ) / lrd(i)
function lofScore(i, Nk, lrd) {
  const nb = Nk[i];
  let s = 0;
  for (const j of nb) s += lrd[j];
  const meanNbLrd = s / Math.max(1, nb.length);
  return meanNbLrd / (lrd[i] > 1e-12 ? lrd[i] : 1e-12);
}
// ≈1 inlier · ≫1 local outlier · <1 in a denser pocket than the neighbours
Enter fullscreen mode Exit fullscreen mode

Why the ratio is the whole point

That division self-normalises. A loose cluster and a tight cluster both score LOF ≈ 1 internally, because inside each cluster every point is about as dense as its crowd. Only points that are genuinely sparse for their own region spike to ≫ 1 — "my neighbours live somewhere far denser than I do." So LOF catches a fringe point on the dense cluster that a global cutoff waves through, and spares a loose-cluster point a global cutoff would wrongly condemn. That gap is the entire reason a local method exists.

The one driver stitches it together, and order matters — every k-distance must exist before any reachability distance, every lrd before any ratio. It's O(n²) naively; scikit-learn's LocalOutlierFactor swaps in a spatial tree, but the quantities on top are identical. Its single most important knob is n_neighbors (k): too small chases sampling noise, too large drags the "local" comparison back toward the global one it was built to escape.

Explore the LOF-vs-global head-to-head and the per-point anatomy live: https://dev48v.infy.uk/ml/day57-local-outlier-factor.html

Top comments (0)