一種時(shí)間序列數(shù)據(jù)的動(dòng)態(tài)k-means 聚類算法?

冀敏杰 肖利雪

（西安郵電大學(xué)計(jì)算機(jī)學(xué)院 西安 710121）

1 引言

時(shí)間序列是指數(shù)據(jù)集隨著時(shí)間變化而變化的數(shù)據(jù)集，在時(shí)間軸上形成連續(xù)的序列，它表明了數(shù)據(jù)內(nèi)部狀態(tài)隨時(shí)間變化的規(guī)律。如今，時(shí)間序列［1～2］越來越廣泛應(yīng)用與氣象［3］、醫(yī)療［4］、金融［5］和網(wǎng)絡(luò)安全［6］等各個(gè)重要領(lǐng)域。聚類對(duì)于時(shí)間序列的分析作為主要研究方法，在現(xiàn)如今的學(xué)術(shù)領(lǐng)域中備受關(guān)注［7～9］。在數(shù)據(jù)挖掘領(lǐng)域中，聚類分析既可以作為數(shù)據(jù)挖掘過程中的一個(gè)環(huán)節(jié)，又可以作為獲取數(shù)據(jù)分布情況的工具。

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

針對(duì)以上問題，本文提出DKCA/TSD 算法。該算法通過時(shí)間序列數(shù)據(jù)之間的關(guān)聯(lián)性，把前一時(shí)刻最佳質(zhì)心應(yīng)用于后一時(shí)刻變化的數(shù)據(jù)集中，讓相鄰的時(shí)間序列關(guān)聯(lián)起來進(jìn)行聚類。有效地解決了初始時(shí)刻類中心選取困難以及利用時(shí)間序列之間的關(guān)聯(lián)性進(jìn)行動(dòng)態(tài)聚類。不僅在每個(gè)時(shí)間片上聚類結(jié)果更加準(zhǔn)確，而且每個(gè)時(shí)間片上聚類的時(shí)間效率更好。

2 k-means算法介紹

2.1 相關(guān)定義

其中nj是類Cj中數(shù)據(jù)對(duì)象個(gè)數(shù)。

2.2 k-means算法

k-means 算法是一種基于樣本間相似性度量的間接聚類方法，也被稱為K均值算法。算法的主要思想是通過迭代的過程把數(shù)據(jù)集劃分為不同的類別，使得評(píng)價(jià)聚類性能的準(zhǔn)則函數(shù)達(dá)到最優(yōu)。算法描述如下：

輸入：簇的個(gè)數(shù)K與數(shù)據(jù)集合ξ。

輸出：K個(gè)簇，每個(gè)數(shù)據(jù)所屬類別標(biāo)簽。

1）隨機(jī)選取k個(gè)點(diǎn)作為初始聚類別的中心。

2）將數(shù)據(jù)集中的數(shù)據(jù)分配到距離最近中心點(diǎn)的類中。

3）使用每個(gè)簇中的樣本數(shù)據(jù)均值作為新的聚類中心。

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

5）結(jié)束，得到K個(gè)結(jié)果簇。

3 時(shí)間序列數(shù)據(jù)及聚類過程分析

3.1 時(shí)間序列數(shù)據(jù)關(guān)聯(lián)性分析

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

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

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

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

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

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

元素的變化導(dǎo)致集合結(jié)構(gòu)發(fā)生變化，而相應(yīng)概率則決定了集合變化趨勢(shì)。假設(shè)ti+1時(shí)刻相對(duì)ti時(shí)刻有w1個(gè)元素不變的概率為p1，w2個(gè)元素消失的概率為p2，w3個(gè)元素新增的概率為p3，w4個(gè)元素位移的概率為p4，那么這種情況下從ti時(shí)刻變化到ti+1時(shí)刻的概率為

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

由于ti+1時(shí)刻元素?cái)?shù)量變?yōu)閚i+1，而ni+1=w1+w2+w3+w4，則式（2）可寫為

顯然，ti+1時(shí)刻的狀態(tài)和w1的大小有直接關(guān)系。對(duì)式（3）求關(guān)于w1偏導(dǎo)數(shù)有：

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

結(jié)論1：當(dāng)p＜0.5 時(shí)且w1越大時(shí)，ti+1時(shí)刻的集合類結(jié)構(gòu)很大程度不會(huì)被破壞。也就是說，p＜0.5 時(shí)且w1越大時(shí)，ti+1時(shí)刻類別數(shù)目發(fā)生改變的概率很小。

3.2 k-means聚類算法在動(dòng)態(tài)聚類過程的案例分析

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

對(duì)于時(shí)間序列上動(dòng)態(tài)聚類，采用k-means 算法對(duì)元素消失的情況進(jìn)行分析，給出ti時(shí)刻和ti+1時(shí)刻采用k-means 聚類的結(jié)果分別如圖2（a）和（b）所示。

圖2 中不同形狀表示不同的類，×表示類的質(zhì)心。由圖2 中（a）可知，當(dāng)元素F 消失后，采用傳統(tǒng)的k-means 算法對(duì)變化后的數(shù)據(jù)進(jìn)行聚類時(shí)，需要調(diào)用k-means 算法重新對(duì)變化后的數(shù)據(jù)進(jìn)行聚類，即重新選取初始質(zhì)心，重新進(jìn)行一次k-means 全局聚類。此方法對(duì)于每一個(gè)時(shí)間片相當(dāng)重新調(diào)用了一次k-means 算法，沒有達(dá)到時(shí)間序列數(shù)據(jù)動(dòng)態(tài)聚類的效果。

圖1 ti時(shí)刻和ti+1時(shí)刻數(shù)據(jù)集

針對(duì)以上問題，本文提出DKCA/TSD 算法，ti+1時(shí)刻的聚類在ti時(shí)刻聚類的基礎(chǔ)上，繼承ti時(shí)刻最優(yōu)的質(zhì)心點(diǎn)進(jìn)行聚類，而不用重新聚類中的隨機(jī)選取質(zhì)心。由于結(jié)論1 可知，變化元素更大概率不會(huì)影響原有類結(jié)構(gòu)的破壞，即原有的質(zhì)心更趨向最優(yōu)質(zhì)心，在進(jìn)行動(dòng)態(tài)聚類的時(shí)候更能保證全局最優(yōu)解以及減少數(shù)據(jù)的迭代次數(shù)，從而減少時(shí)間開銷。

4 DKCA/TSD算法

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

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

圖3 ti+1時(shí)刻采用DKCA/TSD算法結(jié)果

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

基本思想：在ti時(shí)刻采用k-means 聚類形成最初的聚類，以后的每個(gè)時(shí)刻基于前一時(shí)刻聚類的結(jié)果進(jìn)行時(shí)間序列的動(dòng)態(tài)聚類。因?yàn)橄噜彆r(shí)刻的數(shù)據(jù)集具有關(guān)聯(lián)性，并且前一時(shí)刻聚類結(jié)果的質(zhì)心是最佳質(zhì)心，變化數(shù)據(jù)較少的情況下質(zhì)心移動(dòng)較小，這樣在ti+1時(shí)刻的聚類就會(huì)減少迭代次數(shù)，從而達(dá)到更快的達(dá)到全局最優(yōu)解，節(jié)省了大量的時(shí)間。

DKCA/TSD算法步驟：

輸入：ti時(shí)刻聚類結(jié)果的質(zhì)心，ti+1時(shí)刻數(shù)據(jù)集

輸出：ti+1時(shí)刻數(shù)據(jù)聚類結(jié)果以及聚類結(jié)果質(zhì)心

1）記錄ti時(shí)刻聚類的質(zhì)心位置。

2）用ti時(shí)刻聚類的質(zhì)心作為ti+1時(shí)刻類別中心。

3）將數(shù)據(jù)集中的數(shù)據(jù)分配到距離最近中心點(diǎn)的類中。

4）使用每個(gè)簇中的樣本數(shù)據(jù)均值作為新的聚類中心。

5）重復(fù)步驟3）、4）直到質(zhì)心不在變化。

5 實(shí)驗(yàn)

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

表1 真實(shí)數(shù)據(jù)集信息

5.1 評(píng)價(jià)指標(biāo)

本節(jié)采用準(zhǔn)確率（ACC）、簇內(nèi)誤差平方和（SSE）、迭代次數(shù)（N）、運(yùn)行時(shí)間T（單位ms），四個(gè)評(píng)價(jià)指標(biāo)對(duì)所提算法進(jìn)行了有效性評(píng)價(jià)。ACC 表示聚類正確的比例，SSE 表示每個(gè)數(shù)據(jù)到質(zhì)心點(diǎn)的距離和，N 表示聚類算法達(dá)到最優(yōu)時(shí)迭代的次數(shù)，T表示算法完成聚類所需時(shí)間。ACC的值越大，聚類結(jié)果越接近于數(shù)據(jù)集的真實(shí)類劃分，聚類效果越好。SSE 的值越小，表示簇結(jié)構(gòu)越緊湊，聚類效果越好。N 和T 的值越小，表示算法迭代次數(shù)小，運(yùn)行時(shí)間快，聚類的效率越好。

5.2 算法性能比較

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

表2 k-means和DKCA/TSD算法在數(shù)據(jù)集Iris，Seeds和Wine測(cè)試結(jié)果

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

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

為進(jìn)一步DKCA/TSD 算法相對(duì)DBSCAN 算法的時(shí)間效率有所提升，實(shí)驗(yàn)采用SEQUO IA 2000 數(shù)據(jù)庫(kù)，處理過程為每次在數(shù)據(jù)集范圍內(nèi)隨機(jī)替換數(shù)據(jù)集種的5 個(gè)數(shù)據(jù)，一共進(jìn)行3 次這樣的操作形成時(shí)間片上連續(xù)的3 個(gè)數(shù)據(jù)集。數(shù)據(jù)集采用的數(shù)據(jù)個(gè) 數(shù) 分 別 是1000，2000，4000，8000，10000，15000。實(shí)驗(yàn)采用指標(biāo)T 來統(tǒng)計(jì)DBSCAN 和DKCA/TSD 算法的時(shí)間效率，T 是SEQUO IA 2000 數(shù)據(jù)集在3個(gè)時(shí)間片上的平均值。圖4是實(shí)驗(yàn)結(jié)果。

圖4 橫坐標(biāo)作為數(shù)據(jù)庫(kù)中數(shù)據(jù)總數(shù)，縱坐標(biāo)為算法執(zhí)行時(shí)間，單位ms。由圖4 可知，采用時(shí)間序列上的動(dòng)態(tài)k-means 聚類算法的時(shí)間效率明顯優(yōu)于傳統(tǒng)k-means 算法，尤其在數(shù)據(jù)集大于4000 時(shí)，時(shí)間效率差異更加明顯。

圖4 SEQUO IA 2000數(shù)據(jù)測(cè)試的時(shí)間結(jié)果

6 結(jié)語(yǔ)

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