支持向量機的實現

1、模式識別課程大作業(yè)報告-支持向量機（SVM的實現姓名：學號：專業(yè)：任課教師： 研究生導師：內容摘要支持向量機是一種十分經典的分類方法， 它不僅是模式識別學科中的重要內 容，而且在圖像處理領域中得到了廣泛應用?，F在，很多圖像檢索、圖像分類算 法的實現都以支持向量機為基礎。本次大作業(yè)的內容以開源計算機視覺庫 OpenCV為基礎，編程實現支持向量機分類器，并對標準數據集進行測試，分別 計算出訓練樣本的識別率和測試樣本的識別率。本報告的組織結構主要分為 3 大部分。第一部分簡述了支持向量機的原理； 第二部分介紹了如何利用 Ope nCV來實現支持向量機分類器；第三部分給出在標 準數據集上的測試結果。、

2、支持向量機原理概述在高維空間中的分類問題實際上是尋找一個超平面， 將兩類樣本分開， 這個 超平面就叫做分類面。 兩類樣本中離分類面最近的樣本到分類面的距離稱為分類 間隔。最優(yōu)超平面指的是分類間隔最大的超平面。 支持向量機實質上提供了一種 利用最優(yōu)超平面進行分類的方法。 由最優(yōu)分類面可以確定兩個與其平行的邊界超 平面。通過拉格朗日法求解最優(yōu)分類面， 最終可以得出結論： 實際決定最優(yōu)分類 面位置的只是那些離分類面最近的樣本。 這些樣本就被稱為支持向量， 它們可能 只是訓練樣本中很少的一部分。支持向量如圖 1 所示。圖1圖1中，H是最優(yōu)分類面，H1和H2別是兩個邊界超平面。實心樣本就是支持向 量。由

3、于最優(yōu)超平面完全是由這些支持向量決定的， 所以這種方法被稱作支持向 量機（ SVM）。以上是線性可分的情況， 對于線性不可分問題， 可以在錯分樣本上增加一個 懲罰因子來干預最優(yōu)分類面的確定。 這樣一來，最優(yōu)分類面不僅由離分類面最近 的樣本決定，還要由錯分的樣本決定。這種情況下的支持向量就由兩部分組成： 一部分是邊界支持向量；另一部分是錯分支持向量。對于非線性的分類問題， 可以通過特征變換將非線性問題轉化為新空間中的 線性問題。但是這樣做的代價是會造成樣本維數增加， 進而導致計算量急劇增加， 這就是所謂的“維度災難” 。為了避免高維空間中的計算，可以引入核函數的概 念。這樣一來， 無論變換后空間

4、的維數有多高， 這個新空間中的線性支持向量機 求解都可以在原空間通過核函數來進行。 常用的核函數有多項式核、 高斯核（徑 向基核）、 Sigmoid 函數。二、支持向量機的實現Ope nCV是開源計算機視覺庫，它在圖像處理領域得到了廣泛應用。Ope nCV中包含許多計算機視覺領域的經典算法， 其中的機器學習代碼部分就包含支持向 量機的相關內容。OpenCW比較經典的機器學習示例是“手寫字母分類” OpenCV 中給出了用支持向量機實現該示例的代碼。本次大作業(yè)的任務是研究Ope nCW的支持向量機代碼， 然后將其改寫為適用于所有數據庫的通用程序， 并用標準數 據集對算法進行測試。本實驗中使用的O

5、pe nCV版本是，實驗平臺為 VisualStudio 2010 軟件平臺。OpenCV讀取的輸入數據格式為“ .data ”文件。該文件記錄了所有數據樣本 的特征向量和標簽。OpenCV自帶的“ letter-recognition”數據集是手寫字母數據集。 其中共包含 20000個樣本，前 16000個用來訓練， 后4000個用來測試。 樣本是 16維的特征向量。 每條樣本在文件中按行存放。 每行共有 17個字段，第 1個字段是樣本的標簽，以字符形式給出；后面 16個字段分別是樣本的 16 個特 征，以數字形式給出。所有字段之間均以逗號分隔。圖2圖2中展示了 “.data ”文件中樣本的

6、存儲樣式。自行生成“ .data ”文件的過程 十分簡單。只需要新建一個“ .txt ”文件，對其內容進行修改之后，直接把后綴 改為“ .data ”即可。在OpenCV合出的支持向量機示例程序中，可調參數大約有十多個，這些參 數的調整比較復雜。 為了方便使用該程序， 可以將其中重要的參數從程序段中挑 選出來，并制作宏定義。這些重要參數包括：總樣本個數、用于訓練的樣本個數 （總樣本個數 - 訓練樣本個數 =測試樣本個數）、特征向量的維數、選取的核函數 類型?？烧{參數如圖 3 所示：圖3在更換新的數據集時，只需要在宏定義部分修改“ PATH后的路徑即可，其他參 數的修改也都在這里進行，無需再到代

7、碼段內進行修改。其中，宏定義“KERNEL 用來確定SVMK用何種核函數。執(zhí)行程序后， 可以顯示出訓練樣本和測試樣本的識別率。 通過將程序中分類 數組的值輸出，還可以在原有程序基礎上添加顯示測試樣本標簽的功能。對 “l(fā)etter-recognition ”數據集進行分類得到的結果如圖 4 所示：圖4圖 4 展示了 4000 個測試樣本標簽和訓練樣本識別率以及測試樣本識別率?？梢?觀察到訓練樣本的識別率為 %，測試樣本的識別率為 %。將圖 4中展示的測試樣本標簽與“ .data ”文件中的標簽對比，可以直觀地觀察到哪個數據判斷錯誤。圖5 展示了程序輸出的測試樣本標簽與“ .data ”文件中標簽

8、的對應關系。(a) (b)圖5觀察圖5可以發(fā)現，第一行字母P的識別是正確的，而第三行的預測出現了錯誤。 樣本集中的數據為“ O,但支持向量機將其錯分為“ B”。按上述方法可以一一對 照測試樣本的預測結果是否正確。 接下來， 采用其他核函數進行分類。 圖 6 展示 的是徑向基函數的分類效果。圖6觀察圖 6 可以看出，采用徑向基函數可以獲得極高的樣本識別率，可達100%。但是測試樣本的識別率為 %，比起線性基函數有所下降，說明其泛化能力(即推 廣能力)有限。測試表明，對于“ letter-recognition ”，采用多項式基函數和 Sigmoid 基函數分類的識別率更低，因此對此數據集的分類應

9、該采用線性核函 數。三、標準數據集測試前一部分展示了 OpenCV自帶的“l(fā)etter-recognition ”數據集的測試效果。 為了測試編寫的程序的通用性， 接下來對其他標準數據集進行測試。 數據集可以 從“下載，這個網址上提供了上萬個用于機器學習的數據集。接下來分別展示“ iris ”數據集和“ wine ”數據集上的測試結果。(1)“iris ”數據集“iris ”數據集是鳶尾花數據集。 其中共包含 150個樣本， 每個樣本是一個 4維的特征向量， 這 4 個特征分別是萼片長度、 萼片寬度、花瓣長度和花瓣寬度。 數據的標簽總共有三類：“ S”代表刺芒野古草，“ E”代表雜色鳶尾花，“

10、 I”代表 維爾吉尼卡。它們分別是三種不同的鳶尾花品種。該數據集如圖 7 所示：圖7在本實驗中，用前 130個數據作為訓練樣本，后 20 個數據作為測試樣本選定相應的參數如圖 8 所示：圖8圖 8 中，選取核函數為線性核函數。 按照圖 8 所示的參數執(zhí)行程序， 得到的結果 如圖 9 所示：圖9由圖 9可知，對于“ iris ”數據集，訓練樣本的識別率為 %，測試樣本的識別率 為 %。由數據可以看出，支持向量機對“iris ”數據集的分類效果顯然要優(yōu)于“ letter-recognition ”數據集。這可能和數據集本身有關， “iris ”數據集特 征的可分性更好。接下來，變換核函數來觀察分類

11、效果。圖 10 是采用徑向基核函數得到的結 果。圖 10圖 10 中，訓練樣本的識別率比采用線性核函數時略有提升，但測試樣本的識別 率沒有變化，因此可以認為采用徑向基核函數與線性核函數的分類效果是基本相 同的。當采用 Sigmoid 函數進行分類時， 分類效果顯然要差很多。 該分類效果如 圖 11 所示。圖 11圖 11 中，訓練樣本和測試樣本的識別率都很低，因此“ iris ”數據集顯然不適 合用 Sigmoid 函數進行分類。以上實驗結果表明，核函數的選取對于支持向量機的分類效果有至關重要的 影響。(2) wine ”數據集“wine”數據集是紅酒數據集。其中共包含178個樣本，每個樣本是

12、一個13維的特征向量，其中包含酒精度、年份等特征。數據的標簽總共有三類：“ M、H、“L”。它們分別代表三類不同的紅酒。該數據集如圖 12所示:圖 12本實驗用前 125個數據作為訓練樣本，后 53 個數據作為測試樣本。選定相 應的參數如圖 13 所示：2圖 13圖 13 中，核函數選定為線性核函數。按照上述參數設置執(zhí)行程序，得到的結果 如圖 14 所示：圖 14由圖14可得，對于“wine”數據集，訓練樣本的識別率為%測試樣本的識別率 為%。訓練樣本的識別率較高，但測試樣本的識別率卻較低。這說明該學習過程 的泛化能力較差。 這可能由于樣本數量有限， 支持向量機方法很難從這么有限的 樣本中訓練

13、出較為理想的分類器。接下來，嘗試采用其他核函數的分類效果。 結果發(fā)現， 其他和函數的分類效 果并沒有線性核函數的分類效果好。 當采用徑向基核函數時， 訓練樣本的識別率 可達 100%，但測試樣本的識別率變得非常低。該結果如圖 15所示。圖 15可見，對于“wine”數據集來講，采用徑向基核函數雖然能使訓練樣本識別 率最高，但其泛化能力最差，因此對解決實際問題沒有任何幫助。綜合比較上述結果， 可以發(fā)現徑向基函數在大多數情況下都可以獲得較高的 訓練樣本識別率，即經驗風險很小。但是，測試樣本的識別率無法保證，對于某 些數據集的泛化能力有限。致謝今后，我會從事機器學習方向的研究。模式識別課程的內容對我

14、的專業(yè)方向 有很大幫助，令我受益匪淺。尤其是在本次大作業(yè)過程中，支持向量機的編程實 現工作大大加深了我對支持向量機原理的理解， 為我今后的研究工作打下了堅實 基礎。模式識別課程的學習是我研究道路上的一個良好開端， 具有十分重要的意 義。本學期的模式識別課程令我受益頗多。 在此，誠摯地感謝李建更老師的辛勤 付出！附錄：源程序代碼#include opencv2/core/#include opencv2/ml/#include #include /*設置文件路徑 */#define PATH ./*設置樣本個數 */#define SAMPLE 20000/*設置訓練樣本個數 */#define

15、 TRAIN 16000設置特征向量維數*#define VECTOR 16*讀取數據 *static int read_num_class_data( const char* filename, int var_count,CvMat* data, CvMat* responses )const int M = 1024;FILE* f = fopen( filename, rt );CvMemStorage* storage;CvSeq* seq;char bufM+2;float* el_ptr;CvSeqReader reader;int i, j;if( !f ) return 0;

16、el_ptr = new floatvar_count+1;storage = cvCreateMemStorage();(var_count+1)*sizeof(float),seq = cvCreateSeq( 0, sizeof(*seq), storage );for(;)char* ptr;if( !fgets( buf, M, f ) | !strchr( buf, , ) ) break;el_ptr0 = buf0;ptr = buf+2;for( i = 1; i = var_count; i+ )int n = 0;sscanf( ptr, %f%n, el_ptr + i

17、, &n ); ptr += n + 1;if( i total, var_count, CV_32F );*responses = cvCreateMat( seq-total, 1, CV_32F );cvStartReadSeq( seq, &reader );for( i = 0; i total; i+ )const float* sdata = (float*) + 1;float* ddata = data0- + var_count*i;float* dr = responses0- + i;for( j = 0; j elem_size, reader );cvRelease

18、MemStorage( &storage );delete el_ptr;return 1;支持向量機分類器*static int build_svm_classifier( char* data_filename )CvMat* data = 0;CvMat* responses = 0;CvMat train_data;int nsamples_all = 0, ntrain_samples = 0; int var_count;CvSVM svm;&responses );int ok = read_num_class_data( data_filename, VECTOR,&data,

19、 if( !ok )printf( 無法讀取數據庫 %sn, data_filename ); return -1;SVM參數*CvSVMParams param;=CvSVM:LINEAR;=CvSVM:C_SVC;=1;* printf( 數據庫 %s 已經被加載 n, data_filename ); nsamples_all = SAMPLE;ntrain_samples = TRAIN;var_count = data-cols;訓練分類器*printf(正在訓練 SVM分類器.n);cvGetRows( data, &train_data, 0, ntrain_samples );

20、CvMat* train_resp = cvCreateMat( ntrain_samples, 1, CV_32FC1);for (int i = 0; i i = responses-i; (&train_data, train_resp, 0, 0, param);開始對測試樣本分類*printf(/*顯示識別率 */n);std:vector _sample(var_count * (nsamples_all);CvMat sample = cvMat( nsamples_all , VECTOR, CV_32FC1, &_sample0 ); std:vector true_results(nsamples_all );for (int j = 0; j + j * var_count;for (int i = 0; i j;CvMat *result = cvCreateMat(1, nsamples_all, CV_32FC1);printf(分類中 .n);(&sample, result);顯示測試樣本的標簽*printf( 測試樣本的標簽預測結果如下： n);