SVM的可视化验证实验

發表於 2015-10-17   |   分類於 机器学习   |  

支持向量机简介

支持向量机(support vector machine,SVM)是一种二分类模型。他的基本模型是定义在特征空间上的间隔最大的线性分类器，间隔最大使它有别于感知器;支持向量机还包括核技巧，者使它称为实质上的非线性分类器。支持向量机的学习策略就是间隔最大化，可形式化为一个求解凸二次规划 (convex quadratic programming) 的问题，也等价于正则化的合页损失函数的最小化问题。支持向量机的学习算法是求解凸二次规划的最优化算法。

实验说明

本次试验利用python的机器学习库scikit-learn，该库中SVM的实现依赖于台湾大学林智仁团队的LibSVM。本实验的绘图函数库则依赖于Matplotlib。

实验目的

本实验主要探究，以iris数据集为例，利用SVM解决二分类和三分类问题，讨论一些参数（惩罚系数C和协同系数gamma）对模型的影响。

数据集说明

iris以鸢尾花的特征作为数据来源，常用在分类操作中。该数据集由3种不同类型的鸢尾花的50个样本数据构成。其中的一个种类与另外两个种类是线性可分离的，后两个种类是非线性可分离的。
该数据集包含了5个属性：

  • Sepal.Length（花萼长度），单位是cm;
  • Sepal.Width（花萼宽度），单位是cm;
  • Petal.Length（花瓣长度），单位是cm;
  • Petal.Width（花瓣宽度），单位是cm;
  • 种类：Iris Setosa（山鸢尾）、Iris Versicolour（杂色鸢尾），以及Iris Virginica（维吉尼亚鸢尾）。

数据集中共有150条记录，每种鸢尾花有50条记录。只取两种属性绘制散点图时可以得到如下的结果。

iris数据集

二分类问题

##依赖引入

1
2
3
import numpy as np
import matplotlib.pyplot as plt
from sklearn import svm, datasets

##数据读取
iris是scikit-learn内置的数据集，所以可以方便的导入。
为了简化问题，这里我只取了前100条记录（只有两种鸢尾花）的前两种属性（分别是sepal length河sepal width）

1
2
3
4
5
# import some data to play with
iris = datasets.load_iris()
X = iris.data[:100, :2] # we only take the first two features. We could
 # avoid this ugly slicing by using a two-dim dataset
y = iris.target

##模型训练
这里使用的是线性核，即为普通的线性SVM分类器，其惩罚系数为C，核协同系数gamma为0。这里要说明的是gamma只有在kernel为 ‘rbf’, ‘poly’ 和 ‘sigmoid’时才有效，’linear’核时gamma参数无影响。

1
2
3
# we create an instance of SVM and fit out data.
C = 1.0 # SVM regularization parameter
svc = svm.SVC(kernel='linear', C=1,gamma=0).fit(X, y)

##绘制决策边界

首先我们把图上所有的(x,y)坐标都生成出来，组成多个待预测样本，将它们输入svc进行预测，将预测的结果作为Z，之后用(x,y,z)绘制等高线图，这样就能直观地显示出决策边界(decision boundary)。

1
2
3
4
5
6
7
8
9
10
11
# create a mesh to plot in
h = 0.01
x_min, x_max = X[:, 0].min() - 1, X[:, 0].max() + 1
y_min, y_max = X[:, 1].min() - 1, X[:, 1].max() + 1
xx, yy = np.meshgrid(np.arange(x_min, x_max, h),
 np.arange(y_min, y_max, h))
plt.subplot(1, 1, 1)
Z = svc.predict(np.c_[xx.ravel(), yy.ravel()])
Z = Z.reshape(xx.shape)
plt.contourf(xx, yy, Z, cmap=plt.cm.Paired, alpha=0.8)

##绘制训练集散点图

plt.scatter()可以绘制散点图，在这里我们绘制了全部参与训练的样本的散点图。xlabel,ylabel可以控制x,y轴的说明文字，xlim控制x轴的显示范围,title可以控制图像标题。

1
2
3
4
5
6
plt.scatter(X[:, 0], X[:, 1], c=y, cmap=plt.cm.Paired)
plt.xlabel('Sepal length')
plt.ylabel('Sepal width')
plt.xlim(xx.min(), xx.max())
plt.title('SVC with linear kernel')
plt.show()

二分类问题实例

线性核的结果
SVC linear kernel C=1 gamma=0

RBF核的结果
SVC rbf kernel C=1 gamma=0

三分类问题

##SVM如何解决多分类问题
以下内容参考[3]

SVM多类分类方法的实现根据其指导思想大致有两种：
(1) 将多类问题分解为一系列SVM可直接求解的两类问题，基于这一系列SVM求解结果得出最终判别结果。
(2) 通过对前面所述支持向量分类机中的原始最优化问题的适当改变，使得它能同时计算出所有多类分类决策函数，从而“一次性”地实现多类分类。原始问题可以改写为：
SVM多分类公式

虽然第(2)种指导思想看起来简单，但由于它的最优化问题求解过程太复杂，计算量太大，实现起来比较困难，因此未被广泛应用。而基于第(1)种指导思想的SVM多类分类方法主要有5种。

  1. 1-V-R方式(一对其余法)

    一类对余类法(one versus rest，OVR)是最早出现也是目前应用最为广泛的方法之一，其步骤是构造k个两类分类机(设共有志个类别)，其中第i个分类机把第i类同余下的各类划分开，训练时第i个分类机取训练集中第i类为正类，其余类别点为负类进行训练。判别时，输入信号分别经过k个分类机共得到k个输出值fi(x)=sgn(gi(x))，若只有一个+1出现，则其对应类别为输入信号类别；实际情况下构造的决策函数总是有误差的，若输出不只一个+1(不只一类声称它属于自己)，或者没有一个输出为+1(即没有一个类声称它属于自己)，则比较g(x)输出值，最大者对应类别为输入的类别。
    这种方法的优点是，对k类问题，只需要训练k个两类分类支持向量机，故其所得到的分类函数的个数(k个)较少，其分类速度相对较快。

  2. 1-V-1方式(一对一方式)

    该方法在每两类问训练一个分类器，因此对于一个k类问题，将有k(k-1)／2个分类函数。当对一个未知样本进行分类时，每个分类器都对其类别进行判断．并为相应的类别“投上一票”，最后得票最多的类别即作为该未知样本的类别。决策阶段采用投票法，可能存在多个类的票数相同的情况，从而使未知样本同时属于多个类别，影响分类精度。

  3. DAG方式(有向无环图)

    DAG-SVMS是由PIatt提出的决策导向的循环图DAG导出的，是针对“一对一”SVMs存在误分，拒分现象提出的。这种方法的训练过程类似于“一对一”方法，k类别问题需要求解k(k-1)／2个支持向量机分类器，这些分类器构成一个有向无环图。该有向无环图中含有k(k-1)／2个内部节点和k个叶结点，每个节点对应一个二类分类器。
    四类问题DAGSVM结构图
    DAG-SVMS简单易行，只需要使用k-1个决策函数即可得出结果，较“一对一”方法提高了测试速度，而且不存在误分、拒分区域；另外，由于其特殊的结构，故有一定的容错性，分类精度较一般的二叉树方法高。然而，由于存在自上而下的“误差积累”现象是层次结构固有弊端，故DAG-SVMS也逃脱不掉。即如果在某个结点上发生了分类错误，则会把分类错误延续到该结点的后续结点上。

  4. 决策树方法

    决策树的基本思想是从根节点开始，采用某种方法将该节点所包含的类别划分为两个子类，然后再对两个子类进一步划分，如此循环，直到子类中只包含一个类别为止，这样，就得到了一个倒立的二叉树。最后，在二叉树各决策节点训练支持向量机分类器，实现对识别样本的分类。决策树支持向量机多分类方法有很多种，不同方法的主要区别在于设计树结构的方法不同。
    决策树SVM

    完全二叉树结构分类时使用的平均分类器数目为$log_2{(k)}$，偏二叉树使用的平均分类器数为(k+1)／2-1／k，具有其他层次结构的二叉树使用的分类器平均值介于二者之间。完全二叉树分类时所需要的分类器数目最少，因此具有较少支持向量的完全二叉树的分类器速度也是较快的。

  5. 纠错输出编码法（ECOC）

    对于K类分类问题，可以根据不同方法构造一系列的两类分类问题，对于每个两类分类问题可以建立一决策函数。共得到L个决策函数，如果这些决策函数完全正确，K类中的每一类都对应一个元素为-1或+1的长度为L的数
    列，按照K类中的第一类、第二类，…，第K类的顺序，把这些数列排列起来，便可得到一个K行L列的编码矩阵，若要判断一个测试输入点的归属，首先用所得到的L个决策函数，得到一个元素为-l或l的长度为L的数列，然后将此数列与先前得到矩阵比较，相应于矩阵中有一行且仅有一行向与此数列相同，这个行数就是输入点的归属类；若矩阵中没有一行与该数列相同，可以通过计算汉明距离找出最近的一行，改行对应的类别即为该点的类别。

##LibSVM的多分类实现

在LibSVM(同时即为Scikit-Learn)的实现中,采用的是1-V-1方式，因为这种方式思路简单，并且许多实践证实效果比1-V-R方式要好。更具体的内容请参考LibSVM相关的论文以及文档[4]。

##数据读取
此处的数据读取略有不同。取了150条数据（3种鸢尾花），后面的两个属性（petal length 和 petal width）

1
2
3
iris = datasets.load_iris()
X = iris.data[:, 2:] 
y = iris.target

##模型训练
严格意义上来说SVM只是二分类器，要用SVM实现多分类需要一定的技巧，但是库已经帮助我们屏蔽掉这些细节了。

1
svc = svm.SVC(kernel='rbf', C=1,gamma=0).fit(X, y)

##散点图绘制
这里使用了一个小技巧——zip()函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# create a mesh to plot in
h = 0.01
x_min, x_max = 0,10
y_min, y_max = 0,6
xx, yy = np.meshgrid(np.arange(x_min, x_max, h),
    np.arange(y_min, y_max, h))
Z = svc.predict(np.c_[xx.ravel(), yy.ravel()])
Z = Z.reshape(xx.shape)
plt.contourf(xx, yy, Z, cmap=plt.cm.Paired, alpha=0.8)
for t,marker,color in zip(xrange(3),">ox","rgb"):
    plt.scatter(X[y == t,0],
        X[y == t,1],marker=marker,c=color)
plt.xlabel('petal length')
plt.ylabel('petal width')
plt.xlim(xx.min(), xx.max())
plt.ylim(yy.min(), yy.max())
plt.title('SVC with rbf kernel C=1')

##关于参数的说明

  • kernel
    常见的kernel类型包括”linear”, “rbf”,”poly” 和”sigmoid”。”linear”主要用于线性可分问题，”rbf”(径向基核函数)和”poly”(多项式核函数)都是不错的非线性分类器。

  • C
    惩罚系数C (penalty parameter) 主要控制光滑的决策边界与分类准确率的权衡。在李航的《统计学西方法》中，软间隔最大化引入松弛变量后，优化的目标函数由原先的
    $$\min_{w,b} \frac{1}{2}{\left |w \right |}^{2}$$
    变为如下：
    $$\min_{w,b,\xi} \frac{1}{2}{\left |w \right |}^{2} + C \sum_{i=1}^{N} \xi_{i} $$

  • gamma
    核协同系数 (Kernel coefficient), 仅在kernel为 ‘rbf’, ‘poly’ 和 ‘sigmoid’时有影响。 gamma值越高，在模型训练时就会越严格地分类训练集中的每一个训练数据，这样可能会形成较大的泛化误差，造成过拟合的问题。

##实例

SVC linear kernel C=1,10,100
线性核函数，不同C值的影响

SVC rbf kernel C=1,10,100
rbf核函数，不同C值的影响

此处输入图片的描述
rbf核函数，不同gamma值的影响

支持向量机的评价

##优点

  • It works really well with clear margin of separation
  • It is effective in high dimensional spaces.
  • It is effective in cases where number of dimensions is greater than the number of samples.
  • It uses a subset of training points in the decision function (called support vectors), so it is also memory efficient.
  • 当数据之间存在足够的空隙(clear margin)时，分类效果较好。
  • 在高维特征空间中仍然有效。
  • 当每个样本特征数大于每个数据集的样本数较为有效。
  • 在训练时只使用支持向量(support vector)

##缺点

  • It doesn’t perform well, when we have large data set because the required training time is higher
  • It also doesn’t perform very well, when the data set has more noise i.e. target classes are overlapping
  • SVM doesn’t directly provide probability estimates, these are calculated using an expensive five-fold cross-validation. It is related SVC method of Python scikit-learn library.
  • 模型在大规模的数据集表现不好，因为需要的训练时间更长。
  • 数据集中有噪声时，模型分类表现不好。（例如类之间有部分重叠）
  • 不提供概率估计(probability estimate)

参考资料

[1] 《统计学习方法》 李航
[2] Understanding Support Vector Machine algorithm from examples (along with code)
[3] SVM多类分类方法
[4] LibSVM学习（四）——逐步深入LibSVM
[5] libsvm的使用总结 -faruto

#SVM #python
图解Python深拷贝和浅拷贝
利用Scikit-Learn实现SVM