分布熵懲罰的支持向量數(shù)據(jù)描述

胡天杰，胡文軍，王士同

（1.湖州師范學院信息工程學院，浙江湖州 313000；2.江南大學人工智能與計算機學院，江蘇無錫 214122）

0 引言

異常檢測的目標是從正常樣本中訓練得到一個分類模型，進而對未知樣本進行檢測和識別，目前許多學者在訓練樣本中加入少量異常樣本提升了異常檢測的準確率，如帶異常樣本的支持向量數(shù)據(jù)描述（Support Vector Data Description，SVDD）［1］和深度神經網絡（Deep Neural Network，DNN）［2］等。在實際生活的各領域中，如故障診斷［3］、網絡入侵檢測［4］、醫(yī)療圖像診斷［5］、視頻異常檢測［6］和信用卡欺詐行為識別［7］等，獲取正常樣本較為容易，而獲取異常樣本需要花費很高的代價，因此異常檢測方法得到了廣泛使用。目前異常檢測的建模方法較多，比如基于統(tǒng)計學習的方法［8］、基于神經網絡方法［9］和基于密度估計方法［10］等。

Tax等［11］在2004年提出了SVDD方法，目標是在特征空間中找到一個能夠包含所有或大多數(shù)正常樣本的最小超球，作為一種典型的數(shù)據(jù)描述方法，在異常檢測領域受到了廣泛關注［12］。之后，很多學者對它進行了進一步的研究，并針對不同的問題提出了SVDD的改進方法，如為了增大超球體邊界與異常樣本之間的間隔，Wu等［13］在2009年提出了小球體大間隔（Small Sphere and Large Margin，SSLM）的支持向量數(shù)據(jù)描述方法。針對多分布數(shù)據(jù)，文獻［14-15］中提出了多球支持向量數(shù)據(jù)描述（Multi-Sphere SVDD，MS-SVDD）方法。楊小明等［16］從數(shù)據(jù)的幾何結構出發(fā)，綜合數(shù)據(jù)全局和局部幾何結構信息，在2015年提出了局部分塊的支持向量數(shù)據(jù)描述（SVDD based on Local Patch，OCSVDDLP），該方法通過局部分塊和局部樣本重構捕捉數(shù)據(jù)的局部結構信息。此外，為了提高SVDD的決策速度，胡文軍等在2011年提出了快速決策的SVDD方法（Fast Decision Approach of SVDD，F(xiàn)DA-SVDD）［17］，該方法利用超球體球心原像將SVDD的決策復雜度降至O(1)。上述方法在建模時，都使用了相同的懲罰參數(shù)對所有松弛變量進行懲罰，即每個松弛變量的懲罰度一樣，當選擇不同懲罰參數(shù)時得到不同的訓練模型，因此上述方法對懲罰參數(shù)過于敏感。為此，Wang等［18］在2013年提出了位置正則的支持向量數(shù)據(jù)描述（Position regularized SVDD，P-SVDD），該方法利用映射后特征空間中的樣本點與均值點的歐氏距離設計不同的權重，以對相應松弛變量進行不同的懲罰。另外，Cha等［19］在數(shù)據(jù)原始空間中，基于數(shù)據(jù)分布為每個樣本點設計一種密度，并將此密度作為對應松弛變量的懲罰參數(shù)，提出了密度權的支持向量數(shù)據(jù)描述（Density Weighted SVDD，DWSVDD）。

如前所述，SVDD對懲罰參數(shù)相當敏感，其本質是懲罰參數(shù)直接影響到支持向量，而支持向量又決定著超球的球心和半徑。雖然P-SVDD和DW-SVDD從不同角度設計了每個松弛變量的懲罰參數(shù)，也獲得了一定效果，但這兩種方法都僅使用了正常樣本，無法適應包含少量異常樣本的場景。在包含異常樣本的場景下，SVDD中訓練樣本的數(shù)據(jù)分布勢必會變得更加復雜，一般地，在異常檢測任務中，獲取正常樣本容易而獲取異常樣本困難，正常樣本在數(shù)量上遠遠多于異常樣本，且正常樣本來自同一正常模式，數(shù)據(jù)分布單一，而異常樣本通常來自不同的異常模式，數(shù)據(jù)分布較為復雜，因此，正常樣本的分布對整體數(shù)據(jù)結構起決定性作用。為了避免少量異常樣本復雜的數(shù)據(jù)分布對SVDD建模的影響，本文將從高斯核空間中正常樣本的全局分布出發(fā)，提出一種距離度量，并基于此距離度量設計一種概率以評估樣本正常或異常的可能性，最后利用此概率構造基于分布熵的懲罰度對樣本進行懲罰，提出了一種分布熵懲罰的支持向量數(shù)據(jù)描述（Distribution Entropy Penalized SVDD，DEP-SVDD）異常檢測方法。該方法針對包含少量異常樣本的場景，在訓練樣本中加入了正常樣本和少量的異常樣本，并利用核空間中各個樣本點到正常樣本的全局分布中心之間的距離和熵的概念對各個樣本點實施不同的懲罰，降低了樣本在分類時的不確定度。

1 支持向量數(shù)據(jù)描述

1.1 高斯核空間

給定數(shù)據(jù)集：X={xi∈Rd|i=1，2，…，n}。其中，前m個樣本是正常樣本，即標簽yi=1(1≤i≤m)，其他樣本是異常樣本，即標簽yj=-1(m+1≤j≤n)。一般地，數(shù)據(jù)是線性不可分的，為了解決此問題，常用方法是通過一個非線性映射函數(shù)將原始空間非線性映射至高維特征空間F，即?：x→?(x)。同時，利用一個核函數(shù)計算特征空間中的內積，即k(xi，xj)=?(xi)T?(xj)，其中k(xi，xj)是某個核函數(shù)，常用核函數(shù)包括線性核、多項式核和高斯核［20］等。因高斯核能更好地捕捉數(shù)據(jù)的結構信息，故其最為常用，定義如下：

圖1 高斯核空間的幾何含義Fig.1 Geometric interpretation of Gaussian kernel space

1.2 傳統(tǒng)SVDD

SVDD的目標是構造一個包含所有或大部分正常樣本的最小超球，位于球面及球內的樣本為正常樣本，位于球外的樣本為異常樣本。其原始問題的數(shù)學模型為：

其中：R和a分別是超球的半徑和球心，C1和C2是懲罰參數(shù)，ξ=(ξ1，ξ2，…，ξn)T是引入的松弛變量，當正常樣本位于球外時，ξi>0，否則ξi=0；當異常樣本位于球內時，ξj>0，否則ξj=0。利用拉格朗日技巧可得上述問題的對偶形式：

其中α=(α1，α2，…，αn)T是拉格朗日乘子。顯然，式（3）是一個含等式和不等式約束的二次規(guī)劃（Quadratic Programming，QP）問題。根據(jù)KKT（Karush-Kuhn-Tucker）條件可得如下結論：

結論1 對于正常樣本，1）αi=0對應的樣本?(xi)位于超球內；2）0<αi

結論2 對于異常樣本，1）αj=0對應的樣本?(xj)位于超球外；2）0<αj

其中，?(xk)為位于超球面上任意一個樣本點。對于未知樣本x∈Rd，可通過如下函數(shù)進行決策：

當f(x)≤0時，x為正常樣本，否則為異常樣本。

2 分布熵懲罰的SVDD

2.1 距離度量

圖2 高斯核空間中的距離度量Fig.2 Distancemeasure in Gaussian kernel space

2.2 基于熵的懲罰度

比較樣本點與近鄰樣本或樣本類中心之間的距離，也是異常檢測的方法之一［22］。從樣本分布結構來看，若樣本點距離某類樣本越近，則其屬于該類樣本的可能性越大，故距離可以評價樣本點隸屬的可能性。下面基于距離定義兩種概率。

1）正常樣本的異常概率。

2）異常樣本的正常概率。

在信息論領域中，熵是樣本所攜帶信息的度量，可對信息的不確定度進行評價［24］，其定義如下：

設一個離散隨機變量A={a1，a2，…，an}服從概率分布p(a)，則信息熵定義為：

根據(jù)式（7）或（8）的概率pi與式（9）為各個樣本點設計信息熵：

考慮到式（10）中的熵由數(shù)據(jù)的全局分布信息計算而來，因此本文將其稱為分布熵。由式（10）可知，樣本點屬于正?；虍惓５母怕蕄i越大，對應的分布熵呈現(xiàn)先增大后減小的趨勢，這與正常樣本和異常樣本在分類時的不確定度趨勢是一致的。

2.3 DEP-SVDD

為解決SVDD中懲罰參數(shù)固定不變的問題，在目標函數(shù)中對松弛變量加權是一種有效的辦法，將式（10）中每個樣本點的懲罰度Wi應用至SVDD中，得到DEP-SVDD原始問題的數(shù)學模型：

需要注意的是，熵一般作為模型中獨立的一項進行優(yōu)化，對一個動態(tài)系統(tǒng)進行不確定性的度量，而本文在參數(shù)確定之后，模型系統(tǒng)是靜態(tài)的。因此，本文借用熵的概念對松弛變量進行加權去修正SVDD的懲罰參數(shù)，如式（11）所示。

引入拉格朗日乘子構造如下拉格朗日函數(shù)：

其中，α=(α1，α2，…，αn)T≥0，β=(β1，β2，…，βn)T≥0是拉格朗日乘子。式（12）對原始變量R和ξi、ξj求偏導并置為0，對α求偏導并置為0，得：

根據(jù)α≥0，β≥0和式（15）、（16），可得0≤αi≤C1Wi，0≤αj≤C2Wj。將式（13）～（16）代入式（12）得到原始問題的對偶形式：

顯然，式（17）是一個二次規(guī)劃（QP）問題，根據(jù)KKT（Karush-Kuhn-Tucker）條件可得如下結論：

結論3 對于正常樣本，1）αi=0對應的樣本?(xi)位于超球內；2）0<αi

結論4 對于異常樣本，1）αj=0對應的樣本?(xj)位于超球外；2）0<αj

利用超球面上的任意一個樣本點和球心式（14）可計算超球的半徑，其表達式和式（4）相同，對于未知樣本x∈Rd，可通過式（5）進行決策。

2.4 算法實現(xiàn)

DEP-SVDD算法的實現(xiàn)步驟如下：

輸入：數(shù)據(jù)集X={xi∈Rd|i=1，2，…，n}，高斯核帶寬參數(shù)σ和懲罰參數(shù)C1、C2。

輸出 對于未知樣本x，根據(jù)式（5）進行決策，當f(x)≤0時，x為正常樣本；否則為異常樣本。

步驟1 利用式（6）計算各個樣本點到全局分布中心的距離di；

步驟2 利用式（7）計算正常樣本屬于異常樣本的概率pi，或利用式（8）計算異常樣本屬于正常樣本的概率pi；步驟3 利用式（10）計算各個樣本點的懲罰度Wi；步驟4 求解式（17）的二次規(guī)劃問題。

2.5 時間復雜度分析

DEP-SVDD計算的時間復雜度主要包括兩部分：第一部分是利用各個樣本點到數(shù)據(jù)的全局分布中心的距離計算每個樣本的懲罰度（步驟1～3），根據(jù)式（6）可知步驟1計算距離的時間復雜度為O(mn)，得到該距離后，利用式（7）、（8）和（10）為n個樣本分別計算其屬于正?；虍惓颖镜母怕屎蛻土P度（步驟2和3），時間復雜度都為O(n)。第二部分是求解式（17）的二次規(guī)劃問題（步驟4），時間復雜度為O(n3)［25］。綜上，DEP-SVDD的訓練過程的時間復雜度為O(n3+mn+2n)，SVDD雖然少了算法步驟1～3，但仍需進行二次規(guī)劃問題的求解，時間復雜度為O(n3)，因此DEP-SVDD算法會略慢于SVDD。在對未知樣本進行決策時，因DEP-SVDD和SVDD都使用式（5）作為決策函數(shù)，故它們的復雜度一樣，均為O(n)［17］1086。

3 實驗與分析

3.1 數(shù)據(jù)集與幾何精度

實驗環(huán)境：CPU Intel Core i7-4712MQ 2.30 GHz，12 GB RAM，64位Windows 10，Matlab R2017b。

利用幾種廣泛使用的異常檢測數(shù)據(jù)集將DEP-SVDD與SVDD、DW-SVDD、P-SVDD、K最近鄰（K-Nearest Neighbor，KNN）［26］和孤立森林（isolation Forest，iForest）［27］進行分類精確度的比較，如表1所示，其中E.p和G.h分別對應Ecoli periplasm和Glass headlamps數(shù)據(jù)集，具體信息可參考http：//homepage.tudelft.nl/n9d04/occ/index.htm l和http：//archive.ics.uci.edu/m l/datasets.php。

表1 實驗數(shù)據(jù)集描述Tab.1 Description of experimental datasets

3.2 實驗結果及分析

在實驗中，首先對所有樣本的特征進行歸一化到［-1，1］的處理，然后從正常樣本中隨機抽取70%的樣本，從異常樣本中隨機抽取若干樣本使得其占訓練樣本的20%，剩下的樣本用作測試樣本。所有算法都使用高斯核函數(shù)進行實驗，帶寬參數(shù)σ從{2n s}中選擇，其中n={-6，-5，…，6}，s是所有訓練樣本2范數(shù)均值的平方根［28］；由于DW-SVDD和DEPSVDD皆利用權值對懲罰參數(shù)進行了修正，而該權值的范圍在0～1，因此懲罰參數(shù)設置的范圍應大于1，故將從{0.3，0.5，0.7，0.9，1.1，1.3，1.5，1.7，1.9}中選擇懲罰參數(shù)，由于傳統(tǒng)SVDD中的懲罰參數(shù)必須小于等于1，因此對于SVDD，該網格1.1及之后的值都置為1；另外，DW-SVDD和KNN需要尋找數(shù)據(jù)的K最近鄰，參數(shù)K從{3，5，7，9}中選擇；孤立森林方法中，孤立樹的數(shù)量設置為100，子采樣大小設置為256［27］418。

首先分別驗證懲罰參數(shù)C1和C2對DEP-SVDD算法的影響，設置懲罰參數(shù)為1.3，高斯核帶寬參數(shù)σ為2-2s，結果如圖3和圖4所示。

圖3 懲罰參數(shù)C1對算法的影響Fig.3 Influenceof penalty parameter C1 on algorithm

圖4 懲罰參數(shù)C2對算法的影響Fig.4 Influenceof penalty parameter C2 on algorithm

從圖3可以看出：懲罰參數(shù)C1的取值小于等于0.7時，DEP-SVDD算法對C1較為敏感，大部分數(shù)據(jù)集的分類精度波動都較為明顯，其中，在Biomed healthy數(shù)據(jù)集上達到了30%；在C1的取值大于0.7時，DEP-SVDD的分類精度趨于平穩(wěn)，除Glass headlamps數(shù)據(jù)集外，對其他數(shù)據(jù)集的分類精度波動都在6%以內。從圖4可以看出，除Biomed healthy數(shù)據(jù)集外，其余數(shù)據(jù)集的分類精度較為平穩(wěn)，DEP-SVDD算法對懲罰參數(shù)C2的取值相對不敏感。

然后對所有數(shù)據(jù)集進行10次獨立重復的實驗并取均值和標準差進行比較，結果如表2所示。表2顯示了DEP-SVDD與傳統(tǒng)SVDD、解決懲罰參數(shù)敏感問題的DW-SVDD和PSVDD以及基于近鄰的KNN和基于集成學習的孤立森林異常檢測方法的幾何精度對比。一方面，從表2中的幾何精度可以看出，本文提出的DEP-SVDD對上述數(shù)據(jù)集的分類精度大多都達到了83%以上。其中，在Iris setosa數(shù)據(jù)集中KNN的分類精度最高，達到了100%；在Biomed healthy和E.p數(shù)據(jù)集中iForest方法的分類精度最高且明顯高于其他方法，分別達到了98.03%和95.55%；在其余數(shù)據(jù)集中DEP-SVDD算法都取得了最好的效果。除此之外，DEP-SVDD在絕大多數(shù)數(shù)據(jù)集上的表現(xiàn)都要優(yōu)于SVDD以及同樣解決懲罰參數(shù)敏感問題的DW-SVDD和P-SVDD。另一方面，從表2中的標準差可以看出，iForest方法的穩(wěn)定性明顯高于其他方法，而除iForest之外的異常檢測方法的穩(wěn)定性都較為接近。綜上所述，本文提出的DEP-SVDD在一定程度上提高了異常檢測的準確率，這是因為DEP-SVDD利用正常樣本作為數(shù)據(jù)的全局分布，并在特征空間中構建了能更準確描述樣本間分布結構信息的距離度量，基于該距離度量設計了評估各個樣本點屬于正常或異常樣本的概率，最后利用此概率構造基于分布熵的懲罰度對各個樣本點實施不同的懲罰，解決了SVDD對懲罰參數(shù)過于敏感的問題。

表2 不同算法的幾何精度 單位：%Tab.2 Geometric precisionsof different algorithms unit：%

4 結語

針對SVDD對懲罰參數(shù)過于敏感的問題，本文提出了分布熵懲罰的支持向量數(shù)據(jù)描述方法（DEP-SVDD）。該方法將訓練樣本映射至高斯核誘導的特征空間，構建核空間中各個樣本點到正常樣本全局分布中心之間的距離度量來評估各個樣本點屬于正?；虍惓颖镜母怕?，并利用此概率構造基于分布熵的懲罰度對各個樣本點實施不同的懲罰。相較于SVDD，所提方法使用了更多的信息，并最小化樣本分類時的不確定度，提升了算法的分類精確度，最后的實驗結果表明提出的DEP-SVDD是一種有效的異常檢測方法。但本文僅討論了數(shù)據(jù)的全局分布，沒有考慮數(shù)據(jù)的局部信息對算法的影響，并且只考慮了高斯核函數(shù)的使用，并沒有研究其他核函數(shù)在參數(shù)條件合適的情況下的使用，這都將是下一步的重點研究方向。