目前，时间序列的异常检测作为一项重要的数据挖掘任务，已被广泛应用到气象信息^[1]、水文监测^[2]、医疗保健^[3]、工业应用^[4]等众多领域中.根据异常的表现形式不同，时间序列的异常可以分为异常点、异常序列及异常子序列^[5].异常点是与大部分数据点有显著差异的数据点^[6-7]；异常序列指的是与大部分时间序列有显著偏差的整条时间序列^[8-9]；异常子序列是与大部分子序列有显著不同的子序列^[10-11].考虑到异常子序列可能与一段时间内的特殊事件有关，往往会比正常子序列包含更多有用的信息，更有研究价值，本文主要对异常子序列进行研究.

异常子序列并非只有一种，不同的机制^[12]会导致多类异常子序列的产生.例如，心电图的异常子序列即心率失常，可以分为窦性心动过速、早搏、房颤、窦性心动过缓、房室传导阻滞等多种类型；水文时间序列中的异常子序列也可以分为洪水、干旱等多种异常类型.为了识别不同类型的异常，可以先检测异常子序列，然后再利用聚类算法区分异常子序列的类型，令一个异常模式代表一类异常子序列，进而实现异常模式的识别.下面分别对异常子序列检测和异常子序列聚类这2部分的相关工作进行说明.

目前, 常见的异常子序列检测算法包括基于距离的异常子序列检测方法^[13-15]、基于聚类的异常子序列检测方法^[5,16] 、基于密度的异常子序列检测方法等^[17-18].基于距离的异常子序列检测方法利用子序列之间的距离计算子序列的异常分数(异常因子), 通过比较异常分数与设定阈值的大小来检测异常子序列.文献[13]提出一种基于距离的异常子序列检测算法DBAD，通过计算两两子序列的欧氏距离，并比较其与分布中心的偏差程度实现异常子序列检测.文献[15]将子序列与其最近的k个子序列距离的平均值作为异常分数，并利用假设检验确定子序列是否异常.基于聚类的异常子序列检测方法是将子序列划分到不同的类簇中，使得簇中的子序列具有较高相似度，簇间的子序列具有较低相似度.通过分析子序列和类簇中心之间的关系，来寻找异常子序列.文献[16]使用模糊$c$均值聚类^[19]来揭示子序列的结构，然后利用从簇中心和划分矩阵得到的重构准则^[20]重建原始子序列，对于每个子序列，根据原始子序列与重建子序列的差值分配其异常分数.该聚类算法需要人为设置聚类个数，但在实际应用中，我们通常缺少对数据集的先验知识，这会严重影响聚类的效果.而基于密度的异常子序列检测方法是根据子序列的密度与其周围子序列的密度之间的比值来定义异常分数，从而检测出异常子序列.文献[18]提出了一种动态局部密度估计(dynamic local density estimation, DLDE)异常子序列检测算法，利用时间分割树(time split tree, TSTree)动态分割时间序列，并通过子序列中每个数据点的动态局部密度来评估子序列的异常程度；但该算法需要利用集成学习获取参数，算法复杂度较大.

由于不同结构的异常子序列预示着不同的异常事件，因此需要对异常子序列进行聚类以区分不同类型的异常子序列，识别所有异常模式.这里介绍一些可用于聚类异常子序列的时间序列聚类算法.文献[21]提出了一种基于轨迹形状的时间序列聚类算法kmlShape，该算法是k均值聚类算法^[22]的一个变体，利用弗雷歇距离计算出时间序列之间的距离，并提出弗雷歇平均值确定每个类别的均值以实现时间序列的聚类；文献[23]提出一种基于统计预处理的距离密度聚类DDC，将平滑和特征选择作为预处理步骤，在每个特性集群中进行距离密度聚类以完成时间序列聚类；文献[24]提出了一个新颖的时间序列聚类算法，该算法可以生成同质且较好分离的聚类，其采用标准的互相关距离度量方法并基于此提出了一个计算簇心的算法，在每一次迭代中都用其来更新时间序列的聚类分配.然而，这些聚类算法对输入参数较为敏感，影响最终聚类结果的正确性，这在一定程度上限制了这些聚类算法的应用.

文献[21−24]中提出的算法在设置参数方面较为薄弱，且忽略了异常子序列的类别区分问题，因此，本文重新定义了异常模式这一概念，提出一种基于自适应k近邻的异常模式识别算法(anomaly pattern recognition algorithm based on adaptive k nearest neighbor, APAKN).该算法首先根据各子序列的自适应k近邻计算其自适应距离比和相对密度，这里相对密度与传统基于密度的异常检测算法^[25]的局部密度有所区别，无需计算待测对象密度与其邻域对象密度之比；然后提出一种基于最小方差的自适应阈值方法确定异常阈值；最后采用基于自适应k近邻的聚类算法自动发现聚类中心并聚类异常子序列.整个算法过程在无需设置任何参数的情况下，不仅解决了密度不平衡问题，还精简了传统基于密度异常子序列检测算法的步骤，实现良好的异常模式识别效果.

1.   相关定义

定义1. 子序列.给定一子序列集合$D=\left\{{s}_{1},{s}_{2},…, {s}_{i},…,{s}_{N}\right\}$, 其中$N$为子序列的个数, ${s}_{i}= \left\{{x}_{1}^{i}, {x}_{2}^{i},…, {x}_{{l}_{i}}^{i}\right\}$, 其中${l}_{i}$表示子序列${s}_{i}$所包含的数据点个数.

定义2. 异常子序列和正常子序列.异常子序列是子序列集合$D$中异常分数大于异常阈值的子序列，异常子序列集合表示为${D}^{-}=\left\{{s}_{1}^{-}, {s}_{2}^{-}\text{, }…\text{, }{s}_{i}^{-}\text{, }…\text{, }{s}_{n}^{-}\right\}$, 其中$n$为异常子序列的个数, 则正常子序列的个数为$N-n$，正常子序列集合表示为${D}^{+}=\left\{{s}_{1}^{+}, {s}_{2}^{+}\text{, }…\text{, }{s}_{i}^{+}\text{, }…\text{, } {s}_{N-n}^{+}\right\}$.

定义3. 异常模式.异常模式是由相似异常子序列构成的类簇的中心, 异常模式集合表示为$P= \left\{{p}_{1}, {p}_{2},… ,{p}_{i},…,{p}_{c}\right\}$，其中$c$为聚类后的类簇个数.

定义4. 子序列距离.对于子序列集$D$中任意2个子序列${s}_{i}$, ${s}_{j}$, 采用动态时间弯曲（dynamic time warping，DTW）距离^[26]度量计算${s}_{i}$与${s}_{j}$之间的距离${d}_{\text{dtw}}\left({s}_{i},{s}_{j}\right)$：

其中，${s}_{i}\left[1:{l}_{i}-1\right]$为${s}_{i}$去除尾元素后剩余的子序列，即${s}_{i}\left[1:{l}_{i}-1\right]=\left({x}_{1}^{i},{x}_{2}^{i},…,{x}_{{l}_{i}-1}^{i}\right)$；${s}_{j}\left[1:{l}_{j}-1\right]$为${s}_{j}$去除尾元素后剩余的子序列，即${s}_{j}[1:{l}_{j}-1]=({x}_{1}^{j}, {x}_{2}^{j}, …, {x}_{{l}_{j}-1}^{j})$；$d \left({x}_{{l}_{i}}^{i},{x}_{{l}_{j}}^{j}\right)$表示数据点${x}_{{l}_{i}}^{i}$与数据点${x}_{{l}_{j}}^{j}$之间的欧氏距离，计算方法为

定义5. 第$k$近邻和第$k$近邻距离.假设${s}_{i}$和${s}_{j}$为子序列集$D$中的子序列，对于任意正整数$k$,${s}_{i}$的第$k$近邻为${s}_{j}$，${s}_{i}$的第$k$近邻距离为${s}_{i}$与${s}_{j}$之间的距离${d}_{\text{dtw}}\left({s}_{i},{s}_{j}\right)$，记为${kd}_{k}\left({s}_{i}\right)$, ${s}_{j}$需要满足2个条件：

1) $D$中至少存在$k$个子序列${s}_{j'}$, 使${d}_{\text{dtw}}\left({s}_{i},{s}_{{j'}}\right)\leq {kd}_{k}\left({s}_{i}\right)$成立；

2) $D$中最多存在$k-1$个子序列${s}_{{j'}}$，使${d}_{\text{dtw}}\left({s}_{i},{s}_{{j'}}\right) < {kd}_{k}\left({s}_{i}\right)$成立.

定义6. $k$近邻域.子序列集合$D$中，除${s}_{i}$外所有与${s}_{i}$的距离小于等于${s}_{i}$的第$k$近邻距离${kd}_{k}\left({s}_{i}\right)$的子序列构成子序列${s}_{i}$的$k$近邻域$KN{N}_{k}\left({s}_{i}\right)$，即

将$KN{N}_{k}\left({s}_{i}\right)$中子序列的个数定义为${s}_{i}$的$k$近邻个数，记为$\left|KN{N}_{k}\left({s}_{i}\right)\right|$.

定义7. 反向 $k$近邻域.对于任意子序列${s}_{j}\left({s}_{j}\in D\right)$，如果${s}_{i}$属于${s}_{j}$的$k$近邻域，则${s}_{j}$属于${s}_{i}$的反向$k$近邻域$RN{N}_{k}\left({s}_{i}\right)$，即

将$RN{N}_{k}\left({s}_{i}\right)$中子序列的个数定义为${s}_{i}$的反向$k$近邻个数，记为$\left|RN{N}_{k}\left({s}_{i}\right)\right|$.

为说明$k$近邻域和反向$k$近邻域，图1利用7个空心圆分别表示7个子序列，显示出各子序列之间的距离关系.表1列出近邻值$k=4$时7个子序列的$k$近邻域、反向$k$近邻域、反向$k$近邻个数.

图  1  子序列分布示意图

Figure  1.  Schematic diagram of subsequence distribution

下载: 全尺寸图片 幻灯片

表  1  k = 4时子序列的k近邻域与反向k近邻域

Table  1.  k Near Neighbors Domain and Reverse k Near Neighbors Domain of Subsequences when k = 4

子序列	$k$近邻域	反向$k$近邻域	反向$k$近邻个数
${s}_{1}$	$\left\{{s}_{3},{\text{s}}_{2},{\text{s}}_{5},{\text{s}}_{4}\right\}$	$\mathrm{\varnothing }$	0
${s}_{2}$	$\left\{{s}_{4},{\text{s}}_{3},{\text{s}}_{5},{\text{s}}_{6}\right\}$	$\left\{{s}_{1},{\text{s}}_{3},{\text{s}}_{4},{\text{s}}_{6}\right\}$	4
${s}_{3}$	$\left\{{s}_{2},{\text{s}}_{5},{\text{s}}_{4},{\text{s}}_{7}\right\}$	$\left\{{s}_{1},{\text{s}}_{2},{\text{s}}_{4},{\text{s}}_{5},{\text{s}}_{7}\right\}$	5
${s}_{4}$	$\left\{{s}_{2},{\text{s}}_{5},{\text{s}}_{6},{\text{s}}_{3}\right\}$	$\left\{{s}_{1},{\text{s}}_{2},{\text{s}}_{3},{\text{s}}_{5},{\text{s}}_{6},{\text{s}}_{7}\right\}$	6
${s}_{5}$	$\left\{{s}_{4},{\text{s}}_{7},{\text{s}}_{3},{\text{s}}_{6}\right\}$	$\left\{{s}_{1},{\text{s}}_{2},{\text{s}}_{3},{\text{s}}_{4},{\text{s}}_{6},{\text{s}}_{7}\right\}$	6
${s}_{6}$	$\left\{{s}_{4},{\text{s}}_{5},{\text{s}}_{2},{\text{s}}_{7}\right\}$	$\left\{{s}_{2},{\text{s}}_{4},{\text{s}}_{5},{\text{s}}_{7}\right\}$	4
${s}_{7}$	$\left\{{s}_{5},{\text{s}}_{6},{\text{s}}_{4},{\text{s}}_{3}\right\}$	$\left\{{s}_{3},{\text{s}}_{5},{\text{s}}_{6}\right\}$	3

下载: 导出CSV 

| 显示表格

从表1可以看出，同一子序列的$k$近邻域和反向$k$近邻域并不存在对称关系.

2.   基于自适应$\mathit{k}$近邻的异常模式识别算法

APAKN是一个基于自适应$k$近邻的异常模式识别算法，算法整体工作流程如图2所示，主要由异常子序列检测和异常子序列聚类2个部分组成.本节将对 APAKN 算法的基本思想及其实现过程进行详细介绍．

图  2  APAKN的总体工作流程

Figure  2.  The overall workflow of the APAKN

下载: 全尺寸图片 幻灯片

2.1   基于相对密度的异常子序列检测

为了确定子序列是否异常，查询各子序列的自适应$k$近邻值计算子序列的相对密度，根据相对密度计算异常分数，将异常分数大于异常阈值的子序列视为异常子序列.

考虑到异常子序列具有较少的邻居，正常子序列具有较多的邻居，各子序列的$k$近邻值并不相同是自适应$k$近邻搜索算法区别于传统$k$近邻^[27]算法的主要特征.搜索子序列${s}_{i}\left({s}_{i}\in D\right)$的自适应$k$近邻值${k}_{i}$的主要过程为：令搜索次数$r=1$，迭代地寻找每个子序列的$r$近邻域,使用$Nu{m}_{r}$记录第$r$次迭代时$\left\{\right|RN{N}_{r}\left({s}_{i}\right)|{\}}_{i=1}^{N}$集合中0的个数.若$Nu{m}_{r}$在连续3次迭代中未发生变化，即$Nu{m}_{r}=Nu{m}_{r+1}=Nu{m}_{r+2}$，则认为算法达到稳定状态，迭代停止，否则，令$r=r+1$继续迭代.将迭代停止后的迭代次数计为${k}_{f}=r+2$，子序列${s}_{i}$的自适应$k$近邻值${k}_{i}=\mathrm{m}\mathrm{a}\mathrm{x}({\left\{\left|RN{N}_{r}\left({s}_{i}\right)\right|\right\}}_{r=1}^{{k}_{f}})$.

以图1中的子序列为例查找各子序列的自适应$k$近邻值.图3展示了7个子序列在$r=1,r=2, r=3, r=4$时的近邻情况.

图  3  子序列在不同$r$值时的近邻情况

Figure  3.  Neighbors of subsequences at different values of $r$

下载: 全尺寸图片 幻灯片

当$r=1$时, 图3 (a)展示了所有子序列的1近邻，$\left\{|RN{N}_{1}\left({s}_{i}\right)|\right\}{_{i=1}^{7}=\{0,2,1,3,1,0,0}\}$，其$\left|RN{N}_{1}\left({s}_{i}\right)\right|$=0的子序列为${s}_{1},{s}_{6},{s}_{7}$, 此时$Nu{m}_{1}=3$.

当$r=2$ 时，图3 (b)展示了所有子序列的2近邻，$\left\{|RN{N}_{2}\left({s}_{i}\right)|\right\}{_{i=1}^{7}=\{0,3},{2,3},{4,1,1}\}$ ，其$\left|RN{N}_{2}\left({s}_{i}\right)\right|$=0的子序列为${s}_{1}$, 此时$Nu{m}_{2}=1$.

当$r=3$ 时, 图3 (c)展示了子序列${s}_{1},{s}_{5}$的3近邻，$\left\{|RN{N}_{3}\left({s}_{i}\right)|\right\}{_{i=1}^{7}=\{0,4,3,5,6,2,1}\}$，其$\left|RN{N}_{3}\left({s}_{i}\right)\right|$=0的子序列为${s}_{1}$, 此时$Nu{m}_{3}=1$.

当$r=4$ 时, 图3 (d)展示了子序列${s}_{1},{s}_{5}$的4近邻，$\left\{|RN{N}_{4}\left({s}_{i}\right)|\right\}{_{i=1}^{7}=\{0,4,5,6,6,4,3}\}$，其$\left|RN{N}_{4}\left({s}_{i}\right)\right|$=0的子序列为${s}_{1}$, 此时$Nu{m}_{4}=1$.

当$r=2$ 时满足$Nu{m}_{2}=Nu{m}_{3}=Nu{m}_{4}$, 搜索停止, ${k}_{f}= r+2=4$, 输出所有子序列的自适应$k$值为$\left\{{k}_{1}, {k}_{2},…, {k}_{7}\right\}=\{0,4,5,6,6,4,3\}$.

在得到子序列${s}_{i}\left(i={1,2},…,N\right)$的自适应$k$近邻值${k}_{i}\left(i={1,2},…,N\right)$的基础上，计算子序列的相对密度来进一步得到子序列的异常分数.许多复杂的数据集可能有多个密度不同的集群，如果只比较局部密度的大小可能会将一些密度较小集群中的数据对象误检为异常.为解决密度不平衡问题，目前基于密度的异常子序列检测算法通常在估计出所有子序列的局部密度后，通过比较待测子序列的局部密度与其邻域内子序列的局部密度来检测异常，但算法结果对邻域参数较为敏感，人工选择合适的邻域参数较为困难，需要研究者的经验或大量的实验，也使算法不具备自适应性.为此，本文引入自适应距离比计算相对密度，不仅解决密度不平衡问题，而且无需人为选择近邻参数.

令${k}_{m}$为集合$\left\{{k}_{1},{k}_{2},…,{k}_{N}\right\}$中的最大值，${s}_{i}^{j}$为子序列${s}_{i}$的${k}_{m}$近邻域中的子序列，${k}_{i}^{j}$为子序列${s}_{i}^{j}$的自适应$k$近邻值，${s}_{i}$与${s}_{i}^{j}$的距离为${d}_{\text{dtw}}({s}_{i},{s}_{i}^{j})$，${s}_{i}^{j}$的第${k}_{i}^{j}$近邻距离为${kd}_{{k}_{i}^{j}}\left({s}_{i}^{j}\right)$，计算${s}_{i}$与其${k}_{m}$近邻域$KN{N}_{{k}_{m}}\left({s}_{i}\right)$内所有子序列的自适应距离比.子序列${s}_{i}$相对于子序列${s}_{i}^{j}$的自适应距离比为

计算子序列${s}_{i}\left({s}_{i}\in D\right)$的相对密度，其为${s}_{i}$与其所有$KN{N}_{{k}_{m}}\left({s}_{i}\right)$内子序列的平均自适应距离比的倒数，$KN{N}_{{k}_{m}}\left({s}_{i}\right)$中的子序列个数用$\left|KN{N}_{{k}_{m}}\left({s}_{i}\right)\right|$表示.${s}_{i}$的相对密度计算公式为

以图4为例说明自适应距离比如何解决密度不平衡问题.图4中${s}_{8},{s}_{9},{s}_{10}$属于高密度集群，${s}_{11}$为异常子序列，${s}_{12},{s}_{13},{s}_{14},{s}_{15},{s}_{16}$属于低密度集群.若是单纯将密度小的子序列视为异常，则低密度集群都有可能被视为异常.这里以${s}_{8},{s}_{11},{s}_{14}$为例证明自适应距离比解决密度不平衡问题的有效性.在该示例中${k}_{m}=8$，图4中已标注出${s}_{8},{s}_{11},{s}_{14}$的8近邻域范围，表2列出${k}_{m}=8$时${s}_{8},{s}_{11},{s}_{14}$相对于其第8近邻的自适应距离比.

图  4  密度不平衡数据

Figure  4.  Density imbalance data

下载: 全尺寸图片 幻灯片

表  2  s₈, s₁₁, s₁₄相对于其第8近邻的自适应距离比

Table  2.  Adaptive Distance Ratio of s₈, s₁₁, s₁₄ Relative to Its 8th Nearest Neighbor

子序列${s}_{i}$	${s}_{i}$第8近邻${s}_{i}^{8}$	${s}_{i}^{8}$自适应$k$近邻值${k}_{i}^{8}$	${s}_{i}^{8}$的第${k}_{i}^{8}$近邻	自适应距离比
${s}_{8}$	${s}_{9}$	6	${s}_{10}$	$adr\left({s}_{8},{s}_{9}\right)=\dfrac{{d}_{\text{dtw}}\left({s}_{8},{s}_{9}\right)}{{d}_{\text{dtw}}\left({s}_{9},{s}_{10}\right)}=1.833$
${s}_{11}$	${s}_{12}$	3	${s}_{13}$	$adr\left({s}_{11},{s}_{12}\right)=\dfrac{{d}_{\text{dtw}}\left({s}_{11},{s}_{12}\right)}{{d}_{\text{dtw}}\left({s}_{12},{s}_{13}\right)}=4.266$
${s}_{14}$	${s}_{15}$	6	${s}_{16}$	$adr\left({s}_{14},{s}_{15}\right)=\dfrac{{d}_{\text{dtw}}\left({s}_{14},{s}_{15}\right)}{{d}_{\text{dtw}}\left({s}_{15},{s}_{16}\right)}=1.722$

下载: 导出CSV 

| 显示表格

从表2可以看出$adr\left({s}_{8},{s}_{9}\right)$与$adr\left({s}_{14},{s}_{15}\right)$相差较小，而$adr\left({s}_{11},{s}_{12}\right)$远大于$adr\left({s}_{8},{s}_{9}\right)$和$adr\left({s}_{14},{s}_{15}\right)$，根据相对密度的计算公式（6）可以推断出$M\left({s}_{8}\right)$与$M\left({s}_{14}\right)$的值大致相同，而$M\left({s}_{11}\right)$远小于$M\left({s}_{8}\right)$和$M\left({s}_{14}\right)$的值.这可以证明本文提出的自适应距离比和相对密度不受其所属集群密度的影响，解决了密度不平衡问题.

子序列相对密度较低意味着其可能具有较高的异常分数.进一步，子序列${s}_{i}$的异常分数为

得到异常分数集合$S=\left\{S\left({s}_{1}\right),S\left({s}_{2}\right),…,S\left({s}_{i}\right),…, S\left({s}_{N}\right)\right\}$后，对其做归一化处理，子序列${s}_{i}$的最终异常分数为

以图1中${s}_{1}$为例计算异常分数：由于$\{ {k}_{1},{k}_{2},…, {k}_{7}\}= \left\{{0,4},{5,6},{6,4,3}\right\}$，所以该集合中的最大值${k}_{m}=6$，${s}_{1}^{j}$为子序列${s}_{1}$的6近邻域中的子序列，即$s_{1}^{j}(j=1, 2,…,6)\in KNN_6(s_1)=\left\{{s_3},{s_2},{s_5},{s_4},{s_7},{s_6}\right\}$，${k}_{1}^{j}$为子序列${s}_{1}^{j}$的自适应$k$近邻值，${s}_{3},{s}_{2},{s}_{5},{s}_{4},{s}_{7},{s}_{6}$的自适应$k$近邻值分别为${5,4}, 6, 6,{3,4}$，${s}_{3},{s}_{2},{s}_{5},{s}_{4},{s}_{7},{s}_{6}$的第${k}_{1}^{j}$近邻分别是${s}_{6}, {s}_{6}, {s}_{1},{s}_{1}, {s}_{4},{s}_{7}$，因此${s}_{1}^{j}$的第${k}_{1}^{j}$近邻距离分别为${d}_{\text{dtw}}\left({s}_{3}\text{,}{\text{s}}_{6}\right)$，${d}_{\text{dtw}}\left({s}_{2}\text{,}{\text{s}}_{6}\right)$，${d}_{\text{dtw}}\left({s}_{5}\text{,}{\text{s}}_{1}\right)$，${d}_{\text{dtw}}\left({s}_{4}\text{,}{\text{s}}_{1}\right)$，${d}_{\text{dtw}}\left({s}_{7}\text{,}{\text{s}}_{4}\right)$，${d}_{\text{dtw}}\left({s}_{6}\text{,}{\text{s}}_{7}\right)$；代入式(6)可以得到$M\left({s}_{1}\right)=0.413$, ${s}_{1}$的原始异常分数为$S\left({s}_{1}\right)= 1-M\left({s}_{1}\right)=0.586$，归一化异常分数为${S}' \left({s}_{1}\right)= 1$，后文中若无特殊说明，异常分数即是指归一化后的异常分数.

为了准确确定异常子序列，需要设置异常阈值$T$，将待检测子序列${s}_{i}\left(i={1,2},…,N\right)$的异常分数$S'\left({s}_{i}\right)$与异常阈值$T$相比较.若$S'\left({s}_{i}\right) < T$，则子序列${s}_{i}$正常；若$S'\left({s}_{i}\right)\geqslant T$，则子序列${s}_{i}$异常，但异常阈值T选取通常是人为给定的，给实际应用带来较大困难.由于正常子序列远多于异常子序列，以往的异常阈值确定方法通常利用$3\sigma$准则^[28]的思想，根据所有子序列异常分数的均值$u$和标准差${{ \mathrm{\sigma}} }$确定异常阈值$T=u+3\sigma$，但由于不同数据集的异常率不同，T并不适用于所有数据集.考虑到同为异常或同为正常的子序列对之间的异常分数值相差较小，而正常子序列与异常子序列之间的异常分数值相差较大.在阈值合适的情况下异常子序列和正常子序列的异常分数集合的波动都较小，而方差能有效地衡量一组数据的波动程度.为此，本文提出一种新的基于最小方差的自适应阈值方法.

其中均值$u$和标准差$\sigma$是确定值，令参数$\beta \in \left\{{0,0.1}, {0.2,}{0.3},…,{2.8,2.9,3.0}\right\}$.为了选择合适的$\beta$值确定最佳异常阈值$T$，以异常子序列和正常子序列的异常分数集合的方差之和作为目标函数，找出使得目标函数最小的$\beta$以确定异常阈值$T$.

其中${s}_{i}^{-}$为第$i$个异常子序列，${u}^{-}$为所有异常子序列的异常分数的均值，${s}_{i}^{+}$为第$i$个正常子序列，${u}^{+}$为所有正常子序列的异常分数的均值.

以图1中子序列为例确定异常阈值$T$：所有子序列的异常分数的均值和标准差分别为0.280和0.315，$\beta \in \left\{{0,0.1,0.2,0.3},… ,2.8,2.9,3.0\right\}$，则异常阈值$T\in \left\{0.280,0.312,0.343,0.375,… ,1.162,1.194,1.225\right\}$，根据这31个阈值取值分别得到31种异常子序列集合，根据式(12)计算得出目标函数值的集合，当$\beta =0.3$ 时取得目标函数的最小值0.015，此时确定异常阈值$T= 0.280+0.315\times 0.3=0.375$，由于只有$S'\left({s}_{1}\right)\geqslant T$，则检测出图1中子序列${s}_{1}$为异常子序.

2.2   基于自适应$\mathit{k}$近邻的异常子序列聚类

针对异常子序列的多样性，为区分不同类型的异常子序列，本节对得到的异常子序列${D}^{-}= \left\{{s}_{1}^{-}, {s}_{2}^{-}\text{,}…\text{,} {s}_{i}^{-}\text{,}…\text{,}{s}_{n}^{-}\right\}$进行聚类，将每个聚类中心定义为一个异常模式，对不同的异常模式进行识别.本算法能够在聚类个数未知的情况下保证聚类结果的有效性.

APAKN根据2个条件寻找聚类中心：1)聚类中心的密度高于其邻近的子序列的密度；2)任意2个类中心的距离相对较远.首先利用2.1节描述的自适应$k$近邻搜索算法确定所有异常子序列的自适应$k$近邻值${k}_{i}^{-}\left(i={1,2},…,n\right)$，将其作为各异常子序列的密度.将异常子序列中自适应$k$值最大的子序列作为第1个聚类中心${p}_{1}$，在与${p}_{1}$距离最远的$v$个子序列中找出密度最大的异常子序列作为第2个聚类中心${p}_{2}$，其中$v=\left[\dfrac{n}{10}\right]+1$，即为异常子序列个数与10的比值取整加1.在距离存储单元搜索剩余子序列与2个聚类中心之间的距离，确定聚类数为2时各子序列所属聚类.同时使用轮廓系数(silhouette coefficient)^[29]作为聚类有效性指标计算当前的轮廓系数$si{l}_{2}$.

当聚类数为$q$时，轮廓系数的计算公式为

其中$N$为所有子序列个数，${C}_{i}$表示第$i$个类簇，$w$为属于类簇${C}_{i}$的子序列，$sam\left(w,{C}_{i}\right)$被称为子序列$w$的簇内不相似度，是子序列$w$到同类其他子序列的平均距离，$dif\left(w,{C}_{i}\right)$被称为子序列$w$的簇间不相似度, 是子序列$w$到所有其他簇的所有子序列的平均距离中最小的那一个.定义分别为：

其中${n}_{{C}_{i}}$为类别${C}_{i}$所包含子序列的个数，${n}_{{C}_{l}}$为类别${C}_{l}$所包含子序列的个数，${d}_{\text{dtw}}\left(w,u\right)$表示子序列$w$与$u$之间的DTW距离.轮廓系数的值越大，说明同类样本相距越近，不同样本相距越远，聚类效果越好.使得有效性指标最大的聚类中心集合即是算法求得的所有聚类中心.

当聚类数为$i$时，在与已有聚类中心$\left\{{p}_{1},{p}_{2},…, {p}_{i-1}\right\}$的距离之和最大的$v$个子序列中找出密度最大的异常子序列作为第$i$个聚类中心${p}_{i}$，把每个剩余异常子序列分配给距离其最近的聚类中心.计算此时的轮廓系数$si{l}_{i}$，若$si{l}_{i} < si{l}_{i-1}$，此时$c=i-1$，则输出聚类中心集合$P=\left\{{p}_{1},{p}_{2},…,{p}_{c}\right\}$，实现聚类中心的确定和异常子序列的划分.否则$i=i+1$，继续寻找下一聚类中心${p}_{i}$.最终$P=\left\{{p}_{1},{p}_{2},…,{p}_{i},…,{p}_{c}\right\}$为本算法识别出的异常模式集合.

假设图5包含所有异常子序列$\left\{{s}_{1}^{-},{s}_{2}^{-}\text{,}\text{…}\text{,}{s}_{13}^{-}\right\}$.首先根据自适应$k$近邻搜索算法重新确定这些子序列的自适应$k$值，$\{{k}_{1}^{-},{k}_{2}^{-},…,{k}_{13}^{-}\}= \{4,4,8,4,4,6,4,4,7,5,5,5, 5\}$，将这些自适应$k$值作为各子序列密度；其次，由于异常子序列${s}_{3}^{-}$为密度最大的异常子序列，则第1个聚类中心${p}_{1}={s}_{3}^{-}$，$v=\left[\dfrac{n}{10}\right]+1=\left[\dfrac{13}{10}\right]+1=2$，与${s}_{3}^{-}$距离最远的2个子序列中密度最大的异常子序列为${s}_{13}^{-}$，即${p}_{2}={s}_{13}^{-}$，剩余异常子序列的类别则由剩余子序列到${s}_{3}^{-}$，${s}_{13}^{-}$的距离确定，得到2个类别$\{{s}_{1}^{-},{s}_{2}^{-},{s}_{3}^{-},{s}_{4}^{-}, {s}_{5}^{-},{s}_{6}^{-}, {s}_{7}^{-},{s}_{8}^{-}\} \text{和} \{{s}_{9}^{-},{s}_{10}^{-},{s}_{11}^{-},{s}_{12}^{-},{s}_{13}^{-}\}$，利用式(13)计算$si{l}_{2}=0.571$，与聚类中心$\left\{{s}_{3}^{-},{s}_{13}^{-}\right\}$的距离之和最大的2个子序列中密度最大的异常子序列为${s}_{7}^{-}$，将非聚类中心的异常子序列分配类别后，计算得到$si{l}_{3}=0.760$，由于$si{l}_{3} > si{l}_{2}$，${s}_{7}^{-}$为第3个聚类中心${p}_{3}={s}_{7}^{-}$，确定与聚类中心$\{{s}_{3}^{-},{s}_{13}^{-},{s}_{7}^{-}\}$的距离之和最大的2个子序列，其中密度最大的异常子序列为${s}_{12}^{-}$，计算得$si{l}_{4}=0.486$；最后，由于$si{l}_{4} < si{l}_{3}$，所以最佳聚类个数$c=4-1=3$，最终输出的异常模式集合为聚类中心集合$\{{s}_{3}^{-},{s}_{13}^{-},{s}_{7}^{-}\}$.

图  5  异常子序列分布示意图

Figure  5.  Schematic diagram of anomaly subsequence distribution

下载: 全尺寸图片 幻灯片

2.3   APAKN算法步骤

算法1. APAKN算法.

输入：子序列数据集$D=\left\{{s}_{1},{s}_{2},…,{s}_{i},…,{s}_{N}\right\}$；

输出：异常模式集合$P=\left\{{p}_{1}，{p}_{2},…,{p}_{i},…,{p}_{c}\right\}$.

步骤1.对于数据集$D=\left\{{s}_{1},{s}_{2},…,{s}_{i},…,{s}_{N}\right\}$，计算所有子序列之间的DTW距离并将其存放在距离存储单元中以便随时调用，利用子序列距离搜索子序列${s}_{i}\left(i={1,2},…,N\right)$的自适应$k$近邻值.

步骤2.将$k$值集合$\left\{{k}_{1},{k}_{2},…,{k}_{N}\right\}$中的最大值${k}_{m}$代入式(6)计算所有子序列的相对密度，计算异常分数和确定异常阈值，将异常分数大于异常阈值的子序列检测为异常子序列${D}^{-}=\{{s}_{1}^{-},{s}_{2}^{-}\text{,…,}{s}_{i}^{-}\text{,…,}{s}_{n}^{-}\}$.

步骤3.重新搜索异常子序列${s}_{j}^{-}$的自适应$k$值${k}_{j}^{-}$，将其作为${s}_{j}^{-}$的密度，根据所得密度和距离存储单元中的子序列距离迭代地获取聚类中心，并根据式(13)中的轮廓系数判断迭代停止时聚类中心的个数$c$.

步骤4.输出聚类中心集合，即异常模式集合$P=$$\left\{{p}_{1},{p}_{2},…,{p}_{i},…,{p}_{c}\right\}$.

2.4   时间复杂度

APAKN算法采用DTW度量所有子序列之间的距离，该步骤的最大时间复杂度为$O\left({N}^{2}{l}^{2}\right)$，其中数据集中子序列数为$N$, 所有子序列长度都为$l$；异常子序列检测步骤的最大时间复杂度为$O\left(N\;\text{log}\;N+N{k}_{m}\right)$，其中${k}_{m}$为所有子序列自适应$k$值集合中的最大值；异常子序列聚类步骤的最大时间复杂度为$O\left(n\;{{\rm{log}}}\;n\right)$，其中，$n$为异常子序列的个数.可见，APAKN算法的时间复杂度为$O\left({N}^{2}{l}^{2}+ N\;{{\rm{log}}}\;N+ N{k}_{m}+n\;{{\rm{log}}}\;n\right)$，由于$N\;{{\rm{log}}}\;N+ N{k}_{m}+ n\;{{\rm{log}}}\;n\ll{N}^{2}{l}^{2}$，算法的时间复杂度可以表示为$O\left({N}^{2}{l}^{2}\right)$.

3.   实验与结果

为了更好地验证所提出算法的有效性，采用了美国加州大学滨河分校(University of California Riverside，UCR)的时间序列数据集合^[30]中的10个通用数据集作为实验对象对本文算法进行实验评估.由于APAKN算法主要是由异常子序列检测和异常子序列聚类2个方面组成，因此实验部分也将从这2个方向来进行评价.实验环境均为Win 10 64 b操作系统，Python 3.7.6软件，8 GB内存，Intel(R) Core(TM)，i5-4200H CPU@2.80 GHz处理器.

3.1   实验数据

本次实验所用数据为 10 个公开的UCR数据集，由于UCR数据集中并未标出各类子序列是否异常，所以我们选择子序列个数最多的一类作为正常类，随机选择其他几类中的若干子序列组成异常类，使各数据集的异常率不同.表3列出了本次实验中各数据集的详细信息.以50words数据集为例，原数据集包含50个类别，其中类别号为2的子序列簇包含最多的子序列且被选作正常类，类别号为4,10,43的子序列簇被选作异常类，从中随机选择若干子序列作为实验中的异常子序列.

表  3  实验数据集

Table  3.  Experimental Data Sets

数据集	子序列 长度	类别 个数	正常类 别号	异常类 别号	子序列 个数	异常率/%
50words	270	50	2	4$,$10$,$43	905	20
ECG5000	140	5	1	2$,$5	5000	10
FaceAll	131	14	1	2$,$3$,$5	2250	15
Lighting7	319	7	5	3$,$4$,$6	143	35
Trace	275	4	1	2$,$3$,$4	200	30
Two_Patterns	128	4	3	1$,$2$,$4	1114	13
CBF	128	3	1	2$,$3	930	18
Synthetic_Control	60	6	2	1$,$3$,$4$,$5$,$6	600	25
StarLightCurves	1024	3	3	1$,$2	9236	7
ElectricDevices	96	7	5	1$,$2$,$3$,$4	16637	2

下载: 导出CSV 

| 显示表格

3.2   异常子序列检测

3.2.1   评价指标

本节使用准确率(Accuracy)、精确率(Precision) 、召回率(Recall) 、F值作为性能评价指标来评价本算法中异常子序列检测部分的性能，分别定义为:

其中，TP被定义为将异常子序列检测为异常子序列的个数；FP为把非异常子序列检测为异常子序列的个数；FN为将异常子序列检测为非异常子序列的个数；TN表示将非异常子序列正确检测为非异常子序列的个数.

准确率代表的是所有正确预测的样本数占总样本数的比重；精确率衡量算法的查准率，即正确预测为异常子序列占全部预测为异常子序列的比例；召回率衡量算法的查全率，即正确预测为一场子序列占全部实际为异常子序列的比例；F值则为精确率和召回率的调和平均数，同时兼顾算法的精确率和召回率，F度量值的大小反映了聚类结果的精度，它是一个介于−1和1之间的值，该值越接近1，算法的精度就越高.

3.2.2   实验结果

为了证明APAKN算法的优异，图6将算法异常子序列检测部分在10个数据集上的部分实验结果可视化地表示出来.图6中共包含代表着10个数据集的10个子图，每个子图由2个部分组成：时间子序列和子序列异常分数.以50words数据集为例，该数据集的子序列长度为270，我们从类别号为4$,$10$,$43这3个异常子序列簇中分别选择了3个子序列，从类别号为2的正常子序列簇中选择若干子序列，将这些子序列的异常得分在图6 (a)中显示出来.如图6 (a)所示，异常子序列的异常分数远远高于正常子序列的异常分数.此外，对数据集的其他子序列都分配了一个异常分数来度量它们的异常程度.

图  6  UCR部分时间子序列及其异常得分

Figure  6.  UCR partial time subsequences and anomaly scores

下载: 全尺寸图片 幻灯片

为了验证提出的异常模式识别算法APAKN在异常子序列检测部分的性能, 本文比较了APAKN与DBAD^[13]，SFO^[15]，DLDE^[18]算法在各数据集的实验结果.APAKN利用自适应$k$近邻搜索算法自动确定各子序列的最佳近邻值$\left\{{k}_{1},{k}_{2},…,{k}_{N}\right\}$，${k}_{m}$为近邻集合中的最大值；异常子序列检测部分的对比算法DBAD递归计算拟合分布均值方差，需要人为设置递归参数$t$；SFO需要人为设置近邻参数$k$；DLDE构造Hash表以加快估计子序列的局部密度，需人为设置参数Hash值$h$.为了突出显示本文算法的优越性能，在10个实验数据集上，对3个对比算法分别进行多次实验，最终选出一个使其对应检测结果最优的参数值作为其最佳参数，分别记为${t}_{\text{opt}}$，${k}_{\text{opt}}$，${h}_{\text{opt}}$.APAKN算法得到的自适应$k$值中的最大值${k}_{m}$以及对比算法相应的${t}_{\text{opt}}$，${k}_{\text{opt}}$，${h}_{\text{opt}}$如表4所示.

表  4  APAKN的${\mathit{k}}_{\mathit{m}}$值和对比算法的最佳参数值

Table  4.  ${\mathit{k}}_{\mathit{m}}$ Value of APAKN and the Optimal Parameter Values of Comparison Algorithms

数据集	APAKN		DBAD		SFO		DLDE
	${k}_{m}$		${t}_{\text{opt}}$		${k}_{\text{opt}}$		${h}_{\text{opt}}$
50words	18		25		9		24
ECG5000	39		31		29		30
FaceAll	25		20		9		15
Lighting7	17		15		16		15
Trace	15		11		10		16
Two_Patterns	54		27		14		18
CBF	66		33		17		30
Synthetic_Control	24		16		11		10
StarLightCurves	74		86		78		59
ElectricDevices	156		91		153		88

下载: 导出CSV 

| 显示表格

此外，APAKN提出基于最小方差的自适应阈值方法确定异常阈值；SFO算法利用统计假设检验方法判断数据是否异常，其计算较为复杂；而DLDE算法只是对所有数据对象按异常分数值降序排序，人为选择异常分数值最大的几个数据对象作为异常对象，该阈值选择方法需要实验者熟悉各数据集，并且对不同数据集进行实验时需要置换阈值参数，使实验过程更为繁琐.DBAD利用均值和方差确定异常阈值，同样需要人为设置阈值参数.本次实验利用较为常见的$3\sigma$准则作为DBAD和DLDE算法的异常阈值$T=u+3\sigma$.基于表4的最佳参数，表5和表6分别给出了4种算法在异常子序列检测部分的精确率和召回率以及准确率和F值.

表  5  各算法在 10 个数据集上的精确率和召回率对比

Table  5.  Comparison of Accuracy and Recall of Each Algorithm on 10 Data Sets

数据集	APAKN			DBAD			SFO			DLDE
	精确率	召回率		精确率	召回率		精确率	召回率		精确率	召回率
50words	1.000	1.000		0.845	0.742		0.462	1.000		1.000	0.673
ECG5000	0.896	0.875		0.663	0.619		0.650	1.000		0.852	0.642
FaceAll	0.912	1.000		0.796	0.842		0.857	1.000		0.743	0.685
Lighting7	1.000	0.917		0.874	0.903		0.579	0.917		0.845	0.683
Trace	0.923	1.000		0.911	1.000		0.727	0.667		1.000	0.967
Two_Patterns	0.954	0.991		0.852	0.800		0.444	0.533		0.845	0.667
CBF	1.000	1.000		0.860	0.914		0.558	1.000		1.000	0.772
Synthetic_Control	1.000	1.000		0.757	0.637		0.735	1.000		1.000	0.700
StarLightCurves	0.912	0.896		0.912	0.845		0.774	0.685		0.875	0.689
ElectricDevices	0.923	0.851		0.845	0.798		0.855	0.762		0.796	0.744
注：黑体数值表示最佳值.

下载: 导出CSV 

| 显示表格

表  6  各算法在 10 个数据集上的准确率和F值对比

Table  6.  Comparison of Accuracy and F Value of Each Algorithm on 10 Data Sets

数据集	APAKN			DBAD			SFO			DLDE
	准确率	F值		准确率	F值		准确率	F值		准确率	F值
50words	1.000	1.000		0.914	0.790		0.851	0.632		0.901	0.805
ECG5000	0.996	0.885		0.923	0.640		0.973	0.788		0.865	0.732
FaceAll	0.980	0.953		0.802	0.818		0.961	0.923		0.993	0.713
Lighting7	0.974	0.957		0.826	0.888		0.769	0.710		0.875	0.755
Trace	0.971	0.960		0.871	0.953		0.800	0.696		0.963	0.983
Two_Patterns	1.000	0.972		0.836	0.825		0.876	0.485		0.896	0.746
CBF	1.000	1.000		0.931	0.886		0.940	0.716		0.875	0.871
Synthetic_Control	1.000	1.000		0.860	0.691		0.880	0.847		0.698	0.823
StarLightCurves	0.895	0.904		0.889	0.877		0.852	0.727		0.857	0.771
ElectricDevices	0.924	0.886		0.852	0.821		0.824	0.806		0.869	0.769
注：黑体数值表示最佳值.

下载: 导出CSV 

| 显示表格

表5给出了4种算法在10个数据集上异常子序列检测的精确率和召回率对比，表6则给出了异常子序列检测部分的准确率和F值对比, 可以看出，APAKN在10个数据集上的实验结果皆具有最佳性能. 此外，DBAD算法有1个最佳精确率和1个最佳召回率；SFO有6个最佳召回率；DLDE有4个最佳精确率.由上述实验结果可以判断出，相较于其他算法，本文算法不仅具有很强的自适应性，而且具有很高的异常子序列检测水平.

3.3   异常子序列聚类

3.3.1   评价指标

本文利用调整兰德系数(adjusted rand index, ARI)^[31] 和标准化互信息(normalized mutual information, NMI)^[32]两种衡量标准对异常子序列聚类结果进行评判.这2个衡量标准的上限均为1，该值越接近1，表示该聚类算法的准确率越高，算法聚类结果越好.

调整兰德系数值${E}_{{{\rm{ARI}}}}$定义为

其中${n}_{{{{a}}}}$表示在算法聚类结果中为同一类、在数据集真实聚类中也为同一类的子序列对数；${n}_{{{{b}}}}$表示在算法聚类结果中为同一类、在数据集真实聚类中不为同一类的子序列对数；${n}_{{{{c}}}}$表示在算法聚类结果中不为同一类、在数据集真实聚类中为同一类的子序列对数；${n}_{{{{d}}}}$表示在算法聚类结果中不为同一类、在数据集真实聚类中也不为同一类的子序列对数.

标准化互信息值${E}_{{{\rm{N}}}{{\rm{M}}}{{\rm{I}}}}$定义为

其中${c}_{{{{A}}}}$表示算法聚类结果的聚类类别数，${c}_{{{{B}}}}$表示数据集本质聚类类别数，${n}_{ij}$表示子序列属于真实标签类$j$但被划分到聚类结果簇$i$中的个数，${n}_{i}$表示聚类结果类$i$中子序列的个数，${n}_{j}$表示真实标签类$j$中子序列的个数.

3.3.2   实验结果

为了证明APAKN算法的优异, 图7和图8分别将算法异常子序列聚类部分在50words和CBF数据集上的实验结果可视化地表示出来.图7包含代表着3类异常子序列的异常子序列示例和聚类算法下生成的簇质心即异常模式.通过图7中不同类别下的异常子序列的示例可以看出，同一类别下的异常子序列具有相同的趋势.从异常模式图可以看出算法得到的质心很好地表征了每个类别的趋势特征.

图  7  50words数据集在不同类别下的异常子序列示例和异常模式

Figure  7.  Examples of anomaly subsequences and anomaly patterns in different categories of the 50words dataset

下载: 全尺寸图片 幻灯片

图  8  CBF数据集在不同类别下的异常子序列示例和异常模式

Figure  8.  Examples of anomaly subsequences and anomaly patterns in different categories of the CBF dataset

下载: 全尺寸图片 幻灯片

在异常子序列聚类部分，本文选择了kmlShape^[21]，DDC^[23]，KShape^[24]算法进行性能比较.APAKN的聚类部分同样无需设置任何参数，而为了更好地显示出算法的优异性，对3种对比算法都进行了参数调优.由于kmlShape算法选取的初始类簇中心不同，则聚类结果也不同，对每个数据集进行多次重复实验, 取其中最好的结果.kmlShape，DDC，KShape算法需要给定类簇个数，为这3种算法分别选出一个使评价指标最优的参数作为其聚类个数.表7为APAKN的异常子序列聚类部分在10个UCR数据集上与kmlShape，DDC，KShape这3种算法的聚类结果对比.

表  7  各算法在 10 个数据集上的ARI和NMI对比

Table  7.  Comparison of ARI and NMI of Each Algorithm on 10 Data Sets

数据集	APAKN			kmlShape			DDC			KShape
	${E}_{\mathrm{A}\mathrm{R}\mathrm{I}}$	${E}_{\mathrm{N}\mathrm{M}\mathrm{I}}$		${E}_{\mathrm{A}\mathrm{R}\mathrm{I}}$	${E}_{\mathrm{N}\mathrm{M}\mathrm{I}}$		${E}_{\mathrm{A}\mathrm{R}\mathrm{I}}$	${E}_{\mathrm{N}\mathrm{M}\mathrm{I}}$		${E}_{\mathrm{A}\mathrm{R}\mathrm{I}}$	${E}_{\mathrm{N}\mathrm{M}\mathrm{I}}$
50words	0.814	0.825		0.562	0.528		0.524	0.658		0.752	0.635
ECG5000	0.827	0.768		0.662	0.612		0.586	0.693		0.825	0.698
FaceAll	1.000	1.000		0.814	0.802		0.725	0.547		0.408	0.662
Lighting7	0.836	0.905		0.635	0.620		0.433	0.623		0.689	0.814
Trace	0.522	0.734		0.586	0.532		0.425	0.389		0.368	0.647
Two_Patterns	1.000	1.000		0.633	0.396		0.362	0.412		0.453	0.504
CBF	0.925	0.814		0.755	0.852		0.615	0.578		0.847	0.689
Synthetic_Control	0.457	0.667		0.643	0.614		0.303	0.339		0.478	0.713
StarLightCurves	0.956	0.756		0.789	0.812		0.546	0.632		0.874	0.684
ElectricDevices	0.857	0.859		0.478	0.532		0.722	0.566		0.647	0.684
注：黑体数值表示最佳值.

下载: 导出CSV 

| 显示表格

通过表7可知，即使已经给定了对比算法的最佳参数，kmlShape，DDC，KShape算法的聚类结果还是波动较大, DDC聚类效果不佳.kmlShape算法在FaceAll，Trace，CBF，Synthetic_Control数据集上的性能值较优，在其他数据集上的表现不佳；KShape算法在50words，ECG5000，Lighting7，CBF数据集上表现较好.但从总体上来看，APAKN在各个数据集上的评价指标值大部分都要优于与之比较的算法，其余指标均值与最佳指标值相差不大.

因此，结合异常子序列检测与异常子序列聚类2部分的实验结果, 可以验证出算法APAKN是有效可行的.

4.   结　　论

本文提出了基于自适应$k$近邻的异常模式识别算法APAKN，该算法在无需任何参数输入的情况下，不仅检测异常子序列，还区分出异常子序列的不同类别，重新定义了异常模式.采用自适应$k$近邻搜索算法获取子序列的自适应$k$近邻值，解决传统$k$近邻算法的参数设置问题；提出一种基于最小方差的自适应阈值方法解决阈值选择问题；APAKN通过密度与距离结合的思想寻找最优聚类中心，并利用轮廓系数得到聚类数，从而实现异常子序列的快速聚类.在UCR数据集上的实验结果表明了APAKN算法的自适应性与有效性.下一阶段我们将考虑如何从距离度量方面减少算法的时间复杂度以期望提高算法的效率.

作者贡献声明：王玲提出文章的算法思路设计，对论文的逻辑性以及算法的合理性进行指导；周南负责文章的定理和论证过程，以及实验部分的算法实现与实验结果分析；申鹏对文章整体格式进行修改.