趙 曼 趙 耀 朱振峰

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

引 言

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

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

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

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

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

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

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

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

1 標(biāo)簽傳遞模型

1.1 符號(hào)說(shuō)明

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

1.2 標(biāo)簽傳遞模型

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

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

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

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

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

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

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

2 基于標(biāo)簽傳遞的異常檢測(cè)

2.1 問(wèn)題描述

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

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

圖2 針對(duì)異常檢測(cè)的標(biāo)簽傳遞示意圖Fig.2 Outlier detection based on label propagation

2.2 異常檢測(cè)框架

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

圖3 基于標(biāo)簽傳遞的異常檢測(cè)框架Fig.3 Framework of outlier detection based on label propagation

2.3 基于多重隨機(jī)標(biāo)記的標(biāo)簽傳遞

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

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

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

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

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

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

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

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

4.1 數(shù)據(jù)集說(shuō)明及評(píng)價(jià)標(biāo)準(zhǔn)

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

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

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

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

4.1.2 評(píng)價(jià)標(biāo)準(zhǔn)

為評(píng)價(jià)異常檢測(cè)的有效性，本文采用Kubat等人提出的G-means評(píng)價(jià)指標(biāo)作為異常檢測(cè)的評(píng)價(jià)標(biāo)準(zhǔn)，其定義為

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

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

4.1.3 比較算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.2.3 參數(shù)分析

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

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

（2）標(biāo)記比例r對(duì)檢測(cè)結(jié)果的影響

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

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

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

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

5 結(jié)束語(yǔ)

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