基于MapReduce的并行加權(quán)k近鄰與離群檢測

郭娟娟，趙旭俊，張繼福

(太原科技大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院，太原 030024)

k近鄰查詢是最簡單的機(jī)器學(xué)習(xí)算法之一，用于多維空間中查詢與給定對象最近的k個對象[1]，其廣泛應(yīng)用于數(shù)據(jù)挖掘及地理信息系統(tǒng)等多個領(lǐng)域[2]。同時k近鄰查詢也存在一些問題：傳統(tǒng)方法在查詢k近鄰時，視所有屬性對查詢結(jié)果同等重要，但是在實際應(yīng)用場景中，不同屬性對查詢結(jié)果的影響是不同的，若忽略不同屬性的差異，將產(chǎn)生大量無意義的近鄰數(shù)據(jù)；并且隨著數(shù)據(jù)量的增大，傳統(tǒng)k近鄰查詢方法處理效率低，不能滿足大數(shù)據(jù)時代下人們對算法性能的要求。

MapReduce是由Google公司提出的一種具有可擴(kuò)展和高容錯的并行編程模型[3]，它將數(shù)據(jù)進(jìn)行分割并分布到多個工作節(jié)點上，利用集群數(shù)據(jù)節(jié)點之間的并行性，分別處理這些數(shù)據(jù)，然后執(zhí)行歸約操作，形成最終結(jié)果。

本文結(jié)合大數(shù)據(jù)的應(yīng)用背景，給出一種基于MapReduce的并行加權(quán)k近鄰查詢與離群檢測算法WKNNOM-MR,主要貢獻(xiàn)如下：(1)充分考慮分布式計算的因素，緊密結(jié)合MapReduce計算框架，提出適合分布式實現(xiàn)的加權(quán)k近鄰查詢方法，并在Hadoop平臺上實現(xiàn)該方法；(2)全面衡量每個對象與其加權(quán)k近鄰的關(guān)系，提出一種新的離群挖掘方法；(3)為了避免發(fā)生數(shù)據(jù)傾斜現(xiàn)象，采用LSH劃分策略，分散數(shù)據(jù)，使得各節(jié)點的工作量大致平衡；(4)最后在具有5個節(jié)點的Hadoop集群上實現(xiàn)該算法，并采用人工合成數(shù)據(jù)集、UCI標(biāo)準(zhǔn)數(shù)據(jù)集進(jìn)行實驗，結(jié)果驗證了該算法的有效性、可擴(kuò)展性和可伸縮性。

1 相關(guān)工作

1.1 加權(quán)k近鄰查詢的并行化實現(xiàn)

k近鄰查詢是指根據(jù)相似性度量在數(shù)據(jù)集中查詢與給定對象最近的k個數(shù)據(jù)對象，其中Indyk和Motwani[4]提出使用局部敏感哈希LSH查找k近鄰，通過哈希函數(shù)構(gòu)建哈希桶，將相近的對象以較高的概率映射到相同的桶中，從而在每個桶中找各自的最近鄰。但是隨著大數(shù)據(jù)時代的到來，傳統(tǒng)的方法已不能滿足現(xiàn)實需求，算法的性能也有待進(jìn)一步提升，從而加快了分布式數(shù)據(jù)計算的發(fā)展。Qing He等[5]提出基于KD-Tree進(jìn)行k近鄰查詢的并行離群數(shù)據(jù)挖掘算法，并采用MapReduce框架實現(xiàn)，取得了較好的挖掘效果。Stupar等[6]提出使用Map Reduce框架解決海量高維數(shù)據(jù)的近似k近鄰集查詢問題，將LSH技術(shù)應(yīng)用于第一個MapReduce階段，實現(xiàn)合理的分區(qū)映射，有效提高了k近鄰的查詢效率。同時，傳統(tǒng)的方法忽略了不同屬性對查詢結(jié)果的影響，視所有屬性是同等重要的，因此，本文提出一種適合分布式實現(xiàn)的加權(quán)k近鄰方法，用于解決海量數(shù)據(jù)集的加權(quán)k近鄰查詢問題。

1.2 離群檢測算法的并行化實現(xiàn)

離群挖掘是用來發(fā)現(xiàn)數(shù)據(jù)集中實際存在、但又容易被忽略的有價值數(shù)據(jù)，傳統(tǒng)的離群檢測方法[7-8]易受維度影響，不適合用于高維數(shù)據(jù)挖掘，因此將高維數(shù)據(jù)映射到低維空間后再進(jìn)行相似性度量是個可行的方法。文獻(xiàn)[7-9]提出利用MapReduce計算模型實現(xiàn)并行離群點檢測算法，通過迭代計算來更新全局候選離群點，找出離群度最大的數(shù)據(jù)點，但是該算法需要使用多個MapReduce，耗時較多。因此茍杰等[10]提出只需要一次MapReduce的并行化算法PODKNN，首先對數(shù)據(jù)集進(jìn)行無損劃分，之后在Map階段查詢k近鄰并計算離群因子，在Reduce階段進(jìn)行匯總歸約，確定離群因子大的對象為離群對象。楊海峰等[11]利用MapReduce編程模型，實現(xiàn)了一種上下文離群數(shù)據(jù)并行挖掘算法，并用實驗驗證了該算法的可解釋性和有效性。張繼福等[12]在Hadoop平臺上，提出了一種基于MapReduce和相關(guān)子空間的局部離群數(shù)據(jù)挖掘方法，利用局部稀疏差異度矩陣確定相關(guān)子空間，在其相關(guān)子空間中計算數(shù)據(jù)的離群因子，有效降低了“維災(zāi)”對離群挖掘的影響，實驗證明該算法具有較好的挖掘效果及可擴(kuò)展性和可伸縮性。

綜上所述，多數(shù)k近鄰查詢方法是建立在所有屬性的重要性相同的基礎(chǔ)之上，假設(shè)數(shù)據(jù)的所有屬性是同等重要的，但是在很多實際應(yīng)用中，各個屬性對近鄰查詢的重要程度是不同的；同時，隨著數(shù)據(jù)量與數(shù)據(jù)維度的不斷增大，現(xiàn)有的很多離群檢測算法性能較差，不能很好的解決實際應(yīng)用中所遇到的困難。因此，本文將針對以上問題展開研究。

2 基于Z-order的加權(quán)k近鄰與離群檢測算法

2.1 基于Z-order的加權(quán)k近鄰

Z-order曲線是空間填充曲線的一種，能將高維空間數(shù)據(jù)映射到低維空間，有效降低維度對結(jié)果的影響。該曲線穿過且僅穿過一次高維空間中的每一個離散網(wǎng)格，依據(jù)穿過的順序為這些網(wǎng)格進(jìn)行統(tǒng)一編號，該編號稱為Z-value值，簡稱Z值。Z-order曲線就是由數(shù)據(jù)集DS中的對象，經(jīng)位交叉計算得到Z值，再將所有Z值相連形成的Z形曲線，具體的1階、2階Z-order曲線如圖1所示，其中階數(shù)代表了空間被劃分的程度，階數(shù)越大，空間被劃分的越細(xì)。

圖1 Z-order曲線
Fig.1 Z-order curve

Ramaswamy和kyuseok等人[13]提出使用k近鄰方法處理實際問題，但其沒有考慮不同屬性重要程度對結(jié)果的影響，為解決這一問題，提出加權(quán)k近鄰，為不同屬性賦予不同權(quán)值，充分考慮屬性的重要程度對結(jié)果的影響。而信息熵是一種很好的度量權(quán)重的方法，用平均信息量體現(xiàn)信源各個離散消息的不確定性，有效地刻畫了信息的量化度量問題[14]。參照文獻(xiàn)[14]，相關(guān)概念和定義描述如下：

定義1：給定數(shù)據(jù)集DS，A={A1,A2,...,Ad}是DS的屬性集，每個屬性有n個值A(chǔ)i={Ai1,Ai2,...,Ain}，Ail的信號量為I(Ail)=-log2Pl，Pl表示Ail出現(xiàn)的概率，信源的信息熵即：

(1)

在本文中，H(Al)值越大，屬性Al的重要程度越高，該屬性的信息量就越多。信息熵從平均意義上表征了屬性Al的總體特征，因此對所有屬性的信息熵進(jìn)行歸一化操作，從而確定各個屬性的權(quán)值。令屬性權(quán)值為W(A)={w1,w2,…,wd}，其中：

(2)

采用Z-order曲線進(jìn)行加權(quán)k近鄰查詢時，存在高維空間中相近的對象映射到低維空間中不相鄰的情況，為了避免這種現(xiàn)象發(fā)生，引入加權(quán)k近鄰候選集與隨機(jī)位移操作的概念。

定義2：給定數(shù)據(jù)集DS，O={O1,O2,...,On}是DS的對象集，Z'是對象Oi的Z值，在對所有Z值排序之后，生成一個有序數(shù)列，Z值小于Z'的k個對象為Oi的前驅(qū)，大于Z'的k個對象為Oi的后繼，由Oi的前驅(qū)和后繼組成的集合，稱為Oi的加權(quán)k近鄰候選集，記為C(Oi).

采用Z-order曲線搜索加權(quán)k近鄰的詳細(xì)步驟如下：(1)根據(jù)信息熵計算原始數(shù)據(jù)集DS中每個屬性的權(quán)值，對原始數(shù)據(jù)集賦權(quán)之后得到加權(quán)數(shù)據(jù)集DS'；(2)將加權(quán)后的屬性值進(jìn)行二進(jìn)制編碼，并采用文獻(xiàn)[15]中方法，對DS'中所有對象的二進(jìn)制屬性值進(jìn)行位交叉操作，得到各自的Z值；(3)按照Z值的大小對數(shù)據(jù)集進(jìn)行重新排序，在排序結(jié)果中，找到每個對象的k個前驅(qū)和k個后繼，從而確定所有對象的加權(quán)k近鄰候選集；(4)為了保證查詢結(jié)果的準(zhǔn)確性，根據(jù)定義3對DS'進(jìn)行隨機(jī)位移操作，生成f個隨機(jī)位移副本，每個副本都重復(fù)執(zhí)行步驟2和3，DS'中的所有對象都會產(chǎn)生擁有2kf個元素的加權(quán)k近鄰候選集；(5)計算每個對象與其所有加權(quán)k近鄰候選集中元素的歐式距離，距離最小的前k個即為該對象的加權(quán)k近鄰。

2.2 基于加權(quán)k近鄰的離群檢測算法

采用k近鄰查詢方法進(jìn)行離群檢測時，需要考慮查詢對象與其k個最近鄰的關(guān)系，目前已有的離群檢測方法要么只考慮數(shù)據(jù)對象與其k個近鄰的整體水平，要么只考慮與第k個近鄰的關(guān)系，而本文采用綜合分析的方法，既考慮整體水平，也考慮數(shù)據(jù)對象之間的個體差異。

(3)

dq是查詢對象q的離群因子，本文定義前TOP-N個dq值最大的點為離群點。

3 基于MapReduce的加權(quán)k近鄰與離群檢測

MapReduce是Hadoop平臺上處理大數(shù)據(jù)集的編程框架，能夠運行在成千上萬個普通機(jī)器的節(jié)點上，具有很高的容錯性。k近鄰查詢是根據(jù)相似性度量在數(shù)據(jù)集中查詢與給定對象最近的k個數(shù)據(jù)對象。加權(quán)k近鄰是在傳統(tǒng)k近鄰的基礎(chǔ)上，對不同屬性賦予不同權(quán)值，用于區(qū)分各屬性的重要程度。因此，可以借助MapReduce編程框架，將大數(shù)據(jù)集切分為獨立的小塊，在每個小塊中進(jìn)行加權(quán)k近鄰查詢，進(jìn)一步得到對象的離群因子，從而確定數(shù)據(jù)集中的離群對象。本文提出的基于MapReduce的并行加權(quán)k近鄰與離群檢測算法實現(xiàn)過程如圖2所示。

3.1 數(shù)據(jù)預(yù)處理

隨著信息社會的發(fā)展，數(shù)據(jù)量不斷增大，在考慮數(shù)據(jù)屬性重要程度時，需要對大量數(shù)據(jù)進(jìn)行掃描，從而計算出權(quán)值，但此過程非常耗時，開銷很大，因此，對數(shù)據(jù)集進(jìn)行抽樣，從而用樣本數(shù)據(jù)集的屬性權(quán)值代替整個數(shù)據(jù)集的屬性權(quán)值。本文使用文獻(xiàn)[16]的采樣方法，對大數(shù)據(jù)集中數(shù)據(jù)隨機(jī)均勻采樣，并通過實驗證明采樣比例在1%～2%之間最佳。得到樣本數(shù)據(jù)集之后，根據(jù)公式(1)、(2)確定各個屬性的權(quán)值，并將結(jié)果保存到文件Weighted中，上傳至HDFS，以便在第一個MapReduce中對數(shù)據(jù)加權(quán)時調(diào)用。

圖2 MapReduce的實現(xiàn)過程
Fig.2 Implementation framework of MapReduce

3.2 構(gòu)建加權(quán)k近鄰候選集

算法1：構(gòu)造數(shù)據(jù)集副本中所有對象的加權(quán)k近鄰候選集

輸入：數(shù)據(jù)集DS；

輸出：加權(quán)k近鄰候選集；

1)function MAP(key 偏移量, value 數(shù)據(jù)集DS)；

2)for each O in DS ；

3)讀取HDFS上的Weighted文件，根據(jù)文件中的屬性權(quán)值為數(shù)據(jù)對象加權(quán)；

5)g(O)=

6)a=(a1,a2,…,anum)；

7)for (i = 0；i < f；i++){

10)emit(分區(qū)編號1,平移對象值)；

11)}

12)end function

13)function REDUCE(key 分區(qū)編號1, values平移對象集)

14)for (i = 0；i < n1；i++) {

15)對每個對象屬性值的二進(jìn)制編碼執(zhí)行位交叉操作；

16)位交叉的結(jié)果轉(zhuǎn)為十進(jìn)制即為該對象的Z值；

17)}

18)for (j = 0；j < n1；j++) {

19)查詢比q'的Z值小的k個對象放入Z-中，比q'的Z值大的k個對象放入Z+中；

20)將Z-、Z+插入到加權(quán)k近鄰候選集中；

21)emit(分區(qū)編號2, 加權(quán)k近鄰候選集)；

22)}

23)end function

3.3 確定加權(quán)k近鄰

第二個MapReduce讀取第一個MapReduce的輸出文件，根據(jù)每個對象與其加權(quán)k近鄰候選集中所有對象的距離確定最終的加權(quán)k近鄰，具體實現(xiàn)如算法2所示。在Map階段，以鍵值對< key 偏移量，value 加權(quán)k近鄰>作為輸入，分割每條讀入數(shù)據(jù)，以作為輸出，如第1)～3)行所示。在Reduce階段，輸入為每個對象與其所有的加權(quán)k近鄰候選集，計算每個對象與加權(quán)k近鄰候選集中所有元素的歐式距離，確定距離最小的k個對象為加權(quán)k近鄰，最后以鍵值對的形式輸出，如第6)～11)行所示。輸出結(jié)果存入HDFS的文件中，該文件作為第三個MapReduce的輸入。

算法2：計算對象的加權(quán)k近鄰

輸入：第一個MapReduce的輸出

輸出：加權(quán)k近鄰

1)function MAP(key 偏移量, value 加權(quán)k近鄰候選集)

2)對讀入的數(shù)據(jù)進(jìn)行切分；

3)emit(對象編號, 加權(quán)k近鄰候選集)；

4)end function

5)function REDUCE(key 對象編號, values加權(quán)k近鄰候選集)

6)for (i = 0；i < 2kf；i++){

7)for (j = 0；j < d；j++){

8)disq=sqrt(disq+(qj-pij)2)；

9)}

10)}

11)找到disq最小的k個對象為對象q的加權(quán)k近鄰；

12)emit(對象編號, 加權(quán)k近鄰)；

13)end function

3.4 確定離群數(shù)據(jù)

第三個MapReduce讀入第二個MapReduce的輸出文件，根據(jù)每個對象與其加權(quán)k近鄰之間的距離計算離群因子，確定前TOP-N個離群因子最大的對象為離群對象，具體實現(xiàn)如算法3所示。在Map階段，以鍵值對作為輸入，根據(jù)歐式距離計算每個對象與其加權(quán)k近鄰的距離，從而計算出每個對象與k個加權(quán)近鄰中最近近鄰的距離dmin以及平均距離dave，然后根據(jù)公式(3)計算離群因子dq，輸出，如2)～7)行所示。序號全部設(shè)為0，分區(qū)編號3由對象編號、離群因子dq組成。在Reduce階段，比較所有對象的離群因子dq，將離群因子最大的TOP-N個對象輸出，輸出形式為，如11)～13)行所示，此結(jié)果即為WKNNOM-MR離群檢測算法的結(jié)果。

算法3：計算離群因子，確定離群對象

輸入：第二個MapReduce的輸出

輸出：前TOP-N個離群對象

1)function MAP(key 偏移量, value 加權(quán)k近鄰)

2)for (i = 0；i < k；i++) {

3)for (j = 0；j < d；j++) {

4)disq=sqrt(disq+(qj-pij)2)；

5)}

6)}

8)emit(0, 分區(qū)編號3)；

9)end function

10)function REDUCE(key 0, values分區(qū)編號3)

11)for(i = 0；i < n；i++){

12)比較n個對象的dq值大小，保留最大的TOP-N個；

13)}

14)emit(離群因子, 離群對象)；

15)end function

4 實驗與分析

4.1 UCI標(biāo)準(zhǔn)數(shù)據(jù)集

實驗環(huán)境：硬件配置為Intel(R) Core(TM) i5-4570 CPU、8G內(nèi)存、Windows7操作系統(tǒng)的筆記本一臺，在虛擬機(jī)VMware-workstation-12.0.0上安裝Ubuntu14.04操作系統(tǒng)，分布式平臺為hadoop2.6.0，集成開發(fā)環(huán)境為Eclipse，采用java語言實現(xiàn)偽分布環(huán)境下的WKNNOM-MR算法。

實驗數(shù)據(jù)： UCI機(jī)器學(xué)習(xí)庫中的數(shù)據(jù)集Anuran Calls (MFCCs)，該數(shù)據(jù)集所含數(shù)據(jù)量為7 195，屬性個數(shù)為22個，異常值為73個。

為了比較不同副本個數(shù)(即參數(shù)f)對算法WKNNOM-MR各項性能的影響，將副本數(shù)f設(shè)定為0、1、2、5、10和22，其中：f=0代表原始數(shù)據(jù)集DS.圖3(a)顯示了在同一數(shù)據(jù)集中，不同副本個數(shù)f對離群檢測結(jié)果準(zhǔn)確率的影響。當(dāng)f相同k不同時，準(zhǔn)確率隨k值的增大呈上升趨勢；k相同f不同時，準(zhǔn)確率隨f值的增大而增大，且準(zhǔn)確率的提升速度越來越慢。例如f=1與f=0的副本個數(shù)差1，但準(zhǔn)確率卻變化很大，f=2與f=1的變化速度也很明顯；f=5、10、22三者雖然副本數(shù)相差較多，但準(zhǔn)確率曲線卻幾乎完全重合。發(fā)生這種現(xiàn)象主要是因為在第一個MapReduce的Map階段，對數(shù)據(jù)集中的所有對象構(gòu)建數(shù)據(jù)集副本，副本數(shù)越多，Reduce階段的任務(wù)數(shù)越多，加權(quán)k近鄰候選集越龐大，出現(xiàn)重復(fù)對象的個數(shù)也越多，那么準(zhǔn)確率提高的速度就會降低，到達(dá)某個峰值后不再變化。但是，隨著副本數(shù)的增加，算法執(zhí)行時間也會增加，實驗結(jié)果參見圖3(b).

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

實驗環(huán)境：由5個計算節(jié)點構(gòu)成的集群，每個節(jié)點的配置為2-core CPU、2G內(nèi)存、40G硬盤，操作系統(tǒng)為Ubuntu14.04，分布式平臺為hadoop2.6.0，集成開發(fā)環(huán)境為Eclipse，編程語言為java.

實驗數(shù)據(jù)：利用Microsoft Excel的隨機(jī)數(shù)據(jù)生成器來創(chuàng)建大量的人工數(shù)據(jù)，這些數(shù)據(jù)集遵循正態(tài)分布，期望為0，方差為1.本文共創(chuàng)建了兩組合成數(shù)據(jù)集，第一組為D1、D2、D3、D4和D5，分別包含20、40、60、80和100個屬性，同時每個數(shù)據(jù)集由500 000個對象構(gòu)成；第二組為S1、S2、S3、S4和S5，他們擁有50個屬性，其數(shù)據(jù)對象個數(shù)分別為200 000、400 000、600 000、800 000和1 000 000.

4.2.1 維度d對算法WKNNOM-MR挖掘效率的影響

本組實驗采用第一組人工數(shù)據(jù)集D1、D2、D3、D4、D5來評價WKNNOM-MR的性能，取節(jié)點個數(shù)為3、4、5，k=30，實驗結(jié)果如圖4所示。

圖4(a)顯示了集群節(jié)點不同時，數(shù)據(jù)維度對算法挖掘效率的影響。隨著維度的增加，算法WKN-NOM-MR的挖掘時間逐步遞增，運行效率遞減，同時數(shù)據(jù)量不變的情況下，節(jié)點個數(shù)越少，算法效率越低。這是因為隨著數(shù)據(jù)維度增大，每條數(shù)據(jù)的屬性不斷增多，那么在使用Z-order曲線進(jìn)行空間映射時，Z值的計算更復(fù)雜，導(dǎo)致每個對象的查詢時間隨之增加。數(shù)據(jù)量不變的情況下，HDFS文件系統(tǒng)中的數(shù)據(jù)塊數(shù)不變，那么節(jié)點個數(shù)越多，每個節(jié)點上的運行塊數(shù)越少，整個運行時間便會成比例降低，但是在實際運行中，節(jié)點個數(shù)越多，網(wǎng)絡(luò)傳輸耗時也會增加，所以下降比例略有變化。

圖3 副本數(shù)f的性能
Fig.3 Performance of replica numberf

為了測試WKNNOM-MR算法在維度上的可擴(kuò)展性，采用時間比來定量分析。在本實驗中，時間比是不同維度數(shù)據(jù)集的運行時間同20維數(shù)據(jù)集的運行時間之間的比例。通過時間比可體現(xiàn)隨著維度的增加，算法WKNNOM-MR具有較好的擴(kuò)展性，實驗結(jié)果詳見圖4(b).

圖4(b)是節(jié)點個數(shù)為3、4、5時的時間比變化圖，隨著維度的增加，時間比不斷提高，且節(jié)點個數(shù)越多，時間比越大，曲線的傾斜角度逐漸高于線性。這是因為隨著維度的增加，數(shù)據(jù)集容量不斷變大，HDFS文件系統(tǒng)中的數(shù)據(jù)塊變多，每個節(jié)點上的數(shù)據(jù)對象越多，集群的I/O耗時越多，那么在Map與Reduce之間的Shuffle代價不斷增加，導(dǎo)致數(shù)據(jù)維度越大，時間比越大。同時，節(jié)點個數(shù)越多，網(wǎng)絡(luò)傳輸耗時越多，從而時間比越大。

4.2.2 算法WKNNOM-MR的伸縮性

本組實驗采用第二組人工數(shù)據(jù)集S1、S2、S3、S4、S5來評價WKNNOM-MR的伸縮性，取節(jié)點個數(shù)為3、4、5，k=30，實驗結(jié)果如圖5所示。

圖 4 維度對挖掘效率的影響
Fig.4 Efficiency impact of dimension

圖5 數(shù)據(jù)量對挖掘效率的影響
Fig.5 Efficiency impact of data amount

圖5(a)顯示了節(jié)點個數(shù)不同時，數(shù)據(jù)量對WKNNOM-MR挖掘效率的影響，數(shù)據(jù)量越大，算法運行時間越長，且節(jié)點個數(shù)越多，算法的運行時間越少，效率越高。這是因為hadoop平臺的任務(wù)數(shù)是由HDFS分配給節(jié)點的數(shù)據(jù)塊數(shù)決定的，數(shù)據(jù)量越多，每個計算節(jié)點上分配的數(shù)據(jù)對象也越多，導(dǎo)致每個節(jié)點要處理的任務(wù)量越多。同時對象個數(shù)越多，第一個MapReduce階段需要構(gòu)建的數(shù)據(jù)副本越多，最后生成的加權(quán)k近鄰候選集越多，導(dǎo)致離群對象的查找隨數(shù)據(jù)量的增加而線性增長。同樣數(shù)據(jù)量不變時，節(jié)點個數(shù)越少，每個節(jié)點上運行的數(shù)據(jù)對象越多，負(fù)荷越大，運行時間越長，即算法的運行時間與節(jié)點個數(shù)成反比。

在本實驗中，時間比被用于分析WKNNOM-MR算法在數(shù)據(jù)量上的可擴(kuò)展性，它是不同數(shù)據(jù)量的運行時間同最小數(shù)據(jù)量的運行時間的比例，其實驗結(jié)果呈現(xiàn)在圖5(b).

圖5(b)是節(jié)點個數(shù)為3、4、5時的時間比變化圖，數(shù)據(jù)量越大，時間比越大，且節(jié)點個數(shù)越多，時間比越大，曲線傾斜角度逐漸高于線性。這是因為隨著數(shù)據(jù)量的增大，HDFS文件系統(tǒng)中的數(shù)據(jù)塊變多，分配到各個計算節(jié)點上的數(shù)據(jù)對象也會隨之增加，第一個Map階段之后的Shuffle操作代價增大，導(dǎo)致整個分布式運行時間變多，時間比不斷變大。同時節(jié)點個數(shù)增加，網(wǎng)絡(luò)傳輸耗時增加，帶來運行的額外耗時變多，造成了時間比的增加。

4.2.3 算法WKNNOM-MR的可擴(kuò)展性

本組實驗采用第二組人工數(shù)據(jù)集中的S1、S3和S5，數(shù)據(jù)量為200 000、600 000、1 000 000條數(shù)據(jù)，每條數(shù)據(jù)有50個屬性，取k=30進(jìn)行實驗，實驗結(jié)果如圖6所示。

圖 6 節(jié)點個數(shù)對挖掘效率的影響
Fig.6 Efficiency impact of node

圖6(a)展示了不同數(shù)據(jù)集中節(jié)點個數(shù)對挖掘效率的影響，節(jié)點個數(shù)越少，數(shù)據(jù)量越大的數(shù)據(jù)集消耗的時間越多。因為算法中各個數(shù)據(jù)對象離群因子的計算完全可以實現(xiàn)并行化，Z值的計算不會受節(jié)點個數(shù)的影響，相應(yīng)的加權(quán)k近鄰候選集的構(gòu)建也與節(jié)點數(shù)無關(guān)，整個計算過程的計算量只與數(shù)據(jù)對象個數(shù)成線性關(guān)系，數(shù)據(jù)對象按節(jié)點個數(shù)比例分配到各計算節(jié)點。同時隨著計算節(jié)點的增加會增加一些網(wǎng)絡(luò)傳輸量，Shuffle階段受到影響，并行化的效果減弱，因此變化逐漸趨于緩慢。

為了衡量計算節(jié)點數(shù)目與算法效率之間的關(guān)系，采用加速比進(jìn)行定量分析。加速比=單個計算節(jié)點上的運行時間/t個計算節(jié)點上的運行時間。在進(jìn)行實驗時，保持實驗數(shù)據(jù)集不變，并調(diào)整計算節(jié)點的個數(shù)，得到單個節(jié)點同多個節(jié)點運行時間的比例，以此描述節(jié)點個數(shù)對算法運行時間的影響。

圖6(b)是節(jié)點個數(shù)不同時，不同數(shù)據(jù)集的運行加速比變化趨勢，節(jié)點個數(shù)越多，加速比越大，且數(shù)據(jù)量越少，加速比也越大，曲線整體變化趨勢逐漸低于線性。因為數(shù)據(jù)量越少，HDFS文件系統(tǒng)中的數(shù)據(jù)塊越少，每個計算節(jié)點上的數(shù)據(jù)對象越少，查詢所有對象的加權(quán)k近鄰所需時間也會減少，集群I/O耗時較少，這些額外耗時對加速比的影響較小，因此加速比越大。同時集群節(jié)點個數(shù)越多，算法的運行時間越短，理論上加速比應(yīng)與節(jié)點數(shù)成線性關(guān)系，但在實際操作過程中，節(jié)點個數(shù)的增加帶來網(wǎng)絡(luò)傳輸量的增加，因此并行化的效果會逐漸降低。

5 結(jié) 論

隨著信息時代的發(fā)展，數(shù)據(jù)量越來越大，離群數(shù)據(jù)的檢測越來越困難。針對這一問題，本文提出了一種基于MapReduce模型的離群檢測算法WKNNOM-MR.該算法是對WKNNOM的并行化設(shè)計，利用LSH數(shù)據(jù)配置策略分散數(shù)據(jù)，結(jié)合Z值計算每個對象的加權(quán)k近鄰，并根據(jù)近鄰距離值確定最終的離群對象。為了更好的適應(yīng)海量數(shù)據(jù)的需求，下一步會在多種分布特征的數(shù)據(jù)集上及更多集群節(jié)點上進(jìn)行實驗分析，并將該算法用于高維數(shù)據(jù)集的離群檢測。