基于異類近鄰的支持向量機(jī)加速算法

陳景年,胡順祥,徐 力

(a.山東財(cái)經(jīng)大學(xué) 信息與計(jì)算科學(xué)系,濟(jì)南 250014; b.魯南技師學(xué)院 商務(wù)管理系,山東 臨沂 276021; c.濟(jì)南市公路管理局 信息科,濟(jì)南250013)

0 概述

支持向量機(jī)(Support Vector Machine,SVM)是基于統(tǒng)計(jì)學(xué)習(xí)理論的一種機(jī)器學(xué)習(xí)方法,在結(jié)構(gòu)風(fēng)險(xiǎn)最小化基礎(chǔ)上,可有效地避免傳統(tǒng)方法中局部極小、過擬合、維數(shù)災(zāi)難等常見問題,并且在小樣本集上依然能取得好的學(xué)習(xí)效果[1]。因此,在文本分類、網(wǎng)頁過濾、目標(biāo)跟蹤等領(lǐng)域得到了廣泛應(yīng)用[2-4]。

標(biāo)準(zhǔn)的SVM訓(xùn)練過程歸結(jié)為一個(gè)凸二次規(guī)劃問題。 隨著訓(xùn)練樣本的增多,其訓(xùn)練空間和時(shí)間會(huì)急劇增加。所以,SVM難以適用于大規(guī)模數(shù)據(jù)集。如何提高 SVM 的學(xué)習(xí)效率以適應(yīng)大規(guī)模數(shù)據(jù)處理的需求成為近年來的一個(gè)研究熱點(diǎn)[5-8]。

本文利用異類近鄰來選擇邊界樣本,這一方法不僅適用于復(fù)雜邊界的情形,而且對多類分類問題也非常有效。

1 研究背景

文獻(xiàn)[1]指出,在SVM的訓(xùn)練過程中,只有支持向量對構(gòu)建分類模型起作用,并且支持向量往往位于類邊界附近。因此,邊界附近的樣本對SVM的分類結(jié)果起決定作用。所以在構(gòu)建SVM分類模型時(shí),不必應(yīng)用所有訓(xùn)練樣本,而只需選取其中最有可能成為支持向量的邊界樣本參與訓(xùn)練過程。這樣,在保持構(gòu)建的分類模型效果的同時(shí),因訓(xùn)練樣本的減少而可以大幅度提高訓(xùn)練效率。

基于上述思路,研究人員給出了一些有效的方法以選取潛在的支持向量來構(gòu)成精簡的訓(xùn)練集,提高了訓(xùn)練效率。

文獻(xiàn)[9]利用一個(gè)樣本分別到2類樣本中每個(gè)類的中心的距離之比來判斷該樣本是否為邊界樣本。該方法在保持SVM分類效果的情況下,可明顯提高SVM的訓(xùn)練速度。文獻(xiàn)[10]首先用一個(gè)小樣本子集訓(xùn)練得到一個(gè)初始的SVM分類超平面,然后將原樣本集中離此平面較遠(yuǎn)的樣本刪除。通過該方法可以刪除一些冗余樣本,在保持SVM泛化能力的同時(shí),提高了其訓(xùn)練速度。

文獻(xiàn)[11]利用每個(gè)樣本的k近鄰在訓(xùn)練集中的序號及相應(yīng)的距離對樣本打分,并按打分高低選擇樣本。文獻(xiàn)[12]根據(jù)樣本的k近鄰中異類樣本數(shù)來選擇樣本。

近來,文獻(xiàn)[13]利用每個(gè)樣本的最近鄰信息得到訓(xùn)練集的一致子集,然后利用此子集訓(xùn)練SVM。該選擇算法的效率較高,但有時(shí)樣本選擇效果不夠理想。文獻(xiàn)[14]以每類樣本的聚類中心作為參照來選擇其他類中的邊界樣本。

上述研究工作在保持分類效果和提高訓(xùn)練效率方面都有一定作用,但在數(shù)據(jù)集的類別邊界非常復(fù)雜和類別較多的情況下,選擇效果往往不理想。

2 基于異類近鄰的邊界樣本選擇

為使提出的算法更具普適性,考慮一般的多類分類問題。由于SVM分類模型是針對二類分類問題建模的,因此在應(yīng)用SVM模型進(jìn)行分類時(shí),通常將一個(gè)多類分類問題轉(zhuǎn)化為多個(gè)二類分類問題來解決。常用的轉(zhuǎn)化方式有2種:一對一方式和一對多方式。在一對一方式中,多類中的每2個(gè)類之間都要構(gòu)建一個(gè)SVM模型。這樣,不僅需要訓(xùn)練大量的模型,而且使后續(xù)的分類過程變慢。在一對多方式中,每個(gè)類輪流做一次正類。在一個(gè)類作為正類時(shí),其余類合起來作為負(fù)類。由于一對多方式需訓(xùn)練的SVM模型較少,而且后續(xù)的分類過程效率高,因此,在下面的樣本選擇算法中,將采用一對多方式。

假定訓(xùn)練集A是由L類樣本所組成,A中的樣本總數(shù)為N。A中的每一類樣本都輪流做一次正類樣本,與此同時(shí),其余樣本作為負(fù)類樣本。下面考慮第c(1≤c≤L)類樣本為當(dāng)前的正類樣本時(shí)的邊界樣本選擇問題,記選擇的結(jié)果為Sc。

選擇過程包括正類樣本選擇和負(fù)類樣本選擇2個(gè)方面。選擇結(jié)果Sc初始化為空集φ。首先進(jìn)行的是負(fù)類樣本的選擇。對于第c類中的每個(gè)樣本x,計(jì)算x在第l(1≤l≤L,l≠c)類中的k個(gè)最近鄰xlj(1≤j≤k)。判斷xlj是否屬于Sc。如果xlj∈Sc,則將xlj選入Sc。這里,計(jì)算k近鄰的操作是在每一小類樣本中進(jìn)行的,不同于傳統(tǒng)的做法在整個(gè)數(shù)據(jù)集中進(jìn)行。因此,上述k近鄰的搜索過程因搜索范圍的縮小而較傳統(tǒng)做法具有更高的效率。

正類樣本的選擇過程與負(fù)類樣本選擇類似。由于在多類分類問題中采用了一對多的轉(zhuǎn)化模式,這可能會(huì)引起正類與負(fù)類之間樣本數(shù)目嚴(yán)重不均衡的問題。因此,在正類樣本的選擇過程中,增加了一項(xiàng)調(diào)節(jié)正類和負(fù)類之間均衡性的操作,即在正類樣本明顯偏少的情況下(比如少于選擇的負(fù)類樣本數(shù)的一半),則正類樣本將全部保留。整個(gè)邊界樣本選擇過程如圖1所示。其中,L為訓(xùn)練集A中的樣本類數(shù),N為A中的樣本總數(shù),Nc為第c類樣本數(shù),Ns為選擇的負(fù)例數(shù),Sc為第c類作為當(dāng)前正類時(shí)樣本選擇的結(jié)果。

圖1 基于異類近鄰的樣本選擇算法流程

下面是所給的樣本選擇和模型訓(xùn)練的算法描述。

算法基于異類近鄰的樣本選擇算法

輸入訓(xùn)練集A(含有L個(gè)類,共N個(gè)樣本),近鄰數(shù)k

輸出對每個(gè)類別c(1≤c≤L),輸出以c類樣本為正類,其余樣本為負(fù)類時(shí)的選擇結(jié)果Sc

1)初始化:c=1;Sc←φ。

2)以c類樣本為正例,其余樣本為負(fù)例。

3)負(fù)例(即負(fù)類樣本)的選擇過程:

(1)l=1;

(2)如果l≠c,則:

①對于第c類中的每個(gè)樣本x,計(jì)算x在第l類中的k個(gè)最近鄰xlj(l≤j≤k)。

②如果xlj∈Sc,則Sc←Sc∪{xlj}。

(3)l←l+1;

(4)如果l≤L,則轉(zhuǎn)(2),否則轉(zhuǎn)4)。

4)正例(即正類樣本)的選擇過程:

(1)比較c類樣本數(shù)Nc和選擇的負(fù)例數(shù)Ns的大小關(guān)系。

(2)如果Nc<0.5Ns,則所有c類樣本被選入Sc,轉(zhuǎn)5)。

(3)對每個(gè)負(fù)例y:

①計(jì)算y在第c類中的k個(gè)最近鄰xcj(l≤j≤k)。

②如果xcj∈Sc,則Sc←Sc∪{xcj}。

5)在得到的Sc上訓(xùn)練SVM模型。

6)c←c+1。

7)如果c≤L,轉(zhuǎn)2)。

8)結(jié)束。

3 算法說明

3.1 與相關(guān)算法的不同之處

盡管上述基于異類近鄰的邊界樣本選擇算法利用了樣本的k近鄰來進(jìn)行樣本選擇,但與以往基于k近鄰的樣本選擇方法相比,本文所給算法有如下不同之處:

1)以往基于k近鄰的算法往往是在整個(gè)訓(xùn)練集中搜索一個(gè)樣本的k近鄰,而上述算法是在除當(dāng)前正類之外的每個(gè)小類中搜索一個(gè)正類樣本的k近鄰,簡稱異類k近鄰。因此,搜索的效率會(huì)明顯提高。

2)與以往基于k近鄰的算法相比,在上述算法中,異類k近鄰的使用使得選擇算法能夠適用于各種復(fù)雜的類別邊界,而不像以往算法往往受邊界條件的限制。

3)在正類樣本的選擇過程中,能夠根據(jù)正類與負(fù)類樣本數(shù)的差距來消除正、負(fù)類之間的不均衡問題,這也是上述算法的一個(gè)獨(dú)到之處。

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

所給算法包含了負(fù)例選擇和正例選擇2個(gè)過程,并且正例選擇過程的復(fù)雜度不超過(許多情況下遠(yuǎn)低于)負(fù)例選擇過程的復(fù)雜度。所以,這里只對負(fù)例選擇過程的復(fù)雜度進(jìn)行分析。

3.3 算法的參數(shù)設(shè)置方法

在給出的樣本選擇算法中,一個(gè)樣本的近鄰數(shù)k對算法的效果和效率具有重要的作用。很顯然,k越小,選擇的樣本越少,訓(xùn)練效率會(huì)越高。同時(shí),也越容易損失一些支持向量,易引起訓(xùn)練效果的下降。反之,k越大,越不容易漏掉支持向量,但也往往會(huì)選入一些冗余的樣本,不僅使選擇的樣本增多,訓(xùn)練效率降低,同時(shí),較多的冗余樣本也會(huì)降低訓(xùn)練效果。因此,k的值不宜過大或過小,而應(yīng)在一定的范圍內(nèi)尋找合適的k值。實(shí)驗(yàn)發(fā)現(xiàn),絕大多數(shù)情況下,在2～10的范圍內(nèi)即可找到一個(gè)理想的k值。因此,通過實(shí)驗(yàn)不難確定合適的k值。

4 實(shí)驗(yàn)結(jié)果與分析

為驗(yàn)證本文所給算法的有效性,將它與性能顯著的2個(gè)邊界樣本選擇算法NPPS[12]以及FCNN[13]進(jìn)行多方位的比較,具體包括如下3個(gè)方面:1)樣本選擇的效果,即利用選擇的樣本得到的分類模型的分類準(zhǔn)確率;2)選擇的樣本占總訓(xùn)練樣本的比例;3)利用選擇的樣本訓(xùn)練分類模型所需的時(shí)間。

4.1 實(shí)驗(yàn)數(shù)據(jù)集

實(shí)驗(yàn)共采用了12個(gè)數(shù)據(jù)集,其中6個(gè)為小規(guī)模數(shù)據(jù)集,另6個(gè)為中等規(guī)?；虼笠?guī)模數(shù)據(jù)集。它們大都來自于UCI的機(jī)器學(xué)習(xí)數(shù)據(jù)庫[15]。另外,為了驗(yàn)證所給算法對多類分類,特別是大類別數(shù)據(jù)集分類的效果,實(shí)驗(yàn)中還采用了一個(gè)包含3 755類的手寫中文字符數(shù)據(jù)集HCL2000[16]。其中每一類都包含1 000個(gè)樣本,被分成了700個(gè)訓(xùn)練樣本和300個(gè)測試樣本。實(shí)驗(yàn)中選取了其中的前100個(gè)類中的樣本,并通過提取8-方向梯度特征得到512個(gè)屬性。表1列出了每個(gè)實(shí)驗(yàn)數(shù)據(jù)集中包含的樣本數(shù)、屬性數(shù)(也稱為特征數(shù))以及類數(shù)。其中,第1個(gè)～第6個(gè)數(shù)據(jù)集為小規(guī)模數(shù)據(jù)集,其余6個(gè)為中等或大規(guī)模數(shù)據(jù)集。

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

4.2 實(shí)驗(yàn)參數(shù)

在所有SVM模型的訓(xùn)練過程中,采用了下式定義的高斯核函數(shù)。

k(xi,xj)=exp(-‖xi-xj‖2/2σ2)

(1)

除了大類別集的數(shù)據(jù)集HCL2000[16]外,在每個(gè)數(shù)據(jù)集上都采用5重交叉驗(yàn)證的方法進(jìn)行實(shí)驗(yàn)。由于原始的數(shù)據(jù)集HCL2000規(guī)模很大,且已被分成了訓(xùn)練集和測試集,這里沒再對其重新劃分。

在每個(gè)數(shù)據(jù)集上,對式(1)中高斯核函數(shù)的參數(shù)σ2、SVM模型的誤差限C、本文所給算法的異類近鄰數(shù)k以及NPPS算法[12]中的近鄰數(shù)kn都通過實(shí)驗(yàn)的方法進(jìn)行優(yōu)化。表2列出了在每個(gè)數(shù)據(jù)集上的具體參數(shù)取值。由于FCNN[13]中采用的是最近鄰算法,因此不需要對其進(jìn)行參數(shù)設(shè)置。

表2 在每個(gè)數(shù)據(jù)集上的參數(shù)取值

4.3 實(shí)驗(yàn)結(jié)果

表3列出了在6個(gè)小規(guī)模數(shù)據(jù)集上的分類準(zhǔn)確率、樣本選擇比例及訓(xùn)練時(shí)間。表4則給出了在其余6個(gè)中等或大規(guī)模數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果。為了直觀地對所給算法與FCNN以及NPPS進(jìn)行比較,圖2～圖7用折線圖描繪了它們分別在2組數(shù)據(jù)集上的分類準(zhǔn)確率、樣本選擇比例及樣本選擇后的訓(xùn)練時(shí)間與未進(jìn)行樣本選擇的訓(xùn)練時(shí)間之比。

表3 在小規(guī)模數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果

表4 在中等或大規(guī)模數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果

圖2 小規(guī)模數(shù)據(jù)集上的分類精度

圖3 中大規(guī)模數(shù)據(jù)集上的分類精度

圖4 小規(guī)模數(shù)據(jù)集上的樣本選擇比例

圖5 中大規(guī)模數(shù)據(jù)集上的樣本選擇比例

圖6 小規(guī)模數(shù)據(jù)集上的訓(xùn)練時(shí)間比

圖7 中大規(guī)模數(shù)據(jù)集上的訓(xùn)練時(shí)間比

由圖2和圖3可以直觀地發(fā)現(xiàn),在大部分小規(guī)模數(shù)據(jù)集和所有中等規(guī)模與大規(guī)模數(shù)據(jù)集上,本文提出的樣本選擇算法在提高了SVM的訓(xùn)練效率的同時(shí),使分類取得了最好的效果。從表3和表4可以發(fā)現(xiàn),在實(shí)驗(yàn)的每個(gè)數(shù)據(jù)集上,本文算法的分類效果沒有明顯的降低。甚至在HCL2000、Optdigit以及Pendigit等數(shù)據(jù)集上分類準(zhǔn)確率比未進(jìn)行樣本選擇的情況下還有所提高。相比之下,FCNN算法與NPPS算法都沒有很好地保持分類效果。例如在Dermat、Glass、Iris、WDBC等數(shù)據(jù)集上,FCNN使得分類精度明顯下降。NPPS在Glass、Iris、Letter等數(shù)據(jù)集上引起了分類效果的明顯降低。上述實(shí)驗(yàn)結(jié)果表明,本文給出的選擇算法在選擇效果上有著明顯的優(yōu)勢。

由圖4和圖5可以發(fā)現(xiàn),本文所給算法選擇的樣本的比例總體上略低于NPPS算法的選擇比例而高于FCNN算法。在比較的樣本選擇算法中,FCNN算法選擇的樣本比例最低,在降低訓(xùn)練數(shù)據(jù)規(guī)模上具有一定優(yōu)勢。但由上文對選擇效果的比較來看,FCNN算法容易引起分類效果明顯降低。這說明選擇的樣本并不是越少越好。

從圖6和圖7綜合來看,在提高訓(xùn)練效率方面本文所給算法和NPPS算法相當(dāng),而FCNN算法在這方面具有一定優(yōu)勢。這同樣是由于FCNN算法選擇的樣本比例較低的緣故。

5 結(jié)束語

在眾多的分類算法中,支持向量機(jī)(SVM)因其較高的分類精度和堅(jiān)實(shí)的理論基礎(chǔ)而倍受關(guān)注,在諸多的應(yīng)用領(lǐng)域中取得了顯著的分類效果。然而,SVM對于樣本數(shù)目來說,具有立方級的訓(xùn)練復(fù)雜度。因此,如何提高SVM的訓(xùn)練效率一直是機(jī)器學(xué)習(xí)研究中的熱點(diǎn)問題。

為了在保持SVM效果的同時(shí)提高其效率,本文給出了精簡訓(xùn)練集的一種算法,即利用異類近鄰來選擇邊界樣本。這一算法不僅適用于復(fù)雜邊界的情形,也可以有效地用于多類分類問題,而且能在很大程度上減輕不均衡數(shù)據(jù)對分類模型的影響。在多個(gè)實(shí)驗(yàn)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明,該算法在使訓(xùn)練效率大幅提高的同時(shí),能更好地保持甚至改善分類效果。

為了使所給算法能更有效地用于大規(guī)模數(shù)據(jù)集,特別是大數(shù)據(jù)處理,還需要對算法在效率上做進(jìn)一步改進(jìn),這是下一步要做的一項(xiàng)研究內(nèi)容。

[1] VAPNIK V.The Nature of statistical learning theory[M].New York,USA:Springer,1995.

[2] JOACHIMS T.Text categorization with support vector machine:learning with many relevant features[C]//Proceedings of the 10th European Conference on Machine Learning.New York,USA:ACM Press,1998:137-142.

[3] 王憲亮,吳志剛,楊金超,等.基于SVM一對一分類的語種識別方法[J].清華大學(xué)學(xué)報(bào)(自然科學(xué)版),2013,53(6):808- 812.

[4] 孫俊濤,張順利,張 利.基于聯(lián)合支持向量機(jī)的目標(biāo)跟蹤算法[J].計(jì)算機(jī)工程,2017,43(3):266-270.

[5] DONG Jianxiong,KRZYZAK A,SUEN C Y.Fast SVM training algorithm with decomposition on very large data sets[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2005,27(4):603-618.

[6] LI Boyan,WANG Qiangwei,HU Jinglu.Fast SVM training using edge detection on very large datasets[J].IEEE Transactions on Electrical and Electronic Engineering,2013,8(3):229-237.

[7] JUNG H G.Support vector number reduction: survey and experimental evaluations novel[J].IEEE Transactions on Intelligent Transportation Systems,2014,5(2):463-476.

[8] 包文穎,胡清華,王長忠.基于多粒度數(shù)據(jù)壓縮的支持向量機(jī)[J].南京大學(xué)學(xué)報(bào)(自然科學(xué)版),2013,49(5):637- 643.

[9] 焦李成,張 莉,周偉達(dá).支撐矢量預(yù)選取的中心距離比值法[J].電子學(xué)報(bào),2001,29(3):383-386.

[10] 李紅蓮,王春花,袁保宗,等.針對大規(guī)模訓(xùn)練集的支持向量機(jī)的學(xué)習(xí)策略[J].計(jì)算機(jī)學(xué)報(bào),2004,27(5):715-719.

[11] PANDA N,CHANG E Y,WU Gang.Concept boundary detection for speeding up SVM[C]//Proceedings of International Conference on Machine Learning.New York,USA:ACM Press,2006:681-688.

[12] SHIN H,CHO S.Neighborhood property based pattern selection for support vector machines[J].Neural Computation,2007,19(3):816-855.

[13] ANGIULLI F,ASTORINO A.Scaling up support vector machines using nearest neighbor condensation[J].IEEE Transactions on Neural Networks,2010,21(2):351-357.

[14] CHEN Jingnian,ZHANG Caiming,XUE Xiaoping,et al.Fast instance selection for speeding up support vector machines[J].Knowledge-based Systems,2013,45(6):1-7.

[15] HETTICH S,BLAKE C L,MERZ C J.UCI repository of machine learning databases[EB/OL].[2017-03-21].http//www.ics.uci.edu/ ～mlearn/MLRepository.html.

[16] ZHANG Honggang,GUO Jun,CHEN Guang,et al.HCL2000——a large-scale handwritten Chinese character database for handwritten character recognition[C]//Proceedings of the 10th International Conference on Document Analysis and Recognition.Berlin,Germany:Springer,2009:286-289.