一種高效的基于相似性查找時間序列的位符號化表示方法

摘 要：到目前為止能夠計算字符化時間序列的距離度量的方法很少，為此，提出了一種新的字符化的時間序列表示方法BSAP。該方法既能進行維度約簡又允許在符號化后的時間序列表示法上定義距離度量。實驗分別在合成數據和實際數據上進行，實驗表明該方法具有更高的運算效率且需要較少的空間。

關鍵詞：時間序列； 數據挖掘； 符號化表示； 相似性查找

中圖分類號：TP301 文獻標志碼：A 文章編號：1001-3695(2008)08-2328-04

Novel binary symbolic representation of time series for similarity

SUN Mei-yu1，2， FANG Jian-an1

（1.College of Information Science Technology， Donghua University， Shanghai 201620， China； 2. Dept. of Computer， Shandong Labour

Union Administrators College， Jinan 250100， China）

Abstract:In spite of there are dozens of techniques for producing different variants of the symbolic representation， there still have no known method to calculate the distance in the symbolic space to provide the lower bounding guarantee. This paper proposed a novel bit level symbolic representation called BSAP. The representation was unique in which it allowed dimensionality reduction and it also granted a lower bound distance measure defined on the symbolic representation. The experiments was performed on synthetic， as well as real data sequences to evaluate the proposed method.

Key words：time series; data mining; symbolic representation; similarity search

在時間序列的相似性查找問題中，一個難點是如何高效地表示時間序列。近幾年來，在數據挖掘和數據倉庫中時間序列扮演著越來越重要的角色。時間序列是按時間順序排列的、隨時間變化且相互關聯的數據序列，即時間序列S={Si，0≤t[1]。

在數據挖掘的文獻中提到了很多高效的時間序列表示方法^[2~5]，然而關于時間序列數據進行符號化表示的問題始終沒有得到很好的解決。近十年來，提出了很多高效的算法和數據結構，這些算法能夠對字符串進行高效的運算，且已經得到了很多學科包括分析復雜生物資料學科的關注^[6~8]。針對字符串定義了很多工具，包括散列法、馬爾科夫模型、后綴樹、決策樹等。

盡管已經提出了很多符號化的時間序列表示方法^[9，10]，但目前為止能夠計算字符串化的時間序列的距離度量的依舊很少。本文提出了新的位字符串表示方法BSAP能夠實現符號化后的時間序列的距離度量，且滿足無漏報原則^[2]，即要求數據表示滿足以下條件(下邊界引理):

DF(q，s)≤D(q，s)(1)

即約簡后的距離應不大于原先的距離。其中：q是查詢序列；s是數據集中的任意序列；DF是約簡空間中的兩序列距離；D是真實的兩序列距離。

本文中所提出的BSAP方法是一種離散化的表示方法，它采用了一個中間步驟進行第一步轉換，即首先將初始的時間序列數據轉換成APCA（adaptive piecewise constant approximation）表示法，再將得到的表達式進行符號化表示。采用這種做法有如下優點：a)APCA表示法是一種高效的時間序列表示法，能夠高效地進行時間序列數據挖掘任務，可以利用其高效的降維技術進行維度約簡。b)可以很容易地證明筆者所提出的符號化的時間序列表示方法具有比初始數據低的距離度量；c)本文的位符號化表示方法能夠高效地進行存儲和運算。d)很多數據挖掘算法運用到位運算時會更高效。

1 相關工作

在過去幾年中，很多專家學者對時間序列的相似性進行了廣泛的研究，研究的重點在于如何通過選擇合適的時間序列表示方法來達到提高相似性查找效率的目的。本文提出的相關工作是比較簡潔的，建議對此感興趣的讀者可以參考文獻[4]。

面對海量數據，直接去操作一個高維的數據空間是很困難的。一個具有n個點的序列可以看成是n維空間的點，若直接用多維索引結構(如R*樹)來索引這種n維點，容易導致維度災難。因此，需要研究合適的數據表示形式進行維度約簡，在高效、方便的表示形式上進行有效的挖掘。衡量維度約簡效果的重要標準之一是要滿足無漏報原則^[2]。在大多數的情況下，合理的時間序列表示方法能夠提高時間序列數據挖掘的效率。在此想法的推動下，涌現了大量的時間序列表示方法，這些方法有離散傅里葉變換(discrete Fourier transform， DFT)^[11]、離散小波變換(discrete wavelet transform， DWT)^[3]、PAA (piecewise aggregate approximation)方法^[12]、APCA(adaptive piecewise constant approximation)方法^[4]和奇異值分解(singular value decomposition， SVD)^[13]等。

Agrawal 等人^[11]使用DFT將時間序列進行約簡并將時序從時域空間變換到頻域空間。根據Parseval 定理，在頻域空間中，DFT 保持原序列的Euclidian 距離，即滿足下邊界引理。可取頻域的前k個系數形成一個k維點來表示原序列，相似度量就是k維點的Euclidian 距離，并建立索引。該方法要求匹配的時間序列必須等長、系數相同，且僅對全序列匹配有效。Faloutsos 等人^[2]于1994年提出設定滑動窗口，對窗口內的子序列進行DFT 后形成k維特征點軌跡，并對軌跡按照MBR(mini-mum bounding rectangle)來劃分，采用the ST-index的方法建立相應索引，該方法解決了子序列匹配的問題。近來，Keogh等人^[4]提出了一種新的時間序列表示方法APCA，采用可變長度的分割以期獲得更好的時間序列相似性比較。采用該方法時，一個時間序列被近似成一組二維數組，數組的每個分量由均值和每個分割的最后一個點構成。

近年來雖然時間序列表示方法取得了長足的進步，但還有很多不足之處^[4]。很多時間序列表示方法均表現出在某一方面強但在另外的很多方面卻很弱的特點。如前面所言，很多方法在是在增加空間開銷的前提下提高準確率的。本文將把兩種技術進行結合，這正是本文的創新所在，將該方法命名為BSAP(binary symbolic adaptive piecewise constant approximation)。

2 BSAP：位字符串法

2.1 維約簡

Keogh提出的APCA波動較大區間劃分成多個短區段，方法是將平穩區間劃分成少量長區段，以達到最優性能。表1列出了本文所用到的概念。

采用APCA法時，時間序列C可以表示成一系列可變長度的分段構成，每個分段可由一個二維向量表示，每個二維向量由該分段的平均值和該分段的最后一個點構成。一個時間序列的APCA表示法如下所示：

S={〈sv1，sr1〉，…，〈svM， srM〉}， sr0=0(2)

其中：M是可變分段的個數;svi表示第i個分段中數據點的均值（即svi=mean(ccri-1+1，…，ccri)）；sri用來標記第i個分段中最后一個點。可以認為平均定長分段法是該方法的一個特例。圖1是時間序列C用APCA法進行四分段的表示。

在本文中，筆者對APCA方法進行一個小變動，即將時間序列C的APCA表示法表示如下：

/*時間序列S映射到X的算法*/

S:= {} /* APCA 表達式 */

X:= {} /* BSAP 表達式*/

{1}ni /* 由ni個‘1’組成的字符串*/

{0}ni /*由ni個‘0’組成的字符串*/

X=0;

for i=1 to M do

if svi >1

then X=X+{1}ni

else X=X+{0}ni

end for

2.3 距離度量

給定兩個時間序列，查詢序列Q={q1，…，qn}和候選序列S={ s1，…，sn }。 為比較兩個時間序列的相似性，可以采用普遍采用的歐幾里德距離度量^[4，16]

D(Q，S)=ni=1(Qi-Si)2(5)

由于平方根函數是單調的且為凹函數，可以將其移去并同樣對時間序列進行比較、聚類和分類，得到移去平方根后的距離度量為

D(Q，S)≡∑ni=1(Qi-Si)2(6)

很多方法表明采用后一種表示方法在運算過程中可以加快運算的速度^[4]。為了在匹配的過程中達到最優的效果，本文采用后一種表示方法。

下面給出BSAP表示法的距離度量公式：

LB-blax(S，X)≡∑ni=1S2iif(Si＞0 and xi=0)or

(Si≤0 and xi=1)

0otherwise(7)

其中：X為BSAP表達式；S為APCA表達式。

通過上述公式可以證明X與S之間的邊界距離要小于歐幾里德距離。圖3給出了直觀的表示。

推論 LB。BSAP(Q， S)度量比原始序列間的歐式距離要小。

證明:1)DBSAP(Q， S)

假定q和s分別是時間序列Q和S的任意一點，下面列出了它們所有可能的情況：

a) q>0 and s>0； b) q≤0 and s≤0

c) q>0 and s≤0； d) q≤0 and s>0

在a)b)兩種情況下，根據式（7）可知DBSAP(q， s)=0，所以 DBSAP(q， s)

在c)d)兩種情況下，由式（7）可知：DBSAP(q， s)=q2， 根據式（2）和文獻[4]可知：DPACA(q，s)=(sri-sri-1)(qvi-svi)2。因為 (sri-sri-1)>1， (qvi-svi)2>qvi2，所以DBSAP(q， s)

2)DAPCA(Q， S)

在文獻[4]中，作者已經證明DAPCA(Q， S)

1)2)已經得證，所以本文的推論是正確的。

2.4 維度約簡

本文所采用的時間序列表示方法具有數據處理的高效性以及存儲量小的優點。可以看出，若給定一個長的時間序列C，采用BSAP表示方法可以顯著地降低維度。假定原始時間序列的每一個數據需要4 bit的空間，采用BSAP方法可以達到32∶1的壓縮比率。假定采用BSAP方法時，若第一個滑動窗口提取的值為110011，第二個窗口提取的值也是110011，此時可以考慮在滑動窗口矩陣中不再包含第二個窗口的提取值。具體做法是標記第一個產生110011值的窗口的位置，然后滑動窗口去檢測下一個窗口是否產生同樣的字符串，如果是則繼續滑動窗口，直到所產生的字符串發生變化為止。這種簡潔的思想就是經典的無損耗壓縮技術RLE（run-length-encoding）^[17]。

給定一個值為1100000001111111111110000011000000000 0000000111的時間序列X，可以將其改寫為下列格式：2#1，7#0，12#1，5#0，2#1，16#0，and 3#1。這種改寫方式可以在內存中一次放入更多的數據，從而提高效率。事實上，還可以改寫得更簡短些，因為只需要對第一個位進行標記，后面的位均與前一位相反，所以可以改寫為下列格式：!2， 7， 12， 5， 2， 16， 3。其中，用特殊符號“！”表示第一位出現的是位1，這樣可以進一步地對表達式進行壓縮。盡管RLE方法本身就給定了一個比較高的壓縮比，還是可以通過滑動窗口進行進一步的壓縮。可以觀察到，在一個大的數據流上進行窗口滑動時，在一組連續的滑動窗口上經常會得到除了首尾兩個字符串外幾乎完全相似的一組數據。鑒于滑動窗口的這個特性可以僅記錄產生同樣數據的滑動窗口的數量，在產生的數據和滑動窗口的數量之間用一個特殊的符號進行標記就可以了，這樣可以進一步地對時間序列進行壓縮。例如，一個時間序列的RLE編碼如下（在此列舉了六個窗口的數據）：!2， 7， 12， 5， 2， 16， 3; !3， 7， 12， 5， 2， 16， 4; !4， 7， 12， 5， 2， 16， 5; !4， 10， 12， 5， 2， 16， 5， 2; !6， 10， 12， 5， 2， 16， 5， 3; !5， 10， 12， 5， 2， 16， 5， 1。很容易就可以看出前三個窗口和后三個窗口的值相類似，此時經過壓縮了的最終的編碼表達式可以寫成如下格式（數據和滑動窗口的數量之間的特殊符號本文采用$）：!2， 7， 12， 5， 2， 16， 3$3 !4， 10， 12， 5， 2， 16， 5， 2$3。一個包含約20 000個數據的股市數據庫通過哈夫曼編碼可以達到的壓縮比為1 073∶1。另外，由于哈夫曼編碼的前綴特性，上述編碼表達式中的分割符“，”也可以省略，這樣可以產生一個更高的壓縮比。

3 實驗結果

采用BSAP方法進行時間序列的相似性查找實驗，最終的結果與已經存在的方法進行了比較。實驗表明本文的方法具有更高的運算效率且需要較少的空間。

本次試驗采用了兩組數據，一組采用實際數據，一組采用合成數據。其中，實際數據取自2002年7月12日到2006年7月12日間滬深股市上證指數。由于很多現實中的數據如股票市場中的數據和匯率等能夠很好地采用隨機行走方法進行模擬，本文的合成數據就由隨機行走法進行獲取，人工數據大概30k。最終結果表明合成數據和試驗數據在實驗結果上是類似的，由于篇幅關系，在此就不再詳細說明。

本文重點關注剪枝率和讀寫磁盤的數量的比較。選擇精確率作為本文的剪枝率的效率度量。在給定閾值ε下，定義精確率PD（precision degree）^[18]如下：

PD=|sequences actually pruned|/|sequences to be pruned|(8)

試驗結果如圖4、5所示，閾值ε給定一個比較寬的范圍：0.05~0.5。

為避免由于外界因素的變化導致最終實驗結果的不準確性，同時由于磁盤的讀寫次數在相似性查找算法優劣比較中占主導地位且也是下界緊致性的體現^[4]，本文選擇采用磁盤的讀寫次數作為衡量依據，實驗結果如圖6、7所示。

4 結束語

本文介紹了一種新的高效的基于位的時間序列符號化表示法，實驗數據表明該方法在很多領域中具有比較強的優勢，如在速度要求比較高的領域中。未來的研究領域包括算法的改進，將工作擴展到多維時間序列、流數據以及空間數據中^[19]。

參考文獻：

[1] RAFIEI D， MENDELZON A. Similarity-based queries for time series data[C]// Proc of ACM SIGMOD Int’l Conference on Management of Data. New York: ACM Press， 1997:13-25.

[2]FALOUTSOS C， RANGANATHAN M， MANOLOPOULOS Y. Fast subsequence matching in time-series databases[C]// Proc of ACM SIGMOD Int’l Conference on Management of Data. New York: ACM Press， 1994:419-429.

[3]CHAN K P，FU A W. Efficient time series matching by wavelets[C]// Proc of the 15th International Conference on Data Enginee-ring. Washington DC: IEEE Computer Society， 1999:126.

[4]KEOGH E， CHAKRABARTI K， MEHROTRA S， et al. Locally adaptive dimensionality reduction for indexing large time series databases[C]// Proc of ACM SIGMOD Int’l Conference on Mnmanagement of Data. New York: ACM Press， 2001:151-162.

[5]GEURTS P. Pattern extraction for time series classification[C]// Proc of the 5th European Conference on Principles of Data Mining and Knowledge Discovery. London: Springer-Verlag， 2001:115-127.

[6]APOSTOLICO A， BOCK M E， LONARDI S. Monotony of surprise in large-scale quest for unusual words[C]// Proc of the 6th International Conference on Research in Computational Molecular Biology. New York: ACM Press， 2002:22-31.

[7] GIONIS A， MANNILA H. Finding recurrent sources in sequences[C]// Proc of the 7th International Conference on Research in Computational Molecular Biology. New York: ACM Press， 2003:123-130.

[8]BUHLER J， TOMPA M. Finding motifs using random projections[C]// Proc of the 5th International Conference on Research in Computational Molecular Biology. New York: ACM Press. 2001:69-76.

[9]ANDRE-JNNSON H， BADAL D. Using signature files for querying time-series data[C]// Proc of the 1st European Symposium on Principles of Data Mining and Knowledge Discovery. London: Springer-Verlag， 1997:211-220.

[10]DAW C S， FINNEY C E A， TRACY E R. A revicew of symbolicanalysis of experimental data[J]. Review of Scientific Instruments， 2001，74(2):915-930.

[11]AGRAWAL R， FALOUTSOS C， SWAMI A. Efficient similarity search in sequence databases[C]// Proc of the 4th International Conference on Foundations of Data Organizations and Algorithms. London: Springer-Verlag，1993:69-84.

[12]YI B K， FALOUTSOS C. Fast time sequence indexing for arbitrary Lp norms[C]// Proc of the 26th International Conference on Very Large Databases. San Francisco: Morgan Kaufmann Publisher， 2000:385-394.

[13]KOM F， JAGADISH H V， FALOUTSOS C. Efficiently supporting Ad hoc queries in large datasets of time sequences[C]// Proc of ACM SIGMOD Int’l Conference on Management of Data. New York: ACM Press， 1997:289-300.

[14]KEDEM B. Estimation of the parameters in stationary autoregressive processes after hard limiting[J]. Journal of the American Statistical Association， 1980:75(369):146-153.

[15]KEDEM B， SLUD E. On goodness of fit of time series models: an application of higher order crossings[J]. Biometrika， 1981， 68(2):551-556.

[16]KEOGH E， CHAKRABARTI K， PAZZANI M， et al. Dimensionality reduction for fast similarity search in large time series databases[J]. Knowledge and Informations System， 2001，3(3):263-286.

[17]GOLOMB S W. Run-length encodings[J]. IEEE Trans on Info-mation Theory， 1966，12(7):399-401.

[18]VLACHOS M， KOLLIOS G， GUNOPULOS G. Discovering similar multidimensional trajectories[C]// Proc of the 18th International Conference on Data Engineering. Washington DC: IEEE Computer Society， 2002:673.

[19]LEE S， CHUN S， KIM D. Similarity search for multidimensional data sequences[C]// Proc of the 16th Int’l Conference on Data Enginee-ring. Washington DC: IEEE Computer Society， 2000:599.

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文