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

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

在数据挖掘方面,经常需要在做特征工程和模型训练之前对数据进行清洗,剔除无效数据和异常数据。异常检测也是数据挖掘的一个方向,用于反作弊、伪基站、金融诈骗等领域。
异常检测方法,针对不同的数据形式,有不同的实现方法。常用的有基于分布的方法,在上、下α分位点之外的值认为是异常值(例如图1),对于属性值常用此类方法。基于距离的方法,适用于二维或高维坐标体系内异常点的判别,例如二维平面坐标或经纬度空间坐标下异常点识别,可用此类方法。
异常点/离群点检测算法——LOF
这次要介绍一下一种基于距离的异常检测算法,局部异常因子LOF算法(Local Outlier Factor)。
用视觉直观的感受一下,如图2,对于C1集合的点,整体间距,密度,分散情况较为均匀一致,可以认为是同一簇;对于C2集合的点,同样可认为是一簇。o1、o2点相对孤立,可以认为是异常点或离散点。现在的问题是,如何实现算法的通用性,可以满足C1和C2这种密度分散情况迥异的集合的异常点识别。LOF可以实现我们的目标。
异常点/离群点检测算法——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{xp}, 满足d(p,o,)d(p,o)
b) 在集合中最多有不包括p在内的k-1个点o,C{xp},满足d(p,o,)<d(p,o)
p的第k距离,也就是距离p第k远的点的距离,不包括p,如图3。
异常点/离群点检测算法——LOF
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)
异常点/离群点检测算法——LOF
5) local reachability density:局部可达密度
点p的局部可达密度表示为:

lrdk(p)=1/(oNk(p)reach-distk(p,o)|Nk(p)|)

表示点p的第k邻域内点到p的平均可达距离的倒数。
注意,是p的邻域点Nk(p)到p的可达距离,不是p到Nk(p)的可达距离,一定要弄清楚关系。并且,如果有重复点,那么分母的可达距离之和有可能为0,则会导致lrd变为无限大,下面还会继续提到这一点。
这个值的含义可以这样理解,首先这代表一个密度,密度越高,我们认为越可能属于同一簇,密度越低,越可能是离群点。如果p和周围邻域点是同一簇,那么可达距离越可能为较小的dk(o),导致可达距离之和较小,密度值较高;如果p和周围邻居点较远,那么可达距离可能都会取较大值d(p,o),导致密度较小,越可能是离群点。
6) local outlier factor:局部离群因子
点p的局部离群因子表示为:
LOFk(p)=oNk(p)lrdk(o)lrdk(p)|