基于Spark的Top-k对比序列模式挖掘

张 鹏 段 磊,2 秦 攀 左 劼 唐常杰 元昌安 彭 舰

1(四川大学计算机学院 成都 610065)2(四川大学华西公共卫生学院 成都 610041)3 (科学计算与智能信息处理广西高校重点实验室(广西师范学院) 南宁 530001)



基于Spark的Top-k对比序列模式挖掘

张 鹏1段 磊1,2秦 攀1左 劼1唐常杰1元昌安3彭 舰1

1(四川大学计算机学院 成都 610065)2(四川大学华西公共卫生学院 成都 610041)3(科学计算与智能信息处理广西高校重点实验室(广西师范学院) 南宁 530001)

(zp_jy1993@163.com)

对比序列模式(distinguishing sequential pattern, DSP)指在目标类序列集合中频繁出现,而在非目标类序列集合中不频繁出现的序列.对比序列模式能够描述2个序列集合间的差异,有着广泛的应用,例如：构建序列分类器,识别DNA序列的生物特征,特定人群行为分析.与挖掘满足支持度阈值要求的对比序列模式相比,挖掘对比度top-k对比序列模式能避免用户设置不恰当的支持度阈值.因而,更易于用户使用.但是现有的top-k对比序列模式挖掘算法难以处理大规模序列数据.对此,设计了一种基于Spark的top-k对比序列模式并行挖掘算法,称为SP-kDSP-Miner.此外,为了提高SP-kDSP-Miner的效率,针对Spark结构的特点,设计了候选模式生成策略和若干剪枝策略,以及候选模式对比度的并行计算方法.通过在真实数据集与合成数据集上的实验,验证了SP-kDSP-Miner的有效性、执行效率和可扩展性.

并行计算；序列模式；top-k；对比挖掘；Spark

序列模式挖掘作为一项重要的数据挖掘任务,受到学者的广泛关注,提出了频繁序列模式[1]、闭合序列模式[2]、对比序列模式[3]、周期序列模式[4]、偏序模式[5]等概念.其中,对比序列模式挖掘能够识别不同类别序列样本集合间的差异,并描述各类别样本集合的特征,因此获得了广泛应用.例如：在医学领域分析阳性肿瘤与阴性肿瘤的DNA序列、识别对比序列模式,有助于提高临床肿瘤预测和诊断的精度；在商业领域,对比不同特征(如年龄、职业、地域)顾客的购物历史记录,有助于开展更具针对性的商品促销活动.

从概念上讲,对比序列模式泛指在一类序列中出现频繁,而在其他类序列中出现不频繁的序列[3].传统对比序列挖掘算法要求用户设置最大、最小支持度阈值.在不具备足够先验知识的情况下,用户难以设置恰当的支持度阈值,这可能导致挖掘不到有用的结果.为此,文献[6]提出了top-k对比序列模式挖掘算法kDSP-Miner,旨在挖掘对比度最大的k个对比序列模式.由于设置k(对比序列模式的个数)比设置支持度阈值更加直观,因此kDSP-Miner更易于用户使用.

随着数据采集技术的发展,各领域获取数据的规模越来越大.kDSP-Miner算法基于单台计算机设计,难以满足大规模数据挖掘的需求.因此有必要利用并行计算技术,设计并行挖掘算法,实现从大规模序列数据中发现top-k对比序列模式.Spark是在MapReduce基础上设计的基于内存计算的高容错分布式计算框架[7].它避免了对磁盘进行频繁的IO操作,具有良好的伸缩性.本文应用Spark技术于top-k对比序列模式挖掘,设计了基于Spark的top-k对比序列模式挖掘算法SP-kDSP-Miner.

在Spark框架下设计高效稳定的top-k对比序列模式挖掘算法,需要克服3项技术挑战:

1) 候选对比序列模式生成.挖掘top-k对比序列模式要遍历所有的候选对比序列模式,经过计算得到对比最显著的k个序列模式；在Spark框架下不同的模式遍历方式会导致不同的作业调度开销,所以设计合适的候选模式生成策略对提高算法效率至关重要.

2) 并行计算方法.RDD(resilient distributed dataset)是Spark实现高容错性与数据共享提出的弹性分布式数据,在Spark架构下并行挖掘top-k对比序列模式需要将数据集RDD化；对RDD的不恰当操作会导致额外计算开销,因此需要设计恰当的并行计算过程.

3) 剪枝策略.有效的剪枝策略能提高top-k对比序列模式挖掘的效率；考虑Spark并行计算框架的特点,设计有效的剪枝策略是实现分布式并行挖掘top-k对比序列模式的关键.

本文主要工作包括4项：

1) 针对现有top-k对比序列模式挖掘算法难以处理大规模数据集挖掘的不足,提出利用Spark并行计算架构实现大规模序列集合的top-k对比序列模式挖掘的问题；

2) 针对Spark集群并行计算的特点,设计适合Spark架构的候选模式生成策略以及剪枝策略,提高了挖掘算法的执行效率；

3) 设计适合Spark架构的候选对比序列模式对比度并行评价方法；

4) 利用真实数据集和合成数据集进行详实的实验,验证了SP-kDSP-Miner算法的有效性,执行效率及可扩展性.

1 问题定义

定义Σ为序列元素的集合.序列集中序列S形式化表示为S=e1e2…en,ei∈Σ(1≤i≤n).为方便表述,用S[i]表示序列S中的第i个元素,|S|表示序列的长度.对于序列S中任意元素S[i],S[j](1≤i

例1. 对于基因序列数据集,Σ={a,c,g,t}.给定序列S=acgttc,|S|=6,S[2]=c,S[5]=t,S[2],S[5]之间的间隔gap(S,2,5)=5-2-1=2.

假设存在序列S′=S[k1]S[k2]…S[km],其中1≤k1

例2. 给定序列S=aactc,序列P=ac,间隔约束γ=[0,2].那么,P在S中的实例有〈1,3〉,〈1,5〉,〈2,3〉,〈2,5〉,实例〈1,3〉,〈2,3〉,〈2,5〉满足间隔约束γ,即P⊆γS,并存在实例〈2,3〉使P是S的连续子序列.

给定序列S=e1e2…en,n>1,本文定义pre(S)为S的最大前缀,记为pre(S)=e1e2…en-1,定义suf(S)为S的最大后缀,记为suf(S)=e2e3…en.若|S|=1,则pre(S),suf(S)为空.例如,对序列S=aactc,pre(S)=aact,suf(S)=actc.

给定序列样本集合D、间隔约束γ、序列P在D中的支持度,记为Sup(P,D,γ),则：

(1)

例3. 考虑表1中的序列集合D+,令间隔约束γ=[0,2].给定序列P=ac,对序列S1有实例〈1,3〉,〈5,6〉，使得P⊆γS1,对序列S2有实例〈2,3〉，使得P⊆γS2,对序列S3有实例〈1,3〉,〈1,4〉，使得P⊆γS3.由于|D+|=3,所以Sup(P,D+,γ)=(1+1+1)3=1.0.

给定正例序列集D+、负例序列集D-和间隔约束γ,本文定义序列P在D+与D-间的对比度CR(P,D+,D-,γ)为

CR(P,D+,D-,γ)=

Sup(P,D+,γ)-Sup(P,D-,γ).

(2)

例4. 以表1中的D+,D-为例,令间隔约束γ=[0,2],序列P=ac,有Sup(P,D+,γ)=1.0,Sup(P,D-,γ)=0.33,则CR(P,D+,D-,γ)=1.0-0.33=0.67.

Table 1 An Example of Sequence Data Sets表1 序列数据集示例

由于间隔约束γ作为运行参数用户预先给定,且在挖掘过程中不会改变.为了表达简洁,我们将Sup(P,D,γ)简化为Sup(P,D),CR(P,D+,D-,γ)简化为CR(P,D+,D-).表2列出了本文常用的符号及其定义.

Table 2 Summary of Notations表2 记号汇总

定义1. 对比序列模式.给定间隔约束γ、正例序列集D+与负例序列集D-,若序列P的对比度CR(P,D+,D-)>0,则P为一个带间隔约束γ的对比序列模式,简称为对比序列模式.

定义2. top-k对比序列模式.给定间隔约束γ、正例序列集D+、负例序列集D-，对比度最大的k个对比序列模式,称为带间隔约束γ的top-k对比序列模式,简称为top-k对比序列模式.

值得一提的是,本文在进行top-k选择时,若有多个模式的对比度相等,则按2条规则排序对比度：1)优先选择长度更短的模式；2)若长度相同,则按正例序列集合中元素出现顺序选择排序靠前的模式.在实践中,用户也可以根据实际情况修改规则以适应具体应用的需求.

本文研究问题(top-k对比序列模式)的定义与文献[6]一致,但文献[6]提出的top-k对比序列模式挖掘算法处理的数据规模难以突破单台计算机内存容量的限制,导致无法获得挖掘结果.对此,本文提出利用Spark并行计算架构实现大规模序列集的top-k对比序列模式挖掘的问题.我们将在后文详述解决方案.

2 相关工作

序列数据存在于众多应用领域,分析序列数据并提取有用的模式,能够帮助人们发现数据蕴含的知识.例如文献[8]将序列模式挖掘方法应用于手机时空信息挖掘,提取某一事件的局部或者周边环境随时间变化的趋势；文献[9]为了提高运动员的训练积极性,对运动员训练的时间序列数据进行挖掘,发现运动员最偏好的训练方式；文献[10]基于关联规则及支持向量机建立了2个分类器,利用频繁子序列提高蛋白质序列分类的准确性和执行效率.这些工作中都没有引入间隔约束的概念,且没有考虑序列样本的类别.

在序列模式中考虑间隔约束能够提高序列模式的适用性与灵活性,所以间隔约束被普遍应用于序列模式挖掘中.文献[11]针对蛋白质序列数据过长,而数据量偏少的特点,在蛋白质序列数据挖掘中引入间隔约束,增强了挖掘结果的适用性,并提高了算法的效率；文献[12]认为挖掘频繁子序列中人为设置间隔约束影响挖掘结果,因此设计了高效的万能间隔约束挖掘频繁子序列；文献[13]设计了Gap-BIDE算法挖掘带间隔约束的闭合序列模式,并从挖掘结果中抽取特征建立分类器；文献[14]在频繁闭合序列模式挖掘中,引入了非用户设定间隔约束的概念,其挖掘结果具有更强的解释性；文献[15]为了提高序列模式挖掘的效率,基于间隔约束设计了2种模式生成策略与剪枝策略,最后通过实验验证了算法的执行效率.上述工作没有考虑序列样本的类别,无法识别不同序列集合间的差异.

对比序列模式挖掘能够发现识别不同类别序列样本集合间的差异,并描述各类别样本集合的特征.文献[3]提出了具有最小模式的对比序列模式,并设计ConSGapMiner算法挖掘2个序列集合间的对比序列模式；文献[16]建立以对比序列模式为特征的分类器,并对蛋白质序列多肽折叠进行分类；文献[17]在对比序列中引入“密度概念”,丰富了“频繁”含义,并设计了gd-DSPMiner算法挖掘满足“密度”约束的对比序列模式.上述对比序列挖掘工作都需要用户预先设定支持度阈值.

由于在不具备充分领域知识的情况下,用户难以设定恰当的支持度阈值.因此,用参数k(模式的个数)代替支持度阈值更易于实际应用.文献[18]设计了应用于活动序列数据集的top-k对比序列挖掘算法,挖掘2个数据集中出现频率对比最显著的对比序列模式；文献[19]为寻找DNA序列模式与疾病表现的关系,运用top-k挖掘对比度最显著的k个对比序列模式并建立分类器；文献[6]为了避免设置支持度阈值,用top-k代替支持度阈值挖掘对比序列模式.

随着各应用领域数据采集能力的增强,基于Spark的大规模数据挖掘得到越来越多的关注.文献[20]在Spark框架下实现了大规模数据的评估过程；文献[21]用Spark解决了基因检测技术的效率问题；文献[22]提出了基于Spark的分布式算法对推特上的大规模数据进行情感分析；文献[23]利用Spark从大规模单图上挖掘频繁子图,提高了挖掘效率.

据我们所知,文献[6]与本文研究工作最接近.但是文献[6]提出的算法kDSP-Miner基于单台计算机设计,其关键步骤,如采用深度优先遍历集合枚举树生成候选模式的策略,不适合于并行计算,导致其难以对大规模数据进行高效挖掘.对此,本文基于Spark架构特点设计的算法能够有效地弥补kDSP-Miner的不足.

3 SP-kDSP-Miner算法设计

为了实现大规模序列集合中top-k对比序列模式的高效挖掘,本文提出基于Spark的分布式并行处理算法SP-kDSP-Miner.算法要点包括：1)Spark架构下候选对比序列模式生成；2)利用Spark集群计算候选对比序列模式的对比度；3)Spark架构下的候选模式剪枝策略.

图1给出了SP-kDSP-Miner算法的流程图.

Fig. 1 Flow chart of SP-kDSP-Miner图1 SP-kDSP-Miner算法流程图

从图1可以看出,SP-kDSP-Miner算法主要包括4个步骤：

① 启动SP-kDSP-Miner算法并调度Spark集群从HDFS(Hadoop distributed file system)中载入数据到各计算节点,完成数据预处理；

② 生成候选对比序列模式集合,如果候选对比序列模式集合不为空集,则执行步骤③,否则执行步骤④；

③ 调度Spark工作集群,计算每个候选对比序列模式的对比度；

④ 输出top-k对比序列模式挖掘结果.

在SP-kDSP-Miner算法流程中,步骤②生成候选对比序列模式集合与步骤③调用Spark集群计算候选对比序列模式的对比度是整个算法的核心部分.本文接下来将分别介绍步骤②和步骤③以及如何提高算法的执行效率.

3.1 候选对比序列模式生成

容易想到,可以采用遍历集合枚举树(如图2所示)的方式生成候选对比序列模式.完全遍历集合枚举树会导致大量不必要的计算开销,因此,设计适用于Spark架构的集合枚举树遍历方式和剪枝策略是算法执行效率的基础.首先,我们分析对比序列模式关于对比度的性质及可以得到的剪枝策略.

引理1. 给定间隔约束γ、正例序列集D+、负例序列集D-、对序列P,若Sup(P,D+)≤σ(σ>0),则CR(P,D+,D-)≤σ.

证明.

令Sup(P,D+)≤σ(σ>0).

因为CR(P,D+,D-)=Sup(P,D+)-Sup(P,D-)，

所以CR(P,D+,D-)≤σ-Sup(P,D-)；

因为Sup(P,D-,)≥0,

所以CR(P,D+,D-)≤σ.

证毕.

定理1. 给定间隔约束γ、正例序列集D+、负例序列集D-、对序列P,若Sup(P,D+)=0,则P不是对比序列模式.

证明.

用反证法证明.假设P是对比序列模式,根据定义1,CR(P,D+,D-)>0.

由性质1可知,CR(P,D+,D-)≤Sup(P,D+)=0,与对比序列模式定义矛盾.

所以给定候选对比序列模式P,若Sup(P,D+)=0,P不可能成为SP-kDSP-Miner算法的挖掘目标.

证毕.

由定理1可以得到剪枝策略1.

剪枝策略1. 给定候选对比序列模式P,若Sup(P,D+)=0,那么剪去集合枚举树中P的所有子节点.

根据剪枝策略1,在生成候选对比序列模式时,我们只需要考虑Σ中出现在D+中的元素.

定理2. 给定间隔约束γ、正例序列集D+、序列P和P′,满足P′是P的连续子序列.若Sup(P′,D+)<σ，σ>0,则P的正例支持度Sup(P,D+)≤Sup(P′,D+)<σ.

证明.

因为P′是P的连续子序列,

所以给定序列集D+、间隔约束γ、对于任意序列S(S∈D+),P′⊆γS成立,但P⊆γS不一定成立；

所以根据式(1)可得：

即Sup(P,D+)≤Sup(P′,D+).

证毕.

由定理2得到剪枝策略2.

剪枝策略2. 令R为当前对比度最大的k个对比序列模式集合,CRmin=min{CR(P″,D+,D-)|P″∈R}.若Sup(P,D+)

在Spark并行计算中,每项有结果返回的操作都会形成1项具体的作业,1次作业的开销主要包括：作业调度开销、作业通信开销、作业计算开销.如果1次作业只计算1个候选对比序列模式的对比度,作业调度次数等于候选模式数量,这将导致大量的作业调度开销,使得Spark集群工作节点长时间处于空闲状态,无法发挥Spark集群并行计算的优势.因此,应该尽可能产生相互不影响(没有剪枝关系)的候选对比序列模式,进而在1次Spark作业中可以并行处理多个候选模式,充分利用Spark集群的计算能力,提高计算效率.

考虑文献[6]采用的深度优先遍历集合枚举树生成候选模式的策略.我们可以一次生成候选模式P及所有包含P为连续子序列的候选模式.如果Sup(P,D+)

广度优先遍历策略在生成长度为l的候选对比序列模式之前会先生成所有长度小于l的候选模式.注意：长度相等的候选模式,它们之间不存在子序列关系,因此不会出现相互剪枝的情况.而1次Spark作业中可以并行处理所有长度为l的候选对比序列模式,有效降低作业调度开销,充分利用Spark集群的计算能力,提高算法效率.

基于广度优先遍历集合枚举树策略,我们设计了候选模式的生成方法.给定候选对比序列模式P,Q(|P|=|Q|=l),如果pre(P)=suf(Q),则由P,Q可生成第l+1层的对比候选序列模式,表示为

(3)

本文模式生成方法是集合枚举树宽度优先遍历的一种具体实现.图2示例了集合枚举树.

Fig. 2 An example of a set enumeration tree图2 集合枚举树示例

算法1给出了SP-kDSP-Miner生成候选模式算法的伪代码.

算法1.GENERATE(Cl)算法.

输入: 长度为l的候选对比序列模式的集合Cl、当前对比度最大的k个对比序列模式中最小的对比度CRmin；

输出: 长度为l+1的候选对比序列模式集合Cl+1.

①Cl+1←∅；*初始化长度为l+1的候选对比序列集合Cl+1*

②Pl←{P|Sup(P,D+)>CRmin,P∈Cl}；*剪枝策略2*

③ forP∈Pl，Q∈Pldo

④ ifpre(P)=suf(Q) then

⑤Cl+1←Cl+1∪{Q⊕P}；

⑥ endif

⑦ endfor

⑧ returnCl+1.

算法1利用长度为l的候选对比序列模式集合Cl生成长度为l+1的候选对比序列模式集合Cl+1.步骤②利用剪枝策略2,移除不可能成为top-k对比序列模式的候选模式.步骤③～⑦生成长度为l+1的候选对比序列模式.步骤⑧返回利用算法1生成的候选对比序列模式集合.算法1的算法复杂度为O(|Cl|),其中|Cl|是长度为l的候选对比序列模式的个数.

Fig. 3 Contrast calculation process in SP-kDSP-Miner图3 SP-kDSP-Miner中对比度计算过程

3.2 对比度并行计算

SP-kDSP-Miner使用Spark分布式框架将大规模数据分片并读入计算节点,然后各计算结点获取候选对比序列模式集合,SP-kDSP-Miner算法再调用Spark计算节点评价每个候选对比序列模式的对比度.图3展示了对比度的计算过程.

如图3所示,对比度的计算过程主要包括3个步骤：

① 利用Spark并行操作textfile()从HDFS载入数据到计算节点内存；

② 分别计算候选对比序列模式的正例支持度与负例支持度.计算支持度时先将候选对比序列模式集合Cl拷贝到计算节点,调用Spark并行操作函数map()对每一条序列数据进行子序列匹配,然后用flatmap()操作与groupbykey()操作统计子序列匹配结果,最后用统计结果计算出模式P(P∈Cl)的支持度；

③ 用并行操作join()将模式P(P∈Cl)的正例支持度与负例支持度集合在一起,然后调用map()操作计算对比度并输出结果.

表3列出了SP-kDSP-Miner使用的Spark提供的并行操作函数[24].

Table 3 API of Spark Used by SP-kDSP-Miner表3 SP-kDSP-Miner使用的Spark API

在对比度计算过程中,令Cl是长度为l的候选对比序列模式集合.若有P∈Cl,满足Sup(P,D+)

剪枝策略3. 在对比度计算过程中,对于候选模式P,若sup(P,D+)

表面上看,剪枝策略3与剪枝策略2都基于定理2,但它们的执行时机与剪枝对象不同.剪枝策略3在对比度计算过程中生效,即在剪枝条件(CRmin)变化前执行.这是因为计算对比度时使用并行方法,为了降低通信开销,只能先计算正例支持度,这样剪枝策略3可以避免不必要的负例支持度计算.而完成对比度计算之后,会更新全局的结果集R,剪枝条件(CRmin)也随之更新,在生成新的候选对比序列模式时剪枝策略2生效,避免生成无意义的候选模式.

在对比度计算步骤②中,SP-kDSP-Miner在装载序列数据时进行编码.给定任意元素e在序列S,我们用位向量Pos(e,S)记录e在序列S中的位置信息,用Pos(e,S)[i]表示Pos(e,S)的第i位:

(4)

式(4)描述了位向量的编码规则.例如对于序列S=atcgacat,元素a在第1,5,7位出现,因此Pos(a,S)=10 001 010.

给定间隔约束γ=[γ.min,γ.max],若序列S与模式P匹配,那么必然有S[i]=P[j],S[k]=P[j+1],且i+γ.min

3.3 复杂度分析及负载均衡

在Spark架构下对比度计算过程以及候选对比序列模式生成方法的支持下,算法2示例了SP-kDSP-Miner的伪代码.

算法2. SP-kDSP-Miner(D+,D-,γ,k)算法.

输入: 正例序列集D+、负例序列集D-、间隔约束γ和参数k；

输出: top-k对比序列模式集合R.

①R←∅；*R保存挖掘结果*

②Σ←scan(D+)；*scan获取Σ*

③C←Σ；

④ whileC≠∅ do

⑤ 利用spark集群计算候选对比序列模式的对比度*剪枝策略3*

⑥Pl←{P|Sup(P,D+)>min{CR(P′,D+,D-)|P′∈R},P∈C}；

⑦ forP∈Pldo

⑧ ifCR(P,D+,D-)>min{CR(P′,D+,D-)|P′∈R} then

⑨R←R∪{P}；*更新R*

⑩ endif

基于Spark框架的分布式算法的运行时间取决于计算时间最长的计算节点,即符合木桶效应.因此,实现各计算节点的负载均衡有利于降低算法总执行时间.在算法2中步骤⑤调用Spark工作集群计算候选对比序列模式的对比度,当SP-kDSP-Miner评价候选对比模式P在正负例序列集间的差异度时,会将模式P拷贝到各个计算节点,然后将模式P与计算节点载入的序列数据进行子序列匹配,最终各个计算节点将匹配结果汇总,计算出对比度.在整个差异度评价过程中,计算节点的计算量与载入的序列数据大小成正比关系.为保证计算节点负载均衡,各个计算节点载入的序列数据大小应该尽量相同.

因此,在对D+,D-进行分片时,我们采用均分策略,即将数据集分片为与计算节点数量相同的等份载入节点.下一步研究工作中,我们将考虑计算节点的负载动态均衡,即允许节点的负载在算法执行过程中动态调整.

4 实 验

4.1 实验环境

本文在真实序列集与合成序列集上进行了实验,以验证算法的有效性、执行效率及可扩展性.实验采用PFam数据库*http:pfam.sanger.ac.uk提供的2个真实序列集：蛋白质序列数据家族Actin与ABC-2.并以真实序列集Actin为基础,用不同策略合成2组合成序列集,用来进行数据规模的扩展性实验.

在蛋白质序列数据家族Actin中,包含了多个家庭成员序列集,本文选取PF00012作为正例序列集,PF00022作为负例序列集.类似地,在ABC-2家族中,本文选取APF01061作为正例序列集,APF12698作为负例序列集.合成序列集分别为DBMA,DBMB.DBMA的合成方式：首先分别获取Actin中正负序列集各元素出现的频率,然后根据正例序列集中元素的频率合成序列长度为60～200的正例序列集,根据负例序列集中元素的出现频率合成序列长度为60～200的负例序列集.DBMB的合成方式：Actin扩大数倍.表4列出了实验中使用的序列集的特征.

Table 4 Characteristics of Data Sets表4 数据集特征

SP-kDSP-Miner算法用Python2.7.0编程实现,在Spark1.5.0与CDH4(cloudera’s distribution including Apache Hadoop 4)搭建的架构下进行实验.Spark集群总节点数为8,每个节点为配置是Intel core i7-4770 3.40 GHz CPU,16 GB内存,Ubuntu14.04操作系统的PC.所有实验数据都预先存入HDFS.

4.2 有效性实验

因为本文工作的挖掘目标与文献[6]相同,所以用kDSP-Miner挖掘结果与SP-kDSP-Miner的挖掘结果进行对比,以验证有效性.进行有效性实验时,本文在Actin,ABC-2,DBMA和DBMB序列集上分别运行SP-kDSP-Miner算法与kDSP-Miner算法,挖掘带间隔约束的top-k对比序列模式.为了保证挖掘目标的一致性,SP-kDSP-Miner算法和kDSP-Miner算法的参数γ,k应该相同,默认值为γ=[0,2],k=10.kDSP-Miner算法代码来自于文献[6].

表5展示了算法kDSP-Miner与SP-kDSP-Miner在2个蛋白质真实序列集上的挖掘结果.从表5可知,2个算法挖掘结果一致.表6展示了在2个合成大规模序列集上的挖掘结果.由表6可知,SP-kDSP-Miner最终得到了结果,而kDSP-Miner使用深度优先策略,在迭代过程中占用了大量内存保存中间结果,最终因为内存限制无法挖掘到有效的结果.实验结果验证了SP-kDSP-Miner能够从大规模数据中挖掘top-k带间隔约束的对比序列模式.

Notes:k=10,γ=[0,2].

Table 6 Mining Results of the Data Sets DBMA & DBMB表6 数据集DBMA,DBMB的挖掘结果

Notes:k=10,γ=[0,2].

4.3 执行效率实验

为了验证SP-kDSP-Miner的执行效率,本文使用kDSP-Miner进行对比.与kDSP-Miner一样,SP-kDSP-Miner需要设定的参数为γ与k.图4～5展示了参数对SP-kDSP-Miner算法的影响.因为kDSP-Miner算法难以适用于大规模序列数据集,所以只对ABC-2与Actin两个序列集进行了实验.进行此实验时,SP-kDSP-Miner算法用到Spark集群的4个节点,kDSP-Miner所用线程数为5.

图4展示了当设置k=10时,间隔约束γ对算法执行效率的影响,并与kDSP-Miner进行了比较.随着间隔约束的范围增大,候选元素之间有效的组合变多,kDSP-Miner与SP-kDSP-Miner运行时间都会随之增加.相较于kDSP-Miner,SP-kDSP-Miner变化趋势缓慢一些.因为间隔约束的范围比较小,候选模式少,Spark集群计算能力没有被充分利用.并且SP-kDSP-Miner在计算对比度过程中,设计了减枝策略3,降低了计算量.总体来说,对于任意的间隔约束γ,具有集群优势的SP-kDSP-Miner执行时间较kDSP-Miner更短,并且随着间隔约束γ的范围变大,SP-kDSP-Miner所用集群的计算能力被充分利用,执行效率会有一定程度提高.

图5展示了当设置γ=[0,2]时k值对算法执行效率的影响,并与kDSP-Miner进行了比较.随着k值增大,SP-kDSP-Miner与kDSP-Miner执行时间都有增加的趋势,但是kDSP-Miner算法执行时间波动较大.总体上看,SP-kDSP-Miner算法得益于Spark的集群优势,在同等规模数据集下挖掘速度更快.

Fig. 4 Runtime w.r.t. gap constraints (k=10)图4 采用不同间隔约束的执行时间(k=10)

Fig. 5 Runtime w.r.t. k value (γ=[0,2])图5 采用不同k值的执行时间(γ=[0,2])

最重要的是,SP-kDSP-Miner具有可扩展性.随着Spark节点集群增加,SP-kDSP-Miner的执行时间会进一步降低.

4.4 扩展性实验

为了验证SP-kDSP-Miner的适用范围,本文在合成数据集DBMA与DBMB上进行了扩展性实验.图6、图7分别展示了不同的数据规模,以及不同的Spark集群节点对算法执行时间的影响.在数据规模扩展性实验中,运用不同节点数量的SP-kDSP-Miner算法在2个合成数据集DBMA,DBMB上进行了实验,节点数Nodes分别为2,4,6,8.

在图6中,随着数据规模的扩大,执行时间呈线性增长.在图7中,随着节点数量的增加,执行时间先大幅度下降,再趋于平缓,是因为节点数量与运行时间之间呈反比关系.所以,随着Spark集群节点数增加,能有效降低SP-kDSP-Miner的执行时间.

Fig. 7 Runtime w.r.t. number of nodes图7 节点扩展性实验

5 结 论

带间隔约束的top-k对比序列模式挖掘能够从2个不同类别的序列数据集合中挖掘出对比度最大的k个对比序列模式.但是现有的带间隔约束的top-k对比序列模式挖掘算法并不能有效地从大规模数据中挖掘出结果.针对这个问题,本文提出了基于Spark的带间隔约束的top-k对比序列模式挖掘算法SP-kDSP-Miner,设计了3个剪枝策略.最后在真实序列集与合成序列集上验证了SP-kDSP-Miner的有效性,执行效率与可扩展性.

在下一步工作中,我们将增加Spark集群中计算节点的数量,使SP-kDSP-Miner适用于更大规模的数据分析.我们还将考虑计算节点间的动态负载均衡,即允许节点间的负载在算法执行过程中动态调整.同时,在更多实际应用中验证SP-kDSP-Miner的有效性.例如在生物信息学领域,挖掘相同遗传病不同表征的基因序列差异；在医学领域,挖掘患病人群与健康人群的基因组差异；在互联网金融领域,挖掘不同人群的投资特点.

[1]Zaki M J. SPADE: An efficient algorithm for mining frequent sequences[J]. Machine Learning, 2001, 41(12): 31-60

[2]Yan Xifeng, Han Jiawei, Afshar R. CloSpan: Mining closed sequential patterns in large datasets[C]Proc of the 3rd SIAM Int Conf on Data Mining. Philadelphia, PA: SIAM, 2003: 166-177

[3]Ji Xiaonan, Bailey J, Dong Guozhu. Mining minimal distinguishing subsequence patterns with gap constraints[J]. Knowledge & Information Systems, 2007, 11(3): 259-286

[4]Zhang Minghua, Kao B, Cheung D W, et al. Mining periodic patterns with gap requirement from sequences[J]. ACM Trans on Knowledge Discovery from Data, 2007, 1(2): 623-633

[5]Pei Jian, Wang Haixun, Liu Jian, et al. Discovering frequent closed partial orders from strings[J]. IEEE Trans on Knowledge & Data Engineering, 2006, 18(11): 1467-1481

[6]Yang Hao, Duan Lei, Hu Bin, et al. Mining Top-kdistinguishing sequential patterns with gap constraint[J]. Journal of Software, 2015, 26(11): 2994-3009 (in Chinese)(杨皓, 段磊, 胡斌, 等. 带间隔约束的Top-k对比序列模式挖掘[J]. 软件学报, 2015, 26(11): 2994-3009)

[7]Zaharia M, Chowdhury M, Franklin M J, et al. Spark: Cluster computing with working sets[C]Proc of USENIX Conf on Hot Topics in Cloud Computing. Berkeley, CA: USENIX Association, 2010: 1765-1773

[8]Alatrista-Salas H, Bringay S, Flouvat F, et al. Spatio-sequential patterns mining: Beyond the boundaries[J]. Intelligent Data Analysis, 2016, 20(2): 293-316

[9]Hrovat G, Fister I, Yermak K, et al. Interestingness measure for mining sequential patterns in sports[J]. Journal of Intelligent and Fuzzy Systems, 2015, 29(5): 1981-1994

[10]She Rong, Chen Fei, Wang Ke, et al. Frequent-Subsequence-Based prediction of outer membrane proteins[C]Proc of the 9th ACM Knowledge Discovery and Data Mining. New York: ACM, 2003: 436-445

[11]Ferreira P G, Azevedo P J. Protein sequence pattern mining with constraints[G]LNCS 3721: Proc of the 9th European Conf on Principles and Practice of Knowledge Discovery in Databases. Berlin: Springer, 2005: 96-107

[12]Wu Xindong, Zhu Xingquan, He Yu, et al. PMBC: Pattern mining from biological sequences with wildcard constraints[J]. Computers in Biology & Medicine, 2013, 43(5): 481-492

[13]Li Chun, Yang Qingyan, Wang Jianyong, et al. Efficient mining of gap-constrained subsequences and its various applications[J]. ACM Trans on Knowledge Discovery from Data, 2012, 6(1): Article 2

[14]Wang Wentao, Duan Lei, Nummenmaa J, et al. Mining frequent closed sequential patterns with non-user-defined gap constraints[G]LNCS 8933: Proc of the 10th Int Conf on Advanced Data Mining and Applications. Berlin: Springer, 2014: 57-70

[15]Xie Fei, Wu Xindong, Hu Xuegang, et al. MAIL: Mining sequential patterns with wildcards[J]. International Journal of Data Mining & Bioinformatics, 2013, 8(1): 1-23

[16]Shah C C, Zhu Xingquan, Khoshgoftaar T M, et al. Contrast pattern mining with gap constraints for peptide folding prediction[C]Proc of the 21st Int Florida Artificial Intelligence Research Society Conf. Menlo Park, CA: AAAI, 2008: 95-100

[17]Wang Xianming, Duan Lei, Dong Guozhu, et al. Efficient mining of density-aware distinguishing sequential patterns with gap constraints[G]LNCS 8421: Proc of the 20th Int Conf on Database Systems for Advanced Applications. Berlin: Springer, 2014: 372-387

[18]Zaïane O R, Yacef K, Kay J. Finding top-n emerging sequences to contrast sequence sets, TR07-03[R]. Edmonton, Alberta: Department of Computing Science, University of Alberta, 2007

[19]Zhao Yuhai, Li Yuan, Yin Ying, et al. Finding top-kcovering irreducible contrast sequence rules for disease diagnosis[OL]. 2015 [2016-05-07]. https:www.hindawi.comjournalscmmm2015353146

[20]Funika W, Koperek P. Scaling evolutionary programming with the use of Apache Spark[J]. Computer Science, 2016, 17(1): 69-82

[21]Qi Rongzhi, Wang Zhijian, Li Shuiyan. A parallel genetic algorithm based on Spark for pairwise test suite generation[J]. Computer Science and Technology, 2016, 31(2): 417-427

[22]Nodarakis N, Sioutas S, Tsakalidis A K, et al. Large scale sentiment analysis on Twitter with Spark[OL]. [2016-05-07]. http:ceur-ws.orgVol-1558paper41.pdf

[23]Yan Yuliang, Dong Yihong, He Xianmang, et al. FSMBUS: A frequent subgraph mining algorithm in single large-scale graph using Spark[J]. Journal of Computer Research and Development, 2015, 52(8): 1768-1783 (in Chinese)(严玉良, 董一鸿, 何贤芒, 等. FSMBUS: 一种基于Spark的大规模频繁子图挖掘算法[J]. 计算机研究与发展, 2015, 52(8): 1768-1783)

[24]Apache SparkTM. Spark Python API docs: Pyspark package[EBOL]. [2016-05-07]. http:spark.apache.orgdocslatestapipythonpyspark.html#module-pyspark

Zhang Peng, born in 1992. Master candidate. Student member of CCF. His main research interests include data mining and knowledge engineering.

Duan Lei, born in 1981. PhD, associate professor. Senior member of CCF. His main research interests include data mining, health-informatics and evolutionary computation.

Qin Pan, born in 1991. Master candidate. His main research interests include data mining and knowledge engineering (panqin.cn@outlook.com).

Zuo Jie, born in 1977. PhD, associate professor. His main research interests include database management and data mining (zuojie@scu.edu.cn).

Tang Changjie, born in 1946. PhD supervisor, professor. His main research interests include database and knowledge engineering (cjtang@scu.edu.cn).

Yuan Chang’an, born in 1964. PhD, professor. His main research interests include data mining and evolutionary computation (yca@gxtc.edu.cn).

Peng Jian, born in 1970. PhD, professor. Senior member of CCF. His main research interests include big data, cloud computing, and wireless sensor network (jianpeng@scu.edu.cn).

Mining Top-kDistinguishing Sequential Patterns Using Spark

Zhang Peng1, Duan Lei1,2, Qin Pan1, Zuo Jie1, Tang Changjie1, Yuan Chang’an3, and Peng Jian1

1(SchoolofComputerScience,SichuanUniversity,Chengdu610065)2(WestChinaSchoolofPublicHealth,SichuanUniversity,Chengdu610041)3(GuangxiHigherEducationKeyLaboratoryofScienceComputingandIntelligentInformationProcessing(GuangxiTeachersEducationUniversity),Nanning530001)

DSP (distinguishing sequential pattern) is a kind of sequence such that it occurs frequently in the sequence set of target class, while infrequently in the sequence set of non-target class. Since distinguishing sequential patterns can describe the differences between two sets of sequences, mining of distinguishing sequential patterns has wide applications, such as building sequence classifiers, characterizing biological features of DNA sequences, and behavior analysis for specified group of people. Compared with mining distinguishing sequential patterns satisfying the predefined support thresholds, mining distinguishing sequential patterns with top-kcontrast measure can avoid setting improper support thresholds by users. Thus, it is more user-friendly. However, the conventional algorithm for mining top-kDSPs cannot deal with the sequence data set with large-scale. To break this limitation, a parallel mining method using Spark, named SP-kDSP-Miner (Spark based top-kDSP miner), is designed for mining top-kdistinguishing sequential patterns from large-scale sequence data set. Furthermore, in order to improve the efficiency of SP-kDSP-Miner, a novel candidate pattern generation strategy and several pruning strategies, as well as a parallel computing method for the contrast scores of candidate patterns are proposed considering the characteristics of Spark structure. Experiments on both real-world and synthetic data sets demonstrate that SP-kDSP-Miner is effective, efficient and scalable.

parallel computing; sequential pattern; top-k; contrast mining; Spark

2016-08-02；

2016-10-10

国家自然科学基金项目(61572332,61363037)；国家自然科学基金委员会-中国民用航空局民航联和研究基金项目(U1333113)；中国博士后科学基金特别资助项目(2016T90850)；中央高校基本科研业务费专项资金项目(2016SCU04A22)；四川省科技支撑计划基金项目(2014GZ0111) This work was supported by the National Natural Science Foundation of China (61572332, 61363037), the Joint Research Fund in Civil Aviation under Cooperative Agreement Between the National Natural Science Foundation of China and Civil Aviation Administration of China (U1333113), the China Postdoctoral Science Foundation (2016T90850), the Fundamental Research Funds for the Central Universities (2016SCU04A22), and the Key Technology Research and Development Program of Sichuan Province of China (2014GZ0111).

段磊(leiduan@scu.edu.cn)

TP311.13