宗文澤，吳永明,，徐 計，黎 旭，王 晨

(貴州大學 a.現(xiàn)代制造技術(shù)教育部重點實驗室；b.公共大數(shù)據(jù)國家重點實驗室，貴陽 550025)

0 引言

伴隨著大數(shù)據(jù)時代的到來，醫(yī)學、生物、金融、工程和工業(yè)生產(chǎn)等領域產(chǎn)生了大量的具有明顯的時間順序性的數(shù)據(jù)[1-3]。尤其是生產(chǎn)的信息化和傳感器的普及，使越來越多的數(shù)據(jù)被實時記錄下來，形成了時間序列數(shù)據(jù)。在時間序列數(shù)據(jù)中，異常數(shù)據(jù)往往攜帶著大量有用的信息，所以時間序列數(shù)據(jù)的異常檢測正在在當今社會關(guān)注度越來越高。與此同時，聚類算法作為機器學習算法的一個重要分支[4-6],不需要給數(shù)據(jù)打標簽，不需要標記實例[7]，成為最適合處理時間序列數(shù)據(jù)的方法之一，得到廣泛研究和應用。

聚類算法一般可以用基于劃分、基于密度、基于層次等方式來進行分類[8]。黃曉輝等[9]結(jié)合特征加權(quán)方法,提出了一種新的通過在子空間內(nèi)最大化簇中心與其他簇數(shù)據(jù)對象的距離來融合簇內(nèi)和簇間距離進行聚類的加權(quán)K-means方法(KICIC)來解決高維數(shù)據(jù)聚類問題。秦佳睿等[10]提出一種自適應選擇局部半徑的密度聚類算法(SALE-DBSCAN),通過確定密度峰值點,自適應選擇聚類的局部鄰域半徑,簡化了參數(shù)選擇的過程；通過使用自適應選擇的局部鄰域半徑擴張密度峰值點的鄰域進行聚類,提高了聚類結(jié)果質(zhì)量。季姜帥等[11]構(gòu)建了融合精英保留法與輪盤賭的選擇算子，并通過優(yōu)化適應度函數(shù)和小生境策略保持種群多樣性，加快收斂速度，提升聚類精度。時間序列聚類已經(jīng)在時間序列挖掘領域引起了廣泛地關(guān)注。吳永明等[12]設計了一種基于改進生長神經(jīng)氣模型(GNG)的自適應聚類模型,建立基于概率、范圍搜尋、節(jié)點平均距離的節(jié)點生成、刪除機制,實現(xiàn)對漂移數(shù)據(jù)實時監(jiān)控。EUN等[13]提出基于譜密度[14]以及全變分距離[15]的聚類方法，通過事件的相似振蕩行為構(gòu)建類簇，該方法直接對時間序列數(shù)據(jù)聚類，受事件的復雜結(jié)構(gòu)影響，聚類準確率低。SANDER[16]將層次聚類算法應用于時間序列的聚類上，并通過聚類有效性指標表明得到了較好的聚類效果。對應于曲線的極值的分區(qū)用于最終估計群集的數(shù)目，并提出了新的有效性指數(shù)來量化聚類質(zhì)量，獨立于聚類算法和強調(diào)聚類的幾何特征，有效地處理噪聲數(shù)據(jù)和任意形狀的聚類。

綜上所述，本文對時間序列數(shù)據(jù)聚類進行了深入研究，在現(xiàn)有的聚類算法中，通常直接對時間序列數(shù)據(jù)進行聚類，采用歐式距離進行劃分，沒有時間序列對齊的靈活性，無法對時間序列數(shù)據(jù)很好地聚類。因此本文綜合考慮事件的復雜結(jié)構(gòu)特征，提出一種基于DTW與K-medoids算法相結(jié)合的學習模型，通過引入時間動態(tài)規(guī)整，提高聚類對動態(tài)時間序列對齊的靈活性，使聚類適用于動態(tài)時間序列數(shù)據(jù)，同時構(gòu)建閾值機制實現(xiàn)對工業(yè)數(shù)據(jù)的監(jiān)督和預警。

1 K-medoids算法理論

傳統(tǒng)K-medoids聚類算法使用一個代價函數(shù)來評估聚類質(zhì)量的好壞，以重復迭代的方式尋找到最好的聚簇劃分及聚簇中心點。這里使用基于歐式距離的聚類誤差平方E來評估聚類結(jié)果質(zhì)量，定義如下：

(1)

式中，x為各個簇類Cj中的樣本；Oj為其聚類中心。

K-medoids聚類算法步驟可描述如下：

步驟1：從數(shù)據(jù)集中隨機選擇k個對象，作為初始的聚類中心點；

步驟2：根據(jù)與中心點距離的遠近，將數(shù)據(jù)集中的其他非中心點對象分配到最近中心點所在的簇類；

步驟3：重新計算每個簇的中心點位置，使其到該簇其他樣本的距離總和最??；

步驟4：重復執(zhí)行步驟2和步驟3，直到聚類誤差平方和基本不變，達到指定要求為止。

一般K-means聚類算法是通過計算簇類點的平均值來選取中心點，其對孤立點敏感，選取的中心可能不存在。與K-means聚類算法不同的是，K-medoids聚類算法在迭代選取中心點時，總是在中心點的周圍選擇樣本點作為新的中心點，消除了對孤立點的敏感性。

2 DTW-kmedoids聚類算法及閾值模型

DTW-kmedoids聚類算法是K-medoids算法結(jié)合DTW的改進。該算法利用了DTW距離可以反映樣本相似性的特性，以DTW距離為基礎構(gòu)建了聚類結(jié)果質(zhì)量的代價函數(shù)。

2.1 DTW算法

DTW最早由日本學者Itakura提出，是一種基于動態(tài)規(guī)劃(DP)思想的動態(tài)時間歸整算法。DTW可以實現(xiàn)不等長時間序列的度量,還對時間序列的偏移、振幅變化等情況具有較強的魯棒性[17]。ROHIT等[18]指出，DTW特征與其他機器學習方法的結(jié)合使用，可以提高機器學習方法的性能。

DTW的計算過程如下：測試模板第i幀Ti與參考模板第j幀Rj的失真度為d(i,j)，設D(i,j)為測試模板匹配了i幀、參考模板匹配了j幀失真度。為了求取最終答案DTW(m,n)，可以定義1個矩陣，矩陣的(i,j)位置包含d(i,j)和DTW(i,j)。對于規(guī)整路徑W={w1,w2,w3,...,wk}，有：

(2)

式中，wi的約束條件有：

(1)規(guī)整路徑滿足w1=(1,1)，且wk=(m,n)；

(2)對于任意的1≤i

(3)對于任意的1≤i

(3)

式中，DTW代表前面遍歷過的區(qū)域得到的最短距離；d代表前一個坐標到該坐標的距離。

2.2 DTW-kmedoids算法

本文采用了DTW距離代替歐式距離，形成了一種新的基于DTW的對聚類結(jié)果質(zhì)量的評估的代價函數(shù)，其定義如下：

(4)

式中，x為各個簇類Cj中的樣本；Oj為其聚類中心。

如圖1所示，DTW距離的對齊方式如圖1b所示，相比于歐氏距離如圖1a所示，更能夠體現(xiàn)時間序列數(shù)據(jù)特征點到對應特征點的對應關(guān)系，表現(xiàn)序列數(shù)據(jù)之間的相似性。DTW-kmedoids算法首先將樣本標準化，然后隨機選取k個樣本點作為中心點并計算其他點到中心點的DTW代價函數(shù)值，根據(jù)最小的代價函數(shù)將其余的樣本點歸類到中心點代表的簇，重新計算中心點的位置，對其他樣本點歸類，并計算新的中心點的代價函數(shù)，留下代價值最小的中心點，重復這個過程，直到代價函數(shù)值達到最小。它的具體算法如表1所示。

(a) 歐式距離對齊 (b) DTW距離對齊圖1 歐氏距離和DTW距離的對齊模式

表1 DTW-kmedoids算法

2.3 閾值的確定

閾值通過以下方法設定：將每個簇的中心設為Centeri(i=1,2,3)，簇邊界設置于到中心的平均距離，閾值則確定于兩個簇的邊界之間，對于每一個數(shù)據(jù)維度，有上下兩個閾值：

Hthreshold=

(5)

Lthreshold=

(6)

式中，ni(i=1,2,3)代表每個簇內(nèi)樣本數(shù)據(jù)量；aj代表樣本經(jīng)過預處理后的值。閾值可以用來確定正常數(shù)據(jù)的范圍，剩下的就是異常數(shù)據(jù)。

2.4 評價指標

在聚類算法的評價中，引入了評價指標輪廓系數(shù)。它的計算公式為：

(7)

式中，ai為樣本i到同簇其他樣本的平均距離。所有樣本的輪廓系數(shù)的平均值稱為聚類結(jié)果的平均輪廓系數(shù)，是該聚類是否合理、有效的度量。當平均輪廓系數(shù)接近1時，簇內(nèi)緊湊，并遠離其他簇。

除了聚類評價指標輪廓系數(shù)，本文還引入了機器學習評價指標檢測成功率TPR和誤報率FPR。

(8)

(9)

式中，TP代表真正類，即樣本的真實狀態(tài)是異常狀態(tài)，而且模型預測的結(jié)果也是異常狀態(tài)；FP代表假正類，即樣本的真實狀態(tài)是正常狀態(tài)，而且模型預測的結(jié)果是異常狀態(tài)；TN代表真負類，即樣本的真實狀態(tài)是正常狀態(tài)，而且模型預測結(jié)果也是正常狀態(tài)；FN代表假負類，即樣本的真實狀態(tài)是異常狀態(tài)，而且模型預測的結(jié)果正常狀態(tài)。TPR越高，說明有越多的異常樣本被模型預測正確，模型的效果越好；FPR越低，說明有越少的正常樣本被識別為異常樣本，模型的效果越好。

2.5 模型流程

基于DTW-kmedoids算法，本文構(gòu)建了對時間序列數(shù)據(jù)的異常檢測模型，如圖2所示。首先對數(shù)據(jù)進行預處理，使數(shù)據(jù)歸一化；利用DTW-kmedoids對數(shù)據(jù)進行聚類，得到聚類結(jié)果；對于聚類后的樣本，使用式(5)、式(6)的閾值進行判定，大于Hthreshold或小于Lthreshold的判定為異常值。

圖2 基于DTW-kmedoids的異常檢測模型

3 實例驗證

3.1 實驗數(shù)據(jù)及參數(shù)

實驗對象選擇的是貴陽市某卷煙廠1個月內(nèi)31個批次煙葉加工過程中含水率的時間序列數(shù)據(jù)。煙葉含水率對煙葉后續(xù)加工質(zhì)量有著非常大的影響，煙葉含水率不足，會降低煙葉的耐加工性能，增加后續(xù)加工中的損耗。本文使用的是不同工藝后煙葉的含水率數(shù)據(jù)，因為生產(chǎn)工藝在理論上有先后的順序，因此將生產(chǎn)工藝數(shù)據(jù)看作時間序列數(shù)據(jù)?；贒TW的改進K-medoids算法對具有時間序列的含水率數(shù)據(jù)進行聚類和異常識別，為監(jiān)管者提供了良好的理論支持，數(shù)據(jù)指標和數(shù)據(jù)如表2和表3所示。

表2 時間序列含水率指標

表3 時間序列含水率數(shù)據(jù)

表2反映了本次實驗6個輸入指標，以及聚類評價指標輪廓系數(shù)、異常檢測的檢測成功率和誤報率這兩個指標。

因為時間序列數(shù)據(jù)中有三種含水率狀態(tài):初始狀態(tài)，異常狀態(tài)，平穩(wěn)狀態(tài)，所以本文設k=3。用聚類算法可以得到對應的三類。采用了K-means算法，經(jīng)典K-medoids算法和DTW-kmedoids算法對以上數(shù)據(jù)進行聚類。在聚類結(jié)果中，按比例縮放后，初始狀態(tài)樣本點與其自身質(zhì)心之間的所有距離都小于0.1，但它們與另外兩個狀態(tài)質(zhì)心的距離相對較大，即4.5～9.0。相反，處于平穩(wěn)狀態(tài)中所有樣本與初始狀態(tài)質(zhì)心之間的距離大于7.5，而到它們自己聚類中心的距離都小于0.12，這表明，處于初始狀態(tài)、異常狀態(tài)和平穩(wěn)運行狀態(tài)的樣本明顯分布在三個不同的區(qū)域。三種圖案的樣本可以清晰地相互區(qū)分，為閾值區(qū)分奠定了基礎。

在上述6個指標中選取了3個，首先對數(shù)據(jù)進行了可視化處理，如圖3所示。

圖3 時間序列含水率分布

3.2 實驗結(jié)果

為了驗證基于DTW-kmedoids的煙絲含水率控制模型的有效性和準確性，選取了1043個樣本，其中包括314個初始狀態(tài)樣本，212個異常狀態(tài)樣本，517個平穩(wěn)狀態(tài)樣本。本次實驗選取了指標1、指標2、指標3三個輸入指標，以及聚類評價指標輪廓系數(shù)、異常檢測的檢測成功率和誤報率這兩個指標。首先分別采用了K-means算法，經(jīng)典K-medoids算法和DTW-kmedoids算法進行聚類，根據(jù)聚類效果建立對應的閾值對數(shù)據(jù)進行劃分，如果樣本不屬于初始狀態(tài)，也不屬于平穩(wěn)狀態(tài)，則相應的測試樣本被視需要控制的樣本；否則，它將被視為正常樣本。聚類結(jié)果如圖4所示。

(a) DTW-kmedoids聚類結(jié)果 (b) K-means聚類結(jié)果

(c) 傳統(tǒng)K-medoids聚類結(jié)果圖4 聚類結(jié)果

圖4可以明顯看到煙絲含水率數(shù)據(jù)聚集于初始狀態(tài)和平穩(wěn)狀態(tài)，而中間較為離散的數(shù)據(jù)正處于異常狀態(tài)。根據(jù)圖4aDTW-kmedoids算法的聚類結(jié)果，可以看到這些數(shù)據(jù)清晰地聚為3類。圖4b中K-means算法將一部分平穩(wěn)狀態(tài)樣本識別為異常樣本，這是因為異常狀態(tài)的均值中心偏離，導致相似度較高的樣本被不同的中心點俘獲。圖4c中傳統(tǒng)K-medoids算法區(qū)分出了平穩(wěn)狀態(tài)，但是未能根據(jù)時間相似性區(qū)分初始狀態(tài)和異常狀態(tài)，導致某時間段內(nèi)樣本被分為兩部分。

對聚類樣本求輪廓系數(shù)，結(jié)果如圖5所示。

(a) DTW-kmedoids輪廓系數(shù) (b) K-means輪廓系數(shù)

(c) 傳統(tǒng)K-medoids輪廓系數(shù)圖5 輪廓系數(shù)

圖5a為DTW-kmedoids聚類結(jié)果的輪廓系數(shù)圖，正數(shù)較多，平均值更接近1；圖5b和圖5c分別為K-means和傳統(tǒng)K-medois算法聚類結(jié)果輪廓系數(shù)圖，負數(shù)相對較多，平均值較小?？傻帽疚奶岢龅腄TW-kmedoids算法相對于K-means算法和傳統(tǒng)K-medoids算法比較有較明顯提升。這說明，DTW-kmedoids算法能在增大類間距離的同時，有效地減小類內(nèi)距離。

根據(jù)式(5)、式(6)，得到的閾值模型如圖6所示。

(a) DTW-kmedoids獲得的閾值 (b) K-means獲得的閾值

(c) 傳統(tǒng)K-medoids獲得的閾值圖6 不同聚類算法獲得的閾值

圖6中，對于初始狀態(tài)的3個指標，各有兩個閾值進行識別，6個閾值代表的面圍成了長方體，長方體內(nèi)部的數(shù)據(jù)代表識別為初始狀態(tài)；平穩(wěn)狀態(tài)亦然。得益于DTW-kmedoids算法優(yōu)秀的聚類效果，圖6a中的閾值可以很好地識別出數(shù)據(jù)的初始狀態(tài)和平穩(wěn)狀態(tài)，而剩下的就是異常數(shù)據(jù)。圖6b中代表平穩(wěn)狀態(tài)閾值的長方體較小，導致K-means算法異常識別誤報率較高。圖6c中傳統(tǒng)K-medoids算法未能準確區(qū)分初始狀態(tài)和異常狀態(tài)，導致初始狀態(tài)閾值長方體偏離初始狀態(tài)數(shù)據(jù)簇類，進而使識別準確率不足。

除了上述實驗，本文還使用了全部指標進行了實驗Ⅱ，表4～表6是實驗Ⅱ的聚類結(jié)果，A為平穩(wěn)狀態(tài)，B為異常狀態(tài)，C為初始狀態(tài)。

表4 DTW-kmedoids聚類結(jié)果

表5 K-means聚類結(jié)果

表6 傳統(tǒng)K-medoids聚類結(jié)果

對實驗Ⅱ聚類樣本求輪廓系數(shù)，結(jié)果如圖7所示。

(a) 六維數(shù)據(jù)DTW-kmedoids輪廓系數(shù) (b) 六維數(shù)據(jù)K-means輪廓系數(shù)

(c) 六維數(shù)據(jù)K-medoids輪廓系數(shù)圖7 實驗Ⅱ得到的輪廓系數(shù)

圖7a為DTW-kmedoids聚類結(jié)果的輪廓系數(shù)圖，圖7b和圖7c分別為K-means和傳統(tǒng)K-medoids算法聚類結(jié)果輪廓系數(shù)圖。依然可以看出本文提出的DTW-kmedoids算法相對于K-means算法和傳統(tǒng)K-medoids算法比較有較明顯提升。再次說明，DTW-kmedoids算法能在增大類間距離的同時，有效地減小類內(nèi)距離。上述兩個實驗均能表明，基于DTW-kmedoids算法可以對時間序列數(shù)據(jù)有效地進行聚類。表7是實驗Ⅱ得到的閾值。

表7 不同算法得到的閾值

結(jié)合這兩個實驗，得到了異常識別準確率的對比，結(jié)果如表8所示。

表8 異常識別準確率對比

根據(jù)表8，基于DTW-kmedoids算法的模型識別率可以達到最高，誤報率最低。3種方法表明，基于DTW-kmedoids算法得到的閾值效果最優(yōu)，對異常值的判斷最為準確，進而說明了該方法能夠在克服煙絲加工工藝對濕度影響的前提下提取和區(qū)分煙絲特征。因此，基于DTW-kmedoids算法的模型足以識別異常樣本。在異常樣本出現(xiàn)時，可以及時調(diào)整生產(chǎn)工藝，減少異常，降低煙葉含水率不足對后續(xù)加工的影響。

4 結(jié)論

本文針對現(xiàn)有基于聚類算法的時序數(shù)據(jù)異常檢測進行了分析和研究，提出了一種基于改進K-medoids算法(DTW-kmedoids)的時間序列數(shù)據(jù)異常檢測模型。以卷煙廠的時序數(shù)據(jù)為實驗對象，通過對具有時間序列特性的煙絲含水率數(shù)據(jù)進行聚類分析，并以K-means算法、傳統(tǒng)K-medoids算法為參照進行了實驗對比。結(jié)果表明，本文提出的基于DTW-kmedoids的模型在跟蹤與監(jiān)督煙絲含水率異常檢測方面更具有優(yōu)勢，能有效完成工業(yè)生產(chǎn)中對時間序列數(shù)據(jù)的監(jiān)督，并能夠提高時間序列異常數(shù)據(jù)檢測的有效性和精確性，進而為工廠管理者提供理論技術(shù)支持。