1.4. 支持向量机#
支持向量机 (SVM) 是一组用于 分类、回归 和 异常值检测 的监督学习方法。
支持向量机的优点包括
在高维空间中有效。
在维度数量大于样本数量的情况下仍然有效。
在决策函数中使用训练点的子集(称为支持向量),因此它也是内存高效的。
通用性:可以为决策函数指定不同的 核函数。提供了常见的核函数,但也可以指定自定义核函数。
支持向量机的缺点包括
scikit-learn 中的支持向量机支持密集 (numpy.ndarray
以及可通过 numpy.asarray
转换为该类型) 和稀疏 (任何 scipy.sparse
) 样本向量作为输入。但是,要使用 SVM 对稀疏数据进行预测,它必须在稀疏数据上进行拟合。为了获得最佳性能,请使用 C 顺序的 numpy.ndarray
(密集) 或 scipy.sparse.csr_matrix
(稀疏),其中 dtype=float64
。
1.4.1. 分类#
SVC
、NuSVC
和 LinearSVC
是能够对数据集执行二元和多元分类的类。
SVC
和 NuSVC
是类似的方法,但接受的参数集略有不同,并且具有不同的数学公式(参见部分 数学公式)。另一方面,LinearSVC
是支持向量分类的另一种(更快的)实现,适用于线性核的情况。它也缺少 SVC
和 NuSVC
的一些属性,例如 support_
。 LinearSVC
使用 squared_hinge
损失,并且由于它在 liblinear
中的实现,它还会对截距进行正则化(如果考虑的话)。但是,可以通过仔细微调其 intercept_scaling
参数来减少这种影响,该参数允许截距项与其他特征相比具有不同的正则化行为。因此,分类结果和得分可能与其他两个分类器不同。
与其他分类器一样,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()
拟合后,模型可用于预测新值
>>> 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
为多类分类实现了“一对一”方法。总共构建了 n_classes * (n_classes - 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(decision_function_shape='ovo')
>>> dec = clf.decision_function([[1]])
>>> dec.shape[1] # 6 classes: 4*3/2 = 6
6
>>> clf.decision_function_shape = "ovr"
>>> dec = clf.decision_function([[1]])
>>> dec.shape[1] # 4 classes
4
另一方面,LinearSVC
实现了“一对多”多类策略,因此训练了 n_classes
个模型。
>>> lin_clf = svm.LinearSVC()
>>> lin_clf.fit(X, Y)
LinearSVC()
>>> dec = lin_clf.decision_function([[1]])
>>> dec.shape[1]
4
有关决策函数的完整描述,请参见 数学公式。
有关多类策略的详细信息#
请注意,LinearSVC
还实现了另一种多类策略,即 Crammer 和 Singer [16] 提出的所谓多类 SVM,通过使用选项 multi_class='crammer_singer'
。在实践中,通常首选一对多分类,因为结果大多相似,但运行时间明显更短。
对于“一对多”LinearSVC
,属性 coef_
和 intercept_
的形状分别为 (n_classes, n_features)
和 (n_classes,)
。系数的每一行对应于 n_classes
个“一对多”分类器之一,截距也是如此,按“一”类的顺序排列。
在“一对一”SVC
和 NuSVC
的情况下,属性的布局稍微复杂一些。在线性核的情况下,属性 coef_
和 intercept_
的形状分别为 (n_classes * (n_classes - 1) / 2, n_features)
和 (n_classes * (n_classes - 1) / 2)
。这类似于上面描述的 LinearSVC
的布局,其中每一行现在对应于一个二元分类器。类 0 到 n 的顺序为“0 对 1”、“0 对 2”、…“0 对 n”、“1 对 2”、“1 对 3”、“1 对 n”、…“n-1 对 n”。
dual_coef_
的形状为 (n_classes-1, n_SV)
,布局有点难以理解。列对应于参与任何 n_classes * (n_classes - 1) / 2
个“一对一”分类器的支持向量。每个支持向量 v
在将 v
的类与另一个类进行比较的 n_classes - 1
个分类器中的每一个中都有一个对偶系数。请注意,这些对偶系数中的一些(但不是全部)可能为零。每一列中的 n_classes - 1
个条目是这些对偶系数,按相反类的顺序排列。
通过一个例子可以更清楚地说明这一点:考虑一个三类问题,其中类 0 有三个支持向量 \(v^{0}_0, v^{1}_0, v^{2}_0\),类 1 和 2 分别有两个支持向量 \(v^{0}_1, v^{1}_1\) 和 \(v^{0}_2, v^{1}_2\)。对于每个支持向量 \(v^{j}_i\),有两个对偶系数。我们称支持向量 \(v^{j}_i\) 在类 \(i\) 和 \(k\) 之间的分类器中的系数为 \(\alpha^{j}_{i,k}\)。然后 dual_coef_
看起来像这样
\(\alpha^{0}_{0,1}\) |
\(\alpha^{1}_{0,1}\) |
\(\alpha^{2}_{0,1}\) |
\(\alpha^{0}_{1,0}\) |
\(\alpha^{1}_{1,0}\) |
\(\alpha^{0}_{2,0}\) |
\(\alpha^{1}_{2,0}\) |
\(\alpha^{0}_{0,2}\) |
\(\alpha^{1}_{0,2}\) |
\(\alpha^{2}_{0,2}\) |
\(\alpha^{0}_{1,2}\) |
\(\alpha^{1}_{1,2}\) |
\(\alpha^{0}_{2,1}\) |
\(\alpha^{1}_{2,1}\) |
类 0 的 SV 的系数 |
类 1 的 SV 的系数 |
类 2 的 SV 的系数 |
示例
1.4.1.2. 分数和概率#
SVC
和 NuSVC
的 decision_function
方法为每个样本提供每个类的分数(或在二元情况下每个样本提供单个分数)。当构造函数选项 probability
设置为 True
时,类成员资格概率估计(来自方法 predict_proba
和 predict_log_proba
)将被启用。在二元情况下,概率使用 Platt 缩放 [9] 进行校准:对 SVM 的分数进行逻辑回归,通过对训练数据的额外交叉验证进行拟合。在多类情况下,这是根据 [10] 进行扩展的。
注意
相同的概率校准过程可通过 CalibratedClassifierCV
(参见 概率校准)用于所有估计器。在 SVC
和 NuSVC
的情况下,此过程内置于 libsvm 中,该库在幕后使用,因此它不依赖于 scikit-learn 的 CalibratedClassifierCV
。
Platt 缩放中涉及的交叉验证对于大型数据集来说是一个昂贵的操作。此外,概率估计可能与分数不一致
分数的“argmax”可能不是概率的 argmax
在二元分类中,即使
predict_proba
的输出小于 0.5,样本也可能被predict
标记为属于正类;类似地,即使predict_proba
的输出大于 0.5,它也可能被标记为负类。
Platt 的方法也被认为存在理论问题。如果需要置信度分数,但这些分数不必是概率,那么建议设置 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)
相同,否则将始终返回平局类中的第一个类;但请记住,它会带来计算成本。有关打破平局的示例,请参见 SVM 平局打破示例。
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
、LinearSVC
、LinearSVR
和 OneClassSVM
也在 fit
方法中通过 sample_weight
参数实现了对单个样本的权重。与 class_weight
类似,这将第 i 个示例的参数 C
设置为 C * sample_weight[i]
,这将鼓励分类器正确地获取这些样本。下图说明了样本加权对决策边界的影響。圆圈的大小与样本权重成正比
示例
1.4.2. 回归#
支持向量分类的方法可以扩展到解决回归问题。这种方法称为支持向量回归。
支持向量分类(如上所述)产生的模型仅取决于训练数据的子集,因为构建模型的成本函数不关心超出边距的训练点。类似地,支持向量回归产生的模型仅取决于训练数据的子集,因为成本函数忽略了预测接近其目标的样本。
支持向量回归有三种不同的实现:SVR
、NuSVR
和 LinearSVR
。LinearSVR
提供了比 SVR
更快的实现,但只考虑线性核,而 NuSVR
实现了与 SVR
和 LinearSVR
略有不同的公式。由于其在 liblinear
中的实现,LinearSVR
也对截距进行正则化,如果考虑的话。但是,可以通过仔细调整其 intercept_scaling
参数来减少这种影响,该参数允许截距项与其他特征相比具有不同的正则化行为。因此,分类结果和分数可能与其他两个分类器不同。有关更多详细信息,请参见 实现细节。
与分类类一样,fit 方法将接受向量 X、y 作为参数,只是在这种情况下,y 预计具有浮点数而不是整数。
>>> from sklearn import svm
>>> X = [[0, 0], [2, 2]]
>>> y = [0.5, 2.5]
>>> regr = svm.SVR()
>>> regr.fit(X, y)
SVR()
>>> regr.predict([[1, 1]])
array([1.5])
示例
1.4.3. 密度估计,新颖性检测#
类 OneClassSVM
实现了一个用于异常值检测的 One-Class SVM。
有关 OneClassSVM 的描述和用法,请参见 新颖性和异常值检测。
1.4.4. 复杂度#
支持向量机是强大的工具,但它们的计算和存储需求随着训练向量数量的增加而迅速增加。SVM 的核心是一个二次规划问题 (QP),将支持向量与训练数据的其余部分分开。基于 libsvm 的实现使用的 QP 求解器在 \(O(n_{features} \times n_{samples}^2)\) 和 \(O(n_{features} \times n_{samples}^3)\) 之间缩放,具体取决于在实践中 libsvm 缓存的效率(数据集相关)。如果数据非常稀疏,则应将 \(n_{features}\) 替换为样本向量中非零特征的平均数量。
对于线性情况,liblinear 实现中 LinearSVC
使用的算法比其基于 libsvm 的 SVC
对应算法效率高得多,并且可以几乎线性地扩展到数百万个样本和/或特征。
1.4.5. 实际使用技巧#
避免数据复制:对于
SVC
、SVR
、NuSVC
和NuSVR
,如果传递给某些方法的数据不是 C 顺序连续且双精度,则在调用底层 C 实现之前会复制该数据。您可以通过检查给定 numpy 数组的flags
属性来检查它是否为 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
,这是一个合理的默认选择。如果您有很多噪声观测值,您应该降低它:降低 C 对应于更多正则化。LinearSVC
和LinearSVR
对C
变得很大时不太敏感,预测结果在某个阈值后停止改进。同时,较大的C
值将需要更多时间来训练,有时会延长 10 倍,如 [11] 所示。支持向量机算法不是尺度不变的,因此强烈建议您对数据进行缩放。例如,将输入向量 X 上的每个属性缩放到 [0,1] 或 [-1,+1],或将其标准化为均值为 0,方差为 1。请注意,必须对测试向量应用相同的缩放才能获得有意义的结果。这可以通过使用
Pipeline
很容易地完成。>>> from sklearn.pipeline import make_pipeline >>> from sklearn.preprocessing import StandardScaler >>> from sklearn.svm import SVC >>> clf = make_pipeline(StandardScaler(), SVC())
有关缩放和规范化的更多详细信息,请参见部分 预处理数据。
关于
shrinking
参数,引用 [12]:我们发现,如果迭代次数很大,那么收缩可以缩短训练时间。但是,如果我们松散地解决优化问题(例如,通过使用较大的停止容差),不使用收缩的代码可能会快得多参数
nu
在NuSVC
/OneClassSVM
/NuSVR
中近似于训练错误和支持向量的分数。在
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(penalty='l1', dual=False)
提供的 L1 惩罚会产生稀疏解,即只有一部分特征权重与零不同,并有助于决策函数。增加C
会产生更复杂的模型(选择更多特征)。产生“空”模型(所有权重都等于零)的C
值可以使用l1_min_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'
另请参阅 内核近似,了解使用 RBF 内核的更快、更可扩展的解决方案。
1.4.6.1. RBF 内核的参数#
在使用径向基函数 (RBF) 内核训练 SVM 时,需要考虑两个参数:C
和 gamma
。参数 C
对所有 SVM 内核都适用,它权衡了训练样本的误分类与决策面的简单性。较低的 C
使决策面平滑,而较高的 C
旨在正确分类所有训练样本。 gamma
定义了单个训练样本的影响程度。 gamma
越大,其他样本必须越靠近才能受到影响。
正确选择 C
和 gamma
对 SVM 的性能至关重要。建议使用 GridSearchCV
,其中 C
和 gamma
以指数级间隔,以选择最佳值。
示例
1.4.6.2. 自定义内核#
您可以通过将内核作为 Python 函数或预先计算 Gram 矩阵来定义自己的内核。
具有自定义内核的分类器与任何其他分类器的行为方式相同,只是
字段
support_vectors_
现在为空,仅在support_
中存储支持向量的索引。在
fit()
方法中,第一个参数的引用(而不是副本)将被存储以供将来参考。如果该数组在使用fit()
和predict()
之间发生更改,您将得到意外的结果。
使用 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)
使用 Gram 矩阵#
您可以通过使用 kernel='precomputed'
选项来传递预先计算的内核。然后,您应该将 Gram 矩阵而不是 X 传递给 fit
和 predict
方法。必须提供所有训练向量和测试向量之间的内核值:
>>> import numpy as np >>> from sklearn.datasets import make_classification >>> from sklearn.model_selection import train_test_split >>> from sklearn import svm >>> X, y = make_classification(n_samples=10, random_state=0) >>> X_train , X_test , y_train, y_test = train_test_split(X, y, random_state=0) >>> clf = svm.SVC(kernel='precomputed') >>> # linear kernel computation >>> gram_train = np.dot(X_train, X_train.T) >>> clf.fit(gram_train, y_train) SVC(kernel='precomputed') >>> # predict on training examples >>> gram_test = np.dot(X_test, X_train.T) >>> clf.predict(gram_test) array([0, 1, 0])
示例
1.4.7. 数学公式#
支持向量机在高维或无限维空间中构建一个超平面或一组超平面,可用于分类、回归或其他任务。直观地说,通过距离任何类别的最近训练数据点(称为函数裕度)最远的超平面可以实现良好的分离,因为通常,裕度越大,分类器的泛化误差越低。下图显示了线性可分离问题的决策函数,其中三个样本位于裕度边界上,称为“支持向量”。
通常,当问题不是线性可分离时,支持向量是位于裕度边界内的样本。
我们推荐 [13] 和 [14] 作为 SVM 理论和实践的良好参考。
1.4.7.1. SVC#
给定两个类别的训练向量 \(x_i \in \mathbb{R}^p\),i=1,…, n,以及向量 \(y \in \{1, -1\}^n\),我们的目标是找到 \(w \in \mathbb{R}^p\) 和 \(b \in \mathbb{R}\),使得由 \(\text{sign} (w^T\phi(x) + b)\) 给出的预测对大多数样本都是正确的。
SVC 求解以下原始问题
直观地说,我们试图最大化裕度(通过最小化 \(||w||^2 = w^Tw\)),同时在样本被误分类或位于裕度边界内时产生惩罚。理想情况下,值 \(y_i (w^T \phi (x_i) + b)\) 对所有样本都应为 \(\geq 1\),这表示完美的预测。但问题通常并不总是可以用超平面完美地分离,因此我们允许一些样本与其正确裕度边界之间的距离为 \(\zeta_i\)。惩罚项 C
控制这种惩罚的强度,因此充当逆正则化参数(见下文说明)。
原始问题的对偶问题是
其中 \(e\) 是全为 1 的向量,\(Q\) 是一个 \(n\) 行 \(n\) 列的半正定矩阵,\(Q_{ij} \equiv y_i y_j K(x_i, x_j)\),其中 \(K(x_i, x_j) = \phi (x_i)^T \phi (x_j)\) 是核函数。项 \(\alpha_i\) 被称为对偶系数,它们的上限为 \(C\)。这种对偶表示突出了这样一个事实,即训练向量被函数 \(\phi\) 隐式地映射到更高(可能无限)维的空间中:参见 核技巧。
一旦优化问题得到解决,决策函数 对给定样本 \(x\) 的输出变为
预测的类别对应于它的符号。我们只需要对支持向量(即位于边距内的样本)求和,因为其他样本的对偶系数 \(\alpha_i\) 为零。
这些参数可以通过属性 dual_coef_
访问,它保存乘积 \(y_i \alpha_i\),support_vectors_
保存支持向量,intercept_
保存独立项 \(b\)
注意
虽然从 libsvm 和 liblinear 推导出的 SVM 模型使用 C
作为正则化参数,但大多数其他估计器使用 alpha
。两种模型的正则化程度之间的精确等价性取决于模型优化的精确目标函数。例如,当使用的估计器是 Ridge
回归时,它们之间的关系为 \(C = \frac{1}{alpha}\)。
LinearSVC#
1.4.7.2. SVR#
给定训练向量 \(x_i \in \mathbb{R}^p\),i=1,…, n,以及向量 \(y \in \mathbb{R}^n\) \(\varepsilon\)-SVR 求解以下原始问题
这里,我们对预测至少偏离其真实目标 \(\varepsilon\) 的样本进行惩罚。这些样本通过 \(\zeta_i\) 或 \(\zeta_i^*\) 对目标函数进行惩罚,具体取决于它们的预测是在 \(\varepsilon\) 管道的上方还是下方。
对偶问题是
其中 \(e\) 是全为 1 的向量,\(Q\) 是一个 \(n\) 行 \(n\) 列的半正定矩阵,\(Q_{ij} \equiv K(x_i, x_j) = \phi (x_i)^T \phi (x_j)\) 是核函数。这里,训练向量被函数 \(\phi\) 隐式地映射到更高(可能无限)维的空间中。
预测是
这些参数可以通过属性 dual_coef_
访问,它保存差值 \(\alpha_i - \alpha_i^*\),support_vectors_
保存支持向量,intercept_
保存独立项 \(b\)
1.4.8. 实现细节#
在内部,我们使用 libsvm [12] 和 liblinear [11] 来处理所有计算。这些库使用 C 和 Cython 进行包装。有关实现的描述和所用算法的详细信息,请参阅它们各自的论文。
参考文献