一种单时间序列异常子序列检测方法

摘要

本发明提供了一种单时间序列异常子序列检测方法，该方法对异常子序列进行重新定义，提取所有子序列的TSMBRB表示集进行聚类操作，根据得到的聚类信息，如果某个子序列距离其聚类中心较远时，该子序列更可能是异常子序列，或者，如果簇中元素个数越少，则该簇包含异常子序列的可能性更大。该方法采用双层循环结构，外层循环检测候选子序列，内层循环寻找候选子序列的k近邻，且尽可能使内层循环中候选子序列p与异常子序列位置q的距离尽早比当前异常子序列的异常度小，从而提前终止候选子序列的计算。本发明通过分析相邻时刻数据变化规律并加以利用，从而减少了大量的候选子序列，使得距离计算次数大幅度降低，算法效率得到提高。

说明书

技术领域

本发明属于数据挖掘技术领域，尤其涉及一种适用于多领域单时间序列的异常子序列的检测方法。

背景技术

当前异常检测的研究主要集中在数据点的常检测上，即从大量无序的数据点中发现异常的数据点，而没有考虑到数据的次序特征。然而，在很多应用领域，有时研究单一数据点意义并不大，很多时间序列数据就属于这一类，研究其连续的若干数据更具意义。各个领域都包含大量的时间序列数据，例如病人的心电图数据、脑电图数据、发电厂大量传感器的参数数据以及网络流数据等等。而时间序列的异常子序列(模式)检测是一个十分重要的领域，含异常模式的时间序列大部分数据表现为正常形态，异常模式出现频率极少，但极少出现的异常模式却包含相当重要的信息。异常的心电数据意味着病人可能患有某种类型的心脏疾病，异常的脑电数据可能是由癫痫等脑科疾病引起，及时发现病人的异常心电或者脑电数据可以对后续的治疗起到指导作用；而工厂传感器数据异常可能意味着系统某个部分出现了故障，及时发现异常并对系统故障进行修护能减少损失。因此，时间序列数据的异常子序列检测研究极具现实意义。

Dasgupta提出将免疫学中的思想运用到时间序列异常模式检测当中。该方法利用自身免疫系统能够区分自身细胞、分子和外部细胞、分子的特点，将时间序列进行编码处理后利用负向选择原理区别自身及外部细胞或分子，从而进行时间序列异常模式检测。Junshui Ma提出利用One-ClassSVM进行时间序列的异常模式检测，其思想源于One-ClassSVM能够检测向量数据集中的异常点，通过将时间序列数据转化到相空间之后，利用正类训练数据训练出模型，最后使用训练出来的模型对时间序列进行检测看是否偏离模型，这样就能进行时间序列的异常模式检测。Keogh提出了HOTSAX方法来发现时间序列中的异常子序列，该方法将时间序列转化为SAX表示方法，利用启发式方法来改进时间序列子序列的检测顺序，从而极大提高了时间序列异常子序列检测效率。Izakian提出利用模糊C均值聚类的方法来进行时间序列异常子序列检测，其思想为将时间序列子序列利用模糊C均值聚类方法进行聚类，聚类簇中心反映了时间序列的模式结构，对原始子序列用聚类中心来进行重新构建，正常的子序列模式结构能够通过通过聚类簇中心较好的重构，而异常子序列难以通过聚类中心重构，通过比较利用聚类簇中心重构之后的子序列与原子序列差异性，来寻找异常子序列。Sivaraks提出利用主题发现的方法来检测出心电数据中的异常心跳，此种思想也可以运用到其它时间序列的异常子序列检测当中。该方法通过分析心电数据特点并提取出重复出现的模式，并通过比较序列中候选子序列模式与主题之间的相似性，来确定模式是否为异常心电模式，该方法相比其余异常子序列检测算法无需设置异常子序列长度，且结合了心电数据领域知识，检测准确率很高。国内也进行了相关的研究。最先进行研究的是上海复旦大学的肖辉，其将线段作为模式，检测的基本原理是将时间序列转化为多个线段模式，并通过基于模式密度定义的异常度来衡量模式的异常程度，并将异常程度高的模式作为异常。詹艳艳也提出了在时间序列线性表示模式的基础上进行异常模式检测的方法，该算法的思想是如果模式为异常模式，那么该模式出现的频率必然很低，所以对于出现频率低的模式赋予较高的异常值，而对于出现频率较高的模式赋予较低的异常值，异常值高的模式则为异常模式。杜洪波提出利用局部线性映射来检测时间序列中异常模式，其思想为针对时间序列中每个模式，将其通过邻域内的模式进行重构，比较重构后的模式与原模式之间的差异性，重构误差越大的子序列越可能是异常模式。汪斐将时间序列异常子序列检测方法HOTSAX用于在线时间序列数据的异常检测当中，从而实现时间序列数据的动态增量式异常检测。李桂玲提出时间序列的PAA变化模式表示，并利用其聚类结果来寻找时间序列异常，即利用聚类结果启发序列的搜索顺序，从而检测时间序列异常子序列。

单时间序列异常子序列检测方法主要有基于模型的方法及基于比较的方法。基于模型的方法，需要大量的数据来进行模型的训练，设置参数多，算法多针对特定领域，不具有普遍性。基于比较的方法相比基于模型的方法来说，其思想简单直观，设置参数少，无需训练模型，算法适用范围更广。当前基于比较的方法一般通过寻找与其余子序列最不相似的子序列来进行异常子序列的检测。基于比较的方法具有许多优点，但一些问题仍需解决改善，基于比较的方法的原异常子序列定义具有不能发现相似异常的缺点，且当前异常子序列检测算法多只适用于静态时间序列数据。

发明内容

为了解决现有技术中问题，本发明提供了一种单时间序列异常子序列检测方法，改进异常子序列定义，并将异常子序列检测算法运用到动态时间序列数据流中。

本发明通过如下技术方案实现：

一种单时间序列异常子序列检测方法，所述方法采用双层循环结构，所述方法包括：

步骤a，接收单时间序列T，设置子序列长度n值和最近邻个数k值作为输入参数；

步骤b，提取所有子序列的时间序列最小边界矩形比特化TSMBRB表示集，进行聚类操作，得到的聚类结果，如果某个子序列距离其聚类中心较远时，该子序列更可能是异常子序列，或者，如果簇中元素个数越少，则该簇包含异常子序列的可能性更大；

步骤c，利用所述步骤b得到的聚类结果产生外层循环及内层循环检测子序列的检测顺序：在外层循环中，先遍历异常可能性更大的子序列；

步骤d，内层循环中，对于每个候选子序列p，首先应该先排除自身匹配的子序列，若p的k近邻集合中含k个元素，且其与这k个子序列的平均距离小于当前异常子序列的异常度，则可以提前终止内层循环，退出该候选子序列与其他子序列的比较，从而减少比较次数；若不小于当前异常度，且p跟异常子序列位置q之间的距离小于p与其当前k近邻集合中的最大距离，则更新p的k近邻集合；若当前k近邻集合中子序列不足k个，将q加入p的k近邻集合；若内层循环遍历完,候选子序列寻找了其真正k近邻，且其仍然大于当前异常度，则用p及其异常度更新异常子序列位置q及异常度；

步骤e，返回异常子序列位置及其异常度。

本发明还提供了一种单时间序列异常子序列检测方法，所述方法用于时间序列数据流中实现异常子序列的在线检测，所述方法包括：读入一个新数据点并形成新的子序列newseq；然后根据不同情况来确定候选子序列集：若上一时刻异常子序列pre_anomaly_loc为缓冲区中第一个子序列，则候选集为上一时刻第一个子序列的UseList、newseq、当前时刻第一个子序列，否则若newseq的加入使pre_anomaly_loc的异常度变小，则候选集为上一时刻第一个子序列的UseList、newseq、pre_anomaly_loc；否则，候选集为上一时刻第一个子序列的UseList、newseq、pre_anomaly_loc；最后对候选集中子序列调用异常子序列检测算法FTSAD；其中，UseList保存的是那些k近邻集合或者k较相似集合中包含该子序列的子序列，FTSAD算法流程如下：

(1)首先利用上一时刻的异常子序列进行初始化，如果候选集中子序列没有检测完，则针对每个候选子序列p执行以下过程：

i.检测候选子序列p，若已经保存了其k近邻，且其与其k近邻的平均距离(异常度)大于当前异常子序列的异常度，则更新当前异常子序列及异常度，否则其不可能为异常子序列，退出p的检验；若p已经保存了k个较相似子序列，且其与这k个子序列的平均距离小于当前异常子序列的异常值时，也可跳过该候选子序列；

ii.当上述条件不满足时，则p在其所有非自身匹配的子序列中寻找k个较相似的子序列。首先同样进行如下判断：若p已经保存了k个较近子序列，且其与这k个子序列平均距离小于当前异常子序列的异常值，跳过该候选子序列。如果候选子序列p保存了k个较近子序列，但不满足上述条件且内层循环中当前序列q与p的距离比p与其k个较相似子序列最大值小，则用q来更新p的较相似k子序列集合；这时，应该更新p的k较相似子序列集合中被替换的那个子序列的UseList，同时应该更新q的UseList；若p的较相似子序列不足k个时，则将q加入p的较近子序列集合中，同时更新q的使用列表；若p得到了其k近邻子序列，即p与所有非自身匹配子序列进行了距离计算，且p异常度仍大于当前异常子序列的异常度，则用p更新当前异常子序列及其异常度；

(2)当候选集中所有子序列都检测完成，返回最异常子序列及其异常度。

附图说明

图1是本发明的单时间序列异常子序列检测方法的第一实施方式的流程图；

图2是心电数据chf13_45590的曲线图；

图3是心电数据chf13_45590的子序列k近似异常度示意图；

图4是使用列表UseList的结构示意图；

图5是模拟的时间序列数据流示意图；

图6(a)是当前缓冲区中最异常子序列的k近邻异常度示意图；

图6(b)是当前缓冲区中最异常子序列的位置示意图；

图7是附图5所示的数据处理时距离计算次数对数值与新读入数据点数量关系示意图。

图8是附图2所示的数据处理时距离计算次数对数值与新读入数据点数量关系示意图。

具体实施方式

下面结合附图说明及具体实施方式对本发明进一步说明。

本发明给出了基于k近邻的异常子序列定义，并利用子序列的TSMBRB表示的聚类的结果来加速基于新定下的异常子序列检测算法的速度，即可以通过聚类结果对子序列的检测顺序加以优化。首先，因为簇中元素个数越小的簇说明只有少数的子序列映射到这个簇中，所以其包含异常子序列的可能性更大；此外，如果某个子序列距离其聚类中心较远时，该子序列也更可能是异常子序列；另一方面，若子序列越相似，它们的TSMBRB表示在一个簇内可能性更大。

时间序列最小边界矩形比特化表示TSMBRB(Time Series Minimum BoundingRectangles Bit Representation)，将MBR表示与二进制表示结合起来对时间序列进行表示。其中，MBR指的是几何学中用最小边界矩形来包括高维空间点的集合的方法。最小边界矩形法通常用在空间索引当中，例如R-Tree中，MBR可以加快空间索引的速度。

本发明吸取时间序列等长划分简单快速的优点，对时间序列子序列采用等长切割的方法。即对提取的时间序列子序列进行等长划分为若干段，每一段用一个最小的边界矩形将段内的时间序列数据包围起来。时间序列的变化能够通过这几个最小边界矩形呈现出来。对于每一段可以采用最大值、最小值进行表示。最小边界矩形表示相比PAA表示方法来说，其能一定程度反映时间序列在段内的变化。

本发明的异常子序列检测算法可以利用上述这些特点来提高检测效率。本发明的算法采用双层循环结构来寻找异常子序列，并试图通过改进子序列的检测顺序来提高效率。双层循环结构的外层循环检测候选子序列，内层循环寻找候选子序列的k近邻。

在外层循环中，先遍历异常可能性更大的子序列，因为如果算法先求出了异常可能性更大的子序列的k近邻异常度，该值很可能会较大，那么在检测后续子序列时，实际上不用再每次都准确寻找出当前子序列的k近邻，而只需要找到其k个非自身匹配子序列，所谓的非自身匹配子序列就是与当前子序列不重叠的子序列。若其与这k个子序列的平均距离比当前找到的异常子序列的k近邻异常度小时，则可以推断，该子序列不可能为异常子序列，因此，算法可以提前终止内层循环，不再去寻找其真正的非自身匹配k近邻。

这里需要解决的一个问题就是如何尽量早的找到k个较相似子序列，使其与候选子序列的平均距离尽可能小。同样又可以利用TSMBRB聚类的结果，即可以优先搜索候选子序列同一个簇内的k个子序列，因为同一个簇内子序列相似性程度大，这样求出的该子序列与k个子序列的平均距离较小，从而使得及时退出内层循环可能性更大。

基于此，附图1是本发明的单时间序列异常子序列检测方法的第一实施方式(称之为“KTSAD算法”)的流程图。

首先，初始化异常子序列位置及异常度；然后，提取所有子序列并转化为TSMBRB，然后进行聚类得到聚类结果；接着，根据聚类结果产生外层、内层循坏顺序，通过两层循坏来寻找异常子序列，外层循环检测候选子序列，内层循环寻找候选子序列的k近邻；对于每个候选子序列p，首先应该先排除自身匹配的子序列，若p的k近邻集合中含k个元素，且其与这k个子序列的平均距离小于当前异常子序列的异常度，则可以提前终止内层循环，退出该候选子序列与其他子序列的比较，从而减少比较次数。若不小于当前异常度，且p跟异常子序列位置q之间的距离小于p与其当前k近邻集合中的最大距离，则更新p的k近邻集合。若当前k近邻集合中子序列不足k个，将q加入p的k近邻集合。若内层循环遍历完，候选子序列寻找了其真正k近邻，且其仍然大于当前异常度，则用p及其异常度更新异常子序列位置及异常度。最后返回异常子序列位置及其异常度。

本发明中，异常度的计算可以采用基于原始子序列比较，计算欧式距离衡量子序列间相似性。表1位本发明的KTSAD算法的伪代码。

表1 KTSAD算法

本发明以心电数据为例检测时间序列中的异常。心电图数据是能够反映患者心跳数据的时间序列，其在医学是一种很重要的时间序列数据。附图2是心电数据库中截取的一段心电序列数据chf13_45590，其中时间序列含有3750个数据点并且在2800的位置心跳有异常。

利用本发明提出的KTSAD算法对该时间序列进行异常子序列检测。其中设置子序列长度为150，k近邻个数3。通过调用KTSAD算法并观察结果发现，KTSAD算法查找出了异常子序列位置，即为2800左右的子序列。其中附图3为KTSAD算法检测异常子序列时计算出的子序列k近似异常度情况。观察附图3可知，算法检测到位于位置2800左右的异常子序列。

本发明同时将基于k近邻定义的异常子序列算法用于时间序列数据流中实现异常子序列的在线检测，通过分析相邻时刻缓冲区数据的变化规律，缩减候选子序列来提高时间序列数据流中的异常子序列检测效率。

本发明同时将基于k近邻定义的异常子序列算法用于时间序列数据流中实现异常子序列的在线检测，通过分析相邻时刻缓冲区数据的变化规律，缩减候选子序列来提高时间序列数据流中的异常子序列检测效率。

考虑两相邻时刻t与t+1，设时刻t的异常子序列位置为p，时刻t+1的异常子序列位置为q，两时刻异常度变化可分为两种情况：

(1)t+1时刻q的k近邻异常度相比t时刻p的k近邻异常度变小。

(2)t+1时刻q的k近邻异常度相比t时刻p的k近邻异常度变大。

对于情况1又可以分为如下两种可能子情况：

i.新到达的数据所产生的新子序列与p的距离小，需要更新p的k近邻集合，从而使得t+1时刻，子序列p的k近邻异常度变小，这可能会导致时刻t+1其余子序列的k近邻异常度比p的k近邻异常度大。

ii.时刻t异常子序列位置为p，而p在缓冲区中的相对位置为1，t+1时刻，由于第一个数据的删除，p不再存在，从而异常子序列的位置也会发生变化。

对于情况2来说，t+1时刻异常度变大的原因则是由于t时刻缓冲区第一个数据的删除导致第一个子序列不再存在，而缓冲区中其余子序列的k近邻中可能包含t时刻缓冲区的第一个子序列，或者子序列的较相似k子序列集合中包含t时刻缓冲区的第一个子序列，从而使得t+1时刻，这些子序列的异常度可能增大，并可能大于p的异常度，从而使得异常子序列发生变化。

只有上述描述的情景下，相邻两个时刻异常子序列位置才会发生变化。对于情况1，t+1时刻异常子序列q的异常度相比t时刻异常子序列p的异常度变小，这时候应该对缓冲区中的子序列都进行检测。对于情况2来说，如果t+1时刻相比t时刻异常子序列发生变化，那么t+1时刻的异常子序列一定是使用了t时刻缓冲区的第一个子序列作为其k近邻的子序列或者使用其作为较相似k子序列的子序列，或者是新加入的子序列。

因此如果出现情况2，只需要考察上边这些候选的子序列即可，从而极大削减需要检查的子序列。为了快速的找到这些子序列，对于每个子序列，本发明建立一个使用列表UseList，UseList保存的是那些k近邻集合或者k较相似集合中包含该子序列的子序列。其结构如附图4所示。通过使用该列表，出现情况2时，能马上找到候选异常子序列。

对于情况2，如果t+1时刻相比t时刻异常子序列发生变化，那么t+1时刻的异常子序列一定是使用了t时刻缓冲区的第一个子序列作为其k近邻集合中的子序列，或者是新加入的子序列。对于情况1中子情况i，采用的策略是考虑的候选子序列与情况2相同，即t+1时刻只考虑t时刻第一个子序列的使用列表中的子序列、t+1时刻新形成的子序列以及t时刻的异常子序列。对于情况1中子情况ii，采用与子情况i类似的策略，但是不考虑t时刻的异常子序列(第一个子序列)，因为其已经移出了缓冲区，此外应该再考虑t时刻的第二个子序列，因为相邻子序列之间的相似程度相当大，其很可能成为t+1时刻新的异常子序列。表2给出了伪码，算法根据不同情况来确定候选子序列集，最后对候选集中子序列调用异常子序列检测算法FTSAD。

基于此，表2是本发明的单时间序列异常子序列检测方法的第二实施方式(称之为“EOTSAD算法”)的伪代码。

表2 EOTSAD算法

其中FTSAD算法流程描述如下：

(1)首先利用上一时刻的异常子序列进行初始化，如果候选集中子序列没有检测完，则针对每个候选子序列p执行以下过程：

i.检测候选子序列p，若已经保存了其k近邻，且其与其k近邻的平均距离(异常度)大于当前异常子序列的异常度，则更新当前异常子序列及异常度，否则其不可能为异常子序列，退出p的检验。若p已经保存了k个较相似子序列，且其与这k个子序列的平均距离小于当前异常子序列的异常值时，也可跳过该候选子序列。

ii.当上述条件不满足时，则p在其所有非自身匹配的子序列中寻找k个较相似的子序列。首先同样进行如下判断：若p已经保存了k个较近子序列，且其与这k个子序列平均距离小于当前异常子序列的异常值，跳过该候选子序列。如果候选子序列p保存了k个较近子序列，但不满足上述条件且内层循环中当前序列q与p的距离比p与其k个较相似子序列最大值小，则用q来更新p的较相似k子序列集合。这时，应该更新p的k较相似子序列集合中被替换的那个子序列的UseList，因为p不再使用它，同时应该更新q的UseList，因为p使用了q作为较相似子序列。若p的较相似子序列不足k个时，则将q加入p的较近子序列集合中，同时更新q的使用列表。若p得到了其k近邻子序列，即p与所有非自身匹配子序列进行了距离计算，且p异常度仍大于当前异常子序列的异常度，则用p更新当前异常子序列及其异常度。

(2)当候选集中所有子序列都检测完成，返回最异常子序列及其异常度。

表3 FTSAD算法

上述的分析减少了当前缓冲区候选子序列数目，使子序列之间距离计算次数大幅度降低，从而了提高效率。

设置异常子序列长度为50，缓冲区长度为300，并设置k为2。利用本发明提出的EOTSAD算法对附图5所模拟的时间序列数据流进行异常检测，附图6(a)以及附图6(b)分别表示当前缓冲区中最异常子序列的k近邻异常度及其位置，从中可以看到，开始时缓冲区最异常子序列k近邻异常度很小，缓冲区内无真实意义异常，当缓冲区移动大约30个数据点时，缓冲区的k近邻异常度开始变大，因为这时附图5中的第一段异常(记为e3(t))开始进入缓冲区中，附图6(b)显示出异常位置为330左右，随后直到缓冲区首部滑动到380的位置，缓冲区中最异常子序列的k近邻异常度又变得很低，因为此时e3(t)已经从当前缓冲区中消失，随后当缓冲区首部滑动到520的位置时，由于第一段异常(记为e2(t))进入了当前缓冲区，当前缓冲区最异常子序列的k近邻异常度又开始变大，附图6(b)显示异常位置为820左右，直到异常e2(t)从当前缓冲区中消失，当前缓冲区最异常子序列的k近邻异常度又变得很小。将警告阈值为倍率设置为2时，算法在两个异常出现时及时发生了报警，从结果中可以看到EOTSAD算法准确的发现了时间序列数据流中的异常子序列。

上述分析针对的是静态时间序列中异常子序列的检测效率，附图7和附图8为将EOTSAD与KTSAD算法运用到时间序列数据流中并对效率进行对比，其中包括合成时间序列数据流以及真实时间序列数据流，其中，附图7是针对附图5所示的数据处理时距离计算次数对数值与新读入数据点数量关系，附图8是针对附图2所示的数据处理时距离计算次数对数值与新读入数据点数量关系。从图中可以看到，EOTSAD算法比KTSAD算法运用到时间序列数据流中效率高很多。因为KTSAD算法每次都重新对当前缓冲区进行全局处理，而EOTSAD算法通过分析相邻时刻数据变化规律并加以利用，从而减少了大量的候选子序列，使得距离计算次数大幅度降低，算法效率得到提高。

以上内容是结合具体的优选实施方式对本发明所作的进一步详细说明，不能认定本发明的具体实施只局限于这些说明。对于本发明所属技术领域的普通技术人员来说，在不脱离本发明构思的前提下，还可以做出若干简单推演或替换，都应当视为属于本发明的保护范围。