支持向量机 SVM

2018-11-10  本文已影响0人  学以致用123

本文是scikit-learn 支持向量机的翻译，原文地址：http://scikit-learn.org/stable/modules/svm.html

支持向量机是用于分类、回归和异常检测的监督学习方法。

支持向量机的优势：

支持向量机的缺点：

scikit-learn 的支持向量机的输入为稠密矩阵（numpy.ndarray 、可以转化为 numpy.ndarray 的 numpy.asarray ) 和稀疏矩阵（任意 scipy.sparse) 。然而，使用 SVM 对稀疏数据进行预测时必须使用这类数据进行拟合。为了获取最佳效果，请使用 dtype=float64 的 C-ordered numpy.ndarray(稠密) 或 scipy.sparse.csr_matrix(稀疏)。

1.4.1 分类

能够对数据集进行多分类的类包括：SVC、NuSVC 和 LinearSVC 。

SVC 和 NuSVC 是相似的方法，但是采用稍有差异的参数集和不同的数学公式( 见 Mathematical formulation )。LinearSVC 则是使用线性核函数的支持向量机的另一种实现方式。注意，由于假设线性，LinearSVC 并不接受 kernel 关键字的参数，此外，它还缺少 SVC 和 NuSVC 的一些属性，如 support_。

与其它分类器类似，SVC、NuSVC 和 LinearSVC 需要输入两个 arrays：大小为 [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='ovr', 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 使用“one-against-one" 策略（Knerr et al., 1990)实现多分类。如果有 n_class 个类别，那么将构造 n_class*(n_class - 1)/2 个分类器，每个分类器训练两个类。为了与其它分类器的接口保持一致，通过设置 decision_function_shape 可以将 ”one-against-one“ 分类器聚合为 (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 使用 ”one-vs-the-rest“ 策略训练 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

决策函数的完整描述见 Mathematical formulation。

注意， LinearSVC 也可以设置 multi_classes='crammer_singer' 来使用 Crammer 和 Singer 的所谓的多分类策略，这种方法与前面的方法一致，但对于“one-vs-rest”而言却并非如此。实际使用时，通常首选 one-vs-rest，它效果不会差多少但能大大节约运行时间。

one-vs-rest LinearSVC 属性的 coef_ 和 intercept_ 的格式分别为[n_class, n_features] 和 [n_class]。coef_ 的每一行按照”一“ 类的顺序对应 n_class 中的一个 ‘one-vs-rest' 分类器，intercept_ 也是如此。

”one-vs-one“ svc 中，属性的布局更加复杂一些。使用线性核函数时，除了 coef_ 的格式为二分类对应的 [n_class*(n_class-1)/2, n_samples]，conf_ 和 intercept_ 与上面描述的 LinearSVC 的情况类似，分类 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 “one-vs-one” 分类器中用到的任意支持向量。支持向量中的每一个都用于 n_class-1个分类器中。每一行的 n_class - 1 条内容对应这些分类器的双系数。

1.4.1.2 Scores 和 概率

SVC 方法 decision_function 给出每个样本的各类得分（或者二分类中的一个得分）。当构架器选型 probability 设置为 True 时，将启用类成员概率估计（从方法 predict_proba 和 predict_log_proba得到）。对于二分类问题，使用 Platt scaling 进行校准：（通过对训练数据进行额外的交叉验证） SVM score 的 logistic 回归。对于多类情况，Wu et al(2004)等对其进行了扩展。

毋庸置疑，Platt scaling 涉及的交叉验证对于大型数据集来说是一项昂贵的操作。此外，概率估计可能与 scores 不一致。score 的 'argmax' 可能不是概率的 "argmax"，（例如，在二分类中，根据 predict_proba 一个标记的样本属于该类的概率可能 < 1/2)。Platt 方法还存在理论问题。如果需要置信度分数，但是不必是概率，那么建议设置 probability=False 并使用 decison_function 来代替 predict_proba。

相关资料：

1.4.1.3 不平衡问题

特定类或者特定样本需要设置更多权重的问题可以使用 class_weight 和 sample_weight。

SVC（但 NuSVC 不可以）在 fit 方法中使用 class_weight 关键字参数。它的格式是 {class_label:value}，这里 value 是大于 0 的浮点值，如果相同的 class_label 设置了 c 则值为 c*value。

SVC, NuSVC, SVR, NuSVR 和 OneClassSVM 可以在 fit 方法中使用关键词 sample_weight 设置单个样本的权重。与 class_weight 类似参数 c 可用于第 i 个样本 ： c*sample_weight[i]。

例子：

Plot different SVM classifiers in the iris dataset](http://scikit-learn.org/stable/auto_examples/svm/plot_iris.html#sphx-glr-auto-examples-svm-plot-iris-py),

SVM: Maximum margin separating hyperplane,

SVM: Separating hyperplane for unbalanced classes

SVM-Anova: SVM with univariate feature selection,

Non-linear SVM

SVM: Weighted samples,

1.4.2 回归

支持向量分类方法可以扩展到回归问题。这个方法称为 支持向量回归。

由于创建模型的目标函数不关心 margin 之间的训练点，支持向量分类（如上面描述的内容）的模型只依赖于一部分训练数据。

类似的，由于创建模型的目标函数忽略任何与模型预测距离很近的训练数据，支持向量回归也只依赖一部分训练数据。

支持向量回归可以使用三种方法：SVR、NuSVR 和 LinearSVR 。LinearSVR 执行速度比 SVR 快但是只用于线性核函数， NuSVR 与 SVR 和 LinearSVR 的公式稍有不同。详见下面的执行细节。

与分类问题相似，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_deprecated', kernel='rbf', max_iter=-1, shrinking=True,
    tol=0.001, verbose=False)
>>> clf.predict([[1, 1]])
array([1.5])

例子:

1.4.3 密度估计，异常检测

OneClassSVM 类实现一个 One-class SVM 来进行异常检测。

详见 Novelty and Outiler Dection 了解 OneClassSVM 的描述和用法。

1.4.4 复杂度

支持向量机是个强大的工具，但是随着训练样本数量的增加，支持向量机计算和存储的需要会快速增加。SVM的内核是支持向量与其它训练数据分离的二次规划问题（QP）。libsvm 使用的 QP 求解器的计算复杂度在 O(n_{feathures})*n_{samples}^2与O(n_{feathures})*n_{samples}^3之间，具体复杂度取决于实际使用的 libsvm 缓存的效率（依赖数据）。如果数据非常稀疏，应该使用样本向量中的非零特征的平均值替代 n_{features}。

还要注意线性情况下，liblinear 的 LinearSVC 算法执行效率比 基于 libsvm 的 SVC 效率高得多，并且可以几乎线性的扩展到百万个样本或特征。

1.4.5 实际使用过程中的 Tips

1.4.6 核函数

核函数可以是下面的任意一种：

不同的核函数在初始化时由 kernel 关键字指定。

1.4.6.1 自定义核函数

您可以通过自定义 python 函数作为核函数或者使用预先计算的 Gram 矩阵来自定义核函数。

使用自定义核函数的分类器行为与任何其它分类器一致，只有以下区别：

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 with custom kernel。

1.4.6.1.2 使用 Gram 矩阵

设置 kernel =precomputed 并在fit 方法的第一参数中传入 Gram 矩阵来代替 X 。这里， 需要提供所有训练向量和测试向量的 kernel 值。

>>> 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='ovr', degree=3, gamma='auto_deprecated',
    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 核函数的参数

使用 Radial Basis Function(RBF) 核函数训练 SVM 时，必须考虑两个参数 c 和 gamma。参数 C 与 所有 SVM 核函数相似，权衡训练数据错误分类和决策表面的简化。比较低的 c 使得决策表面比较平滑，比较高的 c 期望能够正确分类所有样本。gamma 定义单个样本的影响， gamma 值越大，受到影响的样本越近。

c 和 gamma 的正确选择对 SVM 的性能至关重要。建议使用 sklearn.model_selection.GridSearchCV选择足够好的 c 和 gamma。

例子：

1.4.7 数学公式

支持向量机在高维或无限维空间中构造超平面或超平面集，可用于分类，回归或其他任务。 直观来讲，通过与任何类的最近训练数据点具有最大距离（所谓的功能margin）的超平面实现良好的分离，因为通常 margin 越大，分类器的泛化误差越低。

1.4.7.1 SVC

给定二分类训练向量 x_i \in \R^p,i=1,...,n、y\in \{-1,1\}^n，SVC 解决下面的问题：

min\frac{1}{2}w^Tw+C\sum_{i=1}^n\zeta_i

subject to y_i(w^T \phi(x_i) +b)>=1-\zeta_i ，\zeta_i>=0,i=1,...,n

它的对偶为：

min\frac{1}{2}\alpha^TQ\alpha-e^T\alpha

subject to y^T\alpha=0, 0<=\alpha_i<=C, i=1,...,n

这里，e为全为1的向量，C>0 为上边界，Q 是一个 n*n 正半正定矩阵，Q_{ij}=y_iy_jK(x_i,x_j)，这里 K(x_i,x_j)=\phi(x_i)^T\phi(x_j)是核函数。\phi将训练向量映射到高维(可能无限)空间。

决策函数为：

sgn(\sum_{i=1}^ny_i\alpha_iK(x_i,x)+\rho)

注意， libsvm 和 liblinear 派生的 SVM 模型使用 c 作为正则化参数，但大多数其他估计器使用 alpha 。两个模型的正则化量之间的确切等价关系取决于模型的目标函数。例如，当使用 sklearn_model.Ridge 回归时，它们之间的关系为 C=\frac{1}{alpha}。

这个参数可以通过包含内积y_i\alpha_i 的 dual_coef_ 进行访问，support_vectors_ 包含支持向量，intercept_ 表示独立项 \rho。

参考:

1.4.7.2 NuSVC

我们引入一个新的参数 v，这个参数控制支持向量数量和训练误差。参数 v\in(0,1] 是训练误差部分的上限和支持向量部分的下限。

可以证明 v-SVC 公式是C-SVC的另一表示方法，因此他们在数学上是等效的。

1.4.7.3 SVR

对于训练向量 x_i\in R^p, i=1,...,n, 向量 y\in R^n，\epsilon-SVR解决下面的问题：

min\frac{1}{2}w^Tw+C\sum_{i=1}^{n}(\zeta_i+\zeta_i^*)

subject to y_i-w^T\phi(x_i)-b <= \epsilon+\zeta_i
w^T\phi(x_i)+y_i<=\epsilon+\zeta_i^*$$\zeta_i,\zeta_i^* >=0,i=1,...,n

它的对偶问题为：
min\frac{1}{2}(\alpha-\alpha^*)^TQ(\alpha-\alpha^*)+\epsilon e^T(\alpha+\alpha^*)-y^T(\alpha-\alpha^*)

subject to e^T(\alpha-\alpha^*)=0

0<=\alpha_i,\alpha_i^*<=C,i=1,...,n

这里e为全为 1 的向量， C>0 为上限，Q为 n*n 正半正定矩阵，Q_{ij}=y_iy_jK(x_i,x_j)为核函数，这里的训练向量通过函数\phi映射到更高(可能无限)维度空间。

决策函数为：

\sum_{i=1}^{n}(\alpha_i-\alpha_i^*)K(x_i,x)+\rho

这些参数可以通过保存\alpha_i-\alpha_i^* 的 dual_coef_ 、保存支持向量的 support_vectors 和 保存独立项 \rho 的 intercept_ 获取。

参考：

1.4.8 执行细节

算法内部使用 libsvm 和 liblinear 处理所有计算问题。这些库使用 C 和 Cython 封装。

参考：

详细的算法执行和细节描述请参考：

上一篇下一篇

猜你喜欢

热点阅读