基于遺傳算法的svm決策樹生成算法

基于遺傳算法的svm決策樹生成算法

1基于遺傳算法的svm決策樹多分類方法支持向量機（svm）用于處理多類別分類是svm研究的重點問題之一。目前提出的svm分類方法可分為兩種類型：一次性求解法和分解重建法。一次性解算法由韋恩等人在1998年首次提出。在所有訓練樣本中，解決了一個大型二次規(guī)劃問題，并分別從所有樣本中分開了評論。從那以后，李昆侖等人引入了模糊的成員函數(shù)，這提高了對評論結果的影響，并減少了噪聲對排序結果的影響。然而，總的來說，由于該方法變量多、計算復雜性高，尤其是在較高的類別數(shù)量上，其訓練速度低，分類精度低，其實用性差。分解重建方法是將多類分類問題轉換為三種分類問題，采用一定的策略將兩個類的分類結合起來，實現(xiàn)多分類的方法。該方法的優(yōu)點是分類精度，但缺點是在k分類問題上，需要進行k（k-1）/2的基本svm，并且分類需要按照投票方法的組合策略進行多次分類。評分的優(yōu)點是分類精度，但缺點是在k分類問題上，有必要通過k（k-1）/2的基本svm進行分類，并使用基于投票方法的組合策略對其進行多次分類。該方法的優(yōu)點是分類精度，但缺點是在k分類問題上，有必要通過k（k-1）/2的基本svm進行分類。分類需要按照所有訓練的svm進行。分類是復雜的，分類效率低。使用“最小”方法來訓練所有svm。該方法所需的基本svm比1-a-1的方法要好得多。1-a-r使用“一對”的方法來訓練所有svm，并使用“最大輸出”法對其進行分類。當樣本數(shù)較大時，訓練速度非常緩慢。同時，該方法的分類也需要遵守所有k個svm，效率也不高。t-svm和dag-svm采用決策樹的聯(lián)合分類結構。在每個決策節(jié)點中，t-svm采用“一對”訓練方法，而dag-svm采用“單方面”訓練方法。由于引入決策樹，所培基本svm顯著減少，分類時不需要所有訓練的svm，培訓和分類的效率顯著提高。然而，這兩種多分類方法。本文提出一種基于遺傳算法的SVM決策樹多分類方法,在決策樹的每個決策節(jié)點利用遺傳算法進行兩分類決策優(yōu)化,最終自動生成最優(yōu)(或近優(yōu))決策樹.由于GA優(yōu)化的引入,使得決策樹的結構具有自適應性,在保證訓練和分類效率的同時,使分類性能達到最優(yōu)(或近優(yōu)).理論分析和實驗結果表明,新方法比傳統(tǒng)的DT-SVM、DAG-SVM方法有更高的分類精度,比經(jīng)典的1-a-1、1-a-r有更高的訓練和分類效率.2最優(yōu)分類面求解為了使本文具有自包含性,本節(jié)對支持向量機(SVM)的相關理論進行簡要介紹.SVM是從線性可分的二分類問題發(fā)展而來的,其基本思想是尋找兩類樣本的最優(yōu)分類面,使得兩類樣本的分類間隔(margin)最大.以圖1所示為例:圖中,實心點和空心點分別代表兩類樣本,H為分類線,H1和H2分別為各類中離分類線最近的樣本且平行于分類線的直線,它們之間的距離叫做分類間隔(margin).所謂最優(yōu)分類線就是要求分類線不但能將兩類正確分開,而且使分類間隔最大.不失一般性,設訓練樣本(xi,yi),i=1,2,…,l,x∈Rn,y∈{+1,-1},l為樣本數(shù),n為輸入維數(shù).在線性可分的情況下將兩類樣本完全分開的超平面為:w·x+b=0(1)使分類間隔最大的超平面即為最優(yōu)分類面,為此,需要求解二次規(guī)劃問題:min|w|2/2s.tyi(w?xj+b)-1≥0,i=1,2,?,l(2)min|w|2/2s.tyi(w?xj+b)?1≥0,i=1,2,?,l(2)當訓練樣本集線性不可分時,需引入非負松弛變量ζi,i=1,2,…,l,求解最優(yōu)分類面問題為:min|w|2/2+Cmin|w|2/2+Cl∑i=1∑i=1lζis.tyi(w·xj+b)≥1-ζi,ζi≥0,i=1,2,…,l(3)式中,C為懲罰參數(shù);C越大表示對錯誤分類的懲罰越大.通過Lagrange乘子法求解上述優(yōu)化問題,得最優(yōu)決策函數(shù):f(x)=sgn[l∑i=1yiαi(x?xi)+b](4)其中α為Lagrange系數(shù).在對輸入測試樣本x進行測試時,由式(4)確定x的所屬類別.根據(jù)K-T條件,上述優(yōu)化問題的解必須滿足:αi(yi(ω·x+b)-1)=0(5)因此,對于多數(shù)樣本αi將為零,取值不為零的α*0對應的樣本即為支撐向量,他們通常只是全體樣本中的很少一部分.這樣,僅需要少量支撐向量即可完成正確的樣本分類.當樣本集非線性時,可把樣本x映射到某個高維空間H,并在H中使用線性分類器.根據(jù)Mercer條件,采用不同內(nèi)積函數(shù)K(xi·xj)就可實現(xiàn)非線性的線性分類.K(xi·xj)稱為核函數(shù),此時相應的最優(yōu)決策函數(shù)變?yōu)?f(x)=sgn[l∑i=1yiαiΚ(x?xi)+b](6)3組合多分類策略的關鍵根據(jù)分解重構法思想,一個復雜的多類問題可以劃分為多個兩類問題來解決.而采取決策樹的組合分類策略已被證明是一種高效的多分類組合方法.但不同的決策樹結構會對分類精度產(chǎn)生不同的影響,而且這種影響有可能產(chǎn)生“誤差積累”現(xiàn)象.理論上講,對K類問題,所有可能構造的嚴格二叉樹的數(shù)目為:Nk=Κ-1∏i=1(2·i-1)(7)其中K≥3.因此,如何構造具有最優(yōu)(或近優(yōu))分類性能的二叉決策樹就成為SVM決策樹組合多分類策略的關鍵.傳統(tǒng)的DT-SVM方法和DAG-SVM方法對此均沒有進行深入研究.本節(jié)采用遺傳算法,以類間分類間隔(margin)最大為準則,在每個決策節(jié)點將多類訓練樣本劃分為兩類進行訓練,使兩個子類間的可分性盡可能強,以構造合理的樹結構,最終生成最優(yōu)(或近優(yōu))的決策樹.3.1遺傳計算方法的設計3.1.1類別編碼的編碼參數(shù)編碼是實現(xiàn)GA的關鍵.為了提高搜索效率,本文采用實值編碼的策略來實現(xiàn)原始訓練樣本集類別的編碼.決策樹根節(jié)點的染色體的編碼為:{1,2,…,K},其中K≥3為原始訓練樣本集的類別總數(shù),染色體中每個基因對應的是原始訓練樣本集的類別編號;對于根節(jié)點以下的子節(jié)點,根據(jù)其父節(jié)點的劃分結果,剔除父節(jié)點染色體中本節(jié)點不包含的類別對應的基因,形成新的染色體.3.1.2初始種群的生成采用實值編碼,解空間與染色體空間重合.考慮到種群數(shù)目過大不僅增加GA運算時間,而且會使種群形態(tài)過于分散,從而使算法收斂困難,所以我們選擇種群規(guī)模的大小為訓練樣本的30%.在解空間中隨機產(chǎn)生初始種群,并使其均勻分布于解空間.3.1.3svm分類算法分類間隔我們的目標是在每個決策節(jié)點將原始多類訓練樣本集劃分為兩類,并且使分類間隔最大.因此選擇SVM分類算法的分類間隔作為GA適應度函數(shù).根據(jù)SVM理論,兩類樣本的最大分類間隔為:margin=2/‖w*‖(8)其中:w*=n∑i=1α*iyixi(9)3.1.4種群遺傳本構模型遺傳操作是實現(xiàn)尋優(yōu)的關鍵,為了使染色體完整地包含當前決策節(jié)點訓練樣本所屬的類別種類,又避免染色體基因出現(xiàn)重復(該情況會使劃分出現(xiàn)交疊),本文只采用了選擇操作算子和變異操作算子.(1)選擇.選擇算子的作用是從上一代的遺傳結果中以一定概率繁殖適應度較大的個體進入下一代的遺傳操作.若個體ai的適應度函數(shù)為fit(ai),種群規(guī)模為pop-size,則選中ai為下一代個體的概率為:P(ai)=pop-size×fit(ai)/pop-size∑j=1fit(aj)(10)顯然適應度高的個體,繁殖的下一代數(shù)目較多;而適應度較小的個體,繁殖的數(shù)目較小,甚至被淘汰.(2)變異.為了在遺傳操作初期取得較大的變異算子以維持種群的多樣性,防止出現(xiàn)早熟現(xiàn)象;在算法已接近最優(yōu)解鄰域時,減小變異算子,確保其局部搜索能力,本文采用如下自適應變異概率:Ρm=exp(-1.5×0.5t)/pop-size×√L(11)其中:t是進化代數(shù),L是染色體長度.此外,為了防止同一條染色體中相同基因重復出現(xiàn),染色體中某一基因座上的基因發(fā)生變異時,變異后的基因編碼對應的基因座上的基因應相應地變換為變異基因座上的原基因編碼.例如,8分類問題的某一原始染色體編碼如圖2(a)所示,若第二基因座上的基因發(fā)生變異,變異后的基因編碼為7,則最終變異操作得到的新染色體如圖2(b)所示:3.2所屬類別劃分基于遺傳算法的SVM決策樹生成算法可描述如下:步驟1:將全部訓練樣本集所屬類別按實值編碼策略進行編碼,并在根節(jié)點調(diào)用GA將原始訓練樣本所屬類別劃分為兩類.步驟2:判斷各子節(jié)點是否只包含一類樣本,若是轉步驟4,反之轉步驟3.步驟3:對包含兩類以上樣本的子節(jié)點,剔除其父節(jié)點染色體中本子節(jié)點不包含的類別對應的基因,形成新的染色體,并調(diào)用GA將本節(jié)點的樣本所屬類別劃分為兩類.轉步驟2.步驟4:結束循環(huán),生成最優(yōu)(或近優(yōu))決策樹.需要說明的是,GA是一種啟發(fā)式搜索算法,因此并不能保證任何情況下生成的決策樹一定是最優(yōu)的,有可能是近優(yōu)的.4算法的復雜和執(zhí)行時間的分析4.1svm分類判斷SVM多分類分解重構法的基本SVM訓練方法和組合策略決定了分類器的訓練及分類復雜程度.對于K分類問題,本文提出的方法與常見的SVM多分類分解重構法訓練及分類復雜度的比較見表1.由表1可見,對于基本SVM的訓練,1-a-1與DAG采用“一對一”的方法,需要訓練的SVM最多,且隨類別數(shù)K的增加成平方指數(shù)增加;1-a-r采用“一對其余”的方法,訓練的復雜程度大大減少;DT-SVM和GADT-SVM由于采用了樹結構,訓練的復雜程度最小.在分類判斷時,1-a-1、1-a-r都需要遍歷所有訓練的SVM,效率很低;DAG采用了有向無環(huán)圖結構,分類所需的平均SVM個數(shù)有所減少;DT-SVM采用的是固定結構的二叉樹策略,分類所需的平均SVM個數(shù)進一步減少;本文提出的GADT-SVM采用的決策樹由GA根據(jù)具體情況自適應生成,其分類判斷的最壞情況等于DT-SVM所需的SVM數(shù),具有最高的分類效率.4.2dt-svm方法的分類測試支持向量機的訓練時間與樣本集的大小成超線性關系,T=cka,其中c為比例常數(shù),a為一常數(shù),k為訓練樣本集大小.對于基于分解重構法的支持向量機學習算法來說,a≈2,因此,SVM的訓練時間取決于參與訓練的樣本的數(shù)量多少.設模式類別數(shù)為K≥3,每類樣本數(shù)相等.對于標準的1-a-r方法,需訓練K個SVM,總的訓練時間為:T1-a-r=cKka.對于DT-SVM,雖然也采用“一對其余”的模糊類方法,但隨著樹的高度的增加,參與訓練的樣本數(shù)在逐級減少.設決策樹根節(jié)點高度為0,則高度為i(i=0,1,2,…,K-2)的決策點訓練樣本數(shù)為:k(K-i)/K,DT-SVM總的訓練時間為:TDT-SVM=Κ-2∑i=0c[k(K-i)/K]a.對于1-a-1和DAG方法,需要訓練K(K-2)個SVM,每個SVM的訓練樣本數(shù)為2k/K,總的訓練時間為Τ1-a-1=ΤDAG=cΚ(Κ-1)2(2kΚ)a≈2a-1cΚ2-aka.當a≈2時,這兩種方法的訓練時間與類別數(shù)幾乎無關.對于本文提出的GADT-SVM方法,訓練時間由兩部分組成,一是GA在每個決策節(jié)點對樹結構進行優(yōu)化的時間;二是優(yōu)化結束后各個決策節(jié)點基本SVM的訓練時間.對優(yōu)化結束后各決策節(jié)點基本SVM訓練時間,其最壞情況的樹結構與DT-SVM決策樹的結構相同,即每次決策分類,僅將訓練樣本中的一類與其余類劃分開來;額外的時間開銷來自GA對樹結構的自動優(yōu)化.但對具體的分類問題,決策樹結構的優(yōu)化過程通常是離線進行,并且一旦確定,對該問題就不再改變.因此,以增加離線優(yōu)化時間為代價換取SVM決策樹在線的最優(yōu)(或近優(yōu))分類性能是可行的.至于以上方法的分類測試時間,由分類所需遍歷SVM數(shù)目和每個SVM支持向量(SV)的數(shù)量共同決定,這一方面與組合分類策略有關,一方面與SVM的參數(shù)優(yōu)化有關,本文不進行深入研究.一般來說,分類所需遍歷SVM的平均個數(shù)越少,每個SVM的SV個數(shù)越少,分類時間越短;反之則越長.5dag-svm分類方法的對比A,B,C}、4分類{A,B,C,D}、6分類{B,C,D,E,F,G},7分類{C,D,E,G,H,I,J}和10分類{A,B,C,D,E,F,G,H,I,J}5種情況進行實驗.對于每類,在數(shù)據(jù)集中任取40個樣本作訓練樣本集,100個樣本為測試樣本集.為了便于比較,所有的基本SVM均采用徑向基核函數(shù):K(x,xi)=exp{-|x-xi|2/(2·σ2)},σ=5;懲罰參數(shù)取C=2.根據(jù)前面討論的算法,GADT-SVM對5種多分類情況生成的決策樹如圖3(a)～(e)所示.對DT-SVM,在每個決策節(jié)點隨機將訓練樣本分成兩類進行訓練;對DAG-SVM,在每個決策節(jié)點隨機取兩類進行訓練表.表2列出了5種方法分別在5種分類情況下各SVM的平均支持向量數(shù)目(#SV)和測試所需遍歷SVM的平均數(shù)目(#SVM):5種方法在不同分類情況下的分類精度、基本SVM訓練時間、平均分類時間如圖4所示:由圖4(a)可見,隨著分類類別數(shù)的增加,所有方法的分類精度都成下降趨勢,其中本文方法的精度在3分類、4分類、6分類時高于經(jīng)典的1-a-r和1-a-1方法的精度,在7分類、10分類時與其相當,而其訓練時間和分類時間則分別比1-a-r和1-a-1大大減少(見圖4(b)、(c));在所有5種分類情況下,經(jīng)本文方法優(yōu)化后的SVM決策樹分類精度均高于未經(jīng)優(yōu)化的DT-SVM和DAG-SVM方法的分類精度.在圖4(b)中,1-a-r由于每次訓練都需要所有的樣本參與,故其訓練時間最長;1-a-1/DAG-SVM雖訓練復雜,但每次訓練只需要兩類樣本參與,其訓練時間反而最短,且與類別的變化關