·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 卷