

15 离散序列挖掘

“我凌驾于寻求建立一系列原因和效果的弱点。” - 埃德加爱伦坡

15.1 引言

离散序列数据可以被认为是时间序列数据的分类模拟。就时间序列数据而言，它包含一个通常对应于时间的单个上下文属性。但是，行为属性是明确的。相关应用的一些例子如下：
1.系统诊断：许多自动化系统生成包含有关系统状态信息的离散序列。 系统状态的例子是UNIX系统调用，飞机系统状态，机械系统状态或网络入侵状态。
2.生物学数据：生物学数据通常包含氨基酸序列。 这些序列中的特定模式可能会定义数据的重要属性。
3.用户动作序列：不同的序列由用户在不同域中的动作产生。
（a）网络日志包含不同个人访问网站的长时间序列。 （b）客户交易可能包含一系列购买行为。 序列中的单个元素可能对应于不同物品的标识符，或者是购买的不同物品的标识符。
（c）网站上的用户操作（例如网上银行网站）经常被记录。
这种情况与Web日志的情况类似，除了银行网站的日志通常包含用于安全目的的更多详细信息。

生物数据是一种特殊的序列数据，其中上下文数据不是时态数据，而是与不同属性的布局有关。 时间序列数据的方法可以用于生物序列数据，反之亦然。 一个离散序列被正式定义如下：

定义15.1.1（离散序列数据） 长度为$n$，维度为$d$的离散序列$Y_1$…$Y_n$包含$n$个不同时间戳$t_1$…$t_n$中的每一个的离散特征值。 每个组件$Y_i$包含$d$个离散行为属性（ $y_1$…$y_d$），在第$i$个时间戳中收集。

在许多实际情况下，时间戳$t_1$...$t_n$可能只是从1到n索引的刻度值。 在诸如生物数据的情况下，其中上下文属性表示放置的情况尤其如此。 一般来说，实际时间戳在大多数序列挖掘应用中很少使用，并且假设离散序列值在时间上等间隔。 此外，大多数分析技术都是针对d= 1的情况而设计的。这样的离散序列也被称为字符串。 因此，本章将互换使用这些术语。 本章中的大部分讨论都集中在这些更常见和更简单的情况。
在一些应用中，如序列模式挖掘，每个($Y_i$) 不是一个向量，而是一组无序值。 这与定义15.1.1有所不同。 因此，$Y_i$（无划线）将被用来表示一组，而不是一个向量。 例如，在超市应用程序中，集合$Y_i$可以代表客户在给定时间购买的一组商品。$Y_i$中的项目之间没有时间顺序。 在Web日志分析应用程序中，集合$Y_i$表示给定用户在单个会话中浏览的Web页面。 因此，离散序列可以以比时间序列数据更多的方式来定义。 这是因为能够定义离散项目上的集合。 序列中的每个位置也称为元素，由该集合中的各个项目组成。 在本章中，“元素”一词将指代序列中的一组项目，包括一个项目集。
定义中的这些变化源于不同类型应用场景的自然变化。 本章将研究与离散序列挖掘相关的不同问题定义。 对于离散序列挖掘而言，模式挖掘，聚类，离群分析和分类的四个主要问题分别定义为不同于多维数据。 这些不同的定义将被详细研究。 一些模型，如隐马尔可夫模型，广泛用于许多不同的应用领域。 这些常用的模型也将在本章中进行研究。
本章安排如下。 第15.2节介绍了序列模式挖掘的问题。 序列聚类算法在第15.3节。 序列异常点检测的问题在15.4节里讨论。 第15.5节介绍了可以在聚类，分类或检测之前使用的隐马尔可夫模型（HMM）。序列分类的问题在第15.6节讨论。 第15.7节给出了一个总结。
## 15.2 序列模式挖掘 序列模式挖掘的问题可以认为是频繁模式挖掘的时间模拟。 事实上，大多数频繁模式挖掘算法都可以直接适应序贯模式挖掘和系统化方法，尽管后一个问题更为复杂。 与在频繁模式挖掘中一样，序列模式挖掘的最初激励应用是市场购物篮分析，尽管该问题现在用于更广泛的时间应用领域，例如计算机系统，Web日志和电信应用。 序列模式挖掘问题定义在一组N个序列上。 第i个序列以特定的时间顺序包含n_i元素。 每个元素都包含一组项目。 因此，复杂的因素是一套，比如顾客购买的一篮子商品。 例如，请考虑以下顺序：

[面包，黄油]，[黄油，牛奶]，[面包，黄油，奶酪]，[鸡蛋]

这里， [面包，黄油] 是一个元素，并且面包是在元件内部的项目。该序列的子序列也是集合的时间排序，使得子序列中的每个元素都是相同时间顺序中的基本序列中的元素的子集。 例如，请考虑以下顺序：

[面包，黄油]，[面包，黄油]，[鸡蛋]

第二个序列是第一个序列的子序列，因为第二个序列中的每个元素都可以通过子集关系与第一个序列中的相应元素进行匹配，以便匹配元素的序列时间相同。 与集合的交易不同，请注意序列（和开采的子序列）包含有序（可能重复）的元素，每个元素本身就像一个事务。 例如，{面包，黄油}是上述序列中的重复元素，并且它可以对应于顾客在不同时间对超市的两次单独访问。 形式上，后续关系定义如下：

定义15.2.1(子序列) 设$y$={$Y_1$…$Y_n$}和$z$={$Z_1$…$Z_n$}为两个序列，所有元$Y_i$和$Z_i$都被设定，$z$是$y$的一个子序列，如果在$y$中能找到$k$个元素$Y_(i_1 )$$Y_(i_k )$`，其中$i_1$<$i_2$<⋯<$i_k$，且对于$r$∈{$1$…$k$}，有$Z_r$∈$Y_(i_k)$。

考虑包含一组$N$个序列$Y_1$ ...$Y_n$的序列数据库$T$. 与数据库$T$相关的子序列$Z$的支持被定义为与频繁模式挖掘类似的方式。

定义15.2.2（支持） 子序列Z的支持定义为数据库$T$={$Y_1$…$Y_n$}中包含$Z$作为子序列的序列的比例。

顺序模式挖掘问题是识别所有满足最小支持最小支持水平的子序列。

定义 15.2.3（序列模式挖掘） 给定一个序列数据库$T$={$Y_1$…$Y_n$}，确定他们的支持对于数据库$T$是至少最小支持度的所有序列。

很容易看出，这个定义与第4章关联模式挖掘的定义非常相似。最小支持值可以指定为绝对值或相对支持值。 就频繁模式挖掘而言，除非另有说明，否则将假定相对值。

Apriori-like算法被称为通用序列模式挖掘（GSP），作为序列模式挖掘的第一种算法。 就候选人如何生成和计算而言，该算法与Apriori非常相似。 事实上，许多频繁模式挖掘算法（如TreeProjection和FP-growth）在序列模式挖掘中有直接的类比。 本节仅详细介绍GSP算法。 后面的部分将概括介绍枚举树算法如何推广到顺序模式挖掘。

图15.1：GSP算法与Apriori算法有关。 鼓励读者将这种伪代码与第4章图4.2中描述的Apriori算法进行比较

GSP和Apriori算法是相似的，除了前者需要设计用于发现频繁序列而不是集合。首先候选者的长度的概念需要在连续模式挖掘中定义。这个概念需要更仔细的定义，因为序列中的单个元素是集合而不是项目，候选者的长度或频繁序列的数量等于候选者中项目的数量（不是元素）。换句话说，$k$-序列($Y_1$…$Y_r$ )是长度为$\sum_{i=1}^\infty |Y_i |$的一个序列。因此

[面包，黄油，芝士]，[芝士，鸡蛋] 包含5个项目，尽管只包含两个元素，这是因为该序列总共包含5个项目，包括两个不同元素中的“奶酪”的重复。$A(k-1)$-候选者的$k$-子序列可以通过从$k$-序列中的任何元素中移除项目而生成。 Apriori属性继续保持序列，因为$k$序列的任何$(k-1)$子序列的支持度至少等于后者的支持度。 这为候选生成和测试方法设定了阶段，同时向下关闭修剪，类似于Apriori。
GSP算法首先通过直接计算单个项目来生成所有频繁的1项目序列。这组频繁的$1$-序列由$F_1$表示。随后的迭代通过在$F_k$中连接序列模式对来构建$C_{k+1}$。由于关联序列的定义更复杂，因此关联模式挖掘的连接过程是不同的。如果从一个频繁$k$序列$S_1$中的第一个元素中删除项目与从另一个频繁序列$S_2$中的最后一个元素中删除项目所获得的序列相同，则任意一对频繁k序列$S_1$和$S_2$可以连接。
例如，两个5-序列$S_1$ =[面包，黄油，奶酪]，[奶酪，鸡蛋] 和$S_2$ =[面包，黄油]，[牛奶，奶酪，鸡蛋] 可以加入，因为从$S_1$的第一个元素中移除“Cheese”将产生与从$S_2$的最后一个元素中移除“Milk”所得到的序列相同的序列。 注意，如果$S_2$是一个5个候选元素，其中有3个元素对应于$S_2$ =[面包，黄油]，[牛奶，奶酪，鸡蛋] 。那么一个连接也可以被执行。这是因为从$S_2$中删除最后一个项目会创建一个包含2个元素和4个项目的序列，这与$S_1$完全相同。然而，在这些情况下，加入的性质会有些不同。一般情况下，$S_2$的最后一个元素是1项目集的情况需要特别处理。以下规则可用于执行连接：
1.如果$S_2$的最后一个元素是$1$项目集，则可以通过将$S_1$的最后一个元素附加到$S_1$作为单独的元素来获得加入的候选项。 例如，请考虑以下两个序列：
$S_1$=[面包，黄油，奶酪],[奶酪，鸡蛋]
$S_2$=[面包，黄油],[奶酪，鸡蛋],[牛奶]
两个序列的连接是：[面包，黄油，奶酪],[奶酪，鸡蛋],[牛奶]
2.如果$S_2$的最后一个元素不是$1$项集，而是$S_1$的最后一个元素的超集，那么可以通过用$S_1$的最后一个元素替换$S_1$的最后一个元素来获得加入的候选项。 例如，请考虑以下两个序列：
$S_1$=[面包，黄油，奶酪],[奶酪，鸡蛋]
$S_2$=[面包，黄油],[奶酪，鸡蛋，牛奶]
两个序列的连接是：[面包，黄油，奶酪],[奶酪，鸡蛋，牛奶]
Apriori连接的这些关键差异是时序复杂性和序列模式中基于集合的元素的结果。 存在用于执行连接的替代方法。 例如，另一种方法是从$S_1$和$S_2$的最后一个元素中删除一个项目，以检查结果序列是否相同。 但是，在这种情况下，可能会从同一对中生成多个候选人。例如，和,可以连接成,和中的任意一种。从$S_1$中删除第一个项目和从$S_2$中删除最后一个项目的第一个连接规则的优点是具有唯一的连接结果。 对于任何特定的联合规则，重要的是要确保候选人的详尽和不重复的生成。 正如我们后面将会看到的，可以在序列模式挖掘中引入与频繁模式枚举树类似的概念，以确保穷举和非重复候选生成。
Apriori技巧然后用于修剪违反向下关闭的序列。 这个想法是检查$C_{k + 1}$中候选者的每个$k$-子序列是否存在于$F_k$中。 对那些不满足这种封闭性财产的候选人进行剪裁。 然后针对序列数据库$T$检查频繁的$(k + 1)$ - 候选序列$C_{k + 1}$，并对支持进行计数。 支持的计数按照定义15.2.1中的子序列的概念执行。 $C_{k + 1}$中的所有频繁候选人都保留在$F_{k + 1}$中。 当在特定迭代中在$F_{k + 1}$中没有生成频繁序列时，算法终止。 算法返回在levelwise方法的不同迭代过程中生成的所有频繁序列。 GSP算法的伪代码如图15.1所示。

15.2.1 频繁序列的频繁模式

很容易看出Apriori和GSP算法在结构上相似。 这不是巧合。 频繁模式和顺序模式挖掘问题的基本结构类似。 除了支持计数方法的不同之外，普惠制和Apriori之间的主要区别在于候选人如何生成。 GSP中的连接生成是根据两个不同的情况来定义的。 这两种情况对应于候选人的时间扩展和集合扩展。

图15.2：序列模式挖掘的枚举树的等价物 正如在第四章所示，Apriori算法可以被看作枚举树算法。 在序列模式挖掘中定义一个类似的候选树也是可能的，尽管与频繁模式挖掘中的枚举树有着不同的结构。 Apriori和GSP算法之间基于连接的候选生成中的关键差异转化为顺序模式挖掘中候选树的结构和增长的差异。 一般来说，序列模式挖掘的候选树更复杂，因为它们需要适应序列的时间和集合增长。 因此，需要改变树节点候选扩展的定义。 序列S的节点可以以两种方式之一扩展到较低级别的节点：
1.逐个扩展：在这种情况下，项目被添加到序列S中的最后一个元素以创建候选模式。 因此，元素的数量不会增加。 对于要添加到$S$的最后一个元素的项目，它必须满足两个属性; （a）该项目成功扩展了候选树中$S$的父亲序列，或者是对另一个频繁序列的集合或时间扩展，以及（b）该项目必须按字典顺序晚于$S$的最后一个元素的所有项目。 正如在频繁模式挖掘中一样，项目的字典顺序需要事先确定。
2.时间延伸：具有单个项目的新元素被添加到当前序列$S$的末尾。如前面集合延伸的情况一样，可以使用$S$的父亲的任何频繁项目延伸来扩展$S$（ 条件（$a$））。 然而，添加的项目不需要按字典顺序排列，而是晚于顺序$S$的最后一个元素中的项目。
这两种扩展可以表示为等同于GSP算法中的两种连接。 在频繁模式挖掘中，节点的候选扩展是其父节点的相应频繁扩展的子集。 图15.2说明了序列模式挖掘的候选树的频繁部分的一个例子。 注意树的更大的复杂性，因为在树的每个级别上的项目的集合和时间添加。 集合扩展被标记为“S”，并且时间扩展在相应的树边缘被标记为“T”。 关于这个主题的特别有启发性的讨论可以在[243]中找到，本例以此为基础。
通过系统地进行适当的修改，可以将用于频繁模式挖掘的枚举树算法转换为顺序模式挖掘算法。这些变化说明了序贯模式挖掘中候选树的不同结构与频繁模式挖掘中的不同结构。该候选树由所有序列模式挖掘算法（如GSP和Prefix xSpan）隐式生成。由于枚举树1是描述所有频繁模式挖掘算法的通用框架，这意味着事实上所有频繁模式挖掘算法都可以修改为顺序模式挖掘场景。例如，[243]中的工作概括了Tree-Projection，并且Prefix xSpan算法推广了FP-growth。 Savasere等人的垂直格式[446]也被推广到顺序模式挖掘算法。这些算法之间的主要差异是使用各种数据结构，基于投影的重用技巧以及不同的候选树探索策略（例如广度第一或深度第一）而非计算的不同效率搜索空间大小的基本差异。候选树的大小是固定的，但修剪策略（如Apriori风格的修剪）可以缩小其大小。
基于投影的重用概念也可以扩展到顺序模式挖掘。 序列数据库$T$的投影表示$T(P)$与候选枚举树中的顺序模式$P$（如针对顺序模式挖掘所修改的）相关联。 然后，数据库中的每个序列$y \in T$按照以下规则投影到$P$：
1.序列模式$P$需要是$Y$的子序列，用于投影$Y$以包括在投影数据库$T(P)$中。
2.所有不在$P$的最后一个元素中的项目，或者$P$的父项的不成功频繁扩展（时间或集合方式）都不包含在$Y$的预测中，因为它们与计算频繁扩展无关的$P$.
3.确定$y$中作为子序列的最早时间发生的$P$。 根据这个子序列匹配，让$P$中的最后一个元素$P_r$与$y$中的元素$Y_k$匹配。 然后，$y$的投影表示的第一个元素等于$Y_k$-$P_r$中按照字典顺序晚于$P_r$中的所有项的集合。 如果生成的元素$Q$为空，那么它不包含在$y$的投影中。如果非空，这第一个元素是特殊的，因为它可能只用于计算枚举树中元素$P_r$的集合扩展，并且 因此，在其前面用下划线表示为 $Q$。
4.$Q$之后的投影序列中的其余元素对应于$y$中最后一个匹配元素$Y_k$之后临时出现的Y中的元素。所有这些元素在去除步骤2中讨论的不相关项目之后包含在$y$的投影中。剩余的这些元素 元素可用于对$P$中最后一个元素Pr的集合扩展或$P$的时间扩展进行计数。对于用于计算$P_r$的置位扩展的其余元素（除 _$Q$以外）中的任何一个， 元素已经需要包含$P_r$。
5.计划数据库$T(P)$可以用来更有效地计算$P$的频繁扩展并确定频繁扩展。 与在频繁模式挖掘中一样，可以在构建枚举树状候选结构期间以自上而下的方式连续执行此投影。 在节点上投影的数据库可以通过递归投影数据库的父级来生成。 基本方法与第4章中讨论的基于顶部投影的频繁模式挖掘算法完全类似。该算法从候选树ET开始，该候选树$ET$是在该节点处具有整个序列数据库$T$的空节点。 使用以下步骤重复该树，直到没有节点保留在$ET$中用于进一步扩展。

15.2.2 约束顺序模式挖掘

在许多情况下，对序列模式施加额外的约束，例如序列的连续元素之间的间隙的约束。一种解决方案是使用无约束的GSP算法，然后作为后处理步骤，删除所有不满足约束条件的子序列。然而，这种蛮力方法是一种非常低效的解决方案，因为约束模式的数量可能比无约束模式小几个数量级。因此，在候选生成或支持计数步骤期间将约束直接并入GSP算法显着更有效。根据约束的性质，GSP算法所需的更改可能较小或显着。在所有情况下，$F_k$的支持计数程序都需要修改。在支持计数期间显式检查约束。这减少了生成的频繁模式的数量，并且使得该过程比强力方法更有效。然而，纳入这些限制有时可能会导致开采图案向下的封闭性失效。在这种情况下，可能需要对GSP算法进行适当的更改。在不违反向下关闭属性的情况下，GSP算法可用于非常小的修改，用于支持计数期间的约束检查。
不违反向下关闭属性的一个重要约束是*maxspan*约束。 这个约束规定，子序列的第一个和最后一个元素之间的时间差不能大于*maxspan*。 因此，可以直接使用GSP算法，修改支持计数期间的约束。 因此，该方法在每个步骤中使用更小的一组子序列，并且通常比强力方法更有效。
序列模式挖掘中的另一个常见约束是最大间隙约束。 这也被称为最大间隙约束。 请注意，由于最大间隙约束，特定频繁$k$-序列的所有$(k-1)$-子序列可能无效。 这有点问题，因为Apriori原理不能有效使用。
例如，在*maxgap*值为1的情况下，合约数据库序列$a_1 a_2 a_3 a_4 a_5$不支持子序列$a_1 a_5$，因为$a1$和$a5$之间的间隔值是3。然而，在该最大值下，子序列$a_1a_3a_5$受到相同合约数据库序列的支持。因此，$a_1a_5$可能比$a_1a_3a_5$具有更低的支持。因此，Apriori修剪不能应用。 但是，通过从频繁序列的第一个或最后一个元素中删除项目而获得的序列总是频繁出现。 因此，本章讨论的基于连接的特定方法仍然可以用于在不失去任何频繁模式的情况下全面生成所有候选项。 修改后的修剪规则被使用。在检查候选修剪的$(k-1)$个子序列时，只检查包含与候选相同数量元素的子序列。换句话说，包含1个项目的元素不能从候选中删除以检查其子序列。 这样的子序列被称为连续的子序列。一个值得注意的特例是$maxgap = 0$。这种情况通常用于确定时间序列图案，在时间序列已被转换为离散序列后，使用第14章第14.4节讨论的方法。
感兴趣的另一个约束是最小间隙约束或连续元素之间的*mingap*约束。 连续元素之间的最小间隙约束将始终满足向下关闭属性。 因此，GSP方法可以用于很小的修改。 唯一的修改是在支持计数期间检查这个约束。 这产生了一组较小的子序列$F_k$。 加入和修剪步骤保持不变。 书目笔记包含指向许多其他有趣的约束，如窗口大小约束。

15.3 序列聚类

就时间序列数据而言，序列的聚类很大程度上取决于相似性的定义。 当已经定义了相似函数时，许多传统的多维方法（如$k$-medoids和基于图的方法）可以很容易地适用于序列数据。 应该指出的是，这两种方法实际上可以用于任何数据类型，并且仅取决于距离函数的选择。
序列数据的相似性度量已在第3章中定义。 用于序列数据的最常用的相似性函数如下所示：
1.基于匹配的度量：这个度量等于两个序列之间匹配位置的数量。 这只能在两个序列的长度相等的情况下有意义地计算，并且在这些位置之间存在一一对应关系。
2.动态时间扭曲（DTW）：在这种情况下，两个序列之间的非匹配数量可用于动态时间扭曲。 动态时间规整（DTW）方法在第3章第3.4.1.3节中详细讨论。其思想是动态扩展和缩小时间维度，以考虑不同系列数据生成速度的变化。
3.最长公共子序列（LCSS）：如该测量的名称所示，计算两个序列之间最长的匹配子序列。 然后这用于测量两个序列之间的相似性。 第3章第3.4.2.2节详细讨论了LCSS方法。
4.编辑距离：这被定义为将一个序列转换为另一个序列所需的编辑操作的成本。 编辑距离度量在第3章第3.4.2.1节中描述。许多比对方法（如BLAST）是专门为生物序列设计的。 这些方法的指针可以在书目注释中找到。
5.基于关键字的相似性：在这种情况下，使用$k-gram$表示，其中每个序列由一包长度为$k$的分段表示。 通过使用序列上长度为$k$的滑动窗口从原始数据序列中提取这些$k-gram$。 每个这样的$k-gram$表示新的“关键字”，并且可以根据这些关键字使用$tf-idf$表示。 如果需要，可以删除不常用的$k-gram$。 可以使用任何基于文本的矢量空间相似性度量，在第13章讨论。 由于在转换之后不再使用段的排序，所以这种方法允许使用更广泛的数据挖掘算法。 事实上，任何文本挖掘算法都可以用于这种转换。
6.基于核的相似度：基于核的相似度对于SVM分类特别有用。 第15.6.4节详细讨论了基于内核的相似性的一些例子。
不同的措施可用于不同的应用特定场景。 本章将讨论许多这些场景。

15.3.1 基于距离的方法

当已经定义了距离或相似性函数时，$k-medoids$方法可以非常简单地推广到序列数据。 $k-medoids$方法对于数据类型和相似性函数的选择是不可知的，因为它被设计为通用的爬坡方法。 事实上，第7章第7.3.1节讨论的$CLARANS$算法可以很容易地推广到任何数据类型。 该算法从数据中选择$k$个代表性序列，并使用所选择的距离（相似性）函数将每个数据点分配给它们最接近的序列。 使用爬山算法迭代地改进代表性序列的质量。
在第6章第6.4节中讨论的分层方法也可以推广到任何数据类型，因为它们处理不同数据对象之间的成对距离。使用分层方法的主要挑战是它们需要$O(n^2)$成对距离计算 在$n$个对象之间。 序列数据上的距离函数计算通常是昂贵的，因为它们需要昂贵的动态编程方法。 因此，分层方法的适用性仅限于较小的数据集。

15.3.2 基于图形的方法

基于图的方法是对基础数据类型不可知的集群通用方法。 第2章第2.2.2.9节描述了将不同数据类型转换为相似图。基于图的方法的更广泛的方法如下：
1.构建一个图，其中每个节点对应一个数据对象。 每个节点连接到它的$k$个最近的邻居，权重等于相应的数据对象之间的相似度。 在使用距离函数的情况下，它将转换为相似度函数，如下所示：
$<span><span class="MathJax_Preview">w_{ij}=e^{-d(O_i,O_j)^2/t^2} \tag{15.1}</span><script type="math/tex">w_{ij}=e^{-d(O_i,O_j)^2/t^2} \tag{15.1}$
这里$d(O_i,O_j)$表示对象$O_i$和$O_j$之间的距离，并且$t$是参数。
2.假定边缘是无向的，并且通过放下其中一条边来去除任何平行边缘。 由于假设距离函数是对称的，所以平行边具有相同的权重。
3.3.第19章第19.3节中讨论的任何聚类或社区检测算法都可用于聚类新创建图的节点。
节点聚集后，可以使用节点和数据对象之间的对应关系将这些聚类映射回数据对象的聚类。

15.3.3 基于子序列的聚类

上述方法的主要问题在于它们基于使用序列之间全局比对的相似性函数。 对于更长的序列，由于长序列对之间计算相似性的噪音影响，全局比对变得越来越无效。 即使两个序列的大部分是相似的，许多序列的局部部分都是嘈杂的并且与相似性计算无关。 一种可能性是设计局部对齐相似度函数或使用前面讨论的基于关键字的相似性方法。
更直接的方法是使用频繁的基于子序列的聚类方法。 一些相关的方法也使用从序列中提取的$k-gram$而不是频繁的子序列。然而，$k-gram$通常比频繁的子序列对噪声更敏感。 这个想法是，频繁的子序列代表了不同序列中常见的关键结构特征。 在确定了频繁的子序列之后，可以将原始序列转换到这个新的特征空间中，并且可以根据这些新特征来创建“袋 - 词”表示。 然后，序列对象可以像任何文本聚类算法一样进行聚类。 总体方法可以描述如下：
1.使用任何频繁序列模式挖掘算法从序列数据库$D$中确定频繁子序列$F$. 不同的应用可能会因序列上的特定约束条件而有所不同，例如所确定序列的最小或最大长度。
2.根据适当的选择标准从频繁子序列$F$中确定子集$F_S$。 通常，应该选择频繁子序列的子集，以便最大化覆盖范围并最小化冗余。 这个想法是仅使用适量的相关特征来进行聚类。 例如，频繁汇总子序列（FSS）的概念用于确定序列的缩合组[505]。 书目注释包含了这些方法的特定指针。
3.将数据库中的每个序列表示为来自$F_S$的“频繁子序列包”。 换句话说，一个序列的变换表示包含它所包含的所有来自$F_S$的频繁子序列。
4.在序列数据库的这个新表示上应用任何文本聚类算法。 文本聚类算法在第13章讨论。$tf-idf$加权可以应用于不同的特征，如第13章所讨论的。

图15.3：简化的CLUSEQ算法 前面提到的讨论忽视了以序列为基础的集群的观点，尽管各个步骤是通过不同的方法以不同的方式实施的。 不同算法之间的关键差异在于特征构造方法和文本聚类算法的选择。 $CONTOUR$方法[505]使用两级分级聚类，在第一步中生成细粒度微簇。 然后，这些微簇被聚集成更高级别的簇。 书目注释包含指向此框架的特定实例的指针。

15.3.4 概率聚类

概率聚类方法基于生成原理，即给定序列中的符号是通过与之前的符号之间的统计相关性定义的概率生成的。 这是基于马尔可夫模型的一般原理。 因此，使用该群内符号的生成概率来计算序列和群之间的相似度。 在簇和序列之间定义了相似性函数之后，可以使用它来创建基于距离的算法。$ CLUSEQ$算法基于这个原理。

15.3.4.1 基于马尔可夫相似度的算法：CLUSEQ

聚类序列（CLUSEQ）算法基于马尔可夫模型的更广泛的原理。 马尔可夫模型用于定义序列和聚类之间的相似性函数。 *CLUSEQ*算法可以被认为是基于相似性的迭代分割算法。 虽然传统的分区算法通过多次迭代来确定聚类的数量，但*CLUSEQ*并非如此。 *CLUSEQ*算法仅从一个群集开始。 在每次迭代中添加包含单独序列的精心控制数量的新簇，并且在认为旧簇与现有簇过于相似时删除旧簇。 群集数量的初始增长很快，但在算法过程中会减慢。 甚至有可能在后面的迭代中缩小集群的数量。 这种方法的一个优点是算法可以自动确定簇的自然数。
*CLUSEQ*算法不使用群集数量作为输入参数，而是使用相似度阈值$t$。 如果一个序列与集群的相似度超过阈值$t$，则会将序列分配给一个集群。 只要相似度大于$t$，序列就可以分配给任意数量的聚类（或不聚类）。*CLUSEQ*算法有三个主要步骤，分别对应于添加新的簇，将序列分配给簇，以及消除簇。 迭代地重复这些步骤直到聚类结果没有变化。 图15.3描述了*CLUSEQ*算法的简化版本。 以下提供了各个步骤的详细说明。
1.集群添加：添加的集群数量为$k·f$，其中$k$是最后一次迭代结束时的集群数量。 $f$的值在（0,1）的范围内，计算如下。 假设$k_a$是在前一次迭代中添加的聚类数量，并且令$k_r$是因为在先前迭代中消除重叠聚类而移除的聚类数量。 然后，$f$的值计算如下：
$<span><span class="MathJax_Preview">f=\frac{max(k_a-k_r,0)}{k_a} \tag{15.2}</span><script type="math/tex">f=\frac{max(k_a-k_r,0)}{k_a} \tag{15.2}$
这样做的基本原理是，当算法达到其“自然”数量的群集时，消除将占主导地位。 在这种情况下，f将会很小或为零，并且需要添加很少的新簇。 另一方面，如果当前的聚类数量明显低于数据中“自然”数量的聚类数量，则f的值应该接近于1。在之前的迭代中，添加的聚类数量要大得多 而不是被删除的集群数量，从而导致快速增长。
创建的新群集是单身群集。 选择现有簇和相互之间尽可能不同的序列。 因此需要在每个非聚类序列和其他聚类/非聚类序列之间计算成对相似度。 因为计算聚类和所有非聚类序列之间的成对相似性可能是昂贵的，所以使用非聚类序列的样本来限制新种子选择的范围。 稍后将描述计算相似性的方法。
2.对簇的序列分配：序列被分配给与簇的相似度大于用户指定的阈值t的簇。 原始的$CLUSEQ$算法也提供了调整阈值t的方法，尽管本章中的描述仅提供了算法的简化版本，其中t由用户固定和指定。 给定的序列可以分配给多个群集，也可以保持未分配给任何群集。 实际相似性计算使用马尔可夫相似性度量来执行。 这一措施将在稍后介绍。
3.聚类消除：由于将序列分配给多个聚类，因此许多聚类高度重叠。 希望限制这种重叠以减少聚类中的冗余。 如果特定群集唯一的序列数量小于预定阈值，则会消除这样的群集。
4.唯一需要描述的步骤是计算序列和聚类之间的马尔可夫相似性度量。 这个想法是，如果符号$S = s_1s_2 ... s_n$的序列与聚类$C_i$相似，那么使用聚类内符号的条件分布来生成$S$应该是“容易的”。 那么，概率$P（S | C_i）$定义如下：
$<span><span class="MathJax_Preview">P(S|C_i) = P(s_1|C_i)·P(s_2|s_1,C_i)...P(s_n|s_1 ...s_{n−1},C_i) \tag{15.3}</span><script type="math/tex">P(S|C_i) = P(s_1|C_i)·P(s_2|s_1,C_i)...P(s_n|s_1 ...s_{n−1},C_i) \tag{15.3}$
这是簇$C_i$的序列$S$的生成概率。 直观上，项$P（s_j | s_1 ... s_{j-1}，C_i）$表示$s_j$跟随在群$C_i$中的$s_1 ... s_{j-1}$的次数的分数。 这个术语可以用$C_i$中的序列以数据驱动的方式进行估计。
当一个簇与一个序列高度相似时，这个值会很高。 可以通过与序列生成模型进行比较来计算相对相似性，在所述序列生成模型中，所有符号均随其全部数据集中的存在成比例地随机生成。这种随机生成的概率由$\prod_{j=1}^n P(s_j)$给出，其中$P(s_j)$被估计为包含符号$s_j$的序列的分数。 那么，$S$与簇$C_i$的相似度被定义为：
$<span><span class="MathJax_Preview">sim(S,C_i)=\frac{P(S|C_i)}{\prod_{j=1}^n P(s_j)} \tag{15.4}</span><script type="math/tex">sim(S,C_i)=\frac{P(S|C_i)}{\prod_{j=1}^n P(s_j)} \tag{15.4}$
一个问题是序列$S$的许多部分可能是嘈杂的，并且与簇很好地匹配。 因此，相似度被计算为$S$到$C_i$的任何连续片段的最大相似度。 换句话说，如果$S_{kl}$是从位置$k$到$l$的$S$的连续片段，则最终相似度$SIM(S，C_i)$计算如下：
$<span><span class="MathJax_Preview">SIM(S,C_i) = max_{1≤k≤l≤n}sim(S_{kl},C_i) \tag{15.5}</span><script type="math/tex">SIM(S,C_i) = max_{1≤k≤l≤n}sim(S_{kl},C_i) \tag{15.5}$
最大相似度值可以通过计算所有对$[k，l]$上的$sim(S_{kl}，C_i)$来计算。 这是用于将序列分配给其相关群集的相似性值。
一个有问题的问题是，公式15.3右侧的每个项$P(s_j | s_1 ... s_{j-1}，C_i)$的计算可能需要检查簇$C_i$中的所有序列以进行概率估计目的。
幸运的是，这些术语可以用一种数据结构来高效地估计，这个数据结构被称为概率性树。 无论何时创建新簇或将序列添加到簇中，*CLUSEQ*算法总是动态维护概率性树（PST）。 这个数据结构将在15.4.1.1节详细描述。

15.3.4.2 隐马尔可夫模型的混合

这种方法可以被认为是第6章第6.5节中讨论的概率模型的字符串模拟，用于聚类多维数据。 回想一下，在这种情况下使用生成混合模型，其中混合的每个分量具有高斯分布。 然而，高斯分布仅适用于生成数字数据，并且不适合于生成序列。 一个好的序列生成模型被称为隐马尔可夫模型（HMM）。 本节的讨论将假定使用HMM作为黑盒子。 HMM的实际细节将在后面的章节中讨论。 正如我们将在15.5节后面看到的，HMM本身可以被认为是一种混合模式，其中状态表示混合物的相关组分。 因此，这种方法可以被认为是一个两级混合模型。 本节中的讨论应与第15.5节中对HMM的描述结合起来，以提供基于HMM聚类的完整图像。
基于混合的生成模型的基本原理是假设数据是由$k$个分布的混合产生的，概率分布为$G_1 ... G_k$，其中每个$G_i$都是一个隐马尔可夫模型。 如第6章第6.5节所述，该方法假定对混合物的不同组分使用先验概率$α_1...α_k$。因此，生成过程描述如下：
1.以概率$α_i$选择$k$个概率分布之一，其中$i \in {1 ... k}$。 让我们假设第r一个被选中。
2.从$G_r$生成一个序列，其中$G_r$是一个隐马尔可夫模型。
混合模型的一个很好的特点是数据类型和相应混合分布的变化不会影响算法的更广泛的框架。 在序列数据的情况下，可以应用类似的步骤，因为它们应用于多维数据。 令$S_j$表示第$j$个序列，$Θ$是为不同HMMs估计的整套参数。 然后，E-步骤和M-步骤与多维混合模型的情况完全相似。
1.（E步）给定训练HMM和先验$α_i$的当前状态，使用HMM生成概率$P(S_j | G_i，Θ)$确定每个序列$S_j$的后验概率$P(G_i | S_j，Θ)$ 来自第$i$个HMM的$S_j$，以及与Bayes规则相关的先验$α_1...α_k$。 这是序列$S_j$由第$i$个HMM生成的后验概率。
2.（M步）给定数据点分配给簇的当前概率，使用每个HMM上的$Baum-Welch$算法来学习它的参数。 分配概率被用作平均估计参数的权重。$ Baum-Welch$ 算法在本章15.5.4节中描述。 估计每个$α_i$的值与群集$i$的所有序列的平均分配概率成比例。 因此，M步骤导致整个参数集合$θ$的估计。
请注意，这里使用的步骤与第6章第6.5节中用于混合建模的步骤几乎完全对应。此方法的主要缺点是它可能相当慢。 这是因为训练每个HMM的过程在计算上是昂贵的。

15.4 序列中的异常值检测

序列数据中的异常值检测与时间序列数据共享许多相似之处。 序列数据和时间序列数据之间的主要差异是序列数据是离散的，而时间序列数据是连续的。 前一章的讨论表明时间序列异常值可以是点异常值，也可以是异常值。 由于序列数据是时间序列数据的离散模拟，因此可以将相同的原理应用于序列数据。 序列数据异常值可以是位置异常值或组合异常值。
1.位置异常值：在基于位置的异常值中，特定位置的值由模型预测。 这用于确定与模型的偏差并将特定位置预测为异常值。通常，马尔可夫方法用于预测性外部检测。 这类似于使用回归模型在时间序列数据中发现的基于偏差的异常值。 与回归模型不同，马尔可夫模型更适合离散数据。 这些异常值被称为上下文异常值，因为它们在其临近时间邻域内是异常值。
2.组合异常值：在组合异常值中，由于其中的符号组合，整个测试序列被认为是不常见的。 这可能是这种情况，因为这种组合可能很少出现在序列数据库中，或者它与大多数其他类似大小的序列的距离（或相似性）可能非常大（或小）。 更复杂的模型，例如隐马尔可夫模型，也可以用于根据生成概率对存在频率进行建模。 对于较长的测试序列，从其中提取较小的子序列进行测试，然后将整个序列的异常值分数预测为这些值的组合。 这类似于确定时间序列数据中不寻常的形状。 这些异常值被称为集合异常值，因为它们是通过组合来自多个数据项的模式来定义的。
以下部分将讨论这些不同类型的异常值。

15.4.1 位置异常值

在上一章中讨论的连续时间序列数据的情况下，通过确定时间戳期望值的显着偏差，设计了一类重要的异常值。 因此，这些方法密切结合了预测和偏差检测的问题。 类似的原理适用于离散序列数据，其中可以使用不同的模型预测特定时间戳的离散位置。 当一个头寸与其预测值匹配的可能性非常低时，它被视为异常值。 例如，考虑一种$RFID$应用，其中事件序列通过使用来自$RFID$标签的语义提取而与超级市场中的产品项目相关联。 正常事件序列的典型例子如下：
放置在架子上，从架子上取下，结账，退出商店
另一方面，在商店举行的场景中，事件序列可能异常不同。 行窃场景中的事件序列示例如下：
放置在架子上，从架子上取下，退出商店
显然，序列符号*退出商店*在第二种情况下是异常的，但在第一种情况下不是。 这是因为它没有描述第二种情况下该位置的预期值或预测值。 期望根据预期值检测这种异常位置。 这种异常位置可能出现在序列中的任何位置，而不一定在最后一个元素中，如前述示例中所示。 位置异常检测的基本问题定义如下：
定义 15.4.1 给定一组N个训练序列$D= T_1 ... T_N$和测试序列$V = a_1 ... a_n$，根据测试序列的期望值确定测试序列中的位置$a_i$是否应被视为异常。
有些公式没有明确区分训练和测试序列。 这是因为一个序列可以用于模型构建和非常长的异常值分析。
典型地，位置$a_i$可以仅在来自$a_i$之前的位置的时间域中进行预测，而在其他领域中，诸如生物数据，两个方向可能是相关的。 下面的讨论将假定时间情景，尽管通过检查位置两侧的窗口来简化放置场景（如生物数据）。
正如连续流的回归建模使用过去历史的小窗口一样，离散序列预测也使用符号的小窗口。 假设一个位置上的值的预测取决于这个短的历史。 这被称为离散序列的短记忆性质，并且它通常适用于各种各样的时态应用领域。
定义15.4.2(短记忆性) 对于符号序列$V = a_1 ... a_i ...$，概率$P(a_i | a_1 ... a_{i-1})$的值被$P(a_i | a_{i-k} ... a_{i-1})$为一些小的$k$值。
在估计$P(a_i | a_{i-k} ... a_{i-1})$的值之后，如果测试序列中的位置基于从训练导出的模型具有非常低的概率，则可以将其作为异常值序列。 或者，如果以非常高的概率预测不同的符号（测试序列中存在的符号），那么可以将该位置作为异常值加以扰动。
本节将讨论马尔可夫模型用于位置异常值检测问题。 该模型利用序列的短记忆属性将序列明确地建模为马尔可夫链中的一组状态。 这些模型使用字母$\sum$上定义的马尔可夫链中的转换来表示序列生成过程。 这是一种特殊的有限状态自动机，其中状态由生成的序列的短（前一个）历史定义。 这些模型对应于一组状态$A$，它们表示关于系统事件的不同种类的内存。例如，在一阶马尔科夫模型中，每个状态代表序列中生成的字母$\sum$中的最后一个符号。 在第$k$阶马尔可夫模型中，每个状态对应于序列中最后$k$个符号$a_{n-k} ... a_{n-1}$的子序列。 这个模型中的每个转变都表示一个事件$a_n$，从状态$a_{n-k} ... a_{n-1}$到状态$a_{n-k+1} ... a_n$的转移概率由条件概率$P(a_n | a_{n -k} ... a_{n-1})$。
马尔可夫模型可以描述为一组代表状态的节点和一组边代表引起从一种状态向另一状态移动的事件。可能性提供了相应事件的条件概率。 很明显，模型的顺序编码了为建模过程保留的字符串段的内存长度。 一阶模型对应于最少的保留内存量。
为了理解马尔可夫模型如何工作，先前使用 $RFID$标签跟踪物品的例子将会被重新讨论。 执行项目的动作可以被看作是在字母表上绘制的序列 $\sum = {P，R，C，E}$。 这些符号中的每一个的语义含义如图15.4所示。$k$ 阶马尔可夫模型的状态对应于在字母表 $\sum = {P，R，C，E}$上绘制的序列的前$k$个（动作）符号。
图15.4说明了不同状态以及转换的例子。 图中显示了一阶和二阶模型。 图中还显示了边缘转换概率。 这些通常是从训练数据中估算出来的。 这两个模型都标出了与盗窃行为异常相对应的转换。 在每种情况下，值得注意的是，实际的入店行为事件的相应转换概率非常低。 这是一个特别简单的例子，其中一个事件的记忆足以完全表示物品的状态。 一般情况并非如此。 例如，考虑其中马尔科夫模型对应于用户访问的网页序列的网络日志的情况。 在这种情况下，访问的下一个网页的概率分布不仅取决于访问的最后一页，而且取决于用户以前的其他访问。

图15.4：基于RFID的偷窃异常的马尔科夫模型

从图15.4可以看出，二阶模型中的状态数量大于一阶模型中的状态数量。这不是巧合。尽管这只能提供一个上限，但在$k$序模型中可能存在$|\sum|^k$个状态。 许多对应于这些状态的子序列可能不会出现在训练数据中，或者可能在特定应用中无效。 例如，在图15.4的例子中，一个$PP$状态将是无效的，因为同一个物品不能在货架上顺序放置两次而没有至少移除一次。 至少在理论层面上，高阶模型更精确地表示复杂系统。 然而，选择更高阶的模型会降低效率，也可能导致过度配合。
#### 15.4.1.1 效率问题：概率后缀树 从前面几节的讨论可以明显看出，马尔可夫和基于规则的模型是等价的，后者是前者的一种更简单和易于理解的启发式近似。尽管如此，对于这两种模型，共同的挑战在于，长度为$k$的可能先导的数目可能大到$|\Sigma|^k$。当搜索文本序列$a_{i-k}...a_{i-1}$来决定概率$P(a_i|a_{i-k}... a_{i-1})$时，这个挑战会使得两种方法的速度很慢。实时计算这些值，或者甚至在它们没有合适组织时检索它们的预计算值，这样的代价是高昂的。概率后缀树（PST）为检索这种预先计算的值提供了一种有效的方法。概率后缀树的效用不仅仅局限于异常值检测，也适用于聚类和分类。例如，CLUSEQ算法，在15.3.4.1中使用PST，可以检索这些预先存储的概率值.

后缀树是一种经典的数据结构，用于存储给定数据库中的所有子序列。概率后缀树表示该结构的一般化，该结构还存储给定序列数据库的下一个符号的生成的条件概率。对于k阶马尔可夫模型，深度至多为k的后缀树将存储第k阶马尔可夫模型所需的所有条件概率值，包括所有低阶马尔可夫模型的条件。因此，这样的结构也编码变阶马尔可夫模型所需的所有信息。一个关键的挑战是，这样的后缀树节点的数量可以大到$\sum_{i=0}^{k}{|\Sigma|^i}$，这是一个需要使用选择性修剪解决的问题。

概率后缀树是代表序列不同后缀的分层数据结构。深度为$k$的树中的节点表示长度为$k$的后缀，因此用长度为$k$的序列标记。节点$a_{i-k}...a_{i}$的父节点对应于序列$a_{i-k+1}...a_{i-1}$。后者是通过从前者中删除第一个符号而获得的。每条边都标有需要删除的符号，以便在父节点处派生序列。因此，树中的路径对应于相同序列的后缀。每个节点还保持一个表示概率的向量Σ，其对应在这个后缀的条件下，于从$\Sigma={\sigma_1...\sigma_{|\Sigma|}}$生成任何符号的条件概率因此，对于与序列$a_{i-k}...a_{i}$对应的节点,并且对于每一个$j\in\{1...|\Sigma|\}$每个值$P(\sigma_j|a_{i-k}...a_{i})$被保存下来。如前所述，一旦后面的序列已经被观察到，这对应于$\sigma_j$紧接在$a_{i-k}...a_{i}$之后出现的条件概率。这提供了对确定位置异常值至关重要的生成概率。需要注意，这种生成概率对其他算法也很有用，例如本章前面讨论的CLUSEQ算法

图15.5展示了符号集$\Sigma=\{X,Y\}$的后缀树的一个例子。与符号$X$和$Y$中的任一个对应的每个节点处的两个可能的符号生成概率被放置在相应的节点旁边。同样明显的是，深度$k$的概率后缀树将马尔可夫模型的所有转移概率编码至$k$阶。因此，这种方法可用于高阶马尔可夫模型。

概率后缀树被显着修剪以改善其紧凑性。例如，对应于原始数据中非常低计数的后缀可以从考虑中删减。此外，可以考虑将其潜在序列的生成概率低的节点修剪。 序列$a_1...a_n$的生成概率近似如下： $<span><span class="MathJax_Preview">P(a_1...a_n)=P(a_1)\cdot P(a_2|a_1)...P(a_n|a_1...a_{n-1})\tag{15.6}</span><script type="math/tex">P(a_1...a_n)=P(a_1)\cdot P(a_2|a_1)...P(a_n|a_1...a_{n-1})\tag{15.6}$

对于阶数$k<n$的马尔可夫模型，上式中的$P(a_r|a_1...a_{r-1})$的值通过$P(a_r|a_{r-k}...a_{r-1})$近似,应用于小于$r$的任何$k$值。创建马尔可夫$k$阶或更小的模型，没有必要保留树深度大于$k$的部分。

考虑序列$a_1...a_i...a_n$，其中期望测试位置$a_i$是否位置异常。然后，期望确定$P(a_i|a_1...a_{i-1})$。后缀$a_1...a_{i-1}$可能不存在于后缀树中，因为它可能已被考虑修剪。在这种情况下，短记忆属性用于确定后缀树中存在的最长后缀$a_j...a_{i-1}$，并可估计估计相应的概率$P(a_i|a_j...a_{i-1})$。因此，概率后缀树提供了一种有效的方法来存储和检索相关的概率。后缀树中，包含非零概率估计概率$P(a_i|a_j...a_{i-1})$的最长路径的长度也提供了这种特定事件序列的稀有程度的思路。后缀树中只包含短路径的位置更可能是异常值。因此，可以通过多种方式从后缀树中定义异常值分数：

1. 如果与位置相对应的（修剪后的）后缀树中只存在短路径长度$a_i$及其之前的历史，那么该位置更可能是异常值。

2. 对于位置$P(a_i|a_j...a_{i-1})$的后缀树中确实存在的长度为$1...r$的路径，可以基于不同顺序的模型使用组合分数。在某些情况下，只有低阶分数才会合并。 一般来说，低阶分数的使用是可取的，因为它们通常在训练数据中更具鲁棒性。

15.4.2 组合异常值

在组合异常值中，目标是确定序列中不正常的符号组合。考虑一个集合，其中提供了一组训练序列以及一个测试序列。基于训练序列中的“正常”模式，需要确定测试序列是否是异常的。 在很多情况下，测试序列可能会很长。因此，全序列中符号的组合对于训练序列可以是唯一的。这意味着很难根据全序列表征“正常”序列。因此，为了比较，从训练和测试序列中提取小窗口。通常，所有的窗口（包括重叠的窗口）都是从序列中提取的，尽管也可以使用不重叠的窗口。这些被称为比较单位。针对这些比较单位定义了异常分数。因此，报告了序列中不寻常的窗口。以下讨论将专注于确定这种不寻常的窗口。一些符号和定义将用于区分训练数据库，测试序列和比较单位。

1. 训练数据库由$\cal{D}$表示，并且包含由$T_1...T_N$表示的序列。

2. 测试序列用$V$表示。

3. 比较单位$U_1...U_r$表示。通常，每个$U_i$都来自$V$的小的连续窗口。 在依赖于域的情况下，$U_1...U_r$可以由用户提供。

该模型可以是基于距离的或基于频率的或可以是隐马尔可夫模型。这些将在随后的章节中讨论。由于隐马尔可夫模型是用于聚类，分类和异常检测等不同问题的一般构造，因此它们将在本节紧接着的章节中讨论。

15.4.2.1 基于距离的模型

在基于距离的模型中，比较单元的绝对距离（或相似度）被计算为训练序列的等效窗口。训练序列中第$k$个最近邻窗口的距离用于确定异常分数。在序列数据的背景下，许多接近函数是相似函数而不是距离函数。在前一种情况下，较高的值表示较大的接近度。计算一对序列之间相似性的一些常用方法如下：

1. 简单匹配系数：这是可能的最简单的函数，并确定两个长度相等的序列之间匹配位置的数量。这也等于一对序列之间的汉明距离。

2. 归一化最长公共子序列：最长公共子序列可以被认为是两个有序集合之间余弦距离的序列模拟。假设$T_1$和$T_2$为两个序列，并且$T_1$和$T_2$之间的（未标准化的）最长公共子序列的长度由$L(T_1,T_2)$表示。未规范化的最长公共子序列可以使用章节3中3.4.2讨论的方法进行计算。然后，归一化最长公共子序列的值$NL(T_1,T_2)$，通过以与无序集合之间的余弦计算类似的方式，将$L(T_1,T_2)$与基础序列长度归一化来计算： $<span><span class="MathJax_Preview">NL(T_1,T_2)=\frac {L(T_1,T_2)} {\sqrt{|T_1|}\cdot\sqrt{|T_2|}}\tag{15.7}</span><script type="math/tex">NL(T_1,T_2)=\frac {L(T_1,T_2)} {\sqrt{|T_1|}\cdot\sqrt{|T_2|}}\tag{15.7}$

这种方法的优点是它可以匹配两个不相等长度的序列。缺点是计算过程相对较慢。

1. 编辑距离：编辑距离是用于序列匹配的最常见的相似函数之一。这个相似性函数在第3章讨论过。此函数通过将一个序列转换为另一个序列所需的最少编辑次数来测量两个序列之间的距离。编辑距离的计算在计算上可能非常昂贵。

2. 基于压缩的不相似性：这种测量基于信息论的原理。令$W$为训练数据的窗口， $W\bigoplus U_i$为表示$W$和$U_i$级联的字符串。设$DL(S)<|S|$为对任意字符串$S$应用标准压缩算法之后的描述长度。然后，如下定义基于压缩的相异性$CD(W,U_i)$：

$$CD(W,U_i)=\frac {DL(W\bigoplus U_i)} {DL(W)+DL(U_i)}\tag{15.8}$$

此度量始终位于范围$(0,1)$内，较低的值表示较大的相似度。这种方法背后的直觉是，当两个序列非常相似时，组合序列的描述长度将远小于描述长度总和的描述长度。另一方面，当序列非常不相似时，组合字符串的描述长度将与描述长度的总和几乎相同。

为了计算比较单元$U_i$相对于$T_1...T_N$中的训练序列的异常分数，第一步是从$T_1...T_N$取相等的窗口作为比较单元的大小。第$k$个最近的相邻距离被用作该窗口的异常分数。可能会报告不寻常的窗口，或来自不同的分数窗口可能会合并为一个异常分数。

15.4.2.2 基于频率的模型

基于频率的模型通常与用户指定的特定于域的比较单元一起使用。在这种情况下，需要在训练序列和测试序列中测量比较单元的相对频率，并且相应地确定惊奇水平。
当用户指定比较单位时，确定异常分数的一种自然方式是在训练和测试模式中测试比较单元$U_j$的频率。例如，当序列包含黑客攻击尝试时，如登录和密码事件序列，与训练序列相比，该序列在测试序列中的频率要高得多。用户对这些相关比较单元的指定为异常值分析应用程序提供了非常有用的领域知识。
假设$f(T,U_j)$表示比较单元$U_j$在序列$T$中出现的次数。由于频率$f(T,U_j)$取决于$T$的长度，所以可以通过将频率除以序列的长度来获得归一化频率$\hat{f}(T,U_j)$
$<span><span class="MathJax_Preview">\hat{f}(T,U_j)=\frac {f(T,U_j)} {|T|}</span><script type="math/tex">\hat{f}(T,U_j)=\frac {f(T,U_j)} {|T|}$
然后，通过从测试序列中减去训练序列的相对频率来定义训练序列$T_i$相对于测试序列$V$的异常分数。因此，异常评分$A(T_i,V,U_j)$定义如下：

$<span><span class="MathJax_Preview">A(T_i,V,U_j)=\hat{f}(V,U_j)-\hat{f}(T_i,U_j)</span><script type="math/tex">A(T_i,V,U_j)=\hat{f}(V,U_j)-\hat{f}(T_i,U_j)$

这些分数的平均值的绝对值是在数据库中${\cal{D}}=T_1...T_N$的所有序列中计算的。这代表最终的异常评分。 此方法的一个有用输出是用户指定的比较单元的最具异常性的特定子集。这为分析师提供了关于为什么特定测试序列应被视为异常的内涵知识和反馈。称为TARZAN的方法使用后缀树表示来有效地确定测试序列和训练序列之间的比较意义上的所有异常子序列。读者可以参考书目注释来获取这种方法的指针。 ​

15.5 隐马尔科夫模型

隐马尔可夫模型（HMM）是概率模型，它通过马尔可夫链中状态之间的一系列转换产生序列。使用隐马尔可夫模型用于聚类，分类和异常值检测。因此，这些模型在序列分析中的适用性非常广泛。例如，15.3.4.2 中的聚类方法，使用隐马尔可夫模型作为子程序。本节将使用异常值检测作为HMM的特定应用来促进理解。在15.6.5中，将显示HMM如何用于分类。

那么隐马尔可夫模型如何不同于本章前面介绍的马尔可夫技术？本章前面介绍的马尔可夫技术中的每个状态都很好定义，并且基于序列的最后$k$个位置。这种状态对用户也是直接可见的，因为它是由最新的长度为$k$的序列组合定义的。因此，就特定输入字符串的状态和序列位置之间的对应而言，马尔可夫模型的生成行为始终是确定性地已知的。

在隐马尔可夫模型中，系统的状态是隐藏的，不能直接被用户看到。对于用户来说只有（通常）离散观察序列是由每次转换后状态的符号发射产生的。生成的符号序列对应于应用程序特定的序列数据。在许多情况下，可以根据对底层系统行为的了解，在建模过程中定义这些状态，尽管分析人员可能不知道过渡的精确顺序。 这就是为什么这些模型被称为“隐藏”。

HMM中的每个状态与符号 $\Sigma$上的一组发射概率相关联。换句话说，访问状态$j$将导致以概率 $\theta^j(\sigma_i)$发射符号$\sigma_i\in\Sigma$之一。相应地，HMM中的一系列转换对应于观察的数据序列。 隐马尔可夫模型可以被认为是第一章讨论过的类型的一种混合模型，如第6章所讲，其中混合物的不同成分不是彼此独立的，而是通过顺序过渡相关的。因此，每个状态都类似于第6章讨论的多维混合模型中的一个成分。由该模型生成的每个符号类似于由多维混合模型生成的数据点。此外，与多维混合模型不同，连续生成单个数据项（序列符号）也不是彼此独立的。这是一个事实的自然结果，即发射数据项的连续状态使用概率转换相互依赖。与多维混合模型不同，隐马尔可夫模型是为具有时间相关性的顺序数据而设计的。

为了更好地解释隐马尔可夫模型，一个说明性的例子将用于使用HMM进行异常检测的具体问题。 考虑一组学生注册一门课程，并根据每个每周任务中收到的成绩生成一个序列。该等级来自符$\Sigma=\{A,B\}$。分析师创建的模型是个班级，包含两类学生，执行者或懒惰者，在任何时候都具有不同年级等级生成概率。 一个处于执行者状态的学生有时可能会转变为懒惰状态，反之亦然。这些代表了系统中的两个状态。每周家庭作业分配给每个学生，并用$\Sigma$中的一个符号进行评分。这会为每个学生产生一系列的成绩，并且它是分析师唯一可观察的输出。学生的状态只代表分析师为解释等级序列而创建的模型，因此它本身是不可观察的。理解这一点很重要，如果这个模型对真正的成绩生成过程反映不佳，那么它会影响学习过程的质量。

假设一个处于工作状态的学生很可能在每周任务中获得A等级，其概率为80％，B为20％概率。对于懒虫来说，这些概率值颠倒过来。虽然这些概率在这里为了说明的目的而明确地指出，但是它们需要从所观察到的不同学生的等级序列中学习或估计，并且不是先验的。分析师在任何特定时间都不知道给定周内任何学生的确切状态（状态）。实际上，这些等级序列是分析师唯一可观察的输出。因此，从分析师的角度来看，这是一个隐马尔可夫模型，它根据未知的状态序列生成等级序列，代表学生的状态转换。状态之间的精确转换顺序只能针对特定的观察序列进行估计。

上述例子的双态隐马尔可夫模型如图15.6所示。这个模型包含两个状态，用doer和slacker表示，表示一个学生在某一周的状态。一个学生可能每个星期从一个州过渡到另一个州，尽管可能性很低。假设一组初始状态概率决定了行为者和懒散者的先验分布。这种分布代表了学生参加课程时的先验理解。 从这个模型生成的典型序列的一些例子，以及它们的稀有程度如图15.6所示。例如，序列**AAABAAAABAAAA**很可能是通用的，由持续处于执行状态的学生进行，并且序列**BBBBABBBABBBB**是最可能由一直处于懒惰状态的学生产生。第二个序列通常比第一个序列更稀少，因为人口大多包含实施者。序列**AAABAAABBABBB**对应于最终转变为懒散者的执行者。这种情况更为罕见，因为它需要从执行者状态转换为懒惰状态，其概率非常低。**ABABABABABABA**序列极其异常，因为它不表示时间上一致的行为者或懒惰者的行为模型。相应地，这样的序列对模型的可能性非常低。 马尔科夫模型中的更多状态可以用来编码更复杂的场景。可以使用描述不同生成场景的状态对域知识进行编码。在前面讨论过的例子中，考虑一下这样的情况，即实施者有时会在短时间内懈怠，然后回到其平常状态。或者懒虫有时可能会暂时被启发成为实施者，但最终可能会回到他们最擅长的领域。 这种情节将导致序列的局部部分与剩余序列不同。这些情景可以用图15.7所示的四状态马尔可夫模型来捕捉。状态数量越多，可以捕获的情景就越复杂。当然，需要更多的训练数据来学习这种模型的（大量的）参数，否则这可能导致过度。对于较小的数据集，转换概率和符号生成概率不能准确估计。

15.5.1 隐马尔科夫模型的正式定义和方法

在本节中，隐马尔可夫模型将与相关的训练方法一起正式引入。假定隐马尔可夫模型包含由 $\{s_i...s_n\}$表示的$n$个状态。用来表示从中生成观测值的符号集为$\Sigma=\{\sigma_1...\sigma_{|\Sigma|}\}$。这些符号是通过一系列状态转换从模型生成的。每次访问某个状态（包括自我转换）都会生成一个符号，该符号从$\Sigma$上的分类概率分布中抽取。符号发射分布对每个状态都是特定的。由状态$s_j$生成的符号$\sigma_i$的概率$P(\sigma_i|s_j)$由$\theta^j(\sigma_i)$表示。从状态$s_i$到$s_j$的转换概率由$p_{ij}$表示。对于$n$个不同的状态，初始状态概率由$\pi_1...\pi_n$表示。模型的拓扑结构可以表示为网络$G=(M,A)$，其中$M$是状态集合$\{s_i...s_n\}$。集合$A$表示这些状态之间可能的转换。在最常见的情况下，如果模型的体系结构具有特定领域的理解，则集合$A$不是完整的网络。在特定于领域的知识不可用的情况下，集合$A$可以对应于完整的网络，包括自我转换。 训练HMM模型的目标是从训练数据库$\{T_1...T_N\}$中学习初始状态概率，转移概率和符号发射概率。通常在创建和使用隐马尔可夫模型时使用三种方法：

• 训练：给定一组训练序列$T_1...T_N$，用期望最大化算法估计模型参数，如初始概率，转移概率和符号发射概率。Baum-Welch算法用于此目的。

• 评估：给定测试序列$V$（或比较单元$U_i$），确定它对HMM的概率。这用于确定异常分数。递归转发算法用于计算。

• 说明：给定测试序列$V$，确定生成此测试序列的最可能的状态序列。这有助于理解为什么序列应被视为异常（在异常值检测中）或属于特定类别（在数据分类中）。这个想法是各状态对应于对底层系统的直观理解。 在图15.6的例子中，知道一个观察到的序列是一个异常是有用的，由于学生在执行者和懒惰者之间的异常振荡。这可以提供理解系统状态的内涵知识。这个最可能的状态序列是用维特比算法计算的。

由于训练过程的描述依赖于为评估方法而开发的方法思路，因此我们将偏离演示的自然顺序并提供最后的训练算法。评估和说明方法将假定模型参数（如转换概率）已经可以从训练阶段获得。

15.5.2 评估：计算观察序列的拟合概率

确定序列$V=a_1...a_m$的拟合概率的一种方法将是计算HMM中的所有状态（路径）的所有$n^m$个可能的序列，并计算每个，基于观察到的序列，符号生成概率和转移概率。 这些值的总和可以作为拟合概率报告。显然，这种方法不切合实际，因为它需要列举指数级的可能性。

认识到$r$个符号（和第$r$个状态的固定值）的拟合概率可以用第$r-1$个可观测符号（和固定$r-1$状态）递归计算出来，这样做能使计算极大简化。具体来说，令$\alpha _r(V,s_j)$是由模型$V$中前$r$个符号生成的概率，并且序列中的最后一个状态为$s_j$。 然后，递归计算如下：

$$\alpha_r(V,s_j)=\sum_{i=1}^n\alpha_{r-1}(V,s_i)\cdot p_{ij}\cdot\theta^j(a_r)$$

这种方法递归地总结了不同倒数第二个节点的所有n个不同路径的概率。 上述关系迭代应用于$r=1...m$。第一符号的概率计算为$\alpha _1(V,s_j)=\pi_{j}\cdot\theta^j(a_1)$，用于初始化递归。 这种方法需要时间复杂度为$O(n^2\cdot m)$。然后，通过将所有可能状态$s_j$上的$\alpha_m(V,s_j)$的值相加来计算整体概率。 因此，最终$F(V)$计算如下：

$$F(V)=\sum_{j=1}^n\alpha_m(V,s_j)$$

该算法也被称为前向算法。请注意，拟合概率可直接应用于许多问题，如分类和异常检测，具体取决于HMM是以监督还是非监督的方式构建的。通过为每个类别构建单独的HMM，可以为测试序列测试更好的类别。拟合概率在诸如数据聚类，分类和异常值检测等问题中很有用。在数据聚类和分类中，通过创建特定于组的HMM，可以使用拟合概率来模拟属于聚类或类的序列的概率。 在异常值检测中，可以确定关于全局HMM的不良序列，并将其报告为异常。

15.5.3 说明：确定观察序列的最可能状态序列

许多数据挖掘问题的目标之一是为数据的序列部分（例如类或簇）提供解释，或者不提供整个数据集（例如异常值）。由于（隐藏）生成状态序列通常为观察序列提供直观解释，有时需要确定观察序列的最可能状态序列。维特比算法提供了一种有效的方法来确定最可能的状态序列。

确定测试序列$V=a_1...a_m$的最可能状态路径的一种方法将是计算HMM中的所有状态（路径）的所有$n^m$个可能的序列，并且计算基于观察到的序列，符号生成概率和转移概率，计算它们中的每一个的概率。这些值的最大值可以报告为最可能的路径。请注意，这与拟合概率类似，除了需要在所有可能的路径上确定最大拟合概率，而不是拟合概率之和。相应地，也可以使用与前一种情况类似的递归方法来确定最可能的状态序列。

最佳状态路径的任何子路径对于生成相应的符号子序列也必须是最优的。这个属性在序列选择优化问题的背景下通常会启用动态编程方法。用于生成前$r$符号（第$r$个状态固定为$j$）的最佳状态路径可以递归根据前$r-1$个可观察符号和不同倒数第二个状态的相应最佳路径计算。具体来说，令$\delta_r(V,s_j)$表示最好的概率状态序列，用于在$V$中生成前$r$符号并且也以状态$j$结束。 然后，递归计算如下：

$$\delta_r(V,s_j)=MAX_{i=1}^n\delta_{r-1}(V,s_i)\cdot p_{ij}\cdot\theta^j(a_r)$$

这种方法递归地计算不同倒数第二个节点的所有$n$个不同路径的概率的最大值。 该方法迭代应用于$r=1...m$。第一个概率$\delta_1(V,s_j)=\pi_j\cdot\theta^j(a_1)$被确定为用于初始化递归。这种方法时间复杂度为$O(n^2\cdot m)$，通过使用所有可能状态$s_j$上$\delta_m(V,s_j)$的最大值，可以计算出最佳路径。这种方法本质上是一种动态编程算法。在学生成绩的异常例子中，维特比算法会发现执行者和懒惰者之间的振荡是异常行为。在聚类应用中，执行者状态的一致性将解释勤奋学生这个聚类。

15.5.4 训练：Baum-Welch算法

学习HMM参数的问题非常困难，并且没有已知的算法可以保证全局最优。然而，在大多数情况下，选项可用于确定合理有效的解决方案。Baum-Welch算法就是这样一种方法。它也被称为前向-后向算法，它是EM方法在生成隐马尔可夫模型中的应用。首先，提供单个序列$T=a_1...a_m$进行训练的说明。然后，将讨论对$N$个序列$T_1...T_N$的直接推广。

设$\alpha_r(T,s_j)$为模型中长度为$m$序列$T$中的前$r$个符号的前向概率，并且序列中的最后一个符号是$s_j$。假设$\beta_r(T,s_j)$是该模型生成的序列中不包含第$r$个位置的部分的后向概率，条件是第$r$位置的状态为$s_j$。因此，前向和后向概率定义是不对称的。前向和后向概率可以通过模型概率来计算，其方式类似于前面章节15.5.2中讨论的评估过程。后向概率的主要不同是计算从序列尾部向后的方向开始。此外，在递归的底部，概率值$\beta_{|T|}(T,s_j)$被初始化为1以说明两个定义中的差异。下面需要定义两个额外的概率量来描述EM算法：

• $\psi_r(T,s_i,s_j)$：序列$T$中第$r$个位置对应于状态$s_i$，第$r+1$个位置对应于$s_j$的概率。

• $\gamma_r(T,s_i)​$：序列$T​$中的第$r​$个位置对应于状态$s_i​$的概率。

EM过程从随机初始化模型参数开始，然后从模型参数迭代估计$\alpha(\cdot),\beta(\cdot),\psi(\cdot),\gamma(\cdot)$，反之亦然。具体来说，EM程序的迭代执行步骤如下：

• （E-步骤）根据模型参数$\pi(\cdot),\theta(\cdot),p..$ 的当前估计值估计$\alpha(\cdot),\beta(\cdot),\psi(\cdot),\gamma(\cdot)$

• （M-步骤）根据当前估计值$\alpha(\cdot),\beta(\cdot),\psi(\cdot),\gamma(\cdot)$估计模型参数$\pi(\cdot),\theta(\cdot),p..$

现在解释如何执行上述每个估计。$\alpha(\cdot)$和$\beta(\cdot)$的值可以分别使用前向和后向程序进行估计。转发过程已在评估部分中描述，后向过程类似于转发过程，不同之处在于它从序列末尾开始反向工作。$\psi_r(T,s_i,s_j)$的值等$\alpha_r(T,s_i)\cdot p_{ij}\cdot\theta^j(a_{r+1})\cdot\beta_{r+1}(T,s_j)$，因为序列生成过程可以分为三个部分，分别对应于直到位置$r$，第$r+1$个符号的产生和第$r+1$个符号之后的部分。通过确保不同组合$[i,j]$上的和为1， 概率向量$\psi_r(T,s_i,s_j)$的估计值被归一化。概率向量$\gamma_r(T,s_i)$是通过将概率向量$\psi_r(T,s_i,s_j)$的值相加估计得到，其中$i$的值固定，$j$的值在变化。这完成了E步骤的描述。

M-步骤中模型参数的重新估算公式相对简单。设$I(a_r,\sigma_k)$为二元指示函数，当两个符号相同时取值为1，否则为0。然后，估算可以按如下方式进行：

$$\pi(j)=\gamma_1(T,s_j),p_{ij}=\frac {\sum_{r=1}^{m-1}\psi_r(T,s_i,s_j)} {\sum_{r=1}^{m-1}\gamma_r(T,s_i)} \\ \theta^i(\sigma_k)=\frac {\sum_{r=1}^{m}I(a_r,\sigma_k)\cdot\gamma_r(T,s_i)} {\sum_{r=1}^{m}\gamma_r(T,s_i)}$$

根据期望最大化原则，这些估计的详细推导可以在[327]中找到。这完成了对M-步骤的描述

与所有EM方法一样，该过程迭代应用于收敛。通过对每个序列应用步骤，并在每个步骤中平均相应的模型参数，该方法可以容易地推广到N个序列。

15.5.5 应用

隐马尔可夫模型可用于各种序列挖掘问题，如聚类，分类和异常检测。HMM在聚类中的应用已经在15.3.4.2介绍过。分类的应用将在本章15.6.5中介绍。 因此，本节将重点讨论异常检测问题。

理论上讲，一旦从序列数据库${\cal{D}}=T_1...T_N$构建了训练模型，就可以直接为测试序列V计算异常分数。然而，随着测试序列长度的增加，这种模型的鲁棒性会因维数灾难而增加的噪声而减弱。因此，比较单元（或者从测试序列中提取或者由领域专家指定）被用于计算序列的窗口的异常分数。然后，不同窗口的异常分数可以通过使用简单函数组合在一起，例如将序列中的异常窗口单元的数量以序列。

一些方法也使用测试序列上的维特比算法来挖掘最可能的状态序列。在某些领域，用状态序列而不是可观测序列来确定异常更容易。此外，状态序列部分的低转换概率提供了可观察序列的异常位置。缺点是最可能的状态序列可能与观察序列匹配的概率非常低。因此，当估计的状态序列用于异常检测时，估计的异常可能不会反映数据中的真正异常。维特比算法的实际效用是用可直观理解的状态来解释序列的异常行为，而不是异常分数量化。

15.6 序列分类

假设由$S_i...S_N$表示的一组$N$个序列可用于构建训练模型。这些序列中的每一个都用从$\{1...k\}$中选择一个作为类标签。此训练数据用于构建一个模型，该模型可预测未知测试序列的标签。由于时间序列和离散序列的暂态性质，许多建模技术，例如最近邻分类器，基于规则的方法和基于图的方法，对于这两类序列分类都很常用。

15.6.1 最近邻分类器

最近的分类器经常用于不同的数据类型，包括离散序列数据。关于多维数据的最近邻分类器的基本描述可在章节10.8中找到。对于离散序列数据，主要差异在于用于最近邻分类的相似性函数。关于离散序列的相似函数在3.4.1和3.4.2中有讨论到。基本方法与多维数据相同。对于任何测试实例，确定训练数据中的k个最近邻居。来自这些最近邻居的主要的标签被作为测试实例的相关标签。k的最优值可以通过使用一次性交叉验证来确定。该方法的有效性对距离函数的选择非常敏感。主要问题是序列中存在噪声部分会引起全局相似函数。一种常见的方法是使用基于关键字的相似性，其中从字符串中提取n元模型以创建向量空间表示。最近邻居（或任何其他）类别可以用这种表示来构造。

15.6.2 基于图的方法

这种方法是一种半监督算法，因为它将训练和测试实例中的知识结合起来进行分类。此外，该方法是直接的，因为测试实例的样本外分类通常是不可能的。训练和测试实例必须同时指定。在章节11.6.3中介绍了用于半监督分类的相似图的使用。基于图的方法可以被看作是可以用于任何数据类型的通用半监督元算法。基本方法从训练和测试实例中构建相似度图。构造图$G=(V,A)$，其中$V$中的节点对应于训练和测试实例中的每一个。$G$中的节点的子集被标记。这些对应于训练数据中的实例，而未标记的节点对应于测试数据中的实例。$V$中的每个节点都连接到它的k个最近的邻居，并且在A中具有无向边。使用3.4.1和3.4.2中讨论的任何距离函数来计算相似度。在生成的网络中，节点的一个子集被标记，其余节点未标记。然后使用3.4.1和3.4.2中的节点的指定标签来预测它们未知的节点的标签。这个问题被称为聚集分类。许多集体分类的方法在19.4讨论。然后将节点上的派生标签映射回数据对象。与最近邻分类法一样，该方法的有效性对用于构建图的距离函数的选择很敏感。

15.6 基于规则的方法

序列分类中的一个主要挑战是序列的许多部分可能很嘈杂，与类别标签不相关。在一些情况下，两个符号的短格式可能与分类有关，而在其他情况下，许多符号的较长格式可能对分类有区别性。在某些情况下，判别模式甚至可能不会连续发生。这个问题是在时间序列分类的背景下讨论的,见14.7.2.1。 但是，我们可以使用二值化将离散序列转换成二进制时间序列序列。这些二进制时间序列可以转换为多维小波表示。这在章节2.2.2.6中有详细，此处为了完整而重复描述。

第一步是将离散序列转换为一组（二进制）时间序列，其中该组中的时间序列的数量等于不同符号的数量。第二步是使用小波变换将每个时间序列映射到多维向量中。最后，将来自不同系列的功能组合起来创建一个单一的多维记录。 在这个多维表示上我们构造基于规则的分类器构造。

要将序列转换为二进制时间序列，可以创建一个二进制字符串，其中每个位置值表示某个特定符号是否存在于某个位置。例如，考虑在四个符号上绘制的以下核苷酸序列：

$$ACACACTGTGACTG$$

该序列可以分别转换为对应于符号A，C，T和G的以下四个二进制时间序列集合 $$ 10101000001000\ 01010100000100\ 00000010100010\ 00000001010001\ $$

可以将小波变换应用于这些系列中的每一个以创建多维特征集。来自四个不同系列的特征可以被附加以创建单个数字多维记录。在获得多维表示后，可以使用任何基于规则的分类器。 因此，数据分类的整体方法如下：

1.如上所述，生成$N$个序列中的每一个的小波表示以创建$N$个数字多维表示。

1. 离散化小波表示以创建时间序列小波变换的分类表示。因此，每个分类属性值表示小波系数的数值范围。

2. 使用10.4中描述的任何基于规则的分类器生成一组规则。左侧的图案表示由左侧的小波系数组合定义的不同粒度的图案。

当规则集已经生成时，它可以用来对任意测试序列进行分类，方法是首先将测试序列转换为相同的基于小波的数字多维表示。此表示法与激励规则一起使用来执行分类.这些方法在10.4讨论。不难看出，这种方法是基于规则的时间序列分类的离散版本，如14.7.2.1所示。

15.6.4 内核支持向量机

内核支持向量机可以使用训练和测试实例之间的内核相似性来构造分类器。如10.6.4所示，只要任何一对数据对象之间的基于内核的相似度$K(Y_i,Y_j)$可用，核心支持向量机就不需要记录的特征值。在这种情况下，这些数据对象是字符串。不同种类的内核在字符串分类中非常流行。

15.6.4.1 词袋核

在词袋（BOG）核中，字符串被视为一包字母，频率等于字符串中每种类型的字母数量。这可以被看作是一个字符串的向量空间表示。请注意，文本文档也是一个字符串字母大小等于词典。因此，变换$\Phi(\cdot)$可以被视为几乎等价于文本文档的向量空间变换。如果$\overline{V(Y_i)}$是向量空间表示的字符串，则内核相似度等于相应向量空间表示之间的点积。 $$ \begin{eqnarray*} &&\Phi(Y_i)=\overline{V(Y_i)}\ &&K(Y_i,Y_j)=\Phi(Y_i)\cdot\Phi(Y_j)=\overline{V(Y_i)}\cdot\overline{V(Y_j)} \end{eqnarray*} $$

内核的主要缺点是它丢失了字母之间的所有定位信息。对于字母大小较大的情况，这可能是一种有效的方法一个例子是文本，其中字母（词典）大小为几十万字。但是，对于较小的字母大小，信息丢失对于产生的分类器有用而言可能太重要。

15.6.4.2 频谱核

词袋中的内核会丢失字符串中的所有顺序信息。谱内核通过从字符串中提取k-mers并使用它们构造向量空间表示来解决此问题。最简单的谱内核从字符串中提取所有k-mers并从它们中构建向量空间表示。例如，考虑在字母表$\Sigma=\{A,C,T,G\}$上构造的字符串$ATGCGATGG$。然后，$k=3$的相应频谱表示如下：

$$ATG(2), TGC(1), GCG(1), CGA(1), GAT(1), TGG(1)$$

括号中的值对应于向量空间表示中的频率。这对应于用于定义内核相似性的特征映射$\Phi(\cdot)$。

通过添加不匹配邻到内核域可以进一步增强谱内核。因此，我们不添加仅提取的k-mers到特征地图,而是添加所有与k-mer不匹度为$m$的的k-mers。例如，在$m=1$的不匹配级别，对于ATG的每个实例，以下k-mers被添加到特征映射中：

$$CTG, GTG, TTG, ACG, AAG, AGG, ATC, ATA, ATT$$

对k-mer中的每个元素重复该过程，并将每个邻域元素添加到特征映射中。 在这个扩展的特征映射$\Phi(\cdot)$上作点积。添加不匹配的基本原理是在相似度计算中允许有一些噪音。词袋内核可以被看作$k=1$且没有不匹配的谱内核的特例。频谱内核可以使用字典树或后缀树数据结构进行高效计算。 在书目注释中提供了指向这种高效计算方法的指导。频谱内核的一个优点是，即使两个字符串的长度变化很大，它们也可以以直观的方式计算两个字符串之间的相似度。

15.6.4.3 加权度核

前两种内核方法直接明确定义了特征映射$\Phi(\cdot)$，很大程度上忽略了不同k-mers之间的排序。加权度内核直接定义$K(Y_i,Y_j)$，而不明确定义特征映射$\Phi(\cdot)$。这种方法本着充分利用内核方法的精神。考虑两个长度相同的字符串$Y_i$和$Y_j$。设$KMER(Y_i,r,k)$表示从位置$r$开始从$Y_i$提取的k-mer。然后，加权度内核计算内核相似度，作为完全相应位置上两个字符串中最大指定长度的k-mers完美匹配的次数。因此，与频谱内核不同，使用不同长度的k-mers，并且特定长度$s$的贡献由系数$\beta_s$加权。换句话说，阶$k$的加权度核被定义如下：

$$K(Y_i,Y_j)=\sum_{s=1}^k\beta_s\sum_{r=1}^{n-s+1}I(KMER(Y_i,r,s)=KMER(Y_j,r,s))\tag{15.9}$$

这里，$I(\cdot)$是一个指标函数，在匹配的情况下取值为1，否则为0。加权度核在光谱核上的一个缺点是它需要两个字符串$Y_i$和$Y_j$长度相等。这可以通过允许匹配过程中的变化来部分解决。在书目注释中可以找到指向这些增强功能的指示。

15.6.5 概率方法：隐马尔可夫模型

隐马尔可夫模型是在序列分析中用于各种任务中的重要工具。它已经在本章前面的章节15.3.4.2和15.5中介绍过了，即如何利用隐马尔可夫模型进行聚类和异常值检测。在本节中，将利用隐马尔可夫模型进行序列分类。事实上， HMM最常见的用途是分类问题。HMM在计算生物学中非常流行，它们用于蛋白质分类。

使用HMM进行分类的基本方法是为数据中的每个类创建单独的HMM。因此，如果总共有$k$个类，这将导致$k$个不同的隐马尔可夫模型。在15.5.4介绍的Baum-Welch算法，可用于训练每个类别的HMM。对于一个给定的测试序列，对应匹配的每个$k$模型是使用15.5.2中描述的方法确定的。最好的匹配类将作为相关的类。用HMM进行训练和测试的整体方法可以描述如下：

1. （训练）使用15.5.4的Baum-Welch算法。为每个k类构造一个单独的HMM模型。

2. （测试）对于一个给定的测试序列Y，使用15.5.2中讨论的评估方法，确定序相对k个不同的隐马尔可夫模型的匹配概率。将相应具有最高匹配概率HMM的类别，作为测试序列的分类。

这种基本方法的许多变体已经被用来实现有效性和有效性之间不同的折中。书目注释包含了一些这些方法的建议。

15.7 总结

离散序列挖掘与时间序列数据挖掘密切相关，就像分类数据挖掘与数字数据挖掘紧密相关。因此，许多算法在两个域中非常相似。离散序列挖掘的工作起源于计算生物学领域，其中DNA链编码为字符串。

序列模式挖掘问题从序列数据库中发现频繁序列。用于频繁序列挖掘的GSP算法是基于Apriori方法的。由于这两个问题之间的密切关系，大多数频繁模式挖掘算法可以相对直接的推广到离散序列挖掘。

许多用于多维聚类的方法可以推广到序列聚类，只要能够在序列之间定义有效相似性函数即可。 例子包括k-medoids方法，分层方法和基于图的方法。一系列有趣的工作将序列转换为k-gram袋。文本聚类算法应用于这种表示。另外，还开发了一些专门的方法，例如CLUSEQ。概率方法使用隐马尔可夫模型的混合来进行序列聚类。

序列数据的异常值分析与时间序列数据的异常值分析类似。位置异常值使用马尔可夫模型进行概率预测。组合离群值可以使用基于距离的，基于频率的或隐马尔可夫的模型来确定。隐马尔可夫模型是用于序列分析的非常通用的工具，并且经常用于各种数据挖掘任务。HMM可以被看作混合模型，其中混合物的每个状态依次依赖于之前的状态。

许多来自多维分类的技术可以适应离散序列分类。这些包括最近邻方法，基于图的方法，基于规则的方法，隐马尔可夫模型和内核支持向量机。许多字符串内核已被设计用于更有效的序列分类。

15.8 书目注释

序列挖掘问题已经在计算生物学中被广泛研究。Guseld[244]的经典着作从计算生物学的角度对序列挖掘算法进行了很好的介绍。本书还包含了对字符串，树和图的其他重要相似度度量的优秀调查报告。在本文中详细讨论了字符串索引。[283，432]研究了时间序列相似性的转换规则的使用。这种规则可以用来为连续时间序列创建编辑类似距离的度量。字符串编辑距离的方法在[438]中提出。在[141]中已经表明，$L_p$范数如何与编辑距离相结合。最长的公共子序列问题的算法可以在[77,92,270,280]中找到。这些算法的研究可以在[92]中找到。许多时间序列和序列相似性的其他测量可以在[32]中找到。 时间序列和离散序列相似性度量在第3章详细讨，也可在Gunopulos和Das[241]的早期教程中找到。 在生物学数据的背景下，BLAST系统[73]是最受欢迎的对比工具之一。

在[59]中首先提出了挖掘序列模式的问题。 同样的工作也提出了GSP算法。 GSP算法是Apriori算法的直接修改。由于两个模型之间的关系，最频繁的模式挖掘问题可以扩展到顺序模式挖掘。随后，第4章中讨论的大多数关于频繁模式挖掘的算法。已经推广到顺序模式挖掘。Savasere等人的垂直数据结构[446]已被推广到SPADE[535]，而FP-增长算法已被推广到PrexSpan[421]。 TreeProjection算法也被推广到序列模式挖掘[243]。PrexSpan和基于TreeProjection的方法，都基于将数据库投影与使用枚举树探索候选搜索空间相结合。本章的描述是对这两部相关着作的简单而笼统的描述[243,421]。 在[224,346]中讨论了发现基于约束的序列的方法。最近一项关于序列模式挖掘的调查可以在[392]中找到。

序列数据聚类问题已被广泛研究。关于聚类序列数据的详细调查，在生物学领域中，可以在[32]中找到。CLUSEQ算法在[523]中有详细描述。CLUSEQ使用的概率后缀树将在同一工作中讨论。在[242]中提出了最早的基于频繁序列的聚类方法。[505]中提出了用于频繁序列挖掘的CONTOUR方法。该方法使用频繁序列挖掘和微聚类的组合来从序列创建聚类。[474]中讨论了使用隐马尔可夫模型进行离散序列聚类。一般来说，关于时间异常值检测问题已经完成了大量的工作，特别是离散序列。关于时间异常值检测的一般研究可以在[237]中找到。该书[5]包含关于时间和离散序列异常值检测的章节。[132]中介绍了一个关于离散序列异常检测的调查。在[387,525]中讨论了两种使用马尔可夫技术来寻找位置异常值的熟知技术。出于分析目的，组合离群值通常使用窗口技术，其中比较单元从序列中提取出来[211,274]。 在[311]中提出了基于压缩的相似度的信息论测量。[310]中讨论了基于频率的方法来确定比较单位的惊奇水平。本文提出的TARZAN算法使用后缀树进行有效的计算。关于隐马尔可夫模型的综合研究可以在[327]中找到。

研究[33,516]中详细讨论了序列分类问题。在[51]中提出了使用小波方法进行序列分类。[85]中提供了用于SVM分类的各种字符串内核的描述。在[327]中讨论了使用隐马尔可夫模型进行字符串分类。

15.9 习题

1. 考虑序列$ABCDDCBA$，以字母表$\Sigma=\{A,B,C,D\}$定义。计算长度为1的所有k-mers的向量空间表示以及长度为2的所有k-mers的向量空间表示。对序列$CCCCDDDD$重复该过程.

2. 实现序列模式挖掘的GSP算法。

3. 考虑顺序模式挖掘问题的一个特例，其中元素总是单例项目。（a）GSP算法和（b）基于候选树的算法会有什么样的变化。

4. 讨论k-medoids的普遍性和基于图的方法对任意数据类型的聚类。

5. 本章介绍了一些用于SVM分类的字符串内核。讨论一些可以使用字符串内核实现的其他数据挖掘应用程序。

6. 讨论发现序列数据中位置异常值的马尔可夫模型之间的相似性和差异，以及用于发现时间序列数据中的异常点的自回归模型。

7. 编写一个计算机程序，使用GSP确定来自集合的所有最大频繁子序列。 实现一个程序，以向量空间表示的形式在这些子序列中表达数据库中的序列。 在这个表示上实现一个k-means算法。

8. 编写一个计算机程序，使用1阶马尔可夫模型来确定位置异常值。

9. 考虑离散序列$ACGTACGTACGTACGTATGT$。构建一个1阶马尔可夫模型来确定位置离群值。哪些位置被视为异常值？

10. 对于练习9的离散序列，确定长度为2的所有子序列。使用基于频率的方法将组合离群值分数分配给子序列。 哪些子序列应该被视为组合异常值？

11. 编写一个计算机程序来学习隐马尔可夫模型的状态转换和符号发射概率。 使用练习9的顺序执行程序。

12. 计算练习1中两个序列之间的内核相似度，使用bag-of-words内核和一个长度为2的序列的内核。

13. 长度至多为$k$的可能连续模式的最大数量是多少，其中字母表大小是$\Sigma$。 将此与频繁模式挖掘进行比较，哪个更大？

14. 假设跑道上运动员的速度概率取决于天气是冷的，中等的还是热的。因此，运动员进行分级为快（F），慢（S）或平均（A）的比赛。某一天的天气概率取决于前一天的天气。假设你以一串字符串形式表现了运动员连续几天的表现，例如$FSFAAF$。建立一个隐藏的马尔可夫模型，解释运动员的表现，而不用了解当天的天气情况。