基于導(dǎo)數(shù)序列的時間序列同構(gòu)關(guān)系發(fā)現(xiàn)

鄒蕾　高學(xué)東

摘要：

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

關(guān)鍵詞：

時間序列；數(shù)據(jù)挖掘；子序列匹配；分段；模式發(fā)現(xiàn)

中圖分類號：

C931.6TP301.6

文獻(xiàn)標(biāo)志碼：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.

英文關(guān)鍵詞Key words：

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

0引言

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

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

本文基于以上問題定義了一種寬泛的時間序列相似關(guān)系，即時間序列同構(gòu)關(guān)系。本文提出的時間序列同構(gòu)關(guān)系與傳統(tǒng)數(shù)據(jù)挖掘中的時間序列相似關(guān)系的區(qū)別在于：一是時間

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

1本文后續(xù)章節(jié)的主要內(nèi)容如下：第一章給出了時間序列同構(gòu)關(guān)系的具體概念，并經(jīng)過數(shù)學(xué)推導(dǎo)給出了同構(gòu)關(guān)系判定的法則；第二章給出了具體的時間序列同構(gòu)關(guān)系發(fā)現(xiàn)算法的步驟；第三章通過一個模擬手寫簽名曲線驗證了本文算法對時間序列同構(gòu)關(guān)系發(fā)現(xiàn)的有效性；最后一章是本文的結(jié)論部分。時間序列同構(gòu)關(guān)系基本概念

時間序列同構(gòu)關(guān)系具體概念

1.1時間序列

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

1.2時間序列關(guān)鍵點(diǎn)

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

2.1時間序列數(shù)據(jù)預(yù)處理

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

2.2時間序列分段同構(gòu)關(guān)系發(fā)現(xiàn)

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

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

算法1時間序列同構(gòu)關(guān)系發(fā)現(xiàn)。

輸入：原始時間序列；

參數(shù)：同構(gòu)關(guān)系容忍度μ；

輸出：同構(gòu)關(guān)系的時間序列片段。

步驟1原始時間序列平滑預(yù)處理，并按極值點(diǎn)進(jìn)行分段。

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

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

步驟4如果擬合多項式對應(yīng)項系數(shù)比滿足1.5節(jié)中定義的比例關(guān)系，則將滿足同構(gòu)關(guān)系定義的原始時間序列片段放入同一同構(gòu)時間序列片段類中；若與第二個時間序列片段

集中任意時間序列片段都不滿足同構(gòu)關(guān)系，則放入兩個同構(gòu)時間序列類。

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

步驟6算法結(jié)束，輸出各同構(gòu)關(guān)系時間序列片段類。

以圖2為例，對序列1和2分別平滑預(yù)處理后按照極值點(diǎn)進(jìn)行分段，序列1可分為7段，序列2可分為4段；因此，為了分段更明顯，可以在原有曲線各分段上對應(yīng)標(biāo)上編號1～7（序列1）及1～4（序列2）；然后對各分段進(jìn)行同構(gòu)關(guān)系判定；最終發(fā)現(xiàn)序列1前4分段構(gòu)成的子序列與序列2滿足同構(gòu)關(guān)系。

3實驗分析

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

3.1實驗參數(shù)說明

1）擬合多項式次數(shù)選擇。

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

2）同構(gòu)關(guān)系容忍度參數(shù)。

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

3.2實驗結(jié)果分析

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

4結(jié)語

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

參考文獻(xiàn)：

[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]

董曉莉.時間序列數(shù)據(jù)挖掘相似性度量和周期模式挖掘研究[D].天津：天津大學(xué)，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].上海：復(fù)旦大學(xué)，2005：13.（XIAO H. Similarity search and outlier detection in time series [D]. Shanghai： Fudan University， 2005： 13.）

[10]

劉芬，郭躬德.基于符號化聚合近似的時間序列相似性復(fù)合度量方法[J].計算機(jī)應(yīng)用，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.）