基于最小化界外密度的SVDD參數優化算法

王靖程，曹 暉，張彥斌，任志文

（1．西安熱工研究院有限公司，陜西西安710043；2．西安交通大學電氣工程學院，陜西西安710049）

基于最小化界外密度的SVDD參數優化算法

王靖程1，曹 暉2，張彥斌2，任志文1

（1．西安熱工研究院有限公司，陜西西安710043；2．西安交通大學電氣工程學院，陜西西安710049）

支持向量數據描述（support vector data description，SVDD）是一種具有單類數據描述能力的數據分類算法，因具有結構風險最小化的特性而受到廣泛關注。SVDD的參數優化是影響其分類效果的關鍵問題，本文通過引入樣本點的密度信息，提出了以界外密度最小化為目標的參數優化函數，避免了漏檢率的計算問題，可充分利用訓練數據的分布信息，提高數據描述能力，降低錯分率。仿真實驗和UCI標準數據庫的對比驗證表明，優化后的SVDD算法能夠有效降低漏檢率和錯分率，提高算法性能。

支持向量數據描述；參數優化；密度

0 引 言

支持向量數據描述（support vector data description，SVDD）算法是由Tax和Duin于1999年提出的一種單分類算法［1］。SVDD期望獲得最小化包含樣本數據的超球體，用以區分正常數據和異常數據。由于異常數據采集困難，單分類算法在故障診斷、圖像處理、異常檢測、醫學信號處理等多個領域有大量研究，具有廣闊的應用前景［2－4］。

眾多學者針對SVDD的性能優化提出了多種思路：文獻［5］提出通過核主成分分析（principal component analysis，PCA）將訓練數據映射為單位方差的對稱球形分布，再訓練SVDD模型提升算法性能；文獻［6］仿照支持向量機參數優化方法，通過加入或構造異常樣本數據，計算最小錯分率獲取最優參數；文獻［7］提出通過最近鄰算法增加支持向量數目，從而改善邊界形狀的算法；文獻［8］考慮了樣本點的密度信息，提出了一種基于相對密度指數加權的新距離測度，提高算法性能；文獻［9］考慮到樣本協方差矩陣的信息，提出利用馬氏距離替代歐式距離的方法；文獻［10］又進一步提出在馬氏距離的基礎上，加入模糊C均值聚類思想度量樣本點距離關系，改進SVDD性能；文獻［11］提出采用超橢球體替代超球體，以增強SVDD對不同數據分布的適應能力。上述方法通過對訓練數據的處理或距離量度的改進，提高了SVDD的分類準確率，但是對于算法中參數的選取缺少研究，算法性能難以達到最優。

SVDD中一般采用高斯核函數以滿足不同數據分布下的邊界曲線要求，因此SVDD中有兩個調節參數：懲罰參數C與核參數σ，邊界曲線的形狀同時受到兩個參數的影響。Tax等人對參數影響進行了分析，提出通過支持向量的數目近似估計虛警率，并假設懲罰參數C的影響較小，通過迭代方法優化核參數σ，按照支持向量數目百分比接近設定虛警率的目標，得到參數的最優值［1］。進一步研究表明，采用高斯核函數的SVDD算法與單類支持向量機等價，參數C的取值范圍可設為C≤（N和ν分別為樣本數和虛警率），然后通過迭代方法尋找支持向量數百分比最接近設定虛警率的σ值［12］。由于單分類問題缺乏其他類樣本數據，無法利用交叉檢驗最小化錯分率的方法優化參數，Tax又提出了一種基于模型復雜度的優化方法，通過調整參數σ控制模型復雜度的增加，從而避免邊界曲線過擬合［13］。鑒于單類支持向量機的虛警率可通過ν值設定，而采用高斯核函數的SVDD又與單類支持向量機等價，因此一些文獻采用C＝確定參數C。文獻［14］提出在設定的虛警率下，用支持向量百分比替代實際虛警率的期望值，尋找支持向量數最小的σ值。文獻［15］指出，核函數的作用是將訓練數據映射到高維空間，成為超球形分布后再構造包含目標數據的超球體，通過選取合適的核參數將使得高維空間中的數據分布更接近超球形，從而取得更好的分類效果。文獻［16］提出利用Bootstrap方法，通過最小化超球體半徑與支持向量百分比之和優化核參數。上述方法均基于C＝假設，從核參數優化的角度考慮了參數選取問題。但在SVDD算法中，訓練數據的虛警率根據支持向量的百分比確定，懲罰參數C與核參數σ都對支持向量數目有著重要影響，固定參數C的取值縮小了參數尋優的范圍，無法保證算法性能最優。

文獻［17］采用模擬退火算法優化SVDD參數。文獻［18］從理論上證明了SVDD受參數影響導致超球體半徑的不唯一性，并指出了半徑的優化區間。文獻［19］詳細描述了參數C和σ分別改變時邊界形狀和支持向量數的變化趨勢。文獻［20］提出，為了獲取參數的最優值，需通過交叉檢驗搜索不同參數對下的錯分率，從而選擇出最優參數對。文獻［21］研究了SVDD與核密度估計的關系，指出SVDD中無界支持向量是為了保證魯棒性而拒絕的假設異常樣本點，因此應盡量位于低密度區以使邊界曲線緊密包圍高密度區樣本點。

本文首先對SVDD參數調整的影響進行了分析，定義相對密度指數代表樣本點聚集程度，提出了以界外密度最小化為目標的參數優化函數，避免了漏檢率的計算問題，并通過仿真實驗和UCI數據庫對比驗證了不同參數優化方法的效果。

1 SVDD參數影響分析

由SVDD公式可知，SVDD的邊界形狀完全由αi＞0的支持向量確定，因此本文首先分析參數調節對支持向量及邊界形狀的影響，然后提出一種新的參數優化方法。

懲罰參數C能夠控制支持向量數目，從而影響算法錯分率，在不考慮核函數的情況下，當C＝時，所有樣本點

都成為支持向量，模型嚴重過擬合，無法接受任何新的數據樣本。隨著參數C的增加，更多樣本被超球體包圍，支持向量數目逐漸減少，直至C＝，達到設定的樣本拒絕率。繼續增大參數C，會使得支持向量數目持續減少至構成超球體的最小數目，C＝1時，所有訓練樣本點都在超球體內，模型嚴重欠擬合。因此C的取值范圍是

引入高斯核函數K后，核參數σ能夠改變映射到高維空間后的樣本點之間的距離，從而影響超球體的半徑和原始空間的邊界形狀。當σ非常小時，K（xi，xj）≈0，所有樣本點都成為支持向量。隨著參數σ的增加，邊界形狀變得越來越平坦，支持向量數目逐漸減少。由文獻［12］可知，當取C′＝2C／σ2時可以近似獲得與未加入核函數時相同的SVDD表達式。可以看出，新參數C′同時受到σ的影響，因此加入核參數后，參數C取值范圍也會受到σ的影響。

為了直觀描述參數對邊界形狀的影響，本文利用100個二維Banana數據樣本對SVDD模型進行訓練，參照支持向量機中的參數優化過程，參數C和σ的變化范圍分別為2－5～25和20～210，預設的樣本拒絕率為10%。圖1顯示了不同參數組合下SVDD的邊界形狀，其中同一行的子圖像具有相同的C值，而同一列的具有相同的σ值。從圖1可以看出，隨著σ的增加，邊界曲線明顯平坦，模型復雜度降低，包圍的樣本空間范圍更大。而隨著C值的增加，更多的樣本點被包圍在了邊界曲線內，支持向量的數目明顯減少。

4.3.1 選擇健薯，提早育苗。選用健康種薯，剔除病、雜、退薯塊，確保品種純度。日平均氣溫穩定在7～8 ℃開始育苗。在薯苗發芽出土階段，床土溫度控制在32～35 ℃；齊苗后夜催日煉，采苗前5～7 d進行煉苗，苗高20 cm以上時，及時采苗。

圖1 不同參數下的SVDD邊界形狀

圖2描述了不同參數組合下支持向量數目的等高線圖，支持向量的數目被標在了圖中的等高線上。由圖可見，對于確定的支持向量數，存在C和σ的最低界限值。因此對于設定的樣本拒絕率存在一個調節區間，在該區間內C和σ共同作用影響支持向量的實際數目，超過該區間后，C或σ到達最低界限值，支持向量數受參數極值影響無法達到設定的數目。從圖2中還可以看出，在滿足預設虛警率的前提下，可通過網格搜索找到多組滿足要求的參數對，在僅有單類數據的情況下如何確定尋找最優參數組的目標函數成為優化的關鍵問題。一些研究中將參數C按照期望的虛警率固定后，只調節參數σ，此種方法縮小了參數的調整范圍，只能達到局部最優。

圖2 支持向量數的等高線圖

圖3和圖4分別展示了參數C和σ對SVDD模型超球體半徑的影響。從圖3中可以看出，在確定的σ值下，參數C僅在數值較小時對超球體半徑產生影響，達到σ值對應的最小支持向量數后，半徑不再發生明顯變化，此時σ對超球體半徑的控制作用較為明顯，參數C的調整幾乎無法改變邊界形狀。當參數C確定時，σ的增加使得超球體半徑明顯減小，而且超球體半徑的大小幾乎不因C值變化而改變。由圖1結論可知，隨著σ的增大邊界形狀明顯趨于平坦，映射到高維空間的數據間距會隨之降低，造成超球體半徑的減小，但同時原始空間中的邊界曲線變得松弛，對目標數據的包圍曲線趨向于球形，無法隨數據分布的變化而貼切描述，會導致虛警率升高。因此參數優化時應盡量考慮σ值較小的參數組合，從而獲得緊湊的邊界形狀。

圖3 參數C對超球體半徑的影響

圖4 參數σ對超球體半徑的影響

2 SVDD參數優化

綜合上述分析，為了在預設的虛警率下選擇邊界描述緊湊的SVDD參數組，提高SVDD算法性能，需充分利用樣本分布信息。本文通過估計樣本點分布密度，提出了最小化界外密度的參數優化算法，尋找平均密度最小的無界支持向量，將非支持向量樣本點信息納入尋優過程，使得參數選擇中優先考慮將密度較大的樣本點包圍在超球體內，獲得包含大多數高密度樣本點的緊湊邊界。

本文首先定義相對密度指數，用以代表樣本點的聚集程度，由于該指數僅僅用來表示樣本點密度的相對大小，因此采取高斯函數獲取平滑的密度估計，按如下形式計算：

式中，d（xi，xj）為xi與xj兩點間的歐氏距離；Deni為第i個樣本點的相對密度指數，該指數是點xi與其他所有點的相對密度估計之和。從式（2）可以看出，樣本點xi與周圍樣本點距離越近，Deni數值越高，表示xi所處位置相對其他樣本點的密度越高。由于通過支持向量數估計的虛警率并不連續，具有跳躍性，在支持向量數無法滿足預設的虛警率時，本文定義了容許值ε＝max（1，0．1νN），ν和N分別為預設虛警率和樣本數，則優化參數的目標函數為

步驟1 采集訓練樣本，設定樣本拒絕率ν；

步驟3 按照網格搜索法，計算當前參數組合下的SVDD模型，并由式估算虛警率；

步驟4 若虛警率滿足式（3）中的條件，則進入下一步計算，否則執行步驟6；

步驟5 記錄無界支持向量的平均相對密度指數和當前的參數組合，繼續下一步；

步驟6 按照設定步長改變參數值，返回步驟3繼續運算，若參數搜索完畢，則結束搜索過程；

步驟7 根據所得結果分析步長是否合適，若需調整步長則返回步驟2；

步驟8 在滿足式（3）條件的參數組合里，選擇平均相對密度指數最小的一組參數組合為最優參數組，若有多對參數組合的平均相對密度指數是相同的最小值，則選取σ最小的一組為最優參數組。

3 仿真實驗及結果分析

為了驗證參數優化方法的有效性，本文分別利用人工數據集和UCI數據庫進行了對比驗證。人工數據集采用二維Banana型分布數據，通過不同算法選擇最優參數，比較了在同一樣本拒絕率下不同優化方法得到的SVDD模型邊界形狀。UCI數據作為機器學習領域算法測試的標準平臺，常被用來比較不同優化算法的虛警率和漏檢率，本文選擇UCI數據庫中的Iris、Wine、Sonar和Breast Cancer Wisconsin數據集進行測試，將一類數據作為目標數據，其他類數據作為異常數據，采用10次獨立循環的10折交叉檢驗算法計算分類效果。本文采用的SVDD參數優化對比算法分別是：利用確定參數C值，再通過搜索σ尋找最接近ν時的σ值，獲得最優參數的方法（OS－VDD）；利用網格搜索計算參數C和σ不同組合下的計算虛警率，因此3個SVDD模型的支持向量數近似相同，分別為12、10和10，3種方法得到的優化參數組分別為OSVDD（C＝0．1，σ＝6．498 0）、CSVDD（C＝0．287 2，σ＝4．287 1）、DSVDD（C＝0．176 8，σ＝5．278 0）。由圖可見，OSVDD方法因參數C值較小，需增大σ值才能使支持向量數接近預設的虛警率，但σ值過大造成邊界曲線平坦，形狀趨向于球形邊界，使得Banana型數據中間凹陷部分也被SVDD邊界包圍，增大了將其他類數據識別為同類數據的可能性。CSVDD方法明顯加強了描述邊界的緊湊性，邊界曲線隨訓練樣本的分布變化而改變，在中間凹陷部分有效貼近數據，獲得了接近香蕉形狀的邊界曲線，但左側邊界值，將最接近ν時的參數組挑選出來，選擇σ最小的參數優化方法（CSVDD）；以及本文提出的最小化界外密度方法（DSVDD）。

將OSVDD、CSVDD、DSVDD 3種方法分別應用于具有100個樣本的二維Banana型分布數據上，設定ν＝0．1，所得邊界形狀如圖5所示。由于3種參數優化方法都按照曲線所包圍面積較大。DSVDD方法加入了樣本點密度信息，避免了選取中間凹陷部分密度較大的點作為支持向量，使得邊界曲線沒有過分向中間凹陷，保持了兩端邊界的適度描述，與其他兩種方法相比，DSVDD的邊界形狀最為貼近香蕉型分布，各部分描述恰當，按DSVDD優化所得的參數組是網格搜索中較為合適的一組。

圖5 不同參數優化方法對邊界形狀的影響

為了進一步驗證參數優化方法對SVDD模型邊界及分類效果的影響，本文選擇了4組UCI數據檢驗3種參數優化方法的錯分率（錯分樣本占總樣本數的比例）、虛警率（目標樣本被拒絕的比例）及漏檢率（非目標樣本被接受的比例）。4組UCI數據樣本的信息可見表1。

將3種參數優化方法應用于UCI數據，所有訓練模型均采用10%的樣本拒絕率，將數據中的一類作為目標類，其余作為非目標類，僅用目標類數據訓練SVDD所得結果如表2所示。表中結果為10次獨立循環結果的平均值，括號內的數據則是10次獨立循環結果的標準差，每次獨立循環內都要進行10折交叉檢驗，其均值作為一次獨立循環的最終值。

表2 不同優化方法下的UCI數據檢驗結果

從表2可見，Iris數據中OSVDD的錯分率較高，盡管在訓練時OSVDD選擇了最接近樣本拒絕率的σ值，但參數C的固定限制了優化區間，使得另外兩種參數優化方法均取得了優于OSVDD的分類效果。從虛警率和漏檢率上可以更清楚地發現，OSVDD的C值無法調整使得虛警率較高，從而造成了其較差的分類效果。CSVDD降低了虛警率，DSVDD則更進一步壓縮邊界包圍中樣本聚集密度較低的區域，使得模型邊界優先包圍高密度區域，從而能夠更好地發揮SVDD數據描述能力，在保持漏檢率基本相同的情況下，DSVDD比CSVDD進一步降低了虛警率。Wine數據中，3種方法的錯分率相差較小，但OSVDD的C值固定使得訓練時樣本拒絕率高于預設值，從而造成虛警率過高和漏檢率下降，CSVDD和DSVDD的虛警率都在預設值附近，所以漏檢率和錯分率反而有所增加。但SVDD訓練時需首先保證虛警率滿足要求，在此基礎上盡量降低漏檢率和錯分率，因此OSVDD的結果并不是最優的。DSVDD在第1類和第2類目標樣本中，都有效降低了漏檢率，使得錯分率低于CSVDD，但在第3類目標樣本中略高于CSVDD，表明此時的優化空間有限，原始空間中其他類樣本與目標樣本較為貼近，使得邊界曲線的調整對漏檢率影響較大。Sonar數據中的第1類目標數據和Wine數據情況類似，都是虛警率過高而漏檢率較低，使得錯分率下降。從第2類目標數據中可以看出，CSVDD和DSVDD的網格搜索擴大了參數優化區間，能夠在滿足樣本拒絕率要求的前提下，盡量降低錯分率。但數據維數較高，目標類數據和其他類數據比較貼近，也使得DSVDD的描述效果與CSVDD近似相同。在Breast Cancer Wisconsin的第1類目標數據中，OSVDD由于較高的虛警率而使得錯分率較低，CSVDD獲得了滿足要求的虛警率，但參數組并不合適使得漏檢率較高，DSVDD優化調整了參數組，在與CSVDD近似的虛警率時，獲得了較低的漏檢率，使得分類性能提高。在Breast Cancer Wisconsin的第2類目標數據中，CSVDD和DSVDD均能進一步優化參數組合，調整邊界形狀，從而獲得了比OSVDD更低的漏檢率和錯分率。

4組數據的仿真結果表明，本文所提的基于最小化界外密度的參數優化算法能夠挖掘樣本數據信息，在預設虛警率下獲得較低的漏檢率和錯分率，有效提高SVDD分類性能。

4 結 論

本文針對SVDD參數優化問題進行了研究，深入分析SVDD參數變化對模型邊界的影響，在此基礎上提出相對密度指數代表樣本點的聚集程度，按照模型邊界曲線盡量包圍高密度區樣本點的原則，提出最小化界外密度函數進行參數尋優，并通過仿真實驗對比不同參數優化方法對SVDD分類結果的影響。結果表明，本文提出的參數優化方法能夠有效降低SVDD的漏檢率和錯分率，提高SVDD模型的可靠性。

［1］Tax D M J，Duin R P W．Support vector domain description［J］．Pattern Recognition Letters，1999，20（11／13）：1191－1199．

［2］Xie Y X，Chen X G，Yu X M，et al．Fast SVDD－based Outlier detection approach in wireless sensor networks［J］．Chinese Journal of Scientific Instrument，2011，32（1）：46－51．（謝迎新，陳祥光，余向明，等．基于快速SVDD的無線傳感器網絡Outlier檢測［J］．儀器儀表學報，2011，32（1）：46－51．）

［3］Shin J H，Lee B，Park K S．Detection of abnormal living patterns for elderly living alone using support vector data description［J］．IEEE Trans．on Information Technology in Biomedicine，2011，15（3）：438－448．

［4］Xie L，Liu X Q，Zhang J M，et al．Non－Gaussian process monitoring based on NGPP－SVDD［J］．Acta Automatic Sinica，2009，35（1）：107－112．（謝磊，劉雪芹，張建明，等．基于NGPPSVDD的非高斯過程監控及其應用研究［J］．自動化學報，2009，35（1）：107－112．）

［5］Tax D M J，Juszczak P．Kernel whitening for one－class classification［J］．International Journal of Pattern Recognition and Artificial Intelligence，2003，17（3）：333－347．

［6］Tao X M，Liu F R，Zhou T X．A novel approach to intrusion detection based on support vector data description［C］∥Proc．of the Industrial Electronics Society，2004：2016－2021．

［7］Guo S M，Chen L C，Tsai J S H．A boundary method for outlier detection based on support vector domain description［J］．Pattern Recognition，2009，42（1）：77－83．

［8］Lee K，Kim D W，Lee D，et al．Improving support vector data description using local density degree［J］．Pattern Recognition，2005，38（10）：1768－1771．

［9］Wei X K，Huang G B，Li Y H．Mahalanobis ellipsoidal learning machine for one class classification［C］∥Proc．of the 6th International Conference on Machine Learning and Cybernetics，2007：3528－3533．

［10］Zhang Y，Xie F D，Huang D，et al．Support vector classifier based on fuzzy c－means and Mahalanobis distance［J］．Journal of Intelligent Information Systems，2010，35（2）：333－345．

［11］GhasemiGol M，Monsefi R，Yazdi H S．Intrusion detection by new data description method［C］∥Proc．of the UKSim／AMSS First International Conference on Intelligent Systems，2010：1－55．

［12］Tax D M J，Duin R P W．Support vector data description［J］．Machine Learning，2004，54（1）：45－66．

［13］Tax D M J，Muller K R．A consistency－based model selection for one－class classification［C］∥Proc．of the 17th International Conference on Pattern Recognition，2004：363－366．

［14］Banerjee A，Burlina P，Diehl C．A support vector method for anomaly detection in hyperspectral imagery［J］．IEEE Trans．on Geoscience and Remote Sensing，2006，44（8）：2282－2291．

［15］Zhao F，Zhang J Y，Liu J．An optimizing kernel algorithm for improving the performance of support vector domain description［J］．Acta Automatic Sinica，2008，34（9）：1122－1127．（趙峰，張軍英，劉敬．一種改善支撐向量域描述性能的核優化算法［J］．自動化學報，2008，34（9）：1122－1127．）

［16］Brereton R G，Lloyd G R．Support vector machines for classification and regression［J］．Analyst，2010，135（2）：230－267．

［17］Xing H J，Zhao H X．Feature extraction and parameter selection of SVDD using simulated annealing approach［J］．Computer Science，2013，40（1）：302－305．（邢紅杰，趙浩鑫．基于模擬退火的SVDD特征提取和參數選擇［J］．計算機科學，2013，40（1）：302－305．）

［18］Wang X M，Chung F L，Wang S T．Theoretical analysis for solution of support vector data description［J］．Neural Networks，2011，24（4）：360－369．

［19］Brereton R G．One－class classifiers［J］．Journal of Chemometrics，2011，25（5）：225－246．

［20］Wang C K，Ting Y，Liu Y H，et al．A novel approach to generate artificial outliers for support vector data description［C］∥Proc．of the IEEE International Symposium on Industrial Electronics，2009：2168－2173．［21］Chen B，Li B，Feng A，et al．Essential relationship between domain－based one－class classifiers and density estimation［J］．Transactions of Nanjing University of Aeronautics ＆Astronautics，2008，25（4）：275－281．

E－mail：wangjingcheng＠tpri．com．cn

曹 暉（1978－），男，副教授，博士，主要研究方向為工業智能控制、數據挖掘技術。

E－mail：huicao＠mail．xjtu．edu．cn

張彥斌（1952－），男，教授，主要研究方向為工業智能控制、信息融合。

E－mail：ybzhang＠mail．xjtu．edu．cn

任志文（1962－），男，教授級高級工程師，主要研究方向為工業自動化。

E－mail：renzhiwen＠tpri．com．cn

Parameter optimization algorithm of SVDD based on minimizing the density outside

WANG Jing－cheng1，CAO Hui2，ZHANG Yan－bin2，REN Zhi－wen1
（1．Xi’an Thermal Power Research Institute Limited Liability Company，Xi’an 710043，China；2．School of Electrical Engineering，Xi’an Jiaotong University，Xi’an 710049，China）

Support vector data description（SVDD）is a data classification algorithm of one－class data description，which has the minimum structure risk and attracts much attention recently．The SVDD performance of classification results is determined by the parameter optimization．As the sample point density is defined，a parameter optimization function based on minimizing the density outside is proposed．The proposed algorithm can avoid the calculation of miss detection rate during the optimization，and make full use of sample data distribution information to improve the SVDD performance．Compared with the UCI database，the simulation results confirm that the parameter optimization algorithm can reduce the miss detection rate and miss classification rate effectively．

support vector data description（SVDD）；parameter optimization；density

TP 391

A

10．3969／j．issn．1001－506X．2015．06．33

王靖程（1982－），男，工程師，博士，主要研究方向為模式識別。

1001－506X（2015）06－1446－06

2014－06－13；

2014－10－22；網絡優先出版日期：2014－11－20。

網絡優先出版地址：http：／／www．cnki．net／kcms／detail／11．2422．TN．20141120．1831．005．html

國家自然科學基金（61375055）；新世紀優秀人才支持計劃（NCET－12－0447）；陜西省自然科學基金（2014JQ8365）；華能集團科技項目（HNKJ13－H20－04）資助課題