摘  要: 提出了一種基于DTW的符號化時間序列聚類算法，對降維后得到的不等長符號時間序列進行聚類。該算法首先對時間序列進行降維處理，提取時間序列的關鍵點，并對其進行符號化；其次利用DTW方法進行相似度計算；最后利用Normal矩陣和FCM方法進行聚類分析。實驗結果表明，將DTW方法應用在關鍵點提取之后的符號化時間序列上，聚類結果的準確率有較好大提高。
關鍵詞: 時間序列；DTW；SAX；Normal矩陣；FCM

    時間序列(Time Series)挖掘是數據挖掘中的一個重要研究分支，有著廣泛的應用價值。近年來，時間序列挖掘在宏觀的經濟預測、市場營銷、客流量分析、太陽黑子數、月降水量、河流流量、股票價格變動等眾多領域得到了廣泛應用[1]。
    時間序列的相似性是衡量兩個時間序列相似程度的一個重要指標，它是時間序列聚類、分類、異常發現等諸多數據挖掘的基礎，也是研究時間序列挖掘的核心問題之一[2]。歐氏距離(Euclidean)和動態時間彎曲距離(Dynamic Time Warping)是計算時間序列相似性時經常被采用的兩種度量方式。歐氏距離對時間軸上的輕微變化非常敏感，一些輕微的變化可能使歐氏距離的變化很大，而動態時間彎曲距離可以有效地消除歐氏距離這個缺陷，動態時間彎曲可以廣泛應用在自然科學、醫學、企業和經濟等方面[3]。SAX(Symbolic Aggregate Approximation)[4]是一種運用符號化方法對時間序列進行表示、維度約簡及相似性度量的方法。但SAX方法采用PAA算法將時間序列平均劃分，不能很好地計算序列之間的相似度。而利用均分點和關鍵點對序列進行分段，既考慮了序列本身概率分布的變化,又兼顧到序列形態的變化。
    本文提出一種基于DTW的符號化時間序列聚類算法，在提取關鍵點之后，再進行符號化時間序列，以達到降維的目的。降維之后得到的符號序列為不等長序列，采用動態時間彎曲距離(DTW)方法進行計算, 魯棒性好。然后通過DTW得到的距離矩陣構建復雜網絡，并尋找其社團結構,實現了符號時間序列聚類。本文用DTW方法進行相似性度量比KPDIST[4]在聚類結果的準確率上有較好大提高。
1 相關知識
1.1時間序列關鍵點的選取
　　基于參考文獻[5]可知，時間序列中的極值點EP成為關鍵點KP的條件為：
　　條件1. xi保持極值的時間段與該序列長度的比值必須大于某個閾值C；
　　條件2. 若條件1不滿足，則包含xi的最小序列模式<xi-1,xi,xi+1>中, 三點連線形成的夾角小于篩選角度α0。

2.2 基于DTW的符號化聚類算法
    輸入：時間序列集。
    輸出：聚類結果。
    (1)對每個序列，運用上面的算法得到最終的關鍵點序列；
    (2)計算序列C在各區間[KPci,KPcj)內的均值，并表示為符號序列；
    (3)對序列C和序列Q的符號序列進行相似性距離計算（DTW計算和KPDIST計算）；
    (4)根據相似度，構建復雜網絡G；此處要給相似度賦予一個閾值,相似性小于閾值的點則認為無邊連接。
    (5)用Normal矩陣方法FCM算法對復雜網絡G進行社團劃分，得到聚類結果。
3 實驗結果與分析
    本文實驗采用Keogh博士的Synthetic Control和ECG數據集。實驗環境為2.66 GHz CPU Pentium@4 PC機， 1 GB內存，操作系統為Windows XP Professional。算法實現軟環境為matlab 7.0和VC++6.0。Synthetic Control數據集的實驗數據為300條，每條時間序列長度為60。ECG數據集有100個樣本序列,每條時間序列長度為96（http://www.cs.ucr.edu/~eamonn/time_series_data/）。原時間序列維度為60和96，經過關鍵點提取、符號化之后，維度大大降低,這為后期處理帶來了很大的方便。 在本實驗中，關鍵點提取時篩選角度為45°，預設的壓縮率為80%，劃分了4個區間段，用符號表示時為a,b,c,d四種字母。由于實驗數據的樣本個數很多，這里只顯示synthetic control的部分實驗結果。表1為降維后的前4個符號序列實驗結果。

    表2為Normal矩陣得到的非平凡特征值對應的非平凡特征向量，根據譜平分算法思想，同一社團內的節點相應的元素xi非常接近。從特征向量的分析中可以看出，將DTW與復雜網絡知識應用在符號化時間序列上是一種較好的創新。

    由DTW距離矩陣得到的網絡中，第一非平凡特征值取值為：0.252 9，而通過KPDIST距離矩陣得到的復雜網絡中，第一非平凡特征值取值為：0.125 7，從特征值中就可以初步判斷，DTW得到的特征值更為準確，這兩個特征值對應的特征向量的區間表如表2所示。
    表3為兩種算法對同樣數據集進行聚類得到的結果。數據集Synthetic control采用本文方法正確率為76.3%。而利用KPDIST算法正確率為69%；數據集ECG，本文的正確率為72%，KPDIST的正確率為65%。

    SAX是一種符號化的時間序列相似性度量方法，該方法在對時間序列劃分時，采用了PAA算法的均值劃分，得出的結果不能精確地表示出原時間序列，故將關鍵點提取方法與PAA方法相結合,在對原序列降維的同時又能更準確地表示原時間序列。本文將復雜網絡知識和時間序列降維方法相結合，給出了一種時間序列的聚類方法。該算法用DTW算法計算時間序列間的相似度，而后從時間序列的相似度得到一個復雜網絡，此復雜網絡表示了時間序列相互間的關系。最后采用Normal矩陣的方法進行網絡劃分，得到一個網絡的社團結構。從這個社團結構中已能看出樣本時間序列的歸屬類別，但為了結果更加清晰，用具體數字來體現，所以采用了FCM聚類算法進行最后的聚類。實驗結果表明，用DTW方法計算序列之間的相似度結合在降維后的符號化時間序列上比原文KPDIST方法在準確率上有較好大提高。
參考文獻
[1] 毛國君,段立娟,王實,等.數據挖掘原理與算法（第二版）[M].北京：清華大學出版社，2007.
[2] 劉懿,鮑德沛,楊澤紅.新型時間序列相似性度量方法研究[J].計算機應用研究,2007,24(5):112-114.
[3] KEOGH E, RATANAMAHATANA C A. Exact indexing of dynamic time warping[J]. Springer-Verlag London Ltd, 2005, 10.1007/s10115-004-0154-9:358-386.
[4] 閆秋艷,孟凡榮.一種基于關鍵點的SAX改進算法[J].計算機研究與發展,2009,46(z2):483-490.
[5] 杜奕.時間序列挖掘相關算法研究及應用[D].合肥：中國科學技術大學，2007.
[6] 汪小帆,李翔,陳關榮.復雜網絡理論及其應用[M].北京：清華大學出版社，2006:169-171.