文档介绍：第三十一章支持向量机
支持向量机是数据挖掘中的一项新技术,是借助于最优化方法来解决机器学****问
题的新工具,最初由 等人提出,近几年来在其理论研究和算法实现等方面都
取得了很大的进展,开始成为克服“维数灾难”和过学****等困难的强有力的手段,它的
理论基础和实现途径的基本框架都已形成。
§1 支持向量分类机的基本原理
根据给定的训练集
l ,
T = {(x1,y1),(x2,y2 ),L,(xl ,yl )}∈(X ×Y)
n
其中 xi ∈ X = R , X 称为输入空间,输入空间中的每一个点 xi 由 n 个属性特征组成,
。寻找 n 上的一个实值函数,以便用分类函数
yi ∈Y = {−1,1},i = 1,L,l R g(x)
f (x) = sgn(g(x)),
推断任意一个模式 x 相对应的 y 值的问题为分类问题。
线性可分支持向量分类机
n
考虑训练集T ,若∃ω∈ R , 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 ≥ 0, j = 1,L, N ; x j ∈ M ⎬,
⎩ j==11j ⎭
M −的凸包 conv(M −) 为
N−−N
−⎧−−⎫
conv(M ) = ⎨x = ∑∑λ j x j | λ j =1, λ j ≥ 0, j =1,L, N ; x j ∈ M ⎬.
⎩ j==11j ⎭
其中 N+ 表示+1类样本集中样本点的个数, N−表示−1类样本集中样本点的个数,定
理 1 给出了训练集T 线性可分与两类样本集凸包之间的关系。
定理 1 训练集T 线性可分的充要条件是,T 的两类样本集 M + 和 M −的凸包相
离。如下图所示
图 1 训练集 T 线性可分时两类样本点集的凸包
证明:①必要性
-761-
+ −
若T 是线性可分的,M = {xi | yi =1, xi ∈T},M = {xi | yi = −1, xi ∈T},由线
性可分的定义可知,存在超平面 H = {x ∈ Rn : (ω⋅ x) + b = 0} 和ε> 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+ N+
⎜⎟
(ω⋅ x) + b = ⎜ω⋅∑αi xi ⎟+ b = ∑αi ((ω⋅ xi ) + b) ≥ε∑αi = ε> 0
⎝ i=1 ⎠ i=1 i=1
⎛ N−⎞ N− N−
(ω⋅ x') + b = ⎜ω⋅β x' ⎟+ b = β((ω⋅ x' ) + b) ≤−εβ= −ε< 0
⎜∑ j j ⎟∑ j j ∑ j
⎝ j=1 ⎠ j=1 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 是线性可分的。
由于空