论文研究-基于改进的SVM学习算法及其在信用评分中的应用.pdf,  对于处理大规模问题的信用评分方法除要求达到一定的准确率之外,其速度、可解释性、简洁性等性能也非常重要. 借鉴SMO的思想, 首先提出一个基于三变量的改进的SVM学习算法, 即将SVM问题分解为一系列含有三个变量的二次规划子问题,其优点是所求的相应松弛子问题都有解析解,使得该方法能够更加精确和快速地逼近最优解;其次将新算法应
第3期 陆爱国,、等:基于改进的SVM学习算法及其在信用评分中的应用 517 定理1假设A=(42)是对称正定的记x=(n2)7,b=(1,则边界约束优化间题 in q() Ax-bfr t.lz≤xz t;,2= 有唯一最优解x*=(x1,x2)1,并且有 (1)当a12≥0时 1-min( max(11, Ti b1-a122 b1-a122 max l1 写一m(m(r2)m( l2).a2 (l)当a12<0时 b1- all b1-a12 T =min( max 11, Ti max ,l1 11 C2=min max 12, T2 a⊥2⊥ max l2 a22 a 其中m=-de(A det(al 证明见参考文献[4 31求解三变量SVM子问题 在这一部分,关键的思想是:一方面希望子问题规模不要太小,以免迭代次数太多;另一方面借鉴SMO 算法的优点,找到相应子问题的解析解或近似解,为此我们尝试来求解三变量SVM子问题 不失一般性,假设选取的三个变量是a1,a2,a3,问题(2)可以写成如下的三变量优化问题: mino(a1,a2,3)=k1a3+k2+7k3+K122 /1 3A13103+y23K23023 y1(11+y2202+93(33+ cons s.t. 1C1+32Ce2+ y3C3 = ∑ yiCi= cons 0≤cz≤C,i=1,2,3 其中n1=∑= y: aiKi1,v2=∑l4vaK2,3=E:4ya1k3, 设问题的初始可行解为a,a2,a3最优解为α,a,a3,且满足线性约束∑1a:=0,因此有 y101+ y2a2t y3a3=y101 +92C2+ y3a3 令s1=y33,S2=y3:S1Q1+s202+a3=,由此得: 3=7-S101-S202 求解问题(3)分为两个步骤 第一将间题(3)转化为两变量的松弛边界约束问题,并给出相应的解析解 将(4)式代入(3)中消去a3得两变量的松弛约束问题 nin(ax1,d2)=(K11+k3-2K13)a1+x(Ky+K33-2h23)x2 +y2(K12-K13-K23+K33)a1a2 +s1(K13-K33)+81-1+91(v1-03)o +[s2(K23-F3)+2-1+y2(2-3) 0≤az≤C,=1,2 a11-(K1+K33-2K13),a22-(K22+K33-2K23), a12=1y2(K12-K13-K23+K3), b1=s1V(a)3-V(a)1+a119+a12Q2 b2=2V(a)3-V(a)2+a12a3+a22Q2 518 系统工程理论与实践 第32卷 由于V()=y∑=130K-1,a3=y-81a-62a2,所以 v(1-23)=yo(a)4+1)-∑?Kan-((a)3+1)+∑界Ka b1-51+1+751(K33-K13) (9) (2-23)=y(Vo(2+1)-∑K 3+1)+∑va?K3 b2-82+1+ys2(33-K 记A 11a12 是对称正定的,b=(b1,b2),a=(a1,a2)2 12a22 将(6)代入(5)整理得等价形式为 IIU(〔k Ac-v S.t.0< 根据定理1得问题(5)的解为 1)当a12≥0时, Q bor= min max( 0.a1 )m,o) min( max 0, 2 2-a12C)(b2)+ U22 )当a12<0时, 1(v1-a12C)+ c1,=min max(0, C1, 11 min( max 0, C2 12 其中a a11c22-012 第二:将间问题(5)的解代入线性约束(4),从而得到间题(3)的解析表达式 由(4)知a3=-s10100-s220,下面分三种情况讨论(3)的解 3-1)当0≤a3x≤C时 box y 3-2)当 0时 a3=0 2=a2+ (s2(11-1a12)a3+s12V(a)1-Vv(a)2 K11+K F12 S1S2Qr 其中a2的范围为L≤a2≤U.如果s1=82,L=max(0,61-C),U=min(C,s10);否则L max(0,-81),U=min(C,C-s10) 3)当a3>C时, 2-a2+ (211-1a12)(a3-C)+s12V(a)1-V(a)2 K11+ a=81(-C)-1S2Q2, 其中α2的范围为L≤a≤U.如果s=82,L=max(0.,1(-C)-C),U=min(C,s1(-C);否则 L=max(0,-81(-C),U=min(C,C-81(-C) 第3期 陆爱国,、等:基于改进的SVM学习算法及其在信用评分中的应用 519 32改进的三变量SVM学习算法 首先利用目前的流行方法最大违背对( maximal violating pail,MVP)1原则选取三变量工作集 ∈(y)-mVv(a) t∈ arg max ∈m(c), k∈arg max-yVu(、、∈(n)3vv(a) )B={,j,k 下面给出算法的具体步骤 算法:ISVM-TV 步骤1给定精度c>0,a0=0.Vc(a0)=-e,令k=0. 步骤2若m(a^)-M(ab)≤c,停止;否则根据MVP原则找工作集B={,j,m},定义N {1,2,…,}-B,分别对应的变量为a占,aA 步骤3利用解析表达式3-1)-3-3)得最优解a1,且 步骤4令k=k+1,转步骤2 4数值试验 为验证本文算法的性能,我们在公共数据集上进行测试,并与其它方法做比较停机条件=1×10-10, 使用RBF核函数:K(x,y)=exp(-x-列|2/(2a2).实验都是在 Intel(R)core(①M)2/RAM10GB机上完 成,算法 ISVM-TM和Chen-SMO采用 Matlab7.0编程 我们选用3个来自UI机器学习库中的数据集:第一个是 Adult数据集,共有32561个123维的样 本,这里抽取部分数据子集做实验,用来验证 ISVM-TV算法能够节省计算代价;第二个是 German信用卡 数据集,共由1000个20维的样本构成,其中‘信用好”和“信用差的样本分别为700、300个;第三个是 Australian信用卡数据集,共由690个14维的样本组成,“信用好”和“信用差的样本分别为307、383个 后两个是信用数据集,用于不同信用评分模型之间的性能比较 41分类器性能评价标准 分类器性能评价标准很多,其中常用的主要有准确度、查全率、查准率等.对于两类问题,运用分类器对 测试样本进行分类时,有四种可能的输出结果:正确正例个数(TP),正确的负例个数(IN),错误的正例个数 (FP),错误的负例个数(FN).下面给出一些性能评价标准的定义为 准确度( accuracy)=+x;查准率( precision)=mp; 正确的正例率( TP-rate)=ms错误的正例率( FP-rate)=rHx 查全率rlm+x 般来说,一个分类器若有较高的准确度、查全率、查准率、 TP-rate和较低的 FP-rate,就意味着它具 有较好的性能 42IsVM-T和Chen-SMO的性能比较 在 Adult数据集上的实验,参数取值与通常参考文献中一致,即:C=1,a2=10.实验结果见表1 从表1可以看出.与Chen-SMO算法相比,在保让分类精度变的同时,新方法的迭代次数较少、训练 时间较短.即其训练速度比(hen-SMO算法快约7.5%-12.3%.该实验表明了所提出的新方法 ISVM-TV节 省了计算代价,正与我们的出发点是一致的,尤其对于大规模问题更能体现这一价值 43基于 ISVM-Iⅴ算法的信用评分试验 这部分给出ISVⅥMT和RBF网络,多层感知网络不同信用评分方法之间的性能比较试验.在 German 和 Australian两个信用数据集上的实验结果分别见表2和表3.其中用70%作为训练集,30%作为测试集 520 系统工程理论与实践 第32卷 表1在 Adult数据集上 ISVM-ⅴ和 Chen-SMO的性能比较 数据集 算法 迭代核计算 训练 训练 (维数/大小) 次数 次数 时间(sec)精度(%) adult Chen-SMO 6885 825 5.17 8681 (123/1605) ISVM-TV 793 830 4.71 8681 Adult Chen-SMO 998 85.75 (123/2265) ISVM-TV 7764 1137 8.75 85.75 Adult Chen-SMO 16599 1504 19.67 8589 (123/3185) ISVM-I 12690 1539 17.73 8589 Adults Chen-SMo 47125 99.64 85.23 (123/6414) ISVM-TV 41886 2876 92.14 85.23 表2在 German数据集上不同算法间的性能比较 算法 Accurac TP-rate FP-rate Precision Recall RBF网络 0.693 0.41 0.738 0.737 多层感知內络 0.695 0.74 0.74 0.74 ISVM-TV 0.708 0.76 0.41 0.747 0.76 表3在 Australian数据集上不同算法间的性能比较 算法 Accuracy TP-rate FP-rate Precision Recall RRF网络 0.817 0.828 0.191 0.8;31 0.828 多层感知网络 0.845 0.849 0.158 0.849 0.849 ISVM-TV 0.863 0.855 0.131 U.866 0.855 从表2中的结果可以看出,虽然就 FP-rate而言, ISVM-TV方法与其它两种神经网络方法相当,但 ISVM-TⅤ在一定程度上提高了准确率、查准率、查全率和 TP-rate.在 Australian数据集上的试验结果 表明, ISVM-TⅤ方法在上面提到的所有评价指标上都比其它两种方法有明显改进,即新方法有较高的准确 率、杳准率、查全率、 TP-rate和较低的 FP-rate.从而说明 ISVM-TV是一种较好的信用评分方法.其主要 原因有三方面: 1)它采用结构风险最小化原则,求解的是一个凸二次规划问题,得到的是全局最优解,克服了在神经网 络方法无法避免的局鄙最优解的问题; 2)它通过一个非线性映射将输入空间映射到高维特征空间,并在高维空间中构造线性判别函数来实现 原空间中的非线性判别函数,这使得它有较好的推广能力.并且提高分类性能; 3)由于它所求解的子冋题有解析解,使得它能够快速和精确地逼近最优解,从而提高该分类器的速度和 精度 5结束语 基于合理的猜想,本文提出了一个新的用于信用评分问题的三变量SⅥM学习方法.其最大的优点就是 迭代过程中每一步的相应松弛子问题的最优解都可以直接用解析表达式给出,从而避开了复杂的数值求解过 程,使得该方法能够更加精确和快速地逼近最优解.在来自UαⅠ机器学习库的3个数据集上的数債试验表 明:所提出的方法既节约了计算代价又改进了分类精度,这具有较好的性能,尤其对于大规模问题更能体现 其性能优势.该方法目前只解决了分类冋题,山于其良好的性能,下一步将考虑把该方法改进推广至回归、预 测等其它问题上 参考文献 [1 Desai V S, Crook J N, Overstreet G A. A comparison of neural network and linear scoring models in the credit union environment J]. European Journal of Operational Research, 1996, 95(1): 24-37 2 Lacerda E, Carvalho A CPL F, Braga A P, et al. Evolutionary radial basis functions for credit assessment Applied Intelligence, 2005, 22(3):167-181 第3期 陆爱国,、等:基于改进的SVM学习算法及其在信用评分中的应用 521 3 Laitinen E K. Predicting a corporate credit analyst's risk estimate by logistic and linear models[J. International Review of Financial Analysis, 1999, 8 2):97-121 Huang C L, Chen M C, Wang C Credit scoring with a data mining approach based on support vector machines]. Expert Systems with Applications, 2007, 33(1):817-856 5 Thomas L C, Edelman D B, Crook J N. A survey of the issues in consumer credit modeling research[J. Journal of the Operational Research Society, 2005, 56(9): 1006-1015 [6 Vapnik V N 'The Nature of Statistical Learning Theory[M. Berlin: Springer, 1995 7 Boser B, Guyon I. VapnikVN. A training algorithm for optimal margin classifiers[C//Proceedings of the Fifth Annual Workshop on Computational Learning Theory, Pittsburgh, PA: ACM, 1992: 144-152 8 Osuna F, Fret.md R, Gimsi F. An improved training a.hm for support vector machines[c// proceedings of the 1997 IEEE Workshop on Neural Networks for Signal Processing. New York: IEEE Press, 1997: 276-285 9 Osuna E, Fretmd R, Imsi F. Training support vector machines: An application to face detection C// IEEE Computer Society Conference on Computer Vision and Pattern Recognition(CVPR 97), 1997: 130-136 10 Platt J Sequential minimal optimization: A fast algorithm for training support vector machines[R Technical Report, 1998 [11 Platt J. Fast Training of Support Vector Machines Using Sequential Minimal Optimization M// Scholkopf B Burges C, Smola A. Advance in Kernel Methods: Support Vector Learning, Cambridge, MA: MIT Press, 1998 185-208 [12 PlaLt J. Using analyLic QP anld sparseness lo speed training of support vector Machines[C// Proceedings of the 1998 Conference on Advances in Neural Information Processing Systems Il, Cambridge, MA: MIT Press, 1998 557-563 13 Chen P I, Fan R E, Lin C J. A study on SMO-type decomposition methods for support vector machines J IEEE Transactions on Neural Networks, 2006, 17(4): 893-908 14陆爱国,刘红卫,王珏.训练支持向量机的四重序列解斫优化算法J系统工程理论与实践,2011,31(8):15551564 Lu A G, Liu h w, wang j. Quadruple sequential analytic optimization algorithm for training support vector Illachines[J]. Systems Engineering- Theory Practice, 2011, 31 (8):1555-1564 [15 Keerthi S, Shevade S K, Bhattacharyya. C, et, al. Improvements to Platt's SMO algorithm for SVm classifier designJ. Neural Computation, 2001, 13: 637-649