原创 小伍哥
收录于合集#异常检测17个
LOF这个算法，我之前转载过一篇文章，并且网上写的也很多，各种文章的介绍，都是很多圈圈，我是看着看着，就蒙圈了，初学者很难理解里面的各种距离和转换，我今天换个角度讲讲，希望能帮助大家理解。这个算法非常简单，总结一句话：就是找邻居，然后加减乘除就完了。
一、LOF与KNN的关系？ 在scikit-learn库里面，把这个算法放在了KNN这个系列，其实就是简单的距离计算。简单说：就是一个点的密度，与邻居的平均密度比，某个点的密计算，与其K个邻居有关。所以，我们只要理解一个点的密度怎么算就行了 二、LOF相关的定义先讲几个基本概念，看不懂没关系，先看下面的案例，结合起来就很轻松的能看懂了。
1、可达距离
一个点的密度怎么计算呢？首先就是找到每个点的K个邻居。初步理解就是这个点的K个邻居到这个点的距离的平均值。有两个点要注意，第一是计算邻居到该点的距离，第二个是取平均。上面的理解，我们还需要细化下，距离的计算，用了一个叫可达距离替换，而不是简单的距离计算，可达距离的定义如下：max{点o的第k距离，o到p的距离}。如下所示，计算C的密度，其中一个需要计算B到C的可达距离，也就是计算B的两个邻居的最远距离，和B到C的实际距离，哪个大取哪个，本例中取100.9（具体案例看下文），然后计算D到C的可达距离，然后计算密度就行了。
2、局部可达密度点p的第k距离局部可达密度表示为：点p的第k距离临域中所有的点，这些点到点p的第k可达距离的平均值的倒数
这个值的含义可以这样理解，首先这代表一个密度，密度越高，我们认为越可能属于同一簇，密度越低，越可能是离群点。
3、局部离群因子点p的局部离群因子 = 点p的K个邻居的密度的平均值/点p的密度
三、手动计算LOF我们拿一个简单的一维数据举例：[[-1.1], [0.2], [101.1], [0.3]]，计为[A,B ,C,D]，我们简单处理下，做个排序，方便计算，排序后的数据为：[[-1.1], [0.2], [0.3]，[101.1]]，顺序为：[A,B D,C]
可以看到，C点是明显异常的点，我们就来手动计算C点的LOF值，我们这里取K等于2，也就是每个点计算距离时考虑2个邻居，其实蛮复杂的，要找到3阶邻居才能完成计算，如下图所示。
我们计算分两个大步骤：1）计算C的局部密度 2）计算C的两个邻居B、D的局部密度，并取平均。然后相除就可以得到相对密度，也就是LOF的值。
1、C点的局部密度计算一定要注意，计算C点的密度，我们要计算他的两个邻居B、D到C点的可达距离，不是C到B、D。
B到C的可达距离：B点的两个邻居A、D，K距离为最远的一个1.3，B到C的实际距离为100.9，可达距离取最大值，为100.9。
D到C的可达距离：D点的两个邻居B、A，K距离为最远的一个1.4，B到C的实际距离为100.8，可达距离取最大值，为100.8。
因此，可达密度为：2/(100.9+100.8)
2、B、D两点的局部密度计算和上面的方法一致，只不过邻居需要再拓展一个维度
1）B点密度计算B点的最近两个邻居为D、A
D到B的可达距离：D点的两个邻居B、A，K距离为最远的一个1.4，D到B的实际距离为0.1，可达距离取最大值，为1.4。
A到B的可达距离：A点的两个邻居B、D，K距离为最远的一个1.4，B到A的实际距离为1.3，可达距离取最大值，为1.4。
因此，可达密度为：2/(1.4+1.4)
2）D点密度计算D点的最近两个邻居为B、A
B到D的可达距离：B点的两个邻居D、A，K距离为最远的一个1.3，B到D的实际距离为0.1，可达距离取最大值，为1.3。
A到D的可达距离：A点的两个邻居B、D，K距离为最远的一个1.4，A到D的实际距离为1.4，可达距离取最大值，为1.4。
因此，可达密度为：2/(1.3+1.4)
3、合并计算LOF值LOF = ( (2/(1.4+1.4) + 2/(1.4+1.3) )/( 2/(100.8+100.9) ))/2 = 73.36970899470899
4、官方库计算import pandas as pdpd.set_option('display.float_format',lambda x: '%.4f' % x)import numpy as npnp.set_printoptions(suppress = True)
import numpy as npfrom sklearn.neighbors import LocalOutlierFactorX = [[-1.1], [0.2], [101.1], [0.3]]clf = LocalOutlierFactor(n_neighbors=2)clf.fit_predict(X)clf.negative_outlier_factor_array([ -0.98214286, -1.03703704, -73.36970899, -0.98214286])
可以看到，第三个就是我们要计算的值，这里得到的数据为-73.36970899，与计算的值73.36970899470899几乎一致，为啥说几乎呢，因为往后面四色五入的话，应该还有点微弱的差异，我们看看他的源代码，发现在计算平均密度的时候，加了一个很微小的值1e-10，就是这个差异，导致我们手动算的数据对不上。
((2/(2.8+1e-10)+2/(2.7+1e-10)))/(2/(100.8+100.9+1e-10))/2 = 73.36970899207562
这样计算下来，就和官方的一模一样了，证明我们计算的没有错误。
大家可以参考这个思路，计算一下其他几个点的密度，算一次绝对就理解的特别透彻了。
··· END ···
往期精彩：
