异常点/离群点检测算法——LOF解析

异常点/离群点检测算法——LOF解析

局部异常因子算法-Local Outlier Factor(LOF)

      在数据挖掘方面，经常需要在做特征工程和模型训练之前对数据进行清洗，剔除无效数据和异常数据。异常检测也是数据挖掘的一个方向，用于反作弊、伪基站、金融诈骗等领域。

异常检测方法，针对不同的数据形式，有不同的实现方法。常用的有基于分布的方法，在上、下分位点之外的值认为是异常值（例如图1），对于属性值常用此类方法。基于距离的方法，适用于二维或高维坐标体系内异常点的判别，例如二维平面坐标或经纬度空间坐标下异常点识别，可用此类方法。

这次要介绍一下一种基于距离的异常检测算法，局部异常因子LOF算法（Local Outlier Factor）。

用视觉直观的感受一下，如图2，对于C1集合的点，整体间距，密度，分散情况较为均匀一致，可以认为是同一簇；对于C2集合的点，同样可认为是一簇。o1、o2点相对孤立，可以认为是异常点或离散点。现在的问题是，如何实现算法的通用性，可以满足C1和C2这种密度分散情况迥异的集合的异常点识别。LOF可以实现我们的目标。

下面介绍LOF算法的相关定义：

        1) d(p,o) ：两点p和o之间的距离；

2) k-distance：第k距离

               对于点p的第k距离 dk(p) 定义如下： 

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

                      a) 在集合中至少有不包括p在内的 k 个点o,∈C{x≠p}， 满足 d(p,o,)≤d(p,o) ； 

                      b) 在集合中最多有不包括p在内的 k−1 个点 o,∈C{x≠p} ，满足 d(p,o,)

60;       p的第k距离，也就是距离p第k远的点的距离，不包括p，如图3。

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) 。

5) local reachability density：局部可达密度

点ｐ的局部可达密度表示为：

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

注意，是p的邻域点 Nk(p) 到p的可达距离，不是p到 Nk(p) 的可达距离，一定要弄清楚关系。并且，如果有重复点，那么分母的可达距离之和有可能为0，则会导致lrd变为无限大，下面还会继续提到这一点。

这个值的含义可以这样理解，首先这代表一个密度，密度越高，我们认为越可能属于同一簇，密度越低，越可能是离群点。如果p和周围邻域点是同一簇，那么可达距离越可能为较小的 dk(o) ，导致可达距离之和较小，密度值较高；如果p和周围邻居点较远，那么可达距离可能都会取较大值 d(p,o) ，导致密度较小，越可能是离群点。

6) local outlier factor：局部离群因子

点p的局部离群因子表示为：

表示点p的邻域点 Nk(p) 的局部可达密度与点p的局部可达密度之比的平均数。

如果这个比值越接近1，说明p的其邻域点密度差不多，p可能和邻域同属一簇；如果这个比值越小于1，说明p的密度高于其邻域点密度，p为密集点；如果这个比值越大于1，说明p的密度小于其邻域点密度，p越可能是异常点。

现在概念定义已经介绍完了，现在再回过头来看一下lof的思想，主要是通过比较每个点p和其邻域点的密度来判断该点是否为异常点，如果点p的密度越低，越可能被认定是异常点。至于密度，是通过点之间的距离来计算的，点之间距离越远，密度越低，距离越近，密度越高，完全符合我们的理解。而且，因为lof对密度的是通过点的第k邻域来计算，而不是全局计算，因此得名为“局部”异常因子，这样，对于图1的两种数据集C1和C2，lof完全可以正确处理，而不会因为数据密度分散情况不同而错误的将正常点判定为异常点。

算法思想已经讲完了，现在进入干货环节，亮代码。

给一个python实现的lof算法：

https://github.com/damjankuznar/pylof

再给一下我fork之后的代码：

https://github.com/wangyibo360/pylof

有区别：

上面提到了，对于重复点局部可达密度可能会变为无限大的问题，我改的代码对这个问题做了处理，如果有重复点方面的场景，可以用我的代码，源代码这块有bug没有fix，而且好像代码主人无踪影了，提的pull也没人管。。。

60;       p的第k距离，也就是距离p第k远的点的距离，不包括p，如图3。

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) 。

5) local reachability density：局部可达密度

点ｐ的局部可达密度表示为：

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

注意，是p的邻域点 Nk(p) 到p的可达距离，不是p到 Nk(p) 的可达距离，一定要弄清楚关系。并且，如果有重复点，那么分母的可达距离之和有可能为0，则会导致lrd变为无限大，下面还会继续提到这一点。

这个值的含义可以这样理解，首先这代表一个密度，密度越高，我们认为越可能属于同一簇，密度越低，越可能是离群点。如果p和周围邻域点是同一簇，那么可达距离越可能为较小的 dk(o) ，导致可达距离之和较小，密度值较高；如果p和周围邻居点较远，那么可达距离可能都会取较大值 d(p,o) ，导致密度较小，越可能是离群点。

6) local outlier factor：局部离群因子

点p的局部离群因子表示为：

表示点p的邻域点 Nk(p) 的局部可达密度与点p的局部可达密度之比的平均数。

如果这个比值越接近1，说明p的其邻域点密度差不多，p可能和邻域同属一簇；如果这个比值越小于1，说明p的密度高于其邻域点密度，p为密集点；如果这个比值越大于1，说明p的密度小于其邻域点密度，p越可能是异常点。

现在概念定义已经介绍完了，现在再回过头来看一下lof的思想，主要是通过比较每个点p和其邻域点的密度来判断该点是否为异常点，如果点p的密度越低，越可能被认定是异常点。至于密度，是通过点之间的距离来计算的，点之间距离越远，密度越低，距离越近，密度越高，完全符合我们的理解。而且，因为lof对密度的是通过点的第k邻域来计算，而不是全局计算，因此得名为“局部”异常因子，这样，对于图1的两种数据集C1和C2，lof完全可以正确处理，而不会因为数据密度分散情况不同而错误的将正常点判定为异常点。

算法思想已经讲完了，现在进入干货环节，亮代码。

给一个python实现的lof算法：

https://github.com/damjankuznar/pylof

再给一下我fork之后的代码：

https://github.com/wangyibo360/pylof

有区别：

上面提到了，对于重复点局部可达密度可能会变为无限大的问题，我改的代码对这个问题做了处理，如果有重复点方面的场景，可以用我的代码，源代码这块有bug没有fix，而且好像代码主人无踪影了，提的pull也没人管。。。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。