资源描述：
《31、支持向量机(数学建模)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第三十一章支持向量机支持向量机是数据挖掘中的一项新技术，是借助于最优化方法来解决机器学习问题的新工具，最初由V.Vapnik等人提出，近几年来在其理论研究和算法实现等方面都取得了很大的进展，开始成为克服“维数灾难”和过学习等困难的强有力的手段，它的理论基础和实现途径的基本框架都已形成。§1支持向量分类机的基本原理根据给定的训练集lT={(x,y),(x,y),L,(x,y)}∈(X×Y)，1122lln其中x∈X=R，X称为输入空间，输入空间中的每一个点x由n个属性特征组成，iiny∈Y={−1,1},i=1,L,l。寻找R上的一个实值函数g(x)，以便用分类函数
2、if(x)=sgn(g(x)),推断任意一个模式x相对应的y值的问题为分类问题。1.1线性可分支持向量分类机n考虑训练集T，若∃ω∈R，b∈R和正数ε，使得对所有使y=1的下标i有i(ω⋅x)+b≥ε（这里(ω⋅x)表示向量ω和x的内积），而对所有使y=−1的下标i有iiii(ω⋅x)+b≤−ε，则称训练集T线性可分，称相应的分类问题是线性可分的。i+−记两类样本集分别为M={x
3、y=1,x∈T}，M={x
4、y=−1,x∈T}。定义iiiiii++M的凸包conv(M)为⎧N++N⎫+++conv(M)=⎨x=∑∑λjxj
5、λj=1,λj≥0,j=1,L,N;xj
6、∈M⎬,⎩j==11j⎭−−M的凸包conv(M)为⎧N−−N⎫−−−conv(M)=⎨x=∑∑λjxj
7、λj=1,λj≥0,j=1,L,N;xj∈M⎬.⎩j==11j⎭其中N表示+1类样本集中样本点的个数，N表示−1类样本集中样本点的个数，定+−理1给出了训练集T线性可分与两类样本集凸包之间的关系。+−定理1训练集T线性可分的充要条件是，T的两类样本集M和M的凸包相离。如下图所示图1训练集T线性可分时两类样本点集的凸包证明：①必要性-761-+−若T是线性可分的，M={x
8、y=1,x∈T}，M={x
9、y=−1,x∈T}，由线iiiiiin性可分的定义可知，存在超
10、平面H={x∈R:(ω⋅x)+b=0}和ε>0，使得+−(ω⋅x)+b≥ε，∀x∈M且(ω⋅x)+b≤−ε，∀x∈M.iiii而正类点集的凸包中的任意一点x和负类点集的凸包中的任意一点x'可分别表示为N+N−x=∑αixi和x'=∑βjx'ji=1j=1N+N−其中αi≥0,βj≥0且∑αi=1，∑βj=1。i=1j=1于是可以得到⎛N+⎞N+N+(ω⋅x)+b=⎜⎜ω⋅∑αixi⎟⎟+b=∑αi((ω⋅xi)+b)≥ε∑αi=ε>0⎝i=1⎠i=1i=1⎛N−⎞N−N−(ω⋅x')+b=⎜⎜ω⋅∑βjx'j⎟⎟+b=∑βj((ω⋅x'j)+b)≤−ε∑βj=−ε
11、<0⎝j=1⎠j=1j=1由此可见，正负两类点集的凸包位于超平面(ω⋅x)+b=0的两侧，故两个凸包相离。②充分性+−设两类点集M，M的凸包相离。因为两个凸包都是闭凸集，且有界，根据凸集n强分离定理，可知存在一个超平面H={x∈R:(ω⋅x)+b=0}强分离这两个凸包，+−即存在正数ε>0，使得对M，M的凸包中的任意点x和x'分别有(ω⋅x)+b≥ε(ω⋅x')+b≤−ε+−显然特别的，对于任意的x∈M，有(ω⋅x)+b≥ε，对于任意的x∈M，有iii(ω⋅x)+b≤−ε，由训练集线性可分的定义可知T是线性可分的。in由于空间R中超平面都可以写为(ω⋅x)+b=0
12、的形式，参数(ω,b)乘以任意一个非零常数后得到的是同一个超平面，定义满足条件⎧⎪yi((ω⋅xi)+b)≥0,i=1,L,l⎨min(ω⋅x)+b=1⎪⎩i=1,L,li的超平面为规范超平面。定理2当训练集样本为线性可分时，存在唯一的规范超平面(ω⋅x)+b=0，使得⎧(ω⋅xi)+b≥1yi=1;⎨（1）(ω⋅x)+b≤−1y=−1.⎩ii证明：规范超平面的存在性是显然的，下证其唯一性。假设其规范超平面有两个：(ω'⋅x)+b′=0和(ω"⋅x)+b′′=0。由于规范超平面满足条件-762-⎧⎪yi((ω⋅xi)+b)≥0,i=1,L,l,⎨min(ω⋅x)+
13、b=1.⎪⎩i=1,L,li由第二个条件可知ω'=ω"，b′=b′′，或者ω'=−ω"，b′=−b′′.第一个条件说明ω'=−ω"，b′=−b′′不可能成立，故唯一性得证。式（1）中满足(ω⋅x)+b=±1成立的x称为普通支持向量，对于线性可分的情况ii来说，只有它们在建立分类超平面的时候起到了作用，普通支持向量通常只占样本集很小的一部分，故而也说明SVM具有稀疏性。对于y=1类的样本点，其与规范超平面i的间隔为(ω⋅x)+b1imin=，yi=1ωω对于y=−1类的样本点，其与规范超平面的间隔为i(ω⋅x)+b1imin=，yi=−1ωω22则普通支持向量间的间
14、隔为。最优
