基于辅助分类策略的概率支持向量机

基于辅助分类策略的概率支持向量机王剑锋，杨胜，谢凯，李仁发湖南大学计算机与通信学院，长沙(410082)E-mail：[e-mail]摘要：提出一个新的基于概率估计的支持向量机模型。通过定义相应样本数据点的概率估计值，以及相应的数据样本点到超平面的距离，来形成在线性和非线性情况下的新的支持支持向量机。同时通过定义基于样本点的整体偏离度，提出支持向量机的辅助分类策略。最后通过实验表明，新的支持向量机比以往传统的支持向量机有更好的分类性能并缩短了数据样本的训练时间。关键词：分类，支持向量机，概率估计值，整体偏离度，辅助分类策略中图分类号：TP1831引言在传统的支持向量机的方法中，没有一种统一的方法或者比较有效的方法来辅助支持向量机的分类，即支持向量机的分类判断标准单一，同时，在支持向量机的训练过程中，所有的数据样本点都被等同地看待，在寻找昀优超平面的过程中没有考虑到它们的不同，因而所寻找的超平面往往是局部的昀优的[1,2,3,4]。然而在现实的问题当中，由于噪声，不一致性，模糊性等出现，在数据集中每个样本点的有效性是不一样的，针对这个问题，KiYoungLEE等人提出了概率支持向量机[5]，但是这个方法没有很好的反映数据样本点的有效性，同时，其它的方法文献[8,10]计算复杂度过高。本文提出了一种新的数据样本点的概率估计方法，进而得到新的概率支持向量机。同时针对分类标准的单一性，以及当训练数据集较大时文献[6,7],需要较长的训练时间，还有诸如动态选择分类器的方法文献[9],分类效率不是很高，基于此提出支持向量机的辅助分类策略。由KiYoungLee等人提出的基于概率的支持向量机给出了一个度量训练数据样本点从属度的方法，然而由此所形成的支持向量机，没有很好的分类精度，以及良好的训练效率，从而使得支持向量机并未达到良好的实际分类效果。它采用了每个数据样本点有一个概率的估计值，然后，由此形成的支持向量机。它的每个训练数据样本点kx概率估计为kθ1111−==⎟⎟⎟⎟⎟⎠⎞⎜⎜⎜⎜⎜⎝⎛−−+=∑∑nxxmxxnjjkmllk，在这里lxMthClass∈即lx属于第M类，第M类有m个数据样本点，且假设类MthClass为正例类，jxJthClass∈即jx属于第J类，第J类有n个数据样本点，且假设类JthClass为反例类，其中k为小写。注意到kθ的计算，它是每个训练数据样本点kx到反例类中所有数据样本点的平均距离，设为−d，它到正例类中所有数据样本点的平均距离设为+d，kθ即为)(+−−+ddd。它是针对类别中所有的数据样本点的计算，那么它所计算的即每个数据样本点kx的从属程度，需要)(2mΟ的时间，由此在随后所形成的支持向量机当中，所训练数据样本的时间就会延长，并且训练的精度不是很好。基于概率估计的支持向量机概念首先定义数据样本点的概率估计，然后由此定义相应的点到超平面的距离，继而形成新的基于数据样本点概率估计的支持向量机。随后定义数据样本集的整体偏离度，并与数据样本点的估计值进行比较，来进行支持向量机的辅助分类。定义1：数据样本点的概率估计值kθ每一个样本点kx它到正例中心的距离|1|1∑=+−miikxmxd＝，它到反例中心的距离|1|1∑=−−njjkxnxd＝那么kθ=cccddd−++＋定义为这个数据样本点的概率估计值，即样本点kx到正例中心的距离除以这个距离加上它到反例中心的距离。正例如有m个点，正例中心即∑=miixm11。反例也如此。kθ的计算采用的是样本点kx到中心的距离，而不是到所有点的距离，因此kθ越小越代表该样本点kx属于正例。kθ采用的距离为欧式距离。由于求解支持向量机问题昀终要求解二次规划问题，而二次规划问题又是求平面之间的昀大间隔，因此用kθ定义点到超平面的距离，而由此定义超平面的间隔。定义2：数据样本点到超平面距离kdkd||||||ωωθbxkk−⋅=为点到超平面的距离。其中，ω为一个向量，b为偏移量。根据这个基于数据样本点估计值的距离，会形成新的线性与非线性情况下的支持向量机。在随后的辅助分类策略上也会用到kθ，以提高支持向量机的分类性能。定义3:样本集的整体偏离度Kδ设某个类别包含K个样本点，则这个类别的整体偏离度表示为：()2)(iiKxExE−=δ；这里)(ixE为某个向量ix的数学期望。其中∑==niixnxE11)(，K为大写。2.1基于数据样本点概率估计的新的支持向量机2.1.1首先考虑基本问题的情形求解支持向量机的原始二次规划问题转化为基于数据样本点概率估计的二次规划问题：假设有N个训练样本。minωω⋅T21(1)sub01)(≥−−⋅bxykkkωθ(2)相应拉格朗日函数：]1)([21),,(1−−⋅−=Φ∑=bxybkkkNkkTωθαωωαω(3)求相应偏导数：0=∂Φ∂ω(4)0=∂Φ∂b(5)得到：kkNkkkxy∑==1θαω(6)01=∑=kkNkkyθα(7)相应的二次规划的对偶问题则转化为：max∑∑∑===−=ΦNkNjjkjkjkjkNkkDxxyy11121)(ααθθαα(8)subjectto0≥kα(9)01=∑=Nkkkkyθα(10)相应的判别函数：)sgn()(bxxfk−⋅=ω))(sgn(1bxxyNkjkkkk−⋅=∑=θα(11)此为在考虑了数据样本点的概率估计时，所形成的新的支持向量机的基础上导出的判别函数。2.1.2其次考虑支持向量机在非线性情况下的问题在非线性情形时，注意数据样本点概率估计kθ以及Kδ的计算，kθ的计算要用到kd，kd采用这样一个思想；即类似于在非线性情况下用核函数代替内积的方法，注意到欧氏距离为21||||()2Pppkijijiiijjjpdxxxxxxxxxx==−=−=⋅−+⋅∑其中p为xi，xj的分量，P为x的属性个数，那么在非线性情况下),(),(2),(jjjiiikxxKxxKxxKd+−=，其中),(jkxxK为选用基本的RBF核函数。同时把jx替换某个类别的中心centerx，有∑==miicenterxmx11，则相应的某一点kx到其中心的距离为：),(),(2),(centercentercenteriiikxxKxxKxxKd+−=因为通过核函数的映射，把非线性问题转化为了线性问题，因而kθ的计算公式不变。那么由kθ的定义以及相应的新的kd的计算公式，得出相应的支持向量机的目标函数，min∑=+⋅NkkkTC121ζθωω(12)其中C为惩罚因子，它的取值可参考文献[2],kζ为松弛因子。subto01)(≥−+−⋅kkkbxyζωθ(13)≥kζ(14)拉格朗日函数：∑∑∑===−−+−⋅−+=ΦNkkkNkkkkkkNkkkTkubxyCub111)1)((21),,,,(ζζωθαζθωωαζω(15）再分别对kbζω,,求偏导数：0=∂Φ∂ω(16)0=∂Φ∂b(17)0=∂Φ∂kζ(18)得到：∑==Nkkkkkxy1θαω(19)01=∑=Nkkkkyθα(20)0=−−kkkuCαθ(21)即非线性的原问题的对偶问题为：max∑∑∑===−=ΦNkNjjkjkjkjkNkkDxxyy11121ααθθα(22)subjecttokkCθα≤≤0(23)01=∑=Nkkkkyθα(24)则其相应的判别函数为：)),(sgn()(bxxKyxfjkkkkk−=θα(25)其中),(jkxxK为RBF核函数。每个训练样本数据点的概率估计值计算时间为)(mΟ。由于考虑到每个样本类别中绝大多数数据样本点比较集中，故而直接计算每个训练数据样本点kx到其正例样本类别中心的距离假设cd+，到反例类别中心的距离假设cd−，求)(cccddd−++＋，这样在随后所得到的支持向量机中，训练样本所需要的时间就会缩短，而不是一个数据样本点到类别中所有的样本点之和再求平均距离。这不仅提高了数据样本估计的有效性，并且在随后支持向量机的计算以及在线性和非线性的情况下，支持向量机整个训练过程的效率均得到提高。2.1.3辅助分类策略数据样本在初步训练的基础上，考察某个类别的所有点，通过计算它们偏离其从属类别中心的程度，即整体偏离度，来确定是否还要继续训练，如果这个偏离度小于它们所有点中其估计值kθ的昀大值，则这些点可以归到一个类别中，结束训练，否则，重新训练。即对于数据样本的训练，不一定要求达到支持向量机的分类间隔昀大化的目标，而是在尽可能分开的情况下使得训练时间缩短，达到较好的分类准确率。3算法1）首先计算基于数据样本点的概率估计值kθ，然后计算相应的点到超平面的距离kd；2）对待训练的数据样本，针对于不同的情形（线性可分，线性不可分），由此形成新的支持向量机；进行支持向量机的训练，求解相应的基于数据样本点的二次规划问题；3）计算整体偏离度Kδ，判断偏离度Kδ是否小于他们的估计值kθ的昀大值即}1|max{某个类别的样本数目为，其中mmkkK≤≤≤θδ，4）若是，或者分类间隔已经达到昀大化，则训练结束，否则继续训练。4实验及分析实验部分的实现参考了文献[2]，所有数据均采用UCI数据集，以便进行对比，并且按照数据集的规模的不断扩大，来比较相应的算法的性能。表1标准数据集上的实验数据集传统SVMLI等人SVM本文SVMr93.33%95.37%97.68%Irist(1.47s)(1.32s)(1.05s)r73.35%74.26%80.12%Glasst(3.2s)(2.8s)(1.9s)r56.69%76.17%89.86%Vowelt(6.3s)(5.7s)(4.8s)r52.63%71.26%78.65%Mushroomt(327s)(281s)(236s)其中，r为分类正确率，t为算法训练的时间。由表1可以看出，在数据规模较小的情形下，基于概率估计的支持向量机所需的训练时间有所缩短，并且提高了数据样本的分类精度。在较大的数据样本情况下，所需要的训练时间较大缩短，分类精度有较好地提高，由此，本文提出的基于数据样本点估计的新的支持向量机具备较好的分类性能，并且在辅助分类的策略下，尤其是大规模数据样本的训练时间缩短。5结束语本文首先定义了数据样本点的概率估计，并由此形成了线性与非线性情况下，基于样本点估计的新的支持向量机，随后定义了整体偏离度的概念，以帮助支持向量机的辅助分类。实验表明，新的支持向量机比以往传统的支持向量机有更好的分类性能并缩短了数据样本的训练时间。．S.S.Keerthi,S.K.Shevade,C.Bhattacharyyaetal.AFastIterativeNearestPointAlgorithmforSupportVectorMachineClassifierDesign[J].IEEETransactionsonNeuralNetworks,2000,11(1):124-136.2．C.C.Chang,C.J.Lin.LIBSVM:alibraryforsupportvectormachines,2001.Softwareavailableat~cjlin/libsvm.3．C.J.C.Burges.Atutorialonsupportvectormachinesforpatternrecognition[J].DataMiningandKnowledgeDiscovery,1998,2(2):121-167.4．K.M.Lin,C.J.Lin.Astudyonreducedsupportvectormachines[J].IEEETransactionson