基于形態模式的時間序列相似性度量算法

王 瑞 賈瑞玉

(安徽大學計算機科學與技術學院 安徽 合肥 230601)

基于形態模式的時間序列相似性度量算法

王 瑞 賈瑞玉

(安徽大學計算機科學與技術學院 安徽 合肥 230601)

時間序列的特征表示與相似性度量是時間序列數據挖掘的重要基礎。針對現有的序列表示方法難以具體反映序列的形態變化趨勢，導致相似度量結果不精確的問題，提出一種新的基于形態模式的相似性度量算法。該算法在分段線性表示的基礎上，根據序列在不同時段的斜率變化情況，劃分序列的分段形態模式并用特殊的字符進行表示，把時間序列轉換成字符串序列，利用最長公共子序列方法計算字符串序列的距離作為時間序列之間的距離。最后通過實驗驗證該方法的有效性。理論分析和實驗證明該方法對數據點的值不敏感，能夠減少噪聲的干擾，而且具有較高的準確性。

時間序列 相似性 形態 模式 斜率 子序列

0 引 言

時間序列是按時間順序排列的實數序列，廣泛存在于我們的生活中，如股市指數、氣象數據、銷售額度等[1-3]。時間序列具有時間有序性、數據量巨大且持續增長等特點，對這類數據進行處理的難度較大，因此時間序列的相似性度量方式與聚類方法的研究成為時間序列數據挖掘的熱點，吸引了越來越多研究者的關注[4]。經典的時間序列的相似性度量方法主要有歐氏距離[5]、動態彎曲距離法(DTW)[6]，以及符號距聚合近似方法[7-8]等。近幾年也不斷有新的相似性度量算法被提出，這些方法廣泛應用于時間序列的聚類、相似性搜索、序列預測等工作。

在文獻[9]中提出的基于EMD的K-means的聚類算法能有效提取序列的整體趨勢，根據上升、下降和保持三種狀態對序列進行分段，但是沒有考慮每段的作用強度。在文獻[10]中把序列映射為趨勢符號序列，構成趨勢樹，根據趨勢符號是否相同決定相似性，方法簡單有效，但是趨勢判定條件較為復雜。在文獻[11]中提出的層次分段相似度量算法根據極值點對序列進行層次分段，然后計算動態彎曲距離，時間復雜度有所降低，但用于高維數據的聚類工作時，耗時相對較多。在文獻[12]中提出的基于斜率表示的相似性度量方法，根據斜率偏離程度決定相似度，計算過程簡單，具有對數據的平移不敏感的優點，但是沒有區分序列的模式差異，當序列的模式不同時，可能會有誤判的風險。在文獻[13]中提出漲落模式的概念，將時間序列表示成由布爾值{-1,0,1}構成的漲落模式序列，消除了數據值對時間序列距離計算的影響。該方法對序列的振幅伸縮、漂移和線性漂移均不敏感，但是模式的劃分不夠細致，結果可能不夠精確，而且在原始序列基礎上直接劃分漲落模式，容易受噪聲影響。

本文針對已有算法在時間序列的相似性度量過程中的各種局限性，提出了基于形態模式的相似性度量方法。該方法在分段線性表示的基礎上，根據斜率確定分段形態模式，通過形態模式序列保存序列的變化趨勢，使用最長公共子序列方法計算序列的相似性。形態模式序列確定后，距離度量過程將不再受原始序列中數據元素值的影響，最長公共子序列方法對數據值不敏感，而且支持序列的伸縮和漂移。

1 相關工作

1.1 時間序列分段表示

設時間序列S=(,,…,,…,),j=1,2,…,n，n是序列長度，表示點j對應的數值和時間。時間序列的相似是基于形態的，考慮到不同時間序列度量單位不同，在相似性度量時，度量單位不統一會對結果有一定影響，因此在度量相似性之前，需要對時間序列進行歸一化處理，把數據統一映射到[0,1]區間，方便后期的數據分析。數據統一過程如下：

(1)

min(y)、max(y)分別表示序列中數據的最大值和最小值，y*表示統一處理后的數據。

不同的序列其關鍵點所在位置不同，因此在計算相似度之前，需要在分段后取并集，進行等長處理，即進行時刻對等，保證進行相似性度量的不同序列具有相同的分段數。

1.2 時間序列的漲落模式

根據時間序列的形態變化可以將時間序列大致劃分為上升、下降和保持三種狀態。王釗等[13]基于序列的形態變化提出漲落模式的概念，將原始時間序列保存為由布爾數據構成的擴展布爾型時間序列。用{1，0，-1}為取值范圍的布爾型時序數據保存原始序列的變化趨勢，只關注原有時序數據的形態特征，而不考慮其數值大小。用1表示上升，0表示保持，-1表示下降，在后續的相似度計算中使用生成的布爾型時序數據進行相似性度量。

定義1漲落模式。對于原始時間序列S=(,,…,,…,)，其擴展布爾型時間序列為B=(b1,b2,…,bj,…,bn-1)，二者之間的對應關系如下：

(2)

布爾數據序列B記錄了原始序列S的所有形態漲落趨勢，因此B是S的漲落模式序列。使用漲落模式的意義在于既保留了數據形態變化趨勢，又消除了序列的數值信息對基于形態的相似性度量產生的影響，并且這種方法對數據的平移和伸縮不敏感。

三元漲落模式雖然能夠反映序列的大體趨勢是上升或下降，但是不能描述上升或下降速度的快慢，即使同樣是上升狀態，也存在快速上升和緩慢上升的區別。而且漲落模式的基本思想是直接對原始序列求取模式序列，長度為n的時間序列，對應的模式序列為n-1，所有的點都參與模式的劃分，噪聲的影響不可忽略。

2 基于形態模式的相似度量算法

2.1 形態模式定義

為了能夠更細致地反映數據的變化趨勢，本文將序列的變化趨勢分為七種情況：快速上升、勻速上升、緩慢上升、持平狀態、緩慢下降、勻速下降、快速下降，并分別用{3，2，1，0，-1，-2，-3}表示對應趨勢。序列的形態變化趨勢如圖1所示，其中橫線表示時間軸，箭頭方向代表序列的當前趨勢。

圖1 時間序列的形態模式

斜率是反映曲線變化快慢的變量，為了能準確刻畫時間序列的形態模式，本文方法在序列分段表示的基礎上，首先取得分段序列對應的斜率序列，然后根據每段的斜率值確定對應的形態模式。

定義2形態模式。已知分段斜率列Sk={k1,…,ki,…,km}，參考表1中分段斜率和形態模式之間的關系，形態模式序列P={p1,…,pi,…,pm}中，pi可根據對應的分段斜率值確定。

表1 分段斜率和形態模式之間的關系

若ki≥0且ki>1則當前分段和時間軸之間的夾角大于45度，此時序列處于快速上升狀態，形態模式為3，若ki<0且ki>1，則序列在快速下降，形態模式為-3，其他形態模式可類比得到。

2.2 距離度量方法

形態模式序列是由-3到3之間的數字構成的特殊字符串，形態模式序列的相似性度量可以采用最長公共子序列方法。它的基本思想是對于兩個不同的模式序列，首先求得二者之間的最長公共子序列，進而計算該子序列在整個模式序列之中所占的比重，作為序列之間的相似值。下面分別給出最長公共子序列定義和基于最長公共子序列的相似度定義。

最長公共子序列可以通過動態規劃方法求得，遞歸求解公式如下：

(4)

S1(i)和S2(j)分別表示S1的第i個元素和S2的第j個元素，其中L(i,j)表示S1和S2的最長公共子序列長度。

如果不同序列之間存在最長公共子序列，那么時間序列的相似性可由最長公共子序列在原序列中的比值決定。根據定義3可以得出基于最長公共子序列的相似性計算公式：

(3)

式中ls表示最長公共子序列的長度，min(ls1,ls2)表示序列S1和S2中較短的序列長度。

2.3 基于形態模式的相似度量算法

基于分段形態模式的相似度量算法將時間序列數據分段后轉化為七元形態模式，主要目的在于：① 通過分段線性表示方法降低噪聲對模式劃分的影響，縮減模式序列的長度，提高相似度量的計算效率；② 把序列形態趨勢表示為七元形態模式，使數據的模式表示更貼近數據的實際變化趨勢；③ 用最長公共子序列方法計算形態模式距離可避免具體數據點的值對結果產生影響。

下面給出基于分段形態模式的時間序列相似度量算法邏輯：

輸入：原始時間序列

Step1選取原始序列的關鍵點，對序列進行分段線性表示；

Step2對重要點表示的分段序列進行等長處理；

Step3把分段序列表示為斜率序列；

Step4根據每個分段的斜率值確定該子段對應的形態模式；

Step5確定不同序列對應的形態模式序列；

Step6使用遞歸方法計算不同形態模式序列的最長公共子序列；

Step7根據最長公共子序列計算序列的相似度。

輸出：不同序列的相似度值。

3 實驗結果與分析

為了檢驗提出的改進方法的有效性和優勢，將本文方法應用于時間序列的聚類工作中。實驗環境為Windows操作系統，硬件環境為2.5 GHz CPU，4 GB內存，開發工具為Matlab。

實驗數據使用UCI數據庫中的Isolet5數據集。從Isolet5數據集中抽取第13類和第14類時間序列，共119條序列，其中第13類包含59個序列，作為類別一，第14類包含60個序列，作為類別二，每條序列包含617個屬性。將序列標準化后，通過三種方法進行對比實驗。

方法1即歐氏距離方法，不對時間序列進行任何壓縮或變換處理，直接進行K-means聚類；方法2即漲落模式方法，不對時間序列進行壓縮，直接把時間序列表示成漲落模式序列，然后進行K-means聚類；方法3是本文給出的方法，先對序列進行分段壓縮表示，再進行形態模式轉換，最后進行K-means聚類。

通過平均查全率和平均查準率對聚類結果進行評估，表2給出了查準率和查全率相關變量說明。

表2 查準率和查全率對應的聚類結果

對比表2中的參數根據查準率和查全率計算公式可以得到聚類結果的平均查全率和平均查準率。

其中n表示樣本中的類別數，Pi和Ri表示第i類的查準率和查全率。

使用查準率和查全率公式計算表3中的聚類結果，得到如表4所示的不同方法聚類結果的平均查準率和查全率。從表4可以看出，與方法1和方法2相比，方法3的平均查準率和平均查全率都有所提高。方法1直接對序列計算歐式距離，沒有進行維度約簡，計算量大而且容易受噪聲影響，因此聚類結果不理想；方法2通過劃分漲落模式從趨勢的角度判斷相似度，不受具體數據點值的約束，相對歐氏距離，度量精度有所提高，但是因為直接對原始序列進行模式劃分，所以時間復雜度較高，而且噪聲的干擾也有一定的影響；方法3首先對序列進行分段表示，實現了維度約簡，同時減少了噪聲的干擾，然后使用七元形態模式進行表示，不僅能反映形態變化趨勢而且能體現變化幅度，與方法1、方法2相比，聚類結果最好，因此本文工作具有有效性和先進性。

表3 三種方法聚類結果

表4 平均查準率和平均查全率

4 結 語

本文針對已時間序列距離度量方法的一些不足，提出了基于形態模式的時間序列相似度量方法。基于分段線性表示的形態模式定義，不僅能降低數據維度，而且能描述序列的變化幅度。在此基礎上通過最長公共子序列方法求形態模式序列的相似性，把時間序列的相似性問題轉化為字符串匹配問題，提高了計算結果的準確性，而且計算過程相對簡單。將本文方法用于時間序列的聚類實驗，發現經過適當的參數選取，能取得較好的聚類效果。下一步工作將考慮如何度量非等長時間序列的相似性。

[1] 吳紅花,劉國華,王偉.不確定時間序列的相似性匹配問題[J].計算機研究與發展,2014,51(8):1802-1810.

[2] Izakian H,Pedrycz W.Anomaly Detection and Characterrization in Spatial Time Series Data:A Cluster-Centric Approach[J].Fuzzy Systems IEEE Transactions on,2014,22(6):1612-1624.

[3] Suntinger M,Obweger H,Schiefer J,et al.Trend-Based Similarity Search in Time-Series Data[C]//Advances in Databases Knowledge and Data Applications (DBKDA),2010 Second International Conference on IEEE,2010:97-106.

[4] 丁永偉,楊小虎,陳根才,等.基于弧度距離的時間序列相似度量[J].電子與信息學報,2011,33(1):122-128.

[5] Chiu B,Keogh E,Lonardi S.Probabilistic discovery of time series motifs[C]//Siam International Conference on Data Mining,SDM 2009,April 30-May 2,2009,Sparks,Nevada,Usa.DBLP,2003:493-498.

[6] Berndt D J,Clifford J.Using Dynamic Time Warping to Find Patterns in Time Series[C]//Working Notes of the Knowledge Discovery in Databases Workshop,1994:359-370.

[7] Lin J,Keogh E,Lonardi S,et al.A symbolic representation of time series,with implications for streaming algorithms[C]//ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery.ACM,2003:2-11.

[8] 李桂玲,王元珍,楊林權,等.基于SAX的時間序列相似性度量方法[J].計算機應用研究,2012,29(3):893-896.

[9] 劉慧婷,倪志偉.基于EMD與K-means算法的時間序列聚類[J].模式識別與人工智能,2009,22(5):803-808.

[10] 肖瑞,劉國華.基于趨勢的時間序列相似性度量和聚類研究[J].計算機應用研究,2014,31(9):2600-2605.

[11] 張海濤,李志華,孫雅,等.時間序列的層次分段及相似性度量[J].計算機工程與應用,2015,51(10):147-151.

[12] 張建業,潘泉,張鵬,等.基于斜率表示的時間序列相似性度量方法[J].模式識別與人工智能,2007,20(2):271-274.

[13] 王釗,湯子健.基于漲落模式的時間序列相似性度量研究[J].計算機應用研究,2017,34(3):697-701.

SIMILARITYMEASUREALGORITHMOFTIMESERIESBASEDONMORPHOLOGICALPATTERN

Wang Rui Jia Ruiyu

(CollegeofComputerScienceandTechnology,AnhuiUniversity,Hefei230601,Anhui,China)

Feature representation and similarity measure of time series is an important foundation of time series data mining. Aiming at the problem that the existing sequence representation method is difficult to reflect the morphological change of the sequence, which leads to the inaccuracy of the similarity measurement results, a new similarity measurement algorithm based on morphological patterns is proposed. On the basis of piecewise linear representation, according to the sequence of slope changes in different periods, the algorithm divides the sequence into different morphological pattern and expresses them with special characters. The time sequence is converted into a sequence of strings. The longest common subsequence method is adopted to calculate the distance of string sequences as the distance between time series. Finally, the effectiveness of the proposed method was verified by experiments. Theoretical analysis and experiments show that the method is insensitive to the value of the data points, which can reduce the interference of noise and has high accuracy.

Time series Similarity Morphological Pattern Slope Sub sequence

TP3

A

10.3969/j.issn.1000-386x.2017.09.049

2016-11-24。國家自然科學基金項目(61202227)；國家科技支撐計劃項目(2015BAK24B01)。王瑞，碩士生，主研領域：數據挖掘，數據智能處理。賈瑞玉，副教授。