王 可，李 暉，陳 梅，戴震宇，朱 明

(1.貴州大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，貴州 貴陽 550025; 2.貴州省先進(jìn)計(jì)算與醫(yī)療信息服務(wù)工程實(shí)驗(yàn)室，貴州 貴陽 550025; 3.中國(guó)科學(xué)院國(guó)家天文臺(tái)，北京 100101)

0 引 言

時(shí)間序列數(shù)據(jù)在金融、工業(yè)、醫(yī)藥、科研等領(lǐng)域廣泛存在，人們使用數(shù)據(jù)科學(xué)和機(jī)器學(xué)習(xí)技術(shù)對(duì)其分析進(jìn)行可視化、決策和預(yù)測(cè)。時(shí)序數(shù)據(jù)是數(shù)據(jù)流的一種，且流數(shù)據(jù)挖掘具有量大、速度快、對(duì)數(shù)據(jù)僅掃描一次等特點(diǎn)，同時(shí)流數(shù)據(jù)挖掘是CPU密集型任務(wù)，易過載、高延遲。所以，在資源受限條件下實(shí)現(xiàn)最大化挖掘收益是一項(xiàng)艱巨的任務(wù)。因此，需要引入降載技術(shù)，降載(Load Shedding)[1-7]是指當(dāng)輸入數(shù)據(jù)流超出流處理引擎(Stream-Processing Engines, SPEs)[5,8-10]的處理能力時(shí)移除多余負(fù)載的過程。

降載策略主要包括隨機(jī)降載[1,9]、語義降載[7]和自適應(yīng)降載[1,3-5]。隨機(jī)降載根據(jù)一定比例或隨機(jī)丟棄一些元組，可能會(huì)丟失重要的元組。語義降載基于用戶對(duì)數(shù)據(jù)流語義的理解，并使用可控的方法來拋棄不重要或相對(duì)不重要的元組。自適應(yīng)降載引入一組服務(wù)質(zhì)量(Quality-of-Service, QoS)[1,3,5]或決策質(zhì)量(Quality of Decision, QoD)[2-3]規(guī)范，該策略對(duì)數(shù)據(jù)流及其運(yùn)行環(huán)境的變化具有重要的適應(yīng)能力，將降載問題轉(zhuǎn)化為優(yōu)化問題。

目前，降載的研究主要集中在數(shù)據(jù)流管理系統(tǒng)(Data Stream Management System, DSMS)[5]中的連續(xù)查詢[1-2]和流數(shù)據(jù)挖掘[11]2大方面。降載的代表性工作如下：Tatbul等人[1]研究了可擴(kuò)展和有效的SPEs降載技術(shù)。Babcock等人[3]提出在查詢計(jì)劃的不同位置引入降載操作符和降載程序。Gedik等人[8]提出一種針對(duì)加窗流連接的自適應(yīng)CPU降載方法，旨在最大化流連接的輸出速率。Chi等人[2]引入QoD規(guī)范來度量由降載引起的無法準(zhǔn)確獲得數(shù)據(jù)的特征值時(shí)分類結(jié)果的不確定性程度。陳華輝等人[12]提出H-WAS-clustering算法，該算法利用小波變換系數(shù)來計(jì)算距離和劃分?jǐn)?shù)據(jù)，對(duì)多個(gè)數(shù)據(jù)流進(jìn)行聚類、壓縮數(shù)據(jù)，降低了空間和時(shí)間復(fù)雜度。時(shí)間序列建模是研究歷史時(shí)間序列，以建立適當(dāng)?shù)哪Ｐ蛠砻枋鲈撔蛄械墓逃薪Y(jié)構(gòu)，然后利用該模型預(yù)測(cè)該序列未來的值。自回歸差分移動(dòng)平均(AutoRegressive Integrated Moving Average, ARIMA)模型是最常用的隨機(jī)時(shí)間序列模型之一[13-14]。

在本文工作中，使用DTW距離度量子序列與整個(gè)序列之間相似度的變化以確定用于預(yù)測(cè)的數(shù)據(jù)，然后利用小波變換計(jì)算小波系數(shù)并提取小波系數(shù)的能量值作為預(yù)測(cè)的特征，最后預(yù)測(cè)任務(wù)執(zhí)行時(shí)間。預(yù)測(cè)數(shù)據(jù)挖掘任務(wù)執(zhí)行時(shí)間的實(shí)驗(yàn)結(jié)果表明該方法有較高的準(zhǔn)確性。

1 小波變換和特征提取

1.1 小波變換

小波變換[10,15-20]是一種層次分解序列的時(shí)域變換技術(shù)，是一種時(shí)頻局部化或時(shí)頻定位的工具，其良好的多分辨率特性特別適用于對(duì)非平穩(wěn)信號(hào)分析和處理及構(gòu)造數(shù)據(jù)摘要。小波的特點(diǎn)是在近似部分保留輸入序列的大趨勢(shì)，而在細(xì)節(jié)部分保留局部變化。Haar小波是小波分析發(fā)展過程中出現(xiàn)最早的小波，其實(shí)質(zhì)上是一階的Daubechies小波，也是最簡(jiǎn)單的具有緊致特性的顯式正交小波。其母小波函數(shù)和尺度函數(shù)定義如公式(1)和公式(2)所示：

(1)

(2)

規(guī)范化的Haar小波尺度函數(shù)如公式(3)：

(3)

其中j為尺度因子，改變j使函數(shù)圖形縮小或放大；i為平移參數(shù)，改變i使函數(shù)沿x軸方向平移；常數(shù)因子用以滿足內(nèi)積等于1的條件。

1.2 特征提取

特征提取是指從數(shù)據(jù)中提取有用特征的降維或函數(shù)映射過程[21]。特征提取、選擇和構(gòu)造是選擇數(shù)據(jù)或?qū)嵗葦?shù)據(jù)簡(jiǎn)約的有效方法，其目標(biāo)是：1)減少數(shù)據(jù)量；2)關(guān)注相關(guān)數(shù)據(jù)；3)提高數(shù)據(jù)質(zhì)量。要提高挖掘算法性能，主要依靠挖掘算法或在挖掘前進(jìn)行預(yù)處理2種方法。

時(shí)間序列[18]的應(yīng)用中有多種特征提取算法，如奇異值分解(Singular Value Decomposition, SVD)、離散傅里葉變換(Discrete Fourier Transform, DFT)和離散小波變換(DWT)等。SVD計(jì)算的時(shí)間復(fù)雜度很高，DFT和DWT都是具有快速的計(jì)算算法的信號(hào)處理技術(shù)，DWT將原來的時(shí)間序列從時(shí)域轉(zhuǎn)換為頻域，再由頻域轉(zhuǎn)換為時(shí)頻域[18]。小波變換時(shí)間序列的時(shí)頻局部化特性意味著時(shí)間序列的大部分能量可以用幾個(gè)小波系數(shù)來表示。

2 Wavelet-based特征提取算法

任務(wù)執(zhí)行時(shí)間不僅與任務(wù)參數(shù)相關(guān)，還與執(zhí)行過程中的其他數(shù)據(jù)密切相關(guān)，如服務(wù)器的資源狀態(tài)數(shù)據(jù)(CPU、I/O、內(nèi)存和系統(tǒng)負(fù)載等)、任務(wù)狀態(tài)數(shù)據(jù)等。結(jié)合任務(wù)執(zhí)行過程中的任務(wù)參數(shù)和狀態(tài)數(shù)據(jù)預(yù)測(cè)任務(wù)執(zhí)行時(shí)間可以得到更好的結(jié)果。算法分為2階段：1)引入?yún)?shù)度量降載時(shí)間點(diǎn)；2)利用小波變換進(jìn)行特征提取。

2.1 度量降載時(shí)間點(diǎn)

時(shí)間序列有很強(qiáng)的連續(xù)性，不適合進(jìn)行分段處理。分析時(shí)間序列數(shù)據(jù)，不僅要關(guān)注某一點(diǎn)，還要關(guān)注連續(xù)點(diǎn)和連續(xù)序列的特征，如均值、方差、偏度、峰度、波動(dòng)性等。這些點(diǎn)形成一個(gè)窗口或向量，窗口的大小隨著數(shù)據(jù)的增加而增加；然而，連續(xù)時(shí)間序列中大多數(shù)數(shù)據(jù)點(diǎn)不是獨(dú)立的而是相互關(guān)聯(lián)的，因此會(huì)存在一定的信息冗余，所以對(duì)多個(gè)窗口預(yù)測(cè)并不合適[11]。使用任務(wù)執(zhí)行期間不同數(shù)據(jù)進(jìn)行預(yù)測(cè)，結(jié)果差異非常大，所以需要度量預(yù)測(cè)所使用的數(shù)據(jù)。

整個(gè)序列記為X(X=〈x1,x2,…,xi〉)。引入?yún)?shù)α(α∈(0,1))來衡量預(yù)測(cè)的位置，參數(shù)α將整個(gè)序列X等分為i個(gè)子序列，使用DTW距離[20,22-24]測(cè)量子序列和整個(gè)序列的相似度。參數(shù)α定義如公式(4)，其中l(wèi)ength()表示序列的長(zhǎng)度。Qj為從原序列初始位置取特定比例后的子序列，其定義如公式(5)，其中j∈[0,i],j∈Z。

α=length(xi)/length(X)

(4)

Qj=〈p0,p1,…,pj〉

(5)

設(shè)時(shí)間序列X、Y的DTW距離為D(X,Y)，定義如公式(6)所示，其中，Dbase(xi,yi)表示向量點(diǎn)xi和yi之間的基距離，記D0(xi,yi)為D0。可以根據(jù)情況選擇不同的距離度量，為不失一般性，使用歐氏距離作為基距離。

(6)

使用相似度的變化來度量降載的時(shí)間點(diǎn)：通過捕捉時(shí)間序列相似性的變化，實(shí)現(xiàn)序列相似度變化的離散化并度量預(yù)測(cè)的時(shí)間點(diǎn)。因相似度距離的變化是連續(xù)的，如果對(duì)每個(gè)時(shí)間點(diǎn)都進(jìn)行計(jì)算會(huì)導(dǎo)致復(fù)雜度太高，因而對(duì)參數(shù)α進(jìn)行多窗口大小局部平均處理，這樣可以離散化時(shí)間序列相似度的變化。算法1展示了度量降載時(shí)間點(diǎn)算法的細(xì)節(jié)。

算法1度量降載時(shí)間點(diǎn)。

輸出: 參數(shù)α的取值范圍

1: forl=1 tomdo

2: forj=1 toido

3:Qj=〈p0,p1,…,pj〉

6: end for

7: end for

8: for策略t∈window,l∈[1,m]do

9: 根據(jù)策略t將distancel劃分為n部分，距離結(jié)果集記為{re}

10: 歸一化{re}到[0,1]范圍內(nèi)

11: 根據(jù)不同窗口大小window策略統(tǒng)計(jì)頻繁模式

12: 返回參數(shù)α的取范圍

該策略記為window(win)(win是窗口的大小)，根據(jù)窗口的大小定義3種策略取3種窗口內(nèi)的平均值來捕捉序列相似度變化模式的分割方法，如公式(7)所示：

(7)

為比較不同序列以及獲得不同策略下所有數(shù)據(jù)的變化模式，將每種策略的相似度距離計(jì)算結(jié)果進(jìn)行歸一化，將最小值和最大值映射到[0,1]。模式集中位置i處的模式定義如式(8)，其中h、m、l分別表示High、Middle、Low：

A=〈A1,A2,A3〉,Ai∈{h,m,l}

(8)

圖1 不同窗口大小下模式集的占比

模型集A在3個(gè)位置上的組合模型共27個(gè)(33)。通過對(duì)結(jié)果集進(jìn)行處理和分析，頻繁模式主要集中在以下模式中，這些模式隨α增加相似度距離變化的趨勢(shì)可劃分為以下模式集，包括Hml(〈h,m,l〉)、Hhl(〈h,h,m〉,〈h,h,l〉,〈m,m,l〉)、Hll(〈h,m,m〉，〈h,l,l〉,〈m,l,l〉)和Oth，統(tǒng)計(jì)結(jié)果如圖1所示。Hml表示相似度逐漸增大的模式；Hhl表示相似度先穩(wěn)定后增加的模式集；Hll表示相似度先增加后穩(wěn)定的模式集；Oth表示剩余的沒有共同特征的模式集。圖1是模式集的特征與分析統(tǒng)計(jì)結(jié)果，取所有數(shù)據(jù)序列的平均值作為最終結(jié)果。

不同大小的窗口下模式集的占比結(jié)果如圖1所示，超過90%的數(shù)據(jù)顯示出明顯的下降趨勢(shì)。圖2顯示stage1階段相似度的變化較快，stage3階段相似度的變化較緩，在stage2與stage3序列的相似度更高。通過統(tǒng)計(jì)模式集Hml與Hhl距離的變化，可以得出結(jié)論：與stage1相比stage2部分子序列與整個(gè)序列的距離明顯減小。

圖2 模式集Hml和Hhl距離的變化

數(shù)據(jù)挖掘任務(wù)的主要操作部分耗時(shí)較多且占用CPU資源較多。根據(jù)圖1中相似度變化的統(tǒng)計(jì)分析結(jié)果和任務(wù)執(zhí)行日志分析結(jié)果，stage3階段任務(wù)多位于預(yù)測(cè)、可視化和保存數(shù)據(jù)階段，該部分不會(huì)持續(xù)占用較高的CPU資源，而在stage1和stage2階段任務(wù)多位于比較消耗CPU的核心操作階段(核心操作AutoML、k-Means、GBDT階段)，從任務(wù)開始時(shí)選取特定比例(α)的數(shù)據(jù)用于預(yù)測(cè)，該部分包含了資源指標(biāo)數(shù)據(jù)相對(duì)于全部數(shù)據(jù)中相似度變化較大的部分，說明該部分?jǐn)?shù)據(jù)包含了較多的變化信息，所以選取這部分?jǐn)?shù)據(jù)用于預(yù)測(cè)可以降低預(yù)測(cè)的誤差。在α∈[0.3,0.7]或α∈[0.4,0.6]時(shí)子序列與原序列相似度的變化較大且包含相似度距離變化較快的stage1、stage2階段，根據(jù)以上分析結(jié)果，選擇stage2進(jìn)行預(yù)測(cè)更為合適。

2.2 Wavelet-based特征提取算法

根據(jù)2.1節(jié)中確定的α的取值范圍以及用于預(yù)測(cè)的數(shù)據(jù)，提出一種面向預(yù)測(cè)基于小波變換的特征提取方法。

(9)

算法2Wavelet-based特征提取方法。

輸出: 時(shí)間序列在不同尺度上的特征

1: fori=1tomdo

2: 使用Haar小波計(jì)算時(shí)間序列最大尺度J

3: 將不夠長(zhǎng)度2j的時(shí)間序列補(bǔ)0

4: forj=0 toJ-1 do

7: end for

8: end for

3 實(shí)驗(yàn)結(jié)果和評(píng)估

3.1 實(shí)驗(yàn)設(shè)置

負(fù)載。本實(shí)驗(yàn)中的工作負(fù)載包括一系列基于工作流的數(shù)據(jù)挖掘(DM)和ETL任務(wù)。DM任務(wù)主要包括輸入、AutoML、K-means、GBDT、采樣、預(yù)測(cè)、數(shù)據(jù)可視化、結(jié)果保存等操作，主要操作是CPU密集型任務(wù)，其數(shù)據(jù)集是UCI數(shù)據(jù)集，因標(biāo)準(zhǔn)數(shù)據(jù)集數(shù)據(jù)量小，需要擴(kuò)增數(shù)據(jù)量(150～100000)，使DM任務(wù)可達(dá)到高負(fù)載狀態(tài)。用Java程序調(diào)整用戶數(shù)來控制任務(wù)并發(fā)，并設(shè)置采樣器的參數(shù)來控制數(shù)據(jù)量和任務(wù)中訓(xùn)練集與測(cè)試集的比例等。ETL任務(wù)包括使用TPC-H數(shù)據(jù)集進(jìn)行轉(zhuǎn)換、連接等操作，此任務(wù)主要用于調(diào)整服務(wù)器可用CPU、內(nèi)存和I/O資源狀態(tài)。本文使用多種數(shù)據(jù)收集方法(包括流數(shù)據(jù)處理方法，如Kafka)收集任務(wù)屬性數(shù)據(jù)、服務(wù)器資源狀態(tài)數(shù)據(jù)和任務(wù)狀態(tài)數(shù)據(jù)。

本文使用隨機(jī)森林算法來評(píng)估基于任務(wù)參數(shù)方法(Task-parameters)和以下3種特征提取方法(Statistical, Wavelet-based, Wavelet-sta)的預(yù)測(cè)結(jié)果。為了得到更可靠實(shí)驗(yàn)結(jié)果，采用5折交叉驗(yàn)證法，即將數(shù)據(jù)集平均分成5份，隨機(jī)選擇其中1份作為測(cè)試數(shù)據(jù)，其余的作為訓(xùn)練數(shù)據(jù)，并且取5次的平均值作為最終的結(jié)果。Task-parameters：使用任務(wù)數(shù)據(jù)量、并發(fā)數(shù)、主要操作的重要參數(shù)作為特征。Statistical：計(jì)算時(shí)間序列的一階原點(diǎn)矩(均值)、二階中心矩(方差)和三階中心矩(偏度)作為統(tǒng)計(jì)特征。Wavelet-based：利用第2章提出的基于小波變換的特征提取方法提取時(shí)間序列特征。Wavelet-sta：將Statistical與Wavelet-based方法相結(jié)合提取時(shí)間序列特征。

3.2 預(yù)測(cè)結(jié)果

根據(jù)任務(wù)數(shù)據(jù)量、并發(fā)數(shù)、主要操作的重要參數(shù)(迭代次數(shù)、學(xué)習(xí)率、樹的數(shù)量、訓(xùn)練集測(cè)試集比例(數(shù)據(jù)挖掘任務(wù)中訓(xùn)練集測(cè)試集比例))將數(shù)據(jù)集劃分為D1和D2，主要原則是保證劃分的數(shù)據(jù)集有一定的區(qū)分度以及保證劃分的數(shù)據(jù)集在進(jìn)行實(shí)驗(yàn)時(shí)訓(xùn)練集和測(cè)試集中不會(huì)出現(xiàn)重復(fù)數(shù)據(jù)。其中，任務(wù)執(zhí)行時(shí)間從幾十秒到1600 s不等，平均執(zhí)行時(shí)間約400 s。為驗(yàn)證不同特征提取方法的預(yù)測(cè)結(jié)果的準(zhǔn)確性，使用均方根誤差(RMSE)、平均絕對(duì)誤差(MAE)和確定系數(shù)(R2，回歸中R2是回歸預(yù)測(cè)與真實(shí)數(shù)據(jù)近似程度的統(tǒng)計(jì)度量)來驗(yàn)證隨機(jī)森林算法的準(zhǔn)確性。

Task-parameters方法在數(shù)據(jù)集D1和D2的預(yù)測(cè)結(jié)果評(píng)估指標(biāo)如表1所示。3種特征提取方法在數(shù)據(jù)集D1、D2與參數(shù)α條件下的預(yù)測(cè)結(jié)果的評(píng)估指標(biāo)如表2所示。

表1 僅使用任務(wù)參數(shù)在數(shù)據(jù)集D1和D2預(yù)測(cè)結(jié)果的評(píng)估指標(biāo)

DatasetMethodsRMSEMAER2D1Task-parameters1281030.38D2Task-parameters12798.30.667

比較不同參數(shù)和數(shù)據(jù)集的預(yù)測(cè)結(jié)果，可以得出以下結(jié)論：僅使用任務(wù)參數(shù)在數(shù)據(jù)集D1和D2的預(yù)測(cè)結(jié)果誤差較大且與原始數(shù)據(jù)吻合度較低；在任務(wù)執(zhí)行過程中使用資源和任務(wù)參數(shù)數(shù)據(jù)的可以很大程度減少預(yù)測(cè)誤差。在相同數(shù)據(jù)量的情況下，Wavelet-based方法和Wavelet-sta方法比Statistical方法可得到更好的效果。從表1和表2可以得出，在相同的數(shù)據(jù)集下這3種特征提取方法的預(yù)測(cè)誤差比使用Task-parameters方法要小很多。

表2 3種特征提取方法在數(shù)據(jù)集D1和D2與參數(shù)α條件下預(yù)測(cè)結(jié)果的評(píng)估指標(biāo)

DatasetαMethodsRMSEMAER2D10.40.50.6Statistical69.753.50.81Wavelet-based18120.98Wavelet-sta13100.99Statistical72550.80Wavelet-based20130.98Wavelet-sta15120.99Statistical72.856.80.80Wavelet-based159.20.99Wavelet-sta1280.99D20.40.50.6Statistical92.464.70.82Wavelet-based35160.97Wavelet-sta28.5140.98Statistical95.7660.81Wavelet-based37180.97Wavelet-sta3115.50.98Statistical97.3670.80Wavelet-based41210.965Wavelet-sta3317.60.977

表2中，比較當(dāng)數(shù)據(jù)集為D1、α=0.4時(shí)RMSE與MAE的數(shù)值可得出如下結(jié)論：Wavelet-based和Wavelet-sta方法比Statistical方法有更小的預(yù)測(cè)誤差；比較R2可以得出Wavelet-based和Wavelet-sta方法預(yù)測(cè)結(jié)果與原數(shù)據(jù)擬合效果比Statistical方法好很多。比較當(dāng)數(shù)據(jù)集為D1、α=0.4時(shí)RMSE、MAE與R2的數(shù)值，Wavelet-sta方法的預(yù)測(cè)結(jié)果比Wavelet-based有一定程度的提升。因此，將Statistical與Wavelet-based方法相結(jié)合可以進(jìn)一步降低預(yù)測(cè)誤差。表2中數(shù)據(jù)集為D1時(shí)，實(shí)驗(yàn)結(jié)果的RMSE和MAE相對(duì)于比Task-parameters方法有很大程度的減小，同時(shí)R2提高了很多；隨著α的增加，結(jié)果誤差和擬合系數(shù)都在較小的誤差范圍內(nèi)波動(dòng)。當(dāng)數(shù)據(jù)集為D2時(shí)，可以得到以上類似的結(jié)論。綜合以上結(jié)論，新提出的特征提取方法是有效的；在預(yù)測(cè)結(jié)果方面，降低了誤差，顯著提高了預(yù)測(cè)結(jié)果與原始數(shù)據(jù)的擬合程度，驗(yàn)證了特征提取方法和降載策略的有效性。

4 結(jié)束語

在分析型系統(tǒng)任務(wù)執(zhí)行過程中，任務(wù)執(zhí)行時(shí)間不僅與任務(wù)參數(shù)相關(guān)，而且與執(zhí)行過程中的約束條件(如資源利用率、任務(wù)狀態(tài)數(shù)據(jù))密切相關(guān)。在任務(wù)結(jié)束后進(jìn)行任務(wù)執(zhí)行時(shí)間預(yù)測(cè)毫無意義，需要在任務(wù)執(zhí)行前或執(zhí)行過程中進(jìn)行預(yù)測(cè)。在任務(wù)執(zhí)行過程中，結(jié)合狀態(tài)數(shù)據(jù)和任務(wù)參數(shù)來預(yù)測(cè)任務(wù)執(zhí)行時(shí)間可以得到較好的結(jié)果。本文使用DTW距離來度量子序列和整個(gè)序列之間的相似性變化，從而確定用于預(yù)測(cè)的數(shù)據(jù)和時(shí)間點(diǎn)；利用小波變換計(jì)算時(shí)間序列的小波系數(shù)，提取小波系數(shù)的能量值作為預(yù)測(cè)的特征。數(shù)據(jù)挖掘任務(wù)執(zhí)行時(shí)間預(yù)測(cè)真實(shí)場(chǎng)景的實(shí)驗(yàn)結(jié)果表明了該策略的有效性。