《支持向量机在缺失数据样本分类上的应用》由会员分享，可在线阅读，更多相关《支持向量机在缺失数据样本分类上的应用（4页珍藏版）》请在金锄头文库上搜索。
1、 thProceedings of the 25 Chinese Control Conference 7-11 August, 2006, Harbin, Heilongjiang 支持向量机在缺失数据样本分类上的应用 孙玺菁，司守奎，刘超 海军航空工程学院基础部, 烟台 264001 E-mail: 摘 要:在详细论述支持向量机的核心思想和基本算法的基础上, 采用C-SVM算法用于未知样本分类, 特别是对 于缺失数据的未知样本, 先采用序列极小化方法将与输出无关的特征剔除, 对应地在原始训练集中剔除该特征所 对应的数据并重新求解, 否则采用插值法对缺失数据进行估计. 关键词:最优超平面,
2、 拉格朗日对偶, C-支持向量机, 序列极小化方法, 插值 Support Vector Machine and Its Application in the Classification of Missing Data Sun Xi-jing, Si Shou-kui, Liu Chao Department of Basic Science, Naval Aeronautical Engineering Academy, Yantai 264001 E-mail: Abstract: Support vector machine (SVM) is a popular technique
3、for classification. C-SVM is applied in the classification for the unknown samples, especially for the missing data samples. First serial minimization method is used to delete the characters which are independent on the outputs, correspondingly the data for these characters in primitive training sam
4、ples is deleted and the classification function is recomputed. Otherwise the missing data is estimated by interpolation. Key Words: optimization hyperplane, Lagrange dual, C-SVM, serial minimization method, interpolation 经网络后一个新的研究方向，在短短几年内发展迅 速。 1 引言(Introduction) 支持向量机(Sport Vector Machine ,简称SVM)
5、 是基于统计学习理论框架下的一种新的通用机器学 习算法，是对结构化风险最小化归纳原则的近似。 该方法借助于优化方法解决机器学习问题，并且能 够解决以往学习算法中小样本， 过学习等实际难题, 巧妙的解决了算法复杂度与输入向量维数的关系， 并具有很强的泛化性能力。该算法应用核技术，将 输入空间中的非线性问题通过非线性函数映射到高 维特征空间中，在高维空间中构造线性判别函数， 避免了维数灾难的产生。支持向量机算法最终将问 题转化为一个凸规划,从而保证了算法的全局最优 性,避免了局部最优性的问题。在回归分析，目标识 别等方面取得广泛应用，并为工业控制过程中可能 出现的问题提供了可行的有效途径。支持向量
6、机提 出后，就引起国内外学者高度重视，被誉为是继神IEEE Catalog Number: 06EX1310 2 支持向量机的原理(Theory of SVM) 支持向量机的主要思想是找到一个超平面，使 它能够尽可能将两类数据点正确的分开，同时使分 开的两类数据点间距离最远。已知训练样本集为： )( ,),(),(2211ll,y,y,yTxxx?= (1) 其中： x，y，in iRX =1 , 1=Yi, 1? l=。 2.1 线性可分支持向量分类机 (Linear Separable SVM) 当训练集样本为线性可分时，存在着超平面 0)(=+bx，使得 (2) =+=+11)(11)(
7、iiii ybybxx1148其中使成立的称为支持向量，支持向量与超平面之间的间隔为1)(=+bixix1，支持向量间的距离为2。最优超平面即意味着最大化2。于是寻找最优超平面的问题可以转化为如下的二次 规划问题 libyii, 11)(. t . s21min2?=+ x(3) 引入拉格朗日函数如下1： =+=liiiibybL12) 1)(21),(x(4) 其中为拉格朗日乘子。通过对原问题中各变量的偏导置零可得： +=RlT 1),(?00011=iliiliiiiybLyLx(5) 带入拉格朗日函数化为原问题的拉格朗日对偶问题 如下： ,l,iyyyiliiiliililjjijiji
8、?1, 0, 0. t . s)(21max1111=+=xx (6) 求解上述最优化问题，得到最优解，计算 T* 1*),(l?=(7) =liii* iy1*x由KKT互补条件 0)(1 (*=+byiiix (8) 可得， 只有当为支持向量的时候， 对应的才为正，否则皆为零。选择的一个正分量，并以此计算 ix* i* j(9) =liji* iij*yyb1)(xx于是构造分类超平面， 并由此求得 分类函数 0)(*=+bx)(sgn)(*1byfliii* i+= =xxx (10) 从而对未知样本进行分类。 2.2 线性支持向量分类机(Soft-Margin SVM) 对于上述样本为
9、线性可分的情况，是硬性的使 训练样本关于分类超平面的几何间隔为正且最大 硬间隔。如果允许存在不满足约束条件 1)(+byiix 的样本点后，仍然能继续使用超平面进行划分，则 要对间隔进行“软化”软间隔，该方法用以解决 样本为线性不可分的分类问题。软化的方法是通过 引入松弛变量： lii, 1, 0?= 来得到“软化”的约束条件： libyiii, 11)(?=+x (11) 当i充分大时，样本点总是满足上述的约束条件，但是也要设法避免i取太大的值，为此要在目标函数中对它进行惩罚，得到如下的二次规划问题： libxyCiiiilii, 1, 01)(s.t.21min12?=+ =(12) 其中
10、是一个惩罚参数。其拉格朗日函数如下： 0C=+=liiiliiiiiliibyCbL1112)1)(21),(x,(13) 其中0i且有： 0000011=iiiliiliiiiCLybLyLx(14) 带入拉格朗日函数，得到原问题的对偶问题如下： =+liililjjijijixxyy111)(21max (15) 1149(16) ,l,iCyiliii?1,0, 0. t . s1 = = 求得最优解，计算 T* 1*),(l?= =liii* iy1*x 由互补松弛条件 0)1)(*=+iiiibyx 可得，原问题中约束等号成立的时候，否则为零。选择的一个正分量，并以此计算 ), 0(
11、*Ci* j(17) =liji* iij*yyb1)(xx于是构造分类超平面， 并由此求得 分类函数 0)(*=+bx(18) )(sgn)(*1byfliii* i+= =xxx从而对未知样本进行分类。可见当时，就转 化为硬间隔，即线性可分的情况。 =C2.3 可分支持向量分类机 (Separable SVM) 线性支持向量分类机给出了求解线性不可分问 题的一个途径，在此将给出该类问题求解的另一途 径。通过引进从输入空间X到另一个高维的Hilbert空间H的变换将原输入空间)(xx?nRX的 训练集： (19) )( ,),(),(2211ll,yx,yx,yxT?=转化为Hilbert空
12、间H中的新的训练集： ),( ,),),(),),()()(),(22112211llll yxyxyx,yx,yx,yxT=?(20) 然后在空间H中求得超平面0)(=+bx，这个超平面可以硬性划分训练集T，于是原问题转化 为如下的二次规划问题： libyii, 11)(. t . s21min2?=+x(21) 采用核函数K满足 )()(),(jijiKxxxx= (22) 将避免在高维特征空间进行复杂的运算，不同的核 函数形成不同的算法，主要的核函数有如下几类： 212222)(cos21 (21),()(),(S),( 1)(),()(),(nnkjkikjijijijijiq jij
13、ijijiRxqxxqqxxKcxxvtanhxxKxxexpxxKxxxxKxxxxK+=+=+= =傅立叶核函数形内核函数径向基核函数多项式核函数线性内核函数(23) 同样可以得到其拉格朗日对偶问题如下： =+liililjjijijixxKyy111)(21max (24) ,l,iyiliii?1, 0, 0. t . s1 = = 若K是正定核，则对偶问题是一个凸二次规划问 题，必定有解。求解上述最优化问题，得到最优解，选择的一个正分量，并以此计算 T* 1*),(l?=* j(25) =liji* iij*Kyyb1)(xx构造分类函数 (26) )(sgn)(*1bKyflij*
14、 ii+= =xxx从而对未知样本进行分类。在H空间这种间隔是硬 性的。 2.4 C-支持向量分类机 (C-SVM) 当映射到高维H空间的训练集不能被硬性分 划时，需要对约束条件进行软化。结合2.2和2.3中 所述，得到如下的模型 ,l,iCyKyyiliiiliililjjijiji?1,0, 0. t . s)(21max1111=+=xx (27)得到最优解， 选择的一个正分量，计算 T* 1*),(l?=* j1150(28) =liji* iij*Kyyb1)(xx构造分类函数 (29) ) )(sgn)(*1bKyflij* ii+= =xxx从而对未知样本进行分类。 3 C-SV
15、M在分类上的应用 (The Application of C-SVM in Classification) 3.1 C-SVM用于数据完全的样本分类(The Applica- tion in Sample Classification of Complete data) 某银行欲发行一种可以透支的信誉卡，但是银 行为了减少自身的投资风险，需要每位申请者提供 自身的背景资料(15项)供银行参考，银行根据这些 资料将申请者分为信誉良好和信誉不好两类，并且 批准信誉良好者的申请。 对于600个已知数据完全的 样本，前550个样本作为原始训练集，后50个样本作 为测试集，对于训练集采用径向基核函数，取参数 3=，采用 C-SVM算法
