謝 雨，蔣 瑜，龍超奇

（成都信息工程大學(xué)軟件工程學(xué)院，成都 610225）

（?通信作者電子郵箱jiangyu@cuit.edu.cn）

0 引言

大數(shù)據(jù)時(shí)代的到來，使得海量的數(shù)據(jù)被收集和存儲(chǔ)在數(shù)據(jù)庫中，從體量巨大的數(shù)據(jù)中挖掘可理解的知識顯得更加有意義。作為數(shù)據(jù)挖掘工作中重要的一環(huán)，異常檢測算法正在蓬勃發(fā)展［1］。越來越多的異常點(diǎn)檢測算法正在進(jìn)一步被運(yùn)用于日常生活的方方面面［2］。

近年來，國內(nèi)外學(xué)者研究提出了多種異常檢測算法。文獻(xiàn)［3］中對這些算法進(jìn)行了分類總結(jié)。按照異常識別技術(shù)分為:以基于角度的離群值檢測（Angle-Based Outlier Detection，ABOD）算法［4］與基于連接函數(shù)的異常檢測（COPula-based Outlier Detection，COPOD）算法［5］為代表的基于統(tǒng)計(jì)的方法；以K最近鄰（K-Nearest Neighbor，KNN）分類算法［6］為代表的基于距離的方法；以局部異常因子（Local Outlier Factor，LOF）算法［7］為代表的基于密度的方法；以及以自編碼器（Autoencoder）［8］為代表的基于學(xué)習(xí)的方法等。除此之外，基于集成的方法同樣也在不斷地被研究，其中具有代表性的技術(shù)包括:Bagging［9］與Boosting［10］抽樣等。文獻(xiàn)［11］中提出了一種基于隔離思想［12］的集成學(xué)習(xí)算法［1］:孤立森林（isolation Forest，iForest）算法，該算法首先構(gòu)建了一個(gè)由多棵孤立樹組成的孤立森林，隨后將待檢測數(shù)據(jù)點(diǎn)在孤立森林中進(jìn)行遍歷，記錄該數(shù)據(jù)點(diǎn)被完全隔離的平均路徑長度并生成對應(yīng)的異常分?jǐn)?shù)。文獻(xiàn)［13］中指出由于iForest 算法的核心思想為隔離，且每棵孤立樹通過隨機(jī)選擇的特征值來進(jìn)行隔離，所以該算法具有計(jì)算速度快、準(zhǔn)確度高與內(nèi)存占用低等優(yōu)點(diǎn)。

傳統(tǒng)方法在各個(gè)領(lǐng)域內(nèi)被廣泛應(yīng)用，可以通過不同方法的結(jié)合產(chǎn)生性能更優(yōu)的異常檢測模型。文獻(xiàn)［14］中結(jié)合LOF算法的最近鄰思想與iForest 算法的隔離思想，提出使用最近鄰集合進(jìn)行隔離（isolation using Nearest Neighbor Ensemble，iNNE）的異常檢測算法，使用最近鄰隔離超球體來隔離目標(biāo)空間中的數(shù)據(jù)。該算法是一種基于隔離思想的高精度集成學(xué)習(xí)算法，具有精度高的優(yōu)點(diǎn)，但在樣本數(shù)量巨大的數(shù)據(jù)集中，時(shí)間開銷太大。文獻(xiàn)［15］中結(jié)合多粒度掃描機(jī)制，提出了基于多粒度隨機(jī)超平面的孤立森林（Multi-dimensional Random Hyperplane iForest，MRHiForest）算法，該算法在多個(gè)小于原始數(shù)據(jù)空間的k維空間內(nèi)分別構(gòu)建孤立森林，通過多個(gè)森林集成投票機(jī)制，構(gòu)成層次化集成學(xué)習(xí)的異常檢測模型。該模型提高了在高維數(shù)據(jù)集上進(jìn)行異常檢測工作的穩(wěn)定性與準(zhǔn)確性，但存在精度下降、時(shí)間開銷增加等缺點(diǎn)。

文獻(xiàn)［16］中指出，iForest算法雖然效率與精度很高，但由于隔離條件通常為軸平行的，軸平行的隔離條件必然會(huì)導(dǎo)致隔離平面的交叉，進(jìn)而產(chǎn)生呈規(guī)則分布的異常分?jǐn)?shù)不準(zhǔn)確區(qū)域。文獻(xiàn)［17］中進(jìn)一步指出，在高維數(shù)據(jù)空間中使用iForest算法將導(dǎo)致類似的異常分?jǐn)?shù)不準(zhǔn)確區(qū)域大量存在，因此將這種問題定義為“局部異常不敏感問題”，并在最后提出了擴(kuò)展隔離林（Extended Isolation Forest，EIF）算法，該算法則完全解決了孤立森林算法對局部異常不敏感的問題。但由于EIF 算法在擴(kuò)展孤立樹的每一個(gè)節(jié)點(diǎn)上進(jìn)行隔離計(jì)算時(shí)，都需要進(jìn)行一次向量點(diǎn)乘運(yùn)算，所以在預(yù)測中高維數(shù)據(jù)時(shí)，其時(shí)間開銷往往遠(yuǎn)大于iForest算法。

綜上所述，iForest 算法對局部異常不敏感的問題會(huì)導(dǎo)致部分異常點(diǎn)無法被準(zhǔn)確檢測，而EIF 算法雖然解決了局部異常不敏感的問題，但由于該算法的時(shí)間開銷太大，在高速發(fā)展的當(dāng)下并不適用。

因此，本文結(jié)合子空間思想提出了基于隨機(jī)子空間的擴(kuò)展隔離林（Extended Isolation Forest based on Random Subspace，RS-EIF）算法。該算法從數(shù)據(jù)空間中隨機(jī)選擇維度構(gòu)建子空間，并使用隨機(jī)超平面來避免軸平行隔離條件下隔離條件重合區(qū)域的產(chǎn)生。本文算法在解決iForest算法對局部異常不敏感問題的同時(shí)，相較于EIF算法減少了計(jì)算開銷。

1 相關(guān)工作

1.1 iForest算法

1.1.1 孤立森林的構(gòu)建

設(shè)數(shù)據(jù)集D={d1，d2，…，dn}且D?Ru，其中Ru為實(shí)數(shù)集，u為最高維度，n為數(shù)據(jù)個(gè)數(shù)，di={xi1，xi2，…，xiu}，其中i∈[0，n]。

文獻(xiàn)［12］定義孤立森林的構(gòu)建過程為:首先，在數(shù)據(jù)集D中隨機(jī)抽取η次，每次確定ψ個(gè)樣本作為訓(xùn)練集；然后，在每次抽樣完成后，以lbψ為高度限制構(gòu)建一棵孤立樹；最后，在構(gòu)建η棵孤立樹后，集成為一個(gè)孤立森林。

在每一個(gè)孤立森林中，包含的孤立樹均為二叉樹結(jié)構(gòu)，下面給出孤立樹的定義。

定義1孤立樹。從［1，u］中隨機(jī)確定一個(gè)整數(shù)p作為隨機(jī)選擇的維度，統(tǒng)計(jì)維度p的范圍［pmin，pmax］，并在該范圍下隨機(jī)確定隔離條件q。當(dāng)訓(xùn)練集ψ中的數(shù)據(jù)點(diǎn)在p維度的值小于q時(shí)，將該數(shù)據(jù)確定為節(jié)點(diǎn)的左子樹節(jié)點(diǎn)；反之確定為右子樹節(jié)點(diǎn)。遞歸構(gòu)建一棵高度限制為lbψ的二叉搜索樹。

完成構(gòu)建孤立森林后，得到一個(gè)基于樹形結(jié)構(gòu)的集成學(xué)習(xí)模型［18］。

1.1.2 孤立森林的缺點(diǎn)

在孤立森林中，數(shù)據(jù)點(diǎn)的異常程度通常由數(shù)據(jù)點(diǎn)在每棵孤立樹中遍歷的深度決定。這里的深度指的是數(shù)據(jù)點(diǎn)在空間中被劃分到無法繼續(xù)劃分的子空間時(shí)所需的劃分次數(shù)h。使用數(shù)據(jù)dk在具有η棵孤立樹的孤立森林中進(jìn)行遍歷，得到路徑深度集合H(dk)={h1，h2，…，hη}，并求得平均深度E(h)。最后，將平均深度值通過式（1）歸一化處理為一個(gè)取值范圍為0～1的異常分?jǐn)?shù)s(dk，n)。

式中，c(n)為歸一化因子，被定義為搜索失敗的平均路徑［12］。式（2）為c(n)的具體計(jì)算方式:

其中，H(i)為調(diào)和級數(shù)，可以通過ln(i)+0.577 215 664 9（歐拉常數(shù)）確定。

數(shù)據(jù)并不只是單一地分布在一個(gè)聚類中心，真實(shí)的數(shù)據(jù)往往具有多個(gè)聚類中心［19］。由于iForest算法的隔離條件是軸平行的，在多元數(shù)據(jù)集中，算法會(huì)因隔離條件的重疊使得局部異常難以被檢測到，從而導(dǎo)致算法精度下降。針對該問題，提出了基于隨機(jī)斜率構(gòu)建超平面的EIF算法［17］。

1.2 EIF算法

1.2.1 EIF算法相關(guān)定義

EIF 算法基于iForest 算法進(jìn)行改進(jìn)，將軸平行的隔離條件替換為具有隨機(jī)斜率［20］的超平面。

定義2隨機(jī)斜率。在二維空間中，隨機(jī)超平面可以理解為線，而線段是具有斜率的，其斜率可以用平面內(nèi)隨機(jī)一個(gè)點(diǎn)到原點(diǎn)的向量表示。同理，在k維的高維空間中，其隨機(jī)斜率可以表示為空間內(nèi)的向量j=(i1，i2，…，ik)，其中i∈[0，1)且隨機(jī)生成。

本文將一個(gè)N維空間定義為一個(gè)具有N條坐標(biāo)軸的空間。若存在一個(gè)超平面與N條坐標(biāo)軸中的一條相交，則稱該超平面的擴(kuò)展程度為0。以二維空間為例，在二維空間中，當(dāng)擴(kuò)展等級為0 時(shí)，隔離超平面可以理解為一條平行于坐標(biāo)軸的直線。由于超平面需要由斜率與截距確定，下面給出自定義隔離等級的隨機(jī)截距向量與隔離超平面的定義。

定義3自定義隔離等級的隨機(jī)截距向量。在維度為k的空間中，存在s=(n1，n2，…，nk)，當(dāng)隔離等級為k-1 時(shí)，n1，n2，…，nk均為不為0的實(shí)數(shù)。

定義4隔離超平面。在EIF 算法中，通過隨機(jī)生成超平面的隨機(jī)斜率j與具有自定義隔離等級的存在于超平面上的隨機(jī)截距s可以確定一個(gè)唯一的隔離超平面。

在確定隔離超平面后，隔離條件確定為:(d-s)·j，其中d表示來自數(shù)據(jù)集D中的一個(gè)待檢測數(shù)據(jù)點(diǎn)。當(dāng)隔離條件的值小于0 時(shí)，將d劃分到當(dāng)前根節(jié)點(diǎn)的左子樹，反之劃分到當(dāng)前節(jié)點(diǎn)的右子樹。

1.2.2 EIF算法的優(yōu)勢

為了展示由于隔離平面軸平行導(dǎo)致的精度下降的問題，本節(jié)首先使用基于正弦函數(shù)分布的二維數(shù)據(jù)集來計(jì)算各個(gè)點(diǎn)的異常分?jǐn)?shù)，并使用熱圖分別繪制EIF 算法與iForest 算法對該數(shù)據(jù)集進(jìn)行分析后的得分分布。實(shí)驗(yàn)數(shù)據(jù)集為隨機(jī)在正弦曲線兩側(cè)呈高斯分布的1 000個(gè)二維數(shù)據(jù)點(diǎn)。隨后，對所得的數(shù)據(jù)分別使用EIF 算法與iForest 算法進(jìn)行預(yù)測后，將所得到的異常分?jǐn)?shù)劃分為10 個(gè)不同的等級，為每個(gè)等級標(biāo)注邊界，并使用熱圖繪制邊界。兩種算法的得分熱圖如圖1所示。

iForest 算法得分熱圖如圖1（a）所示，而EIF 算法得分熱圖則如圖1（b）所示。對比兩個(gè)圖可以發(fā)現(xiàn)，正弦函數(shù)的任意兩個(gè)波峰或波谷之間，EIF 算法計(jì)算得到的異常分?jǐn)?shù)相較于iForest 算法異常分?jǐn)?shù)更加具有層次感；而且在EIF 算法的得分熱圖中，在數(shù)據(jù)分布外并沒有存在矩形的得分異常區(qū)域。因此，EIF 算法可以更好地計(jì)算處在正弦函數(shù)任意兩個(gè)波峰或波谷之間局部數(shù)據(jù)點(diǎn)的異常得分。

圖1 正弦分布數(shù)據(jù)上不同算法得分熱圖Fig.1 Score heat maps of different algorithms on sine distribution data

1.2.3 EIF算法的劣勢

EIF 算法核心為使用隨機(jī)隔離超平面進(jìn)行隔離。假設(shè)使用維度為k的數(shù)據(jù)集構(gòu)建一個(gè)包含η棵孤立樹的擴(kuò)展隔離林，其中，每棵樹均為平衡二叉樹且包含有256 個(gè)節(jié)點(diǎn)，每棵樹的擴(kuò)展等級均設(shè)定為k-1。現(xiàn)存在隨機(jī)生成的數(shù)據(jù)點(diǎn)m=(x1，x2，…，xk)，要想計(jì)算出該點(diǎn)的異常分?jǐn)?shù)，在iForest 森林中，最多只需要進(jìn)行8η次、最少僅需要η次比較運(yùn)算即可得出數(shù)據(jù)點(diǎn)m的遍歷深度。

在EIF 森林中，每個(gè)節(jié)點(diǎn)上需要進(jìn)行1 次向量減法與1 次向量乘法運(yùn)算（在k維數(shù)據(jù)集中，需要進(jìn)行k次減法、k次加法與k次乘法運(yùn)算），即:最多需要8η次、最少η次向量運(yùn)算。雖然在EIF 算法中的計(jì)算時(shí)間總體是呈線性增長的［16］，但相較于iForest算法，EIF算法的時(shí)間成本過高。

2 RS-EIF算法

首先，引入子空間思想，在介紹子空間思想在EIF 算法中的應(yīng)用后，結(jié)合集成學(xué)習(xí)的優(yōu)點(diǎn)，使用隨機(jī)子空間思想完成算法改進(jìn)。然后，分析改進(jìn)后算法RS-EIF 的時(shí)間復(fù)雜度與空間復(fù)雜度。

2.1 隨機(jī)子空間優(yōu)化

根據(jù)多粒度思想［15］，本文將子空間定義為維度小于目標(biāo)空間并存在于目標(biāo)空間中的一個(gè)空間，此處的目標(biāo)空間被定義為數(shù)據(jù)集所在的高維空間［21］。由此可知，擴(kuò)展等級為k-1的EIF 算法可以理解為在維度為k-1 的子空間中構(gòu)建維度為k的隨機(jī)斜率向量與隨機(jī)截距向量，其中k為目標(biāo)空間維度。因此，EIF 算法可以理解為在一個(gè)完整的數(shù)據(jù)空間中，以子空間思想對數(shù)據(jù)進(jìn)行隔離。

在文獻(xiàn)［17］中，隨著EIF 算法擴(kuò)展等級的提高，算法對局部異常的敏感性也隨之提升。因此，為了在實(shí)驗(yàn)中獲得最高的精確度，擴(kuò)展等級往往需要設(shè)置為k-1。

然而，在最高擴(kuò)展等級的子空間中構(gòu)建擴(kuò)展隔離森林雖然可以得到一個(gè)高精度的異常檢測模型，但是隨之而來的是大量上升的運(yùn)算成本。因此考慮在更小的子空間中構(gòu)建擴(kuò)展隔離森林來提高運(yùn)算速度。

EIF 算法本身是一種集成學(xué)習(xí)算法，并包含多個(gè)弱分類器。在EIF 算法中，雖然一棵擴(kuò)展隔離樹的預(yù)測結(jié)果并不令人滿意，但在組合多棵樹構(gòu)成森林后，其預(yù)測結(jié)果變得優(yōu)于多數(shù)傳統(tǒng)的異常檢測算法。

因此，本文在隨機(jī)子空間l中生成具有擴(kuò)展等級的隨機(jī)斜率j'與隨機(jī)截距向量s'，其中l(wèi)＜k。再將隔離條件優(yōu)化為d·j'＜s'·j'來確定數(shù)據(jù)點(diǎn)是否存在于l維子空間中的隔離超平面內(nèi)。由此方法構(gòu)建的樹結(jié)構(gòu)命名為隨機(jī)擴(kuò)展隔離樹RS-Tree（Random Subspace Tree）。

由于RS-Tree的精度會(huì)低于原本的擴(kuò)展隔離樹，因此再通過構(gòu)建多棵基于隨機(jī)子空間的RS-Tree 組成一個(gè)完整的模型來提高算法的精度。下面，給出構(gòu)建RS-EIF 森林的偽代碼如算法1所示。

算法1 rsForest（X，t，ψ，k，extendlevel）。

輸入 數(shù)據(jù)集X，樹的棵數(shù)t，每棵樹包含的節(jié)點(diǎn)個(gè)數(shù)ψ，隨機(jī)子空間維度k，樹的擴(kuò)展等級extendlevel；

輸出 包含t棵RS-Tree的RS-EIF森林。

算法1 需要構(gòu)建RS-EIF 森林，該過程與EIF 算法中的擴(kuò)展隔離樹構(gòu)建過程類似。而森林中是包含多棵樹的，因此給出樹的構(gòu)建偽代碼如算法2所示。

算法2 rsTree（X，e，l，k，extendlevel）。

輸入 數(shù)據(jù)集X，當(dāng)前樹的高度e，樹的高度限制l，子空間維度k，樹的擴(kuò)展等級extendlevel；

輸出 1棵RS-Tree。

在一個(gè)完整的RS-EIF 森林中，要想實(shí)現(xiàn)對數(shù)據(jù)的決策判斷，需要將該數(shù)據(jù)在森林中的每棵樹進(jìn)行遍歷，計(jì)算其平均路徑長度，最終給出判斷結(jié)果。下面給出計(jì)算遍歷深度的偽代碼如算法3所示。

算法3 PathCount（d，tree，e，k）。

輸入 數(shù)據(jù)點(diǎn)d，RS-Tree 的節(jié)點(diǎn)tree，當(dāng)前路徑長度e，隨機(jī)子空間維度k；

輸出 數(shù)據(jù)點(diǎn)d的路徑遍歷長度。

最終，在計(jì)算出目標(biāo)數(shù)據(jù)點(diǎn)的平均路徑長度（平均深度）后，再使用式（1）處理為對應(yīng)的異常分?jǐn)?shù)。異常分?jǐn)?shù)越高，則數(shù)據(jù)的異常程度就越高。

2.2 時(shí)間與空間開銷分析

2.2.1 時(shí)間開銷分析

假設(shè)在n個(gè)維度為K的數(shù)據(jù)集中，構(gòu)建包含t棵RS-Tree的RS-EIF 森林，每棵樹包含ψ個(gè)節(jié)點(diǎn)，取子空間大小為k，擴(kuò)展等級為k-1。其中，0 ＜k＜K。

在訓(xùn)練階段，需要進(jìn)行t次隨機(jī)抽樣。由于t是常數(shù)，因此其時(shí)間復(fù)雜度為O(1)。在構(gòu)建RS-Tree時(shí)，每棵樹只需要進(jìn)行一次隨機(jī)的k維選擇即可確定子空間，再在子空間中進(jìn)行ψ次隨機(jī)生成所需的兩個(gè)向量并計(jì)算不同節(jié)點(diǎn)隔離值的工作。因此，一棵完全的RS-Tree只需要常數(shù)時(shí)間O(ψ)即可完成構(gòu)建。對于包含t棵樹的RS-EIF 森林，其訓(xùn)練過程時(shí)間復(fù)雜度為O(ψt)。

在測試階段，一棵完全RS-Tree 中，最多只需要8 次向量乘法運(yùn)算與比較運(yùn)算，由于k維常量，可以近似地等于O(1)。則在t棵RS-Tree進(jìn)行遍歷，時(shí)間復(fù)雜度為O(t)。因此，訓(xùn)練階段的時(shí)間復(fù)雜度取決于樣本個(gè)數(shù)。對于n個(gè)樣本，時(shí)間復(fù)雜度則等同于O(tn)。由于t是一個(gè)需要指定的參數(shù)，該參數(shù)通常為常數(shù)，因此時(shí)間復(fù)雜度可以理解為O(n)。

2.2.2 空間開銷分析

由于RS-EIF 算法的目的是生成一個(gè)強(qiáng)分類器用于判斷輸入信息是否是異常的，因此，算法只需要存儲(chǔ)這個(gè)包含t棵RS-Tree 的數(shù)據(jù)結(jié)構(gòu)以及其包含的信息。因此空間復(fù)雜度為常數(shù)。

3 實(shí)驗(yàn)與結(jié)果分析

為了驗(yàn)證RS-EIF 算法的有效性，本文使用3 組實(shí)驗(yàn)來分別驗(yàn)證該算法的準(zhǔn)確性與時(shí)間提升。

實(shí)驗(yàn)中，使用的人工數(shù)據(jù)集共有7 個(gè)，這些人工數(shù)據(jù)集均使用Python 自帶的sklearn 包生成，每個(gè)數(shù)據(jù)所包含的數(shù)據(jù)點(diǎn)都是呈高斯分布均勻地分布在4 個(gè)聚類中心周圍。其中，DS_One、DS_Two、DS_Three 與DS_Four 均為二維數(shù)據(jù)，其樣本數(shù)量以2 000 的步長遞增；而DS_Five、DS_Six 與DS_Seven 則為包含4 000 個(gè)樣本的數(shù)據(jù)集，并且其維度以步長2 增長。在這些數(shù)據(jù)集中，異常數(shù)據(jù)由均勻分布在其他聚類中心周圍的10個(gè)數(shù)據(jù)代替，具體的信息如表1所示。

表1 實(shí)驗(yàn)使用的人工數(shù)據(jù)集Tab.1 Synthetic datasets used in experiments

其次，實(shí)驗(yàn)使用的真實(shí)數(shù)據(jù)集來自離群值檢測數(shù)據(jù)庫（Outliter Detection DataSet，ODDS）［22］，本文選擇其中9個(gè)具有代表性的多維點(diǎn)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)。選取的數(shù)據(jù)集信息如表2所示。這些數(shù)據(jù)包括低維到高維、低樣本數(shù)量到高樣本數(shù)量的數(shù)據(jù)，可以更好地展現(xiàn)本文算法的性能。

表2 實(shí)驗(yàn)使用的ODDS數(shù)據(jù)集Tab.2 ODDS datasets used in experiments

最后，所有實(shí)驗(yàn)使用Python3.8.3 編程實(shí)現(xiàn)，運(yùn)行在Windows 10 操作系統(tǒng)，12 GB 內(nèi)存，Intel Core i5-4200H CPU@2.90 GHz的計(jì)算機(jī)平臺(tái)上。由于實(shí)驗(yàn)中所涉及的5種算法中有3 種均為基于樹型結(jié)構(gòu)的集成學(xué)習(xí)算法，因此為了更加清晰直接地展現(xiàn)對比結(jié)果，將3 種算法的部分參數(shù)默認(rèn)設(shè)置為訓(xùn)練100棵包含256個(gè)節(jié)點(diǎn)的樹。

3.1 局部異常檢測

本節(jié)選取DS_One 為實(shí)驗(yàn)數(shù)據(jù)集。在該數(shù)據(jù)集中，存在2個(gè)聚類中心的距離偏近，因此視覺上產(chǎn)生了類似于存在3 個(gè)聚類中心的效果。而異常點(diǎn)則明顯遠(yuǎn)離數(shù)據(jù)集中的大量數(shù)據(jù)。

根據(jù)前文分析，如果在該數(shù)據(jù)集上使用傳統(tǒng)的iForest 算法，則必定會(huì)產(chǎn)生至少一個(gè)矩形的得分異常區(qū)域。因此，本節(jié)使用與前文類似的方式繪制EIF算法與RS-EIF算法的異常得分熱圖來觀察是否有效避免了矩形異常區(qū)域的產(chǎn)生。

在參數(shù)設(shè)置方面，由于DS_One 是一個(gè)二維數(shù)據(jù)集，為了避免RS-EIF算法在維度為1的子空間出現(xiàn)隔離條件失效的問題，本節(jié)將子空間的維度設(shè)置為2。除此之外，兩種算法的擴(kuò)展等級均設(shè)置為最高等級。實(shí)驗(yàn)結(jié)果如圖2所示。

在圖2（a）中清晰地展示出:EIF 算法的異常分?jǐn)?shù)熱圖中，并沒有存在呈矩形、由隔離條件重疊所導(dǎo)致的分?jǐn)?shù)異常區(qū)域。在圖2（b）中，同樣沒有發(fā)現(xiàn)類似的矩形區(qū)域。然而，圖2（b）的異常分?jǐn)?shù)輪廓的平滑程度并沒有達(dá)到圖2（a）的程度。分析后發(fā)現(xiàn)，導(dǎo)致該現(xiàn)象出現(xiàn)的原因在于:本節(jié)并沒有刻意地調(diào)整參數(shù)設(shè)置以達(dá)到最佳效果。

圖2 多元分布數(shù)據(jù)上不同算法得分熱圖Fig.2 Score heat maps of different algorithms on multivariate distribution data

綜上所述，不難發(fā)現(xiàn)，RS-EIF 算法具有與EIF 算法相似的局部異常檢測能力。

3.2 維度與樣本數(shù)量對算法運(yùn)行時(shí)間的影響

本節(jié)首先使用RS-EIF 算法與EIF 算法對DS_One、DS_Two、DS_Three 與DS_Four 這4 個(gè)數(shù)據(jù)集進(jìn)行預(yù)測。除了默認(rèn)參數(shù)外，同樣指定RS-EIF 算法在維度為2 的子空間進(jìn)行訓(xùn)練，兩種算法的擴(kuò)展等級均設(shè)置為最高等級，并且采取10次實(shí)驗(yàn)求平均值的方法，得到在不同人工數(shù)據(jù)集的運(yùn)行時(shí)間，實(shí)驗(yàn)結(jié)果如圖3所示。

圖3 展示了在不同樣本數(shù)據(jù)量的情況下，兩種算法在運(yùn)行時(shí)間方面的差異。在圖3（a）中，所繪制的兩條線分別代表兩種算法在不同數(shù)據(jù)集的運(yùn)行時(shí)間。不難看出，雖然兩條折線都是近似線性增加的，但RS-EIF 算法的運(yùn)算時(shí)間明顯少于EIF 算法。出現(xiàn)該現(xiàn)象的原因是:RS-EIF 算法在預(yù)測階段，每個(gè)節(jié)點(diǎn)的遍歷只需要計(jì)算1 次隨機(jī)斜率向量與數(shù)據(jù)點(diǎn)的點(diǎn)乘；而EIF 算法在預(yù)測階段的節(jié)點(diǎn)遍歷則需要分別計(jì)算隨機(jī)截距向量與數(shù)據(jù)點(diǎn)同隨機(jī)斜率向量的點(diǎn)乘。

除此之外，本節(jié)還選取了DS_Two、DS_Five、DS_Six 與DS_Seven 數(shù)據(jù)比較數(shù)據(jù)維度對兩種算法運(yùn)行時(shí)間的影響。由于上述4 個(gè)數(shù)據(jù)的維度是不同的，因此在兩種算法中，擴(kuò)展等級均設(shè)置為最高等級。而RS-EIF 算法的子空間維度則分別設(shè)置為:2、3、5、7。

通過圖3（b）發(fā)現(xiàn)，兩種算法在不同維度的數(shù)據(jù)集中，運(yùn)行時(shí)間均在一個(gè)固定范圍內(nèi)上下變化，但RS-EIF 算法的運(yùn)行時(shí)間同樣遠(yuǎn)少于EIF 算法。出現(xiàn)該現(xiàn)象的原因在于:所選取的數(shù)據(jù)集樣本數(shù)量并不大，沒有完全體現(xiàn)算法在不同維度數(shù)據(jù)集上的運(yùn)行時(shí)間差異。

圖3 數(shù)量與維度對運(yùn)行時(shí)間的影響Fig.3 Impact of quantity and dimension on running time

綜上所述，在相同維度的數(shù)據(jù)集中，雖然EIF 算法與RSEIF 算法時(shí)間開銷均表現(xiàn)為隨樣本數(shù)量的增加而線性增加；但在樣本數(shù)量相同的數(shù)據(jù)集中，EIF 算法的時(shí)間開銷是遠(yuǎn)多于RS-EIF算法。

3.3 與其他異常檢測算法的比較

本節(jié)將兩個(gè)樣本數(shù)量較多的數(shù)據(jù)集ForestCover與Http按照1∶9 劃分為測試集與訓(xùn)練集；將兩個(gè)樣本數(shù)量過少的數(shù)據(jù)集Glass 與Lympho 采用10 折交叉驗(yàn)證求均值的方法進(jìn)行實(shí)驗(yàn)；其余數(shù)據(jù)則使用5折交叉驗(yàn)證取平均值的方法獲得結(jié)果。

算法選擇方面，將RS-EIF 算法與同為集成模型的iForest算法、EIF 算法與輕型在線異常檢測（Lightweight On-line Detection of Anomalies，LODA）算法［23］以及基于統(tǒng)計(jì)的COPOD 算法［5］進(jìn)行對比，這些模型均使用PyOD 庫［24］實(shí)現(xiàn)。參數(shù)設(shè)置方面，iForest 算法使用默認(rèn)參數(shù)；而EIF 算法與RSEIF 算法的擴(kuò)展等級則均設(shè)置為最高；除此之外，為了方便計(jì)算，RS-EIF 算法的子空間維度設(shè)置為對應(yīng)數(shù)據(jù)空間維度的一半；LODA 算法的直方圖數(shù)量與隨機(jī)消減數(shù)則分別設(shè)置為文獻(xiàn)［23］中提出的10與100。

表3 給出了5 種算法在時(shí)間開銷與精確度方面的差異。其中:時(shí)間是指從開始訓(xùn)練到結(jié)束預(yù)測的時(shí)間；精確度（ACcuracy score，AC）則表示使用sklearn 包中的相應(yīng)函數(shù)計(jì)算5種算法預(yù)測結(jié)果的準(zhǔn)確度。通過表3可以發(fā)現(xiàn)，在樣本數(shù)量大于1 000 的數(shù)據(jù)集中，RS-EIF 算法、EIF 算法的精確度與iForest 算法、LODA 算法、COPOD 算法相比分別高出了2～12 個(gè)百分點(diǎn)與3～15 個(gè)百分點(diǎn)，但在時(shí)間開銷上，兩種算法則均劣于其他3 種算法。除此之外，RS-EIF 算法與EIF 算法在這些數(shù)據(jù)集上的精確度均相差不超過5 個(gè)百分點(diǎn)，而RS-EIF 算法的運(yùn)行時(shí)間卻遠(yuǎn)少于EIF 算法。RS-EIF 算法與EIF 算法的精確度遠(yuǎn)高于其他算法的原因是兩種算法均使用隨機(jī)超平面進(jìn)行隔離，可以有效識別出絕大部分異常點(diǎn)。因此，RS-EIF 算法相較于EIF 算法的改進(jìn)是行之有效的。而在兩個(gè)樣本數(shù)量過少的數(shù)據(jù)中，RS-EIF 算法的精確度雖然低于EIF 算法，但與其他3 種算法對比可以發(fā)現(xiàn)，其精確度還是明顯高于iForest 算法的，導(dǎo)致出現(xiàn)該現(xiàn)象的原因則可能是樣本數(shù)量過少。

綜合分析實(shí)驗(yàn)結(jié)果可知，RS-EIF 算法的時(shí)間開銷在各類型的數(shù)據(jù)集上均少于EIF 算法，具體約下降60%。在實(shí)驗(yàn)精確度上，RS-EIF算法與EIF算法相差不大，但在中大型數(shù)據(jù)集中卻明顯優(yōu)于iForest 算法、LODA 算法與COPOD 算法。除此之外，由于RS-EIF 算法需要在子空間中進(jìn)行訓(xùn)練與預(yù)測，而該過程包含大量的隨機(jī)運(yùn)算，因此，即使集成學(xué)習(xí)的方式提高了RS-EIF 算法的精確度，但在少數(shù)數(shù)據(jù)集上，RS-EIF 算法與EIF算法相比還是略有不足。

4 結(jié)語

本文從iForest算法的隔離條件軸平行導(dǎo)致算法對局部異常不敏感入手，借鑒EIF 算法解決該問題的思想，提出在隨機(jī)子空間中使用隨機(jī)超平面進(jìn)行隔離的RS-EIF 算法。該算法從減少向量計(jì)算維度的角度入手，充分利用隨機(jī)的不確定性與集成學(xué)習(xí)提高弱分類器分類效果的特質(zhì)，使得性能更加穩(wěn)定。

實(shí)驗(yàn)結(jié)果驗(yàn)證了RS-EIF 算法存在精度高、時(shí)間開銷呈線性增加并且明顯少于EIF 算法的特點(diǎn)。在真實(shí)的ODDS 數(shù)據(jù)集上，將RS-EIF 算法與其他4 種算法分別對比了精確度與時(shí)間開銷的差異，得出結(jié)論為:在樣本數(shù)量更大的數(shù)據(jù)集中，RSEIF算法的精確度與EIF算法相近，但相較iForest算法、LODA算法與COPOD算法來說，RS-EIF算法的精確度平均提升約為5個(gè)百分點(diǎn)；在時(shí)間開銷方面，該算法較EIF 算法減少約60%，但與其他3 種算法相比，時(shí)間開銷并不占優(yōu)勢。因此，本文所提RS-EIF 算法是一種適用于中大型多元數(shù)據(jù)集的高精度異常檢測算法。

由于本文算法在計(jì)算隨機(jī)超平面時(shí)離不開向量的點(diǎn)乘計(jì)算，因此時(shí)間開銷還是偏大。下一步，可以結(jié)合集成學(xué)習(xí)中，各個(gè)弱分類器之間可以不存在耦合關(guān)系的特點(diǎn)，將該算法部署在分布式系統(tǒng)上，通過合理的任務(wù)規(guī)劃，提高本文算法的運(yùn)行速度與精確度。