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

劉 峰，延婉梅，李洪人

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

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

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

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

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

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

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

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

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

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

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

1 MapReduce簡(jiǎn)介

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

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

2 網(wǎng)格聚類

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

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

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

2.2 網(wǎng)格的劃分

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

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

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

2.4 網(wǎng)格編號(hào)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

同時(shí)，利用網(wǎng)格中數(shù)據(jù)點(diǎn)的個(gè)數(shù)作為網(wǎng)格密度的標(biāo)準(zhǔn)是不嚴(yán)謹(jǐn)?shù)?，如果一個(gè)網(wǎng)格中數(shù)據(jù)點(diǎn)分布的較為集中，不管數(shù)據(jù)點(diǎn)的個(gè)數(shù)是多少，這些數(shù)據(jù)是離群點(diǎn)的可能性都較小。相反，如果一個(gè)網(wǎng)格中數(shù)據(jù)點(diǎn)的個(gè)數(shù)較多，但是數(shù)據(jù)分布的特別分散，那么這些數(shù)據(jù)點(diǎn)是離群點(diǎn)的可能性也是較大的。

3.2 基于聚類半徑的改進(jìn)算法

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

那么在Map階段，輸出的value值不能只是計(jì)數(shù)的，因?yàn)樵趓educe階段求質(zhì)心時(shí)需要數(shù)據(jù)值，相應(yīng)的Map階段的偽代碼為：

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

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

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

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

sum+=1;//統(tǒng)計(jì)數(shù)據(jù)點(diǎn)個(gè)數(shù)

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

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

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

for each gridNumber //第2次遍歷

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

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

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

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

while(it.hasNext()){

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

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

4 LOF算法的應(yīng)用

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

則p的局部離群點(diǎn)因子（LOF）為：

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

5 驗(yàn)證

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

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

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

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

圖1 改進(jìn)前后結(jié)果對(duì)比

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

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

網(wǎng)格聚類過(guò)程中對(duì)記錄標(biāo)識(shí)網(wǎng)格編號(hào)，生成結(jié)果如圖2所示 。

圖2 網(wǎng)格聚類實(shí)驗(yàn)結(jié)果

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

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

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

6 結(jié)束語(yǔ)

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

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

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

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

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

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

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

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

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

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

[10] 張?zhí)煊? 基于網(wǎng)格劃分的高維大數(shù)據(jù)集離群點(diǎn)檢測(cè)算法研究[D].長(zhǎng)沙：中南大學(xué)，2011.

責(zé)任編輯 陳 蓉

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

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