湯其婕，朱小萍

(南京航空航天大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 南京 211106)

0 引 言

時間序列(time series)是一種典型的高維數(shù)據(jù)類型，也是數(shù)據(jù)挖掘[1-2]領(lǐng)域中主要研究的對象。一條時間序列是一組序列數(shù)據(jù)，它通常是在相等間隔的時間段內(nèi)，依照給定的采樣率，對某種潛在過程進(jìn)行觀測的結(jié)果。它廣泛存在于工業(yè)、農(nóng)業(yè)及商業(yè)等領(lǐng)域，與人們的生活息息相關(guān)。其典型數(shù)據(jù)包括航天飛船等重要儀器每一時刻的運(yùn)行狀態(tài)數(shù)據(jù)、醫(yī)療設(shè)備記錄的病人每時每刻的心率變化等。研究如何有效地從這些復(fù)雜的海量時間序列中挖掘潛在的有用信息，具有重要的理論價值與現(xiàn)實(shí)意義[3-4]。

在實(shí)際生產(chǎn)生活中，時間序列的產(chǎn)生通常受不確定因素的影響，如數(shù)據(jù)采集設(shè)備的缺陷和環(huán)境影響，導(dǎo)致數(shù)據(jù)采集與實(shí)際數(shù)據(jù)有一定的偏差；或者出于隱私安全考慮，人為地將一定程度的偏差引入到數(shù)據(jù)中。這些偏差導(dǎo)致時間序列在每一個點(diǎn)上的取值對應(yīng)一個可能值的集合，無法給出其確定值。將這類型的數(shù)據(jù)定義為不確定時間序列。加之時間序列本身具有的海量、高維等特征，若直接對原始不確定數(shù)據(jù)進(jìn)行數(shù)據(jù)挖掘等操作，效率很低。而解決這一問題最直接的方法就是對原始數(shù)據(jù)進(jìn)行預(yù)處理操作。但是由于不確定時間序列與確定時間序列在取值上的不同之處，原有用于確定時間序列上的方法則不適用于不確定時間序列。因此，結(jié)合已有的針對確定數(shù)據(jù)的處理方法，找到適用于不確定時序數(shù)據(jù)的預(yù)處理方法，是目前針對不確定時間序列研究的重點(diǎn)，也是文中主要研究的問題。

文中主要研究了基于關(guān)鍵點(diǎn)的線性降維算法與統(tǒng)計模型相結(jié)合的不確定時間序列線性降維問題。首先對不確定時間序列進(jìn)行有效的描述統(tǒng)計建模，將不確定時間序列歸約為三條確定的時間序列，進(jìn)行空間維度的一次降維；然后分別對三條確定時間序列進(jìn)行關(guān)鍵點(diǎn)的選取，進(jìn)行時間維度的二次降維；最后，綜合空間維度和時間維度的兩次降維，得到整個不確定時序數(shù)據(jù)集的關(guān)鍵點(diǎn)，完成整個降維工作。

1 相關(guān)工作

1.1 線性表示的提出

針對確定時間序列的預(yù)處理，已有許多成熟的方法，如傅里葉變換[5](DFT)、離散小波變換[6](DWT)、奇異值分解[7](SVD)等等。以上幾種方法在某些方面具有明顯的優(yōu)勢，但是也存在不足。例如，傅里葉變換、離散小波變換存在一個共同缺點(diǎn)，即過度除噪。消除了局部極值點(diǎn)，造成重要信息遺失，數(shù)據(jù)表示誤差較大；奇異值分解法依賴數(shù)據(jù)，該方法由于使用數(shù)據(jù)集產(chǎn)生新的基向量，數(shù)據(jù)項(xiàng)的任何改變都需要重新計算，時間復(fù)雜度大?；谝陨蠋追N算法的不足，時間序列線性表示[8-9]方法被提出，其主要目的是有效地保留數(shù)據(jù)的主要特征，對數(shù)據(jù)進(jìn)行高效的降維處理。

1.2 傳統(tǒng)時間序列的線性表示

傳統(tǒng)的時間序列線性表示方法的主要思想就是用一系列前后相互連接的線段近似表示原始數(shù)據(jù)，其關(guān)鍵之處在于分段點(diǎn)的選用[10]。線性表示在時間序列的應(yīng)用上有如下幾個優(yōu)點(diǎn)：理論簡單，實(shí)現(xiàn)容易；壓縮率可以調(diào)整。既保留數(shù)據(jù)的特點(diǎn)，又進(jìn)行有效的降維。近年來，國內(nèi)外許多學(xué)者對線性表示方法進(jìn)行了深入研究，提出了許多優(yōu)秀的線性表示方法。文獻(xiàn)[11-12]各自獨(dú)立提出了分段聚合近似(PAA)的時間序列線性表示方法，該方法的主要思想是首先將時間序列按照相同的時間跨度進(jìn)行劃分，然后以每個時間序列子段的平均值來近似表示相應(yīng)子段。文獻(xiàn)[8]介紹了一種基于重要點(diǎn)的線性表示方法(PLR-IP),即如果一個點(diǎn)在局部區(qū)間內(nèi)與區(qū)間端點(diǎn)的比值超過設(shè)定的閾值R，則認(rèn)為它是重要點(diǎn)。通過調(diào)節(jié)閾值R，可以獲得不同精度的線性表示。文獻(xiàn)[9]介紹了基于特征點(diǎn)的線性表示方法(PLR-FP)，該方法的思想是首先提取時間序列的極值點(diǎn)，然后根據(jù)每個極值點(diǎn)保持的時間跨度去除噪聲點(diǎn)。文獻(xiàn)[13]介紹了一種基于斜率提取邊緣點(diǎn)的時間序列線性表示方法(PLR-SEEP)，該方法的主要思想是首先設(shè)定閾值，然后根據(jù)斜率變化選取分段點(diǎn)。

2 不確定時間序列描述統(tǒng)計模型建模

不確定時間序列與傳統(tǒng)時間序列相比，主要的不同之處在于每個時間點(diǎn)的取值。前者是一個取值的集合，且每一個數(shù)值對應(yīng)該數(shù)值在該時間戳發(fā)生的概率，后者是一個確定的數(shù)值。因此，針對傳統(tǒng)時間數(shù)據(jù)對數(shù)值的處理，需要轉(zhuǎn)換為對集合的處理。

定義1(集中趨勢)：在描述統(tǒng)計學(xué)中，觀察值在分布中心位置的聚集現(xiàn)象稱為分布的集中趨勢，一個分布中心特征的統(tǒng)計度量稱為集中趨勢的度量。數(shù)據(jù)集中，平均值是最常用、最具代表性的度量。其中，算數(shù)平均值，是整體數(shù)學(xué)期望的無偏估計。大數(shù)定律規(guī)定，隨著重復(fù)次數(shù)接近無窮大，數(shù)值的算術(shù)平均值幾乎肯定地收斂于期望值(expected value)。因此，文中選擇觀察值集合的期望值作為觀察值的集中趨勢度量，記為vt,ey，表示不確定時序數(shù)據(jù)的集中趨勢。例如，給定某一時間點(diǎn)的觀察值及對應(yīng)的概率{(5,0.3),(6,0.4),(7,0.2),(8,0.1)}，則該點(diǎn)的集中趨勢為5×0.3+6×0.4+7×0.2+8×0.1=6.1。

定義2(MME-Line不確定時間序列)：長度為n的MM-Line不確定時間序列由一條包含n個元素的序列構(gòu)成，記為：

TSUMME-Line={([v1,min,v1,max],v1,ev),([v1,min,v1,max],v1,ev),…,([vn,min,vn,max],vn,ev)}

(1)

其中，每個元素是一個二元組，由該時刻的觀察值區(qū)間及其集中趨勢組成；ti表示第i個時刻，序列中所有時刻的最大觀察值所構(gòu)成的序列叫作最大值序列，其相連之后所得曲線叫作最大值曲線，記為Max-Line。同樣，所有最小觀察值構(gòu)成最小值序列，相連后曲線記為Min-Line；所有集中趨勢構(gòu)成集中趨勢序列，記為EV-Line。例如，不確定時間序列TSUMME-Line={([2.5,4.2]，3.3)，([3.6,7.9]，5.5)，([4.5,9.2]，7.6)，([3.8,7.2]，6.2)，([6.0,10.8]，8.3)，([5.1,9.6]，9.6)}，所有最大觀察值(3.3,7.9,9.2,7.2,10.8,9.6)構(gòu)成Max-Line序列，所有最小值(2.5,3.6,4.5,3.8,6.0,5.1)構(gòu)成Min-Line序列，所有集中趨勢(3.3,5.5,7.6,6.2,8.3,9.6)構(gòu)成EV-Line序列。

定義3(MME-Line描述統(tǒng)計模型)：不確定時間序列描述統(tǒng)計模型包括三條等長的確定時間序列：Max-Line、Min-Line和EV-Line。因此，不確定時間序列MME-Line的向量形式表示如下：

(2)

其中，XMax-Line為Max-Line序列；XMin-Line為Min-Line序列；XEV-Line為集中趨勢序列。

由此，對不確定時間序列的降維可以歸約為對這三條確定時間序列的降維。

3 基于關(guān)鍵點(diǎn)的不確定時間序列線性降維

3.1 選取關(guān)鍵點(diǎn)

關(guān)鍵點(diǎn)是反映時間序列數(shù)據(jù)特征的重要點(diǎn)，也是對時序數(shù)據(jù)進(jìn)行分段的點(diǎn)，體現(xiàn)了時間序列的輪廓和集中趨勢。如圖1所示，圖中1、2處的關(guān)鍵點(diǎn)是典型的極值點(diǎn)，其可以通過極值法求出；但3～5處的轉(zhuǎn)折點(diǎn)并不能通過極值法求出，而文獻(xiàn)[8]證明，該類型的點(diǎn)在時間序列數(shù)據(jù)集中也是包含大量重要信息的數(shù)據(jù)點(diǎn)。文中關(guān)鍵點(diǎn)的選擇包括極值點(diǎn)和轉(zhuǎn)折點(diǎn)兩部分。

圖1 關(guān)鍵點(diǎn)舉例

定義4(轉(zhuǎn)折點(diǎn))：在不超過序列的最大值和最小值下，由三點(diǎn)組成的簡單時間序列，夾角越小，角處的頂點(diǎn)成為轉(zhuǎn)折點(diǎn)的可能性就越大。將該點(diǎn)稱為轉(zhuǎn)折點(diǎn)。

定義5(閾值參數(shù))：由三點(diǎn)組成的時間序列，A、O、B，其端點(diǎn)O是否為轉(zhuǎn)折點(diǎn)，決定于三點(diǎn)數(shù)值是否滿足條件|Data(A)+Data(B)-2*Data(O)|≥C。其中C即是自定義的閾值參數(shù)，其大小決定于所選數(shù)據(jù)的類型，Data(*)表示在時間點(diǎn)*處的數(shù)值。

數(shù)據(jù)的壓縮程度可以通過調(diào)節(jié)閾值參數(shù)來設(shè)置。閾值參數(shù)設(shè)置越大，則數(shù)據(jù)壓縮程度越大；反之，數(shù)據(jù)壓縮程度越小，數(shù)據(jù)分段越精細(xì)。

3.2 選取關(guān)鍵點(diǎn)算法

由3.1可知，關(guān)鍵點(diǎn)的選擇包含極值點(diǎn)和轉(zhuǎn)折點(diǎn)兩部分。通過對描述統(tǒng)計模型中的三條確定時間序列分別進(jìn)行關(guān)鍵點(diǎn)的選取，可以得到三個關(guān)鍵點(diǎn)的集合，分別是Max-Line關(guān)鍵點(diǎn)集合、Min-Line關(guān)鍵點(diǎn)集合和EV-Line關(guān)鍵點(diǎn)集合。算法的具體過程如下。

算法：MME-KP

輸入：不確定時間序列TSU={(t1,V1,P1),(t2,V2,P2),…,(tn,Vn,Pn)}，閾值參數(shù)C1、C2、C3，時閾參數(shù)T

輸出：三條確定時間序列關(guān)鍵點(diǎn)集合

1 double []MaxNum; double []MinNum; double []EVNum;

2 for(i=0;i<1;i++){

3 sort(Vi);

4 vi,ey=pi,1*vi,1+pi,2*vi,2+…+pi,n*vi,n;

5 MaxNum[i]=vi,max; MinNum[i]=vi,min; EVNum[i]=vi,ey;}

6 ArrayList MaxKP; ArrayList MinKP; ArrayList EVKP;

7 for(i=0;i

8 if(MaxNum[i]是極值點(diǎn)){

9 MaxKP.add(i);

10 }else if(MaxKP[i]是轉(zhuǎn)折點(diǎn) && !MaxKP.contains(i){

11 MaxKP.add(i);

12 }

13 }//MinKP和MaxPV的計算與MaxPV類似

14 MaxKP=getKPArrayList(MaxKP, T); //對關(guān)鍵點(diǎn)進(jìn)行進(jìn)一步篩選，使其滿足時間跨度T

15 MinKP=getKPArrayList(MinKP, T);

16 EVKP=getKPArrayList(EVKP, T);

3.3 算法分析

MME-KP算法首先通過提出的描述統(tǒng)計模型將不確定時間序列歸約為3條確定時間序列，即最大值序列、最小值序列和集中趨勢序列，有效提取了數(shù)據(jù)的三個主要特征。其次，對三條歸約得到的確定時間序列分別進(jìn)行兩遍掃描選取關(guān)鍵點(diǎn)。其中關(guān)鍵點(diǎn)包含了極值點(diǎn)和轉(zhuǎn)折點(diǎn)兩部分，基本保留了數(shù)據(jù)的全部特征。同時，該時間序列線性降維算法綜合考慮了時間跨度的選擇，可以根據(jù)不同數(shù)據(jù)的特點(diǎn)動態(tài)設(shè)置閾值參數(shù)C和時閾參數(shù)T，改變數(shù)據(jù)選取的精細(xì)程度和數(shù)據(jù)的壓縮度。綜上，該算法既能較好地保留時序數(shù)據(jù)的特征關(guān)鍵點(diǎn)，同時又能有效降維。算法的復(fù)雜度為O(n),n為時間序列的長度[14]。

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

4.1 實(shí)驗(yàn)?zāi)康暮蛯?shí)驗(yàn)環(huán)境

為了驗(yàn)證文中提出的基于關(guān)鍵點(diǎn)的線性降維算法與描述統(tǒng)計模型相結(jié)合的實(shí)際效果，選取了10個不同領(lǐng)域的時間序列數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)以壓縮率和擬合誤差作為評價優(yōu)劣的指標(biāo)，將MME-KP算法與PAA算法以及PLR-FP算法進(jìn)行對比。

(3)

擬合誤差是用來衡量擬合時間序列與原始時間序列差異性的一個重要指標(biāo)。在同等壓縮率的情況下，擬合誤差越小，表示擬合效果越好，擬合數(shù)據(jù)越接近真實(shí)數(shù)據(jù)。

4.2 實(shí)驗(yàn)數(shù)據(jù)處理

確定時間序列是一組按時間先后順序排列的精確數(shù)據(jù)，這些數(shù)據(jù)通過加入擾動成為不確定化數(shù)據(jù)，由此成為不確定時間序列。給定某一時刻i，不確定時間序列在該時刻的值可表示為：

Vi=di+ei

(4)

其中，di為確定時間序列i時刻的精確值；ei為該時刻誤差，通常服從某種概率分布。

文中實(shí)驗(yàn)數(shù)據(jù)取自于www.cs.ucr.edu/～eamonn/tutorials.html公布的用于數(shù)據(jù)挖掘的通用實(shí)驗(yàn)數(shù)據(jù)集(KP-Data)，如表1所示。將每個數(shù)據(jù)集的訓(xùn)練子集和測試子集重新配置整合，獲得實(shí)驗(yàn)數(shù)據(jù)集。同時，通過不確定化模型將不確定性引入到確定序列中，人為加入擾動形成誤差ei，并使ei服從某種分布，從而將序列轉(zhuǎn)化成不確定時間序列。

表1 KP-Data數(shù)據(jù)集

4.3 實(shí)驗(yàn)方法

實(shí)驗(yàn)主要分為兩部分：

(1)將原始數(shù)據(jù)進(jìn)行統(tǒng)計模型建模，每種類型的數(shù)據(jù)將分別建模得到三條確定時間序列數(shù)據(jù)：最大值序列、最小值序列和集中趨勢序列；

(2)在步驟1建立的模型基礎(chǔ)上，分別用提出的MME-KP算法、Yi和Keogh提出的分段聚集近似(PAA)線性表示方法，以及文獻(xiàn)[9]提出的PLR-FP線性表示方法對數(shù)據(jù)分別進(jìn)行處理，得到整個不確定時序數(shù)據(jù)集的關(guān)鍵點(diǎn)集合。最終以同種壓縮率的標(biāo)準(zhǔn)下擬合誤差的大小作為評估算法質(zhì)量的指標(biāo)。擬合誤差越小，算法性能越好。

4.4 實(shí)驗(yàn)結(jié)果與分析

(1)第一部分。

在提出的統(tǒng)計模型下，部分?jǐn)?shù)據(jù)的建模表示如圖2所示。

(a)Fish原始數(shù)據(jù)圖

(b)StarLightCurves原始數(shù)據(jù)圖

(2)第二部分。

文中提出的MME-KP需要輸入3個閾值參數(shù)：C1、C2和C3，分別對應(yīng)三條確定時間序列，即最大值時間序列、最小值時間序列及集中趨勢時間序列的關(guān)鍵點(diǎn)閾值參數(shù)。參數(shù)設(shè)置越大，數(shù)據(jù)的壓縮率越小，擬合誤差越大；參數(shù)設(shè)置越小，數(shù)據(jù)壓縮率越大，數(shù)據(jù)分段越精細(xì)，擬合誤差越小。實(shí)驗(yàn)選取的數(shù)據(jù)來自10個不同領(lǐng)域，數(shù)據(jù)的差異性較大。為了對比實(shí)驗(yàn)的公平性，將根據(jù)不同數(shù)據(jù)類型調(diào)整參數(shù)，保證在10組數(shù)據(jù)的壓縮率都在50%的基準(zhǔn)下，進(jìn)行三種算法的擬合誤差對比。在同一壓縮率情況下，擬合誤差越小，算法性能越好。

部分實(shí)驗(yàn)結(jié)果如圖3所示。

從圖3中可以看出，在10個通用時間序列數(shù)據(jù)集中，MME-KP算法在其中7個數(shù)據(jù)集上Max-Line擬合序列的誤差最小，在另外三個數(shù)據(jù)集中，誤差與最好的算法相當(dāng)。同時，由圖(b)可以看出，在EV-Line上的擬合誤差，MME-KP算法明顯優(yōu)于其他兩種算法，在10個數(shù)據(jù)集中都保持優(yōu)勢。實(shí)驗(yàn)結(jié)果說明，采用了極值點(diǎn)與轉(zhuǎn)折點(diǎn)相結(jié)合的選取關(guān)鍵點(diǎn)算法，在數(shù)據(jù)降維上具有明顯優(yōu)勢。因?yàn)槠湓诒Ａ袅藰O值點(diǎn)這一數(shù)據(jù)的明顯特征外，還適當(dāng)選取了體現(xiàn)數(shù)據(jù)特征的轉(zhuǎn)折點(diǎn)，減小了一些重要點(diǎn)被粗暴舍棄的概率，提高了數(shù)據(jù)選取的精細(xì)度，從而降低了擬合誤差。

(a)三種算法在Max-Line上擬合誤差的比較

(b)三種算法在ME-Line上擬合誤差的比較

同時實(shí)驗(yàn)結(jié)果顯示：對于短時間內(nèi)波動頻率比較平緩的時間序列，MME-KP算法的實(shí)驗(yàn)效果與其他兩種算法相比，優(yōu)勢并不是很大，如圖4中的對比1所示，MME-KP算法和PAA算法都能較好地擬合MALLAT的原始數(shù)據(jù)。但是對于短時間內(nèi)波動頻率劇烈的時間序列，如圖4中的對比2所示，數(shù)據(jù)在短時間內(nèi)波動較大，MME-KP算法的擬合效果就遠(yuǎn)勝于PAA算法。主要原因是，在短時間內(nèi)，時間序列波動較大，會產(chǎn)生大量極值點(diǎn)，對于以找極值點(diǎn)和轉(zhuǎn)折點(diǎn)為主要關(guān)鍵點(diǎn)的MME-KP算法來說會捕獲大量關(guān)鍵點(diǎn)，從而保證了數(shù)據(jù)主要特征的不流失。而對于PAA算法，它主要思想是以一段時間內(nèi)的數(shù)據(jù)均值來代替這段序列，所以，在短時間內(nèi)時間序列波動較大的情況下，在這段時間內(nèi)的數(shù)據(jù)均值波動并不會很大，相對地，它的擬合序列與原序列相比，就會丟失很多重要點(diǎn)信息，造成擬合誤差較大。

綜上，MME-KP降維方法在與提出的描述統(tǒng)計模型的結(jié)合上，有以下幾點(diǎn)優(yōu)勢：在降維效果上，可以通過參數(shù)的改變，進(jìn)行不同壓縮率的降維。參數(shù)設(shè)置越高，數(shù)據(jù)壓縮程度越大。在現(xiàn)實(shí)應(yīng)用中可以根據(jù)實(shí)際需求選擇所需的降維效果；在與其他線性降維方法PAA以及PLR-FP的比較過程中，MME-KP方法體現(xiàn)出了更為良好的擬合效果，誤差更小，與原始數(shù)據(jù)保持高度的一致性。

圖4 實(shí)驗(yàn)對比

5 結(jié)束語

針對不確定時序數(shù)據(jù)區(qū)別于確定時序數(shù)據(jù)的主要特征，首先提出不確定時間序列向確定時間序列歸約的描述統(tǒng)計模型，同時綜合考慮已有的確定時間序列的線性分段思想，提出綜合考慮極值點(diǎn)與轉(zhuǎn)折點(diǎn)的關(guān)鍵點(diǎn)選取算法。綜合以上兩點(diǎn)，將不確定時序數(shù)據(jù)進(jìn)行空間和時間上的有效降維。實(shí)驗(yàn)結(jié)果表明，該算法在數(shù)據(jù)降維效果上有良好的性能，且能高度還原原始數(shù)據(jù)。下一步的研究工作是在所提出模型的基礎(chǔ)上找到更合適的原始數(shù)據(jù)擬合方案。

猜你喜歡

降維極值關(guān)鍵點(diǎn)

混動成為降維打擊的實(shí)力 東風(fēng)風(fēng)神皓極

車主之友(2022年4期)2022-08-27

論建筑工程管理關(guān)鍵點(diǎn)

建材發(fā)展導(dǎo)向(2022年3期)2022-04-19

基于數(shù)據(jù)降維與聚類的車聯(lián)網(wǎng)數(shù)據(jù)分析應(yīng)用

汽車實(shí)用技術(shù)(2022年4期)2022-03-07

極值(最值)中的分類討論

新世紀(jì)智能(數(shù)學(xué)備考)(2021年10期)2021-12-21

極值點(diǎn)帶你去“漂移”

新世紀(jì)智能(數(shù)學(xué)備考)(2021年10期)2021-12-21

肉兔育肥抓好七個關(guān)鍵點(diǎn)

今日農(nóng)業(yè)(2021年8期)2021-11-28

建筑設(shè)計中的防火技術(shù)關(guān)鍵點(diǎn)

建材發(fā)展導(dǎo)向(2021年11期)2021-07-28

極值(最值)中的分類討論

新世紀(jì)智能(數(shù)學(xué)備考)(2020年10期)2021-01-04

極值點(diǎn)偏移問題的解法

語數(shù)外學(xué)習(xí)·高中版中旬(2020年10期)2020-09-10

Helicobacter pylori-induced inflammation masks the underlying presence of low-grade dysplasia on gastric lesions

World Journal of Gastroenterology(2020年26期)2020-08-17

計算機(jī)技術(shù)與發(fā)展2018年8期

計算機(jī)技術(shù)與發(fā)展的其它文章

卷積神經(jīng)網(wǎng)絡(luò)并行訓(xùn)練的優(yōu)化研究

基于多描述子特征編碼的人體行為識別

基于MPC的可變相序交通信號優(yōu)化控制方法

面向SQLite的TPC-E基準(zhǔn)測試系統(tǒng)的設(shè)計與實(shí)現(xiàn)

基于最大期望算法的蛋白質(zhì)交互關(guān)系識別

基于持續(xù)集成的冒煙測試