郭娟娟，趙旭俊，張繼福

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

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

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

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

1 相關(guān)工作

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

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

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

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

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

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

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

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

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

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

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

(1)

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

(2)

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

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

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

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

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

(3)

dq是查詢對(duì)象q的離群因子，本文定義前TOP-N個(gè)dq值最大的點(diǎn)為離群點(diǎn)。

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

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

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

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

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

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

算法1：構(gòu)造數(shù)據(jù)集副本中所有對(duì)象的加權(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ù)對(duì)象加權(quán)；

5)g(O)=

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

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

10)emit(分區(qū)編號(hào)1,平移對(duì)象值)；

11)}

12)end function

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

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

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

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

17)}

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

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

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

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

22)}

23)end function

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

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

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

輸入：第一個(gè)MapReduce的輸出

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

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

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

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

4)end function

5)function REDUCE(key 對(duì)象編號(hào), 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個(gè)對(duì)象為對(duì)象q的加權(quán)k近鄰；

12)emit(對(duì)象編號(hào), 加權(quán)k近鄰)；

13)end function

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

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

算法3：計(jì)算離群因子，確定離群對(duì)象

輸入：第二個(gè)MapReduce的輸出

輸出：前TOP-N個(gè)離群對(duì)象

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ū)編號(hào)3)；

9)end function

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

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

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

13)}

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

15)end function

4 實(shí)驗(yàn)與分析

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

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

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

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

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

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

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

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

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

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

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

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

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

4.2.2 算法WKNNOM-MR的伸縮性

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

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

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

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

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

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

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

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

圖 6 節(jié)點(diǎn)個(gè)數(shù)對(duì)挖掘效率的影響
Fig.6 Efficiency impact of node

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

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

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

5 結(jié) 論

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