王 玙，左良利

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

0 引 言

隨著傳感檢測、位置定位和隱私保護等領(lǐng)域的不斷研究，數(shù)據(jù)的不確定性得到了越來越多的重視。把這種按照時間戳先后順序排列的記錄值的數(shù)據(jù)記為時間序列[1-3](time series)，而在每個時間戳上序列的值是多個稱之為不確定時間序列(uncertain time series)。在解決不確定時間序列的諸多問題中，如對時間序列的持久化[4]，降維，聚類[5]，相似性匹配[6-8]等研究工作，推動了數(shù)據(jù)分析技術(shù)的不斷成熟。不確定時序的存儲是其他方面的基石。文獻[9]結(jié)合不確定時間的特點，提出了UK-Means算法來計算初始距離的期望結(jié)果。文獻[10]提出在大規(guī)模時序數(shù)據(jù)庫中通過匹配能找到已知的序列集合。文獻[11]提出用隨機變量描述成不確定時間序列，并提出基于DTW[12]和歐氏距離的PBRQ(probabilistic bounded range query，概率性有界范圍查詢)和PRRQ(probabilistic ranking range query，概率性排序范圍查詢)。文獻[13]等基于兩個不確定時間序列所在的時間點的距離方差是相同的假設(shè)，提出了PROUD算法，利用統(tǒng)計學方法進行剪枝來減少計算代價。

上述研究都是圍繞不確定時間序列的應(yīng)用目的而展開的，對其相似性匹配，聚類研究也只是剛剛起步，但是對于不確定時間序列在關(guān)系數(shù)據(jù)庫上存儲的研究[14]少之又少。文獻[15]提出一種LittleTable的關(guān)系型存儲模型，通過在兩個維度上對表結(jié)構(gòu)進行聚類，按照時間戳來劃區(qū)表示以提高時間序列的檢索效率，并且針對時序數(shù)據(jù)的寫入特點，削弱了一致性功能，使其大大提高了數(shù)據(jù)的寫入能力。

1 不確定時間序列

不確定時間序列的不確定性表示為每個時間戳的數(shù)據(jù)點可能有多個觀察值，在這個時間戳上的值可能由一系列的樣本點組成，這些樣本點分布的不同也構(gòu)成了不確定時間序列模型的不同。

1.1 離散型模型表示

每個時間戳的取值以離散的形式分布，這些離散的點有兩種方法處理：一是將所有的離散點記錄存儲下來；二是這些離散點以一定的概率出現(xiàn)，服從某種離散分布(如二項分布、泊松分布等)。離散模型表示見圖1。

圖1 離散模型表示

1.2 連續(xù)型模型表示

將不確定時間序列的每個時刻觀測到的點看作是某種連續(xù)型的隨機變量，服從某種已知的連續(xù)型概率分布(如正太分布、均勻分布等)。那么該時序某時刻數(shù)據(jù)點就可以形式化表示成某種概率分布函數(shù)(probability distribution function)。

2 不確定時間序列存儲方法

2.1 不確定時間序列數(shù)據(jù)模型

不確定時間序列是一個多元嵌套結(jié)構(gòu),定義如下：

uncertain_timeseries=(timestamp,tags1, …tagsi,>)

其中：

(1)timestamp：時間戳表示采集數(shù)據(jù)的時間點。

(2)tags1…tagsi：維度表示該序列數(shù)據(jù)的歸屬，屬性表明由哪個設(shè)備/模塊產(chǎn)生。一般該條序列的維度值不會隨時間變化，僅供查詢使用。

(3)field：指標代表數(shù)據(jù)的測量值，隨著時間變化而變化，一條序列中的指標可能有多個，其測量值就會有多個。

(4)：測量值，由指標測量的值來表示該值的范圍，當該值帶有不確定因素，則probability∈(0,1)，若該值是確定的值，則probability=1。

需要說明的是，上述離散型模型表示的是不確定離散型時間序列，而對于不確定的連續(xù)型時間序列，其表述方式大致相同，數(shù)據(jù)模型中嵌套的二元組形式替換成三元組，即將概率值替換為方差和均值即可。但這并不是文中的研究重點，故不再敘述。

2.2 存儲規(guī)則

首先，存儲的過程支持對多條時序數(shù)據(jù)進行存儲，需要對不同的不確定時序數(shù)據(jù)進行分類存儲，將各條序列的維度信息與屬性信息一一對應(yīng)，并將其相關(guān)的數(shù)據(jù)元信息完整存儲。接下來通過上述過程提出一系列不確定時序數(shù)據(jù)到關(guān)系模型的存儲規(guī)則，步驟如圖2所示。

圖2 存儲示意

文中根據(jù)時序數(shù)據(jù)不同屬性的用法對其進一步建立二維關(guān)系表，有如下規(guī)則：

規(guī)則1：在對時間戳數(shù)據(jù)值進行數(shù)據(jù)結(jié)構(gòu)表示時，根據(jù)2.1節(jié)將屬性值分為指標和維度屬性，這兩種數(shù)據(jù)結(jié)構(gòu)表示是不一樣的。維度值的數(shù)據(jù)結(jié)構(gòu)是以哈希表來表示的，而指標值可能會產(chǎn)生不確定數(shù)據(jù)，以離散時間序列為例，其數(shù)據(jù)結(jié)構(gòu)依然是鍵值對來表示，只不過該表中相應(yīng)的鍵是指標屬性，而值又是一個哈希表來表示數(shù)據(jù)的不確定性，即嵌套的鍵值對分別表示數(shù)據(jù)及其發(fā)生的概率。當該數(shù)據(jù)為確定性時，為了保證一樣的數(shù)據(jù)結(jié)構(gòu)表示，則規(guī)定確定性的數(shù)據(jù)發(fā)生概率為1。為了方便表述，在接下來的規(guī)則中以鍵值對或者節(jié)點來表示該數(shù)值。

規(guī)則2：維度表的建立，采取系統(tǒng)默認的主鍵自增策略。當維度隊列中維度節(jié)點不存在其對應(yīng)的維度表，則新創(chuàng)建該維度表并新插入行；否則繼續(xù)查找對應(yīng)表中是否有同一個維度，相同的話則忽略，不同則新插入行。例如，對于同一個維度的傳感器產(chǎn)生的時序數(shù)據(jù)，此時不需要每次收集都記錄該維度屬性數(shù)據(jù)，目的是為了避免數(shù)據(jù)冗余。

當不存在則創(chuàng)建維度表的語句：CREATE TABLE tags_Table {id INT AUTO-INCREAMENT，node.k1VARCHAR,…,node.knVARCHAR,PRIMARY KEY(“id”)}，而當進行添加維度表的INSERT TABLE TagsTable{node.v1…node.vn}。

規(guī)則3：指標表的建立，當時序數(shù)據(jù)中有多個指標屬性，則對應(yīng)多個表，而該序列的時間戳作為主鍵，對應(yīng)tags_tables中的主鍵作為該表的外鍵。將指標屬性分開存儲的目的是為了方便查詢和節(jié)省空間，因為數(shù)據(jù)值是隨著時間而不斷生成的，將所有指標放在同一個表中，會使得存儲表過大，并且，在后期優(yōu)化中也不允許將多個指標屬性存儲在一個表中。針對查詢單個指標屬性的場景，也不會造成查詢結(jié)果集過大的問題。

創(chuàng)建指標表的語法：CREATE TABLE metric_Node.k_Tables{timestamp INT，tags_id INT，1S VARCHAR,…,nsVARCHAR,PRIMARYKEY(“timestamp”)，F(xiàn)OREIGN KEY(tags_id) REFERENCE tags_table}。

規(guī)則4:觀察值的表示，表示在接受應(yīng)用設(shè)備的數(shù)據(jù)都統(tǒng)一表示。這樣會使存儲的數(shù)據(jù)格式不一致造成處理差異。無論是確定或者不確定性的指標值都統(tǒng)一化表示，以JSON序列化格式進行存儲，這樣提取出來可以供許多語言進行解析，從而達到數(shù)據(jù)處理的一致性。

規(guī)則5:時間戳轉(zhuǎn)換，在收集到每個時間序列時，都會包含一個時間類型。關(guān)系型數(shù)據(jù)庫存儲采用INT類型來保存UNIX時間戳更合適，因為各個數(shù)據(jù)庫提供的日期時間函數(shù)是不同的，很難在SQL查詢指令中進行協(xié)調(diào)，故采用INT類型表示UNIX時間戳。

規(guī)則6:在進行處理時，不存在任何屬性值為空，以保證算法的嚴謹性，在采集數(shù)據(jù)中規(guī)定每個屬性都可以準確地描述，避免將時序數(shù)據(jù)存入關(guān)系模型中含有空值(NULL)。

規(guī)則7:在將非結(jié)構(gòu)化數(shù)據(jù)轉(zhuǎn)換成層次結(jié)構(gòu)時，不確定時序數(shù)據(jù)在實際應(yīng)用中特殊的表達形式，具有多個同級屬性，這也規(guī)定了在進行樹型結(jié)構(gòu)表示時，最多只有三層結(jié)構(gòu)。如果不滿足此結(jié)構(gòu)，則不屬于該時序數(shù)據(jù)類型。

規(guī)則8:在隊列中存儲的數(shù)據(jù)節(jié)點的Key屬性值，都是以某一規(guī)則進行有序排列的。因為關(guān)系模型中是二維表結(jié)構(gòu)，而表結(jié)構(gòu)中的屬性是有序的，因此，在每次取出進行建表時都會以某一個排序函數(shù)進行排序。

規(guī)則9:在將時序數(shù)據(jù)轉(zhuǎn)換結(jié)構(gòu)化過程中，規(guī)定樹型節(jié)點中有且只有一個代表時間戳的節(jié)點，避免多值混亂存儲。

規(guī)則10:在將時序數(shù)據(jù)各屬性數(shù)據(jù)轉(zhuǎn)換成關(guān)系表時，關(guān)系表對應(yīng)命名方法，文中采取的是駝峰型命名規(guī)則。例如數(shù)據(jù)源關(guān)系表命名為tags_Table，而屬性命名為length_MetricValue等，以此類推。

規(guī)則11:在實際應(yīng)用中收集的時序數(shù)據(jù)都屬于常用的基本類型，需要對其進行基本的數(shù)據(jù)類型轉(zhuǎn)換。由于大多數(shù)基本數(shù)據(jù)類型到SQL數(shù)據(jù)類型都有聯(lián)系，因此轉(zhuǎn)換起來十分簡單。例如，Integer型數(shù)據(jù)對應(yīng)SQL數(shù)據(jù)類型的INTEGER，同理，float轉(zhuǎn)換成FLOAT，string轉(zhuǎn)換成CARCHAR，time轉(zhuǎn)換成TIME，date轉(zhuǎn)換成DATE。

2.3 存儲算法

針對上述提出的存儲規(guī)則，將非結(jié)構(gòu)化的時序數(shù)據(jù)進行建模，并提出存儲方法。本節(jié)基于前兩節(jié)的內(nèi)容進一步提出存儲方法，利用XML的樹型結(jié)構(gòu)層次結(jié)構(gòu)，將其進行結(jié)構(gòu)化表示，然后將各個不確定時序之間屬性的關(guān)系定義清楚，并遍歷不確定時間序列的結(jié)構(gòu)化模型，并根據(jù)不同結(jié)構(gòu)類型找出維度屬性與指標屬性，提出主要的存儲算法。為了更好地敘述算法，引入了幾個簡單的關(guān)于隊列操作的輔助函數(shù)。函數(shù)queuepush(q,node)將node元素添加到q隊列。函數(shù)queuepoll(q)是將取出q隊列中的隊尾元素從隊列中刪除，返回的是取出的node節(jié)點。

存儲算法：

輸入：Uncertain TimeSeries Point

輸出：Relation database Scchema

root=ConvertTree(uncertainTSPoint);

Initq(q1),Initq(q2),Initq(q3);

node Timenode

for(node:queuePoll(q1).childNode){

if(node.value=DateTime){

Timenode=node;}

else if(node.hasChild){//指標

String value="";

for(int i=0;i

value=node(i).getkey+","+node(i).value;}

TempNode=new TempNode();

queuepush(q3,TempNode);}

else {queuepush(q2,node);}}//維度

while(!empty(q2)){

根據(jù)規(guī)則3，創(chuàng)建tags_Tabls }

/q2重新賦值

if(!empty(q2) && TimeNode!=null

&& !empty(q3)){

while(!empty(q2)&& queuePoll(q3){

for(int i=0;i

根據(jù)規(guī)則2、4，創(chuàng)建metric_Tables}

queuePoll(q3)}}

3 實 驗

到目前為止，并沒有一個公認的標準方法評價不確定時序數(shù)據(jù)存儲到關(guān)系模型的效果，要檢驗文中提出的存儲策略與算法的可行性，關(guān)鍵是對結(jié)果進行等價的驗證。存儲系統(tǒng)如圖3所示，該系統(tǒng)分別對人工查詢和數(shù)據(jù)庫查詢語句檢驗的結(jié)果進行對比，若查詢的結(jié)果與最初加噪的數(shù)據(jù)集相同，即證明了存儲的有效性。

圖3 存儲系統(tǒng)

3.1 實驗數(shù)據(jù)及實驗環(huán)境

為了構(gòu)造不確定時間序列數(shù)據(jù)符合原始時間序列數(shù)據(jù)的特征，采取的策略是隨機生成概率值δ進行人工加噪，以表示不確定時間序列，δ的取值范圍為0到1。并且，若該時間點的δ值總和不為1，則應(yīng)該繼續(xù)生成該點的離散值，并且采取誤差值在0.5ε到1.5ε，使確定值上下浮動并且對應(yīng)的概率值累計為1。通過這種方式，使在時間點上的不確定數(shù)據(jù)與真實采集的不確定數(shù)據(jù)更加相似。在實際收集數(shù)據(jù)時，由于外界不可控因素產(chǎn)生誤差，影響因子也隨之變化，但是大部分的采集值是精確的。因此，采取隨機性地標記時間點上的值是能夠有效反映出不確定時間序列。文中研究的是時間序列各個時間點上的不確定性，所以每一類的時間間隔都是相等的。

UCR數(shù)據(jù)集是時間序列分析中應(yīng)用廣泛的測試數(shù)據(jù)集，文中采用UCR數(shù)據(jù)庫中的數(shù)據(jù)作為輸入數(shù)據(jù)，主要選取的數(shù)據(jù)集(見表1)：Synthetic Control(Syn_Ctrl)，Gun-point(Gun)，OSU Leaf(Leaf)，CBF，F(xiàn)ace(all)(Face)。在原始數(shù)據(jù)的基礎(chǔ)上，以離散均勻分布加入噪聲進行干擾，將其存儲的序列變成不確定時間序列進行存儲。

實驗環(huán)境見表2。

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

表2 實驗環(huán)境

3.2 實驗結(jié)果及分析

為了進一步驗證提出的存儲方法的有效性，隨機使用預(yù)先處理好的測試集，對不確定時間序列進行處理并存儲。模擬不同維度屬性的不確定時間序列進行處理，得到對應(yīng)的關(guān)系表，并依次將序列中的觀測值根據(jù)存儲規(guī)則與算法存儲對應(yīng)的表結(jié)構(gòu)中，最終得到圖4的存儲結(jié)果。結(jié)果證明，文中設(shè)計的存儲方法是有效的。

4 結(jié)束語

時間序列是數(shù)據(jù)挖掘領(lǐng)域的一個熱門研究方向，現(xiàn)有關(guān)于時間序列的研究成果主要集中在確定的時間序列上，對于不確定時間序列的研究仍存在很多缺失。不確定時間序列是當前時間序列的主要表現(xiàn)形式，因此對不確定時間序列進行深入研究是對時間序列這一研究方向的一個極大補充。

文中主要根據(jù)不確定時序存儲的特點，提出了針對不確定時間序列的存儲規(guī)則，根據(jù)這些規(guī)則進一步提出存儲算法。該算法實現(xiàn)了將采集到的多條不確定時間序列依次有序地存入關(guān)系數(shù)據(jù)庫，實現(xiàn)了存儲的自動化。并且，設(shè)計了一個存儲原型系統(tǒng)，驗證了該存儲方法的有效性。