異構(gòu)分布式環(huán)境中的并行離群點(diǎn)檢測(cè)算法

王習(xí)特 朱宗梅 于雪蘋 白梅

摘? ?要：離群點(diǎn)檢測(cè)是數(shù)據(jù)挖掘領(lǐng)域研究的熱點(diǎn)之一，主要目的是識(shí)別出數(shù)據(jù)集中異常但有價(jià)值的數(shù)據(jù)點(diǎn). 隨著數(shù)據(jù)規(guī)模不斷擴(kuò)大，使得處理海量數(shù)據(jù)的效率降低，隨即引入分布式算法. 目前現(xiàn)有的分布式算法大都用于解決同構(gòu)分布式的處理環(huán)境，但在實(shí)際應(yīng)用中，由于參與分布式計(jì)算的處理機(jī)配置的差異，現(xiàn)有的分布式離群點(diǎn)檢測(cè)算法不能很好地適用于異構(gòu)分布式環(huán)境. 針對(duì)上述問(wèn)題，本文提出一種面向異構(gòu)分布式環(huán)境的離群點(diǎn)檢測(cè)算法. 首先提出基于網(wǎng)格的動(dòng)態(tài)數(shù)據(jù)劃分方法（Gird-based Dynamic Data Partitioning，GDDP），充分利用各處理機(jī)的計(jì)算資源，同時(shí)根據(jù)數(shù)據(jù)點(diǎn)的空間位置信息進(jìn)行數(shù)據(jù)劃分，可有效減少網(wǎng)絡(luò)通信. 其次基于GDDP算法，提出了異構(gòu)分布式環(huán)境中并行的離群點(diǎn)檢測(cè)算法（GDDP-based Outlier Detection Algorithm，GODA）. 該算法包括2個(gè)階段：在每個(gè)處理機(jī)本地，按照索引中數(shù)據(jù)點(diǎn)的順序進(jìn)行過(guò)濾，通過(guò)2次掃描得到離群點(diǎn)候選集;判斷候選離群點(diǎn)需要進(jìn)行網(wǎng)絡(luò)通信的處理機(jī)，使用較低網(wǎng)絡(luò)開(kāi)銷得出全局離群點(diǎn). 最后，通過(guò)大量實(shí)驗(yàn)驗(yàn)證了本文提出的GDDP和GODA算法的有效性.

關(guān)鍵詞：離群點(diǎn)檢測(cè);異構(gòu)分布式;網(wǎng)格;數(shù)據(jù)劃分

中圖分類號(hào)：TP391 ? ? ? ? ? ? ? ? ? ? ? ? ? 文獻(xiàn)標(biāo)志碼：A

Parallel Outlier Detection Algorithm

in Heterogeneous Distributed Environment

WANG Xite?，ZHU Zongmei，YU Xueping，BAI Mei

（College of Information Science and Technology，Dalian Maritime University，Dalian 116000，China）

Abstract：Outlier detection is one of the hotspots in the field of data mining. The main purpose is to identify the abnormal but valuable data points in the data set. With the expansion of data scale，the efficiency of processing massive data is reduced，and then a distributed algorithm is introduced. At present，most of the existing distributed algorithms are used to solve the homogeneous distributed processing environment. However，in practical applications，due to the differences in processor configuration involved in distributed computing，the existing distributed outlier detection algorithms cannot be well applied to heterogeneous distributed environments. In view of the above problems，this paper proposes an outlier detection algorithm for heterogeneous distributed environments. Firstly，a grid-based dynamic data partitioning （GDDP） method is proposed，which makes full use of the computing resources of each processor and divides the data according to the spatial location information of the data points，which can effectively reduce the network communication. Secondly，based on the GDDP algorithm，a parallel GDDP-based Outlier Detection Algorithm （GODA） is proposed. The algorithm consists of two stages：in each processor，filtering according to the order of the data points in the index and obtaining the outlier candidate set by two scans;determining the candidate outliers requiring network communication and using low network overhead leads to global outliers. Finally，the effectiveness of the proposed GDDP and GODA algorithms is verified by a large number of experiments.

Key words：outlier detection;heterogeneous distribution;grid;data partition

離群點(diǎn)檢測(cè)是數(shù)據(jù)管理領(lǐng)域的重要研究?jī)?nèi)容之一，其主要目的是識(shí)別出數(shù)據(jù)集中與其他數(shù)據(jù)存在顯著差異的數(shù)據(jù)對(duì)象. 隨著對(duì)離群點(diǎn)的不斷研究，出現(xiàn)了多種離群點(diǎn)描述方式. 其中，最直觀的方式是通過(guò)度量數(shù)據(jù)空間中數(shù)據(jù)點(diǎn)間的距離來(lái)量化數(shù)據(jù)的離群程度. 具體地，基于距離的離群點(diǎn)可定義為：給定參數(shù)k和r，對(duì)于數(shù)據(jù)集P中任意數(shù)據(jù)點(diǎn)p，若與點(diǎn)p的距離小于等于r的數(shù)據(jù)點(diǎn)個(gè)數(shù)少于k，則p為離群點(diǎn)[1].

隨著數(shù)據(jù)庫(kù)中數(shù)據(jù)量的不斷增加，有關(guān)離群點(diǎn)的研究已從集中式處理環(huán)境轉(zhuǎn)向分布式處理環(huán)境，以提高海量數(shù)據(jù)的離群點(diǎn)檢測(cè)效率[2]. 但是，現(xiàn)有的分布式算法大都用來(lái)解決同構(gòu)分布式環(huán)境中的離群點(diǎn)檢測(cè)問(wèn)題. 在實(shí)際應(yīng)用中，參與分布式計(jì)算的處理機(jī)大都存在配置上的差異，各處理機(jī)的性能可能存在較大差異. 這也就使得現(xiàn)有的針對(duì)同構(gòu)分布式環(huán)境設(shè)計(jì)的離群點(diǎn)檢測(cè)算法不能很好地適用于異構(gòu)分布式環(huán)境. 因此，迫切需要設(shè)計(jì)一種高效的異構(gòu)分布式環(huán)境中的并行離群點(diǎn)檢測(cè)算法.

本文主要針對(duì)異構(gòu)分布式環(huán)境下的離群點(diǎn)檢測(cè)問(wèn)題，提出一種動(dòng)態(tài)數(shù)據(jù)劃分方法和相應(yīng)計(jì)算方法，旨在提高算法的執(zhí)行效率. 具體地，本文的主要貢獻(xiàn)包括以下幾個(gè)部分：

1）提出一種基于網(wǎng)格的動(dòng)態(tài)數(shù)據(jù)劃分方法GDDP（Gird-based Dynamic Data Partitioning）. 該方法依據(jù)異構(gòu)分布式環(huán)境中各處理機(jī)計(jì)算能力的差異動(dòng)態(tài)分配計(jì)算任務(wù)，實(shí)現(xiàn)了各處理機(jī)計(jì)算任務(wù)的負(fù)載均衡，加快了計(jì)算效率. 同時(shí)，考慮了數(shù)據(jù)集中數(shù)據(jù)點(diǎn)所處的空間位置信息，盡可能將空間上相鄰的數(shù)據(jù)點(diǎn)劃分至同一處理機(jī)，降低網(wǎng)絡(luò)開(kāi)銷.

2）基于GDDP劃分方法，提出了異構(gòu)分布式環(huán)境中并行的離群點(diǎn)檢測(cè)算法GODA（GDDP-based Outlier Detection Algorithm）. 該算法主要包括兩個(gè)過(guò)程：①本地離群點(diǎn)計(jì)算.首先通過(guò)索引對(duì)每個(gè)處理機(jī)本地的數(shù)據(jù)集進(jìn)行管理，然后根據(jù)過(guò)濾規(guī)則實(shí)現(xiàn)數(shù)據(jù)集中非離群點(diǎn)的過(guò)濾，從而快速計(jì)算出本地離群點(diǎn);②全局離群點(diǎn)計(jì)算.利用每個(gè)候選離群點(diǎn)和其所在數(shù)據(jù)塊與相鄰數(shù)據(jù)塊的距離關(guān)系，判斷需要進(jìn)行網(wǎng)絡(luò)通信的處理機(jī)，然后統(tǒng)一將候選點(diǎn)發(fā)送到相應(yīng)的處理機(jī)上，從而得到全局離群點(diǎn).

3）分別利用真實(shí)數(shù)據(jù)集和人工合成數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，驗(yàn)證了本文提出的GDDP和GODA算法的有效性.

1? ?相關(guān)工作

本節(jié)主要從集中式和分布式兩方面對(duì)離群點(diǎn)檢測(cè)的相關(guān)研究進(jìn)行概述.

1.1? ?集中式離群點(diǎn)檢測(cè)

目前，大多數(shù)離群點(diǎn)研究都是面向集中式環(huán)境的. 研究?jī)?nèi)容主要包括兩個(gè)方面：離群點(diǎn)定義和離群點(diǎn)檢測(cè)方法. 首先，離群點(diǎn)定義方面的研究致力于給出一種描述或者形式化定義離群點(diǎn)的方法. Hawkins等[3]最早給出離群點(diǎn)的形象化描述，認(rèn)為離群點(diǎn)是數(shù)據(jù)集中與其他點(diǎn)差距很大、且懷疑與其他數(shù)據(jù)點(diǎn)并非由同一機(jī)制生成的點(diǎn). 為了更明確數(shù)據(jù)點(diǎn)是否為離群點(diǎn)，提出基于模型的離群點(diǎn)定義，以數(shù)據(jù)的分布模型為參考，將數(shù)據(jù)集中不符合分布模型的數(shù)據(jù)點(diǎn)定義為離群點(diǎn)[4]. 至今，研究人員給出了多種不同的離群點(diǎn)定義標(biāo)準(zhǔn)，如：基于距離的離群點(diǎn)、基于聚類的離群點(diǎn)[5]、基于密度的離群點(diǎn)[6]. 其中，基于距離的離群點(diǎn)定義能直觀地反應(yīng)離群點(diǎn)本質(zhì)進(jìn)而得到廣泛應(yīng)用.

其次，離群點(diǎn)檢測(cè)是指根據(jù)某種離群點(diǎn)判定方式，從數(shù)據(jù)集中快速找到符合該判定方式的數(shù)據(jù)點(diǎn)的過(guò)程，判定方式不同，相應(yīng)的離群點(diǎn)計(jì)算方法也不同. 具體地，文獻(xiàn)[1]基于距離的離群點(diǎn)定義，提出一種嵌套循環(huán)方式，對(duì)數(shù)據(jù)集中每個(gè)數(shù)據(jù)點(diǎn)進(jìn)行距離計(jì)算，以找出最終的離群點(diǎn). 這種方法可以應(yīng)對(duì)多維數(shù)據(jù)集，但實(shí)際的計(jì)算效率有待優(yōu)化. 之后，Bay等[7]提出ORCA算法，利用緩沖區(qū)給出一種修剪規(guī)則，實(shí)現(xiàn)對(duì)非離群點(diǎn)的過(guò)濾，加快檢測(cè)效率. 此外，有些學(xué)者利用空間索引加速離群點(diǎn)的計(jì)算過(guò)程. 文獻(xiàn)[8] 提出了基于R樹(shù)的離群點(diǎn)檢測(cè)算法，文獻(xiàn)[9]給出了基于k-d樹(shù)的離群點(diǎn)檢測(cè)算法.

1.2? ?分布式離群點(diǎn)檢測(cè)

為了解決傳統(tǒng)集中式離群點(diǎn)檢測(cè)算法在大規(guī)模數(shù)據(jù)中檢測(cè)效率低的問(wèn)題，許多研究人員提出了有效的分布式算法，而現(xiàn)有的分布式離群點(diǎn)檢測(cè)算法都是面向同構(gòu)分布式環(huán)境的. Hung等[10]首先給出分布式環(huán)境中基于距離的離群點(diǎn)檢測(cè)算法，將數(shù)據(jù)均勻劃分至各處理機(jī)，然后對(duì)傳統(tǒng)嵌套循環(huán)算法進(jìn)行優(yōu)化，實(shí)現(xiàn)分布式的離群點(diǎn)計(jì)算過(guò)程. 文獻(xiàn)[11]首先提出了GBP數(shù)據(jù)劃分方法，利用網(wǎng)格空間索引結(jié)構(gòu)對(duì)數(shù)據(jù)進(jìn)行管理和劃分，然后基于GBP劃分方法給出分布式離群點(diǎn)檢測(cè)算法DLC. 同樣地，針對(duì)同一離群點(diǎn)定義，文獻(xiàn)[12]也提出了相應(yīng)的分布式離群點(diǎn)計(jì)算方法，在處理具有偏態(tài)分布的數(shù)據(jù)集時(shí)非常有效. 文獻(xiàn)[13]首先提出了BDSP數(shù)據(jù)劃分算法，可以有效均衡各計(jì)算節(jié)點(diǎn)的工作負(fù)載，同時(shí)實(shí)現(xiàn)良好的過(guò)濾效果，然后利用BDSP方法提出基于距離的分布式離群點(diǎn)檢測(cè)算法BOD，有效減少網(wǎng)絡(luò)開(kāi)銷，縮短了離群點(diǎn)的計(jì)算時(shí)間. 此外，文獻(xiàn)[14]還給出了利用GPU并行地計(jì)算離群點(diǎn)的策略.

雖然已有一些優(yōu)秀的分布式離群點(diǎn)檢測(cè)方法，但這些方法都是針對(duì)同構(gòu)分布式環(huán)境設(shè)計(jì)的，在異構(gòu)分布式環(huán)境中無(wú)法保證高效的離群點(diǎn)檢測(cè)效率.

2? ?問(wèn)題描述

本文主要研究在異構(gòu)分布式環(huán)境中，如何并行地計(jì)算出數(shù)據(jù)集內(nèi)所有基于距離的離群點(diǎn). 下面，具體地給出基于距離的離群點(diǎn)的形式化定義，其中，表1列出了本文使用的符號(hào)及其含義.

一般地，給定一個(gè)具有d維屬性值的數(shù)據(jù)集合P. 對(duì)于P中任一數(shù)據(jù)點(diǎn)p可表示為： p

p[3]，…，p[d]>，那么對(duì)于數(shù)據(jù)集P中任意兩個(gè)數(shù)據(jù)點(diǎn)p1和p2之間的歐式距離的計(jì)算公式為：

3? ?異構(gòu)分布式中的離群點(diǎn)查詢處理框架

本文主要針對(duì)異構(gòu)分布式環(huán)境，其整體上包含一臺(tái)主控制節(jié)點(diǎn)和數(shù)目固定的多個(gè)從節(jié)點(diǎn)C = {c1，c2，…，cn }. 由于各節(jié)點(diǎn)間數(shù)據(jù)遷移量較小，本文不考慮網(wǎng)絡(luò)異構(gòu)，其異構(gòu)環(huán)境特指每個(gè)參與計(jì)算的從節(jié)點(diǎn)的配置各不相同，使得它們?cè)谟?jì)算能力上存在差異. 另外，主控節(jié)點(diǎn)和每一個(gè)從節(jié)點(diǎn)都通過(guò)網(wǎng)絡(luò)互連，可以進(jìn)行網(wǎng)絡(luò)通信. 每?jī)蓚€(gè)相鄰的從節(jié)點(diǎn)之間也可相互通信. 為了防止主控節(jié)點(diǎn)在計(jì)算過(guò)程中發(fā)生擁塞，在數(shù)據(jù)劃分時(shí)將不給主控節(jié)點(diǎn)分配計(jì)算任務(wù)，即在整個(gè)基于距離的離群點(diǎn)計(jì)算過(guò)程中，主控節(jié)點(diǎn)主要負(fù)責(zé)計(jì)算任務(wù)的調(diào)度，大部分的離群點(diǎn)計(jì)算任務(wù)都將由從節(jié)點(diǎn)完成.

根據(jù)圖1中的查詢處理框架，異構(gòu)分布式環(huán)境中的基于距離的離群點(diǎn)檢測(cè)任務(wù)可以被描述為：對(duì)于給定的數(shù)據(jù)集合P、查詢距離閾值r和查詢數(shù)量閾值k，通過(guò)充分利用異構(gòu)分布式計(jì)算框架中各異構(gòu)處理機(jī)的計(jì)算能力，快速地計(jì)算出給定數(shù)據(jù)集合P中的所有基于距離的離群點(diǎn).

具體地，整個(gè)過(guò)程大致可分為3個(gè)階段：

1）數(shù)據(jù)劃分階段. 對(duì)于給定數(shù)據(jù)集P，主控制節(jié)點(diǎn)首先依據(jù)各異構(gòu)處理機(jī)的計(jì)算能力的不同對(duì)數(shù)據(jù)集進(jìn)行劃分，然后將劃分后的子數(shù)據(jù)集發(fā)送至相應(yīng)的處理機(jī).

2）局部離群點(diǎn)計(jì)算階段. 各個(gè)參與計(jì)算的處理

機(jī)在接收到對(duì)應(yīng)的數(shù)據(jù)子集合后，在本地進(jìn)行局部計(jì)算，得到局部離群點(diǎn)，最后將它們發(fā)送到主控制節(jié)點(diǎn).

3）全局離群點(diǎn)計(jì)算階段. 主控制節(jié)點(diǎn)根據(jù)接收

到的局部離群點(diǎn)的位置信息判斷其需要通信的從節(jié)點(diǎn)，然后將它們發(fā)送到相應(yīng)處理機(jī)再次進(jìn)行距離計(jì)算，得出最終的全局離群點(diǎn).

4? ?基于網(wǎng)格的動(dòng)態(tài)數(shù)據(jù)劃分方法

在離群點(diǎn)檢測(cè)之前，對(duì)數(shù)據(jù)集進(jìn)行有效的劃分，可以顯著提高離群點(diǎn)檢測(cè)效率. 本文提出的基于網(wǎng)格的動(dòng)態(tài)數(shù)據(jù)劃分方法GDDP保證了計(jì)算資源的充分利用，具有較高的負(fù)載均衡性.

4.1? ?計(jì)算能力評(píng)估

在分布式計(jì)算系統(tǒng)中為了能夠?qū)崿F(xiàn)整個(gè)系統(tǒng)的高可用性，一般需要實(shí)現(xiàn)各個(gè)參與計(jì)算的處理機(jī)之間負(fù)載均衡. 在異構(gòu)分布式環(huán)境中，各處理機(jī)間的計(jì)算能力不同，為了能對(duì)計(jì)算任務(wù)進(jìn)行合理的分配，需要對(duì)每個(gè)處理機(jī)的計(jì)算能力進(jìn)行評(píng)估.

首先，查詢處理框架中的主控制節(jié)點(diǎn)會(huì)將相同的一份測(cè)試數(shù)據(jù)集發(fā)送給每個(gè)參與計(jì)算的從節(jié)點(diǎn)，進(jìn)行相同的任務(wù)計(jì)算，然后記錄每個(gè)處理機(jī)完成任務(wù)的時(shí)間. 其中，處理機(jī)完成任務(wù)的時(shí)間越短，說(shuō)明其計(jì)算能力越強(qiáng);反之，其計(jì)算能力越弱.

為了便于后續(xù)基于網(wǎng)格的數(shù)據(jù)集的劃分，本文給出一種有效的評(píng)分機(jī)制. 首先，將工作節(jié)點(diǎn)的計(jì)算能力劃分為m個(gè)等級(jí)，即β1，β2，…，βm，對(duì)應(yīng)得分分別為1，2，3，…，m，相應(yīng)的工作節(jié)點(diǎn)的計(jì)算能力依次增強(qiáng);其次，求出每個(gè)從節(jié)點(diǎn)的計(jì)算能力與當(dāng)前最大計(jì)算能力的比值，所得結(jié)果在（0，1]內(nèi)，其中，將（0，1]劃分為m等份，表示（0，1/m]，（1/m，2/m]，…，（m-1/m，1]，所得比值在各區(qū)間內(nèi)的處理機(jī)的等級(jí)分別為β1，β2，…，βm;最后，根據(jù)每臺(tái)處理機(jī)的計(jì)算能力等級(jí)得出相應(yīng)的評(píng)分. 例如，在一個(gè)異構(gòu)分布式系統(tǒng)中有c1～c5 5臺(tái)從節(jié)點(diǎn)，為簡(jiǎn)化示例，此處等級(jí)數(shù)m=4，由以上方法得出各處理機(jī)的計(jì)算能力評(píng)估表如表2所示.

4.2? ?數(shù)據(jù)集劃分

傳統(tǒng)的數(shù)據(jù)劃分方法對(duì)維度過(guò)高的數(shù)據(jù)集進(jìn)行處理時(shí)，會(huì)產(chǎn)生巨量的劃分子塊，致使檢測(cè)效率低下，由此本文決定對(duì)給定的多維數(shù)據(jù)集中數(shù)據(jù)分布最均勻的二維空間利用網(wǎng)格進(jìn)行數(shù)據(jù)劃分，經(jīng)數(shù)據(jù)劃分后會(huì)形成多個(gè)二維的數(shù)據(jù)子塊.

首先確定數(shù)據(jù)集中每一維數(shù)據(jù)需劃分為幾段. 考慮在異構(gòu)分布式環(huán)境中，各從節(jié)點(diǎn)的計(jì)算能力不同，由此具體的劃分段數(shù)為：

其中，comp_Grade（ci）表示處理機(jī)ci的計(jì)算能力得分，n表示處理機(jī)的數(shù)目. 例如，根據(jù)表2中對(duì)5臺(tái)異構(gòu)處理機(jī)c1 ～ c5計(jì)算能力的評(píng)估結(jié)果，結(jié)合公式（2）可得劃分段數(shù)Segment值為4，因此，數(shù)據(jù)集將被映射到一個(gè)4×4規(guī)模的網(wǎng)格結(jié)構(gòu)內(nèi).

其次，為了判斷數(shù)據(jù)在哪個(gè)維度上分布最均勻，本文給出一種衡量標(biāo)準(zhǔn). 具體地，數(shù)據(jù)在第d維上分布的均勻程度為：

single_U（d）的值越小，說(shuō)明數(shù)據(jù)在第d維上分布越均勻. 其中，num（segment（i））表示數(shù)據(jù)在第d維上的第i個(gè)劃分段內(nèi)的實(shí)際分布數(shù)量;μ表示數(shù)據(jù)在第d維上每個(gè)劃分段數(shù)內(nèi)的平均分布數(shù)量，它等于數(shù)據(jù)集的大小與劃分段數(shù)Segment的比值;n取值為劃分段數(shù)Segment的值.

接下來(lái)，數(shù)據(jù)在由d1和d2維所組成的二維空間內(nèi)的分布均勻程度用multi_U（d1，d2）來(lái)描述. 同樣地，multi_U（d1，d2）的值越小，表明數(shù)據(jù)在該二維空間內(nèi)分布越均勻. 具體地，multi_U（d1，d2）的計(jì)算公式表示為：

式中：num（gi）表示數(shù)據(jù)在當(dāng)前d1和d2維空間內(nèi)所建立的網(wǎng)格索引中第i個(gè)網(wǎng)格內(nèi)的實(shí)際分布數(shù)量;n表示二維網(wǎng)格中網(wǎng)格的數(shù)目，其值等于劃分段數(shù)Segment的平方;μ表示數(shù)據(jù)在每個(gè)網(wǎng)格內(nèi)的平均分布數(shù)據(jù)，其值等于數(shù)據(jù)集的總量與網(wǎng)格數(shù)目的比值.

由以上數(shù)據(jù)分布均勻程度的兩個(gè)衡量過(guò)程，可確定給定數(shù)據(jù)集中數(shù)據(jù)分布最均勻的二維空間，從而完成數(shù)據(jù)集的劃分. 具體地，對(duì)于給定的具有d個(gè)維度的數(shù)據(jù)集的劃分過(guò)程大致為：首先，根據(jù)劃分段數(shù)Segment將數(shù)據(jù)集的每一維度劃分成s個(gè)區(qū)間，然后統(tǒng)計(jì)數(shù)據(jù)在每個(gè)區(qū)間內(nèi)的分布情況，并根據(jù)計(jì)算得出數(shù)據(jù)在每一維上的single_U（d）值，選擇single_U（d）值最小的 [] 個(gè)數(shù)據(jù)維度作為候選目標(biāo);其次，在候選維度里面，根據(jù)劃分段數(shù)Segment，依次選取兩個(gè)維度建立二維網(wǎng)格，并評(píng)估數(shù)據(jù)在二維網(wǎng)格內(nèi)的分布情況;最終，根據(jù)multi_U（d1，d2）值最小的二個(gè)維度上對(duì)應(yīng)的網(wǎng)格對(duì)數(shù)據(jù)集進(jìn)行劃分，可以得到多個(gè)不相交的劃分?jǐn)?shù)據(jù)子塊.

4.3? ?數(shù)據(jù)塊的分配

當(dāng)數(shù)據(jù)集被分成多個(gè)不相交的數(shù)據(jù)子塊后，緊接著需將其合理地分配到各異構(gòu)的從節(jié)點(diǎn)上.

4.3.1? ?分配順序

根據(jù)基于距離的離群點(diǎn)定義，為了減少分布式計(jì)算過(guò)程中各處理機(jī)之間的通信代價(jià)，需要將空間中鄰近的數(shù)據(jù)點(diǎn)盡量分配到同一臺(tái)工作節(jié)點(diǎn)上. 因此，在數(shù)據(jù)塊的分配過(guò)程中首先需要考慮數(shù)據(jù)集劃分后各數(shù)據(jù)塊之間的相鄰關(guān)系，這樣才能盡可能將空間中相鄰的數(shù)據(jù)對(duì)象分配到同一臺(tái)工作節(jié)點(diǎn)上. 由于劃分時(shí)用到的是二維網(wǎng)格，本文則按照網(wǎng)格的行序?qū)⑾噜彽臄?shù)據(jù)塊依次進(jìn)行分配即可保證數(shù)據(jù)塊之間是相鄰的，如圖2中箭頭所指方向即為數(shù)據(jù)塊的分配順序.

4.3.2? ?分配規(guī)則

在本文所指的異構(gòu)分布式環(huán)境中，對(duì)于參與計(jì)算的異構(gòu)處理機(jī)，按照其計(jì)算能力由大到小順序排列，之后優(yōu)先選擇計(jì)算能力強(qiáng)的處理機(jī)進(jìn)行數(shù)據(jù)塊的分配. 如下算法1給出了具體的數(shù)據(jù)塊分配過(guò)程.

經(jīng)過(guò)上述分配過(guò)程，可以完成數(shù)據(jù)集中大多數(shù)數(shù)據(jù)的初分配，并且分配后大多數(shù)處理機(jī)都能獲得小于等于其實(shí)際所需的數(shù)據(jù)量.

例如，給定多維數(shù)據(jù)集P，且|P|=120. 如表2所示，有5臺(tái)異構(gòu)的從節(jié)點(diǎn)參與離群點(diǎn)的計(jì)算，對(duì)應(yīng)的c1～c5處理機(jī)順序?yàn)椋篶2、c4、c1、c3、c5. 圖3所示為數(shù)據(jù)集劃分的結(jié)果，則數(shù)據(jù)塊的分配順序?yàn)閎1～b16 . 首先對(duì)處理機(jī)c2進(jìn)行數(shù)據(jù)塊分配，計(jì)算可得其所需數(shù)據(jù)量為×120 = 40. 優(yōu)先處理數(shù)據(jù)塊b1，由于塊內(nèi)數(shù)據(jù)量5小于c2當(dāng)前所需數(shù)據(jù)量40，則將b2分配給處理機(jī)c2，同時(shí)更新c2當(dāng)前所需數(shù)據(jù)量為35，最終，數(shù)據(jù)塊b1、b2、b3、b4、b5都可被分配給c2，當(dāng)對(duì)數(shù)據(jù)塊b6進(jìn)行分配時(shí)，由于處理機(jī)c2目前所需要的數(shù)據(jù)量為1，小于數(shù)據(jù)塊b6的數(shù)據(jù)量，所以停止對(duì)處理機(jī)c2的數(shù)據(jù)塊分配. 同理，可依次完成處理機(jī)c4、c1、c3、c5的數(shù)據(jù)塊分配任務(wù).

具體的分配結(jié)果如表3所示. 這樣經(jīng)過(guò)數(shù)據(jù)塊的分配后，只有處理機(jī)c5所分配的數(shù)據(jù)量略大于它實(shí)際所需要的數(shù)據(jù)量. 同時(shí)，只有數(shù)據(jù)塊b16未被分配，把它暫時(shí)留在主控制處理機(jī)上.

4.4? ?動(dòng)態(tài)數(shù)據(jù)分配

動(dòng)態(tài)分配旨在對(duì)存儲(chǔ)于主控制節(jié)點(diǎn)上的剩余的未被分配的數(shù)據(jù)塊進(jìn)行數(shù)據(jù)分配. 為了對(duì)空閑處理機(jī)進(jìn)行準(zhǔn)確的任務(wù)分配，主控制節(jié)點(diǎn)需記錄從開(kāi)始執(zhí)行計(jì)算任務(wù)到有空閑節(jié)點(diǎn)出現(xiàn)所經(jīng)過(guò)的時(shí)間，即當(dāng)前空閑的處理機(jī)ci完成初始的分配任務(wù)的時(shí)間t，以及在處理時(shí)間t內(nèi)每個(gè)處理機(jī)已經(jīng)處理的數(shù)據(jù)量complete_num（ci），由此可計(jì)算出各處理機(jī)在當(dāng)前所劃分的數(shù)據(jù)集中進(jìn)行離群點(diǎn)檢測(cè)任務(wù)時(shí)的實(shí)時(shí)處理速度vi（其中，vi = ）;同時(shí)，用當(dāng)前未被處理的數(shù)據(jù)總量除以各處理機(jī)處理速度之和還可預(yù)估出剩余的所有計(jì)算任務(wù)完成的時(shí)間T;最后，將時(shí)間T和空閑處理機(jī)的實(shí)時(shí)處理速度vi相乘，即可得出當(dāng)前空閑工作節(jié)點(diǎn)所應(yīng)分配的數(shù)據(jù)量. 當(dāng)存儲(chǔ)在主控制節(jié)點(diǎn)上的數(shù)據(jù)都被分配后，動(dòng)態(tài)分配過(guò)程結(jié)束.

這種動(dòng)態(tài)數(shù)據(jù)分配方法依據(jù)各處理機(jī)的實(shí)際處理速度進(jìn)行計(jì)算任務(wù)的分配，盡可能地避免了空閑處理機(jī)的等待，并充分利用了整個(gè)異構(gòu)分布式環(huán)境中各處理機(jī)的計(jì)算資源，加快了離群點(diǎn)的檢測(cè)速度.

5? ?GODA算法描述

本節(jié)主要描述了GODA算法的具體細(xì)節(jié). 整個(gè)過(guò)程分為2個(gè)階段：1）本地離群點(diǎn)計(jì)算，即利用每個(gè)處理機(jī)的計(jì)算能力計(jì)算出本地離群點(diǎn);2）全局離群點(diǎn)計(jì)算，即通過(guò)全局通信確定最終離群點(diǎn)結(jié)果集.

5.1? ?本地離群點(diǎn)計(jì)算

本小節(jié)主要闡述GODA算法中一種有效的面向多維大規(guī)模數(shù)據(jù)集的本地離群點(diǎn)計(jì)算方法.

5.1.1? ?索引構(gòu)建

由于網(wǎng)格索引、R樹(shù)索引等一般的空間索引無(wú)法應(yīng)對(duì)數(shù)據(jù)集維度的增長(zhǎng)，并且根據(jù)離群點(diǎn)的形象化描述，在給定的數(shù)據(jù)集中，大部分?jǐn)?shù)據(jù)點(diǎn)都是非離群點(diǎn)，而離群點(diǎn)只占據(jù)數(shù)據(jù)集的很少一部分，因此，本文索引構(gòu)建采用如下方法.

在給定數(shù)據(jù)集中隨機(jī)選取一個(gè)數(shù)據(jù)點(diǎn)p，其中，點(diǎn)p在很大程度上為非離群點(diǎn)，以點(diǎn)p為中心，計(jì)算數(shù)據(jù)集中其他數(shù)據(jù)點(diǎn)到點(diǎn)p的距離，依據(jù)距點(diǎn)p由近及遠(yuǎn)的順序?qū)?shù)據(jù)進(jìn)行管理，如果數(shù)據(jù)點(diǎn)q距離中心點(diǎn)p很遠(yuǎn)，則說(shuō)明點(diǎn)q很可能是離群點(diǎn).

5.1.2? ?本地離群點(diǎn)計(jì)算方法描述

首先，對(duì)于給定數(shù)據(jù)集P中的數(shù)據(jù)點(diǎn)p，自定義數(shù)據(jù)結(jié)構(gòu)node如下：

1）給定數(shù)據(jù)集P中的一個(gè)數(shù)據(jù)點(diǎn)p;

2）數(shù)據(jù)點(diǎn)p在給定數(shù)據(jù)集P中的唯一標(biāo)識(shí)，用

p.id表示;

3）數(shù)據(jù)點(diǎn)p在給定數(shù)據(jù)集P中的鄰居情況，用

p.nn表示;

4）數(shù)據(jù)點(diǎn)p與其第k個(gè)近鄰點(diǎn)的距離，用p.r表示.

其中，p.nn是一個(gè)大小為k（用戶給定的查詢數(shù)量閾值）的列表，用于存儲(chǔ)數(shù)據(jù)集P中與數(shù)據(jù)點(diǎn)p的距離不大于用戶給定的查詢距離閾值r的數(shù)據(jù)點(diǎn)q的標(biāo)識(shí)以及點(diǎn)q與點(diǎn)p間的距離dist（p，q）;對(duì)于p.r，當(dāng)p.nn的大小為k時(shí)，p.r等于存儲(chǔ)在p.nn中最大的距離值;當(dāng)p.nn的大小小于k時(shí)，p.r的值被設(shè)為+∞.

在離群點(diǎn)計(jì)算過(guò)程中，根據(jù)點(diǎn)p的node結(jié)構(gòu)中p.r的值與查詢距離閾值r的大小關(guān)系即可判斷當(dāng)前數(shù)據(jù)點(diǎn)p是否為離群點(diǎn). 例如，若p.r的值小于等于查詢距離閾值r，那么數(shù)據(jù)點(diǎn)p是非離群點(diǎn);若p.nn列表未存滿，且p.r取值為+∞，則點(diǎn)p是離群點(diǎn).

根據(jù)上述自定義的node結(jié)構(gòu)，給出非離群點(diǎn)過(guò)濾定理.

定理1? ?對(duì)于當(dāng)前掃描到的數(shù)據(jù)集P中的數(shù)據(jù)點(diǎn)q，如果它和內(nèi)存中存儲(chǔ)的數(shù)據(jù)點(diǎn)p之間的距離滿足dist（p，q）≤r-p.r，則數(shù)據(jù)點(diǎn)q為非離群點(diǎn).

證? ?根據(jù)dist（p，q）≤r-p.r可得p.r≤r，則說(shuō)明內(nèi)存中的數(shù)據(jù)點(diǎn)p為非離群點(diǎn)，且在p.r范圍內(nèi)數(shù)據(jù)點(diǎn)p的鄰居個(gè)數(shù)至少為k個(gè). 又因?yàn)閿?shù)據(jù)點(diǎn)p和數(shù)據(jù)點(diǎn)q之間的距離滿足dist（p，q）+ p.r≤ r，則說(shuō)明數(shù)據(jù)點(diǎn)p及其鄰居都是數(shù)據(jù)點(diǎn)q的鄰居，也即數(shù)據(jù)點(diǎn)q的鄰居個(gè)數(shù)大于給定的數(shù)量閾值k，因此根據(jù)基于距離的離群點(diǎn)定義可得數(shù)據(jù)點(diǎn)q為非離群點(diǎn).?? ? ? ? 證畢.

根據(jù)索引中數(shù)據(jù)點(diǎn)的順序及定理1中的過(guò)濾規(guī)則，每個(gè)處理機(jī)通過(guò)掃描兩次數(shù)據(jù)集可實(shí)現(xiàn)本地離群點(diǎn)的計(jì)算過(guò)程. 算法2給出了本地離群點(diǎn)檢測(cè)的具體過(guò)程.

算法2? ?本地離群點(diǎn)檢測(cè)算法.

輸入：查詢距離閾值r，查詢數(shù)量閾值k，本地存儲(chǔ)的數(shù)據(jù)集P;

輸出：本地離群點(diǎn)集合

1. 初始化隊(duì)列H為空;

2. FOR 數(shù)據(jù)集P中的每個(gè)數(shù)據(jù)點(diǎn)p? DO

3.? ? 初始化p的信息，p.nn為空，p.r為+∞;

4.? ? IF H為空 或者 IsNoInlier（p）? THEN

5.? ? ? ?將數(shù)據(jù)點(diǎn)p加入到隊(duì)列H中;

6.? ? ENDIF

7. ENDFOR

8. FOR H中的每一個(gè)數(shù)據(jù)點(diǎn)q DO

9.? ? 將滿足q.r不大于查詢半徑r的數(shù)據(jù)點(diǎn)從H中刪除;

10. ENDFOR

11. FOR 數(shù)據(jù)集P中的每個(gè)數(shù)據(jù)點(diǎn)p? DO

12.? ? DeleteInlier（p）;

13. ENDFOR

14. 隊(duì)列H中的數(shù)據(jù)點(diǎn)全部都是離群點(diǎn)，輸出;

第一次掃描數(shù)據(jù)集時(shí)，需要將當(dāng)前掃描到的不能確定是非離群點(diǎn)的數(shù)據(jù)點(diǎn)的node結(jié)構(gòu)存儲(chǔ)到內(nèi)存中，以致于第一次掃描結(jié)束后，內(nèi)存中至少存儲(chǔ)著所有的本地離群點(diǎn)的信息. 由此，判定數(shù)據(jù)點(diǎn)p不是非離群點(diǎn)的IsNoInlier（p）函數(shù)的算法如下：

IsNoInlier（）

輸入：查詢距離閾值r，查詢數(shù)量閾值k，查詢數(shù)據(jù)點(diǎn)p，隊(duì)列H;

輸出：數(shù)據(jù)點(diǎn)p的查詢結(jié)果

1. FOR H中的每一個(gè)數(shù)據(jù)點(diǎn)q? DO

2.? ? IF dist（p，q）≤r-p.r? THEN

3.? ? ? 數(shù)據(jù)點(diǎn)p為非離群點(diǎn)，返回FALSE;

4.? ? ? BREAK;

5.? ? ENDIF

6.? ? IF dist（p，q）≤r THEN

7.? ? ? 利用臨時(shí)變量oldr記錄數(shù)據(jù)點(diǎn)q的q.r值，并將p更新到q的

q.nn列表中;

8.? ? ? IF oldr>r 并且 q.r≤r THEN

9.? ? ? ? 以0.5的概率將數(shù)據(jù)點(diǎn)q從H中刪除;

10.? ? ? ENDIF

11.? ? ? 將q更新到p的p.nn列表中;

12.? ? ? IF p.r≤r? THEN

13.? ? ? ? 數(shù)據(jù)點(diǎn)p為非離群點(diǎn)，返回FALSE;

14.? ? ? ENDIF

15.? ? ENDIF

16. ENDFOR

17. IF p.r>r THEN

18.? ? 返回TRUE;

19. ENDIF

第二次掃描數(shù)據(jù)集時(shí)，即從所有的候選本地離群點(diǎn)集合中找出真正的本地離群點(diǎn)，其中，刪除內(nèi)存中非離群點(diǎn)的DeleteInlier（p）函數(shù)的算法如下：

DeleteInlier（）

輸入：查詢距離閾值r，查詢數(shù)量閾值k，數(shù)據(jù)點(diǎn)p，隊(duì)列H;

輸出：隊(duì)列H

1. FOR H中的每一個(gè)數(shù)據(jù)點(diǎn)q? DO

2.? ? IF dist（p，q）≤r THEN

3.? ? ? 將p更新到q的q.nn列表中;

4.? ? ? IF q.r≤r THEN

5.? ? ? ? 將數(shù)據(jù)點(diǎn)q從隊(duì)列H中刪除;

6.? ? ? ENDIF

7.? ? ENDIF

8. ENDFOR

總體上，本小節(jié)基于距離的本地離群點(diǎn)計(jì)算方法可以通過(guò)掃描較少次數(shù)的數(shù)據(jù)集完成離群點(diǎn)的檢測(cè)過(guò)程，在一定程度上減少了IO代價(jià)，同時(shí)，還可以很好地應(yīng)對(duì)數(shù)據(jù)集中數(shù)據(jù)維數(shù)的增長(zhǎng).

復(fù)雜度分析：記本地?cái)?shù)據(jù)集的大小為N. 對(duì)于本地離群點(diǎn)的計(jì)算，構(gòu)建索引所需時(shí)間復(fù)雜度為O（N·lgN），兩次掃描數(shù)據(jù)集所需的時(shí)間復(fù)雜度為O（|H|·N）. 因此，算法2的時(shí)間復(fù)雜度為O（N·lgN+|H|·N）.

5.2? ?全局離群點(diǎn)計(jì)算

在完成5.1節(jié)的計(jì)算之后，本地離群點(diǎn)被發(fā)送到主控制節(jié)點(diǎn)形成離群點(diǎn)候選集，此后由主控制節(jié)點(diǎn)判斷其所需進(jìn)行網(wǎng)絡(luò)通信的處理機(jī)，進(jìn)而計(jì)算出真正的離群點(diǎn).

對(duì)于給定的數(shù)據(jù)集P，利用GDDP劃分方法對(duì)數(shù)據(jù)分布最均勻的二維空間（假設(shè)是d1和d2維所

組成的空間）劃分后所得的數(shù)據(jù)塊b可表示為b =

[b.min，b.max]. 其中，b.min、b.max分別表示數(shù)據(jù)塊b的下界和上界，則對(duì)于數(shù)據(jù)塊b中的任意數(shù)據(jù)p，

都有b.min[d1]≤p[d1]≤b.max[d1]，b.min[d2]≤p[d2]≤

b.max[d2]. 進(jìn)一步，有如下引理：

引理1[15]? ?對(duì)于數(shù)據(jù)塊b中的任意本地離群點(diǎn)p，如果?i∈{d1，d2}，p[d1]-b.min[d1]>r且b.max[d2]-

p[d2]≥r，則數(shù)據(jù)點(diǎn)p是全局離群點(diǎn).

對(duì)于離群點(diǎn)候選集中滿足引理1的數(shù)據(jù)點(diǎn)p，可得出其一定是全局離群點(diǎn)，而對(duì)于候選集中剩余的非確定的本地離群點(diǎn)，需和其所在數(shù)據(jù)塊的相鄰數(shù)據(jù)塊進(jìn)行計(jì)算，以確定是否為真正的離群點(diǎn).

定義3? ?點(diǎn)與數(shù)據(jù)塊的最小距離.給定數(shù)據(jù)點(diǎn)p和數(shù)據(jù)塊b，則點(diǎn)p與塊b的最小距離：

min_dist（p，b） =? ? ? （5）

其中：

z[i] = b.min[i]-p[i]，b.min[i]>p[i]

p[i]-b.max[i]，p[i]>b.max[i]

0，其他? ? ? （6）

顯然，對(duì)于塊b的近鄰塊集合N（b）中的塊bi，若min_dist（p，bi）≤r，說(shuō)明塊bi中可能存在點(diǎn)p的近鄰，則將點(diǎn)p發(fā)送到Sb集合中，最終將Sb中的數(shù)據(jù)點(diǎn)發(fā)送到塊bi所在的處理機(jī)上. 算法3展示了具體的全局離群點(diǎn)計(jì)算過(guò)程.

算法3? ?全局離群點(diǎn)檢測(cè)算法.

輸入：數(shù)據(jù)塊b中的本地離群點(diǎn)集合Lb，數(shù)據(jù)塊b的近鄰塊集合

N（b），距離閾值r，數(shù)量閾值k;

輸出：本地離群點(diǎn)集合Lb中的全局離群點(diǎn)

1. FOR N（b）中的每一個(gè)數(shù)據(jù)塊bi DO

2.? ? 初始化集合Sb;

3.? ? FOR 本地離群點(diǎn)集合Lb中的每一個(gè)數(shù)據(jù)點(diǎn)p DO

4.? ? ? ?IF min_dist（p，bi）≤r THEN

5.? ? ? ? ?把數(shù)據(jù)點(diǎn)p加入到集合Sb中;

6.? ? ? ?ENDIF

7.? ? ENDFOR

8. 將集合Sb發(fā)送到數(shù)據(jù)塊bi所在的節(jié)點(diǎn)上;

9. ENDFOR

10. FOR Lb中的每個(gè)數(shù)據(jù)點(diǎn)p DO

11.? ? 根據(jù)各數(shù)據(jù)塊返回的結(jié)果，計(jì)算數(shù)據(jù)點(diǎn)p的近鄰數(shù)目 nn（p）;

12.? ? IF nn（p） < k THEN

13.? ? ? 將數(shù)據(jù)點(diǎn)p加入到全局離群點(diǎn)集合中;

14.? ? ENDIF

15. ENDFOR

復(fù)雜度分析：對(duì)于全局離群點(diǎn)的計(jì)算，記本地候選離群點(diǎn)的個(gè)數(shù)為η，根據(jù)公式（2）～（4）可將總數(shù)據(jù)集P劃分為b個(gè)數(shù)據(jù)塊，將本地候選離群點(diǎn)與相鄰數(shù)據(jù)塊中的數(shù)據(jù)點(diǎn)依次計(jì)算，因此，算法3的時(shí)間復(fù)雜度為O（η·（8/b）·|P|）. 不難發(fā)現(xiàn)，在分布式環(huán)境中，一個(gè)數(shù)據(jù)塊的相鄰塊通常分布在不同的處理機(jī)上，因此可以并行執(zhí)行離群點(diǎn)的計(jì)算，使得處理效率大大提高.

6? ?實(shí)驗(yàn)分析

6.1? ?實(shí)驗(yàn)環(huán)境

本文實(shí)驗(yàn)所搭建的異構(gòu)分布式計(jì)算系統(tǒng)共包含5臺(tái)處理機(jī)，其中1臺(tái)主控節(jié)點(diǎn)，4臺(tái)從節(jié)點(diǎn)，它們的具體配置如下.

主控制節(jié)點(diǎn)：Intel Core i3-7020U CPU，4GB內(nèi)存，500GB硬盤，操作系統(tǒng)為Windows 10;從節(jié)點(diǎn)1：Intel Core i5-8265U CPU，8GB內(nèi)存，256GB硬盤，操作系統(tǒng)為Windows 10;從節(jié)點(diǎn)2：Intel Pentium（R） 2020M 2.4 GHz CPU，4GB內(nèi)存，500GB硬盤，操作系統(tǒng)為Windows 10;從節(jié)點(diǎn)3：Intel Core i3 2100 3.1GHz CPU，8GB內(nèi)存，500GB硬盤，操作系統(tǒng)為Windows 10;從節(jié)點(diǎn)4：Intel Core i3-6006U CPU，4GB內(nèi)存，125GB硬盤，操作系統(tǒng)為Windows 10.

本文分別用真實(shí)數(shù)據(jù)集和合成數(shù)據(jù)集對(duì)所提出的GODA算法與PENL算法、BOD算法進(jìn)行對(duì)比實(shí)驗(yàn).

6.2? ?真實(shí)數(shù)據(jù)集中的實(shí)驗(yàn)結(jié)果分析

實(shí)驗(yàn)所用的真實(shí)數(shù)據(jù)集為森林覆蓋數(shù)據(jù)集Covertype，包含581 012條數(shù)據(jù)，每條數(shù)據(jù)有10個(gè)維度，每維屬性值的范圍為[0，100]. 表4和表5展示了3種算法在該數(shù)據(jù)集中的處理時(shí)間和通信量.

如表4和表5所示，本文提出的GODA算法采用了基于網(wǎng)格的動(dòng)態(tài)數(shù)據(jù)劃分方法GDDP，可以根據(jù)各從節(jié)點(diǎn)的計(jì)算能力進(jìn)行數(shù)據(jù)劃分，實(shí)現(xiàn)異構(gòu)分布式環(huán)境中各處理機(jī)的負(fù)載均衡，加快檢測(cè)效率;同時(shí)，考慮點(diǎn)的空間位置，將相鄰的點(diǎn)盡可能劃分至同一節(jié)點(diǎn)，大大節(jié)省了網(wǎng)絡(luò)開(kāi)銷. 相比之下，BOD算法和PENL算法主要針對(duì)同構(gòu)分布式環(huán)境，導(dǎo)致各節(jié)點(diǎn)數(shù)據(jù)分配不均衡，降低處理速度;PENL算法采用基于數(shù)據(jù)量的劃分方法，對(duì)于處理機(jī)的數(shù)據(jù)分配，都需與其他處理機(jī)上的數(shù)據(jù)集比較來(lái)確定最終結(jié)果，導(dǎo)致數(shù)據(jù)集重復(fù)傳輸，增加了網(wǎng)絡(luò)開(kāi)銷.

另一方面，通過(guò)對(duì)比表4和表5中1、2行的實(shí)驗(yàn)結(jié)果，可以發(fā)現(xiàn)，當(dāng)k不變，隨著距離閾值r的增大，數(shù)據(jù)集中離群點(diǎn)數(shù)目逐漸減少，GODA算法和BOD算法的處理時(shí)間和通信量也逐步減少. PENL算法的處理時(shí)間與這兩種算法趨勢(shì)相同，而通信量維持不變. 這主要是因?yàn)镻ENL算法需要將所有處理機(jī)上的數(shù)據(jù)集進(jìn)行兩兩之間的比較，網(wǎng)絡(luò)傳輸量與處理機(jī)的數(shù)目和數(shù)據(jù)集的規(guī)模有關(guān)，與查詢無(wú)關(guān). 通過(guò)對(duì)比3、4行實(shí)驗(yàn)結(jié)果可以看出，隨著查詢閾值k的增大，離群點(diǎn)的數(shù)目變多，導(dǎo)致GODA算法的處理時(shí)間和通信量都隨之增加. 但是，不管查詢閾值k和距離閾值r如何變化，與BOD算法和PENL算法相比，本文提出的GODA算法在異構(gòu)分布式環(huán)境中能更有效地進(jìn)行離群點(diǎn)的檢測(cè).

6.3? ?人工合成數(shù)據(jù)集中的實(shí)驗(yàn)結(jié)果分析

由于真實(shí)數(shù)據(jù)集規(guī)模有限，數(shù)據(jù)維度也無(wú)法變化，所以本節(jié)使用人工合成的數(shù)據(jù)集對(duì)3種算法進(jìn)行有效性驗(yàn)證. 首先，所使用的合成數(shù)據(jù)集為聚簇分布數(shù)據(jù)，各維取值范圍為0～10 000. 具體地，對(duì)于含有n個(gè)數(shù)據(jù)對(duì)象的數(shù)據(jù)集，隨機(jī)生成n/10 000個(gè)聚簇點(diǎn)，每個(gè)聚簇內(nèi)平均包含1 000個(gè)數(shù)據(jù)對(duì)象，并以聚簇點(diǎn)為中心呈高斯分布. 表6給出了實(shí)驗(yàn)相關(guān)變量的默認(rèn)值和變化范圍.

表6? ?人工合成數(shù)據(jù)集中的參數(shù)設(shè)置

Tab.6? ?Parameter settings in a synthetic dataset

[參數(shù) 默認(rèn)值 變化范圍 數(shù)據(jù)量 108 0.2 × 108 ～ 5 × 108 數(shù)據(jù)維度 10 8 ～ 16 查詢數(shù)量閾值k 50 40 ～ 60 查詢距離閾值r 16 14 ～ 18 ]

圖4描述了數(shù)據(jù)量對(duì)3種檢測(cè)算法的影響. 隨著數(shù)據(jù)量的增加，上述算法的處理時(shí)間都會(huì)變長(zhǎng)，對(duì)應(yīng)的通信量也隨之變多. 但通過(guò)對(duì)比可以發(fā)現(xiàn)，GODA算法和BOD算法的處理時(shí)間變化的速度較慢，而PENL算法的處理時(shí)間的增長(zhǎng)趨勢(shì)較快，也會(huì)增大網(wǎng)絡(luò)開(kāi)銷. 由此說(shuō)明GODA算法的查詢效率要高于BOD算法和PENL算法的查詢效率.

圖5顯示了數(shù)據(jù)維度對(duì)3種算法檢測(cè)效果的影響. 在圖5（a）中，隨著數(shù)據(jù)維度的升高，PENL算法和GODA算法的處理時(shí)間呈現(xiàn)出線性變化，而B(niǎo)OD算法處理時(shí)間的增長(zhǎng)趨勢(shì)明顯較快. 通過(guò)圖5（b）可以發(fā)現(xiàn)，3種算法的通信量都不受維度的影響.

圖6表述了查詢閾值k的變化對(duì)3種算法的影響. 在圖6（a）中，查詢閾值k增大時(shí)，3種算法的處理時(shí)間都變長(zhǎng)，這是因?yàn)閗增大，數(shù)據(jù)集中離群點(diǎn)數(shù)目增多，增加了算法的處理時(shí)間. 但與PENL算法相比，由于GODA算法和BOD算法在本地計(jì)算時(shí)良好的過(guò)濾措施，使其處理時(shí)間小于PENL算法. 通過(guò)圖6（b）可得，隨著查詢閾值k增大，PENL算法的通信量不變，而對(duì)于GODA算法和BOD算法，當(dāng)k增大，使得數(shù)據(jù)集中離群點(diǎn)的數(shù)目增多，從而使其通信量稍微增加.

圖7描述了距離閾值r的變化對(duì)3種算法性能的影響. 在圖7（a）中，當(dāng)距離閾值r不斷變大，數(shù)據(jù)集中離群點(diǎn)數(shù)目變少，使得所有算法的處理時(shí)間都變短. 由圖7（b）可以發(fā)現(xiàn)，隨著距離閾值r增大，PENL算法的通信量不變，而對(duì)于GODA算法和BOD算法，由于r變大，數(shù)據(jù)集中離群點(diǎn)數(shù)目減少，使其通信量也稍微變少.

通過(guò)上述對(duì)比實(shí)驗(yàn)，驗(yàn)證了本文提出的GODA算法的優(yōu)秀性能. 與PENL算法和BOD算法相比，GODA算法可以很好地解決異構(gòu)分布式環(huán)境中基于距離的離群點(diǎn)檢測(cè)問(wèn)題.

7? ?結(jié)? ?論

本文針對(duì)常見(jiàn)的異構(gòu)分布式環(huán)境中的離群點(diǎn)檢測(cè)問(wèn)題，首先，提出有效的數(shù)據(jù)劃分方法GDDP，保證了各處理機(jī)計(jì)算能力的充分利用，并通過(guò)考慮數(shù)據(jù)點(diǎn)的空間位置信息減少網(wǎng)絡(luò)通信. 其次，基于GDDP方法，提出了GODA算法，在每個(gè)處理機(jī)本地，通過(guò)構(gòu)建索引進(jìn)行數(shù)據(jù)管理，使用過(guò)濾規(guī)則進(jìn)行批量過(guò)濾，加快本地離群點(diǎn)計(jì)算. 再次，通過(guò)異構(gòu)分布式計(jì)算框架中各節(jié)點(diǎn)間的網(wǎng)絡(luò)通信，計(jì)算出全局離群點(diǎn). 最后，通過(guò)實(shí)驗(yàn)驗(yàn)證了GDDP和GODA算法的有效性.

參考文獻(xiàn)

[1]? ? KNORR E M，NG R T. Algorithms for mining distance-based outliers in large datasets[C]//Proceedings of the 24th International Conference on Very Large Data Bases. New York，USA，1998：392—403.

[2]? ? 鄭明玲，蔣句平，袁遠(yuǎn)，等.? 一種面向大規(guī)模計(jì)算機(jī)的監(jiān)控管理系統(tǒng)[J]. 湖南大學(xué)學(xué)報(bào)（自然科學(xué)版），2015，42（4）：107—113.

ZHENG M L，JIANG J P，YUAN Y，et al. A monitoring and management system for the large-scale computer[J].Journal of Hunan University（ Natural Sciences），2015，42（4）：107—113. （In Chinese）

[3]? ? ATKINSON A C，HAWKINS D M. Identification of outliers[J]. Biometrics，1981，37（4）：860.

[4]? ? FITRIANTO A，RANA S，MIDI H，et al. Effects of a single outlier on the coefficient of determination：An empirical study[J]. Empowering the Applications of Statistical and Mathematical Sciences，2015，1643：409—413.

[5]? ? WANG X T，SHEN D R，BAI M，et al. Cluster-based outlier detection using unsupervised extreme learning machines[C]//Proceedings of ELM-2015 Volume 1. Berlin：Springer International Publishing，2016：135—146.

[6]? ? BREUNIG M M，KRIEGEL H P，NG R T，et al. LOF：Identifying Density-Based Local Outliers[C]// Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data. Dallas，Texas，USA：ACM，2000：93—104.

[7]? ? BAY S D，SCHWABACHER M. Mining distance-based outliers in near linear time with randomization and a simple pruning rule[C]//Proceedings of the ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Texas，USA：ACM，2003：29—38.

[8]? ? YANG P，HUANG B. An efficient outlier mining algorithm for large dataset[C]// International Conference on Information Management. IEEE Computer Society，2008：41—46.

[9]? ? BUZZI-FERRARIS G ，MANENTI F . Outlier detection in large data sets[J]. Computers & Chemical Engineering，2011，35（2）：388—390.

[10]? HUNG E，CHEUNG D W. Parallel mining of outliers in large database[J]. Distributed and Parallel Databases，2002，12（1）：5—26.

[11]? BAI M，WANG X T，XIN J C，et al. An efficient algorithm for distributed density-based outlier detection on big data[J]. Neurocomputing，2016，181：19—28.

[12]? YAN Y Z，CAO L，KULHMAN C，et al. Distributed local outlier detection in big data[C]//Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Halifax，Canada，2017：1225—1234.

[13]? 王習(xí)特，申德榮，白梅，等. BOD：一種高效的分布式離群點(diǎn)檢測(cè)算法[J]. 計(jì)算機(jī)學(xué)報(bào)，2016，39（1）：36—51.

WANG X T，SHEN D R，BAI M，et al. BOD：An efficient algorithm for distributed outlier detection[J]. Chinese Journal of Computers，2016，39（1）：36—51. （In Chinese）

[14]? ANGIULLI F，BASTA S，LODI S，et al. GPU strategies for distance-based outlier detection[J]. IEEE Transactions on Parallel & Distributed Systems，2016，27（11）：3256—3268.

[15]? 王珊，王會(huì)舉，覃雄派，等. 架構(gòu)大數(shù)據(jù)：挑戰(zhàn)、現(xiàn)狀與展望[J]. 計(jì)算機(jī)學(xué)報(bào)，2011，34（10）：1741—1752.

WANG S，WANG H J，QIN X P，et al. Architecting Big data：challenges，studies and forecasts[J]. Chinese Journal of Computers，2011，34（10）：1741—1752. （In Chinese）