《机器学习》第6章
1、支持向量机
支持向量机解决的是多维的分类问题。当给出一定的数据集时，分类学习的最基本想法就是基于训练集在样本空间中找到一个划分超平面，将不同类别的样本划分，又因为在训练学习中，数据大多是高维度的，并且数据不一定都是线性可分的，那么线性不可分的数据，和非线性函数怎么划分呢？这时候就需要使用到一种新的分类器，支持向量机，支持向量机是基于线性分类器提出的另一种设计最佳准则。
2、 支持向量机和线性回归的区别：
线性回归，当样本空间里的属性都是线性可分的时候，如图2.1，使用线性回归即可解决这些问题，但是在实际运用中，样本空间内的特征大部分都不是线性可分的，这时候我们的支持向量机就派上用场了。因为支持向量机可以根据不同的核函数（在下面会讲）得到线性回归模型和非线性回归模型。
2.1
3、支持向量机的基本型
在样本空间中，划分超平面通过如下线性方程来描述：
其中w为法向量，决定超平面的方向，b为位移项，决定超平面与原点之间的距离。
但是能将训练样本分开的划分超平面可能有很多，如图2.1
支持向量与间隔
为了寻找最优的划分超平面，我们必须找到具有“最大间隔”的划分超平面。“间隔”指的是两个异类向量距离超平面的距离。如上图。为了找到‘最大间隔’，在这里加上了一个约束条件:
假设有超平面（w，b）能将训练集正确划分，那对于训练集D中的（xi，yi）则有以下约束条件。
3.1
根据这个约束条件，可以将3.1中的公式重写：
根据这条公式，产生了支持向量机的基本型
4、核函数
在前面使用的支持向量机基本型，只能支持训练样本是线性可分的情况下，即存在一个划分超平面能将训练样本的正确分类，然而在现实任务中，原始样本空间不一定都会存在一个能正确划分的超平面，例如图4.1的“异或”问题就不是线性可分的。
4.1
对于这个问题，怎么办呢？这时候我们就可以将这个原始空间，映射到一个更高维度的特征空间中，如图4.1将一个二维的样本空间，映射到一个三维的特征空间上，就能找到一个合适的划分超平面，按照这个原理，当原始空间是有限维度的，即属性数有限 ，那么一定存在一个高纬度的样本可分。
举个例子：假设需要在一个桌面上划分篮球和红球，并且在尽量在放更多球之后，仍然适用。那么我们可以如下图所示划分，蓝色球跟红色球的间隔最大化。
但如果是下图中的这种无法线性划分的情况，没有直接的直线可以分开两种球了，那怎么办呢？那么可以看做球飞到空中，在其中用一张纸，插到了两种球的中间把两种球分开了。
将原始空间映射后的特征向量模型可表示为：
同样需要寻找最大间隔，所以必须增加约束条件：
对这个函数求解的话，由于特征空间维度可能会很大，甚至无穷维，所以为了避开这个障碍，可以设想一个这样的函数
即Xi与Xj在特征空间内积等于他们在原始空间中通过函数κ（·,·）计算的结果，重写3.5的公式为：
求解后得到
在这里κ(,)就是‘核函数’
通常我们不知道合适映射Φ(·)是什么形式，所以无法直接写出核函数。但任何一个核函数都隐式定义了一个称为“再生和希尔伯特空间”的特征空间。若核函数选择不合适，则意味着将样本映射到了一个不合适的特征空间，很可能导致性能不佳。图3.9列出了常用的核函数。
5、软间隔与正则化
现实任务中，往往很难确定合适的核函数使训练集在特征空间中线性可分，退一步讲，即使恰好找到某个核函数使训练集在特征空间中线性可分，也很难断定这个貌似线性可分的结果是不是过拟合造成的。
缓解这个问题的一个办法就是，允许支持向量机在一些样本上出错。所以引入了‘软间隔’的概念：
在原有的公式上，增加一个损失函数，这些函数不包含在最大间隔计算范围，但是我们计算最大间隔的时候，同时也对于不满足的样本尽可能少
其中C为一个大于0的参数，而C后面的为“0/1损失函数”如图5.1所示
5.1
6、代码实现支持向量机
《机器学习实战》中给出了利用Python实现SVM的代码：
import random
from numpy import *
# 读取数据集
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
def selectJrand(i , m):
j = i
while (j == i):
j = int ( random.uniform ( 0 , m ) )
return j
def clipAlpha(aj , H , L):
if aj > H:
aj = H
if aj < L:
aj = L
return aj
def smoSimple(dataMatIn , classLabels , C , toler , maxIter):
# 将数据转化为矩阵，并求逆
dataMatrix = mat ( dataMatIn );
labelMat = mat ( classLabels ).transpose ( )
b = 0;
m , n = shape ( dataMatrix )
alphas = mat ( zeros ( (m , 1) ) )
iter = 0
while (iter < maxIter):
alphaPairsChanged = 0
for i in range ( m ):
# 输出 alphas 信息
# 输出 labelMat 信息
fXi = float ( multiply ( alphas , labelMat ).T * (dataMatrix * dataMatrix[i , :].T) ) + b
# fXi=float(np.multiply(alphas, labelMat).T*dataMatrix*dataMatrix[i, :].T)+b
Ei = fXi - float ( labelMat[i] )
if ((labelMat[i] * Ei < -toler) and (alphas[i] < C)) or ((labelMat[i] * Ei > toler) and (alphas[i] > 0)):
j = selectJrand ( i , m )
fXj = float ( multiply ( alphas , labelMat ).T * dataMatrix * dataMatrix[j , :].T ) + b
Ej = fXj - float ( labelMat[j] )
alphaIold = alphas[i].copy ( )
alphaJold = alphas[j].copy ( )
if (labelMat[i] != labelMat[j]):
L = max ( 0 , alphas[j] - alphas[i] )
H = min ( C , C + alphas[j] - alphas[i] )
else:
L = max ( 0 , alphas[j] + alphas[i] - C )
H = min ( C , alphas[j] + alphas[i] )
if L == H:
print ( 'L==H')
continue
eta = 2.0 * dataMatrix[i , :] * dataMatrix[j , :].T - \
dataMatrix[i , :] * dataMatrix[i , :].T - \
dataMatrix[j , :] * dataMatrix[j , :].T
if eta >= 0:
print
'eta>=0'
continue
alphas[j] -= labelMat[j] * (Ei - Ej) / eta
alphas[j] = clipAlpha ( alphas[j] , H , L )
if (abs ( alphas[j] - alphaJold ) < 0.00001):
print('j not moving enough')
continue
alphas[i] += labelMat[j] * labelMat[i] * (alphaJold - alphas[j])
b1 = b - Ei - labelMat[i] * (alphas[i] - alphaIold) * \
dataMatrix[i , :] * dataMatrix[i , :].T - \
labelMat[j] * (alphas[j] - alphaJold) * \
dataMatrix[i , :] * dataMatrix[j , :].T
b2 = b - Ej - labelMat[i] * (alphas[i] - alphaIold) * \
dataMatrix[i , :] * dataMatrix[j , :].T - \
labelMat[j] * (alphas[j] - alphaJold) * \
dataMatrix[j , :] * dataMatrix[j , :].T
if (0 < alphas[i]) and (C > alphas[i]):
b = b1
elif (0 < alphas[j]) and (C > alphas[j]):
b = b2
else:
b = (b1 + b2) / 2.0
alphaPairsChanged += 1
print ('iter: %d i: %d, pairs changed %d' % (iter , i , alphaPairsChanged))
if (alphaPairsChanged == 0):
iter += 1
else:
iter = 0
print
'iteration number: %d' % iter
return b , alphas
if __name__ == "__main__":
dataArr , labelArr = loadDataSet ( 'testSet.txt' )
b , alphas = smoSimple ( dataArr , labelArr , 0.6 , 0.001 , 40 )
print(b , alphas)
