异常检测（1）概述

发表于 更新于 分类于 ， ， 阅读次数： 本文字数： 5.3k 阅读时长 ≈ 10 分钟

异常检测 (anomaly detection)

异常检测工具

  • PyOD:超过30种算法，从经典模型到深度学习模型一应俱全，和sklearn的用法一致

  • Scikit-Learn:包含了4种常见的算法，简单易用

  • TODS:与PyOD类似，包含多种时间序列上的异常检测算法

异常检测算法

  • 线性模型：PCA
  • 基于相似度度量的算法：KNN、LOF、HBOS
  • 基于概率的算法：COPOD
  • 集成检测：孤立森林，XGBOD
  • 神经网络算法：自编码器

评估方法

  • ROC-AUC 曲线
  • Precision Topk：top K的准确率
  • AVE Precision：平均准确率

一、概述

1.1 什么是异常检测？

不同于常规模式下的问题和任务，异常检测针对的是少数、不可预测或不确定、罕见的事件，它具有独特的复杂性，使得一般的机器学习和深度学习技术无效。

1.2 异常检测面临的挑战

  • 未知性：异常与许多未知因素有关，例如，具有未知的突发行为、数据结构和分布的实例。它们直到真正发生时才为人所知，比如恐怖袭击、诈骗和网络入侵等应用；
  • 异常类的异构性： 异常是不规则的，一类异常可能表现出与另一类异常完全不同的异常特征。例如，在视频监控中，抢劫、交通事故和盗窃等异常事件在视觉上有很大差异；
  • 类别不均衡：异常通常是罕见的数据实例，而正常实例通常占数据的绝大部分。因此，收集大量标了标签的异常实例是困难的，甚至是不可能的。这导致在大多数应用程序中无法获得大规模的标记数据。

1.3 异常的种类：

  • 点异常（point anomalies）指的是少数个体实例是异常的，大多数个体实例是正常的，例如正常人与病人的健康指标；
  • 条件异常（conditional anomalies），又称上下文异常，指的是在特定情境下个体实例是异常的，在其他情境下都是正常的，例如在特定时间下的温度突然上升或下降，在特定场景中的快速信用卡交易；
  • 群体异常（group anomalies）指的是在群体集合中的个体实例出现异常的情况，而该个体实例自身可能不是异常，例如社交网络中虚假账号形成的集合作为群体异常子集，但子集中的个体节点可能与真实账号一样正常。

1.4 异常检测数据集：

  • 统计型数据static data（文本、网络流）
  • 序列型数据sequential data（sensor data ）
  • 空间型数据spatial data（图像、视频）

1.5 异常检测的应用领域

  • 入侵检测（Intrusion detection）：通过从计算机网络或计算机系统中的若干关键点收集信息并对其执行分析，从中发觉网络或系统中能不能有违反安全策略的行为和遭到袭击的迹象，并对此做出适当反应的流程。最普遍的两种入侵检测系统包括基于主机的入侵检测系统（HIDS）、网络入侵检测系统（NIDS）。
  • 故障检测（Fraud detection）：主要是监控系统，在故障发生时可以识别，并且准确指出故障的种类以及出现位置。主要应用领域包括银行欺诈、移动蜂窝网络故障、保险欺诈、医疗欺诈。
  • 恶意软件检测（Malware Detection）
  • 医疗异常检测（Medical Anomaly Detection）：通过X光片、核磁共振、CT等医学图像检测疾病或量化异常，也可以通过EEG、ECG等时序信号进行疾病检测或异常预警。
  • 深度学习用于社交网络中的异常检测（Deep learning for Anomaly detection in Social Networks）
  • 日志异常检测（Log Anomaly Detection）
  • 物联网大数据异常检测（Internet of things (IoT) Big Data Anomaly Detection）：通过监控数据流信息检测异常设备和系统行为。
  • 工业异常检测（Industrial Anomalies Detection）
  • 时间序列中的异常检测（Anomaly Detection in TimeSeries）
  • 视频监控（Video Surveillance）：检测视频中的异常场景。

1.6 基于标签的可获得性划分异常检测：

  • 有监督异常检测：在训练集中的正常实例和异常实例都有标签，这类方法的缺点在于数据标签难以获得或数据不均衡（正常样本数量远大于异常样本数量）。
  • 半监督异常检测：在训练集中只有单一类别（正常实例）的实例，没有异常实例参与训练，目前很多异常检测研究都集中在半监督方法上，有很多声称是无监督异常检测方法的研究其实也是半监督的，对其解释的是该异常检测是无监督异常检测，学习特征的方式是无监督的，但是评价方式使用了半监督的方法，因此对于无监督与半监督的界定感觉没有那么规范。
  • 无监督异常检测：在训练集中既有正常实例也可能存在异常实例，但假设数据的比例是正常实例远大于异常实例，模型训练过程中没有标签进行校正。
  • 弱监督异常检测：该类我研究的少，不是特别了解，主要是针对异常实例不完全、粗粒度标签、部分实例标签错误等情况进行算法设计。

1.7 基于传统方法的异常检测模型

  • 基于重构的方法： 假设异常点是不可被压缩的或不能从低维映射空间有效地被重构的。常见的方法有PCA、Robust PCA、random projection等降维方法 [4,5] 。
  • 聚类分析方法：通过聚类可以创建数据的模型，而异常点的存在可以扭曲、破坏该模型。常见的方法有Gaussian Mixture Models、 k-means、 multivariate Gaussian Models [6,7,8]。
  • 一类分类方法：对正常数据建立区分性边界，异常点被划分到边界外。常见的方法有OC-SVM [9,10]。

二、常见异常检测算法

一般情况下, 可以把异常检测看成是数据不平衡下的分类问题。因此, 如果数据条件允许, 优先使 用有监督的异常检测[6]。实验结果 [4]发现直接用XGBOOST进行有监督异常检测往往也能得到不错 的结果，没有思路时不妨一试。

而在仅有少量标签的情况下, 也可采用半监督异常检测模型。比如把无监督学习作为一种特征抽取方式来辅助监督学习 \([4,8]\), 和stacking比较类似。这种方法也可以理解成通过无监督的特征工程 对数据进行预处理后, 喂给有监督的分类模型。

但在现实情况中, 异常检测问题往往是没有标签的, 训练数据中并末标出哪些是异常点, 因此必须用无监督学习。从实用角度出发, 我们把文章的重点放在无监督学习上。

本文结构如下: 1. 介绍常见的无监督异常算法及实现; 2. 对比多种算法的检测能力；3. 对比多种算法的运算开销；4. 总结并归纳如何处理异常检测问题。5. 代码重现步骤。

2.1 无监督异常检测

如果归类的话, 无监督异常检测模型可以大致分为:

  • 统计与概率模型 (statistical and probabilistic and models) ：主要是对数据的分布做出假设, 并找出假设下所定义的“异常”, 因此往往会使用极值分析Q或者假设检验。比如对最简单的一维 数据假设高斯分布 \(Q\), 然后将距离均值特定范围以外的数据当做异常点。而推广到高维后, 可以 假设每个维度各自独立, 并将各个维度上的异常度相加。如果考虑特征间的相关性, 也可以用马 氏距离 (mahalanobis distance) 来衡量数据的异常度[12]。不难看出, 这类方法最大的好处就 是速度一般比较快, 但因为存在比较强的"假设", 效果不一定很好。稍微引申一点的话, 其实给每个维度做个直方图做密度估计, 再加起来就是HBOS。
  • 线性模型（linear models）：假设数据在低维空间上有嵌入, 那么无法、或者在低维空间投射后 表现不好的数据可以认为是离群点 \(Q\) 。
    • 举个简单的例子, PCA可以用于做异常检测 [10], 一种方法 就是找到 \(k\) 个特征向量 (eigenvectora), 并计算每个样本再经过这 \(k\) 个特征向量投射后的重建误差 (reconstruction error), 而正常点的重建误差应该小于异常点。
    • 同理, 也可以计算每个样本 到这 \(k\) 个选特征向量所构成的超空间的加权欧氏距离（特征值越小权重越大）。在相似的思路下, 我们也可以直接对协方差矩阵 \(Q\) 进行分析, 并把样本的马氏距离 (在考虑特征间关系时样本到分 布中心的距离) 作为样本的异常度, 而这种方法也可以被理解为一种软性 (Soft PCA) [6]。
    • 同时, 另一种经典算法One-class SVM[3]也一般被归类为线性模型。
  • 基于相似度衡量的模型 (proximity based models) : 异常点因为和正常点的分布不同, 因此相似度较低, 由此衍生了一系列算法通过相似度来识别异常点。
    • 比如最简单的K近邻就可以做异常 检测,一个样本和它第k个近邻的距离就可以被当做是异常值, 显然异常点的k近邻距离更大。
    • 同理, 基于密度分析如LOF [1]、LOCI和LoOP主要是通过局部的数据密度来检测异常。显然, 异常点所在空间的数据点少, 密度低。
    • 相似的是, Isolation Forest[2]通过划分超平面Q来计算"孤立" 一个样本所需的超平面数量（可以想象成在想吃蛋糕上的樱桃所需的最少刀数）。在密度低的空间里 (异常点所在空间中), 孤例一个样本所需要的划分次数更少。
    • 另一种相似的算法ABOD[7] 是计算每个样本与所有其他样本对所形成的夹角的方差, 异常点因为远离正常点, 因此方差变化 小。换句话说, 大部分异常检测算法都可以被认为是一种估计相似度, 无论是通过密度、距离、 夹角或是划分超平面。通过聚类也可以被理解为一种相似度度量, 比较常见不再赘述。
  • 集成异常检测与模型融合: 在无监督学习时, 提高模型的鲁棒性很重要, 因此集成学习就大有用 武之地。比如上面提到的lsolation Forest, 就是基于构建多棵决策树实现的。最早的集成检测框 架feature bagging[9]与分类问题中的随机森林 (random forest) 很像, 先将训练数据随机划分 (每次选取所有样本的 \(d / 2-d\) 个特征, \(d\) 代表特征数) , 得到多个子训练集, 再在每个训练集上训 练一个独立的模型（默认为LOF）并最终合并所有的模型结果（如通过平均）。值得注意的是, 因为没有标签, 异常检测往往是通过bagging和feature bagging比较多, 而boosting比较少见。 boosting情况下的异常检测, 一般需要生成伪标签Q, 可参靠 \([13,14]\) 。集成异常检测是一个新兴但很有趣的领域, 综述文章可以参考 \([16,17,18]\) 。
  • 特定领域上的异常检测：比如图像异常检测 [21], 顺序及流数据异常检测（时间序列异常检测） [22], 以及高维空间上的异常检测 [23], 比如前文提到的Isolation Forest就很适合高维数据上的 异常检测。

不难看出, 上文提到的划分标准其实是互相交织的。比如k-近邻可以看做是概率模型非参数化后的 一种变形, 而通过马氏距离计算异常度虽然是线性模型但也对分布有假设（高斯分布）。Isolation Forest虽然是集成学习, 但其实和分析数据的密度有关, 并且适合高维数据上的异常检测。在这种 基础上, 多种算法其实是你中有我, 我中有你, 相似的理念都可以被推广和应用, 比如计算重建误 差不仅可以用PCA, 也可以用神经网络中的auto-encoder。另一种划分异常检测模型的标准可以理 解为局部算法 (local) 和全局算法 (global), 这种划分方法是考虑到异常点的特性。想要了解更多异常检测还是推荐看经典教科书Outlier Analysis [6], 或者综述文章[15]。

虽然一直有新的算法被提出, 但因为需要采用无监督学习, 且我们对数据分布的有限了解, 模型选 择往往还是采用试错法, 因此快速迭代地尝试大量的算法就是一个必经之路。在这个回答下, 我们 会对比多种算法的预测能力、运算开销及模型特点。如无特别说明，本文中的图片、代码均来自于 开源Python异常检测工具库Pyod。文中实验所使用的17个数据集均来自于 (ODDS - Outlier Detection DataSets) 。

参考文献

  • 「异常检测」开源工具库推荐 - 微调的文章 - 知乎 https://zhuanlan.zhihu.com/p/37132428

  • 数据挖掘中常见的「异常检测」算法有哪些？ - 微调的回答 - 知乎 https://www.zhihu.com/question/280696035/answer/417091151

  • 不得不推荐这门课：CS259D: Data Mining for Cyber Security 虽然是网络安全方面的应用，但是方法都是通用的，看来也很有启发。https://leotsui.gitbooks.io/cs259d-notes-cn/content/

  • 中科院在读美女博士带你全面了解“异常检测”领域 - 王晋东不在家的文章 - 知乎 https://zhuanlan.zhihu.com/p/260651151

  • Python 时间序列异常检测 ADTK：https://blog.csdn.net/BF02jgtRS00XKtCx/article/details/115343456

  • awesome-TS-anomaly-detection：https://github.com/rob-med/awesome-TS-anomaly-detection