1.4. 支持向量机

支持向量机（SVM）是一系列可用于分类、回归和异常值检测的有监督学习方法。

支持向量机的优点包括：

在高维空间中行之有效。
当维数大于样本数时仍然可用。
在决策函数中只使用训练点的一个子集（称为支持向量），大大节省了内存开销。
用途广泛：决策函数中可以使用不同的核函数。提供了一种通用的核，但是也可以指定自定义的核。

而其劣势在于

如果特征数量远大于样本数量，则表现会比较差。
SVM不直接提供概率估计。这个值通过五折交叉验证计算，代价比较高（见下面“跑分与概率”一节）。

Scikit-learn中的支持向量机同时支持密集样本向量（numpy.ndarray和可通过numpy.asarray转化的数据类型）和稀疏样本向量（任何scipy.sparse对象）。但是如果想用SVM对稀疏数据进行预测，则必须先在这些数据上拟合。为了优化性能，应该使用C阶（C-Ordered）numpy.ndarray（密集的）或scipy.sparse.csr_matrix（稀疏的），并指定dtype=float64。

1.4.1. 分类

要在数据集上进行多类别分类，可以使用SVC，NuSVC和LinearSVC这三个类。

SVC和NuSVC两种方法类似，但是接受的参数有细微不同，而且底层的数学原理不一样（见“数学原理”一节）。另一方面，LinearSVC是对支持向量分类的另一种实现，使用了线性核。注意LinearSVC不接受关键字kernel，因为核被预设为是线性的。其与SVC和NuSVC相比还缺少了一些成员，如support_。

和其它分类器一样，SVC，NuSVC和LinearSVC接受两个数组：大小为[n_samples, n_features]的数组X，包含训练样本；以及大小为[n_samples]的数组y，包含类别标签（以字符串类型或整型存储）：

>>> from sklearn import svm
>>> X = [[0, 0], [1, 1]]
>>> y = [0, 1]
>>> clf = svm.SVC()
>>> clf.fit(X, y)  
SVC(C=1.0, cache_size=200, class_weight=None, coef0=0.0,
    decision_function_shape=None, degree=3, gamma='auto', kernel='rbf',
    max_iter=-1, probability=False, random_state=None, shrinking=True,
    tol=0.001, verbose=False)

拟合以后就可以用得到的模型预测新值

>>> clf.predict([[2., 2.]])
array([1])

SVM的决策函数依赖于训练数据的一个子集，称为支持向量。它们的一些属性可以在成员变量support_vectors_，support_和n_support中找到

>>> # get support vectors
>>> clf.support_vectors_
array([[ 0.,  0.],
       [ 1.,  1.]])
>>> # get indices of support vectors
>>> clf.support_ 
array([0, 1]...)
>>> # get number of support vectors for each class
>>> clf.n_support_ 
array([1, 1]...)

1.4.1.1. 多类别分类

SVC和NuSVC使用“一对多”方法（Knerr et al., 1990）来实现多类别分类。如果n_class是类别的数目，则该实现会构造n_class * (n_class - 1) / 2个分类器，每个分类器针对两个类别对数据进行训练。为了提供一个和其它分类器一致的接口，选项decision_function_shape允许调用者将所有“一对一”分类器的结果聚合进一个(n_samples, n_classes)的决策函数

>>> X = [[0], [1], [2], [3]]
>>> Y = [0, 1, 2, 3]
>>> clf = svm.SVC(decision_function_shape='ovo')
>>> clf.fit(X, Y) 
SVC(C=1.0, cache_size=200, class_weight=None, coef0=0.0,
    decision_function_shape='ovo', degree=3, gamma='auto', kernel='rbf',
    max_iter=-1, probability=False, random_state=None, shrinking=True,
    tol=0.001, verbose=False)
>>> dec = clf.decision_function([[1]])
>>> dec.shape[1] # 4 classes: 4*3/2 = 6
6
>>> clf.decision_function_shape = "ovr"
>>> dec = clf.decision_function([[1]])
>>> dec.shape[1] # 4 classes
4

另一方面，LinearSVC实现了“一对多”分类法，因此会训练n_class个模型。如果只有两个类别，那么只会得到一个模型：

>>> lin_clf = svm.LinearSVC()
>>> lin_clf.fit(X, Y) 
LinearSVC(C=1.0, class_weight=None, dual=True, fit_intercept=True,
     intercept_scaling=1, loss='squared_hinge', max_iter=1000,
     multi_class='ovr', penalty='l2', random_state=None, tol=0.0001,
     verbose=0)
>>> dec = lin_clf.decision_function([[1]])
>>> dec.shape[1]
4

决策函数的完整描述可见“数学原理”一节。

需要注意的是，LinearSVC还实现了另一种分类策略，即所谓的多类别SVM（由Crammer和Singer提出）。通过指定multi_class='crammer_singer'，可以使用该方法。它得到的结果总是一致的，但是一对多分类法并不能保证这一点。然而在实际应用中，还是一对多分类法用的更多，因为通常来讲该方法得到的结果变化不会太大（mostly similar），而且用的时间显著的短。

一对多LinearSVC得到的属性中，coef_是n_class * n_features维矩阵，而intercept_是n_class * 1维的。系数中的每一行都对应于n_class个“一对多”分类器中的一个（截距也是类似），按照每个与其它类别进行比较的类别顺序排序（in the order of the "one" class）。

而在“一对一”SVC中，属性的格式略微有些复杂难懂。在有线性核的情况下，coef_和intercept_的格式与上面所述LinearSVC的类似，只不过coef的大小为[n_class * (n_class - 1) / 2, n_features]（对应于二元分类器的个数）。类别0到n的顺序是“0 vs 1”, “0 vs 2” , ... “0 vs n”, “1 vs 2”, “1 vs 3”, “1 vs n”, . . . “n-1 vs n”。

dual_coef的大小是[n_class-1, n_SV]，不过格式有些难以描述。列对应于n_class * (n_class - 1) / 2个“一对一”分类器中出现的支持向量。每个支持向量被用于n_class - 1个分类器中。每一行中n_class - 1个项目对应于这些分类器的对偶系数（dual coefficient）。

举个例子可能能说清楚一点：

考虑一个三元分类问题。类别0的支持向量为 $v_0^0,v_0^1,v_0^2$ 。类别1和2有两个支持向量，分别为 $v_1^0,v_1^1$ 和 $v_2^0,v_2^1$ 。对每个支持向量 $v_i^j$ ，有两个对偶系数。称类别 $i$ 和 $k$ 之间分类器支持向量 $v_i^j$ 的系数为 $\alpha_{i,k}^j$ ，则dual_coef_如下表所示：

[表格暂缺]

1.4.1.2. 得分与概率

SVC中的decision_function方法对每个样本都会给出在各个类别上的分数（在二元分类问题中，是对每个样本给出一个分数）。如果构造函数的probability被设为True，则可以得到属于每个类别的概率估计（通过predict_proba和predict_log_proba方法）。在二元分类中，概率使用Platt缩放进行调整：通过在训练机上做额外的交叉检验来拟合一个在SVM分数上的Logistic回归。在多元分类中，这种方法被Wu et al. (2004)扩展了。

显而易见的是，Platt缩放中的交叉检验在大数据集上是一个代价很高的操作。此外，概率估计与实际得分可能会不一致，即使得分取得了最大值，概率并不一定也能取到最大值。（例如在二元分类中，某个样本经由predict方法得到的分类标签，如果使用predict_proba计算可能概率小于1/2。）Platt的方法在理论上也有一些问题。如果需要拿到置信分数，而这些分数又不一定非得是概率，则建议把probability置为False，并且使用decision_function，而不是predict_proba。

参考文献

Wu, Lin and Weng, “Probability estimates for multi-class classification by pairwise coupling”. JMLR 5:975-1005, 2004.

1.4.1.3. 不平衡问题

在某些情况下，一些指定的类别或某几个样本关键字可能更加重要，这时可以使用class_weight和sample_weight。

SVC（不是NuSVC）在fit方法中实现了关键字class_weight。该关键字是字典类型，形式为{class_label : value}，这里value是一个正浮点数，将类别class_label的参数C设为C * value。

SVC，NuSVC，SVR，NuSVR和OneClassSVM同样在fit方法中通过关键字sample_weight实现了对单独样本赋予特殊权重的功能。与class_weight类似，它们把第i个样本的参数C设为C * sample_weight[i]。

例子

1.4.2. 回归

支持向量分类这样的方法可以经扩展用在回归问题上，称作支持向量回归。

支持向量分类产生的模型，如上所述，只依赖于训练数据的一个子集。其原因在于，构造模型时用到的代价函数并不关心那些不在边界上的数据点。类似的，支持向量回归所生成的模型也只依赖于训练数据的一个自己，因为构造模型时用到的代价函数用不上那些与预测值很接近的训练数据。

支持向量回归有三种不同实现：SVR, NuSVR和LinearSVR。LinearSVR提供的实现比SVR快，但是只使用线性核。NuSVR则是使用了一个略不同的数学原理。细节见后面“实现细节”部分。

与分类问题类似，fit方法接受向量X和y作为参数，不过这里y应该是浮点型而不是整型：

>>> from sklearn import svm
>>> X = [[0, 0], [2, 2]]
>>> y = [0.5, 2.5]
>>> clf = svm.SVR()
>>> clf.fit(X, y) 
SVR(C=1.0, cache_size=200, coef0=0.0, degree=3, epsilon=0.1, gamma='auto',
    kernel='rbf', max_iter=-1, shrinking=True, tol=0.001, verbose=False)
>>> clf.predict([[1, 1]])
array([ 1.5])

例子

使用线性核和非线性核进行支持向量回归（SVR）

1.4.3. 密度估计与新奇值检测（novelty detection）

单类别SVM可用于新奇值检测，即给定一组样本，检测出该数据集的软边界，以判断新数据点是否属于该数据集。OneClassSVM类实现该方法。在这种情况下，由于这是一种无监督学习，数据没有类别标签，因此fit方法只接受数组X作为输入。见新奇值与异常值检测检测一节了解更多用法。

例子

1.4.4. 复杂度

支持向量机是一种能力很强的工具，但是随着支持向量数目的增加，它们对计算和存储资源的需求也会快速增长。SVM的核心是二次规划问题（QP），将支持向量与其他训练数据分开。取决于libsvm缓存在实践中使用的效率（这又是依赖于具体的数据集），基于libsvm的实现所用的QP求解器时间复杂度在 $O(n_{\mathrm{features}} \times n_{\mathrm{samples}}^2)$ 到 $O(n_{\mathrm{features}} \times n_{\mathrm{samples}}^3)$ 不等。如果数据非常稀疏， $n_\mathrm{features}$ 应该被样本向量中非零特征的平均数取代。

还要注意的是，对线性的情况，基于liblinear实现的LinearSVC的算法比基于libsvm实现的SVC效率要高很多，而且前者在处理以百万计的样本和/或特征时仅以线性增长。

1.4.5. 应用建议

避免数据拷贝：对SVC、SVR、NuSVC和NuSVR，如果传给特定方法的数据不是以C语言所使用的顺序排列，而且是double精度，那么该数据会在调用底层C实现之前被拷贝一份。通过检查flag属性，可以检查给定的numpy数组是否是以C格式的连续存储方式排列的。对LinearSVC和LogisticRegression，任何以numpy数组形式传入的输入都会被拷贝，然后转化为liblinear内部的稀疏数据表示形式（双精度浮点数，对非零元素存储32位整型的索引）。如果你想训练一个大规模的线性分类器，而又不想拷贝一个稠密的numpy C-存储双精度数组，我们建议使用SGDClassifier。可以对它的目标函数进行配置，使其与LinearSVC模型所使用的基本相同。
核缓存大小：对SVC、SVR、NuSVC和NuSVR，核缓存的大小对较大问题求解的运行时间有非常强的影响。如果你有足够内存，建议将cache_size设置为一个高于默认值200（MB）的值，比如500（MB）或1000（MB）。
设置C：默认情况下C设为1，这是一个合理的选择。如果样本中有许多噪音观察点，则应该减小这个值。这意味着对估计结果进行更严格的正则化。
SVM算法会受数据取值范围的影响，所以强烈建议在使用之前对数据进行缩放。例如把输入向量X的每个属性缩放到[0,1]或[-1,+1]内，或者进行标准化使数据的均值为0方差为1。注意在测试向量上也要进行同样的缩放，这样才能得到有意义的结果。关于数据缩放和标准化的更多细节，参见处理数据一节
NuSVC/OneClassVM/NuSVR中的参数mu估计了训练误差和支持向量的比率
在SVC中，如果要分类的数据是不平衡的（如有很多正数据但是很少负数据），应该加选项class_weight='balanced'然后/或者尝试不同的惩罚项参数C。
LinearSVC的底层实现使用了随机数生成器来在拟合模型时选择特征。因此对同样的输入数据有略微不同的结果不是怪事。如果发生了这样的情况，试一个更小的tol参数
利用LinearSVC(loss='l2', penalty='l1', dual=False)来引入L1惩罚项会产生一个稀疏解，即特征权重中只有一少部分不为0，会对决策函数产生贡献。增加C会产生一个更复杂的模型（有更多特征被选择）。可以通过l1_min_c来计算产生“空”模型（所有权重都是0）的C值。

1.4.6. 核函数

核函数可以有以下几种选择：

线性核 $\langle x, x' \rangle$
多项式核 $(\gamma \langle x, x' \rangle + r)^d$ 。其中 $d$ 由选项degree指定， $r$ 由coef0指定
径向基函数（RBF）： $\exp(-\gamma|x - x'|^2)$ 。其中 $\gamma$ 由选项gamma指定，必须大于0
sigmoid函数（ $\tanh(\gamma\langle x, x' \rangle + r)$ )，其中 $r$ 由选项coef0指定

在初始化时通过选项kernel指定用什么核

>>> linear_svc = svm.SVC(kernel='linear')
>>> linear_svc.kernel
'linear'
>>> rbf_svc = svm.SVC(kernel='rbf')
>>> rbf_svc.kernel
'rbf'

1.4.6.1. 自定义核

Scikit提供两种方法来自定义核函数：给参数kernel传入一个python函数，或者提前计算好Gram矩阵。使用自定义核的分类器和其它分类器有类似的行为，不过以下两点除外：

support_vectors_域为空，只在support_里面存储支持向量的索引
会为fit()方法的第一个参数存储一个引用（不是拷贝），来为以后引用之做准备。如果在调用fit()之后，在调用predict()之前修改这个数组，则会产生一些不可预知的结果。

1.4.6.1.1. 使用Python函数作为核

可以在构造函数中向参数kernel传进一个函数，来使用自定义的核。该函数必须接受两个大小分别为(n_samples_1, n_features), (n_samples_2, n_features)的矩阵作为参数，返回一个大小为(n_samples_1, n_samples_2)的核矩阵。

如下代码定义了一个线性核，并使用该核创建了一个分类器实例

>>> import numpy as np
>>> from sklearn import svm
>>> def my_kernel(X, Y):
...     return np.dot(X, Y.T)
...
>>> clf = svm.SVC(kernel=my_kernel)

例子

使用自定义核的SVM

1.4.6.1.2. 使用Gram矩阵

将参数kernel设为precomputed，就可以把Gram矩阵（而不是X）传给fit方法。若如此做，需要提供所有训练向量和测试向量之间的核的值。

>>> import numpy as np
>>> from sklearn import svm
>>> X = np.array([[0, 0], [1, 1]])
>>> y = [0, 1]
>>> clf = svm.SVC(kernel='precomputed')
>>> # linear kernel computation
>>> gram = np.dot(X, X.T)
>>> clf.fit(gram, y) 
SVC(C=1.0, cache_size=200, class_weight=None, coef0=0.0,
    decision_function_shape=None, degree=3, gamma='auto',
    kernel='precomputed', max_iter=-1, probability=False,
    random_state=None, shrinking=True, tol=0.001, verbose=False)
>>> # predict on training examples
>>> clf.predict(gram)
array([0, 1])

1.4.6.1.3. RBF核的参数

使用径向基函数（RBF）核训练SVM时，需要考虑C和gamma这两个参数。参数C会被所有SVM核用到，用来在样本误分类和决策平面的简单性之间做出权衡。C值如果小，得到的决策平面会更光滑；而大的C则试图将所有训练样本都进行正确的分类。gamma定义单个训练样本能有多少影响。gamma越大，与之更近的样本受到的影响越大。

对这两个值的选择会极大影响SVM的性能。建议使用sklearn.grid_search.GridSearchCV来在C和gamma广阔的指数空间里进行选择，得到最合适的值。

例子

RBF SVM参数

1.4.7. 数学表示

支持向量机的原理是在高维甚至无限维空间中构建一个超平面或者若干超平面组成的集合，并藉此用于分类、回归或其它任务。从直觉上来讲，好的分隔面是由使得函数间隔最大的超平面得到（即该超平面到任何类别最近训练数据点的距离都取得最大值），因为总体上来讲，间隔越大，分类器的泛化误差越小。

1.4.7.1. SVC

给定可能属于某两种类别的训练向量 $x_i \in \mathbb{R}^p, i=1,\ldots,n$ 和向量 $y\in \{1,-1\}^n$ ，SVC解决的首要问题是 $\begin{align} \min_{w,b,\zeta}&\frac{1}{2}w^Tw+C\sum_{i=1}^n\zeta_i \\ \mathrm{subject\ to}\ \ &y_i(w^T\phi(x_i)+b)\ge 1 - \zeta_i, \\ &\zeta_i \ge 0,i=1,\ldots,n \end{align}$

其对偶形式为 $\begin{align} \min_\alpha &\frac{1}{2}\alpha^TQ\alpha - e^T\alpha \\ \mathrm{subject\ to}\ \ &y^T\alpha = 0 \\ &0 \le \alpha_i \le C, i=1,\ldots,n \end{align}$ 其中 $e$ 是全1向量， $C>0$ 是上界， $Q$ 是 $n \times n$ 半正定矩阵， $Q_ij \equiv y_iy_jK(x_i, x_j)$ ，其中 $K(x_i,x_j) = \phi(x_i)^T\phi(x_j)$ 是核。这里训练向量通过函数 $\phi$ 被隐式映射到一个高维（甚至无限维）空间。

决策函数是 $\mathrm{sgn}(\sum_{i=1}^n y_i\alpha_i K(x_i, x) + \rho)$ 注意：虽然从libsvm和liblinear导出的SVM模型使用C作为正则化参数，但实际上其它更多预测器使用的是alpha。这两个参数之间的关系是 $C=\frac{n_\mathrm{samples}}{alpha}$

这些参数可以通过各个成员变量访问：dual_coef_存放乘积 $y_i\alpha_i$ ，support_vectors存放支持向量，intercept_存放独立项 $\rho$ ：

参考文献：

Automatic Capacity Tuning of Very Large VC-dimension Classifiers, I Guyon, B Boser, V Vapnik - Advances in neural information processing 1993,
Support-vector networks, C. Cortes, V. Vapnik, Machine Leaming, 20, 273-297 (1995)

1.4.7.2. NuSVC

我们提供了一个新的参数 $\nu$ ，控制支持向量的个数和训练误差。参数 $\nu \in (0,1]$ 是训练误差的上限和支持向量的下限。

可以看到 $\nu$ -SVC是 $C$ -SVC的一种重参数化形式，因此两者在数学上是等价的。

1.4.7.3. SVR

给定训练向量组 $x_i \in \mathbb{R}^p,\ i = 1, \ldots, n$ 和向量 $y\in \mathbb{R}^n$ , $\varepsilon$ -SVR要解决的主要问题如下所示： $\begin{align} \min_{w,b,\zeta,\zeta^*} &\frac{1}{2}w^Tw + C\sum_{i=1}^n(\zeta_i + \zeta_i^*) \\ {\rm subject\ to}\ &y_i - w^T\phi(x_i) - b \le \varepsilon + \zeta_i \\ &w^T\phi(x_i) + b - y_i \le \varepsilon + \zeta_i^* \\ &\zeta_i, \zeta_i^* \ge 0, i = 1,\ldots,n \end{align}$ 其对偶为 $\begin{align} \min_{\alpha, \alpha^*}\frac{1}{2} (\alpha-\alpha^*)^T&Q(\alpha-\alpha^*) + \varepsilon e^T(\alpha+\alpha^*) - y^T(\alpha-\alpha^*) \\ {\rm subject\ to}\ \ &e^T(\alpha-\alpha^*) = 0 \\ & 0 \le \alpha_i,\alpha_i^* \le C, i = 1, \ldots, n \end{align}$ 其中 $e$ 是全1向量， $C>0$ 是上界。 $Q$ 是 $n\times n$ 的半正定矩阵， $Q_{ij} \equiv K(x_i, x_j) = \phi(x_i)^T\phi(x_j)$ 是核。这里训练向量通过函数 $\phi$ 被隐式映射到一个高维（甚至无限维）空间。

决策函数为 $\sum_{i=1}^n (\alpha_i - \alpha_i^*)K(x_i, x) + \rho$ 这些参数可以通过各个成员变量访问。其中变量dual_coef_存储 $\alpha_i -\alpha_i^*$ ，support_vectors_存储支持向量，intercept_存储独立项 $\rho$