基于离散序列的异常检测综述
本综述试图对离散序列中异常检测问题的现有研究进行全面、结构化的概述。目的是提供对序列异常检测问题的整体理解，以及针对不同领域提出的技术如何相互关联。我们的具体贡献如下：我们确定了异常检测问题的三种不同的形式，并回顾了来自许多不同和不相连领域的技术，这些技术解决了每一种表述。
在每个问题公式中，我们根据基础算法的性质将技术分组。对于每一类，我们都提供了一种基本的异常检测技术，并展示了现有技术是如何与基本技术不同的。这种方法显示了一个类别中的不同技术是如何相互关联或不同的。我们的分类揭示了以前没有用于异常检测的新变体和组合。我们还讨论了不同技术的相对优势和劣势。我们展示了为一个问题公式开发的技术如何适用于解决不同的公式；从而提供了几种新的适应方案来解决不同的问题。
我们强调了处理离散序列的技术在其他相关领域的适用性，如在线异常检测和时间序列异常检测
1. 背景
（1）会议/刊物级别
IEEE Transactions on Knowledge and Data Engineering ( Volume: 24, Issue: 5, May 2012)
CCF A
（2）作者团队
Varun Chandola：纽约州立大学布法罗分校计算机科学系副教授
（3）研究背景
序列数据广泛应用于入侵检测、生物信息学、天气预报、系统健康管理等领域。
因此，序列数据的异常检测是一个重要的研究课题。在异常检测技术[1]–[3]方面有大量的工作，这些技术可以寻找不同于正常对象的单个对象。这些技术没有考虑数据的序列结构。例如，考虑表1所示的一组用户命令序列。序列S1–S4代表用户的正常日常配置文件，序列S5可能是试图通过尝试不同的密码闯入计算机。虽然序列S5异常，但序列中的每个命令本身都是正常的。
序列是一系列有序的事件。序列可以有不同的类型，例如二进制、离散和连续，这取决于形成序列的事件类型。离散序列和连续序列（或时间序列）是现实生活中遇到的两种最重要的序列形式。在本综述中，我们将重点介绍离散序列。例如，文本文档是一个单词序列，计算机程序是一个系统调用序列，基因是一个核酸序列。
通常，人们感兴趣的是检测离散序列中的异常，以发现可能的入侵、欺诈、故障和污染。例如，收集计算机用户发出的命令序列（如表1所示），以检测可能的入侵活动。
离散序列的异常检测是一项具有挑战性的任务，因为它涉及利用数据的序列性质来检测异常。一些具体挑战如下：
- 序列中存在多种异常定义；序列中的事件可能异常，序列中的子序列可能异常，或者整个序列可能异常。每个定义都需要以不同的方式处理。例如，给定一个蛋白质序列数据库，人们可能会对异常序列感兴趣。另一方面，考虑到计算机系统中执行的系统调用序列很长，当计算机系统受到病毒攻击时，人们可能会对检测子序列感兴趣。在一个序列中检测异常事件的技术可能不直接适用于检测由同时发生的一系列事件引起的异常。
2.序列中异常的长度通常是未知的，并且在不同的应用领域中差异很大。技术通常必须依赖于用户定义的长度，这可能是最优的，也可能不是最优的。
3.对于序列数据来说，计算复杂性是一个重要问题，尤其是因为序列可能非常长，字母表的大小可能很大。
离散序列的异常检测一直是许多研究论文的焦点。但大多数异常检测技术都是在特定的应用领域内开发的。特别是，已经开发了几种技术来检测操作系统调用数据中的异常情况[4]–[10]。Budalakoti等人[11]，[12]对异常检测技术进行了研究，以检测飞行安全领域的异常。Sun等人[13]提出了一种基于概率后缀树的技术，并在生物序列上对其进行了评估。虽然每种技术都在特定领域内进行了评估，但还没有尝试对问题进行整体分析。这种分析之所以至关重要，是因为序列数据的性质以及异常的性质在不同领域可能存在根本性的差异，因此，尽管一种技术在一个领域内被证明是有效的，但它不能保证其在不同领域的有效性。
尽管现有技术似乎具有相同的目标，即检测离散序列中的异常，但更深入的分析表明，不同的技术实际上解决不同的问题公式。例如，Forrest等人[4]提出了几种从未标记序列数据库中检测异常序列的技术。另一方面，Chakrabarti等人[14]在一长串事件中检测到异常子序列。Gwadera等人[15]解决了确定给定长测试序列中短子序列的出现频率相对于其在正常序列中的预期出现频率是否异常的问题。所有这些配方从根本上都是不同的，因此需要专门的技术来解决它们。重要的是，不仅要确定给定技术解决了哪个问题公式，还要了解解决一个公式的技术如何适用于解决不同的公式。
关于序列异常检测的文献分散在不同的应用领域，但还没有任何研究对文献进行全面概述。Forest等人[4]对离散序列的四种不同异常检测技术进行了比较，但所有这些技术都集中在系统调用入侵检测上。Chandola等人[16]对从不同领域收集的序列数据的八种异常检测技术进行了比较评估，但只关注从序列数据库中检测异常序列的问题。
（4）主要贡献
在这项调查中，我们试图对这方面的现有研究提供一个全面和结构化的概述。我们的目标是提供对序列异常检测问题的整体理解，以及针对不同领域提出的技术如何相互关联。我们还研究了不同的问题公式，并展示了为特定问题公式开发的技术如何在不同的环境中进行调整和应用。
我们的具体贡献是：
?我们确定了异常检测问题的三种不同表述，并回顾了来自许多不同和不相连领域的技术，以解决每一种表述。
?在每个问题公式中，我们根据基础算法的性质将技术分组。对于每一类，我们都提供了一种基本的异常检测技术，并展示了现有技术是如何与基本技术不同的。这种方法显示了一个类别中的不同技术是如何相互关联或不同的。我们的分类揭示了以前没有用于异常检测的新变体和组合。我们还讨论了不同技术的相对优势和劣势。
?我们展示了为一个问题公式开发的技术如何适用于解决不同的公式；从而提供了几种新的适应方案来解决不同的问题。
?我们强调处理离散序列的技术适用于其他相关领域，如在线异常检测和时间序列异常检测。
2.基于离散序列的异常检测技术的应用领域
异常检测技术来处理离散序列的几个应用领域如下：
- 操作系统调用/用户命令的顺序[5]，[17]–[19]。序列是使用所有可能的系统调用的字母表定义的(～ 160（适用于Sun Solaris操作系统）或用户命令(～ 2500（对于典型的UNIX用户）。这些数据集中的异常对应于异常的程序行为，通常是由于病毒或恶意用户在计算机系统中的“入侵”，或未经授权访问计算机系统。
- 生物序列，如DNA序列、蛋白质序列[13]、[20]。序列是用对应于核酸碱基（4）或氨基酸碱基的字母表定义的(～ 20). 这些数据集中的异常与生物有机体中的突变或“疾病”状态相对应[21]。
- 来自操作系统（如飞机或航天飞机）的传感器数据[11]、[12]、[22]。在系统运行期间，通过多个离散传感器收集序列。这种离散序列的字母表大小通常很大(～ 1000用于飞机数据[12]）。此类数据集中的异常对应于系统运行中的故障场景或事故。
- 网上银行、客户购买和其他零售商业领域的交易序列[14]。这个这种序列中的“符号”是客户的“动作”，这种序列的字母表大小也可能很大。这些数据集中的异常对应于客户的不规则或异常行为。
- 来自网站的导航点击序列[23]，[24]。这些序列中的“符号”对应于点击的链接（网站）或链接所属的类别。这些数据中的异常对应于不规则或未经授权的用户行为。
3. 问题定义
在这里，我们将讨论序列异常检测问题的三种不同形式，它们在许多应用领域被认为是重要的。就异常的定义而言，这些公式都是独特的。对于第一个公式，如果整个序列与正常序列显著不同，那么它就是异常的。对于第二个公式，如果长序列中的子序列与同一序列中的其他子序列显著不同，则该子序列是异常的。对于第三个公式，如果给定的测试模式在测试序列中出现的频率与其在正常序列中的预期频率显著不同，则该测试模式是异常的。
从应用的角度来看，问题公式的选择取决于异常与应用领域需求的相关性。
例如，考虑操作系统入侵检测领域可能出现的以下三种情况：
场景1：安全分析师对检测属于公司网络的计算机上的“非法”用户会话。非法用户会话是指未经授权的人恶意使用计算机。为了检测此类入侵，分析人员可以使用第一个公式，其中使用过去的正常用户会话（系统调用/命令序列）作为培训数据，并根据该培训数据测试新的用户会话。
场景2：安全分析师感兴趣的是检测用户的帐户在过去几个月是否被滥用（黑客入侵）。为了检测这种误用，分析员可以使用第二个公式，其中用户在过去几个月的活动被视为一个长序列，并对任何异常子序列进行测试。
场景3：安全分析师感兴趣的是确定用户执行特定命令序列的频率是否高于（或低于）预期频率。回到表1中给出的示例，login，passwd，login，passwd序列对应于失败的登录尝试，然后是成功的登录尝试。如果偶尔出现，则用户日常档案中出现此序列是正常的，但如果频繁出现则是异常的，因为它可能对应于未经授权的用户通过尝试多个密码偷偷尝试进入用户的计算机。为了检测此类入侵，分析员可以使用第三个公式，其中命令序列是查询模式，并且将给定日期的用户序列中的查询模式频率与用户过去每天序列中的查询模式预期频率进行比较，以检测异常行为。
大多数论文都讨论了第一个问题公式，但在某些领域也讨论了其他两个公式。接下来的三节将讨论解决这三个问题的技术。
4.通过序列数据库确定序列是否异常
序列异常检测问题最常见的表述是确定给定测试序列相对于序列参考数据库是否异常。该公式的一个应用在第3节中作为场景1提供。大多数解决这个公式的技术都会给测试序列分配一个异常分数。如果给出了一组测试序列，则使用异常评分对它们进行排序，以确定最异常的测试序列。
这个问题公式有两种变体。在第一种变体中，假设参考（或训练）数据库仅包含正常序列，并根据正常参考数据库测试每个测试序列（半监督异常检测）。在第二种变体中，任务是从未标记的序列数据库中检测异常序列（无监督异常检测）。对于第二种变体，假设未标记数据库中的大多数序列是正常的。
问题公式1的半监督变量可表述如下：
定义1：给定一组n序列，S={S1，S2，. . ., Sn}，以及属于测试数据集Sq的序列Sq，计算Sq相对于训练数据集S的异常得分。S序列的长度和Sq序列的长度可能不相等。将异常评分分配给测试序列后，需要一个额外的测试，以确定异常分数是否显著大于被视为异常的测试序列。
问题公式1的半监督变量可表述如下：
定义1a：给定一组n序列，S={S1，S2，. . ., Sn}，找到S中所有异常的序列。
在本节中，我们将主要讨论处理半监督变量的技术。半监督技术可以用来解决无监督问题，方法是将整个数据集视为一个训练集，然后根据该训练集对每个序列进行评分。这种自适应假设给定的集合包含很少的异常序列，因此半监督技术不会受到“训练”集合中异常存在的影响。
解决问题公式1的技术通常分为两个步骤。在第一步中，从S中的序列中学习代表正常行为的“模型”。在第二步中，估计模型M生成的测试序列Sq的“可能性”。可能性用于为测试序列分配异常标签/分数。
我们以松散的方式使用术语模型，它可以指生成模型、非参数密度估计或相似核。生成模型的例子有有限状态自动机（FSA）、隐马尔可夫模型（HMM）和HMM的混合。有几种技术在Sq中的测试序列和S中的正常序列之间使用相似核。此外，还有一类技术使用测试序列中包含的短窗口的可能性来估计测试序列的可能性。因此，此类技术的模型M是测试和训练序列中出现的不同短窗口的密度估计。
异常检测技术也可以根据该技术分析的测试序列的单元元素进行分类，如下所示：
- 基于内核的技术：这些技术将整个测试序列视为分析中的一个单元元素，因此类似于基于点的异常检测技术。他们通常通过为序列定义适当的相似性核来应用基于邻近性的点异常检测技术。
- 基于窗口的技术：这些技术分析一小段符号——一小段子序列-
一次在测试序列内。因此，此类技术将测试序列中的子序列视为分析的单元元素。这些技术需要额外的步骤，根据对整个序列中的子序列的分析，确定整个测试序列的异常性质。 - 马尔可夫技术：这些技术使用概率模型预测观察测试序列每个符号的概率，并使用每符号概率获得测试序列的异常分数。这些技术分析每个符号与前面几个符号的关系。
- 基于隐马尔可夫模型的技术：这些技术将输入序列转换为隐状态序列，然后检测转换序列中的异常。
下面四小节将详细讨论上述四类技术
4.1基于核的技术
这些技术使用特定的相似性度量计算序列之间的成对相似性，然后利用传统的基于点（或实例）的异常检测算法（利用相似性）[11]，[12]，[16]。
基于内核的基本技术的操作如下。
首先，计算S中训练序列的成对相似矩阵。接下来，使用基于点的异常检测算法，将测试序列Sq与相似矩阵进行比较，以获得Sq的异常分数。
已经提出了几种基本技术的变体，它们使用不同的基于点的算法和不同的相似性度量来比较一对序列。
（1）使用不同的基于点的异常检测算法
用于离散序列的两种基于点的异常检测算法是基于k最近邻（kNN）的[25]和基于聚类的[26]。Chandola等人[16]提出了一种基于kNN的技术，其中测试序列的异常分数等于其与训练数据集中第k个最近邻的相似性的倒数。
Budalakoti等人[11]，[12]提出了一种基于聚类的技术，其中首先使用k-medoid算法将训练序列聚类成固定数量的聚类[27]。然后计算测试序列的异常分数，其值等于其与最近medoid相似性的倒数。概率聚类技术也被用于异常检测，它不需要显式的相似矩阵来在训练集中找到聚类。例如，Yang等人[28]提出了一种技术，使用概率萨福克树[29]的混合作为集群表示。其他概率技术，如HMMs混合[30]、[31]或最大熵混合（maxent）模型[24]也可以以相同的方式用于基于聚类的异常检测。
（2）使用不同的相似性度量
比较一对离散序列最简单的相似性度量是简单匹配系数（SMC）[32]，它将两个序列匹配的5个位置的数量计算为其相似性。虽然计算相似性的速度很快（序列长度呈线性），但这种方法的缺点是要求序列长度相等。
一些异常检测技术使用最长公共子序列的长度作为相似性度量，因为它可以计算长度不等的两个序列之间的相似性[11]、[12]、[16]。两个序列Si和Sj之间的相似性（nLCS）计算如下：
使用NLC的缺点是计算复杂度，比SMC高一个数量级，尽管已经提出了计算LCS的更快算法[33]。SMC和NLC的一个缺点是，在计算相似性时，它们不包含不同符号对之间的关系，即所有匹配和不匹配都被同等对待。
也可以使用不要求序列长度相等的其他相似性度量来代替NLC。Kumar等人[34]提出了这样一种度量方法，将序列转换为位图，并比较位图以确定相似度。
（3）基于内核技术的优点和缺点
基于核的技术的优点是，在获得相似核之后，任何基于相似性的点异常检测技术都可以用于检测异常。涉及计算相似性的技术可以利用现有的序列相似性研究[19]、[20]、[35]，然后应用已知的最近邻或基于聚类的异常检测技术[26]、[36]。
基于内核的技术的一个缺点是，它们的性能高度依赖于相似性度量的选择。只有当异常序列与训练序列显著不同时，nLCS等相似性度量才能区分正常和异常测试序列。如果异常在测试序列中是局部的，相似性度量（如NLC）无法识别出这种微小的差异。基于内核的技术的另一个缺点是，计算S中序列之间的成对相似性涉及O（n2）复杂度。
4.2 基于窗口的技术
基于窗口的技术从测试序列中提取固定长度的重叠窗口。每个窗口都分配了一个异常分数。将测试序列中所有窗口的异常分数进行聚合，以获得整个测试序列的异常分数。
首先要理解基于内核技术的局限性，才能理解基于窗口技术背后的动机。从概率上讲，基于核的技术间接估计P（Sq | M），这是给定从训练数据集中学习的模型M，整个测试序列Sq发生的条件概率。研究人员认为，异常的原因通常可以定位于实际序列中的一个或多个较短的子序列[17]。如果将整个序列作为一个整体进行分析，异常信号可能无法与序列之间存在的固有变化区分开来。通过一次分析一个短窗口，基于窗口的技术试图在一个或几个窗口内定位异常的原因。
从序列中获得短窗口的标准技术是沿序列滑动一个固定长度的窗口，每次一个符号。假设对于给定的序列S，提取的窗口用ω1、ω2表示。ωt和每个窗口ωi也可以表示为ωi[1]ωi[2]。ωi[k]。
理解基于窗口技术背后动机的另一种方法。让我们假设一个异常测试序列Sq包含一个子序列aq（一定长度），这是异常的实际原因。在基于滑动窗口的技术中，如果窗口的长度为k，则异常子序列aq将在|aq |+k中发生（部分或全部）? 1扇窗户。因此，可以通过检测至少一个这样的窗口来潜在地检测异常序列。
基于窗口的基本技术的操作如下。在训练阶段，从所有训练序列中提取k长度滑动窗口，并保持训练数据集中每个唯一窗口的出现频率（作为正常字典）。在测试步骤中，从测试序列Sq中提取长度为k的滑动窗口。为窗口ωi分配一个似然分数L（ωi），该分数等于正常字典中与窗口ωi相关的频率。门槛λ用于确定特定窗口ωi是否异常（L（ωi）<λ）或不异常（L（ωi）≥ λ). 测试序列的异常分数与测试序列中异常窗口的数量成正比。测试序列异常分数Sq的精确表达式如下所示：
上述基于窗口的基本技术已被提出用于操作系统调用入侵检测，称为t-STIDE（基于阈值的序列时延嵌入）[4]，[5]。已经提出了t-STIDE技术的几种变体，尤其是用于系统调用入侵检测[17]、[19]、[35]、[37]–[41]。这些变体与tSTIDE的不同之处在于，它们如何将异常分数分配给窗口，以及如何组合分数以获得测试序列的全局异常分数。
（1）为窗口分配异常分数
在t-STIDE技术中，每个窗口ωi（表示为A（ωi））的异常分数等于正常字典中窗口出现频率的倒数。已经提出了其他技术来为窗口分配不同的异常分数。我们将在这里讨论这类技术的三种类型：
1.使用前瞻对。该类别下的技术利用前瞻对为一个窗口ωi分配分数[17]。普通词典的结构如下。对于出现在S中的每个符号，出现在j中的符号位于该符号之后(?J∈ [1，k]）被记录下来。给ωi分配异常分数
，形式为hωi[1]，ωi[j]i的符号对的数量，?J∈ （1，k]被计数，使得ωi[1]后面不跟ωi[j]在正常字典中的j位置之后。不匹配的前瞻对的总数除以k是窗口的异常分数。
2.与普通字典进行比较。这类技术从训练序列构造一个正常字典（固定长度窗口），并将测试序列中的每个窗口与正常字典进行比较，以获得异常分数。
Hofmeyr等人[5]使用测试窗口ωi和正常字典中最近窗口之间的汉明距离（或失配数）作为异常分数A（ωi）。在同一篇论文中，还提出了另一种计算A（ωi）的方法。如果窗口
ωi不存在于正常字典中，如果窗口存在于正常字典中，则为0。[41]、[42]中也使用了汉明距离。[37]、[39]、[40]、[43]都采用了后一种方法。
Lane和Brodley[19]、[35]、[44]使用以下相似性度量来计算相似性Sim（ωi
，?j）在测试窗口ωi和正常字典中的窗口?j之间
3.使用分类器。有些技术使用分类器为每个窗口指定异常标签，而不是使用窗口的出现频率来计算其异常分数。训练涉及从训练数据集S获得的k长度窗口集合中学习分类器。如果S包含正常和异常序列，则[10]提出了一种获得标记窗口的方法：
?从S的正常序列中提取的窗口被分配一个正常标签。
?如果从异常序列中提取的窗口也出现在任何正常序列中，则为其分配正常标签，否则为其分配异常标签。
如果S仅包含正常序列，则使用随机异常生成方法[9]、[40]、[43]。从S中的序列中提取的所有窗口都指定了一个普通标签。为了获得异常窗口，生成随机窗口。如果窗口出现在S中，它将被忽略，否则它将被指定一个异常标签并添加到训练数据集中。
构造训练数据集后，学习分类器。已经学习了不同类型的分类模型，例如基于HMM的[10]、神经网络[9]、[37]、[40]、[51]、SVM[52]、[53]和基于规则的分类器[54]。在测试过程中，每个窗口的异常分数
ωi来自测试序列Sq，如果分类器将其标记为正常，则A（ωi）=0，如果分类器将其标记为异常，则A（ωi）=1。
（2）获取测试序列的异常分数
一旦给定测试序列Sq中的所有窗口都被分配了异常分数，下一步就是合并异常分数（长度为| Sq |的向量）? k+1）以获得总体异常得分A（Sq）。t-STIDE技术之前讨论过一种这样的技术。在这里，我们将描述文献中提出的一些其他组合技术。
Hofmeyr等人[5]提出了两种计算总体异常评分的方法。第一种方法将其计算为Sq中所有窗口上异常信号强度的平均值。
（3）基于窗口技术的优缺点
与基于内核的技术相比，基于窗口的技术的一个关键优势是，它们更适合检测测试序列中短区域内的异常。构造普通字典很容易实现，并且可以使用适当的数据结构高效地完成。
基于窗口的技术的一个缺点是，它们高度依赖于k（窗口长度）的值。如果选择k非常小，大多数k长度窗口在训练序列中出现的概率将很高，而如果选择k非常大，大多数k长度窗口在训练序列中出现的概率将很低。因此，在任何一种情况下，k长度窗口区分正常序列和异常序列的分辨能力都很低。为k设置一个最佳值很有挑战性。另一个缺点是，存储训练序列中出现的所有唯一窗口及其频率可能需要大量内存.
4.3 基于马尔可夫模型
解决问题公式1的第三类技术从训练序列中学习模型。
该模型被用作“真实”的近似值
生成正常数据的分布。通常，给定序列S（=hs1，s2，…sli）的概率使用链式规则进行分解：
其中l是序列的长度，si是出现在S中位置i处的符号。
马尔可夫技术利用序列的短记忆特性，这在不同的域中都可以观察到[29]。短记忆特性本质上是一个高阶马尔可夫条件，它表示符号出现的条件概率为
，考虑到目前为止观察到的序列可以近似为：
（1）修正了马尔可夫技术
这种技术使用固定的历史（长度为k）来估计测试序列中符号的条件概率。
基本的固定马尔可夫技术“学习”给定符号sqi出现的条件概率，如下所示：
（2）可变马尔可夫技术
固定马尔可夫技术的一个问题是，它们强制测试序列的每个符号以之前的k个符号为条件（参见（9））。通常，k长度子序列的频率，即（sq（i?（k）
. . . sq（i）?1） ），可能不够大，无法提供该子序列后面的符号的条件概率的可靠估计。例如，让我们假设子序列aabbb在所有训练序列中出现一次，并且在该单独出现的序列中后跟符号b’。固定马尔可夫技术（k=5）将条件概率1分配给P（b | aabbb）。但这种条件概率是不可靠的，因此可能会产生不理想的结果。可变马尔可夫技术试图通过允许符号以可变长度的历史为条件来解决这个问题。对于上述示例，如果子序列abbb在训练序列中出现了大量次，则P（b | aabbb）可以被P（b | abbb）替换.
（3）稀疏马尔可夫技术
上述可变马尔可夫技术允许针对不同符号可能具有不同长度的历史来分析符号sqi；但他们仍然选择Sq中sqi的连续和紧靠前的符号。稀疏马尔可夫技术更灵活，因为它们基于之前k个符号中的符号来估计sqi的条件概率，这些符号不一定是连续的或紧靠前的sqi
换句话说，这些符号是以稀疏的历史为条件的。使用第4.3.2节中的示例，如果序列“aabbb”
在训练序列中很少出现，条件概率P（b | aabbb）可以潜在地替换为9 P（b | aXbXb），其中X可以替换为字母表的任何符号。
（4）基于隐马尔可夫模型的技术
隐马尔可夫模型（HMM）是功能强大的有限状态机，广泛用于序列建模[59]。HMMs还被应用于序列异常检测[4]，[60]–[62]。这种技术使用HMM将输入序列从符号空间转换到隐藏状态空间。这种技术的基本假设是，隐藏空间可以有效地捕捉序列的性质。
一般的方法是用σ构造HMM
隐藏状态，使用Baum-Welch算法从S中的正常序列[63]。对于S中的每个正常序列以及测试序列Sq，使用维特比算法获得最佳状态转换序列[64]。在这一点上，可以应用前面章节讨论过的任何序列异常检测技术来估计测试序列的异常分数。
[4]中提出了一种这样的技术，其中对隐藏状态序列应用1阶有限马尔可夫技术进行异常检测。乔等人[60]在隐藏状态空间中应用了基于窗口的技术。Zhang等人[61]提出了后一种技术的扩展，其中HMM的状态转换序列用于训练另一个HMM。然后，第二个HMM的状态转换序列用作基于窗口的异常检测技术的输入。
（5）基于HMM技术的优缺点
基于HMM的技术将输入序列转换为隐藏状态序列。因此，如果S中的训练序列由特定HMM生成的假设成立，则转换后的数据（隐藏状态序列）将导致更好的异常检测。
如果上述关于HMM生成的序列的假设不成立，则基于HMM的技术的性能可能比原始数据上的异常检测技术的性能差。基于HMM的技术的另一个缺点是，初始化HMM（隐藏状态的数量、初始转移矩阵）通常不是直观的，对它们的错误选择通常会导致该技术的次优性能。
5.在长序列中检测异常子序列
这类技术解决了以下异常检测问题：
定义2：检测长序列T中的短子序列，相对于T的其余部分异常。
如Keogh等人[65]所定义，此类异常子序列也可被视为不协调：“与时间序列子序列其余部分最大不同的较长时间序列的子序列”。在本节中，我们将把这种异常的子序列称为不和谐。
这个问题定义对于几个应用程序域来说是很自然的，在这些应用程序域中，一个活动会被长时间监控。例如，在信用卡欺诈检测中，个人的信用卡交易会被持续监控，而不一致，即行为（购买）的异常顺序，可能表明存在身份盗窃/滥用的情况。
一种基本的异常检测技术可以描述如下：首先，从给定的序列T中提取所有k长度窗口，并存储为固定长度窗口的数据库，表示为Tk。通过将每个窗口与Tk中的其他窗口进行比较，为每个窗口分配一个异常评分。异常分数高于用户定义阈值的窗口被选为最不和谐的窗口。由于“真实”不和谐的长度是未知的，因此解决该问题的技术通常假定不和谐包含在固定长度k的子序列（或窗口）中。
这项基本技术是Keogh等人[65]–[67]研究的许多技术的核心。请注意，这些技术最初是在时间序列数据的背景下提出的，但可以通过使用符号近似（SAX）等技术对时间序列进行离散化来扩展到离散序列[68]。
基本技术的一个问题是，当将任何窗口与Tk中的其他窗口进行比较时，与T中给定窗口重叠的窗口将与给定窗口高度“相似”。例如，任何窗口与给定序列中的下一个窗口最多相差一个位置。此属性将在正常窗口和包含不和谐的窗口中显示，并且可能会影响窗口异常分数的计算。Keogh等人[66]针对这个问题提出了一个简单的解决方案（本文中称为非自匹配），方法是将一个窗口与Tk中仅与给定窗口不重叠的窗口进行比较。
已经提出了几种基本技术的变体，可以大致分为两类。
第一类技术对窗口的评分不同，而第二类技术处理基本技术的时间复杂性。
5.1 窗口评分技术
对窗口进行评分的一种可能技术是计算所有窗口的数据库Tk中出现窗口的次数（这类似于第4.2节讨论的基于窗口的技术，如t-STIDE）。窗口的异常分数将与此计数相反。对于较小的k值，这是一种合理的方法，但当k值较大时，可能无法在Tk中找到窗口的精确匹配。
对窗口进行评分的另一种可能的技术是，任何窗口的异常评分计算为其到Tk中第m个最近邻居的距离。Keogh等人提出了一种称为HOTSAX[66]的变体，其中m=1，即窗口的异常分数等于其到Tk中最近邻居的距离（仅考虑非自匹配）。基于最近邻的技术的一个缺点是，它们涉及一个额外的参数m，需要仔细设置，尽管可以使用诸如使用到m个最近邻的距离加权和来计算异常分数的方法来降低对m的敏感性。
Keogh等人[69]提出了基本异常检测技术的另一种变体，称为窗口比较异常检测（WCAD）。为了给序列T中的每个窗口分配异常评分，将该窗口与序列的其余部分（例如T）进行比较)使用一种称为基于压缩的差异性（CDM）的信息论度量。对于一个窗口ωi∈ Tk，CDM的定义如下：
5.2 优化基本技术的复杂性
解决问题公式2的基本技术的一个问题是，它需要对窗口对进行O（L2）比较，其中l是序列T的长度。
已经提出了几种更快的变化，它们可以在连续时间序列[66]、[67]、[71]–[73]的背景下以近似线性时间运行，并且可以扩展到离散序列。
一种降低基本技术复杂性的通用技术利用了以下事实。他们没有为所有窗口打分，而是根据需要为最多的窗口打分。因此，如果一个窗口与当前第m个最近邻的距离在任何时候都低于异常得分第p个最大的当前窗口的异常得分，则可以修剪该窗口。由于窗口到其实际第m个最近邻的距离是当前距离的上限，因此该窗口永远不会出现在顶部p个异常窗口中，因此可以进行修剪。
这种修剪已成功地用于传统的异常检测[74]，并已应用于不和谐检测[66]、[67]、[71]。应该注意的是，这种剪枝方法保证了与基本技术相同的结果，但可以降低执行时间。
6.确定给定序列中查询模式的频率是否与预期频率不符
这类技术解决了以下异常检测问题：
定义3：给定短查询模式s、长测试序列s和长序列s的训练集，确定s中s的出现频率相对于s中s的出现频率是否异常。
这个问题也被称为时间序列数据背景下的意外检测[68]，[75]。Keogh等人[75]将一个模式定义为令人惊讶的“如果模式的频率与之前看到的一些数据所预期的频率有很大差异”。请注意，频率较大或较小的模式都很有趣。
上述公式源自第3节中讨论的场景3，其中，如果给定序列中的模式频率与正常序列中的预期频率显著不同，则该模式是异常的。
这种说法的另一个可能动机可能是流行病学研究中流行的病例对照分析[76]。其思想是检测在给定测试数据集（案例）中出现的模式与其在正常数据集（对照）中出现的模式不同的模式。此类技术旨在根据已知异常序列中存在的模式在序列中的频率，对其进行优先级排序。
7.在线异常检测
多个应用领域以流式方式收集序列数据[79]，例如，计算机系统收集的系统呼叫数据、飞机在飞行期间生成的数据等。此类领域通常要求以在线方式在此类序列中检测异常，即一旦发生异常[80]，[81]。在线异常检测的优点是，一旦序列数据中出现异常，分析人员就可以采取预防或纠正措施。
例如，在飞机健康监测中，针对飞机的历史正常飞行序列数据库，测试飞机的当前飞行序列是否异常。一旦发生异常（甚至在收集整个飞行序列之前），确定当前飞行序列有异常可能有助于健康监测系统发出早期警报。
在处理问题公式1的不同技术类别中，有些技术可以很容易地适应在线操作方式。基于窗口和马尔可夫技术在收集窗口（或符号）时为其分配异常分数。通过对异常评分应用阈值，甚至在观察整个序列之前，就可以宣布序列异常。因此，这种技术可以很容易地适应在线操作方式。相比之下，基于核的技术测量整个测试序列与训练序列的相似性，因此不适用于在线检测问题。
处理问题公式2的技术可以很容易地进行调整，以在线方式检测异常。在在线设置中，每个连续的符号子序列都会根据迄今为止观察到的序列分配一个异常分数。只要观察到，就可以使用为每个窗口计算的分数阈值来宣布其为正常或异常。为了获得可靠的异常评分，这种技术可能需要14人在对进入的子序列评分之前，首先观察序列中相当长的一部分。
在在线环境中，问题公式3更难处理，其中测试序列以在线方式收集。这种设置对第6节中讨论的技术提出了挑战，因为必须在不观察整个测试序列的情况下估计测试序列中查询模式的出现频率。
8.结束语
本综述试图对离散序列异常检测问题的研究提供一个结构化和全面的综述。这项调查涵盖了为不同领域独立开发的技术，因此开辟了将一个领域内开发的技术应用于完全不同环境的可能性。此外，这项广泛的调查使我们有可能设想一系列丰富的可能性，将当前的艺术状态扩展到不同的维度。除了对现有研究进行结构化和全面的回顾外，该调查还提供了一套丰富的可能技术，可以通过向不同方向扩展当前的技术水平来开发这些技术。如果不对这一问题进行全球性研究，这种可能性就不明显。
序列异常检测问题最有趣的一个方面是问题公式的丰富多样性。在这项调查中，我们讨论了三种不同的问题公式，它们与不同的应用领域有关。
对于每个问题公式，我们已经确定了使用特定方法检测异常的不同技术组。在每一组中，我们都提供了一种基本技术，并展示了不同的现有技术是相应基本技术的变体。我们还提供了不同变化背后的动机，以及与不同技术类别相关的优势和劣势。这有助于更好地了解当前的研究状况，也有助于未来的研究人员开发新的变体。例如，在基于核的问题公式1技术（第4.1节）中，我们观察到，通过使用基于点的异常检测算法和相似性度量的不同组合，可以开发不同的异常检测技术。同样，通过使用不同的技术来比较一对窗口，可以开发第5.1节中讨论的基于窗口的基本技术的新变体。此外，我们还讨论了如何对一个问题公式中的技术进行调整，以解决不同的公式，从而丰富给定公式中可供选择的技术集。
虽然这篇综述文章的重点是离散序列，但这里讨论的许多技术也适用于连续序列（或时间序列）。例如，基于核的技术可以通过使用适当的相似性/距离核来适应连续序列，例如欧几里德距离[82]，[83]和互相关[84]，[85]。基于窗口的技术可以通过使用从训练序列集中到第k个最近窗口的欧几里德距离来调整，以将异常评分分配给窗口[83]。马尔可夫技术可以通过用时间序列预测模型代替马尔可夫模型进行调整，该模型可以确定在有限的事件历史中观察实值事件的可能性[86]。基于HMM的技术可以通过使用HMM的连续版本进行调整[87]。虽然已经提出了其中一些适应措施，但其他适应措施仍有待进一步研究。
本文主要讨论处理单变量离散序列的技术。许多现实世界的应用程序处理多变量事件序列，其中事件可能包含离散、连续或混合的观测值集[88]。本文中讨论的一些技术与此类设置相关，但还需要考虑如何处理此类复杂序列。例如，用于问题公式1的基于核和窗的技术，以及用于问题公式2的基本技术，可以很容易地扩展到多变量序列，只要可以开发一个相似性度量来比较两个多变量离散序列。此类技术尚未尝试，但需要在未来进行研究。
