局部异常因子 (LOF)
- 提出者
- Breunig, M. M.; Kriegel, H.-P.; Ng, R. T.; Sander, J.
- 年份
- 2000
- 类型
- Density-based anomaly detection (unsupervised)
本文为机器翻译,尚未经过审校。 阅读英文原文
它有什么作用?
局部异常因子 (LOF) 是Breunig、Kriegel、Ng和Sander于2000年推出的一种基于密度的无监督异常检测算法。它为每个数据点分配一个连续的异常分数,量化该点相对于其局部邻域的孤立程度,从而能够检测到全局方法因其在空间其他区域的密集簇中而可能遗漏的异常。
方法背后的直觉
想象一张城市地图,大部分人居住在密集的市中心区域。一座孤零零地坐落在乡下的房子显然是孤立的。但LOF更进一步:它还可以标记一个位于中等密集郊区的房子,如果它所有的直接邻居都挤在一个更密集的簇中。LOF不是问‘这个点是否远离一切?’,而是问‘这个点的邻域是否比它自己的邻居的邻域稀疏得多?’。一个邻居比它自己更紧密地聚集在一起的点会得到一个高的LOF分数——这表明它是一个局部异常点,即使它在全局上并不处于一个空旷的区域。
历史学
LOF由Markus Breunig、Hans-Peter Kriegel、Raymond Ng和Jörg Sander在2000年ACM SIGMOD会议上提出。它解决了现有异常检测方法的一个公认局限性——即它们依赖于全局距离阈值,因此会将局部异常与非密集区域中的正常点混淆。该论文引入了局部可达密度和LOF分数的概念,后者迅速成为异常检测领域的基石参考。此后,它被许多变体扩展,包括LoOP(局部异常概率)、LOCI和COF,并被包含在主要的机器学习库中。ACM SIGMOD 2000的论文已积累了数千次引用,被认为是数据挖掘领域密度基方法的基础性工作之一。
何时使用
当异常可能出现在不同密度的簇中,并且全局距离阈值会遗漏稀疏区域中隐藏的异常点或错误地标记合法但稀疏的簇中的点时,LOF是适用的。它适用于具有有意义距离度量的任何连续特征空间,并且不需要标记的异常样本(完全无监督)。它适用于欺诈检测、网络入侵检测、制造质量控制和医学异常筛查等应用。主要假设是内点形成相当凝聚的局部邻域,并且可以计算有意义的成对距离。LOF在n至少为几十到几百时表现最佳;对于非常高维的数据(维度灾难),距离的区分性会降低,建议先进行降维或特征选择。
局限与注意事项
- 朴素实现中的二次时间复杂度使其在没有近似最近邻索引的情况下在大数据集上速度很慢。
- 对k的选择敏感:k太小会导致分数嘈杂;k太大则会模糊局部结构。
- 由于维度灾难,在高维空间中性能会下降。
- 不自然地扩展到流式或在线数据,除非重新计算。
- 不提供可以直接应用于对新点进行评分的模型,除非访问训练集。
来源中的条件不能替代独立的科学审查或分析引擎的验证。
优势
- 检测具有不同密度簇的数据集中的局部异常点,而全局方法会失败。
- 产生连续、可解释的分数,而不是硬性的二元标签,允许灵活选择阈值。
- 完全无监督:不需要标记的异常数据。
- 适用于任何具有可计算距离度量的特征空间,包括非欧氏距离。
- 在对标准化数据计算距离时,对单个特征的尺度具有鲁棒性。
应用
- 金融交易中的欺诈检测,其中欺诈活动会产生局部稀疏的模式。
- 通过标记其局部邻域比周围环境稀疏得多的流量记录来检测网络入侵。
- 制造质量控制,用于识别传感器密集型生产数据中的缺陷项。
- 医学异常筛查——相对于相似的患者群体检测异常的患者特征。
- 具有异质密度的地理和环境数据中的空间异常检测。
使用方式
使用方式
对于每个点p,算法首先计算k距离:到p的第k个最近邻的距离。这定义了p的局部邻域的范围。在该距离内的所有点构成k邻域N_k(p)。k的选择控制着评估局部性的尺度——小的k捕捉细粒度的局部结构,大的k则平滑掉它。
公式
k\text{-dist}(p) = \text{distance to the } k\text{-th nearest neighbor of } p从p到邻居o的可达性距离定义为o的k距离与p和o之间的实际欧氏距离(或其他度量)之间的最大值。这种平滑处理可以防止两个点靠得非常近时产生的不稳定性:它用o自身邻域的更广阔的范围替换了极小的距离,使得密度估计更加鲁棒。
公式
\text{reach-dist}_k(p, o) = \max\{k\text{-dist}(o),\, d(p, o)\}p的局部可达密度(lrd)是p到其所有k个邻居的平均可达距离的倒数。一个被紧密聚集的邻居包围的点具有较小的平均可达距离,因此具有较高的lrd。一个处于稀疏区域的点具有较大的平均可达距离和较低的lrd。
公式
\text{lrd}_k(p) = \left(\frac{\sum_{o \in N_k(p)} \text{reach-dist}_k(p,o)}{|N_k(p)|}\right)^{-1}p的LOF分数是其邻居的lrd值与其自身lrd值的平均比率。如果p的邻居的lrd都远高于p本身——意味着它们生活在更密集的子区域——那么比率将超过1,表明p是一个局部异常点。分数接近1表示p的密度与其周围环境大致相同。远大于1的分数则标志着越来越异常的点。这种局部感知比较是LOF区别于仅基于距离的方法的关键。
公式
\text{LOF}_k(p) = \frac{\sum_{o \in N_k(p)} \frac{\text{lrd}_k(o)}{\text{lrd}_k(p)}}{|N_k(p)|}常见陷阱
- 忘记在计算距离之前标准化或归一化特征,导致高方差特征占主导地位。
- 使用单一的k值而未进行敏感性分析;最佳实践是评估多个k值。
- 将LOF分数视为概率——它是一种相对度量,没有固定的概率解释。
- 在非常高维的数据中忽略维度灾难,并期望LOF在没有预先降维的情况下工作。
- 设置任意的LOF阈值(例如,分数>1.5),而不检查特定数据集的分数分布。
常见问题
如何选择合适的k值?
没有普遍最优的k。通常的做法是评估一系列值——通常是5到50——并检查分数分布和标记的异常点如何变化。跨k值的敏感性分析可以确保检测到的异常点对于k值的选择是稳健的。关于最小预期簇大小的领域知识也可以指导下限。
LOF分数为1与3的含义是什么?
接近1的分数意味着该点的局部密度与其邻居大致相同,被认为是内点。显著大于1的分数——通常根据数据集解释为大于1.5或2——表明该点的邻域比其邻居的邻域稀疏得多。没有普遍的截止值;阈值应通过检查特定数据集的LOF分数分布来选择。
LOF能否在不重新训练的情况下对新的、未见过的数据点进行评分?
LOF是一种归纳式(transductive)方法:它需要训练集存在才能计算任何新点的邻域和密度。要对新观测值进行评分,必须保留训练集,并且必须将每个新点插入以针对存储的训练点重新计算其k邻域。一些实现提供了此功能,但这与学习紧凑评分函数的参数化模型在根本上不同。
LOF与Isolation Forest在异常检测方面有何比较?
LOF使用基于局部邻域的密度估计,在异常点聚集在异质空间局部稀疏区域时更有效。Isolation Forest使用随机划分,并且通常更快、更易于扩展到大型数据集。对于高维或非常大的数据集,通常首选Isolation Forest;对于具有密度变化的适中维度数据,LOF通常提供更精细的区分。
相关方法
参考文献
Breunig, M. M., Kriegel, H.-P., Ng, R. T., & Sander, J. (2000). LOF: Identifying density-based local outliers. Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data, 93–104.
打开 DOI 文献已复制。Aggarwal, C. C. (2017). Outlier Analysis (2nd ed., Ch. 4). Springer.
ISBN:978-3-319-47577-6已复制。Hastie, T., Tibshirani, R., & Friedman, J. (2009). The Elements of Statistical Learning (2nd ed., Ch. 14). Springer.
ISBN:978-0-387-84857-0已复制。