一種時間序列數據的動態k-means 聚類算法?

冀敏杰 肖利雪

（西安郵電大學計算機學院 西安 710121）

1 引言

時間序列是指數據集隨著時間變化而變化的數據集，在時間軸上形成連續的序列，它表明了數據內部狀態隨時間變化的規律。如今，時間序列［1～2］越來越廣泛應用與氣象［3］、醫療［4］、金融［5］和網絡安全［6］等各個重要領域。聚類對于時間序列的分析作為主要研究方法，在現如今的學術領域中備受關注［7～9］。在數據挖掘領域中，聚類分析既可以作為數據挖掘過程中的一個環節，又可以作為獲取數據分布情況的工具。

k-means 算法是聚類算法中一種典型的算法，最早由MacQueen［10］提出，具有運算簡便，時間復雜度低等優點。k-means 算法的缺點也隨著人們的研究而暴露出來，主要包括三點：一是K 值需要預先給定；二是k-means 算法對初始選取的聚類中心點很敏感，不同的中心點聚類結果有很大的不同［11］。三是對于時間序列上的聚類僅僅是多次的靜態聚類，沒有利用時間序列之間的關聯性進行動態聚類。針對這些問題，國內外學者紛紛提出眾多的解決方法：Rodriguez A等［12］提出的類簇中心都處在局部密度比較大的位置，運用此思想可以確定最佳初始聚類中心及數據集的最佳類簇數目。賈瑞玉［13］等在這個思想的基礎上，運用殘差分析的方法，選取殘差絕對值大于閾值的異常點作為聚類中心。Lei Gu［14］，M.S.Premkumar［15］和C.Lasheng［16］等采用不同的數學方法確定初始聚類中心。Agrawal等［17］首次提出使用離散傅里葉變換將時間序列的時間域轉換為頻率域的特征表示方法。文獻［18］利用Haar 小波變換表示時間序列數據，采用k-Means 算法和歐氏距離對新特征空間中的數據進行聚類。劉琴等［19］結合滑動窗口及類k-means聚類算法提出了一種基于滑窗不等長時間序列的短時間序列距離的聚類算法，能夠解決不等長時間序列聚類的問題，但最佳聚類個數難以確定。謝福鼎等［20］通過等長處理后基于歐氏距離及模糊C 均值聚類算法實現時間序列聚類。上述時間序列聚類算法，均是將長度為n 的時間序列看做n 維空間的一個點，利用處理靜態數據的方法聚類時間序列。但是時間序列具有隨時間改變的動態性能，相鄰時間序列之間具有關聯性，靜態聚類不能反映時間序列變化的特性。

針對以上問題，本文提出DKCA/TSD 算法。該算法通過時間序列數據之間的關聯性，把前一時刻最佳質心應用于后一時刻變化的數據集中，讓相鄰的時間序列關聯起來進行聚類。有效地解決了初始時刻類中心選取困難以及利用時間序列之間的關聯性進行動態聚類。不僅在每個時間片上聚類結果更加準確，而且每個時間片上聚類的時間效率更好。

2 k-means算法介紹

2.1 相關定義

其中nj是類Cj中數據對象個數。

2.2 k-means算法

k-means 算法是一種基于樣本間相似性度量的間接聚類方法，也被稱為K均值算法。算法的主要思想是通過迭代的過程把數據集劃分為不同的類別，使得評價聚類性能的準則函數達到最優。算法描述如下：

輸入：簇的個數K與數據集合ξ。

輸出：K個簇，每個數據所屬類別標簽。

1）隨機選取k個點作為初始聚類別的中心。

2）將數據集中的數據分配到距離最近中心點的類中。

3）使用每個簇中的樣本數據均值作為新的聚類中心。

4）重復步驟2）與3）直至算法收斂。

5）結束，得到K個結果簇。

3 時間序列數據及聚類過程分析

3.1 時間序列數據關聯性分析

不失一般性，一個時間片上的聚類可以描述：數據集ξ由n 個點組成，x1，x2，…，xn。每個點可用d維表示為xi=（xi1，xi2，…，xid）。給定數據集ξ，聚類算法試圖找到一組簇類集合C=｛C1，C2，…，Ck｝使得簇間結構盡可能不同，而簇內結構盡可能相似。其中每個簇的質心點由CEj表示，j=1，2，…，k。與之不同的是，一系列時間片的連續的多個聚類過程，其中兩個相鄰時刻的連續聚類過程可表示為：ti時刻集合中有ni個元素且構成mi個類。而在時間相鄰的ti+1時刻，集合中元素變為ni+1且構成mi+1個類。

假 設 在ti時 刻 中 ，有ni個 元 素 的 集 合 ξi=｛x1，x2，…，xni｝。在ti+1時刻中，有ni+1個元素的集合ξi+1=｛x1，x2，…，xni+1｝?；趖i時刻集合的狀態，元素經過元素消失、元素增加、元素位移或者元素不變的情況，形成ti+1時刻集合總元素為ni+1的新聚類的過程，兩個連續時刻間ξi與ξi+1中元素的變化大體有以下幾種情況：1）元素消失；2）元素新增；3）元素位移；4）元素不變，以下是上述幾種元素狀態的定義。

定義3 元素消失。ti時刻元素xi∈ξi，ti+1時刻元素xi? ξi+1。

定義4 元素新增。ti時刻元素xi∈ ξi，在ti+1時刻元素 ?xi?ξi。

定義5 元素位移。ti時刻元素xi∈ ξi，在ti+1時刻元素xi+1∈ ξi+1，?xi≠ξi+1。

定義6 元素不變。ti時刻元素xi∈ ξi，在ti+1時刻元素xi+1∈ ξi+1，?xi=ξi+1。

元素的變化導致集合結構發生變化，而相應概率則決定了集合變化趨勢。假設ti+1時刻相對ti時刻有w1個元素不變的概率為p1，w2個元素消失的概率為p2，w3個元素新增的概率為p3，w4個元素位移的概率為p4，那么這種情況下從ti時刻變化到ti+1時刻的概率為

為了便于分析，上述四種情況可分為元素發生變化和元素不發生變化兩種，假設元素位移、消失、增加的元素變化概率為p，那么元素不變的概率為1-p，則集合ξi變化為ξi+1的概率α為

由于ti+1時刻元素數量變為ni+1，而ni+1=w1+w2+w3+w4，則式（2）可寫為

顯然，ti+1時刻的狀態和w1的大小有直接關系。對式（3）求關于w1偏導數有：

式（4）為0 時，p=0.5 是一個極值點。當p＜0.5時，函數遞增，當p＞0.5 時，函數遞減。由此可知，當p＜0.5 時且w1越大，形成ti+1時刻情況概率α越大。即當p＜0.5 時，ti+1時刻大多數元素不變時概率最高。

結論1：當p＜0.5 時且w1越大時，ti+1時刻的集合類結構很大程度不會被破壞。也就是說，p＜0.5 時且w1越大時，ti+1時刻類別數目發生改變的概率很小。

3.2 k-means聚類算法在動態聚類過程的案例分析

本節對時間序列上的兩個相鄰時刻聚類過程分析，采用k-means 算法與DKCA/TSD 算法進行對比分析。如圖1（a）是二維平面上ti時刻數據集合ξi=｛1，1；1，2；1.6，1.45；2，1；2，2；2.5，1.55｝，圖1（b）是二維平面上ti+1時刻數據集合ξi+1=｛1，1；1，2；1.6，1.45；2，1；2，2｝，顯然圖1（a）和（b）是時間序列數據相互關聯的數據集，即元素F在ti+1時刻消失。為了分析時間序列上的動態聚類的過程，元素新增和元素位移與元素消失的情況類似，故本節只給出元素消失的例子。

對于時間序列上動態聚類，采用k-means 算法對元素消失的情況進行分析，給出ti時刻和ti+1時刻采用k-means 聚類的結果分別如圖2（a）和（b）所示。

圖2 中不同形狀表示不同的類，×表示類的質心。由圖2 中（a）可知，當元素F 消失后，采用傳統的k-means 算法對變化后的數據進行聚類時，需要調用k-means 算法重新對變化后的數據進行聚類，即重新選取初始質心，重新進行一次k-means 全局聚類。此方法對于每一個時間片相當重新調用了一次k-means 算法，沒有達到時間序列數據動態聚類的效果。

圖1 ti時刻和ti+1時刻數據集

針對以上問題，本文提出DKCA/TSD 算法，ti+1時刻的聚類在ti時刻聚類的基礎上，繼承ti時刻最優的質心點進行聚類，而不用重新聚類中的隨機選取質心。由于結論1 可知，變化元素更大概率不會影響原有類結構的破壞，即原有的質心更趨向最優質心，在進行動態聚類的時候更能保證全局最優解以及減少數據的迭代次數，從而減少時間開銷。

4 DKCA/TSD算法

從圖1（a）到圖1（b）的變化過程可知，在ti+1時刻元素F 消失，而圖2（b）是采用k-means 聚類的結果，在基于圖2（a）的質心上，采用DKCA/TSD 算法的結果如圖3所示。

采用DKCA/TSD 算法的計算過程為，當元素F消失后，類2 的質心會向左偏移，由于質心發生了位移，所以需要對剩余的全部元素重新判斷屬于哪個類。在重新判斷的過程中由于元素C 距離類2的質心比較近，故元素C歸屬于類2，然后重新計算類1 和類2 新的質心如圖3 所示，這樣就形成了ti+1時刻的聚類，此情況達到最優解的迭代次數僅僅是2 次，而傳統k-means 算法在此數據達到最優解迭代次數是4 次。并且，在發生元素變化時，可以挖掘出質心變化過程，上述過程質心的變化過程依次向左移動。

圖3 ti+1時刻采用DKCA/TSD算法結果

基于上述分析，給出DKCA/TSD 算法思想和具體步驟。

基本思想：在ti時刻采用k-means 聚類形成最初的聚類，以后的每個時刻基于前一時刻聚類的結果進行時間序列的動態聚類。因為相鄰時刻的數據集具有關聯性，并且前一時刻聚類結果的質心是最佳質心，變化數據較少的情況下質心移動較小，這樣在ti+1時刻的聚類就會減少迭代次數，從而達到更快的達到全局最優解，節省了大量的時間。

DKCA/TSD算法步驟：

輸入：ti時刻聚類結果的質心，ti+1時刻數據集

輸出：ti+1時刻數據聚類結果以及聚類結果質心

1）記錄ti時刻聚類的質心位置。

2）用ti時刻聚類的質心作為ti+1時刻類別中心。

3）將數據集中的數據分配到距離最近中心點的類中。

4）使用每個簇中的樣本數據均值作為新的聚類中心。

5）重復步驟3）、4）直到質心不在變化。

5 實驗

為了分析傳統k-means 算法和DKCA/TSD 算法的性能，本文進行了真實數據和標準數據庫SEQUO IA 2000測試。實驗采用三個真實數據集Iris、Seeds、Wine，標準數據庫SEQUO IA 2000 和人工數據來進行測試。真實數據集Iris數據集包含3 個類和150 個實例，三個類分別為Setosa，Versicolor 和Virginica，每個實例由三個屬性表示：萼片長度、萼片寬度、花瓣長度和花瓣寬度；Seeds數據集是由波蘭科學院農業物理研究所創建的，數據集代表了三種不同類型的小麥。包含3 個類和210 個實例；Wines 數據集是對意大利同一地區生長但來自三種不同品種的葡萄酒進行化學分析的結果，包括3個類和178 個實例，每個實例有13 種屬性。表1 為真實數據集信息說明。

表1 真實數據集信息

5.1 評價指標

本節采用準確率（ACC）、簇內誤差平方和（SSE）、迭代次數（N）、運行時間T（單位ms），四個評價指標對所提算法進行了有效性評價。ACC 表示聚類正確的比例，SSE 表示每個數據到質心點的距離和，N 表示聚類算法達到最優時迭代的次數，T表示算法完成聚類所需時間。ACC的值越大，聚類結果越接近于數據集的真實類劃分，聚類效果越好。SSE 的值越小，表示簇結構越緊湊，聚類效果越好。N 和T 的值越小，表示算法迭代次數小，運行時間快，聚類的效率越好。

5.2 算法性能比較

本文選擇經典的k-means 和本文提出的DKCA/TSD 算法進行比較。為了驗證DKCA/TSD 算法的有效性，本文對真實數據集和標準數據集進行規范處理得到時間軸上的數據集。處理過程為每次在數據集范圍內隨機替換數據集中的5 個數據，一共進行3 次這樣的操作，形成時間片上連續的3 個數據集。由于k-means 有初始類中心選擇敏感問題，文中采用50次k-means算法結果的平均值作為評價指標。數據集Iris，Seeds 和Wine 在這四種評價指標以及3個時間片上的實驗結果分別如表2所示。

表2 k-means和DKCA/TSD算法在數據集Iris，Seeds和Wine測試結果

由表2 可知，在三個真實數據集中，DKCA/TSD 算法的ACC 指標都比k-means 算法高。尤其在Iris 數據集上，最少提高了8.4%，說明采用DKCA/TSD 算法聚類正確比例高。DKCA/TSD 算法的SSE 指標都比k-means 算法低，尤其在Iris 數據集上，最少減少了2.211，說明DKCA/TSD算法聚類結果更加緊湊，聚類效果更好。再者觀察可以發現，DKCA/TSD 算法的N 指標和T 指標都比k-means 要小，平均減少k-means的一半，說明采用DKCA/TSD算法每次迭代的次數更小，運算時間更快。

綜上述分析可知，DKCA/TSD 算法相較于k-means 算法，不僅聚類結果更優，而且每次聚類時間效率有所提升。

為進一步DKCA/TSD 算法相對DBSCAN 算法的時間效率有所提升，實驗采用SEQUO IA 2000 數據庫，處理過程為每次在數據集范圍內隨機替換數據集種的5 個數據，一共進行3 次這樣的操作形成時間片上連續的3 個數據集。數據集采用的數據個 數 分 別 是1000，2000，4000，8000，10000，15000。實驗采用指標T 來統計DBSCAN 和DKCA/TSD 算法的時間效率，T 是SEQUO IA 2000 數據集在3個時間片上的平均值。圖4是實驗結果。

圖4 橫坐標作為數據庫中數據總數，縱坐標為算法執行時間，單位ms。由圖4 可知，采用時間序列上的動態k-means 聚類算法的時間效率明顯優于傳統k-means 算法，尤其在數據集大于4000 時，時間效率差異更加明顯。

圖4 SEQUO IA 2000數據測試的時間結果

6 結語

k-means 算法是一種應用廣泛的聚類算法，在歷史中取得了很多研究成果。但是對于k-means自身存在的缺點，尤其是在時間序列數據中不能進行動態聚類的缺點。本文提出的算法利用時間序列數據之間的關聯性解決了這一難題。本文提出的算法對時間序列數據上聚類的時間效率和聚類結果有很大提升，但對于每個元素在時間序列數據上的動態變化沒有體現出來，不具有通用性。那么是否可以借鑒前人研究成果，提出一種新的方法適用于挖掘出時間序列中更具體的簇結構的內部變化，這樣的問題值得我們深思，也是作者下一步研究的方向。