基于MapReduce與距離的離群數據并行挖掘算法①

任 燕

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

1 引言

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

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

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

2 離群數據與MapReduce編程模型

2.1 基本定義與概念

假設數據集D是給定度量空間的有限子集,相關概念定義如下:

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

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

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

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

2.2 “解集”算法實現

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

算法描述如下:

2.3 MapReduce框架

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

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

圖1 MapReduce 編程模型的原理

3 基于MapReduce的離群數據并行挖掘

3.1 “解集”算法的并行化

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

主節點主要調度以下兩項任務:

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

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

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

從節點的主要運算包含以下步驟:

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

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

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

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

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

3.2 MapReduce編程模型下的“分布式解集”算法實現

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

圖2 算法在MapReduce編程模型下實現

4 實驗結果及分析

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

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

4.1 人工數據集

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

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

圖3 數據維度對算法性能的影響

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

圖4 節點個數對性能的影響

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

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

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

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

4.2 UCI數據集

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

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

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

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

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

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

5 結束語

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

參考文獻

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云計算實戰.北京:清華大學出版社,2012.