鄒蕾　高學(xué)東

摘要：

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

關(guān)鍵詞：

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

中圖分類號(hào)：

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í)間序列數(shù)據(jù)挖掘的主要任務(wù)包括相似性檢索、聚類、分類、模式發(fā)現(xiàn)、異常監(jiān)測(cè)等，其中模式發(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ù)期的模式行為。

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

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

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

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

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

1.1時(shí)間序列

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

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

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

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

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

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

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

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

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

輸入：原始時(shí)間序列；

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

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

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

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

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

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

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

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

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

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

3實(shí)驗(yàn)分析

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

3.1實(shí)驗(yàn)參數(shù)說(shuō)明

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

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

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

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

3.2實(shí)驗(yàn)結(jié)果分析

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

4結(jié)語(yǔ)

本文針對(duì)時(shí)間序列子序列匹配問(wèn)題，定義了一種全新的時(shí)間序列同構(gòu)關(guān)系模式，并提出了有效的算法以實(shí)現(xiàn)對(duì)時(shí)間序列片段同構(gòu)關(guān)系的挖掘。同時(shí)，針對(duì)實(shí)際背景數(shù)據(jù)難以滿足理論約束時(shí)，通過(guò)定義一個(gè)同構(gòu)關(guān)系容忍度參數(shù)，有效解決了寬同構(gòu)關(guān)系時(shí)間序列片段的匹配問(wèn)題。但針對(duì)時(shí)間序列同構(gòu)關(guān)系模式的聚類、分類等問(wèn)題的研究以及對(duì)時(shí)間序列同構(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í)間序列數(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]

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

[10]

劉芬，郭躬德.基于符號(hào)化聚合近似的時(shí)間序列相似性復(fù)合度量方法[J].計(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.）