机器学习----支持向量机（SVM算法）详解

一、定义

        $$SVM方法是通过一个非线性映射p，把样本空间映射到一个高维乃至无穷维的特征空间中（Hilbert空间），使得在原来的样本空间中非线性可分的问题转化为在特征空间中的线性可分的问题．简单地说，就是升维和线性化．升维，就是把样本向高维空间做映射，一般情况下这会增加计算的复杂性，甚至会引起“维数灾难”，因而人们很少问津．但是作为分类、回归等问题来说，很可能在低维样本空间无法线性处理的样本集，在高维特征空间中却可以通过一个线性超平面实现线性划分（或回归）。

二、概念

2.1、超平面

2.2、超平面公式推导

有此得出点和数据集到超平面的距离就是

2.3、对偶问题

原问题极小极大到对偶问题的极大极小：
                   $$

三、基本流程

支持向量积就是用在高维的空间中使用超平面进行分类，使两边的任意一个数据到超平面的最小距离达到最大！

在这里，有必要解释——-拉格朗日乘子法这里只做简单的解释

根据拉格朗日公式，我们可以得出一下算法：

3.1、我们来看个实例

3.2、松弛因子

四、算法总结

线性（SVM）：找到最好的决策边界
最大化 Margin: 决策边界最近的距离
最小的Margin之和最大化
非线性（SVM）：低维映射到高维再处理，找到最优的（核方法）
里说的缺失数据是指缺失某些特征数据，向量数据不完整。SVM没有处理缺失值的策略（决策树有）。而SVM希望样本在特征空间中线性可分，所以特征空间的好坏对SVM的性能很重要。缺失特征数据将影响训练结果的好坏。

这是我自己写的推导

五、核函数

5.1、问题引入

5.2、映射

假设X是输入空间，H是特征空间，存在一个映射使得X中的点x能够计算得
到H空间中的点h ，对于所有的X中的点都成立：
                                         $$
若x，z是X空间中的点，函数k(x,z)满足下述条件，那么都成立，则称k为核
函数，而为映射函数：
                        $$
      $$要进行高维空间的线性可分，首先要将原始空间的点通过函数映射到特征空间中，然后学习，所谓的学习，其实就是要计算高维空间的点的距离和夹角。

      $$所以我们在高维空间中进行计算的时候，其实根本不必要进行映射，然后再计算，而是直接先进行内积，然后使用核函数。

5.3、核函数分类

5.3.1、线性核

线性核，主要用于线性可分的情况，我们可以看到特征空间到输入空间的维度是一样的，其参数少速度快，对于线性可分数据，其分类效果很理想。
                      $$

5.3.2、多项式核

多项式核，可以实现将低维的输入空间映射到高纬的特征空间，但是多项式核函数的参数多，当多项式的阶数比较高的时候，核矩阵的元素值将趋于无穷大，计算复杂度会大到无法计算。（d≥1为多项式的次数）
                      $$

5.3.3、高斯（RBF）核函数

高斯径向基函数是一种局部性强的核函数，其可以将一个样本映射到一个更高维
的空间内，该核函数是应用最广的一个，无论大样本还是小样本都有比较好的性
能，而且其相对于多项式核函数参数要少，因此大多数情况下在不知道用什么核
函数的时候，优先使用高斯核函数多项式核。（σ> 0为高斯核的带宽 ）

                      $$

5.3.4、sigmoid核函数

5.3.5、选择依据

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

5.4、参数设置

在 SVM 中设定一个参数「C」；从而你可以在两种结果中权衡：
1. 拥有很宽的间隔；
2. 精确分离训练数据；
C 的值越大，意味着在训练数据中允许的误差越少。
必需强调一下这是一个权衡的过程。如果想要更好地分类训练数据，那么代价就是间隔会更宽。以下几个图展示了在不同的 C 值中分类器和间隔的变化（未显示支持向量）。

1. 对于线性可分数据，SVM 工作地非常出色。
2. 对于近似线性可分数据，只要只用正确的 C 值，SVM 仍然可以工作地很好。
3. 对于线性不可分数据，可以将数据映射到另一个空间使数据变得完美或者几乎完美线性可分，将问题回归到了 1 或者 2。
   首先 SVM 一个非常令人惊喜的方面是，其所有使用的数学机制，如精确的映射、甚至是空间的维度都没有显式表示出来。你可以根据数据点（以向量表示）的点积将所有的数学写出来。例如 P 维的向量 i 和 j，第一个下标区分数据点，第二个下标表示维度：
                              $$
   如果数据集中有 n 个点，SVM 只需要将所有点两两配对的点积以寻找分类器。仅此而
   已。当我们需要将数据映射到高维空间的时候也是这样，不需要向 SVM 提供准确的映
   射，而是提供映射空间中所有点两两配对的点积。

                                 $$

确实是这样。这个式子需要多少次计算呢？看看以上式子的第二步。在二维空间中计算
点积只需要 2 次乘法和 1 次加法，平方运算是另一次乘法。因此，总计为：

乘法：2（初始空间的点积）+1（平方运算）=3 次乘法
加法：1（初始空间的点积）

总数为 3+1=4 次计算。只有之前计算量的31%。
看起来使用核函数计算所需要的点积会更快。

5.5、核函数总结

1，通常不会为数据定义一个特定的映射，而是从几个可用的核函数中选择，在某些例子中需要做一些参数调整，最后选出最适合数据的核函数。
2，并不需要定义核函数或者自行将数据映射。
3，如果有可用的核函数，使用它将使计算更快。
4，RBF 核函数可将数据映射到无穷维空间中。

六、核函数选择依据及核矩阵

          $$通过上面的实验我们发现使用多项式核、高斯核的SVM确实是可以解决线性不可分问题的。不同的参数对精度的影响非常大，一般来说，C越大，训练得到的模型越准确。如果采用高斯核，参数γ的值对精度影响也非常大。因此，在实际应用时调一组好的参数对使用效果非常重要！

七、代码部分

import numpy as np
import matplotlib.pyplot as plt
from sklearn import svm
xx, yy = np.meshgrid(np.linspace(-3, 3, 500),
np.linspace(-3, 3, 500))
np.random.seed(0)
X = np.random.randn(300, 2)
Y = np.logical_xor(X[:, 0] > 0, X[:, 1] > 0)
# 训练模型
clf = svm.NuSVC()
clf.fit(X, Y)

Z = clf.decision_function(np.c_[xx.ravel(), yy.ravel()])
Z = Z.reshape(xx.shape)
plt.imshow(Z, interpolation='nearest',
extent=(xx.min(), xx.max(), yy.min(), yy.max()), aspect='auto',origin='lower',cmap=plt.cm.PuOr_r)
contours = plt.contour(xx, yy, Z, levels=[0], linewidths=2,linetypes='--')
plt.scatter(X[:, 0], X[:, 1], s=30, c=Y, cmap=plt.cm.Paired,edgecolors='k')
plt.xticks(())
plt.yticks(())
plt.axis([-3, 3, -3, 3])
plt.show()