-762-第三十一章支持向量机支持向量机是数据挖掘中的一项新技术，是借助于最优化方法来解决机器学习问题的新工具，最初由V.Vapnik等人提出，近几年来在其理论研究和算法实现等方面都取得了很大的进展，开始成为克服“维数灾难”和过学习等困难的强有力的手段，它的理论基础和实现途径的基本框架都已形成。§1支持向量分类机的基本原理根据给定的训练集lllYX,yx,yx,yxT)()}(,),(),{(2211×∈=L，其中niRXx=∈，X称为输入空间，输入空间中的每一个点ix由n个属性特征组成，liYyi,,1},1,1{L=−=∈。寻找nR上的一个实值函数)(xg，以便用分类函数)),(sgn()(xgxf=推断任意一个模式x相对应的y值的问题为分类问题。1.1线性可分支持向量分类机考虑训练集T，若nR∈∃ω，Rb∈和正数ε，使得对所有使1=iy的下标i有εω≥+⋅bxi)(（这里)(ix⋅ω表示向量ω和ix的内积），而对所有使1−=iy的下标i有εω−≤+⋅bxi)(，则称训练集T线性可分，称相应的分类问题是线性可分的。记两类样本集分别为},1|{TxyxMiii∈==+，},1|{TxyxMiii∈−==−。定义+M的凸包)(conv+M为,;,,1,0,1|)(conv11⎭⎬⎫⎩⎨⎧∈=≥===∑∑++==+++NjNjjjjjjMxNjxxMLλλλ−M的凸包)(conv−M为.;,,1,0,1|)(conv11⎭⎬⎫⎩⎨⎧∈=≥===∑∑−−==−−−NjNjjjjjjMxNjxxMLλλλ其中+N表示1+类样本集中样本点的个数，−N表示1−类样本集中样本点的个数，定理1给出了训练集T线性可分与两类样本集凸包之间的关系。定理1训练集T线性可分的充要条件是，T的两类样本集+M和−M的凸包相离。如下图所示图1训练集T线性可分时两类样本点集的凸包证明：①必要性-763-若T是线性可分的，},1|{TxyxMiii∈==+，},1|{TxyxMiii∈−==−，由线性可分的定义可知，存在超平面}0)(:{=+⋅∈=bxRxHnω和0>ε，使得εω≥+⋅bxi)(，+∈∀Mxi且εω−≤+⋅bxi)(，.−∈∀Mxi而正类点集的凸包中的任意一点x和负类点集的凸包中的任意一点'x可分别表示为∑+==Niiixx1α和∑−==Njjjxx1''β其中0,0≥≥jiβα且∑+==Nii11α，∑−==Njj11β。于是可以得到0))(()(111>=≥+⋅=+⎟⎟⎠⎞⎜⎜⎝⎛⋅=+⋅∑∑∑+++===εαεωααωωNiiNiiiNiiibxbxbx0))'((')'(111<−=−≤+⋅=+⎟⎟⎠⎞⎜⎜⎝⎛⋅=+⋅∑∑∑−−−===εβεωββωωNjjNjjjNjjjbxbxbx由此可见，正负两类点集的凸包位于超平面0)(=+⋅bxω的两侧，故两个凸包相离。②充分性设两类点集+M，−M的凸包相离。因为两个凸包都是闭凸集，且有界，根据凸集强分离定理，可知...
