一種SVDD增量學習淘汰算法

孔祥鑫，周 煒，王曉丹，于明秋

空軍工程大學 防空反導學院，西安 710051

1 引言

支持向量數據描述[1]（SVDD）是Tax和Duin等人提出的一種單分類算法。它使用同類樣本數據建立一個最小超球體的數學模型，用來實現對原樣本的描述和新樣本的分類[2-4]。然而，在大多數情況下，難以在訓練初期就獲得某類樣本完備的訓練數據集，即訓練樣本是不斷加入的。為滿足準確率的要求，通常將新增樣本加入原樣本中一起進行訓練并更新分類模型。SVDD構造超球體的實質[5]是求解一個二次規劃問題，隨著時間的累積，當樣本量增大到一定程度時，會導致訓練時間過長甚至無法進行。增量學習思想[6]不同于上文提到的整體塊學習思想，它希望在模型更新時，僅保留歷史模型中的有用信息，同時對新知識進行篩選，去除其中的冗余信息，從而提高模型的訓練效率。

基于這一思想，許多學者進行了SVDD增量學習算法的研究。在已有研究中，文獻[7]使用原樣本集中的支持向量（Support Vector，SV）與增量樣本中違反Karush-Kuhn-Tucker（KKT）條件的樣本進行訓練，但該算法無法控制增量學習過程中支持向量數量增加對模型更新時間的影響；文獻[8]提出一種基于提升思想的SVDD增量學習方法，不斷將誤判樣本提升為訓練樣本并更新分類器，直到分類效果滿足某一閾值，但該算法可能會因更新次數過多而影響模型構建的效率，同時對于閾值如何設定，沒有給出明確說明；文獻[9]多次利用KKT條件對樣本進行篩選，利用得到的少量樣本進行訓練，提升了模型的訓練效率，但該方法實現增量的過程缺乏理論依據；文獻[10]提出一種定向蠶食快速增量SVDD算法，使得增量SVDD的增長步長大于1，但是該方法依賴于初始訓練集的選擇，若選擇不恰當，則會導致模型訓練效率和分類精度大大降低。

本文提出了一種新的SVDD增量學習淘汰算法（NISVDD）。該算法在增量學習過程中考慮到了原樣本中的非SV樣本，以及滿足KKT條件的增量樣本中與原超球分類面距離較近的樣本。通過設置自適應閾值并采用一種樣本淘汰機制，充分挖掘含有重要分類信息的樣本并及時淘汰對新模型構建影響不大的樣本。實驗結果表明，NISVDD算法在提升訓練效率的同時，能夠確保模型具有很高的分類精度。

2 SVDD相關理論

2.1 SVDD算法

SVDD算法對同類樣本集合X={ }x1,x2,…,xN，先進行非線性映射Φ(xi)，把xi映射到高維特征空間。然后，在特征空間中構造出一個包含訓練樣本的最小超球體。

對該問題描述如下：

其中O為球心；r為超球體半徑；ζi和C分別是松弛變量和懲罰系數。

利用Lagrange乘子法構造Lagrange方程：

其中，ai≥0,μi≥0為Lagrange乘子。對式（2）中各變量求偏導，并令偏導數為0，將得到的結果代入式（2），可得到式（2）的對偶問題為：

解該優化問題可得到ai，其中使得0

對待測樣本Z，若滿足式（5）條件，則被判為目標類，否則被判為非目標類：

2.2 Karush-Kuhn-Tucher（KKT）條件

由SVDD算法描述可以看出，構造超球的實質是求解一個二次優化問題，只有當所有的xi均滿足下面的KKT條件時，[ ]α1,α2,…,αn才是規劃問題的最優解。

其中，di2表示樣本xi到球心距離的平方。在SVDD分類中，對應αi=0的樣本位于超球內（含超球邊界）；對應0<αi

3 SVDD增量理論分析

構建的SVDD模型由作為支持向量的樣本決定，即支持向量集可以充分描述整個目標樣本集的特征。基于此原理，當增量樣本加入原樣本后，使用可能成為新模型支持向量的樣本集代替整個樣本集進行訓練，就能在保證分類精度的同時縮減訓練時間。當已有的SVDD模型中加入新增樣本時，會對應以下兩類情況：

（1）新增樣本均滿足原樣本集的KKT條件，即新增樣本均位于原超球內。此時，SVDD對合并后的樣本集進行優化與對原樣本集進行優化是等價的，新模型與原模型保持一致。

（2）新增樣本集中存在違反原樣本集KKT條件的樣本，即新增樣本中有部分樣本位于原超球外。此時，原模型中樣本間的平衡關系被打破，SVDD對合并后的樣本集進行優化所得到的超球模型相比原模型會發生變形。常規增量算法（簡稱ISVDD算法）的做法是：僅保留原模型中的支持向量，將其與增量樣本中違反KKT條件的樣本一起訓練，得到新的模型。

為研究在第二種情況下，原樣本與新增樣本中支持向量的具體變化情況，本文在MATLAB7.10編譯平臺上使用PR_tools工具箱并調用gendatb（）函數生成兩組Banana型數據集，分別包含40個和20個樣本點。其中，40個樣本點的數據集作為原樣本集，另一組作為增量樣本集。

首先，使用SVDD對原樣本集構造數據描述，結果如圖1。將新增樣本加入原樣本集，可以看出，新增樣本中存在違反原樣本集KKT條件的樣本。

圖1 對原樣本集構造數據描述

然后，使用SVDD對包含60個樣本的總樣本集構造數據描述，結果如圖2。

圖2 對增量后的總樣本集構造數據描述

可以看出，增量樣本中違反KKT條件的樣本成為了新的支持向量，大部分原支持向量也成為了新模型的支持向量。同時發現，若增量樣本中存在違反原樣本集KKT條件的樣本，那么原樣本集中靠近模型邊界的非支持向量可能會成為新的支持向量，例如樣本x1；增量樣本集中靠近模型邊界且符合原樣本集KKT條件的樣本也有可能轉化為新的支持向量，例如樣本y1。因此，ISVDD算法將這兩類數據樣本在SVDD增量學習過程中直接舍棄顯然是不合適的，這會導致分類精度的降低。

4 一種新的SVDD增量學習淘汰算法（NISVDD）

4.1 自適應學習閾值

為了從原模型的邊界附近篩選出可能成為新模型支持向量的樣本，定義自適應學習閾值α：

其中，r表示原模型的超球半徑；ε為調節因子，可以表示為：

其中，xi是增量樣本，函數 f(xi)返回增量樣本xi到當前球心的距離；m是增量樣本總數；count是計數函數，返回集合內的元素數量。ε的值等于增量樣本中符合原模型KKT條件的樣本數占增量樣本總數的比例，反映了當前模型對該目標類樣本描述的完備程度。

當加入增量樣本后，計算得到閾值α，從原模型的非支持向量中篩選出距離球心大于閾值α的樣本；同時，符合原樣本KKT條件的增量樣本，若其與球心的距離大于α，也會被篩選出來。這些篩選出的樣本將組成新集合，與原模型的支持向量和違反原樣本KKT條件的增量樣本一起參與增量學習。

可以看出，閾值α的取值滿足0≤α≤r，且閾值α具有自適應性：每次增量學習時計算得到一個對應的ε，ε值越小則表示當前模型越不完備，新模型與原模型相比將會發生較大變化，那么原模型邊界附近的非支持向量和符合KKT條件的增量樣本轉化為新模型支持向量的可能性增大，此時閾值α隨ε減小，能篩選出更多樣本參與增量學習，有利于充分挖掘有用信息；反之，較大的ε值反映出模型在當前階段對該目標類樣本的描述較完備，那么原模型邊界附近的非支持向量和符合KKT條件的增量樣本轉化為新模型支持向量的可能性變小，此時閾值α隨ε增大，減少篩選出的樣本數量，能有效避免對冗余樣本的學習。特別的，當增量樣本均符合原樣本KKT條件時，閾值α=r，沒有樣本被篩選出來參與增量訓練，新模型將與原模型保持一致。

4.2 樣本淘汰機制

隨著增量學習次數的增加，整個樣本集的規模不斷擴大，模型邊界附近的樣本點也會越來越多。如果不對歷史樣本進行有選擇的淘汰，那么隨著增量學習的進行，通過閾值篩選出的樣本將會非常多，從而嚴重影響增量學習的效率。

通過研究，發現如下規律：若某樣本在多次增量學習得到的模型中，都是作為不影響邊界形狀的非支持向量，那么該樣本在之后的學習中繼續成為非支持向量的概率非常高。若及時將這類對后續學習影響較小的樣本淘汰，就能提高增量學習的效率。基于此，提出一種樣本淘汰機制：

首先，設定閾值η（η是正整數），對每個樣本均設置一個計數器θ，初始化令θ均為0。在每次增量訓練完成之后，對所有樣本的θ值進行如下操作：如果該樣本是模型的支持向量，則將其θ置0；反之，如果該樣本是模型的非支持向量或未參與本次訓練，則令其θ加1。在下一次增量訓練之前，將滿足θ＞η對應的樣本淘汰。

閾值η的選取沒有唯一的標準，對于不同類型的目標樣本，最佳的閾值η可能會不同。一般而言，當閾值η取值過大時，會保留大量的冗余數據，從而導致訓練時間過長，達不到樣本淘汰機制提高增量學習效率的目的；當閾值η取值過小時，會舍棄大量的有用信息，從而導致新模型的分類精度不高，無法體現出本文算法提升模型分類精度的優勢。大量不同類型數據集上的實驗結果表明，當閾值η在1～4范圍內選取時，增量算法同時具有較快的訓練速度和較高的模型分類精度。

4.3 NISVDD算法描述

綜合以上思想，提出一種新的SVDD增量學習淘汰算法，其具體算法描述如下：

輸入：原樣本集X0及各樣本的θ值，原SVDD模型Ω0，新增樣本集X1，閾值η。

輸出：增量學習后的模型Ω。

步驟1X0中支持向量樣本組成集合SV0，剩余樣本組成集合NSV0。

步驟2將SV0中所有樣本的θ置0，同時令NSV0中所有樣本的θ值加1。

步驟3檢驗X1中是否存在違反KKT條件的樣本，若無，則輸出Ω0，算法結束；否則，X1被分為違反Ω0的KKT條件的樣本集X1v和符合Ω0的KKT條件的樣本集X1s。

步驟4計算ε和α，根據樣本淘汰機制，淘汰掉NSV0中θ＞η的樣本，將剩余樣本組成集合NSV0′，從NSV0′和X1s中篩選出到球心距離大于閾值α的樣本，放入樣本集Xm。

步驟5將X1v,SV0和Xm合并，訓練得到分類模型Ω 。將 NSV0′,X1v,X1s,SV0合并為樣本集 X0，作為后續增量學習的原樣本集。

5 實驗分析

為驗證本文提出的NISVDD算法的性能，將NISVDD算法與標準SVDD算法和常規增量算法（ISVDD）進行比較，所有實驗在Intel?CoreTMi7-4790 CPU@3.60GHz，Windows 7機器上完成，編譯平臺為MATLAB7.10，實驗數據分別采用UCI數據集和彈頭目標HRRP數據集。

5.1 UCI數據集

本文所選UCI數據集為breast-cancer數據集，該數據集來自美國Wisconsin州醫學院記錄的關于乳腺癌的真實臨床數據。該數據集共包含699條維度為11的數據，第1列是病人ID，第2列是分類標識（2表示良性，共458條；4表示惡性，共241條），其余9列是判斷乳腺癌的9個屬性。

圖3給出了標準SVDD、ISVDD和NISVDD(η=1)對增量數據的訓練時間。可以看出，NISVDD算法的訓練時間接近ISVDD，但遠小于標準SVDD算法。主要原因是：標準SVDD算法在每次增量學習時必須要對新增樣本和所有歷史樣本全部重新訓練，沒能提取有效的歷史信息，大量的重復訓練導致其訓練時間過長；ISVDD只保留前一次學習得到的支持向量樣本與增量樣本合并進行訓練，因此訓練時間最短；本文提出的NISVDD算法參考前幾次的學習結果，可以對歷史樣本進行有選擇的保留和淘汰，因此訓練時間也較短。

圖3 breast-cancer數據集的訓練時間

圖4 給出了 η分別取1，2，3，4時，NISVDD算法對增量數據的訓練時間。可以看出，當η取值增大時，NISVDD的訓練時間也隨之增加，但均小于標準SVDD算法。主要原因是：η是控制樣本淘汰的速度的一個參數，η的增大使得樣本淘汰的速度和數量下降，從而使訓練時間增加。

圖4 η不同取值時的訓練時間

在上述增量訓練過程中，用剩余的158條良性數據作為測試樣本集，分別檢驗增量學習各階段所得模型的分類性能。

圖5給出了3種算法的分類精度，可以看出，3種算法在訓練初期的分類精度相近，但隨著增量學習過程的深入，標準SVDD算法和NISVDD算法的分類精度均逐漸增高且兩者分類精度相差較小；而ISVDD算法分類精度增加的幅度較小，甚至不隨新樣本的加入而增大，其分類精度在增量學習后期明顯小于其他兩種算法。主要原因是：ISVDD算法在增量學習中過多追求樣本量的縮減從而導致大量對模型構造有用的樣本被舍棄，使其分類精度下降；而NISVDD算法在進行樣本縮減的同時，采取了必要機制防止包含有用信息樣本的丟失，因此其具備和標準SVDD算法相近的分類精度。

圖5 不同算法對breast-cancer數據集的分類精度

圖6 給出了 η分別取1，2，3，4時，NISVDD算法的分類精度。可以看出，不同取值對應的分類精度在增量學習各階段的變化趨勢相近，當取較大值時，分類精度會有所增加。主要原因是：η的增大使得樣本淘汰的標準更加嚴格，可能包含有用信息的樣本被保留的時間更長，分類精度也隨之增大。

圖6 η不同值對breast-cancer數據集的分類精度

從以上實驗結果可以看出，應用NISVDD算法進行增量學習時，在提升訓練效率方面具有和ISVDD相近的優勢，并且能夠保持和標準SVDD相近的高分類精度。增大閾值η可以獲得更高的分類精度，但會降低訓練速度；減小閾值η可以提升模型的構建效率，但會損失分類精度。

結合圖4和圖6可以看出，與η=1相比，η=2時模型的分類精度提升很明顯，但兩者的訓練速度接近；與η=3、η=4相比，η=2在分類精度方面的損失非常小，但在訓練速度上卻明顯占優。因此，對于breast-cancer數據集，當閾值取η=2時，NISVDD算法可以很好地平衡分類精度與訓練效率，使增量學習的整體效果達到最優。

5.2 彈頭仿真HRRP數據

當雷達距離分辨單元遠小于目標的徑向尺寸時，目標會連續占據多個距離單元，從而在雷達視線投影上形成目標幅度的圖像，稱為目標高分辨一維距離像（High Range Resolution Profile，HRRP）[12]。實驗使用 FEKO電磁計算軟件生成彈頭目標的HRRP數據[13]。設置雷達入射波方位角范圍為0°～180°，間隔為0.05°，雷達帶寬為1GHz，頻率范圍為8.5～9.5 GHz，頻點數為128，頻率步進7.874 MHz。得到彈頭目標的全方位樣本集包含3 600個數據，在實驗中選擇每15°作為一個實驗范圍，則該角域包含300個樣本，選擇其中180個樣本作為整個訓練樣本集，剩下的120個樣本作為測試樣本集。提取HRRP樣本的幅度譜差分特征[14]、能量聚集區長度特征[15]，采用PCA算法對幅度譜差分特征進行降維，得到5維的特征數據，把其與能量聚集區長度特征進行組合得到6維的彈頭目標HRRP樣本特征數據。

為模擬雷達持續獲取彈頭目標信息的情形，將訓練樣本集劃分為8個樣本子集，其中第一個子集包含40個樣本，作為雷達t0時刻錄入的初始樣本集；其余7個子集均包含20個樣本，分別在t1～t7時刻依次錄入。不斷更新訓練模型并測試分類精度，具體參數設置方法與5.1節中實驗相同。

圖7為標準SVDD、ISVDD和NISVDD(η=1)對彈頭目標HRRP樣本進行增量學習過程中的訓練時間，圖8為 η分別取1，2，3，4時，NISVDD算法對增量數據的訓練時間，圖9為幾種算法在各時刻所得模型的分類精度，圖10為 η 分別取1，2，3，4時，NISVDD算法的分類精度。

圖7 彈頭目標HRRP數據的訓練時間

可以看出，幾種算法在彈頭目標HRRP數據上的實驗結果與在breast-cancer數據集上的實驗結果大體一致。不同之處在于，當閾值取η=3時，與η=1、η=2相比，能夠在訓練時間增加較少的同時使模型的分類精度明顯提升；與η=4相比，兩者的分類精度相近，但η=3時的訓練速度更快。因此，當閾值取η=3時，NISVDD算法在彈頭目標HRRP數據上的整體性能最佳，不僅能夠隨著彈頭目標HRRP數據的不斷獲取快速更新分類模型，而且能夠保證較高的分類精度，符合彈頭目標識別所需的快速性、準確性的要求。

圖8 η不同取值時的訓練時間

圖9 不同算法對彈頭目標HRRP數據的分類精度

圖10 η不同值對彈頭目標HRRP數據的分類精度

6 結束語

本文提出了一種新的SVDD增量學習淘汰算法，通過定義自適應學習閾值篩選出潛在的支持向量，提高了增量學習的精度；通過一種樣本淘汰機制及時淘汰包含冗余信息的樣本，提升了模型的訓練效率。在UCI數據集上的實驗結果證明了本文方法的正確性與有效性。同時，本文方法對彈頭目標HRRP數據也表現出很好的適用性，這有利于將NISVDD算法應用于彈頭目標在線識別領域。對于NISVDD算法的后續改進，可以進一步研究如何根據已有的樣本信息，在增量學習之前確定出可能的最佳淘汰閾值η，從而進一步提高SVDD增量學習的整體性能。