基于改進的K-means聚類方法的多站數據關聯異常檢測

邵開霞，陳淡泊，周曉峰

基于改進的K-means聚類方法的多站數據關聯異常檢測

邵開霞，陳淡泊，周曉峰

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

特征提取；K-means聚類方法；異常檢測

0 引言

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

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

1 特征提取

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

本文通過實驗選取合適的窗口寬度，并結合領域規范或行業標準所規定的置信度要求來計算檢測所需要的閾值。在此，我們假設滑動窗口分割后的子序列為：S1={（s1,t1），（s2,t2），（s3,t3），……，（sm,tm）}以此為例，首先對子序列的均值和方差兩大統計特征進行介紹。因為雖然水文數據是離散的，但是它在時間維度上存在一定的延續性。子序列的平均值計算如式（1）：

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

斜率是子序列的結構特征，是表征數據變化快慢的量，當平緩的數據里突然出現急劇波動的子序列時，我們便有充分的理由相信有某種原因或機制導致了該異常的出現。所以以計算斜率的方法來表征子序列的特征是合理的。斜率的計算如式（3）：

2 算法改進

2.1 改進的K-means聚類方法

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

針對傳統聚類算法存在的問題，本文提出了針對時間序列數據的改進的K-means聚類算法。其主要是基于時間序列數據集的結構特征相似性對比提出的。該方法的算法流程如圖1所示：

圖1 改進的K-means聚類算法流程圖

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

針對傳統的K-means方法需要自己指定k值的缺點，本文還引入了AIC準則對數據進行檢驗測試，得出k值的大小。AIC準則是衡量統計模型擬合優良性的一種標準，它建立在熵的概念基礎上，可以權衡所估計模型的復雜度和此模型擬合數據的優良性。其偽代碼如下：

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

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

2.2 算法分析

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

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

由于水文時序數據具有綿延性質與隨機性質兩大特性，使得水文數據的聚類簇結合相對而言較為緊密；現假設我們對兩個站點的水文時序數據進行關聯異常檢測，給定時間序列數據如下：

M站點水文時序數據集：

為該站的n個數據簇。

N站點水文時序數據集：

M、N站點數據經過改進的K-means算法聚類后，得出其具體的簇分布，在此，我們為方便討論，假設M站聚類結果為兩個個簇：N站的聚類結果為假設的分布位置于位置相似；與位置相似。當聚類結果進行展示時，根據中數據還原出相應時間區間，并回溯該時間區間在簇中的位置，如果出現在簇中，我們能夠判斷其非異常。但是，我們并不能保證還原出的時間區間中的所有數據都恰好出現在簇中，所以我們有一定理由懷疑簇存在異常性。

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

4 實驗

4.1 實驗環境

實驗的環境配置如表1所示：

表1 實驗環境配置表

4.2 數據預處理

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

4.3 實驗過程

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

圖2 M站水位數據

圖3 N站水位數據

根據圖2、圖3比較，我們發現兩站的數據變化及其相似，但我們并不能確定兩者存在的關聯關系，

因此，我們將對其進行進一步分析，判斷該兩站水文時序數據間是否存在某種關系。

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

圖4 M站數據聚類圖

N站數據聚類圖如圖5所示：

圖5 N站數據聚類圖

通過觀察，我們不難發現兩站數據分布極其相似，但兩者的均值、方差、斜率的分布具體細節還是有很大區別，在

此，我們考慮兩者是否存在可探究的弱關聯關系具體數據如 表1、表2所示：

表1 M站數據特征提取數值表

表2 N站數據特征提取數值表

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

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

圖6 簇回溯可能性分析

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

表3 M、N站數據分布情況表

根據《水文巡測規范》，該水文站數據監測可靠度要求為95%，進一步進行異常檢測，在以上基礎上，我們對聚類結果進行進一步異常檢測。

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

圖7 N站聚類異常分析圖

然后回溯其原時間區間所對應的子序列的位置，并標定為異常即紅色部分，如圖8所示：

圖8 N站時序異常圖

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

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

圖10 N站時序數據異常檢測綜合圖

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

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

圖12 M站時序數據異常檢測綜合圖

根據以上實驗結果，我們可知兩水文站數據之間雖然不存在直接的線性關聯關系，但還是存在著很大意義上的弱相關性。

5 總結

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

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

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

[3] 孫友強. 時間序列數據挖掘中的維數約簡與預測方法研究[D].合肥：中國科學技術大學,2014.

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

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

2217-2220.

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

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

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

[9] 中華人民共和國水利部. SL195-2015， 中華人民共和國水利行業標準[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-），女，河海大學，碩士研究生，研究方向：數據挖掘，南京 211100

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

周曉峰（1965-），男，河海大學，教授，研究方向：數據挖掘，南京 211100