一種支持向量機(jī)算法設(shè)計(jì)中優(yōu)化的混合加權(quán)核函數(shù)選取與樣本加權(quán)方法

曹萬(wàn)鵬,羅云彬,史 輝

(北京工業(yè)大學(xué) 未來(lái)網(wǎng)絡(luò)科技高精尖創(chuàng)新中心,北京 100124)

1 引 言

今天,科研人員已經(jīng)提出各種成熟的數(shù)學(xué)分類(lèi)模型,諸如ID3,C4.5,SVM,樸素貝葉斯(Native Bayes),AdaBoost和K-最近鄰(k-Nearest Neighbor),ANN(人工神經(jīng)網(wǎng)絡(luò))等分類(lèi)算法,并基于上述思想,將它們應(yīng)用到面部識(shí)別[1,2]、筆跡驗(yàn)證[3,4]、數(shù)據(jù)分析[5,6]和醫(yī)學(xué)應(yīng)用[7,8]等不同領(lǐng)域.近年來(lái),基于SVM的分類(lèi)算法因其結(jié)構(gòu)簡(jiǎn)單、泛化能力強(qiáng)、學(xué)習(xí)和預(yù)測(cè)時(shí)間短、能實(shí)現(xiàn)全局最優(yōu)等卓越性能而應(yīng)用于諸多領(lǐng)域,特別是在處理小樣本、非線性和高維模式識(shí)別問(wèn)題上.

在SVM算法中,通過(guò)將原始樣本空間的非線性問(wèn)題轉(zhuǎn)化為高維空間中的線性問(wèn)題,可以成功地解決分類(lèi)問(wèn)題.這里,非線性變換是利用滿足Mercer條件的核函數(shù)實(shí)現(xiàn)的.在SVM模型設(shè)計(jì)中合適的核函數(shù)選擇和訓(xùn)練樣本權(quán)值設(shè)置都很重要,共同決定了分類(lèi)器性能的優(yōu)劣.尋找更為合適的核函數(shù),并為訓(xùn)練樣本設(shè)置更加合理權(quán)值等已成為研究熱點(diǎn).

近年來(lái),人們提出不同算法嘗試為SVM算法選取一個(gè)恰當(dāng)?shù)膯我缓撕瘮?shù).吳濤等基于可以將核函數(shù)結(jié)構(gòu)視為函數(shù)插值問(wèn)題這一假設(shè)通過(guò)訓(xùn)練樣本構(gòu)造合適的核函數(shù)[9].Wu等采用一種混合遺傳算法(HGA)優(yōu)化核函數(shù),進(jìn)而提高SVM算法模型的準(zhǔn)確性[10].You等使用三個(gè)主要指標(biāo):Fisher判別,Bregman散度和方差齊性從矩陣中抽取特征進(jìn)行核函數(shù)的選擇[11].Keerthi等人應(yīng)用雙線性方法遍歷核函數(shù)的參數(shù)集,實(shí)現(xiàn)核函數(shù)中參數(shù)的最優(yōu)設(shè)計(jì)[12].Maji等人設(shè)計(jì)了一種自適應(yīng)的支持向量機(jī)核函數(shù),達(dá)到了提高SVM分類(lèi)模型分類(lèi)性能的目標(biāo)[13].盡管單一核函數(shù)在某些情況下對(duì)于分類(lèi)模型的學(xué)習(xí)要求已經(jīng)足夠,但僅依靠單一核函數(shù)構(gòu)建SVM分類(lèi)模型經(jīng)常不能實(shí)現(xiàn)最佳分類(lèi)效果.當(dāng)前,研究人員越來(lái)越多地使用混合核函數(shù),并已經(jīng)證明將不同功能核函數(shù)組合在一起的方法可實(shí)現(xiàn)更優(yōu)SVM模型設(shè)計(jì),更好分類(lèi)性能[14].

對(duì)混合核函數(shù)的研究中,最常用的方法是結(jié)合全局核函數(shù)和局部核函數(shù)來(lái)構(gòu)造混合核函數(shù).Wu等[15]和Huang等[16]都選擇了這種方法,因?yàn)榛诰植亢撕瘮?shù)的學(xué)習(xí)能力和全局核函數(shù)的良好泛化能力所構(gòu)建混合核函數(shù)相對(duì)于單一核函數(shù)方法或一般組合核函數(shù)方法具有更好的性能.許多學(xué)者把RBF核函數(shù)和多項(xiàng)式核函數(shù)作為局部核函數(shù)和全局核函數(shù)進(jìn)行混合核函數(shù)的設(shè)計(jì),并將其成功地應(yīng)用于不同工作中,獲得了令人滿意的分類(lèi)效果[17-19].

一些研究者也采用了不同的方法構(gòu)建混合核函數(shù).Zhu等詳細(xì)分析了核函數(shù)設(shè)計(jì)對(duì)分類(lèi)性能的影響因素,基于Fisher特征與核函數(shù)矩陣校準(zhǔn)方法的結(jié)合,對(duì)單一核函數(shù)性能進(jìn)行預(yù)測(cè),并在此基礎(chǔ)上構(gòu)造了一種新的用于人臉識(shí)別的混合核函數(shù),取得了令人滿意的結(jié)果[20].Xie通過(guò)分析現(xiàn)有LS-SVM核函數(shù)并吸收RBF核函數(shù)和多項(xiàng)式核函數(shù)的優(yōu)點(diǎn)構(gòu)建混合核函數(shù),改進(jìn)了現(xiàn)有的LS-SVM算法[21].üstün等則采用了基于Pearson VII的通用函數(shù)(PUK),實(shí)驗(yàn)證明PUK核與標(biāo)準(zhǔn)核函數(shù)相比具有同等或更強(qiáng)大的映射能力,進(jìn)而導(dǎo)致同等或更好的SVM泛化性能[22].G?nen等人通過(guò)實(shí)驗(yàn)比較了現(xiàn)存的混合核函數(shù)方法,并證明了用混合核函數(shù)的方法在性能上要優(yōu)于單一核函數(shù)構(gòu)建SVM分類(lèi)模型的方法[23].

目前,同步研究在候選核函數(shù)中選取哪些核函數(shù),并且為這些核函數(shù)設(shè)置什么樣權(quán)值的文獻(xiàn)并不多見(jiàn).大多數(shù)混合核函數(shù)算法直接選擇RBF核函數(shù)和多項(xiàng)式核函數(shù)構(gòu)造混合核函數(shù),沒(méi)有進(jìn)行相應(yīng)的學(xué)習(xí)與分析,這不可避免的導(dǎo)致了不盡理想的分類(lèi)效果.而且大多數(shù)混合核函數(shù)的構(gòu)造方法往往缺乏有效的反饋機(jī)制來(lái)指導(dǎo)混合核函數(shù)的設(shè)計(jì),也很少考慮如何基于樣本特征為不同核函數(shù)設(shè)置更為合理的系數(shù).基于此,本文采用ACO算法實(shí)現(xiàn)混合加權(quán)核函數(shù)中相關(guān)核函數(shù)和對(duì)應(yīng)系數(shù)的優(yōu)化選取.此外,因?yàn)镾VM分類(lèi)模型最大分類(lèi)間隔決定了分類(lèi)的確定性和所學(xué)習(xí)分類(lèi)模型對(duì)后續(xù)樣本的潛在分類(lèi)性能,在SVM分類(lèi)模型的設(shè)計(jì)過(guò)程中,為進(jìn)一步提高分類(lèi)模型的分類(lèi)能力,本文基于訓(xùn)練樣本對(duì)SVM分類(lèi)模型最大分類(lèi)間隔的貢獻(xiàn)對(duì)訓(xùn)練樣本進(jìn)行自適應(yīng)權(quán)值設(shè)置.

本文第2節(jié)介紹了SVM算法和組合核函數(shù);第3節(jié)建立了基于當(dāng)前訓(xùn)練樣本特征的自適應(yīng)樣本加權(quán)算法;第4節(jié)根據(jù)SVM分類(lèi)原理設(shè)計(jì)了改進(jìn)的ACO算法,實(shí)現(xiàn)了優(yōu)化混合加權(quán)核函數(shù)的選擇;第5節(jié)完成了本文方法的實(shí)驗(yàn)驗(yàn)證和相應(yīng)的實(shí)驗(yàn)分析;第6節(jié)對(duì)本文工作進(jìn)行了總結(jié).

2 SVM算法與混合核函數(shù)原理介紹

SVM算法核心思想是尋找一個(gè)滿足分類(lèi)要求的最優(yōu)分類(lèi)超平面,具體的分類(lèi)原理如圖1所示.

給定訓(xùn)練集(xi,yi),i=1,2,…,N,x∈Rn,y∈{±1},超平面為w·x+b=0.為使分類(lèi)超平面正確分類(lèi)所有樣本并產(chǎn)生一個(gè)盡量大的分類(lèi)間隔,需滿足方程:

yi[(w·xi)+b]≥1,i=1,2,…,N

(1)

圖1 SVM算法結(jié)構(gòu)圖Fig.1 SVM algorithm structure diagram

因此,分類(lèi)間隔可表示為2/‖w‖,構(gòu)造最優(yōu)超平面的問(wèn)題則轉(zhuǎn)化為下列約束的最小值問(wèn)題:

(2)

這里,引入拉格朗日函數(shù),

(3)

公式(3)中,αi是拉格朗日系數(shù),且有αi>0.該約束優(yōu)化問(wèn)題由拉格朗日函數(shù)鞍點(diǎn)確定,優(yōu)化問(wèn)題的解滿足在鞍點(diǎn)處對(duì)w和b的偏微分為0.最后,QP(二次規(guī)劃)問(wèn)題轉(zhuǎn)化為相應(yīng)的對(duì)偶問(wèn)題:

(4)

這里,滿足,

(5)

通過(guò)計(jì)算,最優(yōu)權(quán)值向量w*和最佳偏置b*分別為:

(6)

那么,最優(yōu)分類(lèi)平面為:

w*·x+b*=0

(8)

最優(yōu)分類(lèi)函數(shù)為:

(9)

在這里,x∈Rn.當(dāng)樣本非線性可分時(shí),輸入特征空間通過(guò)非線性變換變換到一個(gè)高維特征空間.為了在高維空間中尋求最佳線性分類(lèi),通過(guò)定義適當(dāng)?shù)膬?nèi)積函數(shù)(核函數(shù))實(shí)現(xiàn)非線性變換.SVM算法可以用訓(xùn)練集和核函數(shù)完全描述,訓(xùn)練集和核函數(shù)是決定算法成敗的關(guān)鍵.因此,將訓(xùn)練樣本映射到其他空間,實(shí)現(xiàn)線性區(qū)分處理,分割效果取決于核函數(shù)的選擇.不同核函數(shù)K的選擇將導(dǎo)致完全不同的SVM算法,決定了所構(gòu)建分類(lèi)模型的分類(lèi)性能,在SVM算法中起著決定性作用.非線性SVM的最優(yōu)分類(lèi)函數(shù)如下:

(10)

這里,K(x·xj)表示核函數(shù).本文選取6個(gè)最常用的高性能核函數(shù)作為候選核函數(shù),公式具體如下:

1)多項(xiàng)式核函數(shù):

(11)

2)徑向基核函數(shù):

(12)

3)Sigmoid核函數(shù):

(13)

4)線性核函數(shù):

K(xi,xj)=xi·xj

(14)

5)傅里葉核函數(shù):

(15)

6)樣條核函數(shù)

K(xi,xj)=B2n+1(xi-xj)

(16)

那么,本文中混合加權(quán)核函數(shù)可以設(shè)計(jì)為:

K(xi,xj)=∑lclKl(xi,xj),l=1,2,…,6

(17)

同時(shí),為了確?；旌虾撕瘮?shù)不改變?cè)计ヅ涞暮侠硇?通常有接下來(lái)的約束公式[24]:

(18)

在這里,cl是核函數(shù)組合中第l個(gè)核函數(shù)的加權(quán)系數(shù),而Kl(xi,xj)表示6個(gè)候選核函數(shù)中的第l個(gè)核函數(shù).

3 基于當(dāng)前樣本對(duì)SVM最大分類(lèi)間隔貢獻(xiàn)度的自適應(yīng)樣本加權(quán)方法

為進(jìn)一步改進(jìn)對(duì)分類(lèi)模型的學(xué)習(xí),本文構(gòu)建了一種基于訓(xùn)練樣本特征的自適應(yīng)加權(quán)方法.為所有樣本設(shè)置統(tǒng)一的權(quán)值在SVM分類(lèi)模型構(gòu)建中顯然并不恰當(dāng),而基于當(dāng)前樣本特征為不同樣本設(shè)置不同權(quán)值可以提高分類(lèi)模型分類(lèi)性能.為此,本文提出一種自適應(yīng)樣本加權(quán)方法,它基于當(dāng)前樣本對(duì)SVM分類(lèi)模型最大分類(lèi)間隔的貢獻(xiàn),從提高分類(lèi)確定性和分類(lèi)模型對(duì)待檢測(cè)樣本正確分類(lèi)能力的角度構(gòu)造分類(lèi)模型.

如何為訓(xùn)練樣本設(shè)置自適應(yīng)加權(quán)系數(shù)是決定分類(lèi)器性能的關(guān)鍵.從SVM分類(lèi)原則出發(fā),SVM算法中最大分類(lèi)間隔決定了分類(lèi)的確定性程度.對(duì)后續(xù)待檢測(cè)樣本,更大的最大分類(lèi)間隔代表著更好的潛在正確分類(lèi)能力和更大的正確分類(lèi)冗余[25].因此,就分類(lèi)性能而言最大分類(lèi)間隔越大,分類(lèi)性能越佳.一般情況下,使被構(gòu)造分類(lèi)器最大分類(lèi)間隔增加的訓(xùn)練樣本,有利于分類(lèi)器潛在分類(lèi)能力的提升,應(yīng)為其設(shè)置更大權(quán)值.相反,使最大分類(lèi)間隔降低的訓(xùn)練樣本應(yīng)該指定較小權(quán)值.本文設(shè)計(jì)思想是計(jì)算訓(xùn)練樣本對(duì)最終SVM分類(lèi)器最大分類(lèi)間隔的貢獻(xiàn)度,進(jìn)而根據(jù)該信息為其設(shè)置恰當(dāng)權(quán)值.因此,訓(xùn)練樣本自適應(yīng)加權(quán)系數(shù)hj設(shè)計(jì)如下:

(19)

這里,假設(shè)do是基于全部訓(xùn)練樣本學(xué)習(xí)的SVM分類(lèi)模型而獲得的對(duì)應(yīng)最大分類(lèi)間隔,dj是通過(guò)從全部訓(xùn)練樣本中去除當(dāng)前訓(xùn)練樣本后獲得的新的最大分類(lèi)間隔,Δdj是do與dj的差值,Δdmax為所有Δdj中最大的最大分類(lèi)間隔增量.hj可通過(guò)以下步驟獲得:

步驟1.使用所有訓(xùn)練樣本,包括當(dāng)前樣本,基于SVM算法計(jì)算初始最大分類(lèi)間隔do;

步驟2.基于SVM算法,使用除當(dāng)前第j個(gè)樣本外剩余訓(xùn)練樣本計(jì)算得到最大分類(lèi)間隔dj;

步驟3.使用公式Δdj=do-dj計(jì)算由樣本j引起的最大分類(lèi)間隔的增量Δdj;

步驟4.重復(fù)步驟2和步驟3,直到獲得所有的M個(gè)訓(xùn)練樣本對(duì)最大分類(lèi)間隔的貢獻(xiàn)度;

步驟5.在Δdj中選擇最大的最大分類(lèi)間隔增量Δdmax;

步驟6.由公式(19),給出每個(gè)樣本的自適應(yīng)權(quán)值hj;

步驟7.結(jié)束加權(quán)系數(shù)的計(jì)算,并通過(guò)相應(yīng)的自適應(yīng)權(quán)值加權(quán)所有這些訓(xùn)練樣本.

通過(guò)訓(xùn)練樣本權(quán)值更新系數(shù)hj為導(dǎo)致SVM最大分類(lèi)間隔增量增大的樣本設(shè)置更高權(quán)值.因?yàn)橛欣谔岣叻诸?lèi)模型分類(lèi)性能的訓(xùn)練樣本通過(guò)自適應(yīng)加權(quán),獲得了更大權(quán)值,它們?cè)诜诸?lèi)器構(gòu)建中也將發(fā)揮更大作用,所以通過(guò)本文加權(quán)方法構(gòu)建的分類(lèi)模型比非加權(quán)方法獲得了更優(yōu)分類(lèi)性能.

4 基于改善的ACO參數(shù)設(shè)置算法的最優(yōu)混合加權(quán)核函數(shù)搜索

從一系列候選核函數(shù)中選擇恰當(dāng)?shù)暮撕瘮?shù),并為它們?cè)O(shè)置合理的權(quán)值對(duì)提高分類(lèi)器分類(lèi)性能異常關(guān)鍵.基于ACO算法在搜索參數(shù)空間中尋找最佳參數(shù)的優(yōu)勢(shì),本文采用ACO算法,并在算法參數(shù)設(shè)置中引入最大分類(lèi)間隔因素,為SVM分類(lèi)模型尋找最優(yōu)核函數(shù)組合及其對(duì)應(yīng)的核函數(shù)系數(shù).

ACO算法是將待求解計(jì)算問(wèn)題簡(jiǎn)化為搜索最佳路徑的概率算法.最初,該算法的設(shè)計(jì)是模擬螞蟻的行為,即它們?cè)诔惭ê褪澄镌粗g尋找一條最佳路徑的行為.從更廣泛的角度來(lái)看,ACO算法可用于執(zhí)行模板基的搜索算法[26].

ACO參數(shù)的合理設(shè)置對(duì)于為實(shí)際問(wèn)題所建立的數(shù)學(xué)模型尋找最佳系統(tǒng)參數(shù)異常重要.本文中,根據(jù)SVM分類(lèi)算法基本原理,設(shè)計(jì)更為合理和有針對(duì)性的ACO參數(shù)設(shè)置方案,用以決定選擇哪些核函數(shù)并為它們?cè)O(shè)置多大權(quán)值,進(jìn)而獲得更優(yōu)的混合加權(quán)核函數(shù).同時(shí),不同于其他參數(shù)設(shè)置方法,為充分反映分類(lèi)模型的潛在分類(lèi)能力和分類(lèi)確定性,將最大分類(lèi)間隔因素引入到ACO參數(shù)設(shè)置中,對(duì)其改進(jìn)如下:

(20)

這里,i和j分別表示路徑上節(jié)點(diǎn)i和j,ρij是路徑上節(jié)點(diǎn)i和j的信息素?fù)]發(fā)系數(shù),k表示第k條路徑,dk表示路徑k上的最大分類(lèi)間隔,dmax對(duì)應(yīng)著所有最大分類(lèi)間隔中的最大值,M是路徑數(shù).同時(shí),為進(jìn)一步反映和強(qiáng)調(diào)分類(lèi)間隔因素在ACO搜索中的重要性,啟發(fā)式信息ηij設(shè)置為:

ηij=1-ρij

(21)

從這兩個(gè)公式中可以看到,較大的最大分類(lèi)間隔對(duì)應(yīng)于一個(gè)較小的信息素?fù)]發(fā)系數(shù)和一個(gè)較高的轉(zhuǎn)移概率.很明顯,這會(huì)引導(dǎo)螞蟻(訓(xùn)練樣本)聚集向一條對(duì)應(yīng)較大最大分類(lèi)間隔的路徑.最終,基于這種改進(jìn)參數(shù)設(shè)置的ACO算法會(huì)獲得更優(yōu)的核函數(shù)組合及對(duì)應(yīng)加權(quán)系數(shù).本文所提出算法對(duì)應(yīng)流程圖如圖2所示:最后,根據(jù)改進(jìn)的ACO參數(shù)設(shè)置,將給出更為合理核函數(shù)組合和對(duì)應(yīng)加權(quán)系數(shù),具體步驟如下:

步驟1.初始化相關(guān)參數(shù):

1)設(shè)置全部螞蟻(訓(xùn)練樣本)的信息素τ初始值為常量,并將全部螞蟻放置于蟻巢;

2)設(shè)置ACO算法搜索的最大次數(shù)為Nmax;

3)設(shè)置螞蟻數(shù)為S,每個(gè)螞蟻包括n個(gè)參數(shù),對(duì)應(yīng)著螞蟻覓食路徑上的n個(gè)節(jié)點(diǎn).

步驟2.選擇每個(gè)“節(jié)點(diǎn)”(表示每一個(gè)不同的候選核函數(shù)和不同的加權(quán)系數(shù))作為一個(gè)路徑;

步驟3.記錄路徑中核函數(shù)、相應(yīng)系數(shù)的選擇,在到達(dá)目的地后得到混合加權(quán)核函數(shù),更新搜索次數(shù)N=N+1;

步驟4.根據(jù)學(xué)習(xí)得到的SVM模型,利用相應(yīng)的組合加權(quán)核函數(shù),計(jì)算分類(lèi)模型的分類(lèi)精度和最大分類(lèi)間隔;

圖2 算法流程圖Fig.2 Proposed method flow chart

步驟5.基于分類(lèi)精度和分類(lèi)間隔更新信息素τ,信息素τ更新如下:

(22)

轉(zhuǎn)移概率p更新如下:

(23)

步驟6.當(dāng)所有的螞蟻沒(méi)有收斂到一條路徑或搜索次數(shù)小于預(yù)設(shè)的最大迭代次數(shù)時(shí),繼續(xù)重復(fù)步驟2到步驟4;

步驟7.結(jié)束對(duì)核函數(shù)及其相應(yīng)權(quán)值的搜索,并給出基于當(dāng)前訓(xùn)練樣本的最優(yōu)核函數(shù)組合及相應(yīng)核函數(shù)系數(shù).

通過(guò)結(jié)合上文中提出的基于當(dāng)前樣本對(duì)最大分類(lèi)間隔貢獻(xiàn)的自適應(yīng)樣本加權(quán)方法和本部分提出的基于改進(jìn)ACO參數(shù)設(shè)置的最優(yōu)組合加權(quán)核函數(shù)選擇方法,學(xué)習(xí)SVM分類(lèi)模型,可獲得分類(lèi)性能更加卓越的SVM分類(lèi)模型.

5 實(shí)驗(yàn)驗(yàn)證與分析

在這部分中,通過(guò)一系列實(shí)驗(yàn)驗(yàn)證本文方法的分類(lèi)性能,實(shí)驗(yàn)使用中文筆跡樣本進(jìn)行驗(yàn)證,樣本來(lái)自于哈爾濱工業(yè)大學(xué)開(kāi)放手寫(xiě)文本庫(kù)HIT-MW[27].它提供來(lái)源于240個(gè)不同人的中文筆跡樣本,每個(gè)人筆跡為不同內(nèi)容,如圖3所示.

圖3 從開(kāi)放筆跡庫(kù)隨機(jī)選取的4份筆跡樣本Fig.3 Four Chinese handwriting samples randomly taken from open handwritten text library

同時(shí),為驗(yàn)證所學(xué)習(xí)分類(lèi)模型分類(lèi)性能,本文采用李昕的筆跡特征抽取算法[28],該方法經(jīng)驗(yàn)證對(duì)于提取筆跡細(xì)節(jié)特征具有很好性能.通過(guò)該方法從筆跡樣本中提取一系列微結(jié)構(gòu)特征作為樣本多維特征用于SVM分類(lèi)模型的學(xué)習(xí).然后,使用本文算法設(shè)計(jì)分類(lèi)器,通過(guò)5個(gè)有針對(duì)性的驗(yàn)證實(shí)驗(yàn),從多個(gè)角度對(duì)本文算法進(jìn)行了驗(yàn)證、分析.

第1個(gè)驗(yàn)證實(shí)驗(yàn)采用交叉驗(yàn)證方式對(duì)對(duì)應(yīng)不同最大分類(lèi)間隔的SVM分類(lèi)模型進(jìn)行驗(yàn)證,考察最大分類(lèi)間隔因素對(duì)SVM分類(lèi)模型分類(lèi)性能的影響.在樣本庫(kù)中,首先隨機(jī)選擇100個(gè)筆跡實(shí)例作為訓(xùn)練樣本并將其等分為10份.然后,使用這10組樣本采用不同算法分別學(xué)習(xí)SVM分類(lèi)模型,獲得10個(gè)分類(lèi)器,并求解它們所對(duì)應(yīng)的最大分類(lèi)間隔.另外,再選取100個(gè)筆跡樣本,等分為10份作為后續(xù)測(cè)試樣本.用這10個(gè)新構(gòu)建分類(lèi)器分類(lèi)測(cè)試樣本,計(jì)算它們對(duì)應(yīng)的平均分類(lèi)精度.

為增加實(shí)驗(yàn)的一般性,每次更換訓(xùn)練樣本、測(cè)試樣本,重復(fù)上述實(shí)驗(yàn)10次,可方便地獲得SVM分類(lèi)模型的最大分類(lèi)間隔與對(duì)應(yīng)分類(lèi)精度之間的關(guān)系.10個(gè)分類(lèi)器中,兩兩比較對(duì)應(yīng)不同最大分類(lèi)間隔的SVM分類(lèi)模型所獲得分類(lèi)精度.設(shè)某次進(jìn)行比較的兩個(gè)分類(lèi)器分別為Ci和Cj,由(Ci,Cj)表示,模型Ci對(duì)應(yīng)的最大分類(lèi)間隔di,Cj對(duì)應(yīng)的最大分類(lèi)間隔為dj,max(Δdij)表示兩分類(lèi)器對(duì)應(yīng)的較大最大分類(lèi)間隔與較小最大分類(lèi)間隔的差值,其值大于等于0,表1給出了對(duì)比結(jié)果.表1中,“獲勝”代表兩分類(lèi)器精度比較中,對(duì)應(yīng)較大最大分類(lèi)間隔的分類(lèi)器所獲得的分類(lèi)精度不小于對(duì)應(yīng)較小最大分類(lèi)間隔的分類(lèi)器所獲得的分類(lèi)精度;“失敗”則代表兩分類(lèi)器精度比較中,較大最大分類(lèi)間隔的分類(lèi)器所對(duì)應(yīng)分類(lèi)精度小于對(duì)應(yīng)較小最大分類(lèi)間隔的分類(lèi)器所對(duì)應(yīng)分類(lèi)精度.從表1可看到,對(duì)應(yīng)較大最大分類(lèi)間隔的分類(lèi)模型(max(Δdij)大于等于0)在分類(lèi)精度的45次比較中贏了42次.實(shí)驗(yàn)結(jié)果證明了具有較大分類(lèi)間隔的SVM分類(lèi)模型對(duì)后續(xù)未知測(cè)試實(shí)例具有更強(qiáng)分類(lèi)能力.

表1 分類(lèi)精度比較結(jié)果
Table 1 Comparison outcome on classification accuracy

進(jìn)行比較的兩分類(lèi)器max(Δdij)獲勝次數(shù)失敗次數(shù)(Ci，Cj)大于等于0423

為進(jìn)一步驗(yàn)證基于本文樣本加權(quán)方法所構(gòu)建SVM分類(lèi)模型對(duì)于待檢測(cè)樣本擁有更大的正確分類(lèi)確定性,根據(jù)上文方法多次重復(fù)勝負(fù)比較實(shí)驗(yàn),對(duì)比本文樣本加權(quán)方法與非樣本加權(quán)方法分別構(gòu)建的分類(lèi)模型的分類(lèi)精度高低.表2給出了采用這兩種方法構(gòu)建分類(lèi)模型的比較結(jié)果,可以看到,本文方法幾乎贏得了所有的比較.同時(shí),當(dāng)測(cè)試樣本數(shù)量增加時(shí),用本文算法學(xué)習(xí)的SVM分類(lèi)器獲勝面更大.這是因?yàn)閺脑黾覵VM分類(lèi)器最大分類(lèi)間隔的角度設(shè)計(jì)的樣本加權(quán)方法使所構(gòu)建分類(lèi)模型最大分類(lèi)間隔增加.當(dāng)訓(xùn)練樣本增多時(shí),這種改進(jìn)將更加明顯,進(jìn)而使所構(gòu)建SVM分類(lèi)模型與傳統(tǒng)方法相比具有更強(qiáng)正確分類(lèi)能力.

表2 加權(quán)方法對(duì)非加權(quán)方法基于分類(lèi)精度的獲勝率 (%)
Table 2 Classification accuracy win ratio (%)

分類(lèi)模型5樣本10樣本15樣本20樣本25樣本訓(xùn)練樣本加權(quán)方式構(gòu)建的分類(lèi)器模型94．2095．5197．7198．3798．73

在第2個(gè)測(cè)試實(shí)驗(yàn)中,從筆跡樣本庫(kù)中隨機(jī)選取100個(gè)樣本,等分為10份.然后,訓(xùn)練10組筆跡樣本獲得10個(gè)SVM分類(lèi)模型.每次,取其中的9個(gè)訓(xùn)練樣本訓(xùn)練分類(lèi)模型,把另外1個(gè)樣本作為測(cè)試樣本,重復(fù)10次,計(jì)算平均分類(lèi)精度.表3給出了使用本文樣本加權(quán)方法和非加權(quán)方法構(gòu)建的分類(lèi)模型對(duì)應(yīng)的平均分類(lèi)精度.

表3 樣本加權(quán)方法vs非樣本加權(quán)方法的分類(lèi)精度比較(%)
Table 3 Classification accuracy for the sample weighting method vs sample unweighting method (%)

方法MeanClassificationAccuracy樣本加權(quán)方法94．63非樣本加權(quán)方法92．86

從表3可以看到,用樣本加權(quán)算法學(xué)習(xí)到的分類(lèi)模型擁有更高分類(lèi)精度.實(shí)驗(yàn)結(jié)果證明,基于SVM最大分類(lèi)間隔增量為測(cè)試樣本設(shè)置權(quán)值系數(shù),因?yàn)閷?duì)應(yīng)較大最大分類(lèi)間隔增量的樣本被指定了更大權(quán)值,進(jìn)而導(dǎo)致該樣本在分類(lèi)模型構(gòu)建中發(fā)揮了更大作用,使對(duì)分類(lèi)模型的學(xué)習(xí)更傾向于提高SVM的最大分類(lèi)間隔,該方法有益于所構(gòu)建分類(lèi)模型分類(lèi)精度的改善,對(duì)后續(xù)待檢測(cè)樣本具有更強(qiáng)的正確分類(lèi)能力.

在第3個(gè)驗(yàn)證實(shí)驗(yàn)中,為驗(yàn)證在ACO算法參數(shù)設(shè)置中引入SVM最大分類(lèi)間隔因子對(duì)所構(gòu)建分類(lèi)器分類(lèi)性能的正向影響,基于兩種不同參數(shù)設(shè)置方法求解最優(yōu)核函數(shù)組合和對(duì)應(yīng)加權(quán)系數(shù).兩種方法共同的參數(shù)設(shè)置如下:信息素τ和Q(信息素強(qiáng)度)的初始值設(shè)置為10和100,最大迭代次數(shù)設(shè)置為500,α值(激勵(lì)因素),β(期望啟發(fā)式因子)分別設(shè)為1和5.不同設(shè)置為,第一個(gè)方法對(duì)最優(yōu)候選核函數(shù)和相應(yīng)參數(shù)的ACO搜索使用傳統(tǒng)方法,將信息素設(shè)置為與分類(lèi)精度相關(guān),其他參數(shù)設(shè)置為常量.在第二個(gè)ACO參數(shù)搜索中,使用公式(20)至(23)設(shè)置相關(guān)ACO參數(shù),包括揮發(fā)系數(shù)ρ,啟發(fā)信息η,信息素τ和轉(zhuǎn)換概率p.然后,分別根據(jù)兩個(gè)具有不同參數(shù)設(shè)置的ACO算法搜索混合核函數(shù),并比較由不同搜索學(xué)習(xí)的分類(lèi)模型的分類(lèi)精度.

另外,隨機(jī)選取50個(gè)筆跡樣本作為螞蟻,設(shè)置6個(gè)候選核函數(shù)(公式(11)-(16))和它們?nèi)靠赡軐?duì)應(yīng)系數(shù)(0,0.1,0.2,0.3,0.4,0.5,0.6,0.7,0.8,0.9,1)為ACO搜索路徑中的節(jié)點(diǎn).進(jìn)而,ACO中的每條路徑選擇對(duì)應(yīng)一個(gè)混合加權(quán)核函數(shù)方案的選取,如圖4所示.

圖4 本文ACO算法的簡(jiǎn)化示意圖Fig.4 Designed simplified ACO sketch map

這里,Ki表示候選核函數(shù),Wi表示核函數(shù)系數(shù),虛線表示路徑.通過(guò)兩種不同參數(shù)設(shè)置的ACO算法對(duì)候選核函數(shù)與其系數(shù)進(jìn)行搜索,獲得兩條不同路徑,代表著兩個(gè)不同的混合加權(quán)核函數(shù)選擇方案.用這兩個(gè)選擇方案分別學(xué)習(xí)SVM分類(lèi)模型,計(jì)算對(duì)應(yīng)分類(lèi)器的分類(lèi)精度.

實(shí)驗(yàn)中,第1種ACO算法命名為方法1,參數(shù)設(shè)置引入SVM最大分類(lèi)間隔因素.根據(jù)公式(20),最大分類(lèi)間隔越大,則信息素蒸發(fā)速度越慢.相應(yīng)地,啟發(fā)信息ηij更強(qiáng).第2種ACO算法命名為方法2,該方法不在參數(shù)設(shè)置中考慮最大分類(lèi)間隔因子.在相同條件下,使用上述兩方法搜索網(wǎng)絡(luò)中的最佳路徑.為了驗(yàn)證最大分類(lèi)間隔因素的引入對(duì)分類(lèi)模型正確分類(lèi)的能力的提升,這個(gè)實(shí)驗(yàn)使用不同數(shù)量的驗(yàn)證樣本.對(duì)應(yīng)結(jié)果顯示在表4和圖5中.表4給出了用兩種ACO參數(shù)設(shè)置方法構(gòu)建的分類(lèi)模型分類(lèi)精度的比較.實(shí)驗(yàn)結(jié)果展示出因?yàn)樗阉髦锌紤]了最大分類(lèi)間隔因素,使所構(gòu)建分類(lèi)模型在分類(lèi)精度上有了較大改善.

從圖5可以看到,相對(duì)于傳統(tǒng)的ACO參數(shù)設(shè)置方法,本文所提出參數(shù)設(shè)置方法的優(yōu)勢(shì)主要體現(xiàn)在通過(guò)學(xué)習(xí)所得的SVM模型對(duì)后續(xù)未知檢測(cè)樣本的正確分類(lèi)能力.這是因?yàn)锳CO算法中最大分類(lèi)間隔因子的引入改善了算法的優(yōu)化方向,使基于此方法所設(shè)計(jì)SVM分類(lèi)模型傾向于產(chǎn)生一個(gè)更大的最大分類(lèi)間隔,進(jìn)而提高模型正確分類(lèi)性能.

第4個(gè)驗(yàn)證實(shí)驗(yàn)討論了核函數(shù)加權(quán)方法對(duì)所構(gòu)建分類(lèi)模型分類(lèi)性能的影響.從樣本庫(kù)中隨機(jī)選取100個(gè)樣本并等量地將其分為10組.然后,通過(guò)訓(xùn)練10組樣本對(duì)SVM分類(lèi)模型進(jìn)行學(xué)習(xí),獲得10個(gè)分類(lèi)模型.每次,用其中9個(gè)訓(xùn)練樣本建立分類(lèi)模型,把另外1個(gè)樣本作為測(cè)試樣本.重復(fù)此過(guò)程10次,計(jì)算平均分類(lèi)精度.相同情況下,基于同樣步驟采用核函數(shù)系數(shù)加權(quán)方法和非加權(quán)方法分別構(gòu)建混合核函數(shù),并用上述不同混合核函數(shù)分別學(xué)習(xí)SVM分類(lèi)模型,求解對(duì)應(yīng)的平均分類(lèi)精度.

表4 不同訓(xùn)練樣本下本文提出ACO算法 vs 傳統(tǒng) ACO算法的分類(lèi)精度比較 (%)
Table 4 Classification accuracy for the proposed ACO vs traditional ACO from the different number of test samples (%)

精度5樣本10樣本15樣本20樣本25樣本30樣本35樣本方法194．4394．6595．1394．8894．3593．8994．67方法293．2893．6291．5791．9991．1489．1790．35

圖5 本文提出ACO算法 vs 傳統(tǒng) ACO算法Fig.5 Proposed method vs traditional ACO method

表5給出了分別用這兩種方法獲得的分類(lèi)精度,從表5看到,基于混合加權(quán)核函數(shù)構(gòu)建的分類(lèi)模型比非加權(quán)方法獲得了更好分類(lèi)效果.實(shí)驗(yàn)結(jié)果也反映出基于對(duì)最優(yōu)分類(lèi)性能的追求,有必要在混合加權(quán)核函數(shù)設(shè)計(jì)中為不同核函數(shù)賦予不同系數(shù).因?yàn)樵O(shè)置統(tǒng)一系數(shù)的混合核函數(shù)盡管實(shí)現(xiàn)了輸入特征空間到高維特征空間的變換,但這一變換并不是所有變換中最優(yōu)的變換,也不能實(shí)現(xiàn)最優(yōu)SVM分類(lèi)模型的學(xué)習(xí).因此,統(tǒng)一的系數(shù)設(shè)置明顯不夠合理,難以獲得滿意效果.

表5 核函數(shù)加權(quán)方法vs非加權(quán)方法的分類(lèi)精度比較(%)
Table 5 Classification accuracy for the kernel function weighting method vs unweighting method (%)

方法平均分類(lèi)精度核函數(shù)加權(quán)方法94．47核函數(shù)非加權(quán)方法93．03

對(duì)于第5個(gè)驗(yàn)證實(shí)驗(yàn),依然從樣本庫(kù)隨機(jī)選取100個(gè)筆跡樣本并分為等量的10組.然后,通過(guò)訓(xùn)練10組樣本對(duì)SVM分類(lèi)模型進(jìn)行學(xué)習(xí),獲得10個(gè)分類(lèi)模型.每次用不同數(shù)量訓(xùn)練樣本,重復(fù)該過(guò)程10次,計(jì)算平均精度.相同情況下,基于同樣步驟采用樣本加權(quán)方法學(xué)習(xí)分類(lèi)模型,用本文算法和另外3種核函數(shù)構(gòu)建算法分別學(xué)習(xí)分類(lèi)模型.3種方法分別為上文中介紹的Wu[9],Huang[16]和Xie[21]所提出方法.同時(shí),這4種方法一同用于分類(lèi)相同測(cè)試樣本以驗(yàn)證和比較它們的分類(lèi)性能.訓(xùn)練樣本數(shù)量按步長(zhǎng)1從4個(gè)增加到10個(gè),考察不同數(shù)量訓(xùn)練樣本下所構(gòu)建分類(lèi)模型性能.4種方法分類(lèi)精度差異效果顯示在表6和圖6.

表6 不同數(shù)量訓(xùn)練樣本下本文算法vs另外3種算法(%)
Table 6 Classification accuracy for the proposed method vs other three methods based on the different number of training samples (%)

分類(lèi)精度Xie方法Huang方法Wu方法Cao方法4訓(xùn)練樣本89．3189．0786．5789．925訓(xùn)練樣本91．3391．0490．5093．296訓(xùn)練樣本92．8692．4292．5994．317訓(xùn)練樣本93．2693．5693．1594．448訓(xùn)練樣本93．4093．7293．4594．559訓(xùn)練樣本94．1293．9793．3394．9910訓(xùn)練樣本94．2094．1493．4694．62

從表6可以看出,無(wú)論使用多少訓(xùn)練樣本,與其他3種核函數(shù)構(gòu)建方法相比,本文提出的方法具有更高分類(lèi)精度.即使在可獲得訓(xùn)練樣本較少的情況下,本文方法仍然可以訓(xùn)練出性能優(yōu)良的分類(lèi)器,并可取得令人滿意的分類(lèi)精度.

從圖6還可以看出,隨著訓(xùn)練樣本數(shù)的增加,各種方法的分類(lèi)精度均有不同程度的改善.當(dāng)樣本數(shù)繼續(xù)增加時(shí),分類(lèi)精度增加速度逐漸放緩.本文方法與其他3種方法相比,能更快速地達(dá)到較高分類(lèi)精度.當(dāng)訓(xùn)練樣本數(shù)超過(guò)5后,本文算法的精度變化已很小.顯然,本文算法的分類(lèi)性能明顯優(yōu)于其他方法,這是因?yàn)楸疚乃惴ㄊ菑腟VM的構(gòu)建原理和分類(lèi)原則出發(fā)設(shè)計(jì)的,從根本上提高了SVM分類(lèi)模型性能.

圖6 本文提出方法vs對(duì)另外3種方法Fig.6 Proposed method vs other three methods

通過(guò)上述5個(gè)有針對(duì)性的實(shí)驗(yàn)驗(yàn)證了本文算法的有效性,實(shí)驗(yàn)結(jié)果也證明了本文所提出方法的良好性能,并進(jìn)一步顯示出本文算法的有效性.

6 結(jié) 論

在本文中,提出了一種基于ACO算法的最優(yōu)混合加權(quán)核函數(shù)構(gòu)建方法和一種新的基于當(dāng)前樣本特征與SVM分類(lèi)模型工作原理的訓(xùn)練樣本權(quán)值設(shè)置方法.本文首先根據(jù)樣本對(duì)SVM分類(lèi)模型最大分類(lèi)間隔的貢獻(xiàn),建立了一種基于訓(xùn)練樣本特征的自適應(yīng)樣本加權(quán)方法.它基于SVM算法原理設(shè)計(jì),因此所構(gòu)建分類(lèi)模型分類(lèi)性能更強(qiáng).實(shí)驗(yàn)證明,通過(guò)不同權(quán)值設(shè)置,算法提高了正確分類(lèi)能力,有利于提高SVM分類(lèi)器對(duì)待檢測(cè)樣本的潛在正確分類(lèi)能力,進(jìn)而提高分類(lèi)器的整體分類(lèi)性能.

除樣本加權(quán)方法,本文還利用ACO算法尋找加權(quán)核函數(shù)組合的最佳方案.不同于其他ACO搜索算法,本文中ACO參數(shù)設(shè)置中引入了最大分類(lèi)間隔因素,從SVM算法原理上提高了對(duì)后續(xù)樣本正確分類(lèi)的能力,實(shí)驗(yàn)結(jié)果也驗(yàn)證了上述算法.同時(shí),改進(jìn)的參數(shù)設(shè)置因?yàn)榫C合考慮了分類(lèi)器學(xué)習(xí)中分類(lèi)精度和最大分類(lèi)間隔指標(biāo)因素,使所學(xué)習(xí)SVM分類(lèi)模型具有更佳的分類(lèi)性能.

[1] Khan N,Ksantini R,Ahmad I,et al.A novel SVM+NDA model for classification with an application to face recognition[J].Pattern Recognition,2012,45(1):66-79.

[2] Kasar M,Bhattacharyya D,Kim T.Face recognition using neural network:a review[J].International Journal of Security and Its Applications,2016,10(3):81-100.

[3] Hasseim A,Sudirman R,Khalid P.Handwriting classification based on support vector machine with cross validation[J].Engineering,2013,5(5B):84-87.

[4] He Z,You X,Tang Y.Writer identification of Chinese handwriting documents using hidden Markov tree model[J].Pattern Recognition,2008,41(4):1295-1307.

[5] Dhillon S,Kaur K.Comparative study of classification algorithms for web usage mining[J].International Journal of Advanced Research in Computer Science and Software Engineering,2014,4(7):137-140.

[6] Liu B,Blasch E,Chen Y,et al.Scalable sentiment classification for big data analysis using Na?ve Bayes classifier[C].IEEE International Conference on Big Data,2013:99-104.

[7] Bendi V,Surendra P,Venkateswarlu N.A critical study of selected classification algorithms for liver disease diagnosis[J].International Journal of Database Management Systems,2011,3(2):101-114.

[8] Raikwal J,Kanak S.Weight based classification algorithm for medical data[J].International Journal of Computer Applications,2014,107(21):1-5.

[9] Wu Tao,He Han-gen,He Ming-ke.Interpolation based kernel function′s construction[J].Chinese Journal of Computers,2003,26(8):990-996.

[10] Wu C,Tzeng G,Lin R.A Novel hybrid genetic algorithm for kernel function and parameter optimization in support vector regression[J].Expert Systems with Applications,2009,36(3):4725-4735.

[11] You D,Hamsici O,Martinez A.Kernel optimization in discriminant analysis[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2011,33(3):631-638.

[12] Keerthi S.Efficient tuning of SVM hyperparameters using radius/margin bound and iterative algorithms[J].IEEE Transactions on Neural Network,2002,13(5):1225-1229.

[13] Maji S,Berg A,Malik J.Efficient classification for additive kernel svms[J].IEEE Transaction on Pattern Analysis and Machine Intelligence,2013,35(1):66-77.

[14] Smits G,Jordan E.Improved SVM regression using mixtures of kernels[C].International Joint Conference on Neural Networks,2002,3:2785-2790.

[15] Wu F,Ding S.Twin support vector machines based on the mixed kernel function[J].Journal of Computers,2014,9(7):1690-1696.

[16] Huang H,Ding S,Jin F,et al.A novel granular support vector machine based on mixed kernel function[J].International Journal of Digital Content Technology & its Applic,2012,6(20):484-492.

[17] Zheng S,Liu J,Tian J.An efficient star acquisition method based on SVM with mixtures of kernels[J].Pattern Recognition Letters,2005,26(2):147-165.

[18] Yang X,Peng H,Shi M.SVM with multiple kernels based on manifold learning for breast cancer diagnosis[C].IEEE International Conference on Information and Automation,2013:396-399.

[19] Kavzoglu T,Colkesen I.A kernel functions analysis for support vector machines for land cover classification[J].International Journal of Applied Earth Observation and Geoinformation,2009,11(5):352-359.

[20] Zhu Y,Liu W,Jin F,et al.The research of face recognition based on kernel function[J].Applied Mechanics and Materials,2013,321-324(8):1181-1185.

[21] Xie J.Time series prediction based on recurrent LS-SVM with mixed kernel[C].Asia-pacific Conference on Information Processing,2009,1:113-116.

[22] üstün B,Melssen W,Buydens L.Facilitating the application of support vector regression by using a universal Pearson VII function based kernel[J].Chemometrics and Intelligent Laboratory Systems,2006,81(1):29-40.

[23] G?nen M,Alpaydm E.Multiple kernel learning algorithms[J].Journal of Machine Learning Research,2011,12:2211-2268.

[24] Wang G.Properties and construction methods of kernel in support vector machine[J].Computer Science,2006,33(6):172-174.

[25] Li Hang.Statistical learning method[M].Beijing:Tsinghua University Press,Beijing,2012.

[26] Nada M.System evolving using ant colony optimization algorithm[J].Journal of Computer Science,2009,5(5):380-387.

[27] Su T,Zhang T,Guan D.Corpus-based HIT-MW database for offline recognition of general-purpose Chinese handwritten text[J].International Journal on Document Analysis and Recognition,2007,10(1):27-38.

[28] Li Xin,Ding Xiao-qing.Writer identification based on improved microstructure features[J].Journal Tsinghua University (Sci & Tech),2010,50(4):595-600.

附中文參考文獻(xiàn)：

[9] 吳 濤,賀漢根,賀明科.基于插值的核函數(shù)構(gòu)造[J].計(jì)算機(jī)學(xué)報(bào),2003,26(8):990-996.

[25] 李 航.統(tǒng)計(jì)學(xué)習(xí)理論[M].北京:清華大學(xué)出版社,2012.

[28] 李 昕,丁曉青.基于改進(jìn)微結(jié)構(gòu)特征的筆跡鑒別[J].清華大學(xué)學(xué)報(bào)(自然科學(xué)版),2010,50(4):595-600.