基于模擬退火的擴(kuò)展孤立森林異常檢測算法

王詩愉，肖利東，嚴(yán)心淳，應(yīng)文豪

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

0 引 言

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

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

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

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

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

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

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

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

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

1 相關(guān)工作

1.1 iForest算法

iForest是一種集成學(xué)習(xí)算法，類似于隨機(jī)森林由多棵決策樹組成，iForest也由多棵iTree 組成。iForest的異常檢測分為2 個(gè)部分，第一個(gè)部分是訓(xùn)練階段，第二個(gè)部分是評估階段。

1.1.1 訓(xùn)練階段

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

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

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

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

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

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

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

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

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

1.1.2 評估階段

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

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

定義2 異常分?jǐn)?shù)。給定一個(gè)大小為ψ的樣本子空間和一個(gè)樣本數(shù)據(jù)x，則對于樣本數(shù)據(jù)x的異常分?jǐn)?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］的思想進(jìn)行異常檢測，并使用隨機(jī)斜率構(gòu)建孤立超平面來避免iForest 中軸平行現(xiàn)象導(dǎo)致的決策精度下降、對局部異常點(diǎn)不敏感等問題。

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

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

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

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

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

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

1.3 存在的問題

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

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

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

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

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

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

2 基于模擬退火的EIF算法

2.1 iTree的構(gòu)建

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

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

給定訓(xùn)練集Χtrain={x1，x2，…，xψ}，如果樹Ti對于Χn的預(yù)測結(jié)果與真實(shí)結(jié)果一致，則y（ψ，i）=1，預(yù)測錯(cuò)誤則y（ψ，i）=0。L代表初次構(gòu)建時(shí)iTree 的數(shù)量，ψ代表Χtrain中的樣本個(gè)數(shù)。最后根據(jù)每棵iTree 對于訓(xùn)練集的預(yù)測結(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)計(jì)量法，Qi，j∈［-1，1］，Qi，j差異值越大，則說明樹Ti與Tj這2 棵iTree 的差異度越小。如果存在2棵iTree相互獨(dú)立，則這2棵iTree的差異值為0。

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

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

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

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

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

2.3 SA-EIF算法步驟

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

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

算法SA-EIF

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

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

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

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

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

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

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

Step4.2 產(chǎn)生新解?；诋?dāng)前溫度t的大小，隨機(jī)擾動(dòng)產(chǎn)生一個(gè)新解Tj。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.1 實(shí)驗(yàn)數(shù)據(jù)與測試方法

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

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

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

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

3.2 準(zhǔn)確性評估

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

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

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

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

3.3 執(zhí)行效率評估

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

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

3.4 局部異常檢測評估

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

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

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

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

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

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

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

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

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

圖5 SA-EIF在不同參數(shù)k下AUC的標(biāo)準(zhǔn)差

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

4 結(jié)束語

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

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