基于Spark的時(shí)間序列并行分解模型*

李 勇，滕 飛,2+，黃齊川，李天瑞

1.西南交通大學(xué) 信息科學(xué)與技術(shù)學(xué)院，成都 611756

2.軌道交通工程信息化國家重點(diǎn)實(shí)驗(yàn)室（中鐵第一勘察設(shè)計(jì)院），西安 710043

1 引言

時(shí)間序列是指在生產(chǎn)和科學(xué)研究等過程中，按照時(shí)間順序記錄得到的一系列觀測值，反映了現(xiàn)象的發(fā)展變化規(guī)律。隨著信息技術(shù)的快速發(fā)展，各個(gè)行業(yè)應(yīng)用系統(tǒng)產(chǎn)生的時(shí)間序列呈爆炸式增長，已遠(yuǎn)遠(yuǎn)超出了現(xiàn)有傳統(tǒng)的信息系統(tǒng)的處理能力[1-2]。尋求有效的大數(shù)據(jù)處理技術(shù)成為現(xiàn)實(shí)世界的迫切需求。

現(xiàn)實(shí)中的時(shí)間序列一般是比較復(fù)雜的、廣義平穩(wěn)或者非平穩(wěn)的，由多種因素共同作用的結(jié)果，不容易直接對(duì)其進(jìn)行觀察分析，而需要首先對(duì)其分解。本文根據(jù)時(shí)間序列分解算法每個(gè)處理過程輸入數(shù)據(jù)的獨(dú)立性，將時(shí)間序列分解算法分為兩種操作類型：（1）局部相關(guān)。這種操作類型的時(shí)間序列算法具有良好的并行性，因?yàn)榍蟹值玫降臅r(shí)間子序列具有一定的獨(dú)立性，處理節(jié)點(diǎn)之間進(jìn)行少量的通信、數(shù)據(jù)交換就可以達(dá)到較好的處理效果，例如STL（seasonaltrend decomposition using LOESS）[3]、EMD（empirical mode decomposition）[4]、X-12-ARIMA（autoregressive integrated moving average model）[5]等。STL算法可將時(shí)間序列分解為低頻率的趨勢項(xiàng)、高頻率的季節(jié)項(xiàng)及不規(guī)則變化的殘差項(xiàng)[3]。因?yàn)镾TL使用LOESS[6]（locally weighted regression and smoothing）作為平滑器，所以具有良好的數(shù)據(jù)并行特性。（2）全局相關(guān)。時(shí)間序列的每個(gè)時(shí)間點(diǎn)的處理過程都有很強(qiáng)的相關(guān)性，這種類型的時(shí)間序列分析算法難以取得較好的并行效果，例如 SSA（singular spectrum analysis）[7]、WD（wavelet decomposition）[8]等。SSA是一種時(shí)間序列分解算法，具有插值、去噪、識(shí)別趨勢和周期信號(hào)以及建立預(yù)報(bào)模型的功能[9-10]。SSA算法分解過程為：首先將時(shí)間序列轉(zhuǎn)換成軌跡矩陣，然后對(duì)軌跡矩陣進(jìn)行奇異值分解，分解之后再對(duì)每個(gè)分量進(jìn)行分組和重構(gòu)，從而得到分解結(jié)果[7]。SSA分解過程中各時(shí)間點(diǎn)之間具有很強(qiáng)的相關(guān)性，序列分段計(jì)算會(huì)造成信息損失，數(shù)據(jù)并行性較差。

現(xiàn)如今成熟的數(shù)據(jù)挖掘平臺(tái)主要有SAS、SPSS、Matlab、R等，它們當(dāng)中包含豐富的時(shí)間序列分析軟件包，不過這些都不是分布式的，無法高效處理大規(guī)模時(shí)間序列數(shù)據(jù)。Spark是目前最活躍的開源分布式計(jì)算框架之一，其基于內(nèi)存計(jì)算的特點(diǎn)，提高了大數(shù)據(jù)環(huán)境下處理數(shù)據(jù)的實(shí)時(shí)性，同時(shí)也保證了高容錯(cuò)性和高可伸縮性，并且允許用戶將Spark部署在大量廉價(jià)的硬件上，形成集群[11]。研究人員相繼提出了基于Spark平臺(tái)的并行算法。文獻(xiàn)[12]設(shè)計(jì)了基于Spark平臺(tái)的DNA基因序列拼接算法，在保證拼接準(zhǔn)確性的前提下提升了拼接效率。文獻(xiàn)[13]借助Spark平臺(tái)對(duì)道路交通管理分析平臺(tái)的海量系統(tǒng)日志進(jìn)行查詢、分析，相比傳統(tǒng)的分析方法更加高效。文獻(xiàn)[14]提出了基于Spark的序列模式挖掘算法，打破了傳統(tǒng)串行算法不能處理大規(guī)模數(shù)據(jù)集的局限，并在真實(shí)數(shù)據(jù)集上驗(yàn)證了算法效率。文獻(xiàn)[15]提出了基于Spark平臺(tái)的隨機(jī)并行森林算法，算法從數(shù)據(jù)和任務(wù)兩個(gè)角度設(shè)計(jì)并行方案，在分類準(zhǔn)確性、擴(kuò)展性等方面都優(yōu)于現(xiàn)有的隨機(jī)森林并行算法。對(duì)于分布式算法的研究雖然包括了豐富的機(jī)器學(xué)習(xí)算法，但是對(duì)于時(shí)間序列分解算法鮮有涉及。

鑒于傳統(tǒng)的單機(jī)數(shù)據(jù)挖掘平臺(tái)無法處理大規(guī)模的時(shí)間序列，對(duì)于并行的時(shí)間序列分解算法國內(nèi)外研究成果較少，目前流行的分布式機(jī)器學(xué)習(xí)平臺(tái)未涉及時(shí)間序列分解算法的原因，本文提出一種基于Spark平臺(tái)的時(shí)間序列分解模型。模型的核心思想為：首先將完整的時(shí)間序列切分成一系列的子序列，通過對(duì)子序列去冗余的方式保護(hù)內(nèi)部數(shù)據(jù)免受端點(diǎn)數(shù)據(jù)污染，然后將帶有冗余的時(shí)間子序列分發(fā)給Spark集群的計(jì)算節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)獨(dú)立進(jìn)行序列分解，最后去除結(jié)果的冗余部分，再將其合并。本文針對(duì)兩種（局部和全局相關(guān)）分解特點(diǎn)的算法，給出模型的兩個(gè)實(shí)例，在基于內(nèi)存計(jì)算的計(jì)算框架Spark上實(shí)現(xiàn)STL（局部相關(guān)）和SSA（全局相關(guān)）。

本文組織結(jié)構(gòu)如下：第2章結(jié)合具體的時(shí)間序列分解算法STL、SSA詳細(xì)介紹模型的框架結(jié)構(gòu)；第3章針對(duì)模型實(shí)例進(jìn)行實(shí)驗(yàn)測試，驗(yàn)證模型的有效性和高效性；第4章對(duì)全文進(jìn)行總結(jié)。

2 模型設(shè)計(jì)

本文模型的主要目標(biāo)是在保證正確性的前提下高效地分解大規(guī)模時(shí)間序列。因此目標(biāo)主要定位在以下兩方面：（1）著眼于集成兩種類型計(jì)算特點(diǎn)的時(shí)間序列分解算法。對(duì)于第二種類型的時(shí)間序列分析算法并行難度較大，不同的算法需要特定的并行方式才能達(dá)到較好的效果，本文旨在通過數(shù)據(jù)并行的方式得到一個(gè)近似結(jié)果，并通過冗余數(shù)據(jù)的方式提高準(zhǔn)確性。（2）模型能夠架構(gòu)在Spark的集群上。

模型構(gòu)架主要包括3個(gè)模塊，如圖1所示。

Fig.1 Model framework圖1 模型架構(gòu)

（1）時(shí)間序列切分冗余?？紤]到將時(shí)間序列切分后的時(shí)間子序列之間的關(guān)聯(lián)操作是局部相關(guān)的，也就是說對(duì)某個(gè)時(shí)間點(diǎn)的計(jì)算只需要用到附近一定數(shù)量的數(shù)據(jù)點(diǎn)，因此考慮通過對(duì)時(shí)間子序列冗余部分?jǐn)?shù)據(jù)以提高分布式處理時(shí)間序列的準(zhǔn)確性。

（2）時(shí)間序列分解。該模塊的功能是將時(shí)間序列分解算法應(yīng)用到每個(gè)Spark計(jì)算節(jié)點(diǎn)，得到每個(gè)帶冗余的時(shí)間子序列的分析結(jié)果。

（3）時(shí)間序列結(jié)果合并。將每個(gè)計(jì)算節(jié)點(diǎn)的分析結(jié)果去除冗余部分直接合并。

本文將以STL算法為例介紹模型實(shí)現(xiàn)過程。

2.1 模型實(shí)例

2.1.1 冗余數(shù)量選取

時(shí)間子序列之間是局部相關(guān)的，因此冗余的數(shù)據(jù)越多，序列切分處理后的結(jié)果就越接近完整序列處理的結(jié)果。為了方便理解，本文以一個(gè)周期（T）的數(shù)據(jù)為單位對(duì)時(shí)間子序列進(jìn)行冗余。

STL的計(jì)算過程由內(nèi)循環(huán)和外循環(huán)兩部分組成。內(nèi)循環(huán)要進(jìn)行3次窗口長度為 ns、nl、nt的LOESS[3]平滑和3次窗口長度為 np、np、3的移動(dòng)平均，其中np為時(shí)間序列的周期。外循環(huán)是一個(gè)不斷迭代內(nèi)循環(huán)的過程。

假設(shè)某個(gè)時(shí)間序列T的子序列Tn中的一個(gè)時(shí)間點(diǎn)為tm，想要保證在一次內(nèi)部循環(huán)的過程中，獨(dú)立處理子序列Tn和完整處理時(shí)間序列T時(shí)tm時(shí)間點(diǎn)的計(jì)算結(jié)果相近，就必須算出3次LOESS平滑過程和3次移動(dòng)平均過程計(jì)算tm時(shí)所需要前后時(shí)間點(diǎn)的數(shù)據(jù)量，即冗余數(shù)據(jù)量。

分析STL算法的執(zhí)行過程，冗余數(shù)據(jù)量為以下兩部分冗余量的加和（np為周期長度）：

（1）3次LOESS平滑。對(duì)于某個(gè)時(shí)間點(diǎn)tm的LOESS平滑使用到前后時(shí)間點(diǎn)的數(shù)量為窗口長度的一半。周期子序列平滑中的LOESS平滑是在周期層面的平滑，需要窗口長度一半數(shù)量的周期數(shù)據(jù)，低通濾波、趨勢平滑過程中的LOESS平滑是在時(shí)間點(diǎn)層面上的平滑，只需要窗口長度一半數(shù)量的時(shí)間點(diǎn)數(shù)據(jù)。例如，對(duì)于一個(gè)以年為周期的月度時(shí)間序列，假設(shè)分別對(duì)某個(gè)時(shí)間點(diǎn)進(jìn)行窗口長度為5的周期層面和時(shí)間點(diǎn)層面上的平滑需要時(shí)間點(diǎn)前后的數(shù)據(jù)量為24個(gè)月（2個(gè)周期）和2個(gè)月（2/12個(gè)周期）。因此，周期子序列平滑中LOESS平滑過程需要冗余的數(shù)據(jù)量為ns/2，低通濾波平滑過程需要冗余的數(shù)據(jù)量為nl/2×np，趨勢平滑過程中LOESS平滑需要冗余的數(shù)據(jù)量為nt/2×np。

（2）3次移動(dòng)平均。移動(dòng)平均為在時(shí)間點(diǎn)層面上的操作，3次窗口長度為np、np、3的移動(dòng)平均過程中需要的數(shù)據(jù)冗余量分別為 (np-1)/np、(np-1)/np、2/np。

STL算法是一個(gè)迭代的過程，由多次內(nèi)循環(huán)和多次外循環(huán)組成，因此序列切分處理即使冗余數(shù)據(jù)也不可能和完整時(shí)間序列處理的結(jié)果完全一致，冗余數(shù)據(jù)的作用是在一定程度上保護(hù)內(nèi)部的數(shù)據(jù)不受端點(diǎn)數(shù)據(jù)的污染，從而使得序列分塊處理的結(jié)果盡可能地接近完整序列處理的結(jié)果。

綜合以上分析，本文使用如下公式（兩部分冗余數(shù)量的加和）來計(jì)算冗余量：

例如當(dāng) ns=7，nl=np，nt=1.5np時(shí) R=7，即冗余數(shù)據(jù)量為7個(gè)周期。

對(duì)于STL算法切分后的時(shí)間子序列之間是局部相關(guān)的，因此可以分析算法執(zhí)行過程得到合適的冗余數(shù)量。而SSA算法是全局相關(guān)的，因此本文通過實(shí)驗(yàn)確定冗余數(shù)量來達(dá)到較優(yōu)的分解效果。

2.1.2 時(shí)間序列切分

主要包括對(duì)時(shí)間序列切分時(shí)的幾種特殊情況的處理：（1）對(duì)于STL算法為了達(dá)到較好的分解效果，周期子序列平滑窗口必須大于等于7，因此當(dāng)時(shí)間子序列的長度小于7個(gè)周期時(shí)，默認(rèn)其為7個(gè)周期。（2）時(shí)間子序列長度大于完整序列長度時(shí)，將時(shí)間序列劃分成一個(gè)子序列，即處理完整時(shí)間序列。（3）時(shí)間序列不一定能等分，最后一個(gè)子序列應(yīng)包含剩下所有時(shí)間點(diǎn)。

2.2 模型實(shí)現(xiàn)

圖2展示了Spark實(shí)現(xiàn)并行分解算法的狀態(tài)轉(zhuǎn)移圖。結(jié)合并行狀態(tài)轉(zhuǎn)移圖可以將并行過程描述如下：首先從HDFS（Hadoop distributed file system）上讀取數(shù)據(jù)，并將數(shù)據(jù)重新分區(qū)（分區(qū)數(shù)為參數(shù)slice）生成RDD1。然后調(diào)用Spark中的mapPartitions算子獲取每個(gè)分區(qū)的迭代器，調(diào)用切分冗余函數(shù)rdSplit（）將每個(gè)分區(qū)中的時(shí)間序列切分和冗余生成一系列時(shí)間子序列，結(jié)果返回格式為ArrayBuffer（ArrayBuffer（object））的RDD：RDD2。隨后再利用RDD2.map算子將stl（）、ssa（）分解算法應(yīng)用到每個(gè)時(shí)間子序列，每個(gè)時(shí)間子序列分解后直接刪除冗余，結(jié)果返回格式為ArrayBuffer（ArrayBuffer（T，S，R））的三元組集合（一個(gè)時(shí)間子序列分解結(jié)果）組成的集合（一個(gè)分區(qū)中所有時(shí)間子序列分解結(jié)果），再調(diào)用flatMap算子將RDD中每個(gè)分區(qū)每個(gè)集合中的元素合并成一個(gè)集合，即RDD3的格式為ArrayBuffer（（T，S，R））。最后利用Spark提供的saveAsTextFile算子將RDD3持久化存儲(chǔ)到HDFS的指定目錄。

Fig.2 Parallel state transition diagram圖2 并行狀態(tài)轉(zhuǎn)移圖

3 實(shí)驗(yàn)設(shè)計(jì)與結(jié)果分析

本文設(shè)計(jì)了兩部分實(shí)驗(yàn)來驗(yàn)證模型實(shí)例的結(jié)果：設(shè)計(jì)了并行一致性驗(yàn)證實(shí)驗(yàn)來證明時(shí)間序列切分、冗余的并行方式的有效性；設(shè)計(jì)了性能驗(yàn)證實(shí)驗(yàn)來證明基于Spark平臺(tái)實(shí)現(xiàn)的性能優(yōu)勢。

3.1 一致性驗(yàn)證

3.1.1 數(shù)據(jù)集描述

本文采用兩種類型的數(shù)據(jù)集：（1）蘇黎世1749—1983年太陽黑子月度數(shù)據(jù)，共2 820個(gè)觀測；（2）添加了噪聲的正弦模擬信號(hào)，y=50×sin(43×π×t)+20×sin(52×π×t)，采樣頻率為1 000。

3.1.2 實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)中使用的計(jì)算機(jī)配置如表1所示。

Table 1 Computer environment表1 計(jì)算機(jī)配置信息

3.1.3 實(shí)驗(yàn)方案

本文使用相似度函數(shù)來衡量序列分布式處理和完整序列處理結(jié)果的相似程度。相似度函數(shù)[16]定義如下：設(shè)xn和yn是兩個(gè)能量有限的確定性信號(hào)，并假定它們是因果的，則定義xn和yn的相關(guān)系數(shù)為：

由公式可知，當(dāng)xn=yn時(shí),ρxy=1，表明兩個(gè)信號(hào)完全相關(guān)（相等）；當(dāng)它們完全無關(guān)時(shí)，ρxy=0。

本實(shí)驗(yàn)在單機(jī)上進(jìn)行，使用R語言中提供的STL、SSA算法包。實(shí)驗(yàn)方案是對(duì)兩個(gè)類型不同的時(shí)間序列，分別采用不同的處理方式：（1）單機(jī)處理方法，完整時(shí)間序列直接分解；（2）分布式處理方法，時(shí)間序列切分、冗余后分解、合并，然后對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行對(duì)比。其中合并時(shí)間子序列分解結(jié)果時(shí)，冗余處理方式有兩種：冗余部分取平均和冗余直接去除。實(shí)驗(yàn)選取了不同長度的時(shí)間子序列，不同的長度反映了時(shí)間序列切分帶來的端點(diǎn)對(duì)內(nèi)部數(shù)據(jù)的污染程度。

3.1.3.1 局部相關(guān)分解算法一致性驗(yàn)證（STL）

主要包括3組對(duì)比實(shí)驗(yàn)：（1）對(duì)于分布式處理方式，冗余取平均和冗余直接去除的效果對(duì)比；（2）對(duì)于分布式處理方式，采取不同時(shí)間子序列長度的效果對(duì)比；（3）對(duì)于前兩組對(duì)比實(shí)驗(yàn)使用不同類型時(shí)間序列處理結(jié)果對(duì)比。兩種處理方式結(jié)果對(duì)比評(píng)價(jià)指標(biāo)為式（2）。

分布式處理方式將時(shí)間序列分成多個(gè)時(shí)間子序列，由式（1）計(jì)算冗余估計(jì)量（ns=7，nl=np，nt=1.5np，參數(shù)選擇參考文獻(xiàn)[3]），R=7。實(shí)驗(yàn)中選取了6個(gè)長度不同的冗余量：0T（不冗余），1T，3T（R/2），7T（R），10T（3R/2），14T（2R），T表示一個(gè)周期采樣點(diǎn)數(shù)量。

表2給出了完整時(shí)間序列數(shù)據(jù)分解結(jié)果和分布式時(shí)間序列分解結(jié)果的相似度，分解結(jié)果主要包括季節(jié)項(xiàng)（S），趨勢項(xiàng)（T），季節(jié)項(xiàng)和趨勢項(xiàng)的和（S+T）。太陽黑子1、2數(shù)據(jù)集中時(shí)間子序列的長度分別是3T、78T。分解結(jié)果的冗余處理方式為直接去除。太陽黑子3數(shù)據(jù)集中時(shí)間子序列長度為78T，冗余處理方式為冗余部分取平均。正弦模擬信號(hào)序列長度為3T，冗余處理方式為直接去除。（3T，78，冗余去除）表示每個(gè)子序列長度為3周期，共78個(gè)序列，冗余直接去除。

Table 2 Consistency test result for local correlation based decomposition algorithm表2 局部相關(guān)分解算法一致性驗(yàn)證結(jié)果（STL）

對(duì)于兩種不同類型的時(shí)間序列數(shù)據(jù)，分析表2中的數(shù)據(jù)可以得到如下結(jié)論：

（1）時(shí)間子序列冗余數(shù)量越多，與完整序列處理的結(jié)果相似程度越高，太陽黑子1和模擬信號(hào)中時(shí)間子序列的長度為3個(gè)周期，這是一種極端情況即端點(diǎn)數(shù)據(jù)最大程度地污染內(nèi)部數(shù)據(jù)，當(dāng)冗余量達(dá)到7個(gè)周期的數(shù)據(jù)時(shí)，季節(jié)項(xiàng)和趨勢項(xiàng)的相似度都達(dá)到了91%，說明了本文時(shí)間序列分布式處理方法和傳統(tǒng)的單機(jī)處理結(jié)果對(duì)比具有較高的一致性。

（2）對(duì)比太陽黑子和模擬信號(hào)分解結(jié)果，可以說明對(duì)于不同類型的時(shí)間序列，通過冗余的方式，分布式處理都能達(dá)到較好的處理效果。

（3）對(duì)比太陽黑子2和3數(shù)據(jù)集得出結(jié)論，時(shí)間子序列分解結(jié)果合并時(shí)，冗余部分直接去除具有更好的效果，這是因?yàn)槿哂嗖糠秩∑骄禃?huì)把邊緣的誤差傳遞到內(nèi)部。

（4）分布式處理時(shí)間序列的方式，冗余的數(shù)據(jù)造成了額外的計(jì)算開銷，但是極大地提升了計(jì)算結(jié)果的精確度。假設(shè)時(shí)間子序列長度為s，冗余數(shù)據(jù)長度為r，則分布式處理方式增加的計(jì)算量為a=r/s（%）。對(duì)于同一個(gè)時(shí)間子序列來說，子序列長度越大造成的額外開銷就越小。例如，表2中當(dāng)時(shí)間序列的長度為78T時(shí)端點(diǎn)數(shù)據(jù)對(duì)內(nèi)部污染很小，即使不冗余數(shù)據(jù)也可以達(dá)到90%的相似度，冗余數(shù)據(jù)為7T時(shí)增加了17.9%計(jì)算量，相似度提高了4.8%。表4中當(dāng)時(shí)間子序列的長度為3T時(shí)，冗余7T的數(shù)據(jù)時(shí)增加了466%計(jì)算量，相似度提高了59.2%。

3.1.3.2 全局相關(guān)分解算法一致性驗(yàn)證（SSA）

首先將太陽黑子數(shù)據(jù)和模擬信號(hào)時(shí)間序列分為不同段長，然后采取不同冗余長度進(jìn)行分解，最后對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行對(duì)比，結(jié)果對(duì)比評(píng)價(jià)指標(biāo)為式（2）。算法參數(shù)：SSA算法的窗口長度為序列一半，SSA算法分組參數(shù)參考文獻(xiàn)[13]。實(shí)驗(yàn)使用SSA將兩個(gè)序列都分解成兩個(gè)分量F1和F2，太陽黑子數(shù)據(jù)分解后得到趨勢項(xiàng)和周期項(xiàng)，模擬信號(hào)中不包含趨勢，因此分解后得到兩個(gè)正弦分量。

表3給出了分解結(jié)果的相似度，可以發(fā)現(xiàn)：（1）隨著冗余數(shù)量增多，結(jié)果的相似度不斷提升，對(duì)于太陽黑子數(shù)據(jù)段長為3周期這種極端情況，F(xiàn)2分量的分解效果很不理想，這是因?yàn)镾SA分解過程中各時(shí)間點(diǎn)的操作是全局相關(guān)的，時(shí)間序列切分得太短，導(dǎo)致?lián)p失信息太多，信號(hào)周期信息不全，所以分解結(jié)果很不理想。因?yàn)镕1分量能量較強(qiáng)，即使段長很短，也能取得較好的效果。模擬信號(hào)比較平穩(wěn)，在這種極端情況下表現(xiàn)良好。（2）對(duì)于太陽黑子2和模擬信號(hào)數(shù)據(jù)，當(dāng)冗余數(shù)量為2個(gè)周期采樣點(diǎn)時(shí)相似度達(dá)到了91%以上，說明本文方法與單機(jī)處理方式具有較高的一致性，當(dāng)冗余數(shù)據(jù)超過2個(gè)周期采樣點(diǎn)，效果提升不明顯。

Table 3 Consistency test result for global correlation based decomposition algorithm表3 全局相關(guān)分解算法一致性驗(yàn)證結(jié)果（SSA）

3.2 性能提升驗(yàn)證

3.2.1 數(shù)據(jù)集描述

本實(shí)驗(yàn)采用的數(shù)據(jù)是高鐵軌檢車采集的軌道狀態(tài)真實(shí)數(shù)據(jù)。軌檢車是一列裝有專用檢測設(shè)備，對(duì)軌道、供電、信號(hào)、周邊環(huán)境等影響列車安全運(yùn)行和舒適性的技術(shù)指標(biāo)和相關(guān)信息進(jìn)行實(shí)時(shí)檢測。軌檢車每0.25 m采集一個(gè)數(shù)據(jù)點(diǎn)，本實(shí)驗(yàn)只驗(yàn)證算法效率，因此設(shè)置高鐵軌檢數(shù)據(jù)周期T為500 m的采樣點(diǎn)數(shù)，每個(gè)塊的大小為10個(gè)周期數(shù)據(jù)。STL實(shí)驗(yàn)使用6個(gè)數(shù)據(jù)集32 MB（約500萬采樣點(diǎn)）、64 MB、128 MB、256 MB、512 MB、1 024 MB。由于SSA計(jì)算時(shí)間較長，使用5個(gè)較小的數(shù)據(jù)集8 MB、16 MB、32 MB、64 MB、128 MB。

3.2.2 實(shí)驗(yàn)方案

為了方便分析實(shí)驗(yàn)結(jié)果，將本文模型的實(shí)例基于Spark的STL、SSA算法標(biāo)記為STL-Spark、SSASpark。為證明STL-Spark的效率提升和串行單機(jī)算法的局限性，本實(shí)驗(yàn)同R語言軟件包中的STL、SSA算法進(jìn)行比較，該算法標(biāo)記為STL-R、SSA-R，Scala語言實(shí)現(xiàn)的串行STL算法記為STL-S。為了公平起見，Spark實(shí)現(xiàn)的參數(shù)都參照R的設(shè)置。

Spark RDD是被分區(qū)的，在生成RDD時(shí)，一般可以指定分區(qū)的數(shù)量，如果不指定分區(qū)數(shù)量，當(dāng)RDD從集合創(chuàng)建時(shí)，則默認(rèn)為該程序所分配到的資源的CPU核數(shù)，如果是從HDFS文件創(chuàng)建，默認(rèn)為文件的Block數(shù)。分區(qū)的個(gè)數(shù)決定了并行計(jì)算的粒度，本實(shí)驗(yàn)是從HDFS上讀取文件，HDFS上默認(rèn)的Block大小為64 MB，粒度太粗，為了能夠充分利用計(jì)算資源，需要對(duì)RDD進(jìn)行重新分區(qū)。Spark官方建議每一個(gè)CPU核（core）分配2～3個(gè)任務(wù)，本實(shí)驗(yàn)最多使用8個(gè)節(jié)點(diǎn)共32個(gè)核，因此Spark讀HDFS上的時(shí)間序列數(shù)據(jù)時(shí)分區(qū)數(shù)目設(shè)置成96。STL、SSA實(shí)驗(yàn)中冗余數(shù)量為1個(gè)周期數(shù)據(jù)，冗余處理方式采用的是直接去除。

表4展示的是單機(jī)處理方式（STL-R和STL-S）和基于Spark的分布式處理方式的運(yùn)行時(shí)間，表中“NA”表示內(nèi)存溢出程序崩潰。分析表中數(shù)據(jù)可以得到如下結(jié)論：（1）STL-S運(yùn)行效率低且數(shù)據(jù)處理能力較差，最多只能處理128 MB的數(shù)據(jù)，產(chǎn)生這種情況的原因是當(dāng)數(shù)據(jù)量增大時(shí)，JVM（Java virtual machine）垃圾回收時(shí)間較長。（2）STL-R數(shù)據(jù)處理能力較強(qiáng)但是受內(nèi)存限制，數(shù)據(jù)量較大（1 024 MB）時(shí)程序崩潰，此時(shí)STL-Spark表現(xiàn)出較大優(yōu)勢。

表5展示的是SSA算法單機(jī)處理方式SSA-R和基于Spark的分布式處理方式的運(yùn)行時(shí)間。分析表中數(shù)據(jù)可以得出結(jié)論：R語言數(shù)據(jù)處理能力較強(qiáng)但是受內(nèi)存限制，數(shù)據(jù)量較大（32 MB）時(shí)程序崩潰，此時(shí)Spark表現(xiàn)出較大優(yōu)勢。對(duì)于實(shí)驗(yàn)中最大的數(shù)據(jù)集128 MB，8個(gè)節(jié)點(diǎn)相對(duì)于1個(gè)節(jié)點(diǎn)效率提升了7倍，極大地提升了效率。

4 結(jié)束語

為了應(yīng)對(duì)大數(shù)據(jù)時(shí)代下因時(shí)間序列規(guī)模急劇增長導(dǎo)致的傳統(tǒng)單機(jī)算法無法快速進(jìn)行時(shí)間序列分解的問題，本文提出了一種基于Spark平臺(tái)的時(shí)間序列分解模型。模型對(duì)特定計(jì)算特點(diǎn)（局部相關(guān)和全局相關(guān)）的時(shí)間序列分析算法進(jìn)行并行，使其能架構(gòu)在Spark計(jì)算集群上。針對(duì)模型實(shí)例（STL、SSA）進(jìn)行實(shí)驗(yàn)，結(jié)果證明了局部和全局相關(guān)分解算法通過冗余數(shù)據(jù)的方式都能夠保證分布式分解的正確性，同時(shí)基于Spark平臺(tái)的實(shí)現(xiàn)，極大地提高了時(shí)間序列分解效率。對(duì)于段長和冗余數(shù)量參數(shù)的選取，局部相關(guān)分解算法通過分析算法的執(zhí)行過程可以計(jì)算出合適的冗余數(shù)量，即使段長很短的極端情況也可以達(dá)到一個(gè)較優(yōu)的效果（相似度90%以上）。全局相關(guān)分解算法分解過程中各時(shí)間點(diǎn)之間具有很強(qiáng)的相關(guān)性，序列分段計(jì)算會(huì)造成信息損失，通過冗余數(shù)據(jù)的方式難以達(dá)到局部相關(guān)分解算法的效果，但是通過實(shí)驗(yàn)選擇合適的段長和冗余數(shù)量也可以得到一個(gè)較優(yōu)的結(jié)果。未來的工作：（1）對(duì)于SSA這種全局相關(guān)計(jì)算特點(diǎn)的算法，需要做更多的探索來確定分段的長度以及冗余數(shù)據(jù)的數(shù)量；（2）可以考慮將更多的時(shí)間序列分解算法融入到模型中，以形成一個(gè)分布式的時(shí)間序列分解工具。

Table 4 Running time for different processing methods(series and distributed)with different data sizes(STL)表4 STL串行和分布式處理方式、不同大小數(shù)據(jù)集的運(yùn)行時(shí)間

Table 5 Running time for different processing methods(series and distributed)with different data sizes(SSA)表5 SSA串行和分布式處理方式、不同大小數(shù)據(jù)集的運(yùn)行時(shí)間