基于MapReduce與距離的離群數(shù)據(jù)并行挖掘算法①

任 燕

(山西省特殊教育中等專業(yè)學(xué)校,太原 030012)

1 引言

離群數(shù)據(jù)(Outlier)是數(shù)據(jù)集中不滿足數(shù)據(jù)的一般行為或模式,明顯偏離其他數(shù)據(jù)對象的數(shù)據(jù)[1].通常情況下,離群數(shù)據(jù)容易被忽視,但其可能蘊含大量非常有價值的信息.離群數(shù)據(jù)挖掘是數(shù)據(jù)挖掘的一項重要任務(wù),其目標(biāo)是尋找數(shù)據(jù)集中,行為或模式很大程度上不同于其他數(shù)據(jù)對象的數(shù)據(jù).目前,離群數(shù)據(jù)挖掘已廣泛應(yīng)用于信用卡詐騙檢測[2],網(wǎng)絡(luò)入侵檢測[3,4],圖像匹配[5],數(shù)據(jù)清洗[6]以及醫(yī)療診斷等領(lǐng)域.

現(xiàn)有的離群數(shù)據(jù)挖掘方法大致分為四類:基于統(tǒng)計分布的方法[7,8],基于距離的方法[9-11],基于密度的局部離群點方法[12,13]以及基于偏差的方法[14].這些方法針對不同類型的數(shù)據(jù)集可以進行較為有效的數(shù)據(jù)挖掘.經(jīng)過多年的探索和研究,離群數(shù)據(jù)挖掘雖然已有較快發(fā)展,但是當(dāng)處理海量高維數(shù)據(jù)時,仍然會出現(xiàn)算法的時空復(fù)雜度太高,效率低下等問題,無法滿足當(dāng)今社會的需求.因此,尋找一種準(zhǔn)確高效的離群數(shù)據(jù)挖掘方法顯得尤為重要.

基于距離的離群數(shù)據(jù)挖掘算法是一種有效的數(shù)據(jù)挖掘方法,最早由Knorr與Ng提出[9],其主要思路是將離群數(shù)據(jù)定義為與數(shù)據(jù)集中大多數(shù)數(shù)據(jù)之間的距離大于某個閾值的數(shù)據(jù).在此定義中,距離閾值要預(yù)先進行設(shè)定,而對于不同的數(shù)據(jù)集而言,距離閾值可能不同,所以如果要挖掘離群數(shù)據(jù)就必須對數(shù)據(jù)集有一定的了解.針對其不足,Ramaswamy與Kyuseok等人提出了一種在大數(shù)據(jù)集下挖掘離群數(shù)據(jù)的方法[15],即KNN算法.將離群數(shù)據(jù)定義為前n個與其k個最近鄰居的距離和最大的數(shù)據(jù),從而避免了基于距離的離群數(shù)據(jù)挖掘算法需要用戶設(shè)定距離閾值的局限.文獻[16]提出一種基于距離的離群數(shù)據(jù)挖掘算法,不僅可以有效挖掘離群數(shù)據(jù),并且可以通過“解集”來預(yù)測新加入的數(shù)據(jù)是否為離群數(shù)據(jù).但是此算法需要計算所有數(shù)據(jù)之間的歐氏距離,使得算法在高維、大數(shù)據(jù)集上的運行效率較低.隨著并行與分布式計算技術(shù)的發(fā)展,Angiulli等人[17]在文獻[16]的基礎(chǔ)上提出一種基于MPI編程模型的離群數(shù)據(jù)并行挖掘算法.但是由于MPI編程模型較為復(fù)雜,可靠性較差,并且會產(chǎn)生通信延遲和負(fù)載不均衡等問題,因此本文選擇可靠性較強,效率較高的 MapReduce編程模型,在Hadoop平臺下,實現(xiàn)了一種基于MapReduce與距離的離群數(shù)據(jù)并行挖掘算法,在保證算法準(zhǔn)確性的前提下,有效提高了數(shù)據(jù)處理的效率.

2 離群數(shù)據(jù)與MapReduce編程模型

2.1 基本定義與概念

假設(shè)數(shù)據(jù)集D是給定度量空間的有限子集,相關(guān)概念定義如下:

定義1 (離群權(quán)值).對于任意給定的一個數(shù)據(jù)對象p∈D,D中p的權(quán)值wk(p,D)是p到它的k個最近鄰的距離之和.

定義2 (TOPn離群數(shù)據(jù)).假設(shè)T為數(shù)據(jù)集D中具有n個數(shù)據(jù)對象的一個子集.如果不存在對象x∈T、y∈(DT),使得 (y,D)>(x,D),那么,子集T就稱作數(shù)據(jù)集D中前n個離群值集合.在此基礎(chǔ)上,權(quán)值為w*=minx∈T wk(x,D)的數(shù)據(jù)為離群程度最大的前n個離群數(shù)據(jù)中的第n個離群數(shù)據(jù),在子集T中的數(shù)據(jù)為數(shù)據(jù)集D中前n個離群值.

定義3 (離群數(shù)據(jù)檢測解集).離群數(shù)據(jù)檢測解集S是數(shù)據(jù)集D中一個子集,對于每一個數(shù)據(jù)對象y∈DS,使得wk(y,S)≤w*,這里的w*第n個離群數(shù)據(jù)的權(quán)值.

我們注意到解集S總是包含在數(shù)據(jù)集D中的包含topn離群數(shù)據(jù)的集合T,并且,它具有預(yù)測離群數(shù)據(jù)的性質(zhì).

2.2 “解集”算法實現(xiàn)

[16],算法實現(xiàn)大致如下:首先,從數(shù)據(jù)集D中隨機選取一個候選集Cj,將候選集Cj中每個數(shù)據(jù)對象與數(shù)據(jù)集中所有的數(shù)據(jù)對象進行比較,存儲Cj中每個數(shù)據(jù)對象的最近鄰.然后對Cj中每個數(shù)據(jù)對象的最近鄰進行排序,求得Cj中每個數(shù)據(jù)對象的權(quán)值.在Cj中,比第n個最大權(quán)值小的候選集對象不可能屬于topn個離群數(shù)據(jù),被稱為不靈活對象,而剩余的對象就被稱為靈活對象.最初,C1子集包含從數(shù)據(jù)集D中隨機選取的對象,之后的C2,C3,…,Cj-1子集是由在之前的計算中沒有插入到C1,…,Cj中的數(shù)據(jù)集中的靈活對象組成.如果一個對象變成了不靈活對象,便不會是離群數(shù)據(jù),那么在之后的計算中,就不會被插入到以后的候選集.隨著算法產(chǎn)生新的對象,更多準(zhǔn)確的權(quán)值會被計算出來,不靈活對象的數(shù)量會增加.當(dāng)所有的數(shù)據(jù)對象被檢測完畢,即候選集中對象全為不靈活對象時,Cj變?yōu)榭?算法結(jié)束.解集就是在每次循環(huán)中計算出來的子集Cj的并集.

算法描述如下:

2.3 MapReduce框架

MapReduce 是一個編程模型,也是一個處理和生成超大數(shù)據(jù)集的算法模型的相關(guān)實現(xiàn)[18,19].用戶首先創(chuàng)建一個Map函數(shù)處理一個基于key/value pair的數(shù)據(jù)集合,輸出中間的基于 key/value pair 的數(shù)據(jù)集合;然后再創(chuàng)建一個Reduce函數(shù)用來合并所有的具有相同key值的value值.MapReduce是基于數(shù)據(jù)劃分的角度來構(gòu)建并行計算模型的,能夠在大量的普通配置的計算機上實現(xiàn)數(shù)據(jù)的并行化處理.這個系統(tǒng)在運行時只關(guān)心:如何分割輸入數(shù)據(jù),在大量計算機組成的集群上的調(diào)度,集群中計算機的錯誤處理,管理集群中計算機之間必要的通信.采用MapReduce架構(gòu)可以使沒有并行計算和分布式處理系統(tǒng)開發(fā)經(jīng)驗的程序員有效利用分布式系統(tǒng)的豐富資源.MapReduce框架可以運行在規(guī)?？梢造`活調(diào)整的由普通機器組成的集群上:一個典型的 MapReduce 計算往往由幾千臺機器組成、處理以TB計算的數(shù)據(jù).在Google的集群上,每天都有1000多個MapReduce 程序在執(zhí)行.

MapReduce 編程模型的原理如圖1所示.

圖1 MapReduce 編程模型的原理

3 基于MapReduce的離群數(shù)據(jù)并行挖掘

3.1 “解集”算法的并行化

假設(shè)集群中有1個主節(jié)點N0和l個從節(jié)點N1,…,Ni,…,Nl,數(shù)據(jù)集D被分成l個局部數(shù)據(jù)集D1,…,Di,…,Dl,每個局部數(shù)據(jù)集被分配到一個從節(jié)點上,目標(biāo)是計算解集S和包含topn離群數(shù)據(jù)的集合T.

主節(jié)點主要調(diào)度以下兩項任務(wù):

1)分配任務(wù)到各個從節(jié)點,使其同時進行核心操作運算.

2)整合處理每個從節(jié)點完成運算后返回結(jié)果.

主節(jié)點同步處理從節(jié)點數(shù)據(jù),并對從節(jié)點返回結(jié)果進行整合,來產(chǎn)生新的全局候選節(jié)點集,這些候選集被用于接下來的迭代,也用于產(chǎn)生它們每一個最近鄰距離的真實列表(順序),用來計算新的下界.

從節(jié)點的主要運算包含以下步驟:

(1)接收當(dāng)前候選集中的數(shù)據(jù)對象及前n個離群數(shù)據(jù)的下界,并將下界作為w*.

(2)將候選集中數(shù)據(jù)對象與本地數(shù)據(jù)對象進行比較.

(3)求得新的本地候選對象和關(guān)于解集的本地最近鄰的數(shù)據(jù)對象列表.

(4)最后確定本地靈活對象的數(shù)目,向主節(jié)點提交結(jié)果.

在局部數(shù)據(jù)集Di中,用k最近鄰來計算候選集中每個數(shù)據(jù)對象的權(quán)值,找前n個離群數(shù)據(jù),輸出解集DSS和在數(shù)據(jù)集D中包含topn離群數(shù)據(jù)的集合OUT.在算法執(zhí)行的開始時,DSS和OUT被初始化為空集,候選集C被初始化為從數(shù)據(jù)集D中隨機選取的m個對象,當(dāng)候選集C變?yōu)榭諘r結(jié)束主循環(huán).此刻屬于候選集C的數(shù)據(jù)點被添加到集合DSS.在每個循環(huán)開始時,候選集C被傳遞給運行在每個節(jié)點上的NodeComp比較程序,最后由主節(jié)點匯總計算結(jié)果.

3.2 MapReduce編程模型下的“分布式解集”算法實現(xiàn)

為了將該并行算法映射到MapReduce編程模型中,本文將定義兩個Map函數(shù)和兩個Reduce函數(shù).在前一個Map函數(shù)中,將局部數(shù)據(jù)集Di中候選集Ci中的對象p(object)作為Key值,計算p與候選集中所有對象q1,q2,q3,…,ql的歐式距離dist(q1),dist(q2),dist(q3),…,dist(ql),以鍵值對的形式輸出結(jié)果,即:Map,Map,Map,…,Map.當(dāng) dist小于距離數(shù)組的最大值時,更新每個對象的距離數(shù)組.Reduce函數(shù)將Map函數(shù)輸出的鍵值對進行整理(shuffle)和按鍵分組,將p與候選集中對象的距離dist(q1),dist(q2),dist(q3),…,dist(ql)進行降序排序,并篩選前k個距離.再通過Map函數(shù)計算p對應(yīng)的前k個數(shù)據(jù)對象的距離和sum(p),即p權(quán)值,將Map函數(shù)形式的輸出作為Reduce函數(shù)的輸入,最后通過Reduce函數(shù)將數(shù)據(jù)對象的p權(quán)值作為Key值,p作為Value值,并將Key值降序排序,求得前n個離群數(shù)據(jù).具體實現(xiàn)如圖2所示.

圖2 算法在MapReduce編程模型下實現(xiàn)

4 實驗結(jié)果及分析

實驗環(huán)境:偽分布環(huán)境為,1臺Dell筆記本(Core i7 CPU,8 G內(nèi)存);全分布環(huán)境為,由10臺相同性能節(jié)點構(gòu)成的集群(Intel Core i7- 820M CPU,16 G內(nèi)存)操作系統(tǒng)為ubuntu Linux 12.04;實驗平臺:Jdk 1.6.0_37,Hadoop1.1.1,Eclipse.采用 Java語言作為開發(fā)工具.分別在MPI和MapReduce并行環(huán)境下實現(xiàn)了該算法.

實驗數(shù)據(jù)集:1)人工數(shù)據(jù)集:參照文獻[10]中的方式,分別生成了50、100、150和200維的30 000條、60 000條、90 000條和120 000條,共16組人工數(shù)據(jù)集.在每一組人工數(shù)據(jù)集中,包含有30條離群數(shù)據(jù).2)UCI 數(shù)據(jù)庫中Wholesale customers data數(shù)據(jù)集.

4.1 人工數(shù)據(jù)集

選取參數(shù)如下:KNN中K=10,節(jié)點個數(shù)N=6,數(shù)據(jù)量D=30000條,在MapReduce框架下,實驗分析數(shù)據(jù)維度對挖掘性能的影響.如圖3所示.

當(dāng)數(shù)據(jù)集的數(shù)量不變時,隨著數(shù)據(jù)維度的增加,其挖掘效率降低,其主要原因是:隨著數(shù)據(jù)集維度的增加,在進行KNN距離比較的時候計算復(fù)雜度略高于線性,相應(yīng)的挖掘效率要降低.

圖3 數(shù)據(jù)維度對算法性能的影響

選取參數(shù)如下:KNN中K=10,數(shù)據(jù)量D=30000條,數(shù)據(jù)維度d=100,在MapReduce框架下,實驗分析節(jié)點對挖掘性能的影響.如圖4所示.

圖4 節(jié)點個數(shù)對性能的影響

當(dāng)數(shù)據(jù)量一定時,隨著集群計算結(jié)點個數(shù)的增加,算法的挖掘耗時基本按計算結(jié)點比例減小,體現(xiàn)了算法具有較好的并行程度.其主要原因是:首先候選集中各個數(shù)據(jù)對象與本地數(shù)據(jù)對象進行比較計算過程完全可以并行化,各計算結(jié)點的數(shù)據(jù)對象個數(shù),可以按計算結(jié)點比例分配.

選取參數(shù)如下:KNN中K=10,節(jié)點個數(shù)N=6,維度d=100,分別在MPI和MapReduce框架下,實驗分析兩種編程模型在不同數(shù)據(jù)量的情況下對挖掘性能的影響.如圖5所示.

當(dāng)計算節(jié)點不變時,隨數(shù)據(jù)量的增加,其挖掘效率降低,其主要原因是:隨數(shù)據(jù)量的增加,數(shù)據(jù)對象的個數(shù)增多,各節(jié)點上分配的對象個數(shù)基本按計算節(jié)點比例線性增加;每個對象對應(yīng)的KNN查詢的時間也隨之增加.總之,隨著數(shù)據(jù)量的增加,其挖掘效率曲線的傾斜程度要略高于線性.從圖中看出,MapReduce編程模型比MPI編程模型效率高,主要原因是MapReduce比MPI容錯能力強,并且負(fù)載均衡策略更為合理.

圖5 兩種編程模型在不同數(shù)據(jù)量的情況下對挖掘性能的影響

4.2 UCI數(shù)據(jù)集

Wholesale customers data數(shù)據(jù)集,分別在偽分布環(huán)境的MapReduce編程模型和MPI編程模型下,實驗分析k值對挖掘精度的影響.

由圖6可以看出,k值對兩種編程模型的影響幾乎相同.當(dāng)k值較小時,算法挖掘準(zhǔn)確率較低,當(dāng)k值增大到一定值時,挖掘準(zhǔn)確率會上升到一個比較高的值,大約80%,主要原因是當(dāng)k值增大到一定值時,候選集中數(shù)據(jù)對象的最近鄰已經(jīng)能夠較好地體現(xiàn)數(shù)據(jù)的疏密特征或分布趨勢,隨著k繼續(xù)增大,由KNN得到的離群數(shù)據(jù)可能會出現(xiàn)較小誤差.

圖6 兩種編程模型的k值對挖掘精度的影響

選取UCI數(shù)據(jù)集中DOCC (Default of Credit Card Clients)數(shù)據(jù)集,WCD (Wholesale Customers Data)數(shù)據(jù)集,ad數(shù)據(jù)集和adult數(shù)據(jù)集,分別在MapReduce和MPI兩種編程模型下,實驗分析兩種編程模型對數(shù)據(jù)挖掘性能的影響.實驗結(jié)果如圖7所示.

圖7 兩種編程模型性能比較

由圖中可以看出,在4個不同的UCI數(shù)據(jù)集下,MapReduce編程模型均比MPI編程模型的效率高,且數(shù)據(jù)量越大,MapReduce優(yōu)勢越明顯.因為MapReduce隱藏了并簡化了并行計算的細(xì)節(jié),還提拱了備份冗余,本地優(yōu)化以及負(fù)載均衡的機制.

5 結(jié)束語

數(shù)據(jù)的并行與分布式處理逐漸被用于數(shù)據(jù)挖掘領(lǐng)域.而MapReduce框架大大降低了編程的復(fù)雜性,提高了編程的效率,可以有效避免MPI編程模型的不足之處.本文基于MapReduce與距離,實現(xiàn)了一種離群數(shù)據(jù)并行挖掘算法,提高了離群數(shù)據(jù)挖掘的效率,并且使用人工數(shù)據(jù)集和UCI數(shù)據(jù)集,實驗驗證了算法在不同條件下,參數(shù)對性能的影響.

參考文獻

1Knorr EM,Ng RT.Algorithms for mining distance-based outliers in large datasets.Proceedings of the 24th International Conference on Very Large Data Bases.San Francisco,CA,USA.1998.392-403.

2Aggarwal CC.Outlier analysis.Aggarwal CC.Data Mining.Cham:Springer,2015:237-263.

3Hubert M,Rousseeuw PJ,Segaert P.Multivariate functional outlier detection.Statistical Methods &Applications,2015,24(2):177-202.

4Lu W,Shen YY,Chen S,et al.Efficient processing of k nearest neighbor joins using MapReduce.Proceedings of the VLDB Endowment,2012,5(10):1016-1027.[doi:10.14778/2336664]

5Zhao HF,Jiang B,Tang J,et al.Image matching using a local distribution based outlier detection technique.Neurocomputing,2015,148:611-618.[doi:10.1016/j.neucom.2014.07.002]

6Roth V.Kernel fisher discriminants for outlier detection.Neural Computation,2006,18(4):942-960.[doi:10.1162/neco.2006.18.4.942]

7Radovanovi? M,Nanopoulos A,Ivanovi? M.Reverse nearest neighbors in unsupervised distance-based outlier detection.IEEE Transactions on Knowledge and Data Engineering,2015,27(5):1369-1382.[doi:10.1109/TKDE.2014.236 5790]

8Li Y,Nitinawarat S,Veeravalli VV.Universal outlier hypothesis testing.IEEE Transactions on Information Theory,2014,60(7):4066-4082.[doi:10.1109/TIT.2014.2317691]

9Marghny M H,Taloba AI.Outlier detection using improved genetic K-means.International Journal of Computer Applications,2011,28(11):33-36.[doi:10.5120/ijca]

10Kriegel HP,Kr?ger P,Schubert E,et al.Outlier detection in arbitrarily oriented subspaces.Proceedings of the 12th International Conference on Data Mining.Brussels,Belgium.2012.379-388.

11Bhattacharya G,Ghosh K,Chowdhury AS.Outlier detection using neighborhood rank difference.Pattern Recognition Letters,2015,(60-61):24-31.

12Breunig MM,Kriegel HP,Ng RT,et al.LOF:Identifying density-based local outliers.Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data.Dallas,TX,USA.2000.93-104.

13Murugavel P,Punithavalli M.Performance evaluation of density-based outlier detection on high dimensional data.International Journal on Computer Science and Engineering,2013,5(2):62-67.

14Sarawagi S,Agrawal R,Megiddo N.Discovery-driven exploration of OLAP data cubes.In:Schek HJ,Alonso G,Saltor F,et al.eds.Advances in database technology—EDBT’98.Berlin Heidelberg:Springer,1998.168-182.

15Ramaswamy S,Rastogi R,Shim K.Efficient algorithms for mining outliers from large data sets.Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data.New York,NY,USA.2000.427-438.

16Angiulli F,Basta S,Pizzuti C.Distance-based detection and prediction of outliers.IEEE Transactions on Knowledge and Data Engineering,2006,18(2):145-160.[doi:10.1109/TKDE.2006.29]

17Angiulli F,Basta S,Lodi S,et al.Distributed strategies for mining outliers in large data sets.IEEE Transactions on Knowledge and Data Engineering,2013,25(7):1520-1532.[doi:10.1109/TKDE.2012.71]

18Dean J,Ghemawat S.MapReduce:Simplified data processing on large clusters.Proceedings of the 6th Conference on Symposium on Opearting Systems Design &Implementation.San Francisco,CA,USA.2004.

19周品.Hadoop云計算實戰(zhàn).北京:清華大學(xué)出版社,2012.