异常检测论文综述

一、基本概念 异常对象被称作离群点。异常检测也称偏差检测和例外挖掘。 常见的异常成因：数据来源于不同的类（异常对象来自于一个与大多数数据对象源（类）不同的源（类）的思想），自然变异，以及数据测量或收集误差。 异常检测的方法： （1）基于模型的技术：首先建立一个数据模型，异常是那些同模型不能完美拟合的对象；如果模型是簇的集合，则异常是不显著属于任何簇的对象；在使用回归模型时，异常是相对远离预测值的对象。 （2）基于邻近度的技术：通常可以在对象之间定义邻近性度量，异常对象是那些远离其他对象的对象。 （3）基于密度的技术：仅当一个点的局部密度显著低于它的大部分近邻时才将其分类为离群点。二、异常点检测的方法 1、统计方法检测离群点 统计学方法是基于模型的方法，即为数据创建一个模型，并且根据对象拟合模型的情况来评估它们。大部分用于离群点检测的统计学方法都是构建一个概率分布模型，并考虑对象有多大可能符合该模型。离群点的概率定义：离群点是一个对象，关于数据的概率分布模型，它具有低概率。这种情况的前提是必须知道数据集服从什么分布，如果估计错误就造成了重尾分布。异常检测的混合模型方法：对于异常检测，数据用两个分布的混合模型建模，一个分布为普通数据，而另一个为离群点。 聚类和异常检测目标都是估计分布的参数，以最大化数据的总似然（概率）。聚类时，使用EM算法估计每个概率分布的参数。然而，这里提供的异常检测技术使用一种更简单的方法。初始时将所有对象放入普通对象集，而异常对象集为空。然后，用一个迭代过程将对象从普通集转移到异常集，只要该转移能提高数据的总似然（其实等价于把在正常对象的分布下具有低概率的对象分类为离群点）。（假设异常对象属于均匀分布）。异常对象由这样一些对象组成，这些对象在均匀分布下比在正常分布下具有显著较高的概率。 优缺点：（1）有坚实的统计学理论基础，当存在充分的数据和所用的检验类型的知识时，这些检验可能非常有效；（2）对于多元数据，可用的选择少一些，并且对于高维数据，这些检测可能性很差。 2、基于邻近度的离群点检测。 一个对象是异常的，如果它远离大部分点。这种方法比统计学方法更一般、更容易使用，因为确定数据集的有意义的邻近性度量比确定它的统计分布更容易。一个对象的离群点得分由到它的k-最近邻的距离给定。离群点得分对k的取值高度敏感。如果k太小（例如1），则少量的邻近离群点可能导致较低的离群点得分；如果k太大，则点数少于k的簇中所有的对象可能都成了离群点。为了使该方案对于k的选取更具有鲁棒性，可以使用k个最近邻的平均距离。 优缺点：（1）简单；（2）缺点：基于邻近度的方法需要O(m^2)时间，大数据集不适用；（3）该方法对参数的选择也是敏感的；（4）不能处理具有不同密度区域的数据集，因为它使用全局阈值，不能考虑这种密度的变化。 3、基于密度的离群点检测。 从基于密度的观点来说，离群点是在低密度区域中的对象。一个对象的离群点得分是该对象周围密度的逆。基于密度的离群点检测与基于邻近度的离群点检测密切相关，因为密度通常用邻近度定义。一种常用的定义密度的方法是，定义密度为到k个最近邻的平均距离的倒数。如果该距离小，则密度高，反之亦然。另一种密度定义是使用DBSCAN聚类算法使用的密度定义，即一个对象周围的密度等于该对象指定距离d内对象的个数。需要小心的选择d，如果d太小，则许多正常点可能具有低密度，从而具有高离群点得分。如果d太大，则许多离群点可能具有与正常点类似的密度（和离群点得分）。使用任何密度定义检测离群点具有与基于邻近度的离群点方案类似的特点和局限性。特殊地，当数据包含不同密度的区域时，它们不能正确的识别离群点。 为了正确的识别这种数据集中的离群点，我们需要与对象邻域相关的密度概念，也就是定义相对密度。常见的有两种方法：（1）使用基于SNN密度的聚类算法使用的方法；（2）用点x的密度与它的最近邻y的平均密度之比作为相对密度。使用相对密度的离群点检测（局部离群点要素LOF技术）：首先，对于指定的近邻个数（k），基于对象的最近邻计算对象的密度density(x,k) ，由此计算每个对象的离群点得分；然后，计算点的邻近平均密度，并使用它们计算点的平均相对密度。这个量指示x是否在比它的近邻更稠密或更稀疏的邻域内，并取作x的离群点得分（这个是建立在上面的离群点得分基础上的）。 优缺点： （1）给出了对象是离群点的定量度量，并且即使数据具有不同的区域也能够很好的处理； （2）与基于距离的方法一样，这些方法必然具有O(m2)的时间复杂度。对于低维数据使用特定的数据结构可以达到O(mlogm)； （3）参数选择是困难的。虽然LOF算法通过观察不同的k值，然后取得最大离群点得分来处理该问题，但是，仍然需要选择这些值的上下界。 4、基于聚类的技术 一种利用聚类检测离群点的方法是丢弃远离其他簇的小簇。这个方法可以和其他任何聚类技术一起使用，但是需要最小簇大小和小簇与其他簇之间距离的阈值。这种方案对簇个数的选择高度敏感。使用这个方案很难将离群点得分附加到对象上。一种更系统的方法，首先聚类所有对象，然后评估对象属于簇的程度（离群点得分）（基于原型的聚类可用离中心点的距离来评估，对具有目标函数的聚类技术该得分反映删除对象后目标函数的改进（这个可能是计算密集的））。基于聚类的离群点：一个对象是基于聚类的离群点，如果该对象不强属于任何簇。离群点对初始聚类的影响：如果通过聚类检测离群点，则由于离群点影响聚类，存在一个问题：结构是否有效。为了处理该问题，可以使用如下方法：对象聚类，删除离群点，对象再次聚类（这个不能保证产生最优结果）。还有一种更复杂的方法：取一组不能很好的拟合任何簇的特殊对象，这组对象代表潜在的离群点。随着聚类过程的进展，簇在变化。不再强属于任何簇的对象被添加到潜在的离群点集合；而当前在该集合中的对象被测试，如果它现在强属于一个簇，就可以将它从潜在的离群点集合中移除。聚类过程结束时还留在该集合中的点被分类为离群点（这种方法也不能保证产生最优解，甚至不比前面的简单算法好，在使用相对距离计算离群点得分时，这个问题特别严重）。 对象是否被认为是离群点可能依赖于簇的个数（如k很大时的噪声簇）。该问题也没有简单的答案。一种策略是对于不同的簇个数重复该分析。另一种方法是找出大量小簇，其想法是（1）较小的簇倾向于更加凝聚，（2）如果存在大量小簇时一个对象是离群点，则它多半是一个真正的离群点。不利的一面是一组离群点可能形成小簇而逃避检测。 优缺点： （1）基于线性和接近线性复杂度（k均值）的聚类技术来发现离群点可能是高度有效的； （2）簇的定义通常是离群点的补，因此可能同时发现簇和离群点； （3） 产生的离群点集和它们的得分可能非常依赖所用的簇的个数和数据中离群点的存在性； （4）聚类算法产生的簇的质量对该算法产生的离群点的质量影响非常大。新颖性和离群值检测 离群值检测：训练数据包含离群值，即与其他观测值相距甚远的观测值。离群检测估计器会尝试拟合训练数据最集中的区域，忽略异常观察。 新颖性检测：训练数据不受异常值的污染，有兴趣检测新观察值是否是异常值。该情况下离群值也称为新颖性。 离群值检测和新颖性检测均用于异常检测，离群值检测称为无监督异常检测，新颖性检测称为半监督异常检测。离群值检测的情况下，离群值/异常不能形成密集的群集，可假设离群值/异常位于低密度区域；新颖性检测的情况下，只要新颖性/异常位于训练数据的低密度区域，就可以形成密集的簇。 通过对玩具数据集进行异常检测比较异常检测算法 数据集中包含一种或两种模式（高密度区域），以说明算法处理多模式数据的能力。 对于每个数据集，将生成15%的样本作为随机均匀噪声。该比例是OneClassSVM的nu参数和其他异常值检测算法的污染参数提供的值。离群值之间的决策边界以黑色显示，但是LOF除外，因为当采用LOF用于离群值检测时，没有适用于新数据的预测方法。 OneClassSVM对异常值敏感，对异常值检测执行的不好。当训练集不受异常值污染时，此估计器最适合新颖性检测。即不适用在高维中进行离群值检测或者不对基础数据的分布进行任何假设，OneClassSVM在这些情况下可能会根据其超参数给出有用的结果。 covariance EllipticEnvelope（协方差椭圆密度）假定数据是高斯分布并学习一个椭圆。在数据不是单峰时，会退化。此估计器对异常值具有鲁棒性。 IsolationFrorest和LocalOutlierFactor针对多模式数据集效果显著。LOF针对第三种数据集，明显优于其它三种估计器，该数据集中两种模式的密度不同。LOF的局部方面，即它仅将一个样本的异常评分与其邻居评分作比较，从何体现了该方法的优势。 针对最后一个均匀分布在超立方体中的数据集，很难说一个样本比另一个样本异常得多。除了OneClassSVM有些过拟合外，所有估计器都针对该情况提出不错的解决方案。针对这种情况，应该仔细观察样本的异常分数，性能好的估算器应该为所有样本分配相似的分数。 使用局部离群因子（LOF）进行离群值检测 LOF算法是一种无监督的异常检测方法，可计算给定数据点相对于其邻居的局部密度偏差。其中密度远低于其邻居的样本为异常值。 LOF算法的优势在于同时考虑了数据集的局部和全局属性：即使在异常样本具有不同底层密度的数据集中，仍能保持良好性能。问题不在于样本有多孤立，而在于样本相对于周围邻域有多孤立。 通常考虑的邻居数量（1）大于群集必须包含的最小样本数量，以便其他样本可以是相对于该群集的局部离散值；（2）小于可能是局部异常值的最大进距采样数，此类消息通常不可用，采用n_neighbors=20。 具有局部异常值的新颖性检验 LOF是一种无监督的异常检测方法，可计算给定数据点相对于其邻居的局部密度偏差，密度远低于其邻居的样本为异常值。LOF用于新颖性检验时，切勿在训练集上使用预测、决定函数、实例得分，会导致结果错误。只能对新的看不见的数据（不在训练集中）使用这些方法。 通常考虑邻居数量（1）大于群集必须包含的最小样本数，以便其他样本可以是相对于该群集的局部离群值；（2）小于可能是局部异常值的最大进距采样数，此类消息通常不可用，采用n_neighbors=20。 隔离林 在高维数据集中执行异常检测的一种有效方法是使用随机森林，分离的观察通过随机选择一个函数，随机选择所选择的特征的最大值和最小值之间的分割值。递归分区可用树结构表示，隔离样本所需的拆分数量等于从根节点到终止结点的路径长度。随机树的森林中的平均路径长度是对正态性和决策函数的度量。随机分区产生的异常路径明显较短，因此如果随机树森林为特定样本生成的较短路径，则该树代表的值很可能是异常的。 OneClassSVM 无监督的离群值检测，支持高维分布，基于libsvm 不假定数据分布的任何参数形式，可以更好的对数据的复杂形状进行建模，能够捕获真实的数据结构，难点在于调整核函数宽度参数，以便在数据散布矩阵的形状和数据过度拟合的风险间取得折中。 协方差椭圆密度 用于检测高斯分布数据集中的异常值的对象 经验协方差估计（作为非稳健估计）受到观测值异质结构的高度影响；鲁棒协方差估计能够集中于数据分布的主要模式，但是它坚持假设数据是高斯分布，产生了对数据结构的某些估计，在一定程度上是准确的。HBOS单维效果极佳，但是标准差方法的mask 掩码效应严重。例如 数据通常在100以内，但是有两个异常点，500，1000000。这个算法就不能检出500这个异常点。 对比而言，孤立森林理论上更适合大数据的异常检测，且无掩码效应。孤立森林确定异常时训练只用样本数据。每颗树样本数量默认只有256个，默认只用100颗树。所以理论上25600个样本就能确定海量数据中的异常点了。 Sklearn的 isolation forest 例子默认是读入全量数据再采样。如果配上warm up 选项就能分批放入采样。 异常检测的深度学习研究综述

动态图上的异常检测任务包括：发现异常的对象、关系、时点。动态图上的异常检测与静态图上的异常检测不同的地方在于：

本文首先将异常类型分为：anomalous vertices, edges, subgraphs, and events(or change)，将使用的方法分为：community detection, MDL(minimum description length) and compression, decompression, distance, probabilistic， 按每种方法使用的异常类型进行了文献学分类。各方法的主要参考文献见表1：

本文假设不同时点的节点和边都有唯一标签从而不会混淆，定义 为图序列，其中 为总时间步， ， 为节点集， 为边集， 时称 为图流。本文的主要记号见表2：

给定 ，节点集 ,打分函数 ，定义异常节点集为 ，使得对于 ， ，其中 为得分 的摘要式统计。

一个典型的异常节点如图1，其可由基于社区检测的方法识别，即： 其中 为节点所属的社会划分, 为异或操作。

给定 ，边集 ,打分函数 ，定义异常边集为 ，使得对于 ， ，其中 为得分 的摘要式统计。

一个典型的异常边如图2，可令 ，其中 为时间步 时 的权重,可以为边的概率。

给定 ，子图集 ,打分函数 ，定义异常集为 ，使得对于 ， ，其中 为得分 的摘要式统计。

两种典型的异常子图如图3,其中(a)为图的收缩，(b)为图的分裂。图的收缩可根据子图中的的数量衡量，即 ，图的分裂可由不同时间点社区的数量衡量。

与异常节点、边、子图检测不同，异常事件或异常突变检测检验的是时点。

给定 ,打分函数 ，若时点 满足: ， ，则称时点 为一个事件。

给定 ,打分函数 ，若时点 满足: ， ，则称时点 为一个突变。

通常的异常检测都使用两步法：第一步，基于特征的图表示；第二，基于机器学习的异常检测。

基于社区检测的方法关注的是社区和关联节点的演化过程，特征向量的生成亦基于图中的社区结构。不同社区检测方法的区别在于：（1）社区结构的领域，如社区内的连接性.单个节点在每一步所属的社区；(2)社区结构的定义，如基于概率的软社区定义.硬社区定义。基于社区检测的方法可用于异常定点、子图、突变的检测。

基于软社区匹配并单独考察每一个社区，我们可以在连续时间步内计算每个节点归属的平均变化，如果某个节点归属的平均变化显著异于其他节点，则称其为演化社区异常点。

节点社区归属的变化可以构造一个时间模式，称为软时序模式。一些文献使用了最小描述长度(MDL)结合非负矩阵分解的方法来自动检测节点角色及构造转移模型。多数文献通过抽取图中不同节点的共同模式，并比较每个节点与共同模式之间的差异来定义异常节点。部分文献使用了交替迭代优化替代常用的两步法。部分文献使用了corenet的概念，该概念不同于单纯使用density,modularity,hop-distance等概念，而是使用了节点间的加权路径，即一个节点的corenet包含该节点与权重大于给定阈值的两跳邻居。假设两个强连接的节点通常属于同一社区，则如果移除一个节点的两个邻居，一个邻域具有较高的边权重，另一个具有较低的边权重，则移除较高权重邻居的影响应更大，在每一步，每个节点首先被赋予一个异常得分，该得分衡量了其corenet的变化，异常得分较高的 各节点将被视为异常节点。

文献【69】定义了六种基于社区的异常：shrink, grow, merge, split, born, and vanish。其使用图和社区代表(representatives)进行比较以减少计算量，图代表为出现在t时刻，同时还出现在t-1、t+1或t+1与t-1时刻的节点集，社区代表是出现在其他社区最少的定点集合，基于社区代表和图代表，基于规则，判断社区是否落在六种异常中。

文献【73】定义了一种基于社区的异常：comet，周期性出现或消失的社区，演化图可表示为一个张量，然后基于低秩张量分解和MDL原则进行comet检测。

文献【3】基于多种信息源构造时序复网络，识别跨时间和网络的稳定社区结构。行为相似的网络可以用聚类或前验知识分组，如何一个社区结构在组内跨时间步稳定，但在组外没有对应社区，则该社区即为异常，如何两个社区共享一定比例的定点则称为对应。

社交网络可以根据特定时间窗口内的发文量定义事件，一个经历共同事件的组即构成一个异常子图。

通过划分图流为一致的分割来检测，分割是依据划分的相似性。

通过将最新图的顶点分区与当前增长分割中的图的分区进行比较，可以在线找到这些分割。【67】基于可返回随机的相关矩阵和modularity最大化来进行定点划分，当新图的划分与当前分割的划分有很大不同时，一个新段开始，并将新图的时间点输出为检测到的突变。两个划分的相似度使用Jaccard系数定义。GraphScope思路类似，但基于MDL来指导划分和分割。

基于MDL原则和基于该原则的压缩技术利用数据中的模式和规律性实现紧凑的图表示，其主要通过将图的邻接矩阵表示为一个二进制串，如果矩阵的行和列可以重新排列使矩阵的二进制字符串表示的熵最小化，那么压缩损失（也称为编码损失）就会最小化。数据指向的特征都来自于图或其特定子结构的编码代价；因此，异常被定义为抑制可压缩性的图或子结构（如边）

对于一条边和对应子图，如果包含该边的编码损失比不包含该边的编码损失高，则称该边为异常边。

【74】使用了一种两步交替迭代法进行节点的自动划分，当节点划分的熵收敛时，根据包含和不包含该边的编码损失，该方法也给出了边的异常度得分。

突变检测的主要思路是:连续时间步间的图是相似的，因而可以分为一组，从而降低压缩比。压缩比的上升表明新一个时间步的图与已有的图差异明显，因此是一个突变。

该方法将图集合表示为一个tensor，在该tensor上进行矩阵分解或降维，基于分解或降维后的图发现其模式和规律性，该方法可以融合更多属性信息，最常用的方法是SVD和PARAFAC（广义SVD）。

矩阵分解可用于计算每个节点的活跃（activity)向量，如果某个节点的活跃向量在连续时间步间变化明显，则称为异常节点。

【87】首先抽取每个节点的边相关矩阵 ，即该节点的每个邻域都有一行一列，对于节点 的矩阵中的一个entry 代表了边 和 间加权频率的相关性，加权频率由衰减函数获得，时间越近权重越高。M的最大特征值和对应特征向量即顶点的活跃向量的summary及边的相关性。通过寻找这些值的变化而形成的时间序列用于计算每个时间步长中每个顶点的分数，得分高于阈值的顶点将被输出为异常。

基于分解的异常事件检测有两种方法：（1）先基于分解方法来近似原始数据，然后以重建损失作为近似优劣的指标。如果某个子张量、切片或元素的重建损失很高，则即可以视其与周围数据不同特征不同，将其标记为异常事件、子图或节点。（2）跟踪奇异值和向量，以及特征值和特征向量，以检测异常顶点的显著变化。

为解决 intermediate blowup 问题（即计算中输入和输出张量超过内存限制），【81】提出了momery-efficient tucker（MET）分解方法，该方法源于Tucker分解，Tucker分解将高阶tensor用一个core tensor和每个mode(维度)矩阵表示。【80】使用了Compact Matrix Decomposition(CMD)，其可以用来计算给定矩阵的稀疏低秩矩阵。使用CMD对图流中的每个邻接矩阵进行分解，可得到重建值的时间序列，基于重建值序列可进程事件检测，典型应用有COLIBRI, PARCUBE，其中后者在斑点(spotting)异常中的表现更高效。

【84】使用了随机图模型进行基于概率模型的检测，其将真实图邻接矩阵和期望图的邻接矩阵间的差异构造为残差矩阵，对残差矩阵执行SVD，再使用线性Ramp滤波器，基于top奇异值即可进行异常时间窗口检测，通过检查正确的奇异向量来确定相应的顶点。

除以上方法，我们还可以基于分解空间的显著变化来识别事件。【77】通过对数据执行PCA，计算的特征向量可以分为正常和异常两个集合，方法是检验数据中的值映射到特征向量。在每个时间步，根据特征值对特征向量进程降序排列，第一个特征向量则包含一个在其余值的3个标准差之外的投影点，此后的每个特征向量，都构成了异常集。第二步即是将数据映射到正常和异常子空间，一旦完成了这些操作，当从上一个时间步长到当前时间步异常成分的修改超过一个阈值时，即将其视为一个事件。【83】扩展了该方法，提出了联合稀疏PCA和图引导的联合稀疏PCA来定位异常和识别对应的顶点。通过为异常集使用稀疏的成分集，可以更容易识别负责的顶点。顶点根据它们在异常子空间中对应行的值得到一个异常分数，由于异常分量是稀疏的，不异常的顶点得分为0。

图的活跃向量 为主成分，左奇异向量对应最大奇异值，奇异值和奇异向量通过对加权邻接矩阵进行SVD得到。当活跃向量大幅异于“正常活跃"向量时，即定义该时点为突变点，”正常活跃“向量由前序向量得到。

正常活跃向量 ，它是对最后W时间步中活动向量形成的矩阵进行SVD得到的左奇异向量。每个时点都定义一个得分 ,其代表了当前活跃向量与正常向量的差异。异常可以使用动态阈值方案在线发现，其中得分高于阈值的时间点被输出为变化。通过计算正常向量和活动向量之间的变化比率来找到负责的顶点，与变化最大的索引所对应的顶点被标记为异常，类似的方法也可以用于节点-节点相关矩阵的活跃向量，或基于邻居相似度的节点-节点相关矩阵。

基于距离的异常检测算法的不同点在于选择用于提取和比较距离度量，以及它们用于确定异常值和相应图的方法。

如果一些边的属性演化异于正常演化，则该边就是一个异常边。

边之间的权重使用衰减函数定义，在每个时间步长中，根据相似度得分的变化之和计算每条边的异常值得分，使用阈值或简单的 作为异常值标准。

将网络视为边的流，意味着网络没有固定的拓扑，一个边的频率和持久性可以用来作为其新颖性的指标，【48】定义了集合系统不一致性指标来度量频率和持久性，当一条边到达时，计算其差异，并与活动边集的平均不一致性值进行比较，如果边的加权不一致性大于平均不一致性的阈值水平，则声明该边为异常边，基于异常边，可以进一步识别其他异常图元素（如顶点，边，子图）。

具有许多“异常”边的子图即是异常的子图。

【52】将边的权重视为异常得分，每个时间步长上的每条边都有它自己的异常分数，给定了该边权值在所有图序列的分布，该分数表示在该特定的边上看到该特定权值的概率函数。或者，为网络中的边分配异常值分数的现有方法的输出可以用作为该方法的输入。后一种方法允许应用于任何能够为边分配异常值分数的网络，一旦完成每条边的异常打分，即可发现显著异常的区域（SARs），即一个窗口内的固定子图，其类似于HDSs。【112】提出了一种迭代算法，该算法首先固定子图发现最优时间窗口，然后固定时间窗口发现最优子图。【97】拓展了该方法，允许子图渐变，即在相邻时间步间增加或移除顶点。

定义函数 为测度图距离的函数，将其应用于连续图序列，即得到距离序列，基于该距离序列应用一些启发式算法（如基于移动平均阈值的 取值）即可得到异常事件。

称每个顶点及其egonet的特征为局部特征，整张图的特征为全局特征。每个顶点的局部特征可聚合为一个向量，基于该向量的各阶矩可构造signature向量，利用signature向量间的Canberra距离（归一化的曼哈顿距离）可构造图之间的距离函数【93】。【92】利用全局特征，定义了一种基于dK-2序列的距离测度，将高于阈值的特征视为异常点。

【96】使用了顶点亲和度（即一个顶点对另一个顶点的影响，可以用于快速信念传播）得分作为signature向量，其基于连续时间步技术顶点亲和度，基于马氏距离度量两个图的相似度，亲和度得分的变化反应并适应变化的影响水平，例如桥边的移除比正常边移除的得分更高。利用单个移动范围的质量控制，可以对相似度得分的时间序列设置一个移动阈值，如指数移动平均加权。

作为特征相似度的补充，我们也可以比较两个图的结构差异来度量突变的大小，这类方法致力于发现定义距离的函数而非发现特征向量。【88】计算了异常网络的10种距离函数，使用ARMA模型构造特征值的正常模型，然后基于正常模型计算时点的残差，残差超过给定阈值的时间即可标记为异常。10种距离函数中，基于最大共有子图的方法表现最好。【90】使用了五中得分函数（顶点/边重叠，顶点排序，向量相似度，序列相似度，signature相似度）来检测三种异常（子图缺失，顶点缺失，连通性变化），表现最好的方案是抽取每个顶点和边的特征构造signature向量，使用SimHash定义距离。

我们还可以通过计算每个图的稳健性序列来检测事件，稳健性序列是图连通性的测度，具有高稳健性的图即使在去除一些顶点或边的情况下，也能保持相同的一般结构和连通性，事件检测即发现稳健性值异常变化的时点【95】。【89】使用的是图半径的变体作为稳健性指标，图半径的定义是基于所有顶点的平均离心度，而非常用的最大离心度。

基于概率理论、分布、扫描统计学等方法可以构造“正常”样本的模型，偏离该模型的样本即视为异常，这类方法的主要区别在于构造方法、建模对象、离群值定义。

主要有两种方法：一，构造扫描统计时间序列并检测离均值若干标准差的点；二，顶点分类。

扫描统计常称为滑动窗口分析，其在数据的特征区域中发现测度统计量的局部最小或最大值。对某个特定图，扫描统计量可以是图不变特征的最大值，如边的数量。

【8】使用了一个适应测度统计量的变量，即每个节点的0-2度邻居数，然后对每个顶点的局部统计量使用近期值的均值和标准差进行标准化，图的扫描统计量即最大的标准化局部统计量。标准化可以解释每个顶点的历史信息，代表每个顶点的统计量只与自己的历史信息有关而与其他顶点无关。这保证测度的最大变化与变化的绝对量无关而与比例有关。基于扫描统计量标准化时间序列，将序列均值的五个标准差作为异常值。最负责的顶点被确定为为整个图的扫描统计值所选择的顶点。

类似于使用邻居进行扫描统计，我们还可以用Markov随机场（MRF）来发现节点的状态，并通过信念传播算法推断最大似然分配，其中，每个顶点标签取决于其邻居节点。【99】通过发现二部核来检测异常点（即犯），二部核定义为犯与从犯间的交互。利用边的插入或删除只影响局部子图这一事实，它在添加新边时逐步更新模型。在传播矩阵中，一个顶点可以处于三种状态之一：欺诈者、共犯者或诚实者。

边异常检测通常使用计数过程建模，统计上显著异于该模型的边标记为异常边。

【50】用贝叶斯离散时间计数过程来建模顶点间的通信次数（边权重），并根据新图更新模型。基于学习到的计数的分布，对新观测的边进行预测 值计算，基于 值标记异常顶点对。

首先用固定的子图，多重图，累积图来构造预期行为的模型，对模型的偏离可作为子图异常检测的依据。

【104】结合扫描统计量和隐马尔可夫模型（HMM）建模边行为，其使用的局部扫描统计量是基于两种图形状：k-path图和星型图，其将滑动窗口的扫描统计数据与其过去的值进行比较，并使用在线阈值系统识别局部异常，局部异常是所有统计上显著的子图(代表k个路径或恒星)的并集。

另一个建模动态图的方法是基于多重图，其中平行边对应于两个连续时间步顶点间的通信，初始的多重图可分解为多个针对每个时间窗口的叠套子图（TSG），TSG满足两个条件：（1）对于任何两个有共同点的边，首先开始通信的边最后完成通信；（2）存在一个根顶点r，它没有传入的边，并且有一条到TSG中每个顶点的路径。出现概率低的TSG视为异常子图。【102】

累积图即为包含直到当前时点的所有边的图，边权重依据衰减函数定义，通过识别“持久模式”来定义子图的正常行为。该持久模型识别模型如下：首先构造一种图，该图每个边根据时间来加权，然后基于该图迭代抽取最重连接成分来发现。随着累积图的发展，提取的子图将被监控，并将其当前活动与基于最近行为的预期活动进行比较来进行子图异常检测。【101】

事件检测可以基于偏离图似然模型或特征值分布的偏差来进行。

【103】提出了一种新的蓄水池抽样方法来抽取图流的结构摘要，这种在线抽样方法维持多个网络划分以构造统计上显著的摘要，当一个新图进入图流，每个边都根据不同分区的边生成模型计算出一种似然性，然后以这些似然性的几何均值作为全局图似然性。

【98】使用了类似的边生成模型，每个边 的概率都存储在矩阵 中，概率基于期望最大化估计，基于所有收发对的分布，然后为每个收发对给出潜在得分，基于所有边似然得分的均值即得到每个图的得分。

【100】计算了特征值和压缩特征等式的分布（而非计算收发对的分布），基于每个顶点都存在一个顶点局部特征时间序列的假设，可在每个时间步构造一个顶点-顶点相关矩阵，通过保留最大特征值和一组低维矩阵（每个顶点对应一个矩阵），可对相关矩阵的特征方程进行压缩，通过学习特征值和矩阵的分布，即可发现异常顶点和事件。当特征值偏离期望分布时，即认为发生了事件，当顶点的矩阵偏离矩阵分布时，可认为该顶点为异常顶点。

Generalized Out-of-Distribution Detection: A Survey Jingkang Yang, Kaiyang Zhou, Yixuan Li, and Ziwei Liu

分布外（Out-Of-Distribution，OOD）检测对确保机器学习系统的可靠性和安全性至关重要。例如，在自动驾驶中，当遇到它从未见过、无法给出安全决策的非常规情形或物体，我们需要驾驶系统发出警告并且将控制权交给人类。自2017年被提出起，这个问题越来越受研究者关注，各种解决方案层出不穷，大致包括：基于分类的、基于密度的、基于重构的、基于距离的方法。与此同时，其他几个问题在动机和方法上与分布外检测紧密相关，这些问题包括：异常检测（Anomaly Detection，AD）、新类检测（Novelty Detection）、开集识别（Open Set Recognition，OSR）和离群检测（Outlier Detection，OD）。尽管他们各自定义和问题设定不同，这些问题经常使读者和实践者感到困惑，这导致有些现有工作误用了这些术语。实际上，AD、ND、OSR、OOD、OD这五个问题能够统一在广义的分布外检测框架下，都可以视作分布外检测的特例或子任务，并且能够轻易地被区分。这篇综述通过总结最新的技术发展对这五个问题做了深入的回顾，并以该领域的开放挑战和潜在的研究方向作结。

可信的视觉识别系统不仅仅在已知的情境下能给出精确预测，还应该能检测到未知的样本并且丢弃或将它们交给用户来做安全地处理。

比如，一个训练良好的食物分类器应该丢弃像用户自拍照之类的非食物图片，而不是胡乱判定其属于某已知的食物类别。在安全要求极高的应用中，比如无人驾驶，系统应该在它碰到不寻常的、未在训练中见到的情形或物体时发出警告并将控制权交给司机。

大多数现有机器学习模型都基于封闭世界假设（the closed-world assumption）来训练，即测试集和训练集独立同分布，或者说两者来源于同一分布（in-distribution）。然而，当模型被部署在开放世界场景（open-world scenario）中，测试样本的分布可以是取自不同于训练集分布的分布的（out of distribution），因而需要被谨慎处理。分布的变化可能是语义漂移（比如，OOD样本取自别的类别）、协变量漂移（也称输入漂移，比如OOD样本取自其他领域？？）。

只考虑语义漂移和协变量漂移两类漂移。

异常检测目的在于在测试阶段检测异常的样本，“异常”指的是偏离预定义的“正常”。这种偏离可能是协变量漂移或是语义漂移导致的。异常检测可以分为两个子任务：

与异常检测的区别 ：1） 动机上，新类检测中并不像异常检测把没见过的“新”样本看做错误的或是有害的，而是将珍视这些新样本为后续模型的学习资源；2）新类检测首要关注的是语义漂移；3）新类检测中，没有限制ID样本属于单个类，在训练集中可以有多个类别的样本。

新类检测目的在于检测出不属于任何训练类别的测试样本。检测到的新奇样本通常预备用于未来程序的构建，比如特异性更强的分析、当前模型的增量学习等。依据训练类别数量的差异，新类检测分为：

OSR需要一个多类别分类器来同时1）精确地分类 训练类别的 测试样本（ID）；2）识别出测试样本中 不属于训练类别 的样本（OOD）。

OSR = multi-class ND

需要模型拒绝标签迁移的样本以保证预测可靠性和安全性

分布外检测目的在于检测测试样本

当某个样本显著区别于其他的样本时，认为它是“离群”的。在异常检测、新类检测、开集识别、分布外检测的问题设定中，都存在这训练-测试的流程，要挑出测试中出现的不属于训练分布的样本。

而离群检测无“训练分布”、“测试分布”，而是直接挑出所有可见样本中显著区别于其他的那些样本。

给定同构的ID数据，最直接的方法是1）基于密度的方法，这些方法估计ID的密度，拒绝那些偏离估计的OOD的测试样本。其他的方法包括：2）依靠图片重构的质量来识别异常样本，3）直接学习一个决策边界来区分ID和OOD样本，4）基于距离的方法，5）基于元学习的方法

基于密度的方法尝试去建模正常数据（ID数据）的分布，这种做法基于一个实践假设：异常的测试样本在估计的密度模型下游较低的概率值，而正常样本概率值较高。

参数密度估计假设ID样本的密度能够被表示为某种定义好的分布。一种方法是在训练数据上拟合一个多变量高斯分布，并且度量测试样本与训练样本的期望之间的马氏距离（协方差距离，计算两个未知样本集的相似度的方法。与欧氏距离不同的是它考虑到各种特性之间的联系）。其他的工作采用了更复杂的假设，认为训练分布是混合的高斯分布或是泊松分布等。

非参数密度估计考虑了更贴合实际的情形：预定义的分布不能够建模真实分布。可以简单地用直方图对训练分布进行建模。核密度估计（KDE）进一步使用核函数作为离散直方图的连续替代版，它可以灵活地使用点权重和带宽去控制估计的分布。

虽然经典的密度估计方法在很多任务上获得了很好的AD性能，但它们更适合低维任务。 对于计算机视觉任务中的高维数据，这些方法的计算性和可伸缩性受到影响。为缓解维数灾难，有些方法通过特征工程降维[277]，[278]。

通过由潜在嵌入重建出输入，自编码器能学到无标签数据的高效表达。变分自编码器将输入的图片编码为服从高斯分布的潜在向量。习得的潜在嵌入可被视为输入的低维表示。传统密度估计方法可以应用在这些深度表示之上。

生成对抗网络由一个生成网络和一个判别网络构成，两者在零和博弈中相互竞争。典型地，生成网络学习从潜在空间到所研究数据分布的映射，而判别网络试图分辨生成器生成的数据和真实数据。然而，不同于基于自编码器/变分自编码器的范式，少了一个编码器使得GAN难以直接为一张输入图片找到相应的嵌入。针对这个问题，ADGAN [90] 对一个给定的样本，在潜在空间搜索一个好的表示。如果找不到这样的表示，这个样本被认为是异常的。该方法计算代价极高。

规范化的流描述了一个概率分布经过一系列可逆映射的转化过程。通过重复施加变量变化的规则，初始的密度“流”过了一系列可逆映射。因此，使用规范化的流的方法能够直接估计输入空间的可能性。基于流的方法有优雅的数学表示，但是它们同样仅对低维特征敏感。若不进行降维，基于流的方法计算代价高。

除通过生成式模型获取可视化嵌入外，一些方法主要通过扩充模型容量来增加提取到的特征的表示能力，这或许可以让正常（ID）能被更精确地特征化为密度估计。这些策略包括数据增强，对抗训练，蒸馏，损失函数增强，使用浅表/局部特征。

基于能量的方法使用一个标量能量评分来表述变量概率密度，这个标量采用非标准化的负对数概率，

然而，和标准的深度学习模型相比，训练基于能量的方法代价昂贵，因为马尔可夫链蒙特卡罗法（MCMC，在概率空间，通过随机采样估算兴趣参数的后验分布）采样和估计需要积分运算。

为解决这个难题，研究者提出了评分匹配方法和随机梯度之类的方法来支持高效训练。

现有工作也探索了使用频域分析方法做异常检测。人类通过图片的低频信息来理解图片，而CNN更多依赖高频信息来做决策。人们提出了CNN核平滑和谱引导的数据增强之类的方法去抑制高频分量的影响。还有一些工作发现，对低频分量的对抗攻击也很难被检测到，因此提出

基于频率的方法专注于感官异常检测（尤其是检测对抗样本），或许不适用于语义异常检测。

基于重构的方法的核心在于在ID数据上训练得到的编解码器（encoder-decoder）框架通常对ID和OOD样本返回不同的效果。

模型表现的差异可以被用作异常检测的指标。模型表现的差异可以用特征空间的差异或是重构误差来度量。

系数重构假定每个正常样本都能被有限个基础函数精确重构，而异常数据的重构开销则更大，因此生成了稠密表示。稀疏表示的典型技巧包括基于L1正则的核PCA和低阶嵌入网络。

重构误差方法依赖于以下假设：在正常数据上训练得到的重构模型在输入为正常测试样本时会输出更高质量的结果。深度重构模型（包括自编码器AE、变分自编码器VAE、生成对抗网络GAN和U-Net等）都能够被用作这类方法的backbone。

除去这种结合AE/VAE和重构误差这种标准做法，其他方法使用了更加精细的策略，比如通过memorized normality重构，调整模型架构、部分/有条件的重构。

在半监督设定下的异常检测中，CoRA分别在ID样本和OOD样本上训练，得到两个自编码器。这两个自编码器的重构误差被用作异常检测的指标。

GAN中的判别器本质上是 通过计算重构误差 实现异常检测。更进一步，GAN的变种，比如去噪声的GAN和类别-条件GAN通过 增加重构难度 获得了更好的性能。有些方法 利用重构图片在下游任务中的表现来进一步放大异常样本的重构误差 。集成也能够优化模型性能。

异常检测、单类别的新类检测通常被形式化为无监督学习问题，将所有的ID样本看做一类。

【283】做了完全有监督的异常检测

半监督的异常检测中，模型训练时用到了无标签数据。

PU学习针对这个问题被提出

自监督方法

单个类别分类直接学到一个决策边界

未完成

共性：ID样本的类别（训练类别）为多个。

差异：开集识别还需要精确地给ID样本分类，而新类检测只需得到区分ID/OOD的二分类器。

由于开集识别和多类别新类检测的训练类别为多个，大多数方法都是基于分类的。其余方法包括基于ID原型的以及基于重构的。极少数模型是基于密度的。

为了解决

开集识别和多类新类检测都关注ID样本包含多个类别的情形。分类问题中，一般采用独热编码来编码类别信息。然而，独热编码忽略了类别间的内在联系。举例来说，“狗”-“猫”，“狗”-“车”之间有相同的距离显然不合情理。有些工作考虑这一点，尝试利用新类的标签空间上的信息来解决这个新类检测问题。重分配大的语义空间，形成已知类别的层次化分类

基于标签组织重设，自上而下的分类策略和分组softmax训练被证实有效。应一组工作使用词向量嵌入来自动地构建标签空间。【169】中稀疏独热标签被几组产生自不同NLP模型的稠密词向量替代，形成了多个回归头来做鲁棒的训练。

测试时，标签（同所有不同头给出的嵌入向量距离最小的标签被作为预测结果输出，

如果这个最小距离超出阈值，这个样本被分类为“新”。近期工作进一步采用语言-图片预训练模型输出的特征来更好地检测新类，图片编码空间中也包含来自标签空间的丰富特征。）

基于距离的开集识别方法需要“原型”来实现class-conditional。维持ID样本的分类性能。

基于类别的聚类和原型（prototyping）操作在分类器提取到的视觉特征上进行。

OOD样本能够通过计算样本与聚类之间的距离而被识别。

有些方法还引入了对比学习来为已知类别学到更加紧密的聚类，从而拉远ID和OOD样本之间的距离。

CROSR【177】通过拼接分类器和用于距离计算的重构模型给出的可视化嵌入来在拓展的特征空间中得到强化的特征。除了使用分类器给出的特征，GMVAE【178】使用重构VAE来提取特征，将训练集的嵌入建模为一个多中心的混合高斯分布以便后续基于距离的操作。使用最近邻的分类器也适用于开集识别问题。通过存储训练样本，最近邻距离比值被用于在测试中识别未知样本。

基于重构的方法希望ID和OOD样本被重构时表现不同。这种差异能够在潜在特征空间或重构图片的像素空间中被捕捉到。

通过将已知类别的图片转化为稀疏表示，开集样本由于相对稠密能被识别出。用于稀疏编码的技巧包括：疏密指数（sparsity concentration index）【180】和核虚空间方法（kernel null space method）【181，182】。

通过固定在ID样本训练得到的多分类视觉编码器来维持在ID样本上的分类性能，C2AE训练一个以表情按向量为条件的解码器，使用极值理论估计重构后的图片来区分未知类别。后续的工作使用条件高斯分布，使得不同潜在特征逼近类内（class-wise）高斯模型，以达到在分类已知类别样本的同时能拒绝未知类别样本。其他方法生成反事实（counterfactual）图片来帮助模型更关注语义。对抗防御【186】也以这种思路去增强模型鲁棒性。

后处理检测的方法优点在于无需修改训练程序和目标就可以轻易应用。这一点对现实生产环境中的OOD检测方法很重要。早期的ODIN是一个使用temperature scaling和输入扰动来放大ID/OOD差别的后处理方法。该方法中，一个足够大的temperature有很强的平滑作用，能够将softmax值转换到logit空间（），从而有效区分ID和OOD样本。注意这种方式与信心校准不同，它采用了更温和的T

而校准更关注表达ID样本真实的正确概率

ODIN的评分最大化了ID和OOD样本之间的差异，可能从预测信心的角度看不再有意义。

基于这个见解，近期【189】提出使用能量分值来做OOD检测，该方法不需要超参数并且性能与ODIN相当甚至更好。能量函数将logit输出通过便捷的 logsumexp 运算符映射为标量。能量值相对低的测试样本被认为是ID的，反之为OOD。

【55】进一步提出了联合能量值（JointEnergy score）

为OOD检测定制的基于信心的方法能够通过设计信心估计分支和类别数据增强（结合leaving-out留一策略、对抗训练、更强的数据增强、不确定性建模、利用理想深度的特征）来实现。

特别地，为了增强对协变量偏移的敏感性，一些方法关注神经网络中间层的隐藏表示。泛化的ODIN通过使用DeConf-C作为训练目标来扩展ODIN，选择ID数据上的扰动尺度作为超参。

由于ODIN需要模型训练过程，它未被归类到后处理方法。

为了得到质量更优的隐藏层特征以便进行密度估计，分层的 Mahalanobis距离、 Gram Matrix等技巧被引入。

OOD检测的另一分支利用收集到的OOD样本集（离群样本集），在训练中帮助模型学到ID和OOD的差异。

总的来说，采用离群点暴露的OOD检测能达到明显更优的性能。然而，其性能受给定OOD样本和真实OOD样本间相关性强弱影响明显，如何将OOD由已经暴露的OOD泛化到更广泛的OOD还需进一步探索。

离群点暴露方法依赖于OOD训练数据可获取这一强假设，该条件在实际可能不成立。在OOD数据不可获取时，一些方法尝试去合成OOD样本从而让ID和OOD可区分。现有工作利用GAN来生成OOD训练样本并使模型输出均匀（uniform 正态？？？）的预测，从而在低密度区域生成边界样本，或者类似地，生成高置信度的OOD样本。

现有的OOD检测方法主要依赖输出或特征空间来给出OOD评分，而忽视了梯度空间的信息。ODIN【188】首次探索了使用梯度信息检测OOD。ODIN使用经过预处理的输入，其预处理为施加由输入梯度得来的细微扰动。ODIN扰动的目标在于增强模型对预测标签的信心从而增加任何给定输入的softmax值。最终，可以找到能使ID和OOD输入的softmax评分差异更大的扰动，从而使得它们更能被区分，使得OOD检测性能更好。ODIN仅隐式地通过扰动来利用梯度。GradNorm则使用梯度向量的范数，从softmax输出和正态概率分布的KL散度反向传播。

贝叶斯模型是一类统计模型，应用贝叶斯法则来推测模型中所有的不确定性。其中，最有代表性的是贝叶斯神经网络，该方法通过马尔可夫链蒙特卡洛方法、拉普拉斯方法、变分推断来构成模型的认知不确定性，从模型的后验分布中采样。它们最明显的缺陷在于预测不精确，计算代价高使得它们难以用于实际。近期工作尝试了几种less principled（理论性较弱??）的近似，包括 MC-dropout [224] 和深度融合 [225]，299] 用于更快、更好地估计不确定性。这些方法在OOD不确定性估计上不太有竞争力。更进一步的探索需要在保留贝叶斯原理的优势的同时，采用自然梯度变分推理，从而能够采用实用且可负担的现代深度学习训练。狄利克雷先验网络Dirichlet Prior Network (DPN) 也在OOD检测中被运用，使用对模型不确定性、数据不确定性以及分布不确定性三个不同来源的不确定性进行不确定性建模，出现了一系列工作 [227], [228], [229]。

近期工作推进了更贴近实际应用的大规模OOD检测。研究的两个方向是：将OOD检测扩展到大的语义空间、利用大型的预训练模型。例如，【168】指出，在基于CIFAR benchmark数据得到的方法在语义空间更大的benchmark ImageNet上并不奏效，这强调了在大型真实设定下评估OOD检测的必要性。为解决上述挑战，MOS的关键理念是将大的语义空间解构为有相似概念的更小的群组，这简化了已知和未知数据之间的决策边界。强有力的预训练模型在各种任务、模态都达到了惊人的性能。同期的工作 [171], [230], [231] 证实预训练过的transformer在特定的困难的OOD任务上性能显著改善。

OOD检测领域中，基于密度的方法用一些概率模型显式地建模分布内数据，并将低密度区域的测试数据标记为OOD。即使OOD检测在分布内数据为多类别的情形下和异常检测不同，节中的密度估计方法能够通过将分布内数据统一成一个整体而直接适用于OOD检测。当分布内含多个类别时，class-conditional高斯分布能够显式地建模分布内数据，因而分布外样本能够根据输出的预测概率而被识别【207】。基于流的方法 [92], [232], [233], [234]也可被用于概率建模。直接估计OOD概率似乎是一种自然的解决方法，也有一些方法 [235], [236], [237] 通过给OOD样本输出更高的概率预测值来实现OOD检测。【238】尝试使用likelihood ratio来解决这个问题。【239】发现，对输入复杂度，概率值存在明显偏差，提出了一种基于概率值比例的方法来削减输入复杂度的影响。近期的方法转而使用新的评分，例如likelihood regret【240】或是集成多个密度模型【236】。整体上，生成式模型的训练和优化难度几乎是不可接受的，它们的性能也往往落后于基于分类的方法（）

基于距离的方法基本理念在于，测试中OOD样本应当相对远离分布内类别的中心（centroid）或原型（prototype）。【207】使用相对所有类别中心的最小Mahalanobis距离来检测。一个后续工作【241】将图片分为前景和背景，再计算这两个空间间的Mahalanobis距离比例。一些工作使用测试样本特征和类别特征间的余弦相似度来确定OOD样本【242】、【243】。被训练特征的的第一奇异向量一维的子空间

更进一步，其他工作利用了径向基函数核距离（distance with radial basis function kernel）、输入的嵌入向量到类别中心的欧拉距离。

OOD检测领域自出现以来发展迅速，其解决方案从基于分类的、基于密度的、再到基于距离的。在多类别设定下，典型的OOD检测是开集识别问题（第4节），在类别空间Y中精确分类分布内的测试样本，并且丢弃语义不被Y所支持的分布外样本。然而，OOD检测包含了更广泛的学习任务（比如，多标签分类）和解法（比如，密度估计和离群点暴露）。一些方法放宽了开集检测的限制条件，并且达到了更强的性能。

离群检测需要所有样本可见，其目标是检测出那些显著偏离大多数的分布的样本。离群检测方法通常是转导式的，而不是归纳式的。 [13], [14], [15], [16]综述主要回顾了数据挖掘领域的离群检测方法。以下主要回顾离群检测方法，尤其是为计算机视觉设计的使用深度神经网络的方法。即使深度学习方法极少能直接解决离群检测问题，数据清洗程序（从开集脏数据学习的先决条件）和开集半监督学习的方法也在解决离群检测问题。

离群检测模型的基本理念是将整个数据集建模为一个高斯分布，将偏离均值超过三杯标准差的样本标记为离群【300】【301】。其他带参数的概率方法利用Mahalanobis距离[266] 和高斯混合模型 [302]来建模数据密度。和“三倍标准偏离”规则类似，四分位距也可通过构建传统的无参数概率模型来检测离群样本【247】。为了鲁棒和简化，局部离群因子（local outlier factor）方法【248】借助给定点的邻居和它自身局部可达性的比值，去估计给定点的密度。RANSAC【252】迭代地估计数学模型的参数来拟合数据并且找到对估计贡献较少的样本作为离群点。

总体上，经典的异常检测的密度方法比如，核密度估计（节），也可应用于离群检测。即便这些方法由于图片数据维度太高而应用困难，也可以通过降维方法【253,254】和基于最近邻的密度方法(节)来缓解。

检测离群的一个简易方法是计数某特定半径内的邻居数量，或者度量第k近邻居的距离【303,304】。以下主要介绍基于聚类的方法和基于图的方法。

DBSCAN【255】依照基于距离的密度来积聚样本构成聚类。处在主要聚类之外的样本被识别为离群样本。后续工作通过考虑聚类标签的信心改良了聚类的方式【256】。

另一类方法利用数据点之间的关系，并构造邻域图[305], [306]（或其变体[307]），利用图的属性和图挖掘技巧来找到异常的样本【257，258】，比如图聚类[259], [260]、图分割【308】、使用图神经网络的标签传播【261】。