基于自編碼器和集成學習的半監(jiān)督異常檢測算法*

夏火松，孫澤林

(武漢紡織大學管理學院，湖北 武漢 430073)

1 引言

異常檢測是數(shù)據(jù)挖掘中一種重要的分析方法，Hawkins[1]將異常定義為“一種與大部分數(shù)據(jù)偏離較大的數(shù)據(jù)，可能產(chǎn)生于不同的機制”。異常既可能由實驗數(shù)據(jù)的誤差和變異產(chǎn)生，也可能由于此類數(shù)據(jù)來源于不同的類別。所以，異常檢測的應用主要在2個方面，一是在數(shù)據(jù)整理過程中對數(shù)據(jù)清洗，減少噪聲對模型的影響；二是將異常點本身作為研究對象，挖掘異常值產(chǎn)生的實際意義，后者主要應用在金融欺詐、網(wǎng)絡監(jiān)控、醫(yī)療診斷等方面。

異常檢測方法從早期的應用統(tǒng)計檢驗，再到基于密度聚類[2]、鄰近度、可視化的異常檢測方法，如今更多的是用大數(shù)據(jù)驅動的異常數(shù)據(jù)挖掘方法[3,4]，針對不同的目標，檢驗異常程度的方式也不同?；诰垲怺2]的方法是異常檢驗中最常用的方法，該方法通過對樣本進行聚類分析，使樣本點按特征分成不同的簇，將未分入簇中的點視為異常點。Souza等[5]提出一種基于多方向分解技術和多元技術相結合的異常檢測方法，將張量因子分解HOSVD(Higher Order Singular Value Decomposition)算法與K-means分類算法相結合，用于識別智能城市傳感器的數(shù)據(jù)模式。基于概率統(tǒng)計的異常檢驗方法出現(xiàn)相對較早，其基本假設為正常數(shù)據(jù)位于高概率區(qū)域，異常數(shù)據(jù)出現(xiàn)在統(tǒng)計分布低概率的區(qū)域，這類方法通常依賴數(shù)據(jù)分布和先驗概率。Bayerstadler等[6]提出了多項式貝葉斯?jié)撟兞磕Ｐ?，總結了潛變量的行為模式，基于貝葉斯收縮技術的馬爾可夫鏈蒙特卡洛算法來估計模型參數(shù)，對欺詐性和濫用性索賠的識別方法進行了改進。Liu等[7]構造了一種新的測試統(tǒng)計量族，組合新的統(tǒng)計量適應不同的尾部概率，以檢測平均位移判斷異常點的存在。Jiang等[8]提出了一種基于概率表示框架的動態(tài)極大極小概率機DMPM(Dynamic Minimax Probability Machine)診斷過程故障的方法，建立一個信息準則來確定DMPM的最優(yōu)降維順序，能廣泛地應用在工業(yè)故障診斷過程中?；卩徑鹊姆椒蛇M一步分為基于距離[9]和基于密度的方法。任家東等[10]通過比較樣本點之間的相對距離和稀疏性來判斷異常點，提出了一種多層次入侵檢測模型，基于KNN和隨機森林來檢測網(wǎng)絡異常行為?；诳梢暬漠惓z驗方法利用計算機模擬、人機交互等技術，可以直觀地判斷異常點是否存在。Liu等[11]將圖形分析技術應用在異常檢測上，用異構圖表示相關關系，通過分析局部和全局特征來識別異常。對于結構復雜、異常屬性不同的情況，常用集成異常檢測算法組合來識別異常，楊先圣等[12]通過融合3種異常檢測算法，以boost提升框架來增強檢測效率。Eshghi等[13]提出了一種基于Dempster-Shafer和MCDM的異常檢測方法，利用多準則決策方法、直覺模糊集和證據(jù)推理將交易變量行為趨勢結合起來，提高異常檢測的精度。

在多數(shù)情況下異常數(shù)據(jù)是無標記的，因此異常檢測研究多從無監(jiān)督學習的視角出發(fā)[14]。而在僅有少量標簽或者能直觀地判斷出異常存在的情況下，半監(jiān)督學習對于異常檢驗的效果更好。Elkilang等[15]提出了一種基于聚類的半監(jiān)督離群點檢測方法，該方法將正常數(shù)據(jù)和未標記數(shù)據(jù)點表示為二部圖,用無參數(shù)聚類技術對二部圖進行聚類，將未標記的數(shù)據(jù)點分為異常點和正常點，并在分類數(shù)據(jù)集和文本數(shù)據(jù)集上驗證了其有效性。Adeli等[16]提出了一種基于線性判別分析最小二乘公式的半監(jiān)督魯棒判別分類方法，利用有標記訓練數(shù)據(jù)和無標記測試數(shù)據(jù)同時檢測樣本異常得分和特征噪聲。

近幾年有學者結合深度學習的思想來檢測高維數(shù)據(jù)的異常[17]，Deng等[18]提出了一種基于張量-塔克分解和遺傳算法的單分類塔克機GA-OCSTuM(Genetic Algorithm-One Class Support Tucker Machine)，這類無監(jiān)督的大數(shù)據(jù)異常檢測方法在保留數(shù)據(jù)結構信息的同時，提高了異常檢測的準確性和效率。Munir等[19]針對時間序列提出了一種基于深度學習的異常檢測方法DeepAnT(Deep Learning for Anomaly Detection in Time Series),首先用深度卷積神經(jīng)網(wǎng)絡訓練未標記數(shù)據(jù)，預測時間序列的正常行為，并對15種異常算法進行詳細的評估，證明了DeepAnT算法的準確性。Chakraborty等[20]提出了一種基于深度堆疊自編碼器和概率神經(jīng)網(wǎng)絡的異常檢測框架來提升異常檢測技術的性能。Kieu等[21]提出了一個時間序列離群點檢測框架，利用自動編碼器來重建豐富的時間序列特征。

綜上所述，早期的異常檢測研究停留在參數(shù)檢驗、區(qū)間估計等統(tǒng)計回歸方法，對于數(shù)據(jù)量少維度低的數(shù)據(jù)有不錯的識別效果，但隨著數(shù)據(jù)量和數(shù)據(jù)維度的不斷增加以及異常類型的多樣化、復雜化，傳統(tǒng)的應用統(tǒng)計方法難以取得很好的效果，數(shù)據(jù)挖掘的應用已經(jīng)是大勢所趨。并且多數(shù)據(jù)情況下采用無監(jiān)督學習算法解決異常檢測問題，算法通過bagging和feature bagging集成，而boosting應用很少見。針對以上問題，本文基于異常集成視角，提出了一種AE-AdaBoost(Auto Encoder-Adaboos)半監(jiān)督異常檢測模型，首先用正常數(shù)據(jù)集訓練出一個自編碼器[22]，然后導入實驗數(shù)據(jù)進行特征選擇，在編解碼的過程中增大異常點的異常程度(如圖1所示)，再將處理后的數(shù)據(jù)導入AdaBoost提升框架中，融合孤立森林iforest、局部異常因子LOF(Local Outlier Factor)、K-means 3種基分類器，依次檢測全局異常、局部異常點和異常簇，在每一輪訓練過程中，以最小化指數(shù)損失函數(shù)來更新分類器的權重，以此提高模型檢測的準確率。我們在UCI的5組異常數(shù)據(jù)集上進行實驗，采用準確率、ROC曲線和AUC作為評價標準，結果表明，該模型在有效提取關鍵特征的基礎上提高了AdaBoost的穩(wěn)定性,在異常檢測的準確率上要高于目前主流的異常檢測算法。

Figure 1 The abnormal degree increased after AE training圖1 AE訓練后異常程度增大

2 算法原理

2.1 基于自編碼器的降維

自編碼器AE(AutoEncoder)[23]作為非監(jiān)督學習的多層神經(jīng)網(wǎng)絡，包含編碼器、隱含層、解碼器3部分，其工作原理如圖2所示。首先將輸入數(shù)據(jù)X進行壓縮編碼得到隱含層數(shù)據(jù)，再將隱含的數(shù)據(jù)解碼，通過訓練網(wǎng)絡使輸出X′等于輸入，將原始數(shù)據(jù)X映射到隱含層H,得到隱含層特征Z,編碼函數(shù)為f(X),解碼函數(shù)為g(X)，將隱含特征Z映射到輸出X′,訓練過程中損失函數(shù)為：

Loss(X,X′)=‖X-X′‖2

(1)

Figure 2 Structure of AutoEncoder圖2 自編碼器的結構

編碼網(wǎng)絡和解碼網(wǎng)絡用神經(jīng)網(wǎng)絡的激活函數(shù)表示如下：

Z=δ(WX+b)

(2)

X′=δ′(W′Z+b′)

(3)

其中,δ()、δ′()為非線性激活函數(shù),W,b,W′,b′為線性變換的權重和偏置。

最小化損失函數(shù)來優(yōu)化編碼器和解碼器中的參數(shù)，等價成為非線性優(yōu)化問題;

minδ,W,bLoss(X,X′)=

‖X-δ′(δ(WX+b))+b′‖2

(4)

2.2 基于iforest、LOF和K-means的異常檢測

(1)孤立森林iforest[24]。在異常檢測領域中，iforest是一種基于Ensemble的異常檢驗算法，用二叉樹對數(shù)據(jù)進行迭代劃分，該算法用蒙特卡洛方法得到一個收斂值，在數(shù)據(jù)集中隨機選擇一個特征作為起始節(jié)點，并在此特征最大值和最小值之間隨機取值作為分支點，重復上述步驟，直到子節(jié)點中只包含一個數(shù)據(jù)或者樹的深度達到閾值，迭代完成后，計算數(shù)據(jù)點在樹中的層數(shù)即高度，將葉到根的高度作為異常分數(shù)，分離一個點所需的維度越小，即高度越低，那么該點異常的可能性越大。iforest算法不適合特別高維的數(shù)據(jù)，因為在迭代過程中，每次切割數(shù)據(jù)空間都只是選取一個維度和其中的一個特征，生成樹后仍有大量的維度沒有被使用，造成對全局變量敏感，而對于局部異常往往檢驗效果很差。

(2)局部異常因子LOF(Local Outlier Factor)[25]。LOF算法則只著重針對局部異常點，通過比較樣本點與其鄰域點的平均可達密度來判斷樣本是否為異常點。但是，LOF是通過計算樣本點的第K鄰域來確定平均可達密度的，而不是全局計算，所以對于全局異常點的檢測效果較差，而且很難發(fā)現(xiàn)稀疏分布下的異常簇。

(3)K-means[26]。K-means是典型的聚類算法，它將樣本點按照特征劃分成不同的簇，將不屬于任何簇的點視為異常點。算法首先隨機選擇K個樣本作為初始聚類中心，得到初始均值向量，再計算樣本與各均值向量的距離(歐氏距離)，根據(jù)距離最近的均值向量確定樣本點的簇標記，對劃分后的簇重新計算簇中心，更新均值向量并進行迭代，直到均值向量保持不變。傳統(tǒng)的K-means算法因為是隨機選擇初始聚類中心的而具有不穩(wěn)定性，如果初始聚類中心包含離群點，那么聚類的效果會很差。

2.3 基于AdaBoost的提升框架

AdaBoost算法是Freund和Schapire根據(jù)在線分配算法提出的，他們詳細分析了AdaBoost算法錯誤率的上界，以及為了使強分類器達到錯誤率，算法所需要的最多迭代次數(shù)等相關問題。在實際應用中，由于單獨算法的檢驗準確率較低，而且泛化能力較弱，常用集成學習的方法來融合基學習器，發(fā)揮各自的優(yōu)點來提升檢驗的準確率。集成學習可分為序列集成方法和并行集成方法，以boost[27]為代表的序列集成方法根據(jù)基學習器之間的關聯(lián)順序，對上個學習器學習錯誤的樣本，在下個學習器中增加其權重，通過加性模型組合弱學習器成為強學習器來提升學習效果。以Bagging[28]為代表的并行集成方法基于自助抽樣的方法，采用投票的方式獲得最終的結果。

大多數(shù)異常檢測研究都是基于無監(jiān)督學習的，針對無標簽的情況，常用bagging集成方法來訓練模型，而在有標簽或有部分標簽的情況下，半監(jiān)督學習的效果往往優(yōu)于前者。由于本文主要研究有標簽問題，而且基學習器的精度較高，所以以AdaBoost集成方法來融合基學習器優(yōu)化檢測效果。AdaBoost是一種基于提升思想的迭代式算法，通過依次訓練不同的弱分類器，迭代更新數(shù)據(jù)權值，組合弱分類器產(chǎn)生一個強分類器。算法過程如算法1所示。

算法1AdaBoost算法

輸入：D={(x1,y1),…,(xm,ym)},yi∈{-1,1},xi為第i個樣本，yi為其標簽，基學習算法Φi,訓練輪數(shù)為T,x={x1,x2,…,xn}。

步驟1初始化樣本權值分布：D1(x)=1/m;

步驟2 fort= 1,2,…,T

將權值分布代入基學習算法中訓練，得出分類器ht(x);

步驟3ht(x)誤差εt=Px～Dt(ht(x)≠F(x));/*F(x)為x的真實函數(shù)*/

步驟4 ifεt>0.5thenbreak;

步驟5 else更新樣本分布：

其中αt=(1/2)ln((1-εt)/εt),Zt為規(guī)范化因子;

步驟6 endfor

3 算法設計

本文提出的算法如圖3所示，算法由2部分組成，即自動編碼器的數(shù)據(jù)降維和AdaBoost提升框架的檢測部分。將原始數(shù)據(jù)輸入AE的輸入層，經(jīng)過編碼解碼后通過反向傳播得到最優(yōu)參數(shù)，最終在隱含層得到降維后的數(shù)據(jù)，并且在訓練過程中，異常點的異常程度被增大，更利于模型準確地檢測出異常點。AE算法流程如算法2所示。

Figure 3 Algorithm in this paper圖3 本文算法

算法2AE算法

輸入：D={(x1,y1),…,(xm,ym)},xi是n維數(shù)據(jù),yi為數(shù)據(jù)標簽,Z是隱含層的特征,Z的維度n′

輸出：隱含層特征Z。

步驟1對數(shù)據(jù)xi進行編碼，得到隱含層特征：Z=δ(WX+b)，其中δ()是編碼器的非線性激活函數(shù)，W和b是線性變換的權重和偏置。

步驟2對隱含層特征Z解碼，得到重建的輸出:X′=δ′(W′Z+b′),其中δ′()是解碼器的非線性激活函數(shù)，W′和b′是線性變換的權重和偏置。

步驟3通過反向傳播使輸出等于輸入，以最小化損失函數(shù)訓練模型，求得編碼器和解碼器的最優(yōu)參數(shù)：

minδ,W,bLoss(X,X′)=

‖X-δ′(δ(WX+b))+b′‖2

算法3本文算法

輸入：降維后數(shù)據(jù)S={(x′1,y1),…,(x′m,ym)},x′i是n′維數(shù)據(jù),yi為數(shù)據(jù)標簽,弱分類器h1(x)為iforest，弱分類器h2(x)為LOF，弱分類器h3(x)為K-means。

步驟1初始化數(shù)據(jù)分布D′1=(W11,…,W1n),W1i=1/m,其中i=1,2,…,n。

步驟2調用分類器h1(x)訓練數(shù)據(jù)分布D1，通過交叉驗證調整iTree數(shù)量，根據(jù)樣本標簽設置異常比，以最小化誤差e1訓練iforest。

步驟5基于數(shù)據(jù)分布D2調用分類器h2(x)來訓練，通過交叉驗證調整LOF算法中的K值，以最小化誤差e2訓練LOF的閾值t1：(t1,k)=arg mint1,ke2,比較異常得分score和閾值t1來確定異常值：

步驟8基于數(shù)據(jù)分布D3調用分類器h3(x)來訓練，通過交叉驗證調整K-means算法中的聚類簇個數(shù)k，選擇各聚類中心的相對距離D作為異常得分score，以最小化誤差e3訓練K-means得到閾值t2：(D,k)=argminD,ke3,比較相對距離D和閾值t2來確定異常值:

在AdaBoost提升框架中，首先選擇基于Ensemble的異常檢測算法iforest對數(shù)據(jù)進行訓練，在檢測出全局異常點后，在下一輪訓練中，增大未被識別出的局部異常點和異常簇的權重使其被重點關注，接下來融合LOF算法，進一步對局部異常點檢測。經(jīng)過以上2步，模型對于數(shù)據(jù)集的不同種類異常點已有良好的檢測效果，為了增強模型的泛化能力和穩(wěn)定性，模型最后針對特殊的異常簇進行補充檢測，減小了傳統(tǒng)K-means由于初始聚類中心隨機性造成的誤差，隨機選取前2個分類器檢測出的正常點作為初始聚類中心，以計算各聚類中心的相對距離找出異常簇。

4 實驗與分析

將本文算法與當前主流的異常檢驗算法進行實驗對比，并檢驗自編碼器的特征選擇對于異常檢測的影響。首先將iforest、OCSVM(One Class SVM)、LOF、AdaBoost 4種異常檢測算法進行比較，選擇準確率、AUC值和ROC曲線作為泛化性能的評估指標。

準確率基于樣本混淆矩陣(如表1所示)計算，公式如下：

(5)

Table 1 Confusion matrix of classification results表1 分類結果混淆矩陣

選取UCI機器學習庫中5個高維異常數(shù)據(jù)集進行訓練和測試，分別為：Letter數(shù)據(jù)集、Optdigits數(shù)據(jù)集、MNIST數(shù)據(jù)集、Arrhythmia數(shù)據(jù)集、Speech數(shù)據(jù)集，其維度依次為：32維,64維,100維,274維,400維(如表2所示)。樣本數(shù)據(jù)維度不斷增大，以此來檢驗AE降維在異常檢測過程中起到的作用。對于每個數(shù)據(jù)集，采用留出法的思想分配數(shù)據(jù)，即60%的數(shù)據(jù)用來訓練，40%的數(shù)據(jù)用來測試。對于iforest、OCSVM、LOF的參數(shù)設置，采用網(wǎng)格搜索法來尋求最優(yōu)解。

Table 2 List of outlier datasets表2 異常數(shù)據(jù)集列表

4.1 實驗1

將本文算法與單獨的異常檢測算法iforest、LOF、OCSVM進行對比，用交叉驗證法獲得iforest、LOF算法的最優(yōu)參數(shù)，實驗結果如表3所示。對于異常比重較小的數(shù)據(jù)集，數(shù)據(jù)分布較為集中，LOF對局部異常更敏感，所以有較好的準確率,OCSVM有能力獲取數(shù)據(jù)集的分布形狀，對于高維大樣本數(shù)據(jù)集，在未知其數(shù)據(jù)分布的情況下，OCSVM的識別能力較強，所以隨著樣本數(shù)據(jù)量和維度的升高，OCSVM的檢測準確率也隨之提高。從圖4可以看出，本文算法的性能要優(yōu)于單獨異常檢測算法的。

Table 3 Average accuracy of integrated algorithm and individual algorithm表3 集成算法和單獨算法的平均準確率 %

Figure 4 ROC curve and AUC of each algorithm on 5 datasets圖4 各算法在5個數(shù)據(jù)集上的ROC曲線和AUC

4.2 實驗2

將本文算法與bagging集成算法、ILD-BOOST(Iforest-LOF-DBSCAN BOOST)集成算法[12]在未降維的條件下進行對比，bagging集成算法選擇feature bagging[29]法，對以上5個數(shù)據(jù)集進行異常檢測，準確率如表4所示。通過表4中的數(shù)據(jù)可以得出，本文算法對比無監(jiān)督集成學習，異常檢測的效果更好。

Table 4 AUC of 3 integrated algorithms for anomaly detection表4 3種集成算法異常檢測的AUC

4.3 實驗3

首先選用主成分分析對數(shù)據(jù)降維，在此基礎上，分別對比了iforest、LOF和feature bagging與本文算法的集成準確率，結果如表5所示。相比于單獨算法，本文算法的檢測準確率要高得多，feature bagging算法效果更依賴弱分類器的準確性，而本文算法則能夠取長補短地融合弱分類器，降低模型的偏差，所以在有標簽的條件下，本文算法得到的效果更好。下一步將在本文算法的基礎上，選擇不同的降維方法比較檢測的正確率。PCA和KPCA作為線性降維和非線性降維的經(jīng)典方法，將其設置為對照組用來檢測自編碼器的降維效果。對PCA算法，選取95%的貢獻率來確定主成分的個數(shù)，對KPCA算法，選擇徑向基作為核函數(shù)來保證原始數(shù)據(jù)降維后損失較小。將本文算法與PCA-AdaBoost(Principal Component Analysis-AdaBoost)、KPCA-AdaBoost(Kernel Principal Component Analysi-AdaBoost)進行實驗對比，實驗結果如表6所示。隨著維度的增加，PCA對非線性結構的處理能力較差，所以準確率提升效果佳，由于徑向基核函數(shù)能夠將低維空間映射到高維空間，所以KPCA處理非線性結構的數(shù)據(jù)效果較好，但是由于核函數(shù)的計算開銷太大，時間效率低，在實際應用中使用率不高。所以，自編碼器是高維非線性數(shù)據(jù)降維的首選方法。

Table 5 Accuracy of each algorithms under PCA dimension reduction表5 PCA降維下各算法檢測準確率 %

Table 6 Average accuracy of algorithms under different dimension reduction methods表6 不同降維方法下算法平均準確率 %

4.4 實驗4

對比本文算法與深度自編碼器(DAE)的檢測準確率，DAE算法以平均絕對誤差作為損失函數(shù)，迭代次數(shù)和隱含層數(shù)取損失函數(shù)趨于收斂的最小值，隱含層節(jié)點數(shù)為上層的一半，將重建誤差作為異常分數(shù)，誤差過大的數(shù)據(jù)點作為異常點，實驗結果如表7所示。由表7可以看出，DAE算法通過對比數(shù)據(jù)間的重構誤差，獲得了較高的異常檢測率，但是在高維數(shù)據(jù)集上AE-AdaBoost算法表現(xiàn)得更好。并且在效率成本上，DAE花費的訓練時間較長，沒有集成提升框架的高效性。

Table 7 Comparison of accuracy between AE-AdaBoost algorithm and DAE algorithm表7 AE-AdaBoost與DAE算法準確率對比 %

5 結束語

本文通過將自編碼器和AdaBoost集成算法組合在一起，提出AE-AdaBoost半監(jiān)督異常檢測算法。相比于傳統(tǒng)的異常檢測算法，本文算法通過自編碼器對高維數(shù)據(jù)降維，并且在編碼解碼過程中增大異常點的異常程度，使異常點在數(shù)據(jù)集中更容易被識別，相比于PCA降維能更好地識別異常點并提取非線性特征，相較于KPCA算法，在計算復雜度以及時間效率上有更大提升。利用iforest、LOF、K-means 3種異常檢測算法對不同異常類型的敏感特性，全方位地檢測數(shù)據(jù)中存在的異常點。相比于單一算法，集成提升框架能融合每個弱分類器的優(yōu)勢，增加檢測準確率，很好地解決了高維異常數(shù)據(jù)的檢測問題。在后續(xù)研究中，可以考慮在半監(jiān)督的異常檢測模型中加入強化學習以及融合馬爾科夫鏈對異常檢測做進一步研究。