自Agrawal和Srikant^[1]提出序列模式挖掘以来,序列模式作为数据挖掘一项重要任务,吸引了大批研究者的关注,多种不同的序列模式陆续被提出来,如频繁序列模式^[2]、对比序列模式^[3]、闭合模式^[4]、偏序模式^[5]、周期模式^[6]等等.在实际生活中,序列模式有着广泛的应用,例如,卫生疾控部门可以挖掘传染病传播在时间序列上的模式,其挖掘结果可用于发现传染病时空聚集性暴发规律,进而为防控工作提供参考;生物科学家可以通过分析DNA和蛋白质序列寻找疾病产生的根源,研发新药物;电力公司通过分析历史用电数据,提高对电力负荷预测的准确度.

序列挖掘中广泛使用的间隔约束的概念,让模式的匹配更加灵活.间隔约束是一个由两个非负整数确定的区间,表示序列模式中两个相邻元素间允许间隔的元素数目的最小值和最大值.例如,令间隔约束为[1, 3],序列模式P=at,若P能够在序列S中匹配,意味S中存在元素a和元素t,并且存在一组at,a在t之前,且两者之间最少间隔1个元素,最多间隔3个元素.

现有的关于对比序列模式的挖掘工作,如文献[3, 7],都需要用户预先设定正例支持度阈值α、负例支持度阈值β和间隔约束γ.其目标是在间隔约束下,挖掘出正例支持度大于等于α,并且负例支持度小于等于β的最小化模式.但是,这类挖掘算法有两个问题:(a) 用户很难设定合适的支持度阈值,如果设定了不合适的支持度阈值,挖掘出的模式可能不满足用户的期望;(b) 使用最小化约束进行剪枝,虽然减少了搜索空间,但可能会丢失一些对比显著的模式.我们以文献[3]提出的算法为例进行说明(文献[7]是基于文献[3]研究工作的扩展).

例1:表 1示例了一个含有两个类别的基因序列数据集,其中,D₊代表正例数据集,D_-代表负例数据集.令γ=[0, 2],运用文献[3]提出的算法挖掘对比模式,即,在D₊中支持度大于等于α,在D_-中支持度小于等于β,且满足γ的最小化序列.

设置α=0.9,β=0.1,挖掘结果为空集;将α降低到0.83,可以得到模式ct;继续将α降低至0.66,或者将β增大为0.25才能挖掘到新的模式.由此可见,在不具备先验知识的情况下,用户并不容易设定合适的支持度阈值(α,β).

设置α=1.0,β=0.25时,可得到两个模式:at和gt,候选模式agt的正例支持度为1.0,负例支持度为0.25,因此满足支持度约束.但由于模式agt是模式at和模式gt的超序列,根据最小化模式约束,文献[3]算法会将其剪掉,于是,模式agt不会出现在结果集中.由此可见,最小化模式约束可能导致文献[3]算法丢失一些对比显著的模式.

从例1可以看出,不恰当的支持度阈值和最小化约束可能导致不能发现所有对比显著的模式.反复调整支持度阈值,必然增加用户使用算法的难度.故本文引入top-k约束,挖掘在全部对比模式中支持度对比最显著的k个对比序列模式.从分析对象和结果来看,挖掘top-k对比序列模式与挖掘满足支持度阈值的最小对比模式很相似,但是它们之间有本质的区别,具体表现在:

$ \bullet $     挖掘目标不同:带间隔约束的top-k对比序列模式是指支持度变化最为显著的k个对比序列模式,而带间隔约束的满足支持度阈值的对比模式指的是满足支持度阈值的对比序列模式.

$ \bullet $     挖掘过程不同:带间隔约束的top-k对比序列模式不会使用最小化约束来进行剪枝,保证了支持度变化显著的对比序列模式不会由于其子序列满足条件而被剪掉.

$ \bullet $     应用难度不同:在挖掘带间隔约束的top-k对比序列模式时,用户仅需设定期望得到的模式的数目,而不需要设定具体的正例支持度阈值和负例支持度阈值.一般来说,设定k值比较直观,因而不会由于没有足够的先验知识,设定不合适的支持度阈值,导致丢失一些对比显著的模式.

据我们所知,目前还没有工作在带间隔约束的对比序列模式挖掘的基础上引入top-k的概念.带间隔约束的top-k对比序列模式挖掘旨在发现在两个数据集之间支持度变化最为显著的k个对比序列模式,该方法可以避免由于不合适的阈值引起的对比显著的模式的错失;仅需用户设定期望得到的模式的数目即可,使用难度较以往的方法大大降低;同时,增强了挖掘结果的可解释性.本文主要工作包括:(a) 分析了设置正例支持度阈值和负例支持度阈值来挖掘对比序列模式的不足之处;(b) 提出了带间隔约束的top-k对比序列模式挖掘问题;(c) 设计了带间隔约束的top-k对比序列模式挖掘算法kDSP-Miner(top-k distinguishing sequential patterns with gap constraint miner);(d) 针对序列元素集合为高维的应用,设计了kDSP-Miner的多线程版本MT-kDSP-Miner (multi-thread kDSP-miner);(e) 在真实数据集上,验证了提出算法的有效性和执行效率.

本文第1节介绍相关工作.第2节定义本文的研究问题.第3节讲述本文设计的带间隔约束的top-k对比序列模式挖掘算法和其多线程版本的设计.第4节在真实世界的人类活动记录数据集、DNA数据集和Bible数据集上验证本文提出算法的有效性和执行效率.第5节对本文的工作进行总结,并介绍下一步的工作方向.

1 相关工作

由于在众多领域的研究中发挥着重要作用,近年来,序列模式挖掘得到了越来越多的关注.文献 [8, 9, 10]研究了蛋白质和核苷酸序列分析的问题;文献[11]将序列模式挖掘方法应用于软件缺陷的特征发现;文献[12]对音乐数据进行了深入分析;文献[13]提出了一个与语言无关的关键字抽取算法,并且不需要语义字典.

在序列模式中考虑间隔约束,可以提高序列模式的灵活性,扩大序列模式的应用范围.因此,挖掘带间隔约束的序列模式是序列模式挖掘的一个常见问题.文献[14]针对频繁闭合序列模式挖掘问题设计了Gap-BIDE的算法,该算法不需要维持候选集就可高效地得到所有带间隔约束的频繁闭合序列模式.文献[6]解决了在一条序列中挖掘带间隔约束的频繁周期序列模式的问题.文献[15]针对单条序列样本,研究了从中挖掘满足one-off条件和间隔约束的频繁模式的问题.

对比序列模式能够描述两类序列样本中的对比信息,识别不同类别样本集合的特征,适用于多个领域的序列模式分析.文献[3]设计了ConSGapMiner以发现最小化的对比序列模式.文献[16]建立了一个以对比模式作为特征的分类器,应用在多肽折叠预测问题上.文献[17]在对比序列模式挖掘中加入了“密度”的概念,并设计了算法挖掘满足“密度”约束的对比序列模式.文献[7]将基于单元素序列的最小化对比序列模式挖掘扩展为基于元素集合序列的最小化对比序列模式挖掘.

在数据挖掘应用中,经常可以得到大量的模式,top-k约束可以在所有的结果中选择最满足用户期望条件的k个模式,简化挖掘的运行参数设置,提高结果的可解释性.文献[18]提出了在设定最小支持度的基础上挖掘top-k频繁闭合序列模式.文献[19]挖掘两个数据集中的显露序列,使用距离而不是支持度来度量一个序列的显著程度.文献[20]在不确定的流数据上使用滑动窗口模型和Chernoff边界近似的对模式进行计数,以发现top-k模式.

据我们所知,与本文最为相似的工作是文献[3],但文献[3]与本文有如下不同:首先,文献[3]旨在挖掘满足支持度阈值的最小化对比序列模式,而本文旨在挖掘支持度变化最为显著的top-k对比序列模式;其次,文献[3]采用最小化模式约束,可能会导致无法发现一些对比显著的模式,而本文不会;再有,文献[3]需要设定正例样本的最小支持度阈值与负例样本的最大支持度阈值,而本文仅需设置期望发现的对比最显著的模式个数;最后,本文设计了多线程以提高算法的适用性,而文献[3]没有.因此,本文提出的算法相对于文献[3]而言,使用更加方便和直观,不需要对数据集有先验知识,也不需要多次调整支持度阈值来发现模式,因而适用性也更强.

2 问题定义

给定一个有穷元素集合Σ,将其称为字母表.由Σ中的元素构成的有序元素列称为序列,表示为S=e₁,e₂,…,e_n.对于任意$i \in \left[ {1,n} \right]$,有${e_i} \in \sum $成立.使用len(S)来表示序列S的长度,即,S中包含的元素的数目.为了方便表述,使用S[i]来表示序列S中第i个位置上的元素(1≤i≤len(S)).对于序列S上的两个元素S[i]和S[j](1≤i<j≤len(S)),出现在S[i]和S[j]之间的元素个数称为S[i]和S[j]之间的间隔,记为Gap(S,i,j)=j-i-1.

例2:DNA序列的字母表Σ={a,c,g,t},对于DNA序列S=a,t,a,c,g,t,len(S)=6,S[1]=a,S[5]=g,S[1]与S[5]之间的间隔Gap(S,1,5)=5-1-1=3.

对于两个序列S和S'(len(S)≥len(S')),若存在一系列整数1≤k₁<k₂<…<k_len(S')≤len(S),使得S'[i]=S[k_i]对于$i \in [1,len(S')]$恒成立,则称S'是S的子序列,S是S'的超序列,将$\left\langle {{k_1},{k_2}, \ldots ,{k_{len}}{{_{(S'}}_)}} \right\rangle $称为序列S'在序列S中的一个实例.

间隔约束通常被定义为一个由两个非负整数确定的区间,表示为γ=[γ.min,γ.max](0≤γ.min≤γ.max).若$\left\langle {{k_1},{k_2}, \ldots ,{k_{len}}{{_{(S'}}_)}} \right\rangle $是序列S'在序列S中的一个实例,并且对于1≤i≤len(S')-1,γ.min≤Gap(S,k_i,k_i+1)≤γ.max恒成立,则称S'是S在间隔约束γ下的子序列,表示为$S' \subseteq {}_\gamma S$.为简洁起见,后文中的子序列和超序列都是指在间隔约束下的子序列和超序列.

例3:对于序列S=a,g,c,t,g,a和序列S'=a,g,〈1,2〉和〈1，5〉都是S'在S中的实例.若令γ=[0,2],0≤Gap(S,1,2)= 2-1-1=0≤2,则$S'{ \subseteq _\gamma }S$.

给定序列集合D,在间隔约束γ下,序列P在数据集D中的支持度由公式(1)得到:

${\rm{Sup}}(P,D,\gamma ) = \frac{{|\{ S \in D|P{ \subseteq _\gamma }S\} |}}{{|D|}}$ (1)

(1)

其中,|D|为集合D中包含的序列的数目.

定义 1(带间隔约束的对比度). 给定间隔约束γ、序列P、正例数据集D₊和负例数据集D_-,P的对比度定义为

$CR(P,{D_ + },{D_ - },\gamma ) = Sup(P,{D_ + },\gamma ) - Sup(P,{D_ - },\gamma )$ (2)

(2)

后文中关于支持度和对比度的讨论都是在间隔约束γ下进行,简洁起见,将Sup(P,D,γ)简记为Sup(P,D),将CR(P,D₊,D_-,γ)简记为CR(P,D₊,D_-).

例4:考虑表 1中的DNA数据集,|D₊|=6,|D_-|=4.在间隔约束γ=[0,2]下,令P=agt,那么Sup(P,D₊)=1.0,Sup(P, D_-)=0.25,故CR(P,D₊,D_-)=1.0-0.25=0.75.

给定间隔约束γ、正例数据集D₊和负例数据集D_-,若候选序列模式P满足CR(P,D₊,D_-)>0,则将P称为一个带间隔约束的对比序列模式,简称为对比序列模式.

定义 2(带间隔约束的top-k对比序列模式). 给定间隔约束γ、正例数据集D₊和负例数据集D_-,在所有得到的对比序列模式中,对比度最大的k个模式被称为带间隔约束的top-k对比序列模式,简称为top-k对比序列模式.

给定间隔约束γ、正例数据集D₊和负例数据集D_-,带间隔约束的top-k对比序列模式挖掘的目标是:在满足γ的前提下,找出D₊和D_-之间对比度最大的k个对比序列模式.

值得一提的是:在进行top-k选择时,若有多个模式的对比度(公式(2)计算结果)相等,则按如下规则排序对比度:(1) 优先选择长度更短的模式;(2) 若长度相同,则按照算法中的元素顺序选择排序靠前的模式.在实践中,用户也可以根据实际情况修改规则,以适应具体应用的需求.

虽然本文与文献[3]都是关于对比序列模式挖掘的研究工作,但是本文的研究问题定义侧重于对比度的大小,并不要求对比序列模式满足最小化约束,因此能够挖掘出文献[3]中对比度显著(满足k最大)但却不满足最小化约束的模式.

命题 1. 文献[3]的ConSGapMiner算法不适用于挖掘带间隔约束的top-k对比序列模式.

证明:根据文献[3]的定义,给定模式P和支持度阈值α,β,ConSGapMiner算法采用如下剪枝策略:

(1) 若Sup(P,D₊)<α,那么P及其超序列被剪掉;

(2) 若Sup(P,D₊)≥α,且Sup(P,D_-)≤β,那么P的超序列全部被剪掉.

令模式P'满足len(P')=len(P)+1且P'[i]=P[i](1≤i≤len(P)),若有Sup(P,D₊)=Sup(P',D₊),Sup(P,D_-)>Sup(P', D_-),那么CR(P,D₊,D_-)<CR(P',D₊,D_-).

由于ConSGapMiner算法采用深度优先遍历集合枚举树的方式产生候选,ConSGapMiner算法会先产生模式P,由于模式P满足了支持度阈值条件,那么根据剪枝条件(2),模式P的所有超序列将被剪掉.因此,P'不会出现在挖掘结果中.

所以,ConSGapMiner算法不能保证发现所有带间隔约束的top-k对比序列模式.

例5:考虑表 1中的DNA数据集,令k=5,间隔约束γ=[0,2],D₊为正例数据集,D_-为负例数据集,那么挖掘得到的带间隔约束的top-k对比序列模式见表 2.

为方便描述,表 3中列出了本文常用的符号及定义.

3 kDSP-Miner算法设计

为了避免用户设定不合适的支持度阈值,导致不能发现对比显著的对比序列模式,本文提出在两个数据集之间挖掘支持度对比最显著的k个对比序列模式的问题,并设计了一种带间隔约束的top-k对比序列模式挖掘算法,将其命名为kDSP-Miner.给定间隔约束,kDSP-Miner可以挖掘出在正例数据集和负例数据集之间对比度最大的k个对比序列模式.在给出${\rm{Na\ddot 1ve}}$算法的基础上,本文设计了3个剪枝策略以及1个启发策略,从而实现kDSP-Miner.与${\rm{Na\ddot 1ve}}$算法相比,kDSP-Miner算法的执行效率有明显的提升.针对序列元素集合高维的应用,本文在kDSP-Miner的基础上实现了kDSP-Miner的多线程版本,记为MT-kDSP-Miner.接下来,我们首先给出${\rm{Na\ddot 1ve}}$算法;并以此为基础,介绍kDSP-Miner算法的关键技术和MT-kDSP-Miner的设计思路.

3.1 ${\rm{Na\ddot 1ve}}$算法

${\rm{Na\ddot 1ve}}$算法通过扫描数据集,生成字母表Σ;然后,利用Σ生成候选对比序列模式;最后输出结果.为了保证生成模式的完备性,即,找出带间隔约束的top-k对比序列模式而不产生遗漏,${\rm{Na\ddot 1ve}}$算法采用在序列数据模式挖掘中广泛使用的集合枚举树的方法^[21]生成候选对比序列模式.给定字母表Σ,集合枚举树按照集合元素的全序,枚举集合中元素的所有可能组合.图 1展示了对于基因数据集Σ={a,c,g,t},所生成的集合枚举树.

${\rm{Na\ddot 1ve}}$算法以深度优先的方式遍历整个集合枚举树,在遍历过程中,逐一产生候选对比序列模式.

性质 1. 若候选模式P满足Sup(P,D₊)=0,P及其超序列都不可能是top-k对比序列模式.

证明:用反证法证明.

假设候选模式P满足Sup(P,D₊)=0,且P及其超序列是top-k对比序列模式,即$P \subseteq {}_\gamma P'$,使得:

$CR(P',{D_ + },{D_ - }) \ge min\{ CR(P'',{D_ + },{D_ - })|P'' \in R\} > 0,$

其中,R为存储结果的集合.

因为候选模式P满足Sup(P,D₊)=0,

所以,根据Apriori性质^[1],对于所有的候选模式$P{ \subseteq _\gamma }P',Sup(P',{D_ + }) \le Sup\left( {P,{D_ + }} \right) = 0$.

所以,$CR(P',{D_ + },{D_ - }) = S{\rm{up}}P,{D_ + } - S{\rm{up}}(P',{D_ - }) \le S{\rm{up}}P,{D_ + } - 0{\rm{ = }}0$

与假设矛盾.

所以,若候选模式P满足Sup(P,D₊)=0,P及其超序列都不可能是top-k对比序列模式.

根据性质1,可以得到遍历集合枚举树的停止条件:若候选模式P满足Sup(P,D₊)=0,则剪去P对应节点及其所有子孙节点.算法1给出了 ${\rm{Na\ddot 1ve}}$算法的伪代码.

算法 1. ${\rm{Na\ddot 1ve}}$算法.

输入:正例数据集D₊、负例数据集D_-、间隔约束γ和参数k.

输出:在间隔约束γ下,D₊和D_-之间对比度最大的k个对比序列模式的集合R.

1:   $R \leftarrow \emptyset $                //R中仅保存对比度最大的k个对比序列模式

2:   $\Sigma \leftarrow scan({D_ + },{D_ - })$                //扫描数据集D₊和D_-,生成数据集对应的字母表

3:   FOR 候选模式PDO            //按照深度优先遍历基于Σ的集合枚举树

4:        IF Sup(P,D₊)=0 DO           //遍历集合枚举树的停止条件

5:            剪去P的全部超序列;

6:       END IF

7:       IF CR(P,D₊,D_-)>0 DO

8:            $IF|R| < k$ or $|R| = k and CR(P,D + ,D - ) \ge min\{ CR(P\prime ,D + ,D - )|P\prime \in R\} {\rm{ }}DO$

9:               $R \leftarrow R \cup \left\{ P \right\};$           //如果|R|>k,从R中移除对比度最低的模式

10:            END IF

11:           END IF

12:       END FOR

13:    RETURN R

例6:考虑的基因数据集(表 1),间隔约束γ=[0,2],候选模式P=att,由于Sup(P,D₊)=0,所以P的所有超序列,如atta,attc,attg,attt及它们的超序列都将被剪去.

3.2 剪枝和加速策略

${\rm{Na\ddot 1ve}}$算法中,仅通过一个停止条件进行剪枝,遍历了大量无效的节点,这些节点对应的候选序列模式都不是top-k对比序列模式.

性质 2. 如果一个元素e只出现在负例数据集中,则所有包含元素e的候选模式P都不可能满足top-k对比序列模式的定义.

证明:

因为元素$e \in \Sigma ,e \in {D_ - },$并且e∉D₊,

所以,Sup(e,D₊)=0.

所以,根据Apriori性质,对于所有的候选模式$e{ \subseteq _\gamma }P,Sup\left( {P,{D_ + }} \right) \le Sup\left( {e,{D_ + }} \right) = 0.$

所以,$CR(P,D + ,D - ) = Sup(P,D + ) - Sup(P,D - ) \le Sup(P,D + ) - 0 \le 0 - 0 = 0.$

所以,由定义2可知,top-k对比序列模式必须满足对比度大于0.

所以,包含元素e的候选模式P不可能是top-k对比序列模式.

由性质2我们得到剪枝策略1.

剪枝策略 1(负例元素剪枝策略). 对于任意元素e∈Σ,如果e∈D_-,并且e∉D₊,将e从Σ中移除.

性质 3. 在top-k对比序列模式挖掘过程中,当|R|=k,令$C{R_k} = min\{ CR(P'',{D_ + },{D_ - })|P'' \in R\} ,$且Sup(P,D₊)<CR_k,那么P及其超序列都不是top-k对比序列模式.

证明:假设结果集|R|=k,令$C{R_k} = min\{ CR(P'',{D_ + },{D_ - })|P'' \in R\} .$

因为Sup(P,D₊)<CR_k,

所以,根据Apriori性质,对于所有的候选模式P⊆_γP',Sup(P',D₊)≤Sup(P,D₊)<CR_k.

所以,$CR(P\prime ,D + ,D - ) = Sup(P\prime ,D + ) - Sup(P\prime ,D - ) \le Sup(P\prime ,D + ) - 0 = Sup(P\prime ,D + ) < C{R_k}.$

所以,候选模式P'(P及其超序列)的对比度均小于当前结果集中的最小对比度,必然小于最终结果集中的最小对比度,并且|R|=k.

所以,P及其超序列不可能满足top-k对比序列模式的定义.

由性质3我们得到剪枝策略2.

剪枝策略 2(正例支持度 k 剪枝策略). 在top-k对比序列模式挖掘过程中,当|R|=k,且在这k个模式中,对比度的最小值为CR_k时,若候选模式P在正例数据集中的支持度小于CR_k,即Sup(P,D₊)<CR_k,则剪去P对应节点及其所有子孙节点.

性质 4. 在top-k对比序列模式挖掘过程中,当|R|=k时,令CR_k=min{CR(P',D₊,D_-)|P'∈R},对于任意元素e∈Σ,且Sup(e,D₊)<CR_k,所有包含元素e的候选模式P都不是top-k对比序列模式.

证明:假设结果集|R|=k,令$C{R_k} = min\{ CR(P\prime ,D + ,D - )|P\prime \in R\} $.

因为元素e∈Σ,Sup(e,D₊)<CR_k,

所以,根据Apriori性质,所有的包含元素e的候选模式$e \subseteq {}_\gamma P,Sup(P,D + ) \le Sup(e,D + ) < C{R_k}$.

所以,$CR(P,D + ,D - ) = Sup(P,D + ) - Sup(P,D - ) \le Sup(P,D + ) - 0 = Sup(P,D + ) < C{R_k}.$

所以,候选模式P'(所有包含元素e的候选模式)的对比度均小于当前结果集中的最小对比度,必然小于最终结果集中的最小对比度,并且|R|=k.

所以,所有包含元素e的候选模式不可能满足top-k对比序列模式的定义.

由性质4我们得到剪枝策略3.

剪枝策略 3(元素 k 剪枝策略). 在top-k对比序列模式挖掘过程中,当|R|=k,且在这k个模式中,对比度的最小值为CR_k时,对于任意元素e∈Σ,Sup(e,D₊)<CR_k,剪去在集合枚举树中所有包含元素e的节点.

在实践中我们发现,在上述3个剪枝策略中,负例元素剪枝策略(剪枝策略1)可以在枚举过程之前使用;正例支持度k剪枝策略(剪枝策略2)一般来说是最有效的剪枝策略,但它和元素k剪枝策略(剪枝策略3)都是要找到k个对比序列模式之后才开始生效,所以尽快找到对比度尽可能大的k个对比序列模式能够加速整个枚举过程,减少不必要的尝试.

那么,怎样才能尽快找到对比度尽可能大的k个对比序列模式呢?根据集合枚举树的性质,容易想到改变集合枚举树的枚举顺序,先枚举更可能产生对比序列模式的元素.为此,对Σ中的元素排序:(a) 按CR(e,D₊,D_-)从大到小排序;(b) 按Sup(e,D₊)从大到小排序.依排序结果遍历集合枚举树,可望比在原来顺序下遍历集合枚举树更快地找到对比度大的对比序列模式,从而使剪枝策略2和剪枝策略3能够尽快生效,减少算法的运行时间.

启发策略 1(排序加速策略). 对Σ中的所有元素按照CR(e,D₊,D_-)降序,若相同,则按Sup(e,D₊)降序进行排列,排序结果记为Σ'.kDSP-Miner算法按Σ'中元素的顺序遍历集合枚举树,生成候选对比序列模式.

实验结果表明,应用启发策略1能够有效地加速kDSP-Miner算法的执行效率(详见第4.3节).

值得一提的是:应用启发策略1并没有增加kDSP-Miner的计算量,因为Σ中的元素即为长度1的候选模式.此外,第3.3节将介绍:在多线程版本的kDSP-Miner中,Σ中元素的对比度也是线程计算任务分配的重要依据.

在上述剪枝策和启发策略基础上,算法2示例了kDSP-Miner算法的伪代码.

算法 2. kDSP-Miner算法.

输入:正例数据集D₊、负例数据集D_-、间隔约束γ和参数k.

输出:在间隔约束γ下,D₊和D_-之间对比度最大的k个对比序列模式的集合R.

1:  $R \leftarrow \emptyset $               //R中仅保存对比度最大的k个对比序列模式

2:  $\Sigma \leftarrow scan\left( {{D_ + }} \right)$            //仅仅扫描数据集D₊,生成候选元素集合,剪枝策略1

3:  $\Sigma ' \leftarrow sort(\Sigma )$              //对Σ进行排序,启发策略1

4:  $IF \exists e \in \Sigma andCR(e,D + ,D - ) > 0$

5:       $R \leftarrow R \cup \left\{ e \right\}$;           //利用排序信息加快算法,如果|R|>k,移除R中对比度最小的模式

6:  END IF

7:  FOR 候选模式PDO            //按照深度优先遍历基于Σ'的集合枚举树(跳过长度为1的模式)

8:    IF Sup(P,D₊)=0 DO             //遍历集合枚举树的停止条件

9:         剪去P的全部超序列;

10:    END IF

11:    IF |R|=k and Sup(P,D₊)<min{CR(P',D₊,D_-)|P'∈R} DO          //剪枝策略2

12:        剪去P的全部超序列;

13:    END IF

14:     IF |R|=k and ∃e∈P and Sup(e,D₊)<min{CR(P',D₊,D_-)|P'∈R} DO     //剪枝策略3

15:      剪去所有包含e的节点;

16:     END IF

17:    IF CR(P,D₊,D_-)>0 DO

18:    IF |R|<k or |R|=k and CR(P,D₊,D_-)≥min{CR(P',D₊,D_-)|P'∈R} DO

19:       $R \leftarrow R \cup \left\{ P \right\}$;      //如果|R|>k,从R中移除对比度最低的模式

20:  END IF

21:   END IF

22: END FOR

23: RETURN R

定理 1. 算法2能够找出对比度最大的k个对比序列模式(完备性).

证明:使用反证法证明.

假设存在候选对比序列模式P,满足$CR(P,{D_ + },{D_ - }) > min\{ CR(P'',{D_ + },{D_ - })|P'' \in R\} $,且P∉R,R为最终的结果集.由于kDSP-Miner算法采用遍历集合枚举树的方式来生成对比序列模式,那么P必然被剪枝策略1、剪枝策略2或剪枝策略3剪掉.

如果是模式P由剪枝策略1剪掉,那么存在e∈P,且e∈D_-,并且e∉D₊,所以,

$Sup\left( {P,{D_ + }} \right) = 0,CR(P,{D_ + },{D_ - }) \le Sup\left( {P,{D_ + }} \right) - 0 = 0 < min\{ CR(P'',{D_ + },{D_ - })|P'' \in R\} .$

与假设矛盾.

令R'为P被剪掉的时候对比度最大的k个对比模式的集合,那么可得:

$min\{ CR(P'',{D_ + },{D_ - })|P'' \in R'\} \le min\{ CR(P'',{D_ + },{D_ - })|P'' \in R\} .$

如果模式P是由剪枝策略2剪掉,那么P'⊆_γP,且$Sup(P',{D_ + }) < min\{ CR(P'',{D_ + },{D_ - })|P'' \in R'\} $,所以,$\begin{array}{l} CR(P,{D_ + },{D_ - }) \le Sup\left( {P,{D_ + }} \right) - 0 = Sup\left( {P,{D_ + }} \right)\\ \le Sup(P',{D_ + }) < min\{ CR(P'',{D_ + },{D_ - })|P'' \in R'\} \\ \le min\{ CR(P'',{D_ + },{D_ - })|P'' \in R\} \end{array}$.

与假设矛盾.

如果模式P是由剪枝策略3剪掉,那么存在e∈P,且e∈Σ,并且Sup(e,D₊)<min{CR(P',D₊,D_-)|P'∈R'},所以, Sup(P,D₊)≤Sup(e,D₊),

$\begin{array}{l} CR(P,{D_ + },{D_ - }) \le Sup\left( {P,{D_ + }} \right) - 0 = Sup\left( {P,{D_ + }} \right) \le Sup\left( {e,{D_ + }} \right) < min\{ CR(P',{D_ + },{D_ - })|P' \in R'\} \\ \le min\{ CR(P'',{D_ + },{D_ - })|P'' \in R\} . \end{array}$

与假设矛盾.

启发策略1仅改变集合枚举树的枚举顺序,其本身不会对集合枚举树进行剪枝,所以启发策略不会改变挖掘结果.

故算法2能够找出对比度最大的k个对比序列模式.

3.3 多线程kDSP-Miner算法设计

算法2主要由两部分构成:生成候选元素(步骤2、步骤3)和生成候选模式(步骤4~步骤22).其中,

$ \bullet $     生成候选元素包括对数据集进行扫描和对Σ进行排序,时间复杂度分别为O(|D₊|+|D_-|)和O(|Σ|log|Σ|),即,多项式级的;

$ \bullet $     生成候选模式需要遍历整个集合枚举树.理论上,给定最大长度l(l≥1),集合枚举树中包含|Σ|^l个候选模式.可见,对于具有高维Σ的序列集合,候选模式数量呈指数增长.

为了增强kDSP-Miner处理高维Σ序列数据的适用性,我们提出多线程版本的kDSP-Miner,记为MT-kDSP- Miner.设计思路的关键是:利用多线程技术实现候选模式对比度的并行计算.接下来,我们介绍MT-kDSP-Miner的设计细节.

典型情况是,对于含高维Σ的序列数据集合,|Σ|>>m(m为线程总数).这样,以集合枚举树中1项集为根节点划分集合枚举树,可以得到|Σ|棵不相交的子树.MT-kDSP-Miner以每棵子树为单位分配计算任务,因而不会重复计算,并且能保证算法的完备性.若出现|Σ|<m的情况,则需要进一步划分子树.

对Σ的所有元素(即1项集)按启发策略1进行排序得到Σ',设元素e在Σ'的排序为eid(1≤eid≤|Σ|),那么以e为根节点的子树,被分配给编号为tid=(eid+1)%m(1≤tid≤m)的线程.这样,每个线程负责遍历大约|Σ|/m棵子树,每个线程被分配的任务大致相等,实现负载均衡.

例7:对于表 1的数据集,Σ={a,c,g,t},启发策略排序后为Σ'={t,a,c,g},若线程数目m=2,那么MT-kDSP-Miner将集合枚举树以元素t、元素c分别为根节点的子树分配给一个线程,以元素g、元素c分别为根节点的子树分配给另一个线程.

不同于kDSP-Miner按深度优先顺序依次考察集合枚举树每个节点对应候选模式的对比度,MT-kDSP- Miner对多棵子树并行遍历.需要注意的是,剪枝策略2和剪枝策略3依赖于当前全局的挖掘结果,为了让所有线程及时地运用剪枝策略2和剪枝策略3,在MT-kDSP-Miner中,所有线程共享结果集.即,在挖掘过程中,所有线程同步更新当前top-k的挖掘结果.

值得注意的是:线程数目并不是越多越好,因为CPU的计算能力有限,随着线程数目增加,MT-kDSP-Miner算法运行时间总体上呈先下降,然后缓慢上升的趋势.实验中发现:在单机的环境下,当线程数目为4~5时,MT- kDSP-Miner执行效率最高(详见第4.4节).

4 实 验 4.1 实验环境

本文在4组真实数据集上进行实验,以验证kDSP-Miner算法的有效性和执行效率以及MT-kDSP-Miner的适用性.在实验采用的4组数据集中,Activity和Location数据集是人类活动记录数据集,e.Coli数据集为DNA数据集,这3个数据集都选自UCI机器学习数据集^[22];而Bible数据集是文本型数据集.

Activity和Location数据集分别是对文献[23]中的ADLs和Sensor数据集进行预处理后得到的数据集.将ADLs和Sensor数据集按照End time属性进行划分,每天的元组形成一条序列,然后抽取其中的Activity和Location属性形成的序列数据集.文献[23]数据包含A和B两个人的活动记录,这样就构成了Activity+,Activity-和Location+,Location-两组对比数据集.e.Coli数据集包含有两个类型的DNA数据,可自然将其分成两类,构成数据集e.Coli+和e.Coli-.Bible数据集包含代表旧约的Bible+数据集和代表新约的Bible-数据集,其中,圣经中的每个句子被当做一个序列,为了挖掘出有意义的模式,我们将诸如“the, a, is, was…”等常见停用词从数据集中去掉,最终得到Bible数据集.表 4列出了实验中使用的数据集的特征.

${\rm{Na\ddot 1ve}}$算法、kDSP-Miner算法和MT-kDSP-Miner算法均用Java实现,JDK版本为1.8.所有实验都在配置为Intel Core i7-3770 3.90 GHz CPU,8GB内存,Windows 7操作系统的PC上完成.

4.2 有效性实验

为了验证kDSP-Miner算法的有效性,本文在Activity,Location,e.Coli和Bible数据集上分别运行kDSP- Miner算法,挖掘带间隔约束的top-k对比序列模式.与本文最相似的工作是文献[3]提出的ConSGapMiner算法,给定的正例最小支持度阈值α、负例最大支持度阈值β和间隔约束γ,ConSGapMiner算法能够挖掘出在正例数据集中支持度大于等于α、在负例数据集中支持度小于等于β,并满足间隔约束γ的最小化对比序列模式.

在Activity,Location,e.Coli和Bible这4个数据集上,以Activity+/Activity-,Location+/Location-,e.Coli+/ e.Coli-和Bible+/Bible-作为正例数据集(D₊)/负例数据集(D_-).

kDSP-Miner算法设定的参数为k和γ,而ConSGapMiner算法需要设定参数α,β和γ.为了公平地比较kDSP-Miner算法和ConSGapMiner算法,我们按如下方式设定两个算法的执行参数:令R_k表示kDSP-Miner算法挖掘出的top-k对比序列模式的集合,当kDSP-Miner算法参数设定为k和γ,那么将ConSGapMiner算法的参数设定为正例支持度阈值α=min{Sup(P,D₊)|P∈R_k},负例支持度阈值β=max{Sup(P,D_-)|P∈R_k},间隔约束为γ.这样,通过参照kDSP-Miner的挖掘结果设置ConSGapMiner算法的执行参数,从而使得两个算法的挖掘目标尽可能一致,从而使得结果具有可比性.

表 5列出了实验中,kDSP-Miner算法和ConSGapMiner算法的执行参数的对应关系.

观察表 5可以看出,在给定相同k值的情况下,ConSGapMiner算法中的支持度阈值α和β在不同数据集上变化很大.可见,在不具备足够先验知识的情况下,对于ConSGapMiner,用户难以设定合适的支持度阈值.

图 2展示了kDSP-Miner算法和ConSGapMiner算法挖掘出的模式个数.kDSP-Miner算法挖掘出的模式个数等于k,可以发现,相应的α,β参数下,ConSGapMiner算法挖掘出的模式个数不确定,可能大于k个,也可能小于k个.

根据我们对ConSGapMiner参数的设置原则,若不存在最小化模式约束,则ConSGapMiner算法挖掘的结果应该是kDSP-Miner算法结果的超集.但由于ConSGapMiner算法具有最小化模式约束,导致某些满足支持度阈值而不满足最小化约束的模式被剪掉.但因其对比度满足top-k的定义,故出现在kDSP-Miner算法的挖掘结果中而未出现在ConSGapMiner算法的结果集中,最终导致kDSP-Miner算法结果集中的模式多于ConSGapMiner算法的结果集中的模式.其中,在图 2(a)和图 2(b)中可以很明显见到这种情况.

对于图 2(d),我们可以发现,ConSGapMiner算法发现模式的个数远大于kDSP-Miner算法发现模式的个数.这是由于Bible数据集中对比最显著的模式在正例和负例数据集中的支持度间隔很远,即,某一个模式,其对比显著,但其正例和负例支持度都远高(低)于其他模式的正例和负例的支持度.为了让ConSGapMiner算法尽可能地找全kDSP-Miner算法发现的模式,导致支持度阈值设置过于宽松,最终挖掘出大量的模式.

请注意,ConSGapMiner算法由用户显式设置支持度阈值,无法预知能够找到多少个模式.若挖掘出的模式过少,则不利于揭示数据集蕴含的规律;若模式个数过多,则又会增加分析的难度.反复不断调整参数,必然增加用户使用算法的难度.相反,kDSP-Miner算法通过设置期望发现模式的个数,避免了直接设定支持度阈值,非常直观,易于用户理解和使用.

由图 3可知,在4个真实数据集的20组对比实验里,有18组实验中的kDSP-Miner算法的挖掘结果的平均对比度大于ConSGapMiner算法的执行结果.这是由于两种算法的目标模式并不相同:kDSP-Miner算法挖掘对比度最为显著的k个模式,而ConSGapMiner算法挖掘满足支持度阈值的模式.所以,即使将ConSGapMiner算法的支持度阈值设定为kDSP-Miner算法挖掘结果的支持度,其挖掘出的模式的平均对比度在大多数情况下也低于kDSP-Miner算法挖掘模式的平均对比度.

有趣的是,我们发现,在图 3(b)的k=5和k=10的对比实验中,ConSGapMiner算法挖掘模式的平均对比度大于kDSP-Miner算法挖掘模式的平均对比度.这是由于在k=5对应的参数下,由于ConSGapMiner算法要求的最小化模式约束,使得ConSGapMiner算法挖掘模式的个数少于kDSP-Miner算法挖掘结果,且其挖掘出的4个模式恰好具有最大对比度.在k=10对应的参数下,也发生了类似的情况.

为了进一步比较kDSP-Miner算法与ConSGapMiner算法的差异,我们用表 6和表 7分别列出在k=10这组对照参数下,kDSP-Miner算法和ConSGapMiner算法在Activity数据集上的挖掘结果.比较表 6中的模式9和表 7中的模式4可以发现:由于ConSGapMiner算法有最小化约束,在找到满足支持度阈值的表 7中的模式4后就不会继续搜索其超序列,因此,即使表 6中的模式9具有很高的对比度,但是不会出现在ConSGapMiner算法的结果集中.比较表 6中的模式3和表 7中的模式3可以看出:表 6中的模式3是表 7中的模式3的超序列,虽然表 7中的模式3的对比度比表 6中的模式3的对比度大了0.02,但是表 6中的模式3的负例支持度为0.发现负例支持度为0的对比序列模式,将有助于构建高性能的序列分类器.例如,文献^[24]的研究表明,发现负例支持度为0的显露模式对提高分类精度非常有用.而ConSGapMiner算法并未挖掘出对比表 6中的模式3,即使表 5中的模式3满足支持度阈值和间隔约束.

表 8与表 9分别展示了间隔约束γ和k值对kDSP-Miner挖掘出来的对比序列模式的最小对比度(min CR)、最大对比度(max CR)和平均对比度(avg CR)的影响.从表 8中可以看出:间隔约束γ变宽松,挖掘结果中的对比序列模式的最小对比度、最大对比度和平均对比度都呈现波动.这是由于间隔约束变宽,元素之间的组合变多,候选模式在正例和负例中的支持度都会增大,模式的对比度的变化趋势不能确定.

令R_k表示top-k对比序列模式的集合,根据top-k对比序列模式挖掘的定义可知:R_k⊂R_k+l(l>0),且

$max\{ CR(P,{D_ + },{D_ - })|P \in {R_k}\} = max\{ CR(P',{D_ + },{D_ - })|P' \in {R_k}_{ + l}\} .$

若P∉R_k,且P∈R_k+l(l>0),CR(P',D₊,D_-)<min{CR(P',D₊,D_-)|P'∈R_k},即,随着k的增大,新加入结果集的对比序列模式的对比度呈非增长趋势,相应地,其平均对比度和最小对比度呈非增长趋势.表 9的实验结果验证了此分析.

4.3 执行效率实验

为了验证kDSP-Miner的执行效率,本文使用3种算法进行对比:${\rm{Na\ddot 1ve}}$算法、包含全部剪枝策略但不含启发策略的kDSP-Miner(Part)以及包含全部剪枝和启发策略的kDSP-Miner(Full).

图 4~图 6展示了参数对算法执行效率的影响.为了更好地观察算法在不同参数下的执行效率,运行时间用对数形式表示.请注意:在Location,e.Coli和Bible数据集上,${\rm{Na\ddot 1ve}}$算法的运行时间远大于kDSP-Miner(Part)和kDSP-Miner(Full)的运行时间,故未将其描绘在图上.

图 4展示了当设置k=10时,间隔约束γ对算法执行效率的影响.随着间隔约束变宽,候选元素之间有效的组合变多,${\rm{Na\ddot 1ve}}$算法运行时间会随之增加.对于kDSP-Miner(Full)算法和kDSP-Miner(Part)算法,候选模式在正例和负例的支持度都会随着间隔约束而变化,导致剪枝策略2和剪枝策略3生效的时间也开始变化.所以总体上,随着间隔约束变宽,kDSP-Miner(Full)算法和kDSP-Miner(Part)算法的运行时间会变长;但是在某些间隔约束下,运行时间可能会降低.对于任意的间隔约束γ,kDSP-Miner(Full)算法快于kDSP-Miner(Part)算法和${\rm{Na\ddot 1ve}}$算法.

图 5展示了当设置γ=[0,2]时,k值对算法执行效率的影响.从图 5(a)可以看出:

$ \bullet $     k值的变化对${\rm{Na\ddot 1ve}}$算法的运行时间没有影响,这是由于${\rm{Na\ddot 1ve}}$算法不含有与k相关的剪枝策略;

$ \bullet $     对于kDSP-Miner(Part)和kDSP-Miner(Full)算法,由于剪枝策略2和剪枝策略3会在找到k个候选对比序列模式后开始生效,所以k越小,剪枝策略就越快开始工作,运行时间也就越少.所以,随着k的增大,kDSP-Miner(Part)和kDSP-Miner(Full)算法运行时间会增大.

为了测试数据集大小对算法执行效率的影响,本文将Activity,Location,e.Coli和Bible数据集进行复制,产生了大小为其μ倍的数据集.图 6展示了运行时间和参数μ之间的关系,其中,γ=[0,2],k=10.可以看出:随着μ的增加,3种算法的运行时间都在增长,但kDSP-Miner(Part)和kDSP-Miner(Full)算法明显快于${\rm{Na\ddot 1ve}}$算法,且kDSP-Miner (Full)算法快于kDSP-Miner(Part)算法.

观察图 4(c)、图 5(c)和图 6(c)可以发现:在e.Coli数据集上,kDSP-Miner(Full)算法的效率和kDSP-Miner(Part)算法很接近,表明启发策略1并没有很好地工作.这是因为e.Coli的字母表排序后的顺序和字典序是一致的,启发策略1对枚举顺序没有改变.而在另外3个数据集数据集上,启发策略1对算法执行效率都有明显的提升.特别地,观察图 4(b)、图 5(b)和图 6(b)可以发现,启发策略1在Location数据集上效果十分显著.

4.4 多线程算法实验

表 10中给出了各个数据集上,在不同的k值下,kDSP-Miner(Full)需要遍历的集合枚举树的节点数目(γ= [0,2]).可以看出,随着k值的增加,需要遍历的节点数目呈现增长趋势.所以,使用MT-kDSP-Miner将把对这些节点的遍历分配到多个线程上并行,是提高挖掘效率的有效途径.

图7展示了在4个数据集上,在不同线程数目m的情况下,MT-kDSP-Miner 的运行时间.其中,k=10,γ=[0,2].注意:当 m=1 时,MT-kDSP-Miner的执行方式(单线程)等同于kDSP-Miner 算法.图7表明:随着线程数目m的增加,MT-kDSP-Miner 运行时间呈先减少再略微增加的趋势.这是由于随着线程数目的增加,每个线程所需要考察的候选模式的数量降低,相应地,执行时间减少.但当线程数目到一定程度后,受限于CPU的处理能力,线程多数时间处于等待CPU的状态,因而,增加线程数目不会降低执行时间,反而由于线程通信的开销,执行时间略微增加.

5 结 论

对比序列模式常常被用于描述序列数据集的特征属性,但传统的对比序列模式挖掘需要预设支持度阈值,如果不能设定合适的阈值,挖掘出结果就可能不符合用户要求.针对这个问题,本文提出了带间隔约束的top-k对比序列模式挖掘问题,用户不需要直接预设具体的支持度阈值,只需确定期望挖掘出的最显著对比序列模式的个数.为了挖掘出带间隔约束的top-k对比序列模式,本文首先给出${\rm{Na\ddot 1ve}}$算法;然后,在${\rm{Na\ddot 1ve}}$算法的框架上设计了3个剪枝策略和1个启发策略,从而实现了高效的kDSP-Miner算法.为了进一步提高算法对序列元素集合为高维时的适用性,本文设计了kDSP-Miner的多线程版本MT-kDSP-Miner.最后,在真实的人类活动记录数据集——DNA数据集和Bible数据集上验证了kDSP-Miner算法的有效性和执行效率.

在下一步工作中,我们将进一步减少用户需要设定的参数,将间隔约束也设定为自动获取.本文中使用的数据集是元素的序列,还可以将其泛化为元素集合的序列,然后挖掘基于元素集的top-k对比序列模式.应用kDSP- Miner挖掘出来的结果来解决实际问题,如序列属性提取、构建分类器等.同时,针对大数据的时代背景,设计kDSP-Miner算法的Hadoop版本,进一步提高算法效率,然后将其应用于电力、交通和医学领域.