论文阅读_异常检测综述
英文题目：Anomaly Detection: A Survey
中文题目：异常检测综述
论文地址：https://readpaper.com/paper/2122646361
领域：异常检测
发表时间：2009
作者：VARUN CHANDOLA 等，明尼苏达大学
出处：ACM Computing Surveys
被引量：11797（谷歌学术）
1 读后感
一篇典型的综述文章，快速了解异常检测的定义，用途，方法……发表时间比较早，是机器学习异常检测方法的总结。正文 50 多页，比较长。
2 介绍
文章根据方法对异常检测分类，对于每个类别，提供一个基本的异常检测技术，然后展示该类别中新技术与基本技术的差异，此类技术的优缺点及计算复杂度。
异常一般包含：异常 (anomalies)、离群点 (outliers)、不一致的观察结果 (discordant observations)、特例 (exceptions)、畸变 (aberrations)、意外 (surprises)、特性 (peculiarity) 或污染 (contaminants)。其中又以异常和离群点最为常见。
异常检测的应用领域包含：信用卡、医疗保险的欺诈检测，网络安全的入侵检测，关键系统的故障检测，监视敌人军事活动等。异常检测用于识别这些问题，并做出对应的行动。
2.1 何为异常
异常检测是指在数据中发现不符合预期行为的模式。比如图 -1 中的 o1,o2,o3 不在正常的区域 N1,N2 内，它们都是异常点：
异常检测与去噪 (noise removal) 和噪声调和 (noise accommodation) 关注的问题相似，但目标不同。去噪是想从数据中去掉异常数据，噪声调和是让模型更健壮，对异常免疫；而异常检测所感兴趣的是识别出异常数据。另外，与之相似的还有新颖点检测 (novelty detection)，它的目标是检测出之前数据中未被发现的模型。
2.2 挑战
异常检测的目标是检测不属于正常区域的数据，它面临如下挑战：
- 正常范围包含每种正常行为，很难定义，且正常异常之间的边界也不好精确划分。
- 恶意攻击时，异常行为常常将自己表现得像正常行为。
- 在不断发现的领域，当前的正常行为，未必能满足未来的需要。
- 由于数据分布不同，同一技术不一定能直接应用另一领域的异常检测。
- 没有足够的打标签数据。
- 数据中包含噪声常常与异常值相似，噪声难以识别和消除。
常用的异常检测方法包括：统计方法，机器学习，数据挖掘，信息理论，光谱理论等且需要将它们应用于不同领域，如图 -2 所示：
2.3 相关工作
此处对比了本文和另外一些综述性文章和书籍，如下表所示，其中序号 1 表示本文：
2.4 本文贡献
之前文章大多讨论单个领域的异常检测，文章讨论了异常检测在各个领域的应用。文中主要讨论了常用的 6 种技术（在第 4-9 部分详述），针对每种技术提出了基本方法，改良方法，优缺点，计算复杂度等；列出了每个应用领域中所应用的技术列表；另外，还区分了简单异常和复杂的异常（与上下文相关或集体异常）。
2.5 文章组织方式
文章组织方式如图 -2 所示分成三块：
第 2 部分介绍了异常检测的输入输出分类等各个方面的丰富和复杂性；第 3 部分介绍了不同领域的异常检测；第 4-9 部分介绍了具体的几种建模技术；第 10-11 介绍了上下文异常和集体异常检测；第 12-13 部分是总结展望和结束语。
3 异常检测的各个方面
3.1 输入数据
一般数据可能包括：对象，记录，点，向量，模式，事件，案例，样本，观察结果，实体等等。每个实例可能包含一个或多个特征，特征又分：布尔型，类别型及连续型。
数据需要与检测方式匹配，比如假设检验对不同数据类型使用不同方法；最近邻方法需要特征间的距离是可以度量的；数据还可以根据相似度进行分类；数据实例之间还可能存在线性排序关系，比如时间，空间序列，基因组序列，蛋白质序列等。
3.2 异常的类型
异常一般分为以下三类：
3.2.1 点异常
这是最简单的情况，如果一个点与其它点不同，则为点异常，比如图 -1 中的 o1,o2。
3.2.2 上下文异常
上下文异常也叫条件异常，实例一般包含两组特征：
- 上下文特征：用于描述实例上下文（邻居）的情况，比如空间中经度纬度邻近的特征，时间序列中之前之后时间的特征等。
- 行为特征：用于描述与上下文无关的主体本身的特征。
由于上下文的差异，同样的行为有时被认定为正常，比如图 -3 中的 t1 点，而 t2 点被认为异常。
3.2.3 集体异常
数据是否异常取决于相关数据实例的集合，如图 -4 中的心电图数据：
这里的 1000-1500 中的多个实例组合被识别成了集体的异常。集体异常也常常出现在时间序列，空间序列，图片数据检测中。
3.3 给数据打标签
给训练集中的每个实例打标签：是/否为异常数据，常需要专家进行标注，人工标注代价比较高；通常需要获得各种类型的异常实例，比获得正常实例困难得多；数据常常动态变化，新的异常不断出现；另外很多数据非常少，难以获取，比如空难数据。
由于上述问题异常标注分为三种模式：
3.3.1 有监督的异常检测
有监督异常检测需要对全部训练集进行标注，检测方法通常是建立预测模型，这与一般预测模型相似，文中不详细讨论。它有两个主要问题：第一个问题是异常数据相对正常数据一般很少，这造成了数据偏斜，增加了建模难度；第二个问题是获取准确和有代表性的异常标签常常具有挑战性，因此，也有人提出了一些技术向数据集中注入人工异常数据。
3.3.2 半监督的异常检测
只标注训练数据中的正常实例，由于不需要异常类别的标签，因此它们比监督技术更适用，比如飞行器发生异常就是重大事故，也就是说训练数据中可能不包含各种类型的异常数据。常用方法是为正常行为建模，并使用该模型来识别测试数据中的异常。
3.3.3 无监督的异常检测
不需要训练数据，用途更广泛。它背后的假设是正常实例比异常实例多很多，如果不满足这个假设，则会产生大量误报警。
3.4 异常检测的输出
典型的输出一般包含两种类型：
3.4.1 打分
为测试集中每个实例计算异常评分，它取决于该实例的异常程度。有些模型输出异常度排序列表；分析人员通过设定阈值来判定是否为异常。
3.4.2 打标签
为每个测试集中实例打标签：是/否异常。
4 异常检测的应用
（本部分每小节都包含具体方法相关的论文列表，数据太多，请见原文）
对于每种应用场景从四方面讨论：
- 异常的概念
- 数据的性质
- 面对的挑战
- 检测方法
4.1 入侵检测
入侵检测针对计算系统的恶意行为。
面对的挑战是数据量大，需要高效的异常检测，常常需要处理数据流，另外还需要防止大量误报警。
数据难以标注，主要使用半监督和无监督方法。
入侵一般分为主机入侵和网络入侵。
4.1.1 基于主机的入侵
针对基于主机的入侵，主要使用根据系统调用的方法；入侵包含未经授权的行为和违反规则，事件共发是检测异常的关键因素，另外可以在不同层级（程序级、用户级）分析数据。一般情况下，使用序列数据建模，对点建模也比较少。
4.1.2 基于网络的入侵
常见的异常是点异常，也有集合异常的情况，攻击一般由黑客发起，通过获得未经授权的访问网络的权限，目的是窃取信息或破坏网络。检测系统针对不同粒度的数据检测。另外面临的挑战还包括黑客不断变换攻击行为，以逃避被识别。
4.2 欺诈检测
欺诈检测是指对银行、信用卡公司、保险公司、手机公司、股票市场等商业组织中的犯罪活动进行侦查，以避免经济损失。下面介绍一些具体应用：
4.2.1 信用卡欺诈
检测欺诈性信用卡申请或信用卡盗用，检测信用卡申请类似于检测保险欺诈。
数据通常由多个维度定义的记录组成，如用户 ID、消费金额、连续使用卡片的间隔时间等。欺诈通常反映在交易记录中 (点异常)。
信用公司有完整的数据，也有标记记录。
基于概要分析和聚类的技术通常用于该领域。
挑战是它需要即时在线检测，一种方法是使用当前数据与该用户的历史数据比较，该方法需要频繁访问数据库；另一种方法通过检测地理位置，都可归于检测上下文异常的方法。
4.2.2 手机电话欺诈
手机欺诈检测是典型的活动监控问题。任务是扫描大量的帐户，检查每个帐户的呼叫行为，并在帐户似乎被滥用时发出警报。
可以按时间聚合，或按用户或区域进行聚合。这些异常现象包含大量的呼叫或呼叫不可达的目的地。
4.2.3 保险索赔欺诈
该域中的可用数据为索赔人提交的文件，从这些文档中提取不同的特征。人工调查的案例被监督和半监督技术作为标记实例用于保险欺诈检测。保险索赔欺诈检测通常是作为一个通用的活动监控问题处理的，也使用基于神经网络的技术。
4.2.4 内幕交易检测
内幕交易发生在股票交易市场中，即信息公开前利用内部信息非法获利。常 通过识别异常的交易活动来识别，数据源包含：如期权交易数据，股票交易数据，新闻。数据有连续关联。挑战是需要以在线方式尽早发现欺诈行为。
4.3 医学与公共卫生异常检测
医疗和公共卫生领域的异常，包含患者状况异常或仪器错误或记录错误，疾病爆发等。该领域检测对精度要求很高。数据通常由记录组成，这些记录可能包含几种不同类型的特征。主要针对异常记录（点异常）检测，可用的数据常属于健康患者，因此常用半监督学习；其中还包含一些时序数据如心/脑电图，使用集体异常检测。
4.4 工业设备损伤检测
主要指尽早发现工业设备的损坏。数据常常为各种不同传感器的记录数据，又细分为以下两个领域：
4.4.1 机械设备故障
检测可能是由于磨损或其他不可预见的情况而发生的缺陷。数据常具有时间特征，有时使用时序方法或集体异常检测。相对而言，正常数据更容易获得，因此常用半监督方法。挑战是需要尽快发现异常以采取措施。
4.4.2 结构缺陷
缺陷检测用于如梁的裂缝，机体的应变。数据也常具有时间性质，通过检测数据变化，时间空间相关性来计算。
4.5 图像处理
处理图像的异常检测技术包含：对运动的检测，图像上的异常的区域检测，卫星图像，数字识别，光谱学，分析 x 线影像，和视频监控等。数据具有时空特征。像素点往往有连续的颜色，亮度，纹理等。主要挑战是输入的数据量大，有时需要对视频进行实时处理。
4.6 文本数据异常检测
针对文档或新闻文章中的新主题、事件或新闻检测。异常是由新的事件或异常主题引起的。该领域的数据通常是高维且非常稀疏的。且有时效性，因为文档是随着时间收集的。主要面临的挑战是处理数据随时间大量变化。
4.7 传感器网络
传感器网络指从各种无线传感器收集数据。传感器检测包含故障检测和入侵检测。数据可能包含：二进制、离散、连续、音频、视频等。由于资源的限制，异常检测技术需要实现轻量级化，也可能分布式处理，另外，处理噪声和缺失值也是一个挑战，需要区分 噪声和异常。
4.8 其它领域
异常检测还被用于，语音识别，机器人行为中，流量监控，点击通过保护，检测 web 应用程序中的故障，检测生物数据中的异常，检测人口普查数据中的异常，检测犯罪活动之间的关联，检测客户关系管理 (CRM) 数据中的异常，检测天文数据中的异常和检测生态系统干扰等。
5 基于分类的异常检测
分类方法用于有监督学习，需要有标注的训练集，一般分为训练模型和代入实例测试两个阶段。
该方法基于以下假设：
基于给定特征，可以训练能够区分正常类和异常类的分类器。
分类器进一步又可分为单分类（如图 6-b，主要学习正常和异常的边界）和多分类（如图 6-a，多个正常类别，加一个异常类别），有的模型可以给出置信度得分，如果属于哪一类的置信度都不高，则认为是异常类别。
5.1.1 神经网络分类器
神经网络分类器可用于单分类和多分类。自编码器（Replicator Neural Networks）是 2002 年提出的，它用于实现单分类，它是多层的前馈网络，其输入和输出层元素个数相同，训练阶段将数据通过隐藏层压缩再还原，测试时代入 xi，输出 oi，如果 xi 与 oi 足够相似，则认为正常，否则为异常：
其中 n 是特征个数，误差δi 是用于判断 x 与 o 相似度的得分。
5.1.2 贝叶斯网络
贝叶斯网络一般用于多分类任务，其基本方法是针对单个变量的朴素贝叶斯，后验概率最大的作为类别标签。从训练集中计算类先验和测试数据属于各类的可能性，如果概率为 0，则认为异常。该方法可推广到多元数据集。需要注意的是该方法变量之间是无关的，后来又发展出一些改进方法来解决变量依赖问题。
5.1.3 支持向量机
支持向量机用于单分类任务，用它学习一个包含正例的区域，它的核可以学到对复杂区域的表示。如果测试集实例落入区域则认为正常，否则为异常。其中一种变体是找到包含所有训练数据超球，然后判断测试数据在超球的内外。
5.1.4 基于规则的方法
基于规则的方法用于寻找正例的行为规则，如果测试集不符合任意一条规则，则认为异常。规则方法可用于单分类和多分类任务。
在多分类时，先用训练数据学习规则，如使用决策树，RIPPE 等方法，每个规则都有一个置信度；测试数据找到最匹配的规则，并将其置信度的倒数作为异常得分。
关联规则是一个比较重要的方法，常用于单分类方法，通过无监督的方式从训练数据中挖掘规则，支持度的阈值用于对规则剪枝。He 等 2004 年提出了一种方法，将规则的频繁项集个数作为测试集的异常得分。
计算复杂度
分类方法的复杂度视具体方法不同，一般情况下，决策树方法比较快，包含二次优化的 SVM 相对慢（也有改进优化方法）。由于分类方法会训练出模型，在将测试数据代入模型，而非当场计算，所以预测较快。
优点
- 多分类器可以区分实例所属类别。
- 预测速度快。
缺点
- 往往没那么多标注数据用于训练
- 一般情况下结果为标签的值，不过也有一些算法输出概率。
6 基于最近邻的异常检测
该方法基于如下假设：
正常数据出现在密集的区域中，异常数据与正常数据间隔比较远。
最近邻是基于距离的算法，如何衡量距离也比较重要。对于连续型数据，一般使用欧式距离，对于分类变量常使用匹配系数或更加复杂的方法。对于多维变量，会结合各个维度的结果。最近邻方法一般分为以下两类：
6.1 基于距离的 KNN
实例的异常得分取决于距其最近 K 个实例的距离（或相似度）K 根据情况设置，有时设置为 1。然后使用一个阈值定义正常与否；也可以选择异常得分最高的前几个作为异常；还可以选择不同的方法计算距离以实现优化；另外，提升计算效率也是一个优化的方向。
最基本的方法是对与实例最近的 K 个邻居的距离加和，后来还发展出，计算与实例距离在 d 以内的邻居个数 n，它相当于在实例附近做了一个半径为 d 的超球体，其密度可视 为 n/πd^2，其密度的倒数可视为异常得分，即：它周围邻居越少，越可能异常。
一般数据都是连续型，之后也有一些针对于其它类型变量的优化，比如对类别变量使用超图方法计算；以及结合连续型和分类型的距离计算方法；对于分类属性，两个实例具有相同值的属性的数量定义了它们之间的距离，对于连续属性，维护协方差矩阵以捕获连续值之间的依赖关系。
提升效率的方法，有些方法通过忽略肯定异常或肯定非异常的数据消减搜索空间；基于分区和聚类的减枝方法；以及通过下采样提升效率。为了消减搜索空间，有些算法将搜索空间切分成固定大小的立方体组成的超网格，如果一个立方体中实例较多，则认为正常，否则为异常……
6.2 基于密度的方法
基于密度的方法主要计算实例邻居的密度，密度高则认为正常，否则为异常。一个实例的 k 个最近邻可构成一个超球体，球心为该实例，球里包含 k 个近邻。到第距离第 k 个实例的距离的倒数可被视为密度，即 k 个近邻离它越近，密度越大。
基于密度的基本方法也有些问题，比如图 -7 中，由于 C1 中密度低，因此其中很多点间的距离都大于 p2 到 C2 间的距离，如果以 C1 的密度为标准，则 p2 被视为正常，如果以 C2 为标准，位于 C1 中的实例认为异常。
为解决数据集中密度不同的问题，使密度只与近邻相关，出现很多改进方法，其中使用最多的是 LOF(Local Outlier Factor) 及其变种。LOF 的核心是找到局部密度，LOF 分数等于实例的 k 个最近邻居的平均局部密度与数据实例本身的局部密度之比。之后还有一些方法，对本地密度 (COF)，其它变量类型 (PST)，及效率进行改进。
计算复杂度
最近邻的基本方法需要为每个节点找近邻，O(N^2) 的复杂度，上述方法很多着重提升效率，但各有不同的适用范围。如使用超网络在特征数量大时不适用；抽样技术在样本较少时不适用等。
优点
- 这是一种无监督方法，不对分布进行假设，完全是数据驱动的
- 半监督学习相对于无监督学习在遗漏检测中效果更好。
- 可用于不同类型特征的检测，但需要定义好距离计算方法。
缺点
- 算法基于距离，如果正常实例没有太多邻域，或者异常数据有很多邻居则会无效。
- 如果测试集中的正常数据在训练集中没怎么见过，则假阳率很高。
- 在数据量大的情况下，计算效率是一个严重问题。
- 如何定义距离函数是一个挑战，尤其对于图片，序列等数据。
7 基于聚类的异常检测
聚类是将类似的数据分成不同的簇。聚类是一种针对无监督数据的研究方法，基于聚类的方法一般分为三种
- 第一种方法基于以下假设：
正常数据属于聚类中的某一个簇，异常数据不属于任何簇
这种方法包含：DBSCAN，ROCK，SNN，FindOut 等，这种方法 的问题是它没有对异常数据进行调优。
- 第二种方法基于以下假设：
正常数据离簇心近，异常数据离簇心远
该方法分两步，第一步对训练数据聚类，第二步根据每个实例距离质心的远近计算异常得分，从而在训练集中定位一些异常数据。这种方法包括：SOM，KMeans，EM 等，其中 SOM 应用比较广。该方法也可以用于半监督数据，用标签改进聚类（判断同一类别中的标签的一致程度）。如果异常数据单独成簇，则上述方法不可用，于是提出第三种方法.
- 第三种方法基于以下假设：
正常数据属于大而密集的入簇，异常数据属于小而稀疏的簇
该方法包括：FindCBLOF，CBLOF 获取实例所属的集群的大小，以及数据实例到其集群中心的距离作为得分。还有一些改进聚类效率的方法。
7.1 聚类和 K 近邻的区别
由于聚类大多也是基于计算距离的，所以 K 近邻的一些距离计算方法也可以在聚类中使用。不同的是聚类基于所在的簇进行分析，最近邻基于实例的邻居分析。
计算复杂度
训练的复杂度取决于聚类算法。如果聚类需要计算所有数据实例的成对距离，具有二次复杂度；如果使用基于启发式的技术，如 k-means 或近似聚类技术，则具有线性复杂度。测试阶段速度快，它只涉及测试实例与少量集群进行比较。
优点
- 可以在无监督数据中使用
- 普通的聚类方法也可以处理复杂数据
- 测试实例预测快。
缺点
- 高度依赖聚类算法捕捉正常数据的有效性
- 算法必须满足相应的假设（上述三种假设）
- 计算复杂度高
8 基于统计的异常检测
基于统计的方法基于以下假设：
正常数据出现在随机模型的高概率区域，而异常发生在低概率区域。
模型基于统计方法，判断之前没见过的数据是否属于该模型产生的数据，包含参数方法和非参数方法。
8.1 参数方法
参数方法基于的假设是数据符合基于参数Θ的分布，f (x, Θ) 是概率密度函数，x 是训练集中的观测值，Θ是通过 x 学到的，测试集中的异常分数是 f 的倒数。另外，也可以用假设检验的方法判断 x 是否为异常。基于分布的类型，参数方法又可细分如下：
8.1.1 基于高斯分布
假设数据服从高斯分布，参数通过最大似然估计计算，将 x 与估计均值的距离作为异常得分，然后用阈值判断是否异常。不同的技术使用不同的阈值和距离计算方法。常使用标准差的 3 倍作为阈值，如果服从高斯分布，μ ± 3σ 能包含 99.7% 实例。另外，也常用箱图分位数的方法检测异常值（IQR）。常用分位数的 1.5 倍作为阈值，Q1 − 1.5IQR and Q3 + 1.5IQR 一般包含 99.3% 的实例，QR=Q3-Q1。
格拉布斯检验 (Grubbs Test)，也叫最大归一化残差检验，常用于检测单变量的异常值，对于测试集中的 x 计算其 z 得分：
其中上划线 x 是均值，s 是标准差，当 z 大于以下值时，则认为异常。
其中 N 是数据量，t 是阈值。之后有人把它推广到多变量检测中。
学生 T- 检验也是常用于高斯分布的检测方法（使用前需要先确定数据服从高斯分布），它用于判断训练集和测试集是否属于同一分布。扩展到多变量的 t 检验是 t^2-test。
X^2 统计用于检测系统调用异常，训练阶段假设正态数据具有多元正态分布，X^2 定义如下：
其中 Xi 是观测值，E 是期望值，n 是变量个数，当 X^2 很大时，则认为包含异常数据。
8.1.2 基于回归模型
在时间序列的异常检测中常使用回归方法。一般分为两步，第一步用训练数据训练模型参数，第二步计算测试集数据与模型的残差，通过差异大小判断是否异常。
在回归过程中，异常数据可能影响回归参数，因此提出了稳健回归（Robust regression），通过判断残差的大小，它不仅可以忽略异常，还能定位异常，ARIMA 方法与之类似。基于回归的改进主要包括：对多元时间序列的检测。
8.1.3 基于参数分布的混合
基于参数分布的混合使用参数统计分布来对数据建模。又分为两类：
第一类是分别对正常实例和异常实例建模，在测试阶段分别判断实例是属于正常模型还是异常模型，比如假设正常集和异常集都服从高斯分布，且均值一致，但异常集的标准差更大；还有一些迭代计算的方法。
第二种方法把正常数据视为多种高斯分布的混合，如果测试数据不属于其中任何的高斯分布，则认为它是异常数据。
8.2 非参数方法
模型结构不是由先验定义的，而是由给定数据确定的。这种技术通常对数据做较少的假设。
8.2.1 基于直方图
使用直方图描述正常数据，这种方法也被称为基于计数或频率的技术。它能很好地统计识别入侵和诈骗行为。最简单的单变量检测方法分成两步，首先，使用训练集统计直方图，然后检测测试集中数据是否落入其中，以判别其是否为异常；也利用将其落入柱的高度来计算异常分值的；箱的个数是一个重要超参数。之后有一些改进，对异常值也用直方图描述。
在多变量的情况下，可以对每个属性计算直方图，及异常分值，然后聚合各个分值。
8.2.2 基于核函数
概率密度估计的一种非参数技术，它使用核函数来近似实际密度，类似于前面描述的参数化方法，区别是使用的密度估计技术。另外，还可用半监督统计技术来检测异常，该技术使用核函数来估计正常实例的概率分布函数，位于低概率区域的一个实例被视为异常。
计算复杂度
基于统计技术的复杂视具体方法不同，拟合单参数分布，计算高斯、泊松、多项式等，常在数据大小和属性数量上是线性的。使用期望最大化 (EM) 等迭代方法，每次迭代通常也是线性的，收敛可能较慢。基于内核的技术具有与数据大小相关的二次型时间复杂度。
优点
- 当数据满足分布的假设时，统计技术是很好的方案。
- 异常评分与置信区间相关，在进行决策时，可以将其作为附加信息。
- 如果方法对数据中的异常是稳健（容错）的，则可使用无监督数据训练模型。
缺点
- 使用上述方法前需要先验证数据是否满足对应假设，而现实中的数据大多是不满足的高维数据。
- 为复杂分布构造假设检验，选择检验方法难度大。
- 基于直方图的方法难以处理多维数据，数据可能在单个维度上是高频的，但组合后低频异常。
9 基于信息理论异常检测
信息理论技术利用复杂度、熵、相对熵等来分析数据集的信息内容。
该方法基于以下假设：
异常数据会导致数据集的信息内容不正常。
设 D 是数据集，C(D) 是它的复杂度，求取最小的子集 I，使得 C(D)-C(D-I) 取得最大值，也就是说去掉混乱的数据 I，它可能没有单一的最优解。主要的技术在于如何选用不同的 C 来衡量复杂性。
上述方法一方面需要考虑子集的大小，一方面需要考虑复杂性，它需要对每种子集运行指数时间，后续提出了一些技术对最反常子集进行搜索。如局部搜索算法 (LSA)，以及使用信息瓶颈度量技术。
该技术常被用于序列，空间，图数据的异常检测，数据被切分成小块，此技术用于检测各个小块是否异常。
计算复杂度
基本的信息论方法是指数时间复杂度，有的优化方法可以提供具有线性时间复杂度的近似技术。
优点
- 可以处理无监督数据。
- 不需要满足条件假设。
缺点
- 高度依赖于计算复杂方法的选择。通常，只有当数据中存在大量异常时，这种方法才能检测到异常的存在。
- 对序列或空间操作时，需要切分数据，而切分的大小很难确定。
- 难以给异常值打分。
10 基于频谱的异常检测
基于频谱的异常检测利用特征组合捕捉数据的规律。
它基于以下假设：
数据降维后，正常和异常的实体表现出更明显的不同
将数据通过嵌入或者投影方法转换后，异常数据更容易被识别，该技术可用于半监督或无监督学习。
其中主成份分析 PCA 是一种典型方法，转换后满足规律的正常实例的投影值较低，而偏离规律的异常实例的投影值较大，从而实现异常检测。
在时序图的异常检测中，提出通过邻接矩阵的矩阵分解 (CMD) 得到与原始图近似的矩阵，并重建时间序列，然后在序列中检测异常。
另外还有稳健 PCA（robust PCA），主成份通过正常数据的协方差矩阵得到；在预测阶段，根据转换后点到主分量的距离来判断是否为异常值。对比映射后的 y 值与特征值的比λ值：
它类似于统计方法中计算实例与样本均值的马氏距离。
计算复杂度
基于 PCA 的技术对数据量是线性的，但对于维度是二次数。奇异值分解的技术通常对数据量为二次的。
优点
- 一种降维方法，因此适用于处理高维数据，另外，它可以作为数据预处理，然后再使用其它异常检测技术。
- 可用于无监督数据。
缺点
- 只在正常异常数据在低维可分的情况下使用
- 计算复杂度高
11 处理上下文异常
之前讨论的都是基于单点的异常检测，本节讨论基于上下文的异常检测。它首先需要定义上下文，特征一般也分为上下文特征和行为特征两部分。上下文可以定义为：
- 空间：一般定义实例位置，然后以从空间领域中提取特征。
- 图：这里指的是图结构，结点由边相连，可从邻居（有边相连的节点）提取特征。
- 序列：数据是顺序的，并已知实例在序列中的位置，其中时序数据得到广泛研究，另外，带时间戳的事件是一种连续时间不均匀的事件。
- 概况：通常情况下，数据可能没有显式的空间或顺序结构，但仍然可以使用一组上下文属性将数据分割或聚集到组中。然后分析用户在其组内的异常情况。
处理方法分为以下两类：
11.1 简化成点异常检测问题
上下文异常是指实例点在上下文的条件下异常，其根本也是对点的判断，也可将上下文视作为特征。检测一般分两步：第一步把上下文转换成特征，第二步使用点异常检测方法。
假设特征文可拆分成上下文特征 U 和 行为特征 V（点本身的特征），因此学习在 U 条件下 V：p(Vj|Ui)，异常得分计算如下：
具体使用时，比如欺诈检测，将用户和时间作为上下文特征，其它特征作为行为特征，利用规则比较，以检测异常。另外，可先用标签分割数据，然后再用聚类检测异常。
对于空间数据，使用位置坐标可以直接检测出领域，然后使用统计方法检测领域内的异常（局部异常）。
对于时间序列，将观测值与领域值的中位数相比较；还可将时间序列转换到特征空间中，然后使用单点的异常检测方法。
11.2 利用数据中的结构
有些情况下，无法简单划分上下文和行为，比如对于时间序列和事件序列，常使用序列模型的扩展来识别异常。
一般先用训练数据建模以预测上下文中的行为，如果行为和预期明显不符，则认为异常，回归是一种常用方法。
对于时序数据，很多基于回归的技术如：robust regression, auto-regressive, ARMA, ARIMR, Support Vector Regression 等。
一种检测字母序列中单个异常的技术。将序列分为两部分，分别计算其柯尔莫戈罗夫复杂度。复杂程度高的包含异常。序列被递归地分割，直到它们只剩下一个事件，该事件被声明为序列中的异常。
还有一种方法，用前前 N 个时点预测下一个时点的行为，如果预测不正确则视为异常。这种方法被扩展到：频繁项集挖掘，有限状态自动机，马尔可夫链蒙特卡罗，它们用历史数据预测后续事件发生的概率。
P2P 网络中的二部图结构被用来首先识别图中任何节点的邻域，然后检测该节点在邻域内的相关性。相关性评分低的节点被视为异常节点。作者还提出了一种近似技术，首将图划分为不重叠的子图,然后在其分区内计算节点的邻域。
计算复杂度
对于简化成点异常的方法，其训练阶段复杂度取决于具体检测技术，切分技术相对较快，聚类或混合模型估计的技术相对较慢。测试阶段计算相对昂贵。
对于利用数据结构的方法，训练阶段相对较慢，但测试阶段较快。
优点
认为数据实例在一个上下文中往往是相似的（自然定义）。这种技术能够检测到从全局角度检测异常（点异常检测技术不行）。
缺点
只适用于可以定义上下文的情况。
12 处理集体异常
但一组实例同时发生则为异常，而其中的单独发生时可能是正常的，它相对于前两种更复杂是因为它需要探索数据结构中的异常区域。主要是识别实例间的关系，关系又包含：
- 序列异常检测技术：典型的数据集包括事件序列数据，或数值型时间序列数据。
- 空间异常检测技术：处理空间数据，识别数据中的连接子区域是否异常（如图片）。
- 图异常检测技术：处理图数据，识别数据中的连接子图是否异常。
12.1 序列异常检测
序列的异常检测与时间和位置相关，又可分成两类，一类是序列由信号组成，另一类是连续的，如时间序列。另外，序列可以是单变量，也可以是多变量的。
12.1.1 在序列集中检测异常序列
这种方法常用于无监督数据或半监督数据。其挑战是序列不定长，测试数据无法与训练数据对齐，比如事件队列中第一个事件，刚好是另一队列的第三个事件。解决方案有以下两种：
把序列数据转换成点数据后再处理
对于定长序列，将长度为 10 的序列转换成 10 个属性向量，然后使用点异常检测技术来检测异常（如神经网络或聚类）。
对于不定长序列，则把不定长的数据转换成定长的记录，比如用分箱的方式，把序列元素放入箱，把每个箱作为一个特征，然后代入模型（计算欧式距离及 RIPPER 方法）。
还有方法直接计算不等长串之间的距。例如：计算最长公共子序列的长度作为似度量，然后后再使用聚类等异常检测技术。
给序列建模
上面方法主要用于对齐的序列，但对于事件序列，生物序列，不能使用。序列建模主要用于半监督学习，因此，需要训练数据。序列建模的主旨是根据序列建立规则，比如基于时间的归纳学习，测试集数据与所有规则对比，当无法匹配任意规则时视为异常。其中有限状态自动机（FSA）和马尔可夫序列模型最为流行。进而发展出隐马尔可夫模型，概率后缀树 (PST)PST 是变阶马尔可夫链的紧表示，稀疏马尔可夫树 (SMT)。再将 HMM 序列集进行聚类，并将不属于任何聚类的任何序列检测为异常。
12.1.2 检测长序列中的异常子序列
将序列中与其余部分不一致的部分识别为异常子序列。它检测长序列中的区域异常，常用于无监督学习，它背后的假设是正常部分有可识别的模式，而异常数据不适合这一模式，主要面临的挑战是：不能确定异常串的长度；当输入数据包含异常时，难以对正常模式建模。
有一种方法使用香农的经典信息定理，先切分长序列，然后对各段编码，其中编码需要最高比特数的段被视为异常。
相似的方法还有：利用窗口比较的算法，使用滑动窗口从给定的连续观察序列中提取子序列。使用基于压缩的不相似度量将每个子序列与整个序列进行比较。每个子序列的异常值是它与整个序列的不相似度。
还有方法，使用滑动窗口从给定序列中提取子序列，然后计算每个子序列到原始序列中最接近的非重叠子序列的距离。子序列的异常值与它与最近邻居的距离成正比。
还有最大熵马尔可夫模型，即条件随机场，预测最可能的状态序列。观测序列中的任何异常段对于任何状态序列都具有较低的条件概率。
12.1.3 期望频率异常
判断某一模式出现的频率是否异常，它检测的是在测试集中出现的频率是否与训练集中出现的频率一致。比如：使用滑动窗口从给定的字母字符串中提取子字符串，他们确定子字符串相对于正常数据集中是否异常，使用后缀树（或 HMM）来估计它与正常数据中字符串的预期频率的差异。
12.2 空间异常检测
目标是检测子图或子组件的异常。比如检测图片中的某一部分与其余部分的差异（上下文异常），使用多元高斯随机马尔可夫场来分割图片，与之前方法不同的是它使用了空间结构。
具体方法如：自底向上的子图枚举技术，分析给定图中子图的频率，以确定它是否异常（子图的大小也要考虑在内，因为大的子图必然很少出现在图中）；也有些方法测量子图的规律性或熵，与上下文相比，以确定其异常值。
13 异常检测技术的相对优缺点
对于不同问题，需要使用不同的异常检测技术
图 -10(a) 中所示正常数据呈高斯分布，异常数据稀疏且远离正常分布，且是有监督数据。第 4-9 节的方法都可以使用。
图 -10(b) 中数据由多个高斯分布组成，且方差很低，由于它们均匀地分布在一个圆上，如果使用单类建模，可能识别圆外是异常区域，从而无法识别圆中的异常，使用聚类方法识别不同的类，基于多类分类的技术可能能够了解每个聚类周围的边界，或者利用最近邻方法，都可能检测到中心的异常。
如图 -10(c) 的情况，聚类或最近邻也难以识别。
聚类和最近邻，难以识别高维异常；频谱技术通过将数据映射到低维投影，可解决高维问题，前提是数据降维后仍有区别。
最好的情况是正负例都有标签，但很难实现，即使有标签，又难以对不均衡数据建模。对于只有正例标签的半监督数据或无监督数据，聚类可能更为有效。
统计技术只在数据的维数较低和统计假设成立的情况下才有效。
信息理论技术需要一种足够灵敏的测量方法，否则只能在异常数量显著足够多的情况下才能检测到异常。
聚类和最近邻是基于距离的算法，因此需要找到适合的距离度量方法。
时间复杂度也是个重要的问题，基于分类、基于聚类和统计技术的训练时间很长，但预测通常很快。相比之下，基于最近邻的技术、信息论和光谱技术没有训练阶段，预测时间长，实际使用中可能受到限制。
异常检测技术通常假设，与正常实例相比，数据中的异常非常罕见。但也有例外，比如蠕虫爆发。
14 结束语和今后的工作
当前的异常检测没有定义具体的异常是什么，主要是依赖结构判定。因此也无法使用统一的量度来对比不同的方法。未来上下文和集体异常检测技术在将发现越来越多的适用性；分布式位置的数据的存在促进了对分布式异常检测技术的需求；随着传感器网络的出现，也需要检测更具实时及在线检测技术，及增量地更新模型；在复杂的系统中异常检测涉及到建模不同组件之间的相互作用。
核心：建立模型，把其中少量没法建模的视为和其它不同的”异常“。