机器学习_06:SVM支持向量机_svm算法流程图

实验背景

SVM算法在上世纪60年代就已经被提出，学名为Support Vector Machine，是一种非常经典的监督学习方法。我在看来，SVM是最好的现成的分类器，这里说的“现成”指的是分类器不加修改即可直接使用。这意味着在数据上应用基本形式（没有针对数据进行修改）的SVM分类器就可以得到低错误率的结果。SVM能够对训练集之外的数据点做出很好的分类决策。
SVM有很多实现方法，本篇博客只介绍最流行的一种方法，序列最小优化（Sequential Minimal Optimization,SMO）算法。

1.SVM算法原理

1.1.分隔超平面

首先我们要介绍下SVM支持向量机的目的，如图所示

对于整个图像来说，如何找到一条直线将+，-，完美的分开是很困难的，而这条将数据集分开的直线称为分隔超平面。图像中的数据点都在二维平面上，所以分隔超平面就是一条直线，如果数据集是三维的，那分隔超平面就是一个平面。更高维的情况以此类推。SVM的目的就是找到这个最佳的分隔超平面。而SVM中的支持向量，就是指离分隔超平面最近的那些点，而这些点离分隔面越大的话，这个分隔面就越接近完美分隔面。

1.2.最大间隔

1.2.1.寻找最小间隔数据点

如图所示，对于超平面来说，距离其最近的点就是被圆圈框起来的一个+号和两个-号。
假设这个超平面方程为：

那么位于超平面上方的支持向量所经过的直线可以表达为：

位于超平面下方的支持向量所经过的直线可以表达为：

根据直线之间的距离计算公式，最后可以化为：

将问题化为寻找参数w和b，使得下述公式最大

1.2.2.拉格朗日乘子法

为了更好的求得最大值，我们引入拉格朗日乘子得到对应的拉格朗日函数

然后，令L（w,b,α）对w和b的偏导为零

将w，b带回原式得

等价形式为

最终模型：

其中约束条件为：

1.3.SMO高效优化算法

SMO算法的工作原理是：每次循环中选择两个合适的α进行优化处理。一旦找到一对合适的α，就增大其中一个的同时减小另一个。
流程图大致如下：

公式表达为：

得到最优解为：

带回原式解得w和b为

得到分类平面：

伪代码大致如下：
创建一个α向量并将其初始化为0向量
当迭代次数小于最大迭代次数时（外循环）
对数据集中的每个数据向量（内循环）；
如果该数据向量可以被优化：
随机选择另外一个数据向量
同时优化这两个向量
如果两个向量都不能被优化，退出内循环
如果所有向量都没被优化，增加迭代数目，继续下一次循环

2.实验结果

from time import sleep
import matplotlib.pyplot as plt
import numpy as np
import random
import types
"""
函数说明:读取数据

输入：
    fileName - 文件名
输出：
    dataMat - 数据矩阵
    labelMat - 数据标签
"""
def loadDataSet(fileName):
    dataMat = []; labelMat = []
    fr = open(fileName)
    for line in fr.readlines():                                     #逐行读取，滤除空格等
        lineArr = line.strip().split('\t')
        dataMat.append([float(lineArr[0]), float(lineArr[1])])      #添加数据
        labelMat.append(float(lineArr[2]))                          #添加标签
    return dataMat,labelMat

"""
函数说明:数据可视化

输入：
    dataMat - 数据矩阵
    labelMat - 数据标签
输出：
    无
"""
def showDataSet(dataMat, labelMat):
    data_plus = []                                  #正样本
    data_minus = []                                 #负样本
    for i in range(len(dataMat)):
        if labelMat[i] > 0:
            data_plus.append(dataMat[i])
        else:
            data_minus.append(dataMat[i])
    data_plus_np = np.array(data_plus)              #转换为numpy矩阵
    data_minus_np = np.array(data_minus)            #转换为numpy矩阵
    plt.scatter(np.transpose(data_plus_np)[0], np.transpose(data_plus_np)[1])   #正样本散点图
    plt.scatter(np.transpose(data_minus_np)[0], np.transpose(data_minus_np)[1]) #负样本散点图
    plt.show()

"""
函数说明:随机选择alpha

输入：
    i - alpha
    m - alpha参数个数
输出：
    j -
"""
def selectJrand(i, m):
    j = i                                 #选择一个不等于i的j
    while (j == i):
        j = int(random.uniform(0, m))
    return j

"""
函数说明:修剪alpha

输入：
    aj - alpha值
    H - alpha上限
    L - alpha下限
输出：
    aj - alpah值
"""
def clipAlpha(aj,H,L):
    if aj > H:
        aj = H
    if L > aj:
        aj = L
    return aj

"""
函数说明:简化版SMO算法

输入：
    dataMatIn - 数据矩阵
    classLabels - 数据标签
    C - 松弛变量
    toler - 容错率
    maxIter - 最大迭代次数
输出：
    无
"""
def smoSimple(dataMatIn, classLabels, C, toler, maxIter):
    #转换为numpy的mat存储
    dataMatrix = np.mat(dataMatIn); labelMat = np.mat(classLabels).transpose()
    #初始化b参数，统计dataMatrix的维度
    b = 0; m,n = np.shape(dataMatrix)
    #初始化alpha参数，设为0
    alphas = np.mat(np.zeros((m,1)))
    #初始化迭代次数
    iter_num = 0
    #最多迭代matIter次
    while (iter_num < maxIter):
        alphaPairsChanged = 0
        for i in range(m):
            #步骤1：计算误差Ei
            fXi = float(np.multiply(alphas,labelMat).T*(dataMatrix*dataMatrix[i,:].T)) + b
            Ei = fXi - float(labelMat[i])
            #优化alpha，更设定一定的容错率。
            if ((labelMat[i]*Ei < -toler
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107