邵開霞,陳淡泊,周曉峰
基于改進(jìn)的K-means聚類方法的多站數(shù)據(jù)關(guān)聯(lián)異常檢測(cè)
邵開霞,陳淡泊,周曉峰
在傳統(tǒng)的水文時(shí)序數(shù)據(jù)研究中,我們通常只關(guān)注單個(gè)測(cè)點(diǎn)的時(shí)序數(shù)據(jù),這不僅造成數(shù)據(jù)大量的冗余,還大大增加了工作的繁瑣度。本文針對(duì)時(shí)間序列數(shù)據(jù)聚類的統(tǒng)計(jì)特征和結(jié)構(gòu)特征,基于滑動(dòng)窗口特征提取算法提出了改進(jìn)的K-means聚類方法,來探求水文時(shí)間序列數(shù)據(jù)是否在空間上存在某種關(guān)聯(lián),并在此基礎(chǔ)上對(duì)多水文站數(shù)據(jù)進(jìn)行關(guān)聯(lián)異常檢測(cè)。
特征提??;K-means聚類方法;異常檢測(cè)
時(shí)間序列是一類重要的數(shù)據(jù)對(duì)象,在經(jīng)濟(jì)、氣象、醫(yī)療等領(lǐng)域都普遍存在,它們具有數(shù)據(jù)量大、維數(shù)高、更新速度快等特點(diǎn)。近年來許多學(xué)者在時(shí)間序列的挖掘方面做很多工作,相關(guān)的研究主要集中在時(shí)間序列分割、序列聚類和分類、相似查詢、模式發(fā)現(xiàn)等研究方向。所謂的時(shí)間序列就是一系列按照時(shí)間先后順序記錄的各個(gè)觀測(cè)值。相對(duì)正常時(shí)間序列數(shù)據(jù)而言,盡管異常數(shù)據(jù)數(shù)量很少,然而這并不代表異常數(shù)據(jù)不重要,相反,這些少數(shù)的異常數(shù)據(jù)卻可能隱藏著重要的信息。
聚類分析是將樣本分配到不同類的過程,K-means方法是一種最經(jīng)典的聚類分析方法,應(yīng)用也是最為廣泛的聚類方法,該方法以各類樣本的質(zhì)心代表該類不斷迭代,只適用于數(shù)字屬性數(shù)據(jù)的聚類,對(duì)超球形和凸形數(shù)據(jù)有很好的聚類效果。由于傳統(tǒng)的K-means算法需要自己指定K值大小,存在著過分依賴經(jīng)驗(yàn)和遍歷嘗試的缺點(diǎn),本文引入了 AIC準(zhǔn)則(Akaike information criterion)對(duì)數(shù)據(jù)集進(jìn)行先驗(yàn)測(cè)試,得出可以知道K值設(shè)定的結(jié)果。
本文引用基于滑動(dòng)窗口的特征提取算法,它是一種詞匯重組方法,通過設(shè)定一定大小的滑動(dòng)窗口。該方法的定義如下:給定時(shí)間長(zhǎng)度為 n的時(shí)間序列其中點(diǎn)為時(shí)刻的實(shí)際觀測(cè)。此時(shí),建立固定大小的滑窗模型對(duì)上述時(shí)間序列進(jìn)行處理:定義窗口寬度為m(m遠(yuǎn)小于n)。從第一個(gè)數(shù)據(jù)開始將序列依次放入滑窗中,通過滑窗的覆蓋來截取長(zhǎng)度為 m的原序列數(shù)據(jù),每次向右滑動(dòng)一個(gè)節(jié)點(diǎn)以拋棄最先進(jìn)入滑窗的數(shù)據(jù),同時(shí)加入最右數(shù)據(jù)以更新滑窗內(nèi)容,如此循環(huán)往復(fù)直到所有的數(shù)據(jù)都通過滑窗方法完成分割。
本文通過實(shí)驗(yàn)選取合適的窗口寬度,并結(jié)合領(lǐng)域規(guī)范或行業(yè)標(biāo)準(zhǔn)所規(guī)定的置信度要求來計(jì)算檢測(cè)所需要的閾值。在此,我們假設(shè)滑動(dòng)窗口分割后的子序列為:S1={(s1,t1),(s2,t2),(s3,t3),……,(sm,tm)}以此為例,首先對(duì)子序列的均值和方差兩大統(tǒng)計(jì)特征進(jìn)行介紹。因?yàn)殡m然水文數(shù)據(jù)是離散的,但是它在時(shí)間維度上存在一定的延續(xù)性。子序列的平均值計(jì)算如式(1):
方差表示數(shù)據(jù)集的離散化程度。如果兩個(gè)子序列的波動(dòng)程度差異很大,很顯然我們很難將它們聚類到一起。子序列的方差計(jì)算如式(2):
斜率是子序列的結(jié)構(gòu)特征,是表征數(shù)據(jù)變化快慢的量,當(dāng)平緩的數(shù)據(jù)里突然出現(xiàn)急劇波動(dòng)的子序列時(shí),我們便有充分的理由相信有某種原因或機(jī)制導(dǎo)致了該異常的出現(xiàn)。所以以計(jì)算斜率的方法來表征子序列的特征是合理的。斜率的計(jì)算如式(3):
2.1 改進(jìn)的K-means聚類方法
與傳統(tǒng)的靜態(tài)數(shù)據(jù)相比,時(shí)間序列數(shù)據(jù)擁有更為大量、更為復(fù)雜、維度更高等特性。而在水文時(shí)間序列數(shù)據(jù)中這些特性尤為突出。通常我們采用以下兩種方式來處理時(shí)間序列數(shù)據(jù)的聚類問題:一是通過改進(jìn)傳統(tǒng)得聚類算法,使之能夠有效應(yīng)對(duì)時(shí)序數(shù)據(jù)的復(fù)雜性;二是通加工處理時(shí)間序列數(shù)據(jù),使之成為相似于靜態(tài)數(shù)據(jù)的數(shù)據(jù)集。其實(shí)這兩者的本質(zhì)是相通的。
針對(duì)傳統(tǒng)聚類算法存在的問題,本文提出了針對(duì)時(shí)間序列數(shù)據(jù)的改進(jìn)的K-means聚類算法。其主要是基于時(shí)間序列數(shù)據(jù)集的結(jié)構(gòu)特征相似性對(duì)比提出的。該方法的算法流程如圖1所示:
圖1 改進(jìn)的K-means聚類算法流程圖
本文通過提取數(shù)據(jù)集的統(tǒng)計(jì)特征結(jié)構(gòu)特征,進(jìn)一步對(duì)被滑動(dòng)窗口分割后的子序列進(jìn)行降維處理。為了能將提取出的特征值構(gòu)造成三維的向量,我們將傳統(tǒng)的K-means聚類方法拓展到三維空間中來對(duì)時(shí)序數(shù)據(jù)進(jìn)行聚類。
針對(duì)傳統(tǒng)的K-means方法需要自己指定k值的缺點(diǎn),本文還引入了AIC準(zhǔn)則對(duì)數(shù)據(jù)進(jìn)行檢驗(yàn)測(cè)試,得出k值的大小。AIC準(zhǔn)則是衡量統(tǒng)計(jì)模型擬合優(yōu)良性的一種標(biāo)準(zhǔn),它建立在熵的概念基礎(chǔ)上,可以權(quán)衡所估計(jì)模型的復(fù)雜度和此模型擬合數(shù)據(jù)的優(yōu)良性。其偽代碼如下:
我們結(jié)合經(jīng)典K-means聚類算法,在獲得了被滑動(dòng)窗口分割后的子序列進(jìn)行降維處理后的數(shù)據(jù)集后,形成了針對(duì)時(shí)序數(shù)據(jù)的改進(jìn)后的K-means聚類方法。本文得到的降維處理后的數(shù)據(jù)集,每個(gè)均為三維向量,在給定K值(K<n)的條件下,我們將原數(shù)據(jù)分成K類,即,然后求出子集中心的最小值如式(4):
本文提出的改進(jìn)方法依然沿用基于劃分的主要思想,將特征提取降維的數(shù)據(jù)指定到k個(gè)相互排斥的子集中。與層次聚類不同,本文提出的方法更能夠適應(yīng)時(shí)間序列這種數(shù)據(jù)量比較大的數(shù)據(jù)集,而且其直接對(duì)實(shí)際觀測(cè)對(duì)象進(jìn)行操作,而不是對(duì)對(duì)象間距離集進(jìn)行操作。
2.2 算法分析
該算法的時(shí)間復(fù)雜度主要是方差、均值、斜率的運(yùn)算。除去為時(shí)序數(shù)據(jù)進(jìn)行降維準(zhǔn)備的先行算法,K-means算法本身操作的復(fù)雜度為O(nkt),n為數(shù)據(jù)集中對(duì)象的數(shù)量。k為通過 AIC準(zhǔn)則計(jì)算聚類的簇?cái)?shù)的算法迭代次數(shù),最后通過回溯算法定位原時(shí)間序列數(shù)據(jù)的異常,較為容易操作。對(duì)于時(shí)間序列數(shù)據(jù)來說,可靠的降維方式能夠一定程度上保留其數(shù)據(jù)原來的復(fù)雜特征的同時(shí)降低計(jì)算的時(shí)空成本。
由于水文時(shí)序數(shù)據(jù)具有綿延性質(zhì)與隨機(jī)性質(zhì)兩大特性,使得水文數(shù)據(jù)的聚類簇結(jié)合相對(duì)而言較為緊密;現(xiàn)假設(shè)我們對(duì)兩個(gè)站點(diǎn)的水文時(shí)序數(shù)據(jù)進(jìn)行關(guān)聯(lián)異常檢測(cè),給定時(shí)間序列數(shù)據(jù)如下:
M站點(diǎn)水文時(shí)序數(shù)據(jù)集:
為該站的n個(gè)數(shù)據(jù)簇。
N站點(diǎn)水文時(shí)序數(shù)據(jù)集:
M、N站點(diǎn)數(shù)據(jù)經(jīng)過改進(jìn)的K-means算法聚類后,得出其具體的簇分布,在此,我們?yōu)榉奖阌懻?,假設(shè)M站聚類結(jié)果為兩個(gè)個(gè)簇:N站的聚類結(jié)果為假設(shè)的分布位置于位置相似;與位置相似。當(dāng)聚類結(jié)果進(jìn)行展示時(shí),根據(jù)中數(shù)據(jù)還原出相應(yīng)時(shí)間區(qū)間,并回溯該時(shí)間區(qū)間在簇中的位置,如果出現(xiàn)在簇中,我們能夠判斷其非異常。但是,我們并不能保證還原出的時(shí)間區(qū)間中的所有數(shù)據(jù)都恰好出現(xiàn)在簇中,所以我們有一定理由懷疑簇存在異常性。
我們此時(shí)引入置信區(qū)間的概念:根據(jù)《水文巡測(cè)規(guī)范》,水文站數(shù)據(jù)監(jiān)測(cè)可靠度要求為 95%,如果該數(shù)據(jù)集中 95%的數(shù)據(jù)為正常數(shù)據(jù)時(shí),則很顯然剩余5%的數(shù)據(jù)具有較為明顯的異常性。此時(shí),如果簇?cái)?shù)據(jù)回溯后在簇中的概率大于設(shè)定的置信度P,則我們通過判斷該簇中對(duì)象與中心對(duì)象的距離來確認(rèn)異常性,取前95%的數(shù)據(jù)為正常數(shù)據(jù),則其他簇中與簇中的數(shù)據(jù)認(rèn)定為異常;反之,我們則認(rèn)為仍有一定比例的正常數(shù)據(jù)在相近的聚類簇中。通過這樣的方法依次檢驗(yàn)兩站通過回溯后對(duì)兩站的異常檢測(cè)?;诳臻g關(guān)系上的異常檢測(cè)是相互的,所以基于M站數(shù)據(jù)對(duì)N站數(shù)據(jù)異常檢測(cè)的同時(shí),我們也必不能忽略基于N站數(shù)據(jù)對(duì)M站數(shù)據(jù)進(jìn)行檢測(cè)的結(jié)果,進(jìn)行對(duì)比分析,得出全面合理的檢測(cè)結(jié)果。
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ī)范化,指將一個(gè)低一級(jí)范式的關(guān)系模式,通過分解轉(zhuǎn)換為若干個(gè)高一級(jí)范式的關(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)測(cè)站的記錄數(shù)據(jù),適合進(jìn)行關(guān)聯(lián)分析。時(shí)間從2010年5月11號(hào)到2016年1月11號(hào),兩站分別共計(jì)五萬余條數(shù)據(jù),采集系統(tǒng)每小時(shí)獲取一次數(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)系,
因此,我們將對(duì)其進(jìn)行進(jìn)一步分析,判斷該兩站水文時(shí)序數(shù)據(jù)間是否存在某種關(guān)系。
通過對(duì)兩站數(shù)據(jù)的線性相關(guān)性檢驗(yàn),我們得到兩站數(shù)據(jù)的相關(guān)性為0.898,說明兩組數(shù)據(jù)并無絕對(duì)的線性相關(guān)性。首先,我們隊(duì)原時(shí)序數(shù)據(jù)進(jìn)行Max-Min歸一化處理,得到兩站規(guī)范化后的數(shù)據(jù)集。再對(duì)兩站進(jìn)行 AIC準(zhǔn)則檢驗(yàn),通過計(jì)算驗(yàn)證,M站和N站的最佳K值均為4,對(duì)應(yīng)分別為接下來,我們使用改進(jìn)后的K-means聚類方法對(duì)兩站數(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)過了歸一化處理,我們難以帶著時(shí)間維度進(jìn)行精確的分析。這時(shí)候我們采用跟蹤數(shù)據(jù)的方式。降維以前的一個(gè)滑動(dòng)窗口大小的子序列,我們用降維以后的一個(gè)數(shù)據(jù)點(diǎn)代表。通過還原,我們能夠很容易的得到在具體的時(shí)間點(diǎn)上降維以后的數(shù)據(jù)聚類的情況,同時(shí)對(duì)兩站數(shù)據(jù)的聚類情況進(jìn)行跟蹤處理,并加以分析。
將M站數(shù)據(jù)集的聚類分為四個(gè)簇,橫坐標(biāo)是斜率的大小,縱坐標(biāo)為均值、方差的加權(quán)平均。很容易能看出四個(gè)簇的均值、方差和斜率的變化率都依次增大。當(dāng)M站聚類數(shù)據(jù)在第一簇時(shí),該簇?cái)?shù)據(jù)為[0.003,0.71;0.003,0.73;……;0.004;0.74](因數(shù)據(jù)量龐大,在此僅展示少量數(shù)據(jù))。據(jù)此,易追溯其原來降維前的時(shí)序子序列數(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]。故而,我們可以追溯到子序列所對(duì)應(yīng)的時(shí)間,以觀察同時(shí)間段內(nèi),N站的數(shù)據(jù)經(jīng)過降維聚類以后對(duì)應(yīng)的數(shù)據(jù)簇如圖6所示:
圖6 簇回溯可能性分析
根據(jù)此方法,我們可以知道當(dāng)M站數(shù)據(jù)簇聚集在簇1、2、3、4時(shí),N站數(shù)據(jù)在各個(gè)簇的情況如表3所示:
表3 M、N站數(shù)據(jù)分布情況表
根據(jù)《水文巡測(cè)規(guī)范》,該水文站數(shù)據(jù)監(jiān)測(cè)可靠度要求為95%,進(jìn)一步進(jìn)行異常檢測(cè),在以上基礎(chǔ)上,我們對(duì)聚類結(jié)果進(jìn)行進(jìn)一步異常檢測(cè)。
首先基于M站數(shù)據(jù),對(duì)N站數(shù)據(jù)進(jìn)行異常檢測(cè),根據(jù)表3數(shù)據(jù)可知,當(dāng)置信度P為95%時(shí),簇1中的數(shù)據(jù)為非異常數(shù)據(jù),且仍存在5.38%的數(shù)據(jù)分布在其他簇中。此時(shí),根據(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里被還原出的時(shí)間區(qū)間里,則將剩余數(shù)據(jù)判定為異常數(shù)據(jù),如圖7所示:
圖7 N站聚類異常分析圖
然后回溯其原時(shí)間區(qū)間所對(duì)應(yīng)的子序列的位置,并標(biāo)定為異常即紅色部分,如圖8所示:
圖8 N站時(shí)序異常圖
圖8N站時(shí)序異常圖通過以上方法,我們很容易得出基于M站對(duì)N站的異常檢測(cè)的其他三簇的結(jié)果,在此就不上圖說明。通過四個(gè)簇的結(jié)果發(fā)現(xiàn),當(dāng)對(duì)各個(gè)簇分別進(jìn)行聚類異常檢測(cè)時(shí),我們能夠得到四個(gè)簇各自對(duì)應(yīng)的異常檢測(cè)結(jié)果,雖然其中有少數(shù)異常是重復(fù)出現(xiàn)的,但相當(dāng)一部分的異常是獨(dú)自出現(xiàn)的。我們將四簇異常結(jié)果疊加,很容易得到基于M站和N站基礎(chǔ)上,對(duì)N站進(jìn)行檢測(cè)的綜合聚類異常分析圖和,我們繼續(xù)將各類情況綜合疊加,就能夠得到基于M站與N站關(guān)聯(lián)關(guān)系的基礎(chǔ)上進(jìn)行異常檢測(cè)的N站的聚類異常分析結(jié)果與之對(duì)應(yīng)的N站水文時(shí)序數(shù)據(jù)異常檢測(cè)圖,如圖9、圖10所示:
圖9 N站聚類異常分析綜合圖
圖10 N站時(shí)序數(shù)據(jù)異常檢測(cè)綜合圖
同時(shí),我們通過這樣的方法,進(jìn)一步基于N站的數(shù)據(jù)對(duì)M站的數(shù)據(jù)進(jìn)行異常檢測(cè),為簡(jiǎn)化篇幅,這里我們給出其檢測(cè)的最后結(jié)果如圖11、圖12所示:
圖11 M站綜合聚類分析異常圖
圖12 M站時(shí)序數(shù)據(jù)異常檢測(cè)綜合圖
根據(jù)以上實(shí)驗(yàn)結(jié)果,我們可知兩水文站數(shù)據(jù)之間雖然不存在直接的線性關(guān)聯(lián)關(guān)系,但還是存在著很大意義上的弱相關(guān)性。
本文基于滑動(dòng)窗口特征提取方法提出了改進(jìn) K-means算法,與傳統(tǒng)的聚類算法相比,本文提出的改進(jìn)型K-means算法在一定程度上保留了水文時(shí)序數(shù)據(jù)集的統(tǒng)計(jì)特征和結(jié)構(gòu)特征。本文還基于水文時(shí)間序列數(shù)據(jù)的空間關(guān)聯(lián)性,在特征提取的基礎(chǔ)上繼而進(jìn)行聚類操作。首先利用滑動(dòng)窗口分割時(shí)序數(shù)據(jù)并獲取相應(yīng)的子序列集合,緊接提取其均值、方差、斜率等特征,并組合成特征向量。在此基礎(chǔ)上進(jìn)一步利用經(jīng)典的K-means方法對(duì)特征向量操作聚類,形成了完整的針對(duì)水文時(shí)間序列數(shù)據(jù)的聚類方法,并在此基礎(chǔ)上通過對(duì)聚類結(jié)果的分析完成基于多站水文數(shù)據(jù)關(guān)聯(lián)關(guān)系的異常檢測(cè)工作。
[1] 李深洛. 基于特征的時(shí)間序列聚類[D].桂林:廣西師范大學(xué),2014.
[2] 宋辭,裴韜. 基于特征的時(shí)間序列聚類方法研究進(jìn)展[J].地理科學(xué)進(jìn)展,2012,10:1307-1317.
[3] 孫友強(qiáng). 時(shí)間序列數(shù)據(jù)挖掘中的維數(shù)約簡(jiǎn)與預(yù)測(cè)方法研究[D].合肥:中國(guó)科學(xué)技術(shù)大學(xué),2014.
[4] 翁小清,沈鈞毅.基于滑動(dòng)窗口的多變量時(shí)間序列異常數(shù)據(jù)的挖掘[J].計(jì)算機(jī)工程,2007, 33(12): 102-104.
[5] 余宇峰,朱躍龍,萬定生,關(guān)興中.基于滑動(dòng)窗口預(yù)測(cè)的水文時(shí)間序列異常檢測(cè)[J].計(jì)算機(jī)應(yīng)用,2014,08:
2217-2220.
[6] 杜洪波.時(shí)間序列相似性查詢及異常檢測(cè)算法的研究[D].沈陽:沈陽工業(yè)大學(xué),2008.
[7] 曲吉林. 時(shí)間序列挖掘中索引與查詢技術(shù)的研究[D].天津大學(xué),2006.
[8] 趙利紅.水文時(shí)間序列周期分析方法的研究[D].南京: 河海大學(xué)碩士, 2007.
[9] 中華人民共和國(guó)水利部. SL195-2015, 中華人民共和國(guó)水利行業(yè)標(biāo)準(zhǔn)[M]. 北京: 中國(guó)水利水電出版社,
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