王習特 朱宗梅 于雪蘋 白梅

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

關鍵詞：離群點檢測;異構分布式;網(wǎng)格;數(shù)據(jù)劃分

中圖分類號：TP391 ? ? ? ? ? ? ? ? ? ? ? ? ? 文獻標志碼：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

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

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

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

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

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

1? ?相關工作

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

1.1? ?集中式離群點檢測

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

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

1.2? ?分布式離群點檢測

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

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

2? ?問題描述

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

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

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

3? ?異構分布式中的離群點查詢處理框架

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

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

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

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

2）局部離群點計算階段. 各個參與計算的處理

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

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

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

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

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

4.1? ?計算能力評估

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

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

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

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

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

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

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

其次，為了判斷數(shù)據(jù)在哪個維度上分布最均勻，本文給出一種衡量標準. 具體地，數(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ù)在當前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ù)維度作為候選目標;其次，在候選維度里面，根據(jù)劃分段數(shù)Segment，依次選取兩個維度建立二維網(wǎng)格，并評估數(shù)據(jù)在二維網(wǎng)格內(nèi)的分布情況;最終，根據(jù)multi_U（d1，d2）值最小的二個維度上對應的網(wǎng)格對數(shù)據(jù)集進行劃分，可以得到多個不相交的劃分數(shù)據(jù)子塊.

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

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

4.3.1? ?分配順序

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

4.3.2? ?分配規(guī)則

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

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

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

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

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

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

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

5? ?GODA算法描述

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

5.1? ?本地離群點計算

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

5.1.1? ?索引構建

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

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

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

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

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

2）數(shù)據(jù)點p在給定數(shù)據(jù)集P中的唯一標識，用

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的標識以及點q與點p間的距離dist（p，q）;對于p.r，當p.nn的大小為k時，p.r等于存儲在p.nn中最大的距離值;當p.nn的大小小于k時，p.r的值被設為+∞.

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

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

定理1? ?對于當前掃描到的數(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ī)則，每個處理機通過掃描兩次數(shù)據(jù)集可實現(xiàn)本地離群點的計算過程. 算法2給出了本地離群點檢測的具體過程.

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

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

輸出：本地離群點集合

1. 初始化隊列H為空;

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

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

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

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

6.? ? ENDIF

7. ENDFOR

8. FOR H中的每一個數(shù)據(jù)點q DO

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

10. ENDFOR

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

12.? ? DeleteInlier（p）;

13. ENDFOR

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

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

IsNoInlier（）

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

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

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

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

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

4.? ? ? BREAK;

5.? ? ENDIF

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

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

q.nn列表中;

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

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

10.? ? ? ENDIF

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

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

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

14.? ? ? ENDIF

15.? ? ENDIF

16. ENDFOR

17. IF p.r>r THEN

18.? ? 返回TRUE;

19. ENDIF

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

DeleteInlier（）

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

輸出：隊列H

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

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

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

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

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

6.? ? ? ENDIF

7.? ? ENDIF

8. ENDFOR

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

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

5.2? ?全局離群點計算

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

對于給定的數(shù)據(jù)集P，利用GDDP劃分方法對數(shù)據(jù)分布最均勻的二維空間（假設是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]. 進一步，有如下引理：

引理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ù)塊進行計算，以確定是否為真正的離群點.

定義3? ?點與數(shù)據(jù)塊的最小距離.給定數(shù)據(jù)點p和數(shù)據(jù)塊b，則點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）

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

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

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

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

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

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

2.? ? 初始化集合Sb;

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

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

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

6.? ? ? ?ENDIF

7.? ? ENDFOR

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

9. ENDFOR

10. FOR Lb中的每個數(shù)據(jù)點p DO

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

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

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

14.? ? ENDIF

15. ENDFOR

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

6? ?實驗分析

6.1? ?實驗環(huán)境

本文實驗所搭建的異構分布式計算系統(tǒng)共包含5臺處理機，其中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算法進行對比實驗.

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

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

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

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

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

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

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

Tab.6? ?Parameter settings in a synthetic dataset

[參數(shù) 默認值 變化范圍 數(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ù)量對3種檢測算法的影響. 隨著數(shù)據(jù)量的增加，上述算法的處理時間都會變長，對應的通信量也隨之變多. 但通過對比可以發(fā)現(xiàn)，GODA算法和BOD算法的處理時間變化的速度較慢，而PENL算法的處理時間的增長趨勢較快，也會增大網(wǎng)絡開銷. 由此說明GODA算法的查詢效率要高于BOD算法和PENL算法的查詢效率.

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

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

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

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

7? ?結? ?論

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

參考文獻

[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]? ? 鄭明玲，蔣句平，袁遠，等.? 一種面向大規(guī)模計算機的監(jiān)控管理系統(tǒng)[J]. 湖南大學學報（自然科學版），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]? 王習特，申德榮，白梅，等. BOD：一種高效的分布式離群點檢測算法[J]. 計算機學報，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]? 王珊，王會舉，覃雄派，等. 架構大數(shù)據(jù)：挑戰(zhàn)、現(xiàn)狀與展望[J]. 計算機學報，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）