关键字
一根棍分开球。要求：尽量在放更多球之后，仍然适用。
干的不错？
在桌上放了更多的球，似乎有一个球站错了阵营。
SVM就是试图把棍放在最佳位置，好让在棍的两边有尽可能大的间隙。
放了更多的球，棍仍然是一个好的分界线。
然后，在SVM 工具箱中有另一个更加重要的trick。一个新的挑战。
现在，没有棍可以很好帮他分开两种球了，现在怎么办呢？
让球飞到空中。然后，用一张纸，插到了两种球的中间。
现在，这些球看起来像是被一条曲线分开了。
这些球叫做「data」，把棍子 叫做「classifier」, 最大间隙trick 叫做「optimization」， 拍桌子叫做「kernelling」, 那张纸叫做「hyperplane」。
1、支持向量机
支持向量机解决的是多维的分类问题。当给出一定的数据集时，分类学习的最基本想法就是基于训练集在样本空间中找到一个划分超平面，将不同类别的样本划分，又因为在训练学习中，数据大多是高维度的，并且数据不一定都是线性可分的，那么线性不可分的数据，和非线性函数怎么划分呢？这时候就需要使用到一种新的分类器，支持向量机，支持向量机是基于线性分类器提出的另一种设计最佳准则。
2、 支持向量机和线性回归的区别：
线性回归，当样本空间里的属性都是线性可分的时候，如图2.1，使用线性回归即可解决这些问题，但是在实际运用中，样本空间内的特征大部分都不是线性可分的，这时候我们的支持向量机就派上用场了。因为支持向量机可以根据不同的核函数（在下面会讲）得到线性回归模型和非线性回归模型。
3、支持向量机的基本型
在样本空间中，划分超平面通过如下线性方程来描述：
其中w为法向量，决定超平面的方向，b为位移项，决定超平面与原点之间的距离。
但是能将训练样本分开的划分超平面可能有很多，如图2.1
为了寻找最优的划分超平面，我们必须找到具有“最大间隔”的划分超平面。“间隔”指的是两个异类向量距离超平面的距离。如上图。为了找到‘最大间隔’，在这里加上了一个约束条件:
假设有超平面（w，b）能将训练集正确划分，那对于训练集D中的（xi，yi）则有以下约束条件。
根据这个约束条件，可以将3.1中的公式重写：
根据这条公式，产生了支持向量机的基本型
4、核函数
在前面使用的支持向量机基本型，只能支持训练样本是线性可分的情况下，即存在一个划分超平面能将训练样本的正确分类，然而在现实任务中，原始样本空间不一定都会存在一个能正确划分的超平面，例如图4.1的“异或”问题就不是线性可分的。
对于这个问题，怎么办呢？这时候我们就可以将这个原始空间，映射到一个更高维度的特征空间中，如图4.1将一个二维的样本空间，映射到一个三维的特征空间上，就能找到一个合适的划分超平面，按照这个原理，当原始空间是有限维度的，即属性数有限 ，那么一定存在一个高纬度的样本可分。
举个例子：假设需要在一个桌面上划分篮球和红球，并且在尽量在放更多球之后，仍然适用。那么我们可以如下图所示划分，蓝色球跟红色球的间隔最大化。
但如果是下图中的这种无法线性划分的情况，没有直接的直线可以分开两种球了，那怎么办呢？那么可以看做球飞到空中，在其中用一张纸，插到了两种球的中间把两种球分开了。
将原始空间映射后的特征向量模型可表示为：
同样需要寻找最大间隔，所以必须增加约束条件：
对这个函数求解的话，由于特征空间维度可能会很大，甚至无穷维，所以为了避开这个障碍，可以设想一个这样的函数
即Xi与Xj在特征空间内积等于他们在原始空间中通过函数κ（·,·）计算的结果，重写3.5的公式为：
求解后得到
在这里κ(,)就是‘核函数’
通常我们不知道合适映射Φ(·)是什么形式，所以无法直接写出核函数。但任何一个核函数都隐式定义了一个称为“再生和希尔伯特空间”的特征空间。若核函数选择不合适，则意味着将样本映射到了一个不合适的特征空间，很可能导致性能不佳。图3.9列出了常用的核函数。
5、软间隔与正则化
现实任务中，往往很难确定合适的核函数使训练集在特征空间中线性可分，退一步讲，即使恰好找到某个核函数使训练集在特征空间中线性可分，也很难断定这个貌似线性可分的结果是不是过拟合造成的。
缓解这个问题的一个办法就是，允许支持向量机在一些样本上出错。所以引入了‘软间隔’的概念：
在原有的公式上，增加一个损失函数，这些函数不包含在最大间隔计算范围，但是我们计算最大间隔的时候，同时也对于不满足的样本尽可能少
其中C为一个大于0的参数，而C后面的为“0/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)
总结：****SVM是什么？
SVM - support vector machine, 俗称支持向量机，为一种supervised learning算法，属于classification的范畴。
在数据挖掘的应用中，与unsupervised的Clustering相对应和区别。
广泛应用于机器学习(Machine Learning), 计算机视觉(Computer Vision) 和数据挖掘(Data Mining)当中。
SVM大致原理如图1，
假设我们要通过三八线把实心圈和空心圈分成两类。
那么有无数多条线可以完成这个任务。
在SVM中，我们寻找一条最优的分界线使得它到两边的margin都最大。
在这种情况下边缘加粗的几个数据点就叫做support vector，这也是这个分类算法名字的来源。
拓展至任意n维乃至无限维空间，如图2
We got a bunch of data points in a n- dimensional to infinite-dimensional space. Then one can always find a optimal hyperplane which is always in the n-1 dimension.
以及一个很棒的视频演示。自备梯.子。
完整代码参考码云
