支持均勻縮放的不等長時間子序列查詢方法

熊浩然，何震瀛

（1.復旦大學軟件學院，上海 200433；2.復旦大學計算機科學技術學院， 上海 200433）

0 引言

時間序列數據是按時間順序組織的數據序列，廣泛存在于諸多領域，例如醫療、交通、金融等［1-3］。查詢并獲得相似的時間序列（即相似性查詢）是這些應用中的一個基礎任務［4］，其效率對時序數據分析算法和流程的影響較大。為此，時間序列的相似性查詢的效率是業界長久以來關注的重要問題之一。

時間序列的相似性查詢分為全序列查詢和子序列查詢兩種［5］。全序列查詢的目標是從一個時間序列集合中查找出與給定序列相似的序列集合；而子序列查詢旨在從一系列長序列中找到與給定短序列相似的子序列集合。現有大多數子序列查詢方法僅支持查找與目標序列長度相同（或接近相同）的子序列［6-9］。但在許多場景下，查詢序列與目標子序列間可能存在時間維度上的伸縮（拉伸或壓縮），因此，它們的長度并不一定相同。以哼唱查詢（QBH）為例，QBH 系統允許用戶哼唱音樂片段，并在音樂數據庫中查找與之相似的音樂片段，從而完成哼音查詢任務。但若用戶哼唱的速度與實際音樂片段不一致，查詢片段與實際音樂片段會存在時間維度上的差異（伸縮）。

針對此問題，研究者引入了均勻縮放技術，通過均勻上（降）采樣的方式，將時間序列拉伸（壓縮）到不同長度，從而消除序列在時間維度上的差異［10-12］。在均勻縮放的支持下，算法可查找與查詢序列長度不一致但模式相似的子序列，本文將該類查詢稱為支持均勻縮放的不等長子序列相似性查詢。除QBH 外，支持不等長查詢的算法還被應用于人類行為識別（例如動作、語音識別等）、生理監測（例如心跳、呼吸監測等）以及一些工業場景［13-15］。因此，研究者針對支持均勻縮放的不等長序列查詢問題開展了一系列研究工作。KEOGH 等［10］針對支持均勻縮放的相似性查詢問題，提出了理論下界距離，并結合R-樹索引，設計一種保證非漏報的高效相似性查詢算法。WAIYAWUTH 等［16］強調了均勻縮放與Z-標準化在相似性查詢中的重要性，并提出同時支持均勻縮放和Z-標準化的查詢算法。FU 等［17］將均勻縮放和動態時間規整（DTW）距離結合，為其構建理論下界距離以支持快速查詢。然而，文獻［10，16-17］方法僅支持全序列查詢問題。文獻［11］將針對DTW 距離的優化策略遷移到支持均勻縮放的不等長查詢問題上，提出下界距離，用于加速順序掃描的子序列查詢過程。文獻［12］將優化為更緊湊的下界以提高查詢效率。然而，文獻［11-12］方法并未構建索引，需要掃描整條長序列以完成相似性查詢，且無法支持序列Z-標準化。此外，現有較為高效的子序列查詢方法，例如KV-match［7］、ULISSE［8-9］，均為長序列構建對應的索引，減少了數據訪問和計算開銷以優化查詢效率，但它們不支持不等長子序列查詢。

綜上，現有研究工作雖然在不等長查詢問題上取得了不錯的效果，但在效率方面仍有提升的空間，且無法有效支持Z-標準化。為此，本文提出一種支持均勻縮放的不等長子序列高效查詢方法。該方法基于ULISSE 提供的樹狀索引結構，設計保證非漏報的下界距離，為樹狀索引結構的剪枝提供理論保證，并結合ULISSE 索引緊湊的數據信息，提出精確K-近鄰（K-NN）查詢算法，優化數據訪問方式以提高查詢效率。該方法能夠同時適用于非歸一化和歸一化兩種情況。

1 問題描述

為了全文描述的一致性，進行如下形式化定義：

定義1（時間序列）時間序列T是按時間順序組織的數值序列，表示為T=(t1,t2,…,tn)，其中，n=|T|為序列T的長度。

定義2（子序列）子序列是指時間序列中一段連續的數值組成的序列。時間序列T的子序列Ti,l表示從位置i開始，長度為l的子序列，即Ti,l=(ti,ti+1,…,ti+l-1)。

為表達簡潔，本文使用S表示子序列。對于任意子序列S=(s1,s2,…,sn)，μS和σS表示序列S的均值和標準差。

定義3（Z-標準化）給定一個時間序列S=(s1,s2,…,sn)，Z-標準化后的序列表示為其中：

定義4（歐氏距離）給定兩個長度為n的序列S和S'，兩者之間的歐氏距離定義為：

定義5（均勻縮放）給定一個長度為n的時間序列S以及目標長度p，通過均勻縮放將S拉伸（壓縮）至長度為p的序列Sp=其中：

定義6（均勻縮放距離）給定查詢Q和子序列S，兩者之間的均勻縮放距離定義為：

在處理不等長序列查詢時，序列之間歐氏距離除了與序列間的相似度有關外，還受到序列長度的影響，即序列越長，歐氏距離趨向于越大。通常，消除長度影響的做法是使用長度標準化，例如用歐氏距離除以序列長度來表征時間序列。LINARDI等［18］詳盡討論過該問題。本文結合該工作中的結論，使用序列長度的平方根來進行長度標準化。

定義7（歸一化均勻縮放距離）給定查詢Q和子序列S，兩者之間基于均勻縮放的歸一化距離定義為：

給定查詢先被均勻縮放為子序列等長的序列Ql，且在進行歐氏距離計算之前，兩個序列均進行Z-標準化以保證數值維度上的統一，最后將歐氏距離除以長度的平方根以完成長度標準化。

問題定義（精確K-近鄰查詢）給定時間序列T、考慮的長度范圍[lmin,lmax]以及整數K，對于查詢序列Q，精確K-近鄰查詢將返回一個子序列集合R={S1,S2,…,SK} ?A，其中，A表示T中所有長度滿足范圍限制的子序列集合，對于?S?R 和?S'?A-R，滿足D(Q,S)≤D(Q,S')。

本文考慮非歸一化以及歸一化均勻縮放距離，即Dus和Dusn。

2 預備知識

2.1 序列表征方法

分段聚合近似［19-20］（PAA）將序列S切分為等長且不相交的序列片段，并分別用每個片段的均值來作為表征，從而將序列S轉換為w維的表征Vpaa(S)，其中，l為片段的長度，w=S|/l。

符號聚合近似［21］（SAX）將Vpaa(S)中的w個值分別離散化為w個符號，其中離散化符號的候選集大小為c。SAX 離散化的基本思想是用c-1 個斷點將實數空間劃分為c個不相交區域，每個區域會有其對應的二進制符號。例如c=4 時，離散化符號分別為{00,01,10,11}。每個分段的均值會根據其落入的區域，離散化為對應的二進制符號。本文用Vsax(S)來表示序列S的SAX 表征。

可索引符號聚合近似（iSAX）遵循與SAX 相同的離散化邏輯，不同的是iSAX 允許每個分段二進制符號的位數不相同，即不同分段的均值被離散成的符號候選集大小不固定。因此，iSAX 支持擴充二進制符號的位數，使得某個分段獲得更精細的離散化表征，該特性被用于建立時間序列的樹形結構索引——iSAX 索引。類似地，本文用Visax(S)來表示序列S的iSAX 表征。

2.2 ULISSE 索引

ULISSE 是一套以iSAX 為基礎，針對子序列查詢而設計的索引結構。由于相近位置的子序列特征類似，該索引設計了一種表征技術，有效且簡潔地描述了多個不同長度、位置相近的序列，并針對該表征設計了一套結構與iSAX 索引類似的樹形索引。為限制涉及子序列的總數量，iSAX 需要用戶提前設定子序列的長度范圍，即lmin和lmax。

位置接近的子序列之間存在大量重復數值，因此，ULISSE 用統一的信息來總結位置相近的子序列。為獲得子序列的表征信息，ULISSE 將連續γ個開始位置的子序列匯總為一組，并將它們的PAA 表征左對齊，每個分段PAA 數值的最大值和最小值被作為上下界信息來代表該組子序列的特征，其中，γ為用戶定義的步長參數。該表征被稱為閉包，包含上邊界UE和下邊界LE兩種統計信息。圖1 給出了具體示例，其中，圖1（a）示例不同開始位置的子序列，圖1（b）將所有子序列左對齊，圖1（c）框中的區域代表該分段PAA 值的變化范圍，而LE和UE分別由這些框的下邊界和上邊界構成。閉包的規范化表示為：

圖1 閉包構建過程Fig.1 Construction of the envelope

其中：a表示相應子序列在長序列T中開始數值的位置；l表示PAA 中每個分段的長度。

根據定義可知，LE和UE均為lmax/l維的向量。可注意到，圖1 中只給出了非Z-標準化的閉包建立過程，而要求Z-標準化時，相同開始位置、不同長度的子序列PAA 值也會變化。故ULISSE 針對Z-標準化提出了高效的閉包建立算法，其構建結果與非歸一化類似，在此不再贅述，其上下界分別用和表示。

此外，ULISSE 為閉包設計了一個類似于iSAX索引的樹狀數據結構。該索引由3 種類型的節點組成，每個節點與閉包類似，都擁有上下界信息，且每個節點上下界均完整覆蓋其子樹中所有子序列的PAA 表征。3 類節點的特點為：1）根節點指向多個子節點；2）除根節點外的內部節點均擁有2 個子節點；3）每個子節點都包含閉包表征以及其對應子序列的位置信息，不保留原序列數據。該索引支持動態插入序列信息，在此不再贅述。

3 不等長查詢算法

3.1 下界距離

UCR suite［11］將針對DTW 問題的解決思路遷移到均勻縮放問題中，給出一套簡單且有效的掃描加速算法，即把所有縮放后的查詢序列統一起來，組合構成查詢序列的上下閉包，并利用該閉包設計下界距離，用于加速掃描查詢算法。后文構建的下界距離需要借助到類似思想，故此處給出該方法形式化的描述。

給定一個查詢Q以及長度限制范圍[lmin,lmax]，則該查詢的下閉包和上閉包分別為L和U，且滿足：

其中：1 ≤i≤lmin。上/下閉包是所有縮放后的查詢序列的最大值/最小值構成的序列，圖2 給出了具體示例，其中，圖2（a）表示所有縮放后左對齊的查詢序列。

圖2 下界距離Fig.2 Lower bound distance

基于查詢閉包，可以構建新的下界距離，用于加速均勻縮放下的不等長查詢。當考慮時間序列T中，開始位置為s、長度滿足限制范圍[lmin,lmax]的子序列與查詢Q的距離Dus時，可為其構建下界距離：

其中：S表示T中以s為開始位置的子序列；U和L分別表示查詢的上、下閉包；可被標記為圖2（b）中陰影部分的總和。

3.1.2 本文提出的下界距離

3.1.3 PAA-iSAX 下界距離

ULISSE 的閉包信息都是以iSAX 的形式存儲的，因此，下界距離的計算也將以PAA 以及iSAX 表征為基礎。依據iSAX 的定義，文獻［22］提出一個iSAX 與PAA 表征之間的距離，而該距離可作為兩個序列之間歐氏距離的下界。這個性質是兩個新下界距離設計的基礎，因此，本部分先引入PAA-iSAX 下界距離及其基本性質。

令βu(?)和βl(?)分別表示iSAX 離散化符號所對應數值范圍的最大值和最小值。給定兩個等長的序列S和S'，以及分段長度l，為表達簡潔，假設序列長度可被l整除，序列均被切分成為w段，則兩者之間的距離可定義為：

此外，根據文獻［23］可知該下界距離擁有以下性質：

引理1給定兩個等長序列S和S'，則有：

3.1.4 非歸一化下界距離

首先，與ULISSE 中的閉包類似，可使用2 個向量來界定查詢的信息，分別為下閉包LQ和上閉包UQ。給定查詢Q以及長度范圍[lmin,lmax]，先根據均勻縮放的定義，將查詢序列拉伸或壓縮到所有可能的長度，并計算出每個伸縮后序列的PAA 表征，將所有PAA 向量左對齊后，每個維度上的最大值和最小值可構成上閉包和下閉包2 個向量。以下給出形式化的表示：

其中：1≤i≤w；w=；l表示每個分段的長度。

ULISSE 索引的閉包存儲了位置相近、不同長度的子序列的上下界信息，再結合查詢構成的閉包信息，可構建下界距離。給定查詢Q，其上下界分別為UQ和LQ；給定閉包E，其上下界分別為UE和LE。Q和E之間的下界距離表示為：

類似地，w=，其中，l表示每個分段的長度。

圖3 查詢上下界及Fig.3 Lower and upper bounds of query and

性質1給定查詢Q及其上下界UQ和LQ；給定閉包E及其上下界UE和LE。對于閉包中的任意一個子序列S，均滿足(Q,E) ≤Dus(Q,S)。

證明根據查詢閉包的定義，可知縮放后查詢的PAA 信息每個維度都被包含于查詢的上下界內，即：

序列S與閉包E也有類似的關系：

再根據iSAX 以及βu(?)和βl(?)的定義，可得到以下不等式：

故性質1 得證。

3.1.5 歸一化下界距離

首先構建查詢Q在歸一化條件下的上下界和。與非歸一化的方法類似，唯一的區別是需要對縮放后的序列進行Z-標準化操作，具體描述如下：

歸一化均勻縮放距離考慮Z-標準化的同時，引入了長度標準化，因此，針對歸一化均勻縮放距離的下界距離會有所不同。給定查詢Q，其上下界分別為和；給定閉包E，其上下界分別為和Q和E之間的下界距離表示為：

類似地，w=其中，l表示每個分段的長度。

性質2給定查詢Q及其上下界和；給定閉包E及其上下界和對于閉包中的任意一個子序列S，均滿足(Q,E) ≤Dusn(Q,S)。

證明該性質的證明與性質1 的邏輯類似，通過查詢以及閉包的上下界定義可知：

因此，可得：

故性質2 得證。

3.2 查詢算法

下界距離能初步界定查詢與索引中節點或閉包之間的距離。本部分將利用前文提及的下界距離，結合索引結構以及存儲的子序列信息，給出針對均勻縮放距離的高效查詢算法，包括近似查詢算法和精確查詢算法。

3.2.1 閉包內子序列掃描算法

在描述利用索引結構進行查詢的過程之前，先給出閉包內部的子序列查詢算法。原ULISSE 算法僅能夠支持返回與查詢結果長度相等的子序列，若將該算法直接運用到支持均勻縮放的不等長查詢問題上，則最基礎的做法是將查詢縮放到所有可能的長度，再對于每個長度進行一次等長子序列查詢。但每個閉包中的子序列所在位置相鄰，會有大量的數據重疊，信息會比較相近。因此，原ULISSE 算法在解決不等長查詢問題時會造成大量重復且沒有必要的閉包以及子序列數據讀取。

借助新的下界距離，能夠統一判斷閉包中所有子序列與查詢的大致距離。當下界距離大于現有最優距離時，閉包存儲的子序列將直接被省略，不進行下一步距離計算，且因為下界距離性質的存在，該省略操作不影響查詢的正確性。當下界距離較小時，閉包中子序列的信息將一次性取出，用于計算所有子序列與查詢的均勻縮放距離，從而減少數據重復讀取和多余磁盤開銷。算法1 給出了閉包中距離計算的具體流程。

算法1閉包相似性查詢

給定閉包E后，E.a表示E中子序列在長序列中的開始位置。根據ULISSE 中閉包的定義可知，E中包含所有開始位置位于［E.a，E.a+γ）范圍內的所有子序列。因此，算法1 將以子序列的開始位置作為外層循環，以該開始位置下的不同長度的子序列作為內層循環，依次迭代計算相應的距離。計算距離時，早停技術依然可以被使用［24］。可以注意到，一個閉包E涉及的原始序列數據僅限于E.a到E.a+γ+lmax范圍內，因此，在算法開始前，可統一將數據從磁盤加載到緩存數組中，減少磁盤訪問量。

3.2.2 近似查詢算法

下界距離不僅能夠過濾閉包和節點，也能指示如何訪問索引的順序，找到與查詢距離較為接近的子節點，因此，下界距離也能被使用在近似查詢中。算法2 給出了近似K-NN 查詢的過程。

算法2近似K-近鄰查詢

算法2 的基本邏輯是借助最小堆，按照下界距離從小到大訪問對應的節點。若節點為子節點時，則使用算法1 計算相應的距離，并更新K-NN 結果R。此外，借助性質1 和性質2 可知，如果訪問節點的下界距離大于K-NN 距離時，R數組中存儲的信息為精確結果，可直接結束算法，達到剪枝的效果。

3.2.3 精確K-近鄰查詢

ULISSE 在建立索引的過程中，同時維護了一個新的數據結構，其中保存了所有的閉包信息，且根據開始位置進行排序，因此，使用該數據結構可進一步利用數據局部性原理，降低查詢開銷。再結合算法1，算法3 給出了精確查詢算法的流程。

算法3精確K-近鄰查詢

當順序掃描該數據結構中的信息時，對應的子序列位置也有局部性，從而可以減少磁盤訪問的開銷。算法3 開始時先利用近似算法獲得初步結果，再依次調用算法1 獲得最終精確查詢的結果。

4 實驗

4.1 實驗設置

4.1.1 實驗數據

為探究本文方法進行不等長查詢的效率，所有的實驗將在2 個公開的數據集以及1 個人工合成數據集上進行測試：1）GAP，其中包含2006—2008 年期間法國有功功率的記錄，該數據集由法國電力供應商提供［25］；2）CAP，循環交替模式數據集，其中包含發生在非快速眼動睡眠階段的腦電圖活動［26］；3）SYN，人工合成數據集，利用隨機游走的方式生成的時間序列，每個數據點由上一個數據點加上隨機數值而獲得，其中隨機數從高斯分布N(0,1)中取得［9］。

實驗中的3 個數據集長度均為107，且子序列長度范圍默認設置為［256，512］。在此設置下，任意一個查詢的候選子序列數量約為109條。

針對每個數據集的查詢序列均由原序列中的子序列生成。本文隨機挑選子序列，并將其縮放為[lmin,lmax]的一個隨機長度，再為縮放后的序列添加額外的高斯噪聲，以獲得最終的查詢序列。

4.1.2 基線方法

UCR-US［11］是支持均勻縮放距離下不等長查詢的代表性方法，它改進了UCR Suite 中的下界距離，使其適應均勻縮放距離，需要對原始數據進行一次順序掃描，以獲得最終查詢結果。在原論文中，縮放的長度范圍隨著查詢長度和預設縮放因子的變化而改變。為了保證比較的公平性，本文將縮放范圍固定為用戶自定義的范圍[lmin,lmax]。需要注意的是，該方法并不能支持歸一化均勻縮放距離，因此，本文將其作為非歸一化問題的基線方法之一。

ULISSE［9］通過構建基于iSAX 的索引，從而支持在長度范圍約束內的子序列查詢。ULISSE 支持非歸一化和歸一化兩種場景，能夠同時適用于本文需要解決的兩類問題。給定一個查詢，本文先將其縮放到所有可能的長度，再逐一使用ULISSE 進行子序列匹配。

4.2 不等長查詢結果

為了驗證本文方法的有效性，進行3 組實驗，分別為均勻縮放距離、歸一化均勻縮放距離下的1-NN精確查詢，以及均勻縮放距離下的K-NN 查詢。每組實驗都分別在3 個數據集上進行。每個實驗均隨機生成100 條查詢序列，統計其平均查詢時間來體現查詢效率。

1）非歸一化均勻縮放距離下的1-NN 查詢效率。本文方法會使用近似查詢算法獲得近似結果，再配合閉包中的信息對來剪枝具體的距離計算，從而提高查詢效率。圖4（a）體現了本文方法以及UCR-US在該任務下的查詢效率。相較于UCR-US，本文方法在不同數據集上的效率提升1.67～3.59 倍，平均提升2.33 倍。可見，索引的引入以及下界距離的使用可以有效減少具體的距離計算，從而提升查詢效率。

圖4 最近鄰查詢效率Fig.4 Efficiency of 1-NN query

2）歸一化均勻縮放距離下的1-NN 查詢效率。由于UCR-US 的下界距離不能支持歸一化的要求，因此該組實驗的基線程序選用ULISSE 方法。圖4（b）展示了本文方法以及ULISSE 的查詢效率，其中灰色部分表示的是查詢中磁盤I/O 所占用的時間。相較于ULISSE，本文方法在不同數據集上的效率提升2.41～2.69 倍，平均提升2.51 倍。由于本文提出的下界距離考慮到了閉包中所有長度的子序列，因此在計算查詢序列與閉包內序列的具體距離時，僅需要一次磁盤讀取，從而減少了大量的磁盤I/O。在實驗中，磁盤I/O 時間在總查詢時間中的占比平均減少29.6%。由此可知，本文方法不僅減少了計算開銷，同時也節省了大部分的磁盤開銷，從而獲得更多的效率提升。

3）均勻縮放距離下的K-近鄰查詢效率。圖5 展示了不同K值情況下本文算法和ULISSE 算法在GAP 數據集上的查詢效率。隨著K值增大，查詢的最終距離會越大，因此算法的過濾率會隨之下降，查詢時間會一定程度地增加，但查詢時間不會過大地波動，基本保持在同一數量級。

圖5 GAP 數據集上的K-近鄰查詢效率Fig.5 Efficiency of K-NN query on GAP dataset

5 結束語

針對基于均勻縮放的不等長子序列查詢問題，本文提出一種基于索引的查詢方法，設計保證非漏報性質的下界距離，提供索引子分支以及子節點中元數據的剪枝策略，減少查詢過程中的計算開銷。此外，該方法利用索引中元數據具有的局部性，減少數據訪問的次數，降低磁盤I/O 在查詢中的時間占比。在真實和人工合成數據集上的實驗結果表明，本文方法能有效縮短距離計算的總時間，同時降低磁盤訪問的開銷，實現不等長子序列的高效查詢。因考慮技術闡述的簡潔和清晰，本文將歐氏距離作為縮放后序列的距離度量，未來可考慮將編輯距離、DTW 距離等更加魯棒的度量方式融入到所提方法中，進一步拓寬其適用場景。