支持向量機(jī)課件

支持向量機(jī)支持向量機(jī)1.引言1.1.支持向量機(jī)提出的背景1.2.支持向量機(jī)發(fā)展現(xiàn)狀1.3.支持向量機(jī)現(xiàn)在存在的問(wèn)題2.支持向量機(jī)基本原理及特點(diǎn)3.支持向量機(jī)訓(xùn)練算法4.新型支持向量機(jī)5.展望6.應(yīng)用舉例

1.引言

1.1.支持向量機(jī)提出的背景

上世紀(jì)60年代，Rosenblatt（1958）提出了第一個(gè)稱作感知器的學(xué)習(xí)機(jī)器模型，標(biāo)志著人們對(duì)學(xué)習(xí)過(guò)程進(jìn)行數(shù)學(xué)研究的真正開始。Rosenblatt的主要貢獻(xiàn)是把感知器模型表現(xiàn)為一個(gè)計(jì)算機(jī)程序，并且通過(guò)簡(jiǎn)單的試驗(yàn)，說(shuō)明了此模型的可推廣性。反向傳播（BP，BackPropagation）技術(shù)可以同時(shí)尋找多個(gè)神經(jīng)元的權(quán)值，標(biāo)志著構(gòu)造一般性學(xué)習(xí)機(jī)器研究的完成。學(xué)習(xí)機(jī)器的研究歷史進(jìn)入了一個(gè)新階段，即人工神經(jīng)元網(wǎng)絡(luò)（ANNArtificialNeuralNetwork）時(shí)代。1.1.支持向量機(jī)提出的背景在隨后十幾年中，人們?cè)谠S多領(lǐng)域?qū)ι窠?jīng)網(wǎng)絡(luò)進(jìn)行了深入細(xì)致的研究，不但在實(shí)際應(yīng)用中取得了良好效果，而且提出了若干其他神經(jīng)網(wǎng)絡(luò)模型，如自組織映射模型、反饋型以及隨機(jī)型神經(jīng)網(wǎng)絡(luò)等等。盡管神經(jīng)網(wǎng)絡(luò)在許多應(yīng)用領(lǐng)域都取得了重要成果，但其實(shí)現(xiàn)過(guò)程過(guò)多地依賴于人的主觀意識(shí)和先驗(yàn)知識(shí)，而不是建立在嚴(yán)格的理論基礎(chǔ)之上，因此，難以對(duì)神經(jīng)網(wǎng)絡(luò)模型的性能及其適用范圍進(jìn)行理論分析。也正因?yàn)槿绱?，人們?cè)谑畮啄甑纳窠?jīng)計(jì)算研究中，并沒(méi)有對(duì)一般的學(xué)習(xí)理論帶來(lái)更大的貢獻(xiàn)（Vapnik，1998）。1.1.支持向量機(jī)提出的背景及意義

傳統(tǒng)統(tǒng)計(jì)學(xué)研究的內(nèi)容是樣本無(wú)窮大時(shí)的漸進(jìn)理論，即當(dāng)樣本數(shù)據(jù)趨于無(wú)窮多時(shí)的統(tǒng)計(jì)性質(zhì)。而實(shí)際問(wèn)題中樣本數(shù)據(jù)往往是有限的。因此，假設(shè)樣本數(shù)據(jù)無(wú)窮多，并以此為基礎(chǔ)推導(dǎo)出的各種算法，很難在樣本數(shù)據(jù)有限時(shí)取得理想的應(yīng)用效果。神經(jīng)網(wǎng)絡(luò)（ANN）的過(guò)學(xué)習(xí)問(wèn)題就是一個(gè)典型的例子。當(dāng)樣本數(shù)據(jù)有限時(shí)，本來(lái)具有良好學(xué)習(xí)能力的學(xué)習(xí)機(jī)器有可能表現(xiàn)出很差的泛化性能。早在20世紀(jì)70年代誕生的統(tǒng)計(jì)學(xué)習(xí)理論（SLT，StatisticalLearningTheory），系統(tǒng)地研究了機(jī)器學(xué)習(xí)問(wèn)題。它對(duì)有限樣本情況下的統(tǒng)計(jì)學(xué)習(xí)問(wèn)題提供了一個(gè)有效的解決途徑，彌補(bǔ)了傳統(tǒng)統(tǒng)計(jì)學(xué)的不足。1.1.支持向量機(jī)提出的背景統(tǒng)計(jì)學(xué)習(xí)理論是一種專門研究小樣本情況下機(jī)器學(xué)習(xí)規(guī)律的基本理論和數(shù)學(xué)構(gòu)架，也是小樣本統(tǒng)計(jì)估計(jì)和預(yù)測(cè)學(xué)習(xí)的最佳理論。Vapnik（1963，1971）等人從六、七十年代開始致力于此方面研究。到上世紀(jì)九十年代中期，隨著該理論的不斷發(fā)展和成熟，產(chǎn)生了基于統(tǒng)計(jì)學(xué)習(xí)理論體系的新的通用機(jī)器學(xué)習(xí)方法，即支持向量機(jī)（SVMs，SupportVectorMachines）。1.引言1.1.支持向量機(jī)提出的背景1.2.支持向量機(jī)發(fā)展現(xiàn)狀1.3.支持向量機(jī)現(xiàn)在存在的問(wèn)題2.支持向量機(jī)基本原理及特點(diǎn)3.支持向量機(jī)訓(xùn)練算法4.新型支持向量機(jī)5.展望6.應(yīng)用舉例1.2支持向量機(jī)發(fā)展現(xiàn)狀

支持向量機(jī)算法一經(jīng)提出，就得到國(guó)內(nèi)外學(xué)者的高度關(guān)注。學(xué)術(shù)界普遍認(rèn)為它是繼神經(jīng)網(wǎng)絡(luò)之后的一個(gè)新的研究方向。在短短的幾年里，取得了一系列令人矚目的研究成果。1.2.支持向量機(jī)發(fā)展現(xiàn)狀（1）支持向量機(jī)的理論研究：雖然支持向量機(jī)發(fā)展時(shí)間很短，但是由于它的產(chǎn)生是基于統(tǒng)計(jì)學(xué)習(xí)理論的，因此具有堅(jiān)實(shí)的理論基礎(chǔ)。近幾年涌現(xiàn)出的大量理論研究成果，更為其應(yīng)用研究奠定了堅(jiān)實(shí)基礎(chǔ)。-Anthony.（1999）等人給出了關(guān)于硬鄰域支持向量機(jī)學(xué)習(xí)誤差的嚴(yán)格理論界限，Shawe-Taylo（r2000）和Cristianin（i2000）也給出了類似的關(guān)于軟鄰域支持向量機(jī)和回歸情況下的誤差界限；-Westonetal.（1998）和Vapnik（1995，1998）等研究了支持向量機(jī)的泛化性能及其在多值分類和回歸問(wèn)題的擴(kuò)展問(wèn)題；-Smola（1998）和Schoelkopf（1999）提出了支持向量機(jī)一般意義下的損失函數(shù)數(shù)學(xué)描述；-脊回歸是由Tikhonov提出的一種具有特殊形式的正則化網(wǎng)絡(luò)，Girosi（1990）、Poggio（1975）等將其應(yīng)用到正則化網(wǎng)絡(luò)的學(xué)習(xí)中，Smolaetal.（1999）研究了狀態(tài)空間中脊回歸的應(yīng)用，Giros（i1990）、Smola（1998）、Schoelkopf（1999）等討論了正則化網(wǎng)絡(luò)和支持向量機(jī)的關(guān)系。1.2.支持向量機(jī)發(fā)展現(xiàn)狀（2）支持向量機(jī)的訓(xùn)練算法：支持向量機(jī)的最終求解問(wèn)題歸結(jié)為一個(gè)有約束的二次型規(guī)劃（QP，QuadraticProgramming）問(wèn)題?？梢岳脴?biāo)準(zhǔn)二次型優(yōu)化技術(shù)來(lái)求解這個(gè)優(yōu)化問(wèn)題，如牛頓法、共扼梯度法、內(nèi)點(diǎn)法等。但是，這些方法只適合小樣本情況，當(dāng)樣本數(shù)目較大時(shí)，算法復(fù)雜度會(huì)急劇增加，而且占用極大的系統(tǒng)內(nèi)存。為降低計(jì)算資源、提高算法效率，已經(jīng)提出許多針對(duì)大規(guī)模樣本集的訓(xùn)練算法：1.2.支持向量機(jī)發(fā)展現(xiàn)狀

四種訓(xùn)練算法1)分塊算法（Chunking）（CortesandVapnik，1995）2)子集選擇算法（SubsetSelectionalgorithms）（Osuna，1997；Joachims，1998）3)序列最小優(yōu)化算法（SMO，SequentialMinimalOptimization）（Platt，1998）4）增量式算法（Cauwenberghs，2001）支持向量機(jī)1.引言1.1.支持向量機(jī)提出的背景1.2.支持向量機(jī)發(fā)展現(xiàn)狀

1.3.支持向量機(jī)現(xiàn)在存在的問(wèn)題2.支持向量機(jī)基本原理及特點(diǎn)3.支持向量機(jī)訓(xùn)練算法4.新型支持向量機(jī)5.展望6.應(yīng)用舉例1.3.支持向量機(jī)現(xiàn)在存在的問(wèn)題支持向量機(jī)自出現(xiàn)以來(lái)，理論上的研究飛速發(fā)展，應(yīng)用領(lǐng)域越來(lái)越廣泛。但與理論研究相比較，應(yīng)用研究相對(duì)比較滯后。相比之下，分類問(wèn)題的研究較為成熟，其他方面如時(shí)間序列分析，回歸，聚類等方面的研究，還有待進(jìn)一步地完善。雖然到目前已經(jīng)提出了多種訓(xùn)練算法，卻依然存在一些問(wèn)題亟待解決。1.3.支持向量機(jī)現(xiàn)在存在的問(wèn)題1）支持向量機(jī)在理論上，核函數(shù)及參數(shù)的構(gòu)造和選擇缺乏理論指導(dǎo)；2）作為支持向量機(jī)基礎(chǔ)的原始問(wèn)題解和對(duì)偶問(wèn)題解的關(guān)系上，當(dāng)前研究存在邏輯缺陷；3）在部分情況下，支持向量機(jī)無(wú)法利用現(xiàn)有的公式計(jì)算決策函數(shù)的閾值；1.3.支持向量機(jī)現(xiàn)在存在的問(wèn)題4）支持向量機(jī)中一類重要的變形方法，雖然有效，但缺乏相應(yīng)的統(tǒng)計(jì)學(xué)習(xí)理論基礎(chǔ)；5）LS-SVM將SVM的求解從QP問(wèn)題向線性方程組的成功轉(zhuǎn)化極大地提高了SVM的求解效率，也降低了SVM的學(xué)習(xí)難度，極大地促進(jìn)了SVM的應(yīng)用。但LS-SVM同時(shí)也喪失SVM的稀疏性與魯棒性。支持向量機(jī)1.引言1.1.支持向量機(jī)提出的背景1.2.支持向量機(jī)發(fā)展現(xiàn)狀1.3.支持向量機(jī)現(xiàn)在存在的問(wèn)題2.支持向量機(jī)基本原理及特點(diǎn)3.支持向量機(jī)訓(xùn)練算法4.新型支持向量機(jī)5.展望6.應(yīng)用舉例2.支持向量機(jī)基本原理基本原理：通過(guò)用非線性映射將輸入空間變換到一個(gè)高維空間，在這個(gè)高維空間中尋找輸入變量和輸出變量之間的一種非線性關(guān)系。注意到算法僅使用高維空間中的內(nèi)積，通過(guò)引入核函數(shù)，高維空間的內(nèi)積運(yùn)算就可用原空間中的函數(shù)來(lái)實(shí)現(xiàn)，甚至沒(méi)有必要知道非線性映射的形式。通過(guò)采用適當(dāng)?shù)暮撕瘮?shù)就可實(shí)現(xiàn)某一非線性變換后的線性分類，而計(jì)算復(fù)雜度沒(méi)有增加，從而在一定程度上避免了維數(shù)災(zāi)難問(wèn)題。2.支持向量機(jī)的特點(diǎn)1.非線性映射是SVM方法的理論基礎(chǔ),SVM利用內(nèi)積核函數(shù)代替向高維空間的非線性映射;2.對(duì)特征空間劃分的最優(yōu)超平面是SVM的目標(biāo),最大化分類邊際的思想是SVM方法的核心;3.支持向量是SVM的訓(xùn)練結(jié)果,在SVM分類決策中起決定作用的是支持向量。2.支持向量機(jī)的特點(diǎn)SVM是一種有堅(jiān)實(shí)理論基礎(chǔ)的新穎的小樣本學(xué)習(xí)方法。它基本上不涉及概率測(cè)度及大數(shù)定律等,因此不同于現(xiàn)有的統(tǒng)計(jì)方法。從本質(zhì)上看,它避開了從歸納到演繹的傳統(tǒng)過(guò)程,實(shí)現(xiàn)了高效的從訓(xùn)練樣本到預(yù)報(bào)樣本的“轉(zhuǎn)導(dǎo)推理”(transductiveinference),大大簡(jiǎn)化了通常的分類和回歸等問(wèn)題。支持向量機(jī)1.引言1.1.支持向量機(jī)提出的背景1.2.支持向量機(jī)發(fā)展現(xiàn)狀1.3.支持向量機(jī)現(xiàn)在存在的問(wèn)題2.支持向量機(jī)基本原理3.支持向量機(jī)訓(xùn)練算法4.新型支持向量機(jī)5.展望6.應(yīng)用舉例3.支持向量機(jī)訓(xùn)練算法支持向量機(jī)的最終求解問(wèn)題歸結(jié)為一個(gè)有約束的二次型規(guī)劃（QP，QuadraticProgramming）問(wèn)題?？梢岳脴?biāo)準(zhǔn)二次型優(yōu)化技術(shù)來(lái)求解這個(gè)優(yōu)化問(wèn)題，如牛頓法、共扼梯度法、內(nèi)點(diǎn)法等。但是，這些方法只適合小樣本情況，當(dāng)樣本數(shù)目較大時(shí)，算法復(fù)雜度會(huì)急劇增加，而且占用極大的系統(tǒng)內(nèi)存。為降低計(jì)算資源、提高算法效率，已經(jīng)提出許多針對(duì)大規(guī)模樣本集的訓(xùn)練算法：3.支持向量機(jī)訓(xùn)練算法分塊算法（Chunking）（CortesandVapnik，1995）

-1995年，Cortes和Vapnik給出了一種求解支持向量機(jī)二次規(guī)劃（QP）問(wèn)題的分塊算法。其依據(jù)是支持向量機(jī)的最終求解結(jié)果只與支持向量有關(guān)，與非支持向量無(wú)關(guān)。3.支持向量機(jī)訓(xùn)練算法其實(shí)現(xiàn)過(guò)程是將初始QP問(wèn)題分解為一系列小規(guī)模的QP子問(wèn)題，不斷的求解QP子問(wèn)題，保留解中的支持向量，并加入到新的QP子問(wèn)題中。每個(gè)QP子問(wèn)題都采用上次求解的結(jié)果作為初始值。直到所有的QP子問(wèn)題求解完畢。這種方法可以大大減小算法占用的系統(tǒng)內(nèi)存。然而，當(dāng)樣本集中的支持向量數(shù)目很大時(shí)，其算法復(fù)雜度仍然很大。3.支持向量機(jī)訓(xùn)練算法(2)子集選擇算法（Osuna，1997；Joachims，1998）-為加快支持向量機(jī)的訓(xùn)練速度，Osuna（1997）提出了子集選擇算法。該方法首先將數(shù)據(jù)集分塊（chunking），從分塊數(shù)據(jù)中提取支持向量，并加以保留，然后補(bǔ)充新的樣本，反復(fù)運(yùn)算，直至所有的樣本都滿足KKT（Karush-Kuhn-Tucker）（Vapnik，1995）收斂條件。1998年，Joachims指出，采用啟發(fā)式迭代策略會(huì)提高算法的收斂速度，并提出一種稱為SVMlight的支持向量機(jī)分解學(xué)習(xí)算法。該算法實(shí)際上是子集選擇算法的推廣。3.支持向量機(jī)訓(xùn)練算法(3)序列最小優(yōu)化算法（SMO）（Platt，1998）1998年，Platt提出了更為有效的支持向量機(jī)訓(xùn)練算法，即序列最小優(yōu)化算法。其基本思想是把一個(gè)大數(shù)據(jù)量的QP分解為一系列最小的QP子優(yōu)化問(wèn)題。該算法是分解算法的一個(gè)極端特例。其實(shí)現(xiàn)過(guò)程為，每次針對(duì)兩個(gè)樣本的二次規(guī)劃問(wèn)題，直接采用解析方法求其最優(yōu)解，以提高QP問(wèn)題的求解速度。Platt設(shè)計(jì)了一個(gè)兩層嵌套循環(huán)過(guò)程實(shí)現(xiàn)其算法。在外環(huán)中采用啟發(fā)式方法尋找違背KKT最優(yōu)條件的樣本，在內(nèi)環(huán)中對(duì)該樣本的相應(yīng)Lagrange乘子進(jìn)行分析求解，完成一次優(yōu)化。不斷重復(fù)此過(guò)程,直至所有樣本都滿足KKT條件。3.支持向量機(jī)訓(xùn)練算法序列最小優(yōu)化算法將工作樣本集的規(guī)模減少為兩個(gè)，直接導(dǎo)致了迭代次數(shù)的增加。所以序列最小優(yōu)化算法實(shí)際上是將求解優(yōu)化問(wèn)題的耗費(fèi)轉(zhuǎn)嫁到迭代運(yùn)算上。Platt指出，通過(guò)核優(yōu)化方法可以大幅提高序列最小優(yōu)化算法的性能。該算法在訓(xùn)練線性支持向量機(jī)時(shí)，可以獲得非常好的性能，但在訓(xùn)練非線性支持向量機(jī)時(shí)，算法速度會(huì)大大減慢。針對(duì)不同的問(wèn)題，其計(jì)算復(fù)雜度差別很大。3.支持向量機(jī)訓(xùn)練算法(4)增量式算法（Cauwenberghs，2001）Cauwenberghs（2001）提出了一種增量減量式學(xué)習(xí)方法，考慮了增加或減少一個(gè)訓(xùn)練樣本對(duì)Lagrange系數(shù)和支持向量機(jī)的影響，實(shí)驗(yàn)表明算法是有效的。3.支持向量機(jī)訓(xùn)練算法在減少一個(gè)樣本時(shí)，給出了模型選擇算法LOO（Leaveoneout）的形象解釋。Ralaivola（2001）提出了另一種增量式學(xué)習(xí)方法。其思想為基于高斯核的局部特性，只更新對(duì)學(xué)習(xí)機(jī)器輸出影響最大的Lagrange系數(shù)，以減少計(jì)算復(fù)雜度。另外，Suykens（2001）提出了一種周期最小二乘支持向量機(jī)用于時(shí)間序列的預(yù)測(cè)。Carozzaetal.（2000）和Xiaoetal.（2000）等人也分別提出了一些增量式學(xué)習(xí)的支持向量機(jī)訓(xùn)練算法。3.支持向量機(jī)訓(xùn)練算法(5)變形算法：-變形算法主要是通過(guò)增加函數(shù)項(xiàng)，變量或系數(shù)等方法使公式變形，產(chǎn)生出各種有某一方面優(yōu)勢(shì)或者一定應(yīng)用范圍的算法。-Suykens等人以雙螺旋分類問(wèn)題為背景，創(chuàng)造性地把標(biāo)準(zhǔn)SVM的線性不等式約束轉(zhuǎn)化成了等式約束，從而使得SVM的訓(xùn)練等價(jià)于一組線性方程組的求解。該方法被稱為最小二乘支持向量機(jī)（LS-SVM）3.支持向量機(jī)訓(xùn)練算法SVM的求解從QP問(wèn)題向線性方程組的成功轉(zhuǎn)化極大地提高了SVM的求解效率，也降低了SVM的學(xué)習(xí)難度，極大地促進(jìn)了SVM的應(yīng)用。在LS-SVM中，對(duì)于回歸問(wèn)題，未知變量的數(shù)目?jī)H相當(dāng)于同等規(guī)模分類問(wèn)題的未知變量數(shù)目，避免了傳統(tǒng)SVM學(xué)習(xí)方法中回歸問(wèn)題未知變量數(shù)目的膨脹。3.支持向量機(jī)訓(xùn)練算法(6)幾何方法SVM方法具有明顯的幾何意義，線性可分和不可分問(wèn)題分別等價(jià)于求解特征空間中兩類訓(xùn)練樣本形成的凸包及縮小的凸包之間的距離。對(duì)于線性可分問(wèn)題，如果在目標(biāo)函數(shù)中加入0.5b2，則可以轉(zhuǎn)化為凸包到原點(diǎn)的最小距離。它存在簡(jiǎn)單有效的算法，如單純形迭代法。對(duì)于線性不可分問(wèn)題，則通過(guò)采用松弛變量ξ的l2范數(shù)，將其轉(zhuǎn)化為線性可分問(wèn)題進(jìn)行求解。3.支持向量機(jī)訓(xùn)練算法M.H.Yang等利用訓(xùn)練樣本的結(jié)構(gòu)信息，提出了訓(xùn)練SVM的幾何方法以及衛(wèi)向量（Guardvector）的概念。衛(wèi)向量即為通過(guò)該向量使輸入空間線性可分的向量。支持向量集為衛(wèi)向量集的一個(gè)子集。當(dāng)訓(xùn)練集合較大時(shí)，可以先找出衛(wèi)向量，再以衛(wèi)向量構(gòu)成傳統(tǒng)的QP問(wèn)題求出支持向量。衛(wèi)向量的求解是通過(guò)判斷其對(duì)偶空間中的線性規(guī)劃問(wèn)題的可行性而不是求其解，從而使問(wèn)題大大簡(jiǎn)化。3.支持向量機(jī)訓(xùn)練算法試驗(yàn)表明該算法求得的最優(yōu)分類面和傳統(tǒng)QP問(wèn)題一樣。由于衛(wèi)向量約為支持向量的20倍左右，所以該方法訓(xùn)練速度要快30倍，而內(nèi)存要求僅為傳統(tǒng)的1/4。但對(duì)支持向量數(shù)和衛(wèi)向量數(shù)之間的關(guān)系還沒(méi)有做出相應(yīng)的理論分析。3.支持向量機(jī)訓(xùn)練算法張文生等將SVM原理建立在距離空間上，設(shè)計(jì)出基于鄰域原理計(jì)算支持向量的算法。事實(shí)上，鄰域原理求支持向量的過(guò)程就是求一組近似支持向量的過(guò)程。該過(guò)程本質(zhì)上是在簡(jiǎn)化SVM理論中二次規(guī)劃目標(biāo)函數(shù)的Hessian矩陣。該方法不但幾何意義明確，而且計(jì)算速度快，每次可以消掉內(nèi)積矩陣的多行多列，使得計(jì)算機(jī)的內(nèi)存開銷小。3.支持向量機(jī)訓(xùn)練算法汪西莉等提出了一種基于馬氏距離的支持向量快速提取算法。用該方法對(duì)訓(xùn)練數(shù)據(jù)進(jìn)行預(yù)處理后，可以加快支持向量機(jī)的訓(xùn)練速度3.支持向量機(jī)訓(xùn)練算法(7)多類分類算法SVM最初是針對(duì)解決兩類分類問(wèn)題提出的，要將其推廣到多類分類問(wèn)題，需要構(gòu)造多類SVM分類器，其構(gòu)造方法主要有2種：3.支持向量機(jī)訓(xùn)練算法一種是以Weston在1998年提出的多類算法為代表，只需將原始的兩類改為K類，這樣就很自然的將兩類分類SVM轉(zhuǎn)化為K類分類SVM。這種算法選擇的目標(biāo)函數(shù)十分的復(fù)雜，變量數(shù)目過(guò)多，計(jì)算復(fù)雜度也非常的高，實(shí)現(xiàn)困難，所以只在小型問(wèn)題的求解中用到。3.支持向量機(jī)訓(xùn)練算法一種構(gòu)造方法的基本思想就是通過(guò)組合多個(gè)兩類分類器，這類方法目前主要有兩種分支算法：1對(duì)多算法、1對(duì)1算法、決策導(dǎo)向無(wú)環(huán)圖。3.支持向量機(jī)訓(xùn)練算法1對(duì)多算法是由Vapnik提出的，對(duì)于K類問(wèn)題構(gòu)造K個(gè)兩類分類器，第i個(gè)SVM用的i類中訓(xùn)練樣本作為正的分類樣本，而將其他的樣本作為負(fù)的樣本，最后的輸出是兩類分類器輸出的最大的那一類。3.支持向量機(jī)訓(xùn)練算法1對(duì)1算法是由Knerr提出的，該算法在K類訓(xùn)練樣本中構(gòu)造所可能的兩類分類器，每類僅在K類中的兩類訓(xùn)練樣本上訓(xùn)練，結(jié)果共構(gòu)造k×(k—1)/2個(gè)分類器，組合這些兩類分類器并使用投票法，得票最多的類為樣本點(diǎn)所屬的類。3.支持向量機(jī)訓(xùn)練算法針對(duì)1對(duì)1算法，Platt等提出了一個(gè)新的學(xué)習(xí)架構(gòu)：決策導(dǎo)向無(wú)環(huán)圖（DecisionDirectedAcyclicGraph，DDAG）。對(duì)于K類問(wèn)題，DDAG含k×(k-1)/2個(gè)分類器，每個(gè)分類器對(duì)應(yīng)兩類。在對(duì)多個(gè)1對(duì)1子分類器組合的過(guò)程中，引入了圖論中有向無(wú)環(huán)圖的思想。由于DDAG的每個(gè)節(jié)點(diǎn)和一個(gè)分類器相關(guān)，因此根據(jù)DDAG提出的DAGSVM的速度顯然要快。3.支持向量機(jī)訓(xùn)練算法安金龍等提出了基于二叉樹的支持向量機(jī)的多類分類方法。它繼承了一對(duì)多方法的訓(xùn)練支持向量數(shù)少及一對(duì)一方法的訓(xùn)練速度快的優(yōu)點(diǎn)。通過(guò)在分類階段結(jié)合二叉樹，從而大大提高了支持向量機(jī)的分類速度。同時(shí)它也克服了一對(duì)一、一對(duì)多、決策導(dǎo)向無(wú)環(huán)圖方法可能出現(xiàn)的無(wú)法分類區(qū)域的存在，從而提高了支持向量機(jī)多類分類的性能。支持向量機(jī)1.引言1.1.支持向量機(jī)提出的背景1.2.支持向量機(jī)發(fā)展現(xiàn)狀1.3.支持向量機(jī)現(xiàn)在存在的問(wèn)題2.支持向量機(jī)基本原理3.支持向量機(jī)訓(xùn)練算法4.支持向量機(jī)應(yīng)用5.展望6.應(yīng)用舉例4.支持向量機(jī)應(yīng)用目前支持向量機(jī)在如下幾個(gè)方面獲得較為成功的應(yīng)用。(1)生物信息學(xué)生物信息學(xué)是近來(lái)特別受人關(guān)注的一門新學(xué)科,SVM在該領(lǐng)域已經(jīng)獲得重要成果,并有著十分廣闊的應(yīng)用前景。4.支持向量機(jī)應(yīng)用人類的遺傳功能是由核酸承擔(dān)的,核酸分為脫氧核糖核酸(DNA)和核糖核酸(RNA)兩大類,它們由核苷酸、戊糖以及磷酸構(gòu)成。DNA分子上的4種核苷酸A,G,C,T的排列組合順序蘊(yùn)含了豐富的遺傳信息,其中每3個(gè)相鄰的核苷酸包含一個(gè)遺傳密碼?；蚓褪侵溉旧w所運(yùn)載的DNA雙螺旋鏈上的一段序列,該序列由這4種核苷酸通過(guò)不同的排列組合形成。4.支持向量機(jī)應(yīng)用針對(duì)傳統(tǒng)SVM方法中存在的不足,提出了基于數(shù)據(jù)優(yōu)化法的SVM,它通過(guò)其它統(tǒng)計(jì)學(xué)模型優(yōu)化訓(xùn)練數(shù)據(jù)集,進(jìn)而提高分類器的辨識(shí)精度。實(shí)驗(yàn)結(jié)果表明基于數(shù)據(jù)優(yōu)化法的SVM分類器在翻譯起始位點(diǎn)的辨識(shí)上可獲得比其他判別方法更好的效果。近年來(lái),生物學(xué)的信息數(shù)量已成指數(shù)增長(zhǎng),大量關(guān)于DNA和蛋白質(zhì)序列的信息都已公開。這也大大地增強(qiáng)了人們對(duì)發(fā)展數(shù)據(jù)分類技術(shù)的興趣。用分類技術(shù)自動(dòng)地實(shí)現(xiàn)將大量的序列數(shù)據(jù)根據(jù)其結(jié)構(gòu)或功能分成相應(yīng)的不同類別。4.支持向量機(jī)應(yīng)用(2)人臉檢測(cè)、識(shí)別和姿態(tài)判定人臉檢測(cè)是模式識(shí)別和機(jī)器視覺領(lǐng)域的一個(gè)重要研究方向,其目的是判斷圖像中是否存在人臉,并確定所有人臉的大小和位置。Osuna等最早用SVM進(jìn)行人臉檢測(cè),方法是直接取象素點(diǎn)的灰度值作為輸入特征。4.支持向量機(jī)應(yīng)用由于需要大量的存儲(chǔ)空間和較多的支持向量,速度很慢。Lyons使用圖像的彈性圖的某些格點(diǎn)上的2D2Gabor小波變換系數(shù)幅值作為特征,使用LDA進(jìn)行線性判別種族、表情、性別等二值訓(xùn)練和分類,這種方法的缺點(diǎn)是2D2Gabor小波變換,很費(fèi)時(shí),再加上主成分分析計(jì)算量也大,使系統(tǒng)的實(shí)時(shí)性大大降低。4.支持向量機(jī)應(yīng)用(3)文本分類文本分類的任務(wù)是根據(jù)文本的內(nèi)容自動(dòng)地進(jìn)行歸類,應(yīng)用很廣泛,比如郵件過(guò)濾、網(wǎng)頁(yè)搜索、辦公自動(dòng)化等領(lǐng)域均涉及這一問(wèn)題。專業(yè)中文網(wǎng)頁(yè)分類器,利用SVM對(duì)網(wǎng)頁(yè)進(jìn)行兩類分類,找出所需專業(yè)的中文網(wǎng)頁(yè);然后利用向量空間模型,對(duì)分類好的專業(yè)網(wǎng)頁(yè)進(jìn)行多類分類。在構(gòu)造支持向量機(jī)的過(guò)程中,為了提高分類的召回率,采用了一種偏移因子。該算法只需要計(jì)算兩類SVM分類器,實(shí)驗(yàn)表明,它不僅具有較高的訓(xùn)練效率,同時(shí)能得到很高的分類精確率和召回率。支持向量機(jī)1.引言1.1.支持向量機(jī)提出的背景1.2.支持向量機(jī)發(fā)展現(xiàn)狀1.3.支持向量機(jī)現(xiàn)在存在的問(wèn)題2.支持向量機(jī)基本原理3.支持向量機(jī)訓(xùn)練算法4.支持向量機(jī)應(yīng)用5.展望6.應(yīng)用舉例5.展望作為機(jī)器學(xué)習(xí)的一個(gè)重要內(nèi)容，支持向量機(jī)的研究已受到眾多研究者的關(guān)注，但由于出現(xiàn)時(shí)間不長(zhǎng)，許多問(wèn)題的研究還處于起步階段，許多理論問(wèn)題亟待解決，應(yīng)用領(lǐng)域也需要進(jìn)一步拓展。目前，下述幾個(gè)方面的問(wèn)題值得進(jìn)行深入的研究：5.展望1）有限維空間的SVM理論發(fā)展較快，無(wú)限維空間的SVM理論還需深入研究和推廣；2）針對(duì)SVM理論中優(yōu)化問(wèn)題的特點(diǎn)，如何建立簡(jiǎn)單、有效、實(shí)用的算法是迫切需要解決的問(wèn)題；3）將神經(jīng)網(wǎng)絡(luò)與模糊邏輯等領(lǐng)域已有的研究方法與思想與SVM理論相結(jié)合，提出新的方法；4）訓(xùn)練樣本中數(shù)據(jù)含有不確定性以及噪聲時(shí)的SVM理論性能，即SVM理論的魯棒性問(wèn)題是值得研究的重點(diǎn)課題；5）進(jìn)一步拓展SVM的應(yīng)用領(lǐng)域，特別是SVM在控制中的應(yīng)用需要重點(diǎn)研究。支持向量機(jī)1.引言1.1.支持向量機(jī)提出的背景1.2.支持向量機(jī)發(fā)展現(xiàn)狀1.3.支持向量機(jī)現(xiàn)在存在的問(wèn)題2.支持向量機(jī)基本原理3.支持向量機(jī)訓(xùn)練算法4.支持向量機(jī)應(yīng)用5.展望6.應(yīng)用舉例

6.應(yīng)用舉例

基于免疫優(yōu)化的支持向量機(jī)文本分類算法

6.1免疫算法原理：是一種復(fù)雜的分布式信息處理學(xué)習(xí)系統(tǒng)，免疫算法的思想來(lái)源于生物免疫機(jī)體的原理，其具有較強(qiáng)的自適應(yīng)性、多樣性、學(xué)習(xí)、識(shí)別和記憶等特點(diǎn)，其克服遺傳算法易陷入局部最優(yōu)的缺陷，收斂速度大大加快。它模仿生物的免疫過(guò)程，具有良好的全局搜索能力和記憶功能?？乖瓕?duì)應(yīng)于優(yōu)化問(wèn)題的目標(biāo)函數(shù)，抗體對(duì)應(yīng)于優(yōu)化問(wèn)題的解。通過(guò)抗原和抗體的親和力來(lái)描述可行解與最優(yōu)解的逼近程度。對(duì)外界抗原的侵入，系統(tǒng)自動(dòng)產(chǎn)生相應(yīng)的抗體，通過(guò)抗