Local Outlier Factor

什么是Local Outlier Factor?

LOF(Local Outlier Factor)，又称局部异常因子算法。

区别于Isolation Forest算法(切分次数)，LOF算法以距离为切入点，做异常检测。

以上图为例，可以很简单的理解距离做异常检测来源的想法。

1.d(p,o)

两点p和o之间的距离；

2.k-distance第k距离

dk(p)=d(p,o)dk(p)=d(p,o)，并且满足：

　　　　　　a) 在集合中至少有不包括p在内的k个点o'∈C{x≠p}，满足d(p,o')≤d(p,o) ;(就是包括圈边的点，最少为k)

　　　　　　b) 在集合中最多有不包括p在内的k−1个点o'∈C{x≠p}，满足d(p,o,)<d(p,o);(就是不含圈边的点，最多为k-1)

　　　　p的第k距离，也就是距离p第k远的点的距离，不包括p(这句话很重要)

Local Outlier Factor

3.k-distance neighborhood of p:第k距离邻域

点p的第k距离邻域Nk(p)，就是p的第k距离即以内的所有点，包括第k距离。

因此p的第k邻域点的个数 |Nk(p)|≥k。

4. reach-distance：可达距离

点o到点p的第k可达距离定义为:

reach−distancek(p,o)=max{k−distance(o),d(p,o)}

也就是，点o到点p的第k可达距离，至少是o的第k距离，或者为o、p间的真实距离。

这也意味着，离点o最近的k个点，o到它们的可达距离被认为相等，且都等于dk(o)。

如图4，o1到p的第5可达距离为d(p,o1)，o2到p的第5可达距离为d5(o2)。 (这是一个矢量)

Local Outlier Factor

好了，接下来到最重要的东西了

local reachability density：局部可达密度

Local Outlier Factor

表示点p的第k邻域内点到p的平均可达距离的倒数。

这个值的理解可以这么来，首先p的第k距离邻域的应该是死的，所以就看上面的可达距离。从上图中可以看出来，可达距离越小，说明越是同一簇中的数据。所以局部可达密度越大，密度越高，我们就认为越可能属于同一簇。(反之亦然)

ps:这里有个点不是很懂，为什么重复点会导致可达距离之和为0

local outlier factor：局部离群因子

Local Outlier Factor

其实这个式子我不是很懂。但其实只要看懂上面的就好了。局部可达密度之比，第k邻域内的点和p点相比。首先我们假设为同一簇，那么这个比值应该是接近于1的。然后外面有一个加，就是把第k邻域内的点全部算一遍。最后再除以这个个数。嗯，分母是为了让它趋近于1，这样我们有一个比较量。

下面给出官方的说法

如果这个比值越接近1，说明p的其邻域点密度差不多，p可能和邻域同属一簇；如果这个比值越小于1，说明p的密度高于其邻域点密度，p为密集点；如果这个比值越大于1，说明p的密度小于其邻域点密度，p越可能是异常点(可以结合上面的图来理解)。

基于距离结合密度的概念是LOF的核心思想