LOF(Local Outlier Factor)原理

1定义

LOF（Local Outlier Factor）是一种描述异常值的方法。

2 k近邻距离（k-distance of an object p）

假设p是查询点，离p最近的第K个点为o，则点p的k近邻距离记为$k-distance(o)$，一般情况下可以认为$k-distance(o)$等于po之间的距离$d(p,o)$。

3 k近邻

假设p是查询点，距离小于k近邻距离的点，都属于点p的k近邻，由集合$N_{k-distance(p)}(p)$表示，简记为$N_k(p)$。
如果对k近邻算法很熟悉的话，以上两个定义都是很自然而然的定义。

4 可达距离

假设p是查询点，o是p的第k个近邻点，则定义p的可达距离：
reach-distk(p,o)=max⁡{k−distance(o),d(p,o)}\text{reach-dist}_k(p, o) = \max \left\{k-distance(o), d(p, o)\right\}reach-distk​(p,o)=max{k−distance(o),d(p,o)}
值得注意的是:$k-distance(o)$是第k个近邻点o的k近邻距离，不是查询点p的k近邻距离（网上博客很多都是错误的）。因此通俗的讲：
对于查询点p而言，假设其第k个近邻点为o，则p的可达距离为o到o的第k个近邻点距离和po的最大值。

5 局部可达密度

假设p是查询点，o是p的近邻点集合N中的任一点，则定义p的可达密度：
$${\mathrm{lrd}}_k(p)=\left(1/\frac{\sum _{o\in N_k(p)}{\text{ reach-dist }}_{\text{k }}(p,o)}{\left|N_{\text{k }}(p)\right|}\right)$$
局部可达密度等于p的所有k近邻点集合(从第一个近邻点到第k个近邻点)对应的可达距离平均值的倒数。$\left|N_{\text{k }}(p)\right|$这里应该表示查询点p的近邻数量，一般情况等于k

6 lof

假设p是查询点，o是p的近邻点集合N中的任一点，lof定义如下：
$${\mathrm{LOF}}_k(p)=\left(\frac{\sum _{o\in N_k(p)}\frac{{lrd}_k(o)}{{lrd}_k(p)}}{\left|N_{\text{k }}(p)\right|}\right)$$
可以看出，lof计算不难，但要计算所有近邻点的局部可达密度，所以应该是比较耗时的。

参考：

lof原文：《LOF: Identifying Density-Based Local Outliers》
Charu C. Aggarwal《data mining》8.5.2.1 Local Outlier Factor (LOF)
sklearn 源码1
pdal源码1