基于MapReduce的時序數據離群點挖掘算法

劉 峰，延婉梅，李洪人

（1.北京交通大學 計算機與信息技術學院，北京 100044；2.朔黃鐵路發展有限公司 原平分公司，忻州 034100）

基于MapReduce的時序數據離群點挖掘算法

劉 峰1，延婉梅1，李洪人2

（1.北京交通大學 計算機與信息技術學院，北京 100044；2.朔黃鐵路發展有限公司 原平分公司，忻州 034100）

針對海量數據中離群點的挖掘，將網格聚類和MapReduce編程模型相結合，排除不可能包含離群點的網格，再用LOF算法對剩余網格中的數據進行離群點檢測。為了提高網格聚類的檢測精度，本文提出了一種基于聚類半徑的改進算法。實驗表明了該算法的有效性，同時分析了在節點數不同的情況下，網格聚類所用時間，證明了基于MapReduce的網格聚類適合處理海量時序數據。

海量時序數據；網格聚類；MapReduce；LOF；聚類半徑

多變量時間序列（MTS）在各個領域中是非常普遍的，比如動車組數據。動車組在運行過程中接收到的閘片數據可以用多個變量的MTS描述，MTS矩陣通常用m?n矩陣來表示，其中m是記錄的個數，n是屬性的個數。

在分析時間序列時，經常會發現一些特殊的數據或數據段，它們的波動顯著不同，這種極少出現的數據點或者數據段就稱為異常點[1]。異常點的出現嚴重影響了數據利用的效率和決策質量，同時，時序數據中的離群數據使人們能夠發現一些潛在有用的知識，如動車運行中環境因素對閘片的影響。

目前異常檢測方法主要包括以下幾種[2]：基于統計的孤立點檢測方法；基于距離的孤立點檢測方法；基于密度的孤立點檢測方法；基于聚類的方法[3]。

針對單變量時間序列，基于離群指數[4]和基于小波變換[5]的異常數據的挖掘方法得到了應用。針對多變量時間序列，有學者提出了基于滑動窗口[6]和基于局部線性映射[7]的異常數據診斷方法。然而，隨著各種數據的急速增長，目前，對如何從海量的多變量時間序列中挖掘出異常數據這方面的研究很少。

本文在此基礎上對時序數據的異常值進行檢測，將MapReduce與網格聚類相結合，利用基于網格的聚類對數據進行劃分，有助于快速發現可能的離群點，快速找到可能離群點的k-近鄰。同時對基于網格的聚類進行改進，提高檢測精度。最后以動車組閘片數據驗證了算法的有效性和合理性。

1 MapReduce簡介

MapReduce編程模型的原理是[8]：利用一個輸入key/value對集合來產生一個輸出的key/value對集合。用戶可以用兩個函數表達這一計算：Map（映射）和Reduce（規約）函數。MapReduce將大數據集分解為成百上千的小數據集，每個（或若干個）數據集分別由集群中的1個節點并行執行Map計算任務，并生成中間結果，然后這些中間結果又由大量的節點并行執行Reduce計算任務，形成最終結果。

為了適合MapReduce計算模型，數據記錄都是以行形式存儲的。將網格聚類和MapReduce編程模型相結合，程序可以在Map階段讀入網格劃分數據，然后并行處理每行數據，各個節點分別進行計算，能夠提高效率。

2 網格聚類

基于離群指數的離群點檢測中，算法的時間復雜度主要集中在查找一個點的k個鄰居，同時，當數據海量時，頻繁地遍歷數據集合會消耗很多的時間，因此，很可能會出現機器內存不足，不能完成任務的情況。所以，本文引入網格聚類的方法?；诰W格劃分的離群點檢測方法是離群點挖掘的一種非常重要技術，該方法的核心思想：先將數據空間的每一維進行劃分，原數據空間被分割成彼此不相交的網格單元，距離較近的點歸屬于同一個網格的可能性比較大，快速地查找一個點的k個鄰居。同時，由于離群點的數目只占整個數據集的一小部分，因此在計算LOF 值之前，把不可能成為離群點的點集提前刪除，然后對剩下的點集作進一步檢測，選出符合條件的點作為結果[9]。該算法的優點是：采用聚類方法把非離群點集篩選出來刪除掉，再對剩下的可能成為離群點的點集做進一步考察，減少了不必要的計算，節省了算法的運行時間。

2.1 網格密度定義

在網格數據結構中，由一般的方法是指定一個數值δ于每個網格單元都有相同的體積，因此網格單元中數據點密度的計算可以轉換成簡單的數據點個數，即落到某個單元中點的個數當成這個單元的密度[9]。一般的方法是指定一個數值δ，當某網格單元中點的個數大于該數值時，就說這個單元是密集的。

2.2 網格的劃分

在基于網格劃分的聚類分析與離群點檢查中，如何確定網格單元格劃分的方法是問題的關鍵。最常用也是最簡單的一種劃分方法是將每個維度做等距離劃分。例如，在對d維數據空間進行網格劃分時，每一維度的距離為k，劃分后所得到的網格單元數為。

2.3 相鄰網格單元定義

該定義表明，兩個網格相鄰當且僅當這兩個網格單元有一個公共的邊或面。

2.4 網格編號

對網格編號：首先保證d維屬性的順序固定A1，A2，…，Ad，對于其中的每個屬性Ai（1≤i≤d），將其均分為s個間隔段，按照范圍從小到大編號為1，2，…，s。那么一個網格的編號即為Ai（1≤i≤d）中范圍編號的集合。之所以這樣定義網格編號，是為了方便查找一個網格的鄰居網格，假設一個網格的編號為那么一個網格的鄰居網格編號為

3 Mapreduce實現網格聚類

3.1 Map函數與Reduce函數的基本思想

Map函數的任務是判斷每條記錄屬于哪個網格，網格的劃分都是提前定義好的，生成的網格范圍存儲到hashMap中。那么，hashMap的key值為當前網格的編號gridNumber，value值為網格范圍rangeneighbor。Map函數的輸入是各條記錄數據，輸出為各個記錄所屬的網格編號。偽代碼如下：

HashMap(gridNumber,range);//網格范圍都存儲在HashMap中

For each data p//對數據集中的每條記錄p

For each gridNumber //循環遍歷每一個網格的范圍

compare(p, range);//比較p和每個網格的范圍

Reduce函數的任務是篩選出網格密度最小的n個網格，偽代碼如下。

sum+=1;//計算每個網格中的數據個數

hashMap1.add(gridNumber,sum);//將計算后的數值存儲到hashMap1中

sort();//根據sum值升序排列

Iterator iter = map.entrySet().iterator();

for i from 0 to n-1//循環遍歷hashMap它的前n個數，即為網格密度最小的n個網格

上述過程是一般的網格聚類方法，但是網格的劃分與劃分間隔大小的選擇直接影響著算法的正確性與算法的執行效率。如果間隔 w 選擇過大，則會導致一個含有離群點的網格單元的相鄰單元都不為空，該單元作為非邊界網格單元被刪除，其離群點不能被檢測到，從而引起有用數據的丟失；如果 w選擇過小，網格單元的計算量會大大增加；可能導致比較稀疏的聚類點不容易被檢測到，這樣就會增加后面 LOF 的計算工作。因此，合理地劃分每一維是算法的關鍵所在，也是本文的研究重點。

同時，利用網格中數據點的個數作為網格密度的標準是不嚴謹的，如果一個網格中數據點分布的較為集中，不管數據點的個數是多少，這些數據是離群點的可能性都較小。相反，如果一個網格中數據點的個數較多，但是數據分布的特別分散，那么這些數據點是離群點的可能性也是較大的。

3.2 基于聚類半徑的改進算法

本文提出一種改進方法，可以減小網格劃分的影響，對于每個網格內的數據密度，不單純使用數據個數的方法，而是通過網格質心與網格內最遠點的距離來衡量，即聚類半徑。規定網格質點為所有數據點的平均值。直觀的想法是聚類半徑大的數據分布的較為稀疏，聚類半徑小的數據分布的較為密集。

那么在Map階段，輸出的value值不能只是計數的，因為在reduce階段求質心時需要數據值，相應的Map階段的偽代碼為：

HashMap(gridNumber,range);//網格范圍都存儲在HashMap中

For each data p//對數據集中的每條記錄p

For each gridNumber //循環遍歷每一個網格的范圍

compare(p, range);//比較p和每個網格的范圍

sum+=1;//統計數據點個數

sumValue+=value;//統計一個網格內所有記錄的數據和

average=sumValue/sum;//求質心

context.write(gridNumber,p);//給每條記錄標記所屬網格，便于刪除不可能成為離群點的點集

for each gridNumber //第2次遍歷

Max = distince(p,average);//計算每個點和質心的距離,即簇半徑，每次只保留最大值

hashMap1.add(gridNumber,Max); //將計算后的數值存儲到hashMap中

sort();//根據sum值升序排列

Iterator it = map.entrySet().iterator();

while(it.hasNext()){

for i from 0 to n-1//循環遍歷hashMap,取出值最大的n個數

print hashMap.getKey();//將這些網格編號輸出

4 LOF算法的應用

為了降低LOF的時間復雜度，設定Nk(p)為點p的k–近鄰點，則定義點p的k–近鄰分布密度為[4]：

則p的局部離群點因子（LOF）為：

在用LOF算法進行離群點檢測的時候，只需要簇半徑最大的n個網格中的數據和它的鄰居網格中的數據，其它編號的網格數據就可以刪除了，此時，大數據集已經大大減少了。

5 驗證

實驗中總共使用10臺機器來搭建云計算環境，其中一個是主節點（master），用來管理其它的節點，其它9臺作為工作節點（slave），用來運行MapReduce任務。實驗數據是國內某公司2013年動車組運行的所有閘片數據。

閘片數據說明如表1所示。

表1 閘片數據說明

實驗1：為了證實網格聚類算法改進的有效性，選取2 GB動車組閘片數據，每條數據由6個屬性組成，每維數據分別均分為2，5，10，12個等長的間隔，選取9個節點參與計算，實驗結果如圖1所示。

圖1 改進前后結果對比

實驗結果表明：算法改進前，網格聚類的準確率變化很大，說明網格劃分對正確率影響較大，并且聚類結果不甚理想。算法改進后，不管網格如何劃分，聚類正確率都保持在一個較高并且平穩的狀態。說明算法改進是有效的。

實驗2：比較在Hadoop分布式運行環境下，數據量和節點數不同時，程序運行時間。實驗分別采用3組數據集，數據大小分別為5 GB，10 GB，15 GB，每條記錄由22維數據值的數據組成，除速度和總里程外，其它數據都是以十六進制形式存儲的。每維數據均分為5個等長的間隔，分別選擇1, 3, 5, 7, 9個節點參與計算，實驗考察在逐漸增加節點的情況下，網格聚類算法的執行效率。

網格聚類過程中對記錄標識網格編號，生成結果如圖2所示 。

圖2 網格聚類實驗結果

執行時間如圖3所示。

從實驗中可以看出每個作業的執行時間隨著節點數的增加而降低。由此證明，增加節點數可以顯著提高系統對同規模數據的處理能力。

圖3 網格聚類時間

6 結束語

本文旨在利用基于離群點因子的離群點檢測算法LOF來查找多維海量時序數據中的離群點，在MapReduce基礎上利用網格聚類減小數據集，能夠有效減小LOF算法的時間復雜度。實驗證明了提高網格聚類檢測精度所做的改進是有效的。

[1] 劉明華，張晉昕.時間序列的異常點診斷方法[J]. 中國衛生統計，2011，28（4）：478-481.

[2] 郭逸重. 一種基于孤立點挖掘的Hadoop數據清洗算法的研究[D]. 廣州：華南理工大學, 2012.

[3] 楊正寬.基于距離的離群挖掘算法研究[D]. 重慶：重慶大學，2011.

[4] 鄭斌祥，席裕庚，杜秀華．基于離群指數的時序數據離群挖掘[J]．自動化學報，2004，30（1）：70-77．

[5] 文 琪，彭 宏．小波變換的離群時序數據挖掘分析[J]．電子科技大學學報，2005，34（4）：556-558．

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

[7] 杜洪波，張 穎．基于LLM的時間序列異常子序列檢測算法[J]．沈陽工業大學學報，2009，31（3）：328-332．

[8]江小平，李成華，向 文，等.k-means聚類算法的Map-Reduce 并行化實現[J].華中科技大學學報（自然科學版），2011，39 （增刊I）：120-124.

[9] 曹洪其, 余 嵐, 孫志揮. 基于網格聚類技術的離群點挖掘算法[J]. 計算機工程，2006，32（11）：119-122.

[10] 張天佑. 基于網格劃分的高維大數據集離群點檢測算法研究[D].長沙：中南大學，2011.

責任編輯 陳 蓉

Outlier Mining Algorithm for time series data based on MapReduce

LIU Feng1, YAN Wanmei1, LI Hongren2
( 1.School of Computer and Information Technology, Beijing Jiaotong University, Beijing 100044, China; 2. Yuanping Brach, Shuo Huang Railway Development Company Limited, Xinzhou 034100, China )

Aiming at outlier mining in massive time series data, the paper combined grid clustering with MapReduce programming model to exclude grids that was impossible to contain outlier, and then used LOF Algorithm to detect outliers from the rest grids. In order to improve the detection accuracy of the grid clustering, this paper proposed an improved algorithm based on clustering radius. Experimental results showed the effectiveness of the improvement. Experiment also analyzed the execution time grid cluster cost under the circumstances with different number of nodes, which proved it was suitable for handling massive time series data combined MapReduce with grid clustering.

massive time series data; grid clustering; MapReduce; LOF; clustering radius

U266.2∶TP39

A

1005-8451（2015）04-0001-05

2014-09-23

劉 峰，教授；延婉梅，在讀碩士研究生。