31第三十一节 支持向量机.doc

第三十一章 支持向量机 支持向量机是数据挖掘中的一项新技术，是借助于最优化方法来解决机器学习问题的新工具，最初由 V.Vapnik 等人提出，近几年来在其理论研究和算法实现等方面都取得了很大的进展，开始成为克服“维数灾难”和过学习等困难的强有力的手段，它的理论基础和实现途径的基本框架都已形成。 §1 支持向量分类机的基本原理根据给定的训练集 T = {(x1,y1 ), (x2 ,y2 ),L, (xl ,yl )}∈ ( X ×Y )l ， 其中 xi ∈ X = Rn ， X 称为输入空间，输入空间中的每一个点 xi 由 n 个属性特征组成， yi ∈Y = {?1,1},i = 1,L,l 。寻找 Rn 上的一个实值函数 g(x) ，以便用分类函数 f (x) = sgn(g(x)), 推断任意一个模式 x 相对应的 y 值的问题为分类问题。 线性可分支持向量分类机 考虑训练集 T ，若 ?ω ∈ Rn ， b ∈ R 和正数 ε ，使得对所有使 yi = 1 的下标 i 有 (ω ? xi ) + b ≥ ε（这里 (ω ? xi ) 表示向量 ω 和 xi 的内积），而对所有使 yi = ?1的下标 i 有 (ω ? xi ) + b ≤ ?ε ，则称训练集 T 线性可分，称相应的分类问题是线性可分的。 记两类样本集分别为 M + = {xi | yi = 1, xi ∈T}， M ? = {xi | yi = ?1, xi ∈T}。定义  M + 的凸包 conv(M + ) 为 N+ N+ conv(M + ) = x = ∑ λ j x j | ∑λ j = 1, j=1 j=1 M ? 的凸包 conv(M ? ) 为 N? N? conv(M ? ) = x = ∑ λ j x j | ∑λ j = 1, j=1 j=1  λ j ≥ 0, j = 1,L, N + ; x j ∈ M + , λ j ≥ 0, j = 1,L, N ? ; x j ∈ M ? . 其中 N+ 表示 +1 类样本集中样本点的个数， N? 表示 ?1类样本集中样本点的个数，定理 1 给出了训练集 T 线性可分与两类样本集凸包之间的关系。 定理 1 训练集 T 线性可分的充要条件是， T 的两类样本集 M + 和 M ? 的凸包相离。如下图所示 图 1 训练集 T 线性可分时两类样本点集的凸包 证明：①必要性  -762-  和 ε 0 ，使得 若 T 是线性可分的，M + = {xi | yi = 1, xi ∈T}，M ? = {xi | yi = ?1, xi ∈T}，由线 性可分的定义可知，存在超平面 H = {x ∈ Rn : (ω ? x) + b = 0} (ω ? xi ) + b ≥ ε ， ?xi ∈ M + 且 (ω ? xi ) + b ≤ ?ε ， ?xi ∈ M ? . 而正类点集的凸包中的任意一点 x 和负类点集的凸包中的任意一点 x 可分别表示为 N+ N? x = ∑αi xi 和 x = ∑β j x j i=1 j=1 N + N ? 其中αi ≥ 0, β j ≥ 0 且 ∑αi = 1， ∑β j = 1。 i =1 j =1 于是可以得到  (ω ? (ω ?  N+ N+ + b = ∑αi ((ω ? xi x) + b = ω ? ∑αi xi i=1 i=1 N? N? + b = ∑β j ((ω ? x) + b = ω ? ∑β j x j j=1 j=1  ) + x j  N+ b) ≥ ε ∑αi = ε 0 i=1 N? ) + b) ≤ ?ε ∑β j = ?ε 0 j=1 由此可见，正负两类点集的凸包位于超平面 (ω ? x) + b = 0 的两侧，故两个凸包相离。②充分性设两类点集 M + ，M ? 的凸包相离。因为两个凸包都是闭凸集，且有界，根据凸集 强分离定理，可知存在一个超平面 H = {x ∈ Rn : (ω ? x) + b = 0} 强分离这两个凸包，即存在正数 ε 0 ，使得对 M + ， M ? 的凸包中的任意点 x 和 x 分别有 (ω ? x) + b ≥ ε (ω ? x) + b ≤ ?ε 显然特别的，对于任意的 xi ∈ M + ，有 (ω ? xi ) + b ≥ ε ，对于任意的 xi ∈ M ? ，有 (ω ? xi ) + b ≤ ?ε ，由训练集线性可分的定义可知 T 是线性可分的。 由于空间 Rn 中超平面都可以写为 (ω ? x) + b =