支持向量機多類分類算法的研究.pdf

1、關(guān)于支持向量機多類分類問題的模型和算法的研究是當(dāng)今研究的熱點之一。無論是最近提出的"一對一對余"結(jié)構(gòu)的算法，還是通常用的"一一對一"結(jié)構(gòu)的算法，對于K類分類問題，都需要解決K(K-1)/2個二次規(guī)劃問題，使得支持向量機在求解大規(guī)模問題中就會產(chǎn)生速度很慢的缺陷。因此，研究高效的求解算法是很有意義并且急需解決的問題。本文主要研究多類分類問題，從最優(yōu)化理論和算法的角度研究支持向量的最優(yōu)化問題，并建立了高效的求解算法。 本文所做的主要研

2、究工作如下： 1.構(gòu)造了基于線性規(guī)劃的"一對一"三類結(jié)構(gòu)支持向量分類器。由Chih-wei H等人將幾個常用的算法，如："一對多"算法， "一對一"算法，"有向無環(huán)圖"算法，"糾錯輸出編碼"算法以及兩種聚集算法進(jìn)行了數(shù)據(jù)試驗的比較，試驗結(jié)果表明"一對一"算法更適合于解決多類分類問題。但其也存在一定的缺點，由于在構(gòu)造子分類器的時候，只有兩類數(shù)據(jù)參與訓(xùn)練，容易造成由其它數(shù)據(jù)的信息缺失而帶來的錯誤分類的問題。由Cecilio A等人提

3、出的基于二次規(guī)劃的"一對一"三類結(jié)構(gòu)支持向量機，與傳統(tǒng)的"一對一"結(jié)構(gòu)相比較，其優(yōu)勢在于在分解的過程中，除了需要計算被區(qū)分的兩類訓(xùn)練點外。其它類別中訓(xùn)練點的信息也被充分利用，在一定程度上可以防止由信息的不完全帶來的分類誤差，同時，也減少了參數(shù)的個數(shù)。但由于增加了模型的復(fù)雜性，限制了其應(yīng)用。本文構(gòu)造了基于線性規(guī)劃的"一對一"三類結(jié)構(gòu)支持向量分類器，可以直接利用比較成熟的線性規(guī)劃算法-預(yù)測-校正原對偶內(nèi)點法，并在此基礎(chǔ)上提出了基于預(yù)測-校正

4、原對偶內(nèi)點法的支持向量機的多類分類學(xué)習(xí)算法，這種算法可用于比較龐大的多類別識別問題。數(shù)值試驗表明，本文提出的算法訓(xùn)練速度快，而且保持良好的分類精度。 2.在K-SVCR算法結(jié)構(gòu)的基礎(chǔ)上，構(gòu)造了新的模型。由Angulo C等人提出的K-SVCR算法，作者只給出了K-SVCR模型,并沒有提供相應(yīng)的求解算法，在一定程度上限制了K-SVCR算法的推廣使用，并且其對偶目標(biāo)函數(shù)為凸函數(shù)，而不是嚴(yán)格凸函數(shù)。本文構(gòu)造了新模型，該模型的特點是它的

5、一階最優(yōu)化條件可以轉(zhuǎn)化為一個線性互補問題，通過Lagrangian隱函數(shù)，可以將其進(jìn)一步轉(zhuǎn)化成一個嚴(yán)格凸的無約束優(yōu)化問題。利用Sherman-Moodbury-identity等式減小相應(yīng)優(yōu)化問題的規(guī)模。并在此基礎(chǔ)上利用了快速的Annijo步長的有限牛頓法和解決大型問題的共軛梯度法來求解無約束優(yōu)化問題，理論和數(shù)值試驗都表明有限牛頓法、共軛梯度法速度快、容易實現(xiàn)。另外，支持向量機的模型中含有多個參數(shù)，參數(shù)的取值直接影響分類的精確度，針對支