基于Spark的序列數據質量評價*

2017-06-15 15:14:02王慧鋒唐常杰

計算機與生活 2017年6期

關鍵詞：評價質量

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

1.四川大學計算機學院，成都 610065

2.四川大學華西公共衛生學院，成都 610041

3.南京郵電大學先進技術研究院，南京 210003

基于Spark的序列數據質量評價*

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

1.四川大學計算機學院，成都 610065

2.四川大學華西公共衛生學院，成都 610041

3.南京郵電大學先進技術研究院，南京 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.

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

數據質量；概率后綴樹；Spark；并行計算

1 引言

大數據時代下的數據信息成為社會關注焦點。數據質量的高低影響其承載信息的利用效率和傳播廣度。高質量的數據是統計分析、數據挖掘、決策支持的基石；含有誤差、噪聲等質量差的數據會降低數據信息的利用和價值，降低生產生活效率。

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

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

為實現基于Spark框架的大規模序列數據質量評價，本文在文獻[2]工作基礎上需要克服以下挑戰：（1）針對Spark集群計算的特點，分析選用合適的序列數據生成模型的學習策略對提高算法執行效率至關重要；（2）為提高Spark集群中各計算節點的效率，設計有效的剪枝策略是實現并行建立概率后綴樹的關鍵；（3）設計適合Spark架構的高效數據分發和共享策略是實現對查詢序列的快速質量評價的基礎。

本文主要貢獻有：（1）提出了基于Spark的大規模序列數據質量評價問題；（2）討論了Spark框架上生成概率后綴樹的方法，并設計了基于Spark的序列數據質量評價算法STALK；（3）實驗驗證了STALK算法的有效性、執行效率和可擴展性。

本文組織結構如下：第2章給出本文研究問題定義；第3章介紹相關工作；第4章講述基于Spark的序列數據質量評價算法STALK；第5章通過實驗驗證STALK算法的有效性、執行效率和可擴展性；第6章總結本文工作，并對未來工作進行展望。

2 問題定義

給定序列樣本集合D，定義Σ為D中序列元素的集合，|S|為D中序列樣本S的長度，S[k]表示序列S中第k(1≤k≤|S|)個元素。為便于表達，定義如下對序列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′，若存在正整數k1,k2,…,km滿足1≤k1是S′在S中的一個實例。特別地，若?m>1，有kmkm-1=1，則稱S′是S的連續子序列。

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

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

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

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

例2考慮表1中的序列樣本集合D，令γ=[0,1]。給定序列S′=ab，對序列S1有實例<1，2>、<1，3>、<4，6>、<5，6>、<5，7>使得S′?γS1，對序列S2有實例<1，2>、<1，3>、<4，5>、<6，7>使得S′?γS2，對序列S3有實例<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的連續子序列，那么Sup()≥Sup()≥0。

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

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

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

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

條件2|S|≤l

給定樣本集合D，查詢序列S和質量評價閾值θ，本文目標在于訓練得到滿足定義2的生成模型?，通過計算S由?生成可能性L(S|?)與S由隨機模型生成可能性的比值，進行數據質量評價。具體地，若比值大于θ則認為S的質量可接受。

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

Table 2 Summary of notations表2 符號匯總

3 相關工作

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

序列數據中各元素之間的位置，蘊含著豐富的信息，各元素出現的先后位置信息存在某種潛在的規律或者滿足某個特殊的分布。針對序列數據具有短暫記憶性特征，文獻[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]之后出現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)。為了直接使用高階馬爾科夫鏈模型，文獻[3]提出利用概率后綴樹來模擬變化的記憶長度。文獻[10]針對鐵路數據利用概率后綴樹進行離群點檢測。文獻[11]利用概率后綴樹與支持向量機對數據進行分類。

為有效提高序列模式的適應性，挖掘序列模式時通常會考慮間隔約束。文獻[12]提出了產生序列前綴和后綴的PrefixSpan算法。文獻[13]在PrefixSpan算法的基礎上，提出了帶間隔約束的序列模式挖掘算法。文獻[14]設計了利用帶間隔約束的序列模式評價軟件缺陷特征的方法。

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

4 STALK算法設計

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

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

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

4.1 STALK算法生成概率后綴樹

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

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

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

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

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

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

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

輸出：概率后綴樹PST

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

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

3.k=1;//k描述當前后綴樹的深度

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函數計算候選序列模式的轉移概率，Generate函數生成下一層概率后綴樹的候選模式。

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

廣度優先遍歷策略在生成長度為l的候選序列模式之前會生成所有長度小于l的候選模式，Spark集群可以并行處理所有長度為l的候選序列模式，這樣可以提高算法效率。因此，采用廣度優先遍歷集合枚舉樹方式來生成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生成候選模式的過程類似于廣度優先遍歷集合枚舉樹。即對兩個長度為l且其后綴、前綴相同的模式，通過拼接操作生成長度為l+1的候選模式。例如，對ba和ab，由于Suf(ba)=Pre(ab),則生成新的候選模式bab。

4.2 序列轉移概率并行計算

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

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

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

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

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

算法3PST上節點的轉移概率計算getMatch (S′,γ)

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

輸出：S′及其轉移概率P

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

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

3.For each sequenceS∈Ddo

4. IfS′?γSthen

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

6. EndIf

7.EndFor

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

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

10.Return(S′,P);

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

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

Fig.3 Transition probability prcoss in STALK圖3 STALK中轉移概率計算過程

4.3 查詢序列的數據質量估計方法

通過得到的訓練模型?，給定序列S=S[1]S[2]…S[|S|]，用L(S|?)來衡量生成S的可能性。由貝葉斯后驗概率方法得L(S|?)=P(S[1])P(S[2]|S[1])…P(S[|S|]|S[1]S[2]…S[|S|-1])。根據記憶長度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])。

假設序列中各元素相互獨立，則生成S的概率為計算如下所示：

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

例5考慮例4中S=abba，θ=1.0。根據式（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的質量可接受。

4.4 Spark下的數據分發和共享策略

為適應基于內存的Spark框架，STALK算法在內存中存儲概率后綴樹，即各候選序列模式及其轉移概率，且主節點每次任務分發時將概率后綴樹底層的所有節點分發出去，降低了通信開銷。

在建立概率后綴樹過程中，每個計算節點分片計算新的序列模式匹配度，有兩種剪枝方案：

方案1計算節點剪枝。

方案2主節點剪枝。

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

5 實驗

實驗算法由Python語言實現，實驗節點配置為Intel Core i7，16 GB內存，Ubuntu14.0.4操作系統，Spark1.6.0版本。本文采用UCI機器學習數據集[23]中基因序列數據集SpliceEI、SpliceIE、SpliceN來驗證STALK算法的有效性、執行效率和可擴展性；采用SpliceIE、Activity、Location數據集[24-25]和蛋白質ABC-2族的APF01061數據集驗證序列元素集合對STALK執行效率的影響。實驗數據集如表3所示。算法參數默認值為l=2,γ=[0,1],minSup=0.85，計算節點數為8。

Table 3 Characteristics of experimental data sets表3 實驗數據集特征

5.1 算法有效性驗證

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

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

策略2在與策略1相同的生成條件下，利用隨機數r匹配區間，與策略1不同的是，匹配成功則轉移至對應小區間的節點，生成1×103條質量不可接受的SpliceEID-、SpliceIED-、SpliceND-集合。

用SpliceEID+∪SpliceEID-，SpliceIED+∪SpliceIED-，SpliceND+∪SpliceND-分別組成測試數據SpliceEID、SpliceIED、SpliceND。為驗證STALK算法能否有效檢測到質量不可接受的序列樣本，分別用SpliceEI、SpliceIE、SpliceN作為訓練集，利用STALK算法生成模型，對SpliceEID、SpliceIED、SpliceND進行質量評價。表4給出θ改變時STALK算法在各數據集上的數據質量評價結果，觀察得，STALK算法能有效查找出數據質量不可接受的序列。

Table 4 Results of STALK on test data sets表4 STALK算法對測試數據集的結果

5.2 算法執行效率驗證

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

Fig.4 Comparison of runtime between STALK and SQEPST圖4 STALK與SQEPST算法的運行時間比較

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

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

5.3 算法可擴展性驗證

為驗證STALK算法的可擴展性，按照策略1對3個基因序列數據集合成5×105條數據，分析計算節點數目對建立生成模型時間的影響。觀察圖5~圖7中（c）圖，隨著節點數目增加，STALK算法執行時間顯著降低。原因為給定數據條數，主節點根據計算節點數目分發任務。因此增加節點數，各節點的數據分片會減少，相應各計算節點的執行時間減小，總時間減小。為驗證數據規模對算法可擴展性的影響，按照策略1分別將3個基因數據集的規模合成為2× 106、4×106、6×106、8×106、10×106。觀察圖5~圖7中（d）圖，隨著數據規模增大，算法執行時間增加。原因為當數據規模增大時，算法需要在更多序列樣本上計算候選模式的匹配度和支持度，因此執行時間增長。

Fig.5 Runtime of STALK on synthetic data set by SpliceEI圖5 在SpliceEI合成數據集上STALK算法的運行時間

Fig.6 Runtime of STALK on synthetic data set SpliceIE圖6 在SpliceIE合成數據集上STALK算法的運行時間

Fig.7 Runtime of STALK on synthetic data set SpliceN圖7 在SpliceN合成數據集上STALK算法的運行時間

5.4 |Σ|對算法執行效率的影響

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

Fig.8 Runtime of STALK on data sets with different|Σ|圖8 STALK算法在含有不同|Σ|的數據集上的運行時間

6 結束語

數據質量評價的傳統方式是定性分析，缺少利用生成模型對大規模數據質量的分析。針對該問題，本文提出了基于Spark的序列數據質量評價算法STALK。STALK算法利用質量可靠的序列樣本集合高效建立生成模型，并根據生成模型快速評價查詢數據質量，并且采用改進的剪枝策略優化了算法在Spark平臺的執行效率。通過大規模序列數據集驗證了算法的有效性、執行效率和可擴展性。

下一步，將增加Spark集群中計算節點數量，使STALK適用于更大規模的數據分析。同時，考慮更多實際應用中對STALK算法有效性、執行效率和可擴展性的驗證；設計STALK算法在不同領域的應用，嘗試將其運用到理財投資中，分析個人理財習慣并對理財產品進行推薦，利用序列質量評價進行DNA異常序列檢測。

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.

附中文參考文獻:

[1]郭志懋,周傲英.數據質量和數據清洗研究綜述[J].軟件學報,2002,13(11):2076-2082.

[2]王慧鋒,段磊,胡斌,等.帶間隔約束的序列數據質量評價算法設計[J].計算機科學與探索,2015,9(10):1180-1194.

[7]孟嘯,王宏志,高宏,等.bibEOS:一個高質量的社會化文獻檢索與管理系統[J].計算機科學與探索,2010,4(1):54-63.

[8]丁小歐,王宏志,張笑影,等.數據質量多種性質的關聯關系研究[J].軟件學報,2016,27(7):1626-1644.

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

[25]楊皓,段磊,胡斌,等.帶間隔約束的Top-k對比序列模式挖掘[J].軟件學報,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—），男，甘肅慶陽人，四川大學計算機學院碩士研究生，CCF學生會員，主要研究領域為數據挖掘，知識工程。

段磊（1981—），男，四川成都人，2008年于四川大學計算機應用技術專業獲得博士學位，現為四川大學副教授、碩士生導師，CCF高級會員，主要研究領域為數據挖掘，健康信息學，進化計算。

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—），男，安徽合肥人，博士，高級工程師，主要研究領域為分布式數據挖掘，智能電網信息安全，電力信息物理融合系統。

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年于四川大學計算機科學與技術專業獲得碩士學位，主要研究領域為數據挖掘，知識工程。

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—），男，重慶人，四川大學教授、博士生導師，CCF杰出會員，主要研究領域為數據庫技術，數據挖掘。

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.

TP391

*The National Natural Science Foundation of China under Grant Nos.61572332,51507084(國家自然科學基金);the Postdoctoral Science Foundation of China under Grant Nos.2016T90850,2016M591890(中國博士后科學基金);the Fundamental Research Funds for the Central Universities of China under Grant No.2016SCU04A22(中央高校基本科研業務費專項資金).

Received 2016-08,Accepted 2016-10.

CNKI網絡優先出版: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