异构分布式环境中的并行离群点检测算法

王习特，朱宗梅，于雪苹，白梅

（大连海事大学信息科学技术学院，辽宁大连 116000）

离群点检测是数据管理领域的重要研究内容之一，其主要目的是识别出数据集中与其他数据存在显著差异的数据对象.随着对离群点的不断研究，出现了多种离群点描述方式.其中，最直观的方式是通过度量数据空间中数据点间的距离来量化数据的离群程度.具体地，基于距离的离群点可定义为：给定参数k 和r，对于数据集P 中任意数据点p，若与点p 的距离小于等于r 的数据点个数少于k，则p 为离群点[1].

随着数据库中数据量的不断增加，有关离群点的研究已从集中式处理环境转向分布式处理环境，以提高海量数据的离群点检测效率[2].但是，现有的分布式算法大都用来解决同构分布式环境中的离群点检测问题.在实际应用中，参与分布式计算的处理机大都存在配置上的差异，各处理机的性能可能存在较大差异.这也就使得现有的针对同构分布式环境设计的离群点检测算法不能很好地适用于异构分布式环境.因此，迫切需要设计一种高效的异构分布式环境中的并行离群点检测算法.

本文主要针对异构分布式环境下的离群点检测问题，提出一种动态数据划分方法和相应计算方法，旨在提高算法的执行效率.具体地，本文的主要贡献包括以下几个部分：

1） 提出一种基于网格的动态数据划分方法GDDP（Gird-based Dynamic Data Partitioning）.该方法依据异构分布式环境中各处理机计算能力的差异动态分配计算任务，实现了各处理机计算任务的负载均衡，加快了计算效率.同时，考虑了数据集中数据点所处的空间位置信息，尽可能将空间上相邻的数据点划分至同一处理机，降低网络开销.

2）基于GDDP 划分方法，提出了异构分布式环境中并行的离群点检测算法GODA（GDDP-based Outlier Detection Algorithm）.该算法主要包括两个过程：①本地离群点计算.首先通过索引对每个处理机本地的数据集进行管理，然后根据过滤规则实现数据集中非离群点的过滤，从而快速计算出本地离群点；②全局离群点计算.利用每个候选离群点和其所在数据块与相邻数据块的距离关系，判断需要进行网络通信的处理机，然后统一将候选点发送到相应的处理机上，从而得到全局离群点.

3）分别利用真实数据集和人工合成数据集进行实验，验证了本文提出的GDDP 和GODA 算法的有效性.

1 相关工作

本节主要从集中式和分布式两方面对离群点检测的相关研究进行概述.

1.1 集中式离群点检测

目前，大多数离群点研究都是面向集中式环境的.研究内容主要包括两个方面：离群点定义和离群点检测方法.首先，离群点定义方面的研究致力于给出一种描述或者形式化定义离群点的方法.Hawkins等[3]最早给出离群点的形象化描述，认为离群点是数据集中与其他点差距很大、且怀疑与其他数据点并非由同一机制生成的点.为了更明确数据点是否为离群点，提出基于模型的离群点定义，以数据的分布模型为参考，将数据集中不符合分布模型的数据点定义为离群点[4].至今，研究人员给出了多种不同的离群点定义标准，如：基于距离的离群点、基于聚类的离群点[5]、基于密度的离群点[6].其中，基于距离的离群点定义能直观地反应离群点本质进而得到广泛应用.

其次，离群点检测是指根据某种离群点判定方式，从数据集中快速找到符合该判定方式的数据点的过程，判定方式不同，相应的离群点计算方法也不同.具体地，文献[1]基于距离的离群点定义，提出一种嵌套循环方式，对数据集中每个数据点进行距离计算，以找出最终的离群点.这种方法可以应对多维数据集，但实际的计算效率有待优化.之后，Bay 等[7]提出ORCA 算法，利用缓冲区给出一种修剪规则，实现对非离群点的过滤，加快检测效率.此外，有些学者利用空间索引加速离群点的计算过程.文献[8]提出了基于R 树的离群点检测算法，文献[9]给出了基于k-d 树的离群点检测算法.

1.2 分布式离群点检测

为了解决传统集中式离群点检测算法在大规模数据中检测效率低的问题，许多研究人员提出了有效的分布式算法，而现有的分布式离群点检测算法都是面向同构分布式环境的.Hung 等[10]首先给出分布式环境中基于距离的离群点检测算法，将数据均匀划分至各处理机，然后对传统嵌套循环算法进行优化，实现分布式的离群点计算过程.文献[11]首先提出了GBP 数据划分方法，利用网格空间索引结构对数据进行管理和划分，然后基于GBP 划分方法给出分布式离群点检测算法DLC.同样地，针对同一离群点定义，文献[12]也提出了相应的分布式离群点计算方法，在处理具有偏态分布的数据集时非常有效.文献[13]首先提出了BDSP 数据划分算法，可以有效均衡各计算节点的工作负载，同时实现良好的过滤效果，然后利用BDSP 方法提出基于距离的分布式离群点检测算法BOD，有效减少网络开销，缩短了离群点的计算时间.此外，文献[14]还给出了利用GPU并行地计算离群点的策略.

虽然已有一些优秀的分布式离群点检测方法，但这些方法都是针对同构分布式环境设计的，在异构分布式环境中无法保证高效的离群点检测效率.

2 问题描述

本文主要研究在异构分布式环境中，如何并行地计算出数据集内所有基于距离的离群点.下面，具体地给出基于距离的离群点的形式化定义，其中，表1 列出了本文使用的符号及其含义.

一般地，给定一个具有d 维属性值的数据集合P.对于P 中任一数据点p 可表示为：p，那么对于数据集P 中任意两个数据点p1和p2之间的欧式距离的计算公式为：

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

定义1 （r-近邻集合）.给定数据集合P 和用户定义的查询半径r，点pi的近邻集合是指P 中所有到pi的距离不大于r 的点的集合，即N（pi，r）={pj|pj∈P，dist（pi，pj）≤r}.

定义2 （（r，k）-离群点）.给定距离阈值r 和查询邻居阈值k，对于数据集P 中的任意一数据点p，若到数据点p 的距离小于等于r 的数据点个数小于k，即|N（pi，r）|

3 异构分布式中的离群点查询处理框架

本文主要针对异构分布式环境，其整体上包含一台主控制节点和数目固定的多个从节点C={c1，c2，…，cn}.由于各节点间数据迁移量较小，本文不考虑网络异构，其异构环境特指每个参与计算的从节点的配置各不相同，使得它们在计算能力上存在差异.另外，主控节点和每一个从节点都通过网络互连，可以进行网络通信.每两个相邻的从节点之间也可相互通信.为了防止主控节点在计算过程中发生拥塞，在数据划分时将不给主控节点分配计算任务，即在整个基于距离的离群点计算过程中，主控节点主要负责计算任务的调度，大部分的离群点计算任务都将由从节点完成.

根据图1 中的查询处理框架，异构分布式环境中的基于距离的离群点检测任务可以被描述为：对于给定的数据集合P、查询距离阈值r 和查询数量阈值k，通过充分利用异构分布式计算框架中各异构处理机的计算能力，快速地计算出给定数据集合P 中的所有基于距离的离群点.

图1 查询处理框架Fig.1 Query processing framework

具体地，整个过程大致可分为3 个阶段：

1）数据划分阶段.对于给定数据集P，主控制节点首先依据各异构处理机的计算能力的不同对数据集进行划分，然后将划分后的子数据集发送至相应的处理机.

2）局部离群点计算阶段.各个参与计算的处理机在接收到对应的数据子集合后，在本地进行局部计算，得到局部离群点，最后将它们发送到主控制节点.

3）全局离群点计算阶段.主控制节点根据接收到的局部离群点的位置信息判断其需要通信的从节点，然后将它们发送到相应处理机再次进行距离计算，得出最终的全局离群点.

4 基于网格的动态数据划分方法

在离群点检测之前，对数据集进行有效的划分，可以显著提高离群点检测效率.本文提出的基于网格的动态数据划分方法GDDP 保证了计算资源的充分利用，具有较高的负载均衡性.

4.1 计算能力评估

在分布式计算系统中为了能够实现整个系统的高可用性，一般需要实现各个参与计算的处理机之间负载均衡.在异构分布式环境中，各处理机间的计算能力不同，为了能对计算任务进行合理的分配，需要对每个处理机的计算能力进行评估.

首先，查询处理框架中的主控制节点会将相同的一份测试数据集发送给每个参与计算的从节点，进行相同的任务计算，然后记录每个处理机完成任务的时间.其中，处理机完成任务的时间越短，说明其计算能力越强；反之，其计算能力越弱.

为了便于后续基于网格的数据集的划分，本文给出一种有效的评分机制.首先，将工作节点的计算能力划分为m 个等级，即β1，β2，…，βm，对应得分分别为1，2，3，…，m，相应的工作节点的计算能力依次增强；其次，求出每个从节点的计算能力与当前最大计算能力的比值，所得结果在（0，1]内，其中，将（0，1]划分为m 等份，表示（0，1/m]，（1/m，2/m]，…，（m-1/m，1]，所得比值在各区间内的处理机的等级分别为β1，β2，…，βm；最后，根据每台处理机的计算能力等级得出相应的评分.例如，在一个异构分布式系统中有c1～c55 台从节点，为简化示例，此处等级数m=4，由以上方法得出各处理机的计算能力评估表如表2所示.

表2 处理机的计算能力评估Tab.2 Evaluation of the calculation ability of the processors

4.2 数据集划分

传统的数据划分方法对维度过高的数据集进行处理时，会产生巨量的划分子块，致使检测效率低下，由此本文决定对给定的多维数据集中数据分布最均匀的二维空间利用网格进行数据划分，经数据划分后会形成多个二维的数据子块.

首先确定数据集中每一维数据需划分为几段.考虑在异构分布式环境中，各从节点的计算能力不同，由此具体的划分段数为：

其中，comp_Grade（ci）表示处理机ci的计算能力得分，n 表示处理机的数目.例如，根据表2 中对5 台异构处理机c1～c5计算能力的评估结果，结合公式（2）可得划分段数Segment 值为4，因此，数据集将被映射到一个4×4 规模的网格结构内.

其次，为了判断数据在哪个维度上分布最均匀，本文给出一种衡量标准.具体地，数据在第d 维上分布的均匀程度为：

single_U（d）的值越小，说明数据在第d 维上分布越均匀.其中，num（segment（i））表示数据在第d 维上的第i 个划分段内的实际分布数量；μ 表示数据在第d 维上每个划分段数内的平均分布数量，它等于数据集的大小与划分段数Segment 的比值；n 取值为划分段数Segment 的值.

接下来，数据在由d1和d2维所组成的二维空间内的分布均匀程度用multi_U（d1，d2）来描述.同样地，multi_U（d1，d2）的值越小，表明数据在该二维空间内分布越均匀.具体地，multi_U（d1，d2）的计算公式表示为：

式中：num（gi）表示数据在当前d1和d2维空间内所建立的网格索引中第i 个网格内的实际分布数量；n表示二维网格中网格的数目，其值等于划分段数Segment 的平方；μ 表示数据在每个网格内的平均分布数据，其值等于数据集的总量与网格数目的比值.由以上数据分布均匀程度的两个衡量过程，可确定给定数据集中数据分布最均匀的二维空间，从而完成数据集的划分.具体地，对于给定的具有d 个维度的数据集的划分过程大致为：首先，根据划分段数Segment 将数据集的每一维度划分成s 个区间，然后统计数据在每个区间内的分布情况，并根据计算得出数据在每一维上的single_U（d） 值，选择single_U（d）值最小的个数据维度作为候选目标；其次，在候选维度里面，根据划分段数Segment，依次选取两个维度建立二维网格，并评估数据在二维网格内的分布情况；最终，根据multi_U（d1，d2）值最小的二个维度上对应的网格对数据集进行划分，可以得到多个不相交的划分数据子块.

4.3 数据块的分配

当数据集被分成多个不相交的数据子块后，紧接着需将其合理地分配到各异构的从节点上.

4.3.1 分配顺序

根据基于距离的离群点定义，为了减少分布式计算过程中各处理机之间的通信代价，需要将空间中邻近的数据点尽量分配到同一台工作节点上.因此，在数据块的分配过程中首先需要考虑数据集划分后各数据块之间的相邻关系，这样才能尽可能将空间中相邻的数据对象分配到同一台工作节点上.由于划分时用到的是二维网格，本文则按照网格的行序将相邻的数据块依次进行分配即可保证数据块之间是相邻的，如图2 中箭头所指方向即为数据块的分配顺序.

图2 数据块的分配顺序Fig.2 The allocated order of data blocks

4.3.2 分配规则

在本文所指的异构分布式环境中，对于参与计算的异构处理机，按照其计算能力由大到小顺序排列，之后优先选择计算能力强的处理机进行数据块的分配.如下算法1 给出了具体的数据块分配过程.

算法1 数据块分配算法.

输入：数据块集合B={b1，b2，…，bb}，从节点集合C={c1，c2，…，cn}；

输出：分配给每个从节点的数据块集合

经过上述分配过程，可以完成数据集中大多数数据的初分配，并且分配后大多数处理机都能获得小于等于其实际所需的数据量.

例如，给定多维数据集P，且|P|=120.如表2 所示，有5 台异构的从节点参与离群点的计算，对应的c1～c5处理机顺序为：c2、c4、c1、c3、c5.图3 所示为数据集划分的结果，则数据块的分配顺序为b1～b16.首先对处理机c2进行数据块分配，计算可得其所需数据量为×120=40.优先处理数据块b1，由于块内数据量5 小于c2当前所需数据量40，则将b2分配给处理机c2，同时更新c2当前所需数据量为35，最终，数据块b1、b2、b3、b4、b5都可被分配给c2，当对数据块b6进行分配时，由于处理机c2目前所需要的数据量为1，小于数据块b6的数据量，所以停止对处理机c2的数据块分配.同理，可依次完成处理机c4、c1、c3、c5的数据块分配任务.

图3 数据集划分结果Fig.3 The partition result of the data set

具体的分配结果如表3 所示.这样经过数据块的分配后，只有处理机c5所分配的数据量略大于它实际所需要的数据量.同时，只有数据块b16未被分配，把它暂时留在主控制处理机上.

表3 分配结果Tab.3 Allocation result

4.4 动态数据分配

动态分配旨在对存储于主控制节点上的剩余的未被分配的数据块进行数据分配.为了对空闲处理机进行准确的任务分配，主控制节点需记录从开始执行计算任务到有空闲节点出现所经过的时间，即当前空闲的处理机ci完成初始的分配任务的时间t，以及在处理时间t 内每个处理机已经处理的数据量complete_num（ci），由此可计算出各处理机在当前所划分的数据集中进行离群点检测任务时的实时处理速度vi（其中，vi=；同时，用当前未被处理的数据总量除以各处理机处理速度之和还可预估出剩余的所有计算任务完成的时间T；最后，将时间T 和空闲处理机的实时处理速度vi相乘，即可得出当前空闲工作节点所应分配的数据量.当存储在主控制节点上的数据都被分配后，动态分配过程结束.

这种动态数据分配方法依据各处理机的实际处理速度进行计算任务的分配，尽可能地避免了空闲处理机的等待，并充分利用了整个异构分布式环境中各处理机的计算资源，加快了离群点的检测速度.

5 GODA 算法描述

本节主要描述了GODA 算法的具体细节.整个过程分为2 个阶段：1）本地离群点计算，即利用每个处理机的计算能力计算出本地离群点；2）全局离群点计算，即通过全局通信确定最终离群点结果集.

5.1 本地离群点计算

本小节主要阐述GODA 算法中一种有效的面向多维大规模数据集的本地离群点计算方法.

5.1.1 索引构建

由于网格索引、R 树索引等一般的空间索引无法应对数据集维度的增长，并且根据离群点的形象化描述，在给定的数据集中，大部分数据点都是非离群点，而离群点只占据数据集的很少一部分，因此，本文索引构建采用如下方法.

在给定数据集中随机选取一个数据点p，其中，点p 在很大程度上为非离群点，以点p 为中心，计算数据集中其他数据点到点p 的距离，依据距点p 由近及远的顺序对数据进行管理，如果数据点q 距离中心点p 很远，则说明点q 很可能是离群点.

5.1.2 本地离群点计算方法描述

首先，对于给定数据集P 中的数据点p，自定义数据结构node 如下：

1）给定数据集P 中的一个数据点p；

2）数据点p 在给定数据集P 中的唯一标识，用p.id 表示；

3）数据点p 在给定数据集P 中的邻居情况，用p.nn 表示；

4）数据点p 与其第k 个近邻点的距离，用p.r表示.

其中，p.nn 是一个大小为k（用户给定的查询数量阈值）的列表，用于存储数据集P 中与数据点p 的距离不大于用户给定的查询距离阈值r 的数据点q的标识以及点q 与点p 间的距离dist（p，q）；对于p.r，当p.nn 的大小为k 时，p.r 等于存储在p.nn 中最大的距离值；当p.nn 的大小小于k 时，p.r 的值被设为+∞.

在离群点计算过程中，根据点p 的node 结构中p.r 的值与查询距离阈值r 的大小关系即可判断当前数据点p 是否为离群点.例如，若p.r 的值小于等于查询距离阈值r，那么数据点p 是非离群点；若p.nn列表未存满，且p.r 取值为+∞，则点p 是离群点.

根据上述自定义的node 结构，给出非离群点过滤定理.

定理1 对于当前扫描到的数据集P 中的数据点q，如果它和内存中存储的数据点p 之间的距离满足dist（p，q）≤r-p.r，则数据点q 为非离群点.

证 根据dist（p，q）≤r-p.r 可得p.r≤r，则说明内存中的数据点p 为非离群点，且在p.r 范围内数据点p 的邻居个数至少为k 个.又因为数据点p 和数据点q 之间的距离满足dist（p，q）+p.r≤r，则说明数据点p 及其邻居都是数据点q 的邻居，也即数据点q 的邻居个数大于给定的数量阈值k，因此根据基于距离的离群点定义可得数据点q 为非离群点.

证毕.

根据索引中数据点的顺序及定理1 中的过滤规则，每个处理机通过扫描两次数据集可实现本地离群点的计算过程.算法2 给出了本地离群点检测的具体过程.

算法2 本地离群点检测算法.

输入：查询距离阈值r，查询数量阈值k，本地存储的数据集P；

输出：本地离群点集合

第一次扫描数据集时，需要将当前扫描到的不能确定是非离群点的数据点的node 结构存储到内存中，以致于第一次扫描结束后，内存中至少存储着所有的本地离群点的信息.由此，判定数据点p 不是非离群点的IsNoInlier（p）函数的算法如下：

IsNoInlier（）

输入：查询距离阈值r，查询数量阈值k，查询数据点p，队列H；

输出：数据点p 的查询结果

第二次扫描数据集时，即从所有的候选本地离群点集合中找出真正的本地离群点，其中，删除内存中非离群点的DeleteInlier（p）函数的算法如下：

DeleteInlier（）

输入：查询距离阈值r，查询数量阈值k，数据点p，队列H；

输出：队列H

总体上，本小节基于距离的本地离群点计算方法可以通过扫描较少次数的数据集完成离群点的检测过程，在一定程度上减少了IO 代价，同时，还可以很好地应对数据集中数据维数的增长.

复杂度分析：记本地数据集的大小为N.对于本地离群点的计算，构建索引所需时间复杂度为O（N·lgN），两次扫描数据集所需的时间复杂度为O（|H|·N）.因此，算法2 的时间复杂度为O（N·lgN+|H|·N）.

5.2 全局离群点计算

在完成5.1 节的计算之后，本地离群点被发送到主控制节点形成离群点候选集，此后由主控制节点判断其所需进行网络通信的处理机，进而计算出真正的离群点.

对于给定的数据集P，利用GDDP 划分方法对数据分布最均匀的二维空间（假设是d1和d2维所组成的空间）划分后所得的数据块b 可表示为b=[b.min，b.max].其中，b.min、b.max 分别表示数据块b的下界和上界，则对于数据块b 中的任意数据p，都有b.min[d1]≤p[d1]≤b.max[d1]，b.min[d2]≤p[d2]≤b.max[d2].进一步，有如下引理：

引理1[15]对于数据块b 中的任意本地离群点p，如果∀i∈{d1，d2}，p[d1]-b.min[d1]＞r 且b.max[d2]-p[d2]≥r，则数据点p 是全局离群点.

对于离群点候选集中满足引理1 的数据点p，可得出其一定是全局离群点，而对于候选集中剩余的非确定的本地离群点，需和其所在数据块的相邻数据块进行计算，以确定是否为真正的离群点.

定义3 点与数据块的最小距离.给定数据点p和数据块b，则点p 与块b 的最小距离：

显然，对于块b 的近邻块集合N（b）中的块bi，若min_dist（p，bi）≤r，说明块bi中可能存在点p 的近邻，则将点p 发送到Sb集合中，最终将Sb中的数据点发送到块bi所在的处理机上.算法3 展示了具体的全局离群点计算过程.

算法3 全局离群点检测算法.

输入：数据块b 中的本地离群点集合Lb，数据块b 的近邻块集合N（b），距离阈值r，数量阈值k；

输出：本地离群点集合Lb中的全局离群点

复杂度分析：对于全局离群点的计算，记本地候选离群点的个数为η，根据公式（2）～（4）可将总数据集P 划分为b 个数据块，将本地候选离群点与相邻数据块中的数据点依次计算，因此，算法3 的时间复杂度为O（η·（8/b）·|P|）.不难发现，在分布式环境中，一个数据块的相邻块通常分布在不同的处理机上，因此可以并行执行离群点的计算，使得处理效率大大提高.

6 实验分析

6.1 实验环境

本文实验所搭建的异构分布式计算系统共包含5 台处理机，其中1 台主控节点，4 台从节点，它们的具体配置如下.

主控制节点：Intel Core i3-7020U CPU，4GB 内存，500GB 硬盘，操作系统为Windows 10；从节点1：Intel Core i5-8265U CPU，8GB 内存，256GB 硬盘，操作系统为Windows 10；从节点2：Intel Pentium（R）2020M 2.4 GHz CPU，4GB 内存，500GB 硬盘，操作系统为Windows 10；从节点3：Intel Core i3 2100 3.1GHz CPU，8GB 内存，500GB 硬盘，操作系统为Windows 10；从节点4：Intel Core i3-6006U CPU，4GB内存，125GB 硬盘，操作系统为Windows 10.

本文分别用真实数据集和合成数据集对所提出的GODA 算法与PENL 算法、BOD 算法进行对比实验.

6.2 真实数据集中的实验结果分析

实验所用的真实数据集为森林覆盖数据集Covertype，包含581 012 条数据，每条数据有10 个维度，每维属性值的范围为[0，100].表4 和表5 展示了3 种算法在该数据集中的处理时间和通信量.

表4 真实数据集中的处理时间Tab.4 Processing time in real data sets

表5 真实数据集中的通信量Tab.5 Traffic in real data sets

如表4 和表5 所示，本文提出的GODA 算法采用了基于网格的动态数据划分方法GDDP，可以根据各从节点的计算能力进行数据划分，实现异构分布式环境中各处理机的负载均衡，加快检测效率；同时，考虑点的空间位置，将相邻的点尽可能划分至同一节点，大大节省了网络开销.相比之下，BOD 算法和PENL 算法主要针对同构分布式环境，导致各节点数据分配不均衡，降低处理速度；PENL 算法采用基于数据量的划分方法，对于处理机的数据分配，都需与其他处理机上的数据集比较来确定最终结果，导致数据集重复传输，增加了网络开销.

另一方面，通过对比表4 和表5 中1、2 行的实验结果，可以发现，当k 不变，随着距离阈值r 的增大，数据集中离群点数目逐渐减少，GODA 算法和BOD 算法的处理时间和通信量也逐步减少.PENL算法的处理时间与这两种算法趋势相同，而通信量维持不变.这主要是因为PENL 算法需要将所有处理机上的数据集进行两两之间的比较，网络传输量与处理机的数目和数据集的规模有关，与查询无关.通过对比3、4 行实验结果可以看出，随着查询阈值k的增大，离群点的数目变多，导致GODA 算法的处理时间和通信量都随之增加.但是，不管查询阈值k 和距离阈值r 如何变化，与BOD 算法和PENL 算法相比，本文提出的GODA 算法在异构分布式环境中能更有效地进行离群点的检测.

6.3 人工合成数据集中的实验结果分析

由于真实数据集规模有限，数据维度也无法变化，所以本节使用人工合成的数据集对3 种算法进行有效性验证.首先，所使用的合成数据集为聚簇分布数据，各维取值范围为0～10 000.具体地，对于含有n 个数据对象的数据集，随机生成n/10 000 个聚簇点，每个聚簇内平均包含1 000 个数据对象，并以聚簇点为中心呈高斯分布.表6 给出了实验相关变量的默认值和变化范围.

表6 人工合成数据集中的参数设置Tab.6 Parameter settings in a synthetic dataset

图4 描述了数据量对3 种检测算法的影响.随着数据量的增加，上述算法的处理时间都会变长，对应的通信量也随之变多.但通过对比可以发现，GODA 算法和BOD 算法的处理时间变化的速度较慢，而PENL 算法的处理时间的增长趋势较快，也会增大网络开销.由此说明GODA 算法的查询效率要高于BOD 算法和PENL 算法的查询效率.

图5 显示了数据维度对3 种算法检测效果的影响.在图5（a）中，随着数据维度的升高，PENL 算法和GODA 算法的处理时间呈现出线性变化，而BOD算法处理时间的增长趋势明显较快.通过图5（b）可以发现，3 种算法的通信量都不受维度的影响.

图4 数据量的影响Fig.4 The effect of data volume

图5 维度的影响Fig.5 The effect of dimensionality

图6 表述了查询阈值k 的变化对3 种算法的影响.在图6（a）中，查询阈值k 增大时，3 种算法的处理时间都变长，这是因为k 增大，数据集中离群点数目增多，增加了算法的处理时间.但与PENL 算法相比，由于GODA 算法和BOD 算法在本地计算时良好的过滤措施，使其处理时间小于PENL 算法.通过图6（b）可得，随着查询阈值k 增大，PENL 算法的通信量不变，而对于GODA 算法和BOD 算法，当k 增大，使得数据集中离群点的数目增多，从而使其通信量稍微增加.

图6 查询阈值k 的影响Fig.6 The effect of query threshold k

图7 描述了距离阈值r 的变化对3 种算法性能的影响.在图7（a）中，当距离阈值r 不断变大，数据集中离群点数目变少，使得所有算法的处理时间都变短.由图7（b）可以发现，随着距离阈值r 增大，PENL 算法的通信量不变，而对于GODA 算法和BOD 算法，由于r 变大，数据集中离群点数目减少，使其通信量也稍微变少.

通过上述对比实验，验证了本文提出的GODA算法的优秀性能.与PENL 算法和BOD 算法相比，GODA 算法可以很好地解决异构分布式环境中基于距离的离群点检测问题.

图7 距离阈值r 的影响Fig.7 The effect of distance threshold r

7 结论

本文针对常见的异构分布式环境中的离群点检测问题，首先，提出有效的数据划分方法GDDP，保证了各处理机计算能力的充分利用，并通过考虑数据点的空间位置信息减少网络通信.其次，基于GDDP 方法，提出了GODA 算法，在每个处理机本地，通过构建索引进行数据管理，使用过滤规则进行批量过滤，加快本地离群点计算.再次，通过异构分布式计算框架中各节点间的网络通信，计算出全局离群点.最后，通过实验验证了GDDP 和GODA 算法的有效性.