對(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-kDSPMiner的效率,針對(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ì)算機(jī)研究與發(fā)展. 2017,54(07)北大核心EICSCD

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

【部分圖文】：

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

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

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

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



本文編號(hào)：3491893