基于時間窗口聚類的時序數據索引壓縮

劉 璐 王 鵬 汪 衛

1(復旦大學軟件學院 上海 200120) 2(復旦大學計算機科學與技術學院 上海 200120)

0 引 言

隨著智能設備的大量應用，在很多應用場景中會生成大型的數據集，如用戶登錄數據、設備運行狀態數據等。這些數據在不同的時間段上會表現出不同的特征。在對數據進行挖掘的過程中，常需要去發現屬于特定時間段的相似數據序列。以下的一個例子可以說明多時間段上相似性查詢的問題。圖1給出了一個收集了不同區域的降雨情況的數據集，橫坐標代表時間戳，縱坐標代表具體的降雨量的數值。考慮這樣一個問題：找出在特定時段(例如t1到t2時間段)內與上海表現最相似降雨趨勢的區域。在這個問題中，查詢的時間段是固定的。一種直接的查詢方式就是通過遍歷整個數據集中t1到t2時間段內的子序列來尋找最近鄰。但是當數據量很大時，直接從數據集中讀取全部的序列并進行序列相似性計算是很費時的。為了加快查詢過程，可以給t1到t2時間段內的子序列建立索引。每一段子序列被表示成一個摘要的值，然后根據這些摘要來建立索引。數據序列的摘要可以近似序列之間的距離，從而剪枝掉不必要的時間序列。上述的過程是在固定的時間段上創建索引來支持該時間段上的查詢。

圖1 多個地區降雨量

構建單個索引以支持限制在該窗口上的查詢是可行的。但是，當查詢窗口更改為(t3,t4)時，又需要構建一個新索引。以圖1中的數據為例，時間序列在不同的時間段上是變化的。在時間段(t1,t2)中，北京的降雨量與上海的更為相似，但在時間段(t3,t4)內,答案應該是杭州與上海更相似。因此，需要建立不同的索引來滿足不同的查詢窗口。顯然，如果要支持大量的查詢窗口，建立索引需要消耗的時間和空間將是巨大的。例如，對于包含長度為104個時間戳的序列的數據集，可能窗口的數量約為108的數量級(考慮全部可能的時間窗口)。

目前的問題是，一些對時序數據建索引的方法只能為單個時間段(序列的一部分或整個序列)構建索引。換句話說，對于可變窗口的查詢，這些方法需要在實際查詢每個窗口上的子序列之前為該窗口建立索引。很明顯，這既費時又費空間。另一方面，一些已有的可變長度索引對基于窗口的查詢執行表現出較低的查詢效率。因為當查詢受窗口而不是長度限制時，它們的剪枝策略效率低下。本文提出一種構造輕量索引的方法，達到較低的總索引代價，對于可變窗口具有高的查詢執行性能。本文方法可以支持精確和近似最近鄰(NN)查詢以及范圍查詢。

1 關鍵概念

(1)時間窗口：如圖1所示，橫坐標t1到t2這一段時間就稱為一個時間窗口。

(2)時序數據子序列：數據序列T={p1,p2,…,pn}是長度為n的序列，其中每個數據點pi按時間戳的順序出現。數據序列在窗口w上的子序列表示為Tw，其中窗口w通常表示為(s,e)，其中s和e定義時間窗口w的開始時間點和結束時間點。

(3)時間窗口的集合：時間窗口的集合可以表示為WS={w1,w2,…,wm}。集合中的每個窗口由一個開始時間戳s和結束時間戳e表示出來。

(4)帶有窗口限制的N近鄰查詢：給定一個時間序列的集合D,給出一條查詢序列Q和一個查詢窗口w(s,e)，用規范化的歐氏距離來衡量時間序列之間的距離。查詢N近鄰的含義是：從所有限制在時間窗口w(s,e)的子序列中找到與查詢序列Qw距離最近的N條子序列。

(5)帶有窗口限制和閾值范圍的查詢：給定一個時間序列的集合D,給出一條查詢序列Q和一個查詢窗口w(s,e)以及距離閾值ε。范圍查詢的含義是：從所有限制在時間窗口w(s,e)的子序列中找到與查詢序列Q距離不大于閾值ε的所有子序列。

2 相關工作

對于時間序列距離的衡量，目前已經有很多文獻提出距離計算的方法。給定兩個標準化的時間序列Q和T，一個相似的函數dist測量Q和T之間的距離，用dist(Q,T)表示兩條序列之間的距離。目前主要的序列距離計算方式包括歐氏距離(ED)[1]、DTW[2]、最長公共子序列(LCSS)[3]等。在這項工作中，使用ED作為距離測量。ED是時間序列中最常見的相似性度量，因為它很簡單且便于計算。對于距離測量的詳細信息，可以參考文獻[4]。

為計算在某個窗口上的相似子序列，直接掃描所有子序列進行查詢非常耗時。之前很多工作提出了許多計算序列摘要方法，使用子序列的摘要值對子序列進行剪枝，例如：離散傅里葉變換[5]、奇異值分解、哈爾變換[6]、APCA[7]、分段均值(PAA)[8]和SAX[9]等。在不同的應用中通常需要根據剪枝的能力對摘要進行選擇。

為了加快查詢速度，現有方法通常會根據序列的摘要創建索引。索引構建方法可分為兩種樣式：自頂向下索引和自底向上索引。自頂向下的方式構造索引會從根節點開始把序列放到節點中[10-12]，當節點容量滿了之后就將節點進行拆分。這種方法會導致許多小的隨機I/O存儲，從而降低索引構建速度。同時，由于節點大小不固定，整個指數結構是較難描述的。另一種自底向上的構造索引方式，例如Coconut[13]，在索引構建之前對數據序列進行排序，從而避免存儲空間的再次分配。因此，它以更快的方式構建索引，而無須拆分節點。一旦序列被排好序，序列的摘要和序列指針就會直接被刷新到磁盤。

除了單獨對每個時間窗口建立索引，目前有一些把多個窗口的索引壓縮到一起的方法[14-16]。但是這些索引壓縮的方法對基于窗口的查詢表現出較低剪枝能力，因為這些索引壓縮的方式沒有充分考慮到索引的特征和相似程度，導致壓縮后的索引比較粗糙。另一方面，這些方法通常只是把鄰近的窗口上的索引壓縮到一起，而并不能把非相鄰窗口的索引進行壓縮。

總之，不管是單窗口的索引還是已有的可變窗口的索引，都不能有效地用于基于窗口的相似性搜索問題。這項工作提出了利用不同查詢窗口的索引的相似性，對索引的時間空間開銷進行優化。

3 方法描述

3.1 方法目標和方法概述

對于查詢窗口較多的時候，為每個時間窗口分別建立索引是很低效的方式。對于所有需要建立索引的時間窗口，本文的基本思想是，如果兩個窗口上構建的索引具有類似的索引結構，則這兩個窗口的索引是相似的。通過把相似的窗口聚類到一起，提取出相似的索引中冗余的部分，以達到索引壓縮的效果。

3.2 窗口索引的相似度

這里主要考慮對于自底向上索引結構的壓縮。正如前文講到過的，自底向上的索引結構通常根據時間序列排序的情況來組織序列，基于排序來構建索引。也就是說，窗口上時間序列的排序情況決定了窗口的索引結構。這一特征有助于比較不同索引之間的相似程度。

序列和窗口之間的關系可以由圖2體現出來。對于圖2中的4個窗口w1-w4,12條序列T1-T12，每一條序列都可以在4個窗口上切出4條不同的子序列。每段子序列可以計算出一個摘要值(例如摘要可以定義為一段子序列中數據的均值)。由于在不同的窗口上計算出的摘要值不同，子序列的排序情況不同，從而不同窗口的索引結構就不同。在實現方法的時候，本文使用的序列排序方式參考文獻[13]。

圖2 不同窗口上序列的相對位置

下面說明如何根據窗口內序列排序的情況來計算窗口間的距離。這里舉例了兩個窗口w5和w6。表1中序列的順序就是子序列的兩個窗口上的排序情況，w5和w6上序列順序略有不同。直接拿排序情況比較兩個窗口的相似度復雜度會較高。事實上需要比較的是兩個窗口上每個排序區間包含的序列的差異。

表1中列舉了一個簡單的例子。把排序后的12條序列劃分成3個長度為4的排序區間：1～4、5～8、9～12。對w5和w6兩個窗口而言，每個窗口上的12條子序列分別放到了如表1的排序區間里。那么通過比較每個排序區間，就能比較出兩個窗口的差異。

表1 不同窗口上的排序情況

對表1兩個窗口的表示，并不能直觀地進行計算。為了數字化地表示出每個排序范圍里分布了哪些子序列，本文把序列按照它們的編號又進行了分組。若設置編號分組大小為3，那么編號為前3的序列依次為T1、T2、T3就被分到第一個編號分組，T4、T5、T6屬于第二個編號分組，以此類推第三編號分組中的序列是T7、T8、T9，第四個編號分組是T10、T11、T12。然后就可以通過計數的方式表示序列的分布情況。如表2所示，把每個排序區間都總結成4個數值(這里數值的個數等于編號分組的數量)，這4個數值分別表示各個編號分組內的序列有多少個出現在了當前的排序區間。例如，w5中的排序1～4的序列中有3個序列屬于第一個編號分組，分別為T1、T2、T3，而T4屬于第二個編號分組。第三和第四個編號分組的序列沒有出現在排序區間1～4中，所以計數分別為3、1、0、0。w5中排序為5到8的序列中沒有第一個編號分組中的序列，有2個(T5和T6)屬于第二個編號分組的序列，第三個編號分組的序列(T7)和第四個編號分組的序列(T11)各有一個，所以計數分別為0、2、1、1。w6的序列分布情況計算是同理的。這樣就統計出了各個窗口上序列的分布情況。可以看到雖然w5和w6的序列排序不完全相同，但是表示出來的序列分布情況是相同的。這就意味著本文方法根據索引結構的實際情況比較索引之間的相似程度，而不是僅僅依賴于精確的序列排序，這樣的計算方法更有利于找到相似的索引，并且計算復雜度也相對低。

表2 窗口的表示

把窗口的每個排序區間的表示拼起來表示成一個向量，例如w5表示為<3,1,0,0,0,2,1,1,0,0,2,2>。進而，窗口間的距離就可以用窗口間的歐氏距離來計算。

3.3 窗口聚類

將每個窗口表示成了上述的向量形式，然后用向量間的歐氏距離來度量不同窗口的索引間的距離，根據這個距離來對窗口進行聚類。基于以上的窗口向量和窗口距離定義，本文使用k-means[17]對窗口進行聚類。參數k用來控制聚類的個數。聚類過程首先選擇k個窗口的向量作為初始k個聚類中心：

(1)聚類更新：給每個窗口計算它的向量到k個中心向量的歐氏距離，把每個窗口分到距離最近的那個聚類。

(2)重新計算聚類中心：對更新之后的每個聚類中所有向量計算，計算這些向量的均值作為新的聚類中心。

這樣就得到了k個窗口的聚類結果。接下來的建立索引的過程是逐一在這k個聚類上分別進行的。

3.4 索引結構和構建方法

對于每個窗口的聚類，只選擇一個代表窗口，同一聚類中的其他窗口被稱作附屬窗口。本文選擇離聚類中心最近的窗口作為代表窗口。下面分別介紹如何為代表窗口和附屬窗口創建輕量級索引。

(1)代表窗口：代表窗口索引的構建遵循常規的自底向上構建索引的方式，首先對數據集中的所有時間序列切分出代表窗口內的子序列，然后對子序列進行排序[13]。指定索引中節點大小的參數，把排好序的序列依次放到節點中，當第一個節點裝滿后，就繼續裝第二個節點，以此類推。同時每個節點維護一個摘要用來描述節點中包含的時間序列的信息。每個節點的摘要就作為最終該節點的索引信息。

(2)附屬窗口：在構造索引的步驟中，附屬窗口內的子序列不需要再進行排序，而是使用該窗口所在聚類的代表窗口同樣的序列排序。也就是說附屬窗口的每個節點指向的序列集合與它所在聚類的代表窗口相同。附屬窗口同樣需要計算每個節點的摘要，作為描述節點的索引。由于窗口是不同的，節點的摘要計算出來也是不同的。

也就是說，每個聚類中只維護一次序列的排序情況，而不是給每個窗口都維護依次排序。由于只維護代表窗口的排序，這樣很大程度上節省了索引占用的開銷。這個聚類中唯一維護的排序稱為聚類的排序。每個聚類的排序和聚類里所有窗口的對應關系如圖3所示。聚類C1中只包含了一份排序信息，聚類中的兩個窗口依次根據每個排序區間的序列構建節點的摘要。每個窗口的節點摘要和排序的對應關系如圖3所示。

圖3 索引結構圖

(3)節點摘要的計算：無論是代表窗口還是附屬窗口，每個節點的摘要其實總結了該節點指向的所有子序列。由于排序中只保留了序列的編號，在計算不同窗口上的節點摘要的時候，只需要把序列對應到不同窗口上的子序列然后計算即可。節點摘要可以用來計算任意一條查詢序列到節點指向的全部序列的距離下界。

例如，給定一個序列子集S={T1,T2,T3,T4}，每個子序列可以表示成x段的SAX值[5]，這里舉例x=3。那么指向子集S的節點摘要就由兩個長度為3的下界和上界構成。下界用向量L來表示，上界由向量U來表示。另外，用SAXi(Tj)來表示序列Tj的SAX值的第i段，其中：i=1,2,3；j=1,2,3,4。那么L和U可以描述為：

式中:參數i表示L和U的第i個分段。有了這樣的節點摘要，就可以明確計算出任意一條查詢序列到一個節點指向的全部序列的距離下界，這樣就能保證在查詢的過程中不去訪問那些一定不包含最終結果的序列。文獻[16]給出了定理來說明如何計算這個距離下界。

4 基于索引的查詢

本文的索引支持以下三種查詢：近似N近鄰查詢、精確N近鄰查詢和帶閾值范圍的查詢。對于一個查詢Q和窗口w，Q到一個節點中所有序列的下界距離可以由公式計算出來，參考文獻[16]。

4.1 近似N近鄰查詢

經典的基于索引的查詢方式[13]在計算近似解的時候，通常優先訪問最有可能包含結果的節點。類似地，CBI選擇Q和節點的摘要之間下邊距離最小的節點摘要。鎖定節點摘要之后，可以定位到摘要指向的一段排序中包含的所有序列，然后計算Q到這些序列的確切歐氏距離，選出距離最小的N條就完成近似N近鄰的查詢。

4.2 精確N近鄰查詢

在精確N近鄰查詢中，首先使用近似查詢的答案作為初始的最優解(BSF)。然后用BSF來檢查查詢窗口w的每個節點摘要。對于距離下界大于BSF的節點摘要可以直接剪枝掉，不再繼續訪問該節點中的序列。對于滿足距離下界的節點摘要，定位到該摘要指向的一段排序中的全部序列，逐一計算Q到節點中每條序列的距離，并更新最優距離。完成對所有節點摘要的檢查后，就得到了精確N近鄰查詢的解。

4.3 帶閾值限制的查詢

由于每個節點都維護了一個可以提供距離下界的摘要，當查詢帶有閾值限制時，直接檢查每個節點摘要和Q的距離下界，如果節點摘要的距離大于閾值，則不再繼續訪問當前節點指向的序列。反之，如果當前節點的距離下界小于閾值要求，則逐條檢查節點指向序列和查詢Q的精確歐氏距離是否滿足閾值，滿足閾值的序列即加入到結果集合中。

5 實驗與結果分析

5.1 實驗設置

所有實驗均在16 GB DDR4內存的Intel i7-7700k CPU上執行。本文測試了以下數據集：

(1)真實數據集使用的是一個濕度數據集，其中包含1998年1月至2018年12月從美國9 115個不同站點收集的濕度測量數據[18]。該數據集的總大小為8 GB，包含約2×109個浮點數，數值范圍為[0,100]。

(2)生成數據集合成時間序列是由隨機游走時間序列、高斯時間序列和混合正弦時間序列三種時間序列組合而成的。生成一個4 GB的合成數據，其中包含10萬個數據序列，長度為10 000，數據數值范圍為[-5,5]。

本文實驗的所有方法都是使用Java語言實現的。

5.2 索引的性能

為了評估CBI創建索引的性能，進行了聚類效率的研究。如圖4所示，3 200個聚類過程需要大約30 min。聚類幾乎是CBI中唯一耗時的過程。這說明CBI建立索引所需要的時間開銷較小。

圖4 CBI聚類時間

圖5顯示了CBI在多個窗口的索引建立方面如何優于Coconut方法。從平均每個索引建立的時間開銷來看，本文的索引在基于窗口的索引時間上是優于普通的單索引構造方式的。

圖5 平均每個窗口上索引的構造時間

空間使用分析：當索引參數固定時，CBI和Coconut消耗空間大小分別都是固定的。以4 GB的生成數據集為例，假設每個序列由16段的SAX表示，索引的節點大小設置為200，單個窗口的Coconut索引的最終大小為7 MB。CBI單個壓縮索引的大小為32 KB。很明顯，CBI索引大小比Coconut小得多。需要構建的基于窗口的索引越多，CBI節省的空間就越多。

5.3 查詢性能

通過與Coconut索引和子序列匹配方法KV-match[19]進行比較，評估CBI的查詢性能。由于這兩個對比算法本身的原因，它們并不完全支持文中列出的這三種查詢。Coconut支持精確和近似的N近鄰查詢，KV-match支持閾值范圍查詢。

(1)N近鄰查詢：比較了CBI與Coconut的剪枝效率，在生成數據集上選擇查詢窗口長度為1 000的整數倍，并對每個窗口運行10個隨機查詢。平均剪枝效率如圖6所示，圖中的數據比較了不同聚類情況下CBI的效率，橫坐標CBI括號里的數字代表聚類個數。剪枝率定義為查詢過程中從磁盤上讀取的序列的數量比上總的序列數。6 400個聚類的CBI的剪枝率為91%，略低于Coconut的93.6%。對于CBI，構建的聚類數越多，剪枝效率越高。

圖6 剪枝率

查詢時間如圖7所示。隨機選擇長度為1 000的窗口，將查詢時間與Coconut進行比較。除了CBI和Coconut之外，還對比了直接暴力搜索的方法運行查詢的時間開銷，該方法直接掃描磁盤上的數據集并計算查詢與所有數據系列之間的標準化歐氏距離。結論是，CBI在節省空間開銷的同時，可以很好地保證查詢效率，平衡了直接搜索的查詢方式和單索引Coconut的不足。

圖7 不同方法的查詢時間

(2)帶閾值限制的范圍查詢：由于Coconut索引的結構不能支持閾值限制查詢，通過選擇可變長度的索引KV-match來驗證CBI的閾值查詢性能。在生成的數據集上測試了各種范圍閾值，并使用1 000的查詢窗口長度。圖8給出了KV-match在變量窗口查詢上執行的剪枝效率很弱。即使對于一個小的閾值3，KV-match也需要計算64 846個數據序列的精確歐氏距離，導致剪枝能力低于36%。CBI在范圍查詢中表現出較好的剪枝效率。

圖8 不同閾值下的剪枝效率

6 結 語

本文論述了目前其他一些方法的索引不適合可變窗口查詢的問題，提出一種壓縮的自底向上索引(CBI)方法。本文從索引的原理、索引結構、索引構造方法等多個方面對提出的方法進行了闡述。實驗結果表明，CBI能夠高效、準確地回答給定數據集上的基于窗口的查詢，比目前已有的方法在索引開銷和查詢效率方面有較大的改進。下一步將考慮如何進一步壓縮CBI索引，進一步減少索引開銷并繼續提升索引查詢效率。