基于模糊孤立森林算法的多維數(shù)據(jù)異常檢測方法*

李 倩 韓 斌 汪旭祥

（江蘇科技大學 鎮(zhèn)江 212000）

1 引言

所謂異常，即為一種具有不同數(shù)據(jù)特征的數(shù)據(jù)模式，該模式有別于正常情況，基于這種異常情況的研究與分析就稱之為異常檢測技術［1～4］。近年來，國內外研究學者不斷研究探索提出了許多異常檢測的算法，主要包括基于統(tǒng)計的模型，基于距離的模型，基于線性變換的模型，基于非線性變換的模型等。丁潔等［5］提出了一種基于相關系數(shù)的異常行為檢測方法，該方法借助于自相關系數(shù)，研究并實現(xiàn)了基于自相關模型的異常行為自動檢測系統(tǒng)，擁有較強的擴展性。文獻［6］結合基于成分分裂的增量學習方法，采用局部貝葉斯模型選擇方法進行高斯混合模型訓練。提出了一種基于高斯混合模型的異常檢測算法（LVBGMMS），該算法針對EM算法以及貝葉斯模型選擇方法的弊端進行改進。李海林等［7］提出一種基于頻繁模式發(fā)現(xiàn)的異常檢測方法，利用符號化的時間序列找出原有序列中的頻繁模式，最后根據(jù)最長公共子序列匹配方法度量頻繁模式與當前新增加時間序列數(shù)據(jù)之間的相似度，找出新增數(shù)據(jù)的異常模式，解決了傳統(tǒng)異常片段檢測方法在處理增量式時間序列時效率低下的問題。然而上述的這些方法大都基于正常模型，是針對正常數(shù)據(jù)的一種優(yōu)化方法，因此，存在一定的誤報情況，即將正常數(shù)據(jù)識別為異常數(shù)據(jù)或不能全部識別出異常數(shù)據(jù)。

孤立森林算法由文獻［8］首次提出，該算法是由大量的樹組成，這里稱作iTree，最后的結果則是綜合各個iTree的結果。然而iTree樹又有別于決策樹，就是一個完全隨機的過程，因此構建的過程也較為簡單。與所有現(xiàn)有方法基本不同，孤立森林算法［9］是純粹基于孤立的概念檢測異常，而不依賴于任何距離或密度度量，放棄了對正常數(shù)據(jù)建模的過程，通過構建的iTree樹顯示地找出異常數(shù)據(jù)，并通過限制樹的深度來提高算法效率。由于在使用孤立森林算法［10～11］時大部分的訓練樣本是不需要被孤立的，并且能夠在不隔離所有正常點的情況下使用部分模型，因此利用一個小樣本容量的數(shù)據(jù)集就可以構建模型。然而對于待測的樣本而言，在檢測過程中需要遍歷森林中的每一棵樹，得到一個平均路徑的長度，再進行異常分數(shù)值的計算，但由于每次都是隨機選取屬性進行建樹的，而每個樣本數(shù)據(jù)對于隨機選取的屬性的異常程度又是不同的，所以顯然這種做法存在一些問題。

基于上述問題，本文在孤立森林算法中引入了隸屬度函數(shù)的概念，利用模糊綜合評價的方法對待測數(shù)據(jù)進行綜合評判，提出了一種基于模糊孤立森林算法的多維數(shù)據(jù)異常檢測方法。該方法通過挑選一些有價值的屬性對其分別建樹組成孤立森林，再對每一維屬性的檢測結果進行隸屬度判斷，并與模糊矩陣進行模糊運算得到最終評價結果，最后通過對實際校園一卡通的異常檢測實驗，驗證了其有效性。

2 模糊孤立森林算法

2.1 孤立森林算法

利用孤立森林算法進行異常檢測分為兩個階段［12］：第一個訓練階段，使用訓練集的子樣本構建隔離樹；第二個測試階段，通過隔離樹傳遞測試實例，以獲得每個測試樣本的異常值。

1）訓練階段

在訓練階段，通過遞歸地劃分給定的訓練集，直到實例被孤立或達到一個特定的樹高，從而得到部分模型。樹的高度限制I是隨機的，按次抽樣大小設置大約是樹的平均高度即I=ceiling（log2），然而我們只研究低于平均值的數(shù)據(jù)點，因為這些點更有可能是異常的。

假設從n個樣本數(shù)據(jù)的數(shù)據(jù)集，從數(shù)據(jù)集中無放回抽樣得到個數(shù)據(jù)樣本X=｛x1，…，xn｝，并且服從M變量分布，構建一棵iTree時，在樣本中選擇一個特征值，在其最值區(qū)間選擇一個屬性q和一個分割p，遞歸地劃分X，直到滿足下列終止條件：

（1）樹的高度達到限制值（從算法效率角度出發(fā)，iTree在算法里限制了高度為log2（n））；

（2）|X|=1；

（3）樣本X中所有的數(shù)據(jù)相同；

不斷循環(huán)上述方法，隨機選擇的不同樣本訓練得到多個iTree樹，訓練階段就完成了，即可對待測數(shù)據(jù)進行預測。

2）預測階段

將測試數(shù)據(jù)x從根節(jié)點穿過iTree進行遍歷，直到達到葉子節(jié)點，其中遍歷過程中的路徑長度記作h（x），即從根節(jié)點，經過中間節(jié)點，到達葉子節(jié)點的邊數(shù)。由于iTrees與二叉樹或BST有一個等價的結構，因此外部節(jié)點終止的平均高度h（x）的估計值與在BST中搜索失敗的值相同，我們可以借鑒BST的分析方法來估計其平均路徑長度。BST中不成功搜索的路徑長度為

其中H（k）是諧波數(shù)可以被一個估計值表示，即H（k）=ln（k）+ξ，ξ為歐拉常數(shù)，為0.5772156649。

由于c（n）是給定n的路徑長度的平均值，我們用它來規(guī)范h（x）。則我們定義測試數(shù)據(jù)的異常分數(shù)為

2.2 模糊孤立森林算法

模糊綜合評價［13～14］是一種基于模糊數(shù)學的綜合評價方法，具體來說，模糊綜合評判就是利用模糊數(shù)學以及模糊關系合成原理，將一些難以量化表達、難以確定邊界的因素以定量的形式表達出來，因此可以從多角度對待評價的事物進行隸屬等級情況的綜合評判。

在本文中用該方法對孤立森林算法進行了優(yōu)化，即對孤立森林的異常檢測分數(shù)值不進行異常判斷，而是將孤立森林算法檢測結果進行隸屬度判斷再利用算子與模糊矩陣進行模糊計算得到最終評價結果。模糊綜合評價的具體步驟如下：

1）確定評價對象的因素集U，ui為評價因素，m為評價因素的個數(shù)：

2）確定評價因素的評語集合V，vi為各種可能的評價結果，n為評價結果的總個數(shù)：

3）進行單因素評價。一般來說，為了研究評價對象與評語集合V的隸屬關系，在構造了等級模糊子集后，需要對因素集里的每一個因素ui定量化，即從單因素的角度對各等級的模糊子集做隸屬度判斷。本文采用的是專家估計法，由專家根據(jù)評判等級對評價對象進行打分，最后統(tǒng)計打分結果，并組成模糊關系矩陣：

其中模糊向量rij（i=1，2，…，m，j=1，2，…n）表示某個待評價對象的因素集U中評價因素ui對評語集合V中，各種可能的評價結果vj的隸屬程度。即利用rij來描述一個評價對象在某個因素ui的表現(xiàn)。

4）確定評價因素的模糊隸屬度［16～17］。由于各因素在綜合評價中的重要程度不同，需要對每一個因素ui進行一個隸屬度的判斷，并組成一個集合T記作ti（i=1，2，…，m）且ti≥0，∑ti=1，T就表示所有單因素的隸屬度組成的一個模糊集合。本文將采用孤立森林算法的異常分數(shù)值，經歸一化后得到的值S'作為模糊集合的值，即5）多因素模糊評價［17～18］。利用M( )·，⊕ 算子將模糊集合T與模糊關系矩陣R進行計算，得到各待評價對象的模糊綜合評價結果向量B：

6）模糊綜合評價結果分析。將等級看作一種相對位置，并用秩表示，通常為“1，2，3，…，m”，使其連續(xù)化。最后利用向量B中對應的分量與對應分量所對應的各等級的秩進行求和，從而得到待評價對象的相對位置：

其中，k為待定系數(shù)（k=1或2）目的是防止bj較大時對結果產生影響。

3 實驗

3.1 實驗數(shù)據(jù)

本文的實驗數(shù)據(jù)采用的是實際校園一卡通的消費數(shù)據(jù)，該數(shù)據(jù)記錄了2017年8月至12月校園一卡通的消費情況，共計1136653條。其中，包含了學生和教職工的學號/工號、一卡通號，以及在校使用一卡通卡消費時的時間、地點、每一次的消費金額、交易計數(shù)、收支功能、設備ID、設備流水以及期初余額和期末余額等信息。由于本次實驗是針對學生展開的，所以在異常檢測之前對原始數(shù)據(jù)進行了預處理，去掉了一些無關信息，例如教職工工號、設備流水等。同時，又利用統(tǒng)計學增加了一些學生在校的消費情況統(tǒng)計，最后提取出一些有價值的屬性對其分別建樹，具體的實驗基本步驟如下：

1）第一步：創(chuàng)建iForest；

2）第二步：計算所有待測樣本的異常分數(shù)值；

3）第三步：利用模糊孤立森林算法進行模糊綜合評價；

4）第四步：實驗驗證。

孤立森林算法有兩個輸入?yún)?shù)分別為子采樣大小Ψ和樹的數(shù)目t。其中，子采樣大小Ψ控制訓練數(shù)據(jù)的大小，因為當Ψ無限增加時，會增加處理時間并且需要更大的內存，并不能獲得較好的檢測性能，因此當取樣度較小時，孤立方法效果最好，本文采用Ψ=100作為實驗值。樹t的數(shù)量控制集成的大小，因為路徑長度通常會在t=100之前收斂，所以本文使用t=100作為實驗值。對于孤立森林算法中二叉樹劃分的閾值本文則選取的是每組數(shù)據(jù)的均方差。

3.2 數(shù)據(jù)異常影響因素指標

對一卡通數(shù)據(jù)異常進行模糊綜合評判［19］，主要考慮兩個方面：判斷數(shù)據(jù)是否存在異常的評價因素，即判斷某一學生在校期間是否存在異常行為的評價因素和產生異常的程度。本文主要以經過孤立森林算法處理后的六個方面的學生消費行為為主要評價因素，建立在校學生產生異常行為的指標體系，異常程度也根據(jù)實際情況分為四大類。評價指標如圖1。

由此可見，評價因素集U為U=｛單次消費金額，日消費總額，周消費方差，月消費方差，日正常教學活動期間消費頻次，日早晨八點前消費頻次｝，評價因素的評語集V為V=｛特別異常，異常，較為異常，正常｝，分配給各等級的秩為｛4，3，2，1｝。通過對辦公室老師以及任課老師的調查問卷的統(tǒng)計和歸一化后，我們得到的模糊矩陣為

圖1 在校學生產生異常行為指標

3.3 實驗驗證

通過實驗，我們得到了實際校園一卡通數(shù)據(jù)的模糊綜合評價的結果，并對結果進行了降序排序，根據(jù)結果分布情況按照比例分配，將前10%判斷為特別異常，35%為異常，45%為較為異常，10%為正常，如圖2所示。為了驗證本文所提出的模糊孤立森林異常檢測算法的準確性，隨機抽取了一百位學生進行回訪調查，根據(jù)了解有的學生因為身體的原因需要在?？床≠I藥所以導致了單次消費過高，有的學生確實存在逃課的行為，有的學生不愛吃早飯因此每天早晨八點前消費次數(shù)較少，有的學生已經申請了走讀所以在校的消費行為較少。由此根據(jù)調查結果的統(tǒng)計情況，計算出本文所提的算法準確率為90%，達到了不錯的檢測效果。

圖2 模糊孤立森林算法異常檢測結果圖

4 結語

針對原有的孤立森林算法采用的是隨機選取屬性的方法進行建樹，最后綜合各個樹的結果進行異常判斷，而忽略了每一條數(shù)據(jù)對于所選取的屬性異常程度是不同的這一問題。本文提出了一種基于模糊孤立森林的異常檢測方法，在原有的基礎上引入了模糊的概念。利用隸屬度函數(shù)，從多維度出發(fā)，將數(shù)據(jù)相對于屬性的隸屬度考慮進去，對孤立森林的結果進行了隸屬度的判斷，最后與由評價對象和評語集的隸屬度關系組成的模糊矩陣進行模糊計算，得到一個綜合評價的結果。該方法從多角度對待測樣本進行了一個模糊綜合評判，使得檢測的標準更加的全面、更加的合理化，檢測的結果更加準確，因此達到了較好的實驗效果。