时序数据异常检测论文

这是一篇发表于2015年SIGMODE数据管理国际顶会的论文，它主要针对时序数据的聚类问题，提出了K-Shape方法。与以往的方法相比，它优化了距离计算方法，质心计算方法，还引入了提取频域特征方法，以提升效率。 作者认为它是一种独立于领域、高精度、高效率的时间序列聚类方法。 我觉得相对于传统方法，它聚类效果更好；相对于DTW类方法，效果稍差，但速度快很多。毕竟从原理来看，K-Shape只考虑了纵向拉伸和横向平移，而DTW还考虑了横向拉伸。 K-Shape原理和K-means相似，不同在于它改进了距离计算方法，并优化了质心计算方法。一方面支持振幅缩放和平移不变性，另一方面计算效率也比较高，并且不用手动设置参数，便于扩展到更多领域。 距离算法用于计算两组时序数据的差异，其中的核心问题是如何处理时序数据的形变，论文中的图-1 展示的心电图数据被分为A/B两类： 其中A类的特点是：上升->下降->上升，而B类的特点是：下降->上升。图-1 的右下图展示了理想的建模效果，它识别到了相同的模式，而忽略了幅度和相位的差异。人们也更倾向使用这种方法计算距离，很多时候甚至认为距离计算方法比聚类方法更加重要。一般来说，支持振幅缩放和平移不变性的方法，计算成本较高，难以对大数据量建模。 K-Shape之前的主流距离算法如下： K-Shape用互相关方法计算两个时间序列的距离。假设有X和Y两个时间序列，序列长度均为m。为实现平移不变性，Y不变，一步一步划动X，并计算每一步X与Y的差异。 如上图所示：假设绿色区域为Y，白色区域为划动的X，每一行s（step)向前划动一步，序列长度为m=4，s∈(-3,3)共7种取值，w是所有移动的可能性2m-1=7次，w-m=s=k，也就是下面公式中的对齐位置（对齐逻辑贯穿整个算法）。 定义互相关系数CC： 利用R来计算x和y在每一步的相似度，在对的上(在X,Y中都存在)的位置计算点积，最终R是有效区域的点积之和（对每个对上的小块加和）。可以说，R越大两个序列越相似。 由于对比的每个子序列振幅不同，块数也不同，所以在对比时需要进行归一化，归一化方法有三种， 第三种使用了互相关方法，效果最好。 归一化效果如下图所示： 其中图(a)使用z-normalization只做了对振幅的归一化，没有平移，可见在上述情况下，不平移（正对上）时对齐效果最好。从(b)(c)(d)可以看到：(d)图使用第三种方法，在最中间的点上相似度值最大（s=0时），即正对上的时候，其相似度最大，这与(a)呈现出的效果一致。而(b)(c)都认为最相似的情况出现在右侧，这明显不太对。 文中定义了基于形态的距离SBD（Shape-based distance），块重叠越多形状越像CC越大，对比所有可能位置的相似度值，取最相似的max(CC)，然后用1-max(CC)得到SBD，也就是说形状越相似，距离SBD越小，归一化后的NCC值在[-1,1]之间，因此，SBD值在[0,2]之间。 可以看到，用以上方法时间在序列较长时复杂度比较高，当序列较长时，计算量也会很大，为解决这一问题，作者提出使用傅里叶变换将序列由时域转到频域再比较，以节约计算量。 定义了距离之后，还需要根据距离逻辑来调整质心算法。 从图-4 可以看到：时序数据的质心也是一条时序变化线，图中的蓝色线使用均值方法（计算每个点的均值）来计算质心；由于错位，波峰和波谷被拉成了直线，因此不能正确地表达形状趋势。 K-Shape使用基于SBD的方式计算质心。 该公式的目标是寻找μk*，使质心μk与该簇Pk中各条序列xi的相似度NCC最大。 算法一：先使用SBD() 函数计算dist和y'，dist是时序x,y之间的距离，y'是y中与x最匹配的子段。使用这种方法解决了波峰波谷对不齐，以致相互抵消的问题。 然后用基于线性代数方法，将公式13展开成公式15： 最终可利用瑞利商公式加以简化： 瑞利商R(M,x)的一个重要的性质是：R的最大值等于矩阵M最大的特征值，最小值等于矩阵M最小的特征值。此时，就不用太考虑R(M,x)中的x(即本问题中的uk)。公式13被简化成以下算法： 算法二：ShapeExtraction()根据簇的当前质心C和簇内的所有点X，计算更合理的质心C'。 line2: 遍历簇内所有的点X(i) line3: 计算各点与质心的距离dist以及其中与质心最为相似的片断x' line4: 将最为相似的片断加入X' line5: X'转置与X相乘生成一个方阵（X的平方） line6: 创建用于正则化的矩阵Q line7: 正则化后生成矩阵M line8: 取矩阵M对应最大特征值时的特征向量，以实现对X'的特征抽取 （以上说明为个人理解，不一定对，仅供参考） 最终的聚类方法通过迭代实现，每次迭代分为两步：第一步重新计算质心，第二步根据每个序列与新质心的距离将它们重新分配到不同的簇中；一直循环迭代到标签不再变化为止。 算法三：聚类的完整过程由 k-Shape() 实现： 其中X是所有序列，k是簇的个数，IDX是标签。 line3: 在标签稳定前&迭代次数不超过100次的条件下，不断迭代 line4-10：根据簇中的元素重新计算每个簇的质心C line11-line17：计算每个序列与各个质心的距离，并将它分配到新的簇中（重新打标签）。 K-Shape算法每次迭代所需时间为： O(max{n·k·m·log(m), n·m^2, k·m^3}) 其中n是实例个数，k是簇个数，m是序列长度。可见，该算法大部分的计算代价依赖于时间序列的长度m。然而，这个长度通常比时间序列的数目小得多，因此，对m的依赖不是瓶颈。在m非常大的极少数情况下，可以使用分段或降维方法来有效地减小序列的长度。 图-5对比了K-Shape、ED和DTW模型效果，可以看到绝大多数情况下，SBD好于ED，部分情况下SBD好于DTW。但SBD比DTW好在它速度更快。

STL 表示基于损失的季节性分解的过程。该技术能够将时间序列信号分解为三个部分： 季节性变化（seasonal）、趋势变化（trend）和剩余部分（residue） 。

顾名思义，这种方法适用于季节性的时间序列，这是比较常见的情况。

这里不太明显的地方是，我们为了得到更可靠的异常检测结果，使用了 绝对中位偏差 。该方法目前最好的实现是 Twitter 的异常检测库 ，它使用了 Generalized Extreme Student Deviation （广义的 ESD 算法）测试残差点是否是一个离群点。

该方法的优点在于其简单性和健壮性。它可以处理很多不同的情况，并且所有的异常情况仍然可以直观解释。

它主要擅长于附加的异常值检测。如果想要检测一些水平变化，则可以对移动平均信号进行分析。

该方法的缺点是在调整选项方面过于死板。你所能做的只有通过显著性水平来调整置信区间。

当信号特征发生了剧烈变化时，该方法就失效了。例如，跟踪原本对公众是关闭状态的，却突然对公众开放的网站用户数量。在这种情况下，就应该分别跟踪在启动开放之前和开放之后发生的异常。

分类回归树（CART）是目前最稳健、最有效的机器学习技术之一。它也可以应用于异常检测问题。

分类树学习的最流行实现是 xgboost 库 。

这种方法的优点是它不受信号结构的任何约束，而且可以引入许多的特征参数进行学习，以获得更为复杂的模型。

该方法的缺点是会出现越来越多的特征，这很快会影响到整体的计算性能。在这种情况下，你应该有意识地选择有效特征。

自回归移动平均模型（ARIMA）是一种设计上非常简单的方法，但其效果足够强大，可以预测信号并发现其中的异常。

该方法的思路是从过去的几个数据点来生成下一个数据点的预测，在过程中添加一些随机变量（通常是添加白噪声）。以此类推，预测得到的数据点可以用来生成新的预测。很明显：它会使得后续预测信号数据更平滑。

使用这种方法最困难的部分是 选择 差异数量、自动回归数量和预测误差系数。

该方法的另一个障碍是信号经过差分后应该是固定的。也就是说，这意味着信号不应该依赖于时间，这是一个比较显著的限制。

异常检测是利用离群点来建立一个经过调整的信号模型，然后利用 t-统计量 来检验该模型是否比原模型能更好的拟合数据。

该方法最受欢迎的实现是 R 语言中的 tsoutliers 包。在这种情况下，你可以找到适合信号的 ARIMA 模型，它可以检测出所有类型的异常。

指数平滑方法与 ARIMA 方法非常相似。基本的指数模型等价于 ARIMA (0, 1, 1) 模型。

从异常检测的角度来看，最有趣的方法是 Holt-Winters 季节性方法 。该方法需要定义季节性周期，比如周、月、年等等。

如果需要跟踪多个季节周期，比如同时跟踪周和年周期，那么应该只选择一个。通常是选择最短的那个：所以这里我们就应该选择周季节。

这显然是该方法的一个缺点，它会大大影响整体的预测范围。

和使用 STL 或 CARTs 方法一样，我们可以通过统计学方法对离群值进行统计来实现异常检测。

与 CART 方法一样， 神经网络 有两种应用方式：监督学习和无监督学习。

我们处理的数据是时间序列，所以最适合的神经网络类型是 LSTM 。如果构建得当，这种循环神经网络将可以建模实现时间序列中最复杂的依赖关系，包括高级的季节性依赖关系。

如果存在多个时间序列相互耦合，该方法也非常 有用 。