陳宇晨，何毅斌，戴喬森，劉 湘

(武漢工程大學(xué) 機電工程學(xué)院，湖北 武漢 430205)

0 引 言

標(biāo)注出正常數(shù)據(jù)中的異常數(shù)據(jù)的問題稱為異常檢測[1]，通常檢測任務(wù)中只有一類樣本充分采集，而另一類欠采樣[2-4]，目前處理這一類特殊問題最常用的方法為基于數(shù)據(jù)描述的方法[5]?；跀?shù)據(jù)描述的方法主要指支持向量數(shù)據(jù)描述法及在其基礎(chǔ)上改進和補充的方法，這些改進和補充的方法包括：利用現(xiàn)代優(yōu)化方法對懲罰項系數(shù)和核寬度參數(shù)優(yōu)化[6,7]，對核方法采用擴展策略[8]以及組合多種核方法[9,10]，使用其它距離表示方式代替歐式距離[11,12]等，然而這些方法無論怎樣改進和補充，均無法改變其本質(zhì)是通過在高維空間中訓(xùn)練一個超球體支撐域來描述數(shù)據(jù)，若訓(xùn)練樣本在線性空間中極度不符合超球體時，將會產(chǎn)生較大分類誤差。

為了給數(shù)據(jù)描述類方法提供另一種支撐域形狀，在訓(xùn)練樣本不適合使用支持向量數(shù)據(jù)描述方法時有更多的方法選擇，本文提出一種基于核主成分分析超多面體數(shù)據(jù)描述的方法，該方法首先使用核方法對訓(xùn)練樣本進行非線性映射，再利用非線性映射后樣本的主成分信息構(gòu)造超多面體分類器，解決了主成分分析僅能對數(shù)據(jù)線性表示的局限，實現(xiàn)對樣本的異常檢測。與支持向量數(shù)據(jù)描述法相比，超多面體具有更多的訓(xùn)練參數(shù)，在某些分布下，超多面體比超球體支撐域的描述更加符合訓(xùn)練樣本。

1 多面體數(shù)據(jù)描述模型建立

1.1 問題描述及模型評價方法

異常檢測問題往往可以得到大量的正常數(shù)據(jù)，異常數(shù)據(jù)出現(xiàn)的概率非常低，然而異常數(shù)據(jù)一旦產(chǎn)生，且未被正確識別將會造成很大的不良影響[13,14]。通常對未標(biāo)記錯誤的數(shù)據(jù)進行監(jiān)督學(xué)習(xí)會產(chǎn)生不錯的模型，但數(shù)據(jù)中若混有錯誤標(biāo)記的數(shù)據(jù)往往降低模型精度，因此本文主要對擁有標(biāo)記樣本以及標(biāo)記樣本中混有異常數(shù)據(jù)的情況建模，即對樣本進行監(jiān)督學(xué)習(xí)。

由于樣本的不平衡性，以準(zhǔn)確率作為評價標(biāo)準(zhǔn)的方法并不適用此類問題，對于這類問題需要同時考慮第一種誤差和第二種誤差。預(yù)測結(jié)果和真實結(jié)果的混淆矩陣見表1。

表1 混淆矩陣

定義精確率為P、召回率為R計算公式分別如下所示

(1)

F1分數(shù)定義為準(zhǔn)確率與召回率的加權(quán)平均

(2)

精確率P代表正確被檢索的占所有實際被檢索到的比例，召回率R代表正確被檢索的占所有應(yīng)該檢索到的比例，F(xiàn)1分數(shù)為兩者的調(diào)和平均數(shù)，F(xiàn)1分數(shù)越大，表示分類正確的數(shù)量越多，當(dāng)F1分數(shù)為1時，表示分類完全正確[15]。

1.2 多面體數(shù)據(jù)描述模型建立

N維空間中的一組數(shù)據(jù)可以由y1…y2N，共2N個超平面形成的超多面體支撐域完全包圍，其中

(3)

式中：wi——超平面的法向量，bi——超平面的常數(shù)項。

每個yi可視為一個線性分類器，且總存在兩個不同的超平面擁有相同的法向量wi，分別將其稱為下界分類器與上界分類器，對于新的樣本點xi，若其屬于正常類，應(yīng)滿足

(4)

二維空間中一組樣本的平行四邊形支撐域如圖1所示。

圖1 二維空間四邊形支撐域

圖1中y2、y4為下界分類器，y1、y3為上界分類器，4個分類器組合成為一個平行四邊形，當(dāng)新的樣本點xi落在四邊形內(nèi)部時則判定其為正常樣本，反之則為異常樣本。

對高維空間每個下界分類器ym，若已知法向量wm，bm的值可以通過以下約束優(yōu)化問題求解

(5)

式中：xi——某個樣本點，εi——松弛變量，C——自定義量。

與ym對應(yīng)的上界分類器yn，其法向量與上界分類器的wm相同，常數(shù)項bn的值可以通過以下約束優(yōu)化問題求解

(6)

由于無法保證用于訓(xùn)練模型的數(shù)據(jù)全為正常樣本，為減少異常樣本的影響可以調(diào)整式(5)、式(6)中εi以及C的值。

調(diào)整C的值對分類器的影響如圖2所示。

圖2 調(diào)整參數(shù)C的影響

圖2為組一維數(shù)據(jù)，數(shù)據(jù)多集中在中央，中間的密度很大，向兩側(cè)密度逐漸降低，密度很低的點為異常樣本的可能性大，通過逐漸減小C，越來越多的低密度點被排除，即起到了排除訓(xùn)練數(shù)據(jù)中異常樣本的作用。

若認為用于模型訓(xùn)練的樣本中有較多異常樣本，可將C設(shè)定較小，反之則給C較大的值。

2 主成分分析及模型簡化

對法向量wi的選擇直接影響模型，本文使用主成分分析方法計算法向量wi，主成分分析法主要用于提取數(shù)據(jù)的主要特征，利用數(shù)據(jù)協(xié)方差矩陣的特征向量作為法向量wi，wi包含了數(shù)據(jù)間的相關(guān)信息，利用此作為法向量，得到的超多面體恰好符合數(shù)據(jù)各個方向的變化趨勢。

2.1 主成分分析

主成分分析的主要思想是將空間中一組具有相關(guān)性的數(shù)據(jù)，使用其協(xié)方差矩陣的特征向量組成的基，表示原數(shù)據(jù)的坐標(biāo)，消除數(shù)據(jù)間的相關(guān)性，也可將數(shù)據(jù)投影到部分特征向量組成的子空間中，實現(xiàn)數(shù)據(jù)的降維[16]。

主成分分析方法可以通過下面的步驟實現(xiàn)：

(1)計算數(shù)據(jù)每個特征的平均值μ=(μ1…μn)；

(2)利用平均值μ計算數(shù)據(jù)的協(xié)方差矩陣

(7)

(3)對協(xié)方差矩陣進行特征值分解

∑=QΛQ′

(8)

其中，Q為特征向量組成的矩陣，Λ為特征值組成的對角矩陣；

(4)數(shù)據(jù)投影到N個特征向量構(gòu)建的子空間

Xnew=QX

(9)

2.2 模型簡化

假設(shè)特征向量組成的矩陣為：Q=(Q1,…,Qn)，分別利用Qi作為模型的法向量wi，將空間中所有的數(shù)據(jù)投影到以Qi為基的一維子空間中，此時所有的數(shù)據(jù)退化為標(biāo)量，訓(xùn)練的參數(shù)為超平面的平移量b′m，對下界分類器，b′m的值可以通過以下約束優(yōu)化問題求解

stxi+εi>b′m

εi≥0

(10)

對應(yīng)上界分類器平移量b′n通過以下約束優(yōu)化問題求解

stxi-εi

εi≥0

(11)

上式與式(5)、式(6)相比，約束優(yōu)化問題的求解難度降低。

二維空間一組數(shù)據(jù)，協(xié)方差矩陣特征向量為Q=(Q1,Q2)，數(shù)據(jù)向每個特征向量的投影及支撐域如圖3所示。

圖3 主成分方法訓(xùn)練支撐域

圖3中，使用主成分法將數(shù)據(jù)分別投影到基為Q1和Q2的一維子空間中，并訓(xùn)練簡化后的約束優(yōu)化模型，得到的平行四邊形支持域可以很好描述原數(shù)據(jù)，表明利用主成分的方法簡化以及求解模型的有效性。

簡化后的約束優(yōu)化模型的平移量b′m、b′n與原模型的常數(shù)項bm、bn間的關(guān)系滿足

(12)

式中：Qi——模型的法向量，但是由于式中絕對值的影響，導(dǎo)致了bm、bn均會求解出雙值，為了避免在高維空間中對多個結(jié)果的討論，所以采用將新數(shù)據(jù)投影到其特征向量為基底的線性空間中判斷其是否為正常數(shù)據(jù)的策略，而不是顯式求解出2N個超平面的方程。

3 核方法下的超多面體非線性描述

3.1 主成分分析的局限性

主成分分析簡化模型求解，并計算出法向量wi，但因為其線性特性，往往無法處理非線性數(shù)據(jù)，導(dǎo)致這類數(shù)據(jù)最后得到的支撐域判決效果很差，一組以異或方式分布的數(shù)據(jù)及其向特征向量投影及支撐域如圖4所示。

圖4 非線性可分數(shù)據(jù)的支撐域

圖4中，兩種數(shù)據(jù)不可被線性分離，以一種異或狀態(tài)分布，使用主成分分析法建立平行四邊形支撐域?qū)е铝舜罅慨惓?shù)據(jù)被誤分類。

為了解決這個問題，在主成分分析的基礎(chǔ)上引入核方法，核方法以一種非線性映射的方式將數(shù)據(jù)投射到一個高維的特征空間里，不僅改變了數(shù)據(jù)的維度，而且使數(shù)據(jù)的某一特征得到保留甚至強化得到更好的分類效果[17]。

3.2 核主成分分析

設(shè)Φ(·)為向高維空間的映射，對協(xié)方差矩陣的特征分解可以表示為

(13)

式中：x——數(shù)據(jù)矩陣，μ——數(shù)據(jù)矩陣特征的均值，ωi——Φ(X)Φ(X)′的特征向量，λi——特征值。

核主成分分析的一個重要定理表明：空間中的任一向量都可以由該空間的所有數(shù)據(jù)線性表示，將特征向量ωi利用數(shù)據(jù)集合Φ(X)線性表示

ωi=Φ(X)α′

(14)

式中：α——線性組合的系數(shù)向量。

將式(14)帶入式(13)，在等號兩側(cè)同時左乘Φ(X)，得到

Φ(X)′Φ(X)Φ(X)′Φ(X)α=λiΦ(X)′Φ(X)α

(15)

式中：Φ(X)′Φ(X)用中心化的Gram矩陣Kc代替，即

(16)

由于矩陣Kc為正定對稱矩陣，所以存在逆矩陣，上式可進一步簡化為

Kcα=λiα

(17)

Kc可用Gram矩陣K表示

Kc=K-KE-EK-EKE

(18)

式中：E——所有元素均為1/n的Rn×n的矩陣。

計算Gram矩陣常用的核函數(shù)包括：線性核函數(shù)、多項式核函數(shù)、高斯核函數(shù)，其表達式分別為

(19)

式中：p、σ——核的大小，屬于自定義量。

一般情況下，高斯核是合理的首選。第一，對比線性內(nèi)核，非線性內(nèi)核映射數(shù)據(jù)進入一個更高維空間，可以處理類別標(biāo)簽和屬性之間的非線性的關(guān)系，第二，超參數(shù)的數(shù)量會影響模型選擇的復(fù)雜性，而多項式內(nèi)核的超參數(shù)多于高斯核，最后，高斯核將向量間的內(nèi)積映射到0-1之間，而多項式核可能將向量內(nèi)積映射到無窮。

(20)

將上文異或條件下的數(shù)據(jù)利用核主成分分析投影到新的二維平面上，其中核函數(shù)選擇高斯核函數(shù)，新數(shù)據(jù)的位置和訓(xùn)練的支撐域如圖5所示。

圖5 核主成分分析得到的坐標(biāo)及支撐域

利用核主成分分析將異或狀態(tài)數(shù)據(jù)中正常數(shù)據(jù)投影到不同的高維線性空間中并訓(xùn)練模型，再將異常數(shù)據(jù)帶入模型測試，其準(zhǔn)確率、精確率、召回率以及F1分數(shù)見表2。

表2 各維度下各項指標(biāo)

圖5和表2表明在高維線性空間，異或分布的數(shù)據(jù)各項指標(biāo)均值均較高，說明了核方法的有效性，將線性不可分的數(shù)據(jù)在高維空間下變的可分，訓(xùn)練出了有效的超多面體支撐域。

核主成分分析超多面體數(shù)據(jù)描述方法的步驟如圖6所示。

圖6 核主成分分析超多面體數(shù)據(jù)描述方法步驟

4 實例分析

本文采用mulcross數(shù)據(jù)集進行實驗，該數(shù)據(jù)集共有235 930組正常數(shù)據(jù)及26 214組異常數(shù)據(jù)，每個數(shù)據(jù)包括4個特征，其分布特征如圖7所示。

圖7 數(shù)據(jù)分析盒須圖

圖7表示了數(shù)據(jù)集每個特征的數(shù)據(jù)分布范圍、數(shù)據(jù)的中位數(shù)、上四分位數(shù)和下四分位數(shù)以及異常數(shù)據(jù)值。

使用matlab 2015b測試本文方法，dd_tools工具箱構(gòu)造支持向量描述方法。從數(shù)據(jù)集的正常數(shù)據(jù)中不放回抽取5000組正常數(shù)據(jù)作為訓(xùn)練集，再從剩余包含正常和異常數(shù)據(jù)的數(shù)據(jù)中抽取1000組數(shù)據(jù)作為測試集，改變空間維度，記錄空間維度數(shù)及準(zhǔn)確率、精確率、召回率、F1分數(shù)，結(jié)果見表3。

表3 本文算法各維度下分項指標(biāo)

表3表明空間維度選擇4以上時可以得到不錯的分類效果，因此本文實驗中的空間維度選擇4維。

重復(fù)上述方法抽樣5次，使用本文算法及支持向量描述方法利用同樣的數(shù)據(jù)訓(xùn)練模型、測試模型，本文算法使用粒子群算法求解約束優(yōu)化，兩種方法均選用高斯核函數(shù)，結(jié)果見表4。

表4 兩種算法分類指標(biāo)結(jié)果

表4表明在所有訓(xùn)練數(shù)據(jù)均為正常時，本文的方法與支持向量描述方法都可以得到非常好的分類效果，且精確率均為1，說明分類時沒有犯第二類錯誤，即沒有將異常數(shù)據(jù)分類為正常數(shù)據(jù)，驗證了本文方法的有效性。

當(dāng)在選擇訓(xùn)練集數(shù)據(jù)時，不放回的抽取N組異常數(shù)據(jù)以及5000-N組正常數(shù)據(jù)作為訓(xùn)練集，再從剩下的數(shù)據(jù)中抽取1000組作為測試集數(shù)據(jù)，當(dāng)N取不同值時兩種算法各項指標(biāo)結(jié)果見表5。

表5 加入異常數(shù)據(jù)后兩種算法分類指標(biāo)結(jié)果

將表5繪制為折線圖比較兩種方法，折線如圖8所示。

表5和圖8表明兩種方法的精確率均為1，分類結(jié)果均沒有發(fā)生第二類錯誤，有效防止了第二類錯誤產(chǎn)生的不良后果，本文的方法除精確率以外的各項指標(biāo)會隨著異常數(shù)據(jù)混入的越來越多而下降，但即使在數(shù)據(jù)中混入10%的異常數(shù)據(jù)，依然可以得到較好的分類結(jié)果，在數(shù)據(jù)中混入2%的異常數(shù)據(jù)時，準(zhǔn)確率依然可以達到0.945，F(xiàn)1分數(shù)達到0.9717，實驗結(jié)果上看混入異常數(shù)據(jù)的情況下本文方法各項指標(biāo)高于支持向量描述方法，驗證了本文方法的穩(wěn)定性。

圖8 兩種算法混入異常數(shù)據(jù)時各項分類指標(biāo)

為了比較本文的方法與支持向量數(shù)據(jù)描述方法的時間差異，取訓(xùn)練集的數(shù)量為1000～5000，取樣間隔為1000，記錄每次訓(xùn)練的時間，結(jié)果見表6。

表6 兩種算法時間比較/s

表6表明當(dāng)訓(xùn)練數(shù)據(jù)的數(shù)量較少時，支持向量描述方法的訓(xùn)練時間略少于本文的方法，但隨著訓(xùn)練數(shù)據(jù)的增加，支持向量描述方法需要的訓(xùn)練時間也隨之迅速增長，當(dāng)訓(xùn)練數(shù)量達到5000時，本文法的訓(xùn)練時間不到支持向量描述方法的1/10。

將該方法與支持向量描述方法應(yīng)用到ODDS數(shù)據(jù)集中的thyroid數(shù)據(jù)集(共3772組數(shù)據(jù)，數(shù)據(jù)維度為6，93組離群數(shù)據(jù))，wbc數(shù)據(jù)集(共278組數(shù)據(jù)，數(shù)據(jù)維度為30，21組離群數(shù)據(jù))、vomels數(shù)據(jù)集(共1456組數(shù)據(jù)，數(shù)據(jù)維度為12，50組離群數(shù)據(jù))、ecoli數(shù)據(jù)集(共336組數(shù)據(jù)，數(shù)據(jù)維度為7，9組離群數(shù)據(jù))中，兩種方法的各項指標(biāo)如圖9所示。

圖9 4種不同數(shù)據(jù)集兩種方法測試

圖9表明4種不同數(shù)據(jù)集測試下本文方法的效果均好于支持向量數(shù)據(jù)描述方法，利用更多的數(shù)據(jù)集再次驗證了本文方法在異常檢測中的可行性和有效性。

5 結(jié)束語

本文研究了基于核主成分分析的超多面體數(shù)據(jù)描述方法，用于解決數(shù)據(jù)中正常異常樣本分布不均勻的情況下的異常檢測問題，與支持向量數(shù)據(jù)描述方法相比較，本文方法不再局限于使用超球體對數(shù)據(jù)進行描述，而是為數(shù)據(jù)描述類的方法提供了另外的支撐域形狀。通過實驗發(fā)現(xiàn)，當(dāng)訓(xùn)練數(shù)據(jù)中的樣本量增多時，本文方法的時間復(fù)雜度并不會急劇上升，在一些數(shù)據(jù)集上可以得到比支持向量描述更好的分類效果，即使訓(xùn)練數(shù)據(jù)中混有部分異常數(shù)據(jù)時也具有一定的穩(wěn)定性。