异常检测算法-LOF（Local Outlie Factor）

LOF异常检测算法是一种基于密度的异常检测算法，基于密度的异常检测算法主要思想是：给定的样本数据集，对于数据集中的点，如果其局部领域的点都很密集，那么这个点大概率为正常的数据点；而如果这个点距离其相邻的点距离较远，也就是在一个局部领域的点密度较小，那么这个点可能为异常点。

1 算法简介

LOF算法通过对计算数据集中的每一个点的离群因子LOF，对离群因子的大小进行判断，如果离群因子远大于1，将该点判断为异常点，如果离群因子接近1，则数据点为正常样本点。

定义$d_k(O)$为点O的k-邻近距离，$d_k(O)=d(O,P)$满足以下两个条件：

也就是说第k距离就是距离点P第k远的点，不包括点P在内，如下图所示：

WechatIMG137

定义$N_k(O)$为点O的第k距离邻域，那么它需要满足：

也就是点O的第k距离以内的所有点，包括第k距离。在上图中点O的第5邻域为${P,P_1,P_2,P_3,P_4,P_5}$，$|N_k(O)|=5$

定义$d_k(P,O)$为点P到点O的可达距离，那么它满足：

也就是说点O的第k邻域内的所有点到点O的可达距离均为点O点第k距离。

点P的局部可达密度$\rho_k(P)= \frac{|N_k(P)|}{\sum_{O\in N_k(P)}d_k(P,O)}$

可以理解为点P到其第k邻域内到点的可达距离的均值的倒数，如果点P与其第k邻域内的点是属于同一个簇，那么点P到这些点的可达距离均值就会很小，因此局部可达密度就会较高。反之，如果点P与其第k邻域内的点不在同一个簇，那么它们之间的可达距离就会很大，即局部可达密度较小。

注意：这里会有一个问题，当存在和p点重复的k个点时，那么这个时候点P的第k邻域内的点到点P点可达距离都是0，此时会造成分母为0，导致局部可达密度无限大的情况。

如果单纯的使用局部可达密度来衡量一个点是否异常，会有一个问题，局部可达密度容易受到簇的密度的影响，当样本空间里存在多个密度不同的簇时，密度较大的簇它的局部可达密度会比较大，容易造成误判。而LOF的思想不仅仅是看它的绝对密度，而是看这个点和相邻点的相对密度。

点P的局部离群因子$LOF_k(P) = \frac{\sum_{O\in{N_k(P)}}\frac{\rho_k(O)}{\rho_k(P)}}{|N_k(p)|}$

LOF主要是通过点的第k邻域内的点的平均局部可达密度与当前点的局部可达密度比值来衡量点的异常，也就是该点的相对密度。如果这个比值等于1，说明这个点和其邻域内的点的密度一致，因此它们可能属于同一个簇；而当这个比值大于1时，说明这个点的局部可达密度，相对于其相邻点都要小，因此它可能是异常点。

LOF算法的主要流程比较简单，如下所示

1. 遍历数据集中的所有点
    a) 计算每一个点与其他点的欧式距离；
    b) 对欧式距离进行排序，计算第k距离及其第k邻域；
    c) 计算点的局部可达密度；
    d) 计算点的局部离群因子；
2. 对所有点的局部离群因子进行排序，输出

LOF的优点有以下几点：

而LOF的缺点也比较明显