第4期 李欢，等：支持向量机的多观测样本二分类算法 ·395· 二次规划的对偶问题： 2.2基于SVM的多观测样本二分类 mas-p 由于支持向量机具有结构简单、推广性能好、优 化求解时具有惟一最优解等优点，本文将用SVM的 =1 相关理论来解决多观测样本二分类问题，确定多观 s.t. a≥0，i=1,2,…,n (6) g%0 测样本的类别。根据SVM的原理可知，SVM要解 决的数学问题为 在式(6)所得的结果中，只有少数的α：不等于 min21w2+c}车 零，其对应的样本离最优分类面最近，这些样本被称 s.t.y:(wp(x)+b)≥1-专，i=1,2,,n 为支持向量。上述问题存在惟一最优解，若最优解 5:≥0，i=1,2,…,n 为a,”,则w=∑ayx,b可由式(2)取等号 (7) 时得到，因此，最终的最优分类函数为 而从多观测样本二分类问题的描述可知，二分 f(x)=sg((w)'x+b·)= 类问题中的所有数据只属于2个类别，数据的标签 集为{-1，+1}，设多观测样本集X)的标签为 m(宫a+b) y,则y=-1或y=+1。因此可以通过假设多观测 对于样本集非线性可分的情况，可以先把原始 样本的标签来增加式(7)的约束条件： 空间的样本集通过非线性变换”映射到一个高维 1 min2 IwI2+c∑专 的特征空间，使得样本集在新的空间线性可分，然后 构造最优分类平面。这种非线性变换可以通过引入 st.y:(wp(x）+b)≥1-5，i=1,2,,l 适当的核函数来实现，用k(x:,x)=P(x:)·p() y(w'p(x)+b)≥1，j=l+1,2,…,n 代替线性可分情况下的点积(x,),式(6)中的优 y41=142=…=yn=y 化函数变为 5≥0，i=1,2,…,l Q(a)= 0,ayyk(r,x）/2 (8) =1 可以先假设y=-1,求解得到目标函数值g1。 最终的分类函数为 再假设y=+1,求解得到目标函数值g2。只有当假 fx)=sg(∑ayk(x,x)+b) 设的标签与多观测样本的实际标签相同时，相应得 到的目标函数值才是最优解。因此，可以通过比较 在线性不可分的问题中，SVM还引入了惩罚因 两次得到的目标函数值来确定待测试的多观测样本 子C和松弛变量专，此时最优分类面的求解问题可 的标签。如式(9)所示： 描述为 -1,81>82 (9) min wC y= +1,81≤82 为求解式(8)所述的优化问题，引入拉格朗日 s.t.y(wp(x:)+b)≥1-，i=1,2,,n 函数L: ≥0，i=1,2,…,n 同样地，通过定义拉格朗日函数的方法可以将 (w,b,5,aB)=2Iw2+C:- 原问题转换为凸二次规划的对偶问题： ∑a,[y(w'e(x)+b)-1+]- max∑a:-2,a ayiyk(x:) a i=l 2r右.-2B,[(w'(x)+b)-1](10) s.t. 0≤a:≤C,i=1,2,,n 式中：a:B:J:为Lagrange系数，a:≥0，B,≥0，：≥ 0,5:≥0。要使函数L关于w、b、5:最小化，由极值 存在的必要条件可知，函数L的极值满足下列条件： 对应的最优分类函数为 (aL/aw =0 aL/ab=0 (11) f(x)sgn(aiyk(x.x)+b') aL/aξ：=0二次规划的对偶问题院 皂葬曾 琢 移 灶 蚤 越 员 琢蚤 原 移 灶 蚤袁躁 越 员 琢蚤琢躁 赠蚤赠躁 曾蚤 栽 曾躁 辕 圆 泽援贼援摇 琢蚤 逸 园袁蚤 越 员袁圆袁噎袁灶 移 灶 蚤 越 员 琢蚤赠蚤 越 园          渊远冤 摇 摇 在式渊远冤所得的结果中袁只有少数的 琢蚤 不等于 零袁其对应的样本离最优分类面最近袁这些样本被称 为支持向量遥 上述问题存在惟一最优解袁若最优解 为 琢蚤 鄢 袁则 憎鄢 越 移 灶 蚤 越 员 琢鄢 蚤 赠蚤曾蚤袁 遭鄢 可由式渊圆冤取等号 时得到袁因此袁最终的最优分类函数为 枣渊曾冤 越 泽早灶渊渊憎鄢冤 栽 曾 垣 遭鄢冤 越 泽早灶渊移 灶 蚤 越 员 琢鄢 蚤 赠蚤曾蚤 栽 曾 垣 遭鄢冤 摇 摇 对于样本集非线性可分的情况袁可以先把原始 空间的样本集通过非线性变换 渍 映射到一个高维 的特征空间袁使得样本集在新的空间线性可分袁然后 构造最优分类平面遥 这种非线性变换可以通过引入 适当的核函数来实现袁用 噪渊曾蚤袁曾躁 冤 越 渍渊曾蚤冤窑渍渊曾躁 冤 代替线性可分情况下的点积 渊曾栽 蚤 袁曾躁 冤 袁式渊远冤中的优 化函数变为 匝渊琢冤 越 移 灶 蚤 越 员 琢蚤 原 移 灶 蚤袁躁 越 员 琢蚤琢躁 赠蚤赠躁 噪渊曾蚤袁曾躁 冤 辕 圆 最终的分类函数为 枣渊曾冤 越 泽早灶渊移 灶 蚤 越 员 琢鄢 蚤 赠蚤噪渊曾蚤袁曾冤 垣 遭鄢冤 摇 摇 在线性不可分的问题中袁杂灾酝 还引入了惩罚因 子 悦 和松弛变量 孜 袁此时最优分类面的求解问题可 描述为 皂蚤灶 椰憎椰圆 辕 圆 垣 悦移 灶 蚤 越 员 孜蚤 泽援贼援摇 赠蚤 渊憎栽 渍渊曾蚤冤 垣 遭冤逸员 原 孜蚤袁蚤 越 员袁圆袁援援援袁灶 孜蚤 逸 园袁蚤 越 员袁圆袁噎袁灶        摇 摇 同样地袁通过定义拉格朗日函数的方法可以将 原问题转换为凸二次规划的对偶问题院 皂葬曾 琢 移 灶 蚤 越 员 琢蚤 原 员 圆 移 灶 蚤袁躁 越 员 琢蚤琢躁 赠蚤赠躁 噪渊曾蚤袁曾躁 冤 泽援贼援摇 园 臆 琢蚤 臆 悦袁蚤 越 员袁圆袁援援援袁灶 移 灶 蚤 越 员 琢蚤赠蚤 越 园          对应的最优分类函数为 枣渊曾冤 越 泽早灶渊移 灶 蚤 越 员 琢鄢 蚤 赠蚤噪渊曾蚤袁曾冤 垣 遭鄢冤 圆援圆摇 基于 杂灾酝 的多观测样本二分类 由于支持向量机具有结构简单尧推广性能好尧优 化求解时具有惟一最优解等优点袁本文将用 杂灾酝 的 相关理论来解决多观测样本二分类问题袁确定多观 测样本的类别遥 根据 杂灾酝 的原理可知袁杂灾酝 要解 决的数学问题为 皂蚤灶 员 圆 椰憎椰圆 垣 悦移 灶 蚤 越 员 孜蚤 泽援贼援 赠蚤 渊憎栽 渍渊曾蚤冤 垣 遭冤逸员 原 孜蚤袁蚤 越 员袁圆袁援援援袁灶 孜蚤 逸 园袁蚤 越 员袁圆袁噎袁灶        渊苑冤 摇 摇 而从多观测样本二分类问题的描述可知袁二分 类问题中的所有数据只属于 圆 个类别袁数据的标签 集为   原 员袁 垣 员 袁设多观测样本集 载渊怎冤 的标签为 赠 袁则 赠 越 原 员 或 赠 越 垣 员遥 因此可以通过假设多观测 样本的标签来增加式渊苑冤的约束条件院 皂蚤灶 员 圆 椰憎椰圆 垣 悦移 造 蚤 越 员 孜蚤 泽援贼援摇 赠蚤 渊憎栽 渍渊曾蚤冤 垣 遭冤逸员 原 孜蚤袁蚤 越 员袁圆袁援援援袁造 赠躁 渊憎栽 渍渊曾躁 冤 垣 遭冤 逸 员袁躁 越 造 垣 员袁圆袁援援援袁灶 赠造垣员 越 赠造垣圆 越 噎 越 赠灶 越 赠 孜蚤 逸 园袁蚤 越 员袁圆袁噎袁造            渊愿冤 摇 摇 可以先假设 赠 越 原 员袁求解得到目标函数值 早员 遥 再假设 赠 越 垣 员袁求解得到目标函数值 早圆 遥 只有当假 设的标签与多观测样本的实际标签相同时袁相应得 到的目标函数值才是最优解遥 因此袁可以通过比较 两次得到的目标函数值来确定待测试的多观测样本 的标签遥 如式渊怨冤所示院 赠 赞 越 原 员袁早员 跃 早圆 垣 员袁早员 臆 早圆  渊怨冤 摇 摇 为求解式渊愿冤所述的优化问题袁引入拉格朗日 函数 蕴 院 蕴渊憎袁遭袁孜蚤袁琢蚤袁茁蚤袁则蚤冤 越 员 圆 椰憎椰圆 垣 悦移 造 蚤 越 员 孜蚤 原 移 造 蚤 越 员 琢蚤 咱赠蚤 渊憎栽 渍渊曾蚤冤 垣 遭冤 原 员 垣 孜蚤暂 原 移 造 蚤 越 员 则蚤孜蚤 原 移 灶 蚤 越 造垣员 茁蚤咱赠渊憎栽 渍渊曾蚤冤 垣 遭冤 原 员暂 渊员园冤 式中院 琢蚤尧茁蚤尧则蚤 为 蕴葬早则葬灶早藻 系数袁 琢蚤 逸 园袁茁蚤 逸 园袁则蚤 逸 园袁孜蚤 逸 园遥 要使函数 蕴 关于 憎尧遭尧孜蚤 最小化袁由极值 存在的必要条件可知袁函数 蕴 的极值满足下列条件院 鄣蕴 辕 鄣憎 越 园 鄣蕴 辕 鄣遭 越 园 鄣蕴 辕 鄣孜蚤 越 园       渊员员冤 第 源 期摇摇摇摇摇摇摇摇摇摇摇摇摇摇 李欢袁等院 支持向量机的多观测样本二分类算法 窑猿怨缘窑