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

【文章來源】：計算機研究與發(fā)展. 2017,54(07)北大核心EICSCD

【文章頁數(shù)】：13 頁

【部分圖文】：

圖２集合枚舉樹示例Ｆｉｇ．２Ａｎｅｘａｍｐｌｅｏｆａｓｅｔｅｎｕｍｅｒａｔｉｏｎｔｒｅｅ

列模式集合Ｃｌ生成長度為ｌ＋１的候選對比序列模式集合Ｃｌ＋１．步驟②利用剪枝策略２，移除不可能成為ｔｏｐ－ｋ對比序列模式的候選模式．步驟③～⑦生成長度為ｌ＋１的候選對比序列模式．步驟⑧返回利用算法１生成的候選對比序列模式集合．算法１的算法復雜度為Ｏ（｜Ｃｌ｜），其中｜Ｃｌ｜是長度為ｌ的候選對比序列模式的個數(shù)．Ｆｉｇ．３ＣｏｎｔｒａｓｔｃａｌｃｕｌａｔｉｏｎｐｒｏｃｅｓｓｉｎＳＰ－ｋＤＳＰ－Ｍｉｎｅｒ圖３ＳＰ－ｋＤＳＰ－Ｍｉｎｅｒ中對比度計算過程３．２對比度并行計算ＳＰ－ｋＤＳＰ－Ｍｉｎｅｒ使用Ｓｐａｒｋ分布式框架將大規(guī)模數(shù)據(jù)分片并讀入計算節(jié)點，然后各計算結(jié)點獲�。保矗担窂堸i等：基于Ｓｐａｒｋ的Ｔｏｐ－ｋ對比序列模式挖掘

Ｍｉｎｅｒ的執(zhí)行效率，本文使用ｋＤＳＰ－Ｍｉｎｅｒ進行對比．與ｋＤＳＰ－Ｍｉｎｅｒ一樣，ＳＰ－ｋＤＳＰ－Ｍｉｎｅｒ需要設定的參數(shù)為γ與ｋ．圖４～５展示了參數(shù)對ＳＰ－ｋＤＳＰ－Ｍｉｎｅｒ算法的影響．因為ｋＤＳＰ－Ｍｉｎｅｒ算法難以適用于大規(guī)模序列數(shù)據(jù)集，所以只對ＡＢＣ－２與Ａｃｔｉｎ兩個序列集進行了實驗．進行此實驗時，ＳＰ－ｋＤＳＰ－Ｍｉｎｅｒ算法用到Ｓｐａｒｋ集群的４個節(jié)點，ｋＤＳＰ－Ｍｉｎｅｒ所用線程數(shù)為５．圖４展示了當設置ｋ＝１０時，間隔約束γ對算法執(zhí)行效率的影響，并與ｋＤＳＰ－Ｍｉｎｅｒ進行了比較．隨著間隔約束的范圍增大，候選元素之間有效的組合變多，ｋＤＳＰ－Ｍｉｎｅｒ與ＳＰ－ｋＤＳＰ－Ｍｉｎｅｒ運行時間都會隨之增加．相較于ｋＤＳＰ－Ｍｉｎｅｒ，ＳＰ－ｋＤＳＰ－Ｍｉｎｅｒ變化趨勢緩慢一些．因為間隔約束的范圍比較小，候選模式少，Ｓｐａｒｋ集群計算能力沒有被充分利用．并且ＳＰ－ｋＤＳＰ－Ｍｉｎｅｒ在計算對比度過程中，設計了減枝策略３，降低了計算量．總體來說，對于任意的間隔約束γ，具有集群優(yōu)勢的ＳＰ－ｋＤＳＰ－Ｍｉｎｅｒ執(zhí)行時間較ｋＤＳＰ－Ｍｉｎｅｒ更短，并且隨著間隔約束γ的范圍變大，ＳＰ－ｋＤＳＰ－Ｍｉｎｅｒ所用集群的計算能力被充分利用，執(zhí)行效率會有一定程度提高．圖５展示了當設置γ＝［０，２］時ｋ值對算法執(zhí)行效率的影響，并與ｋＤＳＰ－Ｍｉｎｅｒ進行了比較．隨著ｋ值增大，ＳＰ－ｋＤＳＰ－Ｍｉｎｅｒ與ｋＤＳＰ－Ｍｉｎｅｒ執(zhí)行時間

【參考文獻】：
期刊論文
[1]帶間隔約束的Top-k對比序列模式挖掘[J]. 楊皓,段磊,胡斌,鄧松,王文韜,秦攀.  軟件學報. 2015(11)
[2]FSMBUS:一種基于Spark的大規(guī)模頻繁子圖挖掘算法[J]. 嚴玉良,董一鴻,何賢芒,汪衛(wèi).  計算機研究與發(fā)展. 2015(08)



本文編號：3491893