至今已经有很多种序列模式被提出，包括周期模式^[1]、偏序模式^[2]、闭合模式^[3]、对比序列模式^[4]、频繁序列模式^[5]等。对比序列模式挖掘作为数据挖掘中重要的一个问题，目前已经积累了大量的研究成果^[6-7]。对比序列模式是指在一类数据集中频繁出现，而在另一类数据集中很少出现的序列模式。对比序列模式可以描述不同数据集之间的差异，在很多领域有广泛应用。例如，对比序列模式可以用于纳税人行为分析^[8]，患者的风险预测^[9]等。在对比序列模式挖掘中，Top-k对比序列模式挖掘是一种重要的挖掘策略。Top-k方法是指在给定的标准下挖掘出差异最大的k个模式的方法。该方法被广泛应用在关联规则^[10]、序列规则^[11]、相关模式^[12]和序列模式^[7]等领域中。但是，在Top-k策略挖掘结果中依然存在冗余的问题。针对这一问题，本文提出了挖掘去冗余Top-k对比序列模式集合的方法。

1 相关工作

对比序列模式挖掘主要包括基于阈值的对比序列模式挖掘和Top-k对比序列模式挖掘两个研究方向。基于阈值的对比序列模式挖掘的目标是找出所有满足给定阈值的模式。最直接挖掘对比序列模式的方法是枚举所有的序列模式，然后统计它们在每个类别上的频率。很明显这种方法的效率太低，不能满足实际应用的需求。Chan等^[13]于2003年提出一种基于后缀树的挖掘对比序列模式的算法(emerging substrings mining，ESM)。与朴素的挖掘算法相比，ESM提高了一定的效率。Ji等^[14]于2007年定义了MDS (minimal distinguishing subsequence) 的概念，并提出了相应的挖掘算法，即ConSGapMiner (contrast sequences with gap miner)算法。ConSGapMiner是比较经典的对比序列模式挖掘算法，它能以较快的效率挖掘出对比序列模式。但是MDS定义的对比序列模式在正例集中大于一个固定的阈值，在反例集中小于一个固定阈值，这种定义可能使一些有意义的模式没有被挖掘出来。2010年Deng等^[15]在ConSGapMiner的基础上利用F-ratio作为对比度；2011年Yu等^[16]提出了TSEPsMiner算法；TSEPsMiner利用GrowthRate作为对比度，而且将这个对比度应用在了挖掘对比序列模式的算法中；2014年Wang等^[17]提出用gd-DSPMiner算法来解决MDS定义中存在的问题。在不明确数据的差异程度时，使用基于阈值的对比序列模式挖掘难以挖掘出预期的序列模式。在这种情况下，Top-k对比序列模式挖掘是一个可行的办法。Top-k算法不用设定对比度的阈值，只需要设置想要挖掘模式的数目。杨皓等^[7]于2015年提出了新的Top-k挖掘算法，即kDSP-Miner(Top-k distinguishing sequential patterns with gap constraint miner)算法。但是kDSP-Miner并没有考虑冗余问题，kDSP-Miner挖掘出的序列模式可能会有大量的冗余。

2 问题定义

对于一个给定的数据集 $D$ ，它由两部分组成，分别是 ${D_ + }$ 和 ${D_ - }$ 。其中， ${D_ + }$ 是正例集， ${D_ - }$ 是反例集。数据集 $D$ 由多个序列组成。对于每个序列 $S$ ，有 $S = {e_1},{e_2}, \cdots ,{e_n}$ 。其中 ${e_i}$ 称为组成序列 $S$ 的元素。用 ${\rm{len}}(S)$ 来表示序列 $S$ 的长度，即 $S$ 中包含元素的数目。用 $S[i]$ 表示序列 $S$ 第 $i$ 个位置的元素 ${e_i}$ 。由数据集D中所有的元素组成的集合称为字母表，用符号 $\Sigma $ 表示。对于给定的两个序列 $S$ 和 $S'$ ，若存在一组整数 $1 \leqslant {k_1} < {k_2} < \cdots < {k_m} \leqslant {\rm{len}}(S)$ ，使得对于任意的 $i \in [1,{\rm{len}}(S')]$ ，都有 $S'[i] = S[{k_i}]$ ，则称 $S$ 是 $S'$ 的超序列， $S'$ 是 $S$ 的子序列。

例1　对于序列， $S = \{ A,C,G,T,C,A\} $ ， $S' = \{ C,G, $ $T\} $ ，存在一组整数 ${k_1} = 2$ ， ${k_2} = 3$ ， ${k_3} = 4$ ，使得 $S[{k_1}] = $ $ S'[1],S[{k_2}] = S'[2],S[{k_3}] = S'[3]$ ，所以 $S'$ 是 $S$ 的子序列，记作 $S' \subseteq S$ 。给定数据集 $D$ ，序列 $P$ 在数据集 $D$ 中的支持度由式(1)来定义：

${\rm{Sup}}(P,D) = \frac{{\left| {\left\{ {S \in D|P \subseteq S} \right\}} \right|}}{{\left| D \right|}}$

(1)

式中 $\left| D \right|$ 表示数据集 $D$ 中包含序列的个数。

定义1　(对比度)对于给定的数据集 $D$ ， $D$ 由正例集 ${D_ + }$ 和反例集 ${D_ - }$ 组成。序列 $P$ 的对比度定义为

${\rm{CR}}(P,{D_ + },{D_ - }) = {\rm{Sup}}(P,{D_ + }) - {\rm{Sup}}(P,{D_ - })$

例2　对于表1中给出的DNA数据集， $\left| {{D_ + }} \right| = 6,$ $\left| {{D_ - }} \right| = 4$ 。令序列 $P = \left\{ {A,G,T} \right\}$ ，有 ${\rm{Sup}}(P,{D_ + }) = 1,{\rm {Sup}}$ $(P,D_-) =0.25$ 。 ${\rm{CR}}(P,{D_ + },{D_ - }) = {\rm{Sup}}(P,{D_ + }) - {\rm{Sup}},$ (P,D_–),CR (P) = 0.75。对于一个给定的数据集 $D$ ，如果序列 $P$ 满足 ${\rm{CR}}(P,{D_ + },{D_ - }) > 0$ ，则称 $P$ 是一个对比序列模式。

定义2　(Top-k对比序列模式)给定正例集 ${D_ + }$ 和反例集 ${D_ - }$ ，在所有的对比序列模式中,对比度最大的前k个序列模式称为Top-k对比序列模式。

Top-k对比序列模式挖掘的目标是找出给定数据集中对比度最大的k个序列模式。

例3　在表1的数据集中，令 $k = 5$ ,则找出的Top-k对比序列模式见表2所示。

定义3　(冗余对比序列模式) 对于两个给定的对比序列模式 $P$ 和 $P'$ ，如果满足：

1) $P'$ 是的 $P$ 子序列，即 $P' \subseteq P$ ；

2) ${\rm{CR}}(P',{D_ + },{D_ - }) \geqslant {\rm{CR}}(P,{D_ + },{D_ - })$ ；则称模式 $P$ 是冗余对比序列模式。

表2的对比序列模式中， $\{ G,T\} \subseteq \{ G,T,A\} $ ，且 ${\rm{CR}}(\{ G,T\} ,{D_ + },{D_ - }) \geqslant {\rm{CR}}(\{ G,T,A\} ,{D_ + },{D_ - })$ ，所以模式 $\{ G,T,A\} $ 是相对于 $\{ G,T\} $ 的冗余对比序列模式。

定义4　(去冗余Top-k对比序列模式)集合L满足Top-k对比序列模式集合的要求，同时对于每个序列 ${r_a} \! \in \! L$ ，不存在 ${r_b} \! \notin \! L \! \wedge \! {r_b} \! \subseteq \! {r_a} \! \wedge \! {\rm{CR}}({r_b},{D_ + },{D_ - }) \! \geqslant$ $ {\rm{CR}}({r_a},{D_ + },{D_ - })$ ；对于任意序列 ${r_a} \in L$ ， ${r_c} \in L$ ， ${r_a}$ 不是相对于 ${r_c}$ 的冗余对比序列模式。

例4　在表1的数据集中，令 $k = 5$ ，则找出的去冗余Top-k对比序列模式如表3所示。

本文中常用的符号及定义总结在表4中。

3 算法设计

为了挖掘去冗余Top-k对比序列模式的集合，用本文提出的BFM和PBFM算法，来解决挖掘出的结果集合的冗余问题。BFM和PBFM算法基于广度优先生成树的原理来寻找Top-k序列的集合，树的生成过程就是Top-k集合的更新过程。相比于使用深度优先的方法来生成树结构，使用广度优先的方法每次更新时不改变Top-k集合的大小，所以不会出现冗余的Top-k集合。

3.1 广度优先的生成树算法

1) 根据给定的数据集 $D$ ，生成字母表 $\Sigma $ 。

2) 创建Top-k集合L，设置集合 $L$ 的最小对比度阈值 $\min {\rm{TopkCR}} = 0$ 。

3) 创建一个队列，将字母表中的每个元素放入队列中。

4) 对于队列的第一个元素，在其末尾分别与字母表中的每个元素连接，形成新的序列。

5) 计算每个新的序列P的支持度和对比度，如果 ${\rm{Sup}}(P,{D_ + }) \geqslant \min {\rm{TopkCR}}$ ，将P放入队列中，否则不放入队列中。

当 $\left| L \right| < k$ 时，在集合L中寻找序列P的子序列，若未找到子序列，将P加入集合L；若找到了子序列P，且P相对于P′不是冗余序列，则将P加入集合L，并更新集合 $L$ 的最小对比度阈值 $\min {\rm{TopkCR}}$ (若 ${\rm{CR}}(P,{D_ + },{D_ - }) \leqslant \min {\rm{TopkCR}}$ ，则min TopkCR = CR(P, D₊, D_–))，否则不加入集合。

当 $\left| L \right| = k$ 时，如果 ${\rm{CR}}(P,{D_ + },{D_ - }) > \min {\rm{TopkCR}}$ ，在集合L中寻找序列P的子序列，若未找到子序列，用P替换集合L中对比度最小的序列；若找到了子序列P′，且P相对P′不是冗余序列，则用P替换集合L中对比度最小的序列，并更新集合L的最小对比度阈值 $\min {\rm{TopkCR}}$ (若此时集合中第二小的CR小于 ${\rm{CR}}(P,{D_ + },{D_ - })$ ，则将它设置为 $\min {\rm{TopkCR}}$ ，否则 $\min {\rm{TopkCR = }} {\rm{CR}}(P,{D_ + },{D_ - })$ )；否则不替换。

6) 将队列的第一个元素弹出。

7) 重复4)~6)，直到队列为空。

例5　对表1的数据集进行去冗余Top-k对比序列模式挖掘, 令k=5。找出基因数据集的字母表 $\Sigma $ 为 $\Sigma = \{ A,G,C,T\} $ 。将字母表的每个元素放入队列中，生成的树结构和队列如图1所示。

在Top-k对比序列模式挖掘中，去除冗余序列模式是提高挖掘结果质量的重要一步。但是在原有挖掘过程的基础上，加入去冗余的步骤后，一个新的序列可能会替换Top-k集合中的多个序列，使Top-k集合中的序列模式数目小于k个。针对以上问题，本文提出基于广度优先的生成树算法BFM (breadth-first miner)来去除冗余的序列模式。使用BFM算法可以在去除冗余序列模式的同时，保证Top-k集合的大小不发生变化。

算法1　BFM (breadth-first miner)

输入　正例集 ${D_ + }$ 、反例集 ${D_ - }$ 、参数 $k$ 。

输出　包含Top-k对比序列模式的集合 $L$ 。

/*初始化*/

1）创建集合 $L$ ，设置集合 $L$ 的最小对比度阈值 $\min {\rm{TopkCR}} = 0$ ；

2）创建队列，初始化队列queue为空；

3）计算出字母表 $\Sigma $ ，将字母表中的每个元素加入到queue中；

4）创建树的根节点,建立由根节点分别指向字母表中每个元素的连接，令min TopkCR = getMinTopkCR (L)；

5）对 $\Sigma $ 中的每一个元素 $e$ ，把 $e$ 添加到queue的第一个序列的末尾，组成新的序列P，如果 ${\rm{Sup}}(P,{D_ + }) \geqslant \min {\rm{TopkCR}}$ 则把 P加入到队列中；

如果 $\left| L \right| < k$ 则在集合 $L$ 寻找中 $P$ 的子序列 $P'$ ；

如果 P′被找到且 P不是相对于P′的冗余序列模式，则把P加入集合L, 更新 $\min {\rm{TopkCR}}$ ；

否则把P加入集合L, 更新 $\min {\rm{TopkCR}}$ ；

6）如果 $\left| L \right| = k$ ，并且 ${\rm{CR}}(P,{D_ + },{D_ - }) > \min {\rm{TopkCR}}$ 那么在集合L中寻找P的子序列P′；

如果 P′被找到并且P是相对于P′的冗余序列，则用P替换集合L中对比度最小的序列更新 $\min \operatorname{TopkCR} $ ，否则，用P替换集合L中对比度最小的序列更新 $\min {\rm{TopkCR}}$ ；

7）重复步骤 5）、6），直到对列为空。

3.2 剪枝策略

为了提高算法的性能，本文中应用了一系列剪枝策略来辅助算法的运行^[7]。运用这些剪枝策略，可以使程序运行的效率提高，更快地找出Top-k集合。

剪枝策略1　(反例元素剪枝策略)在遍历数据集 $D$ 生成字母表 $\Sigma $ 时，只统计正例集 ${D_ + }$ 中出现的元素，而不统计反例集 ${D_ - }$ 中出现的元素。

这条剪枝策略基于以下原理：如果元素 $e$ 不在正例集 ${D_ + }$ 中，则所有包含元素 $e$ 的超序列E也不在正例集中， ${\rm{Sup}}(E,{D_ + }) = $ 0。由对比序列模式的定义可知，对比序列模式必须满足 ${\rm{CR}}(P,{D_ + },{D_ - }) > 0$ ，即 ${\rm{Sup}}(P,{D_ + }) - {\rm{Sup}}(P, {D_ - }) > 0$ 。因为 ${\rm{Sup}}(E,{D_ + }) = 0$ ， ${\rm{Sup}}(E,{D_ - }) \geqslant $ 0，所以序列E不满足 ${\rm{Sup}}(P,{D_ + }) - $ $ {\rm{Sup}}(P,{D_ - }) > 0$ ，E不是对比序列模式，字母表 $\Sigma $ 中不需要包含元素 $e$ 。

剪枝策略2　(序列支持度的剪枝策略)当 $\left| L \right| = k$ 时，如果序列 $P$ 满足 ${\rm{Sup}}(P,{D_ + }) \leqslant \min {\rm{TopkCR}}$ ，则不把序列 $P$ 放入队列。

由 ${\rm{CR}}(P,{D_ + },{D_ - }) = {\rm{Sup}}(P,{D_ + }) - {\rm{Sup}}(P,{D_ - })$ 可知， ${\rm{Sup}}(P,{D_ - }) \geqslant 0$ ，如果 ${\rm{Sup}}(P,{D_ + }) \leqslant \min {\rm{TopkCR}}$ 则CR $(P,{D_ + },{D_ - }) \leqslant \min {\rm{TopkCR}}$ ，序列P不是Top-k对比序列模式。对于任意一个模式P的超模式 $P' $ ，有 ${\rm{Sup}}(P',{D_ + }) \! \leqslant \! {\rm{Sup}}(P,{D_ + })$ ，因此 ${\rm{Sup}}(P',{D_ + })\! \leqslant \! \min {\rm{TopkCR}}$ 也成立。所以序列P′也不是Top-k对比序列模式。序列P不用放入队列，即把以序列P为根节点的子树从整体的生成树上剪枝。

剪枝策略3　(元素支持度的剪枝策略)当 $\left| L \right| = k$ 时，如果元素 $e$ 满足 ${\rm{Sup}}(e,{D_ + }) \leqslant \min {\rm{TopkCR}}$ ，则将元素 $e$ 从字母表中移除。

由Top-k对比序列模式的定义可知，包含元素 $e$ 的序列不是Top-k对比序列，所以在生成树结构时，不用生成包含元素 $e$ 的序列，可以将元素 $e$ 从字母表移除。

加入以上3条剪枝策略后，树结构生成的速度会加快，可以在更短的时间内找到Top-k对比序列模式。对于某一类数据集，使用剪枝后，算法的效率会显著提升。加入剪枝后的算法如算法2。

算法2　PBFM(pruning breadth-first miner)

输入　正例集 ${D_ + }$ ，反例集 ${D_ - }$ ，参数 $k$ 。

输出　包含Top-k对比序列模式的集合L。

/*初始化*/

1）创建集合L，设置集合L的最小对比度阈值 $\min {\rm{TopkCR}} = 0$ ；

2）创建队列，初始化队列queue为空；

3）计算正例集 ${D_ + }$ 的字母表 $\Sigma $ ，将字母表中的元素加入到queue中；

4）创建树的根节点，建立由根节点分别指向字母表中每个元素的指针，令min TopkCR = getMinTopkCR (L)；

5）如果 ( ${\rm{Sup}}(e,{D_ + }) \leqslant \min {\rm{TopkCR}}$ ) 则从字母表 $\Sigma $ 中删除元素 $e$ ，对 $\Sigma $ 中的每一个元素 $e$ ，把e添加到队列的第一个序列的末尾，组成新的序列P；

如果 ${\rm{Sup}}(P,{D_ + }) \geqslant \min {\rm{TopkCR}}$ ，则把P加入到队列中；

如果 $\left| L \right| < k$ ，则在集合L寻找P的子序列 $P'$ ；

如果 $P'$ 被找到且P不是相对于 $P' $ 的冗余序列，则把 $P$ 加入集合 $L$ ,更新 $\min {\rm{TopkCR}}$ ，否则把P加入集合L，更新min TopkCR；

6）如果 $\left| L \right| = k$ ，并且 ${\rm{CR}}(P,{D_ + },{D_ - }) > \min $ TopkCR，则在集合 $L$ 寻找 $P$ 的子序列 $P'$ ；

如果 $P'$ 被找到，并且P不是相对于P'的冗余序列 ，则用P替换集合L中对比度最小的序列，更新 $\min {\rm{TopkCR}}$ ，否则用P替换集合L中对比度最小的序列更新 $\min {\rm{TopkCR}}$ ；

7）重复步骤 5）、6），直到队列为空。

4 实验结果 4.1 实验环境

本文设计了一系列实验来评估算法的有效性。算法用C++语言来实现。实验中所用到的数据集为4组真实数据。这4组数据分别是：E.Coli数据集,记录了两个不同类型的DNA序列。在E.Coli数据集中，每个DNA序列前面都用“+”和“–”标记出了序列所属的类别。UJI数据集，记录了超过11 000个独立的手写数字。ADLs数据集，记录了一段时间内不同的人在自己家中的活动情况。Question数据集，记录了各种不同的问题，可以将每个问题看作由不同单词组成的序列。前3个数据集来自UCI的机器学习数据集。最后一个数据集是Question的训练数据集。实验运行的环境是：Core i3的处理器，Windows 7操作系统，2GB RAM 的计算机上完成。表5中列出了实验中用到的数据集的特征。

4.2 实验结果分析

1) 实验1(去冗余前后Top-k集合对比实验)

实验1的目标是比较去冗余前后Top-k集合中序列模式的变化，来验证去冗余算法的有效性。在该实验中，使用了3组数据来对比去冗余前后Top-k结果集合的不同。每组数据分别找出了含有冗余序列的Top-k集合和不含冗余序列的Top-k集合，并比较其中序列的组成。在实验中，k值设置为5。实验结果如表6~8所示。

通过实验结果可以发现，去冗余Top-k集合中出现了冗余Top-k集合中没有出现的序列模式。同时，去冗余Top-k集合中删去了冗余的序列模式。因此，本文的算法能够有成效地去除冗余对比序列模式。

2) 实验2(加入剪枝策略前后的对比实验)

实验2的目标是比较算法1与加入剪枝策略后算法效率的变化。分别在ADLs数据集和Question数据集上进行对比实验，比较算法1和算法2运行的时间，来衡量算法的效率。

将k的值分别从1取到20，比较算法1(BFM)和算法2(PBFM)运行的时间如图2所示。从图2中可以看出，随着k值的增加，两种算法的运行时间都在增长，但PBFM的运行时间明显少于BFM的运行时间。在ADLs数据集中，随着k值逐渐变大，这一区别越来越明显。在Question 数据集中，当k值较小时，这一区别较为明显。随着k值的增大，Top-k集合的最小对比度minTopkCR逐渐变小，当 $k \geqslant 18$ 时，PBFM算法中删除的元素个数较少，但PBFM算法运行的时间仍然少于BFM算法运行的时间。

5 结束语

本文首先提出了一种挖掘去冗余Top-k对比序列模式的算法BFM,这是一种基于广度优先生成树的算法。通过不断的比较子序列和超序列的对比度，Top-k集合不断地更新，直到树结构的生成过程结束。相比之前的Top-k对比序列模式挖掘算法，BFM算法可以得到去冗余的Top-k集合，并且不需要其他集合的辅助。

在BFM算法的基础上,提出了性能更好的PBFM算法。与BFM算法相比，PBFM算法可以在更短的时间内完成挖掘任务，并且不需要额外的操作。