1.4. 支持向量机

1.4. 支持向量机

支持向量机 (SVMs) 是一套监督学习方法,可用于分类,回归和离群值检测。

支持向量机的优点:

  • 在高维空间中非常有效。

  • 在维度数大于样本数的情况下仍然有效。

  • 在决策函数(称为支持向量)中使用训练集的子集,因此它能提高内存利用率。

  • 多用途:可以为决策函数指定不同的内核函数。提供了通用内核,但也可以指定自定义内核。

支持向量机的缺点:

  • 如果特征数远大于样本数,则在选择核函数时要避免过拟合,并且正则化项至关重要。
  • 支持向量机不直接提供概率估计,而是使用高代价的五重交叉验证来计算(请参阅下面的得分和概率)。

scikit-learn中的支持向量机支持密集(numpy.ndarray,可以通过numpy.asarray进行转换)和稀疏(任何scipy.sparse)样本向量作为输入。 但是,要使用SVM对稀疏数据进行预测,它必须已经拟合此类数据。 为了获得最佳性能,请使用行优先存储(C-order)的numpy.ndarray(密集)或带有数据类型为float64scipy.sparse.csr_matrix(稀疏)。

1.4.1. 分类

SVC,NuSVC andLinearSVC 是能够对数据集进行多元分类。

https://scikit-learn.org/stable/_images/sphx_glr_plot_iris_svc_0011.png

SVC andNuSVC 都是相似的方法,但接受的参数集略有不同,并且有不同的数学公式(请参见数学公式)。另一方面, LinearSVC 是线性核函数的支持向量分类的另一个实现。 注意,LinearSVC不接受关键字kernel,因为这是被假定为线性化的。它还缺少一些SVCNuSVC的成员, 如support_。与其他分类器一样, SVC, NuSVC andLinearSVC 采用两个数组作为输入:一个是大小为[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()

模型进行拟合后,可用于预测新数据:

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

支持向量机决策函数取决于训练数据的子集,称为支持向量。这些支持向量的某些属性可以在成员support_vectors_, support_ and n_support中找到:

>>> # 获得支持向量
>>> clf.support_vectors_
array([[0., 0.],
       [1., 1.]])
>>> # 获得支持向量的索引
>>> clf.support_
array([0, 1]...)
>>> # 为每个类别获得支持向量的数量
>>> clf.n_support_
array([1, 1]...)

1.4.1.1. 多元分类

SVCNuSVC 实现了多元分类 “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(decision_function_shape='ovo')
>>> 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()
>>> dec = lin_clf.decision_function([[1]])
>>> dec.shape[1]
4

有关决策函数的完整说明,请参见数学公式

注意,LinearSVC还通过选项multi_class='crammer_singer'实现了另一种多类别策略,即由Crammer和Singer构造的多元SVM。 这种方法是一致的,对于”one-vs-rest”分类是不对的。实际上,通常首选”one-vs-rest”分类,因为其结果基本相似,但运行时间明显较少。

对于”one vs rest” LinearSVC,属性coef_intercept_ 形状分别为[n_class, n_features][n_class]。系数的每一行对应于n_class分类器“one vs rest”中的一个,并且这一类的顺序类似于拦截器(intercepts)。

对于”one-vs-one” SVC,属性的布局要复杂得多。 在具有线性核函数的情况下,属性coef_intercept_ 形状分别为[n_class * (n_class - 1) / 2, n_features][n_class * (n_class - 1) /2]。这类似于上述 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个条目对应于这些分类器的对偶系数。

举个例子可以更清楚地说明这一点:

考虑一个三类问题,类0有三个支撑向量,v^0_0v^1_0v^2_0,类1和类2有两个支撑向量,分别为v^0_1v^1_1v^0_2v^1_2,对于每一个支持向量v^j_i,有两个对偶系数。在类i和类k之间,我们将支持向量v^j_i的系数记为\alpha^j_{i,k}。那么dual_coef_ 可以表示为:

\alpha^0_{0,1} \alpha^0_{0,2} Coefficients for SVs of class 0
\alpha^1_{0,1} \alpha^1_{0,2} Coefficients for SVs of class 0
\alpha^2_{0,1} \alpha^2_{0,2} Coefficients for SVs of class 0
\alpha^0_{1,0} \alpha^0_{1,2} Coefficients for SVs of class 1
\alpha^1_{1,0} \alpha^1_{1,2} Coefficients for SVs of class 1
\alpha^0_{2,0} \alpha^0_{2,1} Coefficients for SVs of class 2
\alpha^1_{2,0} \alpha^1_{2,1} Coefficients for SVs of class 2

1.4.1.2. 分数和概率

SVCNuSVCdecision_function方法给出每个样本的每类分数(或者在二分类情况下,一个样本一个分数)。当构造函数的probability选项设置为True时,将启用类成员概率估计(来自predict_probapredict_log_proba方法)。在二分类中,概率使用 Platt scaling 进行标准化:在支持向量机的分数上进行逻辑回归,在训练数据上用交叉验证进行拟合。在多类情况下,这可以扩展为Wu et al. (2004).

不用说,对于大型数据集而言,Platt scaling所涉及的交叉验证是一项高代价操作。 另外,分数的”argmax”可能不是概率的”argmax”,所以概率估计可能与分数不一致。 (例如,在二分类中,根据predict_proba,样本可能会被predict值标记为属于概率小于1/2的类别。)Platt的方法也存在理论问题。 如果需要置信度得分(confidence scores),但不一定非要是概率,那么建议设置probability=False,并使用 decision_function代替predict_proba

请注意,当decision_function_shape='ovr'n_classes > 2时,与decision_function不同,predict方法在默认情况下不会尝试断开关系。您可以设置break_ties=True,使得predict的输出与np.argmax(clf.decision_function(...), axis=1)相同,否则将始终返回绑定类中的第一个类;但请记住,它会带来计算开销。

https://scikit-learn.org/stable/_images/sphx_glr_plot_svm_tie_breaking_0011.png

参考文献:

1.4.1.3. 不平衡的问题

在希望更加重视某些类或某些单独样本的问题中,可以使用关键字class_weightsample_weight

SVC (而不是 NuSVC)在fit 方法中实现了一个关键字 class_weight 。这是一个{class_label:value}格式的字典,其中value是一个大于0的浮点数,它将classclass_label的参数 C设置为C * value

https://scikit-learn.org/stable/_images/sphx_glr_plot_separating_hyperplane_unbalanced_0011.png

SVC,NuSVC, SVR,NuSVR,LinearSVC,LinearSVR andOneClassSVM 还实现了在fit 方法中通过关键字sample_weight给单个样本添加权重。与class_weight类似,它们将第i个样本的参数C设置为C * sample_weight[i]

https://scikit-learn.org/stable/_images/sphx_glr_plot_weighted_samples_0011.png

案例:

1.4.2. 回归

支持向量分类方法可以推广到求解回归问题。这种方法称为支持向量回归(Support Vector Regression)。支持向量分类(如上所述)生成的模型仅依赖于训练数据的子集,因为构建模型的损失函数不关心超出边界的训练点。类似地,支持向量回归产生的模型只依赖于训练数据的子集,因为建立模型的损失函数忽略了接近模型预测的任何训练数据。

支持向量回归有三种不同的实现方式:仅考虑线性核的情况下,SVR,NuSVRLinearSVR.LinearSVR 提供比SVR更快的实现,但NuSVR的实现方式与SVRLinearSVR略有不同。 有关更多详细信息,请参见实现细节

与分类类一样,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()
>>> clf.predict([[1, 1]])
array([1.5])

案例:

1.4.3. 密度估计,离群点检测

OneClassSVM实现了一个用于离群点检测的单类支持向量机(One-Class SVM)。

关于OneClassSVM的描述和用法,请参见新奇和异常点检测(Novelty and Outlier Detection)

1.4.4. 复杂性

支持向量机是一种功能强大的工具,但随着训练数据数量的增加,其计算和存储需求也迅速增加。支持向量机的核心是一个二次规划问题(QP),它将支持向量从其余的训练数据中分离出来。基于libsvm实现O(n_{features} * n^2_{samples})和O(n_{features} * n^3_{samples})之间缩放,QP求解器才会被调用,这取决于在实践中使用libsvm缓存的效率(取决于数据集)。如果数据非常稀疏,则应使用样本向量中非零特征的平均数替换n_{features}

还要注意的是,对于线性情况,与基于libsvmSVC算法相比,liblinear实现在LinearSVC中使用的算法效率更高,并且可以线性地扩展到数百万个样本和(/或)特征。

1.4.5. 实用小贴士

  • 避免数据复制:对于SVC,SVR,NuSVCNuSVR,如果传递给特定方法的数据不是行优先存储(C-order)连续的、双精度的,那么在调用底层C命令之前将其复制。通过检查numpy数组的 flags属性来判断该数组是否是行优先存储(C-order)。

    对于LinearSVC (和LogisticRegression),作为numpy数组传递的任何输入都将被复制并转换为用 liblinear 内部稀疏数据表示(双精度浮点和非零部分的int32索引)。如果您想在不复制密集的numpy C-连续双精度数组作为输入的情况下适应大规模线性分类器,我们建议改用SGDClassifier类。目标函数可以配置成与LinearSVC模型几乎相同。

  • 内核缓存大小 : 对于SVC,SVR,NuSVCNuSVR, 内核缓存的大小会对大规模问题的运行时间有很大影响。如果您有足够的可用RAM,建议将 cache_size设置为比默认值200(MB)更高的值,例如500(MB)或1000(MB)。

  • 设置乘法系数CC默认值为1 ,这是一个合理的默认选择。如果你有很多混杂的观测数据,你应该将其值调小。这样更符合正则化估计。

    c值变大时,LinearSVCLinearSVRC的敏感性降低,并且在达到一定阈值后,预测结果将停止提高。 同时,较大的C值将花费更多的时间进行训练,有时会长达10倍,如Fan等人(2008年)的论文所示。

  • 支持向量机算法并不能很好地支持非标准化数据,所以强烈建议您将数据进行标准化。例如,将输入向量X上的每个特征缩放为[0,1]或[-1,+1]范围,或将其标准化为平均值0和方差1。请注意,必须对测试向量应用相同的缩放以获得有意义的结果。有关缩放和标准化化的详细信息,请参阅 数据预处理部分。

  • NuSVC/OneClassSVM/NuSVR 中的参数nu近似于训练误差和支持向量的比例。
  • SVC中,如果分类数据不平衡(例如,多正例少负例),则设置class_weight='balanced'和/或尝试使用其他惩罚参数C
  • 底层实现的随机性SVCNuSVC的**底层实现仅使用随机数生成器来随机打乱数据以进行概率估计(当probability设置为True时) 。 这个随机性可以通过random_state参数来控制。 如果将probability设置为False,则这些估计器不是随机的,并且random_state对结果没有影响。 底层的OneClassSVM实现类似于SVCNuSVC。由于没有为OneClassSVM提供概率估计,因此它不是随机的。

    底层的LinearSVC实现在使用双坐标下降拟合模型时(即当dual设置为True)使用随机数生成器选择特征。因此,对于相同的输入数据有略微不同的结果并不罕见。如果发生这种情况,请尝试使用较小的tol参数。这种随机性也可以用random_state参数来控制。当dual设置为False时,LinearSVC的底层实现不是随机的,random_state对结果没有影响。

  • 使用LinearSVC(loss='l2', penalty='l1', dual=False)提供的L1惩罚会产生稀疏解,即只有特征权重的子集不同于零,才有助于决策函数。增加C 会产生更复杂的模型(更多特征被选择)。可以使用l1_min_C计算出生成 空模型(所有权重都等于零)的C 值。

参考文献:

1.4.6. 内核函数

内核函数可以是以下任意一种:

  • 线性的: \langle x, x’\rangle
  • 多项式的: (\gamma \langle x, x’\rangle + r)^d,其中d是关键字degree指定,rcoef0指定。
  • 径向基函数:(\exp(-\gamma |x-x’|^2)), 其中\gamma由关键字gamma指定,值必须大于0。
  • sigmoid (tanh(\gamma \langle x,x’\rangle + r)),其中rcoef0指定。

初始化时,不同的内核由关键字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. 自定义内核

可以通过将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)

案例:

1.4.6.1.2. 使用Gram矩阵

在fit方法中,设置kernel='precomputed',并给fit方法传递Gram矩阵而不是X。此时,必须提供所有训练向量和测试向量之间的内核值。

>>> import numpy as np
>>> from sklearn import svm
>>> X = np.array([[0, 0], [1, 1]])
>>> y = [0, 1]
>>> clf = svm.SVC(kernel='precomputed')
>>> # 线性内核计算
>>> gram = np.dot(X, X.T)
>>> clf.fit(gram, y)
SVC(kernel='precomputed')
>>> # 预测训练样本
>>> clf.predict(gram)
array([0, 1])

1.4.6.1.3. RBF核的参数

径向基函数(RBF)内核训练支持向量机时,有两个参数必须考虑:Cgamma。所有支持向量机内核函数都有一个共同的参数“C”,它权衡了训练样本的错误分类和决策曲面的简单性。C值低会使决策面平滑,而C值高旨在正确分类所有训练示例。gamma 定义了对单个训练样本的影响程度。gamma越大,其他样本就越容易受到影响。

正确选择 Cgamma 对支持向量机的性能至关重要。建议人们使 sklearn.model_selection.GridSearchCV,使Cgamma以指数方式分隔开,以选择好的值。

案例:

1.4.7. 数学公式

支持向量机在高维或无限维空间中构造一个超平面或一组超平面,可用于分类、回归或其它任务。直观地说,一个好的分割是通过一个超平面来实现的,使得在任何类别中距离超平面最近的训练数据点与超平面的距离最大(所谓的函数裕度),因为通常裕度越大,分类器的泛化误差就越小。

https://scikit-learn.org/stable/_images/sphx_glr_plot_separating_hyperplane_0011.png

1.4.7.1. SVC

给定两个类的训练向量 x_i \in \mathbb{R}^p, i=1,…, n,和y \in \\{{1, -1}\\}^n,SVC解决了以下主要问题:

\min_ {w, b, \zeta} \frac{1}{2} w^T w + C\sum_{i=1}^{n} \zeta_i

subject \quad to \quad y_i (w^T \phi(x_i) + b) \geq 1 – \zeta_i

\zeta_i \geq 0, i=1, …,n

它的对偶是
\min_{\alpha} \frac{1}{2} \alpha^T Q \alpha – e^T \alpha

subject \quad to \quad y^T \alpha = 0

0 \leq \alpha_i \leq C, i=1, …, n

其中e是全为1的向量,C > 0是上界,Qnn的半正定矩阵,Q_{ij} \equiv y_i y_j K(x_i, x_j),其中K(x_i, x_j) = \phi (x_i)^T \phi (x_j)\quad是内核。这里的训练向量由函数\phi间接地映射到一个更高的(可能是无限的)维空间。

决策函数为:
\operatorname{sgn}(\sum_{i=1}^n y_i \alpha_i K(x_i, x) + \rho)
注意

虽然SVM是libsvmliblinear使用C作为正则化参数派生出来的支持向量机模型,但大多数其他估计器使用alpha。两个模型正则化量的精确等价性取决于模型优化的精确目标函数。例如,当使用的估计器是sklearn.linear_model.Ridge回归时,它们之间的关系为C=\frac{1}{alpha}

此参数可通过成员dual_coef_访问,成员dual_coef_包含乘积y_i\alpha_isupport_vectors_包含支持向量,而 intercept_ 包含无关项\rho

参考文献:

1.4.7.2. NuSVC

我们引入了一个新的参数\nu来控制支持向量的个数和训练误差。(0,1]中的参数\nu是训练误差数的上界和支持向量数的下界。

可以证明,\nu-SVC公式是C-SVC的再参数化,因此在数学上是等价的。

1.4.7.3. SVR

给定训练向量 x_i \in \mathbb{R}^p, i=1,…, n, 和向量 y \in \mathbb{R}^n \varepsilon-SVR 解决了以下主要问题:
\min_ {w, b, \zeta, \zeta^_} \frac{1}{2} w^T w+ C \sum_{i=1}^{n} (\zeta_i + \zeta_i^_)

subject \quad to \quad y_i – w^T \phi (x_i) – b \leq \varepsilon + \zeta_i,

w^T \phi (x_i) + b – y_i \leq \varepsilon + \zeta_i^*,

\zeta_i,\zeta_i^* \geq 0, i=1, …,n

它的对偶是
\min_{\alpha, \alpha^_} \frac{1}{2} (\alpha – \alpha^_)^T Q (\alpha – \alpha^_) + \varepsilon e^T (\alpha + \alpha^_) – y^T (\alpha – \alpha^*)

subject \quad to \quad e^T (\alpha – \alpha^*)=0,

0\leq \alpha_i, \alpha_i^* \leq C, i=1, …, n

其中 e是全为1的向量, C > 0 是上界, Q 是一个 nn 的半正定矩阵, 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_访问,成员dual_coef_包含差值\alpha_i-\alpha_i^_support_vectors_包含支持向量,intercept_包含无关项\rho

参考文献:

1.4.8. 实现细节

在内部,我们使用libsvmliblinear 处理所有的计算。这些库是使用C和Cython进行包装的。

参考文献

有关实现的描述和使用算法的详细信息,请参考

(C) 2007 – 2019, scikit-learn 开发人员(BSD许可证). 此页显示源码

未经允许不得转载:PythonOK » 1.4. 支持向量机

赞 (0)