支持向量機(jī)多類(lèi)分類(lèi)算法的研究.pdf

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

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

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

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

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