基于改進(jìn)的K-means聚類方法的多站數(shù)據(jù)關(guān)聯(lián)異常檢測

邵開霞，陳淡泊，周曉峰

基于改進(jìn)的K-means聚類方法的多站數(shù)據(jù)關(guān)聯(lián)異常檢測

邵開霞，陳淡泊，周曉峰

在傳統(tǒng)的水文時序數(shù)據(jù)研究中，我們通常只關(guān)注單個測點(diǎn)的時序數(shù)據(jù)，這不僅造成數(shù)據(jù)大量的冗余，還大大增加了工作的繁瑣度。本文針對時間序列數(shù)據(jù)聚類的統(tǒng)計特征和結(jié)構(gòu)特征，基于滑動窗口特征提取算法提出了改進(jìn)的K-means聚類方法，來探求水文時間序列數(shù)據(jù)是否在空間上存在某種關(guān)聯(lián)，并在此基礎(chǔ)上對多水文站數(shù)據(jù)進(jìn)行關(guān)聯(lián)異常檢測。

特征提?。籏-means聚類方法；異常檢測

0 引言

時間序列是一類重要的數(shù)據(jù)對象，在經(jīng)濟(jì)、氣象、醫(yī)療等領(lǐng)域都普遍存在，它們具有數(shù)據(jù)量大、維數(shù)高、更新速度快等特點(diǎn)。近年來許多學(xué)者在時間序列的挖掘方面做很多工作，相關(guān)的研究主要集中在時間序列分割、序列聚類和分類、相似查詢、模式發(fā)現(xiàn)等研究方向。所謂的時間序列就是一系列按照時間先后順序記錄的各個觀測值。相對正常時間序列數(shù)據(jù)而言，盡管異常數(shù)據(jù)數(shù)量很少，然而這并不代表異常數(shù)據(jù)不重要，相反，這些少數(shù)的異常數(shù)據(jù)卻可能隱藏著重要的信息。

聚類分析是將樣本分配到不同類的過程，K-means方法是一種最經(jīng)典的聚類分析方法，應(yīng)用也是最為廣泛的聚類方法，該方法以各類樣本的質(zhì)心代表該類不斷迭代，只適用于數(shù)字屬性數(shù)據(jù)的聚類，對超球形和凸形數(shù)據(jù)有很好的聚類效果。由于傳統(tǒng)的K-means算法需要自己指定K值大小，存在著過分依賴經(jīng)驗(yàn)和遍歷嘗試的缺點(diǎn)，本文引入了 AIC準(zhǔn)則（Akaike information criterion）對數(shù)據(jù)集進(jìn)行先驗(yàn)測試，得出可以知道K值設(shè)定的結(jié)果。

1 特征提取

本文引用基于滑動窗口的特征提取算法，它是一種詞匯重組方法，通過設(shè)定一定大小的滑動窗口。該方法的定義如下：給定時間長度為 n的時間序列其中點(diǎn)為時刻的實(shí)際觀測。此時，建立固定大小的滑窗模型對上述時間序列進(jìn)行處理：定義窗口寬度為m（m遠(yuǎn)小于n）。從第一個數(shù)據(jù)開始將序列依次放入滑窗中，通過滑窗的覆蓋來截取長度為 m的原序列數(shù)據(jù)，每次向右滑動一個節(jié)點(diǎn)以拋棄最先進(jìn)入滑窗的數(shù)據(jù)，同時加入最右數(shù)據(jù)以更新滑窗內(nèi)容，如此循環(huán)往復(fù)直到所有的數(shù)據(jù)都通過滑窗方法完成分割。

本文通過實(shí)驗(yàn)選取合適的窗口寬度，并結(jié)合領(lǐng)域規(guī)范或行業(yè)標(biāo)準(zhǔn)所規(guī)定的置信度要求來計算檢測所需要的閾值。在此，我們假設(shè)滑動窗口分割后的子序列為：S1={（s1,t1），（s2,t2），（s3,t3），……，（sm,tm）}以此為例，首先對子序列的均值和方差兩大統(tǒng)計特征進(jìn)行介紹。因?yàn)殡m然水文數(shù)據(jù)是離散的，但是它在時間維度上存在一定的延續(xù)性。子序列的平均值計算如式（1）：

方差表示數(shù)據(jù)集的離散化程度。如果兩個子序列的波動程度差異很大，很顯然我們很難將它們聚類到一起。子序列的方差計算如式（2）：

斜率是子序列的結(jié)構(gòu)特征，是表征數(shù)據(jù)變化快慢的量，當(dāng)平緩的數(shù)據(jù)里突然出現(xiàn)急劇波動的子序列時，我們便有充分的理由相信有某種原因或機(jī)制導(dǎo)致了該異常的出現(xiàn)。所以以計算斜率的方法來表征子序列的特征是合理的。斜率的計算如式（3）：

2 算法改進(jìn)

2.1 改進(jìn)的K-means聚類方法

與傳統(tǒng)的靜態(tài)數(shù)據(jù)相比，時間序列數(shù)據(jù)擁有更為大量、更為復(fù)雜、維度更高等特性。而在水文時間序列數(shù)據(jù)中這些特性尤為突出。通常我們采用以下兩種方式來處理時間序列數(shù)據(jù)的聚類問題：一是通過改進(jìn)傳統(tǒng)得聚類算法，使之能夠有效應(yīng)對時序數(shù)據(jù)的復(fù)雜性；二是通加工處理時間序列數(shù)據(jù)，使之成為相似于靜態(tài)數(shù)據(jù)的數(shù)據(jù)集。其實(shí)這兩者的本質(zhì)是相通的。

針對傳統(tǒng)聚類算法存在的問題，本文提出了針對時間序列數(shù)據(jù)的改進(jìn)的K-means聚類算法。其主要是基于時間序列數(shù)據(jù)集的結(jié)構(gòu)特征相似性對比提出的。該方法的算法流程如圖1所示：

圖1 改進(jìn)的K-means聚類算法流程圖

本文通過提取數(shù)據(jù)集的統(tǒng)計特征結(jié)構(gòu)特征，進(jìn)一步對被滑動窗口分割后的子序列進(jìn)行降維處理。為了能將提取出的特征值構(gòu)造成三維的向量，我們將傳統(tǒng)的K-means聚類方法拓展到三維空間中來對時序數(shù)據(jù)進(jìn)行聚類。

針對傳統(tǒng)的K-means方法需要自己指定k值的缺點(diǎn)，本文還引入了AIC準(zhǔn)則對數(shù)據(jù)進(jìn)行檢驗(yàn)測試，得出k值的大小。AIC準(zhǔn)則是衡量統(tǒng)計模型擬合優(yōu)良性的一種標(biāo)準(zhǔn)，它建立在熵的概念基礎(chǔ)上，可以權(quán)衡所估計模型的復(fù)雜度和此模型擬合數(shù)據(jù)的優(yōu)良性。其偽代碼如下：

我們結(jié)合經(jīng)典K-means聚類算法，在獲得了被滑動窗口分割后的子序列進(jìn)行降維處理后的數(shù)據(jù)集后，形成了針對時序數(shù)據(jù)的改進(jìn)后的K-means聚類方法。本文得到的降維處理后的數(shù)據(jù)集，每個均為三維向量，在給定K值（K＜n）的條件下，我們將原數(shù)據(jù)分成K類，即，然后求出子集中心的最小值如式（4）：

本文提出的改進(jìn)方法依然沿用基于劃分的主要思想，將特征提取降維的數(shù)據(jù)指定到k個相互排斥的子集中。與層次聚類不同，本文提出的方法更能夠適應(yīng)時間序列這種數(shù)據(jù)量比較大的數(shù)據(jù)集，而且其直接對實(shí)際觀測對象進(jìn)行操作，而不是對對象間距離集進(jìn)行操作。

2.2 算法分析

該算法的時間復(fù)雜度主要是方差、均值、斜率的運(yùn)算。除去為時序數(shù)據(jù)進(jìn)行降維準(zhǔn)備的先行算法，K-means算法本身操作的復(fù)雜度為O(nkt)，n為數(shù)據(jù)集中對象的數(shù)量。k為通過 AIC準(zhǔn)則計算聚類的簇數(shù)的算法迭代次數(shù)，最后通過回溯算法定位原時間序列數(shù)據(jù)的異常，較為容易操作。對于時間序列數(shù)據(jù)來說，可靠的降維方式能夠一定程度上保留其數(shù)據(jù)原來的復(fù)雜特征的同時降低計算的時空成本。

3 基于特征提取的聚類異常檢測方法

由于水文時序數(shù)據(jù)具有綿延性質(zhì)與隨機(jī)性質(zhì)兩大特性，使得水文數(shù)據(jù)的聚類簇結(jié)合相對而言較為緊密；現(xiàn)假設(shè)我們對兩個站點(diǎn)的水文時序數(shù)據(jù)進(jìn)行關(guān)聯(lián)異常檢測，給定時間序列數(shù)據(jù)如下：

M站點(diǎn)水文時序數(shù)據(jù)集：

為該站的n個數(shù)據(jù)簇。

N站點(diǎn)水文時序數(shù)據(jù)集：

M、N站點(diǎn)數(shù)據(jù)經(jīng)過改進(jìn)的K-means算法聚類后，得出其具體的簇分布，在此，我們?yōu)榉奖阌懻?，假設(shè)M站聚類結(jié)果為兩個個簇：N站的聚類結(jié)果為假設(shè)的分布位置于位置相似；與位置相似。當(dāng)聚類結(jié)果進(jìn)行展示時，根據(jù)中數(shù)據(jù)還原出相應(yīng)時間區(qū)間，并回溯該時間區(qū)間在簇中的位置，如果出現(xiàn)在簇中，我們能夠判斷其非異常。但是，我們并不能保證還原出的時間區(qū)間中的所有數(shù)據(jù)都恰好出現(xiàn)在簇中，所以我們有一定理由懷疑簇存在異常性。

我們此時引入置信區(qū)間的概念：根據(jù)《水文巡測規(guī)范》，水文站數(shù)據(jù)監(jiān)測可靠度要求為 95%，如果該數(shù)據(jù)集中 95%的數(shù)據(jù)為正常數(shù)據(jù)時，則很顯然剩余5%的數(shù)據(jù)具有較為明顯的異常性。此時，如果簇數(shù)據(jù)回溯后在簇中的概率大于設(shè)定的置信度P，則我們通過判斷該簇中對象與中心對象的距離來確認(rèn)異常性，取前95%的數(shù)據(jù)為正常數(shù)據(jù)，則其他簇中與簇中的數(shù)據(jù)認(rèn)定為異常；反之，我們則認(rèn)為仍有一定比例的正常數(shù)據(jù)在相近的聚類簇中。通過這樣的方法依次檢驗(yàn)兩站通過回溯后對兩站的異常檢測?；诳臻g關(guān)系上的異常檢測是相互的，所以基于M站數(shù)據(jù)對N站數(shù)據(jù)異常檢測的同時，我們也必不能忽略基于N站數(shù)據(jù)對M站數(shù)據(jù)進(jìn)行檢測的結(jié)果，進(jìn)行對比分析，得出全面合理的檢測結(jié)果。

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

4.1 實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)的環(huán)境配置如表1所示：

表1 實(shí)驗(yàn)環(huán)境配置表

4.2 數(shù)據(jù)預(yù)處理

數(shù)據(jù)規(guī)范化，指將一個低一級范式的關(guān)系模式，通過分解轉(zhuǎn)換為若干個高一級范式的關(guān)系模式的集合的過程，通常我們有Max-Min歸一化和均值規(guī)范化兩種最常用的方法，考慮到均值規(guī)范化后的數(shù)值仍處于散亂狀態(tài)無法聚集在固定的區(qū)間內(nèi)，為后續(xù)實(shí)驗(yàn)帶來不便，本文使用Max-Min歸一化如式（5）：

4.3 實(shí)驗(yàn)過程

該實(shí)驗(yàn)使用某市地域相近，人工水利設(shè)施極少的M站和 N站兩水文監(jiān)測站的記錄數(shù)據(jù)，適合進(jìn)行關(guān)聯(lián)分析。時間從2010年5月11號到2016年1月11號，兩站分別共計五萬余條數(shù)據(jù)，采集系統(tǒng)每小時獲取一次數(shù)據(jù)，期間并無遺漏如圖2、圖3所示：

圖2 M站水位數(shù)據(jù)

圖3 N站水位數(shù)據(jù)

根據(jù)圖2、圖3比較，我們發(fā)現(xiàn)兩站的數(shù)據(jù)變化及其相似，但我們并不能確定兩者存在的關(guān)聯(lián)關(guān)系，

因此，我們將對其進(jìn)行進(jìn)一步分析，判斷該兩站水文時序數(shù)據(jù)間是否存在某種關(guān)系。

通過對兩站數(shù)據(jù)的線性相關(guān)性檢驗(yàn)，我們得到兩站數(shù)據(jù)的相關(guān)性為0.898，說明兩組數(shù)據(jù)并無絕對的線性相關(guān)性。首先，我們隊(duì)原時序數(shù)據(jù)進(jìn)行Max-Min歸一化處理，得到兩站規(guī)范化后的數(shù)據(jù)集。再對兩站進(jìn)行 AIC準(zhǔn)則檢驗(yàn)，通過計算驗(yàn)證，M站和N站的最佳K值均為4，對應(yīng)分別為接下來，我們使用改進(jìn)后的K-means聚類方法對兩站數(shù)據(jù)進(jìn)行聚類分析，并以圖像呈現(xiàn)，M站數(shù)據(jù)聚類圖如圖4所示：

圖4 M站數(shù)據(jù)聚類圖

N站數(shù)據(jù)聚類圖如圖5所示：

圖5 N站數(shù)據(jù)聚類圖

通過觀察，我們不難發(fā)現(xiàn)兩站數(shù)據(jù)分布極其相似，但兩者的均值、方差、斜率的分布具體細(xì)節(jié)還是有很大區(qū)別，在

此，我們考慮兩者是否存在可探究的弱關(guān)聯(lián)關(guān)系具體數(shù)據(jù)如 表1、表2所示：

表1 M站數(shù)據(jù)特征提取數(shù)值表

表2 N站數(shù)據(jù)特征提取數(shù)值表

進(jìn)行聚類的數(shù)據(jù)經(jīng)過了特征提取，經(jīng)過了歸一化處理，我們難以帶著時間維度進(jìn)行精確的分析。這時候我們采用跟蹤數(shù)據(jù)的方式。降維以前的一個滑動窗口大小的子序列，我們用降維以后的一個數(shù)據(jù)點(diǎn)代表。通過還原，我們能夠很容易的得到在具體的時間點(diǎn)上降維以后的數(shù)據(jù)聚類的情況，同時對兩站數(shù)據(jù)的聚類情況進(jìn)行跟蹤處理，并加以分析。

將M站數(shù)據(jù)集的聚類分為四個簇，橫坐標(biāo)是斜率的大小，縱坐標(biāo)為均值、方差的加權(quán)平均。很容易能看出四個簇的均值、方差和斜率的變化率都依次增大。當(dāng)M站聚類數(shù)據(jù)在第一簇時，該簇數(shù)據(jù)為[0.003，0.71；0.003,0.73；……；0.004；0.74]（因數(shù)據(jù)量龐大，在此僅展示少量數(shù)據(jù)）。據(jù)此，易追溯其原來降維前的時序子序列數(shù)據(jù)[7.23；7.23；7.24；……；7.26]、[7.23；7.24；7.24；……；7.26]……[8.46；8.46；8.46；……；8.72]。故而，我們可以追溯到子序列所對應(yīng)的時間，以觀察同時間段內(nèi)，N站的數(shù)據(jù)經(jīng)過降維聚類以后對應(yīng)的數(shù)據(jù)簇如圖6所示：

圖6 簇回溯可能性分析

根據(jù)此方法，我們可以知道當(dāng)M站數(shù)據(jù)簇聚集在簇1、2、3、4時，N站數(shù)據(jù)在各個簇的情況如表3所示：

表3 M、N站數(shù)據(jù)分布情況表

根據(jù)《水文巡測規(guī)范》，該水文站數(shù)據(jù)監(jiān)測可靠度要求為95%，進(jìn)一步進(jìn)行異常檢測，在以上基礎(chǔ)上，我們對聚類結(jié)果進(jìn)行進(jìn)一步異常檢測。

首先基于M站數(shù)據(jù)，對N站數(shù)據(jù)進(jìn)行異常檢測，根據(jù)表3數(shù)據(jù)可知，當(dāng)置信度P為95%時，簇1中的數(shù)據(jù)為非異常數(shù)據(jù)，且仍存在5.38%的數(shù)據(jù)分布在其他簇中。此時，根據(jù)改進(jìn)的K-means聚類方法衡量數(shù)據(jù)的相似度，以距離作為衡量標(biāo)準(zhǔn)，我們可以認(rèn)為距離簇1的中心點(diǎn)距離最近的5.38%的數(shù)據(jù)為非異常數(shù)據(jù)，其他為異常數(shù)據(jù)。在所有非異常數(shù)據(jù)確認(rèn)的基礎(chǔ)上，在M站簇1里被還原出的時間區(qū)間里，則將剩余數(shù)據(jù)判定為異常數(shù)據(jù)，如圖7所示：

圖7 N站聚類異常分析圖

然后回溯其原時間區(qū)間所對應(yīng)的子序列的位置，并標(biāo)定為異常即紅色部分，如圖8所示：

圖8 N站時序異常圖

圖8N站時序異常圖通過以上方法，我們很容易得出基于M站對N站的異常檢測的其他三簇的結(jié)果，在此就不上圖說明。通過四個簇的結(jié)果發(fā)現(xiàn)，當(dāng)對各個簇分別進(jìn)行聚類異常檢測時，我們能夠得到四個簇各自對應(yīng)的異常檢測結(jié)果，雖然其中有少數(shù)異常是重復(fù)出現(xiàn)的，但相當(dāng)一部分的異常是獨(dú)自出現(xiàn)的。我們將四簇異常結(jié)果疊加，很容易得到基于M站和N站基礎(chǔ)上，對N站進(jìn)行檢測的綜合聚類異常分析圖和，我們繼續(xù)將各類情況綜合疊加，就能夠得到基于M站與N站關(guān)聯(lián)關(guān)系的基礎(chǔ)上進(jìn)行異常檢測的N站的聚類異常分析結(jié)果與之對應(yīng)的N站水文時序數(shù)據(jù)異常檢測圖，如圖9、圖10所示：

圖9 N站聚類異常分析綜合圖

圖10 N站時序數(shù)據(jù)異常檢測綜合圖

同時，我們通過這樣的方法，進(jìn)一步基于N站的數(shù)據(jù)對M站的數(shù)據(jù)進(jìn)行異常檢測，為簡化篇幅，這里我們給出其檢測的最后結(jié)果如圖11、圖12所示：

圖11 M站綜合聚類分析異常圖

圖12 M站時序數(shù)據(jù)異常檢測綜合圖

根據(jù)以上實(shí)驗(yàn)結(jié)果，我們可知兩水文站數(shù)據(jù)之間雖然不存在直接的線性關(guān)聯(lián)關(guān)系，但還是存在著很大意義上的弱相關(guān)性。

5 總結(jié)

本文基于滑動窗口特征提取方法提出了改進(jìn) K-means算法，與傳統(tǒng)的聚類算法相比，本文提出的改進(jìn)型K-means算法在一定程度上保留了水文時序數(shù)據(jù)集的統(tǒng)計特征和結(jié)構(gòu)特征。本文還基于水文時間序列數(shù)據(jù)的空間關(guān)聯(lián)性，在特征提取的基礎(chǔ)上繼而進(jìn)行聚類操作。首先利用滑動窗口分割時序數(shù)據(jù)并獲取相應(yīng)的子序列集合，緊接提取其均值、方差、斜率等特征，并組合成特征向量。在此基礎(chǔ)上進(jìn)一步利用經(jīng)典的K-means方法對特征向量操作聚類，形成了完整的針對水文時間序列數(shù)據(jù)的聚類方法，并在此基礎(chǔ)上通過對聚類結(jié)果的分析完成基于多站水文數(shù)據(jù)關(guān)聯(lián)關(guān)系的異常檢測工作。

[1] 李深洛. 基于特征的時間序列聚類[D].桂林：廣西師范大學(xué),2014.

[2] 宋辭,裴韜. 基于特征的時間序列聚類方法研究進(jìn)展[J].地理科學(xué)進(jìn)展,2012,10：1307-1317.

[3] 孫友強(qiáng). 時間序列數(shù)據(jù)挖掘中的維數(shù)約簡與預(yù)測方法研究[D].合肥：中國科學(xué)技術(shù)大學(xué),2014.

[4] 翁小清,沈鈞毅.基于滑動窗口的多變量時間序列異常數(shù)據(jù)的挖掘[J].計算機(jī)工程,2007, 33(12)： 102-104.

[5] 余宇峰,朱躍龍,萬定生,關(guān)興中.基于滑動窗口預(yù)測的水文時間序列異常檢測[J].計算機(jī)應(yīng)用,2014,08：

2217-2220.

[6] 杜洪波.時間序列相似性查詢及異常檢測算法的研究[D].沈陽：沈陽工業(yè)大學(xué),2008.

[7] 曲吉林. 時間序列挖掘中索引與查詢技術(shù)的研究[D].天津大學(xué),2006.

[8] 趙利紅.水文時間序列周期分析方法的研究[D].南京： 河海大學(xué)碩士, 2007.

[9] 中華人民共和國水利部. SL195-2015， 中華人民共和國水利行業(yè)標(biāo)準(zhǔn)[M]. 北京： 中國水利水電出版社,

2016：4.3.8.

Multistation Data Correlation Anomaly Detection Based on Improved K- means Clustering Method

Shao Kaixia, Chen Danbo, Zhou Xiaofeng
(Department of Data Minging,Hohai University, Nanjing 21100, China)

In the study of traditional hydrological time-series data, it usually only focuses on a single point of time-series data. This not only causes a large number of redundant data, but also greatly increases the complicated degree of work. In this paper, according to the statistical characteristics and structure features of time-series data clustering, K-means clustering method which is based on feature extraction algorithm of sliding window is put forward to explore whether there is a correlation between hydrological time series data in the space, and anomaly detect the multiple hydrologic data on the basis of it.

Feature extraction； K-means clustering method； Anomaly detection

TP311

A

1007-757X(2016)11-0074-05

2016.07.29）

邵開霞（1992-），女，河海大學(xué)，碩士研究生，研究方向：數(shù)據(jù)挖掘，南京 211100

陳淡泊（1991-），男，河海大學(xué)，碩士研究生，研究方向：數(shù)據(jù)挖掘，南京 211100

周曉峰（1965-），男，河海大學(xué)，教授，研究方向：數(shù)據(jù)挖掘，南京 211100