基于隨機投影與集成學習的離群點檢測算法

收稿日期：2022-02-10；修回日期：2022-04-07" 基金項目：國家自然科學基金資助項目（61862060，61462079，61562086，61562078）

作者簡介：郭一陽（1996-），男，山東滕州人，碩士研究生，主要研究方向為機器學習、數據挖掘；于炯（1964-），男（通信作者），北京人，教授，博導，博士，主要研究方向為分布式計算、機器學習、數據挖掘（yujiong@xju.edu.cn）；杜旭升（1995-），男，甘肅慶陽人，博士研究生，主要研究方向為機器學習、數據挖掘；曹銘（1996-），女，山東菏澤人，碩士研究生，主要研究方向為機器學習、數據挖掘.

摘 要：

針對傳統基于相似度的離群點檢測算法在高維不均衡數據集上效果不夠理想的問題，提出一種新穎的基于隨機投影與集成學習的離群點檢測（ensemble learning and random projection-based outlier detection，EROD）框架。算法首先集成多個隨機投影方法對高維數據進行降維，提升數據多樣性；然后集成多個不同的傳統離群點檢測器構建異質集成模型，增加算法魯棒性；最后使用異質模型對降維后的數據進行訓練，訓練后的模型經過兩次優化組合以降低泛化誤差，輸出最終的對象離群值，離群值高的對象被算法判定為離群點。分別在四個不同領域的高維不均衡真實數據集上進行對比實驗，結果表明該算法與傳統離群點檢測算法和基于集成學習的離群點檢測算法相比，在AUC和precision@n值上平均提高了3.6%和14.45%，證明EROD算法具有處理高維不均衡數據異常的優勢。

關鍵詞：數據挖掘； 離群點檢測； 隨機投影； 集成學習

中圖分類號：TP311.1"" 文獻標志碼：A"" 文章編號：1001-3695（2022）09-007-2608-07

doi： 10.19734/j.issn.1001-3695.2022.02.0053

Outlier detection algorithm based on random projection and ensemble learning

Guo Yiyang1a， Yu Jiong1a，1b， Du Xusheng1a， Cao Ming2

（1. a.College of Information Science amp; Engineering， b.School of Software， Xinjiang University， Urumqi 830091， China; 2.Ocean University of China， College of Information Science amp; Engineering， Qingdao Shandong 266100， China）

Abstract：To address the problem that traditional similarity-based outlier detection algorithms were not effective enough on high-dimensional unbalanced datasets，this paper proposed a novel ensemble learning and random projection-based outlier detection （EROD） framework. Firstly，the EROD algorithm integrated several random projection methods to reduce the dimensionality of high-dimensional data，which improved the data diversity. Secondly，it integrated several different traditional outlier detectors to build a heterogeneous ensemble model，which increased the robustness of the algorithm. Finally，the EROD acquired the final outlier value of the object by using the heterogeneous ensemble model to train the reduced-dimensional data and by using two optimal combinations of the trained model to reduce the total error，and the algorithm determined the object with high outlier value as outlier point. The results show that the algorithm has an average improvement of 3.6% and 14.45% in AUC and precision@n value compared with the traditional outlier detection algorithm and the outlier detection algorithm based on ensemble learning. Therefore，the EROD algorithm has the advantage of handling the anomalies of high-dimensional unbalanced data.

Key words：data mining; outlier detection; random projection; ensemble learning

0 引言

與正常數據相比，離群點是具有不同特征的數據點，其被定義為：假設某一個數據在數據集中遠遠地偏離其他絕大多數數據，那么該數據被認知為與其他數據所產生的機制不相同，則它被判定為離群點［1］。之所以刪除離群點是數據挖掘中不可或缺的預處理步驟，是因為離群點的存在對數據統計分析的結果有嚴重的負面影響［2］。因此，為了刪除離群點，首先需要對其進行識別，這是離群點檢測算法的首要目標。

離群點檢測是一項重要的機器學習任務，它可以在許多具有高風險應用的常規數據對象中檢測出異常對象，例如流量反作弊檢測。

據《2020年中國異常流量報告》，異常流量約占整體的8.6個百分點。作為全球最大的廣告流量平臺，阿里媽媽（隸屬于阿里巴巴集團）擁有超過1 000億美元的商業流量，這代表著其為黑灰產業瞄準的首要對象。從阿里媽媽團隊的業務角度分析，流量反作弊檢測的核心思想之一是識別欺詐和低質量的異常流量內容，以保護客戶和平臺的權益。在當前的機器學習領域，流量反作弊檢測可能是對算法魯棒性和解釋性要求最高、精確度要求最高、系統規模和時效性要求最高、行業規模最大的業務。因此，流量反作弊檢測技術團隊必須要有“鐵打”的營盤，才能夠將離群點檢測技術與流量反作弊應用結合得更加緊密。在流量反作弊檢測任務中，高維不均衡數據的離群點檢測成為國內外相關團隊關注的首要焦點。

基于相似度的離群點檢測算法是常見的傳統無監督機器學習算法，但該種類離群點檢測算法在檢測高維數據時由于在距離計算方面面臨維度災難的挑戰，使其難以衡量對象在高維空間分布模式上的相似度，進而導致其在檢測高維不均衡數據集時，存在檢測率低、參數敏感性高等問題。在現實工業界實際環境中，在沒有真實的數據標簽的情況下，工程師們通常要構建大量、無監督的異質集成模型，即具有不同超參數的不同算法的集成模型，以便進一步地組合進行研究分析，而不是依靠單個算法。因此，本文提出了一種基于隨機投影和集成學習（EROD）的離群點檢測算法。

為了提升傳統的離群點檢測算法在高維不均衡數據集上的檢測正確率，EROD算法應用隨機投影對待檢測的數據集進行降維，集成傳統的離群點檢測算法對降維后的數據計算出所有數據對象的離群值，通過對傳統的離群點檢測算法進行動態分組與優化組合，組合后的離群值作為算法最終判定的離群值。在UCI（University of California，Irvine）真實數據集上的實驗表明，EROD算法與其他離群點檢測算法對比，檢測率得到了明顯提升。

本文的主要貢獻總結如下：

a）提出了一種新的無監督離群點檢測框架，在數據和模型上進行了異質集成。對隨機投影法進行集成以提升數據多樣性，集成傳統的離群點檢測算法以提升模型多樣性，通過兩個階段的組合，提升整體框架的檢測率。

b）針對傳統的離群點檢測算法在不同的高維不均衡數據集上存在不穩定性，利用集成的特性對傳統算法進行均衡處理，使得整體趨于穩定，提升了檢測率。

c）對傳統的離群點檢測算法進行了全面的參數敏感性分析，預測了整體框架的參數與性能，并對特別的數據集進行了可視化分析論述。

1 相關工作

從19世紀，研究學者們就已經展開了對離群點檢測的科學研究［3］。基于統計與概率的離群點檢測方法是一種較早提出的研究方法，這種方法根據統計與概率學原理檢測離群現象，具有時間復雜度低的優點。其核心思想是：首先，估計出數據集的分布模型；然后，假設其中的數據對象滿足該分布模型的分布規律；最后，通過評判數據對象與該分布模型是否一致來檢測出數據集中存在的離群點。文獻［4］受到統計函數Copula函數的啟發，通過利用Copula函數預測每個給定樣本的尾部分布概率，以確定其離群程度。但是這種方法需要預先準確地計算出分布模型的參數，如果不能預先準確地估計出該參數，那么將導致該方法得到的參數估計值與真實值之間存在顯著差異，使得離群點檢測的準確率大幅度降低。

由于基于統計與概率的離群點檢測方法的局限性，基于相似度的離群點檢測研究方法在21世紀初被提出。基于相似度的離群點檢測方法針對正常點和離群點在數據集中分布不同的特點，通過度量數據對象之間的相似度（如距離、密度、角度等）進行檢測離群點。在文獻［5］中，K最近鄰（K nearest neighbors，KNN）、K最近鄰平均數（average K nearest neighbors，Avg-KNN）和K最近鄰中位數（median K nearest neighbors，K-Median）通過計算樣本之間的歐氏距離來檢測離群點，但它們對參數設置非常敏感，且檢測高維數據時檢測率低。文獻［6］提出了首個基于密度的聚類局部離群因子（local outlier factor，LOF）檢測方法，該技術為每個數據對象分配一個離群因子，解決了把離群值看做二元屬性的問題，但無法處理多粒度和超參敏感性問題。Tang等人［7］對LOF進行改進，提出了基于連接的離群因子（connective-based outlier factor，COF），該方法通過計算連接距離作為最短路徑以估計鄰居的局部密度，其關鍵思想是基于低密度和孤立性之間的區分，但是該方法與LOF相比耗費更多的計算成本。文獻［8］提出了基于角度的離群點檢測（angle-based outlier detection，ABOD）方法，通過將加權余弦分值與所有近鄰點的方差作為離群分值，該方法的決策邊界比較復雜，容易導致過擬合。

從閱讀相關文獻獲知，集成學習的不同基檢測器各自產生獨立誤差，對多個基檢測器進行組合，可以在一定程度上緩解單一基檢測器的超參數敏感、訓練難度大和擬合效果差等問題［9］。文獻［10］提出了特征裝袋（feature bagging，FB）離群點檢測算法，該方法通過分離原始特征并創建隨機的特征子集，合并多個算法應用于該子集產生相應的離群分數，該算法提高了檢測性能，但由于其檢測器為同質檢測器這導致了其方法不夠多樣性；文獻［11］提出了一種輕量級異常在線檢測（lightweight on-line detector of anomalies，LODA）方法，其通過識別偏離大多數特征的數據進而檢測出離群點，該算法有著較低的時間復雜度，但由于單個檢測器輸出結果不穩定導致其檢測率比較低；文獻［12］提出孤立森林（isolation forest，IForest）算法，其集成多棵孤立樹并記錄這些孤立樹的路徑長度，以此作為計算離群分值的依據，但若是離群點樣本占比較高，與該算法所假設的離群點易被孤立的理論基礎互相沖突，致使產生不理想的結果。

可以看出，基于集成學習的離群點檢測算法可以通過側重于結合模型的輸出結果以生成穩定的集成模型，進而有效檢測離群點。這為本文解決上述基于相似度的離群點檢測算法局限性提供了思路，即EROD算法。EROD算法利用集成學習的特性對傳統算法進行均衡處理，且與組件檢測器選擇上的理論基礎互相補充，并提高了算法的魯棒性。同時，EROD算法在數據和模型上進行了異質集成，提升了整體結構的多樣性，并通過兩個階段的組合提升了算法的檢測率。

與上述離群點檢測算法相比，EROD具有魯棒性更強、檢測率更高以及不依賴先前假設的優勢。

2 本文方法與理論性質

表1詳細列出了本文后面內容所需的部分符號定義。

2.1 EROD算法整體框架與流程

EROD算法分為三個步驟實現：

a）降維。主要利用隨機投影法將高維數據隨機投影成低維數據。

b）構建組件檢測器集成模型。為了增強EROD算法的魯棒性，將不同類別的離群點檢測模型進行異質集成。

c）二階段聚合。將異質集成中多個組件檢測器隨機劃分成多個不同的集群，在不同的集群中選取每個集群中的最大值，對多個最大值求均值，該均值作為EROD判定的離群值。EROD算法整體框架與流程如圖1所示。

2.2 隨機投影集成

在離群點檢測過程中，絕大多數離群點檢測算法在高維數據上易受到維度災難的嚴重影響［13］。為了解決該問題，JL隨機投影法被廣泛使用進行消除維度災難所帶來的負面效果。JL隨機投影是一種降維算法，它之所以被廣泛使用在離群點檢測上面，是因為其降維機制可保持兩兩數據之間的相對距離，對高維數據在歐氏空間上進行低失真的壓縮，離群點的信息在壓縮過程中得以保留下來。更為重要的是，JL隨機投影法的隨機機制可增強集成學習的多樣性。

JL隨機投影的目的是近似保距，其理論基礎是Johnson-Lindenstrauss輔助定理［14］。如式（1）所示，JL隨機投影表示一種線性映射關系f：Rd→Rk，即將d維數據隨機投影為k維數據；如式（2）所示，由Johnson-Lindenstrauss輔助定理可知，1≤i≠j≤n，ε∈（0，3），要以較高的概率P滿足兩兩數據對象之間的相對距離保持在（1-ε，1+ε）內，需將數據對象降維到k=O（log（n）/ε2）維。

f（xi）=xiA" A∈Euclid ExtraaBpd×k（1）

P［（1－ε）‖xi－xj‖2≤‖f（xi）－f（xj）‖2≤（1+ε）‖xi－xj‖2］≤2e－ε2k6（2）

如表2所示，根據文獻［15］中的四種廣泛使用的隨機矩陣A，可將JL隨機投影劃分為四種方法。

在四種JL隨機投影法中，稀疏隨機投影法在時間效率上略優于另外三種隨機投影法［16］，故EROD算法采用稀疏隨機投影法。

如式（3）（4）所示，原始數據集X的特征空間是由n個具有d維特征的數據構成；稀疏隨機矩陣A是m個不同的稀疏隨機投影矩陣，每個稀疏隨機投影矩陣A∈Euclid ExtraaBpd×k，Yi是由稀疏隨機矩陣A作用在原始數據集X上得到的具有n個k維特征的數據，其中0lt;klt;d，i=1，2，…，m。

X={x1，x2，x3，…，xn}∈Euclid ExtraaBpn×d（3）

Yi=〈X，A〉∈Euclid ExtraaBpn×k（4）

EROD算法使用JL隨機投影法進行集成，其基本過程如下：首先，EROD算法使用稀疏隨機投影法生成m個不同的稀疏隨機投影矩陣A∈Euclid ExtraaBpd×k；然后，利用這m個稀疏矩陣A對高維數據集X∈Euclid ExtraaBpn×d進行投影，得到m個投影后的數據集Yi∈Euclid ExtraaBpn×k；最后，把Yi存入集合Y中，輸出集合Y。

算法1 隨機投影集成算法

輸入：數據集X∈Euclid ExtraaBpn×d，數據集X降維后的維度k。

輸出：集合Y。

a） initialize m sparse random projection matrix A={A1，A2，A3，… ，Am}∈Euclid ExtraaBpd×k // 初始化m個JL稀疏隨機投影矩陣A

b） for Ai in A do // 遍歷m個JL稀疏隨機投影矩陣A

c）"" Yi=〈X，Ai〉∈Euclid ExtraaBpn×k

// 對X進行隨機投影，得到投影后的數Yi

d）"" add（Yi，Y） // 把數據Yi存入集合Y

e） end for

f） output（Y） // 輸出集合Y

表2 隨機投影法說明

Tab. 2 Description of the random projection

JL隨機投影法A或Aij

高斯隨機投影Aij滿足獨立標準正態分布

離散隨機投影Aij=1kp=12

－1kp=12

循環隨機投影A=1kb0b1b2…bd－1bd－1b0b1…bd－2bd－2bd－1b0…bd－3bd－k+1bd－k+2bd－k+3…bd－k Λ

其中：b0，b1，…，bd－1滿足高斯分布;Λ為d×d對角矩陣，其對角線元素滿足獨立伯努利分布

稀疏隨機投影Aij=k" p=12k

0p=1－1k

－kp=12k

2.3 異質集成學習

EROD離群點檢測算法選擇KNN、Avg-KNN、K-Median、LOF、COF和ABOD檢測器作為異質集成學習模型的組件檢測器，即m=6。

之所以選擇這六種不同的離群點檢測算法作為異質集成學習模型中的組件檢測器，是因為相同的離群點檢測算法產生的相同輸出對集成學習的積極影響效果不明顯［17］，換句話說，一般情況下，不同的離群點檢測算法所構建成的異質集成學習模型會產生明顯的積極效果。這是因為不同的組件檢測器會促使集成學習在學習過程中產生多樣性，可以學習數據的不同特征，進一步提升模型的泛化能力。另外，相似度高的離群點檢測算法會產生相似的誤差，這會對預測結果帶來一定的消極影響［18］。

由于使用不同的、檢出率低的離群點檢測算法，雖然保證了一定的多樣性，但是模型的預測率將會降低，所以應平衡多樣性和檢測率之間的關系。

因此，本文使用KNN、Avg-KNN、K-Median、LOF、COF和ABOD檢測器這六種具有不同特色且檢測率在所有主流的離群點檢測算法中較高的離群點檢測算法作為異質集成學習模型的組件檢測器。

如式（5）所示，異質集成學習模型中每個組件檢測器對數據Y計算所獲得的分值，在此被稱為離群因子Outlier_Factor，每個組件檢測器的輸出為D（X）∈Euclid ExtraaBpn×1。

Outlier_Factor=［D1（Y），D2（Y），…，D6（Y）］∈Euclid ExtraaBpn×6（5）

異質集成基本過程如下：a）初始化異質集成模型中的六個組件檢測器；b）利用初始化后的組件檢測器檢測由算法1輸出的數據Y；c）判定組件檢測器的輸出值作為數據Y的離群值。

算法2 異質集成學習算法

輸入：集合Y={Y1，Y2，Y3，…，Ym}，集合D={D1，D2，D3，…，Dm}。

輸出：離群值矩陣OF。

a） for i=1∶Size（D） do

b）" initialize component detector Di // 對每個組件檢測器進行初始化

c） end for

d） for Yi in Y do // 遍歷集合Y

e）" for yj in Yi do // 遍歷數據集Yi

f）"" OF=Di（yj） /* 利用第i個組件檢測器檢測yj，得到yj的離群值Di（yj），將其作為離群值矩陣OF中的元素 /*

g）" end for

h） end for

i） output（OF） // 輸出離群值矩陣OF

算法2中全部組件檢測器在數據集Yi上輸出的離群值矩陣OF如式（6）所示。

OF=D1（y1）D2（y1）…D6（y1）

D1（y2）D2（y2）…D6（y2）

D1（yn）D2（yn）…D6（yn）

（6）

離群值矩陣OF的物理意義：該矩陣由數據集Yi中全部樣本的離群因子所構成，即矩陣中的某個元素代表某個檢測器對于某個樣本所評估的離群程度［19，20］。

2.4 二階段聚合方法

如圖2所示，偏差與方差之間存在反比關系，即隨著集成學習模型復雜程度的增加，偏差下降，方差上升。這是因為復雜程度低的模型在擬合能力上是欠缺的，即組件檢測器學習能力不夠強，此時偏差主導了泛化誤差；反之，則方差主導了泛化誤差。

圖2 偏差—方差—泛化誤差三者之間的關系

Fig. 2 Relationship among bias-variance-total error

通常情況下，對組件檢測器求均值可以達到降低方差，提高偏差的效果；對組件檢測器求最大值則可以達到降低偏差，提高方差的效果。由于單一地使用任何一種組合方式可能會導致所獲得的離群分值與真實分值產生較大的誤差［21］，所以，合理地結合均值和最大值兩種組件檢測器組合方式可以起到平衡偏差與方差的作用，使得泛化誤差降到一個合理范圍，提高檢測率。

由于泛化誤差可近似看成偏差的平方與方差之間的求和，所以，在第一階段，對組件檢測器求最大值，最大程度地降低泛化誤差；在第二階段，對余下的組件檢測器求均值，可使得偏差增加的幅度降到最低，進而最大程度地降低泛化誤差的上升幅度。

二階段聚合基本過程：a）對算法2的輸出進行歸一化處理，使不同離群點檢測模型的輸出值規范化到同一級量綱；b）將六個組件檢測器隨機劃分成兩個集群，且每個集群中所包含的三個離群點檢測模型存在互斥關系；c）從每個集群中選擇最大值作為該集群代表值，對每個集群代表值進行求平均，該均值作為EROD算法最終判定的數據對象離群值。

算法3 二階段聚合算法

輸入：離群值矩陣OF。

輸出：EROD算法最終判定的對象離群值。

a） ZOF=Z-normalization（OF） /*對OF進行歸一化處理（為避免數據表示雜亂，歸一化后的數據形式仍采用表1中的數學符號表示）*/

b） row=countRow（ZOF） // 計算矩陣ZOF行數

c） for j=1∶row do // 遍歷Y1～Y6中第j個數據

d）" for i=1∶6 do // 遍歷組件檢測器

e）"" detectors=Di（yj）

// 將矩陣ZOF每行中的離群值存入集合detectors

f）" end for

g） group1，group2=randomDivide（detectors） // 劃分集群

h） max1=Max（group1）

i） max2=Max（group2）

j） outlierScore=Average（max1，max2）

k） end for

l） output（outlierScore）

2.5 時間復雜度分析

設數據的數量和維度分別為n和d。算法1中，對數據進行預處理，遍歷數據進行隨機投影，該階段的時間復雜度為O（n）；算法2中，使用組件檢測器對數據進行計算，故該階段的復雜度取決于組件檢測器，且COF和ABOD檢測器都是Fast版本，故KNN、Avg-KNN、K-Median、LOF、COF和ABOD檢測器的時間復雜度分別為O（nd）、O（nd）、O（nd）、O（n）、O（n2）和O（n2），故該階段的時間復雜度為O（n2）；算法3中，該階段任務是對算法2中的計算結果進行優化組合，該階段的時間復雜度為O（n）。

綜上可得EROD算法的時間復雜度規模為O（n2）。

3 實驗

3.1 實驗環境

實驗的硬件環境是：處理器為Intel Xeon Gold 5117 CPU @ 2.00 GHz 2.00 GHz（2處理器），顯卡為NVIDIA Tesla V100 PCIE 16 GB（共3塊），內存（RAM）為256 GB。

實驗的軟件環境是：操作系統環境為Microsoft Windows Server 2016 Standard，算法的實現環境為PyCharm Professional、Python 3.6.2、TensorFlow 1.14。

3.2 數據集

如表3所示，為了評估本文方法的檢測性能，選擇了四組均來自UCI數據存儲庫的具有不同實際應用場景的真實數據集。下面分別對該四組數據集的具體信息進行詳細論述：

a）Arrhythmia數據集。該原始數據集承載的是心律失常的信息，屬于多類分類數據集，共16個類別和279個維度，其作用是區分是否存在心律失常現象。現對該原始數據集進行預處理，刪除5個維度，第3、4、5、7、8、9、14、15等一系列小類別被定義為離群，其余類為正常。處理后的數據集總共包含452個樣本對象，每個樣本包含274個維度，其中有66個樣本對象作為離群樣本。

b）Mnist數據集。該原始數據集承載的是手寫數字的圖像信息，包含數字0～9等10個圖像類別。現對該原始數據集進行預處理，數字0被定義為正常，其余數字被定義為離群，從原始數據集784個維度中隨機選擇100個維度作為處理后的樣本維度。處理后的數據集總共包含7 603個樣本對象，每個樣本包含100個維度，其中有700個樣本對象作為離群樣本。

c）Musk數據集。該原始數據集承載的是麝香分子的信息，其作用是根據分子區分是否為麝香。現對該原始數據集進行預處理，編號j146、j147和252等非麝香類被定義為正常，編號213和211等麝香類被定義為離群，刪除其他類別。處理后的數據集總共包含3 062個樣本對象，每個樣本包含166個維度，其中有97個樣本對象作為離群樣本。

d）Speech數據集。該數據集承載的是現實世界中語音的信息，其中美國口音占比最大，其作為正常類，其余口音被定位為離群。該數據集總共包含3 686個樣本對象，每個樣本包含400個維度，其中有61個樣本對象作為離群樣本。

3.3 評價指標

在評估檢測性能和指導檢測器建模時，評價指標起著不可或缺的作用。由于本文所使用的數據均為不平衡數據集，accuracy評價指標在數據不平衡時，其衡量結果往往不具備參考性。在機器學習領域，對該類數據集所使用的評價指標為AUC（area under curve）和precision@n。故本文使用這兩類評價指標。

AUC是ROC（receiver operating characteristic）曲線下的面積，其分值越大，則代表算法檢測性能越強。計算公式為

AUC=∑n+i=1 ∑n-j=1Ι［d（x+i）gt;d（x-j）］+12Ι［d（x+i）=d（x-j）］n+n-（7）

其中：n+和n-分別表示正樣本和負樣本的數量；xi和xj分別表示第i個和第j個樣本；d表示檢測器；I［］表示指示函數，該函數參數為真時，值等于1，否則等于0。

precision@n是precision指標的特殊情況，該種評價指標是在把離群點閾值設置成指定的n個正例時，檢測器輸出的precision分值。計算公式為

precision=TPTP+FP（8）

其中：TP表示離群樣本被正確標記為離群樣本的數量；FP表示正常樣本被錯誤標記為異常樣本的數量。

3.4 實驗設計

為驗證EROD算法將多個組件檢測器集成的有效性，將本文方法與KNN、Avg-KNN、K-Median、LOF、COF和ABOD六個組件檢測器以及FB、LODA和IForest三個集成學習算法分別進行了對比實驗；同時，為保證EROD算法的時效性，EROD算法與較新的同類方法EAOD（ensemble and autoencoder-based outlier detection，EAOD）［22］和GAN-VAE（generative adversarial network and variational auto-encoder based outlier detection，GAN-VAE）［23］在高維不均衡數據集Mnist上，以AUC值為評估指標進行了對比實驗。

在實驗中，EROD算法為了平衡維度災難和數據多樣性帶來的影響，JL隨機投影將數據維度壓縮為原來的三分之二。同時，為了探究EROD算法對其起到決定性參數的敏感程度，對集成學習中每個組件檢測器的近鄰參數k進行了敏感性實驗分析，進一步地從其中選擇出對EROD算法檢測性能影響較為積極的取值參數k，并以此建立EROD離群點檢測模型。

在實驗中，在分析并選擇出對EROD算法檢測性能影響較為積極的取值參數k后，對比算法KNN、Avg-KNN、K-Median、LOF、COF和ABOD的參數k與EROD中相對應的組件檢測器的參數k保持一致；在對比集成學習算法中，FB算法的基檢測器設置為LOF檢測器，且與EROD中組件檢測器LOF的參數保持一致；LODA算法中參數為自動優化；IForest算法的采樣大小參數Ψ設置為256和樹的數目參數tn設置為100；同時，為保證實驗的公平性和合理性，設置EAOD中檢測器個數與EROD中檢測器個數等同。

為了確保本實驗的結果具有穩定性，現對EROD算法和其對比算法分別執行10次，對該10次產生的結果計算均值作為最終的結果。

3.5 參數敏感性分析與選擇

為了使用EROD算法進行離群點檢測，本文對集成模型中各個組件檢測器中的近鄰參數k做不同的取值進行對比實驗，進一步地從中選擇出對EROD算法檢測性能影響較為積極的取值參數k，并建立EROD離群點檢測模型。

近鄰參數k具體選擇策略為：首先，近鄰參數k取值為［10，100］，取值間隔為10；然后，在不同k值上，分析組件檢測器在Arrhythmia、Mnist、Musk、Speech這四個數據集上的四個AUC分值，對這四個AUC分值取均值；最后，對計算得到的10個AUC均值取最大值，該最值對應的k值作為組件檢測器的近鄰參數理想選取值的參考依據。具體過程如算法4所示。

算法4 組件檢測器近鄰參數k選擇策略

輸入：k值初始值，組件檢測器D，數據集Arrhythmia、Mnist、Musk、Speech。

輸出：k值參考值。

a） k=［10，20，30，40，50，60，70，80，90，100］

b） AUC=［］

c） avgAUC=［］

d） max=0

e） j=1

f） for i=k［j］，ilt;101， j=j+1 do

g）"" AUC.append（D（i，Arrhythmia））

h）"" AUC.append（D（i，Mnist））

i）"" AUC.append（D（i，Musk））

j）"" AUC.append（D（i，Speech））

k）"" avgAUC.append（Average（AUC））

l） end for

m） k_reference=Max（avgAUC）

n） output（k_reference）

如圖3所示，KNN組件檢測器在Arrhythmia、Mnist、Musk、Speech數據集上：

從k=10逐次遞增到k=40的過程中，AUC均值處于顯著上升趨勢；從k=40逐次遞增到k=80的過程中，AUC均值漲幅較為微小；從k=80逐次遞增到k=90的過程中，AUC均值處于不明顯下降狀態；AUC均值在k=90和k=100兩處相等；當k=80時，AUC均值達到最大值0.783 8。但是，從k=40開始，AUC均值變化不大。因此，KNN組件檢測器在k=40時處于最優狀態。

如圖4所示，Avg-KNN組件檢測器在Arrhythmia、Mnist、Musk、Speech數據集上：

從k=10逐次遞增到k=100的過程中，AUC均值變化趨勢為上升狀態。其中，從k=10遞增到k=50的過程中，AUC均值上升幅度較為明顯；從k=50以后，AUC均值上升幅度較小；當k=100時，AUC均值達到最大值0.784 0。因此，Avg-KNN組件檢測器在k=50時處于最優狀態。

如圖5所示，K-Median組件檢測器在Arrhythmia、Mnist、Musk、Speech數據集上：

從k=10逐次遞增到k=100的過程中，AUC均值不斷上升。當k從10增加至60時，AUC上升較為顯著；當k從60增加至100時，AUC上升較為細微；當k=100時，AUC均值達到最大值0.782 1。因此，K-Median組件檢測器在k=60時處于最優狀態。

如圖6所示，LOF組件檢測器在Arrhythmia、Mnist、Musk、Speech數據集上：

從k=10逐次遞增到k=100的過程中，AUC均值先上升，后下降，再上升。其中，當k從10增加到20時，AUC均值顯著上升；當k從20增加到80時，AUC均值近似于線性下降；當k從80增加到100時，AUC均值激增；當k=100時，AUC均值達到最大值0.761 2。從宏觀角度觀察，k=100對應的AUC均值明顯高于其他k值對應的AUC均值。因此，LOF組件檢測器在k=100時處于最優狀態。

如圖7所示，COF組件檢測器在Arrhythmia、Mnist、Musk、Speech數據集上：

從k=10逐次遞增到k=100的過程中，AUC均值先上升，后下降，其中，當k由10增加到50的過程中，AUC均值處于上升狀態；當k由50增加到100的過程中，AUC均值處于下降狀態；當k=50時，AUC均值達到峰值0.639 7。因此，COF組件檢測器在k=50時處于最優狀態。

如圖8所示，ABOD組件檢測器在Arrhythmia、Mnist、Musk、Speech數據集上：

從k=10逐次遞增到k=100的過程中，AUC均值先下降，再上升，但是其變化幅度十分細微。其中，k由10增加到70時，AUC均值以近似于水平的細微程度緩慢下降；k由70增加到100時，AUC均值又以近似于水平的細微程度緩慢上升；當k=10時，AUC均值達到峰值0.580 7。因此，ABOD組件檢測器在k=10時處于最優狀態。

綜上所述，KNN、Avg-KNN、K-Median、LOF、COF、ABOD這六個組件檢測器的近鄰參數k分別取值為40，50，60，100，50，10時，它們的性能處于最優。因此，選取這些近鄰參數取值作為EROD算法中各個組件檢測器的近鄰參數取值。

3.6 實驗結果與分析

表4給出了在四個不同的高維數據集上EROD與KNN、Avg-KNN、K-Median、LOF、COF和ABOD的比較結果，表中加粗的數字代表檢測性能最強的兩個算法。而且，圖9和10分別給出了在不同數據集上各算法的AUC和precision分值的比較。

表5給出了在四個不同的高維數據集上EROD與FB、LODA和IForest等三個集成學習算法的比較結果，表中加粗的數字代表檢測性能最強的兩個算法。而且，圖11和12分別給出了在不同數據集上各算法的AUC和precision分值的比較。

圖13給出了EROD與較新的兩個同類方法EAOD和GAN-VAE在高維不均衡數據集Mnist上，以AUC值為評估指標進行了對比實驗。

對于EROD算法相比較于各組件檢測器可以看出，在Arrhythmia、Mnist、Musk上，EROD算法的兩個評價指標均優于其他算法：在Arrhythmia上，AUC和precision分值相較于檢測性能次高的算法分別提升了1.2個百分點和1.7和百分點；在Mnist上，AUC和precision分值相較于檢測性能次高的算法分別提升了1.3個百分點和2.7個百分點；在Musk上，AUC和precision分值相較于檢測性能次高的算法分別提升了0.9個百分點和1.6個百分點。但是，在Speech上，EROD算法的兩個評價指標均處于次高狀態，這是因為集成框架中大部分組件檢測器在該數據集上表現較差，導致EROD算法平衡泛化誤差的能力有所降低，但EROD的表現優于大部分組件檢測器。

對于EROD算法相比較于其他集成學習算法可以看出，在Arrhythmia、Mnist、Speech上，EROD算法的兩個評價指標均優于其他算法：在Arrhythmia上，AUC和precision分值相較于檢測性能次高的算法分別提升了1.2個百分點和3.4個百分點；在Mnist上，AUC和precision分值相較于檢測性能次高的算法分別提升了8.2個百分點和44個百分點；在Speech上，AUC和precision分值相較于檢測性能次高的算法分別提升了11.2個百分點和33.3個百分點。但是，在Musk上，EROD算法在precision分值上稍遜于IForest算法，但在AUC分值上均優于其他算法，相較于檢測性能次高的算法提升了1.2個百分點，這是因為衡量指標在統計學上側重點不同，導致EROD算法在AUC和precision分值上一高一低。

對于EROD算法相比較于較新的同類方法EAOD和GAN-VAE，在高維不均衡數據集Mnist上，AUC分值分別提升了1.02%和0.46%，這證明了EROD在解決同種問題上的先進性。

在表4和5中，在Speech數據集上，無論是何種算法，在該數據集上分值普遍較低。如圖14所示，Speech在2D可視化圖像中，紅色菱形表示離群點（見電子版），其余表示正常點，可以看出這是因為在該數據集中，離群點與正常點高度地混合在一起，隱藏在正常點內部，且在維度分布上未處于尾部位置，導致其在維度分布上與正常點高度相似，使得離群點檢測算法無法達到最佳檢測性能。只有離群點位于暴露明顯的尾部時，離群點檢測算法才可精準地捕獲與識別。

綜上所述，通過與各種離群點檢測算法在多個高維數據集上的對比實驗，驗證了EROD算法的有效可行性。

4 結束語

本文提出一種新的離群點檢測框架——EROD，算法集成隨機投影對高維數據進行降維，同時提升了數據多樣性，通過對多個異質離群點檢測器進行集成，提升了算法魯棒性，之后異質集成模型對多個降維后的數據進行訓練，并分兩次對訓練后的模型進行組合，有效降低了泛化誤差，提升了算法檢測性能。同時，從理論上分析了算法的參數敏感性，并討論了集成組件檢測器時超參的選擇依據。在UCI數據集上實驗，以AUC和precision為評價指標對算法進行評估，與傳統的離群點檢測算法和基于集成學習的離群點檢測算法進行比較，實驗結果表明EROD算法具有處理高維不均衡數據異常的優勢。同時，考慮到隨機投影和異質檢測器的集成機制對EROD算法效率的作用，是值得深入探討的課題。進一步研究將從實驗上研究不同的降維方式和檢測器對EROD算法的影響以及從理論上分析EROD算法泛化誤差臨界點和其組件檢測器泛化誤差臨界點的關系。

參考文獻：

［1］Boukerche A，Zheng L，Alfandi O. Outlier detection： methods，models，and classification ［J］. ACM Computing Surveys，2020，53（3）： 1-37.

［2］Najafi M，He Lifang，Philip S Y. Outlier-robust multi-aspect streaming tensor completion and factorization ［C］// Proc of the 28th International Joint Conference on Artificial Intelligence. San Mateo，CA： Morgan Kaufmann Publishers，2019： 3187-3194.

［3］Walfish S. A review of statistical outlier methods ［J］. Pharmaceutical Technology，2006，30（11）： 82.

［4］Li Zheng，Zhao Yue，Botta N，et al. COPOD： copula-based outlier detection ［C］// Proc of the 20th International Conference on Data Mi-ning. Piscataway，NJ： IEEE Press，2020： 1118-1123.

［5］Aggarwal C C. Outlier analysis ［M］. 2nd ed. Berlin： Springer，2017： 1-34.

［6］Breunig M M，Kriegel H P，Ng R T，et al. LOF： identifying density-based local outliers ［C］// Proc of SIGMOD. New York： ACM Press，2000： 93-104.

［7］Tang Jian，Chen Zhixiang，Fu A W C，et al. Enhancing effectiveness of outlier detections for low density patterns ［C］// Proc of PAKDD. Berlin： Springer，2002： 535-548.

［8］Kriegel H P，Schubert M，Zimek A. Angle-based outlier detection in high-dimensional data ［C］// Proc of the 14th ACM Knowledge Discovery and Data Mining. New York： ACM Press，2008： 444-452.

［9］Chen Wenqi，Wang Zhiliang，Zhong Ying，et al. ADSIM： network anomaly detection via similarity-aware heterogeneous ensemble lear-ning ［C］// Proc of the 17th IFIP/IEEE International Symposium on Integrated Network Management. Piscataway，NJ： IEEE Press，2021： 608-612.

［10］Lazarevic A，Kumar V. Feature bagging for outlier detection ［C］// Proc of the 11th ACM Knowledge Discovery and Data Mining. New York： ACM Press，2005： 157-166.

［11］Pevny T. Loda： lightweight on-line detector of anomalies ［J］. Machine Learning，2016，102（2）： 275-304.

［12］Liu F T，Ting Kaiming，Zhou Zhihua. Isolation forest ［C］// Proc of the 8th International Conference on Data Mining. Piscataway，NJ： IEEE Press，2008： 413-422.

［13］Pang Guansong，Cao Longbing，Chen Ling，et al. Learning representations of ultrahigh-dimensional data for random distance-based outlier detection ［C］// Proc of the 24th ACM Knowledge Discovery and Data Mining. New York： ACM Press，2018：2041-2050.

［14］Cohen M B，Jayram T S，Nelson J. Simple analyses of the sparse Johnson-Lindenstrauss transform ［C］// Proc of the 1st Symposium on Simplicity in Algorithms. Philadelphia，PA： SIAM Press，2018： 1-9.

［15］Jin Ruhui，Kolda T G，Ward R. Faster Johnson-Lindenstrauss transforms via Kronecker products ［J］. Information and Inference： Journal of the IMA，2021，10（4）： 1533-1562.

［16］Venkatasubramanian S，Wang Qiushi. The Johnson-Lindenstrauss transform： an empirical study ［C］// Proc of the 13th Workshop on Algorithm Engineering and Experiments. Philadelphia，PA： SIAM Press，2011： 164-173.

［17］Pasillas-Diaz J R，Ratte S. An unsupervised approach for combining scores of outlier detection techniques，based on similarity measures ［J］. Electronic Notes in Theoretical Computer Science，2016，329： 61-77.

［18］Aggarwal C C，Sathe S. Outlier ensembles： an introduction ［M］. Berlin： Springer，2017： 35-73.

［19］杜旭升，于炯，陳嘉穎，等. 一種基于鄰域系統密度差異度量的離群點檢測算法 ［J］. 計算機應用研究，2020，37（7）： 1969-1973. （Du Xusheng，Yu Jiong，Chen Jiaying，et al. Outlier detection algorithm based on neighborhood system density difference measurement ［J］. Application Research of Computers，2020，37（7）： 1969-1973.）

［20］杜旭升，于炯，葉樂樂，等. 基于圖上隨機游走的離群點檢測算法 ［J］. 計算機應用，2020，40（5）： 1322-1328. （Du Xusheng，Yu Jiong，Ye Lele，et al. Outlier detection algorithm based on graph random walk ［J］. Journal of Computer Applications，2020，40（5）： 1322-1328.）

［21］Aggarwal C C，Sathe S. Theoretical foundations and algorithms for outlier ensembles ［J］. ACM SIGKDD Explorations Newsletter，2015，17（1）： 24-47.

［22］郭一陽，于炯，杜旭升，等. 基于自編碼器與集成學習的離群點檢測算法 ［J］. 計算機應用，2022，42（7）：2078-2087. （Guo Yiyang，Yu Jiong，Du Xusheng，et al. Outlier detection algorithm based on autoencoder and ensemble learning ［J］. Journal of Computer Applications，2022，42（7）：2078-2087.

［23］金利娜，于炯，杜旭升，等. 基于生成對抗網絡和變分自編碼器的離群點檢測算法 ［J］. 計算機應用研究，2022，39（3）： 774-779. （Jin Lina，Yu Jiong，Du Xusheng，et al. Generative adversarial network and variational auto-encoder based outlier detection［J］. Application Research of Computers，2022，39（3）： 774-779.）