Outlier Detection: Quartiles, Distance-Based, Density-Based

• Apply the interquartile-range rule while naming the quartile method, and show that two methods flag different points on one dataset.
• Explain masking, and show when the quartile and z-score rules go blind.
• Define distance-based outliers and explain why a global distance misses local outliers.
• Compute reachability distance, local reachability density, and LOF by hand, and match LocalOutlierFactor, including its sign convention and its handling of ties and duplicates.
• Explain why LOF has no universal threshold, and decide whether an outlier is an error or the finding.

density-based-clustering-with-dbscan labels sparse points as noise, as a side effect of clustering. Outlier detection makes those points the target. A definition by Hawkins, as quoted by Breunig et al. (2000): "An outlier is an observation that deviates so much from other observations as to arouse suspicion that it was generated by a different mechanism." Every method below turns "deviates so much" into a formula, and each formula sees some deviations and misses others. Flagging a point is also only the start, because a flag does not say whether the point is a bad record or the most interesting one in the data.

The quartile rule, and which quartile

With first and third quartiles $Q_1,Q_3$ and $\mathrm{IQR}=Q_3-Q_1$, flag $x$ outside

The factor 1.5 is a convention, the default coef of R's boxplot.stats. The quartile itself has several definitions. For sorted data $x_{(1)}\le\dots\le x_{(n)}$, three common ones are:

Hyndman and Fan (1996) compared the common definitions, noted that one package may use different ones for quantiles and for box plots, and recommended the median-unbiased estimator (type 8). R's quantile() defaults to type 7 while its box plots use hinges. These two agree for odd $n$ and differ for even $n$. So state the method with the rule.

Masking

The rule estimates spread from the same data it screens. Masking happens when outliers distort that estimate enough to hide themselves. The quartile rule resists this up to a point: if more than about a quarter of the data sit on one side, $Q_3$ lands among them and the fence moves past them.

The z-score rule, $\lvert x-\bar x\rvert/s>3$, is much more fragile, and small samples can make it impossible.

Property. With the sample standard deviation $s$ (divisor $n-1$), $\max_i\lvert x_i-\bar x\rvert/s\le(n-1)/\sqrt n$.

For $n=10$ the bound is $2.846$, reached by nine equal values and one different, however far away. The rule with threshold 3 cannot fire for $n\le10$. A robust alternative replaces mean and $s$ with the median and the median absolute deviation (MAD), which resist up to about half the data.

Distance-based outliers

Knorr and Ng (1998) define distance-based outliers, and Breunig et al. restate the definition: $p$ is a $DB(pct,dmin)$-outlier if at least percentage $pct$ of the objects in $D$ lie farther than $dmin$ from it, that is, if $\{q\in D\mid d(p,q)\le dmin\}$, which contains $p$ itself, has at most $(100-pct)\%$ of the size of $D$. Ramaswamy et al. (2000) instead rank points by the distance to their $k$-th nearest neighbor and report the top ones. Both use one global scale. Breunig et al. show the failure: take a dense cluster beside a sparse one, and a point closer to the dense cluster than sparse-cluster points are to their nearest neighbors. Then no $(pct,dmin)$ flags that point without also flagging many sparse-cluster points.

LOF

Breunig et al. compare a point's density with that of its neighbors. Fix MinPts, here $k$, and exclude $p$ from its own neighbor counts.

• $k\text{-distance}(p)$: the distance to $p$'s $k$-th nearest neighbor.
• $N_k(p)$: all objects other than $p$ within $k$-distance of $p$. With ties, $\lvert N_k(p)\rvert$ can exceed $k$.
• Reachability distance: $\text{reach-dist}_k(p,o)=\max\{k\text{-distance}(o),\,d(p,o)\}$. It smooths distances to very close neighbors.
• Local reachability density and the factor:

Property (Breunig et al., Lemma 1). Let $C$ be a set of objects, and let $\varepsilon=\text{reach-dist-max}/\text{reach-dist-min}-1$ over $C$. If $p\in C$, all $k$-nearest neighbors $q$ of $p$ are in $C$, and all $k$-nearest neighbors of those $q$ are in $C$, then $1/(1+\varepsilon)\le\mathrm{LOF}(p)\le1+\varepsilon$. So objects deep in a tight cluster score near 1. The lemma says nothing about a point outside $C$: the paper's Theorem 1 gives separate bounds for any object.

scikit-learn's conventions

• n_neighbors is $k$ and excludes the point. DBSCAN's min_samples, by contrast, includes it.
• negative_outlier_factor_ is $-\mathrm{LOF}$: higher means more normal.
• fit_predict returns $-1$ for outliers, $+1$ for inliers, by comparing with offset_.
• With contamination='auto', offset_ is $-1.5$, so the cut is $\mathrm{LOF}>1.5$. With a float, offset_ is a percentile of the scores, so you set the outlier fraction yourself.
• It uses exactly $k$ neighbors, so it does not keep ties as $N_k(p)$ does.
• It adds $10^{-10}$ to the mean reachability distance, which avoids dividing by zero.
• With novelty=False, the default, only training scores exist: score_samples and decision_function are unavailable. With novelty=True, it scores new data and fit_predict is unavailable. That mode is how a threshold fitted on training data is applied to test data without leakage.

Error or finding?

A statistical flag cannot decide this. Check the record's provenance: is the value impossible (a negative age, a sentinel such as $-999$), a unit slip, or a duplicate load? If so, it is an error, so correct or drop it and say so. If the value is possible, keep it and look for a mechanism, because it may be the finding: Breunig et al. report that their strongest soccer outlier was the league's top scorer. When unsure, report results with and without it. Example 1 shows why: dropping 57 moves the mean from $27.22$ to $23.5$ and the median from $24$ to $23.5$.

Example 1: same data, different flags

Take $11,17,21,23,24,25,27,40,57$ ($n=9$), run in NumPy 2.5.

text
method                 Q1      Q3      IQR     lower    upper    flagged
linear (type 7)        21      27       6.0    12       36       11 40 57
Tukey hinges           21      27       6.0    12       36       11 40 57
median_unbiased (8)    19.67   31.33   11.67    2.17    48.83    57
weibull (type 6)       19      33.5    14.5    -2.75    55.25    57

For type 7 the positions are 3 and 7, so $Q_1=x_{(3)}$ and $Q_3=x_{(7)}$. For type 6 they are $2.5$ and $7.5$, so $Q_1=(17+21)/2$ and $Q_3=(27+40)/2$. The points 11 and 40 are outliers under one definition and normal under another. With odd $n$, hinges equal type 7. Adding 31 makes $n=10$, and they differ: $(21.5,\ 30)$ for type 7 and $(21,\ 31)$ for hinges.

Example 2: masking

Take $10,11,\dots,18$ and append $m$ high values $95,96,\dots$, using type 7.

text
m   n    Q1      Q3      upper fence   IQR rule flags   max z   MAD rule flags
1   10   12.25   16.75    23.5         95               2.832   95
2   11   12.5    17.5     25.0         95 96            2.032   95 96
3   12   12.75   37.25    74.0         95 96 97         1.682   95 96 97
4   13   13.0    95.0    218.0         none             1.476   95 to 98
5   14   13.25   95.75   219.5         none             1.339   95 to 99

At $m=4$, 31% of the data, $Q_3$ is itself an outlier, so the rule flags nothing. The z-score rule with threshold 3 never fires, not even at $m=1$, where $n=10$ makes it impossible. The MAD column flags $\lvert x-\mathrm{med}\rvert/(1.4826\,\mathrm{MAD})>3.5$, and it flags every planted value in each row.

Example 3: LOF by hand

Points on a line, with $k=2$ and no tied distances:

text
A=0  B=1  C=3  D=4.5  E=11

text
p   N2(p)   k-dist   reach-dist to each neighbor    lrd      LOF
A   B C     3        2 (B), 3 (C)                   0.4      0.9545
B   A C     2        3 (A), 2 (C)                   0.4      0.9545
C   D B     2        3.5 (D), 2 (B)                 0.3636   1.05
D   C B     3.5      2 (C), 3.5 (B)                 0.3636   1.05
E   D C     8        6.5 (D), 8 (C)                 0.1379   2.6364

Follow $E$. Its neighbors are $D$ at 6.5 and $C$ at 8. Then $\text{reach-dist}(E,D)=\max\{3.5,6.5\}=6.5$ and $\text{reach-dist}(E,C)=\max\{2,8\}=8$, so $\mathrm{lrd}(E)=1/7.25=0.1379$. Then $\mathrm{LOF}(E)=\tfrac12(0.3636+0.3636)/0.1379=2.6364$.

Lemma 1 applies to $C=\{A,B,C,D\}$: reachability distances run from 2 to 4.5, so $\varepsilon=1.25$ and the bounds are $0.444$ and $2.25$. All four points fit. $E$, outside the set, scores $2.6364$, above the bound.

Example 4: matching scikit-learn

LocalOutlierFactor(n_neighbors=2).fit(X) gives

text
negative_outlier_factor_  [-0.9545 -0.9545 -1.05 -1.05 -2.6364]
offset_ -1.5     fit_predict  [ 1  1  1  1 -1]

The largest gap from the hand values is $6\times10^{-11}$, the effect of the $10^{-10}$ term. Fitted with novelty=True on $A$ to $D$, $E$ gets score_samples $-2.6364$ and decision_function $-1.1364$ (the score minus offset_).

Ties change the result. For $(0,0),(1,0),(-1,0),(0,1),(3,0),(3.5,1)$ with $k=2$, the origin has three neighbors at distance 1. An implementation of the paper's $N_k$ keeps all three and gives it $1.1504$, while scikit-learn keeps two and gives $1.1716$.

Example 5: duplicates

The paper assumes no duplicates. It notes that $\mathrm{lrd}$ is infinite when $p$ has at least MinPts duplicates, and suggests a neighborhood based on distinct coordinates. In scikit-learn, for $0,0,0,1,2.5,4.5$ with n_neighbors=2:

text
negative_outlier_factor_  [-1 -1 -1 -1e+10 -1.7045 -1.925]
UserWarning: Duplicate values are leading to incorrect results. ...

The copies get $\mathrm{lrd}=10^{10}$, purely from the $10^{-10}$ term, so the point at 1 scores $10^{10}$, and this number has no meaning. With two copies of 0 instead of three, or with n_neighbors=3, every score is finite and the point at 1 scores 1. Deduplicate or raise n_neighbors before reading LOF on data with repeats.

Example 6: global distance misses a local outlier

This dataset is not from the paper, though it follows the idea of its Figure 1. From one rng = numpy.random.default_rng(3), draw in this order rng.normal([0, 0], 1.0, (400, 2)) and rng.normal([10, 0], 0.1, (100, 2)), then add $o_1=(0,9)$ and $o_2=(10,1)$, for 502 objects. With $k=10$, the distance column excludes the point itself:

text
              rank of o1   rank of o2   score o1   score o2
10-NN dist    1            18           6.98       0.86
LOF           2            1            8.48       8.87

Sixteen points of the sparse cluster rank above $o_2$ by distance, while LOF puts it first. With $pct=99$, an object is flagged when at most 5 of the 502 objects, itself included, lie within $dmin$. That flags $o_2$ at $dmin=0.5$ along with 34 sparse-cluster points, still flags it at $dmin=0.8$ along with 10, and misses it from $dmin=0.829$ on. Here $o_2$ is 0.71 from the dense cluster, farther than 99% of sparse points are from their nearest neighbor, so the paper's condition does not hold and the collateral is partial, but it never vanishes: on a grid of step 0.001, every $dmin$ that flags $o_2$ also flags at least 7 sparse points.

Example 7: no universal threshold

The paper never fixes a cut-off for LOF. It proposes ranking by the maximum LOF over a range of MinPts, with a lower bound of at least 10. Its experiments show top scores of 2.4 and 6.0 on two hockey tests, and it discusses soccer players with LOF above 1.5 as one choice for that dataset. scikit-learn's documentation says 'auto' follows the original paper, but in the paper 1.5 appears only as the cut for reporting the soccer results. On 500 points from rng = numpy.random.default_rng(5), with no outliers planted, drawn as rng.normal(0, 1, (500, 2)) and then rng.random((500, 2)):

text
data               k=5    k=10   k=20   k=50
Gaussian: LOF>1.5  11     10     15     24
Gaussian: max      2.355  2.111  2.100  2.260
Uniform:  LOF>1.5  3      0      0      0
Uniform:  max      1.561  1.315  1.359  1.342

The same cut flags up to 4.8% of a plain Gaussian, and the count changes with $k$. Read LOF as a ranking, and pick a cut from the cost of reviewing a flag.

• "Three sigma always catches extreme values." It cannot fire for $n\le10$ with the sample standard deviation.
• "LOF above 1 means outlier." Values near 1 are normal, and there is no fixed cut.
• "Flagged means delete." Example 1's mean moves by 3.7 from one point. Removing it needs a reason from the data's origin.

The quartile rule depends on the quartile definition and fails once outliers on one side exceed about a quarter of the data, and the z-score rule can fail far sooner. Distance-based rules use one global scale, so they miss points that are outlying only relative to a dense neighborhood. LOF compares local densities through reachability distance, with values near 1 inside tight clusters. scikit-learn's score is $-\mathrm{LOF}$, it uses exactly $k$ neighbors excluding the point, and it needs care with ties and duplicates. No threshold is universal, and only the data's origin decides between error and finding.