劉 峰，延婉梅，李洪人

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

基于MapReduce的時序數(shù)據(jù)離群點挖掘算法

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

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

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

海量時序數(shù)據(jù)；網(wǎng)格聚類；MapReduce；LOF；聚類半徑

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

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

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

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

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

1 MapReduce簡介

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

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

2 網(wǎng)格聚類

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

2.1 網(wǎng)格密度定義

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

2.2 網(wǎng)格的劃分

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

2.3 相鄰網(wǎng)格單元定義

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

2.4 網(wǎng)格編號

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

3 Mapreduce實現(xiàn)網(wǎng)格聚類

3.1 Map函數(shù)與Reduce函數(shù)的基本思想

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

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

For each data p//對數(shù)據(jù)集中的每條記錄p

For each gridNumber //循環(huán)遍歷每一個網(wǎng)格的范圍

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

Reduce函數(shù)的任務(wù)是篩選出網(wǎng)格密度最小的n個網(wǎng)格，偽代碼如下。

sum+=1;//計算每個網(wǎng)格中的數(shù)據(jù)個數(shù)

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

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

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

for i from 0 to n-1//循環(huán)遍歷hashMap它的前n個數(shù)，即為網(wǎng)格密度最小的n個網(wǎng)格

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

同時，利用網(wǎng)格中數(shù)據(jù)點的個數(shù)作為網(wǎng)格密度的標準是不嚴謹?shù)模绻粋€網(wǎng)格中數(shù)據(jù)點分布的較為集中，不管數(shù)據(jù)點的個數(shù)是多少，這些數(shù)據(jù)是離群點的可能性都較小。相反，如果一個網(wǎng)格中數(shù)據(jù)點的個數(shù)較多，但是數(shù)據(jù)分布的特別分散，那么這些數(shù)據(jù)點是離群點的可能性也是較大的。

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

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

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

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

For each data p//對數(shù)據(jù)集中的每條記錄p

For each gridNumber //循環(huán)遍歷每一個網(wǎng)格的范圍

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

sum+=1;//統(tǒng)計數(shù)據(jù)點個數(shù)

sumValue+=value;//統(tǒng)計一個網(wǎng)格內(nèi)所有記錄的數(shù)據(jù)和

average=sumValue/sum;//求質(zhì)心

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

for each gridNumber //第2次遍歷

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

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

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

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

while(it.hasNext()){

for i from 0 to n-1//循環(huán)遍歷hashMap,取出值最大的n個數(shù)

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

4 LOF算法的應用

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

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

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

5 驗證

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

閘片數(shù)據(jù)說明如表1所示。

表1 閘片數(shù)據(jù)說明

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

圖1 改進前后結(jié)果對比

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

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

網(wǎng)格聚類過程中對記錄標識網(wǎng)格編號，生成結(jié)果如圖2所示 。

圖2 網(wǎng)格聚類實驗結(jié)果

執(zhí)行時間如圖3所示。

從實驗中可以看出每個作業(yè)的執(zhí)行時間隨著節(jié)點數(shù)的增加而降低。由此證明，增加節(jié)點數(shù)可以顯著提高系統(tǒng)對同規(guī)模數(shù)據(jù)的處理能力。

圖3 網(wǎng)格聚類時間

6 結(jié)束語

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

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

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

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

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

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

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

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

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

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

[10] 張?zhí)煊? 基于網(wǎng)格劃分的高維大數(shù)據(jù)集離群點檢測算法研究[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

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