1.什么支持向量机

当给出一定的数据集时，分类学习的最基本想法就是基于训练集在样本空间中找到一个划分超平面，将不同类别的样本去划分，又因为在训练学习中，数据大多是高维度的，并且数据不一定都是线性可分的，那么线性不可分的数据，和非线性函数怎么划分呢？这时候就需要使用到一种新的分类器，支持向量机，支持向量机是基于线性分类器提出的另一种设计最佳准则。

支持向量机和线性回归的区别：

线性回归，当样本空间里的属性都是线性可分的时候，如图1.1，使用线性回归即可解决这些问题，但是在实际运用中，样本空间内的特征大部分都不是线性可分的，这时候我们的支持向量机就派上用场了

1.1

2.支持向量机的基本型

在样本空间中，划分超平面通过的线性方程：

2.1

其中w为法向量，决定超平面的方向，b为位移项，决定超平面与原点之间的距离
但是基于这个线性方程划分的超平面，很明显，会有很多种划分方法，如图1.1

而为了寻找最优的划分超平面，我们必须找到具有“最大间隔”的划分超平面。“间隔”指的是两个异类向量距离超平面的距离。为了找到‘最大间隔’，在这里加上了一个约束条件，将2.1中的公式重写：

2.3

根据这条公式，产生了支持向量机的基本型

3.核函数

在2中使用的支持向量机基本型，只能支持训练样本是线性可分的情况下，即存在一个划分超平面能将训练样本的正确分类，然而在现实任务中，原始样本空间不一定都会存在一个能正确划分的超平面，例如图3.1的“异或”问题就不是线性可分的。

3.1

对于这个问题，怎么办呢？这时候我们就可以将这个原始空间，映射到一个更高维度的特征空间中，如图3.1将一个二维的样本空间，映射到一个三维的特征空间上，就能找到一个合适的划分超平面，按照这个原理，当原始空间是有限维度的，即属性数有限 ，那么一定存在一个高纬度的样本可分。
将原始空间映射后的特征向量模型可表示为：

3.2
如2.2一样，需要寻找最大间隔，所以必须增加约束条件：
3.3

对这个函数求解的话，由于特征空间维度可能会很大，甚至无穷维，所以为了避开这个障碍，可以设想一个这样的函数

3.4
即Xi与Xj在特征空间内积等于他们在原始空间中通过函数κ（，）计算的结果，重写3.3的公式为：
3.4
求解后得到 3.5
在这里κ(,)就是‘核函数’

4.软间隔与正则化

在现实任务中，数据并不“纯”，而且在显示任务中很难确认核函数是否真的那么适合，即使你得出一个刚刚好把数据划分得很完美的超平面，你也很难确定，这是不是因为学习器把数据学习得太好了，而产生‘过拟合’。
为了缓解这个问题的一个办法就是，允许支持向量机在一些样本上出错。所以引入了‘软间隔’的概念：

4.1

在原有的公式上，增加一个损失函数，这些函数不包含在最大间隔计算范围，但是我们计算最大间隔的时候，同时也对于不满足的样本尽可能少

4.2
其中C为一个大于0的参数，而C后面的为“0/1损失函数”如图4.1所示，间隔在1的样本，我们把它当作损失函数 4.2

《机器学习实战》中给出了利用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)

码云地址：https://gitee.com/ZHBIT-MachineLearning/Machine-Learning-Base/tree/master/SVM