局部异常因子简介

局部异常因子,别名:Local Outlier Factor、LOF,它是基于密度的经典算法

核心思想是:异常与否,取决于局部环境。

优点:简单,直观,不需要知道数据集的分布,并能量化每个样本点的异常程度。

算法简介

局部密度:

LOF 认为,某个样本点p的第k个最近邻居越近,表明靠近它的邻居越多,它的局部密度越大;反之,第k个最近邻居越远,它的局部密度越小。

因此,LOF 将样本点 p 的局部密度定义为第 k 个最近邻居的距离的倒数

异常程度:

p 异常与否,并不是取决于 p 的局部密度,而取决于 p 的局部密度与邻居们的局部密度的对比

比如,p 的局部密度虽然小,但它的邻居们局部密度都很小,那么 p 的异常程度就很低。反而,p 的局部密度小,邻居们的局部密度都很大,那么 p 的异常程度就很高。

算法描述

1. 计算出所有样本点的局部密度

k-distance:计算出所有其他点到样本点 p 的距离

样本点p的局部密度 p = 1 / k-distance

若有 k 个或以上的点跟 p 重合,即到 p 的距离是0,则 p 无法计算,要排除这种情况。或者,k-distance 都加上一个很小的值,避免 ρ 无法计算。

2. 计算出所有样本点的异常分数

 

 记所有离样本点 p 的距离小于等于 k-distance 的点的集合为 N,即 p 的 k-distance 以内的邻居们

 

​ 计算出 N 中所有点的局部密度,并取其平均值,记为 ρ-mean

 

​ 样本点 p 的异常分数 score = ρ-mean / ρ

3. 分析异常程度

 

若异常分数接近1,则说明样本点 p 的局部密度跟邻居的接近

 

​若异常分数小于1,表明 p 处于一个相对密集的区域,不像一个异常点

 

​若异常分数远大于1,表明 p 跟其他点比较疏远,很可能是一个异常点

4. LOF 算法要计算样本点的两两距离,时间复杂度为O(n ^ 2)

算法的变种

FastLOF 算法

 

为了提高算法效率,后续有算法尝试改进。FastLOF 先将整个数据随机的分成多个子集,然后在每个子集里计算 LOF 值。

对于那些 LOF 异常得分小于等于1的,从数据集里剔除,剩下的在下一轮寻找更合适的 nearest-neighbor,并更新 LOF 值。

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/wpdjwf.html