第13卷第5期 智能系统学报 Vol.13 No.5 2018年10月 CAAI Transactions on Intelligent Systems Oct.2018 D0:10.11992/tis.201702019 网络出版地址：http:/kns.cnki.net/kcms/detail/23.1538.tp.20180417.1130.008.html 去冗余Top-k对比序列模式挖掘 江冰，谷飞洋，何增有 (大连理工大学软件学院，辽宁大连116621) 摘要：对比序列模式可以用来表征不同类别数据集之间的差异。在生物信息、物流管理、电子商务等领域， 对比序列模式有着广泛的应用。T©k对比序列模式挖掘的目标是发现数据集中对比度最高的前k个序列模 式。在Topk对比序列模式挖掘中，可能挖掘出冗余的序列模式。目前，虽然有Top-k对比序列模式发现算法 被提出，但这些算法并未考虑冗余序列模式的问题。为此，本文提出了基于广度优先生成树的去冗余T©p-k 对比序列模式挖掘算法BFM(breadth--first miner)。使用BFM算法可以有效地解决冗余问题，得到去冗余的Top-k 对比序列模式。在BFM算法的基础上，提出了性能更好的算法PBFM(pruning breadth--first miner)。通过在真实 数据集上的实验分析与对比，验证了本文算法的有效性。 关键词：对比序列模式：广度优先；冗余序列模式；模式挖掘：Topk 中图分类号：TP393文献标志码：A文章编号：1673-4785(2018)05-0680-07 中文引用格式：江冰，谷飞洋，何增有.去冗余Top-k对比序列模式挖掘J.智能系统学报，2018,13(5)：680-686. 英文引用格式：JIANG Bing,GU Feiyang,HE Zengyou.Mining Top-knon-redundant distinguishing sequential patterns.CAAI transactions on intelligent systems,2018,13(5):680-686. Mining Top-k non-redundant distinguishing sequential patterns JIANG Bing,GU Feiyang,HE Zengyou (Software School,Dalian University of Technology,Dalian 116621,China) Abstract:Distinct sequential patterns can be used to characterize different categories of datasets.In the field of bioin- formatics,logistics management,and e-commerce,the comparison of sequential pattern has a wide range of applica- tions.The goal of the Top-k distinguishing sequential pattern mining is to find k patterns with the highest contrast in a given data set.However,in the Top-k distinguishing sequential pattern mining,there is a redundancy problem with re- spect to the set of reported sequential patterns,which is not considered by the algorithm.Therefore,in this paper,a non- redundant Top-k distinguishing sequential pattern mining algorithm,breadth-first miner(BFM),is proposed based on breadth-first spanning tree.The redundancy problem is effectively solved using the BFM algorithm.Based on the BFM algorithm,a better algorithm,pruning breadth-first miner(PBFM),is proposed.Through the experimental analysis and comparison on the real data set,the validity of the algorithm is verified. Keywords:distinguishing sequential pattern;breadth-first,redundant sequential patterns;pattern mining;Top-k 至今已经有很多种序列模式被提出，包括周 据集中频繁出现，而在另一类数据集中很少出现 期模式山、偏序模式)、闭合模式倒、对比序列模 的序列模式。对比序列模式可以描述不同数据集 式、频繁序列模式阿等。对比序列模式挖掘作为 之间的差异，在很多领域有广泛应用。例如，对 数据挖掘中重要的一个问题，目前已经积累了大 比序列模式可以用于纳税人行为分析，患者的 量的研究成果6刀。对比序列模式是指在一类数 风险预测例等。在对比序列模式挖掘中，Top-k对 收稿日期：2017-02-26.网络出版日期：2018-04-18. 比序列模式挖掘是一种重要的挖掘策略。Top 基金项目：国家自然科学基金项目(61572094)：大学生创新创 业训练计划项日(2017101410901010382) k方法是指在给定的标准下挖掘出差异最大的 通信作者：何增有.E-mail:yhe@dut.edu.cn. k个模式的方法。该方法被广泛应用在关联规则
DOI: 10.11992/tis.201702019 网络出版地址: http://kns.cnki.net/kcms/detail/23.1538.tp.20180417.1130.008.html 去冗余 Top-k 对比序列模式挖掘 江冰，谷飞洋，何增有 （大连理工大学 软件学院，辽宁 大连 116621） 摘 要：对比序列模式可以用来表征不同类别数据集之间的差异。在生物信息、物流管理、电子商务等领域， 对比序列模式有着广泛的应用。Top-k 对比序列模式挖掘的目标是发现数据集中对比度最高的前 k 个序列模 式。在 Top-k 对比序列模式挖掘中，可能挖掘出冗余的序列模式。目前，虽然有 Top-k 对比序列模式发现算法 被提出，但这些算法并未考虑冗余序列模式的问题。为此，本文提出了基于广度优先生成树的去冗余 Top-k 对比序列模式挖掘算法 BFM(breadth-first miner)。使用 BFM 算法可以有效地解决冗余问题，得到去冗余的 Top-k 对比序列模式。在 BFM 算法的基础上，提出了性能更好的算法 PBFM(pruning breadth-first miner)。通过在真实 数据集上的实验分析与对比 ，验证了本文算法的有效性。 关键词：对比序列模式；广度优先；冗余序列模式；模式挖掘；Top-k 中图分类号：TP393 文献标志码：A 文章编号：1673−4785(2018)05−0680−07 中文引用格式：江冰, 谷飞洋, 何增有. 去冗余 Top-k 对比序列模式挖掘[J]. 智能系统学报, 2018, 13(5): 680–686. 英文引用格式：JIANG Bing, GU Feiyang, HE Zengyou. Mining Top-k non-redundant distinguishing sequential patterns[J]. CAAI transactions on intelligent systems, 2018, 13(5): 680–686. Mining Top-k non-redundant distinguishing sequential patterns JIANG Bing，GU Feiyang，HE Zengyou (Software School, Dalian University of Technology, Dalian 116621, China) Abstract: Distinct sequential patterns can be used to characterize different categories of datasets. In the field of bioinformatics, logistics management, and e-commerce, the comparison of sequential pattern has a wide range of applications. The goal of the Top-k distinguishing sequential pattern mining is to find k patterns with the highest contrast in a given data set. However, in the Top-k distinguishing sequential pattern mining, there is a redundancy problem with respect to the set of reported sequential patterns, which is not considered by the algorithm. Therefore, in this paper, a nonredundant Top-k distinguishing sequential pattern mining algorithm, breadth-first miner (BFM), is proposed based on breadth-first spanning tree. The redundancy problem is effectively solved using the BFM algorithm. Based on the BFM algorithm, a better algorithm, pruning breadth-first miner (PBFM), is proposed. Through the experimental analysis and comparison on the real data set, the validity of the algorithm is verified. Keywords: distinguishing sequential pattern; breadth-first; redundant sequential patterns; pattern mining; Top-k 至今已经有很多种序列模式被提出，包括周 期模式[1] 、偏序模式[2] 、闭合模式[3] 、对比序列模 式 [4] 、频繁序列模式[5]等。对比序列模式挖掘作为 数据挖掘中重要的一个问题，目前已经积累了大 量的研究成果[6-7]。对比序列模式是指在一类数 据集中频繁出现，而在另一类数据集中很少出现 的序列模式。对比序列模式可以描述不同数据集 之间的差异，在很多领域有广泛应用。例如，对 比序列模式可以用于纳税人行为分析[8] ，患者的 风险预测[9]等。在对比序列模式挖掘中，Top-k 对 比序列模式挖掘是一种重要的挖掘策略。 Topk 方法是指在给定的标准下挖掘出差异最大的 k 个模式的方法。该方法被广泛应用在关联规则[10] 、 收稿日期：2017−02−26. 网络出版日期：2018−04−18. 基金项目：国家自然科学基金项目 (61572094)；大学生创新创 业训练计划项目 (2017101410901010382). 通信作者：何增有. E-mail: zyhe@dlut.edu.cn. 第 13 卷第 5 期 智 能 系 统 学 报 Vol.13 No.5 2018 年 10 月 CAAI Transactions on Intelligent Systems Oct. 2018
第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 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并没有考虑冗余问题， kDSPMiner 挖掘出的序列模式可能会有大量的冗余。 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·
·682· 智能系统学报 第13卷 2)CR(P',D.,D-)>CR(P.D.,D_); 3算法设计 则称模式P是冗余对比序列模式。 表2的对比序列模式中，{G,T)s{G,T,A,且 为了挖掘去冗余Top-k对比序列模式的集 CR(IG,T,D,D)≥CR(IG,T,A,D,D),所以模式 合，用本文提出的BFM和PBFM算法，来解决挖 {G,T,A)是相对于G,T)的冗余对比序列模式。 掘出的结果集合的冗余问题。BFM和PBFM算 表2表1中基因数据集的Top-5对比序列模式 法基于广度优先生成树的原理来寻找Topk序列 Table 2 Top-five discriminative sequential patterns from 的集合，树的生成过程就是Top-k集合的更新过 gene data set in table 1 程。相比于使用深度优先的方法来生成树结构， Sequence Sup(P,D)Sup(P,D_) Sup (P,D,D_) 使用广度优先的方法每次更新时不改变Top-k集 (4,G) 1 0.25 0.75 合的大小，所以不会出现冗余的Topk集合。 (G,T) 1 0.25 0.75 3.1广度优先的生成树算法 I)根据给定的数据集D,生成字母表Σ。 (A,G,TY 1 0.25 0.75 2)创建Top-k集合L,设置集合L的最小对比 (G,T,A) 0.67 0 0.67 度阈值minTopkCR=O。 (A,G,T,A) 0.67 0 0.67 3)创建一个队列，将字母表中的每个元素放 定义4（去冗余Top-k对比序列模式）集合 入队列中。 L满足Top-k对比序列模式集合的要求，同时对 4)对于队列的第一个元素，在其末尾分别与 于每个序列r∈L,不存在rb生LArCraACR(b,D,D)≥ 字母表中的每个元素连接，形成新的序列。 CRa,D,D);对于任意序列raeL,r∈L,r不是相 5)计算每个新的序列P的支持度和对比度， 对于的冗余对比序列模式。 如果Sup(P,D,)≥minTopkCR,将P放入队列中，否 例4在表1的数据集中，令k=5,则找出的 则不放入队列中。 去冗余Top-k对比序列模式如表3所示。 当四<k时，在集合L中寻找序列P的子序列， 表3表1中基因数据集的Top-5去冗余对比序列模式 若未找到子序列，将P加入集合L;若找到了子序 Table 3 Top-five non-redundant distinguishing sequential 列P,且P相对于P不是冗余序列，则将P加入集 patterns from gene data set in table 1 合L,并更新集合L的最小对比度阈值minTopkCR Sequence Sup (P,D.) Sup(P,D) Sup(P,D.,D) (若CR(P,D,D-)≤minTopkCR,则min TopkCR=CRP, {A,G} 0.25 0.75 D,D),否则不加入集合。 (G,T 0.25 0.75 当I=k时，如果CR(P,D,D)>minTopkCR,在 集合L中寻找序列P的子序列，若未找到子序 {T,A} 0.67 0.25 0.42 列，用P替换集合L中对比度最小的序列；若找 (C,4) 0.5 0.25 0.25 到了子序列P',且P相对P不是冗余序列，则用 (T,C) 0.17 0 0.17 P替换集合L中对比度最小的序列，并更新集合 本文中常用的符号及定义总结在表4中。 L的最小对比度阈值minTopkCR(若此时集合中第 表4符号及其含义 二小的CR小于CR(P,D,D),则将它设置为 Table 4 Symbols and their meaning minTopkCR,否则minTopkCR=CR(P,D,D);否则 符号 含义 不替换。 6)将队列的第一个元素弹出。 D 数据集 7)重复4)6)，直到队列为空。 D 正例集 例5对表1的数据集进行去冗余Top-k对 D 反例集 比序列模式挖掘，令k=5。找出基因数据集的字 len (S) 序列S的长度 母表Σ为∑={A,G,C,T1。将字母表的每个元素放入 s阳 序列S第i个位置的元素e, 队列中，生成的树结构和队列如图1所示。 S'CS S是S的子序列 在Topk对比序列模式挖掘中，去除冗余序 Sup(P,D) 序列P在数据集D中的支持度 列模式是提高挖掘结果质量的重要一步。但是在 原有挖掘过程的基础上，加人去冗余的步骤后， CR(P.D..D_) 序列P的对比度 ,个新的序列可能会替换Top-k集合中的多个序
CR(P ′ ,D+,D−) ⩾ CR(P,D+,D−) P 2) ； 则称模式 是冗余对比序列模式。 {G,T} ⊆ {G,T,A} CR({G,T},D+,D−) ⩾ CR({G,T,A},D+,D−) {G,T,A} {G,T} 表 2 的对比序列模式中， ，且 ，所以模式 是相对于 的冗余对比序列模式。 表 2 表 1 中基因数据集的 Top-5 对比序列模式 Table 2 Top-five discriminative sequential patterns from gene data set in table 1 Sequence Sup (P, D+ ) Sup (P, D– ) Sup (P, D+ , D– ) {A, G} 1 0.25 0.75 {G, T} 1 0.25 0.75 {A, G, T} 1 0.25 0.75 {G, T, A} 0.67 0 0.67 {A, G, T, A} 0.67 0 0.67 ra ∈L rb <L∧rb ⊆ra∧CR(rb,D+,D−)⩾ CR(ra,D+,D−) ra ∈ L rc ∈ L ra rc 定义 4 (去冗余 Top-k 对比序列模式) 集合 L 满足 Top-k 对比序列模式集合的要求，同时对 于每个序列 ，不存在 ；对于任意序列 ， ， 不是相 对于 的冗余对比序列模式。 例 4 在表 1 的数据集中，令 k = 5 ，则找出的 去冗余 Top-k 对比序列模式如表 3 所示。 表 3 表 1 中基因数据集的 Top-5 去冗余对比序列模式 Table 3 Top-five non-redundant distinguishing sequential patterns from gene data set in table 1 Sequence Sup (P, D+ ) Sup (P, D– ) Sup (P, D+ , D– ) {A, G} 1 0.25 0.75 {G, T} 1 0.25 0.75 {T, A} 0.67 0.25 0.42 {C, A} 0.5 0.25 0.25 {T, C} 0.17 0 0.17 本文中常用的符号及定义总结在表 4 中。 表 4 符号及其含义 Table 4 Symbols and their meaning 符号 含义 D 数据集 D+ 正例集 D– 反例集 len (S) 序列 S 的长度 S[i] 序列 S 第 i 个位置的元素 ei S' ⊆ S S'是 S 的子序列 Sup (P, D) 序列 P 在数据集 D 中的支持度 CR (P, D+ , D– ) 序列 P 的对比度 3 算法设计 为了挖掘去冗余 Top-k 对比序列模式的集 合，用本文提出的 BFM 和 PBFM 算法，来解决挖 掘出的结果集合的冗余问题。BFM 和 PBFM 算 法基于广度优先生成树的原理来寻找 Top-k 序列 的集合，树的生成过程就是 Top-k 集合的更新过 程。相比于使用深度优先的方法来生成树结构， 使用广度优先的方法每次更新时不改变 Top-k 集 合的大小，所以不会出现冗余的 Top-k 集合。 3.1 广度优先的生成树算法 1) 根据给定的数据集 D ，生成字母表 Σ。 L minTopkCR = 0 2) 创建 Top-k 集合 L，设置集合 的最小对比 度阈值 。 3) 创建一个队列，将字母表中的每个元素放 入队列中。 4) 对于队列的第一个元素，在其末尾分别与 字母表中的每个元素连接，形成新的序列。 Sup(P,D+) ⩾ minTopkCR 5) 计算每个新的序列 P 的支持度和对比度， 如果 ，将 P 放入队列中，否 则不放入队列中。 |L| < k L minTopkCR CR(P,D+,D−) ⩽ minTopkCR 当 时，在集合 L 中寻找序列 P 的子序列， 若未找到子序列，将 P 加入集合 L；若找到了子序 列 P，且 P 相对于 P′不是冗余序列，则将 P 加入集 合 L，并更新集合 的最小对比度阈值 (若 ，则 min TopkCR = CR(P, D+ , D– ))，否则不加入集合。 |L| = k CR(P,D+,D−) > minTopkCR minTopkCR CR(P,D+,D−) minTopkCR minTopkCR =CR(P,D+,D−) 当 时，如果 ，在 集合 L 中寻找序列 P 的子序列，若未找到子序 列，用 P 替换集合 L 中对比度最小的序列；若找 到了子序列 P′，且 P 相对 P′不是冗余序列，则用 P 替换集合 L 中对比度最小的序列，并更新集合 L 的最小对比度阈值 (若此时集合中第 二 小 的 C R 小 于 ，则将它设置为 ，否则 )；否则 不替换。 6) 将队列的第一个元素弹出。 7) 重复 4)~6)，直到队列为空。 Σ Σ = {A,G,C,T} 例 5 对表 1 的数据集进行去冗余 Top-k 对 比序列模式挖掘, 令 k =5。找出基因数据集的字 母表 为 。将字母表的每个元素放入 队列中，生成的树结构和队列如图 1 所示。 在 Top-k 对比序列模式挖掘中，去除冗余序 列模式是提高挖掘结果质量的重要一步。但是在 原有挖掘过程的基础上，加入去冗余的步骤后， 一个新的序列可能会替换 Top-k 集合中的多个序 ·682· 智 能 系 统 学 报 第 13 卷
第5期 江冰，等：去冗余Top-k对比序列模式挖掘 ·683· 列，使Top-k集合中的序列模式数目小于k个。 的序列更新minTopkCR; 针对以上问题，本文提出基于广度优先的生成树 7)重复步骤5)、6)，直到对列为空。 算法BFM(breadth-first miner)来去除冗余的序列 3.2剪枝策略 模式。使用BFM算法可以在去除冗余序列模式 为了提高算法的性能，本文中应用了一系列 的同时，保证Top-k集合的大小不发生变化。 剪枝策略来辅助算法的运行。运用这些剪枝策 略，可以使程序运行的效率提高，更快地找出 Top-k集合。 G C T AGCT (a)枚举树与队列的初始化 剪枝策略1（反例元素剪枝策略）在遍历数 据集D生成字母表Σ时，只统计正例集D,中出现的 T AGCTAAAGACAT 元素，而不统计反例集D中出现的元素。 AA AG AC AT 这条剪枝策略基于以下原理：如果元素e不在 )生成第一个元素的子序列 正例集D,中，则所有包含元素e的超序列E也不在 正例集中，Sup(E,D)=0。由对比序列模式的定 C T GCTAAAG AC AT 义可知，对比序列模式必须满足CR(PD,D)>0, AA AG AC AT (©)将第一个元素从队列中删除 即Sup(P,D4)-Sup(P,D-)>0。因为Sup(E,D4)=0, Sup(E,D-)≥0，所以序列E不满足Sup(P,D,) C T GCTAAAGACATGAGGGCGI Sup(P,D)>0,E不是对比序列模式，字母表Σ中不 AA AG AC AT GA GG GC GT 需要包含元素eo (d)生成第二个元素的子序列 剪枝策略2（序列支持度的剪枝策略）当 图1生成树和队列的动态变化 ☑=k时，如果序列P满足Sup(P,D,)≤minTopkCR, Fig.1 The dynamic change of spanning tree and queue 则不把序列P放人队列。 算法1BFM(breadth-first miner) 由CR(PD,D)=Sup(PD)-Sup(PD)可知， 输入正例集D、反例集D、参数k。 Sup(PD)≥0，如果Sup(P,D,)≤minTopkCR则CR 输出包含Top-k对比序列模式的集合L。 (P,D,D)≤minTopkCR,序列P不是Top-k对比序 体初始化*/ 列模式。对于任意一个模式P的超模式P',有 1)创建集合L,设置集合L的最小对比度阈值 Sup(P',D,)≤Sup(PD+),因此Sup(P',D)≤minTopkCR minTopkCR =0; 也成立。所以序列P'也不是Top-k对比序列模 2)创建队列，初始化队列queue为空； 式。序列P不用放入队列，即把以序列P为根节 3)计算出字母表Σ，将字母表中的每个元素 点的子树从整体的生成树上剪枝。 加入到queue中； 剪枝策略3（元素支持度的剪枝策略）当 4)创建树的根节点，建立由根节点分别指向 凹=k时，如果元素e满足Sup(e,D+)≤minTopkCR, 字母表中每个元素的连接，令min TopkCR=get 则将元素e从字母表中移除。 MinTopkCR(L); 由Top-k对比序列模式的定义可知，包含元 5)对Σ中的每一个元素e,把e添加到queue的 素e的序列不是Top-k对比序列，所以在生成树结 第一个序列的末尾，组成新的序列P,如果 构时，不用生成包含元素e的序列，可以将元素e从 Sup(PD,)≥minTopkCR则把P加入到队列中； 字母表移除。 如果四<k则在集合L寻找中P的子序列P'; 加人以上3条剪枝策略后，树结构生成的速 如果P'被找到且P不是相对于P'的冗余序 度会加快，可以在更短的时间内找到Top-k对比 列模式，则把P加入集合L,更新minTopkCR; 序列模式。对于某一类数据集，使用剪枝后，算 否则把P加入集合L,更新minTopkCR; 法的效率会显著提升。加入剪枝后的算法如算 6)如果U=k,并且CR(PD,D)>minTopkCR 法2。 那么在集合L中寻找P的子序列P; 算法2PBFM(pruning breadth-first miner) 如果P'被找到并且P是相对于P'的冗余序 输入正例集D,反例集D,参数k。 列，则用P替换集合L中对比度最小的序列更新 输出包含Topk对比序列模式的集合L。 minTopkCR,否则，用P替换集合L中对比度最小 /体初始化*1
列 ，使 Top-k 集合中的序列模式数目小于 k 个。 针对以上问题，本文提出基于广度优先的生成树 算法 BFM (breadth-first miner) 来去除冗余的序列 模式。使用 BFM 算法可以在去除冗余序列模式 的同时，保证 Top-k 集合的大小不发生变化。 A G C T A G C T AA AG AC AT A G C T AA AG AC AT A G C T AA AG AC AT GA GG GC GT A G C T A G C T AA AG AC AT G C T AA AG AC AT G C T AA AG AC AT GA GG GC GT （a）枚举树与队列的初始化 （b）生成第一个元素的子序列 （d）生成第二个元素的子序列 （c）将第一个元素从队列中删除 图 1 生成树和队列的动态变化 Fig. 1 The dynamic change of spanning tree and queue 算法 1 BFM (breadth-first miner) 输入 正例集 D+、反例集 D−、参数 k。 输出 包含 Top-k 对比序列模式的集合 L。 /*初始化*/ L L minTopkCR = 0 1）创建集合 ，设置集合 的最小对比度阈值 ； 2）创建队列，初始化队列 queue 为空； 3）计算出字母表 Σ ，将字母表中的每个元素 加入到 queue 中； 4）创建树的根节点,建立由根节点分别指向 字母表中每个元素的连接，令 min TopkCR = getMinTopkCR (L)； Σ e e Sup(P,D+) ⩾ minTopkCR 5）对 中的每一个元素 ，把 添加到 queue 的 第一个序列的末尾，组成新的序 列 P ，如果 则把 P 加入到队列中； |L| < k L P P 如果 则在集合 寻找中 的子序列 ′； minTopkCR 如果 P′被找到且 P 不是相对于 P′的冗余序 列模式，则把 P 加入集合 L, 更新 ； 否则把 P 加入集合 L, 更新 minTopkCR ； 6）如果 |L| = k ，并且 CR(P,D+,D−) > minTopkCR 那么在集合 L 中寻找 P 的子序列 P′； minTopkCR 如果 P′被找到并且 P 是相对于 P′的冗余序 列，则用 P 替换集合 L 中对比度最小的序列更新 ，否则，用 P 替换集合 L 中对比度最小 的序列更新 minTopkCR ； 7）重复步骤 5）、6），直到对列为空。 3.2 剪枝策略 为了提高算法的性能，本文中应用了一系列 剪枝策略来辅助算法的运行[7]。运用这些剪枝策 略，可以使程序运行的效率提高，更快地找出 Top-k 集合。 D Σ D+ D− 剪枝策略 1 (反例元素剪枝策略) 在遍历数 据集 生成字母表 时，只统计正例集 中出现的 元素，而不统计反例集 中出现的元素。 e D+ e Sup(E,D+) = CR(P,D+,D−) > 0 Sup(P,D+)−Sup(P,D−) > 0 Sup(E,D+) = 0 Sup(E,D−) ⩾ Sup(P,D+)− Sup(P,D−) > 0 Σ e 这条剪枝策略基于以下原理：如果元素 不在 正例集 中，则所有包含元素 的超序列 E 也不在 正例集中， 0。由对比序列模式的定 义可知，对比序列模式必须满足 ， 即 。因为 ， 0 ，所以序 列 E 不满足 ，E 不是对比序列模式，字母表 中不 需要包含元素 。 |L| = k P Sup(P,D+) ⩽ minTopkCR P 剪枝策略 2 (序列支持度的剪枝策略) 当 时，如果序列 满足 ， 则不把序列 放入队列。 CR(P,D+,D−) = Sup(P,D+)−Sup(P,D−) Sup(P,D−) ⩾ 0 Sup(P,D+) ⩽ minTopkCR (P,D+,D−) ⩽ minTopkCR P ′ Sup(P ′ ,D+)⩽Sup(P,D+) Sup(P ′ ,D+)⩽minTopkCR 由 可知， ，如果 则 C R ，序列 P 不是 Top-k 对比序 列模式。对于任意一个模式 P 的超模式 ，有 ，因此 也成立。所以序列 P′也不是 Top-k 对比序列模 式。序列 P 不用放入队列，即把以序列 P 为根节 点的子树从整体的生成树上剪枝。 |L| = k e Sup(e,D+) ⩽ minTopkCR e 剪枝策略 3 (元素支持度的剪枝策略) 当 时，如果元素 满 足 ， 则将元素 从字母表中移除。 e e e 由 Top-k 对比序列模式的定义可知，包含元 素 的序列不是 Top-k 对比序列，所以在生成树结 构时，不用生成包含元素 的序列，可以将元素 从 字母表移除。 加入以上 3 条剪枝策略后，树结构生成的速 度会加快，可以在更短的时间内找到 Top-k 对比 序列模式。对于某一类数据集，使用剪枝后，算 法的效率会显著提升。加入剪枝后的算法如算 法 2。 算法 2 PBFM(pruning breadth-first miner) 输入 正例集 D+，反例集 D−，参数 k。 输出 包含 Top-k 对比序列模式的集合 L。 /*初始化*/ 第 5 期 江冰，等：去冗余 Top-k 对比序列模式挖掘 ·683·
·684· 智能系统学报 第13卷 1)创建集合L,设置集合L的最小对比度阈 数据集，记录了两个不同类型的DNA序列。在 值minTopkCR=O; E.Coli数据集中，每个DNA序列前面都用“+”和 2)创建队列，初始化队列queue为空； “-”标记出了序列所属的类别。UI数据集，记录 3)计算正例集D,的字母表Σ，将字母表中的 了超过11000个独立的手写数字。ADLs数据 元素加入到queue中； 集，记录了一段时间内不同的人在自己家中的活 4)创建树的根节点，建立由根节点分别指向 动情况。Question数据集，记录了各种不同的问 字母表中每个元素的指针，令min TopkCR=get- 题，可以将每个问题看作由不同单词组成的序 MinTopkCR (L); 列。前3个数据集来自UCI的机器学习数据集。 5)如果(Sup(e,D,)≤minTopkCR)则从字母表 最后一个数据集是Question的训练数据集。实验 Σ中删除元素e,对Σ中的每一个元素e,把e添加 运行的环境是：Core i.3的处理器，Windows7操作 到队列的第一个序列的末尾，组成新的序列P: 如果Sup(P,D,)≥minTopkCR,则把P加入到 系统，2 GB RAM的计算机上完成。表5中列出了 队列中： 实验中用到的数据集的特征。 如果叫<k,则在集合L寻找P的子序列P; 表5数据集的特征 如果P被找到且P不是相对于P的冗余序 Table 5 The characteristics of the data sets 列，则把P加入集合L,更新minTopkCR,否则把 数据集 类别 DD☒ D P加入集合L,更新min TopkCR; E.Coli E.Coli+E.Coli- 53534106 6)如果☑=k,并且CR(P,D,D-)>minTopkCR UJI Write+Write- 784784101568 则在集合L寻找P的子序列P; ADLs Activity+Activity- 13219 34 如果P被找到，并且P不是相对于P的冗余 Question Question+Question- 151156146307 序列，则用P替换集合L中对比度最小的序列， 更新minTopkCR,否则用P替换集合L中对比度 4.2 实验结果分析 最小的序列更新minTopkCR; 1)实验1（去冗余前后Top-k集合对比实验） 7)重复步骤5)、6)，直到队列为空。 实验1的目标是比较去冗余前后Top-k集合 4实验结果 中序列模式的变化，来验证去冗余算法的有效 性。在该实验中，使用了3组数据来对比去冗余 4.1实验环境 前后Top-k结果集合的不同。每组数据分别找出 本文设计了一系列实验来评估算法的有效 了含有冗余序列的Topk集合和不含冗余序列的 性。算法用C+语言来实现。实验中所用到的数 Top-k集合，并比较其中序列的组成。在实验中， 据集为4组真实数据。这4组数据分别是：E.Coli k值设置为5。实验结果如表6~8所示。 表6去冗余前后Top-k序列模式集合的变化(ADLs数据集) Table 6 The set of Top-k sequential patterns before and after eliminating redundancy(ADLs data set) 冗余Top-k集合 去冗余Topk集合 序列 对比度 序列 对比度 洗澡、吃早餐 1 洗澡、吃早餐 梳妆、洗澡、吃早餐 0.846154 梳妆、洗澡、吃早餐 0.769231 上厕所、梳妆、洗澡 0.769231 睡觉、上厕所、梳妆、洗澡 0.692308 洗澡、吃早餐、休息 0.769231 睡觉、上厕所、梳妆 0.59707 上厕所、梳妆、洗澡、吃早餐 0.769231 梳妆、洗澡 0.56044 通过实验结果可以发现，去冗余Top-k集合 2)实验2（加入剪枝策略前后的对比实验） 中出现了冗余T0p-k集合中没有出现的序列模 实验2的目标是比较算法1与加入剪枝策略 式。同时，去冗余Top-k集合中删去了冗余的序 后算法效率的变化。分别在ADLs数据集和 列模式。因此，本文的算法能够有成效地去除冗 Question数据集上进行对比实验，比较算法1和 余对比序列模式。 算法2运行的时间，来衡量算法的效率
minTopkCR = 0 1）创建集合 L，设置集合 L 的最小对比度阈 值 ； 2）创建队列，初始化队列 queue 为空； 3）计算正例集 D+的字母表 Σ ，将字母表中的 元素加入到 queue 中； 4）创建树的根节点，建立由根节点分别指向 字母表中每个元素的指针，令 min TopkCR = getMinTopkCR (L)； Sup(e,D+) ⩽ minTopkCR Σ e Σ e 5）如果 ( ) 则从字母表 中删除元素 ，对 中的每一个元素 ，把 e 添加 到队列的第一个序列的末尾，组成新的序列 P； 如果 Sup(P,D+) ⩾ minTopkCR ，则把 P 加入到 队列中； |L| < k P 如果 ，则在集合 L 寻找 P 的子序列 ′； P ′ P ′ P L minTopkCR 如果 被找到且 P 不是相对于 的冗余序 列，则把 加入集合 ,更 新 ，否则 把 P 加入集合 L，更新 min TopkCR； |L| = k CR(P,D+,D−) > min L P P ′ 6）如果 ，并且 TopkCR， 则在集合 寻找 的子序列 ； P ′ minTopkCR minTopkCR 如果 被找到，并且 P 不是相对于 P'的冗余 序列 ，则用 P 替换集合 L 中对比度最小的序列， 更新 ，否则用 P 替换集合 L 中对比度 最小的序列更新 ； 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 中列出了 实验中用到的数据集的特征。 表 5 数据集的特征 Table 5 The characteristics of the data sets 数据集 类别 |D+ | |D– | |Σ| |D| E.Coli E.Coli+E.Coli- 53 53 4 106 UJI Write+Write- 784 784 10 1 568 ADLs Activity+Activity- 13 21 9 34 Question Question+Question- 151 156 146 307 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 运行的时间，来衡量算法的效率。 表 6 去冗余前后 Top-k 序列模式集合的变化 (ADLs 数据集) Table 6 The set of Top-k sequential patterns before and after eliminating redundancy(ADLs data set) 冗余 Top-k 集合 去冗余 Top-k 集合 序列 对比度 序列 对比度 洗澡、吃早餐 1 洗澡、吃早餐 1 梳妆、洗澡、吃早餐 0.846 154 梳妆、洗澡、吃早餐 0.769 231 上厕所、梳妆、洗澡 0.769 231 睡觉、上厕所、梳妆、洗澡 0.692 308 洗澡、吃早餐、休息 0.769 231 睡觉、上厕所、梳妆 0.597 07 上厕所、梳妆、洗澡、吃早餐 0.769 231 梳妆、洗澡 0.560 44 ·684· 智 能 系 统 学 报 第 13 卷