基于核主成分分析的超多面體數(shù)據(jù)描述方法

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

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

0 引 言

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

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

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

1.1 問(wèn)題描述及模型評(píng)價(jià)方法

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

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

表1 混淆矩陣

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

(1)

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

(2)

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

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

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

(3)

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

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

(4)

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

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

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

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

(5)

式中：xi——某個(gè)樣本點(diǎn)，εi——松弛變量，C——自定義量。

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

(6)

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

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

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

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

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

2 主成分分析及模型簡(jiǎn)化

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

2.1 主成分分析

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

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

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

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

(7)

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

∑=QΛQ′

(8)

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

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

Xnew=QX

(9)

2.2 模型簡(jiǎn)化

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

stxi+εi>b′m

εi≥0

(10)

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

stxi-εi

εi≥0

(11)

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

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

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

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

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

(12)

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

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

3.1 主成分分析的局限性

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

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

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

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

3.2 核主成分分析

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

(13)

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

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

ωi=Φ(X)α′

(14)

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

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

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

(15)

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

(16)

由于矩陣Kc為正定對(duì)稱(chēng)矩陣，所以存在逆矩陣，上式可進(jìn)一步簡(jiǎn)化為

Kcα=λiα

(17)

Kc可用Gram矩陣K表示

Kc=K-KE-EK-EKE

(18)

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

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

(19)

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

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

(20)

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

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

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

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

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

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

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

4 實(shí)例分析

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

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

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

使用matlab 2015b測(cè)試本文方法，dd_tools工具箱構(gòu)造支持向量描述方法。從數(shù)據(jù)集的正常數(shù)據(jù)中不放回抽取5000組正常數(shù)據(jù)作為訓(xùn)練集，再?gòu)氖Ｓ喟：彤惓?shù)據(jù)的數(shù)據(jù)中抽取1000組數(shù)據(jù)作為測(cè)試集，改變空間維度，記錄空間維度數(shù)及準(zhǔn)確率、精確率、召回率、F1分?jǐn)?shù)，結(jié)果見(jiàn)表3。

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

表3表明空間維度選擇4以上時(shí)可以得到不錯(cuò)的分類(lèi)效果，因此本文實(shí)驗(yàn)中的空間維度選擇4維。

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

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

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

當(dāng)在選擇訓(xùn)練集數(shù)據(jù)時(shí)，不放回的抽取N組異常數(shù)據(jù)以及5000-N組正常數(shù)據(jù)作為訓(xùn)練集，再?gòu)氖Ｏ碌臄?shù)據(jù)中抽取1000組作為測(cè)試集數(shù)據(jù)，當(dāng)N取不同值時(shí)兩種算法各項(xiàng)指標(biāo)結(jié)果見(jiàn)表5。

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

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

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

圖8 兩種算法混入異常數(shù)據(jù)時(shí)各項(xiàng)分類(lèi)指標(biāo)

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

表6 兩種算法時(shí)間比較/s

表6表明當(dāng)訓(xùn)練數(shù)據(jù)的數(shù)量較少時(shí)，支持向量描述方法的訓(xùn)練時(shí)間略少于本文的方法，但隨著訓(xùn)練數(shù)據(jù)的增加，支持向量描述方法需要的訓(xùn)練時(shí)間也隨之迅速增長(zhǎng)，當(dāng)訓(xùn)練數(shù)量達(dá)到5000時(shí)，本文法的訓(xùn)練時(shí)間不到支持向量描述方法的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ù))中，兩種方法的各項(xiàng)指標(biāo)如圖9所示。

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

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

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

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