張 鵬 段 磊,2 秦 攀 左 劼 唐常杰 元昌安 彭 艦

1(四川大學(xué)計(jì)算機(jī)學(xué)院 成都 610065)2(四川大學(xué)華西公共衛(wèi)生學(xué)院 成都 610041)3 (科學(xué)計(jì)算與智能信息處理廣西高校重點(diǎn)實(shí)驗(yàn)室(廣西師范學(xué)院) 南寧 530001)

?

基于Spark的Top-k對(duì)比序列模式挖掘

張 鵬1段 磊1,2秦 攀1左 劼1唐常杰1元昌安3彭 艦1

1(四川大學(xué)計(jì)算機(jī)學(xué)院 成都 610065)2(四川大學(xué)華西公共衛(wèi)生學(xué)院 成都 610041)3(科學(xué)計(jì)算與智能信息處理廣西高校重點(diǎn)實(shí)驗(yàn)室(廣西師范學(xué)院) 南寧 530001)

(zp_jy1993@163.com)

對(duì)比序列模式(distinguishing sequential pattern, DSP)指在目標(biāo)類序列集合中頻繁出現(xiàn),而在非目標(biāo)類序列集合中不頻繁出現(xiàn)的序列.對(duì)比序列模式能夠描述2個(gè)序列集合間的差異,有著廣泛的應(yīng)用,例如：構(gòu)建序列分類器,識(shí)別DNA序列的生物特征,特定人群行為分析.與挖掘滿足支持度閾值要求的對(duì)比序列模式相比,挖掘?qū)Ρ榷萾op-k對(duì)比序列模式能避免用戶設(shè)置不恰當(dāng)?shù)闹С侄乳撝?因而,更易于用戶使用.但是現(xiàn)有的top-k對(duì)比序列模式挖掘算法難以處理大規(guī)模序列數(shù)據(jù).對(duì)此,設(shè)計(jì)了一種基于Spark的top-k對(duì)比序列模式并行挖掘算法,稱為SP-kDSP-Miner.此外,為了提高SP-kDSP-Miner的效率,針對(duì)Spark結(jié)構(gòu)的特點(diǎn),設(shè)計(jì)了候選模式生成策略和若干剪枝策略,以及候選模式對(duì)比度的并行計(jì)算方法.通過在真實(shí)數(shù)據(jù)集與合成數(shù)據(jù)集上的實(shí)驗(yàn),驗(yàn)證了SP-kDSP-Miner的有效性、執(zhí)行效率和可擴(kuò)展性.

并行計(jì)算；序列模式；top-k；對(duì)比挖掘；Spark

序列模式挖掘作為一項(xiàng)重要的數(shù)據(jù)挖掘任務(wù),受到學(xué)者的廣泛關(guān)注,提出了頻繁序列模式[1]、閉合序列模式[2]、對(duì)比序列模式[3]、周期序列模式[4]、偏序模式[5]等概念.其中,對(duì)比序列模式挖掘能夠識(shí)別不同類別序列樣本集合間的差異,并描述各類別樣本集合的特征,因此獲得了廣泛應(yīng)用.例如：在醫(yī)學(xué)領(lǐng)域分析陽性腫瘤與陰性腫瘤的DNA序列、識(shí)別對(duì)比序列模式,有助于提高臨床腫瘤預(yù)測和診斷的精度；在商業(yè)領(lǐng)域,對(duì)比不同特征(如年齡、職業(yè)、地域)顧客的購物歷史記錄,有助于開展更具針對(duì)性的商品促銷活動(dòng).

從概念上講,對(duì)比序列模式泛指在一類序列中出現(xiàn)頻繁,而在其他類序列中出現(xiàn)不頻繁的序列[3].傳統(tǒng)對(duì)比序列挖掘算法要求用戶設(shè)置最大、最小支持度閾值.在不具備足夠先驗(yàn)知識(shí)的情況下,用戶難以設(shè)置恰當(dāng)?shù)闹С侄乳撝?這可能導(dǎo)致挖掘不到有用的結(jié)果.為此,文獻(xiàn)[6]提出了top-k對(duì)比序列模式挖掘算法kDSP-Miner,旨在挖掘?qū)Ρ榷茸畲蟮膋個(gè)對(duì)比序列模式.由于設(shè)置k(對(duì)比序列模式的個(gè)數(shù))比設(shè)置支持度閾值更加直觀,因此kDSP-Miner更易于用戶使用.

隨著數(shù)據(jù)采集技術(shù)的發(fā)展,各領(lǐng)域獲取數(shù)據(jù)的規(guī)模越來越大.kDSP-Miner算法基于單臺(tái)計(jì)算機(jī)設(shè)計(jì),難以滿足大規(guī)模數(shù)據(jù)挖掘的需求.因此有必要利用并行計(jì)算技術(shù),設(shè)計(jì)并行挖掘算法,實(shí)現(xiàn)從大規(guī)模序列數(shù)據(jù)中發(fā)現(xiàn)top-k對(duì)比序列模式.Spark是在MapReduce基礎(chǔ)上設(shè)計(jì)的基于內(nèi)存計(jì)算的高容錯(cuò)分布式計(jì)算框架[7].它避免了對(duì)磁盤進(jìn)行頻繁的IO操作,具有良好的伸縮性.本文應(yīng)用Spark技術(shù)于top-k對(duì)比序列模式挖掘,設(shè)計(jì)了基于Spark的top-k對(duì)比序列模式挖掘算法SP-kDSP-Miner.

在Spark框架下設(shè)計(jì)高效穩(wěn)定的top-k對(duì)比序列模式挖掘算法,需要克服3項(xiàng)技術(shù)挑戰(zhàn):

1) 候選對(duì)比序列模式生成.挖掘top-k對(duì)比序列模式要遍歷所有的候選對(duì)比序列模式,經(jīng)過計(jì)算得到對(duì)比最顯著的k個(gè)序列模式；在Spark框架下不同的模式遍歷方式會(huì)導(dǎo)致不同的作業(yè)調(diào)度開銷,所以設(shè)計(jì)合適的候選模式生成策略對(duì)提高算法效率至關(guān)重要.

2) 并行計(jì)算方法.RDD(resilient distributed dataset)是Spark實(shí)現(xiàn)高容錯(cuò)性與數(shù)據(jù)共享提出的彈性分布式數(shù)據(jù),在Spark架構(gòu)下并行挖掘top-k對(duì)比序列模式需要將數(shù)據(jù)集RDD化；對(duì)RDD的不恰當(dāng)操作會(huì)導(dǎo)致額外計(jì)算開銷,因此需要設(shè)計(jì)恰當(dāng)?shù)牟⑿杏?jì)算過程.

3) 剪枝策略.有效的剪枝策略能提高top-k對(duì)比序列模式挖掘的效率；考慮Spark并行計(jì)算框架的特點(diǎn),設(shè)計(jì)有效的剪枝策略是實(shí)現(xiàn)分布式并行挖掘top-k對(duì)比序列模式的關(guān)鍵.

本文主要工作包括4項(xiàng)：

1) 針對(duì)現(xiàn)有top-k對(duì)比序列模式挖掘算法難以處理大規(guī)模數(shù)據(jù)集挖掘的不足,提出利用Spark并行計(jì)算架構(gòu)實(shí)現(xiàn)大規(guī)模序列集合的top-k對(duì)比序列模式挖掘的問題；

2) 針對(duì)Spark集群并行計(jì)算的特點(diǎn),設(shè)計(jì)適合Spark架構(gòu)的候選模式生成策略以及剪枝策略,提高了挖掘算法的執(zhí)行效率；

3) 設(shè)計(jì)適合Spark架構(gòu)的候選對(duì)比序列模式對(duì)比度并行評(píng)價(jià)方法；

4) 利用真實(shí)數(shù)據(jù)集和合成數(shù)據(jù)集進(jìn)行詳實(shí)的實(shí)驗(yàn),驗(yàn)證了SP-kDSP-Miner算法的有效性,執(zhí)行效率及可擴(kuò)展性.

1 問題定義

定義Σ為序列元素的集合.序列集中序列S形式化表示為S=e1e2…en,ei∈Σ(1≤i≤n).為方便表述,用S[i]表示序列S中的第i個(gè)元素,|S|表示序列的長度.對(duì)于序列S中任意元素S[i],S[j](1≤i

例1. 對(duì)于基因序列數(shù)據(jù)集,Σ={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.

假設(shè)存在序列S′=S[k1]S[k2]…S[km],其中1≤k1

例2. 給定序列S=aactc,序列P=ac,間隔約束γ=[0,2].那么,P在S中的實(shí)例有〈1,3〉,〈1,5〉,〈2,3〉,〈2,5〉,實(shí)例〈1,3〉,〈2,3〉,〈2,5〉滿足間隔約束γ,即P?γS,并存在實(shí)例〈2,3〉使P是S的連續(xù)子序列.

給定序列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)為空.例如,對(duì)序列S=aactc,pre(S)=aact,suf(S)=actc.

給定序列樣本集合D、間隔約束γ、序列P在D中的支持度,記為Sup(P,D,γ),則：

(1)

例3. 考慮表1中的序列集合D+,令間隔約束γ=[0,2].給定序列P=ac,對(duì)序列S1有實(shí)例〈1,3〉,〈5,6〉，使得P?γS1,對(duì)序列S2有實(shí)例〈2,3〉，使得P?γS2,對(duì)序列S3有實(shí)例〈1,3〉,〈1,4〉，使得P?γS3.由于|D+|=3,所以Sup(P,D+,γ)=(1+1+1)3=1.0.

給定正例序列集D+、負(fù)例序列集D-和間隔約束γ,本文定義序列P在D+與D-間的對(duì)比度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 序列數(shù)據(jù)集示例

由于間隔約束γ作為運(yùn)行參數(shù)用戶預(yù)先給定,且在挖掘過程中不會(huì)改變.為了表達(dá)簡潔,我們將Sup(P,D,γ)簡化為Sup(P,D),CR(P,D+,D-,γ)簡化為CR(P,D+,D-).表2列出了本文常用的符號(hào)及其定義.

Table 2 Summary of Notations表2 記號(hào)匯總

定義1. 對(duì)比序列模式.給定間隔約束γ、正例序列集D+與負(fù)例序列集D-,若序列P的對(duì)比度CR(P,D+,D-)>0,則P為一個(gè)帶間隔約束γ的對(duì)比序列模式,簡稱為對(duì)比序列模式.

定義2. top-k對(duì)比序列模式.給定間隔約束γ、正例序列集D+、負(fù)例序列集D-，對(duì)比度最大的k個(gè)對(duì)比序列模式,稱為帶間隔約束γ的top-k對(duì)比序列模式,簡稱為top-k對(duì)比序列模式.

值得一提的是,本文在進(jìn)行top-k選擇時(shí),若有多個(gè)模式的對(duì)比度相等,則按2條規(guī)則排序?qū)Ρ榷龋?)優(yōu)先選擇長度更短的模式；2)若長度相同,則按正例序列集合中元素出現(xiàn)順序選擇排序靠前的模式.在實(shí)踐中,用戶也可以根據(jù)實(shí)際情況修改規(guī)則以適應(yīng)具體應(yīng)用的需求.

本文研究問題(top-k對(duì)比序列模式)的定義與文獻(xiàn)[6]一致,但文獻(xiàn)[6]提出的top-k對(duì)比序列模式挖掘算法處理的數(shù)據(jù)規(guī)模難以突破單臺(tái)計(jì)算機(jī)內(nèi)存容量的限制,導(dǎo)致無法獲得挖掘結(jié)果.對(duì)此,本文提出利用Spark并行計(jì)算架構(gòu)實(shí)現(xiàn)大規(guī)模序列集的top-k對(duì)比序列模式挖掘的問題.我們將在后文詳述解決方案.

2 相關(guān)工作

序列數(shù)據(jù)存在于眾多應(yīng)用領(lǐng)域,分析序列數(shù)據(jù)并提取有用的模式,能夠幫助人們發(fā)現(xiàn)數(shù)據(jù)蘊(yùn)含的知識(shí).例如文獻(xiàn)[8]將序列模式挖掘方法應(yīng)用于手機(jī)時(shí)空信息挖掘,提取某一事件的局部或者周邊環(huán)境隨時(shí)間變化的趨勢(shì)；文獻(xiàn)[9]為了提高運(yùn)動(dòng)員的訓(xùn)練積極性,對(duì)運(yùn)動(dòng)員訓(xùn)練的時(shí)間序列數(shù)據(jù)進(jìn)行挖掘,發(fā)現(xiàn)運(yùn)動(dòng)員最偏好的訓(xùn)練方式；文獻(xiàn)[10]基于關(guān)聯(lián)規(guī)則及支持向量機(jī)建立了2個(gè)分類器,利用頻繁子序列提高蛋白質(zhì)序列分類的準(zhǔn)確性和執(zhí)行效率.這些工作中都沒有引入間隔約束的概念,且沒有考慮序列樣本的類別.

在序列模式中考慮間隔約束能夠提高序列模式的適用性與靈活性,所以間隔約束被普遍應(yīng)用于序列模式挖掘中.文獻(xiàn)[11]針對(duì)蛋白質(zhì)序列數(shù)據(jù)過長,而數(shù)據(jù)量偏少的特點(diǎn),在蛋白質(zhì)序列數(shù)據(jù)挖掘中引入間隔約束,增強(qiáng)了挖掘結(jié)果的適用性,并提高了算法的效率；文獻(xiàn)[12]認(rèn)為挖掘頻繁子序列中人為設(shè)置間隔約束影響挖掘結(jié)果,因此設(shè)計(jì)了高效的萬能間隔約束挖掘頻繁子序列；文獻(xiàn)[13]設(shè)計(jì)了Gap-BIDE算法挖掘帶間隔約束的閉合序列模式,并從挖掘結(jié)果中抽取特征建立分類器；文獻(xiàn)[14]在頻繁閉合序列模式挖掘中,引入了非用戶設(shè)定間隔約束的概念,其挖掘結(jié)果具有更強(qiáng)的解釋性；文獻(xiàn)[15]為了提高序列模式挖掘的效率,基于間隔約束設(shè)計(jì)了2種模式生成策略與剪枝策略,最后通過實(shí)驗(yàn)驗(yàn)證了算法的執(zhí)行效率.上述工作沒有考慮序列樣本的類別,無法識(shí)別不同序列集合間的差異.

對(duì)比序列模式挖掘能夠發(fā)現(xiàn)識(shí)別不同類別序列樣本集合間的差異,并描述各類別樣本集合的特征.文獻(xiàn)[3]提出了具有最小模式的對(duì)比序列模式,并設(shè)計(jì)ConSGapMiner算法挖掘2個(gè)序列集合間的對(duì)比序列模式；文獻(xiàn)[16]建立以對(duì)比序列模式為特征的分類器,并對(duì)蛋白質(zhì)序列多肽折疊進(jìn)行分類；文獻(xiàn)[17]在對(duì)比序列中引入“密度概念”,豐富了“頻繁”含義,并設(shè)計(jì)了gd-DSPMiner算法挖掘滿足“密度”約束的對(duì)比序列模式.上述對(duì)比序列挖掘工作都需要用戶預(yù)先設(shè)定支持度閾值.

由于在不具備充分領(lǐng)域知識(shí)的情況下,用戶難以設(shè)定恰當(dāng)?shù)闹С侄乳撝?因此,用參數(shù)k(模式的個(gè)數(shù))代替支持度閾值更易于實(shí)際應(yīng)用.文獻(xiàn)[18]設(shè)計(jì)了應(yīng)用于活動(dòng)序列數(shù)據(jù)集的top-k對(duì)比序列挖掘算法,挖掘2個(gè)數(shù)據(jù)集中出現(xiàn)頻率對(duì)比最顯著的對(duì)比序列模式；文獻(xiàn)[19]為尋找DNA序列模式與疾病表現(xiàn)的關(guān)系,運(yùn)用top-k挖掘?qū)Ρ榷茸铒@著的k個(gè)對(duì)比序列模式并建立分類器；文獻(xiàn)[6]為了避免設(shè)置支持度閾值,用top-k代替支持度閾值挖掘?qū)Ρ刃蛄心Ｊ?

隨著各應(yīng)用領(lǐng)域數(shù)據(jù)采集能力的增強(qiáng),基于Spark的大規(guī)模數(shù)據(jù)挖掘得到越來越多的關(guān)注.文獻(xiàn)[20]在Spark框架下實(shí)現(xiàn)了大規(guī)模數(shù)據(jù)的評(píng)估過程；文獻(xiàn)[21]用Spark解決了基因檢測技術(shù)的效率問題；文獻(xiàn)[22]提出了基于Spark的分布式算法對(duì)推特上的大規(guī)模數(shù)據(jù)進(jìn)行情感分析；文獻(xiàn)[23]利用Spark從大規(guī)模單圖上挖掘頻繁子圖,提高了挖掘效率.

據(jù)我們所知,文獻(xiàn)[6]與本文研究工作最接近.但是文獻(xiàn)[6]提出的算法kDSP-Miner基于單臺(tái)計(jì)算機(jī)設(shè)計(jì),其關(guān)鍵步驟,如采用深度優(yōu)先遍歷集合枚舉樹生成候選模式的策略,不適合于并行計(jì)算,導(dǎo)致其難以對(duì)大規(guī)模數(shù)據(jù)進(jìn)行高效挖掘.對(duì)此,本文基于Spark架構(gòu)特點(diǎn)設(shè)計(jì)的算法能夠有效地彌補(bǔ)kDSP-Miner的不足.

3 SP-kDSP-Miner算法設(shè)計(jì)

為了實(shí)現(xiàn)大規(guī)模序列集合中top-k對(duì)比序列模式的高效挖掘,本文提出基于Spark的分布式并行處理算法SP-kDSP-Miner.算法要點(diǎn)包括：1)Spark架構(gòu)下候選對(duì)比序列模式生成；2)利用Spark集群計(jì)算候選對(duì)比序列模式的對(duì)比度；3)Spark架構(gòu)下的候選模式剪枝策略.

圖1給出了SP-kDSP-Miner算法的流程圖.

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

從圖1可以看出,SP-kDSP-Miner算法主要包括4個(gè)步驟：

① 啟動(dòng)SP-kDSP-Miner算法并調(diào)度Spark集群從HDFS(Hadoop distributed file system)中載入數(shù)據(jù)到各計(jì)算節(jié)點(diǎn),完成數(shù)據(jù)預(yù)處理；

② 生成候選對(duì)比序列模式集合,如果候選對(duì)比序列模式集合不為空集,則執(zhí)行步驟③,否則執(zhí)行步驟④；

③ 調(diào)度Spark工作集群,計(jì)算每個(gè)候選對(duì)比序列模式的對(duì)比度；

④ 輸出top-k對(duì)比序列模式挖掘結(jié)果.

在SP-kDSP-Miner算法流程中,步驟②生成候選對(duì)比序列模式集合與步驟③調(diào)用Spark集群計(jì)算候選對(duì)比序列模式的對(duì)比度是整個(gè)算法的核心部分.本文接下來將分別介紹步驟②和步驟③以及如何提高算法的執(zhí)行效率.

3.1 候選對(duì)比序列模式生成

容易想到,可以采用遍歷集合枚舉樹(如圖2所示)的方式生成候選對(duì)比序列模式.完全遍歷集合枚舉樹會(huì)導(dǎo)致大量不必要的計(jì)算開銷,因此,設(shè)計(jì)適用于Spark架構(gòu)的集合枚舉樹遍歷方式和剪枝策略是算法執(zhí)行效率的基礎(chǔ).首先,我們分析對(duì)比序列模式關(guān)于對(duì)比度的性質(zhì)及可以得到的剪枝策略.

引理1. 給定間隔約束γ、正例序列集D+、負(fù)例序列集D-、對(duì)序列P,若Sup(P,D+)≤σ(σ>0),則CR(P,D+,D-)≤σ.

證明.

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

因?yàn)镃R(P,D+,D-)=Sup(P,D+)-Sup(P,D-)，

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

因?yàn)镾up(P,D-,)≥0,

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

證畢.

定理1. 給定間隔約束γ、正例序列集D+、負(fù)例序列集D-、對(duì)序列P,若Sup(P,D+)=0,則P不是對(duì)比序列模式.

證明.

用反證法證明.假設(shè)P是對(duì)比序列模式,根據(jù)定義1,CR(P,D+,D-)>0.

由性質(zhì)1可知,CR(P,D+,D-)≤Sup(P,D+)=0,與對(duì)比序列模式定義矛盾.

所以給定候選對(duì)比序列模式P,若Sup(P,D+)=0,P不可能成為SP-kDSP-Miner算法的挖掘目標(biāo).

證畢.

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

剪枝策略1. 給定候選對(duì)比序列模式P,若Sup(P,D+)=0,那么剪去集合枚舉樹中P的所有子節(jié)點(diǎn).

根據(jù)剪枝策略1,在生成候選對(duì)比序列模式時(shí),我們只需要考慮Σ中出現(xiàn)在D+中的元素.

定理2. 給定間隔約束γ、正例序列集D+、序列P和P′,滿足P′是P的連續(xù)子序列.若Sup(P′,D+)<σ，σ>0,則P的正例支持度Sup(P,D+)≤Sup(P′,D+)<σ.

證明.

因?yàn)镻′是P的連續(xù)子序列,

所以給定序列集D+、間隔約束γ、對(duì)于任意序列S(S∈D+),P′?γS成立,但P?γS不一定成立；

所以根據(jù)式(1)可得：

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

證畢.

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

剪枝策略2. 令R為當(dāng)前對(duì)比度最大的k個(gè)對(duì)比序列模式集合,CRmin=min{CR(P″,D+,D-)|P″∈R}.若Sup(P,D+)

在Spark并行計(jì)算中,每項(xiàng)有結(jié)果返回的操作都會(huì)形成1項(xiàng)具體的作業(yè),1次作業(yè)的開銷主要包括：作業(yè)調(diào)度開銷、作業(yè)通信開銷、作業(yè)計(jì)算開銷.如果1次作業(yè)只計(jì)算1個(gè)候選對(duì)比序列模式的對(duì)比度,作業(yè)調(diào)度次數(shù)等于候選模式數(shù)量,這將導(dǎo)致大量的作業(yè)調(diào)度開銷,使得Spark集群工作節(jié)點(diǎn)長時(shí)間處于空閑狀態(tài),無法發(fā)揮Spark集群并行計(jì)算的優(yōu)勢(shì).因此,應(yīng)該盡可能產(chǎn)生相互不影響(沒有剪枝關(guān)系)的候選對(duì)比序列模式,進(jìn)而在1次Spark作業(yè)中可以并行處理多個(gè)候選模式,充分利用Spark集群的計(jì)算能力,提高計(jì)算效率.

考慮文獻(xiàn)[6]采用的深度優(yōu)先遍歷集合枚舉樹生成候選模式的策略.我們可以一次生成候選模式P及所有包含P為連續(xù)子序列的候選模式.如果Sup(P,D+)

廣度優(yōu)先遍歷策略在生成長度為l的候選對(duì)比序列模式之前會(huì)先生成所有長度小于l的候選模式.注意：長度相等的候選模式,它們之間不存在子序列關(guān)系,因此不會(huì)出現(xiàn)相互剪枝的情況.而1次Spark作業(yè)中可以并行處理所有長度為l的候選對(duì)比序列模式,有效降低作業(yè)調(diào)度開銷,充分利用Spark集群的計(jì)算能力,提高算法效率.

基于廣度優(yōu)先遍歷集合枚舉樹策略,我們?cè)O(shè)計(jì)了候選模式的生成方法.給定候選對(duì)比序列模式P,Q(|P|=|Q|=l),如果pre(P)=suf(Q),則由P,Q可生成第l+1層的對(duì)比候選序列模式,表示為

(3)

本文模式生成方法是集合枚舉樹寬度優(yōu)先遍歷的一種具體實(shí)現(xiàn).圖2示例了集合枚舉樹.

Fig. 2 An example of a set enumeration tree圖2 集合枚舉樹示例

算法1給出了SP-kDSP-Miner生成候選模式算法的偽代碼.

算法1.GENERATE(Cl)算法.

輸入: 長度為l的候選對(duì)比序列模式的集合Cl、當(dāng)前對(duì)比度最大的k個(gè)對(duì)比序列模式中最小的對(duì)比度CRmin；

輸出: 長度為l+1的候選對(duì)比序列模式集合Cl+1.

①Cl+1←?；*初始化長度為l+1的候選對(duì)比序列集合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的候選對(duì)比序列模式集合Cl生成長度為l+1的候選對(duì)比序列模式集合Cl+1.步驟②利用剪枝策略2,移除不可能成為top-k對(duì)比序列模式的候選模式.步驟③～⑦生成長度為l+1的候選對(duì)比序列模式.步驟⑧返回利用算法1生成的候選對(duì)比序列模式集合.算法1的算法復(fù)雜度為O(|Cl|),其中|Cl|是長度為l的候選對(duì)比序列模式的個(gè)數(shù).

Fig. 3 Contrast calculation process in SP-kDSP-Miner圖3 SP-kDSP-Miner中對(duì)比度計(jì)算過程

3.2 對(duì)比度并行計(jì)算

SP-kDSP-Miner使用Spark分布式框架將大規(guī)模數(shù)據(jù)分片并讀入計(jì)算節(jié)點(diǎn),然后各計(jì)算結(jié)點(diǎn)獲取候選對(duì)比序列模式集合,SP-kDSP-Miner算法再調(diào)用Spark計(jì)算節(jié)點(diǎn)評(píng)價(jià)每個(gè)候選對(duì)比序列模式的對(duì)比度.圖3展示了對(duì)比度的計(jì)算過程.

如圖3所示,對(duì)比度的計(jì)算過程主要包括3個(gè)步驟：

① 利用Spark并行操作textfile()從HDFS載入數(shù)據(jù)到計(jì)算節(jié)點(diǎn)內(nèi)存；

② 分別計(jì)算候選對(duì)比序列模式的正例支持度與負(fù)例支持度.計(jì)算支持度時(shí)先將候選對(duì)比序列模式集合Cl拷貝到計(jì)算節(jié)點(diǎn),調(diào)用Spark并行操作函數(shù)map()對(duì)每一條序列數(shù)據(jù)進(jìn)行子序列匹配,然后用flatmap()操作與groupbykey()操作統(tǒng)計(jì)子序列匹配結(jié)果,最后用統(tǒng)計(jì)結(jié)果計(jì)算出模式P(P∈Cl)的支持度；

③ 用并行操作join()將模式P(P∈Cl)的正例支持度與負(fù)例支持度集合在一起,然后調(diào)用map()操作計(jì)算對(duì)比度并輸出結(jié)果.

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

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

在對(duì)比度計(jì)算過程中,令Cl是長度為l的候選對(duì)比序列模式集合.若有P∈Cl,滿足Sup(P,D+)

剪枝策略3. 在對(duì)比度計(jì)算過程中,對(duì)于候選模式P,若sup(P,D+)

表面上看,剪枝策略3與剪枝策略2都基于定理2,但它們的執(zhí)行時(shí)機(jī)與剪枝對(duì)象不同.剪枝策略3在對(duì)比度計(jì)算過程中生效,即在剪枝條件(CRmin)變化前執(zhí)行.這是因?yàn)橛?jì)算對(duì)比度時(shí)使用并行方法,為了降低通信開銷,只能先計(jì)算正例支持度,這樣剪枝策略3可以避免不必要的負(fù)例支持度計(jì)算.而完成對(duì)比度計(jì)算之后,會(huì)更新全局的結(jié)果集R,剪枝條件(CRmin)也隨之更新,在生成新的候選對(duì)比序列模式時(shí)剪枝策略2生效,避免生成無意義的候選模式.

在對(duì)比度計(jì)算步驟②中,SP-kDSP-Miner在裝載序列數(shù)據(jù)時(shí)進(jìn)行編碼.給定任意元素e在序列S,我們用位向量Pos(e,S)記錄e在序列S中的位置信息,用Pos(e,S)[i]表示Pos(e,S)的第i位:

(4)

式(4)描述了位向量的編碼規(guī)則.例如對(duì)于序列S=atcgacat,元素a在第1,5,7位出現(xiàn),因此Pos(a,S)=10 001 010.

給定間隔約束γ=[γ.min,γ.max],若序列S與模式P匹配,那么必然有S[i]=P[j],S[k]=P[j+1],且i+γ.min

3.3 復(fù)雜度分析及負(fù)載均衡

在Spark架構(gòu)下對(duì)比度計(jì)算過程以及候選對(duì)比序列模式生成方法的支持下,算法2示例了SP-kDSP-Miner的偽代碼.

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

輸入: 正例序列集D+、負(fù)例序列集D-、間隔約束γ和參數(shù)k；

輸出: top-k對(duì)比序列模式集合R.

①R←?；*R保存挖掘結(jié)果*

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

③C←Σ；

④ whileC≠? do

⑤ 利用spark集群計(jì)算候選對(duì)比序列模式的對(duì)比度*剪枝策略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框架的分布式算法的運(yùn)行時(shí)間取決于計(jì)算時(shí)間最長的計(jì)算節(jié)點(diǎn),即符合木桶效應(yīng).因此,實(shí)現(xiàn)各計(jì)算節(jié)點(diǎn)的負(fù)載均衡有利于降低算法總執(zhí)行時(shí)間.在算法2中步驟⑤調(diào)用Spark工作集群計(jì)算候選對(duì)比序列模式的對(duì)比度,當(dāng)SP-kDSP-Miner評(píng)價(jià)候選對(duì)比模式P在正負(fù)例序列集間的差異度時(shí),會(huì)將模式P拷貝到各個(gè)計(jì)算節(jié)點(diǎn),然后將模式P與計(jì)算節(jié)點(diǎn)載入的序列數(shù)據(jù)進(jìn)行子序列匹配,最終各個(gè)計(jì)算節(jié)點(diǎn)將匹配結(jié)果匯總,計(jì)算出對(duì)比度.在整個(gè)差異度評(píng)價(jià)過程中,計(jì)算節(jié)點(diǎn)的計(jì)算量與載入的序列數(shù)據(jù)大小成正比關(guān)系.為保證計(jì)算節(jié)點(diǎn)負(fù)載均衡,各個(gè)計(jì)算節(jié)點(diǎn)載入的序列數(shù)據(jù)大小應(yīng)該盡量相同.

因此,在對(duì)D+,D-進(jìn)行分片時(shí),我們采用均分策略,即將數(shù)據(jù)集分片為與計(jì)算節(jié)點(diǎn)數(shù)量相同的等份載入節(jié)點(diǎn).下一步研究工作中,我們將考慮計(jì)算節(jié)點(diǎn)的負(fù)載動(dòng)態(tài)均衡,即允許節(jié)點(diǎn)的負(fù)載在算法執(zhí)行過程中動(dòng)態(tài)調(diào)整.

4 實(shí) 驗(yàn)

4.1 實(shí)驗(yàn)環(huán)境

本文在真實(shí)序列集與合成序列集上進(jìn)行了實(shí)驗(yàn),以驗(yàn)證算法的有效性、執(zhí)行效率及可擴(kuò)展性.實(shí)驗(yàn)采用PFam數(shù)據(jù)庫*http:pfam.sanger.ac.uk提供的2個(gè)真實(shí)序列集：蛋白質(zhì)序列數(shù)據(jù)家族Actin與ABC-2.并以真實(shí)序列集Actin為基礎(chǔ),用不同策略合成2組合成序列集,用來進(jìn)行數(shù)據(jù)規(guī)模的擴(kuò)展性實(shí)驗(yàn).

在蛋白質(zhì)序列數(shù)據(jù)家族Actin中,包含了多個(gè)家庭成員序列集,本文選取PF00012作為正例序列集,PF00022作為負(fù)例序列集.類似地,在ABC-2家族中,本文選取APF01061作為正例序列集,APF12698作為負(fù)例序列集.合成序列集分別為DBMA,DBMB.DBMA的合成方式：首先分別獲取Actin中正負(fù)序列集各元素出現(xiàn)的頻率,然后根據(jù)正例序列集中元素的頻率合成序列長度為60～200的正例序列集,根據(jù)負(fù)例序列集中元素的出現(xiàn)頻率合成序列長度為60～200的負(fù)例序列集.DBMB的合成方式：Actin擴(kuò)大數(shù)倍.表4列出了實(shí)驗(yàn)中使用的序列集的特征.

Table 4 Characteristics of Data Sets表4 數(shù)據(jù)集特征

SP-kDSP-Miner算法用Python2.7.0編程實(shí)現(xiàn),在Spark1.5.0與CDH4(cloudera’s distribution including Apache Hadoop 4)搭建的架構(gòu)下進(jìn)行實(shí)驗(yàn).Spark集群總節(jié)點(diǎn)數(shù)為8,每個(gè)節(jié)點(diǎn)為配置是Intel core i7-4770 3.40 GHz CPU,16 GB內(nèi)存,Ubuntu14.04操作系統(tǒng)的PC.所有實(shí)驗(yàn)數(shù)據(jù)都預(yù)先存入HDFS.

4.2 有效性實(shí)驗(yàn)

因?yàn)楸疚墓ぷ鞯耐诰蚰繕?biāo)與文獻(xiàn)[6]相同,所以用kDSP-Miner挖掘結(jié)果與SP-kDSP-Miner的挖掘結(jié)果進(jìn)行對(duì)比,以驗(yàn)證有效性.進(jìn)行有效性實(shí)驗(yàn)時(shí),本文在Actin,ABC-2,DBMA和DBMB序列集上分別運(yùn)行SP-kDSP-Miner算法與kDSP-Miner算法,挖掘帶間隔約束的top-k對(duì)比序列模式.為了保證挖掘目標(biāo)的一致性,SP-kDSP-Miner算法和kDSP-Miner算法的參數(shù)γ,k應(yīng)該相同,默認(rèn)值為γ=[0,2],k=10.kDSP-Miner算法代碼來自于文獻(xiàn)[6].

表5展示了算法kDSP-Miner與SP-kDSP-Miner在2個(gè)蛋白質(zhì)真實(shí)序列集上的挖掘結(jié)果.從表5可知,2個(gè)算法挖掘結(jié)果一致.表6展示了在2個(gè)合成大規(guī)模序列集上的挖掘結(jié)果.由表6可知,SP-kDSP-Miner最終得到了結(jié)果,而kDSP-Miner使用深度優(yōu)先策略,在迭代過程中占用了大量內(nèi)存保存中間結(jié)果,最終因?yàn)閮?nèi)存限制無法挖掘到有效的結(jié)果.實(shí)驗(yàn)結(jié)果驗(yàn)證了SP-kDSP-Miner能夠從大規(guī)模數(shù)據(jù)中挖掘top-k帶間隔約束的對(duì)比序列模式.

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

Table 6 Mining Results of the Data Sets DBMA & DBMB表6 數(shù)據(jù)集DBMA,DBMB的挖掘結(jié)果

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

4.3 執(zhí)行效率實(shí)驗(yàn)

為了驗(yàn)證SP-kDSP-Miner的執(zhí)行效率,本文使用kDSP-Miner進(jìn)行對(duì)比.與kDSP-Miner一樣,SP-kDSP-Miner需要設(shè)定的參數(shù)為γ與k.圖4～5展示了參數(shù)對(duì)SP-kDSP-Miner算法的影響.因?yàn)閗DSP-Miner算法難以適用于大規(guī)模序列數(shù)據(jù)集,所以只對(duì)ABC-2與Actin兩個(gè)序列集進(jìn)行了實(shí)驗(yàn).進(jìn)行此實(shí)驗(yàn)時(shí),SP-kDSP-Miner算法用到Spark集群的4個(gè)節(jié)點(diǎn),kDSP-Miner所用線程數(shù)為5.

圖4展示了當(dāng)設(shè)置k=10時(shí),間隔約束γ對(duì)算法執(zhí)行效率的影響,并與kDSP-Miner進(jìn)行了比較.隨著間隔約束的范圍增大,候選元素之間有效的組合變多,kDSP-Miner與SP-kDSP-Miner運(yùn)行時(shí)間都會(huì)隨之增加.相較于kDSP-Miner,SP-kDSP-Miner變化趨勢(shì)緩慢一些.因?yàn)殚g隔約束的范圍比較小,候選模式少,Spark集群計(jì)算能力沒有被充分利用.并且SP-kDSP-Miner在計(jì)算對(duì)比度過程中,設(shè)計(jì)了減枝策略3,降低了計(jì)算量.總體來說,對(duì)于任意的間隔約束γ,具有集群優(yōu)勢(shì)的SP-kDSP-Miner執(zhí)行時(shí)間較kDSP-Miner更短,并且隨著間隔約束γ的范圍變大,SP-kDSP-Miner所用集群的計(jì)算能力被充分利用,執(zhí)行效率會(huì)有一定程度提高.

圖5展示了當(dāng)設(shè)置γ=[0,2]時(shí)k值對(duì)算法執(zhí)行效率的影響,并與kDSP-Miner進(jìn)行了比較.隨著k值增大,SP-kDSP-Miner與kDSP-Miner執(zhí)行時(shí)間都有增加的趨勢(shì),但是kDSP-Miner算法執(zhí)行時(shí)間波動(dòng)較大.總體上看,SP-kDSP-Miner算法得益于Spark的集群優(yōu)勢(shì),在同等規(guī)模數(shù)據(jù)集下挖掘速度更快.

Fig. 4 Runtime w.r.t. gap constraints (k=10)圖4 采用不同間隔約束的執(zhí)行時(shí)間(k=10)

Fig. 5 Runtime w.r.t. k value (γ=[0,2])圖5 采用不同k值的執(zhí)行時(shí)間(γ=[0,2])

最重要的是,SP-kDSP-Miner具有可擴(kuò)展性.隨著Spark節(jié)點(diǎn)集群增加,SP-kDSP-Miner的執(zhí)行時(shí)間會(huì)進(jìn)一步降低.

4.4 擴(kuò)展性實(shí)驗(yàn)

為了驗(yàn)證SP-kDSP-Miner的適用范圍,本文在合成數(shù)據(jù)集DBMA與DBMB上進(jìn)行了擴(kuò)展性實(shí)驗(yàn).圖6、圖7分別展示了不同的數(shù)據(jù)規(guī)模,以及不同的Spark集群節(jié)點(diǎn)對(duì)算法執(zhí)行時(shí)間的影響.在數(shù)據(jù)規(guī)模擴(kuò)展性實(shí)驗(yàn)中,運(yùn)用不同節(jié)點(diǎn)數(shù)量的SP-kDSP-Miner算法在2個(gè)合成數(shù)據(jù)集DBMA,DBMB上進(jìn)行了實(shí)驗(yàn),節(jié)點(diǎn)數(shù)Nodes分別為2,4,6,8.

在圖6中,隨著數(shù)據(jù)規(guī)模的擴(kuò)大,執(zhí)行時(shí)間呈線性增長.在圖7中,隨著節(jié)點(diǎn)數(shù)量的增加,執(zhí)行時(shí)間先大幅度下降,再趨于平緩,是因?yàn)楣?jié)點(diǎn)數(shù)量與運(yùn)行時(shí)間之間呈反比關(guān)系.所以,隨著Spark集群節(jié)點(diǎn)數(shù)增加,能有效降低SP-kDSP-Miner的執(zhí)行時(shí)間.

Fig. 7 Runtime w.r.t. number of nodes圖7 節(jié)點(diǎn)擴(kuò)展性實(shí)驗(yàn)

5 結(jié) 論

帶間隔約束的top-k對(duì)比序列模式挖掘能夠從2個(gè)不同類別的序列數(shù)據(jù)集合中挖掘出對(duì)比度最大的k個(gè)對(duì)比序列模式.但是現(xiàn)有的帶間隔約束的top-k對(duì)比序列模式挖掘算法并不能有效地從大規(guī)模數(shù)據(jù)中挖掘出結(jié)果.針對(duì)這個(gè)問題,本文提出了基于Spark的帶間隔約束的top-k對(duì)比序列模式挖掘算法SP-kDSP-Miner,設(shè)計(jì)了3個(gè)剪枝策略.最后在真實(shí)序列集與合成序列集上驗(yàn)證了SP-kDSP-Miner的有效性,執(zhí)行效率與可擴(kuò)展性.

在下一步工作中,我們將增加Spark集群中計(jì)算節(jié)點(diǎn)的數(shù)量,使SP-kDSP-Miner適用于更大規(guī)模的數(shù)據(jù)分析.我們還將考慮計(jì)算節(jié)點(diǎn)間的動(dòng)態(tài)負(fù)載均衡,即允許節(jié)點(diǎn)間的負(fù)載在算法執(zhí)行過程中動(dòng)態(tài)調(diào)整.同時(shí),在更多實(shí)際應(yīng)用中驗(yàn)證SP-kDSP-Miner的有效性.例如在生物信息學(xué)領(lǐng)域,挖掘相同遺傳病不同表征的基因序列差異；在醫(yī)學(xué)領(lǐng)域,挖掘患病人群與健康人群的基因組差異；在互聯(lián)網(wǎng)金融領(lǐng)域,挖掘不同人群的投資特點(diǎn).

[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對(duì)比序列模式挖掘[J]. 軟件學(xué)報(bào), 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)(嚴(yán)玉良, 董一鴻, 何賢芒, 等. FSMBUS: 一種基于Spark的大規(guī)模頻繁子圖挖掘算法[J]. 計(jì)算機(jī)研究與發(fā)展, 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

國家自然科學(xué)基金項(xiàng)目(61572332,61363037)；國家自然科學(xué)基金委員會(huì)-中國民用航空局民航聯(lián)和研究基金項(xiàng)目(U1333113)；中國博士后科學(xué)基金特別資助項(xiàng)目(2016T90850)；中央高校基本科研業(yè)務(wù)費(fèi)專項(xiàng)資金項(xiàng)目(2016SCU04A22)；四川省科技支撐計(jì)劃基金項(xiàng)目(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