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

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

（大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院，遼寧大連 116000）

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

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

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

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

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

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

1 相關(guān)工作

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

1.1 集中式離群點檢測

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

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

1.2 分布式離群點檢測

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

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

2 問題描述

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

一般地，給定一個具有d 維屬性值的數(shù)據(jù)集合P.對于P 中任一數(shù)據(jù)點p 可表示為：p，那么對于數(shù)據(jù)集P 中任意兩個數(shù)據(jù)點p1和p2之間的歐式距離的計算公式為：

表1 符號列表Tab.1 List of symbols

定義1 （r-近鄰集合）.給定數(shù)據(jù)集合P 和用戶定義的查詢半徑r，點pi的近鄰集合是指P 中所有到pi的距離不大于r 的點的集合，即N（pi，r）={pj|pj∈P，dist（pi，pj）≤r}.

定義2 （（r，k）-離群點）.給定距離閾值r 和查詢鄰居閾值k，對于數(shù)據(jù)集P 中的任意一數(shù)據(jù)點p，若到數(shù)據(jù)點p 的距離小于等于r 的數(shù)據(jù)點個數(shù)小于k，即|N（pi，r）|

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

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

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

圖1 查詢處理框架Fig.1 Query processing framework

具體地，整個過程大致可分為3 個階段：

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

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

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

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

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

4.1 計算能力評估

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

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

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

表2 處理機(jī)的計算能力評估Tab.2 Evaluation of the calculation ability of the processors

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

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

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

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

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

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

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

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

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

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

4.3.1 分配順序

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

圖2 數(shù)據(jù)塊的分配順序Fig.2 The allocated order of data blocks

4.3.2 分配規(guī)則

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

算法1 數(shù)據(jù)塊分配算法.

輸入：數(shù)據(jù)塊集合B={b1，b2，…，bb}，從節(jié)點集合C={c1，c2，…，cn}；

輸出：分配給每個從節(jié)點的數(shù)據(jù)塊集合

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

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

圖3 數(shù)據(jù)集劃分結(jié)果Fig.3 The partition result of the data set

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

表3 分配結(jié)果Tab.3 Allocation result

4.4 動態(tài)數(shù)據(jù)分配

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

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

5 GODA 算法描述

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

5.1 本地離群點計算

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

5.1.1 索引構(gòu)建

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

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

5.1.2 本地離群點計算方法描述

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

1）給定數(shù)據(jù)集P 中的一個數(shù)據(jù)點p；

2）數(shù)據(jù)點p 在給定數(shù)據(jù)集P 中的唯一標(biāo)識，用p.id 表示；

3）數(shù)據(jù)點p 在給定數(shù)據(jù)集P 中的鄰居情況，用p.nn 表示；

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

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

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

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

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

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

證畢.

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

算法2 本地離群點檢測算法.

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

輸出：本地離群點集合

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

IsNoInlier（）

輸入：查詢距離閾值r，查詢數(shù)量閾值k，查詢數(shù)據(jù)點p，隊列H；

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

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

DeleteInlier（）

輸入：查詢距離閾值r，查詢數(shù)量閾值k，數(shù)據(jù)點p，隊列H；

輸出：隊列H

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

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

5.2 全局離群點計算

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

對于給定的數(shù)據(jù)集P，利用GDDP 劃分方法對數(shù)據(jù)分布最均勻的二維空間（假設(shè)是d1和d2維所組成的空間）劃分后所得的數(shù)據(jù)塊b 可表示為b=[b.min，b.max].其中，b.min、b.max 分別表示數(shù)據(jù)塊b的下界和上界，則對于數(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]對于數(shù)據(jù)塊b 中的任意本地離群點p，如果?i∈{d1，d2}，p[d1]-b.min[d1]＞r 且b.max[d2]-p[d2]≥r，則數(shù)據(jù)點p 是全局離群點.

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

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

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

算法3 全局離群點檢測算法.

輸入：數(shù)據(jù)塊b 中的本地離群點集合Lb，數(shù)據(jù)塊b 的近鄰塊集合N（b），距離閾值r，數(shù)量閾值k；

輸出：本地離群點集合Lb中的全局離群點

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

6 實驗分析

6.1 實驗環(huán)境

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

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

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

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

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

表4 真實數(shù)據(jù)集中的處理時間Tab.4 Processing time in real data sets

表5 真實數(shù)據(jù)集中的通信量Tab.5 Traffic in real data sets

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

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

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

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

表6 人工合成數(shù)據(jù)集中的參數(shù)設(shè)置Tab.6 Parameter settings in a synthetic dataset

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

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

圖4 數(shù)據(jù)量的影響Fig.4 The effect of data volume

圖5 維度的影響Fig.5 The effect of dimensionality

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

圖6 查詢閾值k 的影響Fig.6 The effect of query threshold k

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

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

圖7 距離閾值r 的影響Fig.7 The effect of distance threshold r

7 結(jié)論

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