支持向量机原理：

VC维：对一个指标函数集，如果存在H个样本能够被函数集中的函数按所有可能的2的H次方种形式分开，则称函数集能够把H个样本打散；函数集的VC维就是它能打散的最大样本数目H。VC维反映了函数集的学习能力，VC维越大则学习机器越复杂（容量越大），遗憾的是，目前尚没有通用的关于任意函数集VC维计算的理论，只对一些特殊的函数集知道其VC维。例如在N维空间中线形分类器和线形实函数的VC维是N+1。

结构风险最小原理（Structural Risk Minimization）基础之上的：指把函数集构造为一个函数子集序列,使各个子集按照VC维的大小排列;在每个子集中寻找最小经验风险,在子集间折衷考虑经验风险和置信范围，取得实际风险的最小化。即SRM准则。

在感知机的最后，说到它必须是在线性可分的条件下使用，正因为这样，满足条件的超平面可能会有多条，那么哪一条是最好的呢？直观上看，应该去找“正中间”的那条，因为它尽可能的讲样本分开，而且不易受到局部的干扰。首先和感知机一样，划分超平面的线性方程可为：$$w^{T}X+b=0$$
任一点的几何距离为（其中y表示正负样本，取1，-1）：$$\frac{y(w^T{x}_i+b)}{||w||}$$
实际上分子的含义是预测的$w^{T}X+b$和真实的标签y是否一致（在感知机中大于0为1，小于0则为-1，那么这个值本身减去分割值0就是它们之间的函数距离，乘以y以代表是否被误分作为损失函数），而$||w||$是分割线的单位向量指示方向，即样本点与线之间的几何距离。

那么如何使这间隔最大？那就使所有点都尽可能的离这分割线远远的就好，这就能得到第一个约束条件：$$\sum _{x_i\in M}-y^{(i)}(w^T{x}^{(i)}+b)$$在感知机模型中，优化时希望所有的点都离超平面远。但是实际上离超平面很远的点已经被正确分类，所以让它再离超平面更远并没有很大的意义。而那些离超平面很近的点，这些点非常容易被误分类，所以反过来关心这些点似乎更有帮助，这些点即被称为“支持向量”。
现在我们固定函数间隔为1，这并没有什么影响，只是方便分析（间隔为0的时候，样本点将落入在线上，实际上我们是想要让样本之间分隔的越大越好，从这一点看SVM实际上是一个margin-large liner classification，而margin算是一个中立的缓冲区，至少要有1或者其他数能够分隔出两类）。比如如下图：

最佳线是红线，但是使两样本距离最大其实仅仅与||w||有关，所以将原式分子设为1。
然后可以得到基于让所有点都隔得远的约束条件的情况下，使间隔最大的优化函数：$$max\frac{1}{||w||}s.t{y}_i(w^T{x}_i+b)\ge 1(i=1,2,...m)$$
显然为了最大化间隔，需要最大化$||w|{|}^{-1}$，这等价于最小化$\frac{1}{2}||w|{|}^2$，为了方便处理，于是可以重写函数为：$$min\frac{1}{2}||w|{|}^{2}s.t{y}_i(w^T{x}_i+b)\ge 1(i=1,2,...m)$$
st是subject to，注意到该式是一个凸二次规划（convex quadratic programing，寻找一个w使二次线性约束函数最小化，所以变成$\frac{1}{2}||w|{|}^2$也是故意的，毕竟二次规划问题的处理太成熟了），能用现成的优化计算包求解。

• 线性规划: 目标函数和约束条件都为变量的线性函数
• 二次规划: 目标函数为变量的二次函数, 约束条件为线性函数
• 非线性规划: 目标函数或者约束条件是非线性函数

不过考虑到$\frac{1}{2}||w|{|}^2$是凸函数，约束条件不等式又是仿射的，所以可以有更高效的方法来解。即通过拉格朗日函数合二为一将其转化为无约束的优化函数。首先，该问题的拉格朗日函数为：$$L(w,b,\alpha )=\frac{1}{2}||w|{|}^2+\sum _{i=1}^m{\alpha }_i((1-y_i(w^T{x}_i+b))$$

因为是不等式条件下的约束，所以不能仅仅是求导数，还需要最大化正数的$\alpha$以保证不等式的约束是有效的！不至于无解。
令$L(w,b,\alpha )$对w，b求偏导得：$$\frac{\partial L(w,b,\alpha )}{\partial w}=0\Rightarrow w=\sum _{i=1}^m{\alpha }_i{y}_i{x}_i$$$$\frac{\partial L(w,b,\alpha )}{\partial b}=0\Rightarrow \sum _{i=1}^m{\alpha }_i{y}_i=0$$然后将w带入拉格朗日函数消去w，b，再考虑$\sum _{i=1}^m{\alpha }_i{y}_i=0$的约束，便可得到其对偶问题（并不一定要用拉格朗日对偶。要注意用拉格朗日对偶并没有改变最优解，而是改变了算法复杂度。在原问题$mi{n}_{w,b}ma{x}_{\alpha }$下，求解算法的复杂度与样本维度w有关；而在对偶问题$ma{x}_{\alpha }mi{n}_{w,b}$下，求解算法的复杂度与样本数量（$\alpha$的数量）有关，因为内层求导为0得到值最大的情况就可以了）。：$$max\sum _{i=1}^m{\alpha }_i-\frac{1}{2}\sum _{i=1}^m\sum _{j=1}^m{\alpha }_i{\alpha }_j{y}_i{y}_j(x_i^T{x}_j)$$$$s.t.\sum _{i=1}^m{\alpha }_i{y}_i=0$$$${\alpha }_i\ge 0i=1,2,...m$$
奇迹！ 在于这个式子的w，b被完全没有了，只和样本的两两相乘有关！（这也是后面可以用各种核方法进行优化的点）。那么只要求出${\alpha }_i$就完全ok了（由于消去了参数，SVM也就不像LR，SVM是一个非参数模型，拿出来就能用）。

KKT（Karush-Kuhn-Tucker）
那么怎么求${\alpha }_i$呢？因为不等式的约束，所以必须得满足KKT（Karush-Kuhn-Tucker）条件（其实是拉格朗日乘数法的推广，用于求解即带有等式，也带有不等式的函数极值，做法跟拉格朗日也基本一致，先把不等式当等式所有值求出来之后满足所有条件的值才保留，这些所有的条件包括不等式的条件就是KKT）:$${\alpha }_i\ge 0;$$$$y_{i}f(s_i)-1\ge 0;$$$${\alpha }_i(y_{i}f(s_i)-1)=0;$$

满足最后的条件的就是支持向量。这是一个二次规划问题，但是如果直接用二次规划算法求解在实际任务中可能会有很大的时间开销，所以SMO登场。

SMO（Sequential Minimal Optimization）
$\alpha$的数目实在太多了，不方便直接优化。所以SMO算法则采用了一种启发式的方法,由于$\sum _{i=1}^m{\alpha }_i{y}_i=0$，若固定某一个之外的其他变量，他本身是可以由其他变量导出的，于是SMO算法每次优化两个变量，将其他的变量都视为常数。这样再初始化后，不断执行更新直至收敛。除了SMO还有Chunking算法，Osuna算法等也很高效。

SVM流程

• 构造优化问题
• SMO算法求解$\alpha$
• 根据$\alpha$求解w
• 满足$\alpha$大于0的样本，使其满足最后一个条件即支持向量以算出b，b的均值就是最后的b值

（通过约束得到所有样本的距离最小即w，最好的分割则由支持向量算b做准确的调整）

算法实现：（Python）

def selectJrand(i,m):#取一个不等于i的j
    j=i
    while (j==i):
        j = int(random.uniform(0,m))
    return j

def clipAlpha(aj,H,L):#调整alpha在H和L之间
    if aj > H: 
        aj = H
    if L > aj:
        aj = L
    return aj
    
#简易SMO。输入参数分别为数据集，类别标签，常数c，容错率，最大循环次数。
#常数c用来控制最大化间隔和保证大部分点的函数间隔小于1
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)))#初始化alpha为0
    iter = 0
    while (iter < maxIter):#外循环，迭代次数控制
        alphaPairsChanged = 0#记录alpha的更改次数
        for i in range(m):#内循环，对每个数据向量
            fXi = float(multiply(alphas,labelMat).T*(dataMatrix*dataMatrix[i,:].T)) + b#multiply对应元素相乘。
            Ei = fXi - float(labelMat[i])
            if ((labelMat[i]*Ei < -toler) and (alphas[i] < C)) or ((labelMat[i]*Ei > toler) and (alphas[i] > 0)):#由于下面max和min的调整，如果alpha为0是已经在边界内部（已经正确分类的点），为c则是在两条边界之间，不需要再做优化。
                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#两个alpha必须1.都在间隔之外，2.没有进行过区间化处理或者不在边界上。H，L是线性规划得出的范围，是alpha的值范围，详情见SOM原理！！！
                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
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

在前面的讨论中一直假定了特征空间是线性可分的，但是现实样本往往摻杂噪声使空间难以分割，而且退一步就算找到了可分，也很难断定它的结果是否是由于过拟合造成的。缓解这种现象的办法就是在一定范围内允许SVM在一些样本上出错，为此产生了 “软间隔” （soft margin），加入一个C稀疏来平衡对间隔1的放水因子$\xi$。
$$min\frac{1}{2}||w|{|}_2^2+C\sum _{i=1}^m{\xi }_i$$$$s.t.y_i(w^T{x}_i+b)\ge 1-{\xi }_i(i=1,2,...m)$$$${\xi }_i\ge 0(i=1,2,...m)$$
hinge合页损失，如果点被正确分类，且函数间隔大于1，损失是0。

。

从线性到非线性。核机器
然而对于大部分数据不是线性的，软间隔的处理效果有限。但是既然SVM是个“升维”投影的作用，那么是否可以直接x投影升维变成非线性再SVM（不过核函数不用显示升维，而是可以看作就是一个在低维计算高维的表现）：
$$f(x)=\sum _{i=1}^n{\alpha }_i{y}_i<\varphi (x_i),\varphi (x)>+b$$

所以SVM 的处理方法是选择一个核函数 κ(⋅,⋅) ，通过将数据映射到高维空间，来解决在原始空间中线性不可分的问题。正如奇迹推导的最后是不同样本中相乘，k：
$$K(x,z)=\varphi (x)\bullet \varphi (z)$$
几种常见的核函数在后面整理。下面这张投影图很深刻的解释了kernel。。。

详细推导看v_JULY_v的这篇文章：http://blog.csdn.net/v_july_v/article/details/7624837。看三遍看三遍看三遍！

最后就SVM方法的算法而言它最终转化成了一个二次型寻优问题，得到了在神经网络中很难得到的全局最优值。将实际问题通过非线性变换到高维的特征空间，巧妙的解决了维数问题。而且只要定义不同的内积函数，就可以实现多项式逼近，贝叶斯分类器，径向基函数（Radial Basic Function，RBF），多层感知机等算法。

如何处理多分类？
训练时依次把某个类别的样本归为一类,其他剩余的样本归为另一类，这样k个类别的样本就构造出了k个SVM。
其做法是在任意两类样本之间设计一个SVM，因此k个类别的样本就需要设计k(k-1)/2个SVM。
层次分类法首先将所有类别分成两个子类，再将子类进一步划分成两个次级子类，如此循环，直到得到一个单独的类别为止。

解释对偶的概念。
线性规划有一个有趣的特性，就是任何一个求极大的问题都有一个与其匹配的求极小的线性规划问题。
若一个模型为目标求极大 约束为小于等于的不等式，则它的对偶模型为目标求极小 约束为极大的不等式 。

为什么要将求解SVM的原始问题转换为其对偶问题？
当在寻找约束存在时的最优点的时候，约束的存在虽然减小了需要搜寻的范围，但是却使问题变得更加复杂。为了使问题变得易于处理，就把目标函数和约束全部融入一个新的函数，即拉格朗日函数，再通过这个函数来寻找最优点。自然引入核函数，进而推广到非线性分类问题。

SVM算法特性
可以解决高维特征，在特征维度大于样本数时仍有很好的效果。
仅仅使用一部分支持向量来做超平面的决策，无需依赖全部数据。
有大量的核函数可以使用，从而可以很灵活的来解决各种非线性的分类回归问题。高斯核便于逼近任意的联系函数，但在大数据的情况下，多是选用线性核，因为在效果相当的情况下，速度会更快。

如果特征维度远远大于样本数，SVM容易欠拟合，效果不佳。
SVM在样本量非常大，核函数映射维度非常高时，计算量过大，不太适合使用。
SVM对缺失数据敏感。这里说的缺失数据是指缺失某些特征数据，向量数据不完整。SVM没有处理缺失值的策略（决策树有）。

SVM、LR、决策树的选择？
首先就应该选择的逻辑回归，如果它的效果不怎么样，也可以作为基准来参考，然后再试决策树（随机森林）是否可以大幅度提升模型性能。如果也不会当做最终模型，移除噪声变量也是很好的，如果特征的数量和观测样本特别多，当资源和时间充足时，应该使用SVM。
关于三者的详细比较在这里。

SVM与NN

• SVM在数据量很大的时候，计算量过大，不太适合使用。而NN是数据驱动，数据量很重要。
• SVM非参数，NN需要训练收敛。

常用核函数

• 线性核函数: $K(x,z)=x\bullet z$，主要用于线性可分的情况，而且参数少速度快，对于线性可分数据，其分类效果很理想。
• 多项式核函数: $K(x,z)=（\gamma x\bullet z+r{)}^d$，多项式核函数可以实现将低维的输入空间映射到高纬的特征空间，但是多项式核函数的参数多，当多项式的阶数比较高的时候，核矩阵的元素值将趋于无穷大或者无穷小，计算复杂度会大到无法计算。
• 高斯核函数: $K(x,z)=exp(-\gamma ||x-z|{|}^2)$，高斯径向基函数是一种局部性强的核函数，其可以将一个样本映射到一个更高维的空间内，该核函数是应用最广的一个，无论大样本还是小样本都有比较好的性能，而且其相对于多项式核函数参数要少，因此大多数情况下在不知道用什么核函数的时候，优先使用高斯核函数。
• Sigmoid核函数: $K(x,z)=tanh（\gamma x\bullet z+r)$，拉普拉斯，幂指数，多元二次，逆多元二次，小波核，贝叶斯核。

选用方法：
如果特征的数量大到和样本数量差不多，则选用LR或者线性核的SVM；
如果特征的数量小，样本的数量正常，则选用SVM+高斯核函数；
如果特征的数量小，而样本的数量很大，则需要手工添加一些特征从而变成第一种情况。

SVM应用：
（1）用sklearn来分类iris数据集

from sklearn import datasets,svm
import matplotlib.pyplot as plt
import numpy as np


iris=datasets.load_iris()

x=iris.data[:,:2]
y=iris.target
svc=svm.SVC(kernel='linear',C=1.0).fit(x,y)
x_min,x_max=x[:,0].min()-0.5,x[:,0].max()+0.5
y_min,y_max=x[:,1].min()-0.5,x[:,1].max()+0.5
X,Y=np.meshgrid(np.arange(x_min,x_max,0.02),np.arange(y_min,y_max,0.02))

Z=svc.predict(np.c_[X.ravel(),Y.ravel()])
Z=Z.reshape(X.shape)
plt.contourf(X,Y,Z,alpha=0.4)
plt.contour(X,Y,Z,colors='k')
plt.scatter(x[:,0],x[:,1],c=y)
plt.show()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

更换核函数：svc=svm.SVC(kernel=‘poly’,C=1.0，degree=3).fit(x,y)

更换核函数：svc=svm.SVC(kernel=‘rbf’,gamma=3,C=1.0).fit(x,y)

（2）sklearn异常检测

import numpy as np
import matplotlib.pyplot as plt
import matplotlib.font_manager
from sklearn import svm

xx, yy = np.meshgrid(np.linspace(-5, 5, 500), np.linspace(-5, 5, 500))
X = 0.3 * np.random.randn(100, 2)
X_train = np.r_[X + 2, X - 2]
X = 0.3 * np.random.randn(20, 2)
X_test = np.r_[X + 2, X - 2]
X_outliers = np.random.uniform(low=-4, high=4, size=(20, 2))


clf = svm.OneClassSVM(nu=0.1, kernel="rbf", gamma=0.1)
clf.fit(X_train)
y_pred_train = clf.predict(X_train)
y_pred_test = clf.predict(X_test)
y_pred_outliers = clf.predict(X_outliers)
n_error_train = y_pred_train[y_pred_train == -1].size
n_error_test = y_pred_test[y_pred_test == -1].size
n_error_outliers = y_pred_outliers[y_pred_outliers == 1].size


Z = clf.decision_function(np.c_[xx.ravel(), yy.ravel()])
Z = Z.reshape(xx.shape)

plt.title("Novelty Detection")
plt.contourf(xx, yy, Z, levels=np.linspace(Z.min(), 0, 7), cmap=plt.cm.PuBu)
a = plt.contour(xx, yy, Z, levels=[0], linewidths=2, colors='darkred')
plt.contourf(xx, yy, Z, levels=[0, Z.max()], colors='palevioletred')

s = 40
b1 = plt.scatter(X_train[:, 0], X_train[:, 1], c='white', s=s, edgecolors='k')
b2 = plt.scatter(X_test[:, 0], X_test[:, 1], c='blueviolet', s=s,
                 edgecolors='k')
c = plt.scatter(X_outliers[:, 0], X_outliers[:, 1], c='gold', s=s,
                edgecolors='k')
plt.axis('tight')
plt.xlim((-5, 5))
plt.ylim((-5, 5))
plt.legend([a.collections[0], b1, b2, c],
           ["learned frontier", "training observations",
            "new regular observations", "new abnormal observations"],
           loc="upper left",
           prop=matplotlib.font_manager.FontProperties(size=11))
plt.xlabel(
    "error train: %d/200 ; errors novel regular: %d/40 ; "
    "errors novel abnormal: %d/40"
    % (n_error_train, n_error_test, n_error_outliers))
plt.show()

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

用台湾大学的林教授等人开源的libsvm库

from svmutil import *
x,y = svm_read_problem('../train_data')
x_,y_=svm_read_problem('../test_data')
m = svm_train(x,y)
label, acc, val = svm_predict(x_,y_, m)
print(label)
#svm_save_model("model.txt",m)
1
2
3
4
5
6
7