支持向量机(SVM)的实现

1、模式识别课程大作业报告支持向量机（SVM）的实现姓名： 学号：专业： 任课教师： 研究生导师： 内容摘要支持向量机是一种十分经典的分类方法，它不仅是模式识别学科中的重要内容，而且在图像处理领域中得到了广泛应用。现在，很多图像检索、图像分类算法的实现都以支持向量机为基础。本次大作业的内容以开源计算机视觉库OpenCV为基础，编程实现支持向量机分类器，并对标准数据集进行测试，分别计算出训练样本的识别率和测试样本的识别率。本报告的组织结构主要分为3大部分。第一部分简述了支持向量机的原理；第二部分介绍了如何利用OpenCV来实现支持向量机分类器；第三部分给出在标准数据集上的测试结果。一、支持向量机原理

2、概述在高维空间中的分类问题实际上是寻找一个超平面，将两类样本分开，这个超平面就叫做分类面。两类样本中离分类面最近的样本到分类面的距离称为分类间隔。最优超平面指的是分类间隔最大的超平面。支持向量机实质上提供了一种利用最优超平面进行分类的方法。由最优分类面可以确定两个与其平行的边界超平面。通过拉格朗日法求解最优分类面，最终可以得出结论：实际决定最优分类面位置的只是那些离分类面最近的样本。这些样本就被称为支持向量，它们可能只是训练样本中很少的一部分。支持向量如图1所示。图1图1中，H是最优分类面，H1和H2别是两个边界超平面。实心样本就是支持向量。由于最优超平面完全是由这些支持向量决定的，所以这种方

3、法被称作支持向量机（SVM）。以上是线性可分的情况，对于线性不可分问题，可以在错分样本上增加一个惩罚因子来干预最优分类面的确定。这样一来，最优分类面不仅由离分类面最近的样本决定，还要由错分的样本决定。这种情况下的支持向量就由两部分组成：一部分是边界支持向量；另一部分是错分支持向量。对于非线性的分类问题，可以通过特征变换将非线性问题转化为新空间中的线性问题。但是这样做的代价是会造成样本维数增加，进而导致计算量急剧增加，这就是所谓的“维度灾难”。为了避免高维空间中的计算，可以引入核函数的概念。这样一来，无论变换后空间的维数有多高，这个新空间中的线性支持向量机求解都可以在原空间通过核函数来进行。常用

4、的核函数有多项式核、高斯核（径向基核）、Sigmoid函数。二、支持向量机的实现OpenCV是开源计算机视觉库，它在图像处理领域得到了广泛应用。OpenCV中包含许多计算机视觉领域的经典算法，其中的机器学习代码部分就包含支持向量机的相关内容。OpenCV中比较经典的机器学习示例是“手写字母分类”。OpenCV中给出了用支持向量机实现该示例的代码。本次大作业的任务是研究OpenCV中的支持向量机代码，然后将其改写为适用于所有数据库的通用程序，并用标准数据集对算法进行测试。本实验中使用的OpenCV版本是2.4.4，实验平台为Visual Studio 2010软件平台。OpenCV读取的输入数据

5、格式为“.data”文件。该文件记录了所有数据样本的特征向量和标签。OpenCV自带的“letter-recognition”数据集是手写字母数据集。其中共包含20000个样本，前16000个用来训练，后4000个用来测试。样本是16维的特征向量。每条样本在文件中按行存放。每行共有17个字段，第1个字段是样本的标签，以字符形式给出；后面16个字段分别是样本的16个特征，以数字形式给出。所有字段之间均以逗号分隔。图2图2中展示了“.data”文件中样本的存储样式。自行生成“.data”文件的过程十分简单。只需要新建一个“.txt”文件，对其内容进行修改之后，直接把后缀改为“.data”即可。在O

6、penCV给出的支持向量机示例程序中，可调参数大约有十多个，这些参数的调整比较复杂。为了方便使用该程序，可以将其中重要的参数从程序段中挑选出来，并制作宏定义。这些重要参数包括：总样本个数、用于训练的样本个数（总样本个数-训练样本个数=测试样本个数）、特征向量的维数、选取的核函数类型。可调参数如图3所示：图3 在更换新的数据集时，只需要在宏定义部分修改“PATH”后的路径即可，其他参数的修改也都在这里进行，无需再到代码段内进行修改。其中，宏定义“KERNEL”用来确定SVM采用何种核函数。执行程序后，可以显示出训练样本和测试样本的识别率。通过将程序中分类数组的值输出，还可以在原有程序基础上添加显

7、示测试样本标签的功能。对“letter-recognition”数据集进行分类得到的结果如图4所示：图4 图4展示了4000个测试样本标签和训练样本识别率以及测试样本识别率。可以观察到训练样本的识别率为64.36%，测试样本的识别率为60.75%。将图4中展示的测试样本标签与“.data”文件中的标签对比，可以直观地观察到哪个数据判断错误。图5展示了程序输出的测试样本标签与“.data”文件中标签的对应关系。 (a) (b) 图5 观察图5可以发现，第一行字母P的识别是正确的，而第三行的预测出现了错误。样本集中的数据为“O”，但支持向量机将其错分为“B”。按上述方法可以一一对照测试样本的预测结

8、果是否正确。接下来，采用其他核函数进行分类。图6展示的是径向基函数的分类效果。图6观察图6可以看出，采用径向基函数可以获得极高的样本识别率，可达100%。但是测试样本的识别率为51.25%，比起线性基函数有所下降，说明其泛化能力（即推广能力）有限。测试表明，对于“letter-recognition”，采用多项式基函数和Sigmoid基函数分类的识别率更低，因此对此数据集的分类应该采用线性核函数。三、标准数据集测试前一部分展示了OpenCV自带的“letter-recognition”数据集的测试效果。为了测试编写的程序的通用性，接下来对其他标准数据集进行测试。数据集可以从“http:/arc

9、/ml/”下载，这个网址上提供了上万个用于机器学习的数据集。接下来分别展示“iris”数据集和“wine”数据集上的测试结果。（1）“iris”数据集“iris”数据集是鸢尾花数据集。其中共包含150个样本，每个样本是一个4维的特征向量，这4个特征分别是萼片长度、萼片宽度、花瓣长度和花瓣宽度。数据的标签总共有三类：“S”代表刺芒野古草，“E”代表杂色鸢尾花，“I”代表维尔吉尼卡。它们分别是三种不同的鸢尾花品种。该数据集如图7所示：图7 在本实验中，用前130个数据作为训练样本，后20个数据作为测试样本。选定相应的参数如图8所示：图8 图8中，选取核函数为线性核函

10、数。按照图8所示的参数执行程序，得到的结果如图9所示：图9 由图9可知，对于“iris”数据集，训练样本的识别率为98.46%，测试样本的识别率为90.00%。由数据可以看出，支持向量机对“iris”数据集的分类效果显然要优于“letter-recognition”数据集。这可能和数据集本身有关，“iris”数据集特征的可分性更好。接下来，变换核函数来观察分类效果。图10是采用径向基核函数得到的结果。图10图10中，训练样本的识别率比采用线性核函数时略有提升，但测试样本的识别率没有变化，因此可以认为采用径向基核函数与线性核函数的分类效果是基本相同的。当采用Sigmoid函数进行分类时，分类效果

11、显然要差很多。该分类效果如图11所示。图11图11中，训练样本和测试样本的识别率都很低，因此“iris”数据集显然不适合用Sigmoid函数进行分类。 以上实验结果表明，核函数的选取对于支持向量机的分类效果有至关重要的影响。（2）“wine”数据集“wine”数据集是红酒数据集。其中共包含178个样本，每个样本是一个13维的特征向量，其中包含酒精度、年份等特征。数据的标签总共有三类：“M”、“H”、“L”。它们分别代表三类不同的红酒。该数据集如图12所示：图12本实验用前125个数据作为训练样本，后53个数据作为测试样本。选定相应的参数如图13所示：2图13图13中，核函数选定为线性核函数。按

12、照上述参数设置执行程序，得到的结果如图14所示：图14由图14可得，对于“wine”数据集，训练样本的识别率为88.00%，测试样本的识别率为37.74%。训练样本的识别率较高，但测试样本的识别率却较低。这说明该学习过程的泛化能力较差。这可能由于样本数量有限，支持向量机方法很难从这么有限的样本中训练出较为理想的分类器。接下来，尝试采用其他核函数的分类效果。结果发现，其他和函数的分类效果并没有线性核函数的分类效果好。当采用径向基核函数时，训练样本的识别率可达100%，但测试样本的识别率变得非常低。该结果如图15所示。图15可见，对于“wine”数据集来讲，采用径向基核函数虽然能使训练样本识别率最

13、高，但其泛化能力最差，因此对解决实际问题没有任何帮助。综合比较上述结果，可以发现径向基函数在大多数情况下都可以获得较高的训练样本识别率，即经验风险很小。但是，测试样本的识别率无法保证，对于某些数据集的泛化能力有限。致 谢今后，我会从事机器学习方向的研究。模式识别课程的内容对我的专业方向有很大帮助，令我受益匪浅。尤其是在本次大作业过程中，支持向量机的编程实现工作大大加深了我对支持向量机原理的理解，为我今后的研究工作打下了坚实基础。模式识别课程的学习是我研究道路上的一个良好开端，具有十分重要的意义。本学期的模式识别课程令我受益颇多。在此，诚挚地感谢李建更老师的辛勤付出！附录：源程序代码#inclu

14、de "opencv2/core/core_c.h"#include "opencv2/ml/ml.hpp"#include <cstdio>#include <vector>/*设置文件路径*/#define PATH "./letter-recognition.data"/*设置样本个数*/#define SAMPLE 20000/*设置训练样本个数*/#define TRAIN 16000/*设置特征向量维数*/#define VECTOR 16/*/*读取数据*/static intread_num_c

15、lass_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; el_ptr = new floatvar_count+1; storage = cv

16、CreateMemStorage(); seq = cvCreateSeq( 0, sizeof(*seq), (var_count+1)*sizeof(float), 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 <= var_count ) break; cvSeqPush( seq, el_ptr ); fclose(f); *data = cvCreateMat( seq->total, var_count, CV_32F ); *responses = cvCreateMat( seq->total, 1, CV_32F ); cvStartReadSeq( seq, &reader ); for( i = 0; i < seq->total; i+ ) const float* sdata = (floa

18、t*)reader.ptr + 1; float* ddata = data0->data.fl + var_count*i; float* dr = responses0->data.fl + i; for( j = 0; j < var_count; j+ ) ddataj = sdataj; *dr = sdata-1; CV_NEXT_SEQ_ELEM( seq->elem_size, reader ); cvReleaseMemStorage( &storage ); delete el_ptr; return 1;/*支持向量机分类器*/static

19、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; int ok = read_num_class_data( data_filename, VECTOR, &data, &responses ); if( !ok ) printf( "无法读取数据库 %sn", da

20、ta_filename ); return -1; /* SVM 参数 */ CvSVMParams param; param.kernel_type=CvSVM:LINEAR; param.svm_type=CvSVM:C_SVC; param.C=1;/*/ printf( "数据库 %s 已经被加载n", data_filename ); nsamples_all = SAMPLE; ntrain_samples = TRAIN; var_count = data->cols;/*训练分类器*/ printf( "正在训练SVM分类器.n")

21、; cvGetRows( data, &train_data, 0, ntrain_samples ); CvMat* train_resp = cvCreateMat( ntrain_samples, 1, CV_32FC1); for (int i = 0; i < ntrain_samples; i+) train_resp->data.fli = responses->data.fli; svm.train(&train_data, train_resp, 0, 0, param);/*开始对测试样本分类*/ std:vector<float&g

22、t; _sample(var_count * (nsamples_all); CvMat sample = cvMat( nsamples_all , VECTOR, CV_32FC1, &_sample0 ); std:vector<float> true_results(nsamples_all ); for (int j = 0; j < nsamples_all; j+) float *s = data->data.fl + j * var_count; for (int i = 0; i < var_count; i+) sample.data.

23、fl(j) * var_count + i = si; true_resultsj = responses->data.flj; CvMat *result = cvCreateMat(1, nsamples_all, CV_32FC1); printf("分类中.n"); svm.predict(&sample, result);/*显示测试样本的标签*/printf("测试样本的标签预测结果如下：n");for (int i = ntrain_samples; i < nsamples_all ; i+) printf("

24、;测试样本%d=%cn",i-ntrain_samples+1,char(result->data.fli); /*计算识别率*/ printf("/*显示识别率*/n");/训练样本识别率int true_resp = 0; for (int i = 0; i < ntrain_samples; i+) if (result->data.fli = true_resultsi) true_resp+; printf("训练样本识别率 = %.2f%n", (float)true_resp / (ntrain_samples) * 100);/测试样本识别率true_resp = 0; for (int i = n