王詩愉，肖利東，嚴心淳，應文豪

（1.常熟理工學院計算機科學與工程學院，江蘇 常熟 215500；2.常熟市醫(yī)學檢驗所，江蘇 常熟 215500）

0 引 言

在數(shù)據(jù)挖掘中，異常檢測是指對不符合預期模式的樣本進行識別，從數(shù)據(jù)集中識別出與大多數(shù)樣本差異較大的對象。異常點也被稱為離群值、噪聲和偏差等［1］，通常被認為是與其他數(shù)據(jù)點明顯不同或不符合整體預期正常模式的數(shù)據(jù)點［2］。異常檢測是數(shù)據(jù)挖掘領域中一個重要的方面，被廣泛應用于各個領域。例如，在醫(yī)學領域中，異常數(shù)據(jù)可能意味著禽流感等傳染類疾病的預警，而在天文領域中，異常數(shù)據(jù)則可能標志著新星的發(fā)現(xiàn)［3-6］。因此，異常數(shù)據(jù)可能具備和正常數(shù)據(jù)相等的科學價值。

近年來，國內(nèi)外學者對異常檢測領域進行了深入的探討，提出了許多實用性很高的異常檢測算法，為異常檢測的進一步研究奠定了基礎。Domingues等［7］對常見的異常檢測算法進行了分類總結(jié)，并根據(jù)異常檢測所使用技術(shù)的不同，分為基于連接函數(shù)的異常檢測方法［8］（Copula-Based Outlier Detection，COPOD）、基于距離的異常檢測方法［9］和基于密度評估的異常檢測方法等。其中基于密度評估的局部離群因子檢測方法［10］（Local Outlier Factor，LOF）解決了數(shù)據(jù)傾斜分布下的異常檢測問題。LOF 通過計算局部可達密度來得到每一個樣本點的局部離群因子，最后根據(jù)閾值判斷該樣本點是否異常。但是，基于密度評估的局部異常檢測方法時間復雜度均為O（n2）［11］，這種方法在大規(guī)模數(shù)據(jù)集上的計算成本很高。同時，因為數(shù)據(jù)相似度的計算離不開距離計算，所以可能會面臨距離計算上的“維數(shù)災難”問題［12］。隨著大數(shù)據(jù)時代的到來，數(shù)據(jù)集的數(shù)量和維度呈爆炸式增長，基于此，設計出在高維數(shù)據(jù)集上表現(xiàn)良好的異常檢測算法具有重要意義。

iForest［13］是一種基于相似度的算法，與集成學習算法隨機森林［14］有許多內(nèi)在的相似之處。iForest 的主要優(yōu)點在于直接孤立異常點達到異常檢測的目的，從而在一定程度上緩解異常檢測的掩蓋和淹沒效應［15］，而傳統(tǒng)的異常檢測算法通常需要針對正常數(shù)據(jù)構(gòu)建模型。iForest 利用數(shù)據(jù)集中異常點“少而不同”的特點采用子采樣的方法構(gòu)建iTree，將數(shù)據(jù)遍歷劃分到iTree 的節(jié)點中，數(shù)據(jù)在iTree 中所處的深度反映了該數(shù)據(jù)的“異?！背潭?，因此數(shù)據(jù)點在iTree 中的深度越淺，越有可能為異常點。

iForest不需要計算距離或密度度量，也不需要構(gòu)建完全的模型，且具備線性復雜度，因而能高效處理高維數(shù)據(jù)［16-17］。即使iForest 適用于高維數(shù)據(jù)集的異常檢測，但由于在構(gòu)建iTree 時，每次劃分數(shù)據(jù)空間都是隨機選取一個特征，構(gòu)建完iTree 后仍有大量維度信息沒有被使用，并且每個數(shù)據(jù)點對于隨機選取特征的異常程度也是不同的，最終導致算法的穩(wěn)定性降低［18］?；谏鲜鰡栴}，楊曉輝等［19］提出了基于多維度隨機超平面的iForest 異常檢測算法（Multi-dimensional Random Hyperplane iForest，MRH-iForest）。該算法結(jié)合滑動窗口的多粒度掃描機制，在每個維度子集上分別構(gòu)建iForest，多個iForest 構(gòu)造層次化集成學習異常檢測模型。該模型改善了iForest 在高維數(shù)據(jù)集中異常檢測精度下降和穩(wěn)定性較低的缺陷，但是隨著數(shù)據(jù)集維度的增加，MRH-iForest 的時間開銷增量要遠大于iForest。

同時，因為iForest 使用的切割平面是軸平行的，而軸平行的切割方式可能會導致隔離超平面的交叉，進而產(chǎn)生異常分數(shù)分布不準確的區(qū)域。Hariri 等［20］發(fā)現(xiàn)iForest 對于局部異常點不敏感，基于此提出了EIF，該算法可以隨機生成各種角度的切割平面，有效解決了iForest 對于局部異常點不敏感的問題。但由于EIF 在構(gòu)建擴展孤立樹（Extended Isolation Tree，EIT）時進行了多次向量點乘運算，所以在高維數(shù)據(jù)集上其計算成本往往遠大于iForest。同時因為EIF 將軸平行的孤立條件更替為使用隨機斜率［21］的超平面，導致算法模型損失了一部分泛化能力。

基于上述問題，本文利用模擬退火能夠有效避免算法陷入局部最優(yōu)解并最終以一定概率趨于全局最優(yōu)解的特性，提出一種基于模擬退火的擴展孤立森林算法SA-EIF。SA-EIF的核心思想是：

1）在集成構(gòu)建EIF的過程中計算iTree之間的差異值。2棵iTree之間的差異值越大，則說明2棵iTree的關聯(lián)性越小。

2）基于K 折交叉驗證的方法計算iTree 的精度值。因為檢測精度較低的iTree 在集成學習模型中具有相同的投票權(quán)重，因此低精度的iTree 通常會降低集成學習模型的異常檢測能力。

3）基于每棵iTree 的平均差異值和檢測精度構(gòu)建適應度函數(shù)，最終選擇部分高平均差異值和檢測能力較強的iTree 構(gòu)建集成學習模型［22］。這就使得SAEIF 可以在保持原有檢測精度的情況下，降低構(gòu)造過程中所占用的內(nèi)存，減少約20%～40%的時間開銷，增強了算法的泛化能力和穩(wěn)定性。

1 相關工作

1.1 iForest算法

iForest是一種集成學習算法，類似于隨機森林由多棵決策樹組成，iForest也由多棵iTree 組成。iForest的異常檢測分為2 個部分，第一個部分是訓練階段，第二個部分是評估階段。

1.1.1 訓練階段

在iForest 的訓練階段算法步驟中，假設數(shù)據(jù)集Χ={x1，x2，…，xn}，數(shù)據(jù)的維度為d，l為iTree 的數(shù)目，隨機子采樣的大小為ψ，將樹的深度限制設為l，一棵iTree的構(gòu)造步驟如下：

Step1 從數(shù)據(jù)集中隨機選取ψ個數(shù)據(jù)，組成樣本子空間，作為iTree的根節(jié)點。

Step2 從樣本子空間中隨機選取一個特征q作為起始節(jié)點，并在該特征的值區(qū)間內(nèi)隨機選取劃分點p。

Step3 基于劃分點生成的超平面，將當前樣本子空間劃分為2 個部分。把樣本子空間中小于劃分點p的數(shù)據(jù)劃分到當前節(jié)點的左子樹，大于等于p的數(shù)據(jù)劃分到當前節(jié)點的右子樹。

Step4 在iTree 的所有左右子樹中重復執(zhí)Step2、Step3 來構(gòu)建一棵完整的iTree，當滿足終止條件時，完成對當前iTree的構(gòu)建，終止條件如下：

1）節(jié)點中只包含一個數(shù)據(jù)。

2）節(jié)點上數(shù)據(jù)的所有特征值相同。

3）iTree 達到限定的最大深度l（從算法效率角度出發(fā)，限制了l=log2（ψ））。

重復上述過程，得到由L棵iTree 構(gòu)成的集成學習模型［23］iForest：

1.1.2 評估階段

在iForest的評估階段中，每個樣本數(shù)據(jù)在每棵孤立樹上都能得到一個路徑長度，在所有iTree上的路徑長度平均值則可以作為整個iForest 對于該樣本異常程度的度量指標，路徑長度越小，異常的可能性越大。

定義1 路徑長度。對于給定的測試數(shù)據(jù)x，路徑長度為x從iTree的根節(jié)點到葉節(jié)點所經(jīng)歷邊的數(shù)目。

定義2 異常分數(shù)。給定一個大小為ψ的樣本子空間和一個樣本數(shù)據(jù)x，則對于樣本數(shù)據(jù)x的異常分數(shù)s定義如公式（2）所示：

其中，E（h（x））表示樣本數(shù)據(jù)x在多棵iTree中路徑長度的均值；c（ψ）定義為在二叉搜索樹（Binary Search Tree，BST）中搜索失敗的平均路徑長度［24］，在此處主要起歸一化的作用，其定義如公式（3）所示：

其中，H（i）=ln（i）+0.5772156649（歐拉常數(shù)），H（i）為調(diào)和級數(shù)。

1.2 EIF算法

EIF 算法使用子空間［25］的思想進行異常檢測，并使用隨機斜率構(gòu)建孤立超平面來避免iForest 中軸平行現(xiàn)象導致的決策精度下降、對局部異常點不敏感等問題。

EIF 算法適合高維度的數(shù)據(jù)，與iForest 不同，EIF將軸平行的孤立條件改進為具有隨機斜率和截距的孤立超平面。每一個孤立超平面由隨機斜率→n和隨機截距→p確定。其中，隨機斜率→n∈［0，1），隨機截距→p則從每個分支點的值區(qū)間內(nèi)隨機選取。

在確定孤立超平面后，針對數(shù)據(jù)集Χ中一個給定的數(shù)據(jù)點→x，對其劃分的孤立條件如公式（4）所示：

（→x-→p）·→n≤0 （4）

如果滿足公式（4），則將數(shù)據(jù)點→x劃分到當前節(jié)點的左子樹，否則分配到當前節(jié)點的右子樹。

對于一個N維數(shù)據(jù)集，EIF 可以確定N個擴展級別。以三維空間為例，在三維空間中，當擴展等級為完全擴展（Ex 2）即擴展等級為N-1 時，孤立超平面與3 個坐標軸相交。如果將擴展等級減小1，則二維孤立超平面始終與3 個坐標軸之一平行，此時的擴展等級為1（Ex 1）。再次減小擴展等級，此時的擴展等級為0（Ex 0）。孤立超平面始終平行于2 個坐標軸。擴展等級為0時，EIF 算法等同于標準的iForest算法。每個擴展等級的孤立超平面如圖1所示。

圖1 三維數(shù)據(jù)集中每個擴展等級的孤立超平面

1.3 存在的問題

在決策樹對單一特征的決策過程中，會出現(xiàn)決策邊界與坐標軸平行的軸平行（axis-parallel）現(xiàn)象［26］。因為iForest的決策模式與決策樹具有高度一致性，所以也受軸平行的影響。iForest在高維數(shù)據(jù)集中，受軸平行現(xiàn)象的影響會發(fā)生異常檢測的掩蓋和重疊效應，導致iTree 對局部異常點不敏感，決策精度降低。因此iForest僅對全局異常點敏感，且更適用于分布稀疏且連續(xù)的數(shù)據(jù)集。

針對上述問題，Hariri 等［20］提出基于隨機斜率構(gòu)建超平面的EIF，在一定程度上改善了iForest 對于局部異常點不敏感的問題。

隨著EIF 算法擴展等級的提高，算法的偏差也會隨之減小。在各個維度上數(shù)據(jù)的分布差別較大的情況下，具有多個擴展等級的EIF 相比于iForest 精度和穩(wěn)定性更好。但EIF仍存在一些需要改進的問題：

1）在一些極端情況下，若存在三維數(shù)據(jù)集，但其中2 個維度的值區(qū)間比第3 個維度小得多，則該數(shù)據(jù)集本質(zhì)上可能是沿一條直線分布的，此時過高的擴展等級會帶來不必要的計算開銷。并且在EIF的訓練和評估過程中，每棵iTree節(jié)點上都需要進行1次向量減法和乘法計算。因此EIF 相比于iForest，雖然增加了對局部異常點的敏感性，但同時也增加了計算開銷。

2）在EIF 中每棵iTree 的檢測能力不同，但每棵iTree 的投票權(quán)重卻是相同的，因此可能會有一些異常檢測能力較差的iTree 會對最終的異常檢測結(jié)果產(chǎn)生誤導影響。

基于上述問題，本文提出SA-EIF異常檢測算法，該算法利用模擬退火算法優(yōu)化EIF 的執(zhí)行效率和泛化能力。

2 基于模擬退火的EIF算法

2.1 iTree的構(gòu)建

模擬退火算法起源于冶金學的固體退火原理，是基于概率的一種局部搜索算法。在1983 年被Kirkpatrick 等［27］應用于組合優(yōu)化領域。模擬退火算法最終求得的最優(yōu)解與算法的初解無關，因此具備一定的穩(wěn)定性。同時已在理論上證明模擬退火算法能夠有效避免目標算法陷入局部最優(yōu)解并最終以一定概率趨于全局最優(yōu)解。

在EIF 中，雖然構(gòu)造每棵iTree 的方式相同，但它們用于構(gòu)建所選取的訓練數(shù)據(jù)集卻大不相同，因此導致了每棵iTree 的檢測能力不同，基于Zhou 等［28］提出的選擇性集成思想：部分或許優(yōu)于整體，在集成模型中，從子集中選擇優(yōu)秀的個體構(gòu)成新的子集可能會比整體集合的效果更好。本文基于模擬退火對EIF 進行改進的思想是：針對已經(jīng)訓練好的iTree 集合T中，利用模擬退火算法從T中選擇檢測性能較好的iTree組成最優(yōu)子集T′來構(gòu)建EIF，從而減少構(gòu)建EIF 所需的iTree數(shù)量，提高執(zhí)行效率和分類精度。

給定訓練集Χtrain={x1，x2，…，xψ}，如果樹Ti對于Χn的預測結(jié)果與真實結(jié)果一致，則y（ψ，i）=1，預測錯誤則y（ψ，i）=0。L代表初次構(gòu)建時iTree 的數(shù)量，ψ代表Χtrain中的樣本個數(shù)。最后根據(jù)每棵iTree 對于訓練集的預測結(jié)果y（ψ，i）來構(gòu)建Ti與Tj之間的混淆矩陣（i∈［1，L］，j∈［1，L］），如表1所示。

表1 Ti與Tj的檢測結(jié)果混淆矩陣

iTree與iTree之間的差異值Qi，j如公式（5）所示：

根據(jù)Q-統(tǒng)計量法，Qi，j∈［-1，1］，Qi，j差異值越大，則說明樹Ti與Tj這2 棵iTree 的差異度越小。如果存在2棵iTree相互獨立，則這2棵iTree的差異值為0。

其次，對于iTree 檢測能力的區(qū)分，本文使用K 折交叉驗證的方法來計算每棵iTree 的檢測性能。首先將訓練數(shù)據(jù)劃分為數(shù)量相等的K份子集，每次隨機使用K-1份子集構(gòu)建iTree，然后使用剩余的1份子集對模型的檢測性能進行測試。將K份數(shù)據(jù)分別作為測試集進行測試，最終取K次檢測精度值的平均值作為該棵iTree 的精度值A。A越高則代表iTree 的檢測性能越好。使用K 折交叉驗證計算精度值可以更準確客觀地反應iTree的檢測性能。

在選取iTree 時，通常選擇精度較高、差異度較大的iTree。選擇差異度較大的iTree 可以更容易互補iTree 之間的不同信息，增加EIF 的泛化能力，而低精度的iTree 通常會對集成學習模型的檢測結(jié)果產(chǎn)生誤導影響，因此需要舍棄檢測能力較差的iTree。

2.2 適應度函數(shù)的構(gòu)建

本節(jié)綜合考慮精度值和差異值來計算每棵iTree的適應度值。適應度函數(shù)如公式（6）所示：

其中，μ和λ分別表示精確度和差異值對應的權(quán)重；Ai表示參與集成的Ti對于訓練集的精度值；Qi表示Ti對于其他iTree的平均差異值，其計算方法如公式（7）：

2.3 SA-EIF算法步驟

隨著EIF 擴展等級的提高，EIF 對局部異常點的敏感度也會隨之提升，但隨之而來的是大量的計算成本。EIF 本身是一種集成學習算法，本文結(jié)合模擬退火算法對EIF進行選擇性集成。

隨機選擇一棵iTree 作為初解，將溫度t模擬為控制參數(shù)，然后從初解的鄰域中根據(jù)溫度t隨機擾動選擇一個新解，其中，算法接受Metropolis 準則，計算新解與舊解的目標函數(shù)差值，允許目標函數(shù)在可接受的概率范圍內(nèi)接受新解。算法重復執(zhí)行“產(chǎn)生新解→計算目標函數(shù)差→判斷是否接受新解→接受或舍棄”的迭代過程，如果滿足終止條件則終止上述過程，并輸出當前選擇的iTree。否則，減小控制參數(shù)t的值，并重復上述過程。最終使用從T棵iTree 中選擇的k棵iTree來構(gòu)建EIF。具體算法步驟如下：

算法SA-EIF

輸入：數(shù)據(jù)集Χ；子采樣數(shù)ψ；初始iTree數(shù)量L。

Step1 設置iTree的初始參數(shù)。

Step2 構(gòu)建L棵iTree組成初始EIF。

Step3 使用數(shù)據(jù)集Χtrain對參與集成的L棵iTree進行訓練，基于Q-統(tǒng)計量法計算iTree 之間的平均差異值，再根據(jù)K折交叉驗證法計算每棵iTree的精度值。

Step4 結(jié)合模擬退火算法從L棵iTree 中選出k棵檢測性能較優(yōu)的iTree 構(gòu)建EIF。該步驟的算法流程如圖2所示。

圖2 SA-EIF核心算法流程圖

Step4.1 初始化參數(shù)。設初始溫度t=t0，結(jié)束溫度為t′，Metropolis 鏈的長度即任意溫度的迭代次數(shù)C，任取一棵iTree作為初解Ti。

Step4.2 產(chǎn)生新解?；诋斍皽囟萾的大小，隨機擾動產(chǎn)生一個新解Tj。

Step4.3 計算目標函數(shù)差：Δf=F（Tj）-F（Ti）。其中，F(xiàn)（Ti）、F（Tj）分別為樹Ti和Tj的適應度值。

Step4.4 判斷是否接受新解。根據(jù)Metropolis接受準則，若Δf＜0，則接受Tj作為新的當前解；否則以概率exp接受Tj作為新的當前解，其中，k是玻爾茲曼常數(shù)。

Step4.5 判斷在當前溫度t下，是否達到迭代次數(shù)C，若未達到迭代次數(shù)，則返回至Step4.2。

Step4.6 當滿足模擬退火算法規(guī)定的終止條件，則返回當前解為最優(yōu)解。終止條件如下：

1）連續(xù)若干個Metropolis中都沒有新解被采用。

2）t≤t′，即當前溫度t小于等于設定的結(jié)束溫度t′。

若不滿足終止條件，則根據(jù)溫度衰減函數(shù)緩慢降低當前溫度t，并返回至Step4.2，衰減函數(shù)如公式（8）所示：

Step4.7 最終從T棵iTree 中篩選出k（k≤L）棵檢測性能較優(yōu)的iTree構(gòu)建EIF。

Step5 對測試集Χtest使用構(gòu)建的EIF 進行檢測，根據(jù)實例x在每棵iTree 中的平均路徑長度E（h（x））計算其異常分數(shù)S（x，ψ），對于異常分數(shù)的評估指標如下：

1）E（h（x））→n-1，S（x，ψ）→0，說明x平均路徑越長，越不容易被孤立，越有可能為正常點。

2）E（h（x））→0，S（x，ψ）→1，說明x越容易被孤立，越有可能為異常點。

3）E（h（x））→c（ψ），S（x，ψ）→0.5，說明實例x的平均路徑長度E（h（x））與iTree 中查找點失敗的平均路徑c（ψ）相近，則x可能為異常點，也可能為正常點。

此時構(gòu)建EIF 的iTree 即滿足高精度值和高差異度值的iTree。SA-EIF 降低了基分類器的數(shù)量，提升了EIF的執(zhí)行效率和分類精度。

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

實驗平臺配備Intel Core i7-8750H 處理器，16 GB 內(nèi)存，Windows10 操作系統(tǒng)，所有算法都基于Python實現(xiàn)。

本章使用3組實驗來對SA-EIF的有效性進行綜合評估，驗證該算法對于EIF執(zhí)行效率和精確度的提升。

3.1 實驗數(shù)據(jù)與測試方法

實驗數(shù)據(jù)：實驗使用離群值檢測數(shù)據(jù)庫（Outlier Detection DataSets，ODDS）中的真實數(shù)據(jù)集，詳細信息如表2 所示。這些數(shù)據(jù)集包括低維數(shù)據(jù)集和高維數(shù)據(jù)集、樣本數(shù)量較少的數(shù)據(jù)集和樣本數(shù)量較多的數(shù)據(jù)集。對于樣本數(shù)量較少的數(shù)據(jù)集Lympho，則采用10 折交叉驗證求平均值的方法進行實驗，對于其他數(shù)據(jù)集則采用5折交叉驗證法。

表2 ODDS異常數(shù)據(jù)集

對比算法：為了驗證所提SA-ELF 算法的有效性，將實驗結(jié)果與EIF、iForest、LOF，進行了對比分析。同時為了更加合理地展現(xiàn)對比結(jié)果，將iForest、EIF、SA-EIF 的默認參數(shù)設定為：子樣本數(shù)量ψ=256，iTree 數(shù)量T=100。其中EIF 與SA-EIF 的擴展等級則設置為最高。

評估指標：針對算法預測的準確性，選用異常檢測常用的評估指標AUC［29］來對算法的準確性進行檢驗。AUC 值越高，則說明模型的泛化能力越強，預測的準確性越高［30］。同時，分別對算法的執(zhí)行效率進行評估。最終，為了更好地評價算法性能，評估了iTree參數(shù)的變化對SA-EIF 算法預測結(jié)果的影響。

3.2 準確性評估

首先，在表2所示的6個異常檢測數(shù)據(jù)集上，評估了SA-EIF 的預測準確性，并與EIF、iForest、LOF 算法進行了對比分析，實驗結(jié)果如表3所示。

表3展示了4種算法在檢測精度上的差異。綜合分析實驗結(jié)果可知，SA-EIF 算法的AUC 均優(yōu)于EIF，具體提升約5%。而在較小規(guī)模的數(shù)據(jù)集中，LOF 的檢測精度要高于其他3種算法，SA-EIF算法的檢測精度與EIF 總體上差別很小，這是因為數(shù)據(jù)集分布較為稀疏因此易于劃分。而對于異常點較多的Satellite數(shù)據(jù)集，由于異常數(shù)據(jù)的增多并且分布更加密集，SAEIF 的分類效果均優(yōu)于其他3 種算法。因為SA-EIF基于模擬退火選擇了精度高且差異度高的iTree 構(gòu)建集成學習模型，使得最終的集成分類效果更好。

表3 4種算法在不同數(shù)據(jù)集上檢測的AUC值

在Arrhythmia 和Satellite 這2 種異常數(shù)據(jù)比例較高的數(shù)據(jù)集中，SA-EIF 的AUC 值要明顯高于其他3種算法，說明SA-EIF 更適合應用于異常數(shù)據(jù)比例較高的數(shù)據(jù)集。

3.3 執(zhí)行效率評估

本節(jié)在表2 所給數(shù)據(jù)集上評估對比了SA-EIF、EIF、iForest、LOF 算法的執(zhí)行時間。實驗結(jié)果如表4所示。

由表4 綜合分析實驗結(jié)果可知，SA-EIF 算法由于構(gòu)建時舍棄了部分檢測性能較差的iTree，減少了測試時的計算消耗，因此SA-EIF 在各類型數(shù)據(jù)集上的執(zhí)行效率均高于EIF 算法。根據(jù)SA-EIF 構(gòu)建時選擇iTree 的數(shù)量，較EIF 算法減少了約20%～40%的計算成本。隨著數(shù)據(jù)量的增大，因為SA-EIF 和EIF 在構(gòu)建過程中會進行部分向量間運算，所以在時間開銷上均劣于iForest。在高維度的數(shù)據(jù)集上，LOF 的時間開銷均高于其他3 種算法，因為LOF 是一種基于密度評估的算法，數(shù)據(jù)集維度的增加會導致距離計算的時間復雜度隨之增加。而其他3 種算法的孤立機制對于數(shù)據(jù)集的維數(shù)不具依賴性，在高維數(shù)據(jù)集中也具有線性的復雜度。

3.4 局部異常檢測評估

本節(jié)選用的實驗數(shù)據(jù)集為服從高斯分布的2 個二維數(shù)據(jù)集。左上和右下數(shù)據(jù)簇的數(shù)量均為400。將iForest 和SA-EIF 算法的異常檢測能力進行對比，可以直觀地看出EIF 改善了iForest 對于局部異常點不敏感的問題。

分別使用iForest 和SA-EIF 對數(shù)據(jù)集進行訓練、評估的過程后，得到2 組異常分數(shù)，并將所得到的異常分數(shù)劃分為10 個層次。最終2 種算法的異常分數(shù)分布等高圖如圖3 所示，圖中顏色越深，則表明該區(qū)域的異常分數(shù)越高，分布在該區(qū)域的數(shù)據(jù)點越有可能為異常點。

iForest由于采用了軸平行的劃分策略，使得異常分數(shù)等高圖在數(shù)據(jù)簇的平行軸線上偏差較大，導致了異常檢測的掩蓋效應。如圖3（a）中，iForest就可能會將左下區(qū)域和右上區(qū)域中的異常點錯誤地判斷為正常點。而SA-EIF的異常分數(shù)等高分布圖則更具層次感，更加符合原數(shù)據(jù)的分布規(guī)律，因此可以更好地檢測出數(shù)據(jù)集中的局部異常點。

圖3 高斯分布數(shù)據(jù)集上異常分數(shù)等高圖

3.5 參數(shù)敏感性評估

本節(jié)在異常數(shù)據(jù)比例較高的Arrhythmia 數(shù)據(jù)集上評估SA-EIF 選取k棵iTree 構(gòu)建EIF 的重要參數(shù)k，觀察k的變化對算法預測結(jié)果的影響。

設置SA-EIF算法的默認參數(shù)T=100，子采樣數(shù)ψ=256，從50 到100 變化參數(shù)k。圖4 展示了SA-EIF 在數(shù)據(jù)集上隨參數(shù)k變化的時間開銷。而圖5 展示了SA-EIF在數(shù)據(jù)集上隨著參數(shù)k變化的AUC標準差。

如圖4 所示，隨著k值從100～50 降低，SA-EIF 算法的時間開銷也隨之減小，這是因為k值的降低，縮小了EIF 的構(gòu)建規(guī)模，減少了算法的測試開銷。分析圖5 可以得出，當k值在100～80 以內(nèi)時，算法的AUC標準差波動較為平穩(wěn)，隨著k值從80～50 緩慢減少，SA-EIF 算法的AUC 標準差逐漸增加，當k值減少至50時，此時算法的預測結(jié)果波動較大，穩(wěn)定性降低。

圖4 SA-EIF在不同參數(shù)k下的時間開銷

圖5 SA-EIF在不同參數(shù)k下AUC的標準差

由實驗結(jié)果得知，SA-EIF 參數(shù)k值設置過低雖然可以大幅減少EIF 的時間開銷，但會導致最終的集成學習模型不收斂、欠擬合，算法的穩(wěn)定性降低。

4 結(jié)束語

本文從EIF 算法泛化能力弱、構(gòu)建冗余的iTree導致算法的時間開銷較大等問題入手，根據(jù)選擇性集成思想提出一種基于模擬退火的擴展孤立森林算法，對構(gòu)建EIF 的iTree 使用了擇優(yōu)再組合的集成方法。最終在ODDS 異常檢測數(shù)據(jù)集中的實驗結(jié)果表明，SA-ELF 算法較EIF算法提升了約5%的檢測精度，減少了約30%的時間開銷。同時，與iForest 相比，改善了iForest對于局部異常點檢測不敏感的問題，但增加了時間開銷。

此外，SA-EIF 基于EIF，所以在構(gòu)建孤立超平面時無法避免使用向量間計算，因而增加了計算成本。下一步工作可以結(jié)合SA-EIF 構(gòu)建時選取的iTree 具有高差異度因此耦合度較低的特點，利用分布式系統(tǒng)實現(xiàn)并行化，改善本算法的執(zhí)行效率。同樣可以利用多粒度掃描機制MGS 作為維數(shù)選擇過程，構(gòu)建層次化集成學習模型，進一步提高算法的檢測精度。