基于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