支持向量机 SVM

作者: 学以致用123 | 来源:发表于2018-11-10 14:14 被阅读0次

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

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

支持向量机的优势：

高维空间有效；
维度高于采样数量的情况依然有效；
在决策函数中使用训练点的子集（称为支持向量），因此节约内存；
功能多样：可以为决策函数指定不同的核函数。这里提供了通用核函数，也可以指定之定义核函数。

支持向量机的缺点：

如果特征的数量大大多于采样的数量，在选择核函数时避免过拟合，正则化至关重要。
SVM 并不直接提供概率估计，概率估计需要使用代价高昂的五重交叉验证计算（参见 Scores and probablities)。

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。

相关资料：

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

Platt “Probabilistic outputs for SVMs and comparisons to regularized likelihood methods".

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])

例子:

Support Vector Regression (SVR) using linear and non-linear kernels

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

避免数据拷贝：对于 SVC、SVR、NuSVC和 NuSVR，如果传入特定方法的数据不是 C-ordered 连续的以及双精度的，那么在调用底层 C 实现之前将进行拷贝。您可以通过检查 flag 属性确定给定的 numpy 数组是否 C 连续。

对于 LinearSVC（和 LogisticRegression)，任何传入的 numpy数据都将被拷贝并转换为 liblinear 内部稀疏数据表示（双精度浮点数，非零元素的 int32 索引）。如果你想不复制大规模线性分类器的密集 numpy C连续双精度数据的输入，我们建议使用 SGDClassifier 类，它可以设置几乎与 LinearSVC 几乎相同的目标函数。
核心缓存大小 对于 SVC、SVR、NuSVC和 NuSVR，对于规模较大的问题核心缓存大小对运行时间影响很大。如果你有足够的 RAM ，推荐将 cache_size 设置到高于默认的200(MB) ，比如 500(MB) 或 1000(MB)。
设置 C 默认 C 为 1，这是一个合理的值，如果有很多噪音样本，应该减小它的值，它与正则化对应。
支持向量机的规模是变化的，强烈推荐归一化数据。例如，将输入向量 X 的每个属性归一化到 [0,1] 或[-1,1]，或者标准化到均值为 0 方差为 1。注意，要对训练向量进行相同的归一化来得到有意义的结果。归一化和标准化的更多内容见 PreProcessing data。
NuSVC / OneClassSVM / NuSVR中的参数nu近似于训练误差和支持向量的比值。
SVC 中如果分类器的数据不平衡（比如很多的正值和很少的负值），尝试设置 class_weight='balanced' 并/或尝试不同的惩罚参数 C。
底层实现的随机性：SVC 和 NuSVC 的底层实现使用一个随机数生成器为概率估计(probability设置为 True 时)打乱数据。这种随机性可以通过 random_state 来控制。如果 probability 设置为 False，估计不是随机的，random
_state对结果没有影响。 OneClassSVM 与 SVC 和 NuSVC 的底层执行类似，OneClassSVM 不提供概率估计，它也不是随机的。
LinearSVC 的底层实现使用双坐标下降（dual 设置为 True) 拟合模型时使用随机数生成器来选择特征，因此，相同的输入数据得到稍微不同的结果并不罕见。如果发生这种情况，尝试减少 tol 参数的值。这种随机性也可以通过 random_state 来控制。当 dual 设置为 False 时，LinearSVC 的底层实现不是随机的，random_state 对结果没有影响。
使用LinearSVC提供的L1惩罚（loss ='l2'，penalty ='l1'，dual = False）产生稀疏解，即只有特征权重的子集不为零并且对决策函数有贡献。增加 C 会产生更复杂的模型（选择更多特征）。可以使用 l1_min_c 计算产生“空”模型（所有权重等于零）的 C 值。

1.4.6 核函数

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

线性的：(x,x')
多项式的： (γ⟨x,x′⟩+r)d。d 由关键字 degree指定, r 由 coef0指定。
rbf： $exp(-\gamma||x-x^{'}||^2)$ ， $\gamma$ 由关键字 gamma 指定，必须大于 0 。
sigmoid： $(tanh(\gamma(x,x^{'})+r))$ ， $r$ 由 coef0指定。

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

1.4.6.1 自定义核函数

您可以通过自定义 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 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。

例子：

RBF SVM parameters

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$ 。

参考:

“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 Learning, 20, 273-297 (1995).

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_ 获取。

参考：

“A Tutorial on Support Vector Regression”, Alex J. Smola, Bernhard Schölkopf - Statistics and Computing archive Volume 14 Issue 3, August 2004, p. 199-222.

1.4.8 执行细节

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

参考：

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

LIBSVM: A Library for Support Vector Machines.

LIBLINEAR – A Library for Large Linear Classification.

支持向量机 SVM

1.4.1 分类

1.4.1.1 多分类

1.4.1.2 Scores 和概率

1.4.1.3 不平衡问题

1.4.2 回归

1.4.3 密度估计，异常检测

1.4.4 复杂度

1.4.5 实际使用过程中的 Tips

1.4.6 核函数

1.4.6.1 自定义核函数

1.4.6.1.1 使用 python 函数作为核函数

1.4.6.1.2 使用 Gram 矩阵

1.4.6.1.3 RBF 核函数的参数

1.4.7 数学公式

1.4.7.1 SVC

1.4.7.2 NuSVC

1.4.7.3 SVR

1.4.8 执行细节

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

支持向量机 SVM

1.4.1 分类

1.4.1.1 多分类

1.4.1.2 Scores 和 概率

1.4.1.3 不平衡问题

1.4.2 回归

1.4.3 密度估计，异常检测

1.4.4 复杂度

1.4.5 实际使用过程中的 Tips

1.4.6 核函数

1.4.6.1 自定义核函数

1.4.6.1.1 使用 python 函数作为核函数

1.4.6.1.2 使用 Gram 矩阵

1.4.6.1.3 RBF 核函数的参数

1.4.7 数学公式

1.4.7.1 SVC

1.4.7.2 NuSVC

1.4.7.3 SVR

1.4.8 执行细节

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

1.4.1.2 Scores 和概率