一篇关于时间序列异常检测的论文

异常值是指一个时间序列观测值中，原来序列一般水平的极端大值和极端小值，有时称为离群点或野值。 用SAS软件运行上述程序，可以从图形中直观看到是异常值。 修正方法一： 如果X_(t+1)是一个异常值，我们可以用^X_(t)来修正X_(t+1),即 ^X_(t)=2X_(t)-X_(t-1) 这里我们用2*代替

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

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