宗文澤,吳永明,,徐 計(jì),黎 旭,王 晨
(貴州大學(xué) a.現(xiàn)代制造技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室;b.公共大數(shù)據(jù)國(guó)家重點(diǎn)實(shí)驗(yàn)室,貴陽(yáng) 550025)
伴隨著大數(shù)據(jù)時(shí)代的到來(lái),醫(yī)學(xué)、生物、金融、工程和工業(yè)生產(chǎn)等領(lǐng)域產(chǎn)生了大量的具有明顯的時(shí)間順序性的數(shù)據(jù)[1-3]。尤其是生產(chǎn)的信息化和傳感器的普及,使越來(lái)越多的數(shù)據(jù)被實(shí)時(shí)記錄下來(lái),形成了時(shí)間序列數(shù)據(jù)。在時(shí)間序列數(shù)據(jù)中,異常數(shù)據(jù)往往攜帶著大量有用的信息,所以時(shí)間序列數(shù)據(jù)的異常檢測(cè)正在在當(dāng)今社會(huì)關(guān)注度越來(lái)越高。與此同時(shí),聚類算法作為機(jī)器學(xué)習(xí)算法的一個(gè)重要分支[4-6],不需要給數(shù)據(jù)打標(biāo)簽,不需要標(biāo)記實(shí)例[7],成為最適合處理時(shí)間序列數(shù)據(jù)的方法之一,得到廣泛研究和應(yīng)用。
聚類算法一般可以用基于劃分、基于密度、基于層次等方式來(lái)進(jìn)行分類[8]。黃曉輝等[9]結(jié)合特征加權(quán)方法,提出了一種新的通過(guò)在子空間內(nèi)最大化簇中心與其他簇?cái)?shù)據(jù)對(duì)象的距離來(lái)融合簇內(nèi)和簇間距離進(jìn)行聚類的加權(quán)K-means方法(KICIC)來(lái)解決高維數(shù)據(jù)聚類問(wèn)題。秦佳睿等[10]提出一種自適應(yīng)選擇局部半徑的密度聚類算法(SALE-DBSCAN),通過(guò)確定密度峰值點(diǎn),自適應(yīng)選擇聚類的局部鄰域半徑,簡(jiǎn)化了參數(shù)選擇的過(guò)程;通過(guò)使用自適應(yīng)選擇的局部鄰域半徑擴(kuò)張密度峰值點(diǎn)的鄰域進(jìn)行聚類,提高了聚類結(jié)果質(zhì)量。季姜帥等[11]構(gòu)建了融合精英保留法與輪盤賭的選擇算子,并通過(guò)優(yōu)化適應(yīng)度函數(shù)和小生境策略保持種群多樣性,加快收斂速度,提升聚類精度。時(shí)間序列聚類已經(jīng)在時(shí)間序列挖掘領(lǐng)域引起了廣泛地關(guān)注。吳永明等[12]設(shè)計(jì)了一種基于改進(jìn)生長(zhǎng)神經(jīng)氣模型(GNG)的自適應(yīng)聚類模型,建立基于概率、范圍搜尋、節(jié)點(diǎn)平均距離的節(jié)點(diǎn)生成、刪除機(jī)制,實(shí)現(xiàn)對(duì)漂移數(shù)據(jù)實(shí)時(shí)監(jiān)控。EUN等[13]提出基于譜密度[14]以及全變分距離[15]的聚類方法,通過(guò)事件的相似振蕩行為構(gòu)建類簇,該方法直接對(duì)時(shí)間序列數(shù)據(jù)聚類,受事件的復(fù)雜結(jié)構(gòu)影響,聚類準(zhǔn)確率低。SANDER[16]將層次聚類算法應(yīng)用于時(shí)間序列的聚類上,并通過(guò)聚類有效性指標(biāo)表明得到了較好的聚類效果。對(duì)應(yīng)于曲線的極值的分區(qū)用于最終估計(jì)群集的數(shù)目,并提出了新的有效性指數(shù)來(lái)量化聚類質(zhì)量,獨(dú)立于聚類算法和強(qiáng)調(diào)聚類的幾何特征,有效地處理噪聲數(shù)據(jù)和任意形狀的聚類。
綜上所述,本文對(duì)時(shí)間序列數(shù)據(jù)聚類進(jìn)行了深入研究,在現(xiàn)有的聚類算法中,通常直接對(duì)時(shí)間序列數(shù)據(jù)進(jìn)行聚類,采用歐式距離進(jìn)行劃分,沒(méi)有時(shí)間序列對(duì)齊的靈活性,無(wú)法對(duì)時(shí)間序列數(shù)據(jù)很好地聚類。因此本文綜合考慮事件的復(fù)雜結(jié)構(gòu)特征,提出一種基于DTW與K-medoids算法相結(jié)合的學(xué)習(xí)模型,通過(guò)引入時(shí)間動(dòng)態(tài)規(guī)整,提高聚類對(duì)動(dòng)態(tài)時(shí)間序列對(duì)齊的靈活性,使聚類適用于動(dòng)態(tài)時(shí)間序列數(shù)據(jù),同時(shí)構(gòu)建閾值機(jī)制實(shí)現(xiàn)對(duì)工業(yè)數(shù)據(jù)的監(jiān)督和預(yù)警。
傳統(tǒng)K-medoids聚類算法使用一個(gè)代價(jià)函數(shù)來(lái)評(píng)估聚類質(zhì)量的好壞,以重復(fù)迭代的方式尋找到最好的聚簇劃分及聚簇中心點(diǎn)。這里使用基于歐式距離的聚類誤差平方E來(lái)評(píng)估聚類結(jié)果質(zhì)量,定義如下:
(1)
式中,x為各個(gè)簇類Cj中的樣本;Oj為其聚類中心。
K-medoids聚類算法步驟可描述如下:
步驟1:從數(shù)據(jù)集中隨機(jī)選擇k個(gè)對(duì)象,作為初始的聚類中心點(diǎn);
步驟2:根據(jù)與中心點(diǎn)距離的遠(yuǎn)近,將數(shù)據(jù)集中的其他非中心點(diǎn)對(duì)象分配到最近中心點(diǎn)所在的簇類;
步驟3:重新計(jì)算每個(gè)簇的中心點(diǎn)位置,使其到該簇其他樣本的距離總和最??;
步驟4:重復(fù)執(zhí)行步驟2和步驟3,直到聚類誤差平方和基本不變,達(dá)到指定要求為止。
一般K-means聚類算法是通過(guò)計(jì)算簇類點(diǎn)的平均值來(lái)選取中心點(diǎn),其對(duì)孤立點(diǎn)敏感,選取的中心可能不存在。與K-means聚類算法不同的是,K-medoids聚類算法在迭代選取中心點(diǎn)時(shí),總是在中心點(diǎn)的周圍選擇樣本點(diǎn)作為新的中心點(diǎn),消除了對(duì)孤立點(diǎn)的敏感性。
DTW-kmedoids聚類算法是K-medoids算法結(jié)合DTW的改進(jìn)。該算法利用了DTW距離可以反映樣本相似性的特性,以DTW距離為基礎(chǔ)構(gòu)建了聚類結(jié)果質(zhì)量的代價(jià)函數(shù)。
DTW最早由日本學(xué)者Itakura提出,是一種基于動(dòng)態(tài)規(guī)劃(DP)思想的動(dòng)態(tài)時(shí)間歸整算法。DTW可以實(shí)現(xiàn)不等長(zhǎng)時(shí)間序列的度量,還對(duì)時(shí)間序列的偏移、振幅變化等情況具有較強(qiáng)的魯棒性[17]。ROHIT等[18]指出,DTW特征與其他機(jī)器學(xué)習(xí)方法的結(jié)合使用,可以提高機(jī)器學(xué)習(xí)方法的性能。
DTW的計(jì)算過(guò)程如下:測(cè)試模板第i幀Ti與參考模板第j幀Rj的失真度為d(i,j),設(shè)D(i,j)為測(cè)試模板匹配了i幀、參考模板匹配了j幀失真度。為了求取最終答案DTW(m,n),可以定義1個(gè)矩陣,矩陣的(i,j)位置包含d(i,j)和DTW(i,j)。對(duì)于規(guī)整路徑W={w1,w2,w3,...,wk},有:
(2)
式中,wi的約束條件有:
(1)規(guī)整路徑滿足w1=(1,1),且wk=(m,n);
(2)對(duì)于任意的1≤i (3)對(duì)于任意的1≤i (3) 式中,DTW代表前面遍歷過(guò)的區(qū)域得到的最短距離;d代表前一個(gè)坐標(biāo)到該坐標(biāo)的距離。 本文采用了DTW距離代替歐式距離,形成了一種新的基于DTW的對(duì)聚類結(jié)果質(zhì)量的評(píng)估的代價(jià)函數(shù),其定義如下: (4) 式中,x為各個(gè)簇類Cj中的樣本;Oj為其聚類中心。 如圖1所示,DTW距離的對(duì)齊方式如圖1b所示,相比于歐氏距離如圖1a所示,更能夠體現(xiàn)時(shí)間序列數(shù)據(jù)特征點(diǎn)到對(duì)應(yīng)特征點(diǎn)的對(duì)應(yīng)關(guān)系,表現(xiàn)序列數(shù)據(jù)之間的相似性。DTW-kmedoids算法首先將樣本標(biāo)準(zhǔn)化,然后隨機(jī)選取k個(gè)樣本點(diǎn)作為中心點(diǎn)并計(jì)算其他點(diǎn)到中心點(diǎn)的DTW代價(jià)函數(shù)值,根據(jù)最小的代價(jià)函數(shù)將其余的樣本點(diǎn)歸類到中心點(diǎn)代表的簇,重新計(jì)算中心點(diǎn)的位置,對(duì)其他樣本點(diǎn)歸類,并計(jì)算新的中心點(diǎn)的代價(jià)函數(shù),留下代價(jià)值最小的中心點(diǎn),重復(fù)這個(gè)過(guò)程,直到代價(jià)函數(shù)值達(dá)到最小。它的具體算法如表1所示。 (a) 歐式距離對(duì)齊 (b) DTW距離對(duì)齊圖1 歐氏距離和DTW距離的對(duì)齊模式 表1 DTW-kmedoids算法 閾值通過(guò)以下方法設(shè)定:將每個(gè)簇的中心設(shè)為Centeri(i=1,2,3),簇邊界設(shè)置于到中心的平均距離,閾值則確定于兩個(gè)簇的邊界之間,對(duì)于每一個(gè)數(shù)據(jù)維度,有上下兩個(gè)閾值: Hthreshold= (5) Lthreshold= (6) 式中,ni(i=1,2,3)代表每個(gè)簇內(nèi)樣本數(shù)據(jù)量;aj代表樣本經(jīng)過(guò)預(yù)處理后的值。閾值可以用來(lái)確定正常數(shù)據(jù)的范圍,剩下的就是異常數(shù)據(jù)。 在聚類算法的評(píng)價(jià)中,引入了評(píng)價(jià)指標(biāo)輪廓系數(shù)。它的計(jì)算公式為: (7) 式中,ai為樣本i到同簇其他樣本的平均距離。所有樣本的輪廓系數(shù)的平均值稱為聚類結(jié)果的平均輪廓系數(shù),是該聚類是否合理、有效的度量。當(dāng)平均輪廓系數(shù)接近1時(shí),簇內(nèi)緊湊,并遠(yuǎn)離其他簇。 除了聚類評(píng)價(jià)指標(biāo)輪廓系數(shù),本文還引入了機(jī)器學(xué)習(xí)評(píng)價(jià)指標(biāo)檢測(cè)成功率TPR和誤報(bào)率FPR。 (8) (9) 式中,TP代表真正類,即樣本的真實(shí)狀態(tài)是異常狀態(tài),而且模型預(yù)測(cè)的結(jié)果也是異常狀態(tài);FP代表假正類,即樣本的真實(shí)狀態(tài)是正常狀態(tài),而且模型預(yù)測(cè)的結(jié)果是異常狀態(tài);TN代表真負(fù)類,即樣本的真實(shí)狀態(tài)是正常狀態(tài),而且模型預(yù)測(cè)結(jié)果也是正常狀態(tài);FN代表假負(fù)類,即樣本的真實(shí)狀態(tài)是異常狀態(tài),而且模型預(yù)測(cè)的結(jié)果正常狀態(tài)。TPR越高,說(shuō)明有越多的異常樣本被模型預(yù)測(cè)正確,模型的效果越好;FPR越低,說(shuō)明有越少的正常樣本被識(shí)別為異常樣本,模型的效果越好。 基于DTW-kmedoids算法,本文構(gòu)建了對(duì)時(shí)間序列數(shù)據(jù)的異常檢測(cè)模型,如圖2所示。首先對(duì)數(shù)據(jù)進(jìn)行預(yù)處理,使數(shù)據(jù)歸一化;利用DTW-kmedoids對(duì)數(shù)據(jù)進(jìn)行聚類,得到聚類結(jié)果;對(duì)于聚類后的樣本,使用式(5)、式(6)的閾值進(jìn)行判定,大于Hthreshold或小于Lthreshold的判定為異常值。 圖2 基于DTW-kmedoids的異常檢測(cè)模型 實(shí)驗(yàn)對(duì)象選擇的是貴陽(yáng)市某卷煙廠1個(gè)月內(nèi)31個(gè)批次煙葉加工過(guò)程中含水率的時(shí)間序列數(shù)據(jù)。煙葉含水率對(duì)煙葉后續(xù)加工質(zhì)量有著非常大的影響,煙葉含水率不足,會(huì)降低煙葉的耐加工性能,增加后續(xù)加工中的損耗。本文使用的是不同工藝后煙葉的含水率數(shù)據(jù),因?yàn)樯a(chǎn)工藝在理論上有先后的順序,因此將生產(chǎn)工藝數(shù)據(jù)看作時(shí)間序列數(shù)據(jù)。基于DTW的改進(jìn)K-medoids算法對(duì)具有時(shí)間序列的含水率數(shù)據(jù)進(jìn)行聚類和異常識(shí)別,為監(jiān)管者提供了良好的理論支持,數(shù)據(jù)指標(biāo)和數(shù)據(jù)如表2和表3所示。 表2 時(shí)間序列含水率指標(biāo) 表3 時(shí)間序列含水率數(shù)據(jù) 表2反映了本次實(shí)驗(yàn)6個(gè)輸入指標(biāo),以及聚類評(píng)價(jià)指標(biāo)輪廓系數(shù)、異常檢測(cè)的檢測(cè)成功率和誤報(bào)率這兩個(gè)指標(biāo)。 因?yàn)闀r(shí)間序列數(shù)據(jù)中有三種含水率狀態(tài):初始狀態(tài),異常狀態(tài),平穩(wěn)狀態(tài),所以本文設(shè)k=3。用聚類算法可以得到對(duì)應(yīng)的三類。采用了K-means算法,經(jīng)典K-medoids算法和DTW-kmedoids算法對(duì)以上數(shù)據(jù)進(jìn)行聚類。在聚類結(jié)果中,按比例縮放后,初始狀態(tài)樣本點(diǎn)與其自身質(zhì)心之間的所有距離都小于0.1,但它們與另外兩個(gè)狀態(tài)質(zhì)心的距離相對(duì)較大,即4.5~9.0。相反,處于平穩(wěn)狀態(tài)中所有樣本與初始狀態(tài)質(zhì)心之間的距離大于7.5,而到它們自己聚類中心的距離都小于0.12,這表明,處于初始狀態(tài)、異常狀態(tài)和平穩(wěn)運(yùn)行狀態(tài)的樣本明顯分布在三個(gè)不同的區(qū)域。三種圖案的樣本可以清晰地相互區(qū)分,為閾值區(qū)分奠定了基礎(chǔ)。 在上述6個(gè)指標(biāo)中選取了3個(gè),首先對(duì)數(shù)據(jù)進(jìn)行了可視化處理,如圖3所示。 圖3 時(shí)間序列含水率分布 為了驗(yàn)證基于DTW-kmedoids的煙絲含水率控制模型的有效性和準(zhǔn)確性,選取了1043個(gè)樣本,其中包括314個(gè)初始狀態(tài)樣本,212個(gè)異常狀態(tài)樣本,517個(gè)平穩(wěn)狀態(tài)樣本。本次實(shí)驗(yàn)選取了指標(biāo)1、指標(biāo)2、指標(biāo)3三個(gè)輸入指標(biāo),以及聚類評(píng)價(jià)指標(biāo)輪廓系數(shù)、異常檢測(cè)的檢測(cè)成功率和誤報(bào)率這兩個(gè)指標(biāo)。首先分別采用了K-means算法,經(jīng)典K-medoids算法和DTW-kmedoids算法進(jìn)行聚類,根據(jù)聚類效果建立對(duì)應(yīng)的閾值對(duì)數(shù)據(jù)進(jìn)行劃分,如果樣本不屬于初始狀態(tài),也不屬于平穩(wěn)狀態(tài),則相應(yīng)的測(cè)試樣本被視需要控制的樣本;否則,它將被視為正常樣本。聚類結(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)樣本識(shí)別為異常樣本,這是因?yàn)楫惓顟B(tài)的均值中心偏離,導(dǎo)致相似度較高的樣本被不同的中心點(diǎn)俘獲。圖4c中傳統(tǒng)K-medoids算法區(qū)分出了平穩(wěn)狀態(tài),但是未能根據(jù)時(shí)間相似性區(qū)分初始狀態(tài)和異常狀態(tài),導(dǎo)致某時(shí)間段內(nèi)樣本被分為兩部分。 對(duì)聚類樣本求輪廓系數(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ù)圖,負(fù)數(shù)相對(duì)較多,平均值較小??傻帽疚奶岢龅腄TW-kmedoids算法相對(duì)于K-means算法和傳統(tǒng)K-medoids算法比較有較明顯提升。這說(shuō)明,DTW-kmedoids算法能在增大類間距離的同時(shí),有效地減小類內(nèi)距離。 根據(jù)式(5)、式(6),得到的閾值模型如圖6所示。 (a) DTW-kmedoids獲得的閾值 (b) K-means獲得的閾值 (c) 傳統(tǒng)K-medoids獲得的閾值圖6 不同聚類算法獲得的閾值 圖6中,對(duì)于初始狀態(tài)的3個(gè)指標(biāo),各有兩個(gè)閾值進(jìn)行識(shí)別,6個(gè)閾值代表的面圍成了長(zhǎng)方體,長(zhǎng)方體內(nèi)部的數(shù)據(jù)代表識(shí)別為初始狀態(tài);平穩(wěn)狀態(tài)亦然。得益于DTW-kmedoids算法優(yōu)秀的聚類效果,圖6a中的閾值可以很好地識(shí)別出數(shù)據(jù)的初始狀態(tài)和平穩(wěn)狀態(tài),而剩下的就是異常數(shù)據(jù)。圖6b中代表平穩(wěn)狀態(tài)閾值的長(zhǎng)方體較小,導(dǎo)致K-means算法異常識(shí)別誤報(bào)率較高。圖6c中傳統(tǒng)K-medoids算法未能準(zhǔn)確區(qū)分初始狀態(tài)和異常狀態(tài),導(dǎo)致初始狀態(tài)閾值長(zhǎng)方體偏離初始狀態(tài)數(shù)據(jù)簇類,進(jìn)而使識(shí)別準(zhǔn)確率不足。 除了上述實(shí)驗(yàn),本文還使用了全部指標(biāo)進(jìn)行了實(shí)驗(yàn)Ⅱ,表4~表6是實(shí)驗(yàn)Ⅱ的聚類結(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é)果 對(duì)實(shí)驗(yàn)Ⅱ聚類樣本求輪廓系數(shù),結(jié)果如圖7所示。 (a) 六維數(shù)據(jù)DTW-kmedoids輪廓系數(shù) (b) 六維數(shù)據(jù)K-means輪廓系數(shù) (c) 六維數(shù)據(jù)K-medoids輪廓系數(shù)圖7 實(shí)驗(yàn)Ⅱ得到的輪廓系數(shù) 圖7a為DTW-kmedoids聚類結(jié)果的輪廓系數(shù)圖,圖7b和圖7c分別為K-means和傳統(tǒng)K-medoids算法聚類結(jié)果輪廓系數(shù)圖。依然可以看出本文提出的DTW-kmedoids算法相對(duì)于K-means算法和傳統(tǒng)K-medoids算法比較有較明顯提升。再次說(shuō)明,DTW-kmedoids算法能在增大類間距離的同時(shí),有效地減小類內(nèi)距離。上述兩個(gè)實(shí)驗(yàn)均能表明,基于DTW-kmedoids算法可以對(duì)時(shí)間序列數(shù)據(jù)有效地進(jìn)行聚類。表7是實(shí)驗(yàn)Ⅱ得到的閾值。 表7 不同算法得到的閾值 結(jié)合這兩個(gè)實(shí)驗(yàn),得到了異常識(shí)別準(zhǔn)確率的對(duì)比,結(jié)果如表8所示。 表8 異常識(shí)別準(zhǔn)確率對(duì)比 根據(jù)表8,基于DTW-kmedoids算法的模型識(shí)別率可以達(dá)到最高,誤報(bào)率最低。3種方法表明,基于DTW-kmedoids算法得到的閾值效果最優(yōu),對(duì)異常值的判斷最為準(zhǔn)確,進(jìn)而說(shuō)明了該方法能夠在克服煙絲加工工藝對(duì)濕度影響的前提下提取和區(qū)分煙絲特征。因此,基于DTW-kmedoids算法的模型足以識(shí)別異常樣本。在異常樣本出現(xiàn)時(shí),可以及時(shí)調(diào)整生產(chǎn)工藝,減少異常,降低煙葉含水率不足對(duì)后續(xù)加工的影響。 本文針對(duì)現(xiàn)有基于聚類算法的時(shí)序數(shù)據(jù)異常檢測(cè)進(jìn)行了分析和研究,提出了一種基于改進(jìn)K-medoids算法(DTW-kmedoids)的時(shí)間序列數(shù)據(jù)異常檢測(cè)模型。以卷煙廠的時(shí)序數(shù)據(jù)為實(shí)驗(yàn)對(duì)象,通過(guò)對(duì)具有時(shí)間序列特性的煙絲含水率數(shù)據(jù)進(jìn)行聚類分析,并以K-means算法、傳統(tǒng)K-medoids算法為參照進(jìn)行了實(shí)驗(yàn)對(duì)比。結(jié)果表明,本文提出的基于DTW-kmedoids的模型在跟蹤與監(jiān)督煙絲含水率異常檢測(cè)方面更具有優(yōu)勢(shì),能有效完成工業(yè)生產(chǎn)中對(duì)時(shí)間序列數(shù)據(jù)的監(jiān)督,并能夠提高時(shí)間序列異常數(shù)據(jù)檢測(cè)的有效性和精確性,進(jìn)而為工廠管理者提供理論技術(shù)支持。2.2 DTW-kmedoids算法
2.3 閾值的確定
2.4 評(píng)價(jià)指標(biāo)
2.5 模型流程
3 實(shí)例驗(yàn)證
3.1 實(shí)驗(yàn)數(shù)據(jù)及參數(shù)
3.2 實(shí)驗(yàn)結(jié)果
4 結(jié)論