机器学习-异常检测算法(二):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
目录
相关文章
|
19天前
|
机器学习/深度学习 存储 运维
机器学习异常检测实战:用Isolation Forest快速构建无标签异常检测系统
本研究通过实验演示了异常标记如何逐步完善异常检测方案和主要分类模型在欺诈检测中的应用。实验结果表明,Isolation Forest作为一个强大的异常检测模型,无需显式建模正常模式即可有效工作,在处理未见风险事件方面具有显著优势。
119 46
|
2月前
|
机器学习/深度学习 数据采集 人工智能
20分钟掌握机器学习算法指南
在短短20分钟内,从零开始理解主流机器学习算法的工作原理,掌握算法选择策略,并建立对神经网络的直观认识。本文用通俗易懂的语言和生动的比喻,帮助你告别算法选择的困惑,轻松踏入AI的大门。
144 7
|
5月前
|
机器学习/深度学习 算法 数据安全/隐私保护
基于GRU网络的MQAM调制信号检测算法matlab仿真,对比LSTM
本研究基于MATLAB 2022a,使用GRU网络对QAM调制信号进行检测。QAM是一种高效调制技术,广泛应用于现代通信系统。传统方法在复杂环境下性能下降,而GRU通过门控机制有效提取时间序列特征,实现16QAM、32QAM、64QAM、128QAM的准确检测。仿真结果显示,GRU在低SNR下表现优异,且训练速度快,参数少。核心程序包括模型预测、误检率和漏检率计算,并绘制准确率图。
146 65
基于GRU网络的MQAM调制信号检测算法matlab仿真,对比LSTM
|
1月前
|
机器学习/深度学习 监控 算法
面向办公室屏幕监控系统的改进型四叉树屏幕变化检测算法研究
本文提出一种改进型四叉树数据结构模型,用于优化办公室屏幕监控系统。通过动态阈值调节、变化优先级索引及增量更新策略,显著降低计算复杂度并提升实时响应能力。实验表明,该算法在典型企业环境中将屏幕变化检测效率提升40%以上,同时减少资源消耗。其应用场景涵盖安全审计、工作效能分析及远程协作优化等,未来可结合深度学习实现更智能化的功能。
37 0
|
3月前
|
机器学习/深度学习 存储 Kubernetes
【重磅发布】AllData数据中台核心功能:机器学习算法平台
杭州奥零数据科技有限公司成立于2023年,专注于数据中台业务,维护开源项目AllData并提供商业版解决方案。AllData提供数据集成、存储、开发、治理及BI展示等一站式服务,支持AI大模型应用,助力企业高效利用数据价值。
|
4月前
|
机器学习/深度学习 人工智能 自然语言处理
AI训练师入行指南(三):机器学习算法和模型架构选择
从淘金到雕琢,将原始数据炼成智能珠宝!本文带您走进数字珠宝工坊,用算法工具打磨数据金砂。从基础的经典算法到精密的深度学习模型,结合电商、医疗、金融等场景实战,手把手教您选择合适工具,打造价值连城的智能应用。掌握AutoML改装套件与模型蒸馏术,让复杂问题迎刃而解。握紧算法刻刀,为数字世界雕刻文明!
144 6
|
4月前
|
机器学习/深度学习 存储 算法
基于MobileNet深度学习网络的活体人脸识别检测算法matlab仿真
本内容主要介绍一种基于MobileNet深度学习网络的活体人脸识别检测技术及MQAM调制类型识别方法。完整程序运行效果无水印,需使用Matlab2022a版本。核心代码包含详细中文注释与操作视频。理论概述中提到,传统人脸识别易受非活体攻击影响,而MobileNet通过轻量化的深度可分离卷积结构,在保证准确性的同时提升检测效率。活体人脸与非活体在纹理和光照上存在显著差异,MobileNet可有效提取人脸高级特征,为无线通信领域提供先进的调制类型识别方案。
|
5月前
|
机器学习/深度学习 算法 数据安全/隐私保护
基于机器学习的人脸识别算法matlab仿真,对比GRNN,PNN,DNN以及BP四种网络
本项目展示了人脸识别算法的运行效果(无水印),基于MATLAB2022A开发。核心程序包含详细中文注释及操作视频。理论部分介绍了广义回归神经网络(GRNN)、概率神经网络(PNN)、深度神经网络(DNN)和反向传播(BP)神经网络在人脸识别中的应用,涵盖各算法的结构特点与性能比较。
|
5月前
|
机器学习/深度学习 算法 安全
基于深度学习的路面裂缝检测算法matlab仿真
本项目基于YOLOv2算法实现高效的路面裂缝检测,使用Matlab 2022a开发。完整程序运行效果无水印,核心代码配有详细中文注释及操作视频。通过深度学习技术,将目标检测转化为回归问题,直接预测裂缝位置和类别,大幅提升检测效率与准确性。适用于实时检测任务,确保道路安全维护。 简介涵盖了算法理论、数据集准备、网络训练及检测过程,采用Darknet-19卷积神经网络结构,结合随机梯度下降算法进行训练。
|
4月前
|
机器学习/深度学习 数据采集 算法
基于yolov2和googlenet网络的疲劳驾驶检测算法matlab仿真
本内容展示了基于深度学习的疲劳驾驶检测算法,包括算法运行效果预览(无水印)、Matlab 2022a 软件版本说明、部分核心程序(完整版含中文注释与操作视频)。理论部分详细阐述了疲劳检测原理,通过对比疲劳与正常状态下的特征差异,结合深度学习模型提取驾驶员面部特征变化。具体流程包括数据收集、预处理、模型训练与评估,使用数学公式描述损失函数和推理过程。课题基于 YOLOv2 和 GoogleNet,先用 YOLOv2 定位驾驶员面部区域,再由 GoogleNet 分析特征判断疲劳状态,提供高准确率与鲁棒性的检测方法。

热门文章

最新文章