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

劉秀梅

(泉州理工學(xué)院)

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

劉秀梅

(泉州理工學(xué)院)

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

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

0 引言

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

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

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

設(shè)時間序列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)表示序列點(diǎn)xi和yi之間的距離.

1.2小波變換[2]

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

(2)

(3)

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

1.3 Haar小波變換

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

(4)

(5)

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

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

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

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

定義1 方差和

(6)

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

定義2 能量

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

(7)

定義3 能量差異

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

(8)

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

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

當(dāng)把X分解到j(luò)尺度時

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

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

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

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

(9)

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

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

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

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

2.1K均值聚類

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

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

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

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

(7)算法收斂產(chǎn)生最終聚類結(jié)果.

2．3聚類結(jié)果評估方法

(1)已知真實(shí)聚類

(10)

(11)

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

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

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

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

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

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

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

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

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

表3 選擇的小波變換尺度

(2)聚類結(jié)果比較

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

表4 聚類結(jié)果對比

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

表5 運(yùn)行時間對比 s

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

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

[1] 曲文龍,張德政,楊炳儒.基于小波和動態(tài)時間彎曲的時間序列相似匹配[J].北京科技大學(xué)學(xué)報,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

(責(zé)任編輯：季春陽)

TimeSeriesClusteringBasedonWaveletTransform

Liu Xiumei

(Quanzhou Institute of Technology)

O211.61

A

1000-5617(2017)02-0013-05

2016-12-11