支撐向量機(jī)快速訓(xùn)練方法研究


本文共計(jì)45頁，23279字；

摘 要

支撐向量機(jī)（Support Vector Machines，簡稱SVM）是基于統(tǒng)計(jì)學(xué)習(xí)理論的一種新的機(jī)器學(xué)習(xí)技術(shù)。由于采用了使用結(jié)構(gòu)風(fēng)險(xiǎn)最小化原則替代經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化原則，它較好的解決了小樣本學(xué)習(xí)問題。又由于采用了核函數(shù)思想，它把非線性空間的問題轉(zhuǎn)換到線性空間，降低了算法的復(fù)雜度。正因?yàn)镾VM理論有較為完備的理論基礎(chǔ)和較好的學(xué)習(xí)性能，使得它成為繼神經(jīng)網(wǎng)絡(luò)研究之后新的研究熱點(diǎn)，并將推動(dòng)機(jī)器學(xué)習(xí)理論和技術(shù)有重大的發(fā)展。盡管SVM理論的性能在許多實(shí)際問題中得到了驗(yàn)證，但是該算法在計(jì)算上存在著一些問題，包括訓(xùn)練算法速度慢、算法復(fù)雜而難以實(shí)現(xiàn)以及檢測階段運(yùn)算量大等等。本文針對(duì)上面的問題，主要對(duì)SVM算法進(jìn)行了研究，并針對(duì)大規(guī)模數(shù)據(jù)集提出一種新的訓(xùn)練方法。為此，本文集中進(jìn)行了下面一些研究工作。
首先對(duì)SVM理論進(jìn)行基本概念上的介紹，并深入探討了SVM算法的基本理論。然后對(duì)四種具體的SVM算法——SVMlight、SMO、BSVM和LIBSVM算法進(jìn)行了深入研究，并利用標(biāo)準(zhǔn)數(shù)據(jù)對(duì)三種算法性能進(jìn)行比較。
其次針對(duì)大規(guī)模訓(xùn)練集，為了克服訓(xùn)練算法速度慢，提高訓(xùn)練速度，提出了一種分塊LIBSVM算法。這種算法將分塊算法和LIBSVM兩種算法相結(jié)合，將大規(guī)模問題分解為許多子塊，并對(duì)每個(gè)子塊進(jìn)行快速優(yōu)化。運(yùn)用這種方法有望使大規(guī)模訓(xùn)練問題得到快速解決。
最后將SVM算法應(yīng)用到舌象分析中。根據(jù)舌象數(shù)據(jù)的特點(diǎn)，分析將SVM應(yīng)用于舌象分析的可行性。

關(guān)鍵詞：支撐向量機(jī),訓(xùn)練算法,CLIBSVM算法,舌象分析
ABSTRACT

Support Vector Machines (SVM) is a new pattern recognition technology, which is based on Statistical Learning Theory. It can solve small-sample learning problems better by using Experiential Risk Minimization in place of Structural Risk Minimization. Moreover, this theory can change the problem in non-linearity space to that in the linearity space in order to reduce the algorithm complexity by using the kernel function idea. Because it has quite perfect theoretical properties and good learning performance, SVM theory becomes the new research hotspot after the research of Artificial Nerve Net and pushes the development in machine learning theory and technology. However, SVM theory performance has been validated in many practical applications, there are still some drawbacks. For example: train speed is slow, algorithm is complex and check phase operation is large, etc. According to above problems, this dissertation mainly focuses on the SVM algorithm research and tries to find a fast training algorithm. So, the following research works are done.
目 錄

1.緒論----------------------------------------------------------------------5
1.1論文背景-------------------------------------------------------------5
1.2論文研究內(nèi)容---------------------------------------------------------6
2.模式識(shí)別系統(tǒng)--------------------------------------------------------------8
2.1模式識(shí)別系統(tǒng)概述-----------------------------------------------------8
2.2支撐向量機(jī)在模式識(shí)別中的應(yīng)用----------------------------------------10
3.統(tǒng)計(jì)學(xué)習(xí)理論和支撐向量機(jī)原理---------------------------------------------11
3.1統(tǒng)計(jì)學(xué)習(xí)理論的主要內(nèi)容----------------------------------------------11
3.1.1 邊界理論與VC維-----------------------------------------------11
3.1.2 推廣誤差邊界--------------------------------------------------11
3.1.3 結(jié)構(gòu)風(fēng)險(xiǎn)最小化原理--------------------------------------------12
3.2支撐向量機(jī)的原理----------------------------------------------------14
3.2.1 最優(yōu)分類面----------------------------------------------------14
3.2.2 線性可分情況--------------------------------------------------15
3.2.3 線性不可分情況------------------------------------------------17
3.2.4 非線性情況----------------------------------------------------18
4.支撐向量機(jī)快速訓(xùn)練算法及其實(shí)現(xiàn)-------------------------------------------19
4.1支撐向量機(jī)訓(xùn)練算法的研究現(xiàn)狀----------------------------------------19
4.2 SVMlight算法----------------------------------------------------------20
4.2.1算法的基本思想-------------------------------------------------20
4.2.2算法原理-------------------------------------------------------21
4.3 SMO算法-------------------------------------------------------------25
4.3.1算法的基本思想-------------------------------------------------25
4.3.2算法原理-------------------------------------------------------25
4.4 BSVM算法------------------------------------------------------------29
4.4.1算法的基本思想-------------------------------------------------29
4.4.2算法原理-------------------------------------------------------30
4.5 LIBSVM算法----------------------------------------------------------31
4.5.1算法的基本思想-------------------------------------------------31
4.5.2算法原理-------------------------------------------------------31
4.6四種算法的比較實(shí)驗(yàn)---------------------------------------------------34
5.一種超大規(guī)模訓(xùn)練問題的解決方法-------------------------------------------38
5.1四種算法的優(yōu)缺點(diǎn)分析------------------------------------------------38
5.2大規(guī)模訓(xùn)練問題的解決方案--------------------------------------------38
5.2.1分塊LIBSVM方法的提出------------------------------------------38
5.2.2分塊LIBSVM算法的實(shí)現(xiàn)------------------------------------------39
5.2.3五種算法的比較實(shí)驗(yàn)及結(jié)果分析-----------------------------------40
6.支撐向量機(jī)在舌象分析中的應(yīng)用---------------------------------------------41
6.1計(jì)算機(jī)舌象分析方法簡介----------------------------------------------41
6.2支撐向量機(jī)在舌象分析中的應(yīng)用思路------------------------------------41
結(jié)束語---------------------------------------------------------------------43
致謝-----------------------------------------------------------------------44
參考文獻(xiàn)-------------------------------------------------------------------45
參考文獻(xiàn)

1. 邊肇祺，張學(xué)工，模式識(shí)別（第2版），北京：清華大學(xué)出版社，1999.12.
2. Richard O. Duda and Peter E. Hart and David G. Stork，李宏樂，姚天翔譯，Pattern Classification，北京：機(jī)械工業(yè)出版社，2003.9.
3. 范昕煒，支撐向量機(jī)算法的研究及其應(yīng)用，浙江大學(xué)博士畢業(yè)論文，2003.5.
4. 沈培華，支持矢量機(jī)的算法研究和應(yīng)用，碩士畢業(yè)論文，2002.1.
5. Thorsten Joachims, Making Large-Scale SVM Learning Practical. LS-8 Report 24. Dortmund, USA. 15. June, 1998.