【机器学习】去冗余Top-k对比序列模式挖掘

第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 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 至今已经有很多种序列模式被提出，包括周 期模式[1] 、偏序模式[2] 、闭合模式[3] 、对比序列模 式 [4] 、频繁序列模式[5]等。对比序列模式挖掘作为 数据挖掘中重要的一个问题，目前已经积累了大 量的研究成果[6-7]。对比序列模式是指在一类数 据集中频繁出现，而在另一类数据集中很少出现 的序列模式。对比序列模式可以描述不同数据集 之间的差异，在很多领域有广泛应用。例如，对 比序列模式可以用于纳税人行为分析[8] ，患者的 风险预测[9]等。在对比序列模式挖掘中，Top-k 对 比序列模式挖掘是一种重要的挖掘策略。 Top￾k 方法是指在给定的标准下挖掘出差异最大的 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≤k1O,则称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 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所示。 当四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 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加入到队列中； 字母表移除。 如果四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 = get￾MinTopkCR (L)； Σ e e Sup(P,D+) ⩾ minTopkCR 5）对 中的每一个元素 ，把 添加到 queue 的 第一个序列的末尾，组成新的序 列 P ，如果 则把 P 加入到队列中； |L| 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中列出了 队列中： 实验中用到的数据集的特征。 如果叫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 = get￾MinTopkCR (L)； Sup(e,D+) ⩽ minTopkCR Σ e Σ e 5）如果 ( ) 则从字母表 中删除元素 ，对 中的每一个元素 ，把 e 添加 到队列的第一个序列的末尾，组成新的序列 P； 如果 Sup(P,D+) ⩾ minTopkCR ，则把 P 加入到 队列中； |L| 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 卷

第5期 江冰，等：去冗余Top-k对比序列模式挖掘 ·685· 表7去冗余前后Top-k序列模式集合的变化(E.Coli数 120 据集) ◆-BFM Table 7 The set of Top-k sequential patterns before and 100 *-PBFM after eliminating redundancy(E.Coli data set) 冗余Top-k集合 去冗余Top-k集合 序列 对比度 序列 对比度 ATA 0.396226 ATA 0.396226 40 AAA 0.452830 AAA 0.452830 20 TATA 0.396226 TTTA 0.377358 2468101214161820 AATT 0.415094 TATA 0.396226 AAAA 0.415094 AATT 0.415094 (b)Question数据集 图2BFM和PBFM的效率对比 表8去冗余前后Top-k序列模式集合的变化(UJI数据集) Fig.2 Comparison of BFM and PBFM efficiencies Table 8 The set of Top-k sequential patterns before and after eliminating redundancy(UJI data set) 结束语 冗余Top-k集合 去冗余Top-k集合 本文首先提出了一种挖掘去冗余Top-k对比 序列 对比度 序列 对比度 序列模式的算法BFM,这是一种基于广度优先生 712 0.0816327 712 0.0816327 成树的算法。通过不断的比较子序列和超序列的 317 0.0790816 317 0.0790816 对比度，Top-k集合不断地更新，直到树结构的生 931 0.0880102 931 0.0880102 成过程结束。相比之前的Top-k对比序列模式挖 610 0.0880102 610 0.0880102 掘算法，BFM算法可以得到去冗余的Top-k集 126 0.0790816 126 0.0790816 合，并且不需要其他集合的辅助。 在BFM算法的基础上，提出了性能更好的 将k的值分别从1取到20，比较算法1(BFM) PBFM算法。与BFM算法相比，PBFM算法可以 和算法2(PBFM)运行的时间如图2所示。从图2 在更短的时间内完成挖掘任务，并且不需要额外 中可以看出，随着k值的增加，两种算法的运行时 的操作。 间都在增长，但PBFM的运行时间明显少于 BFM的运行时间。在ADLs数据集中，随着k值 参考文献： 逐渐变大，这一区别越来越明显。在Question数 [1]ZHANG Minghua,KAO Ben,CHEUNG D W,et al.Min- 据集中，当k值较小时，这一区别较为明显。随 ing periodic patterns with gap requirement from sequences 着k值的增大，Top-k集合的最小对比度minTopkCR [J].ACM transactions on knowledge discovery from data. 逐渐变小，当k≥18时，PBFM算法中删除的元素 2007,12):7. 个数较少，但PBFM算法运行的时间仍然少于 [2]PEI Jian,WANG Haixun,LIU Jian,et al.Discovering fre- BFM算法运行的时间。 quent closed partial orders from strings[J].IEEE transac- 4.0r tions on knowledge and data engineering,2006,18(11): 3.5 PBEM 1467-1481. 3.0 [3]YAN Xifeng,HAN Jiawei,AFSHAR R.CloSpan:mining: closed sequential patterns in large datasets[C]//Proceed- ings of the 3rd SIAM International Conference on Data Mining.San Francisco,USA,2003:166-177. 1.5 [4]JI Xiaonan,BAILEY J,DONG Guozhu.Mining minimal 1.0 distinguishing subsequence patterns with gap constraints 0.5 [J].Knowledge and information systems,2007,11(3): 259-286. 4 68101214161820 [5]ZAKI M J.SPADE:an efficient algorithm for mining fre- (a)ADLs数据集 quent sequences[J].Machine learning,2001,42(1/2):

k ⩾ 18 将 k 的值分别从 1 取到 20，比较算法 1(BFM) 和算法 2(PBFM) 运行的时间如图 2 所示。从图 2 中可以看出，随着 k 值的增加，两种算法的运行时 间都在增长， 但 PBFM 的运行时间明显少 于 BFM 的运行时间。在 ADLs 数据集中，随着 k 值 逐渐变大，这一区别越来越明显。在 Question 数 据集中，当 k 值较小时，这一区别较为明显。随 着 k 值的增大，Top-k 集合的最小对比度 minTopkCR 逐渐变小，当 时，PBFM 算法中删除的元素 个数较少，但 PBFM 算法运行的时间仍然少于 BFM 算法运行的时间。 5 结束语 本文首先提出了一种挖掘去冗余 Top-k 对比 序列模式的算法 BFM,这是一种基于广度优先生 成树的算法。通过不断的比较子序列和超序列的 对比度，Top-k 集合不断地更新，直到树结构的生 成过程结束。相比之前的 Top-k 对比序列模式挖 掘算法，BFM 算法可以得到去冗余的 Top-k 集 合，并且不需要其他集合的辅助。 在 BFM 算法的基础上,提出了性能更好的 PBFM 算法。与 BFM 算法相比，PBFM 算法可以 在更短的时间内完成挖掘任务，并且不需要额外 的操作。 参考文献： ZHANG Minghua, KAO Ben, CHEUNG D W, et al. Min￾ing periodic patterns with gap requirement from sequences [J]. ACM transactions on knowledge discovery from data, 2007, 1(2): 7. [1] PEI Jian, WANG Haixun, LIU Jian, et al. Discovering fre￾quent closed partial orders from strings[J]. IEEE transac￾tions on knowledge and data engineering, 2006, 18(11): 1467–1481. [2] YAN Xifeng, HAN Jiawei, AFSHAR R. CloSpan: mining: closed sequential patterns in large datasets[C]//Proceed￾ings of the 3rd SIAM International Conference on Data Mining. San Francisco, USA, 2003: 166–177. [3] JI Xiaonan, BAILEY J, DONG Guozhu. Mining minimal distinguishing subsequence patterns with gap constraints [J]. Knowledge and information systems, 2007, 11(3): 259–286. [4] ZAKI M J. SPADE: an efficient algorithm for mining fre￾quent sequences[J]. Machine learning, 2001, 42(1/2): [5] 表 7 去冗余前后 Top-k 序列模式集合的变化 (E.Coli 数 据集) Table 7 The set of Top-k sequential patterns before and after eliminating redundancy(E.Coli data set) 冗余 Top-k 集合 去冗余 Top-k 集合 序列 对比度 序列 对比度 ATA 0.396 226 ATA 0.396 226 AAA 0.452 830 AAA 0.452 830 TATA 0.396 226 TTTA 0.377 358 AATT 0.415 094 TATA 0.396 226 AAAA 0.415 094 AATT 0.415 094 表 8 去冗余前后 Top-k 序列模式集合的变化 (UJI 数据集) Table 8 The set of Top-k sequential patterns before and after eliminating redundancy(UJI data set) 冗余 Top-k 集合 去冗余 Top-k 集合 序列 对比度 序列 对比度 712 0.081 632 7 712 0.081 632 7 317 0.079 081 6 317 0.079 081 6 931 0.088 010 2 931 0.088 010 2 610 0.088 010 2 610 0.088 010 2 126 0.079 081 6 126 0.079 081 6 (b) Question数据集 BFM PBFM 120 100 80 60 40 20 运行时间/s 0 2 4 6 8 10 12 14 16 18 20 k 图 2 BFM 和 PBFM 的效率对比 Fig. 2 Comparison of BFM and PBFM efficiencies (a) ADLs数据集 BFM PBFM 4.0 3.5 3.0 2.5 2.0 1.5 1.0 0.5 运行时间/s 0 2 4 6 8 10 12 14 16 18 20 k 第 5 期 江冰，等：去冗余 Top-k 对比序列模式挖掘 ·685·

·686· 智能系统学报 第13卷 31-60. [J].Knowledge and information systems,2007,11(3): [6]YANG Hao,DUAN Lei,DONG Guozhu,et al.Mining 259-286. itemset-based distinguishing sequential patterns with gap [15]DENG Kang,ZAIANE O R.An occurrence based ap- constraint[C]//Proceedings of the 20th International Con- proach to mine emerging sequences[C]//Proceedings of ference on Database Systems for Advanced Applications. the 12th International Conference on Data Warehousing Hanoi,Vietnam,2015:39-54. and Knowledge Discovery.Bilbao,Spain,2010:275-284. [7]杨皓，段磊，胡斌，等.带间隔约束的Top-k对比序列模 [16]YU HH,CHEN Chunhao,TSENG V S.Mining emer- 式挖掘).软件学报，2015,26(11)：2994-3009. YANG Hao,DUAN Lei,HU Bin,et al.Mining Top-k dis- ging patterns from time series data with time gap con- tinguishing sequential patterns with gap constraint[J]. straint[J].International journal of innovative computing Journal of software,2015,26(11):2994-3009. information and control,2011,7(9):5515-5528 [8]ZHENG Zhigang,WEI Wei,LIU Chunming,et al.An ef- [17]WANG Xianming,DUAN Lei,DONG Guozhu,et al.Ef- fective contrast sequential pattern mining approach to tax- ficient mining of density-aware distinguishing sequential payer behavior analysis[J].World wide web,2016,19(4): patterns with gap constraints[C]/Proceedings of the 19th 633-651. International Conference on Database Systems for Ad- [9]GHOSH S,FENG Mengling,NGUYEN H,et al.Risk pre- vanced Applications.Bali,Indonesia,2014:372-387. diction for acute hypotensive patients by using gap con- strained sequential contrast patterns[J].AMIA annual sym- 作者简介： posium proceedings,2014,2014:1748-1757. 江冰.女，1995年生，硕土研究 生，主要研究方向为数据挖掘和生物 [10]FOURNIER-VIGER P,TSENG VS.Mining Top-K Non- 信息。 redundant association rules[Cl//Proceedings of the 20th International Symposium on Foundations of Intelligent Systems.Macau,China,2012,7661:31-40. [11]FOURNIER-VIGER P,TSENG V S.TNS:mining top-k non-redundant sequential rules[C]//Proceedings of the 谷飞洋，男，1991年生，硕士研究 28th Symposium on Applied Computing.Coimbra,Por- 生，主要研究方向为数据挖掘和生物 tugal,,2013:164-166. 信息。 [12]KAMEYA Y,SATO T.RP-growth:Top-k mining of rel- evant patterns with minimum support raising[C]//Proceed- ings of the 12th SIAM International Conference on Data Mining.Anaheim,USA.2012:816-827. [13]CHAN S,KAO B,YIP C L,et al.Mining emerging sub- 何增有，男，1976年生.教授，博 土生导师，博士，主要研究方向为数据 strings[C]//Proceedings of 8th International Conference 挖掘、生物信息。获得省部级奖励 on Database Systems for Advanced Applications.Kyoto, 3项。发表国际期刊论文40余篇，据 Japan,2003:119-126. Google Scholar统计，发表的论文被引 [14]JI Xiaonan,BAILEY J,DONG Guozhu.Mining minimal 用2600余次，出版英文学术专著 distinguishing subsequence patterns with gap constraints 1部

31–60. YANG Hao, DUAN Lei, DONG Guozhu, et al. Mining itemset-based distinguishing sequential patterns with gap constraint[C]//Proceedings of the 20th International Con￾ference on Database Systems for Advanced Applications. Hanoi, Vietnam, 2015: 39–54. [6] 杨皓, 段磊, 胡斌, 等. 带间隔约束的 Top-k 对比序列模 式挖掘[J]. 软件学报, 2015, 26(11): 2994–3009. YANG Hao, DUAN Lei, HU Bin, et al. Mining Top-k dis￾tinguishing sequential patterns with gap constraint[J]. Journal of software, 2015, 26(11): 2994–3009. [7] ZHENG Zhigang, WEI Wei, LIU Chunming, et al. An ef￾fective contrast sequential pattern mining approach to tax￾payer behavior analysis[J]. World wide web, 2016, 19(4): 633–651. [8] GHOSH S, FENG Mengling, NGUYEN H, et al. Risk pre￾diction for acute hypotensive patients by using gap con￾strained sequential contrast patterns[J]. AMIA annual sym￾posium proceedings, 2014, 2014: 1748–1757. [9] FOURNIER-VIGER P, TSENG VS. Mining Top-K Non￾redundant association rules[C]//Proceedings of the 20th International Symposium on Foundations of Intelligent Systems. Macau, China, 2012, 7661: 31–40. [10] FOURNIER-VIGER P, TSENG V S. TNS: mining top-k non-redundant sequential rules[C]//Proceedings of the 28th Symposium on Applied Computing. Coimbra, Por￾tugal, 2013: 164–166. [11] KAMEYA Y, SATO T. RP-growth: Top-k mining of rel￾evant patterns with minimum support raising[C]//Proceed￾ings of the 12th SIAM International Conference on Data Mining. Anaheim, USA, 2012: 816–827. [12] CHAN S, KAO B, YIP C L, et al. Mining emerging sub￾strings[C]//Proceedings of 8th International Conference on Database Systems for Advanced Applications. Kyoto, Japan, 2003: 119–126. [13] JI Xiaonan, BAILEY J, DONG Guozhu. Mining minimal distinguishing subsequence patterns with gap constraints [14] [J]. Knowledge and information systems, 2007, 11(3): 259–286. DENG Kang, ZAIANE O R. An occurrence based ap￾proach to mine emerging sequences[C]//Proceedings of the 12th International Conference on Data Warehousing and Knowledge Discovery. Bilbao, Spain, 2010: 275–284. [15] YU H H, CHEN Chunhao, TSENG V S. Mining emer￾ging patterns from time series data with time gap con￾straint[J]. International journal of innovative computing information and control, 2011, 7(9): 5515–5528. [16] WANG Xianming, DUAN Lei, DONG Guozhu, et al. Ef￾ficient mining of density-aware distinguishing sequential patterns with gap constraints[C]//Proceedings of the 19th International Conference on Database Systems for Ad￾vanced Applications. Bali, Indonesia, 2014: 372–387. [17] 作者简介： 江冰，女，1995 年生，硕士研究 生，主要研究方向为数据挖掘和生物 信息。 谷飞洋，男，1991 年生，硕士研究 生，主要研究方向为数据挖掘和生物 信息。 何增有，男，1976 年生，教授，博 士生导师，博士，主要研究方向为数据 挖掘、生物信息。获得省部级奖励 3 项。发表国际期刊论文 40 余篇，据 Google Scholar 统计，发表的论文被引 用 260 0 余次，出版英文学术专著 1 部。 ·686· 智 能 系 统 学 报 第 13 卷