基于邊界點的支持向量機分類算法

李福祥， 王 雪， 張 馳， 周 明

(哈爾濱理工大學(xué) 理學(xué)院， 黑龍江 哈爾濱 150080)

支持向量機[1](Support Vector Machine，SVM)于20世紀90年代末由Vapnik等人提出，由于其堅實的數(shù)學(xué)理論并且具有良好的泛化能力，一經(jīng)提出就得到了廣泛的研究和應(yīng)用。支持向量機是基于統(tǒng)計學(xué)理論的一種新的機器學(xué)習(xí)方法，它成功地解決了機器學(xué)習(xí)一直存在的高維度和局部極值問題，目前已經(jīng)在很多領(lǐng)域取得了巨大的成功[2-4]。盡管傳統(tǒng)的支持向量機占據(jù)諸多優(yōu)勢，但是仍然存在許多問題。支持向量機的基本動機是找到一個決策超平面，使兩類數(shù)據(jù)之間的間隔最大，根據(jù)其間隔最大化，構(gòu)造目標函數(shù)，再轉(zhuǎn)化成其對偶問題進行求解。支持向量機的原問題是一個凸的二次規(guī)劃問題，在求解其對偶問題時，其運算量取決于樣本的規(guī)模大小與維度的高低。在實際問題中，如圖像處理[5]、雷達一維距離像處理[6]、數(shù)據(jù)挖掘等領(lǐng)域[7]，通常樣本集的規(guī)模都非常龐大，并且具有很高的維度，如此大規(guī)模的數(shù)據(jù)，占用了大量的內(nèi)存空間導(dǎo)致支持向量機的訓(xùn)練時間過長。因此，為了減少其運算量，有必要對樣本集進行約簡?？紤]到實際的支持向量機在分類時只用了少部分的支持向量，在求解其對偶問題時，最優(yōu)分類超平面只與拉格朗日乘子不為零的項有關(guān)，如果能在求解二次規(guī)劃前把包含支持向量的邊界點提取出來，并用這些邊界樣本點來替代所有的訓(xùn)練樣本進行支持向量機訓(xùn)練，這無疑會大量減少運算成本，從而可解決支持向量機訓(xùn)練時間過長和內(nèi)存消耗過大等方面的問題[8]。傳統(tǒng)的支持向量機對噪聲點和孤立點異常敏感，并且在優(yōu)化過程中不僅對支持向量進行了優(yōu)化，同時也對非支持向量進行了優(yōu)化，這無疑增大了運算成本。近年來，研究者提出大量方法以減少孤立點、噪聲點對傳統(tǒng)支持向量機的影響，同時針對處理大規(guī)模數(shù)據(jù)集時怎樣有效地篩選出支持向量也進行了諸多研究[9-11]，大體上有兩方面的改進。其一是在大規(guī)模數(shù)據(jù)集上，根據(jù)支持向量分布的幾何意義，把支持向量提取出來，從而達到了縮減樣本集規(guī)模的目的[12]。其二是根據(jù)在分類時每個樣本對分類決策超平面起作用的程度不同，給每個樣本賦予權(quán)重，對遠離整體樣本集的噪聲點和孤立點賦予更小的權(quán)重，從而減少了孤立點和噪聲點對決策超平面的影響，形成了模糊支持向量[13-14]。此類方法雖然降低了孤立點和噪聲點對決策超平面的影響，但是孤立點和噪聲點以及大量的非邊界點仍然參加了訓(xùn)練，并沒有降低運算成本，且分類精度的提高是以計算每個樣本的權(quán)重為代價的。文獻[14]和文獻[15]提出了兩種針對訓(xùn)練集不同的刪減策略，但是它們都需要對訓(xùn)練樣本集進行多次的支持向量機模型訓(xùn)練，較為復(fù)雜。文獻[16]根據(jù)每個樣本的最近鄰是否為同類別來對樣本集進行刪減，但是這種刪減策略有時可能會誤刪分類時所用到的支持向量，同時也有可能誤保留噪聲點。文獻[17]利用K-近鄰方法來對樣本集進行刪減，計算每個樣本的K個最近鄰，利用這K個最近鄰中同類樣本的數(shù)量是否低于給定的閾值來對樣本集進行刪減，盡管與文獻[16]相比，可以更有效合理的對樣本進行刪減，但是仍然保留了大量的非邊界點。

針對上述支持向量機的缺陷，本文提出了一種改進的支持向量機分類算法——基于邊界點的支持向量機分類方法(Support Vector Machine Classification Algorithm Based on Boundary Points，BP-SVM)。

1 支持向量機簡介

1.1 線性可分支持向量機

給定訓(xùn)練樣本集F={(x1,y1),(x2,y2),…，(xn,yn)},yi∈{-1,1}，支持向量機的核心思想是基于訓(xùn)練集F，在其空間中找到一個最優(yōu)的分類超平面，使兩類樣本之間的間隔最大，其超平面方程可描述為

ωTx+b=0。

若超平面(ω,b)能將訓(xùn)練樣本正確分類，即對于(xi,yi)∈D，若yi=1，則有ωTxi+b>0；若yi=-1，則有ωTxi+b<0。令

(1)

構(gòu)造支持向量機優(yōu)化模型

(2)

這就是支持向量機的基本模型。

注意到式(2)本身是一個凸的二次規(guī)劃問題，利用拉格朗日乘子法可以轉(zhuǎn)化成其對偶問題進行求解，該凸二次規(guī)劃問題的拉格朗日函數(shù)為

其中αi≥0是拉格朗日乘子。

得到式(2)的對偶問題

αi≥0,i=1,2,…,n,

決策函數(shù)為

1.2 線性不可分支持向量機

有時并不是所有的樣本都能同時滿足式(1)中的約束條件，在這種情況下，向式(2)中引入一個松弛變量ξi，則目標函數(shù)式(2)變?yōu)?/p>

(3)

將式(3)引入拉格朗日乘子αi和βi，構(gòu)造拉格朗日函數(shù)得

其中αi≥0、βi≥0是拉格朗日乘子。

得到式(3)的對偶問題為

0≤αi≤C,i=1,2,…,n,

決策函數(shù)為

1.3 非線性支持向量機

對于非線性問題，首先使用一個變換z=φ(x)將x映射到新的特征空間z,得到支持向量機的對偶問題

0≤αi≤C,i=1,2,…,n,

決策函數(shù)為

其中k(·,·)是核函數(shù)。常見的核函數(shù)有：

總體來說支持向量機的核函數(shù)主要分為全局核函數(shù)和局部核函數(shù)。全局核函數(shù)的支持向量機外推能力強而學(xué)習(xí)能力弱，局部核函數(shù)的支持向量機學(xué)習(xí)能力強但泛化能力較弱。在以上列舉的核函數(shù)中線性核函數(shù)和多項式核函數(shù)屬于全局核函數(shù)，徑向基核函數(shù)屬于局部核函數(shù)。

2 邊界點下的支持向量機分類算法

2.1 K-近鄰算法

K-近鄰(K-Nearest Neighbor，KNN)算法是機器學(xué)習(xí)中最基本的一個算法，其思想相對比較容易理解。K-近鄰算法大體思想就是在特征空間中按照某種距離的計算方法，根據(jù)距離公式找到每個樣本距離最近的K個樣本，在每個樣本的K個最近鄰中，大多數(shù)樣本都屬于哪個類別，就把這個樣本也歸到其相應(yīng)的類別，這就是K-近鄰算法的基本思想。

2.2 提取邊界樣本點

2.2.1 線性情況下提取邊界樣本點

設(shè)F={(x1,y1),(x2,y2),…,(xn,yn)}，其中xi∈Rn，yi∈{-1,1},i=1,2,…,n。正類樣本xi(i=1,2,…,n+)，負類樣本xj(j=n++1,n++2,…,n++n-)，其中n=n++n-。給定正類樣本xt，提取邊界樣本的步驟如下：

根據(jù)兩樣本的歐氏距離

通常情況下，如果一個樣本點xt到同類樣本的K個最近鄰的距離和到異類樣本的K個最近鄰的距離都相對較小，那么此樣本點更可能成為邊界點。如圖1所示，樣本點A的同類3-近鄰和異類3-近鄰均比較小，所以點A為邊界樣本點，樣本點B的同類3-近鄰相對較小而異類3-近鄰相對較大，所以點B為非邊界樣本點。

圖1 邊界點與非邊界點示意圖

2.2.2 非線性條件下提取邊界樣本點

在大多數(shù)分類任務(wù)中，樣本所在的原始空間并不能找到一個能將兩類樣本正確劃分的超平面，通常情況下，通過映射φ(x)將樣本映射到一個高維特征空間，使樣本在這個高維的特征空間內(nèi)變得線性可分。令φ(x)表示將x映射后的特征向量，兩樣本在特征空間中的距離為

(4)

其中φ(xt)·φ(xi)是樣本xt、xi映射到特征空間之后的內(nèi)積，k(xt,xi)=φ(xt)·φ(xi)是核函數(shù)。

無論是線性情況下還是非線性情況下，閾值θ1、θ2的選取都是依據(jù)空間中各個維度的最大值、最小值和平均值來根據(jù)經(jīng)驗確定的。如果閾值θ1、θ2的值選擇過大，會導(dǎo)致邊界點過多，不能有效地去除非邊界點，如果閾值θ1、θ2的值選擇過小，會過濾掉包含支持向量的邊界點，造成模型效果不佳。

記D1為所有非邊界點構(gòu)成的集合。

對于非線性情況，在提取邊界點時，需要通過核函數(shù)將樣本映射到特征空間計算其距離來尋找其K個最近鄰，但是核函數(shù)的參數(shù)并未能事先取得，為此，給出定理。

定理當(dāng)支持向量機核函數(shù)為徑向基核函數(shù)或者指數(shù)核函數(shù)時，可更簡單的采用輸入空間的距離公式

(5)

證明對于徑向基核函數(shù)和指數(shù)核函數(shù)都有k(xi,xi)=k(xj,xj)=1，所以

或者有

而d(xi,xj)≥0，由指數(shù)函數(shù)和冪函數(shù)的性質(zhì)可知，對于輸入空間的兩個固定樣本xi、xj，D(xi,xj)是關(guān)于d(xi,xj)單調(diào)遞增的，這表明樣本在原始輸入空間和特征空間中，樣本的相對遠近程度并沒有發(fā)生改變，僅僅只有緊密度發(fā)生了變化，從而當(dāng)核函數(shù)為徑向基核函數(shù)或指數(shù)核函數(shù)時，在原始輸入空間和特征空間所求的K個最近鄰?fù)耆嗤?。證畢。

2.3 K-近鄰刪除樣本點

2.4 邊界點下的支持向量機的步驟

步驟一：根據(jù)公式(5)計算兩兩樣本之間的歐式距離;

步驟三：根據(jù)2.2提取出邊界樣本點，刪除非邊界點;

步驟五：對刪減過后的樣本集利用傳統(tǒng)的支持向量機進行訓(xùn)練。

邊界點下的支持向量機步驟流程如圖2所示。

圖2 邊界點下的支持向量機步驟流程圖

2.5算法的復(fù)雜度分析

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

3.1 實驗設(shè)計

為了驗證BP-SVM算法的有效性，對算法進行測試，實驗環(huán)境如下：

1)硬件環(huán)境：1.80 GHz CPU，內(nèi)存8 GB，硬盤100 GB以上的個人計算機;

2)軟件環(huán)境：Windows10 Professional操作系統(tǒng)，用Python3.8編程實現(xiàn)。

線性條件下的實驗數(shù)據(jù)集采用隨機產(chǎn)生的400個服從高斯分布的線性不可分數(shù)據(jù)，其中正樣本的個數(shù)為200，負樣本的個數(shù)為200，正樣本集服從均值為1、方差為2的高斯分布，負樣本集服從均值為4，方差為1的高斯分布。支持向量機采用線性核函數(shù)。非線性條件下的實驗數(shù)據(jù)集采用Banana數(shù)據(jù)集，支持向量機采用徑向基核函數(shù)。除此之外，本文從UCI機器學(xué)習(xí)庫中共選取6個數(shù)據(jù)集，分別是Banana、Breast、Thyroid、Heart、Titanic、Diabetis，除Diabetis數(shù)據(jù)集采用了線性核函數(shù)，其他數(shù)據(jù)集均采用徑向基核函數(shù)。

在分類任務(wù)中，通常用正確率和錯誤率來衡量分類器性能的好壞，如果樣本總數(shù)為n，其中有m個樣本被誤分，則錯誤率可以表示為

分類正確率可表示為

本文用正確率來衡量分類器的性能。

3.2 各類算法的訓(xùn)練點數(shù)量對比圖

圖3和圖4分別是在線性條件下和非線性條件下，傳統(tǒng)支持向量機(SVM)、最近鄰支持向量機(NN-SVM)、K-近鄰支持向量機(KNN-SVM)和BP-SVM算法訓(xùn)練點的數(shù)量對比圖。從圖中可以看出，最近鄰支持向量機有效地刪除了混雜在異類中的點，但是同時也誤刪了支持向量機在分類時所用的邊界點。K-近鄰支持向量機刪除了混雜在異類中的點，同時克服了最近鄰支持向量機的缺陷，保留了支持向量機在分類時所用的邊界點，但是仍有許多孤立點和大量的非邊界點存在。本文算法既有效地保留了支持向量分類時起作用的邊界點，同時也刪除了混雜在異類中的點和一些遠離整體樣本的孤立點、噪聲點，大大縮減了訓(xùn)練樣本的數(shù)量。

(a)SVM (b)NN-SVM (c)KNN-SVM (d)BP-SVM

(a)SVM (b)NN-SVM (c)KNN-SVM (d)BP-SVM

圖5和圖6分別是在線性條件下和非線性條件下，傳統(tǒng)支持向量機、最近鄰支持向量機、K-近鄰支持向量機和BP-SVM算法分類效果對比圖。從圖中可以看出，線性條件下，BP-SVM算法只用了少量的邊界點對支持向量機進行訓(xùn)練，同時排除了噪聲點和孤立點對決策超平面的影響，使分類器有更好的泛化能力；非線性條件下，與傳統(tǒng)支持向量機、最近鄰支持向量機和K-近鄰支持向量機相比，BP-SVM算法刪去了大量的非邊界點、和混雜在異類中的樣本點，只利用了少量的邊界點對支持向量機進行訓(xùn)練，從而大大縮減了在優(yōu)化時所帶來的計算損失。

(a)SVM (b)NN-SVM (c)KNN-SVM (d)BP-SVM

(a)SVM (b)NN-SVM (c)KNN-SVM (d)BP-SVM

3.3 實驗結(jié)果

本文從UCI機器學(xué)習(xí)庫中共選取6個數(shù)據(jù)集，分別是Banana、Breast、Thyroid、Heart、Titanic、Diabetis，數(shù)據(jù)集描述見表1。各種算法的訓(xùn)練點數(shù)量和分類正確率見表2和表3。從表2和表3可以看出，與傳統(tǒng)支持向量機、最近鄰支持向量機和K-近鄰支持向量機相比，BP-SVM算法大幅度裁減了冗余的、無用的訓(xùn)練樣本的數(shù)量，只利用了少量的邊界點進行訓(xùn)練。從表3可以看出，本文算法在Breast、Thyroid數(shù)據(jù)集中，正確率等于或者大于傳統(tǒng)支持向量機，其原因是本文算法在提取邊界點時，刪除了非邊界點，這些非邊界點包括噪聲點和孤立點，從而提高了正確率。

表1 數(shù)據(jù)集描述

表2 各種算法的訓(xùn)練點數(shù)量

表3 各種算法的分類正確率 %

4 結(jié)論

本文針對傳統(tǒng)支持向量機在訓(xùn)練時應(yīng)用了所有的樣本點進行訓(xùn)練，提出了一種利用邊界點進行訓(xùn)練的支持向量機(BP-SVM)。與傳統(tǒng)支持向量機、最近鄰支持向量機、K-近鄰支持向量機相比，只利用了少量的邊界點訓(xùn)練支持向量機，同時排除了噪聲點和孤立點對決策超平面的影響。在算法復(fù)雜度方面，BP-SVM算法的復(fù)雜度明顯低于傳統(tǒng)支持向量機的復(fù)雜度。在正確率方面，在Breast、Thyroid數(shù)據(jù)集中，BP-SVM算法的正確率大于或等于傳統(tǒng)支持向量機。最后得出結(jié)論，與傳統(tǒng)支持向量機、最近鄰支持向量機、K-近鄰支持向量機相比，在正確率相當(dāng)?shù)那闆r下，BP-SVM方法有效地縮減了訓(xùn)練樣本數(shù)目。