基于遺傳算法的支持向量機(jī)分類算法

基于遺傳算法的支持向量機(jī)分類算法

張東東

(上海理工大學(xué) 光電信息與計(jì)算機(jī)工程學(xué)院,上海200093)

摘要針對(duì)現(xiàn)有部分支持向量機(jī)在多類分類過程中存在的數(shù)據(jù)不均衡性、對(duì)算法結(jié)構(gòu)依賴性強(qiáng)的問題,提出一種新的基于遺傳算法的支持向量機(jī)多類分類算法。以遺傳算法中的交叉作為支持向量機(jī)中類的選擇,以變異改善分類過程中的糾錯(cuò)能力,以適應(yīng)度函數(shù)作為最優(yōu)分類結(jié)果的確定。在不同特性的樣本集上進(jìn)行仿真測試,結(jié)果證明,該算法在類數(shù)較多的情況下,有更好的數(shù)據(jù)均衡性,在分類速度及準(zhǔn)確度上均有一定的優(yōu)越性。

關(guān)鍵詞遺傳算法;支持向量機(jī);多類分類

收稿日期:2015-04-18

作者簡介:張東東(1991—),男,碩士研究生。研究方向:故障診斷,圖像識(shí)別。E-mail:156848686@qq.com

doi:10.16180/j.cnki.issn1007-7820.2015.12.009

中圖分類號(hào)TP301.6文獻(xiàn)標(biāo)識(shí)碼A

Support Vector Machine Classification Algorithm Based on Genetic Algorithms

ZHANG Dongdong

(School of Optical-Electrical and Computer Engineering,Shanghai University for

Science and Technology,Shanghai 200093,China)

AbstractIn view of the some existing SVMS issues such as data disproportion and strong dependence on the algorithm structure in the process of multi-classification,a new SVM classification algorithm based on genetic algorithms is proposed.The new algorithm considers the crossover in the genetic algorithm as the choice of divisions in the SVM,improves the correction capability during classification by mutation and bases the optimal classification results on the fitness function.Simulation and tests are performed on sample sets with different characteristics and the result shows the algorithm has superiority in data balance,speed and accuracy of classification in the case of multi-classification.

Keywordsgenetic algorithm;SVM;multi-classification

支持向量機(jī)(SVM)[1]是一種機(jī)器學(xué)習(xí)方法,采用結(jié)構(gòu)風(fēng)險(xiǎn)最小化原則[2]代替?zhèn)鹘y(tǒng)統(tǒng)計(jì)學(xué)的基于大樣本的經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化原則。這種方法最初是針對(duì)兩類問題的分類而提出的,在面對(duì)實(shí)際問題中普遍存在的多類問題時(shí),將SVM進(jìn)行有效的應(yīng)用,已成為研究熱點(diǎn)。

因此,本文在對(duì)現(xiàn)有幾種SVM多類問題[3]的分類算法進(jìn)行簡單總結(jié)的基礎(chǔ)上,提出了一種新的基于遺傳算法[4]的SVM多類分類方法,并通過仿真和數(shù)據(jù)分析,得出新算法的結(jié)構(gòu)特點(diǎn)及性能的優(yōu)越性。

1多類支持向量機(jī)

當(dāng)前較為通用的方法是通過組合多個(gè)二值分類器來實(shí)現(xiàn)多類分類器的構(gòu)造,而SVM擴(kuò)展方法并不唯一,且目前沒有一種方法在性能上明顯優(yōu)于其他方法。常見的構(gòu)造方法[5-6]有:分解法、糾錯(cuò)輸出編碼支持向量機(jī)、基于決策樹的支持向量機(jī)等。

1.1分解法

(1)一對(duì)多算法[7]。該算法將一個(gè)n類分類問題轉(zhuǎn)化為n個(gè)二分類問題。當(dāng)類別數(shù)較大時(shí),某一類的訓(xùn)練樣本將遠(yuǎn)少于其他訓(xùn)練樣本總和,這種樣本不均衡將對(duì)測試精度產(chǎn)生明顯的影響。

該方法每個(gè)SVM只考慮兩個(gè)樣本,避免了樣本數(shù)據(jù)不均衡問題。但當(dāng)單個(gè)兩類分類器不規(guī)范時(shí),存在著不可分區(qū)域,分類器數(shù)目隨類數(shù)增加而迅速增加,決策速度減慢。

1.2糾錯(cuò)輸出編碼支持向量機(jī)

糾錯(cuò)編碼被用于分類器輸出的解碼,能夠解決多分類中的不可分區(qū)域問題[9]。如何根據(jù)問題確定碼本、選擇排練順序及分類效果受錯(cuò)誤碼相關(guān)性影響大仍有待進(jìn)一步探究,且對(duì)于類別較多的問題,處理效果不佳。

1.3基于決策樹的支持向量機(jī)

(1)有向無環(huán)圖支持向量機(jī)。將多個(gè)二元分類器組合成多元分類器。對(duì)于一個(gè)n元的分類問題,經(jīng)過n-1次排除可得到樣本所屬的類別。DDAG的結(jié)構(gòu)具有冗余性,但分類結(jié)果對(duì)節(jié)點(diǎn)排序依賴性很大,不同的排列順序與根節(jié)點(diǎn)選取會(huì)使分類結(jié)果產(chǎn)生不確定性。

(2)二叉樹支持向量機(jī)。在每個(gè)節(jié)點(diǎn)上進(jìn)行聚類,首先將所有類別分成兩個(gè)子類,再將子類劃分成兩個(gè)次級(jí)子類,如此循環(huán)得到一個(gè)倒立的二叉分類樹[10]。然而,若在某節(jié)點(diǎn)上發(fā)生分類錯(cuò)誤,則會(huì)將分類錯(cuò)誤延續(xù)到該節(jié)點(diǎn)的后續(xù)節(jié)點(diǎn)上。因而,分類錯(cuò)誤在越靠近根節(jié)點(diǎn)的地方發(fā)生,分類性能就越差。

2支持向量機(jī)分類算法的設(shè)計(jì)

遺傳算法[11]是一類借鑒生物界的進(jìn)化規(guī)律演化而來的隨機(jī)化搜索方法。其主要特點(diǎn)是直接對(duì)結(jié)構(gòu)對(duì)象進(jìn)行操作,不存在求導(dǎo)和函數(shù)連續(xù)性的限定;具有內(nèi)在的隱并行性和更好的全局尋優(yōu)能力;采用概率化的尋優(yōu)方法,能自動(dòng)獲取和指導(dǎo)優(yōu)化的搜索空間,自適應(yīng)地調(diào)整搜索方向,無需確定的規(guī)則。

基于遺傳算法以上特點(diǎn),因而將其引入到支持向量機(jī)多類問題的分類當(dāng)中。其分類過程如圖1所示,依照遺傳算法的流程,可分為以下幾個(gè)步驟:

(1)個(gè)體編碼。遺傳算法的運(yùn)算對(duì)象是表示個(gè)體的符號(hào)串,本題中采用的表示形式為無符號(hào)的位操作,每位都代表一個(gè)類別,低位表示基數(shù)小的類。例如:x=10110011,則表明選擇了1、2、5、6、8這些類。同理,其它類數(shù)的情況也按照上述規(guī)則進(jìn)行相應(yīng)編碼。

(2)初始群體的產(chǎn)生。遺傳算法是對(duì)群體進(jìn)行進(jìn)化操作,需要準(zhǔn)備搜索點(diǎn)的初始群體的數(shù)據(jù)。以8類數(shù)據(jù)樣本為例,群體規(guī)模取為2,則取為互補(bǔ)的兩種分類,即x1(11110000)和x2(00001111),必須確保每種數(shù)據(jù)類都被包含在分類的并集中。若總類別數(shù)為奇數(shù)類,則生成規(guī)則如圖2所示。

圖1　基于遺傳算法支持向量機(jī)分類流程圖

圖2　奇數(shù)類個(gè)體生成規(guī)則圖

兩個(gè)個(gè)體交集不為空集,可根據(jù)實(shí)際需要選取交集所包含的類。圖4選取的交集為第4類。因支持向量機(jī)分類必有結(jié)果,若省略其中一類,則該類失去判定過程,直接導(dǎo)致該類失效,因而將每一類都包含是有必要的,且需要兼顧避免數(shù)據(jù)出現(xiàn)不均衡的問題,這均是產(chǎn)生初始群體所需考慮的重要規(guī)則。

(3)適應(yīng)度計(jì)算。適應(yīng)度計(jì)算是用于評(píng)價(jià)個(gè)體優(yōu)劣程度與遺傳概率的一個(gè)過程。對(duì)于適應(yīng)度函數(shù),不需要滿足連續(xù)可微等條件,要求是對(duì)于輸入能夠計(jì)算出能加以比較的非負(fù)的結(jié)果。

(4)選擇運(yùn)算。本文為確保分類準(zhǔn)確度,不采取概率傳遞的形式進(jìn)行復(fù)制遺傳,而是通過支持向量機(jī)的二分類判定,對(duì)于判定結(jié)果繼續(xù)進(jìn)行適應(yīng)度計(jì)算,若A(x)值不為1,繼續(xù)對(duì)其編碼并進(jìn)行下一步操作。

對(duì)于總類別數(shù)為奇數(shù)類的個(gè)體,采用與初始群體分類一樣的規(guī)則。例:當(dāng)個(gè)體為1110000時(shí),與0000000交叉后產(chǎn)生的兩類子類個(gè)體,選取一組:1100000、01100000。

(6)變異運(yùn)算。對(duì)于11000000與00110000并集11110000之外的低四位所屬的類進(jìn)行變異,變異概率采取自適應(yīng)[12]的方式,算法運(yùn)行前期由于類數(shù)收斂較快,采取較高的變異概率規(guī)避錯(cuò)分的風(fēng)險(xiǎn),算法后期則采取較低的變異概率以達(dá)到算法最終的收斂?？衫煤瘮?shù)模型或模糊控制的模糊規(guī)則建立變異概率的數(shù)學(xué)模型。

變異操作用以減少其他支持向量機(jī)分類方法中容易出現(xiàn)的錯(cuò)分情況,對(duì)分類結(jié)果能夠進(jìn)行多次驗(yàn)證,提高了算法的冗余性和判別準(zhǔn)確率。

圖3　一種變異概率函數(shù)模型

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

對(duì)SVM多類問題分類方法不僅與樣本數(shù)據(jù)本身有關(guān),還與SVM中核函數(shù)形式以及其他參數(shù)的選取有關(guān),本文數(shù)據(jù)選取UCI數(shù)據(jù)庫中不同類別數(shù)、樣本數(shù)及特征向量數(shù)的不同樣本,使實(shí)驗(yàn)數(shù)據(jù)更加有代表性。并統(tǒng)一選取相同的SMO訓(xùn)練方法,選取RBF徑向基核函數(shù)進(jìn)行訓(xùn)練。

表1　待測數(shù)據(jù)表

(1)首先以D組數(shù)據(jù)為例,分析算法的運(yùn)算過程。針對(duì)D組數(shù)據(jù),采用無符號(hào)編碼,選用的交叉概率為1,即交叉是必然發(fā)生的,對(duì)變異概率則依表2所示,采用簡單的對(duì)應(yīng)規(guī)則。

表2　變異概率表

針對(duì)其他多類情況,也可根據(jù)具體情況設(shè)計(jì)隸屬度函數(shù)對(duì)變異概率進(jìn)行模糊分類。將D組數(shù)據(jù)進(jìn)行3次重復(fù)調(diào)用到新算法中運(yùn)行,可得到3組算法運(yùn)行次數(shù)與適應(yīng)度的值。圖4相對(duì)應(yīng)的變異情況與表3相對(duì)應(yīng),相同數(shù)據(jù)3次運(yùn)行步數(shù)不相同,但最終均在A(x)=1時(shí)算法結(jié)束。

圖4　算法適應(yīng)度趨勢圖

運(yùn)行次數(shù)第1次第2次第3次1000210131104001510160-17--0

表3中,1表示變異;0表示未發(fā)生變異;“-”表示算法運(yùn)行結(jié)束。

由圖4和表3可得:1)對(duì)相同樣本數(shù)據(jù)進(jìn)行分類,分類次數(shù)受變異次數(shù)的影響而不同,進(jìn)而使算法運(yùn)行次數(shù)、運(yùn)行時(shí)間有所差異;2)分類結(jié)果相同,均將收斂到適應(yīng)度為1,但其分類的過程不同;3)第3次曲線在適應(yīng)度值為2時(shí)陷入局部極小值,因此在算法分類后期,即剩余類別數(shù)較少時(shí),降低變異的概率是非常有必要的。

(2)對(duì)A、B、C、D這4組測試數(shù)據(jù)進(jìn)行測試。為保證實(shí)驗(yàn)結(jié)果的可靠性,對(duì)每組測試進(jìn)行重復(fù)性測試,本文對(duì)每組測試均進(jìn)行了6次重復(fù)測試,采集實(shí)驗(yàn)結(jié)果并取其均值,測試集所得測試時(shí)間長短即可反映出算法測試速度的快慢。

表4　測試數(shù)據(jù)時(shí)間與準(zhǔn)確率表

表4中數(shù)據(jù)為A/B格式,其中A表示判定分類時(shí)長,B表示用百分制統(tǒng)計(jì)的算法的準(zhǔn)確度?！?”表示判定類別時(shí)間過短,給予忽略。

根據(jù)實(shí)驗(yàn)結(jié)果,對(duì)數(shù)據(jù)進(jìn)行分析可得:1)OVR測試速度較慢,OVO在類別多的情況下測試速度也較慢;2)DAG算法測試速度最快,且準(zhǔn)確率也相對(duì)較高;3)基于遺傳算法的向量機(jī)兼顧了速度與準(zhǔn)確率。分類速度快,且準(zhǔn)確率高,因而在類別數(shù)多、對(duì)準(zhǔn)確率要求高的場合中具有一定的優(yōu)越性。

綜上所述,基于遺傳算法支持向量機(jī)充分利用了遺傳算法結(jié)構(gòu)的優(yōu)點(diǎn),將其運(yùn)用到分類當(dāng)中,且分類具有較好的精度及速度等優(yōu)勢。

4結(jié)束語

針對(duì)支持向量機(jī)多類一些分類算法在分類過程中存在的數(shù)據(jù)不均衡及對(duì)分類結(jié)構(gòu)依賴重且缺乏糾錯(cuò)的能力,對(duì)這些原因進(jìn)行分析,考慮到支持向量機(jī)二分類的特點(diǎn),本文結(jié)合遺傳算法的一些特性,并將其交叉、變異的結(jié)構(gòu)特性,合理地運(yùn)用到支持向量機(jī)多類問題的分類當(dāng)中,避免了分類過程對(duì)算法結(jié)構(gòu)的依賴性。

根據(jù)實(shí)驗(yàn)仿真證明,基于遺傳算法的支持向量機(jī)分類算法結(jié)構(gòu)具為靈活的特點(diǎn),在保證運(yùn)行速度的同時(shí),確實(shí)能使分類準(zhǔn)確度更高,分類結(jié)果更為可靠。

參考文獻(xiàn)

[1]Friedman J H.Another approach to polychotomous classification[R].Palo Alto:Stanford University,1996.

[2]Krebel U.Pairwise classification and support vector machines[M].Cambridge,USA:The MIT Press,1999.

[3]Cutzu F.Lecture notes in computer science[M].Berlin,Heidelberg:Springer,2003.

[4]Golberg D E.Genetic algorithms in search,optimization,and machine learning[M].New York:Addion Wesley,1989.

[5]徐勛華,王繼成.支持向量機(jī)的多類分類方法[J].微電子學(xué)與計(jì)算機(jī),2004,21(10):149-152.

[6]Su H C,Lin C,A comparison of methods for multi-class support vector machines[J].IEEE Transactions on Neural Networks,2002,13(2):415-425.

[7]Vapnik V,Ladimir N.The nature of statistical learning theory[M].NewYork:Springer-Verlag,2000.

[8]Kreβel U H.Pairwise classification and support vector machines[M].CA USA:Advances in Kernel Methods,1998.

[9]Dietterich T G,Bakiri G.Solving multi-class learning problems via error-correcting output codes[J].Journal of Artificial Intelligence Research,1995(2):263-286.

[10]Fei B,Liu J B.Binary tree of SVM:a new fast multiclass training and classification algorithm[J].IEEE Transactions on Neural Net-Works,2006,17(3):696-704.

[11]戴朝華,朱云芳,陳維榮.云自適應(yīng)遺傳算法[J].控制理論與應(yīng)用,2007,24(4):646-650.

[12]陳世哲,劉國棟,浦欣.基于優(yōu)勢遺傳的自適應(yīng)遺傳算法[J].哈爾濱工業(yè)大學(xué)學(xué)報(bào),2007,39(7):1021-1024.