劉秀梅

(泉州理工學院)

基于小波變換的時間序列聚類

劉秀梅

(泉州理工學院)

針對傳統(tǒng)以歐氏距離為相似性度量的K-均值聚類算法應用于時間序列數(shù)據(jù)上存在的時間軸偏移敏感性問題及以動態(tài)時間軸彎曲距離為相似性度量的高計算復雜性問題，提出基于小波變換的動態(tài)時間彎曲距離作為相似性度量方法，根據(jù)提取的小波低頻系數(shù)與原時間序列之間的低能量差異來選擇小波變換的尺度，能保證選取的特征在擁有盡量低的維數(shù)的同時保留時間序列主要信息.實驗結果顯示，基于小波動態(tài)時間彎曲距離的K均值聚類比基于歐氏距離的K均值聚類效果好，運行速度比動態(tài)彎曲距離快.

時間序列;小波變換;聚類

0 引言

傳統(tǒng)在時間序列數(shù)據(jù)的聚類，以歐氏距離為相似性度量的K-均值聚類算法存在時間軸偏移敏感性問題;以動態(tài)時間軸彎曲距離為相似性度量存在高計算復雜性問題.該文提出基于小波變換的動態(tài)時間彎曲距離作為相似性度量方法，根據(jù)提取的小波低頻系數(shù)與原時間序列之間的能量差異來選擇小波變換的尺度，并通過小波變換提取時間序列的低頻系數(shù)作為特征，然后用這些特征作為動態(tài)彎曲距離計算的輸入值.這樣既降低了時間序列的維數(shù)，降低了動態(tài)彎曲距離的計算復雜度，又保留了時間序列的主要特征.

1 小波動態(tài)時間彎曲距離

1.1動態(tài)時間彎曲距離[1]

設時間序列X=(x1,x2,…,xn),Y=(y1,y2,…,yn)，其長度分別為n和m.它們之間的動態(tài)時間彎曲距離定義為：

Ddtw(<>,<>)=0,

Ddtw(X,<>)=Ddtw(<>,Y)=∞,

(1)

Ddtw(X,Y)=d(x1,y1)+

其中<>表示空的時間序列，d(x1,y1)表示序列點xi和yi之間的距離.

1.2小波變換[2]

小波變換是一種將數(shù)據(jù)、函數(shù)或者算子分解成不同頻率的成分，然后在與其尺度相匹配的分辨中研究各個成分的工具[3].可以總結為下面公式尺度函數(shù)(2)和小波函數(shù)(3)：

(2)

(3)

從公式(2)和(3)可以看出小波函數(shù)是通過尺度函數(shù)構造的，其中hn,gn是兩個關鍵系數(shù)，分別定義為低通濾波器和高通濾波器.

1.3 Haar小波變換

Haar小波變換的尺度函數(shù)φ(t)和小波函數(shù)ψ(t)的定義為：

(4)

(5)

Haar變換可以被認為是對一個離散函數(shù)進行一系列的平均化和差分化操作.該文在每兩個相鄰的f(x)值之間計算其平均值和差值.

1.4小波變換不同尺度系數(shù)的選擇

該文把某一尺度j的低頻系數(shù)作為重構原始時間序列的特征，那么選擇系數(shù)的關鍵就在于如何選擇適當?shù)某叨萰.采用原始時間序列與小波特征的能量差異來選擇適當?shù)男〔ㄗ儞Q尺度[4].

提取的特征必須和原始的數(shù)據(jù)相似，要有一種適合的度量方法來衡量特征與數(shù)據(jù)之間的相異性，這里采用方差和來衡量時間序列和它的近似表示的差異.

定義1 方差和

(6)

因為對應j尺度的特征的長度比時間序列X小，因此不能直接通過公式計算.可以用低頻系數(shù)Aj來重構一序列 ，然后計算X′和X之間的平方誤差和.在正交小波變換中，能量是保持不變的，即E(X′)=E(Aj)，因此X′與X的能量差異等同于低頻系數(shù)Aj與X之間的能量差異.這個屬性使得不用重構X′，就能衡量Aj重構的X′與X之間的相似性.

定義2 能量

時間序列X={x0,x1,…,xn-1}，那么X的能量為

(7)

定義3 能量差異

時間序列X={x0,x1,…,xn-1}，經過j尺度的小波變換低頻系數(shù)為Aj，那么Aj與X之間的能量差異為

(8)

X′可以通過在Aj后補0(補0后要保證重構X′的長度與X長度一樣)重構而成.小波變換是保持能量不變的，因此j尺度的小波系數(shù)的能量應該和它重構的時間序列的能量是一樣的.

E(X′)=E(Aj)和E(X)=E(Aj-1)+E(Dj-1)

當把X分解到j尺度時

因此，Aj和X的能量差異ED(X,Aj)就是在尺度j和高于j尺度的小波高頻系數(shù)之和.

X的j尺度小波變換系數(shù)為{Aj,Dj,…,DJ-1}，X′的j尺度小波變換系數(shù)為{Aj,0,…,0}.因為歐氏距離同樣在小波變換中保持不變，所以

因此X和X′的方差和等同于X和Aj的能量差異

SSE(X,X′)=ED(X,Aj)

(9)

對于小波變換從時間序列提取的特征中，尺度高的特征與尺度的低的特征相比保留更多的小波系數(shù)，維數(shù)也更高，因此隨著小波變換的尺度的遞減，SSE(X,X′)值會遞增.理想尺度的特征應該同時具有較低的維數(shù)和較小的SSE(X,X′).

下面給出了小波變換選擇低頻系數(shù)的變換尺度的步驟：

(3)若找不到這樣的尺度，選擇尺度1作為小波系數(shù)提取的變換尺度.

2 基于小波變換的時間序列聚類

2.1K均值聚類

由于K均值的聚類結果受初始中心的選擇影響很大，若隨機選擇序列作為初始聚類中心，那么聚類結果變化太大，這里采取兩次K均值聚類，第一次采用歐氏距離度量方法，迭代收斂后產生的聚類中心作為第二次K均值聚類的初始聚類中心，第二次K均值聚類采用的是動態(tài)彎曲距離度量方法，這樣能使聚類結果比較穩(wěn)定.

2.2基于小波變換的時間序列聚類算法步驟

(2)選擇小波變換提取特征的尺度j.

(5)用聚類中心c作為第二次K均值聚類的初始聚類中心.

(7)算法收斂產生最終聚類結果.

2．3聚類結果評估方法

(1)已知真實聚類

(10)

(11)

公式(11)中的|·|表示集合的勢.

3 實驗及結果分析

3．1實驗環(huán)境及實驗數(shù)據(jù)

在實驗中，運行的環(huán)境是Pentium4 1.7GHz中的Matlab 6.5，實驗數(shù)據(jù)采用keogh等人[6]提供的用于時間序列聚類的數(shù)據(jù)(見表1).

表1 聚類數(shù)據(jù)描述

3.2實驗結果及分析

該文設計兩個實驗，實驗一：計算出數(shù)據(jù)在不同Haar小波變換尺度下高頻系數(shù)的能量，然后根據(jù)能量差異來選擇小波變換的尺度.這樣做的原因在于提取的時間序列的特征不僅要能提高聚類效率，而且不能丟失原時間序列的主要信息，否則聚類失去了實際意義.實驗二：在該實驗中，比較以下幾種方法的聚類準確性和運行時間：①采用歐氏距離的kmeans聚類(簡稱EKC)；②采用動態(tài)彎曲距離的kmeans聚類(簡稱DKC)；③基于小波的歐氏距離的kmeans的聚類(簡稱WEKC)；④基于小波的動態(tài)彎曲距離的kmeans的聚類(簡稱WDKC).

(1)小波變換尺度的選擇

表2 不同小波變換尺度下高頻系數(shù)的能量

表3 選擇的小波變換尺度

(2)聚類結果比較

采用公式(10)(11)作為評價聚類結果的度量，近似度越高表示聚類的準確率越高，聚類方法的性能越好(見表4).

表4 聚類結果對比

從表4中發(fā)現(xiàn)小波變換對采用歐氏距離的kmeans聚類的聚類效果有適當?shù)母倪M，改進的原因主要在于小波變換提取了時間序列中的低頻系數(shù)并去除了高頻系數(shù)中存在的噪聲的影響，但改進不大，因為小波變換并沒有解決歐氏距離對于時間軸彎曲的敏感性.而動態(tài)彎曲距離由于它支持時間軸彎曲，與歐氏距離方法EKC相比，對聚類效果的改善非常明顯.

表5 運行時間對比 s

雖然動態(tài)彎曲距離可以解決時間軸彎曲的問題從而改善聚類質量,見表4，但由于其時間復雜性太高，運行時間過長,見表5.歐氏距離雖然在運行速度方面對動態(tài)彎曲距離有著明顯的優(yōu)勢，但是不支持時間軸彎曲，使得其聚類質量并不高.而采用該文方法小波變換提取的特征系數(shù)在對時間序列降維的同時保留時間序列的主要信息，因此在不降低聚類的質量的同時明顯改善了基于動態(tài)彎曲距離聚類的效率，也就是說基于小波變換的動態(tài)彎曲距離比普通動態(tài)彎曲距離效率提高達60%左右.

基于小波的動態(tài)彎曲距離能夠很好的解決時間序列的時間彎曲問題，從而提高聚類的準確率，但是聚類的準確度還有提升的空間，距離度量方法還有提升的空間，現(xiàn)有的距離度量方法大多是把求解序列之間的相似度轉化為序列中點與點之間的距離之和，很容易忽略了序列中點與點本身的聯(lián)系.因此，下一階段的研究方向是一種能更好地把序列中點與點之間的聯(lián)系融合進距離度量方法.

[1] 曲文龍,張德政,楊炳儒.基于小波和動態(tài)時間彎曲的時間序列相似匹配[J].北京科技大學學報,2006(4):36-41.

[2] Chan K,Fu W.Efficient time series matching by wavelets[C].In:Proceedings of the 15th IEEE International Conference on Data Engineering,Sydney:IEEE,1999.126-133.

[3] Li Tao,Li Qi,Zhu Shenghuo,et al.A Survey on Wavelet Applications in Data Mining.SIGKDD Explorations,2003,4(2):49-68.

[4] Zhang H,Ho T B,Zhang Y,et al.Unsupervised Feature Extraction for Time Series Clustering Using Orthogonal Wavelet Transform[J].Journal Informatica,2006.

[5] Gavrilov M,Anguelov D,Indyk P,et al.Mining the stock market:Which measure is best?[J].In Proc of KDD’00,2000:487-496.

[6] Keogh E,Xi X,Wei L&Ratanamahatana C A.[EB/OL].The UCR Time Series Classification/Clustering Homepage:www.cs.ucr.edu/～eamonn/time_series_data/,2006.

Abstract:As Euclidean distance and its enlargement were sensitive to the shift of time axis and the defect of dynamic time warping in time complexity,a wavelet based dynamic time warping distance is proposed,which choose the wavelet coefficient by lower sum of squared errors between the features and the original time series,it can reduce the dimension of time series and preserve most information of the time series at the same time.TheKmeans for twice to limit the influence of choosing initial clustering center are applied.Euclidean distance for the first time and the final clustering center preparing for the initial clustering center of the second time are adopted,based danymic time warping distance.Expremental results show that the effect of clustering base wavelet based danymic time warping distance is better than that based Euclidean distance,and the run time of wavelet based danymic time warping distance is fast than dynamic time warping distance.

Keywords:Time series; Wavelet tranform;Clustering

(責任編輯：季春陽)

TimeSeriesClusteringBasedonWaveletTransform

Liu Xiumei

(Quanzhou Institute of Technology)

O211.61

A

1000-5617(2017)02-0013-05

2016-12-11