机器学习-异常检测算法(二):Local Outlier Factor

简介: Local Outlier Factor(LOF)是基于密度的经典算法(Breuning et.al. 2000), 文章发表于 SIGMOD 2000, 到目前已经有 3000+ 的引用。在 LOF 之前的异常检测算法大多是基于统计方法的,或者是借用了一些聚类算法用于异常点的识别(比如 ,DBSCAN,OPTICS)。

Local Outlier Factor(LOF)是基于密度的经典算法(Breuning et.al. 2000), 文章发表于 SIGMOD 2000, 到目前已经有 3000+ 的引用。在 LOF 之前的异常检测算法大多是基于统计方法的,或者是借用了一些聚类算法用于异常点的识别(比如 ,DBSCAN,OPTICS)。但是,基于统计的异常检测算法通常需要假设数据服从特定的概率分布,这个假设往往是不成立的。而聚类的方法通常只能给出 0/1 的判断(即:是不是异常点),不能量化每个数据点的异常程度。相比较而言,基于密度的LOF算法要更简单、直观。它不需要对数据的分布做太多要求,还能量化每个数据点的异常程度(outlierness)。

算法介绍

LOF 是基于密度的算法,其最核心的部分是关于数据点密度的刻画。如果对 distanced-based 或者 density-based 的聚类算法有些印象,你会发现 LOF 中用来定义密度的一些概念似曾相识。了解了这些核心概念,整个算法也就显而易见了。而整个算法,最主要的是下面四个概念:

K-邻近距离(k-distance):在距离数据点 p 最近的几个点中,第 k 个最近的点跟点 p 之间的距离称为点 p 的 K-邻近距离,记为 k-distance (p) 。

可达距离(rechability distance):可达距离的定义跟K-邻近距离是相关的,给定参数k时, 数据点 p 到 数据点 o 的可达距离 reach-dist(p, o)为数据点 o 的K-邻近距离 和 数据点p与点o之间的直接距离的最大值。即:

$$ reach\\_dist_{k}(p,o)=\max\\{k\text{-}distance(o),d(p,o)\\} $$

局部可达密度(local rechability density):局部可达密度的定义是基于可达距离的,对于数据点 p,那些跟点p的距离小于等于 k-distance(p)的数据点称为它的 k-nearest-neighbor,记为 $N_k(p)$,数据点 p 的局部可达密度为它与邻近的数据点的平均可达距离的倒数,即:

$$ lrd_{k}(p)=\frac{1}{\frac{\sum_{o\in{N_{k}(p)}}reach\_dist_k(p,o)}{|N_k(p)|}} $$

局部异常因子(local outlier factor):根据局部可达密度的定义,如果一个数据点跟其他点比较疏远的话,那么显然它的局部可达密度就小。但LOF算法衡量一个数据点的异常程度,并不是看它的绝对局部密度,而是看它跟周围邻近的数据点的相对密度。这样做的好处是可以允许数据分布不均匀、密度不同的情况。局部异常因子即是用局部相对密度来定义的。数据点 p 的局部相对密度(局部异常因子)为点p的邻居们的平均局部可达密度跟数据点p的局部可达密度的比值,即:

$$ LOF_{k}(p)=\frac{\sum_{o\in{N_k(p)}}\frac{lrd(o)}{lrd(p)}}{|N_{k}(p)|}=\frac{\sum_{o\in{N_{k}(p)}}lrd(o)}{|N_{k}(p)|}/lrd(p) $$

根据局部异常因子的定义,如果数据点 p 的 LOF 得分在1附近,表明数据点p的局部密度跟它的邻居们差不多;如果数据点 p 的 LOF 得分小于1,表明数据点p处在一个相对密集的区域,不像是一个异常点;如果数据点 p 的 LOF 得分远大于1,表明数据点p跟其他点比较疏远,很有可能是一个异常点。下面这个图来自 Wikipedia 的 LOF 词条,展示了一个二维的例子。上面的数字标明了相应点的LOF得分,可以让人对LOF有一个直观的印象。

800px-LOF.svg.png

了解了 LOF 的定义,整个算法也就显而易见了:

  1. 对于每个数据点,计算它与其它所有点的距离,并按从近到远排序;
  2. 对于每个数据点,找到它的 k-nearest-neighbor,计算 LOF 得分。

算法应用

LOF算法中关于局部可达密度的定义其实暗含了一个假设,即:不存在大于等于 k 个重复的点。当这样的重复点存在的时候,这些点的平均可达距离为零,局部可达密度就变为无穷大,会给计算带来一些麻烦。在实际应用时,为了避免这样的情况出现,可以把 k-distance 改为 k-distinct-distance,不考虑重复的情况。或者,还可以考虑给可达距离都加一个很小的值,避免可达距离等于零。

LOF 算法需要计算数据点两两之间的距离,造成整个算法时间复杂度为 $O(n^2)$ 。为了提高算法效率,后续有算法尝试改进。FastLOF (Goldstein,2012)先将整个数据随机的分成多个子集,然后在每个子集里计算 LOF 值。对于那些 LOF 异常得分小于等于 1 的,从数据集里剔除,剩下的在下一轮寻找更合适的 nearest-neighbor,并更新 LOF 值。这种先将数据粗略分成多个部分,然后根据局部计算结果将数据过滤来减少计算量的想法,并不罕见。比如,为了改进 K-means 的计算效率, Canopy Clustering 算法也采用过比较相似的做法。

参考文献

  1. M. M. Breunig, H. P. Kriegel, R. T. Ng, J. Sander. LOF: Identifying Density-based Local Outliers. SIGMOD, 2000.
  2. M. Goldstein. FastLOF: An Expectation-Maximization based Local Outlier detection algorithm. ICPR, 2012
目录
相关文章
|
20天前
|
机器学习/深度学习 人工智能 自然语言处理
【MM2024】阿里云 PAI 团队图像编辑算法论文入选 MM2024
阿里云人工智能平台 PAI 团队发表的图像编辑算法论文在 MM2024 上正式亮相发表。ACM MM(ACM国际多媒体会议)是国际多媒体领域的顶级会议,旨在为研究人员、工程师和行业专家提供一个交流平台,以展示在多媒体领域的最新研究成果、技术进展和应用案例。其主题涵盖了图像处理、视频分析、音频处理、社交媒体和多媒体系统等广泛领域。此次入选标志着阿里云人工智能平台 PAI 在图像编辑算法方面的研究获得了学术界的充分认可。
【MM2024】阿里云 PAI 团队图像编辑算法论文入选 MM2024
|
8天前
|
机器学习/深度学习 算法 Java
机器学习、基础算法、python常见面试题必知必答系列大全:(面试问题持续更新)
机器学习、基础算法、python常见面试题必知必答系列大全:(面试问题持续更新)
|
16天前
|
机器学习/深度学习 人工智能 算法
【玉米病害识别】Python+卷积神经网络算法+人工智能+深度学习+计算机课设项目+TensorFlow+模型训练
玉米病害识别系统,本系统使用Python作为主要开发语言,通过收集了8种常见的玉米叶部病害图片数据集('矮花叶病', '健康', '灰斑病一般', '灰斑病严重', '锈病一般', '锈病严重', '叶斑病一般', '叶斑病严重'),然后基于TensorFlow搭建卷积神经网络算法模型,通过对数据集进行多轮迭代训练,最后得到一个识别精度较高的模型文件。再使用Django搭建Web网页操作平台,实现用户上传一张玉米病害图片识别其名称。
38 0
【玉米病害识别】Python+卷积神经网络算法+人工智能+深度学习+计算机课设项目+TensorFlow+模型训练
|
24天前
|
机器学习/深度学习 算法 决策智能
【机器学习】揭秘深度学习优化算法:加速训练与提升性能
【机器学习】揭秘深度学习优化算法:加速训练与提升性能
|
20天前
|
机器学习/深度学习 算法 Python
探索机器学习中的决策树算法:从理论到实践
【10月更文挑战第5天】本文旨在通过浅显易懂的语言,带领读者了解并实现一个基础的决策树模型。我们将从决策树的基本概念出发,逐步深入其构建过程,包括特征选择、树的生成与剪枝等关键技术点,并以一个简单的例子演示如何用Python代码实现一个决策树分类器。文章不仅注重理论阐述,更侧重于实际操作,以期帮助初学者快速入门并在真实数据上应用这一算法。
|
3天前
|
存储 JSON 算法
TDengine 检测数据最佳压缩算法工具,助你一键找出最优压缩方案
在使用 TDengine 存储时序数据时,压缩数据以节省磁盘空间是至关重要的。TDengine 支持用户根据自身数据特性灵活指定压缩算法,从而实现更高效的存储。然而,如何选择最合适的压缩算法,才能最大限度地降低存储开销?为了解决这一问题,我们特别推出了一个实用工具,帮助用户快速判断并选择最适合其数据特征的压缩算法。
11 0
|
25天前
|
机器学习/深度学习 算法 大数据
机器学习入门:梯度下降算法(下)
机器学习入门:梯度下降算法(下)
|
17天前
|
机器学习/深度学习 算法 数据处理
EM算法对人脸数据降维(机器学习作业06)
本文介绍了使用EM算法对人脸数据进行降维的机器学习作业。首先通过加载ORL人脸数据库,然后分别应用SVD_PCA、MLE_PCA及EM_PCA三种方法实现数据降维,并输出降维后的数据形状。此作业展示了不同PCA变种在人脸数据处理中的应用效果。
20 0
|
17天前
|
算法 计算机视觉 Python
圆形检测算法-基于颜色和形状(opencv)
该代码实现了一个圆检测算法,用于识别视频中的红色、白色和蓝色圆形。通过将图像从RGB转换为HSV颜色空间,并设置对应颜色的阈值范围,提取出目标颜色的区域。接着对这些区域进行轮廓提取和面积筛选,使用霍夫圆变换检测圆形,并在原图上绘制检测结果。
42 0
|
25天前
|
机器学习/深度学习 算法
机器学习入门:梯度下降算法(上)
机器学习入门:梯度下降算法(上)