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


本文共計45頁，23279字；

摘 要

支撐向量機(jī)（Support Vector Machines，簡稱SVM）是基于統(tǒng)計學(xué)習(xí)理論的一種新的機(jī)器學(xué)習(xí)技術(shù)。由于采用了使用結(jié)構(gòu)風(fēng)險最小化原則替代經(jīng)驗風(fēng)險最小化原則，它較好的解決了小樣本學(xué)習(xí)問題。又由于采用了核函數(shù)思想，它把非線性空間的問題轉(zhuǎn)換到線性空間，降低了算法的復(fù)雜度。正因為SVM理論有較為完備的理論基礎(chǔ)和較好的學(xué)習(xí)性能，使得它成為繼神經(jīng)網(wǎng)絡(luò)研究之后新的研究熱點，并將推動機(jī)器學(xué)習(xí)理論和技術(shù)有重大的發(fā)展。盡管SVM理論的性能在許多實際問題中得到了驗證，但是該算法在計算上存在著一些問題，包括訓(xùn)練算法速度慢、算法復(fù)雜而難以實現(xiàn)以及檢測階段運(yùn)算量大等等。本文針對上面的問題，主要對SVM算法進(jìn)行了研究，并針對大規(guī)模數(shù)據(jù)集提出一種新的訓(xùn)練方法。為此，本文集中進(jìn)行了下面一些研究工作。
首先對SVM理論進(jìn)行基本概念上的介紹，并深入探討了SVM算法的基本理論。然后對四種具體的SVM算法——SVMlight、SMO、BSVM和LIBSVM算法進(jìn)行了深入研究，并利用標(biāo)準(zhǔn)數(shù)據(jù)對三種算法性能進(jìn)行比較。
其次針對大規(guī)模訓(xùn)練集，為了克服訓(xùn)練算法速度慢，提高訓(xùn)練速度，提出了一種分塊LIBSVM算法。這種算法將分塊算法和LIBSVM兩種算法相結(jié)合，將大規(guī)模問題分解為許多子塊，并對每個子塊進(jìn)行快速優(yōu)化。運(yùn)用這種方法有望使大規(guī)模訓(xùn)練問題得到快速解決。
最后將SVM算法應(yīng)用到舌象分析中。根據(jù)舌象數(shù)據(jù)的特點，分析將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.模式識別系統(tǒng)--------------------------------------------------------------8
2.1模式識別系統(tǒng)概述-----------------------------------------------------8
2.2支撐向量機(jī)在模式識別中的應(yīng)用----------------------------------------10
3.統(tǒng)計學(xué)習(xí)理論和支撐向量機(jī)原理---------------------------------------------11
3.1統(tǒng)計學(xué)習(xí)理論的主要內(nèi)容----------------------------------------------11
3.1.1 邊界理論與VC維-----------------------------------------------11
3.1.2 推廣誤差邊界--------------------------------------------------11
3.1.3 結(jié)構(gòu)風(fēng)險最小化原理--------------------------------------------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)練算法及其實現(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四種算法的比較實驗---------------------------------------------------34
5.一種超大規(guī)模訓(xùn)練問題的解決方法-------------------------------------------38
5.1四種算法的優(yōu)缺點分析------------------------------------------------38
5.2大規(guī)模訓(xùn)練問題的解決方案--------------------------------------------38
5.2.1分塊LIBSVM方法的提出------------------------------------------38
5.2.2分塊LIBSVM算法的實現(xiàn)------------------------------------------39
5.2.3五種算法的比較實驗及結(jié)果分析-----------------------------------40
6.支撐向量機(jī)在舌象分析中的應(yīng)用---------------------------------------------41
6.1計算機(jī)舌象分析方法簡介----------------------------------------------41
6.2支撐向量機(jī)在舌象分析中的應(yīng)用思路------------------------------------41
結(jié)束語---------------------------------------------------------------------43
致謝-----------------------------------------------------------------------44
參考文獻(xiàn)-------------------------------------------------------------------45
參考文獻(xiàn)

1. 邊肇祺，張學(xué)工，模式識別（第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.