基于CART决策树的分布式数据离群点检测算法

摘" 要： 在分布式计算环境中，离群点通常表示数据中的异常情况，例如故障、欺诈、攻击等。通过检测分布式数据的离群点，可以对这些异常数据进行集中处理，保护系统和数据的安全。而进行离群点检测时，不仅要考虑数据的规模和复杂性，还要在分布式环境下高效地发现离群点。因此，提出一种基于CART决策树的分布式数据离群点检测算法。在构建CART决策树时，使用类间中心距离作为分裂准则，根据分离类别对训练数据进行分类，从而确定数据的类型。在上述基础上，考虑到离群点的分布模式与其周围数据对象不同，使用空间局部偏离因子（SLDF）对空间内各个数据对象之间的离群程度展开度量，同时在高维空间内展开网格划分，引入SLDF算法检测剩余离群点集，最终实现分布式数据离群点检测。实验结果表明，所提方法的离散点检测错误率在0.010以内，可以更加精准地实现分布式数据离群点检测，具有良好的检测性能。

关键词： CART决策树； 分布式数据； 离群点检测； 类间距离； 数据分类； 空间局部偏离因子

中图分类号： TN919⁃34； TP391" " " " " " " " " "文献标识码： A" " " " " " " " " " " 文章编号： 1004⁃373X（2024）16⁃0157⁃06

Distributed data outlier detection algorithm based on CART decision tree

ZHU Hua1， QIAO Yongjin2， 3， DONG Guogang1

（1. School of Computer Science and Technology， Wuhan University of Bioengineering， Wuhan 430415， China;

2. China Agricultural University， Beijing 100091， China; 3. Shanghai Academy of Agricultural Sciences， Shanghai 201403， China）

Abstract： In distributed computing environments， outliers often represent abnormal situations in data， such as failures， fraud， attacks， etc. By detecting outliers in distributed data， these abnormal data can be processed centrally to protect the security of the system and data. When conducting outlier detection， it is not only necessary to consider the size and complexity of the data， but also to efficiently discover outliers in a distributed environment. Therefore， a distributed data outlier detection algorithm based on CART decision tree is proposed. When constructing the CART decision tree， the inter class center distance is used as the splitting criterion to classify the training data according to the separated categories， so as to determine the type of data. On the basis of the above， considering that the distribution pattern of outliers is different from their surrounding data objects， a spatial local deviation factor （SLDF） is used to measure the degree of outliers between various data objects in space. The grid partitioning is carried out in high⁃dimensional space， and the SLDF algorithm is introduced to detect the remaining outlier set， ultimately realizing the outlier detection of the distributed data. The experimental results show that the error rate of the proposed method for the outlier detection is within 0.010， which can realize more accurate outlier detection of the distributed data， and has good detection performance.

Keywords： CART decision tree; distributed data; outlier detection; inter class distance; data classification; spatial local deviation factor

0" 引" 言

在分布式数据[1⁃2]中，离群点即那些与数据集中其他数据点显著不同的数据点，蕴含着重要的信息，如异常行为、故障预警或新的发现等[3⁃4]。因此，有效地检测和处理离群点对于提高数据质量、增强决策准确性和保障系统安全具有重要意义。国内外相关专家针对分布式数据离群点检测方面的内容展开了大量研究。

张忠平等采用近邻数替换k近似关系，组建全部的邻域集合，采用质心投影概念刻画各个数据对象和其邻居点的分布特征；在数据对象邻居点逐渐增多的情况下，通过质心投影波动衡量各个数据对象的离散程度，最终实现离群点检测[5]。该算法在数据集比较大或者维度比较高的情况下，计算复杂度会大幅度增加。郑忠龙等通过密度估计获取稳态密度，根据稳态密度展开不同策略的模拟投票；同时考虑了数据点的重要性和其近邻的相似性展开投票，根据投票结果实现离群点检测[6]。该算法中的密度估计在实际应用过程中会受到数据分布以及噪声等因素的影响，从而导致估计结果准确率偏低，进而影响离群点检测结果。Jing W等采用坐标映射对不同坐标系的数据坐标展开转换，通过主成分分析可以精准地提取网络中的流数据特征，最终使用差分点因子对网络中的非线性异常值展开检测[7]。该算法适用于特定的数据类型，对于其他类型的数据适用性较差。S. M. Kaddour等提出了一种基于能耗数据的异常检测方法，以帮助居民减少能源消耗，并为能源提供商提供详细数据，从而改善能源管理[8]。在研究过程中，某些无监督异常检测方法对于特定类型的数据特征更为适用，如果所选模型并未考虑到能耗数据的特点，可能无法准确捕捉异常行为，从而导致误报或漏报。

CART决策树作为一种强大的机器学习模型，具有良好的解释性和分类能力。其通过递归地将数据划分为更纯的子集来生成树结构，这一过程自然地适用于数据的分布式处理。通过将决策树与分布式计算框架相结合，可以实现对大规模数据的并行处理，从而显著提高离群点检测的效率。因此，本文提出一种基于CART决策树的分布式数据离群点检测算法。

1" 分布式数据离群点检测

1.1" 分布式数据分类

分布式环境下，数据存储在不同的节点上，但节点中存在数据倾斜问题，即某些节点上的数据量远大于其他节点，导致部分节点计算负载过重，影响整体离群点检测的准确性和效率。而将分布式数据集划分为多个不同类别的子集，再分布到不同的节点上并行处理，最后整合各节点的结果，可以缩短计算时间，提高效率。CART决策树是一种二叉树结构，采用自上而下的递归方式展开划分，在分布式数据分类[9⁃10]过程中，其可以清晰地展示数据属性之间的关系和分类依据，有效降低上层节点的分类误差，获取更加精准的分类结果。

在构建决策树时，需要选择一个最佳的特征和阈值来划分数据集。通过计算类间距离，可以量化不同类别之间的相似度或差异度，从而更好地选择适合划分数据的特征和阈值。

设定类别中共有[N]个样本，每个样本具有[i]个特征，则样本中第[i]个特征的平均值[Bxi]可以表示为：

[Bxi=1Nj=1Nxij] （1）

式中[xij]代表第[j]个样本中第[i]个特征值。采用公式（1）计算获取各类分布式数据中每个特征的平均值后，即可确定各类数据的类中心。

接下来，计算各类样本之间的类间距离[Dn]，公式如下：

[Dn=Bxix1-y12+x2-y22+…+xn-yn2] （2）

式中：[xn]和[yn]代表不同类别的分布式数据特征值。

基于数据挖掘[11⁃12]技术的思想，将分布式数据进行数据清理和集成等相关操作，进而获取一组高纯度的数据集，并直接将其存储于数据库中；然后确定数据集的相关属性，选取分裂函数最大值对应的属性[Ci]作为分裂属性。分裂属性的计算公式如下所示：

[Ci=PkDnRij] （3）

式中：[Rij]代表分布式数据集中的第[i]个属性；[Pk]代表分布式数据集中第[i]个属性第[j]个属性值为第[k]类决策属性的概率。

通过最佳分裂属性即可确定最佳分裂点。最佳分裂属性[Cibest]可以表示为：

[Cibest=CiRLRkRFjtL-RFjtR]" " " " " （4）

式中：[t]的下标L和R代表当前分裂节点的左子树和右子树；[RFjtL]和[RFjtR]代表左子树和右子树中任意数据记录被判定为类别[Fj]的概率；[RL]和[Rk]代表分布式数据集中数据记录所占比例。

依据最佳的分割属性将当前节点的数据集划分为两个子集，一旦所有的叶节点只包含属于同一类别的训练样本，或者没有可用的分割属性，则构建二叉树的流程结束；否则，将继续在待分裂的节点中展开计算，以找到下一个节点的最佳分裂值。但该过程中生成的二叉树规模庞大，为了降低计算复杂度，采用剪枝技术在所构建的二叉树中以最小代价复杂性为目标，组建一颗真误差率比较小的二叉树，操作步骤如下。

1） 计算当前二叉树中节点[Hi]的各个节点[t]的值，公式如下：

[ht=At×h×Tt-AhThTt-1]" "（5）

式中：[ht]代表节点集合[H]中内节点[t]的值；[At]代表拟合节点所在数据集对应的局部平方误差；[Tt]代表模型的拟合效果评估值；[Ah]代表最小子树；[Th]代表模型准确性度量结果。

2） 求解最小内节点，同时将其作为下一棵最小树。

3） 判断当前是否只有一个根节点。只有一个根节点时，根据分裂属性确定第一优先级分离类别；反之则跳转至步骤1）。

4） 设定Gini系数阈值，计算数据集中不同特征的Gini系数；再以Gini系数为判定依据，确定左右节点上的分离类别。如果Gini系数低于设定的阈值则回到决策树的子节点，重新确定左右节点上的分离类别，完成组建。

5） 将数据集中不同类型的数据分别采用不同的数字代替，同时将数字化的数据进行归一化处理，确保各值都在[0，1]。

6） 将一个类型的样例用作正例，剩余部分则用于反例，通过其完成分类器的训练。

7） 训练完成后，将预测结果作为第一优先级分离类别的样本输出，并剔除该分裂属性。根据第二优先级分离类别对其他的训练数据展开分类，确定数据的类型。

8） 重复步骤6）、步骤7），直至分离类别中只有一个类别，输出最终的分布式数据分类结果。

1.2" 数据离群点检测

数据离群点检测的目标是识别异常数据点，而异常数据点通常是在数据分类过程中被错误分类的样本。同时，考虑到离群点的分布模式与其周围数据对象不同，因此，在分布式数据分类[13⁃14]的基础上，采用空间局部偏离因子（SLDF）对设定空间内不同数据对象的离散程度展开度量，更好地捕捉到数据对象之间的相对位置关系，即哪些数据对象在空间中相对分散，哪些数据对象相对聚集。这种信息可以帮助识别出属于离群点的数据对象，提高离群点检测的效果。

设定对象[p]的k距离邻域[Nk⁃distancep]，则对象对其邻域内全部邻居的平均值[θ]表示为：

[θ=distp，o，wNk⁃distancep]" " "（6）

式中：[distp，o，w]代表邻域内全部邻居的数量；[o]代表数据对象。

结合上述分析，给出SLDF度量空间点对象离群程度的步骤。

1） 对各个对象的非空间属性值进行归一化处理。

2） 通过计算可以确定分布式数据集合中随机两个数据对象之间的空间距离，进而更好地掌握和理解数据间的关系以及真实分布情况。

3） 从数据集中随机选择一个起始点，然后根据数据的特性，逐步确定每个数据点在空间中的位置和邻近区域。

4） 根据设定的顺序对数据集中的各个数据对象展开空间局部偏离率[Sp]计算，即：

[Sp=θNk⁃distancep]" " " " " " （7）

5） 按照空间局部偏离因子大小对其展开降序排列，同时利用给定的参数，选取一定数量的对象作为结果直接输出。

接下来展开网格划分处理，并通过SLDF算法检测剩余部分的离群点[15]。

第一阶段步骤如下所示。

1） 任意地选择一个分布式数据子空间中没有访问过的点，以设定的维度间隔距离值作为判定依据展开网格单元划分。

2） 组建哈希函数，将网格单元信息映射到对应的哈希表中，计算网格单元中包含的分布式数据点总数。根据事先设定的值判断网格单元所属的类型，即稠密网格单元还是非密集网格单元。

3） 对哈希表中的全部标记展开遍历处理，将其设定为稠密的网格单元，利用其对应的邻近单元特征判断网格是否为边界网格单元，相应地做好标记。

4） 删除全部稠密网格单元和非边界网格单元中的聚类点，将剩余网格单元放入到候选离群点集合中。

5） 重复以上操作步骤，直至分布式数据集中全部的点都映射到对应的哈希表中，获取数据空间中全部聚类区域和全部由非边界网格单元包含的聚类点，同时将其剔除。

第二阶段步骤如下所示。

1） 对分布式数据集展开第1次扫描，获取每一维数据集中数据对应的取值。将全部数据按照维度大小展开排序，同时利用公式（8）计算各个维度的等分间隔[Dp]。

[Dp=SpNk⁃distancep]" " " " " " （8）

2） 继续对数据集展开扫描描述，经过计算确定数据点在不同维度对应的网格单元；同时利用哈希函数将获取的网格单元分别映射到对应的哈希表中。

3） 对哈希表扫描，识别出边界单元网格。

4） 通过广度优先的遍历方法对哈希表中的候选离群点展开扫描，同时利用SLDF算法计算各个数据对象的SLDF值[S⋅]。

第三阶段步骤为：将全部数据对象的[SLDFk]值进行降序排列，选取前[m]个数据对象对应的结果作为输出，实现分布式数据离群点检测。

2" 实验分析

2.1" 实验设置

为了验证基于CART决策树的分布式数据离群点检测算法的有效性，选取RDD分布式数据集用于实验。RDD在抽象上来说是一种元素集合，分为多个分区，每个分区分布在集群中的不同节点上，从而让RDD中的数据可以被并行操作。在RDD中随机选取4组数据，离散点图如图1所示。

在Ubuntu 20.04 LTS操作系统中设置如表1所示的实验参数，得到的离群点检测结果如图2所示。

分析图2可知，所提算法可以将离散点与正常点进行有效区分，表明所提方法可以有效检测出分布式数据中的离散点。

2.2" 结果与分析

为了进一步验证所提方法的有效性，在图1所示的4种不同数据中，以文献[5]方法和文献[6]方法作为对比方法展开离群点检测，获取的离群点发现曲线如图3所示。

曲线测试结果对比

通过分析图3中的实验数据可以看出，在不同的人工数据集中，所提算法对应的离群点发现曲线表现出最佳性能，说明采用所提算法可以更好地提升分布式数据离群点检测性能，并且可以适用于不同类型的数据集，具有较好的检测性能和稳定性。

为了进一步验证各个算法的检测性能，采用两种识别错误展开分析，第一种类型为[S1]，即正常数据被标识为错误标记离群点数据；第二种类型为[S2]，即错误标记离群点数据可以被正确识别。定义3个指标衡量各个算法的性能，具体如下所示。

1） [uS1]代表错误丢弃正常数据的概率，公式如下：

[uS1=Z-M⋂ZG-M] （9）

式中：[Z]代表检测到的离群点数据；[M]代表训练样本中真实离群点数据数量；[G]代表训练样本的数量。

2） [uS2]代表误标记离群点数据没有被正确识别，主要反映的是漏检测率，公式如下：

[uS2=M-M⋂ZM]" （10）

3） [uS]是上述两种错误的一种综合考虑，公式为：

[uS=12uS1+uS2] （11）

表2给出了各个算法在不同数据集的测试结果。通过分析表2中的实验数据可以看出，采用所提算法获取的各项测试指标在0.010以内，均低于另外两种算法。说明通过所提算法可以有效检测出分布式数据集中的离群点，充分验证了该算法的优越性和有效性。

3" 结" 语

离群点通常表示数据中的异常情况，例如故障、欺诈、攻击等。为保证数据安全，本文提出一种基于CART决策树的分布式数据离群点检测算法。在构建CART决策树时，使用类间中心距离作为分裂准则，根据分离类别对训练数据进行分类，从而确定数据的类型。在上述基础上，考虑到离群点的分布模式与其周围数据对象不同，使用空间局部偏离因子（SLDF）对空间内各个数据对象之间的离群程度展开度量，同时在高维空间内展开网格划分，引入SLDF算法检测剩余离群点集，最终实现分布式数据离群点检测。

通过实验分析表明，所提算法在不同数据中具有良好的分布式数据离群点检测性能，可以有效提升检测结果的准确性。在后续的研究过程中，将针对检测效率方面的内容进行探索。

参考文献

[1] 吴爱华，陈出新.分布式数据库中关系数据正负关联规则挖掘[J].计算机仿真，2021，38（9）：344⁃347.

[2] 金利娜，于炯，杜旭升，等.基于生成对抗网络和变分自编码器的离群点检测算法[J].计算机应用研究，2022，39（3）：774⁃779.

[3] 叶晟，吴晓朝.基于网格划分和LLE的高维数据离群点自适应检测方法[J].湖南科技大学学报（自然科学版），2023，38（1）：85⁃91.

[4] 张忠平，邓禹，刘伟雄，等.FNOD：基于近邻差波动因子的离群点检测算法[J].高技术通讯，2022，32（7）：674⁃686.

[5] 张忠平，张玉停，刘伟雄，等.基于质心投影波动的离群点检测算法[J].计算机集成制造系统，2022，28（12）：3869⁃3878.

[6] 郑忠龙，曾心，刘华文.两阶段的近邻密度投票模拟离群点检测算法[J].郑州大学学报（工学版），2023，44（6）：33⁃39.

[7] JING W， WANG P， ZHANG N. A nonlinear outlier detection method in sensor networks based on the coordinate mapping [J]. International journal of sensor networks， 2022， 39（2）： 136⁃144.

[8] KADDOUR S M， LEHSAINI M. Electricity consumption data analysis using various outlier detection methods [J]. International journal of software science and computational intelligence， 2021， 13（3）： 12⁃27.

[9] 梁越，刘晓峰，李权树，等.面向司法文本的不均衡小样本数据分类方法[J].计算机应用，2022，42（z2）：118⁃122.

[10] 薛占熬，李永祥，姚守倩，等.基于Bayesian直觉模糊粗糙集的数据分类方法[J].山东大学学报（理学版），2022，57（5）：1⁃10.

[11] 陈波，詹明强，黄梓莘.基于关联规则的库岸边坡监测数据挖掘方法[J].长江科学院院报，2022，39（8）：58⁃64.

[12] 周燕，肖莉.基于改进关联聚类算法的网络异常数据挖掘[J].计算机工程与设计，2023，44（1）：108⁃115.

[13] 朱先远，严远亭，张燕平.邻域信息修正的不完整数据多填充集成分类方法[J].计算机工程与应用，2023，59（23）：125⁃135.

[14] 李京泰，王晓丹.基于代价敏感激活函数XGBoost的不平衡数据分类方法[J].计算机科学，2022，49（5）：135⁃143.

[15] 高志宇，宋学坤，肖俊生，等.基于神经网络的大规模数据集离群点检测算法[J].沈阳工业大学学报，2022，44（4）：420⁃425.