唐 瀛 閆仁武

（江蘇科技大學(xué)計算機(jī)學(xué)院 鎮(zhèn)江 212028）

1 引言

在1995 年時Vapnik 和Cortes 領(lǐng)導(dǎo)的AT&Bell實(shí)驗(yàn)室［1］正式提出了支持向量機(jī)（SVM）算法［2］。支持向量機(jī)在對數(shù)據(jù)進(jìn)行分類時通過結(jié)構(gòu)風(fēng)險最小化原則尋找超平面從而進(jìn)行分類，并且它能夠?qū)⒌途S的不可分特征向量通過使用核函數(shù)映射，從而轉(zhuǎn)換到高維特征空間，進(jìn)而進(jìn)行分類，這樣在實(shí)際的機(jī)器學(xué)習(xí)問題中能夠得到應(yīng)用［3］。由于SVM 算法在訓(xùn)練樣本的訓(xùn)練階段進(jìn)行超平面劃分過程中會出現(xiàn)設(shè)置不準(zhǔn)確的情況，本文提出使用基于密度的裁剪方法對訓(xùn)練樣本進(jìn)行裁剪，去除樣本集的噪聲和冗余樣本，優(yōu)化分類超平面的劃分。因?yàn)閼土P因子C 和核函數(shù)g對于分類性能影響較大［4］，提出基于粒子群算法對SVM算法進(jìn)行改進(jìn)，通過粒子群算法優(yōu)化懲罰因子C和核參數(shù)g，提高SVM分類準(zhǔn)確率。

2 支持向量機(jī)（SVM）算法

支持向量機(jī)實(shí)質(zhì)是一種分類算法，能夠解決在樣本集中兩類樣本分類問題，通過尋找一個最優(yōu)超平面使得對兩類樣本的分割間隔達(dá)到最大，從而將樣本集按照規(guī)則進(jìn)行分類。

1）線性可分支持向量機(jī)原理

假設(shè)訓(xùn)練樣本集為（xi，yi）（i=1，2…,m），其中xi?Rn為輸入變量，yi是對應(yīng)的預(yù)期值，m 是樣本的數(shù)量，在線性回歸［5～6］的情況下，利用SVM構(gòu)造一個目標(biāo)函數(shù)，可獲得最優(yōu)分割超平面的函數(shù)為

式中：ω?Rn為權(quán)值矢量，b ?R 為偏差量，對于需要分類的兩類樣本來說，它們之間的距離為此時為了使分類效果最優(yōu)，則需要讓兩類樣本距離最大，所以相當(dāng)于求||ω||的最小值。那么求權(quán)值ω和偏差b就可以通過下面的求解最優(yōu)問題來解決：

引入拉格朗日［7］公式，然后再根據(jù)轉(zhuǎn)換后的問題求解，從而獲取最優(yōu)解：

在式（4）中取得最優(yōu)解后，于是將a的最優(yōu)解設(shè)為a*，把最優(yōu)解a*代入下列公式，并求出關(guān)于分類面的分類器閾值b*以及全系數(shù)向量ω*：

對于取得的值b*和ω*，將其代入下列公式當(dāng)中，形成分類決策的超平面形式化方程：

再通過將樣本轉(zhuǎn)化的數(shù)據(jù)代入最后的方程中進(jìn)行分類，得到分類結(jié)果。

2）線性不可分支持向量機(jī)原理

在目前日常生活中我們遇到的問題很多都是線性不可分問題，在線性不可分的情況下，使用SVM 算法進(jìn)行分類時會通過引入一個松弛變量δi，然后在松弛變量前加入一個懲罰系數(shù)C，通過將懲罰系數(shù)C 的變化來控制分類錯誤的數(shù)量，然后通過下面的求解最優(yōu)問題來解決：

式中：C 為懲罰因子，δi為松弛變量，當(dāng)C 取值大時表示對分類的懲罰力度大。使用拉格朗日函數(shù)和核函數(shù)后可獲得線性回歸函數(shù)：

式中：αi為拉格朗日參數(shù)，K(xi,yi)為核函數(shù)。

本文采用高斯核函數(shù)來映射數(shù)據(jù)并求取最優(yōu)分類面，高斯核函數(shù)的計算公式為

3 改進(jìn)支持向量機(jī)算法

3.1 基于密度的訓(xùn)練樣本裁剪方法算法原理

為了衡量樣本分類密度，實(shí)現(xiàn)對于訓(xùn)練樣本的裁剪，接下來給出關(guān)于裁剪算法的相關(guān)定義：

定義1設(shè)樣本集中樣本X 與樣本Y 之間的距離為Dis（tX，Y），定義X的ε鄰域?yàn)?/p>

定義2設(shè)定樣本集M=C1∪C2∪C3∪C4∪…Cm（i=1，2…,m）代表一個樣本類別，且Ci∩Cj=?（i，j=1，2…,m），對于任意的X?Ci，若X 的ε鄰域內(nèi)任何樣本都屬于Ci，則X 在類內(nèi)區(qū)域，否則，X 在類邊界區(qū)域。

定義3給定樣本閾值Minpts（Minpts>0，Minpts?Z），那么對于任意的樣本X，若X 的ε鄰域中存在的樣本數(shù)|Nε(X)|>Minpts時，則X 處于高密度區(qū)域，若X 的ε鄰域中存在的樣本數(shù)|Nε(X)|=Minpts時，則X 處于均勻密度區(qū)域，若X 的ε鄰域中存在的樣本數(shù)|Nε(X)|

定義4給定鄰域半徑ε和樣本閾值Minpts（Minpts>0，Minpts?Z）。對于任意的樣本X 和X 鄰域內(nèi)的樣本Y，若|Nε(Y)|>Minpts，則Y處于高密度區(qū)域，且Y 與X 高密度可達(dá)；此時把所有高密度可達(dá)的樣本Y 的樣本集定義為RH（X），同理把所有均勻密度可達(dá)的樣本Y 的樣本集定義為RA（X），把所有低密度可達(dá)的樣本Y的樣本集定義為RL（X）。

基于密度的訓(xùn)練樣本裁剪方法［8］原理如下：

1）類邊界區(qū)域樣本裁剪如圖1所示：

圖1 類邊界樣本裁剪示意圖

設(shè)定Minpts=4，在圖中三個圓形分別是對于樣本A、B、C鄰域ε的區(qū)域，圖中分為兩種類別的樣本1 和樣本2，此時樣本B 處于類邊界區(qū)域，且樣本B的ε鄰域內(nèi)樣本數(shù)量超過Minpts，是一個高密度區(qū)域樣本，所以會對樣本B 進(jìn)行裁剪，根據(jù)上述定義，樣本A 則會被裁減掉，且位于樣本B 的ε鄰域中的其他三個類別樣本為1 的樣本，而樣本C 的ε鄰域中的樣本數(shù)量沒有超過Minpts，則不會對其鄰域進(jìn)行裁剪，在裁剪后，樣本B 會處于均勻密度區(qū)域，同時能夠降低類別樣本1對測試樣本X（未知類別）的干擾，提高準(zhǔn)確率。

2）在對于類內(nèi)區(qū)域樣本進(jìn)行裁剪時，則會裁減掉更多的冗余樣本，此時需要設(shè)置一個最少樣本閾值lowpts（lowpts>0，lowpts ?Z），且lowpts ≤Minpts，如果類內(nèi)樣本X的鄰域內(nèi)樣本數(shù)量|Nε(X)|>lowpts，將與X 高密度可達(dá)的樣本進(jìn)行裁剪，直到|Nε(X)|=lowpts 時停止；當(dāng)|Nε(X)|≤lowpts時，則將X 的ε鄰域內(nèi)所有訓(xùn)練樣本進(jìn)行保留。

基于密度的訓(xùn)練樣本裁剪方法具體算法如下：

第一步我們首先需要把樣本集X 中處于類內(nèi)區(qū)域且鄰域半徑ε中樣本數(shù)量少于Minpts 的低密度區(qū)域樣本添加到我們新建的樣本集W中，然后對樣本集X 進(jìn)行篩選，若樣本集中X［i］的鄰域半徑ε內(nèi)樣本數(shù)量小于Minpts，則保留。

通過這樣處理之后就能得到低密度區(qū)域的樣本集W和高密度樣本集WH，接下來進(jìn)行第二步：

在第二步中我們首先一次遍歷樣本X，對每個樣本X［i］獲取它的鄰域半徑內(nèi)樣本集，此樣本集會包含|Nε(X)|>lowpts 的樣本，然后將這個樣本集與低密度樣本集Z 取差值，并添加到樣本集Y 中，因?yàn)槊看伪闅v都會去除樣本集Y 中低密度樣本，只有高密度樣本，而且排除了|Nε(X)|lowpts 時，將與X 高密度可達(dá)的樣本進(jìn)行裁剪，直到|Nε(X)|=lowpts 時停止；當(dāng)|Nε(X)|≤lowpts時，則將X 的ε鄰域內(nèi)所有訓(xùn)練樣本進(jìn)行保留。當(dāng)RH 中的所有樣本|Nε(X)|≤lowpts時，進(jìn)行判斷結(jié)束循環(huán)，返回裁減之后的樣本集A。

3.2 基于密度裁剪算法的參數(shù)確定

在實(shí)際密度裁剪算法中的參數(shù)鄰域半徑ε、Minpts 和lowpts 的具體值會直接影響到裁剪效果，并且這幾種參數(shù)值當(dāng)中具有某種關(guān)聯(lián)，而在這三種值當(dāng)中，lowpts的值由Minpts間接決定，于是給出以下關(guān)于密度裁剪算法參數(shù)確定的定義：

定義5：給定訓(xùn)練樣本集M，把訓(xùn)練樣本集M中的樣本距離訓(xùn)練樣本集M 中的樣本X 第k 近的樣本，與樣本X 之間的距離設(shè)為Distk（X），于是當(dāng)訓(xùn)練樣本集M 的最少樣本數(shù)為Minpts時，樣本集M 的平均鄰域半徑為

通過以上定義，在對參數(shù)鄰域半徑ε、Minpts和lowpts 的進(jìn)行多次設(shè)定實(shí)驗(yàn)便能得到測試結(jié)果。從而可以得到參數(shù)設(shè)定的經(jīng)驗(yàn)值［9］，當(dāng)Minpts的值設(shè)置為訓(xùn)練樣本的平均樣本數(shù)的5%～8%，lowpts 的值設(shè)置為Minpts 的0.7～0.8 倍，此時的裁剪效果最好。

3.3 粒子群算法概述

粒子群算法［10-11］實(shí)質(zhì)是基于模擬鳥群覓食過程而提出的一種尋優(yōu)算法。研究人員Eberhart 和Kennedy 發(fā)現(xiàn)鳥群在覓食過程中如果發(fā)現(xiàn)草坪上某處有面包［12］，然后整個鳥群通過信息共享調(diào)整位置移動到面包地吃到面包。于是模擬鳥群的移動過程提出了粒子群算法，通過距離速度計算和個體鳥與群體鳥的信息共享［13］，然后找到調(diào)整整個鳥群所有鳥的位置的最優(yōu)解，不斷更新整個鳥群的位置，最終達(dá)到尋優(yōu)目標(biāo)［14］。粒子群算法選擇精度和速度優(yōu)良，在數(shù)據(jù)挖掘方向使用較多，對于算法的參數(shù)尋優(yōu)方向也有大量使用。

假設(shè)尋優(yōu)問題［15］的空間維度為N，尋優(yōu)問題的種群大小為M，組成的初始種群為Xi=｛X1，X2，…，Xm｝，則第i個粒子在某一時刻的位置和速度分別為Xi（t）=［Xi1（t），Xi2（t），…，Xin（t）］和Vi（t）=［Vi1（t），Vi2（t），…。Vin（t）］，粒子的最優(yōu)位置為pbesti（t）=［Pi1（t），Pi2（t），…。Pin（t）］，粒子的最優(yōu)位置為gbesti（t）=［Gi1（t），Gi2（t），…，Gin（t）］。在迭代過程中，粒子的個體最優(yōu)位置為

種群最優(yōu)位置為

更新公式為

式中：i?［1，m］，i?［1，n］，w為慣性權(quán)重［16］，c1和c2為加速因子，r1和r2取區(qū)間［0，1］內(nèi)的隨機(jī)數(shù)，t 為迭代數(shù)量。

粒子群算法具體流程步驟如下：

1）對數(shù)據(jù)集進(jìn)行初始化，設(shè)置數(shù)據(jù)集中樣本的位置和速度，對種群評估初始最優(yōu)位置gbest，給每個樣本設(shè)置個體最優(yōu)位置pbest作為初始值。

2）對數(shù)據(jù)集中的樣本進(jìn)行適應(yīng)度函數(shù)計算得到適應(yīng)度函數(shù)值。

3）評估數(shù)據(jù)集中的樣本，更新粒子個體的最優(yōu)位置pbest。

4）評估種群的最優(yōu)位置gbest。

5）更新樣本的速度和位置，將樣本位置移動至最優(yōu)位置pbest

6）進(jìn)行判定，如果失敗，則對所有樣本重新進(jìn)行2）到5）的操作，如果成功，則輸出種群最優(yōu)位置并結(jié)束循環(huán)。

3.4 基于密度裁剪和粒子群算法的SVM 算法實(shí)現(xiàn)

為了考察上述的兩種算法在SVM 算法中的性能，通過設(shè)定一種算法來實(shí)現(xiàn)對SVM 算法的改進(jìn)，對原始訓(xùn)練樣本集使用基于密度的裁剪方法，然后通過對裁減之后的新訓(xùn)練樣本集進(jìn)行訓(xùn)練建模并測試實(shí)驗(yàn)。本文對于SVM 算法的粒子群參數(shù)尋優(yōu)方法是將粒子群的位置變量設(shè)置為二維變量，即X1和X2，其中X1的取值范圍為（Cmin，Cmax)，X1的取值范圍為（gmin，gmax)，通過對X1和X2進(jìn)行計算來對SVM 算法參數(shù)C 和g 進(jìn)行尋優(yōu)。改進(jìn)算法具體步驟如下：

1）由于需要處理的數(shù)據(jù)，首先設(shè)定原始樣本集的數(shù)據(jù)為X=（xij）nxp，對原始訓(xùn)練樣本集進(jìn)行數(shù)據(jù)預(yù)處理，將數(shù)據(jù)各維歸一到［0，1］的范圍中，得到處理之后的數(shù)據(jù)集，便于剪裁算法進(jìn)行計算。歸一化公式如式（18）。

2）通過上述裁剪算法對處理后的數(shù)據(jù)進(jìn)行裁剪，裁減掉冗余樣本，生成新訓(xùn)練樣本集。

3）對新訓(xùn)練樣本集進(jìn)行上述粒子群算法進(jìn)行SVM 參數(shù)尋優(yōu)，運(yùn)行l(wèi)ibsvm 工具箱中的svmtrain 函數(shù)，計算適應(yīng)度值，建立優(yōu)化后訓(xùn)練模型。

4）通過svmpredict（）函數(shù)對測試數(shù)據(jù)進(jìn)行測試，得到準(zhǔn)確率。

上述基于密度裁剪和粒子群算法的SVM 算法的具體算法流程如圖2所示。

圖2 具體算法流程圖

4 算法測試和實(shí)驗(yàn)結(jié)果分析

本文實(shí)驗(yàn)是對UCI 標(biāo)準(zhǔn)數(shù)據(jù)庫中樣本集（Wdbc，Pima，Spambase，Shuttle）進(jìn)行測試，驗(yàn)證本文提出算法的有效性，而且UCI標(biāo)準(zhǔn)數(shù)據(jù)庫中的各類數(shù)據(jù)存在差異，在數(shù)據(jù)維度和數(shù)據(jù)分布情況上也皆不相同，所以可以比較客觀地驗(yàn)證本文算法的可靠性。本文將在原始數(shù)據(jù)集中取訓(xùn)練樣本集和測試樣本集比值為4∶1 進(jìn)行測試分析，具體情況如表1所示。

表1 原始實(shí)驗(yàn)數(shù)據(jù)集

采用上述提出的基于密度的裁剪方法進(jìn)行裁減，得到裁剪率等于裁減掉的樣本數(shù)量與訓(xùn)練樣本數(shù)量的比值，情況如表2所示。

表2 裁剪后實(shí)驗(yàn)數(shù)據(jù)集

可以看到數(shù)據(jù)集的訓(xùn)練樣本裁剪率在0.1～0.35 之間，在數(shù)據(jù)集維數(shù)較低時，裁剪的樣本數(shù)更高，但是在數(shù)據(jù)集維數(shù)較高時，裁剪的樣本數(shù)較低。然后對裁剪后的新訓(xùn)練樣本使用libsvm 工具箱進(jìn)行測試實(shí)驗(yàn)，得到使用基于密度裁剪和粒子群算法前后的識別準(zhǔn)確率結(jié)果如表3和圖3所示。

表3 使用算法前后準(zhǔn)確率

圖3 使用算法前后準(zhǔn)確率比較圖

對照使用基于密度裁剪和粒子群算法前后的數(shù)據(jù)，可以看出當(dāng)使用算法后，所有測試數(shù)據(jù)的預(yù)測識別準(zhǔn)確率均得到了提升，可以看到在Spambase數(shù)據(jù)集提升了11.5%的準(zhǔn)確率，而在Wdbc 數(shù)據(jù)集中也有1%的準(zhǔn)確率提升，可以說明使用基于裁剪和粒子群算法可以減少訓(xùn)練樣本的部分冗余樣本，提高分類超平面劃分的準(zhǔn)確程度，并提升SVM 算法的識別準(zhǔn)確率。

5 結(jié)語

本文介紹了SVM 算法，并對SVM 算法提出了改進(jìn)方向，為了提升算法的準(zhǔn)確率，分別使用了密度裁剪方法和粒子群尋優(yōu)方法對SVM 算法進(jìn)行研究和優(yōu)化。對密度裁剪方法在實(shí)行過程中的算法進(jìn)行了分析，分步驟的對實(shí)行過程算法進(jìn)行了實(shí)現(xiàn)，討論了各個步驟算法實(shí)現(xiàn)的含義，通過對數(shù)據(jù)樣本的測試，較為有效地減少了訓(xùn)練樣本的冗余樣本。對懲罰參數(shù)C 和核參數(shù)g 地粒子群算法進(jìn)行了研究和使用，探討研究了實(shí)現(xiàn)原理和過程。通過使用UCI 數(shù)據(jù)庫的數(shù)據(jù)集對改進(jìn)后算法進(jìn)行實(shí)驗(yàn)論證，通過結(jié)果表明確實(shí)有效地提升了SVM 算法的性能。