基于時間序列線性擬合方法的時間序列層次聚類

王赫楠 燕燕 王甜宇 王和禹

(遼寧中醫藥大學信息工程學院,遼寧沈陽 110032)

基于時間序列線性擬合方法的時間序列層次聚類

王赫楠 燕燕 王甜宇 王和禹

(遼寧中醫藥大學信息工程學院,遼寧沈陽 110032)

本文利用一種有效的時間序列線性擬合方法。算法所選出的關鍵點是對時間序列的形態變化影響較大的點,將這些點依次連接實現時間序列的線性擬合。這種線性擬合算法在剔除了噪聲的同時,能更精確的定位時間序列中的關鍵點。實驗結果表明,該方法能更好的近似表示原時間序列。和已有的方法相比,該方法擬合后的時間序列和原時間序列之間的擬合誤差更小。并且在該方法的基礎上運用動態彎曲距離進行層次聚類得到了較好的結果。

時間序列 線性擬合 擬合誤差 關鍵點 動態彎曲距離

1 引言

時間序列數據挖掘是數據挖掘的一個重要分支，廣泛應用于醫學，金融，工業等眾多領域[1-2]。但由于時間序列有如下的特點，(1)時間序列的數據量巨大；(2)時間序列的噪聲干擾嚴重；(3)時間序列的短期波動頻繁。所以直接在原始時間序列上進行相似性查詢[3]、分類聚類[4]、模式挖掘等操作很難得到滿意的結果。因此許多研究者提出了時間序列的線性擬合表示方法，刻畫時間序列主要形態而忽略那些微小的細節，從而在保持序列的主要特征不變的情況下達到簡化計算量的目的。

本文詳細分析了如何抽取時間序列中的關鍵點，利用了一種有效的線性擬合方法FPSegmentation(Feature Piecewise Segmentation)。利用非單調序列中極值點保持時間段閾值來選取關鍵點，這種線性擬合方法相對于以往的方法不僅將壓縮率提升了，而且能更好的近似表示原時間序列，通過使用動態彎曲距離，對時間序列進行層次聚類得到了較好的結果。

2 基本概念

定義1：時間序列：時間序列是由記錄值和記錄時間組成的元素的有序集合，記為Q={q1=(p1，v1)，q2=(p2，v2)，…，qn=(pn，vn)}，元素qi=(pi，vi)表示時間序列在vi時刻的 記錄值為pi。一般情況下，時間序列的采樣間隔 v=vi-vi-1相等，可以看做v1=0，v=1，此時間序列記為時Q={q1，q2，…qn}。qi表示時間序列Q的第i個元素。

定義2：時間序列分段線性表示的擬合誤差：時間序列Q={q1，q2，…qn}，通過線性分段擬合后得到的時間序列L(Q)={L(qi1，qi2)，L(qi3，qi4)，…，L(qik-1，qik)}，其中L表示連接兩點的直線段。將L(Q)通過線性差值之后得到的時間序列記為Q’={q1’，q2’…，qn’}，那么該線性表示和原時間序列之間的擬合誤差定義為

Fig.1 the effect of Hierarchical clustering圖1 層次聚類的效果

3 特征點擬合法

特征點擬合法F P S e g m e n t a t i o n是對極值點擬合法IPSegmentation的改進。特征點擬合法所選出的關鍵點是對時間序列的形態變化影響較大的點，將這些點依次連接實現時間序列的線性擬合。具體實現原理如下所述：

FPSegmentation算法把時間按序列Q的起點和終點保留下來作為特征點，其它關鍵點需滿足以下兩點要求：①所選的特征值點必須是序列的極值點；②該極值點保持極值的時間段(即該點的前后極值點之間的時間段)與該序列長度的比值必須大于某個閾值M(參數M看作特征點的判斷影響因子，M的取值和領域知識、序列長度以及實際的關注點有關，一般在0.01-0.1之間)。

4 基于重要點的動態彎曲距離

動態時間彎曲距離在語音處理領域得到廣泛的研究，并且由Berndt和Clifford首次引入到數據挖掘領域。到現在，動態時間彎曲距離已經在醫療信號、生物學數據以及指紋識別等領域得到快速的發展。下面簡要介紹動態時間彎曲距離的基本定義和常用的計算方法.

定義1.時間序列x和y之間的動態時間彎曲距離定義為：

動態時間彎曲距離可以用動態規劃的方法計算，時間復雜度為O(|z|.|y|)。

我們在FPSegmentation的基礎上，運用動態彎曲距離，對于時間序列進行層此聚類，得到了較好的結果，如第五節中實驗所示。

5 實驗結果及分析

我們使用數據集system control chart。該數據集包括600個樣本，每個樣本60個點，共6類，每個類都是100個樣本。通過FPSegme ntation方法提取特征點，我們的聚類正確率可以達到70%以上。

圖中有三種樣本的時間序列分類明顯錯誤，其它的時間序列分類結果較好，分類的正確率能夠達到70%以上。

6 結語

特征點線性擬合法FPSegmentation能夠更好的擬合原時間序列，擬合后的時間序列和原時間序列相比，擬合誤差更小，壓縮率更大。我們在FPSegmentation的基礎上，利用動態彎曲距離，對擬合后的時間序列進行層次聚類得到了較好的結果。

[1]Park S,Kim S,Chu W. Segmentation-based approach for subsequence searchs in sequence databases[C]/.Proceedings of the 16th ACM Symposium on Applied Computing.New York: ACM Press,2001:248-252.

[2]肖輝,胡運發.基于分段時間彎曲距離的時間序列挖掘[J].計算機研究與發展.2005.42(1):72-78.

[3]Park K B,Fink E. Search for patterns in compressed time series[J]. International Journal of Image and Graphics,2002,2(1):89-106.

[4]D.J.Berndt,J.Clifford.Using dynamic time warping to find patterns in time series.Working Notes of the Knowledge Discovery in Databases Workshop,Seatle,WA,1994.