湯其婕，王 玙

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

0 引 言

時(shí)間序列(time series)是一種典型的高維數(shù)據(jù)類型，其在傳感器網(wǎng)絡(luò)、位置定位服務(wù)(location based service，LBS)、環(huán)境監(jiān)測(cè)、醫(yī)療檢測(cè)、物聯(lián)網(wǎng)等眾多領(lǐng)域應(yīng)用廣泛[1-2]。但是，受數(shù)據(jù)采集設(shè)備的缺陷或者人為因素的影響，采集得到的數(shù)據(jù)在一定范圍內(nèi)存在偏差。將這類型的數(shù)據(jù)定義為不確定時(shí)間序列(uncertain time series)。而針對(duì)不確定時(shí)間序列的有效存儲(chǔ)，到目前為止仍沒(méi)有良好的解決方案。

一種處理不確定數(shù)據(jù)最有效的方案是概率方法。近年來(lái)許多專家和學(xué)者提出了一系列的方法用于解決不確定數(shù)據(jù)的管理和查詢問(wèn)題[3-9]。這些方法有一個(gè)共同特征，即假定用于進(jìn)行查詢的概率數(shù)據(jù)是已知的，可以直接獲取到。但是，現(xiàn)實(shí)情況并非如此。不確定時(shí)間序列的概率是由推導(dǎo)出這些概率的概率分布函數(shù)決定的，這些概率分布函數(shù)以時(shí)間為坐標(biāo)不斷發(fā)生變化。簡(jiǎn)而言之，不確定時(shí)間序列的概率值隨時(shí)間不斷變化，無(wú)法得到其固定值，因此無(wú)法使用已有的概率數(shù)據(jù)庫(kù)生成方法直接對(duì)其進(jìn)行存儲(chǔ)處理。因此，如何“創(chuàng)造”概率數(shù)據(jù)仍是未解決的問(wèn)題，也是文中主要研究的問(wèn)題。

針對(duì)從已知的時(shí)間序列推導(dǎo)得到時(shí)間序列的概率分布問(wèn)題，文中主要完成的工作分為兩部分。一是依托已有的各種數(shù)學(xué)模型，結(jié)合已有的動(dòng)態(tài)密度指標(biāo)的概念，提出ARMA-GARCH動(dòng)態(tài)密度指標(biāo)模型，并對(duì)其推算原理進(jìn)行了詳細(xì)的分析與介紹；二是針對(duì)GARCH模型無(wú)法高效處理含錯(cuò)數(shù)據(jù)的弊端，提出改進(jìn)的I-GARCH模型。該模型在處理含錯(cuò)數(shù)據(jù)集時(shí)能體現(xiàn)出良好的容錯(cuò)性，更符合一般的不確定時(shí)間序列數(shù)據(jù)的采集規(guī)律。最后通過(guò)實(shí)驗(yàn)進(jìn)行驗(yàn)證。

1 相關(guān)工作

1.1 動(dòng)態(tài)密度指標(biāo)

時(shí)間序列由于依賴時(shí)間的變化，通常呈現(xiàn)出很大的不確定性，因此為不確定時(shí)間序列數(shù)據(jù)創(chuàng)建概率數(shù)據(jù)庫(kù)的最大挑戰(zhàn)之一是處理不斷更新的概率分布。如圖1所示，該圖為一天當(dāng)中的氣溫隨時(shí)間的變化曲線。

圖1 氣溫變化曲線

在臨近日出和日落兩個(gè)時(shí)間點(diǎn)，溫度的變化十分明顯，如A區(qū)域所示，但是在夜間的時(shí)候，整體的溫度變化幅度不大，如B區(qū)域所示。兩處的概率分布規(guī)律明顯不一致。如果用相同的概率分布基來(lái)表示兩處的概率分布，顯然不科學(xué)。因此，應(yīng)該隨著時(shí)間的變化動(dòng)態(tài)地更新用來(lái)表示概率分布的概率分布基，使其符合當(dāng)前數(shù)據(jù)的變化趨勢(shì)。由此，引入了動(dòng)態(tài)密度指標(biāo)的概念。

動(dòng)態(tài)密度指標(biāo)[10]依托多種數(shù)學(xué)模型，可以從一條給定的時(shí)間序列中動(dòng)態(tài)地推算出隨著時(shí)間變化的概率分布。然后，由這些動(dòng)態(tài)密度指標(biāo)推算得到的概率分布就可以用來(lái)創(chuàng)建概率數(shù)據(jù)庫(kù)，完成數(shù)據(jù)的存儲(chǔ)工作。已有的動(dòng)態(tài)密度指標(biāo)介紹如下。

1.2 已有動(dòng)態(tài)密度指標(biāo)

(1)統(tǒng)一閾值指標(biāo)。

Cheng等[11]提出了一個(gè)通用的不確定數(shù)據(jù)的查詢估約框架。它的主要思想是將原始數(shù)據(jù)進(jìn)行建模，將建模得到的數(shù)據(jù)范圍作為對(duì)應(yīng)時(shí)間點(diǎn)數(shù)據(jù)的波動(dòng)范圍。同時(shí)，該范圍也是該時(shí)間點(diǎn)所對(duì)應(yīng)的真正值的所在范圍。然后在計(jì)算出的波動(dòng)范圍中進(jìn)行查詢操作，代替直接在原始值上進(jìn)行查詢。

統(tǒng)一閾值指標(biāo)(uniform thresholding metric，UT)的思想是上述思想的一種擴(kuò)展，即通過(guò)推導(dǎo)得到對(duì)應(yīng)時(shí)間點(diǎn)的一個(gè)“預(yù)期真實(shí)值”，然后以該“預(yù)期真實(shí)值”代表該時(shí)間點(diǎn)的原始真實(shí)數(shù)值，表示該點(diǎn)的概率分布。“預(yù)期真實(shí)值”的定義如下。

(1)

其中，(p,q)是非負(fù)整數(shù)，定義了模型的順序；φ1,φ2,…，φp是自回歸參數(shù)；θ1,θ2,…,θq是移動(dòng)平均參數(shù)；φ0是一個(gè)常量；t>max(p,q)。

(2)可變閾值指標(biāo)。

(2)

2 GARCH指標(biāo)

由上述可知，統(tǒng)一閾值指標(biāo)中u是一個(gè)固定值，這與實(shí)際情況不相符，因?yàn)樵谡鎸?shí)世界中，每個(gè)時(shí)間點(diǎn)的不確定范圍通常不是一個(gè)統(tǒng)一值，而是隨著時(shí)間的變化不斷發(fā)生改變。由圖1可以看出，區(qū)域A數(shù)據(jù)波動(dòng)明顯，而區(qū)域B數(shù)據(jù)波動(dòng)較為平緩。區(qū)域A和區(qū)域B數(shù)據(jù)的波動(dòng)規(guī)律不一致，在進(jìn)行數(shù)據(jù)的表示時(shí)不能使用統(tǒng)一的概率密度方程籠統(tǒng)代替。通過(guò)進(jìn)一步研究發(fā)現(xiàn)，在進(jìn)行一個(gè)概率密度函數(shù)推算時(shí)，底層的描述模型加入均值和時(shí)變方差能夠很好地提高數(shù)據(jù)描述的精度，由此提出了GARCH密度指標(biāo)的概念。

2.1 GARCH模型

(3)

(4)

(5)

1．推算模型ARMA(p,q)，得到ai，其中t-H+max(p,q)≤i≤t-1

2．根據(jù)ai推算模型GARCH(1,1)

4．ub←rt+kσt,lb←rt-kσt

2.2 加強(qiáng)的GARCH模型I-GARCH

在實(shí)際中，時(shí)間序列通常存在噪聲點(diǎn)或者錯(cuò)誤值，例如傳感器錯(cuò)誤、網(wǎng)絡(luò)斷開等。上述提出的GARCH模型只適用于處理數(shù)據(jù)精確的不確定時(shí)間序列，對(duì)于包含錯(cuò)誤數(shù)據(jù)的時(shí)間序列沒(méi)有很好的性能。為了解決這一問(wèn)題，提出了一種加強(qiáng)的GARCH密度指標(biāo)I-GARCH(improved GARCH)。

圖2 ARMA-GARCH和I-GARCH舉例說(shuō)明

3 I-GARCH動(dòng)態(tài)指標(biāo)的改進(jìn)

盡管在現(xiàn)實(shí)中，一條時(shí)間序列連續(xù)出現(xiàn)錯(cuò)誤值的可能性很小，但是為了確保數(shù)據(jù)的精確性，提出了一種新的方法，用來(lái)過(guò)濾I-GARCH模型中的錯(cuò)誤值，稱為錯(cuò)誤值過(guò)濾算法EVF(erroneous value filtering)。

算法的輸入為包含錯(cuò)誤值的時(shí)間序列V=[v1,v2,…，vk]以及閾值參數(shù)DTmax和Emax。具體的實(shí)現(xiàn)步驟如下：

(1)計(jì)算記錄了一條時(shí)間序列V中，兩兩相鄰的數(shù)據(jù)之間的差值；

(2)遍歷差值集合，根據(jù)DTmax判斷該差值是否在允許范圍內(nèi)，如果小于閾值參數(shù)，默認(rèn)該數(shù)值為正確值；如果差值大于閾值，則繼續(xù)遍歷；

(3)如果連續(xù)出現(xiàn)差值超過(guò)閾值的情況，記錄出現(xiàn)的次數(shù)，如果該次數(shù)大于Emax，則認(rèn)為這些連續(xù)的點(diǎn)并非錯(cuò)誤值，而是時(shí)間序列的走勢(shì)發(fā)生了明顯的變化，原始數(shù)值不作變動(dòng)，繼續(xù)向下遍歷；

(4)反之，當(dāng)記錄的次數(shù)在閾值范圍內(nèi)，則說(shuō)明該點(diǎn)為異常點(diǎn)。找到該點(diǎn)在序列中的位置，將其刪除。并通過(guò)線性插值的方法計(jì)算新的值代替原有錯(cuò)誤值。

算法2：EVF

輸入：包含錯(cuò)誤值的時(shí)間序列V，差值閾值DTmax，連續(xù)錯(cuò)誤個(gè)數(shù)閾值Emax

輸出：干凈值序列V

李順過(guò)來(lái)說(shuō)，六如叔，你怎么這么擰呢，社區(qū)開發(fā)那是鄉(xiāng)里開會(huì)訂下的，你那個(gè)合同也不頂事。再說(shuō)，還是人家佟老板救了你，你總不能恩將仇報(bào)吧。

1．ArrayList differList=new ArrayList<>();

2．int differ=0;int count=0;

3．for(int i=1;i

4．differ=abs(vi-vi-1);

5．differList.add(differ);

6．}

7．ArrayList posList=new ArrayList<>();

9．while(i

10．int count=0;

11．while(differList.get(i)

12．while(differList.get(i)>DTmax&& i

13．if(count

14．}

15．for(int i=0;i

16．Vi+1為錯(cuò)誤值將其刪除;

17．使用(vi+vi+2)/2線性插值代替Vi+1;

18．}

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

4.1 實(shí)驗(yàn)?zāi)康?/h3>

實(shí)驗(yàn)?zāi)康闹饕袃蓚€(gè)：驗(yàn)證提出的動(dòng)態(tài)密度指標(biāo)ARMA-GARCH對(duì)于真實(shí)數(shù)據(jù)集有良好的準(zhǔn)確性與高效性；比較ARMA-GARCH與I-GARCH，驗(yàn)證添加了錯(cuò)誤過(guò)濾的I-GARCH模型對(duì)處理包含錯(cuò)誤數(shù)據(jù)的數(shù)據(jù)集的優(yōu)越性。

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

實(shí)驗(yàn)數(shù)據(jù)取自兩個(gè)真實(shí)的數(shù)據(jù)集。一個(gè)是Temperature Dataset，該數(shù)據(jù)集記錄了20天內(nèi)傳感器網(wǎng)絡(luò)監(jiān)測(cè)得到的氣溫變化的所有數(shù)據(jù)，約21 000條樣本數(shù)據(jù)。另一個(gè)數(shù)據(jù)集為GPS Dataset。這個(gè)數(shù)據(jù)集包括從導(dǎo)航系統(tǒng)記錄的192輛車的GPS日志。每一個(gè)日志元組包含時(shí)間和x-y數(shù)值，本實(shí)驗(yàn)只取用其中的x數(shù)值。該數(shù)據(jù)集包含約10 000條數(shù)據(jù)。兩個(gè)數(shù)據(jù)集的詳細(xì)情況如表1所示。

表1 實(shí)驗(yàn)數(shù)據(jù)說(shuō)明

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

(1)動(dòng)態(tài)密度指標(biāo)的衡量。

設(shè)p1(R1),p2(R2),…，pt(Rt)是用動(dòng)態(tài)密度指標(biāo)推導(dǎo)得到的概率分布序列，z1，z2，…，zt為相應(yīng)的概率積分變換值。則只有當(dāng)pt(Rt)等于真正的密度分布pi(Ri)時(shí)，z1，z2，…，zt才會(huì)均勻分布在(0,1)之間。實(shí)驗(yàn)使用直方圖近似法驗(yàn)證z1，z2，…，zt的累計(jì)分布方程，判斷其是否為均勻分布，將其累計(jì)方程定義為Oz(z)，同時(shí)定義在(0,1)上均勻分布的標(biāo)準(zhǔn)累計(jì)方程為Uz(z)。定義Oz(z)和Uz(z)之間的差距為密度距離，表達(dá)式如下：

密度距離可以量化地測(cè)量觀察值分布，z1，z2，…，zt和它們的預(yù)期分布之間的差距，因此可以作為衡量動(dòng)態(tài)密度指標(biāo)的標(biāo)準(zhǔn)。

(2)實(shí)驗(yàn)過(guò)程。

第一部分：動(dòng)態(tài)密度指標(biāo)的比較。

將提出的ARMA-GARCH與統(tǒng)一閾值和可變閾值進(jìn)行比較。所有的評(píng)估都在兩個(gè)數(shù)據(jù)集上進(jìn)行。使用密度距離作為衡量各個(gè)動(dòng)態(tài)密度指標(biāo)質(zhì)量的標(biāo)準(zhǔn)。同時(shí)，也比較了各動(dòng)態(tài)密度指標(biāo)的運(yùn)行效率，以運(yùn)行時(shí)間作為衡量的標(biāo)準(zhǔn)。

第二部分：I-GARCH和ARMA-GARCH的比較，實(shí)驗(yàn)在Temperature Dataset上進(jìn)行驗(yàn)證。為了比較兩個(gè)指標(biāo)對(duì)于處理數(shù)據(jù)的精確性，在原有數(shù)據(jù)中插入人工合成的錯(cuò)誤數(shù)值，即隨機(jī)地在原始數(shù)據(jù)中插入數(shù)值遠(yuǎn)高于或低于正常范圍數(shù)據(jù)的數(shù)值。以捕獲錯(cuò)誤值的數(shù)目和運(yùn)行時(shí)間作為衡量?jī)蓚€(gè)指標(biāo)優(yōu)劣的標(biāo)準(zhǔn)。

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

(1)第一部分的實(shí)驗(yàn)結(jié)果。

圖3 動(dòng)態(tài)密度指標(biāo)比較

圖3顯示了隨著窗口尺寸(H)的增大，各種動(dòng)態(tài)密度指標(biāo)在兩個(gè)數(shù)據(jù)集上的密度距離的比較。從圖中可以明顯看出，MARA-GARCH優(yōu)于原始的動(dòng)態(tài)密度指標(biāo)。

圖4顯示了執(zhí)行一次密度推算迭代所需的平均時(shí)間。由圖中可以看出，雖然ARMA-GARCH的執(zhí)行時(shí)間總體上超出原始動(dòng)態(tài)密度指標(biāo)，但是差距并不明顯，大約在0.2～0.4 s左右?？紤]到其在準(zhǔn)確度和效率上的優(yōu)勢(shì)，ARMA-GARCH仍是性能最好的動(dòng)態(tài)密度指標(biāo)。

圖4 動(dòng)態(tài)密度指標(biāo)效率比較

(2)第二部分的實(shí)驗(yàn)結(jié)果。

圖5 I-GARCH和GARCH的比較

綜上，文中提出的ARMA-GARCH模型及I-GARCH模型與已有的統(tǒng)一閾值指標(biāo)(UT)以及可變閾值指標(biāo)(VT)相比具有很大的優(yōu)勢(shì)，可以準(zhǔn)確地推算出不確定時(shí)間序列的概率密度分布，在準(zhǔn)確度和時(shí)間消耗上優(yōu)勢(shì)明顯；同時(shí)，優(yōu)化了I-GARCH指標(biāo)，提出的算法EVF可以很好地檢測(cè)出不確定時(shí)間序列中的錯(cuò)誤值，進(jìn)行錯(cuò)誤值的清洗與替換，具有良好的容錯(cuò)性和一般通用性。

5 結(jié)束語(yǔ)

不確定時(shí)間序列的概率分布隨著時(shí)間的變化而不斷改變，無(wú)法使用已有的概率數(shù)據(jù)庫(kù)生成方法直接對(duì)其進(jìn)行數(shù)據(jù)庫(kù)生成操作。因此在進(jìn)行數(shù)據(jù)的存儲(chǔ)之前，需要對(duì)原始數(shù)據(jù)進(jìn)行有效的概率分布推導(dǎo)工作，得到不確定時(shí)間序列數(shù)據(jù)隨著時(shí)間變化的一般分布規(guī)律。文中依托已有的ARMA模型和GARCH模型，提出推導(dǎo)不確定時(shí)間序列概率分布的ARMA-GARCH模型以及I-GARCH模型，并且在此基礎(chǔ)上進(jìn)行進(jìn)一步的改進(jìn)，提出能有效過(guò)濾錯(cuò)誤值的算法EVF。實(shí)驗(yàn)結(jié)果表明，ARMA-GARCH模型和I-GARCH模型能有效地根據(jù)時(shí)間序列的發(fā)展規(guī)律推導(dǎo)得出正確的概率分布。同時(shí)，針對(duì)包含錯(cuò)誤數(shù)據(jù)的數(shù)據(jù)集，EVF算法體現(xiàn)出高效的錯(cuò)誤排查功能，具有良好的容錯(cuò)性和一般通用性。下一步的研究工作是利用推導(dǎo)得出的概率分布生成不確定時(shí)間序列的概率數(shù)據(jù)庫(kù)。