1.什么支持向量机

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

---

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

线性回归，当样本空间里的属性都是线性可分的时候，如图1.1，使用线性回归即可解决这些问题，但是在实际运用中，样本空间内的特征大部分都不是线性可分的，这时候我们的支持向量机就派上用场了。因为支持向量机可以根据不同的核函数（在下面会讲）得到线性回归模型和非线性回归模型。

1.1

2.支持向量机的基本型

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

2.1

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

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

---

假设有超平面（w，b）能将训练集正确划分，那对于训练集D中的（xi，yi）则有以下约束条件。

2.2

根据这个约束条件，可以将2.2中的公式重写：

2.3

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

3.核函数

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

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

---

举个例子：假设需要在一个桌面上划分篮球和红球，并且在尽量在放更多球之后，仍然适用。那么我们可以如下图所示划分，蓝色球跟红色球的间隔最大化。 3.2

但如果是下图中的这种无法线性划分的情况，没有直接的直线可以分开两种球了，那怎么办呢？那么可以看做球飞到空中，在其中用一张纸，插到了两种球的中间把两种球分开了。

3.3

将原始空间映射后的特征向量模型可表示为：

3.4

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

3.5
对这个函数求解的话，由于特征空间维度可能会很大，甚至无穷维，所以为了避开这个障碍，可以设想一个这样的函数 3.6
即Xi与Xj在特征空间内积等于他们在原始空间中通过函数κ（，）计算的结果，重写3.5的公式为：
3.7
求解后得到 3.8
在这里κ(,)就是‘核函数’

---

通常我们不知道合适映射0(·)是什么形式，所以无法直接写出核函。但任何一个核函数都隐式定义了一个称为“再生和希尔伯特空间”的特征空间。核函数的选择对支持向量机的性能至关重要。图3.9列出了常用的核函数。 3.9

4.软间隔与正则化

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

4.1

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

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

5.代码实现支持向量机

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

详细代码查看请点击码云