基于CART決策樹的分布式數(shù)據(jù)離群點檢測算法

摘" 要： 在分布式計算環(huán)境中，離群點通常表示數(shù)據(jù)中的異常情況，例如故障、欺詐、攻擊等。通過檢測分布式數(shù)據(jù)的離群點，可以對這些異常數(shù)據(jù)進行集中處理，保護系統(tǒng)和數(shù)據(jù)的安全。而進行離群點檢測時，不僅要考慮數(shù)據(jù)的規(guī)模和復雜性，還要在分布式環(huán)境下高效地發(fā)現(xiàn)離群點。因此，提出一種基于CART決策樹的分布式數(shù)據(jù)離群點檢測算法。在構建CART決策樹時，使用類間中心距離作為分裂準則，根據(jù)分離類別對訓練數(shù)據(jù)進行分類，從而確定數(shù)據(jù)的類型。在上述基礎上，考慮到離群點的分布模式與其周圍數(shù)據(jù)對象不同，使用空間局部偏離因子（SLDF）對空間內各個數(shù)據(jù)對象之間的離群程度展開度量，同時在高維空間內展開網(wǎng)格劃分，引入SLDF算法檢測剩余離群點集，最終實現(xiàn)分布式數(shù)據(jù)離群點檢測。實驗結果表明，所提方法的離散點檢測錯誤率在0.010以內，可以更加精準地實現(xiàn)分布式數(shù)據(jù)離群點檢測，具有良好的檢測性能。

關鍵詞： CART決策樹； 分布式數(shù)據(jù)； 離群點檢測； 類間距離； 數(shù)據(jù)分類； 空間局部偏離因子

中圖分類號： 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" 引" 言

在分布式數(shù)據(jù)[1?2]中，離群點即那些與數(shù)據(jù)集中其他數(shù)據(jù)點顯著不同的數(shù)據(jù)點，蘊含著重要的信息，如異常行為、故障預警或新的發(fā)現(xiàn)等[3?4]。因此，有效地檢測和處理離群點對于提高數(shù)據(jù)質量、增強決策準確性和保障系統(tǒng)安全具有重要意義。國內外相關專家針對分布式數(shù)據(jù)離群點檢測方面的內容展開了大量研究。

張忠平等采用近鄰數(shù)替換k近似關系，組建全部的鄰域集合，采用質心投影概念刻畫各個數(shù)據(jù)對象和其鄰居點的分布特征；在數(shù)據(jù)對象鄰居點逐漸增多的情況下，通過質心投影波動衡量各個數(shù)據(jù)對象的離散程度，最終實現(xiàn)離群點檢測[5]。該算法在數(shù)據(jù)集比較大或者維度比較高的情況下，計算復雜度會大幅度增加。鄭忠龍等通過密度估計獲取穩(wěn)態(tài)密度，根據(jù)穩(wěn)態(tài)密度展開不同策略的模擬投票；同時考慮了數(shù)據(jù)點的重要性和其近鄰的相似性展開投票，根據(jù)投票結果實現(xiàn)離群點檢測[6]。該算法中的密度估計在實際應用過程中會受到數(shù)據(jù)分布以及噪聲等因素的影響，從而導致估計結果準確率偏低，進而影響離群點檢測結果。Jing W等采用坐標映射對不同坐標系的數(shù)據(jù)坐標展開轉換，通過主成分分析可以精準地提取網(wǎng)絡中的流數(shù)據(jù)特征，最終使用差分點因子對網(wǎng)絡中的非線性異常值展開檢測[7]。該算法適用于特定的數(shù)據(jù)類型，對于其他類型的數(shù)據(jù)適用性較差。S. M. Kaddour等提出了一種基于能耗數(shù)據(jù)的異常檢測方法，以幫助居民減少能源消耗，并為能源提供商提供詳細數(shù)據(jù)，從而改善能源管理[8]。在研究過程中，某些無監(jiān)督異常檢測方法對于特定類型的數(shù)據(jù)特征更為適用，如果所選模型并未考慮到能耗數(shù)據(jù)的特點，可能無法準確捕捉異常行為，從而導致誤報或漏報。

CART決策樹作為一種強大的機器學習模型，具有良好的解釋性和分類能力。其通過遞歸地將數(shù)據(jù)劃分為更純的子集來生成樹結構，這一過程自然地適用于數(shù)據(jù)的分布式處理。通過將決策樹與分布式計算框架相結合，可以實現(xiàn)對大規(guī)模數(shù)據(jù)的并行處理，從而顯著提高離群點檢測的效率。因此，本文提出一種基于CART決策樹的分布式數(shù)據(jù)離群點檢測算法。

1" 分布式數(shù)據(jù)離群點檢測

1.1" 分布式數(shù)據(jù)分類

分布式環(huán)境下，數(shù)據(jù)存儲在不同的節(jié)點上，但節(jié)點中存在數(shù)據(jù)傾斜問題，即某些節(jié)點上的數(shù)據(jù)量遠大于其他節(jié)點，導致部分節(jié)點計算負載過重，影響整體離群點檢測的準確性和效率。而將分布式數(shù)據(jù)集劃分為多個不同類別的子集，再分布到不同的節(jié)點上并行處理，最后整合各節(jié)點的結果，可以縮短計算時間，提高效率。CART決策樹是一種二叉樹結構，采用自上而下的遞歸方式展開劃分，在分布式數(shù)據(jù)分類[9?10]過程中，其可以清晰地展示數(shù)據(jù)屬性之間的關系和分類依據(jù)，有效降低上層節(jié)點的分類誤差，獲取更加精準的分類結果。

在構建決策樹時，需要選擇一個最佳的特征和閾值來劃分數(shù)據(jù)集。通過計算類間距離，可以量化不同類別之間的相似度或差異度，從而更好地選擇適合劃分數(shù)據(jù)的特征和閾值。

設定類別中共有[N]個樣本，每個樣本具有[i]個特征，則樣本中第[i]個特征的平均值[Bxi]可以表示為：

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

式中[xij]代表第[j]個樣本中第[i]個特征值。采用公式（1）計算獲取各類分布式數(shù)據(jù)中每個特征的平均值后，即可確定各類數(shù)據(jù)的類中心。

接下來，計算各類樣本之間的類間距離[Dn]，公式如下：

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

式中：[xn]和[yn]代表不同類別的分布式數(shù)據(jù)特征值。

基于數(shù)據(jù)挖掘[11?12]技術的思想，將分布式數(shù)據(jù)進行數(shù)據(jù)清理和集成等相關操作，進而獲取一組高純度的數(shù)據(jù)集，并直接將其存儲于數(shù)據(jù)庫中；然后確定數(shù)據(jù)集的相關屬性，選取分裂函數(shù)最大值對應的屬性[Ci]作為分裂屬性。分裂屬性的計算公式如下所示：

[Ci=PkDnRij] （3）

式中：[Rij]代表分布式數(shù)據(jù)集中的第[i]個屬性；[Pk]代表分布式數(shù)據(jù)集中第[i]個屬性第[j]個屬性值為第[k]類決策屬性的概率。

通過最佳分裂屬性即可確定最佳分裂點。最佳分裂屬性[Cibest]可以表示為：

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

式中：[t]的下標L和R代表當前分裂節(jié)點的左子樹和右子樹；[RFjtL]和[RFjtR]代表左子樹和右子樹中任意數(shù)據(jù)記錄被判定為類別[Fj]的概率；[RL]和[Rk]代表分布式數(shù)據(jù)集中數(shù)據(jù)記錄所占比例。

依據(jù)最佳的分割屬性將當前節(jié)點的數(shù)據(jù)集劃分為兩個子集，一旦所有的葉節(jié)點只包含屬于同一類別的訓練樣本，或者沒有可用的分割屬性，則構建二叉樹的流程結束；否則，將繼續(xù)在待分裂的節(jié)點中展開計算，以找到下一個節(jié)點的最佳分裂值。但該過程中生成的二叉樹規(guī)模龐大，為了降低計算復雜度，采用剪枝技術在所構建的二叉樹中以最小代價復雜性為目標，組建一顆真誤差率比較小的二叉樹，操作步驟如下。

1） 計算當前二叉樹中節(jié)點[Hi]的各個節(jié)點[t]的值，公式如下：

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

式中：[ht]代表節(jié)點集合[H]中內節(jié)點[t]的值；[At]代表擬合節(jié)點所在數(shù)據(jù)集對應的局部平方誤差；[Tt]代表模型的擬合效果評估值；[Ah]代表最小子樹；[Th]代表模型準確性度量結果。

2） 求解最小內節(jié)點，同時將其作為下一棵最小樹。

3） 判斷當前是否只有一個根節(jié)點。只有一個根節(jié)點時，根據(jù)分裂屬性確定第一優(yōu)先級分離類別；反之則跳轉至步驟1）。

4） 設定Gini系數(shù)閾值，計算數(shù)據(jù)集中不同特征的Gini系數(shù)；再以Gini系數(shù)為判定依據(jù)，確定左右節(jié)點上的分離類別。如果Gini系數(shù)低于設定的閾值則回到?jīng)Q策樹的子節(jié)點，重新確定左右節(jié)點上的分離類別，完成組建。

5） 將數(shù)據(jù)集中不同類型的數(shù)據(jù)分別采用不同的數(shù)字代替，同時將數(shù)字化的數(shù)據(jù)進行歸一化處理，確保各值都在[0，1]。

6） 將一個類型的樣例用作正例，剩余部分則用于反例，通過其完成分類器的訓練。

7） 訓練完成后，將預測結果作為第一優(yōu)先級分離類別的樣本輸出，并剔除該分裂屬性。根據(jù)第二優(yōu)先級分離類別對其他的訓練數(shù)據(jù)展開分類，確定數(shù)據(jù)的類型。

8） 重復步驟6）、步驟7），直至分離類別中只有一個類別，輸出最終的分布式數(shù)據(jù)分類結果。

1.2" 數(shù)據(jù)離群點檢測

數(shù)據(jù)離群點檢測的目標是識別異常數(shù)據(jù)點，而異常數(shù)據(jù)點通常是在數(shù)據(jù)分類過程中被錯誤分類的樣本。同時，考慮到離群點的分布模式與其周圍數(shù)據(jù)對象不同，因此，在分布式數(shù)據(jù)分類[13?14]的基礎上，采用空間局部偏離因子（SLDF）對設定空間內不同數(shù)據(jù)對象的離散程度展開度量，更好地捕捉到數(shù)據(jù)對象之間的相對位置關系，即哪些數(shù)據(jù)對象在空間中相對分散，哪些數(shù)據(jù)對象相對聚集。這種信息可以幫助識別出屬于離群點的數(shù)據(jù)對象，提高離群點檢測的效果。

設定對象[p]的k距離鄰域[Nk?distancep]，則對象對其鄰域內全部鄰居的平均值[θ]表示為：

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

式中：[distp，o，w]代表鄰域內全部鄰居的數(shù)量；[o]代表數(shù)據(jù)對象。

結合上述分析，給出SLDF度量空間點對象離群程度的步驟。

1） 對各個對象的非空間屬性值進行歸一化處理。

2） 通過計算可以確定分布式數(shù)據(jù)集合中隨機兩個數(shù)據(jù)對象之間的空間距離，進而更好地掌握和理解數(shù)據(jù)間的關系以及真實分布情況。

3） 從數(shù)據(jù)集中隨機選擇一個起始點，然后根據(jù)數(shù)據(jù)的特性，逐步確定每個數(shù)據(jù)點在空間中的位置和鄰近區(qū)域。

4） 根據(jù)設定的順序對數(shù)據(jù)集中的各個數(shù)據(jù)對象展開空間局部偏離率[Sp]計算，即：

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

5） 按照空間局部偏離因子大小對其展開降序排列，同時利用給定的參數(shù)，選取一定數(shù)量的對象作為結果直接輸出。

接下來展開網(wǎng)格劃分處理，并通過SLDF算法檢測剩余部分的離群點[15]。

第一階段步驟如下所示。

1） 任意地選擇一個分布式數(shù)據(jù)子空間中沒有訪問過的點，以設定的維度間隔距離值作為判定依據(jù)展開網(wǎng)格單元劃分。

2） 組建哈希函數(shù)，將網(wǎng)格單元信息映射到對應的哈希表中，計算網(wǎng)格單元中包含的分布式數(shù)據(jù)點總數(shù)。根據(jù)事先設定的值判斷網(wǎng)格單元所屬的類型，即稠密網(wǎng)格單元還是非密集網(wǎng)格單元。

3） 對哈希表中的全部標記展開遍歷處理，將其設定為稠密的網(wǎng)格單元，利用其對應的鄰近單元特征判斷網(wǎng)格是否為邊界網(wǎng)格單元，相應地做好標記。

4） 刪除全部稠密網(wǎng)格單元和非邊界網(wǎng)格單元中的聚類點，將剩余網(wǎng)格單元放入到候選離群點集合中。

5） 重復以上操作步驟，直至分布式數(shù)據(jù)集中全部的點都映射到對應的哈希表中，獲取數(shù)據(jù)空間中全部聚類區(qū)域和全部由非邊界網(wǎng)格單元包含的聚類點，同時將其剔除。

第二階段步驟如下所示。

1） 對分布式數(shù)據(jù)集展開第1次掃描，獲取每一維數(shù)據(jù)集中數(shù)據(jù)對應的取值。將全部數(shù)據(jù)按照維度大小展開排序，同時利用公式（8）計算各個維度的等分間隔[Dp]。

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

2） 繼續(xù)對數(shù)據(jù)集展開掃描描述，經(jīng)過計算確定數(shù)據(jù)點在不同維度對應的網(wǎng)格單元；同時利用哈希函數(shù)將獲取的網(wǎng)格單元分別映射到對應的哈希表中。

3） 對哈希表掃描，識別出邊界單元網(wǎng)格。

4） 通過廣度優(yōu)先的遍歷方法對哈希表中的候選離群點展開掃描，同時利用SLDF算法計算各個數(shù)據(jù)對象的SLDF值[S?]。

第三階段步驟為：將全部數(shù)據(jù)對象的[SLDFk]值進行降序排列，選取前[m]個數(shù)據(jù)對象對應的結果作為輸出，實現(xiàn)分布式數(shù)據(jù)離群點檢測。

2" 實驗分析

2.1" 實驗設置

為了驗證基于CART決策樹的分布式數(shù)據(jù)離群點檢測算法的有效性，選取RDD分布式數(shù)據(jù)集用于實驗。RDD在抽象上來說是一種元素集合，分為多個分區(qū)，每個分區(qū)分布在集群中的不同節(jié)點上，從而讓RDD中的數(shù)據(jù)可以被并行操作。在RDD中隨機選取4組數(shù)據(jù)，離散點圖如圖1所示。

在Ubuntu 20.04 LTS操作系統(tǒng)中設置如表1所示的實驗參數(shù)，得到的離群點檢測結果如圖2所示。

分析圖2可知，所提算法可以將離散點與正常點進行有效區(qū)分，表明所提方法可以有效檢測出分布式數(shù)據(jù)中的離散點。

2.2" 結果與分析

為了進一步驗證所提方法的有效性，在圖1所示的4種不同數(shù)據(jù)中，以文獻[5]方法和文獻[6]方法作為對比方法展開離群點檢測，獲取的離群點發(fā)現(xiàn)曲線如圖3所示。

曲線測試結果對比

通過分析圖3中的實驗數(shù)據(jù)可以看出，在不同的人工數(shù)據(jù)集中，所提算法對應的離群點發(fā)現(xiàn)曲線表現(xiàn)出最佳性能，說明采用所提算法可以更好地提升分布式數(shù)據(jù)離群點檢測性能，并且可以適用于不同類型的數(shù)據(jù)集，具有較好的檢測性能和穩(wěn)定性。

為了進一步驗證各個算法的檢測性能，采用兩種識別錯誤展開分析，第一種類型為[S1]，即正常數(shù)據(jù)被標識為錯誤標記離群點數(shù)據(jù)；第二種類型為[S2]，即錯誤標記離群點數(shù)據(jù)可以被正確識別。定義3個指標衡量各個算法的性能，具體如下所示。

1） [uS1]代表錯誤丟棄正常數(shù)據(jù)的概率，公式如下：

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

式中：[Z]代表檢測到的離群點數(shù)據(jù)；[M]代表訓練樣本中真實離群點數(shù)據(jù)數(shù)量；[G]代表訓練樣本的數(shù)量。

2） [uS2]代表誤標記離群點數(shù)據(jù)沒有被正確識別，主要反映的是漏檢測率，公式如下：

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

3） [uS]是上述兩種錯誤的一種綜合考慮，公式為：

[uS=12uS1+uS2] （11）

表2給出了各個算法在不同數(shù)據(jù)集的測試結果。通過分析表2中的實驗數(shù)據(jù)可以看出，采用所提算法獲取的各項測試指標在0.010以內，均低于另外兩種算法。說明通過所提算法可以有效檢測出分布式數(shù)據(jù)集中的離群點，充分驗證了該算法的優(yōu)越性和有效性。

3" 結" 語

離群點通常表示數(shù)據(jù)中的異常情況，例如故障、欺詐、攻擊等。為保證數(shù)據(jù)安全，本文提出一種基于CART決策樹的分布式數(shù)據(jù)離群點檢測算法。在構建CART決策樹時，使用類間中心距離作為分裂準則，根據(jù)分離類別對訓練數(shù)據(jù)進行分類，從而確定數(shù)據(jù)的類型。在上述基礎上，考慮到離群點的分布模式與其周圍數(shù)據(jù)對象不同，使用空間局部偏離因子（SLDF）對空間內各個數(shù)據(jù)對象之間的離群程度展開度量，同時在高維空間內展開網(wǎng)格劃分，引入SLDF算法檢測剩余離群點集，最終實現(xiàn)分布式數(shù)據(jù)離群點檢測。

通過實驗分析表明，所提算法在不同數(shù)據(jù)中具有良好的分布式數(shù)據(jù)離群點檢測性能，可以有效提升檢測結果的準確性。在后續(xù)的研究過程中，將針對檢測效率方面的內容進行探索。

參考文獻

[1] 吳愛華，陳出新.分布式數(shù)據(jù)庫中關系數(shù)據(jù)正負關聯(lián)規(guī)則挖掘[J].計算機仿真，2021，38（9）：344?347.

[2] 金利娜，于炯，杜旭升，等.基于生成對抗網(wǎng)絡和變分自編碼器的離群點檢測算法[J].計算機應用研究，2022，39（3）：774?779.

[3] 葉晟，吳曉朝.基于網(wǎng)格劃分和LLE的高維數(shù)據(jù)離群點自適應檢測方法[J].湖南科技大學學報（自然科學版），2023，38（1）：85?91.

[4] 張忠平，鄧禹，劉偉雄，等.FNOD：基于近鄰差波動因子的離群點檢測算法[J].高技術通訊，2022，32（7）：674?686.

[5] 張忠平，張玉停，劉偉雄，等.基于質心投影波動的離群點檢測算法[J].計算機集成制造系統(tǒng)，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] 梁越，劉曉峰，李權樹，等.面向司法文本的不均衡小樣本數(shù)據(jù)分類方法[J].計算機應用，2022，42（z2）：118?122.

[10] 薛占熬，李永祥，姚守倩，等.基于Bayesian直覺模糊粗糙集的數(shù)據(jù)分類方法[J].山東大學學報（理學版），2022，57（5）：1?10.

[11] 陳波，詹明強，黃梓莘.基于關聯(lián)規(guī)則的庫岸邊坡監(jiān)測數(shù)據(jù)挖掘方法[J].長江科學院院報，2022，39（8）：58?64.

[12] 周燕，肖莉.基于改進關聯(lián)聚類算法的網(wǎng)絡異常數(shù)據(jù)挖掘[J].計算機工程與設計，2023，44（1）：108?115.

[13] 朱先遠，嚴遠亭，張燕平.鄰域信息修正的不完整數(shù)據(jù)多填充集成分類方法[J].計算機工程與應用，2023，59（23）：125?135.

[14] 李京泰，王曉丹.基于代價敏感激活函數(shù)XGBoost的不平衡數(shù)據(jù)分類方法[J].計算機科學，2022，49（5）：135?143.

[15] 高志宇，宋學坤，肖俊生，等.基于神經(jīng)網(wǎng)絡的大規(guī)模數(shù)據(jù)集離群點檢測算法[J].沈陽工業(yè)大學學報，2022，44（4）：420?425.