湯其婕，王 玙

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

0 引 言

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

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

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

1 相關(guān)工作

1.1 動態(tài)密度指標

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

圖1 氣溫變化曲線

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

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

1.2 已有動態(tài)密度指標

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

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

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

(1)

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

(2)可變閾值指標。

(2)

2 GARCH指標

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

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 加強的GARCH模型I-GARCH

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

圖2 ARMA-GARCH和I-GARCH舉例說明

3 I-GARCH動態(tài)指標的改進

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

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

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

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

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

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

算法2：EVF

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

輸出：干凈值序列V

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

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為錯誤值將其刪除;

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

18．}

4 實 驗

4.1 實驗?zāi)康?/h3>

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

4.2 實驗數(shù)據(jù)

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

表1 實驗數(shù)據(jù)說明

4.3 實驗方法

(1)動態(tài)密度指標的衡量。

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

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

(2)實驗過程。

第一部分：動態(tài)密度指標的比較。

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

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

4.4 實驗結(jié)果與分析

(1)第一部分的實驗結(jié)果。

圖3 動態(tài)密度指標比較

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

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

圖4 動態(tài)密度指標效率比較

(2)第二部分的實驗結(jié)果。

圖5 I-GARCH和GARCH的比較

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

5 結(jié)束語

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