【数据挖掘】十大算法之SVM支持向量机分类算法

1 基本概念

支持向量机(support vector machines,SVM)是一种二分类模型。分为

• 线性可分支持向量机：训练数据线性可分，通过硬间隔最大化学习一个线性的分类器，又称为硬间隔支持向量机。
• 线性支持向量机：训练数据近似线性可分，通过软间隔最大化学习一个线性的分类器，又称为软间隔支持向量机。
• 非线性支持向量机：训练数据线性不可分，通过核技巧及软间隔最大化，学习非线性支持向量机。(核技巧：当输入空间为欧式空间或离散集合、特征空间为希尔伯特空间时，核函数表示将输入空间映射到特征空间得到的特征向量之间的内积。通过使用核函数，可以学习非线性支持向量机，等价于隐式地在高维的特征空间中学习线性支持向量机)

2 线性可分支持向量机 2.1 定义

给定线性可分训练数据集，通过间隔最大化或等价地求解相应的凸二次规划问题学习得到的分离超平面为 w ∗ ⋅ x + b ∗ = 0 (1) w^* \cdot x + b^* = 0\tag{1} w∗⋅x+b∗=0(1) 以及相应的分类决策函数 f ( x ) = s i g n ( w ∗ ⋅ x + b ∗ ) (2) f(x) = sign(w^* \cdot x +b^*)\tag{2} f(x)=sign(w∗⋅x+b∗)(2) 称为线性可分支持向量机。

2.2 相关概念

（1）函数间隔

一个点距离超平面的远近可以表示分类预测的确信程度，即函数间隔来表述分类的正确性及确信度。

对于给定的训练数据集T和超平面(w,b)，定义超平面(w,b)关于样本点 ( x i , y i ) (x_i,y_i) (xi​,yi​)的函数间隔为 γ ^ i = y i ( w ⋅ x i + b ) (3) \hat{\gamma } _i = y_i(w \cdot x_i +b) \tag{3} γ^​i​=yi​(w⋅xi​+b)(3) 定义超平面(w,b)关于训练数据集T的函数间隔为超平面(w,b)关于T中所有样本点 ( x i , y i ) (x_i,y_i) (xi​,yi​)的函数间隔之最小值，即 γ ^ = m i n i γ ^ i     i = 1 , . . . , N (4) \hat{\gamma} = min_{i}\hat{\gamma} _i ~~~ i = 1,...,N \tag{4} γ^​=mini​γ^​i​   i=1,...,N(4)

（2）几何间隔

在函数间隔的基础上，将点与超平面之间的间隔规范化。对分离超平面的法向量 w w w取L2范数。表示为 ∣ ∣ w ∣ ∣ ||w|| ∣∣w∣∣，使得超平面的两个参数成比例变化，间隔都是确定。

对于给定的训练数据集T和超平面(w,b)，定义超平面(w,b)关于样本点 ( x i , y i ) (x_i,y_i) (xi​,yi​)的几何间隔为 γ ^ i = y i ( w ∣ ∣ w ∣ ∣ ⋅ x i + b ∣ ∣ w ∣ ∣ ) (5) \hat{\gamma } _i = y_i(\frac{w}{||w||} \cdot x_i +\frac{b}{||w||}) \tag{5} γ^​i​=yi​(∣∣w∣∣w​⋅xi​+∣∣w∣∣b​)(5) 其中 ∣ ∣ w ∣ ∣ ||w|| ∣∣w∣∣表示取w的L2范数。 定义超平面(w,b)关于训练数据集T的几何间隔为超平面(w,b)关于T中所有样本点 ( x i , y i ) (x_i,y_i) (xi​,yi​)的几何间隔之最小值，即 γ ^ = m i n i γ ^ i     i = 1 , . . . , N (6) \hat{\gamma} = min_{i}\hat{\gamma} _i ~~~ i = 1,...,N \tag{6} γ^​=mini​γ^​i​   i=1,...,N(6)

（3）间隔最大化

支持向量机学习的基本想法是求解能够正确划分训练数据集并且几何间隔最大的分离超平面。

间隔最大化：对训练数据集找到几何间隔最大的超平面，以充分大的确信度对训练数据进行分类。

（4）最大间隔法

输入：线性可分训练数据集 T = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , . . . , ( x N , y N ) } T = \{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\} T={(x1​,y1​),(x2​,y2​),...,(xN​,yN​)}，其中 x ∈ X = R n , y i ∈ Y = − 1 , + 1 , i = 1 , 2 , . . . , N x \in X = R^n,y_i \in Y = {-1,+1},i=1,2,...,N x∈X=Rn,yi​∈Y=−1,+1,i=1,2,...,N

输出：最大间隔分离超平面和分类决策函数

a.构造并求解约束最优化问题 m i n w , b 1 2 ∣ ∣ w ∣ ∣ 2 s . t . y i ( w ⋅ x i + b ) − 1 ≥ 0 , i = 1 , 2 , . . , N (7) min_{w,b} \frac{1}{2}||w||^2 \\ s.t. y_i(w \cdot x_i +b)-1 \geq 0,i=1,2,..,N \tag{7} minw,b​21​∣∣w∣∣2s.t.yi​(w⋅xi​+b)−1≥0,i=1,2,..,N(7)

求得最优解 w ∗ , b ∗ w^*,b^* w∗,b∗

b.由此得到分离超平面 w ∗ ⋅ x + b ∗ = 0 (8) w^* \cdot x + b^* = 0\tag{8} w∗⋅x+b∗=0(8) 分类决策函数 f ( x ) = s i g n ( w ∗ ⋅ x + b ∗ ) (9) f(x) = sign(w^* \cdot x +b^*) \tag{9} f(x)=sign(w∗⋅x+b∗)(9) 注意：线性可分训练数据集的最大间隔分离超平面是存在且唯一的。

（5）支持向量

在线性可分的情况下，训练数据集的样本点中与分离超平面距离最近的样本点的实例称为支持向量。

对于 y i y_i yi​ = +1 的正例点，支持向量在超平面 H 1 : w ⋅ x + b = 1 (10) H_1:w \cdot x+b = 1\tag{10} H1​:w⋅x+b=1(10) 对于 y i y_i yi​ = -1 的负例点，支持向量在超平面 H 1 : w ⋅ x + b = − 1 (11) H_1:w \cdot x+b = -1\tag{11} H1​:w⋅x+b=−1(11)

（6）间隔边界

H 1 H_1 H1​和 H 2 H_2 H2​平行，并且没有实例点落在它们中间。在 H 1 H_1 H1​与 H 2 H_2 H2​之间形成一条长带，分离超平面与他们平行且位于他们中央。长带的宽度，即 H 1 H_1 H1​与 H 2 H_2 H2​之间的距离称为间隔。间隔依赖于分离超平民啊的法向量 w w w，等于 2 ∣ ∣ w ∣ ∣ \frac{2}{||w||} ∣∣w∣∣2​。称为 H 1 H_1 H1​和 H 2 H_2 H2​称为间隔边界。

2.3 学习算法

（1）学习的原始算法

线性可分支持向量机学习的原始最优化问题 m i n w , b 1 2 ∣ ∣ w ∣ ∣ 2 s . t . y i ( w i ⋅ i + b ) − 1 ≥ 0 , i = 1 , 2 , . . . , N (12) min_{w,b} \frac{1}{2}||w||^2 \\ s.t. \quad y_i(w_i \cdot_i+b)-1 \geq 0 ,i=1,2,...,N \tag{12} minw,b​21​∣∣w∣∣2s.t.yi​(wi​⋅i​+b)−1≥0,i=1,2,...,N(12) 这是一个凸二次规划问题。

（2） 学习的对偶算法

线性可分支持向量机的对偶算法

对偶算法：将原始最优化问题，应用拉格朗日对偶性，求解对偶问题得到原始问题的最优解。

与原始最优化问题等价的最优化问题： m i n 1 2 ∑ i = 1 N ∑ j = 1 N α i α j y i y j ( x i ⋅ x j ) − ∑ i = 1 N α i s . t . ∑ i = 1 N α i y i = 0 α i ≥ 0 , i = 1 , 2 , . . . , N (13) min \frac{1}{2} \sum_{i=1}^N\sum_{j=1}^N \alpha_i \alpha_j y_i y_j(x_i \cdot x_j) - \sum_{i=1}^N \alpha_i \\ s.t. \quad \sum_{i=1}^N \alpha_i y_i = 0\\ \alpha _i \geq 0,i=1,2,...,N \tag{13} min21​i=1∑N​j=1∑N​αi​αj​yi​yj​(xi​⋅xj​)−i=1∑N​αi​s.t.i=1∑N​αi​yi​=0αi​≥0,i=1,2,...,N(13) 其中 α = ( α 1 , α 2 , . . . , α N ) T \alpha = (\alpha_1,\alpha_2,...,\alpha_N)^T α=(α1​,α2​,...,αN​)T为朗格朗日乘子向量。

定理： 设 α ∗ = ( α 1 ∗ , α 2 ∗ , . . . , α l ∗ ) \alpha^* = (\alpha_1^*,\alpha_2^*,...,\alpha_l^*) α∗=(α1∗​,α2∗​,...,αl∗​)是以上公式13对偶最优化问题的解，则存在小标j，使得 α j ∗ > 0 \alpha_j^* >0 αj∗​>0，并按下式求得原始最优化问题公式12的解 w ∗ w^* w∗， b ∗ b^* b∗ w ∗ = ∑ i = 1 N α i ∗ y i x i b ∗ = y i − ∑ i = 1 N α i ∗ y i ( x i ⋅ x j ) (14) w^* = \sum_{i=1}^N \alpha_i^*y_ix_i\\ b^* = y_i - \sum_{i=1}^N\alpha_i^* y_i(x_i \cdot x_j) \tag{14} w∗=i=1∑N​αi∗​yi​xi​b∗=yi​−i=1∑N​αi∗​yi​(xi​⋅xj​)(14)

优点

• 对偶问题更容易求解
• 自然引入核函数，进而推广到非线性分类问题

4 线性支持向量机 4.1 软间隔最大化

假设给定一个特征空间上的训练数据集 T = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , . . . , ( x N , y N ) } (15) T = \{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\} \tag{15} T={(x1​,y1​),(x2​,y2​),...,(xN​,yN​)}(15) 其中， x i ∈ X = R n , y i ∈ Y = { + 1 , − 1 } , i = 1 , 2 , . . , N , x i x_i \in X = R^n,y_i \in Y = \{+1,-1\},i=1,2,..,N,x_i xi​∈X=Rn,yi​∈Y={+1,−1},i=1,2,..,N,xi​是第i个特征向量， y i y_i yi​为 x i x_i xi​的类标记。

线性不可分意味着某些样本点 ( x i , y i ) (x_i,y_i) (xi​,yi​)不能满足函数间隔大于等于1的约束条件公式12。软间隔最大化就是对每个样本点 ( x i , y i ) (x_i,y_i) (xi​,yi​)引进一个松弛变量 ξ ≥ 0 \xi \geq 0 ξ≥0，使函数间隔加上松弛变量大于等于1。公式12的约束条件就变为 y i ( w ⋅ x i + b ) ≥ 1 − ξ i (16) y_i (w \cdot x_i +b) \geq 1- \xi_i \tag{16} yi​(w⋅xi​+b)≥1−ξi​(16)

同时，对每个松弛变量 ξ i \xi_i ξi​，支付一个代码 ξ i \xi _i ξi​。目标函数由原来的 1 2 ∣ ∣ w ∣ ∣ 2 \frac{1}{2}||w||^2 21​∣∣w∣∣2变成 1 2 ∣ ∣ w ∣ ∣ 2 + C ∑ i = 1 N ξ i (17) \frac{1}{2}||w||^2 +C \sum_{i=1}{N} \xi _i \tag{17} 21​∣∣w∣∣2+Ci=1∑​Nξi​(17) 这里， C > 0 C >0 C>0称为惩罚参数，一般由问题决定，C值大时对误分裂的惩罚增大，反之。

这里的最小目标函数有两层含义

• 使得 1 2 ∣ ∣ w ∣ ∣ 2 \frac{1}{2}||w||^2 21​∣∣w∣∣2尽量小，间隔尽量大。
• 使误分类的个数尽量小。C是调和二者的系数。

通过软间隔最大化，就能以线性可分的方式来处理线性不可分的线性支持向量机学习问题。

4.2 线性支持向量机的原始最优化问题

线性不可分的线性支持向量机的学习问题变成凸二次规划问题 m i n w , b . ξ 1 2 ∣ ∣ w ∣ ∣ 2 + C ∑ i = 1 N ξ i s . t . y i ( w ⋅ x i + b ) ≥ 1 − ξ i , i = 1 , 2 , . . . , N ξ i ≥ 0 , i = 1 , 2 , . . , N (18) min_{w,b.\xi} \quad \frac{1}{2}||w||^2 +C\sum_{i=1}^N \xi _i\\ s.t. \quad y_i(w \cdot x_i +b) \geq 1- \xi _i,i=1,2,...,N\\ \xi _i \geq 0,i=1,2,..,N \tag{18} minw,b.ξ​21​∣∣w∣∣2+Ci=1∑N​ξi​s.t.yi​(w⋅xi​+b)≥1−ξi​,i=1,2,...,Nξi​≥0,i=1,2,..,N(18)

4.3 线性支持向量机定义

对于给定的线性不可分的训练数据集，通过求解凸二次规划问题，即软间隔最大化问题，得到的分离超平面为 w ∗ ⋅ x + b ∗ = 0 (19) w^* \cdot x +b^* = 0 \tag{19} w∗⋅x+b∗=0(19) 以及相应的分类决策函数 f ( x ) = s i g n ( w ∗ ⋅ x + b ∗ ) (20) f(x) = sign(w^* \cdot x +b^*) \tag{20} f(x)=sign(w∗⋅x+b∗)(20)

称为线性支持向量机。

4.4 线性支持向量机的对偶最优化问题

m i n α 1 2 ∑ i = 1 N ∑ j = 1 N α i α j y i y j ( x i ⋅ x j ) − ∑ i = 1 N α i s . t . ∑ i = 1 N α i y i = 0 0 ≤ α i ≤ C , i = 1 , 2 , . . . , N (21) min_{\alpha} \frac{1}{2}\sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j(x_i \cdot x_j) - \sum_{i=1}^N \alpha_i\\ s.t. \quad \sum_{i=1}^N\alpha_i y_i = 0\\ 0 \leq \alpha_i \leq C,i=1,2,...,N \tag{21} minα​21​i=1∑N​j=1∑N​αi​αj​yi​yj​(xi​⋅xj​)−i=1∑N​αi​s.t.i=1∑N​αi​yi​=00≤αi​≤C,i=1,2,...,N(21)

4.5 线性支持向量机学习算法

输入：训练数据集 T = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , . . . , ( x N , y N ) } T = \{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\} T={(x1​,y1​),(x2​,y2​),...,(xN​,yN​)}其中， x i ∈ X = R n ， y i ∈ Y = { + 1 , − 1 } , i = 1 , 2 , . . . , N x_i \in X =R^n，y_i \in Y = \{+1,-1\},i=1,2,...,N xi​∈X=Rn，yi​∈Y={+1,−1},i=1,2,...,N

输出：分离超平面和分类决策函数

（1）选择惩罚参数C>0，构造并求解凸二次规划问题 m i n α 1 2 ∑ i = 1 N ∑ j = 1 N α i α j y i y j ( x i ⋅ x j ) − ∑ i = 1 N α i s . t . ∑ i = 1 N α i y i = 0 0 ≤ α i ≤ C , i = 1 , 2 , . . . , N (22) min_{\alpha} \frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N \alpha_i \alpha_j y_i y_j(x_i \cdot x_j)-\sum_{i=1}^N \alpha_i\\ s.t. \quad \sum_{i=1}^N \alpha_i y_i =0\\ 0 \leq \alpha_i \leq C ,i = 1,2,...,N \tag{22} minα​21​i=1∑N​j=1∑N​αi​αj​yi​yj​(xi​⋅xj​)−i=1∑N​αi​s.t.i=1∑N​αi​yi​=00≤αi​≤C,i=1,2,...,N(22) 求得最优解 α ∗ = ( α 1 ∗ , α 2 ∗ , . . . , α N ∗ ) T \alpha^* = (\alpha^*_1,\alpha^*_2,...,\alpha^*_N)^T α∗=(α1∗​,α2∗​,...,αN∗​)T

（2）计算 w ∗ = ∑ i = 1 N α i ∗ y i x i w^* = \sum_{i=1}^N\alpha_i^* y_i x_i w∗=∑i=1N​αi∗​yi​xi​

选择 α ∗ \alpha^* α∗的一个分量 α j ∗ \alpha_j^* αj∗​适合条件 0 < α j ∗ < C 0