2.3 支持向量机复杂度
使用SVM进行分类的时候，实际上是训练和分类两个完全不同的过程，因而讨论复杂度就不能一概而论，我们这里所说的主要是训练阶段的复杂度，即解那个二次规划问题的复杂度。对这个问题的解，基本上要划分为两大块，解析解和数值解。
解析解就是理论上的解，它的形式是表达式，因此它是精确的，一个问题只要有解，那它的解析解是一定存在的。当然存在是一回事，能够解出来，或者可以在可以承受的时间范围内解出来，就是另一回事了。对SVM来说，求得解析解的时间复杂度最坏可以达到O(Nsv3)，其中Nsv是支持向量的个数，而虽然没有固定的比例，但支持向量的个数多少也和训练集的大小有关。
3、多类分类问题
经典的支持向量机主要解决的是二分类问题，而在实际问题中，除了二分类问题，还有很多是多类分类问题。为实现多分类的问题，SVM应用不同的组合策略达到多分类的目的。
3.1 一对一组合
一对一分类法[2,3,4](One-Versus-One，简称OVO)也称为成对分类法，是一种将多分类问题分解为多个两分类子问题，每次只是选取其中的两类训练样本，在任意两类间构建分类超平面，假设有n类问题，总共需要构造n(n一1)/2个二值SVM分类器。如图1.3.1
图1.3.1 一对一多分类示意图
当对一个未知样本进行分类时，使用投票法:每个分类器都对其类别进行判断，并为相应的类别投上一票，最后得票最多的类别即作为该未知样本的类别。
3.2一对多组合分类
一对多组合分类法(One Versus Rest，简称OVR)是最早的多类分类算法，该方法的基本
6
思想就是先将每一类训练样本同其它所有类别的训练样本区分开来，构造所有可能的两分类SVM，再采用某种结合策略将训练得到的全部两分类SVM组合起来解决多分类问题。如下图所示。对n类问题，该方法需构造n个二类支持向量机，每个支持向量机分别把某一类数据从其他类别中分离出来。
图1.3.2 一对多多分类示意图
对任意一个未知样本的判别方法，就是将样本点分别代入上述的n个分类决策函数中，具有最大分类函数值关(x)的那个类，即为样本点的类别。
二、 实现方法
1. 获取数据
实验用的数据来自UCI数据集的wine的数据。在葡萄酒制造业中,对于葡萄酒的分类具有很大意义,因为这涉及到不同种类的葡萄酒的存放以及出售价格,采用SVM做为分类器可以有效预测相关葡萄酒的种类,从UCI数据库中得到wine数据记录的是在意大利某一地区同一区域上三种不同品种的葡萄酒的化学成分分析,数据里含有178个样本分别属于三个类别(类别标签已给),每个样本含有13个特征分量(化学成分)。
1.1 测试数据
整体数据存储在lyx_wine.mat中。数据内容如下： Classnumber=3，记录类别数目（用1,2,3代替）；
Wine，178*13的一个double型的矩阵，记录178个样本的13个属性，如下图所示； Wine_lable,178*1的一个double型的列向量，记录178个样本各自的类别标签（用1，2,3）标记。
7
图2.1.1 lyx_wine.mat数据示意图
图2.1.2 wine数据示意图
1.2 数据详细描述
从UCI数据库中得到wine数据记录的是在意大利某一地区同一区域上三种不同品种的葡萄酒的化学成分分析,数据里含有178个样本分别属于三个类别(类别标签已给),每个样本含有13个特征分量(化学成分)，如下：
图2.1.3 数据中13个特征分量含义示意图
8
2. 实验模型建立
本次实验大致分为4部分，分别为：实验数据分析、建立分类模型，进行类别标签预测、ROC图形分析以及运用不同数量的训练样本及采用不同核函数的对比。
三、 实验仿真及编程
1.实验仿真环境
本实验的运行环境为matlab7.12.0（R2011a），其中svm的实现采用的是libsvm工具箱。
2.实验内容
2.1实验数据分析
对wine数据进行分析，得到wine数据的可视化图和wine数据的分维可视化图。
仿真结果：
wine数据的box可视化图ProlineOD280/OD315 of diluted winesHueColor intensitysProanthocyaninsNonflavanoid phenolsFlavanoidsTotal phenolsMagnesiumAlcalinity of ashAshMalic acidAlcohol050010001500属性值图3.2.1 wine数据的可视化图
9
图3.2.2 wine数据的分维可视化图
结果分析：从上图可以看出wine数据里含有178个样本分别属于三个类别(类别标签已给),每个样本含有13个特征分量(化学成分)，且分布较均匀。
2.2建立分类模型，进行类别标签预测
将这178个样本50%做为训练样本,另50%做为测试样本,用训练样本对SVM分类器进行训练，用得到的模型对测试样本的进行分类标签预测。
首先需要从原始数据里把训练集和测试集提取出来，然后进行一定的预处理，之后用训练集对SVM进行训练，再用得到的模型来预测测试集的分类标签，即流程如下：
（1）选定训练集和测试集
（2）数据预处理 （3）训练SVM （4）预测
（5）分类准确率
仿真结果：
10