張國棟，肖　婭，周　炬，郭　薇

(沈陽航空航天大學(xué) 計算機學(xué)院，沈陽 110136)

?

信息科學(xué)與工程

一種支持向量機的樣本約簡方法

張國棟，肖婭，周炬，郭薇

(沈陽航空航天大學(xué) 計算機學(xué)院，沈陽 110136)

支持向量機算法求解會涉及矩陣的存儲與運算，因此算法的時空復(fù)雜度較大，這些不足之處限制了支持向量機的應(yīng)用。為提高支持向量機的訓(xùn)練速度，縮短訓(xùn)練時間，提出一種樣本約簡方法。該方法通過兩次樣本約簡，剔除掉大部分非邊界樣本，保留少數(shù)且有效的樣本作為訓(xùn)練集。然后，采取KNN算法去除約簡后訓(xùn)練集中的孤立點和噪音點。最后，對UCI標(biāo)準(zhǔn)數(shù)據(jù)集中的Breast-Cancers數(shù)據(jù)進行實驗，支持向量減少了25個，訓(xùn)練時間減少了7 ms，而準(zhǔn)確率卻得到了提高。實驗結(jié)果表明，在保證預(yù)測精確度的前提下，該算法能夠有效進行樣本約簡，縮短訓(xùn)練時間。

樣本約簡；支持向量機；邊界樣本；核函數(shù)；KNN

支持向量機(Support Vector Machine，SVM)算法[1-2]是根據(jù)Vapnik等人提出的統(tǒng)計學(xué)習(xí)理論發(fā)展而來，它在人臉識別、目標(biāo)跟蹤、工業(yè)檢測、網(wǎng)絡(luò)入侵檢測等領(lǐng)域都取得了很好的應(yīng)用效果[3-7]。但SVM的本質(zhì)是求解數(shù)學(xué)上的凸二次規(guī)劃問題，涉及矩陣的存儲和運算操作。因此，算法的時空復(fù)雜度較大,這影響了SVM的運算效率以及在大規(guī)模數(shù)據(jù)上的應(yīng)用。目前，相關(guān)研究學(xué)者分別從如下兩個角度提高SVM的訓(xùn)練速度，縮短訓(xùn)練時間：

(1)基于分解的思想。Vapnik等[8]人在1995年提出選塊算法，其思想是將原始的樣本集分解為若干個小的子樣本集，隨機選擇一個子樣本集作為工作集進行SVM訓(xùn)練，然后去掉工作集中拉格朗日乘子等于零對應(yīng)的樣本，只保留支持向量。Osuna等[9]人在1997年提出分解算法。它與選塊算法一樣，都是在子集中進行求解，都是用違反KKT條件的樣本去替換非支持向量，但是分解算法要求每次替換的數(shù)目要保持相等。Platt等[10]人在1998年提出序列最小最優(yōu)化算法(SMO算法)，該算法是一種特殊的分解算法。它的工作集數(shù)目固定為2個，每次迭代只更新2個拉格朗日乘子，就變?yōu)榍蠼鈨蓚€變量的優(yōu)化問題。

(2)基于邊界樣本選取的思想。李青等[11]人提出一種基于向量投影的支持向量預(yù)選取方法。Shin等[12]人提出了一種基于KNN算法的支持向量預(yù)選取方法。汪西莉等[13]人提出了一種利用馬氏距離選取支持向量(SV)的方法改進SVM。

本文提出一種支持向量機的樣本約簡方法。該算法通過兩次樣本約簡，剔除大部分的非邊界樣本，再利用KNN算法去除訓(xùn)練集中的噪音點和孤立點。

1　樣本約簡策略

本文提出一種樣本約簡方法。其主要思想是先在原始樣本集S0(如圖1(a))中挑選出環(huán)形邊界樣本集S1(如圖1(b))，再在樣本集S1中挑選出有效的邊界樣本集S2(如圖1(c))，以達到樣本約簡的目的。

圖1　訓(xùn)練集約簡

1.1樣本線性可分

樣本集線性可分情形下，約簡步驟如下：

(1)定義樣本集S0涉及的變量

定義1：樣本集中兩類樣本的中心o1,o2分別為兩類樣本集L1,L2中所有樣本的平均值。

定義2：樣本集中任意兩個樣本點之間的距離采用歐式距離表示，樣本點xi到兩類數(shù)據(jù)中心o1,o2的距離dist(o1,xi)和dist(o2,xj)，數(shù)據(jù)中心o1,o2之間的距離dist(o1,o2)。

定義3：樣本集中兩類樣本的數(shù)據(jù)半徑r1,r2為樣本集中的樣本到該樣本集數(shù)據(jù)中心o1,o2的最遠距離。

(2)構(gòu)造環(huán)形邊界訓(xùn)練集S1。對于樣本集S0中的第一類樣本xi，計算它到數(shù)據(jù)中心o1的距離dist(o1,xi)，并與閾值T1進行比較，將滿足條件dist(o1,x)>T1的樣本點xi挑選出來作為訓(xùn)練集S1中的第一類樣本。針對第二類樣本xj，也是按照同樣的方法進行挑選。如圖1(b)所示，兩個環(huán)形區(qū)域包含的樣本構(gòu)成訓(xùn)練集S1。

(3)構(gòu)造有效邊界訓(xùn)練集S2。針對訓(xùn)練集S1中的兩類樣本點，利用公式(1)計算樣本與兩類數(shù)據(jù)中心夾角的余弦值。將符合cosαi∈L1>0的第一類樣本點和符合cosαj∈L2>0的第二類樣本點作為訓(xùn)練集S2的樣本點。如圖1(c)所示，最終的訓(xùn)練集S2包含的樣本處于兩個半環(huán)形區(qū)域，即虛線L1和L2之間。

定義4：樣本點余弦值。第一類樣本點xi的向量o1xi與數(shù)據(jù)中心向量o1o2的夾角余弦值和第二類樣本點xj的向量o2xj與數(shù)據(jù)中心向量o2o1的夾角余弦值如式(1)所示：

(1)

1.2樣本非線性可分

當(dāng)訓(xùn)練數(shù)據(jù)為非線性時，直接使用上述方法進行樣本約簡，效果并不理想，因此核函數(shù)的思想被引用來解決樣本的非線性可分情況。核函數(shù)k(xi,xj)=<φ(xi)·φ(xj)>，不僅解決了原始空間到特征空間的映射問題，還避免了復(fù)雜的向量內(nèi)積運算。

非線性可分情形下，樣本約簡算法流程如下：

(1)核函數(shù)的選擇。根據(jù)SVM初始訓(xùn)練集的先驗信息，選擇合適的核函數(shù)進行相關(guān)運算。

(2)樣本約簡。采用前述樣本約簡方法對數(shù)據(jù)進行約簡，只是在計算數(shù)據(jù)中心、樣本距離、數(shù)據(jù)半徑以及樣本余弦值時計算公式發(fā)生改變。

2　孤立點或噪音點的去除

2.1KNN思想

KNN算法[14-15]是一種基于類比學(xué)習(xí)的非參數(shù)分類技術(shù)，在許多領(lǐng)域已取得較好應(yīng)用效果。算法的基本原理是先計算待測樣本與已有訓(xùn)練集中所有樣本的距離，然后選取距離待測樣本最近的K個樣本點，K個樣本中哪一類的樣本數(shù)目多，則將待測樣本判定為該類別。

2.2孤立點或噪音點去除

這里的噪音點去除算法主要是針對SVM樣本約簡后的訓(xùn)練集，步驟如下：

(1)計算樣本之間的距離。對SVM的約簡樣本集S2中的任意樣本xi，采用歐式距離公式計算它與剩余樣本點xj(j∈S2,j≠i)的距離。若樣本集S2中有N個樣本，經(jīng)過距離計算后可得到一個N×N對稱矩陣。

(2)孤立點或噪音點的去除。根據(jù)距離選擇離樣本點xi最近的k個近鄰點，如果在這k個點中不存在k′個樣本與xi屬于同一類別，則將xi定義為噪音點或孤立點，且將它從樣本集中移走。參數(shù)k/k′需要根據(jù)實驗結(jié)果進行相應(yīng)調(diào)節(jié)。

3　實驗結(jié)果

實驗采用UCI數(shù)據(jù)庫中Breast-cancers數(shù)據(jù)測試非線性情況下的約簡效果。由表1可知：Breast-cancers數(shù)據(jù)集約簡后支持向量的數(shù)目減少了13個，訓(xùn)練時間減少了58%，并且準(zhǔn)確率得到一定程度的提升。這表明，本文方法在保證預(yù)測精確度的同時，能夠有效剔除大部分非邊界樣本，縮短訓(xùn)練時間。

表1　Breast-cancers數(shù)據(jù)集樣本約簡實驗結(jié)果

SVM初始樣本集經(jīng)過樣本約簡后，采用KNN思想刪除噪音點或孤立點。實驗采用UCI標(biāo)準(zhǔn)數(shù)據(jù)庫中的Breast-cancers數(shù)據(jù)集進行實驗。如表2所示，數(shù)據(jù)的約簡參數(shù)p1/p2為0.5/0.5，KNN參數(shù)k/k′為10/6，去除的噪音點的數(shù)目為9個，去除的支持向量數(shù)目為12個。實驗結(jié)果表明，本文所采用的KNN算法，能夠去除SVM訓(xùn)練集中的噪音點。

表2　Breast-cancers數(shù)據(jù)集去除噪音點實驗結(jié)果

4　結(jié)論

通過研究支持向量機的原理和幾何分布的特點，提出了一種樣本約簡方法。根據(jù)樣本點與類中心的距離和樣本點與類中心夾角的余弦值兩個指標(biāo)對樣本集進行挑選，獲取訓(xùn)練集，并且在處理非線性樣本時，引入核函數(shù)的思想，最后采用KNN算法去除約簡后訓(xùn)練集中的孤立點或噪音點。實驗結(jié)果表明，本文方法在保證分類精確度的前提下，能夠獲取有效的支持向量，縮短訓(xùn)練時間。

[1]V.N.VAPNIK,Statistical Learning Theory[M].New York,USA,Jhon Wiley & Sons,1998.

[2]BURGES C J C.A Tutorial on Support Vector Machines for Pattern Recognition [J].Data Mining and Knowledge Discovery,1998,2(2):955-974.

[3]YANG J，YU X，XIE Z Q.A novel virtual sample generation method based on Gaussian distribution [J].Knowledge-Based Systems,2011,24(8):740-748.

[4]MIN N I,GUI-AN H U,DAI Y.Application of SVM in UAVs Real-time Route Planning[J].Journal of Chongqing Institute of Technology,2009,5

[5]王朝勇.支持向量機若干算法研究及應(yīng)用[D].長春：吉林大學(xué),2008.

[6]宋華軍.基于支持向量機的目標(biāo)跟蹤技術(shù)研究[D].長春：中國科學(xué)院研究生院(長春光學(xué)精密機械與物理研究所),2006.

[7]方駿.支持向量機在工業(yè)質(zhì)量檢測中的應(yīng)用研究[D].杭州：浙江大學(xué),2004.

[8]CORTES C，VAPNIK V.Support vector networks [J].Machine Learning,1995,20(3):273-297.

[9]OSUNA E，F(xiàn)REUND R，GIROSI F.An Improved Training Algorithm for Support Vector Machine [C].Proceedings of the 1997 IEEE Workshop on Network for Signal Processing Ⅶ,Amelea Island,USA,IEEE,1997:276-285.

[10]PLATT J C.Fast training of support vector machines using sequential minimal optimization [M].Advances in Kernel Methods-Support Vector Learning,MIT Press,1999:185-208.

[11]李青，焦李成，周偉達.基于向量投影的支持向量預(yù)選取[J].計算機學(xué)報,2005，28(2):145-152.

[12]SHIN H,CHO S.Pattern Selection for Support Vector Classifiers[J].Lecture Notes in Computer Science,2002(2412):469-474.

[13]WANG XI-LI，JIAO LI-CHENG.A fast algorithm for extracting the support vector on the mahalanobis distance [J].Journal of Xidian University(S1001-2400),2004,31(4):639-643.

[14]SOUCY P,MINEAU G W.A simple KNN algorithm for text categorization [C].IEEE International Conference on Data Mining,San Jose,CA,2001,647-648.

[15]CHEN Y Q,YAN M S,NIXON,et al.Implementing the k-nearest neighbor rule via a neural network[C].In Proceedings of the IEEE International Conference on Neural Networks,Perth,WA,1995,1:136-140.

(責(zé)任編輯：劉劃英文審校：趙亮)

Method of sample reduction for Support Vector Machine

ZHANG Guo-dong，XIAO Ya，ZHOU Ju，GUO Wei

(College of Computer Science,Shenyang Aerospace University,Shenyang 110136，China)

Support Vector Machine(SVM)involves the storage and calculation of the matrix.Therefore,the huge space and time involved limit the application of SVM.In order to improve the training speed and save storage space,this paper presented a method to reduce the number of the training data.Firstly,the method removed most of the non-boundary samples and keeps only a few samples as training data by two steps reduction.Then,KNN was used to remove some noise.Breast-Cancers of UCI standard data sets were employed to evaluate our method.Twenty-five data were removed from the set of support vectors and the training time was decreased by 7 ms,while the accuracy of classification has improved.The experimental result shows that the proposed method can effectively reduce the number of training data,and decrease the training time with the increase in the accuracy of classification.

sample reduction;SVM;boundary sample;kernel function;KNN

2095-1248(2016)03-0063-04

2015-11-03

國家自然科學(xué)基金(項目編號：61373088)，國家自然科學(xué)基金(項目編號：61402298)，航空基金(項目編號：2013ZE54025)

張國棟(1972-)，男，黑龍江牡丹江人，教授，主要研究方向：醫(yī)學(xué)圖像處理，E-mail:zhanggd@sau.edu.cn。

TP391.41

A

10.3969/j.issn.2095-1248.2016.03.010