支持向量機(jī)方法課件

1、支持向量機(jī)肖瑩2022/7/241知識管理與數(shù)據(jù)分析實(shí)驗(yàn)室支持向量機(jī)支持向量機(jī)(Support Vector Machine,簡稱SVM)是在統(tǒng)計(jì)學(xué)習(xí)理論基礎(chǔ)上提出一種新型通用的機(jī)器學(xué)習(xí)方法。它建立在結(jié)構(gòu)風(fēng)險(xiǎn)最小化原則基礎(chǔ)之上，具有很強(qiáng)的學(xué)習(xí)能力。2022/7/24知識管理與數(shù)據(jù)分析實(shí)驗(yàn)室2支持向量機(jī)其主要借助于最優(yōu)化方法解決數(shù)據(jù)挖掘中的分類問題，是數(shù)據(jù)挖掘技術(shù)中一個(gè)新的研究熱點(diǎn)。它是統(tǒng)計(jì)學(xué)習(xí)理論中最年輕也最實(shí)用的部分，在很多領(lǐng)域得到了成功應(yīng)用，如人臉檢測、手寫數(shù)字識別、文本分類、生物信息學(xué)等。2022/7/24知識管理與數(shù)據(jù)分析實(shí)驗(yàn)室3支持向量機(jī)的提出SVM理論源于Vapinik在1963年

2、提出的用于解決模式識別問題的支持向量方法。這種方法從訓(xùn)練集中選擇一組特征子集, 使得對特征子集的線性劃分等價(jià)于對整個(gè)數(shù)據(jù)集的分割。這組特征子集稱為支持向量SV。在此后近30年中, 對SV的研究主要集中在對分類函數(shù)的改進(jìn)和函數(shù)預(yù)測上。2022/7/24知識管理與數(shù)據(jù)分析實(shí)驗(yàn)室4支持向量機(jī)的提出在1971年,Kimel-dorf提出使用線性不等約束重新構(gòu)造SV的核空間, 解決了一部分線性不可分的問題, 為以后SVM的研究開辟了道路。1990年, Grace, Boster和Vapnik等人開始對SVM技術(shù)進(jìn)行研究, 并取得突破性進(jìn)展。1995年, Vapnik提出了統(tǒng)計(jì)學(xué)習(xí)理論, 較好地解決了線性

3、不可分的問題, 正式奠定了SVM的理論基礎(chǔ)。2022/7/24知識管理與數(shù)據(jù)分析實(shí)驗(yàn)室5支持向量機(jī)理論支持向量機(jī)的理論最初來自對數(shù)據(jù)分類問題的處理。對于數(shù)據(jù)分類問題, 如果采用通用的神經(jīng)網(wǎng)絡(luò)方法來實(shí)現(xiàn), 其機(jī)理可以簡單地描述為：系統(tǒng)隨機(jī)產(chǎn)生一個(gè)超平面并移動(dòng)它, 直到訓(xùn)練集中屬于不同分類的點(diǎn)正好位于平面的不同側(cè)面。這種處理機(jī)制決定了：用神經(jīng)網(wǎng)絡(luò)方法進(jìn)行數(shù)據(jù)分類最終獲得的分割平面將相當(dāng)靠近訓(xùn)練集中的點(diǎn), 而在絕大多數(shù)情況下, 并不是一個(gè)最優(yōu)解。2022/7/24知識管理與數(shù)據(jù)分析實(shí)驗(yàn)室6支持向量機(jī)理論為此SVM考慮尋找一個(gè)滿足分類要求的分割平面, 并使訓(xùn)練集中的點(diǎn)距離該分割平面盡可能地遠(yuǎn),即尋找一

4、個(gè)分割平面, 使其兩側(cè)的空白區(qū)域(margin)最大。2022/7/24知識管理與數(shù)據(jù)分析實(shí)驗(yàn)室7支持向量機(jī)理論在很多情況下, 訓(xùn)練數(shù)據(jù)集中的數(shù)據(jù)是線性不可分的, 這使得SV的應(yīng)用受到了很大的限制。為了解決這個(gè)問題, Vapnik等人提出使用SVM作為超平面分割方法的擴(kuò)展。使用SVM進(jìn)行數(shù)據(jù)集分類工作的典型流程如圖2所示。2022/7/24知識管理與數(shù)據(jù)分析實(shí)驗(yàn)室8支持向量機(jī)理論首先, 通過預(yù)先選定的一些非線性映射將輸入空間映射到高維屬性空間, 使得在高維屬性空間中有可能對訓(xùn)練數(shù)據(jù)實(shí)現(xiàn)超平面的分割, 避免了在原輸入空間中進(jìn)行非線性曲面分割計(jì)算。SVM數(shù)據(jù)集形成的分類函數(shù)具有這樣的性質(zhì):它是一組

5、以SV為參數(shù)的非線性函數(shù)的線性組合, 因此分類函數(shù)的表達(dá)式僅和SV的數(shù)量相關(guān), 而獨(dú)立于空間的維度。在處理高維輸入空間的分類時(shí), 這種方式尤其有效。2022/7/24知識管理與數(shù)據(jù)分析實(shí)驗(yàn)室9支持向量機(jī)算法的發(fā)展模糊支持向量機(jī)最小二乘支持向量機(jī)加權(quán)支持向量機(jī)(有偏樣本的加權(quán),有偏風(fēng)險(xiǎn)加權(quán))主動(dòng)學(xué)習(xí)的支持向量機(jī)粗糙集與支持向量機(jī)的結(jié)合基于決策樹的支持向量機(jī)分級聚類的支持向量機(jī)2022/7/24知識管理與數(shù)據(jù)分析實(shí)驗(yàn)室10支持向量機(jī)算法的發(fā)展算法上的提高-Vapnik 在1995 年提出了 “chunking” 算法， Osuna 提出了一種分解算法， Platt 于1998年提出了序貫最小優(yōu)化核

6、函數(shù)的構(gòu)造和參數(shù)的選擇理論研究支持向量機(jī)從兩類問題向多類問題的推廣2022/7/24知識管理與數(shù)據(jù)分析實(shí)驗(yàn)室11支持向量機(jī)的特點(diǎn)（1） 非線性映射是SVM方法的理論基礎(chǔ),SVM利用內(nèi)積核函數(shù)代替向高維空間的非線性映射；（2）對特征空間劃分的最優(yōu)超平面是SVM的目標(biāo),最大化分類邊際的思想是SVM方法的核心；（3）支持向量是SVM的訓(xùn)練結(jié)果,在SVM分類決策中起決定作用的是支持向量。2022/7/24知識管理與數(shù)據(jù)分析實(shí)驗(yàn)室12支持向量機(jī)的特點(diǎn)（4）SVM是一種有堅(jiān)實(shí)理論基礎(chǔ)的新穎的小樣本學(xué)習(xí)方法。它基本上不涉及概率測度及大數(shù)定律等,因此不同于現(xiàn)有的統(tǒng)計(jì)方法。從本質(zhì)上看,它避開了從歸納到演繹的傳統(tǒng)

7、過程,實(shí)現(xiàn)了高效的從訓(xùn)練樣本到預(yù)報(bào)樣本的“轉(zhuǎn)導(dǎo)推理”,大大簡化了分類和回歸等問題。2022/7/24知識管理與數(shù)據(jù)分析實(shí)驗(yàn)室13支持向量機(jī)的特點(diǎn)（5）SVM的最終決策函數(shù)只由少數(shù)的支持向量所確定,計(jì)算的復(fù)雜性取決于支持向量的數(shù)目,而不是樣本空間的維數(shù),這在某種意義上避免了“維數(shù)災(zāi)難”。2022/7/24知識管理與數(shù)據(jù)分析實(shí)驗(yàn)室14支持向量機(jī)的應(yīng)用舉例以在手寫數(shù)字識別和文本分類中的應(yīng)用為例說明。這個(gè)問題通常用來做分類器的測試平臺，最初是美國郵政服務(wù)部門使用手寫郵政編碼自動(dòng)分類郵件的需要提出的。2022/7/24知識管理與數(shù)據(jù)分析實(shí)驗(yàn)室15支持向量機(jī)的應(yīng)用舉例這是一個(gè)可識別性較差的數(shù)據(jù)庫，人工識別

8、平均錯(cuò)誤率是2.5%，用決策樹方法識別錯(cuò)誤率是16.2%，兩層神經(jīng)網(wǎng)絡(luò)中錯(cuò)誤率最小的是5.9%，專門針對該問題設(shè)計(jì)的五層神經(jīng)網(wǎng)絡(luò)錯(cuò)誤率為5.1% (其中利用了大量先驗(yàn)知識)，而用SVM方法得到的錯(cuò)誤率僅為4.0%，且其中直接采用了16X16的字符點(diǎn)陣作為svm的輸入，并沒有進(jìn)行專門的特征提取。2022/7/24知識管理與數(shù)據(jù)分析實(shí)驗(yàn)室16支持向量機(jī)的應(yīng)用舉例文本分類的任務(wù)是將文本文件根據(jù)內(nèi)容分為預(yù)先定義的幾個(gè)類別。很多領(lǐng)域都有這種問題，包括郵件過濾、網(wǎng)頁搜索、辦公自動(dòng)化、主題索引和新聞故事的分類。因?yàn)橐粋€(gè)文件可以分給不止一個(gè)類別，所以這不是一個(gè)多分類問題，而是兩分類問題，即是或不是屬于某類。2

9、022/7/24知識管理與數(shù)據(jù)分析實(shí)驗(yàn)室17支持向量機(jī)的應(yīng)用舉例Joachims等人用傳統(tǒng)的向量空間模型作為輸入訓(xùn)練支持向量機(jī)，表現(xiàn)出比傳統(tǒng)方法如簡單貝葉斯、Rocchio、決策樹的C4.5算法和K近鄰等更好的性能，這是因?yàn)閭鹘y(tǒng)方法在文本的高維向量空間中的推廣性能差，而支持向量機(jī)得到的最大間隔分類器克服了高維空間中的維數(shù)困難。2022/7/24知識管理與數(shù)據(jù)分析實(shí)驗(yàn)室18支持向量機(jī)的不足（1）SVM算法對大規(guī)模訓(xùn)練樣本難以實(shí)施。由于SVM是借助二次規(guī)劃來求解支持向量，而求解二次規(guī)劃將涉及m 階矩陣的計(jì)算（m 為樣本的個(gè)數(shù)），當(dāng)m 數(shù)目很大時(shí)該矩陣的存儲(chǔ)和計(jì)算將耗費(fèi)大量的機(jī)器內(nèi)存和運(yùn)算時(shí)間。20

10、22/7/24知識管理與數(shù)據(jù)分析實(shí)驗(yàn)室19支持向量機(jī)的不足（2）用SVM解決多分類問題存在困難經(jīng)典的支持向量機(jī)算法只給出了二類分類的算法，而在數(shù)據(jù)挖掘的實(shí)際應(yīng)用中，一般要解決多類的分類問題?？梢酝ㄟ^多個(gè)二類支持向量機(jī)的組合來解決。2022/7/24知識管理與數(shù)據(jù)分析實(shí)驗(yàn)室20支持向量機(jī)的研究難點(diǎn)（1）核函數(shù)和參數(shù)的構(gòu)造和選擇缺乏理論指導(dǎo)。核函數(shù)的選擇影響著分類器的性能，如何根據(jù)待解決問題的先驗(yàn)知識和實(shí)際樣本數(shù)據(jù)，選擇和構(gòu)造合適的核函數(shù)、確定核函數(shù)的參數(shù)等問題，都缺乏相應(yīng)的理論指導(dǎo)。2022/7/24知識管理與數(shù)據(jù)分析實(shí)驗(yàn)室21支持向量機(jī)的研究難點(diǎn)（2）訓(xùn)練大規(guī)模數(shù)據(jù)集的問題。如何解決訓(xùn)練速度與訓(xùn)練樣本規(guī)模間的矛盾，測試速度與支持向量數(shù)目間的矛盾，找到對大規(guī)模樣本集有效的訓(xùn)練算法和分類實(shí)現(xiàn)算法，仍是未很好解決的問題。2022/7/24知識管理與數(shù)據(jù)分析實(shí)驗(yàn)室22支持向量機(jī)的研究難點(diǎn)（3）多類分類問題的有效算法與SVM 優(yōu)化設(shè)計(jì)問題。盡管訓(xùn)練多類SVM 問題的算法已被提出，但用于多類分類問題時(shí)的有效算法、多類SVM 的優(yōu)化設(shè)計(jì)仍是一個(gè)需要進(jìn)一步研究的問題。2022/7/24知識管理與數(shù)據(jù)