1. 简介

LOF算法(Local Outlier Factor,局部离群因子检测方法),是基于密度的离群点检测方法中一个比较有代表性的算法。该算法会给数据集中的每个点计算一个离群因子LOF,通过判断LOF是否接近于1来判定是否是离群因子。若LOF远大于1,则认为是离群因子,接近于1,则是正常点。

2. 步骤

LOF是基于密度的算法,其最核心的部分是关于数据点密度的刻画。LOF会计算得到一个数值score,这个score的大致意思是:一个样本点周围最近的K个样本点所处位置的平均密度比上该样本点所在位置的密度。比值越大于1,则该点所在位置的密度越小于其周围样本所在位置的密度,这个点就越有可能是异常点。

2.1 Step 1

首先,从最终的公式开始看,p点的LOF-score的计算公式如下: LOFk(p)=oNklrdk(o)lrdk(p)Nk(p) LOF_{k}(p) = \frac{\sum_{o \in N_{k}} \frac{lrd_{k}(o)}{lrd_{k}(p)}}{\left | N_{k}(p) \right |}

其中Nk(p)N_{k}(p) 表示p点最近的k个点的集合,所以Nk(p)|N_{k}(p)|就是集合元素个数,其实就是k。lrdk(p)lrd_{k}(p) 表示p点的密度,lrdk(o)lrd_{k}(o)表示属于最近k个点的领域内的o点的密度。lrdk(o)lrdk(p) \frac{lrd_{k}(o)}{lrd_{k}(p)} 如果越接近1表示p点和o点密度相同,越可能属于同一类别。

所以上述公式表明,判断p点是不是异常点,计算离p点最近的k个点的密度和p点密度比值之和,最后取平均。这个值也就是最终要的p点的LOF score。

2.2 Step 2

其次,看每个点的密度计算,其实就是平均可达距离的倒数。设avg_reach_dist表示p点到最近的k个点的平均可达距离。计算公式如下: lrdk(p)=1avg_reach_dist=1oNkrech_dist(p,o)Nk lrd_k(p) = \frac{1}{avg\_reach\_dist} = \frac{1}{\frac{\sum_{o \in N_{k}}rech\_dist(p,o)}{|N_{k}|}}

其实求p点到领域内k个点的“距离”,最后加权取平均。这个值的倒数就是我们要的 lrdk(p)lrd_k(p)。但是需要注意的是“距离”并不是定义为两个点的直接距离,而是LOF算法中定义的“可达距离”。

2.3 Step 3

最后,计算可达距离rech_dist(p,o)rech\_dist(p,o)即可。就是说如果p点和o点直接计算的距离dist(p,o)dist(p,o)小于o点的最近第k近邻距离distk(o)dist_k(o)。那么 rech_dist(p,o)=distk(o)rech\_dist(p,o) = dist_k(o),否则rech_dist(p,o)=dist(p,o)rech\_dist(p,o) = dist(p, o)

对于p点,在已知o点属于p点的最近k个点之一。那么rech_dist(p,o)rech\_dist(p,o) 简单来说就是:

  1. 如果p点正好也属于o点的最近k个点中,那么p点和o点的可达距离就是o点的第k个近邻点的距离。也可以认为,对于o点不区分最近k个点的距离,统一设为distk(o)dist_k(o)
  2. 如果p点不属于o点的最近k个点中,那么p点和o点的可达距离就是两者的直接距离。

3. 实现

讲个线下训练和线上测试的思路。

线下训练过程:

  1. 对于训练集中的每个样本。需要需要计算出最近的k个样本点,这是一个O(n2)O(n^2)复杂度的过程。
  2. 然后根据每个目标样本点和最近k个样本点的可达距离,计算出每个目标样本点的密度。这是一个O(n×k)O(n \times k)的复杂度。
  3. 最后存的参数就是训练集中样本点xix_ixix_i的k个最邻近的样本点集合XikX_{ik}、以及xix_i对应的密度。

线上测试过程:

  1. 对于测试集的每一条数据 xix_i,需要先计算出与训练集中最近的k个样本点。
  2. 根据这个k个样本点,和这些样本点的最邻近集合,计算出测试集样本xix_i的密度。
  3. 根据测试样本的密度和训练几种k个样本的平均密度的比值,如果这个值远比1大。那么这个测试集数据xix_i 就是一个异常数据。

4. 参考

  1. 异常检测(三)——Local Outlier Factor(LOF)
  2. 知乎问答:机器学习-异常检测算法(二):Local Outlier Factor
  3. 异常点/离群点检测算法——LOF
  4. python sklearn 文档

results matching ""

    No results matching ""