楊曉暉，張圣昌

（河北大學(xué)網(wǎng)絡(luò)空間安全與計算機(jī)學(xué)院，河北 保定 071002）

1 引言

異常檢測的作用是分類出與多數(shù)數(shù)據(jù)有不同行為模式的稀有數(shù)據(jù)。Grubbs[1]對異常點有如下定義：異常點是一種模式，在此模式下的數(shù)據(jù)點偏離了大部分?jǐn)?shù)據(jù)點的模式特征，甚至不是同一種機(jī)制產(chǎn)生的。本文將異常點定義為分布稀疏且距離密度較高的數(shù)據(jù)簇較遠(yuǎn)的點。異常檢測在諸多領(lǐng)域中有廣泛應(yīng)用，例如，在電子現(xiàn)金支付過程中，異常點代表著套現(xiàn)欺詐行為；在科學(xué)計算領(lǐng)域，異常數(shù)據(jù)和正常數(shù)據(jù)具有相等的利用價值[2]，如天文圖像檢測中的異常點可能意味著新星的出現(xiàn)；在網(wǎng)絡(luò)安全領(lǐng)域，異常點可能是惡意用戶的非法入侵。

近年來，基于密度評估的異常檢測方案深受關(guān)注[3]?；诿芏仍u估的異常檢測方案將異常點定義如下：異常點是低密度區(qū)域的數(shù)據(jù)對象，密度的核心概念是近鄰距離。對密度概念的改進(jìn)衍生出不同的算法，例如局部異常因子算法（LOF,local outlier factor）[4]、密度偏移抽樣算法[5]等。LOF 通過k近鄰距離計算局部可達(dá)密度，得到每個點的局部離群因子，根據(jù)閾值判斷點是否異常。LOF 的優(yōu)勢是既可以計算局部異常點，也可以計算全局異常點，在小數(shù)據(jù)集中效果極佳。利用聚類進(jìn)行異常檢測也是基于密度概念，此類算法利用數(shù)據(jù)點的分布規(guī)律對數(shù)據(jù)集進(jìn)行分簇，按每個數(shù)據(jù)點到簇中心的距離排序，根據(jù)超參閾值比較，超過閾值的數(shù)據(jù)點稱為異常點。例如經(jīng)典k-means 聚類算法檢測網(wǎng)絡(luò)流量異常[6]，利用遺傳算法對k-means 聚類改進(jìn)解決了局部最優(yōu)問題[7]；Tang 等[8-9]提出了基于特征選擇的模糊聚類異常檢測模型，利用層次聚類和遺傳算法改進(jìn)了聚類模型，進(jìn)一步降低了異常檢測的誤報率。

隨著大數(shù)據(jù)時代的到來，數(shù)據(jù)的量和維度發(fā)生了爆炸式增長。高維數(shù)據(jù)存在2 個問題：1)距離計算上的“維數(shù)災(zāi)難”[10]，數(shù)據(jù)相似度的計算離不開距離計算，比如歐氏距離，隨著數(shù)據(jù)維度的增加，點與點間距離的區(qū)分度變小，數(shù)據(jù)分布稀疏，異常點不再敏感；2)時間復(fù)雜度過高，高維數(shù)據(jù)間的距離計算所需時間開銷過大，對實時檢測應(yīng)用來說無法滿足需求，例如網(wǎng)絡(luò)入侵檢測和信用卡欺詐檢測都對低時間開銷有較高要求。基于密度評估的異常檢測方案時間復(fù)雜度均在O(n2)[11]，因此設(shè)計出對高維度、大數(shù)據(jù)集進(jìn)行異常檢測的高效方法具有重要意義。

質(zhì)量評估思想在數(shù)據(jù)分類、回歸異常檢測等領(lǐng)域有顯著效果，該思想重新定義數(shù)據(jù)點靠近數(shù)據(jù)簇中心或靠近數(shù)據(jù)簇邊緣的度量，并稱該度量為質(zhì)量。相比于密度評估方法，基于質(zhì)量評估的方法有以下2 個優(yōu)勢[12]：1)數(shù)據(jù)質(zhì)量的計算量小，數(shù)據(jù)質(zhì)量計算只統(tǒng)計一個區(qū)域內(nèi)的數(shù)據(jù)量，不需要計算距離；2)數(shù)據(jù)質(zhì)量的大小反映了數(shù)據(jù)點是靠近還是遠(yuǎn)離數(shù)據(jù)簇中心。

基于質(zhì)量評估的異常檢測方案利用隔離機(jī)制來計算數(shù)據(jù)質(zhì)量。根據(jù)隔離機(jī)制的不同，衍生出許多異常檢測算法，例如half-space tree[13]、SCiForest[14]、基于近鄰距離的隔離機(jī)制[15]等。

孤立森林（iForest，isolation forest）[16]屬于集成學(xué)習(xí)方法，是隨機(jī)森林算法的無監(jiān)督版本，廣泛應(yīng)用于異常檢測領(lǐng)域。iForest 對數(shù)據(jù)空間進(jìn)行隨機(jī)隔離，以此構(gòu)造決策樹樁（decision stump），也稱為孤立樹（iTree,isolation tree）。iForest 也符合質(zhì)量評估思想，質(zhì)量被定義為iTree 中葉節(jié)點的深度，深度越小，越有可能為異常點。

iForest 解決了高維數(shù)據(jù)集中異常檢測的2 個問題[17]：1)iForest 不需要計算距離，算法的時間開銷不隨數(shù)據(jù)維度的增加而增加，為線性時間復(fù)雜度；2)iForest 對大型數(shù)據(jù)集的檢測性能好，并且是集成學(xué)習(xí)算法，iTree 越多，iForest 越穩(wěn)定。

雖然iForest 適用于高維數(shù)據(jù)集的異常檢測，但隨著數(shù)據(jù)分布復(fù)雜性的增加，檢測效率也會降低，而且在極高維數(shù)據(jù)的異常檢測中，算法的波動性較高。因此，本文提出基于多特征決策的隨機(jī)超平面隔離機(jī)制，以及基于滑動窗口的多粒度掃描機(jī)制，進(jìn)而構(gòu)造層次化集成學(xué)習(xí)模型。

2 iForest 方案

2.1 質(zhì)量評估思想

定義1隔離超平面。假設(shè)數(shù)據(jù)集D在維數(shù)i上有序，當(dāng) 且 僅 當(dāng)且時，為數(shù)據(jù)點在維度i上的隔離超平面。

定義2基本質(zhì)量函數(shù)。數(shù)據(jù)集D中每個點都有

定義3數(shù)據(jù)點質(zhì)量函數(shù)。計算式如式(2)所示。

2.2 iForest 的構(gòu)建

定義4 孤立樹。若Node 是孤立樹的節(jié)點，則是具有(NodeL,NodeR)子節(jié)點的內(nèi)部節(jié)點，或是無子節(jié)點的終端節(jié)點。NodeL與 NodeR的定義為在特征集合中選擇i，該特征上值區(qū)間內(nèi)隨機(jī)選擇數(shù)據(jù)j，小于j的數(shù)據(jù)劃分為左子樹NodeL，大于j的數(shù)據(jù)劃分為右子樹 NodeR。

iForest 由T個iTree 構(gòu)成，如式(3)所示。

2.3 iForest 的問題

軸平行（axis-parallel）是指在單一特征的決策過程中，決策邊界與坐標(biāo)軸平行的現(xiàn)象。軸平行是決策樹的一種特性，由于iForest 的決策模式類似于決策樹，因此也受軸平行特性的影響。

在密集的數(shù)據(jù)集中，受軸平行特性的影響，iForest會產(chǎn)生重疊和覆蓋效應(yīng)，導(dǎo)致決策精度降低，同時會增加iTree 的高度和訓(xùn)練過程的時間開銷，無法高效生成iTree，因此iForest 更適用于具有分布稀疏特性的數(shù)據(jù)集。文獻(xiàn)[16]提出類似于隨機(jī)森林中子采樣的方法解決了這個問題。設(shè)定ψ為隨機(jī)子采樣的樣本數(shù)量，iTree 由隨機(jī)子采樣的樣本集生成。

圖1(a)構(gòu)造了3 個服從高斯分布的數(shù)據(jù)集。左上數(shù)據(jù)簇的數(shù)量為300，左下為500，右側(cè)為1 000。圖1(b)中的數(shù)據(jù)量為1 000，數(shù)據(jù)的分布模式符合余弦函數(shù)趨勢。黑白梯度線為異常分?jǐn)?shù)的等高線，黑色表示1，白色表示0，異常分?jǐn)?shù)越大，表示越有可能為異常點。如圖1(a)所示，異常分?jǐn)?shù)梯度線在數(shù)據(jù)簇的平行軸線上偏差較大；圖1(b)失去了余弦函數(shù)趨勢，無法正確檢測異常點。

圖1 iForest 對不同數(shù)據(jù)集的異常分?jǐn)?shù)

3 基于多粒度級聯(lián)孤立森林算法

為解決iForest 的不足，本文提出基于多維度隨機(jī)超平面的孤立森林（MRHiForest,multi-dimensional random hyperplane iForest）隔離機(jī)制，在數(shù)據(jù)集隔離的過程中，使用多元線性組合構(gòu)成多樣化的隨機(jī)超平面。同時，利用多粒度掃描器（MGS，multi-grained scanner）進(jìn)行高維數(shù)據(jù)的特征子采樣，類似隨機(jī)森林，但樣本的選取采用滑動窗口的方式，特征樣本存在連續(xù)性。每個特征樣本構(gòu)造新的數(shù)據(jù)集訓(xùn)練孤立森林，以此構(gòu)造基于多粒度級聯(lián)孤立森林算法的異常檢測模型。

3.1 隨機(jī)超平面隔離

定義5隨機(jī)超平面。隨機(jī)超平面為iForest 的隔離機(jī)制產(chǎn)生的超平面，Su是所有隨機(jī)超平面的集合。p(x,y)表示為點x及點y被隨機(jī)超平面K隔離的概率，如式(4)所示。

iForest 中的隔離機(jī)制為式(4)的特例。iForest隨機(jī)選擇一個特征η，令

聯(lián)合式(4)和式(5)得到iForest 的隔離超平面為

iForest 僅就一個特征η進(jìn)行隔離，丟失了大部分特征信息，因此隨著數(shù)據(jù)維數(shù)的增加，iForest 的性能不穩(wěn)定。相比之下，隨機(jī)超平面的隔離機(jī)制包含所有特征信息。

在iForest 中，數(shù)據(jù)的隔離是隨機(jī)的，針對隨機(jī)超平面的隨機(jī)選擇容易出現(xiàn)偏離數(shù)據(jù)集現(xiàn)象，造成無效開銷。本文利用法向量隨機(jī)生成斜率向量。首先隨機(jī)選擇2 個點，然后求2 個點的法向量作為斜率向量，從而保證隨機(jī)超平面存在于數(shù)據(jù)集中。

圖2(a)是二維數(shù)據(jù)空間中一個iTree 的生成過程實例。選取平行于軸的超平面來隔離數(shù)據(jù)，數(shù)據(jù)質(zhì)量高的數(shù)據(jù)點被隔離多次才會被劃分出去（如圖2(a)中的點n），而質(zhì)量低的數(shù)據(jù)點經(jīng)過少數(shù)的幾次隔離就會被劃分出去（如圖2(a)中的點a）。圖2(b)展示了MRHiForest 中隨機(jī)超平面的生成過程，圖中兩點是隨機(jī)選取的，兩點的法向量表示隨機(jī)超平面的方向，灰色區(qū)域為截距b的區(qū)間選取范圍。從圖2 中可以明顯看出，iForest 隔離超平面是平行于坐標(biāo)軸的，MRHiForest 隔離超平面的方向是隨機(jī)的。

圖2 隔離超平面的構(gòu)造過程

生成MRHiTree 的偽代碼如算法1 所示。

算法1生成MRHiTree

參數(shù)數(shù)據(jù)集X，當(dāng)前樹高度h，閾值yz

3.2 多粒度掃描采樣

定義 6多粒度掃描。設(shè)數(shù)據(jù)的特征集合P={d1,d2,d3,…,du}，特征的最大值為u。多粒度掃描定義窗口大小q，當(dāng)且僅當(dāng)u＞q，根據(jù)窗口q重新構(gòu)成新的特征集合，定義滑動窗口步長step，生成多個子特征集合，新的特征集合構(gòu)成新的數(shù)據(jù)集。如式(7)所示。

其中，L為特征子采樣的最大值，如式(8)所示。

多粒度掃描的滑動窗口過程如圖3 所示。影響特征空間大小的因素為step 和q，隨著step 的減小，特征空間數(shù)量越多，但是時間開銷就越高。相反，隨著step 增大，生成新的特征空間數(shù)量就越少，當(dāng)step＞q時，會產(chǎn)生特征丟失現(xiàn)象，因此step 的理論峰值為q。MGS 偽代碼如算法2 所示。

圖3 多粒度掃描過程

算法2 MGS

參數(shù)數(shù)據(jù)集X，維度集Dims，維度數(shù)目u，步長step

3.3 層次化集成學(xué)習(xí)異常檢測模型

本文首先利用多粒度掃描機(jī)制MGS 作為特征選擇過程，然后利用多維度隨機(jī)超平面隔離機(jī)制MRH 對基于孤立森林iForest 的異常檢測模型進(jìn)行優(yōu)化，從而構(gòu)建基于多粒度掃描與多維度隨機(jī)超平面的孤立森林算法（MGS-MRHiForest）的層次化集成學(xué)習(xí)異常檢測模型。模型結(jié)構(gòu)如圖4 所示，偽代碼如算法3 所示。

圖4 基于MGS-MRHiForest 的層次化集成學(xué)習(xí)異常檢測模型

算法3MGS_MRHiForest

參數(shù)數(shù)據(jù)集X，MRHiTree 的數(shù)量T，子樣本數(shù)ψ

MRHiForest 經(jīng)過多粒度掃描后形成森林集合RFs={RF1,RF2,…,RFL}，表示葉子節(jié)點的深度，經(jīng)過集成學(xué)習(xí)計算的過程如式(9)所示。

其中，ψ表示MRHiForest 的隨機(jī)子采樣大小，歐拉常數(shù)γ=0.577 215 664 901532 8，c(ψ)表示孤立樹中查找點失敗的平均路徑。

iForest 的時間復(fù)雜度為O(Tψlbψ)[18]，多粒度級聯(lián)會產(chǎn)生L個森林，所以MGS_MRHiForest 的時間復(fù)雜度為O(LTψlbψ)。

4 實驗結(jié)果與分析

實驗環(huán)境為Intel Core i7-6700 3.4 GHz；16 GB內(nèi)存：Windows 10 操作系統(tǒng)。本文所有算法都基于Python 語言的Sklearn 庫實現(xiàn)，MRHiForest 在原始iForest 基礎(chǔ)上增加了多粒度掃描算法和隨機(jī)森林算法。本文使用Area Under ROC Curve(AUC)作為算法性能評測標(biāo)準(zhǔn)，AUC 越大，代表學(xué)習(xí)模型的泛化能力越強(qiáng)。所有實驗均經(jīng)過5 次運(yùn)算得到測量結(jié)果，并以其算術(shù)平均值作為最終的實驗結(jié)果。

iForest 的默認(rèn)參數(shù)設(shè)定為 iTree 的數(shù)量T=100，子樣本數(shù)量ψ=256。這是因為iForest在此參數(shù)下有最好的檢測效果。

MGS 的默認(rèn)參數(shù)設(shè)定為維數(shù)閾值q=100，粒度掃描步長step=1 。q體現(xiàn)多粒度掃描的特征選擇過程，step 則關(guān)系著樣本集的多樣性，步長越小，樣本集的多樣性就越高，iForest 的泛化能力就越強(qiáng)，但代價是時間開銷會增加。

4.1 復(fù)雜數(shù)據(jù)模式的局部異常點檢測

為了驗證在復(fù)雜數(shù)據(jù)分布的數(shù)據(jù)集中進(jìn)行異常檢測的效果，使用阿基米德螺旋方程構(gòu)造了包含1 000 個點的螺旋數(shù)據(jù)分布數(shù)據(jù)集，分別使用iForest和MRHiForest 算法生成異常分?jǐn)?shù)圖，以展示算法對異常點的梯度分布。

實驗結(jié)果如圖5 所示。其中亮區(qū)表示異常分?jǐn)?shù)較低，暗區(qū)表示異常分?jǐn)?shù)較高，兩部分區(qū)域構(gòu)成了復(fù)雜數(shù)據(jù)模式下正常數(shù)據(jù)和異常數(shù)據(jù)的數(shù)據(jù)分布規(guī)律。由圖5(a)可知，iForest 生成的異常分?jǐn)?shù)梯度偏差較大，圖5(b)中MRHiForest 的異常分?jǐn)?shù)梯度更符合螺旋數(shù)據(jù)的分布規(guī)律。上述實驗結(jié)果與算法的隔離機(jī)制有關(guān)，iForest 軸平行的特點導(dǎo)致偏差，MRHiForest 對隔離機(jī)制的改進(jìn)使之對復(fù)雜數(shù)據(jù)模式具有更好的隔離能力。

圖5 iForest 和MRHiForest 在螺旋數(shù)據(jù)集中的異常分?jǐn)?shù)圖

為了測試算法對異常數(shù)據(jù)的穩(wěn)健性，在上述螺旋數(shù)據(jù)集中逐步添加異常點，分別計算2 種算法的AUC。螺旋數(shù)據(jù)集中添加100 個異常點如圖6 所示。

圖6 螺旋數(shù)據(jù)集中插入100 個均勻分布異常點

實驗結(jié)果如圖7 所示，2 種算法的AUC 曲線表明，MRHiForest 整體性能高于iForest，說明MRHiForest 的隨機(jī)超平面隔離機(jī)制更好地隔離了復(fù)雜數(shù)據(jù)模型的局部異常點。當(dāng)異常點數(shù)為115 時，iForest 的AUC 減少到0.9 以下；當(dāng)異常點為200 時，MRHiForest 的AUC 下降到0.9 以下，此時iForest 的AUC 為0.78。由此可知，MRHiForest 的穩(wěn)健性強(qiáng)于iForest，AUC 的持續(xù)下降是因為異常點的數(shù)量占比達(dá)到數(shù)據(jù)集的16%以上，iForest 的適用前提正是數(shù)據(jù)集中異常點分布的稀疏特性。

圖7 iForest 和MRHiForest 在不同異常點樣本數(shù)量上的AUC

上述實驗中，MRHiForest 將iTree 數(shù)量T直接設(shè)定為iForest 的最佳參數(shù)值100。為進(jìn)一步探討MRHiForest 中T的最佳設(shè)定，在異常樣本集為100 的螺旋數(shù)據(jù)集中，令T分別為20、50、100、150、200、250、300、350，逐一計算MRHiForest的AUC，以5 次實驗結(jié)果的算術(shù)平均值作為最終結(jié)果，并以方差作為算法的穩(wěn)定性指標(biāo)。實驗結(jié)果分別如圖8 和圖9 所示。

圖8 MRHiForest 在不同數(shù)量孤立樹下的AUC

圖9 MRHiForest 在不同數(shù)量孤立樹下AUC 的方差

隨機(jī)性是導(dǎo)致iForest 性能不穩(wěn)定的主要原因[19]。而圖8 和圖9 表明，隨著iTree 數(shù)量T的增加，MRHiForest 的性能和穩(wěn)定性也在增強(qiáng)，當(dāng)T=100 時，AUC 的增長趨勢和方差逐漸平緩。這是因為MRHiForest 屬于集成學(xué)習(xí)方法，弱學(xué)習(xí)器iTree 的增加會降低錯誤率，增加穩(wěn)定性[20]?？紤]到iTree 帶來的時間開銷，將T的默認(rèn)值設(shè)定為100。

4.2 高維數(shù)據(jù)集異常點檢測

為了檢測多粒度掃描機(jī)制MGS 對高維數(shù)據(jù)集異常點檢測的性能，使用維數(shù)為617 的實驗數(shù)據(jù)集isolet，分別測試iForest 和MRHiForest 的平均異常分?jǐn)?shù)來對比算法對異常點的分離程度。平均異常分?jǐn)?shù)AveScore 定義為數(shù)據(jù)集中所有異常點的異常分?jǐn)?shù)的算術(shù)平均值，如式(12)所示。

其中，na為異常數(shù)據(jù)點總數(shù)，S(x a,ψ)為異常點xa在iForest 中的異常分?jǐn)?shù)。

實驗分為iForest 組和MRHiForest 組，分別使用不帶MGS 的iForest 和MRHiForest 與帶MGS的MGS-iForest 和MGS-MRHiForest 進(jìn)行評測并計算其AveScore。由于MGS 會產(chǎn)生多個子數(shù)據(jù)集，每個子數(shù)據(jù)集再分別使用 iForest 或者M(jìn)RHiForest 進(jìn)行層次化集成學(xué)習(xí)，因此，對未啟用MGS 的iForest 或者M(jìn)RHiForest 也構(gòu)造層次化集成學(xué)習(xí)模型，僅對完整的數(shù)據(jù)集進(jìn)行L次重復(fù)訓(xùn)練，從而生成L個iForest 或者M(jìn)RHiForest。對各組分別進(jìn)行500 次實驗，結(jié)果分別如圖10和圖11 所示。

圖10 iForest 組在高維數(shù)據(jù)集中的平均異常分?jǐn)?shù)

圖10 的測試結(jié)果顯示，iForest 的AveScore 在0.55 附近波動，MGS-iForest 的AveScore 在0.65 附近波動，說明MGS-iForest 對異常點的檢測和分離能力高于iForest。

圖11 MRHiForest 組在高維數(shù)據(jù)集中的平均異常分?jǐn)?shù)

圖11的測試結(jié)果顯示，MRHiForest的AveScore在0.76 附近波動，MGS-MRHiForest 的AveScore在0.85 附近波動，說明MGS-MRHiForest 對異常點的檢測和分離能力高于MRHiForest。

結(jié)合兩組實驗結(jié)果，使用MGS的算法AveScore普遍高于不使用MGS 的算法，說明多粒度掃描機(jī)制提高了算法對高維數(shù)據(jù)集異常點的檢測性能。

進(jìn)一步的實驗結(jié)果如表1 所示，在不啟用MGS的iForest 和MRHiForest 的500 次實驗中，平均異常分?jǐn)?shù)最大值與最小值之間的極差分別達(dá)到0.19和0.11；而在啟用MGS 的對照實驗中，平均異常分?jǐn)?shù)最大值與最小值之間的極差降為0.05。這說明多粒度掃描機(jī)制提高了異常檢測算法的穩(wěn)定性。

表1 4 種算法的平均異常分?jǐn)?shù)

4.3 真實數(shù)據(jù)集

本節(jié)對表2 所示的4 個真實數(shù)據(jù)集分別進(jìn)行異常檢測算法的性能評估。

表2 真實數(shù)據(jù)集詳細(xì)情況

表2 中，isolet 是簡單的音頻字母識別數(shù)據(jù)集，包括617 個特征。P53Mutant 是P53 基因編碼中與癌癥相關(guān)的數(shù)據(jù)集，包括5 408 個特征。http 是網(wǎng)絡(luò)入侵檢測數(shù)據(jù)集，來自KDD CUP99，提取其中3 個特征。mnist 為手寫數(shù)字0～9 數(shù)據(jù)集，提取其中2、3、5 的數(shù)據(jù)，并利用文獻(xiàn)[15]的算法進(jìn)行處理，特征維度是96。對于低維度數(shù)據(jù)集http 和mnist，不需要進(jìn)行多粒度掃描；對于高維度數(shù)據(jù)集isolet和P53Mutant，則要開啟多粒度掃描機(jī)制。

為評估基于質(zhì)量評估算法和基于密度評估算法的優(yōu)劣，將LOF 算法作為實驗的對比算法之一。在參數(shù)選擇上，LOF 的參數(shù)區(qū)間設(shè)置為10～1 000。iForest的隨機(jī)子采樣數(shù)量設(shè)置為2n，n取值1～10，取AUC最優(yōu)組為實驗結(jié)果。實驗結(jié)果如表3～表5 所示。

表3 3 種算法的AUC

表4 3 種算法的時間開銷

表5 3 種算法的最優(yōu)參數(shù)設(shè)定

由表3 可知，4 個數(shù)據(jù)集中，MRHiForest 的AUC 均優(yōu)于iForest 和LOF。其中iForest 僅在低維度的http 數(shù)據(jù)集中表現(xiàn)出和MRHiForest 和LOF 相同的檢測性能。在http 數(shù)據(jù)集中，MRHiForest 的時間開銷比iForest 少，這是因為：1)MRHiForest 的隨機(jī)子采樣數(shù)目小于iForest，這使iTree 的構(gòu)建速度更快；2)MRHiForest 的隔離機(jī)制提高了算法對異常點的敏感性，進(jìn)而提高了異常檢測效率。

由表4 可知，除了isolet 數(shù)據(jù)集外，其他數(shù)據(jù)集中LOF 的時間開銷最大，這是因為：1)隨著數(shù)據(jù)量的增加，LOF 的最優(yōu)參數(shù)K隨之增大，增加了處理開銷；2)隨著數(shù)據(jù)集維度的增加，距離計算的時間復(fù)雜度隨之提高。isolet 數(shù)據(jù)集中LOF 的時間開銷小是因為其數(shù)據(jù)量小，因此LOF 不適用于高維度、大數(shù)據(jù)量下的異常檢測。在高維數(shù)據(jù)集中iForest 的時間開銷是最少的，這是因為iForest 的單維度隔離機(jī)制對數(shù)據(jù)集的維數(shù)沒有依賴性，無論維度多高的數(shù)據(jù)集，iForest 都能以線性的時間開銷進(jìn)行異常檢測[21]。

由表3～表5 可知，數(shù)據(jù)集維度和數(shù)據(jù)集大小與算法的時間開銷存在相關(guān)性，因此設(shè)計了2 個實驗進(jìn)一步探索其相關(guān)性。

第一個實驗用來測試數(shù)據(jù)集大小與算法時間開銷的關(guān)系。將http 作為實驗數(shù)據(jù)集，選擇1×103～500×103個數(shù)據(jù)分別測試算法的執(zhí)行時間。

圖12 表明，隨著數(shù)據(jù)集大小的增加，iForest和 MRHiForest 的執(zhí)行時間均單調(diào)增加，但MRHiForest 的時間開銷更小。這是因為MRHiForest的平均查找路徑更短，而iForest 由于軸平行特性，iTree 相對較高，平均查找路徑較長。

圖12 iForest 和MRHiForest 不同數(shù)據(jù)集大小的執(zhí)行時間

第二個實驗用來測試數(shù)據(jù)集維度與算法時間開銷的關(guān)系。將P53Mutant 作為實驗數(shù)據(jù)集，選擇5到1 000 個維度分別測試算法的執(zhí)行時間。

圖13 表明，隨著數(shù)據(jù)集維度的增加，iForest 和MRHiForest 的執(zhí)行時間均單調(diào)遞增，但維度的增加對MRHiForest 的影響更大。這是因為MRHiForest中每一顆樹的節(jié)點均是多項式計算，維度的提升增加了計算開銷；iForest 僅隨機(jī)選擇一個維度進(jìn)行隔離，并不依賴于維度大小，因此時間開銷增加不明顯。

圖13 iForest 和MRHiForest 不同數(shù)據(jù)集維度的執(zhí)行時間

進(jìn)一步測試多粒度掃描機(jī)制對MRHiForest 和iForest 的性能提升，實驗結(jié)果如表6 所示。

表6 多粒度掃描機(jī)制下算法的AUC

由表6 可知，通過多粒度掃描的特征選擇，MRHiForest 和iForest 的AUC 均有所提升，驗證了多粒度掃描機(jī)制對算法的優(yōu)化效果。

5 結(jié)束語

本文提出基于多維度隨機(jī)超平面的iForest 異常檢測模型MRHiForest，同時引入多粒度掃描機(jī)制MGS，構(gòu)造了層次化集成學(xué)習(xí)異常檢測模型。MRHiForest 使用隨機(jī)超平面生成MRHiTree，使隔離機(jī)制更符合數(shù)據(jù)分布特征；MGS 增加了對高維數(shù)據(jù)集檢測的多樣性。與傳統(tǒng)iForest 的對比實驗結(jié)果表明，MRHiForest 對復(fù)雜的數(shù)據(jù)模型有更高的檢測效率，并且在低維數(shù)據(jù)集中檢測時間更少。對高維度數(shù)據(jù)集進(jìn)行的對比實驗結(jié)果表明，MGS-MRHiForest 能夠彌補(bǔ)iForest 對高維度數(shù)據(jù)異常點不敏感和檢測不穩(wěn)定的缺陷。

MGS 未考慮到關(guān)聯(lián)屬性特性，增加了算法的不確定性，隨著集成數(shù)量的增加，時間開銷有所增加，因此后續(xù)工作將考慮對關(guān)聯(lián)屬性特性的處理，進(jìn)一步改善異常檢測模型的性能。