《技創(chuàng)實踐論文作設計報/

學期

計

09

支向機類類法究摘提出一種新的基于二叉樹結構的支持向(SVM)多分類算法法解決了現(xiàn)有主要算法所存在的不可分區(qū)域問題了獲得較高的推廣能力須樣本分布廣的類處于二叉樹的上層節(jié)點才能獲得更大的劃空問以該算法采用最小超立方體和最小超球體類包含作為二叉樹的生成算法。實驗結果表明，該算法具有一定的優(yōu)越性。關詞支持向量機；多類分類；二叉樹；多類支持向量機Themulticlassmethodsonbinaryare．newmethodscanresolveunclassifiableregionproblemsintheconventionalmulticlassSVM．maintainhighgeneralizationtheclassshouldbeseparatedatuppernodesofabinary．a(chǎn)ndhypersphereclassleastcoversareusedtoberulesofconstructingbinary．NumericalexperimentresultsshowthatthemulticlassSVMmethodsaresuitableforpractical．SupportvectormachinesMulticlassBinaryMulticlasssupportvectormachines一基于叉樹多SVM基于二叉樹的多類是將所有類別分成兩個子類，再將子類進一步劃分成兩個次級子類如此循環(huán)下去直到所有的節(jié)點都只包含一個單獨的類別為止此節(jié)點也是決策樹中的葉子該方法將原有的多類題同樣分解成了一系列的兩類分類問題中兩個子類間的分類函數(shù)采用．叉方法可以避免傳統(tǒng)方法的不可分情況，并且只需構造k-1個分類器，測試時并不一定需要計算所有分類器判別函數(shù)，從而可節(jié)省測試時間．二叉樹的結構對整個分類模型的分類精度有較大的影響1是個4類題的不同的二叉樹法構造示意圖．在圖1(a)中第個割是由第1類和第，第，4類成，第個分割面是由第2類和第4類成一個分割面是由第類和第類構成圖1(b)的分割順序是第2類，第1類第3類．從此例可看出，分割順序不一樣，每個類的分割區(qū)域也不同．因此，此多類SVM方法的每個類的區(qū)域依賴于二叉樹的結構，主要是二樹節(jié)點所代表的二值分器的位置．二又樹的結構有兩種一種是在個內節(jié)點處一個類與剩下的類構造分割面一種是在內節(jié)點處可以是多個類多個類的分割文只考慮前一種情況即次分割只分割出一個類．基于二叉樹的多類SVM，在測試段類似，根節(jié)點開始計算決策

函數(shù)根值的正負決定下一節(jié)如下去，直到到達某一葉節(jié)點為止葉點所代表的類別就是測試樣本的所屬類別．從面的分析可看出，越上層節(jié)點的分類性能對整個分類模型的推廣性影響越大因此生成二叉樹的過程中該讓最易分割的類最早分割出來即二叉樹的上層節(jié)點處分割于此本文提出了根據(jù)訓練樣本在屬性空間的幾何分布情況來生成二又樹的方法，從而建立一個推廣性高的多類VM分類模型．由于支持向量機的思想是在樣本的屬性空間中構造最優(yōu)超平面，線性SVM的屬性空間等價于輸人空間，但非線性的SVM卻法得到具體的屬性空間表達式．事實上，樣本在輸入空間中的物理聯(lián)系在屬性空間也同樣存在．所以，只需在輸入空間中考慮樣本的幾何分布．二改進多分二樹法二叉樹多類分類法的每個類的區(qū)域依賴于二叉樹的生成順序，主要是二值SVM分器所在的內節(jié)點位置了高類模型的推廣能力須利用合理的策略來生成二叉樹結構所本提出以類樣本分情況作為二又樹的生成算法而構造推廣能力好的基于二叉樹的多分類模型．改進算法的基思想就是在每次生成二叉樹內節(jié)點時，選擇最易分割的情況來構造當前節(jié)點的二值SVM．割順序不一樣，每個類的分割區(qū)域是不同的先割出來的類更容易有較大的分割區(qū)域了讓分布廣的類擁有較大的分割區(qū)域就

應最先把這些類分割出來為類數(shù)據(jù)的真實分布無法得知以有限樣本數(shù)據(jù)的分布來對真實分布作近似估計分布范圍的度量可采用超長方體和超球體最小包含某一類的樣本，超長方體超球的積就是此類樣本的分布度量．圖為類本數(shù)據(jù)的二維輸人空間分布圖，直觀上看，最好的分割順序為1類其他類構造分割超平面接第類第3和4類造分割超平面后第與4類造分割超平面主要是考慮到各類樣本空間分布范圍的大?。藰颖痉植挤秶攘慷x不同之外超長方體最小類包含和超球體最小類包含二叉樹生成法的多類別SVM分類算法流程幾乎是相同的，具體的算法流程為：Step：根據(jù)式或計各類樣本數(shù)的分布體積v，..，．iStep：根據(jù)各類的分布體積由大到小的順序，對類別進行排序當存在兩個或兩個以上的類別具有相同分布體積時這情況很少出，類標號小的排在前面．最后得到所有類別的排列n,n，..，，處∈，，.，，，..，為類標號．12kmStep二值分類的SVM訓算法構二叉樹各內節(jié)點的最優(yōu)超平面節(jié)處，從樣本集中選擇第類本為正樣本集，其他樣本為負樣本集，利用SVM訓算法構最1優(yōu)超平面，然后把屬于第n類的樣本從樣本集中刪除．在第2個節(jié)點處，從樣本集中選擇1第類本為正樣本集剩的樣本為負樣本集SVM訓練算法構造最優(yōu)超平面，2然后把屬于第n類的樣本從樣本集中刪除．依次下去，最終可得到如圖3所的基于二叉2樹的多類別SVM分模型．Step：法結束．三實驗

2-104012-104011.實數(shù)據(jù)實為了比較各種多類SVM算的性能使Statlog數(shù)庫中的多類別數(shù)據(jù)集letter、satimage和shuttle對one-against-one以本文提出的兩種算法分別進行實驗測試．表1列出了各數(shù)據(jù)集的一些信息，最后一列是Statlog主上給出的根據(jù)不同學習算法所取得的最好測試結果。為了避免取值范圍大的屬性比取值范圍小的屬性更占優(yōu)勢必須對樣本數(shù)據(jù)各屬性進行歸一化預處理，線性調整，1]．實驗中本文只使用RBF核數(shù)K(x，一ijIlxIl)，以便減少最優(yōu)參數(shù)集的搜索空間．考慮模型的推廣能力與常，γ)有，對于ij每一個優(yōu)化問題，可利用不同的核參γ和罰系數(shù)C組，γ一，

，.，

‘]，C=[2，….，．從而對于每個問題，可以嘗試×種數(shù)組合來建立模，從中得到推廣精度高γ和參數(shù)存在多個相同的最高測試率時支向量數(shù)少的那組γ和參每個實驗的KKT停止條件的容許誤差為0.001本所有算法均采用實現(xiàn)，并利用編，二值分算法是在LIBSVM具包的基礎上修改實現(xiàn)的．實驗平臺為酷睿t6600RAM的Lenovo，操作系統(tǒng)為Windows7對于每個優(yōu)化問題，分配40MB的存作為核函數(shù)計算值的緩存，同時采用Shrinking軟件實現(xiàn)技術來加快訓練．2.結和分表2列出了種方法的試驗比較結果中只列出最參(cγ)及對應的測試準確率．由2出，同問題、不同的分類算，最優(yōu)參數(shù)(C，所在的區(qū)域也會不同，這是要測試多(Cγ參對的原因．從實驗結果以看到，本文法雖然采用不的二叉樹生成方法，得每個類的分割順序不樣，但最優(yōu)參下的測試正確率非常接近，且與性能現(xiàn)最好的one-against-one方法也比較接近．One-against-rest應該是本次實驗中推廣性能差的一種SVM多類分類算法．表3列出了實驗的訓練時間、測試時以支持向量數(shù)．支持向量數(shù)一中#SVs表的是各個二值分類器支持向量總和u-SVs(uniqueSVs)表示的是不同的支持向量個，因為一個訓練樣本能會是多個二值分類器的支持向量。試階段，對于相的支持向量五與測試本的核函數(shù)值K(xi,xj)只需計算一次從而可以減少測試間時間和測時間是以程序運行的CPU時為準單位為S文算法的訓練間包括了類樣本體積計算和排序．在3個驗中，本文算法的測試時間比其他種算法少，因為二叉法測試樣本時并不需要算所有的二值類器One-against-rest方法支持向量個數(shù)遠遠多于其的法，這是因為其每個子分類器都需用到所有的訓練樣本構造的分面較其他算雜One-against-one和one-against-rest的測試時間相對長，因為這兩種方法必須計所的二值SVM分類器判別函數(shù)，且one-against-rest的總支向量數(shù)較多，使得其測時間更長。

總體上，本文出的兩種算法的測試間和測試正確率都較好超球體最小類包含法的測試確率更高一些，這是為以類重心為球心的球包含更能反映樣本的真實分布圍，而超立方體包含以樣本各屬性最值來構的，并不一定最小包含類樣本四結語本文首先分析當前使用較多的幾種SVM多類分算法的特點以及存在一些問題．此基上，提出了基于二叉的SVM多分算．新的二叉樹生成算法以使得分布廣類別在屬性空間中獲更大的劃分區(qū)域，從而高多分類模型推廣性能．最后本文通過幾個實驗，這些算法進行了比較，驗結果表明本算法可以明顯的少測試時間，且分類度也較理想．五參考獻References)[1]KolmanovskyHMcClamrochNH．DevelopmentsinNonholonomicControlSystems[J]．IEEEControlSystemMagazine，1995，15(6)20—．[2]馬笑瀟，黃席樾，毅．基于SVM的二叉樹多類分類算法及其在故障診斷中的應用J]．控與決策，2003，18(3)：272—276．[3]HongY．Fini