基于標簽傳遞的異常檢測算法研究

趙 曼 趙 耀 朱振峰

（北京交通大學信息科學研究所，北京，100044）

引 言

隨著信息技術(shù)的飛速發(fā)展，互聯(lián)網(wǎng)已經(jīng)滲透到人們?nèi)粘Ｉ畹母鱾€領(lǐng)域。在這些領(lǐng)域中，偶發(fā)性的異常常常蘊含著顯著的（通常具有很大危害性的）行為信息，如機器的不正常運轉(zhuǎn)表示其存在部件故障，信用卡欺詐意味著巨大的經(jīng)濟損失等[1]。因此，研究如何及時檢測異常信息具有重大的現(xiàn)實意義，已成為當前數(shù)據(jù)挖掘領(lǐng)域中的研究熱點[2]。這類檢測出觀測數(shù)據(jù)中的非正常值的學習方式，即為異常檢測。目前，異常檢測主要基于Hawkins對異常的定義[2]：異常點是與其他觀測值存在巨大的差異，以至于使人懷疑這些數(shù)據(jù)產(chǎn)生自不同的機理的觀測值。根據(jù)異常的定義以及異常和其它數(shù)據(jù)之間的關(guān)系，如圖1所示，可以將異常分為3類：點異常、全局異常和上下文異常（條件異常）。

圖1 異常類型Fig.1 Type of outliers

迄今為止學者們提出了多種異常檢測算法。根據(jù)是否利用數(shù)據(jù)的標簽信息，可以將這些算法分為無監(jiān)督檢測算法和有監(jiān)督檢測算法。

無監(jiān)督檢測算法通過學習樣本的隱式結(jié)構(gòu)來區(qū)分孤立點或離群點。典型的算法包含局部異常因子(Local outlier factor，LOF)[3-4]、深度算法[5]、基于角度的異常檢測算法(Angle-based outlier detection，ABOD）[6]等。由于這類算法沒有利用先驗標簽信息，無法判斷其區(qū)分出的離群點是否為異常點，此外該類方法對于全局異常和上下文異常也無法有效檢測，無監(jiān)督檢測算法并不適用于異常檢測，在此不作比較討論。

有監(jiān)督檢測算法利用已有的標簽信息區(qū)分異常。在很多場合，異常樣本（如衛(wèi)星網(wǎng)絡(luò)管理中的故障、網(wǎng)絡(luò)入侵樣例）獲取代價極高，數(shù)據(jù)樣本數(shù)量嚴重失衡。基于此，監(jiān)督檢測算法可以分為單分類算法和兩分類算法：

（1）單分類算法從正例樣本中學習一個數(shù)據(jù)描述，根據(jù)給定或設(shè)計的相似性度量準則判定待測樣本的類別。典型的算法有基于高斯和小波等的算法[7]支持向量數(shù)據(jù)描述(Support vector data description,SVDD)[8]及單分類支持向量機(One-class SVM)[9]等基于支撐域的算法、主元分析(PCA)[10]等基于重構(gòu)的算法以及基于k-mens聚類的檢測算法[11]。其中基于K-means聚類的檢測算法將正例樣本聚為K類，依據(jù)每個聚類的中心和半徑將不屬于所有簇的樣本判為異常；SVDD通過建立一個盡可能包含所有正例樣本的最小超球檢測異常；PCA通過捕捉數(shù)據(jù)的最大變化方向，利用重構(gòu)誤差區(qū)分異常。

（2）由于數(shù)據(jù)的嚴重失衡，學者們在現(xiàn)有兩分類算法的基礎(chǔ)上進行了改進。Veropoulos提出了有偏支持向量機(Biased support vector machine,BSVM)[12]，賦予異常較大的懲罰參數(shù)；Chawla等人[13]提出了樣本合成過采樣技術(shù)(Synthetic minority oversampling technique,SMOTE)來平衡數(shù)據(jù)，提高檢測性能。

雖然學者們提出了大量的異常檢測算法，但目前很少有算法對數(shù)據(jù)的內(nèi)蘊結(jié)構(gòu)進行挖掘。而在異常檢測問題中，相比于大量存在的正常數(shù)據(jù)，異?？梢员灰暈橐环N隨機現(xiàn)象，它通常不具有正常數(shù)據(jù)所具有的某種內(nèi)蘊結(jié)構(gòu)，因此挖掘數(shù)據(jù)內(nèi)蘊結(jié)構(gòu)，利用數(shù)據(jù)結(jié)構(gòu)差異性有助于提高異常檢測性能。為此，本文從數(shù)據(jù)結(jié)構(gòu)差異性角度出發(fā)，提出了基于標簽傳遞的異常檢測算法。本文首先標記部分正例樣本，通過無向圖模型刻畫數(shù)據(jù)所具有的內(nèi)蘊結(jié)構(gòu)，然后通過多重標簽傳遞獲得穩(wěn)定狀態(tài)下未標記正例樣本和待測數(shù)據(jù)的標簽置信度。由于異常數(shù)據(jù)不符合正常數(shù)據(jù)具有的內(nèi)蘊結(jié)構(gòu)，其在穩(wěn)態(tài)下的標簽置信度遠遠低于正常數(shù)據(jù)，由此可將它們在數(shù)據(jù)結(jié)構(gòu)上的差異性轉(zhuǎn)換為標簽置信度的差異性。最后基于正例樣本標簽置信度的統(tǒng)計特性分析，進行集成判決，實現(xiàn)對測試樣本的異常性判決。

1 標簽傳遞模型

1.1 符號說明

為了方便后文闡述，首先對本文用到的一些符號進行說明。令X=[xi]i=1,2,…,N∈RN×d為給定的數(shù)據(jù)集（矩陣），y=[yi]i∈L為標簽向量，其中，yi∈ {1,2,…,c}為與樣本xi相對應(yīng)的類標簽，c為類別數(shù)。此外，定義Y=[Yi,j]∈RN×c為類標簽編碼矩陣，其中，，L={1,…,l}與U={l+1,…,N}分別為標記樣本與非標記樣本索引集合。基于數(shù)據(jù)集X可構(gòu)建一個無向圖G(V,E)，其中V={vi}i=1,…,N為無向圖的結(jié)點集合，E={ei,j=(vi,vj)}i,j=1,…,N為無向圖的邊集合，代表結(jié)點間的關(guān)系。此外，定義對稱權(quán)重矩陣W=[wi,j]i,j∈1,…N∈RN×N，來反應(yīng)圖結(jié)點間的相似度，式中wi,j=exp(-‖ ‖xi-xj2/2σ2)(i≠ j)，且 wi,i=0。

1.2 標簽傳遞模型

標簽傳遞（Label propagation,LP）的目的是用已標記數(shù)據(jù)的標簽信息去預測未標記數(shù)據(jù)的標簽信息。Zhou等[14]在高斯場的啟發(fā)下提出了一種基于圖的標簽傳遞模型，該模型本質(zhì)上屬于一種半監(jiān)督學習模型，其主要思想是：根據(jù)樣本相似性建立圖后，每個樣本的標記信息迭代地向其鄰近樣本傳遞，直至達到全局穩(wěn)定狀態(tài)。

基于全局與局部的一致性假設(shè)前提為：(1)臨近的樣本更可能具有相同的標簽；(2)處于同一結(jié)構(gòu)的數(shù)據(jù)點具有相同標記的可能性較大，構(gòu)造的標簽傳遞模型可通過最小化如下代價函數(shù)得到

該式右側(cè)第一項符合一致性假設(shè)(1)：相鄰的數(shù)據(jù)點具有相似的標記；第二項貼合假設(shè)(2)，表明樣本的穩(wěn)定狀態(tài)與其初始標記相關(guān)。其中，μ＞0為平衡系數(shù)，D=diag[di,i]∈RN×N為對角矩陣，di,i= ∑jwi,j，F(xiàn)=[Fi,…,FN]T∈RN×c為標簽置信度矩陣，‖?‖F(xiàn)表示F-范數(shù)。 對于式（1）的最小化問題，不難得出其最優(yōu)解（標簽傳遞模型）為

如果把反應(yīng)原始標簽信息的標簽編碼矩陣Y看作標簽置信度的初始狀態(tài)，那么，F(xiàn)則可看作是初始標簽置信度經(jīng)過傳遞模型后的穩(wěn)定狀態(tài)。定理1表明Y與F之間存在守恒關(guān)系。

定理1對于式（3）給出的標簽傳遞模型，標簽置信度的初始狀態(tài)與穩(wěn)定狀態(tài)之間存在著守恒，即：1T?F=1T?Y，其中1∈ RN×1為全1列向量。

證明：用1T(μ?I+Δ)左乘式（3）兩邊，可得1T(μ ?I+Δ)F=μ1T?Y。對于拉普拉斯矩陣Δ，由于存在1T?Δ=1T(D-W)≡0,為此不難得出1T?F=1T?Y，證明完畢。

基于由式（2），（3）得到的標簽置信度矩陣，可通過下式對未標記樣本xi，i∈U，的標簽置信度進行預測，獲得相應(yīng)的預測標簽yˉi，從而實現(xiàn)分類的目的。

2 基于標簽傳遞的異常檢測

2.1 問題描述

對于異常檢測問題，相比于大量存在的正常數(shù)據(jù)，異常數(shù)據(jù)可以看成是一種隨機現(xiàn)象，因而通常不具有正常數(shù)據(jù)所具有的某種內(nèi)蘊的數(shù)據(jù)結(jié)構(gòu)。為此，本文提出一種基于標簽傳遞的異常檢測模型。具體來說，即對已知正例樣本（訓練集）進行部分標記，使這些樣本獲得初始的標簽置信度，然后通過標簽傳遞使得未標記的正常數(shù)據(jù)以及測試數(shù)據(jù)獲得穩(wěn)定狀態(tài)下的標簽置信度。對于標記的正例樣本，可以假設(shè)未標記的正常數(shù)據(jù)具有與之相一致的數(shù)據(jù)結(jié)構(gòu)，而異常數(shù)據(jù)通常不符合該內(nèi)蘊結(jié)構(gòu)。這樣，當通過標簽傳遞達到穩(wěn)定狀態(tài)時，未標記的異常樣本的標簽置信度要遠遠低于正例樣本。因而，可以利用異常樣本與正常數(shù)據(jù)在穩(wěn)定狀態(tài)下的標簽置信度的差異性，實現(xiàn)對異常樣本的有效判決。

圖2給出了基于標簽傳遞的異常檢測問題的示意圖。如圖2所示，對于已采集的正常數(shù)據(jù)，隨機標記部分樣本，令標記樣本的初始標簽為1，剩余正常數(shù)據(jù)與待測數(shù)據(jù)視作未標記樣本，初始標簽為0，通過標簽傳遞可獲得穩(wěn)態(tài)下各樣本的標簽置信度。由于異常數(shù)據(jù)通常不符合正例樣本所具有的內(nèi)蘊結(jié)構(gòu)，這樣，異常樣本通過標簽傳遞在穩(wěn)態(tài)下的標簽置信度明顯小于正例樣本，因此可用樣本標簽置信度的差異性體現(xiàn)數(shù)據(jù)結(jié)構(gòu)上的差異性，進而通過分析穩(wěn)態(tài)下未標記正例樣本與待測樣本的置信度差異區(qū)分異常。

圖2 針對異常檢測的標簽傳遞示意圖Fig.2 Outlier detection based on label propagation

2.2 異常檢測框架

基于2.1節(jié)中描述的出發(fā)點，本文提出的基于標簽傳遞的異常檢測框架如圖3所示。令X∈RN×d表示已有的正例樣本數(shù)據(jù)矩陣，xtest∈ R1×d為待測試數(shù)據(jù),～G(～V,～E)為由 ～X=[XTxTtest]T∈ R(N+1)×d構(gòu)建的無向圖。對于來自X的N個節(jié)點，隨機選取l個樣本作為標記樣本，其余N-l個樣本與待測樣本共同看作是未標記樣本。此時，與標記樣本～X～L及未標記樣本～X～U相對應(yīng)的初始標簽分別記為～y～L=[1]T∈ Rl×1與～y～U=[0]T∈ R(N+1-l)×1，其中 ～L與～U分別為標記樣本與非標記樣本的索引集合。經(jīng)過標簽傳遞后，對于每個未標記樣本x∈～X～U都將獲得一個穩(wěn)定狀態(tài)下的標簽置信度。進一步，通過對這些標簽置信度的統(tǒng)計分析，可以對測試樣本進行異常性判決。

圖3 基于標簽傳遞的異常檢測框架Fig.3 Framework of outlier detection based on label propagation

2.3 基于多重隨機標記的標簽傳遞

在2.2節(jié)中提出，通過從正例樣本中隨機選取部分樣本作為標記樣本，然后基于標簽傳遞模型把標記的正例樣本的標簽置信度傳遞給未標記的正例樣本以及測試樣本。這樣，可以在穩(wěn)態(tài)下利用異常數(shù)據(jù)與正例樣本標簽置信度間的差異性，對測試數(shù)據(jù)的異常性進行判決。然而，形成上述穩(wěn)態(tài)下標簽置信度差異性的前提是假設(shè)標記的正例樣本與未標記的正例樣本具有同一的內(nèi)蘊數(shù)據(jù)結(jié)構(gòu)。當對所有正例樣本進行如1.2節(jié)所述的初始隨機標記時，上述假設(shè)條件則有時很難滿足，進而造成上述差異性不明顯。為此，本文提出基于多重隨機標記的標簽傳遞，并進一步通過后續(xù)的集成判決機制，來克服上述問題。

3 基于標簽置信度統(tǒng)計特性的異常判決

對于如圖3所示的第i次，i=1,…,K，基于隨機標記的標簽傳遞，令Pi(?)表示此時未標記正例樣本在穩(wěn)態(tài)下的標簽置信度′的分布，其中表示未標記樣本正例樣本的索引集合。對于測試樣本在穩(wěn)態(tài)下的標簽置信度，如前所述，當其不服從Pi(?)時，則可對其做出異常判決。為此，對于Pi(?)，本文采用如下的閾值設(shè)置方式

式中，Si={}t=1,2…,N-l，sort(?)表示升序函數(shù)。

對于測試樣本xtest在穩(wěn)態(tài)下的標簽置信度，若＜Ti，則得與其相應(yīng)的標簽預測值=-1，否則，t=+1。

最后，為對測試樣本xtest的異常性進一步做出可靠性判決，采取如下的集成投票判決方法

當yˉtest=-1時，則可判定xtest為異常數(shù)據(jù)，否則為正常數(shù)據(jù)。

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

4.1 數(shù)據(jù)集說明及評價標準

4.1.1 數(shù)據(jù)集

為驗證算法的有效性，本文分別在兩個人工數(shù)據(jù)集和5個真實數(shù)據(jù)集上進行了驗證。

兩個人工數(shù)據(jù)集分別為Trefoil-knot數(shù)據(jù)集、Two moon數(shù)據(jù)集，分別包含正例樣本數(shù)：200，100，異常樣本數(shù)：50,100。

5個真實數(shù)據(jù)集分別為：（1）USPS手寫體數(shù)字數(shù)據(jù)集，包含數(shù)字0～9的灰度圖像，取其偶數(shù)類做實驗；（2）UCID圖像壓縮數(shù)據(jù)集，包含圖像的一次和二次壓縮特征，由于圖片經(jīng)過兩次壓縮可能被篡改或加入了其他信息，二次壓縮特征被視作異常類；（3）Arrhythmia數(shù)據(jù)庫，包含正常心率數(shù)據(jù)和15類異常心率數(shù)據(jù)；（4）Isolet口語數(shù)據(jù)集，來源于文獻[15]，包含150個人對26個英文字母的兩次發(fā)音信息；（5）Olivetti人臉數(shù)據(jù)集，包含40個人的人臉圖像，取前10個人的人臉信息作為正常類，其余作為異常類。各真實數(shù)據(jù)集的信息如表1所示。

4.1.2 評價標準

為評價異常檢測的有效性，本文采用Kubat等人提出的G-means評價指標作為異常檢測的評價標準，其定義為

表1 測試數(shù)據(jù)統(tǒng)計信息Tab.1 Information of real datasets

式中：Qse=TP/(TP+FN)表示正常類樣本準確率，Qsq=TN/(TN+FP)表示異常類樣本準確率，TP,TN,FP,FN的定義如表2所示。從定義可以看出，G-means同時兼顧了正常數(shù)據(jù)類與異常數(shù)據(jù)類精度的平均，能更客觀的反映異常檢測算法的檢測性能。

4.1.3 比較算法

為驗證本文提出的基于標簽傳遞的異常檢測算法的性能(Outlier detection based on label propaga-tion，ODLP)，實驗中同如下具有代表性的異常檢測算法進行了比較：主元分析（PCA）[10]、支持向量數(shù)據(jù)描述（SVDD）[8]、PCA與SVDD相結(jié)合的PSVDD[8,10]以及基于K-means聚類[11]的檢測算法。實驗中，本文統(tǒng)一令隨機標記的正例樣本數(shù)l=0.7×N，并且進行K=10次基于隨機標記的標簽傳遞。對于圖權(quán)重wi,j=exp(-‖xi- xj‖2/2σ2)中 σ的選取，令 σ=k?dist，其中dist表示數(shù)據(jù)集X全部樣本距離的均值，定義為

表2 異常檢測分類混淆矩陣Tab.2 Classification confusion matrix in outlier detection

參數(shù)k的取值在(0,5)之間選取即可。

4.2 實驗結(jié)果分析

4.2.1 人工數(shù)據(jù)集實驗結(jié)果分析

本文首先在3個人工數(shù)據(jù)集上進行了驗證。圖4，5分別展示了針對人工數(shù)據(jù)集Trefoil-knot和Two moon異常檢測示意。圖(a)所示為部分正例樣本具有標記的初始標簽狀態(tài)，圖(b)表示經(jīng)過標簽傳遞達到穩(wěn)定狀態(tài)后的未標記樣本標簽置信度，置信度越高則顏色越深。從圖4，5中可以看出，異常樣本的置信度明顯小于正例樣本，進而可以通過分析穩(wěn)定狀態(tài)下未標記樣本的置信度進行異常判決。

圖4 Trefoil-knot數(shù)據(jù)集實驗結(jié)果示意圖Fig.4 Schematic diagram of experimental results of trefoil-knot dataset

圖5 Moon數(shù)據(jù)集實驗結(jié)果示意圖Fig.5 Schematic diagram of experimental results of Moon dataset

表3所示為不同算法在人工數(shù)據(jù)集上的性能對比?？梢钥闯?，對于具有流形內(nèi)蘊結(jié)構(gòu)的合成數(shù)據(jù)，本文提出的ODLP的檢測結(jié)果明顯優(yōu)于其他算法。

表3 不同算法在人工數(shù)據(jù)集上的性能對比Tab.3 Performance of different algorithms on artificial datasets %

4.2.2 真實數(shù)據(jù)集實驗結(jié)果分析

對于多類數(shù)據(jù)集USPS，本文采用one-against-all的實驗方法，相應(yīng)的，對于UCID等其他真實數(shù)據(jù)集，本文統(tǒng)一選取各數(shù)據(jù)集80%的正例樣本作為訓練集，剩余樣本作為測試集。在實驗中，SVDD及PSVDD算法選用高斯核函數(shù)，各種算法的檢測結(jié)果如表4所示。

表4 不同算法在真實數(shù)據(jù)集上的性能對比Tab.4 Performance of different algorithms on real world datasets %

從實驗結(jié)果可以看出，基于K-means聚類的算法的檢測效果略優(yōu)于或相近于構(gòu)建整體數(shù)據(jù)包絡(luò)面的SVDD算法和基于重構(gòu)誤差的PCA算法，但對于具有流形結(jié)構(gòu)的數(shù)據(jù)，其檢測效果并不理想。本文提出的ODLP算法由于充分挖掘了數(shù)據(jù)內(nèi)蘊結(jié)構(gòu)，將正例樣本和異常數(shù)據(jù)在數(shù)據(jù)結(jié)構(gòu)上的差異轉(zhuǎn)換為標簽置信度的差異，有效利用了數(shù)據(jù)的局部結(jié)構(gòu)信息，取得了較為理想的檢測性能，相較于其他算法，平均提高了2%～3%。

對于流形結(jié)構(gòu)數(shù)據(jù)集Olivetti，本文提出的ODLP算法能夠達到88%的檢測性能，明顯優(yōu)于其他算法。

值得注意的是，Arrhythmia數(shù)據(jù)集相較于其樣本維度來說，是一個高維小樣本數(shù)據(jù)集，現(xiàn)有算法均不能取得較理想的檢測結(jié)果，本文提出的基于標簽傳遞的異常檢測算法利用多重隨機標記機制成功解決了高維小樣本問題，取得了理想的檢測效果。

4.2.3 參數(shù)分析

（1）集成模型的個數(shù)K對最終決策結(jié)果的影響

圖6(a)體現(xiàn)了Arrhythmia真實數(shù)據(jù)集中集成個數(shù)K對最終結(jié)果的影響，從圖中可以看出，當K過小或過大時，最終決策效果相應(yīng)下降，K的選取在5～15之間時，檢測效果最好，因此本文選取K=10作為集成模型的個數(shù)。當K過小時，由于標記正常數(shù)據(jù)的隨機性，標記的正例樣本與未標記的正例樣本未必具有同一的內(nèi)蘊數(shù)據(jù)結(jié)構(gòu)，因此需要多次隨機標記。當K過大時，過多的隨機標記過程中極有可能出現(xiàn)多次不能反映數(shù)據(jù)結(jié)構(gòu)的標記。

（2）標記比例r對檢測結(jié)果的影響

圖6 Arrhythmia數(shù)據(jù)集中參數(shù)的影響Fig.6 Influence of parameters in Arrhythmia dataset

圖6 (b)所示為隨機標記過程中標記比例r對檢測結(jié)果的影響。從圖6中可以看出，當標記比例為0.7時，異常檢測效果最佳。因標簽傳遞模型的前提是：標記的正例樣本與未標記的正例樣本具有同一的內(nèi)蘊數(shù)據(jù)結(jié)構(gòu)，即正常數(shù)據(jù)自身的內(nèi)蘊結(jié)構(gòu)。當標記比例過低時，標記樣本不能反映數(shù)據(jù)的結(jié)構(gòu)；當標記比例過高時，未標記樣本數(shù)量減少，同樣不具有數(shù)據(jù)的內(nèi)蘊結(jié)構(gòu)。

（3）PSVDD算法中降維維度對檢測結(jié)果的影響

PSVDD算法通過PCA降維后使用SVDD模型判決異常，其中降維維度對異常檢測結(jié)果影響較大，圖6(c)所示為Arrhythmia數(shù)據(jù)集中使用PCA降維后，維度對檢測檢測結(jié)果的影響。通過觀察可以發(fā)現(xiàn)，原274維數(shù)據(jù)集降至64維后檢測結(jié)果較好，因Arrhythmia數(shù)據(jù)集訓練樣本較少，數(shù)據(jù)維度相對較高，所以相應(yīng)降低數(shù)據(jù)維度可以提高檢測效果，但過低的維度可能導致數(shù)據(jù)信息丟失嚴重，影響檢測效果。

5 結(jié)束語

針對現(xiàn)有異常檢測算法很少對數(shù)據(jù)內(nèi)蘊結(jié)構(gòu)進行挖掘的缺陷，本文提出了一種基于標簽傳遞的異常檢測算法。該算法充分挖掘正常數(shù)據(jù)與異常數(shù)據(jù)結(jié)構(gòu)上的差異，首先標記部分正例樣本，通過圖模型刻畫數(shù)據(jù)的內(nèi)蘊結(jié)構(gòu)，利用標簽傳遞的思想，提出了標簽置信度的概念，并巧妙地將正常數(shù)據(jù)和異常數(shù)據(jù)結(jié)構(gòu)上的差異轉(zhuǎn)化為穩(wěn)定狀態(tài)下標簽置信度的差異；然后通過多重標記過程來避免算法標記樣本出現(xiàn)的誤差；最后，基于正例樣本的標簽置信度的統(tǒng)計特性分析，實現(xiàn)對測試樣本的異常性判決。在人工合成數(shù)據(jù)集和真實數(shù)據(jù)集上的實驗，驗證了本文算法的有效性。