第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 = get￾MinTopkCR (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·