基于導數序列的時間序列同構關系發現

鄒蕾　高學東

摘要：

時間序列子序列匹配作為時間序列檢索、聚類、分類、異常監測等挖掘任務的基礎被廣泛研究。但傳統的時間序列子序列匹配都是對精確相同或近似相同的模式進行匹配，為此定義了一種全新的具有相似發展趨勢的序列模式——時間序列同構關系，經過數學推導給出了時間序列同構關系判定的法則，并基于此提出了同構關系時間序列片段發現的算法。該算法首先對原始時間序列進行預處理，然后分段擬合后對各時間序列分段進行同構關系判定。針對現實背景數據難以滿足理論約束的問題，通過定義一個同構關系容忍度參數使實際時間序列數據的同構關系挖掘成為可能。實驗結果表明，該算法能有效挖掘出滿足同構關系的時間序列片段。

關鍵詞：

時間序列；數據挖掘；子序列匹配；分段；模式發現

中圖分類號：

C931.6TP301.6

文獻標志碼：A

Abstract：

As the basis of time series data mining tasks， such as indexing， clustering， classification， and anomaly detection， subsequence matching has been researched widely. Since the traditional time series subsequence matching only aims at matching the exactly same or approximately same patterns， a new sequence pattern with similar tendency， called time series homogeneous pattern， was defined. With mathematical derivation， the time series homogeneous pattern judgment rules were given， and an algorithm on time series homogeneous pattern discovery was proposed based on those rules. Firstly， the raw time series were preprocessed. Secondly， the homogeneous patterns were matched with segmentation and fitting subsequences. Since practical data can not satisfy the theoretical constraints， a parameter of homogeneous pattern tolerance was defined to make it possible for the practical data homogeneous patterns mining. The experimental results show that the proposed algorithm can effectively mine the time series homogeneous patterns.

英文關鍵詞Key words：

time series； data mining； subsequence matching； segmentation； pattern discovery

0引言

時間序列數據挖掘的主要任務包括相似性檢索、聚類、分類、模式發現、異常監測等，其中模式發現又分為序列模式發現、有趣模式發現、周期模式挖掘、異常模式發現等。序列模式發現最早由Agrawal等[1]提出，算法的輸入是一系列序列數據集，算法的目標是找到滿足用戶定義的最小支持度的所有頻繁序列模式；有趣模式發現[2]是指發現滿足用戶事先預期的、存在特定規律的模式行為；周期模式發現[3-7]根據周期特征的不同，分為完全周期模式挖掘、部分周期模式挖掘、同步周期模式挖掘、異步周期模式挖掘、近似周期模式挖掘等；異常模式發現[8]是指找出發生頻率遠不同于先前預期的模式行為。

已有的時間序列模式發現技術都是通過挖掘完全相同的序列模式，基于已知序列模式訓練集的趨勢從而進行未知序列模式的趨勢預測。但現實的時間序列數據中，往往很難找到完全相同的時間序列模式，卻存在類似發展趨勢的時間序列模式。比如，各個國家鋼鐵產量時間序列、不同病人的心電圖序列、不同地區降水量序列等，以上序列間雖不一定存在完全相同的序列模式，但由于內在的發展規律一致性，很可能存在同比發展趨勢的序列模式。因此，如果能挖掘出有效的同比發展趨勢的序列模式（如圖1）也可以用于時間序列趨勢預測。

本文基于以上問題定義了一種寬泛的時間序列相似關系，即時間序列同構關系。本文提出的時間序列同構關系與傳統數據挖掘中的時間序列相似關系的區別在于：一是時間

序列的相似關系要求待比較序列間形狀精確相同或近似相同，而本文提出的時間序列同構關系要求時間序列的變化趨勢相似，因此，同構關系是一種更寬泛的相似關系；二是時間序列相似性度量需經過距離度量與主觀設置的相似性閾值進行比較從而判定待比較時間序列是否相似，具有一定的主觀性，而時間序列同構關系判定通過曲線間導數關系直接判斷時間序列是否滿足同構關系。

1本文后續章節的主要內容如下：第一章給出了時間序列同構關系的具體概念，并經過數學推導給出了同構關系判定的法則；第二章給出了具體的時間序列同構關系發現算法的步驟；第三章通過一個模擬手寫簽名曲線驗證了本文算法對時間序列同構關系發現的有效性；最后一章是本文的結論部分。時間序列同構關系基本概念

時間序列同構關系具體概念

1.1時間序列

時間序列是由記錄值和記錄時間組成的元素的有序集合，記為X={x1=（v1，t1），x2=（v2，t2），…，xn=（vn，tn）}，元素xi=（vi，ti）表示時間序列在時刻ti的記錄值為vi，記錄時間是嚴格增加的（i

1.2時間序列關鍵點

時間序列關鍵點[10]即包含時間序列重要分段信息的點，比如極值點、拐點、最值點等，本文以極值點作為時間序列分段的關鍵點。

2.1時間序列數據預處理

由于原始時間序列可能波動過于頻繁，如果對原始時間序列直接按極值點分段，則各分段時間區間過短，也難以形成趨勢。因此，在數據預處理階段首先對原始時間序列數據進行平滑預處理。本文采用平滑濾波[11]技術，平滑濾波技術是低頻增強的空間域濾波技術。它的目的有兩個：一個是模糊，一個是消除噪聲。空間域的平滑濾波一般采用簡單平均法進行，與滑動窗口平均法類似，不同的是，各個元素在平均時所占權重不同。

2.2時間序列分段同構關系發現

本文定義兩時間序列同構時需滿足兩時間序列導數序列任意對應點處導數比相等，即兩時間序列擬合后的多項式系數滿足1.5節中定義的比例關系時，則認為兩時間序列同構。由于在實際時間序列數據中，保證各多項式系數同時滿足1.5節中定義的比例關系的條件較苛刻，可能很難達到，導致挖掘不出存在同構關系的時間序列分段。因此，為使算法可行，本文設置一個同構關系容忍度參數μ，當aibi∈[pωi-112（1-μ），pωi-112（1+μ）]（i∈[1，k]）時，也可認為兩時間序列分段近似存在同構關系。

其中，在對各同構時間序列片段聚類時，由于嚴同構的時間序列片段間擬合多項式系數比嚴格滿足比例關系，因此，各時間序列片段間的同構關系具有傳遞性。而對于寬同構的時間序列片段而言，由于各時間序列片段間擬合多項式系數比不嚴格滿足比例關系，可能導致時間序列片段1與時間序列片段4間近似滿足比例關系，時間序列片段1同時與時間序列片段7近似滿足比例關系，但時間序列片段4與時間序列片段7間卻不滿足寬松比例關系，而無法聚到一個寬同構時間序列片段類。但本文定義當出現上述情況時，只要待聚類時間序列片段與已有類中任意時間序列片段存在寬同構關系，即認為該時間序列片段可聚到當前類中。因此，上述時間序列片段1、4、7可聚為一個寬同構時間序列片段類。

算法1時間序列同構關系發現。

輸入：原始時間序列；

參數：同構關系容忍度μ；

輸出：同構關系的時間序列片段。

步驟1原始時間序列平滑預處理，并按極值點進行分段。

步驟2對各時間序列片段進行最小二乘擬合，并記錄各擬合多項式系數。

步驟3從第一個時間序列片段集中順次取出一個時間序列片段，并將其從原時間序列片段集中刪除，依次計算其與第二個時間序列片段集中各片段的擬合多項式對應項系數比。

步驟4如果擬合多項式對應項系數比滿足1.5節中定義的比例關系，則將滿足同構關系定義的原始時間序列片段放入同一同構時間序列片段類中；若與第二個時間序列片段

集中任意時間序列片段都不滿足同構關系，則放入兩個同構時間序列類。

步驟5若第一個時間序列片段集非空，順次取出一個時間序列片段，并將其從原時間序列片段集中刪除，依次與已有同構關系時間序列片段類中任一元素計算其擬合多項式對應項系數比，若與其中任一時間序列片段滿足1.5節中定義的比例關系，則將該時間序列放入相應的同構關系時間序列類中。否則，依次與第二個時間序列片段集元素判斷是否滿足同構關系，若滿足，則聚成一個同構關系時間序列片段類；否則，新生成一個時間序列片段類。重復步驟5直到第一個時間序列片段集為空。

步驟6算法結束，輸出各同構關系時間序列片段類。

以圖2為例，對序列1和2分別平滑預處理后按照極值點進行分段，序列1可分為7段，序列2可分為4段；因此，為了分段更明顯，可以在原有曲線各分段上對應標上編號1～7（序列1）及1～4（序列2）；然后對各分段進行同構關系判定；最終發現序列1前4分段構成的子序列與序列2滿足同構關系。

3實驗分析

本文算法可以用于時間序列子序列匹配、手寫簽名識別、心電圖異常檢測等問題，其中，時間序列子序列匹配又可以作為時間序列聚類、分類、預測等的基礎。由于以往的研究中沒有涉及對時間序列同構關系發現的研究，因此，本文實驗不設對比實驗，僅通過一組模擬手寫簽名曲線匹配驗證本文算法的合理性。

3.1實驗參數說明

1）擬合多項式次數選擇。

由于本文對原始時間序列進行平滑濾波處理后基于極值點進行分段，因此同一分段內曲線是單調變化的，基于這一特性，本文選擇三次多項式對各分段進行最小二乘擬合。

2）同構關系容忍度參數。

由于實際背景的時間序列數據難以挖掘出有意義的同構關系時間序列片段，因此，有必要定義一個同構關系容忍度參數。經過多次實驗，本文取同構關系容忍度參數為0.1，針對不同問題同構關系容忍度參數將根據具體情況而定。

3.2實驗結果分析

采用本文算法對圖3所示的兩條模擬手寫簽名曲線進行匹配結果如下。對如圖3所示序列1和2，由于兩條曲線時間區間長度不同，因此，無法用傳統的歐氏距離進行曲線間距離度量，而動態時間彎曲（Dynamic Time Warping， DTW）距離也難以得出兩條曲線相似的結論；現有學者提出的基于相似性變換[12]、遺傳算法[13]、演化計算[14-15]等的方法計算復雜性較大，【；采用本文算法后，圖3中所示兩條曲線的加粗部分均滿足同構關系，因此，兩條簽名曲線可認為近似同構。因此本文算法通過比較導數直接判定兩條曲線的關系，大大降低了問題的復雜性。實驗結果如圖3所示，兩條曲線的加粗部分對應同構，兩條簽名曲線可認為滿足寬同構關系。

4結語

本文針對時間序列子序列匹配問題，定義了一種全新的時間序列同構關系模式，并提出了有效的算法以實現對時間序列片段同構關系的挖掘。同時，針對實際背景數據難以滿足理論約束時，通過定義一個同構關系容忍度參數，有效解決了寬同構關系時間序列片段的匹配問題。但針對時間序列同構關系模式的聚類、分類等問題的研究以及對時間序列同構關系模式的拓展應用仍有待于進一步研究。

參考文獻：

[1]

AGRAWAL R， SRIKANT R. Mining sequential patterns [C]// ICDE 95： Proceedings of the 11th International Conference on Data Engineering. Washington， DC： IEEE Computer Society， 1995： 3-14.

[2]

FRADKIN D， MRCHEN F. Mining sequential patterns for classification [J]. Knowledge and Information Systems， 2015， 45（3）： 731-749.

[2]

RATANAMAHATANA C A， LIN J， GUNOPULOS D， et al. Data Mining and Knowledge Discovery Handbook [M]. Berlin： Springer， 2005： 1069-1103.

[3]

HAN J， DONG G， YIN Y. Efficient mining of partial periodic patterns in time series database [C]// Proceedings of the 1999 15th International Conference on Data Engineering. Washington， DC： IEEE Computer Society， 1999： 106-115.

[4]

SIRISHA G N V G， SHASHI M， RAJU G V P. Periodic pattern miningalgorithms and applications [J]. Global Journal of Computer Science and Technology， 2013， 13（13）： 18-28.

SIRISHA G N V G， SHASHI M， RAJU G V P. Periodic pattern mining—algorithms and applications [EB/OL]. [20151204]. http：//globaljournals.org/GJCST_Volume13/4PeriodicPatternMiningAlgorithms.pdf.

[5]

YU X， YU H. An asynchronous periodic sequential patterns mining algorithm with multiple minimum item supports [C]// Proceedings of the 2014 9th International Conference on P2P， Parallel， Grid， Cloud and Internet Computing. Washington， DC： IEEE Computer Society， 2014： 274-281.

[6]

董曉莉.時間序列數據挖掘相似性度量和周期模式挖掘研究[D].天津：天津大學，2007：20-25.（DONG X L. Similarity measure and periodic pattern mining of time series data mining [D]. Tianjin： Tianjin University， 2007： 20-25.）

[7]

AMIR A， APOSTOLICO A， EISENBERG E， et al. Detecting approximate periodic patterns [C]// Proceedings of the 1st Mediterranean Conference on Design and Analysis of Algorithms. Berlin： Springer， 2012： 1-12.

[8]

YANG J， WANG W， YU P S. Mining surprising periodic patterns [J]. Data Mining and Knowledge Discovery， 2004， 9（2）： 189-216.

[9]

肖輝.時間序列的相似性查詢與異常檢測[D].上海：復旦大學，2005：13.（XIAO H. Similarity search and outlier detection in time series [D]. Shanghai： Fudan University， 2005： 13.）

[10]

劉芬，郭躬德.基于符號化聚合近似的時間序列相似性復合度量方法[J].計算機應用，2013，33（1）：192-198.（LIU F， GUO G D. Composite metric method for time series similarity measurement based on symbolic aggregate approximation [J]. Journal of Computer Applications， 2013， 33（1）： 192-198.）