第5期 江冰，等：去冗余Top-k对比序列模式挖掘 ·681· 序列规则、相关模式2和序列模式等领域 有S=e,e2,…,en。其中e称为组成序列S的元素。 中。但是，在Top-k策略挖掘结果中依然存在冗 用len(S)来表示序列S的长度，即s中包含元素的数 余的问题。针对这一问题，本文提出了挖掘去冗 目。用S[表示序列S第i个位置的元素e。由数据 余Topk对比序列模式集合的方法。 集D中所有的元素组成的集合称为字母表，用符 号Σ表示。对于给定的两个序列S和S',若存在一 1相关工作 组整数1≤k1<k2<…<km≤len(S),使得对于任意 对比序列模式挖掘主要包括基于阈值的对比 的ie[1,len(S刃，都有S'[=S[k],则称S是S的超序 序列模式挖掘和Top-k对比序列模式挖掘两个研 列，S是S的子序列。 究方向。基于阈值的对比序列模式挖掘的目标是 例1对于序列，S={A,C,G,T,C,A,S'={C,G, 找出所有满足给定阈值的模式。最直接挖掘对比 T,存在一组整数k=2,k2=3,k=4,使得S[k]= 序列模式的方法是枚举所有的序列模式，然后统 S[1,S[k]=S2,S[k]=S[3],所以S'是S的子序 计它们在每个类别上的频率。很明显这种方法的 列，记作S'SS。给定数据集D,序列P在数据集 效率太低，不能满足实际应用的需求。Chan等 D中的支持度由式(1)来定义： 于2003年提出一种基于后缀树的挖掘对比序列 Sup(P.D)=IS EDIPSS (1) 模式的算法(emerging substrings mining,.ESM)。与 朴素的挖掘算法相比，ESM提高了一定的效率。 式中D表示数据集D中包含序列的个数。 Ji等于2007年定义了MDS(minimal distinguish- 定义1（对比度）对于给定的数据集D,D由 ing subsequence)的概念，并提出了相应的挖掘算 正例集D,和反例集D组成。序列P的对比度定 法，即ConSGapMiner(contrast sequences with gap 义为 miner)算法。ConSGapMiner是比较经典的对比 CR(P.D.,D_)=Sup(P,D.)-Sup(P,D_) 序列模式挖掘算法，它能以较快的效率挖掘出对 例2对于表1中给出的DNA数据集，D=6, 比序列模式。但是MDS定义的对比序列模式在 ID=4。令序列P={A,G,T},有Sup(PD4)=1,Sp 正例集中大于一个固定的阈值，在反例集中小于 (P,D-)=0.25。CR(P,D+,D-)=Sup(P,D+)-Sup,(P,D) 一个固定阈值，这种定义可能使一些有意义的模 CR(P)=0.75。对于一个给定的数据集D,如果序 式没有被挖掘出来。2010年Deng等1s1在Con- 列P满足CR(P,D,D)>O,则称P是一个对比序列 SGapMiner的基础上利用F-ratio作为对比度；2011 模式。 年Yu等提出了TSEPsMiner算法；TSEPsMiner 表1含有两个类别的基因数据集 利用GrowthRate作为对比度，而且将这个对比度 Table 1 A gene data set with two classes 应用在了挖掘对比序列模式的算法中：2014年 序列 类别 序列 类别 Wang等m提出用gd-DSPMiner算法来解决MDs C,A,G,T,A D C,A,A,G,T,A D. 定义中存在的问题。在不明确数据的差异程度 C,A,G,T,G D A.A.C.T D 时，使用基于阈值的对比序列模式挖掘难以挖掘 A,G,A,G,T,C D. A,T,G,C D 出预期的序列模式。在这种情况下，Top-k对比 序列模式挖掘是一个可行的办法。Top-k算法不 T,T,A,A,G,T,A D C,A,G,T D 用设定对比度的阈值，只需要设置想要挖掘模式 T,A,G,T,A,C D T,A,A,T D 的数目。杨皓等于2015年提出了新的Top-k挖 定义2(Top-k对比序列模式)给定正例集 掘算法，即kDSP-Miner(Top-k distinguishing se- D,和反例集D,在所有的对比序列模式中，对比度 quential patterns with gap constraint miner)算法。但 最大的前k个序列模式称为Top-k对比序列模式。 是kDSP-Miner并没有考虑冗余问题，kDSP- Top-k对比序列模式挖掘的目标是找出给定 Miner挖掘出的序列模式可能会有大量的冗余。 数据集中对比度最大的k个序列模式。 2问题定义 例3在表1的数据集中，令k=5,则找出的 Top-k对比序列模式见表2所示。 对于一个给定的数据集D,它由两部分组成， 定义3（冗余对比序列模式）对于两个给定 分别是D,和D。其中，D,是正例集，D是反例 的对比序列模式P和P,如果满足： 集。数据集D由多个序列组成。对于每个序列S, I)P是的P子序列，即PcP:序列规则[ 1 1 ] 、相关模式[ 1 2 ]和序列模式[ 7 ]等领域 中。但是，在 Top-k 策略挖掘结果中依然存在冗 余的问题。针对这一问题，本文提出了挖掘去冗 余 Top-k 对比序列模式集合的方法。 1 相关工作 对比序列模式挖掘主要包括基于阈值的对比 序列模式挖掘和 Top-k 对比序列模式挖掘两个研 究方向。基于阈值的对比序列模式挖掘的目标是 找出所有满足给定阈值的模式。最直接挖掘对比 序列模式的方法是枚举所有的序列模式，然后统 计它们在每个类别上的频率。很明显这种方法的 效率太低，不能满足实际应用的需求。Chan 等 [13] 于 2003 年提出一种基于后缀树的挖掘对比序列 模式的算法 (emerging substrings mining，ESM)。与 朴素的挖掘算法相比，ESM 提高了一定的效率。 Ji 等 [14]于 2007 年定义了 MDS (minimal distinguish￾ing subsequence) 的概念，并提出了相应的挖掘算 法，即 ConSGapMiner (contrast sequences with gap miner) 算法。ConSGapMiner 是比较经典的对比 序列模式挖掘算法，它能以较快的效率挖掘出对 比序列模式。但是 MDS 定义的对比序列模式在 正例集中大于一个固定的阈值，在反例集中小于 一个固定阈值，这种定义可能使一些有意义的模 式没有被挖掘出来。2010 年 Deng 等 [15]在 Con￾SGapMiner 的基础上利用 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 se￾quential patterns with gap constraint miner) 算法。但 是 kDSP-Miner并没有考虑冗余问题， kDSP￾Miner 挖掘出的序列模式可能会有大量的冗余。 2 问题定义 D D+ D− D+ D− D S 对于一个给定的数据集 ，它由两部分组成， 分别是 和 。其中， 是正例集， 是反例 集。数据集 由多个序列组成。对于每个序列 ， S = e1, e2,··· , en ei S len(S ) S S S [i] S i ei Σ S S ′ 1 ⩽ k1 < k2 < ··· < km ⩽ len(S ) i ∈ [1,len(S ′ )] S ′ [i] = S [ki] S S ′ S ′ S 有 。其中 称为组成序列 的元素。 用 来表示序列 的长度，即 中包含元素的数 目。用 表示序列 第 个位置的元素 。由数据 集 D 中所有的元素组成的集合称为字母表，用符 号 表示。对于给定的两个序列 和 ，若存在一 组整数 ，使得对于任意 的 ，都有 ，则称 是 的超序 列， 是 的子序列。 S = {A,C,G,T,C,A} S ′ = {C,G, T} k1 = 2 k2 = 3 k3 = 4 S [k1] = S ′ [1],S [k2] = S ′ [2],S [k3] = S ′ [3] S ′ S S ′ ⊆ S D P D 例 1 对于序列， ， ，存在一组整数 ， ， ，使得 ，所以 是 的子序 列，记作 。给定数据集 ，序列 在数据集 中的支持度由式 (1) 来定义： Sup(P,D) = |{S ∈ D|P ⊆ S }| |D| (1) 式中 |D| 表示数据集 D 中包含序列的个数。 D D D+ D− P 定义 1 (对比度) 对于给定的数据集 ， 由 正例集 和反例集 组成。序列 的对比度定 义为 CR(P,D+,D−) = Sup(P,D+)−Sup(P,D−) |D+| = 6, |D−| = 4 P = {A,G,T} Sup(P,D+) = 1,Sup (P,D−) = 0.25 CR(P,D+,D−) = Sup(P,D+)−Sup, D P CR(P,D+,D−) > 0 P 例 2 对于表 1 中给出的 DNA 数据集， 。令序列 ， 有 。 (P,D– ), CR (P) = 0.75。对于一个给定的数据集 ，如果序 列 满足 ，则称 是一个对比序列 模式。 表 1 含有两个类别的基因数据集 Table 1 A gene data set with two classes 序列 类别 序列 类别 C, A, G, T, A D+ C, A, A, G, T, A D+ C, A, G, T, G D+ A, A, C, T D– A, G, A, G, T, C D+ A, T, G, C D– T, T, A, A, G, T, A D+ C, A, G, T D– T, A, G, T, A, C D+ T, A, A, T D– D+ D− 定义 2 (Top-k 对比序列模式) 给定正例集 和反例集 ，在所有的对比序列模式中,对比度 最大的前 k 个序列模式称为 Top-k 对比序列模式。 Top-k 对比序列模式挖掘的目标是找出给定 数据集中对比度最大的 k 个序列模式。 例 3 在表 1 的数据集中，令 k = 5,则找出的 Top-k 对比序列模式见表 2 所示。 P P ′ 定义 3 (冗余对比序列模式) 对于两个给定 的对比序列模式 和 ，如果满足： P ′ P P ′ 1) 是的 子序列，即 ⊆ P ； 第 5 期 江冰，等：去冗余 Top-k 对比序列模式挖掘 ·681·