工程科学学报，第37卷，第3期：385-389,2015年3月 Chinese Journal of Engineering,Vol.37,No.3:385-389,March 2015 DOI:10.13374/j.issn2095-9389.2015.03.019:http://journals.ustb.edu.cn 一个广义三次样条光滑半监督支持向量机 张晓丹四，马菁改 北京科技大学数理学院，北京100083 ☒通信作者，Email:bkdzxd(@163.com 摘要研究半监督支持向量机分类优化模型的非光滑问题.建立了光滑半监督支持向量机模型，采用广义三弯矩法导出 零点二阶光滑的广义三次样条函数，并以此逼近半监督支持向量机优化中的非光滑部分.构造出基于上述样条函数的具有 一阶光滑的半监督支持向量机，从而可以用优化中的光滑算法来求解该模型.分析了广义三次样条函数逼近对称铰链损失 函数的逼近精度，证明了新模型的收敛性.数值实验显示新模型有较好的分类效果 关键词支持向量机：三次样条函数：分类：光滑 分类号TP181 A general cubic spline smooth semi-supervised support vector machine ZHANG Xiao-dan,MA Jing-gai School of Mathematics and Physics,University of Science and Technology Beijing,Beijing 100083,China Corresponding author,E-mail:bkdzxd@163.com ABSTRACT This article is focused on the non-smooth problem of the semi-supervised support vector machine optimization model.A smooth semi-supervised support vector machine model was established.A general cubic spline function with 2 times differentiable at zero point was deduced by a general three-moment method and was used to approach the non-smooth part in the semi-supervised sup- port vector machine.A new smooth semi-supervised support vector with I time differentiable based on the general cubic spline function was constructed,and thus a lot of fast optimization algorithms could be applied to solve the smooth semi-supervised vector machine model.The approximation accuracy of the general cubic spline function to the symmetric hinge loss function was analyzed,and the convergence accuracy of the new model was proved.Numerical experiments show that the new model has a better classification result. KEY WORDS support vector machines:cubic spline function:classification:smoothing 为了得到精确的分类器，支持向量机-四训练过 光滑的规划问题.20O5年，Chapelle和Zien建立了 程需要大量的标记数据.然而要获得大量的标记样 一个无约束的光滑半监督支持向量机模型，采用光滑 本，需要耗用大量的人力物力.半监督支持向量机 的高斯函数来逼近无标记样本的对称铰链损失函数. (semi-supervised support vector machine,SVM) 光滑函数的应用使原来的不可微模型变成可微模型， 以同时利用标记样本和无标记样本的信息，当有小部 从而可以采用快速的优化算法求解，大大降低了半监 分标记样本和大量无标记样本时，半监督支持向量机 督支持向量机的计算复杂度.本文应用广义三弯矩法 亦能够提供给我们一个性能良好的分类器网.由于半 构造广义三次样条函数来逼近对称铰链损失函数，建 监督支持向量机的实用性，近年来受到了广泛的关注. 立了光滑半监督支持向量机模型.数值计算显示广义 半监督支持向量机把间隔最大化原则应用到标记 三次样条函数比高斯函数能更好地逼近对称铰链损失 样本和无标记样本中，从而使半监督支量机是一个非 函数，且新模型有更好的分类效果. 收稿日期：2013-12-30 基金项目：中央高校基本科研业务费资助项目(FRF-BR-12O21)
工程科学学报，第 37 卷，第 3 期: 385--389，2015 年 3 月 Chinese Journal of Engineering，Vol． 37，No． 3: 385--389，March 2015 DOI: 10． 13374 /j． issn2095--9389． 2015． 03． 019; http: / /journals． ustb． edu． cn 一个广义三次样条光滑半监督支持向量机 张晓丹，马菁改 北京科技大学数理学院，北京 100083 通信作者，E-mail: bkdzxd@ 163． com 摘 要 研究半监督支持向量机分类优化模型的非光滑问题． 建立了光滑半监督支持向量机模型，采用广义三弯矩法导出 零点二阶光滑的广义三次样条函数，并以此逼近半监督支持向量机优化中的非光滑部分． 构造出基于上述样条函数的具有 一阶光滑的半监督支持向量机，从而可以用优化中的光滑算法来求解该模型． 分析了广义三次样条函数逼近对称铰链损失 函数的逼近精度，证明了新模型的收敛性． 数值实验显示新模型有较好的分类效果． 关键词 支持向量机; 三次样条函数; 分类; 光滑 分类号 TP181 A general cubic spline smooth semi-supervised support vector machine ZHANG Xiao-dan ，MA Jing-gai School of Mathematics and Physics，University of Science and Technology Beijing，Beijing 100083，China Corresponding author，E-mail: bkdzxd@ 163． com ABSTＲACT This article is focused on the non-smooth problem of the semi-supervised support vector machine optimization model． A smooth semi-supervised support vector machine model was established． A general cubic spline function with 2 times differentiable at zero point was deduced by a general three-moment method and was used to approach the non-smooth part in the semi-supervised support vector machine． A new smooth semi-supervised support vector with 1 time differentiable based on the general cubic spline function was constructed，and thus a lot of fast optimization algorithms could be applied to solve the smooth semi-supervised vector machine model． The approximation accuracy of the general cubic spline function to the symmetric hinge loss function was analyzed，and the convergence accuracy of the new model was proved． Numerical experiments show that the new model has a better classification result． KEY WOＲDS support vector machines; cubic spline function; classification; smoothing 收稿日期: 2013--12--30 基金项目: 中央高校基本科研业务费资助项目( FＲF--BＲ--12--021) 为了得到精确的分类器，支持向量机［1 － 2］训练过 程需要大量的标记数据． 然而要获得大量的标记样 本，需要耗用大量的人力物力． 半监督支持向 量 机 ( semi-supervised support vector machine，S3 VM) ［3 － 5］可 以同时利用标记样本和无标记样本的信息，当有小部 分标记样本和大量无标记样本时，半监督支持向量机 亦能够提供给我们一个性能良好的分类器［6］． 由于半 监督支持向量机的实用性，近年来受到了广泛的关注． 半监督支持向量机把间隔最大化原则应用到标记 样本和无标记样本中，从而使半监督支量机是一个非 光滑的规划问题． 2005 年，Chapelle 和 Zien［7］建立了 一个无约束的光滑半监督支持向量机模型，采用光滑 的高斯函数来逼近无标记样本的对称铰链损失函数． 光滑函数的应用使原来的不可微模型变成可微模型， 从而可以采用快速的优化算法求解，大大降低了半监 督支持向量机的计算复杂度． 本文应用广义三弯矩法 构造广义三次样条函数来逼近对称铰链损失函数，建 立了光滑半监督支持向量机模型． 数值计算显示广义 三次样条函数比高斯函数能更好地逼近对称铰链损失 函数，且新模型有更好的分类效果．
·386· 工程科学学报，第37卷，第3期 1光滑半监督支持向量机模型 2g2盟-1ul+ 考虑两分类问题圆，训练集包括m个标号样本 乞IAD(aw+e,B)I:+亏VIBa+,b)I经 {(y)}和1个未标号样本(x}其中，x,∈ (6) R”为行向量，y:∈{1，-1}.将上述m个标记样本x: 其中，∫(x)为逼近对称铰链损失函数的任一光滑函数. (i=1,2,…,m)用矩阵Amxn表示.xx2,,xm被分 本文研究样条函数逼近对称铰链损失函数的光滑半监 为A和Aˉ两类.若x:属于类A,记为1：若x:属于 督支持向量机. 类A”,记为-1.这样，可以用一个m×m的对角阵D 表示分类情况，D的对角元素为1或-1.对1个未标 2样条铰链光滑函数的构造与分析 记样本点，用矩阵Bxn表示.记e,(i=1,2)为分量全 2.1广义三次样条函数的构造 为1的列向量，e,∈R",e2∈R',w∈R",b∈R研究如 定义1设A(1x1)为对称铰链损失函数，x。= 下半监督支持向量机模型 -1/k,x1=0,x2=1/k是节点，k>1,y1>0,m,n∈Z,, Tmin2∥wli+cei+ce5 则函数s(x,)定义如下： (1) s.t.D(Aw+e1b)≥e1-51,51≥0； (x,), -1/h≤x<0: 1Bw+e2bl≥e2-52,52≥0. s(x,k)= s(x,k),0≤x≤1/k; 这里，c和c是错分惩罚参数，专，和52为松弛向 A(1xl),1xl>1/k. 量，专1∈R,专2∈R.令：为如下形式： 这里，s(x,k)和s,(x,k)分别是定义在区间[-1/，0] 专1=A(D(Aa+e,b)),专2=A(IBw+e2b1).(2) 和D,1/们上的n次多项式.若s(x,k)满足如下条件： 式中，A(t)=max(0,1-t)为铰链损失函数，A(1tl) (1）s(xo,k)=0,d=2,3,…,mk>0,s(xoh)=1, =max(O,1-I)为对称铰链损失函数.若u∈R”, s(x。,）=1-1/k 则定义A(u)=(4(u,),A(2),…,A()).将式 (2)s0(x2k)=0,d=2,3,,m:k>0,s(x2,k)= (1)目标函数中专(i=1,2)用式(2)代替，得到无约束 -1,s(x2,k)=1-1/k. 优化问题： (3)s00(x,+0,k)=s0(x1-0,k),d=1,2,…, 时IwI+eAD(aw+eb)+ m,5(x1+0,k)=s1(x1-0,k)=y1 则称s(x,k)为逼近对称铰链损失函数(IxI),满足 c'e2A(IBo+e2bl). (3) 零点m阶光滑条件的广义n次样条函数. 由于铰链损失函数和对称铰链损失函数均为不可微， 定理1设k>1,x=-1/k,x,=0,x2=1/k是节 无约束优化模型(3)是非光滑规划问题. 点，则存在唯一一个逼近对称铰链损失函数A(1x), 用光滑函数A2(t）=max(0,1-)2来逼近铰链 满足零点二阶光滑条件的广义三次样条函数，形式 损失函数，用高斯函数T(t)=er来逼近式(3)中对 如下： 称较链损失函数，可得光滑半监督支持向量机： r2Ix3/3-kx2-1/(3k)+1,1xl≤1/k; 肿2Io+分IA(D(aw+e,b)I;+ s(x,k)= LA(Ixl), Ixl >1/k. (7) ce;r(Bo+eb) (4) 证明：采用广义三弯矩法@证明此结论 这里，T(w）=(T(u,),T(u2),…,T(un))T,u∈R". 设函数s(x,k)为满足零点二阶光滑条件，逼近对 本文对模型(3)进行修正，得到如下半监督支持 向量机模型： 称铰链损失函数的广义三次样条函数.由于s(x,k)在 区间[-1k,0],0,1/]上是三次多项式，故s(x, min+A(D(Ao+e6))+ k)在每个区间上是常数.设在区间[-1/k,0]上的表 合A(+ebl)I住 达式为s。(x,)=m。,对该式逐次积分可得： (5) so (x,k)mox +a' 这种修正对原问题的影响很小，但该修正却能避开铰 链损失函数A(x)在点1的不可微性(A2(x)= s6(x,k)= +a+a: ‖A(x)‖)以及避开对称铰链损失函数A(Ix1)在两 点-1和1的不可微性.基于式(5)，建立如下光滑半 (,制=+22+a+a 监督支持向量机： 根据在点x。处的二阶光滑性，可解得：
工程科学学报，第 37 卷，第 3 期 1 光滑半监督支持向量机模型 考虑两分类问题［8］，训练集包括 m 个标号样本 { ( xi，yi ) } m i = 1和 l 个未标号样本{ xi} m + l i = m + 1 ． 其中，xi ∈ Ｒn 为行向量，yi∈{ 1，－ 1} ． 将上述 m 个标记样本 xi ( i = 1，2，…，m) 用矩阵 Am × n表示． x1，x2，…，xm 被分 为 A + 和 A － 两类． 若 xi 属于类 A + ，记为 1; 若 xi 属于 类 A － ，记为 － 1． 这样，可以用一个 m × m 的对角阵 D 表示分类情况，D 的对角元素为 1 或 － 1． 对 l 个未标 记样本点，用矩阵 Bl × n表示． 记 ei ( i = 1，2) 为分量全 为 1 的列向量，e1∈Ｒm，e2∈Ｒl ，ω∈Ｒn ，b∈Ｒ． 研究如 下半监督支持向量机模型 min ω，b 1 2 ‖ω‖2 2 + ceT 1 ξ1 + c * eT 2 ξ2 ． s． t． D( Aω + e1 b) ≥e1 － ξ1，ξ1≥0; | Bω + e2 b | ≥e2 － ξ2，ξ2≥0 { ． ( 1) 这里，c 和 c * 是错分惩罚参数，ξ1 和 ξ2 为松弛向 量，ξ1∈Ｒm，ξ2∈Ｒl ． 令 ξi 为如下形式: ξ1 = Λ( D( Aω + e1 b) ) ，ξ2 = Λ( | Bω + e2 b | ) ． ( 2) 式中，Λ( t) = max ( 0，1 － t) 为铰链损失函数，Λ( | t | ) = max ( 0，1 － | t | ) ［9］为对称铰链损失函数． 若 u∈Ｒn ， 则定 义 Λ ( u) = ( Λ( u1 ) ，Λ( u2 ) ，…，Λ( un ) ) T ． 将式 ( 1) 目标函数中 ξi ( i = 1，2) 用式( 2) 代替，得到无约束 优化问题: min ω，b 1 2 ‖ω‖2 2 + ceT 1Λ( D( Aω + e1 b) ) + c * eT 2Λ( | Bω + e2 b | ) ． ( 3) 由于铰链损失函数和对称铰链损失函数均为不可微， 无约束优化模型( 3) 是非光滑规划问题． 用光滑函数 Λ2 ( t) = max ( 0，1 － t) 2 来逼近铰链 损失函数，用高斯函数 Γ( t) = e － 3t 2 来逼近式( 3) 中对 称铰链损失函数，可得光滑半监督支持向量机: min ω，b 1 2 ‖ω‖2 2 + c 2 ‖Λ( D( Aω + e1 b) ) ‖2 2 + c * eT 2 Γ( Bω + e2 b) ． ( 4) 这里，Γ( u) = ( Γ( u1 ) ，Γ( u2 ) ，…，Γ( un ) ) T ，u∈Ｒn ． 本文对模型( 3) 进行修正，得到如下半监督支持 向量机模型: min ω，b 1 2 ‖ω‖2 2 + c 2 ‖Λ( D( Aω + e1 b) ) ‖2 2 + c * 2 ‖Λ( | Bω + e2 b | ) ‖2 2 ． ( 5) 这种修正对原问题的影响很小，但该修正却能避开铰 链损 失 函 数 Λ ( x) 在 点 1 的 不 可 微 性 ( Λ2 ( x ) = ‖Λ( x) ‖2 2 ) 以及避开对称铰链损失函数 Λ( | x | ) 在两 点 － 1 和 1 的不可微性． 基于式( 5) ，建立如下光滑半 监督支持向量机: φ( ω，b) ( ωT ，b) ∈Ｒn + 1 = min ( ωT ，b) ∈Ｒn + 1 1 2 ‖ω‖2 2 + c 2 ‖Λ( D( Aω + e1 b) ) ‖2 2 + c * 2 ‖f( | Bω + e2 b | ) ‖2 2 ． ( 6) 其中，f( x) 为逼近对称铰链损失函数的任一光滑函数． 本文研究样条函数逼近对称铰链损失函数的光滑半监 督支持向量机． 2 样条铰链光滑函数的构造与分析 2. 1 广义三次样条函数的构造 定义 1 设 Λ( | x | ) 为对称铰链损失函数，x0 = － 1 / k，x1 = 0，x2 = 1 / k 是节点，k ＞ 1，y1 ＞ 0，m，n∈Z + ， 则函数 s( x，k) 定义如下: s( x，k) = s0 ( x，k) ， － 1 / k≤x ＜ 0; s1 ( x，k) ， 0≤x≤1 / k; Λ( | x | ) ， | x | ＞ 1 { / k． 这里，s0 ( x，k) 和 s1 ( x，k) 分别是定义在区间［－ 1 / k，0］ 和［0，1 / k］上的 n 次多项式． 若 s( x，k) 满足如下条件: ( 1) s ( d) ( x0，k) = 0，d = 2，3，…，m; k ＞ 0，s'( x0，k) = 1， s( x0，k) = 1 － 1 / k． ( 2) s ( d) ( x2，k) = 0，d = 2，3，…，m; k ＞ 0，s'( x2，k) = － 1，s( x2，k) = 1 － 1 / k． ( 3) s ( d) 0 ( x1 + 0，k) = s ( d) 1 ( x1 － 0，k) ，d = 1，2，…， m，s0 ( x1 + 0，k) = s1 ( x1 － 0，k) = y1 ． 则称 s( x，k) 为逼近对称铰链损失函数 Λ( | x | ) ，满足 零点 m 阶光滑条件的广义 n 次样条函数． 定理 1 设 k ＞ 1，x0 = － 1 / k，x1 = 0，x2 = 1 / k 是节 点，则存在唯一一个逼近对称铰链损失函数 Λ( | x | ) ， 满足零点二阶光滑条件的广义三次样条函数，形式 如下: s( x，k) = k 2 | x | 3 /3 － kx2 － 1 /( 3k) + 1， | x | ≤1 / k; {Λ( | x | ) ， | x | ＞ 1 / k． ( 7) 证明: 采用广义三弯矩法［10］证明此结论． 设函数 s( x，k) 为满足零点二阶光滑条件，逼近对 称铰链损失函数的广义三次样条函数． 由于 s( x，k) 在 区间［－ 1 / k，0］，［0，1 / k］上是三次多项式，故 s ( 3) ( x， k) 在每个区间上是常数． 设在区间［－ 1 / k，0］上的表 达式为 s ( 3) 0 ( x，k) = m0，对该式逐次积分可得: s″0 ( x，k) = m0 x + a1， s'0 ( x，k) = m0 2 x 2 + a1 x + a2， s0 ( x，k) = m0 3! x 3 + a1 2 x 2 + a2 x + a3 ． 根据在点 x0 处的二阶光滑性，可解得: · 683 ·
张晓丹等：一个广义三次样条光滑半监督支持向量机 ·387· a停1+是1+ mo 6k3 (2)0≤N(1x)-(x,≤(2-） 同理，在区间D,1/们上，设s(x,k)=m,对该 证明：(1)当x≥1/k和x≤-1/k时，A(1x1)- 式逐次积分，有 s(x,)=0,结论显然成立.当x∈（-1/，0)时，s(x, s"(x,k)=m1x+b1, k)=-2x33-kx2-1/(3k)+1,s(x,k)=1- i(x,月=2+6x+, (x+1)2≥0，s(x,k)单调增，故s(x,k)≥s(-1/, k)=1-1/k≥0.其次，令A(x,k)=A(IxI)-s(x,k), ,-+号++ (x,k)=kx+x+13k.(x,k)=kx+ 2kx+1=(kx+1)2≥0，A(x,)单调增，在x=-1/k处 根据在点x2处的光滑条件，可以求得： 取最小值入（-1/k,k)=0,所以入(x,k)≥0，即0≤ 6=受么-1+贤么-10 s(x,k)≤A(Ixl). 当xe(0,1/k)时，s(x,k)=2x3B-x2-1/3k+ 因此，s(x,)在[-1/k,1/们上是带有参数m。和 1,易证s(x,k)单调递减，故s(x,k)≥s(1/k,k)=1- m,的分段三次多项式，应用点x1处的光滑条件，可得 1/k≥0.其次，A(x,)=-k2x33+kx2-x+1/(3k), 出如下矩阵方程： A(x,)单调减，在x=1/k处取最小值A(1/,k)=0, e-1 所以入(x,k)≥0，即0≤s(x,k)≤A(Ix1). (2)当x≥1/k和x≤-1/k时，结论显然成立.当 因为系数矩阵是非奇异的，所以矩阵方程有唯一解： x∈（-1/k,0)时，由(1)，A(x,k)单调增，在x=0处取 最大值为1/3k,因此有0≤A(1x1)-s(x,k)≤1/3k. m=-2k2,m1=2k2. 又0≤A(Ixl)+s(x,k)≤2-1/3k,所以0≤A2(1x1)- 最后可求得唯一一个在[-1k,1/们上具有零点二阶 光滑性的广义三次样条对称铰链损失逼近函数： (,)≤(2-)结论成立 类似可证，在区间(0,1/)上，0≤42(1x)-s2(x, s(x,k)= 「-kx23/3-2-1/(3k)+1,-1/k≤x≤0： 12xB-kx2-1/(3k)+1,0<x≤1/k. )≤(2-)成立 从图1中可以看出，随着k的加大，广义三次样条 函数逐步逼近对称铰链损失函数，逼近误差远小于高 3 模型的收敛性分析 斯函数的逼近误差 定理3设A∈Rmx,B∈Rx",x∈R”,7∈R", 1.00 对称铰链 u∈R,c,c∈R,DER"x"是对角阵，D的对角元素为 高斯函数一 损失函数 1或-1.实函数定义如下： 0.95 h(田)=2Ix:+号IA(D(Ax+n)I匠+ 米 (8) 0.90 米 合A(+aDIi g,A=1x径+分IA(D(Ax+n)I+ 0.85 (9) 广义三次样条函数=10 合I:(r+r,I店 广义三次样条函数-20 其中，s(x,),k>1由(7)式定义.则： -0.1 0.1 0.2 (1)优化问题minh(x)存在最优解x,ming(x,k) 图1不同光滑函数与对称较链损失函数的逼近效果 存在最优解x,并且limh()=h(d). Fig.1 Approximation effect of different smooth functions and the (2)设优化问题mih(x)的最优解集合为U,则 symmetry hinge loss function {F}存在的收敛子列{F}满足Iimr=x,这里x。∈ 2.2样条铰链光滑函数逼近精度分析 U 定理2设x∈R,k>1,A(Ix|)是对称铰链损失 证明：(1)定义相应的水平集为L,(h(x)={xlx∈ 函数，s(x,)是广义三次样条函数，则 R",h(x)≤. (1)0≤s(x,k)≤A(1xl): L,（g(x,k))={xIxER",g(x,k)≤.由于0≤
张晓丹等: 一个广义三次样条光滑半监督支持向量机 a1 = m0 k ，a2 = 1 + m0 2k 2，a3 = 1 + m0 6k 3 ． 同理，在区间［0，1 / k］上，设 s ( 3) 1 ( x，k) = m1，对该 式逐次积分，有 s″1 ( x，k) = m1 x + b1， s'1 ( x，k) = m1 2 x 2 + b1 x + b2， s1 ( x，k) = m1 3! x 3 + b1 2 x 2 + b2 x + b3 ． 根据在点 x2 处的光滑条件，可以求得: b1 = － m1 k ，b2 = － 1 + m1 2k 2，b3 = 1 － m1 6k 3 ． 因此，s( x，k) 在［－ 1 / k，1 / k］上是带有参数 m0 和 m1 的分段三次多项式，应用点 x1 处的光滑条件，可得 出如下矩阵方程: 1 1 1 /2k 2 － 1 /2k [ 2 ] m0 [ m ] 1 = 0 [ ] － 2 ． 因为系数矩阵是非奇异的，所以矩阵方程有唯一解: m0 = － 2k 2 ，m1 = 2k 2 ． 最后可求得唯一一个在［－ 1 / k，1 / k］上具有零点二阶 光滑性的广义三次样条对称铰链损失逼近函数: s( x，k) = － k 2 x 3 /3 － kx2 － 1/( 3k) + 1， － 1/ k≤x≤0; k 2 x 3 /3 － kx2 { － 1/( 3k) + 1， 0 ＜ x≤1/ k． 从图 1 中可以看出，随着 k 的加大，广义三次样条 函数逐步逼近对称铰链损失函数，逼近误差远小于高 斯函数的逼近误差． 图 1 不同光滑函数与对称铰链损失函数的逼近效果 Fig． 1 Approximation effect of different smooth functions and the symmetry hinge loss function 2. 2 样条铰链光滑函数逼近精度分析 定理 2 设 x∈Ｒ，k ＞ 1，Λ( | x | ) 是对称铰链损失 函数，s( x，k) 是广义三次样条函数，则 ( 1) 0≤s( x，k) ≤Λ( | x | ) ; ( 2) 0≤Λ2 ( | x | ) － s 2 ( x，k) ≤ 1 3 ( k 2 － 1 3 ) k ． 证明: ( 1) 当 x≥1 / k 和 x≤ － 1 / k 时，Λ( | x | ) － s( x，k) = 0，结论显然成立． 当 x∈( － 1 / k，0) 时，s( x， k) = － k 2 x 3 /3 － kx2 － 1 /( 3k ) + 1，s' ( x，k ) = 1 － ( kx + 1) 2 ≥0，s( x，k) 单调增，故 s( x，k) ≥s( － 1 / k， k) = 1 － 1 / k≥0． 其次，令 λ( x，k) = Λ( | x | ) － s( x，k) ， 则 λ( x，k) = k 2 x 3 /3 + kx2 + x + 1 /3k． λ'( x，k) = k 2 x 2 + 2kx + 1 = ( kx + 1) 2 ≥0，λ( x，k) 单调增，在 x = － 1 / k 处 取最小值 λ( － 1 / k，k) = 0，所以 λ( x，k) ≥0，即 0≤ s( x，k) ≤Λ( | x | ) ． 当 x∈( 0，1 / k) 时，s( x，k) = k 2 x 3 /3 － kx2 － 1 /3k + 1，易证 s( x，k) 单调递减，故 s( x，k) ≥s( 1 / k，k) = 1 － 1 / k≥0． 其次，λ( x，k) = － k 2 x 3 /3 + kx2 － x + 1 /( 3k) ， λ( x，k) 单调减，在 x = 1 / k 处取最小值 λ( 1 / k，k) = 0， 所以 λ( x，k) ≥0，即 0≤s( x，k) ≤Λ( | x | ) ． ( 2) 当 x≥1 / k 和 x≤ － 1 / k 时，结论显然成立． 当 x∈( － 1 / k，0) 时，由( 1) ，λ( x，k) 单调增，在 x = 0 处取 最大值为 1 /3k，因此有 0≤Λ( | x | ) － s( x，k) ≤1 /3k． 又0≤Λ( |x | ) + s( x，k) ≤2 － 1/3k，所以 0≤Λ2 ( | x | ) － s 2 ( x，k) ≤ 1 3 ( k 2 － 1 3 ) k ，结论成立． 类似可证，在区间( 0，1 / k) 上，0≤Λ2 ( | x | ) － s 2 ( x， k) ≤ 1 3 ( k 2 － 1 3 ) k 成立． 3 模型的收敛性分析 定理 3 设 A∈Ｒm × n ，B∈Ｒl × n ，x∈Ｒn ，η∈Ｒm， μ∈Ｒl ，c，c * ∈Ｒ，D∈Ｒm × m 是对角阵，D 的对角元素为 1 或 － 1． 实函数定义如下: h( x) = 1 2 ‖x‖2 2 + c 2 ‖Λ( D( Ax + η) ) ‖2 2 + c * 2 ‖Λ( | Bx + μ | ) ‖2 2 ( 8) g( x，k) = 1 2 ‖x‖2 2 + c 2 ‖Λ( D( Ax + η) ) ‖2 2 + c * 2 ‖s( Bx + μ，k) ‖2 2 ( 9) 其中，s( x，k) ，k ＞ 1 由( 7) 式定义． 则: ( 1) 优化问题min x∈Ｒn h( x) 存在最优解 x，min x∈Ｒn g( x，k) 存在最优解 xk ，并且lim k→∞ h( xk ) = h( x) ． ( 2) 设优化问题min x∈Ｒn h( x) 的最优解集合为 Uh，则 { xk } 存在的收敛子列{ xkn } 满足lim n→∞ xkn = xh，这里 xh∈ Uh ． 证明: ( 1) 定义相应的水平集为 Lν ( h( x) ) = { x | x∈ Ｒn ，h( x) ≤ν} ． Lν ( g( x，k) ) = { x | x∈Ｒn ，g( x，k) ≤ν} ． 由于 0≤ · 783 ·
·388· 工程科学学报，第37卷，第3期 s(x,k)≤A(1x1),对任意v≥0，它们满足L.(h(x))C minh(x)的最优解. rER L(g(x,k))C{xI≤2.因此，L(h(x))和 L(g(x,)是R空间中的紧集，从而优化问题 4 数值实验 minh(x),ming(,k)的最优解存在，满足minh(r)）= 在三个数据集上进行了实验，数据样本可以从 h(),ming(,k)=g(,k).其次，对任意xeR",由 UCI机器学习问题库得到.为比较不同光滑半监督支 定理2， 持向量机的性能，采用分类器的推广能力作为检验指 0≤h(x)-g(x,k)= 标，分类器的推广能力用未标记训练样本的正确率来 衡量.本实验采用模型(6)，其中函数∫(x)分别取为 亏IA(Bx+e)I-亏Is(Br+e,店= 高斯函数和广义三次样条函数.为方便起见，将光滑 号茗(sg》-F顶，]≤ 半监督支持向量机分类模型标记如下：采用广义三次 样条函数的光滑半监督支持向量机模型记为3SSVM: 2-永) 采用高斯函数的光滑半监督支持向量机模型记为 GSS3VM.实验采用BFGS-Armijo0算法. 因为h()≥h(田)，g(c,)≥g(,k),所以 4.1在心脏病诊断数据集上的实验 0≤h()-h()≤h()-h(R)+g(x,k)- 数据规模为270个样本，均已标记.本实验取前 g(,)=h()-g(k)+g(,)-h() 70个数据为标记数据，对后200个数据进行无标记处 h()-g,)≤2-) 理.其中病理检测有13项：年龄，性别，胸腔疼痛类 型，舒张血压，每分升血浆内Cholestoral的含量，血糖， 从而， 心电图结果，最快心率，物理感应疼痛度，ST下降段， limh ()=h() ST切片检查，主要血管数，丘脑状态.心脏病状况分为 (2)对任意keZ,k>1,由式(9)得71F≤ 两类：有和无.这样，每个数据样本包括13个属性，所有 数据样本被分为两类.在实验中，对模型错分惩罚参数c、 g(,k)≤g(x,k),{F}有界，从而{F}有收敛子列 c'及光滑参数k进行了优选，比较了c和c'取不同值时 之.不妨设limr=x,可得imh()=h(x)= 的实验结果，发现c和c取相等值，参数k取100时，3SS3 Iimh()=h(),因此xa∈U,即x.是优化问题 VM的分类正确率较好.具体计算结果见表1. 表1用3SS3VM与GSS3VM检测心脏病问题的正确率和CPU时间 Table 1 Training accuracy rate and CPU time using 3SS VM and CSSVM to test heart disease 正确率/% CPU 正确率/% CPU 正确率/% CPU 模型 (c=c=0.1) 时间/s (c=c"=1) 时间/s (c=c=10) 时间/s 3SS*VM (k =100) 85 0.12 82.5 0.20 83 0.12 GSS3 VM 77.5 0.21 82 0.22 82.5 0.21 由表1可见，当c=c取不同值时，采用广义三 样本，均为已标记.本实验取前200个数据为标记数 次样条函数逼近对称铰链损失函数有训练优势，且 据，对后1399个数据进行无标记处理.其中属性检测 计算时间较短.实验发现，当c=c取0.1、1和10成 信息有12项：固定酸度，挥发性酸度，柠檬酸，残糖， 倍变化时，3SS3VM分类器的分类正确率有所变化， 氯，游离二氧化硫，总二氧化硫，密度，pH值，硫酸盐， 当c=c取值变化范围较小时，分类器的分类正确率 醇，品质.红酒品质的取值为0~10，实验中对所有品 没有明显的变化，即模型的解对参数的微小扰动不 质小于5的归为差类，红酒的品质分为优和差两类. 敏感. 每个数据样本包括12个属性，所有数据样本被分为两 4.2在红酒和白酒质量检测数据集上的实验 类.在实验中，仍取k=100及有代表性的c=c的值， 首先进行红酒品质检测.数据规模为有1599个 求解得到的性能指标如表2. 表2用3SS3VM与GSS3VM检测红酒质量问题的正确率和CPU时间 Table 2 Training accuracy rate and CPU time using 3SS3VM and GSSVM to test the quality of red wine 正确率/% CPU 正确率/% CPU 正确率/% CPU 模型 (c=c'=1) 时间/s (c=c'=100) 时间/s (c=c'=1000) 时间/s 3SS*VM (k =100) 68.76 0.78 98.50 2.11 98.36 5.47 GSS VM 53.96 1.04 67.91 2.38 97.35 8.01
工程科学学报，第 37 卷，第 3 期 s( x，k) ≤Λ( | x | ) ，对任意 ν≥0，它们满足 Lν ( h( x) ) Lν ( g( x，k) ) { x | ‖x‖2 2 ≤2ν} ． 因此，Lν ( h( x) ) 和 Lν ( g( x，k) ) 是 Ｒn 空 间 中 的 紧 集，从 而 优 化 问 题 min h( x) ，min g( x，k) 的最优解存在，满足min x∈Ｒn h( x) = h( x) ，min x∈Ｒn g( x，k) = g( xk ，k) ． 其次，对任意 x∈Ｒn ，由 定理 2， 0≤h( x) － g( x，k) = c * 2 ‖Λ( | Bx + μ | ) ‖2 2 － c * 2 ‖s( Bx + μ，k) ‖2 2 = c * 2 ∑ i = l i = 1 ［Λ2 ( | Bix + μι | ) － s 2 ( Bix + μι，k) ］≤ c * l 6 ( k 2 － 1 3 ) k ． 因为 h( xk ) ≥h( x) ，g( x，k) ≥g( xk ，k) ，所以 0≤h( xk ) － h( x) ≤h( xk ) － h( x) + g( x，k) － g( xk ，k) = h( xk ) － g( xk ，k) + g( x，k) － h( x) ≤ h( xk ) － g( xk ，k) ≤c * l 6 ( k 2 － 1 3 ) k ， 从而， lim k→∞ h( xk ) = h( x) ． ( 2) 对任意 k∈Z + ，k ＞ 1，由式( 9) 得 1 2 ‖xk ‖2 2≤ g( xk ，k) ≤g( x，k) ，{ xk } 有界，从而{ xk } 有收敛子列 xkn ． 不妨 设 lim n→∞ xkn = xh，可 得 lim n→∞ h ( xkn ) = h ( xh ) = lim kn→∞ h( xkn ) = h( x) ，因 此 xh ∈ Uh，即 xh 是 优 化 问 题 min x∈Ｒn h( x) 的最优解． 4 数值实验 在三个数据集上进 行 了 实 验，数 据 样 本 可 以 从 UCI 机器学习问题库得到． 为比较不同光滑半监督支 持向量机的性能，采用分类器的推广能力作为检验指 标，分类器的推广能力用未标记训练样本的正确率来 衡量． 本实验采用模型( 6) ，其中函数 f( x) 分别取为 高斯函数和广义三次样条函数． 为方便起见，将光滑 半监督支持向量机分类模型标记如下: 采用广义三次 样条函数的光滑半监督支持向量机模型记为 3SS3 VM; 采用高斯函数的光滑半监督支持向量机模型记为 GSS3 VM． 实验采用 BFGS--Armijo［1］算法． 4. 1 在心脏病诊断数据集上的实验 数据规模为 270 个样本，均已标记． 本实验取前 70 个数据为标记数据，对后 200 个数据进行无标记处 理． 其中病理检测有 13 项: 年龄，性别，胸腔疼痛类 型，舒张血压，每分升血浆内 Cholestoral 的含量，血糖， 心电图结果，最快心率，物理感应疼痛度，ST 下降段， ST 切片检查，主要血管数，丘脑状态． 心脏病状况分为 两类: 有和无． 这样，每个数据样本包括 13 个属性，所有 数据样本被分为两类． 在实验中，对模型错分惩罚参数 c、 c * 及光滑参数 k 进行了优选，比较了 c 和 c * 取不同值时 的实验结果，发现 c 和 c * 取相等值，参数 k 取 100 时，3SS3 VM 的分类正确率较好． 具体计算结果见表1． 表 1 用 3SS3VM 与 GSS3VM 检测心脏病问题的正确率和 CPU 时间 Table 1 Training accuracy rate and CPU time using 3SS3VM and GSS3VM to test heart disease 模型 正确率/% ( c = c* = 0. 1) CPU 时间/ s 正确率/% ( c = c* = 1) CPU 时间/ s 正确率/% ( c = c* = 10) CPU 时间/ s 3SS3VM ( k = 100) 85 0. 12 82. 5 0. 20 83 0. 12 GSS3VM 77. 5 0. 21 82 0. 22 82. 5 0. 21 由表 1 可见，当 c = c * 取不同值时，采用广义三 次样条函数逼近对称铰链损失函数有训练优势，且 计算时间较短． 实验发现，当 c = c * 取 0. 1、1 和 10 成 倍变化时，3SS3 VM 分类器的分类正确率有所变化， 当 c = c * 取值变化范围较小时，分类器的分类正确率 没有明显的变化，即模型的解对参数的微小扰动不 敏感． 4. 2 在红酒和白酒质量检测数据集上的实验 首先进行红酒品质检测． 数据规模为有 1599 个 样本，均为已标记． 本实验取前 200 个数据为标记数 据，对后 1399 个数据进行无标记处理． 其中属性检测 信息有 12 项: 固定酸度，挥发性酸度，柠檬酸，残糖， 氯，游离二氧化硫，总二氧化硫，密度，pH 值，硫酸盐， 醇，品质． 红酒品质的取值为 0 ～ 10，实验中对所有品 质小于 5 的归为差类，红酒的品质分为优和差两类． 每个数据样本包括 12 个属性，所有数据样本被分为两 类． 在实验中，仍取 k = 100 及有代表性的 c = c * 的值， 求解得到的性能指标如表 2． 表 2 用 3SS3VM 与 GSS3VM 检测红酒质量问题的正确率和 CPU 时间 Table 2 Training accuracy rate and CPU time using 3SS3VM and GSS3VM to test the quality of red wine 模型 正确率/% ( c = c* = 1) CPU 时间/ s 正确率/% ( c = c* = 100) CPU 时间/ s 正确率/% ( c = c* = 1000) CPU 时间/ s 3SS3VM ( k = 100) 68. 76 0. 78 98. 50 2. 11 98. 36 5. 47 GSS3VM 53. 96 1. 04 67. 91 2. 38 97. 35 8. 01 · 883 ·
张晓丹等：一个广义三次样条光滑半监督支持向量机 ·389 由表2可知，当c=c取不同值时，采用广义三次 总结上述三个数据集上的实验结果可得，当数据 样条函数逼近对称铰链损失函数分类正确率较高，且 规模变化时，所得到的广义三次样条光滑半监督支持 计算时间较短.特别当c=c成倍增大达到100时，分 向量机亦有较好的分类效果 类器的分类正确率达到最高.当c=c'=1000时，分 5 类器仍维持较高的分类正确率，但时间大大增加 结论 在红酒质量检测实验中，我们对光滑参数k的选 应用广义三弯矩法证明了满足零点二阶光滑条件 取作最优检测，取c=c=100,分类正确率随k的变化 的广义三次样条对称铰链逼近函数的存在唯一性：分 如图2. 析了该函数的逼近精度.最后，证明了基于此函数的 100 光滑半监督支持向量分类机具有较好的收敛性并进行 95 了数值检验.数值实验显示新模型比基于高斯函数的 光滑半监督支持向量机模型具有更好的分类正确率和 90 更快的处理速度 85 参考文献 80 [1]Deng N Y.Tian Y J.Neu Method in Data Mining:Support Vector 75 Machine.Beijing:Science Press,2004:49 70 (邓乃扬，田英杰.数据挖掘的新方法：支持向量机.北京： 100200300400500600700800900 科学出版社，2004：49) 图2当k取不同值时，3SS3VM的训练正确率 2] Xu Q L,Wang X L.A Novel Semi-supervised classification meth- Fig.2 Training accuracy rate of 3SS VM with different values of k od based on SVM.Comput Technol Dev,2010,20(10):115 (徐庆伶，汪西莉.一种基于支持向量机的半监督分类方法 由图2可见：c=c的取值固定，k取值越大，分类 计算机技术与发展，2010,20(10)：115) 器的性能越好：当k足够大时，分类器的性能趋于稳 B] Chapelle 0,Sindhwani V,Keerhi S S.Optimization techniques 定，继续增大k,由于舍入误差等原因导致分类器性能 for semi-supervised support vector machines.J Mach Learn Res, 2008,9:203 并没有提高.因此，针对不同的实际训练问题，不同的 [4] Bennett K P.DemirizA.Semi-supervised support vector machines c和c取值，k选取适当即可. /Adrances in Neural Information Processing Systems 11,Cam- 下面进行白酒品质检测.数据规模增大为4898 bridge:MIT Press,1998:368 个样本，均为已标记.任取100个数据为标记数据，对 [5]Reddy IS,Shevade S,Murty M N.A fast quasi-Newton method 其余4798个数据进行无标记处理.其中属性检测信 for semi-supervised SVM.Pattern Recognit,2011,44:2305 息与红酒实验数据相同.白酒品质的取值为0~10，实 6 Liu Y Q,Liu S Y,Gu M T.Polynomial smooth classification al- 验中对所有品质小于5的归为差类，白酒的品质分为 gorithm of semi-supervised support vector machines.Comput Sci, 2009,36(7):179 优和差两类.每个数据样本包括12个属性，所有数据 (刘叶青，刘三阳，谷明涛.一种多项式光滑的半监督支持向 样本被分为两类.基于模型3Ss3VM的求解得到的性 量机分类算法.计算机科学，2009,36(7)：179) 能指标如表3. [7]Chapelle 0,Zien A.Semi-supervised classification by low density 表3用3SSVM检测白酒质量问题的正确率 separation /10th International Workshop on Artificial Intelligence Table 3 Training accuracy rate using 3SSVM to test the quality of liq- and Statistics.Barbados,2005:57 uor 的 8]Lee Y J,Mangasarian O L.SSVM:A smooth support vector ma- chine for classification.Comput Optim Appl,2001,22(1):5 c=c" k=1 k=10k=100 k=1000k=10000 9] Wu Q.Support Vector Machines Learning Algorithm Research 1 69.10 69.21 83.24 80.61 83.36 Based on Optimization Theory [Dissertation].Xian:Xidian Uni- 10 70.11 70.1380.8869.66 59.55 versity,2009:85 (吴青.基于最优化理论的支持向量机学习算法研究[学位 由表3可知：当c=c=1,k=10000时，有较好的 论文].西安：西安电子科技大学，2009：85) 分类效果：当c=c°=10，k=100时，有较好的分类效 [10]Zhang X D,Shao S,Liu Q S.Smooth support vector machine 果.对于不同的c和c取值，模型3SSVM的参数k有 model based on spline function.J Unir Sci Technol Beijing, 2012,34(6):718 不同的最优值.因此，针对不同的实际训练问题，不同 (张晓丹，邵帅，刘软圣.基于样条函数的光滑支持向量机 的c和c取值，k选取较优值就可以. 模型.北京科技大学学报，2012,34(6)：718)
张晓丹等: 一个广义三次样条光滑半监督支持向量机 由表 2 可知，当 c = c * 取不同值时，采用广义三次 样条函数逼近对称铰链损失函数分类正确率较高，且 计算时间较短． 特别当 c = c * 成倍增大达到 100 时，分 类器的分类正确率达到最高． 当 c = c * = 1000 时，分 类器仍维持较高的分类正确率，但时间大大增加． 在红酒质量检测实验中，我们对光滑参数 k 的选 取作最优检测，取 c = c * = 100，分类正确率随 k 的变化 如图 2． 图 2 当 k 取不同值时，3SS3VM 的训练正确率 Fig． 2 Training accuracy rate of 3SS3VM with different values of k 由图 2 可见: c = c * 的取值固定，k 取值越大，分类 器的性能越好; 当 k 足够大时，分类器的性能趋于稳 定，继续增大 k，由于舍入误差等原因导致分类器性能 并没有提高． 因此，针对不同的实际训练问题，不同的 c 和 c * 取值，k 选取适当即可． 下面进行白酒品质检测． 数据规模增大为 4898 个样本，均为已标记． 任取 100 个数据为标记数据，对 其余 4798 个数据进行无标记处理． 其中属性检测信 息与红酒实验数据相同． 白酒品质的取值为 0 ～ 10，实 验中对所有品质小于 5 的归为差类，白酒的品质分为 优和差两类． 每个数据样本包括 12 个属性，所有数据 样本被分为两类． 基于模型 3SS3 VM 的求解得到的性 能指标如表 3． 表 3 用 3SS3VM 检测白酒质量问题的正确率 Table 3 Training accuracy rate using 3SS3VM to test the quality of liquor % c = c* k = 1 k = 10 k = 100 k = 1000 k = 10000 1 69. 10 69. 21 83. 24 80. 61 83. 36 10 70. 11 70. 13 80. 88 69. 66 59. 55 由表 3 可知: 当 c = c * = 1，k = 10000 时，有较好的 分类效果; 当 c = c * = 10，k = 100 时，有较好的分类效 果． 对于不同的 c 和 c * 取值，模型 3SS3 VM 的参数 k 有 不同的最优值． 因此，针对不同的实际训练问题，不同 的 c 和 c * 取值，k 选取较优值就可以． 总结上述三个数据集上的实验结果可得，当数据 规模变化时，所得到的广义三次样条光滑半监督支持 向量机亦有较好的分类效果． 5 结论 应用广义三弯矩法证明了满足零点二阶光滑条件 的广义三次样条对称铰链逼近函数的存在唯一性; 分 析了该函数的逼近精度． 最后，证明了基于此函数的 光滑半监督支持向量分类机具有较好的收敛性并进行 了数值检验． 数值实验显示新模型比基于高斯函数的 光滑半监督支持向量机模型具有更好的分类正确率和 更快的处理速度． 参 考 文 献 ［1］ Deng N Y，Tian Y J． New Method in Data Mining: Support Vector Machine． Beijing: Science Press，2004: 49 ( 邓乃扬，田英杰． 数据挖掘的新方法: 支持向量机． 北京: 科学出版社，2004: 49) ［2］ Xu Q L，Wang X L． A Novel Semi-supervised classification method based on SVM． Comput Technol Dev，2010，20( 10) : 115 ( 徐庆伶，汪西莉． 一种基于支持向量机的半监督分类方法． 计算机技术与发展，2010，20( 10) : 115) ［3］ Chapelle O，Sindhwani V，Keerhi S S． Optimization techniques for semi-supervised support vector machines． J Mach Learn Ｒes， 2008，9: 203 ［4］ Bennett K P，Demiriz A． Semi-supervised support vector machines / / Advances in Neural Information Processing Systems 11，Cambridge: MIT Press，1998: 368 ［5］ Ｒeddy I S，Shevade S，Murty M N． A fast quasi-Newton method for semi-supervised SVM． Pattern Ｒecognit，2011，44: 2305 ［6］ Liu Y Q，Liu S Y，Gu M T． Polynomial smooth classification algorithm of semi-supervised support vector machines． Comput Sci， 2009，36( 7) : 179 ( 刘叶青，刘三阳，谷明涛． 一种多项式光滑的半监督支持向 量机分类算法． 计算机科学，2009，36( 7) : 179) ［7］ Chapelle O，Zien A． Semi-supervised classification by low density separation / / 10th International Workshop on Artificial Intelligence and Statistics． Barbados，2005: 57 ［8］ Lee Y J，Mangasarian O L． SSVM: A smooth support vector machine for classification． Comput Optim Appl，2001，22( 1) : 5 ［9］ Wu Q． Support Vector Machines Learning Algorithm Ｒesearch Based on Optimization Theory［Dissertation］． Xian: Xidian University，2009: 85 ( 吴青． 基于最优化理论的支持向量机学习算法研究［学位 论文］． 西安: 西安电子科技大学，2009: 85) ［10］ Zhang X D，Shao S，Liu Q S． Smooth support vector machine model based on spline function． J Univ Sci Technol Beijing， 2012，34( 6) : 718 ( 张晓丹，邵帅，刘钦圣． 基于样条函数的光滑支持向量机 模型． 北京科技大学学报，2012，34( 6) : 718) · 983 ·