基于Fisher向量投影的支持向量機增量算法

吳　青, 趙　祥

(西安郵電大學(xué) 自動化學(xué)院, 陜西 西安 710121)

支持向量機(support vector machines, SVM)是一種基于統(tǒng)計學(xué)習(xí)理論的機器學(xué)習(xí)方法[1-2]，其借助最優(yōu)化理論來解決機器學(xué)習(xí)問題，體現(xiàn)了統(tǒng)計學(xué)習(xí)理論中的結(jié)構(gòu)風(fēng)險最小化思想，目前已經(jīng)得到了廣泛的應(yīng)用[3-5]。支持向量(support vectors, SV)是SVM訓(xùn)練樣本中的一組特殊向量集合，這些向量通常離最優(yōu)分類面較近，對最終的分類面的確定起著決定性的作用[6]。通常情況下，SV只占訓(xùn)練集的一部分，但是在標(biāo)準(zhǔn)SVM算法的學(xué)習(xí)過程中，大量時間花費在非SV的樣本上，當(dāng)處理大規(guī)模樣本集時，算法的學(xué)習(xí)效率進一步降低，使得SVM算法在很多實際應(yīng)用問題中受到制約[7]。因此，提高算法的效率是一個很重要的研究課題。

在支持向量機的基礎(chǔ)上提出了增量學(xué)習(xí)SVM(incremental learning algorithm of SVM, ISVM)[8]算法。由于ISVM算法在處理大規(guī)模數(shù)據(jù)集以及流數(shù)據(jù)方面具有優(yōu)勢，已經(jīng)得到了廣泛的研究[9-10]。與標(biāo)準(zhǔn)SVM算法相比，其優(yōu)勢在于能夠充分利用歷史訓(xùn)練信息，無需對加入新增量后的訓(xùn)練集重新訓(xùn)練，但是其訓(xùn)練樣本中包含了很多對最終結(jié)果無用的數(shù)據(jù)，對算法的訓(xùn)練效率造成了一定的影響。為了解決上述問題，一種基于向量投影的支持向量機增量學(xué)習(xí)算法[11]被提出，該算法利用預(yù)選取訓(xùn)練樣本的方法對訓(xùn)練樣本進行預(yù)處理，有效地提高了增量算法的訓(xùn)練速度，但其選取邊界樣本的方法過于簡單，致使選取的邊界樣本的數(shù)目過多，影響了算法的性能[12]。

為了提高算法學(xué)習(xí)效率及其在處理大規(guī)模數(shù)據(jù)集和流數(shù)據(jù)方面的能力，本文擬利用基于向量投影的支持向量預(yù)選取方法[12]，將基于Fisher準(zhǔn)則的邊界向量預(yù)選取方法與增量算法相結(jié)合，提出一種基于Fisher判別向量投影的支持向量預(yù)選取增量算法(SVs pre-extracting method of ISVM based on vector projection of Fisher discriminant, FP-ISVM)，根據(jù)支持向量機中SV的幾何分布特性對樣本進行預(yù)處理，在不影響最終訓(xùn)練結(jié)果的前提下減少參與訓(xùn)練的樣本數(shù)目，再結(jié)合增量算法，充分利用歷史訓(xùn)練信息，減少重復(fù)訓(xùn)練的樣本數(shù)目，壓縮訓(xùn)練樣本集的規(guī)模，提高算法的訓(xùn)練速度。

1　支持向量預(yù)選取

1.1　支持向量機

首先考慮線性可分的情況，假設(shè)一組訓(xùn)練樣本D={(xi,yi)},i=1,2,…,l，其中，xi∈n表示第i個樣本，yi∈{-1,1}表示樣本所屬類別。訓(xùn)練的最終目的是找到一個最優(yōu)分類面，使得兩類樣本之間以最大間隔分開，使泛化誤差達到最小或者有上界[13]。這個最優(yōu)分類面即超平面。要找到這個超平面，就轉(zhuǎn)變?yōu)榍蠼庖粋€線性約束的二次規(guī)劃(quadratic programming, QP)問題。引入拉格朗日乘子α，最終轉(zhuǎn)化為求解上述規(guī)劃的對偶規(guī)劃問題[14]。

對于非線性分類情況，可通過核函數(shù)(kernel function)K(xi,xj)=φ(xi)φ(xj)將訓(xùn)練樣本從輸入空間n映射到高維特征空間，并在高維特征空間中構(gòu)造出最優(yōu)分類超平面。

1.2　支持向量預(yù)選取方法

在求解上述二次規(guī)劃的對偶問題時，系數(shù)αi對應(yīng)每一個訓(xùn)練樣本的解，在這些解中，存在許多系數(shù)αi=0，最優(yōu)分類面的確定僅依賴于對應(yīng)αi≠0的樣本點，這些樣本點被稱為支持向量[2]。通常情況下支持向量只是訓(xùn)練樣本的一部分，且正好位于兩類邊界上，如果可以通過對訓(xùn)練樣本進行預(yù)處理，篩選出那些可能成為支持向量的邊界向量，則可以有效地提高算法學(xué)習(xí)效率。

在現(xiàn)實應(yīng)用中遇到的數(shù)據(jù)通常都是高維的，不能直觀地確定數(shù)據(jù)邊界。為了更好地確定邊界向量集合，需要對原始數(shù)據(jù)降維處理，將原始樣本投影到某一直線上，然后在一維空間確定邊界向量集合。投影直線的確定，關(guān)系到邊界向量預(yù)選取的效果，直接影響算法的性能，可以根據(jù)原始數(shù)據(jù)是否線性可分選擇不同的投影直線確定方法。

1.2.1線性可分情況

采用Fisher判別法來確定線性可分情況下的最佳投影直線。根據(jù)Fisher準(zhǔn)則的基本原理[15]，找到一個最佳投影方向，使兩類樣本在該方向上投影之間的距離盡可能遠，即類間離散度最大，而每一類樣本的投影之間盡可能緊湊，即類內(nèi)離散度最小，從而使分類效果最佳。具體實現(xiàn)如下[15]。

設(shè)初始樣本分別為

兩類樣本的中心分別為

計算各樣本的類內(nèi)離散度矩陣Sg和總類內(nèi)離散度矩陣Sw:

再求出兩類樣本間的類間離散度矩陣

SB=(m1-m2)(m1-m2)T。

因為Fisher準(zhǔn)則要解決的基本問題就是找到一個最佳投影方向w，使得兩類樣本在該方向上的投影能夠盡可能的分開，以達到最好的分類效果。由Fisher準(zhǔn)則的定義可知，要想獲得最好的分類效果即要求兩類樣本間的類間離散度SB盡可能大，總類內(nèi)離散度Sw盡可能小，為此，構(gòu)造Fisher準(zhǔn)則函數(shù)

其中，wT表示w的轉(zhuǎn)置。通過求解maxJF(w)來得到最佳投影方向

1.2.2非線性可分情況

首先，定義特征空間中樣本與2個樣本中心之間的Euclidean距離，并將其求法以定理的形式給出。自中心距離指樣本與本類樣本中心向量之間的距離，互中心距離指樣本與它類樣本中心向量之間的距離，中心距離指兩類樣本中心之間的距離。

互中心距離分別為

2　基于Fisher向量投影的SVM增量學(xué)習(xí)算法

2.1　邊界向量集合的確定

2.1.1線性可分情況

已知兩類模式的初始訓(xùn)練樣本分別為

線性可分情況下確定邊界向量集合方法的具體實現(xiàn)步驟如下。

步驟1利用Fisher判別法找到最佳投影直線方向w，確定最佳投影直線；

步驟3構(gòu)造邊界向量集合。若初始訓(xùn)練樣本X=X1∪X2={x1,x2,…,xl}中對應(yīng)投影點與中點c0之間距離分別滿足不等式

2.1.2非線性可分情況

對非線性可分情況，通過φ(·)將原始樣本映射到高維特征空間，選取兩類樣本在高維特征空間中的樣本中心所在直線為最佳投影直線，將原始樣本投影到該最佳投影直線上，再根據(jù)上述定義的特征空間中樣本及樣本中心之間的相關(guān)距離篩選出所需的邊界向量。原始樣本在特征空間中的投影示意圖，如圖1所示。

圖1　原始樣本在特征空間中的投影

對第一類中投影點位于m1φ和m2φ之間的樣本，分別求出它們的投影點到m1φ的最大距離D1和最小距離D2，邊界向量確定規(guī)則如下。

(1) 若D1≤D2，則從投影點位于m1φ和m2φ之間的樣本中，選出投影點到m1φ的距離d滿足不等式

或者

的樣本作為邊界向量，其中0≤λ≤1。

(2) 若D1>D2，則分別從投影點位于m1φ和m2φ之間的兩類樣本中，選出投影點到m1φ的距離d滿足不等式

或者

的樣本作為邊界向量，其中0≤λ≤1。

2.2　算法步驟

設(shè)初始樣本集為X0，增量訓(xùn)練樣本集為X1，并且設(shè)X0∩X1=??；贔isher向量投影的SVM增量算法FP-ISVM的具體步驟如下。

步驟1對初始樣本集X0進行預(yù)處理，得到邊界向量集T0，在T0上訓(xùn)練得到分類器M0和支持向量集V0；

步驟2新增樣本X1，對這批樣本進行預(yù)處理得到相應(yīng)的邊界向量集T1，在T1上訓(xùn)練得到新的分類器M1和支持向量集V1；

步驟5重復(fù)步驟2、3、4，即可完成對多批增量樣本的處理。

3　實驗結(jié)果及分析

下面對所提出的FP-ISVM算法進行數(shù)值實驗。文中的算法均使用MATLAB R2012b軟件的編程語言實現(xiàn)，操作系統(tǒng)為Windows10 64位，實現(xiàn)的硬件條件是Intel Core i7-4790，主頻3.6 GHz，計算機的內(nèi)存是8 GB，實驗中的算法均采用高斯核函數(shù)，距離均為歐式距離。

3.1　對NDC數(shù)據(jù)集的實驗

實驗數(shù)據(jù)來自NDC(normally distributed clustered)數(shù)據(jù)集。實驗中，訓(xùn)練樣本的總個數(shù)為12 000個，把訓(xùn)練樣本分為4個部分，分別為初始訓(xùn)練樣本，增量1，增量2，增量3，對應(yīng)的樣本個數(shù)分別為4 800、3 600、2 160、1 440，測試樣本的個數(shù)為2 400。3種算法處理NDC數(shù)據(jù)集的實驗結(jié)果比較，見表1。

表1　三種算法對NDC數(shù)據(jù)集的實驗結(jié)果比較

如表1所示，在處理NDC數(shù)據(jù)集時，F(xiàn)P-ISVM算法與標(biāo)準(zhǔn)SVM相比訓(xùn)練時間縮短了94.41%，與文獻[11]中的算法相比訓(xùn)練時間縮短了64.26%。通過對樣本的預(yù)處理，F(xiàn)P-ISVM算法減少了參與訓(xùn)練的樣本數(shù)目，在數(shù)據(jù)逐批增加的過程中，利用歷史數(shù)據(jù)信息，避免對所有樣本的重復(fù)訓(xùn)練，提高了算法的學(xué)習(xí)效率。由于在數(shù)據(jù)預(yù)處理和增量學(xué)習(xí)的過程中可能會去掉少量的有效數(shù)據(jù)，所以導(dǎo)致精度略微下降。

3.2　對UCI數(shù)據(jù)集的實驗

試驗對來自標(biāo)準(zhǔn)UCI((university of California Irvine))數(shù)據(jù)庫的musk數(shù)據(jù)集進行實驗。該數(shù)據(jù)集共6 598個樣本，樣本維數(shù)166，將該數(shù)據(jù)集分成2組，一組為測試樣本集，共包含659個數(shù)據(jù)；另一組為訓(xùn)練樣本集，共包含5 939個數(shù)據(jù)，從中隨機選取2 375個數(shù)據(jù)作為初始訓(xùn)練樣本集，并將剩余的數(shù)據(jù)隨機分成3組，構(gòu)成3個增量訓(xùn)練樣本集，樣本個數(shù)分別為1 782、1 069、713。數(shù)值實驗結(jié)果如表2所示。

從表2可以看出，在實際數(shù)據(jù)集上，F(xiàn)P-ISVM算法通過對數(shù)據(jù)的預(yù)處理和增量學(xué)習(xí)算法，可以有效地壓縮訓(xùn)練樣本的規(guī)模，在精度略有降低的情況下訓(xùn)練時間大幅度地縮短，提高了訓(xùn)練速度，而且隨著訓(xùn)練樣本數(shù)目的逐漸增加，這種優(yōu)勢更加明顯。算法FP-ISVM所需時間與標(biāo)準(zhǔn)SVM相比減少了86.67%，與文獻[11]中的算法相比訓(xùn)練時間減少了33.12%，進一步體現(xiàn)了該算法在處理大規(guī)模數(shù)據(jù)集以及流數(shù)據(jù)方面的優(yōu)勢。

表2　三種算法對UCI數(shù)據(jù)集的實驗結(jié)果比較

4　結(jié)語

為了提高支持向量機在處理流數(shù)據(jù)及大規(guī)模數(shù)據(jù)集時的學(xué)習(xí)效率，提出一種新的基于Fisher判別的支持向量預(yù)選取增量算法。該算法根據(jù)支持向量機中支持向量的分布特性對初始訓(xùn)練集及增量集進行預(yù)處理，結(jié)合增量算法，充分利用歷史數(shù)據(jù)信息，減少對樣本的重復(fù)訓(xùn)練，壓縮參加訓(xùn)練的數(shù)據(jù)規(guī)模，提高訓(xùn)練速度。但是由于在數(shù)據(jù)預(yù)處理和增量學(xué)習(xí)的過程中可能會將一些有效數(shù)據(jù)剔除，導(dǎo)致精度略微有點下降。實驗結(jié)果表明，這種算法在速度上優(yōu)于標(biāo)準(zhǔn)支持向量機算法及文獻[11]中的算法，能夠提高支持向量機的學(xué)習(xí)效率，適合于樣本集規(guī)模較大的情況；另一方面，在訓(xùn)練樣本逐漸增加的情況下，該算法基于之前訓(xùn)練的結(jié)果對后繼增量進行學(xué)習(xí)，提高了處理流數(shù)據(jù)的能力。