支持向量机的实现

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

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

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

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

5、sualStudio 2010软件平台。OpenCV读取的输入数据格式为“ .data”文件。该文件记录了所有数据样本的特征向量和标签。OpenCV自带的“ letter-recognition”数据集是手写字母数据集。其中共包含20000个样本，前16000个用来训练，后4000个用来测试。样 本是16维的特征向量。每条样本在文件中按行存放。每行共有 17个字段，第1 个字段是样本的标签，以字符形式给出；后面16个字段分别是样本的16个特征， 以数字形式给出。所有字段之间均以逗号分隔。Tj 2a 8j 3j 5 打 & 13 0, 610j & 0& 0, 8I, 5

6、 12a 3,7, £ 10,5,5, 43133 39, 2, 8a £ 10 D, £ 11, 6, & 6,10, E 2, E10, 3九 3, 7, 39 N.L 11, 6. 6, 3, 5 玄 4,乞 4,4,珂 610, 2S 8 &1, 3 L, 1, 8, 6,6> 6f 6,5,9175,10Sf 4,11, 5, 8j 3j 8j & 6,9,5,6, 6j Oj & 9； 7 B,札 2, 5 2 4 8, J 6,6.理& 7,10 h Lf 1, 3,2,1, & N 2,2,8J

7、 2, & 1J 6J 2,7 L Z N 2 4, 2,10, 6, Z 6,12,4& b 6,1, T JI, 11,15,13, 9, 7,13, Z 6, 2,12. 1. 9, 8,1, 1, 3 X, 3, 9, 5, 7,3,8f 5, 6, & N & 6f 7Q 6,13, 4 化 £ 6* 7,氐 3.10. J 玄 59, 5 8图2图2中展示了“ .data”文件中样本的存储样式。自行生成“ .data”文件的过程十 分简单。只需要新建一个“ .txt ”文件，对其容进行修改之后，直接把后缀改为“.data 即可。在OpenC

8、V给出的支持向量机示例程序中，可调参数大约有十多个，这些参 数的调整比较复杂。为了方便使用该程序，可以将其中重要的参数从程序段中挑 选出来，并制作宏定义。这些重要参数包括：总样本个数、用于训练的样本个数（总样本个数-训练样本个数=测试样本个数）、特征向量的维数、选取的核函数 类型。可调参数如图3所示：_/*“*nm*i殳置 文件 3&径 *»*i*m*：*#*/#define PATH " ./letter-teccgnition. dataft/*水*杠*）殳皆 样本 个 数* 木釈*木 *：+*/Jfdefine SAMPLE 20000/*：殳置 <|

9、练样 本 个勘 * * * * * 床* * * 农* * * * * */define TRAIN 16000/*设養 特征向蛍维數* *C* * * * * * */define VECTOR 16/*和*和*和* 选 軽核頤埶类 理* m* */#defina KERNEL 1"KERNEL養数说明；佃纸性檢函数i压參项式核函繳；左遵向葛（高斷）核函册4勺1師0诃函数。 图3在更换新的数据集时，只需要在宏定义部分修改“PATH ”后的路径即可，其他参数的修改也都在这里进行，无需再到代码段进行修改。其中，宏定义“ KERNEL 用来确定SVM采用何种核函数。执行程序后，可以显示出

10、训练样本和测试样本的识别率。通过将程序中分类数组的值输出，还可以在原有程序基础上添加显示测试样本标签的功能。对“ letter-recog nitio n”数据集进行分类得到的结果如图4所示：因 <:W nd疗:enfij2cnnc.emc9 12 98 o ft O9 S 9 93 3 3 3Ll-XIrm工1!是疋J - . 二 J 二 J - i -/-/ - - - -/- - _ £ - J - - c£二 E 二 £二丿二丄二 > r.T:l< = < 尸!=!K “严=. X =严亠严左;尸!I J-T'B-CT=X詡

11、疔率绩 99sas 継 35.4QE 识识M 试更试试篡试试试建试试-出舌已円恐IT.,试"练<按=60.75X图4展示了 4000个测试样本标签和训练样本识别率以及测试样本识别率。可以观察到训练样本的识别率为64.36%,测试样本的识别率为60.75%。将图4中展示的测试样本标签与“ .data”文件中的标签对比，可以直观地观察到哪个数据判 断错误。图5展示了程序输出的测试样本标签与“.data”文件中标签的对应关系P, 2,1,3,2,1, £ 10, 3,5,10, 8,5, 0,9,3,7 Nf 3,5,6,541,11,1158必 7,12,1,70, &#

12、163;3,5, £2,L 6, &&6,5,7,3, 8,4,8 lt 4； 9,5 6； 35,9f 2JQ10& 9,2/ & 5,5J, 2,11,3,8,2,馬鎳 513 丄 &0,7,0,8 T, 5,9, £8山 WAW0,2,2,3,3,2 畀弭行 6,6,6, £2厨 3畀 CfL10f 8&4再&6,9,12,9,13,2,9,3,7T, 6,9,6,7,5,6,11,3,7,11,9,5,2,12,2,4 S* 2,3.12丄 & 7, Z 6,10,6,8,1,9,5,8A,

13、4,9,6,6,2> 9.5,3» 18,1* 8,2, 7,2,8测述牟2日肝站P>Oil *J>. XL -it3»93-T，哮恋3舸4=J3991 =W(a)fi.i:.«399E=T 3?96=Daill卒3?=C本3998-T显不识别率 :样本识别厘IsS.4BUS=AMygMM/蚕=61.3&Z=阪g(b)图5观察图5可以发现，第一行字母P的识别是正确的，而第三行的预测出现了错误。 样本集中的数据为“ O”，但支持向量机将其错分为“ B”。按上述方法可以一一 对照测试样本的预测结果是否正确。接下来，采用其他核函数进行分类。图6

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

15、9;下载，这个网址上提供了上万个用于机器学习的数据集。 接下来分别展示“ iris”数据集和“ wine”数据集上的测试结果。(1) “ iris ”数据集戈忡心幅旧 tSHO：琶吾您超抚H3 9 3 5 2 2 2LL9,7,®45.5.S.&5.!.!.L 行 n«J& e 5 Th3.25. .9,乩禺 3L6 3 a6. .山5fi5.?bu56,5,5,6.6.6.G,6.5 I-匚i?|-"亠 N 尸4 E £,E.“iris”数据集是鸢尾花数据集。其中共包含150个样本，每个样本是一个4 维的特征

16、向量，这4个特征分别是萼片长度、萼片宽度、花瓣长度和花瓣宽度。 数据的标签总共有三类：“ S”代表刺芒野古草，“ E”代表杂色鸢尾花，“ I”代表 维尔吉尼卡。它们分别是三种不同的鸢尾花品种。该数据集如图 7所示：3, 3/ . 4 6 23. 2, 4. 7, k 42. % 4.2,1 3Z 9, L 3,1 3Z N 3. 0,1.1Z 8, 4.1,1.33. t fi. CL 2, 53. 0J 5. N 2 32. E, E. 03 lr 93. O, 5. 2；, 2,03. £ 5. £ 2. 33. 0, £.1,1.8图7在本实验中，用前130

17、个数据作为训练样本，后20个数据作为测试样本 选定相应的参数如图8所示:/尊水尊水草水期:席童斗祗水當斗當斗家席車设羞文件豁怪*#*#*#*#def ine PATH ". /iris, dat af!/*#*置样本个救球*4c*事*事*事*暮水事*草*尊暮專*/#define SAliPLE 150/*#*#*#* J*C*#*：3|C*i* */define TRAIN 130/卓半尊當st*屮:*車嗥*:*卓出电:耳事,殳養特彳正向里维数电半电半电半电半电半車半芈半尊字草*/Sdefine VECTOR 4/寓常审當案當當常當*幕當當事當*當常选择核函埶 类型*寓*电*幫*倉*

18、：«常屮:*事鼎案常/#define KERNEL 1"KERNEL蜃数说明；山绒性複函数*凸多顼式核函S0U 3=径向基（高斯）核囲数* Sui酣oi日函数* 案*當*卓當卷常當*當當車老束* *:*字*耳*电*电*柬常巔*草*:戟常章常电*重常童鼎草/图8中，选取核函数为线性核函数。按照图8所示的参数执行程序，得到的结果 如图9所示：图9由图9可知，对于“iris ”数据集，训练样本的识别率为 98.46%，测试样本的识 别率为90.00%。由数据可以看出，支持向量机对“ iris”数据集的分类效果显然 要优于“ letter-recognition”数据集。这可能和数

19、据集本身有关，“iris”数据集特 征的可分性更好。接下来，变换核函数来观察分类效果。图10是采用径向基核函数得到的结SS 匚:,nd,cmc.e-. e9 Q勺3 02 0 "仇0. K UJ 99L23 4b-&7 9yltllltlllL2 - N 二 / -J 丁二 / - - - i - / - - 二 £ 二 £ 二 E二，；!二 Ml 二-MI-一 E二丿二 r - - - ' E 诗译蒔吁吁舛琳詩讦舛齐坪诗畔聲持节杆#腎祥yl=g継 ;_k识识龍 忒專忒版廩障悽墨陳扇闵倭试练简按 则処.以臾以如加艮如如処坝卿则则以贝毁以则"

20、;训则青 -1 屮一 ”1-扌 “"1 ”J.f -"-1 ->T- Jf 1 一 *：彳"！- J-"! Jfll'tf ->*1- -:l J.1 *11 ll1 JIT- f .!.- I l-图10图10中，训练样本的识别率比采用线性核函数时略有提升，但测试样本的识别 率没有变化，因此可以认为采用径向基核函数与线性核函数的分类效果是基本相 同的。当采用Sigmoid函数进行分类时，分类效果显然要差很多。该分类效果如图11所示图11中，训练样本和测试样本的识别率都很低，因此iris ”数据集显然不适合用Sigmoid函数进行分类

21、。以上实验结果表明，核函数的选取对于支持向量机的分类效果有至关重要的 影响。（2） “wine ”数据集“wine”数据集是红酒数据集。其中共包含178个样本，每个样本是一个13维的特征向量，其中包含酒精度、年份等特征。数据的标签总共有三类：“M”、wine.chta -忙事本“H”、“L”。它们分别代表三类不同的红酒。该数据集如图12所示：L13.58. 2. 5& 2. S9. 24.5.1Q5 1.55因39 h 54. 8. 66. 50 L13- 4.4.6,2.瓯 25,112,1.9& . 27,1.11, 8. 5, .67,1. 92.(30L

22、12. 2,3,03,2.32,1 睥 L 2瓦 4%, 73,反 5托£ ., 83, 510U12- 77, 2. 39, S. 2D, 19.瓦 86,1. 39. 51,. 43,.妣 9. 899993, .57,1. 63,4T0 1,13. 77,1. 9, 2. 68,17. L 115,3. 2. T91.68f 氐 3,1.13,2. 93,13751,13.1. 6T, 2. Z5,1&.出 113,2.&.2,也.21,1 也，乩鬲羁 3.乙 1060II1,13.56 74 2 46, 20.5116,2” 96J 2.73,. 2, 2.4

23、5, 6. 25 9&3.03,1120 L14, 2Z 1. 7,2.3,16.3,11 出 3. Z 3,弧 2. D3,6*3&一 94,3,31,970 丸 13. 29, 1. 97, 2.碣 16. & 103,3. 23,. 31. 1.66, $ 1. 07, 2. 84, 12T0 1,13.72,1. 4% S. E；*1E lt 108J 3, 4, 3. 67, .19, 2. 04, &&.S缶 2.87,1235 比 11* 87, 4. 31, S. 39, 21, 82,2. 85f 3. 03,. 21, 2. 91,

24、2. 8f . 75, 3. 64,380 比 12. JL 2.16, 2. LT, 21, 85, 2. 6, 2.隔.37, L 35, 2.76,. 86, 3.28,3T8 H,12.43, . 53, 2. 29? 21.5,86,2. 74, 3.15,. 3% 1. F7, 3.処.険込 84,352 All. 79,2.13,2. 78, 28.反 92,込 13f 2, 24.5&1. 76, 39 化 2.44,466 H, 12. 37,1.鸥 3. £ 24. S,呕 2. 22, 2.酝.4d 1.爲 2.12,. 89, 2 72,342 比 1

25、2. 04, 4. 3, 2. 3S, 22, 80, 2.1丄理.42,1. 3反 2.瓦.7% 2.硏，580 U 14.1 & 2. 51, 2. 4& 20, 91,1. 63,. 7,. 44,1. 24, 9.13.6& 1. 71,660 U 13. U, 5.隔 2. 45, 20.玄 95 1.憾.61,.鸥 1. 06,7. 7.鸥 1.珂 T® L.13- 4,3.91,2.48,23,102,1.8, . 75,. 43,1,41,7, 3, .7,1,56J50图12本实验用前125个数据作为训练样本，后53个数据作为测试样本。选定相

26、 应的参数如图13所示：2/* * * * * i殳蛊文 f牛貉 彳圣* * * 相# * */# define PATH ". /wine. datX/* 设蛊祎不 吓数* *»*w*4cw*4nk#y«d«fine SAMPLE 178/»*»*»*»*”设養训镰样 本个敎 * *审/#define TRAIN 125/*# +：+ lx S 特征向量维數 *壮*!/#define VECTOR 13/*:* * 选择核函数类型 He* *#*：+：# 水* 朮*:</#define KEKHEL 1&q

27、uot;KEEHEL番数说明；"结性檢函数i N多项式檢函数丨奔径向棊高斯）核函制H "sigmoid囲数。 /當當當*當當當當*當當當*萼幕當當當*屮事當*當*當耳當*屮*當當當*當耳當*當*當*将*當耳*耳F图13中，核函数选定为线性核函数。按照上述参数设置执行程序，得到的结果如图14所示：讯 <:W ndowATCTi52 cmc.ewe呗!喲r35=H EXH wn,皈=n 畑AH1 =H 肚第=HX44=H7 轴 fi =HT47=H亦 4H=L7 5 =HM苗QT3=n握试试试協弑弑试頁出出因也出出答一=37.74k本 9T=H品示识别率图14由图14可得

28、，对于“win e”数据集，训练样本的识别率为 88.00%,测试样本的 识别率为37.74%。训练样本的识别率较高，但测试样本的识别率却较低。这说 明该学习过程的泛化能力较差。这可能由于样本数量有限，支持向量机方法很难 从这么有限的样本中训练出较为理想的分类器。接下来，尝试采用其他核函数的分类效果。结果发现，其他和函数的分类效 果并没有线性核函数的分类效果好。当采用径向基核函数时，训练样本的识别率 可达100%，但测试样本的识别率变得非常低。该结果如图 15所示。X卫Ife站4胡彩M37-H；£： <xJB=Hfe 站 9=H欝g-M 乂粗 1-H岸丄口42=H 43=H申

29、£44 =H 辛定.45-H 乂牲 E =H fe囲=H 执翎=« fe 5 =H '2 5B-H 电! 3=H fe 52 =H 早本盟=H F临不识号 钟识另>C:Wm Mb 必sys£ m32li1cmcie)ce图15可见，对于“wine”数据集来讲，采用径向基核函数虽然能使训练样本识别 率最高，但其泛化能力最差，因此对解决实际问题没有任何帮助。综合比较上述结果，可以发现径向基函数在大多数情况下都可以获得较高的训练样本识别率，即经验风险很小。但是，测试样本的识别率无法保证，对于某 些数据集的泛化能力有限。致今后，我会从事机器学习方向的研究。

30、模式识别课程的容对我的专业方向有 很大帮助，令我受益匪浅。 尤其是在本次大作业过程中， 支持向量机的编程实现 工作大大加深了我对支持向量机原理的理解， 为我今后的研究工作打下了坚实基 础。模式识别课程的学习是我研究道路上的一个良好开端， 具有十分重要的意义。本学期的模式识别课程令我受益颇多。 在此，诚挚地感建更老师的辛勤付出！附录：源程序代码#include "opencv2/core/core_c.h"#include "opencv2/ml/ml.hpp"#include <cstdio>#include <vector>/*

31、设置文件路径 */#define PATH "./letter-recognition.data"/*设置样本个数 */#define SAMPLE 20000/*设置训练样本个数 */#define 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

32、, "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 = cvCreateMemStorage();seq = cvCreateSeq( 0, sizeof(*seq), (var_count+1)*sizeof(float), storage );for(;)char* ptr;if( !fgets( buf, M, f ) |

33、 !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, &n );ptr += n + 1;if( i <= var_count )break;cvSeqPush( seq, el_ptr );fclose(f);*data = cvCreateMat( seq->total, var_count, CV_32F ); *respo

34、nses = cvCreateMat( seq->total, 1, CV_32F );cvStartReadSeq( seq, &reader );for( i = 0; i < seq->total; i+ )const float* sdata = (float*)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 = sdata

35、j;*dr = sdata-1;CV_NEXT_SEQ_ELEM( seq->elem_size, reader );cvReleaseMemStorage( &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

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

37、); nsamples_all = SAMPLE;ntrain_samples = TRAIN; var_count = data->cols;*训练分类器 */printf( " 正在训练 SVM 分类器 .n"); 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

38、.fli = responses->data.fli;svm.train(&train_data, train_resp, 0, 0, param);开始对测试样本分类*std:vector<float> _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.fl(j) * var_count + i = si;true_resultsj = responses->data.flj;CvMat *result = cvCreateMat(1, nsamples_all, CV_32FC1);printf(&