韓 超，段 磊,2+，鄧 松，王慧鋒，唐常杰

1.四川大學(xué) 計(jì)算機(jī)學(xué)院，成都 610065

2.四川大學(xué) 華西公共衛(wèi)生學(xué)院，成都 610041

3.南京郵電大學(xué) 先進(jìn)技術(shù)研究院，南京 210003

基于Spark的序列數(shù)據(jù)質(zhì)量評(píng)價(jià)*

韓 超1，段 磊1,2+，鄧 松3，王慧鋒1，唐常杰1

1.四川大學(xué) 計(jì)算機(jī)學(xué)院，成都 610065

2.四川大學(xué) 華西公共衛(wèi)生學(xué)院，成都 610041

3.南京郵電大學(xué) 先進(jìn)技術(shù)研究院，南京 210003

HAN Chao,DUAN Lei,DENG Song,et al.Evaluation of sequential data quality using Spark.Journal of Frontiers of Computer Science and Technology,2017,11(6)：897-907.

隨著序列數(shù)據(jù)在實(shí)際中的廣泛應(yīng)用，序列數(shù)據(jù)質(zhì)量評(píng)價(jià)成為學(xué)術(shù)、工業(yè)等眾多領(lǐng)域的熱門研究問題。目前主流的序列數(shù)據(jù)質(zhì)量評(píng)價(jià)方法是基于概率后綴樹模型進(jìn)行數(shù)據(jù)質(zhì)量評(píng)價(jià)，然而這種方法難以實(shí)現(xiàn)對(duì)大規(guī)模數(shù)據(jù)的處理。為解決此問題，提出了基于Spark的序列數(shù)據(jù)質(zhì)量評(píng)價(jià)算法STALK（sequential data quality evaluation with Spark），并且采用了改進(jìn)的剪枝策略來提高算法效率。具體地，在Spark平臺(tái)下，利用大規(guī)模序列數(shù)據(jù)高效建立生成模型，并根據(jù)生成模型對(duì)查詢序列的數(shù)據(jù)質(zhì)量進(jìn)行快速評(píng)價(jià)。最后通過真實(shí)序列數(shù)據(jù)集驗(yàn)證了STALK算法的有效性、執(zhí)行效率和可擴(kuò)展性。

數(shù)據(jù)質(zhì)量；概率后綴樹；Spark；并行計(jì)算

1 引言

大數(shù)據(jù)時(shí)代下的數(shù)據(jù)信息成為社會(huì)關(guān)注焦點(diǎn)。數(shù)據(jù)質(zhì)量的高低影響其承載信息的利用效率和傳播廣度。高質(zhì)量的數(shù)據(jù)是統(tǒng)計(jì)分析、數(shù)據(jù)挖掘、決策支持的基石；含有誤差、噪聲等質(zhì)量差的數(shù)據(jù)會(huì)降低數(shù)據(jù)信息的利用和價(jià)值，降低生產(chǎn)生活效率。

傳統(tǒng)的數(shù)據(jù)質(zhì)量評(píng)價(jià)主要依靠定性策略，即從數(shù)據(jù)的一致性、完整性、及時(shí)性和準(zhǔn)確性等指標(biāo)進(jìn)行統(tǒng)計(jì)分析[1]。針對(duì)序列數(shù)據(jù)，傳統(tǒng)質(zhì)量評(píng)價(jià)算法缺少對(duì)數(shù)據(jù)模型和序列元素出現(xiàn)周期性變化的分析，對(duì)此文獻(xiàn)[2]考慮間隔約束，提出通過概率后綴樹[3]和馬爾科夫鏈型生成訓(xùn)練模型的數(shù)據(jù)質(zhì)量評(píng)價(jià)方法。然而，文獻(xiàn)[2]提出的SQEPST（sequence quality evaluation based on probability suffix tree）算法伸縮性差，難以適用大規(guī)模數(shù)據(jù)。

Spark框架具有較高的容錯(cuò)性和伸縮性[4]，為解決大規(guī)模序列數(shù)據(jù)質(zhì)量評(píng)價(jià)問題，本文利用Spark框架，考慮概率后綴樹和馬爾科夫鏈型[2]，提出了基于Spark的序列數(shù)據(jù)質(zhì)量評(píng)價(jià)算法STALK（sequential data quality evaluation with Spark），即根據(jù)給定的可靠序列數(shù)據(jù)集訓(xùn)練序列生成模型，并用其對(duì)查詢序列進(jìn)行質(zhì)量評(píng)價(jià)。

為實(shí)現(xiàn)基于Spark框架的大規(guī)模序列數(shù)據(jù)質(zhì)量評(píng)價(jià)，本文在文獻(xiàn)[2]工作基礎(chǔ)上需要克服以下挑戰(zhàn)：（1）針對(duì)Spark集群計(jì)算的特點(diǎn)，分析選用合適的序列數(shù)據(jù)生成模型的學(xué)習(xí)策略對(duì)提高算法執(zhí)行效率至關(guān)重要；（2）為提高Spark集群中各計(jì)算節(jié)點(diǎn)的效率，設(shè)計(jì)有效的剪枝策略是實(shí)現(xiàn)并行建立概率后綴樹的關(guān)鍵；（3）設(shè)計(jì)適合Spark架構(gòu)的高效數(shù)據(jù)分發(fā)和共享策略是實(shí)現(xiàn)對(duì)查詢序列的快速質(zhì)量評(píng)價(jià)的基礎(chǔ)。

本文主要貢獻(xiàn)有：（1）提出了基于Spark的大規(guī)模序列數(shù)據(jù)質(zhì)量評(píng)價(jià)問題；（2）討論了Spark框架上生成概率后綴樹的方法，并設(shè)計(jì)了基于Spark的序列數(shù)據(jù)質(zhì)量評(píng)價(jià)算法STALK；（3）實(shí)驗(yàn)驗(yàn)證了STALK算法的有效性、執(zhí)行效率和可擴(kuò)展性。

本文組織結(jié)構(gòu)如下：第2章給出本文研究問題定義；第3章介紹相關(guān)工作；第4章講述基于Spark的序列數(shù)據(jù)質(zhì)量評(píng)價(jià)算法STALK；第5章通過實(shí)驗(yàn)驗(yàn)證STALK算法的有效性、執(zhí)行效率和可擴(kuò)展性；第6章總結(jié)本文工作，并對(duì)未來工作進(jìn)行展望。

2 問題定義

給定序列樣本集合D，定義Σ為D中序列元素的集合，|S|為D中序列樣本S的長度，S[k]表示序列S中第k(1≤k≤|S|)個(gè)元素。為便于表達(dá)，定義如下對(duì)序列S的操作：

Suf(S)為S的最大后綴，Suf(S)=S[2]S[3]…S[|S|]；

Pre(S)為S的最大前綴，Pre(S)=S[1]S[2]…S[|S|-1]；

Apd(S,e)表示在S末尾拼接元素e組成的新序列，即Apd(S,e)=S[1]S[2]…S[|S|]e。

給定序列S和S′，若存在正整數(shù)k1,k2,…,km滿足1≤k1是S′在S中的一個(gè)實(shí)例。特別地，若?m>1，有kmkm-1=1，則稱S′是S的連續(xù)子序列。

間隔約束γ是一個(gè)正整數(shù)域區(qū)間，記為γ=[γ.min,γ.max](0≤γ.min≤γ.max)。若序列S′在S上存在一個(gè)實(shí)例并且滿足?m>1，有km-km-1-1∈γ，那么稱S′匹配S，記為S′?γS。

例1給定序列S=abbaabaa，當(dāng)序列S′=abb，間隔約束γ=[0,1]，S′在S中的實(shí)例集合為{<1，2，3>，<1，2，6>，<1，3，6>}，其中存在實(shí)例<1，2，3>滿足2-1-1∈γ且3-2-1∈γ，因此S′?γS。

定義1（匹配度）給定序列S′、S，間隔約束γ,S′在S中滿足γ-匹配的實(shí)例集合稱為S′在S中的匹配集合，記為match(S′,S)。match(S′,S)={| 是S′在S中的一個(gè)實(shí)例且ki+1-ki-1∈γ(1

給定序列S′，序列樣本集合D，間隔約束γ，稱D中與S′滿足γ-匹配的序列樣本數(shù)占總樣本數(shù)的比例為S′在D的支持度，記為Sup(S′,D,γ)，如式（1）：

例2考慮表1中的序列樣本集合D，令γ=[0,1]。給定序列S′=ab，對(duì)序列S1有實(shí)例<1，2>、<1，3>、<4，6>、<5，6>、<5，7>使得S′?γS1，對(duì)序列S2有實(shí)例<1，2>、<1，3>、<4，5>、<6，7>使得S′?γS2，對(duì)序列S3有實(shí)例<1，2>、<3，4>、<3，5>使得S′?γS3。由于|D|=3，則Sup(S′,D,γ)=(1+1+1)/3=1.0。

Table 1 An example of a set of sequences表1 序列集合示例

定理1給定間隔約束γ，序列樣本集合D，序列模式S′和S，其中S′為S的連續(xù)子序列，那么Sup()≥Sup()≥0。

證明由于S′為S的連續(xù)子序列，那么給定樣本集合D，間隔約束γ，對(duì)于任意序列P(P∈D),S′?γP成立，但S?γP不一定成立，則|match(S′,P)|≥|match(S,P)|，根據(jù)式（1）可得：

假設(shè)序列樣本集合D中所有序列的生成服從分布?。對(duì)于查詢序列S，用L(S|?)表示S由?生成的可能性。

定義2（基于概率后綴樹的生成模型）給定記憶長度l，間隔約束γ和支持度閾值minSup。概率后綴樹中任一節(jié)點(diǎn)表示的序列模式S，若滿足如下條件，稱概率后綴樹為序列樣本集合D的生成模型：

條件1Sup(S,D,γ)≥minSup

條件2|S|≤l

給定樣本集合D，查詢序列S和質(zhì)量評(píng)價(jià)閾值θ，本文目標(biāo)在于訓(xùn)練得到滿足定義2的生成模型?，通過計(jì)算S由?生成可能性L(S|?)與S由隨機(jī)模型生成可能性的比值，進(jìn)行數(shù)據(jù)質(zhì)量評(píng)價(jià)。具體地，若比值大于θ則認(rèn)為S的質(zhì)量可接受。

表2給出了本文所使用的重要符號(hào)及其含義。

Table 2 Summary of notations表2 符號(hào)匯總

3 相關(guān)工作

在數(shù)據(jù)挖掘領(lǐng)域，數(shù)據(jù)質(zhì)量直接影響挖掘效果和意義，數(shù)據(jù)質(zhì)量評(píng)價(jià)算法可以對(duì)待分析的數(shù)據(jù)進(jìn)行質(zhì)量評(píng)估，因而受到廣泛關(guān)注。文獻(xiàn)[5]對(duì)非結(jié)構(gòu)化數(shù)據(jù)進(jìn)行質(zhì)量評(píng)價(jià)，對(duì)受控詞匯定義了26種數(shù)據(jù)質(zhì)量問題，并利用函數(shù)對(duì)數(shù)據(jù)質(zhì)量進(jìn)行衡量，發(fā)現(xiàn)潛在的數(shù)據(jù)質(zhì)量問題。除此之外，大多數(shù)學(xué)者對(duì)結(jié)構(gòu)化數(shù)據(jù)的數(shù)據(jù)質(zhì)量進(jìn)行了研究[6]。文獻(xiàn)[7]針對(duì)結(jié)構(gòu)化數(shù)據(jù)進(jìn)行質(zhì)量評(píng)價(jià)，利用給定的用戶信息對(duì)系統(tǒng)數(shù)據(jù)質(zhì)量進(jìn)行改進(jìn)，提高了查詢結(jié)果的質(zhì)量。文獻(xiàn)[8]研究了在實(shí)際信息系統(tǒng)中適用的綜合性數(shù)據(jù)質(zhì)量評(píng)估方法，并提出了基于性質(zhì)的數(shù)據(jù)質(zhì)量評(píng)估框架。文獻(xiàn)[9]提出了函數(shù)依賴于條件約束的數(shù)據(jù)修復(fù)方法。與傳統(tǒng)統(tǒng)計(jì)方法相比，本文考慮序列出現(xiàn)的先后順序，建立序列數(shù)據(jù)的生成模型，進(jìn)而利用生成模型對(duì)查詢序列進(jìn)行質(zhì)量評(píng)價(jià)。

序列數(shù)據(jù)中各元素之間的位置，蘊(yùn)含著豐富的信息，各元素出現(xiàn)的先后位置信息存在某種潛在的規(guī)律或者滿足某個(gè)特殊的分布。針對(duì)序列數(shù)據(jù)具有短暫記憶性特征，文獻(xiàn)[3]提出記憶長度概念，即：給定序列S=S[1]S[2]…S[|S|]，P(S[|S|]|S[1]S[2]…S[|S|-1])表示子序列S[1]S[2]…S[|S|-1]之后出現(xiàn)S[|S|]的概率，若存在記憶長度l，P(S[|S|]|S[1]S[2]…S[|S|-1])≈P(S[|S|]|S[|S|-l]S[|S|-l+1]…S[|S|-1])(1≤l≤n-1)。為了直接使用高階馬爾科夫鏈模型，文獻(xiàn)[3]提出利用概率后綴樹來模擬變化的記憶長度。文獻(xiàn)[10]針對(duì)鐵路數(shù)據(jù)利用概率后綴樹進(jìn)行離群點(diǎn)檢測(cè)。文獻(xiàn)[11]利用概率后綴樹與支持向量機(jī)對(duì)數(shù)據(jù)進(jìn)行分類。

為有效提高序列模式的適應(yīng)性，挖掘序列模式時(shí)通常會(huì)考慮間隔約束。文獻(xiàn)[12]提出了產(chǎn)生序列前綴和后綴的PrefixSpan算法。文獻(xiàn)[13]在PrefixSpan算法的基礎(chǔ)上，提出了帶間隔約束的序列模式挖掘算法。文獻(xiàn)[14]設(shè)計(jì)了利用帶間隔約束的序列模式評(píng)價(jià)軟件缺陷特征的方法。

Spark框架于2011年提出，現(xiàn)已成為流行的并行框架[15]。文獻(xiàn)[16]對(duì)Spark上交互式數(shù)據(jù)進(jìn)行快速處理和分析，并對(duì)Spark和Hadoop性能進(jìn)行比較。文獻(xiàn)[17-18]利用Spark進(jìn)行大規(guī)模頻繁項(xiàng)集的并行挖掘分析。文獻(xiàn)[19]利用Spark框架對(duì)海量天文圖像進(jìn)行快速處理。文獻(xiàn)[20]利用Spark SQL研究計(jì)算過程中的內(nèi)存崩潰問題。文獻(xiàn)[21]利用Spark對(duì)藥物不良反應(yīng)數(shù)據(jù)庫進(jìn)行并行查重。

4 STALK算法設(shè)計(jì)

給定序列樣本集合D，查詢序列S，記憶長度l，間隔約束γ和最小支持度閾值minSup，本文提出基于Spark的序列數(shù)據(jù)質(zhì)量評(píng)價(jià)算法STALK。

圖1給出了STALK算法的流程?？梢钥闯?，STALK算法主要步驟包括：步驟①，啟動(dòng)STALK算法，并從HDFS（Hadoop distributed file system）中載入數(shù)據(jù)到Spark集群，完成數(shù)據(jù)預(yù)處理；步驟②，在Spark框架下，根據(jù)定義2訓(xùn)練生成模型?，當(dāng)候選序列模式的長度大于l時(shí)執(zhí)行步驟④，否則執(zhí)行步驟③；步驟③，調(diào)用Spark的工作集群，計(jì)算每個(gè)候選序列模式的匹配度，并計(jì)算評(píng)價(jià)其支持度；步驟④，計(jì)算S由?生成可能性L(S|?)與S由隨機(jī)模型生成可能性的比值，評(píng)價(jià)數(shù)據(jù)質(zhì)量。

Fig.1 Flowchart of STALK圖1 STALK算法流程

4.1 STALK算法生成概率后綴樹

用S表示概率后綴樹中當(dāng)前訪問的節(jié)點(diǎn)表示的序列模式，S′為包含S為連續(xù)子序列的序列模式。若S的支持度滿足?的生成條件1，則將其節(jié)點(diǎn)保存至概率后綴樹中；否則，根據(jù)定理1，S′的支持度Sup()

剪枝條件1（最小支持度剪枝）給定樣本集合D，間隔約束γ，若序列S的支持度Sup()

記憶長度l限定了概率后綴樹的深度，即后綴樹中節(jié)點(diǎn)表示的序列模式的長度。如圖2所示，給定l=3,則后綴樹中各節(jié)點(diǎn)表示的序列S的長度|S|≤3。由此可得剪枝條件2[2]。

剪枝條件2（記憶長度剪枝）若概率后綴樹中節(jié)點(diǎn)表示的序列模式的長度大于記憶長度l，則將該節(jié)點(diǎn)及其子節(jié)點(diǎn)從概率后綴樹中移除。

在生成概率后綴樹時(shí)，Spark集群計(jì)算節(jié)點(diǎn)的任務(wù)是計(jì)算概率后綴樹中每個(gè)節(jié)點(diǎn)表示的候選序列模式的匹配度，并根據(jù)剪枝條件1、剪枝條件2進(jìn)行剪枝，最終建立滿足定義2的概率后綴樹。根據(jù)定義2和剪枝條件1、剪枝條件2，算法1描述了建立概率后綴樹的偽代碼。

算法1建立概率后綴樹Build(D,Σ,γ,l,minSup)

輸入：數(shù)據(jù)質(zhì)量可靠的序列樣本集合D，元素集合Σ，間隔約束γ，最小支持度閾值minSup，記憶長度l

輸出：概率后綴樹PST

1.PST←?;Set←?;Ck←?;//初始化PST,Set,Ck

2.Ck←Σ;//生成第一層候選模式集合

3.k=1;//k描述當(dāng)前后綴樹的深度

4.While(k≤l)do

5.Set←map(getMatch(Ck,γ));//匹配候選模式

6. 移除Set中不滿足剪枝條件1的候選序列模式；

7. ForS∈Set.collect()do//更新概率后綴樹

8.PST←PST∪{S};

9. EndFor

10.Ck←Generate(Ck);//算法2

11.k←k+1;

12.EndWhile

13.ReturnPST;

在算法1中，PST表示概率后綴樹，Set表示候選模式集合，Ck表示底層候選模式集合。首先通過步驟2由Σ生成第一層候選模式集合；步驟3用k來描述樹的深度，即候選序列模式的最大長度；步驟4~12將滿足剪枝條件1的候選模式保存至PST中，最終生成滿足定義2的概率后綴樹。其中，get-Match函數(shù)計(jì)算候選序列模式的轉(zhuǎn)移概率，Generate函數(shù)生成下一層概率后綴樹的候選模式。

利用長度為l的候選模式生成長度為l+1的候選模式時(shí)，容易想到采用遍歷集合枚舉樹的方式。傳統(tǒng)的完全遍歷枚舉樹方法是把每個(gè)候選模式與候選元素集合逐一匹配，這樣會(huì)造成不必要的計(jì)算開銷。而深度優(yōu)先遍歷集合枚舉樹[22]會(huì)一次生成候選模式S及其所有包含S為連續(xù)子序列的候選模式，但利用剪枝條件移除不符合條件的候選模式的同時(shí)，Spark集群會(huì)計(jì)算所有候選序列模式的匹配度，這樣會(huì)造成不必要的計(jì)算開銷，浪費(fèi)計(jì)算資源。

廣度優(yōu)先遍歷策略在生成長度為l的候選序列模式之前會(huì)生成所有長度小于l的候選模式，Spark集群可以并行處理所有長度為l的候選序列模式，這樣可以提高算法效率。因此，采用廣度優(yōu)先遍歷集合枚舉樹方式來生成PST中所有候選模式。算法2給出了STALK生成候選模式的算法偽代碼。

算法2候選模式生成Generate(Ck)

輸入：概率后綴樹上第k層的候選序列模式集合Ck

輸出：概率后綴樹上第k+1層的候選序列模式集合Ck+1

1.Ck+1←?;//初始化Ck+1

2.For eachP∈Ckand eachQ∈Ckdo

3. IfSuf(P)=Pre(Q)then

4.Ck+1←Ck+1∪Apd(P,Q[|Q|]);

5. EndIf

6.EndFor

7.ReturnCk+1;

算法2生成候選模式的過程類似于廣度優(yōu)先遍歷集合枚舉樹。即對(duì)兩個(gè)長度為l且其后綴、前綴相同的模式，通過拼接操作生成長度為l+1的候選模式。例如，對(duì)ba和ab，由于Suf(ba)=Pre(ab),則生成新的候選模式bab。

4.2 序列轉(zhuǎn)移概率并行計(jì)算

通過算法1得到了概率后綴樹PST，概率后綴樹中任意節(jié)點(diǎn)的轉(zhuǎn)移向量為{P1,P2,…,P|Σ|},Pr(1≤r≤|Σ|)表示當(dāng)前節(jié)點(diǎn)轉(zhuǎn)移到下一子節(jié)點(diǎn)的概率，其中轉(zhuǎn)移概率P計(jì)算如下[2]：

式（2）中分子表示元素e和序列S組成的新序列在D中的匹配度之和，分母表示元素集合Σ中的所有元素和序列S分別組成的序列在D中的匹配度之和。為避免概率為0，公式進(jìn)行拉普拉斯平滑處理。

例3在表1中，序列aa、ba滿足的間隔約束γ=[0,1]的實(shí)例個(gè)數(shù)分別為5和11，則序列a轉(zhuǎn)移到序列aa的概率為(5+1)/(11+5+2)≈0.33。

根據(jù)表1中的樣本集合，在滿足l=2,γ=[0,1]，minSup=0.85的條件下生成概率后綴樹，如圖2所示。節(jié)點(diǎn)aaa的支持度小于minSup，根據(jù)剪枝條件1，aaa及其子節(jié)點(diǎn)從后綴樹中移除。根據(jù)式（2），可以得到由后綴樹中每一個(gè)節(jié)點(diǎn)轉(zhuǎn)移至子節(jié)點(diǎn)的概率。算法3給出圖2中轉(zhuǎn)移概率的計(jì)算方法。

Fig.2 Probability suffix tree generated by Table 1圖2 根據(jù)表1序列建立的概率后綴樹

算法3PST上節(jié)點(diǎn)的轉(zhuǎn)移概率計(jì)算getMatch (S′,γ)

輸入：序列S′，間隔約束γ

輸出：S′及其轉(zhuǎn)移概率P

1.num←0;//num用來保存S′在樣本序列上的匹配度

2.sum←0;//sum用來保存S′在D中的匹配度

3.For each sequenceS∈Ddo

4. IfS′?γSthen

5. 利用Spark集群計(jì)算S′在S的匹配度;

6. EndIf

7.EndFor

8.(S′,sum)←reduceByKey(S′,num);//S′在D中匹配度

9.(S′,P)←map(S′,sum);//計(jì)算S′的轉(zhuǎn)移概率

10.Return(S′,P);

觀察算法3，步驟3~步驟7利用Spark集群計(jì)算S′在每個(gè)序列樣本上的匹配度；步驟8利用reduce-ByKey操作對(duì)S′在序列樣本上的匹配度相加，最終得到S′在原始樣本集合D的匹配度；步驟9進(jìn)行map操作得到S′在D上的轉(zhuǎn)移概率。

STALK算法中序列轉(zhuǎn)移概率計(jì)算過程（即算法1中步驟5~11）如圖3所示。包括3個(gè)步驟：步驟①，Spark集群利用textfile操作載入序列樣本集，進(jìn)行數(shù)據(jù)預(yù)處理；步驟②，利用Spark中map操作對(duì)序列樣本進(jìn)行候選模式匹配，并通過flatMap、reduceByKey和map操作生成候選序列模式及其轉(zhuǎn)移概率；步驟③，通過collect操作生成該層滿足剪枝條件1、剪枝條件2的候選模式集合，最終將序列模式及其轉(zhuǎn)移概率保存至概率后綴樹中。

Fig.3 Transition probability prcoss in STALK圖3 STALK中轉(zhuǎn)移概率計(jì)算過程

4.3 查詢序列的數(shù)據(jù)質(zhì)量估計(jì)方法

通過得到的訓(xùn)練模型?，給定序列S=S[1]S[2]…S[|S|]，用L(S|?)來衡量生成S的可能性。由貝葉斯后驗(yàn)概率方法得L(S|?)=P(S[1])P(S[2]|S[1])…P(S[|S|]|S[1]S[2]…S[|S|-1])。根據(jù)記憶長度l，由馬爾科夫鏈模型可知L(S|?)≈P(S[1]) P(S[2]|S[1])…P(S[l+1]|S[1]S[2]…S[l])…P(S[|S|]|S[|S|-l]S[|S|-l+1]…S[|S|-1])。

例4若查詢序列S=abba，計(jì)算圖2中表示的概率后綴樹生成S的概率。由貝葉斯后驗(yàn)概率可知L(S|?)=P(a)P(b|a)P(b|ab)P(a|abb)≈P(a)P(b|a)P(b|ab) P(a|bb)≈0.46×0.67×0.58×0.61≈0.109。

假設(shè)序列中各元素相互獨(dú)立，則生成S的概率為計(jì)算如下所示：

用L(S|?)與R(S)的比值Score來衡量序列的質(zhì)量可接受度[2]。給定閾值θ，若Score≥θ，則序列S的質(zhì)量可接受。

例5考慮例4中S=abba，θ=1.0。根據(jù)式（4），R(S)=P(a)P(b)P(b)P(a)=0.46×0.54×0.54×0.46≈0.062。由例4，L(S|?)≈0.109。Score=0.109/0.062≈1.758>θ。因此，序列S的質(zhì)量可接受。

4.4 Spark下的數(shù)據(jù)分發(fā)和共享策略

為適應(yīng)基于內(nèi)存的Spark框架，STALK算法在內(nèi)存中存儲(chǔ)概率后綴樹，即各候選序列模式及其轉(zhuǎn)移概率，且主節(jié)點(diǎn)每次任務(wù)分發(fā)時(shí)將概率后綴樹底層的所有節(jié)點(diǎn)分發(fā)出去，降低了通信開銷。

在建立概率后綴樹過程中，每個(gè)計(jì)算節(jié)點(diǎn)分片計(jì)算新的序列模式匹配度，有兩種剪枝方案：

方案1計(jì)算節(jié)點(diǎn)剪枝。

方案2主節(jié)點(diǎn)剪枝。

根據(jù)數(shù)據(jù)規(guī)模大小和并行操作的特性，STALK算法選用方案1，即每個(gè)計(jì)算節(jié)點(diǎn)上進(jìn)行剪枝操作，這樣可以減低主節(jié)點(diǎn)對(duì)數(shù)據(jù)集的操作耗時(shí)。在數(shù)據(jù)分發(fā)時(shí)，分片數(shù)目需大于CPU內(nèi)核數(shù)，選取線程數(shù)目為分片數(shù)目，以提高CPU使用率。本文實(shí)驗(yàn)采用8個(gè)計(jì)算節(jié)點(diǎn)，分成64片。此外，使用廣播變量和累加器（Spark框架的兩種共享變量）降低通信開銷，本文將γ、minSup、l作為廣播變量，概率后綴樹作為累加器。

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

實(shí)驗(yàn)算法由Python語言實(shí)現(xiàn)，實(shí)驗(yàn)節(jié)點(diǎn)配置為Intel Core i7，16 GB內(nèi)存，Ubuntu14.0.4操作系統(tǒng)，Spark1.6.0版本。本文采用UCI機(jī)器學(xué)習(xí)數(shù)據(jù)集[23]中基因序列數(shù)據(jù)集SpliceEI、SpliceIE、SpliceN來驗(yàn)證STALK算法的有效性、執(zhí)行效率和可擴(kuò)展性；采用SpliceIE、Activity、Location數(shù)據(jù)集[24-25]和蛋白質(zhì)ABC-2族的APF01061數(shù)據(jù)集驗(yàn)證序列元素集合對(duì)STALK執(zhí)行效率的影響。實(shí)驗(yàn)數(shù)據(jù)集如表3所示。算法參數(shù)默認(rèn)值為l=2,γ=[0,1],minSup=0.85，計(jì)算節(jié)點(diǎn)數(shù)為8。

Table 3 Characteristics of experimental data sets表3 實(shí)驗(yàn)數(shù)據(jù)集特征

5.1 算法有效性驗(yàn)證

令|D-|表示數(shù)據(jù)質(zhì)量可接受的序列樣本條數(shù)數(shù)；|D+|表示數(shù)據(jù)質(zhì)量可接受的序列樣本條數(shù)；|SD-|表示數(shù)據(jù)質(zhì)量不可接受且被STALK正確判斷的序列條數(shù)；|SD+|表示數(shù)據(jù)質(zhì)量可接受且被STALK正確判斷的序列條數(shù)。定義查準(zhǔn)率Acc=(|SD-|+|SD+|)/(|D-|+|D+|)，查全率Rec=|SD-|/|D-|。為驗(yàn)證STALK算法的有效性，用STALK算法分別生成數(shù)據(jù)集SpliceEI、SpliceIE、SpliceN的訓(xùn)練模型。然后對(duì)它們用以下策略生成2×103條測(cè)試樣本。

策略1對(duì)長度相同的候選模式按照轉(zhuǎn)移概率從大到小排序，根據(jù)轉(zhuǎn)移概率的值將[0,1]分為不同的小區(qū)間；然后利用Python的random函數(shù)，生成隨機(jī)數(shù)r(r∈[0,1])，根據(jù)r的大小匹配各個(gè)區(qū)間，匹配成功則轉(zhuǎn)移至該節(jié)點(diǎn)；最終生成1×103條質(zhì)量可接受的SpliceEID+、SpliceIED+、SpliceND+集合。

策略2在與策略1相同的生成條件下，利用隨機(jī)數(shù)r匹配區(qū)間，與策略1不同的是，匹配成功則轉(zhuǎn)移至對(duì)應(yīng)小區(qū)間的節(jié)點(diǎn)，生成1×103條質(zhì)量不可接受的SpliceEID-、SpliceIED-、SpliceND-集合。

用SpliceEID+∪SpliceEID-，SpliceIED+∪SpliceIED-，SpliceND+∪SpliceND-分別組成測(cè)試數(shù)據(jù)SpliceEID、SpliceIED、SpliceND。為驗(yàn)證STALK算法能否有效檢測(cè)到質(zhì)量不可接受的序列樣本，分別用SpliceEI、SpliceIE、SpliceN作為訓(xùn)練集，利用STALK算法生成模型，對(duì)SpliceEID、SpliceIED、SpliceND進(jìn)行質(zhì)量評(píng)價(jià)。表4給出θ改變時(shí)STALK算法在各數(shù)據(jù)集上的數(shù)據(jù)質(zhì)量評(píng)價(jià)結(jié)果，觀察得，STALK算法能有效查找出數(shù)據(jù)質(zhì)量不可接受的序列。

Table 4 Results of STALK on test data sets表4 STALK算法對(duì)測(cè)試數(shù)據(jù)集的結(jié)果

5.2 算法執(zhí)行效率驗(yàn)證

為驗(yàn)證STALK算法的執(zhí)行效率，對(duì)比SQEPST算法[2]和STALK算法的執(zhí)行時(shí)間。本文按照策略1對(duì)SpliceIE樣本數(shù)據(jù)集合成2×104、4×104、6×104、8× 104條數(shù)據(jù)建立生成模型?的執(zhí)行時(shí)間，如圖4所示。

Fig.4 Comparison of runtime between STALK and SQEPST圖4 STALK與SQEPST算法的運(yùn)行時(shí)間比較

圖4中，隨著數(shù)據(jù)集規(guī)模的增大，STALK算法和SQEPST算法的執(zhí)行時(shí)間逐漸增加，然而STALK算法的執(zhí)行效率遠(yuǎn)優(yōu)于SQEPST算法。特別是，SQEPST算法在數(shù)據(jù)規(guī)模為4×104條時(shí)內(nèi)存溢出。分析原因如下：隨著數(shù)據(jù)集規(guī)模增大，候選序列模式集合增大，SQEPST算法匹配度計(jì)算開銷增加；此外，深度優(yōu)先遍歷集合枚舉樹不能及時(shí)剪枝，增加了計(jì)算資源開銷。

為分析間隔約束γ、記憶長度l對(duì)建立生成模型時(shí)間的影響，按照策略1對(duì)3個(gè)基因序列數(shù)據(jù)集合成5×105條數(shù)據(jù)。觀察圖5~圖7中（a）圖，隨著γ的增大，算法執(zhí)行時(shí)間增大。分析原因如下：γ決定候選模式的匹配集合長度，當(dāng)γ增大時(shí)，匹配集合長度增加，因此算法執(zhí)行時(shí)間增加。觀察圖5~圖7中（b）圖，隨著l的增大，算法執(zhí)行時(shí)間增大。分析原因如下：記憶長度決定概率后綴樹的深度，l增大時(shí)，概率后綴樹的深度增大，因此算法執(zhí)行時(shí)間增加。

5.3 算法可擴(kuò)展性驗(yàn)證

為驗(yàn)證STALK算法的可擴(kuò)展性，按照策略1對(duì)3個(gè)基因序列數(shù)據(jù)集合成5×105條數(shù)據(jù)，分析計(jì)算節(jié)點(diǎn)數(shù)目對(duì)建立生成模型時(shí)間的影響。觀察圖5~圖7中（c）圖，隨著節(jié)點(diǎn)數(shù)目增加，STALK算法執(zhí)行時(shí)間顯著降低。原因?yàn)榻o定數(shù)據(jù)條數(shù)，主節(jié)點(diǎn)根據(jù)計(jì)算節(jié)點(diǎn)數(shù)目分發(fā)任務(wù)。因此增加節(jié)點(diǎn)數(shù)，各節(jié)點(diǎn)的數(shù)據(jù)分片會(huì)減少，相應(yīng)各計(jì)算節(jié)點(diǎn)的執(zhí)行時(shí)間減小，總時(shí)間減小。為驗(yàn)證數(shù)據(jù)規(guī)模對(duì)算法可擴(kuò)展性的影響，按照策略1分別將3個(gè)基因數(shù)據(jù)集的規(guī)模合成為2× 106、4×106、6×106、8×106、10×106。觀察圖5~圖7中（d）圖，隨著數(shù)據(jù)規(guī)模增大，算法執(zhí)行時(shí)間增加。原因?yàn)楫?dāng)數(shù)據(jù)規(guī)模增大時(shí)，算法需要在更多序列樣本上計(jì)算候選模式的匹配度和支持度，因此執(zhí)行時(shí)間增長。

Fig.5 Runtime of STALK on synthetic data set by SpliceEI圖5 在SpliceEI合成數(shù)據(jù)集上STALK算法的運(yùn)行時(shí)間

Fig.6 Runtime of STALK on synthetic data set SpliceIE圖6 在SpliceIE合成數(shù)據(jù)集上STALK算法的運(yùn)行時(shí)間

Fig.7 Runtime of STALK on synthetic data set SpliceN圖7 在SpliceN合成數(shù)據(jù)集上STALK算法的運(yùn)行時(shí)間

5.4 |Σ|對(duì)算法執(zhí)行效率的影響

在建立概率后綴樹過程中，元素個(gè)數(shù)決定每一層節(jié)點(diǎn)個(gè)數(shù)，觀察圖5~圖7，3個(gè)數(shù)據(jù)集的|Σ|都為4，故相同條件下算法運(yùn)行時(shí)間相似。為驗(yàn)證|Σ|對(duì)算法執(zhí)行時(shí)間的影響，按照策略1將SpliceIE、Activity、Location、APF01061各自生成5×105條合成數(shù)據(jù)集。從圖8中可得，增大|Σ|，算法執(zhí)行時(shí)間增加。從圖8（b）看出，增大minSup會(huì)縮小樣本集合中符合條件的序列篩選范圍，因此執(zhí)行時(shí)間降低。

Fig.8 Runtime of STALK on data sets with different|Σ|圖8 STALK算法在含有不同|Σ|的數(shù)據(jù)集上的運(yùn)行時(shí)間

6 結(jié)束語

數(shù)據(jù)質(zhì)量評(píng)價(jià)的傳統(tǒng)方式是定性分析，缺少利用生成模型對(duì)大規(guī)模數(shù)據(jù)質(zhì)量的分析。針對(duì)該問題，本文提出了基于Spark的序列數(shù)據(jù)質(zhì)量評(píng)價(jià)算法STALK。STALK算法利用質(zhì)量可靠的序列樣本集合高效建立生成模型，并根據(jù)生成模型快速評(píng)價(jià)查詢數(shù)據(jù)質(zhì)量，并且采用改進(jìn)的剪枝策略優(yōu)化了算法在Spark平臺(tái)的執(zhí)行效率。通過大規(guī)模序列數(shù)據(jù)集驗(yàn)證了算法的有效性、執(zhí)行效率和可擴(kuò)展性。

下一步，將增加Spark集群中計(jì)算節(jié)點(diǎn)數(shù)量，使STALK適用于更大規(guī)模的數(shù)據(jù)分析。同時(shí)，考慮更多實(shí)際應(yīng)用中對(duì)STALK算法有效性、執(zhí)行效率和可擴(kuò)展性的驗(yàn)證；設(shè)計(jì)STALK算法在不同領(lǐng)域的應(yīng)用，嘗試將其運(yùn)用到理財(cái)投資中，分析個(gè)人理財(cái)習(xí)慣并對(duì)理財(cái)產(chǎn)品進(jìn)行推薦，利用序列質(zhì)量評(píng)價(jià)進(jìn)行DNA異常序列檢測(cè)。

References：

[1]Guo Zhimao,Zhou Aoying.Research on data quality and data cleaning:a survey[J].Journal of Software,2002,13 (11):2076-2082.

[2]Wang Huifeng,Duan Lei,Hu Bin,et al.Design of evaluating sequential data quality with gap constraint[J].Journal of Frontiers of Computer Science and Technology,2015,9 (10):1180-1194.

[3]Ron D,Singer Y,Tishby N.The power of amnesia:learning probabilistic automata with variable memory length[J].Machine Learning,1996,25(2/3):117-149.

[4]Zaharia M,Chowdhury M,Franklin M J,et al.Spark:cluster computing with working sets[C]//Proceedings of the 2nd USENIX Conference on Hot Topics in Cloud Computing, Boston,USA,Jun 22-25,2010.Berkeley,USA:USENIX Association,2010:1765-1773.

[5]Suominen O,Mader C.Assessing and improving the quality of SKOS vocabularies[J].Journal on Data Semantics,2014, 3(1):47-73.

[6]Carlo B,Daniele B,Federico C,et al.A data quality methodology for heterogeneous data[J].International Journal of Database Management Systems,2011,3(1):60-79.

[7]Meng Xiao,Wang Hongzhi,Gao Hong,et al.bibEOS:a social system of bibliography retrieval and management[J]. Journal of Frontiers of Computer Science and Technology, 2010,4(1):54-63.

[8]Ding Xiaoou,Wang Hongzhi,Zhang Xiaoying,et al.Association relationships study of multi-dimensional data quality [J].Journal of Software,2016,27(7):1626-1644.

[9]Jin Cheqing,Liu Huiping,Zhou Aoying.Functional dependency and conditional constraint based data repair[J].Journal of Software,2016,27(7):1671-1684.

[10]Rabatel J,Bringay S,Poncelet P.Anomaly detection in monitoring sensor data for preventive maintenance[J].Expert Systems withApplications,2011,38(6):7003-7015.

[11]Lu Kefa,Cao Qing,Thomason M.Bugs or anomalies?sequence mining based debugging in wireless sensor networks [C]//Proceedings of the 9th International Conference on Mobile Ad-Hoc and Sensor Systems,Las Vegas,USA,Oct 8-11,2012.Washington:IEEE Computer Society,2012:463-467.

[12]Pei Jian,Han Jiawei,Mortazavi-Asl B,et al.PrefixSpan: mining sequential patterns efficiently by prefix-projected pattern growth[C]//Proceedings of the 17th International Conference on Data Engineering,Heidelberg,Germany, Apr 2-6,2001.Washington:IEEE Computer Society,2001: 215-224.

[13]Antunes C,Oliveira A L.Generalization of pattern-growth methods for sequential pattern mining with gap constraints [C]//LNCS 2734:Proceedings of the 3rd International Conference on Machine Learning and Data mining in Pattern Recognition,Leipzig,Germany,Jul 5-7,2003.Berlin,Heidelberg:Springer,2003:239-251.

[14]Sun Pei,Chawla S,Arunasalam B.Mining for outliers in sequential databases[C]//Proceedings of the 6th SIAM International Conference on Data Mining,Bethesda,USA,Apr 20-22,2006.Philadelphia,USA:SDM,2006:94-106.

[15]Zaharia M,Chowdhury M,Das M,et al.Resilient distributed datasets:a fault-tolerant abstraction for in-memory cluster computing[C]//Proceedings of the 9th USENIX Conference on Networked Systems Design and Implementation,San Jose, USA,Apr 25-27,2012.Berkeley,USA:USENIX Association,2012:141-146.

[16]Zaharia M,Chowdhury M,Das T,et al.Fast and interactive analytics over Hadoop data with Spark[J].USENIX Login, 2012,37(4):45-51.

[17]Qiu Hongjian,Gu Rong,Yuan Chunfeng,et al.YAFIM:a parallel frequent itemset mining algorithm with Spark[C]// Proceedings of the 2014 IEEE International Parallel&Distributed Processing Symposium Workshops,Phoenix,USA, May 19-23,2014.Washington:IEEE Computer Society,2014: 1664-1671.

[18]Zhang Feng,Liu Min,Gui Feng,et al.A distributed frequent itemset mining algorithm using Spark for big data analytics[J].Cluster Computing,2015,18(4):1493-1501.

[19]Zhang Zhao,Barbary K,Nothaft F A,et al.Scientific computing meets big data technology:an astronomy use case [C]//Proceedings of the 2015 International Conference on Big Data,Santa Clara,USA,Oct 29-Nov 1,2015.Piscataway,USA:IEEE,2015:918-927.

[20]Rao P S,Porter G.Is memory disaggregation feasible?a case study with Spark SQL[C]//Proceedings of the 2016 Symposium on Architectures for Networking and Communications Systems,Santa Clara,USA,Mar 17-18,2016. New York:ACM,2016:75-80.

[21]Wang Chen,Karimi S.Parallel duplicate detection in adverse drug reaction databases with Spark[C]//Proceedings of the 19th International Conference on Extending Database Technology,Bordeaux,France,Mar 15-18,2016:551-562.

[22]Wang Xianming,Duan Lei,Dong Guozhu,et al.Efficient mining of density-aware distinguishing sequential patterns with gap constraints[C]//LNCS 8421:Proceedings of the 19th International Conference on Database Systems for Ad-vanced Applications,Bali,Indonesia,Apr 21-24,2014.Berlin,Heidelberg:Springer,2014:372-387.

[23]Lichman M.UCI machine learning repository[EB/OL].Irvine,CA:University of California,School of Information and Computer Science(2013)[2015-03-20].http://archive. ics.uci.edu/ml.

[24]Ordó?ez F J,Toledo P,Sanchis A.Activity recognition using hybrid generative/discriminative models on home environments using binary sensors[J].Sensors,2013,13(5):5460-5477.

[25]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.

附中文參考文獻(xiàn):

[1]郭志懋,周傲英.數(shù)據(jù)質(zhì)量和數(shù)據(jù)清洗研究綜述[J].軟件學(xué)報(bào),2002,13(11):2076-2082.

[2]王慧鋒,段磊,胡斌,等.帶間隔約束的序列數(shù)據(jù)質(zhì)量評(píng)價(jià)算法設(shè)計(jì)[J].計(jì)算機(jī)科學(xué)與探索,2015,9(10):1180-1194.

[7]孟嘯,王宏志,高宏,等.bibEOS:一個(gè)高質(zhì)量的社會(huì)化文獻(xiàn)檢索與管理系統(tǒng)[J].計(jì)算機(jī)科學(xué)與探索,2010,4(1):54-63.

[8]丁小歐,王宏志,張笑影,等.數(shù)據(jù)質(zhì)量多種性質(zhì)的關(guān)聯(lián)關(guān)系研究[J].軟件學(xué)報(bào),2016,27(7):1626-1644.

[9]金澈清,劉輝平,周傲英.基于函數(shù)依賴與條件約束的數(shù)據(jù)修復(fù)方法[J].軟件學(xué)報(bào),2016,27(7):1671-1684.

[25]楊皓,段磊,胡斌,等.帶間隔約束的Top-k對(duì)比序列模式挖掘[J].軟件學(xué)報(bào),2015,26(11):2994-3009.

HAN Chao was born in 1994.He is an M.S.candidate at School of Computer Science,Sichuan University,and the student member of CCF.His research interests include data mining and knowledge engineering.

韓超（1994—），男，甘肅慶陽人，四川大學(xué)計(jì)算機(jī)學(xué)院碩士研究生，CCF學(xué)生會(huì)員，主要研究領(lǐng)域?yàn)閿?shù)據(jù)挖掘，知識(shí)工程。

段磊（1981—），男，四川成都人，2008年于四川大學(xué)計(jì)算機(jī)應(yīng)用技術(shù)專業(yè)獲得博士學(xué)位，現(xiàn)為四川大學(xué)副教授、碩士生導(dǎo)師，CCF高級(jí)會(huì)員，主要研究領(lǐng)域?yàn)閿?shù)據(jù)挖掘，健康信息學(xué)，進(jìn)化計(jì)算。

DENG Song was born in 1980.His research interests include distributed data mining,smart grid information security and physical fusion system of electric power information.

鄧松（1980—），男，安徽合肥人，博士，高級(jí)工程師，主要研究領(lǐng)域?yàn)榉植际綌?shù)據(jù)挖掘，智能電網(wǎng)信息安全，電力信息物理融合系統(tǒng)。

WANG Huifeng was born in 1988.He received the M.S.degree in computer science from Sichuan University in 2016.His research interests include data mining and knowledge engineering.

王慧鋒（1988—），男，河南南陽人，2016年于四川大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)獲得碩士學(xué)位，主要研究領(lǐng)域?yàn)閿?shù)據(jù)挖掘，知識(shí)工程。

TANG Changjie was born in 1946.He is a professor and Ph.D.supervisor at Sichuan University,and the distinguishing member of CCF.His research interests include database technique and data mining.

唐常杰（1946—），男，重慶人，四川大學(xué)教授、博士生導(dǎo)師，CCF杰出會(huì)員，主要研究領(lǐng)域?yàn)閿?shù)據(jù)庫技術(shù)，數(shù)據(jù)挖掘。

Evaluation of Sequential Data Quality Using Spark*

HAN Chao1,DUAN Lei1,2+,DENG Song3,WANG Huifeng1,TANG Changjie1
1.School of Computer Science,Sichuan University,Chengdu 610065,China
2.West China School of Public Health,Sichuan University,Chengdu 610041,China
3.Institute ofAdvanced Technology,Nanjing University of Posts and Telecommunications,Nanjing 210003,China
+Corresponding author:E-mail:leiduan@scu.edu.cn

Sequential data are prevalent in many real world applications.The quality evaluation on sequential data, which attracts the attentions from both academic research and industry fields,is important and prerequisite for extracting knowledge from the sequential data.Recently,a method using the probabilistic suffix tree has been proposed for evaluating the sequential data quality.However,this method cannot deal with the large-scale data set.To break this limitation,this paper proposes a Spark-based algorithm,called STALK(sequential data quality evaluation with Spark),for evaluating the quality of large-scale sequential data.Moreover,this paper uses the novel pruning strategies to improve the efficiency of STALK.Specifically,on the Spark platform,the large-scale sequential data are efficiently used to generate model,and the data quality of query sequence can be evaluated according to the generated model rapidly.Experiments on real-world sequential data sets demonstrate that STALK is effective,efficient and scalable.

was born in 1981.He

the Ph.D.degree in computer science from Sichuan University in 2008. Now he is an associate professor and M.S.supervisor at Sichuan University,and the senior member of CCF.His research interests include data mining,health-informatics and evolutionary computation.

A

TP391

*The National Natural Science Foundation of China under Grant Nos.61572332,51507084(國家自然科學(xué)基金);the Postdoctoral Science Foundation of China under Grant Nos.2016T90850,2016M591890(中國博士后科學(xué)基金);the Fundamental Research Funds for the Central Universities of China under Grant No.2016SCU04A22(中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金).

Received 2016-08,Accepted 2016-10.

CNKI網(wǎng)絡(luò)優(yōu)先出版:2016-10-18,http://www.cnki.net/kcms/detail/11.5602.TP.20161018.1622.018.html

Key words:data quality;probabilistic suffix tree;Spark;parallel computing