基于孪生支持向量机的特征选择与分类算法研究

《基于孪生支持向量机的特征选择与分类算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

代号10701学号1010120913分类号TP181密级公开题(中、英文)目基于孪生支持向量机的特征选择与分类算法研究ResearchonFeatureSelectionandClassificationMethodsAlgorithmResearchUsingTwinSupportVectorMachine作者姓名封瑞指导教师姓名、职务姬红兵教授学科门类工学学科、专业信号与信息处理提交论文日期二○一三年一月 摘要I摘要孪生支持向量机(TWSVM)摒弃了传统SVM平行约束的条件，通过求解两个形如SVM的二次规划问题来获得分类模型,可以将训练时间缩短到原SVM的1/4。然而，原始TWSVM并没有考虑到数据的分布信息，对于一些分布复杂的数据，TWSVM就不能进行有效的分类识别。针对此问题，本文从流形学习和聚类两方面进行讨论，对TWSVM进行改进。首先，从流形学习进行考虑，通过将数据的流形结构引入至分类目标函数中，提出基于流形结构的TWSVM(MTSVM)分类算法，其主旨是假设所处理的数据采样于一个潜在的流形上，通过建立类内散度矩阵，获得数据内部的流形结构，并将其引入到目标函数中，使得类内邻近样本之间的距离最小化，不同类样本之间的间隔最大化。进一步，为了提高其计算速度，提出基于流形结构的最小二乘TWSVM(LS-MTSVM)算法。其次，我们通过采用聚类技术，提出基于聚类结构的TWSVM(STSVM)分类算法，其通过对数据在类内进行聚类，将获得的结构信息以协方差矩阵的形式引入到分类算法的目标函数中，在保证各类数据都尽量围绕在其分类面周围的同时，使得同一类内数据分布更加紧凑。进一步，为了提高其计算速度，提出基于聚类结构的最小二乘TWSVM算法。此外，对于STSVM在处理非均衡数据时存在的问题对其进行改进，提出非对称型STSVM(AS-STSVM)算法。最后，在STSVM的基础上，构造了基于STSVM的特征选择算法(LP-STSVM)，该分类器只需求解一个线性规划，在保证得到与STSVM相当的分类性能以及较快的计算速度上，此方式还减少了输入空间的特征数，对于非线性问题，其可以减少核函数数目。通过在机器学习标准数据集、图像数据和雷达辐射源数据上的实验验证了本文所提方法的有效性以及在工程应用中的潜在价值。关键词：孪生支持向量机流形学习聚类最小二乘孪生支持向量机特征选择 AbstractIIIAbstractTwinsupportvectormachine(TWSVM)removestheconstraintsoftheparallelseparatinghyperplaneoftraditionalSVM.ItdeterminesthetwononparallelhyperplanesbysolvingtworelatedSVM-typeproblems,suchthatitscomputingcostinthetrainingstageis1/4ofstandardSVM.However,TWSVMdoesnottakeintoconsiderationoftheinformationofdatadistribution.Forsomedatawithcomplexlydistribution,TWSVMcannotmakeeffectiveclassification.Therefore,manifoldlearningandclusteringtechnologyareintroducedinthisthesistoimprovetheperformanceofTWSVM.Firstly,amanifoldstructure-basedTwinSVM(MTSVM)isproposed,whichtakethemanifoldstructureofdataintotheobjectfunctionofTwinSVMfromtheperspectiveofmanifoldlearning.Itassumesthatthedataneedtobeprocessedaresampledfromapotentialmanifoldandobtainstheinnermanifoldstructureofdatabyestablishingwithin-classscattermatrix.Itthenintroducesthestructureinformationintotheobjectfunctiontominimizethedistancesbetweentheadjacentwithin-classsampleswhilemaximizingthemarginsbetweensamplesfromdifferentclasses.Further,amanifoldstructure-basedleast-squareTwinSVM(LS-MTSVM)ispresentedinordertoimprovethecomputingspeed.Secondly,theclusteringtechnologyisemployedtodesignaclusteringstructure-basedTwinSVM(STSVM)classifier.Byclusteringthedatawithintheclass,thismethodintroducestheobtainedstructureinformationintotheobjectfunctionofTWSVMintheformofcovariancematrix,sothatthedatawithinthesameclassesisdistributedmorecompactwhilethedataofeachclassesaresurroundingitshyperplaneascloselyaspossible.Thenaclusterstructure-basedleast-squareTwinSVM(LS-STSVM)isproposedinordertoimprovethecomputingspeed.Furthermore,todealwithunbalanceddata,thedesignofasymmetricSTSVM(AS-STSVM)isalsopresented.Atlast,basedonlinearprogram,afeatureselectionmethodforSTSVM(LP-STSVM)isiscussed,whichonlyneedstosolvetwosetsoflinearequations.ThemethodcanobtaincomparableclassificationperformancetostandardSTSVM,whilehavinghighercomputingspeedandbettersuppressionofinputfeatures.Meanwhile,itcanreducethenumberofkernelfunctionsfornonlinearclassificationproblems. IVAbstractThevalidityandpotentialvalueinengineeringapplicationsoftheproposedalgorithmsaresupportedbytheexpetimentalresultsonmachinelearningbenchmarkdatasets,imagedatasets,aswellasrealradaremitterdatasets.Keywords:TwinSVMManifoldLearningClusteringLeastSquareTwinSVMFeatureSelection 目录V目录摘要.................................................................IAbstract.......................................................................................................III目录...........................................................................................................V第一章绪论.................................................................................................11.1研究背景及意义............................................................................................11.2国内外研究现状............................................................................................21.2.1支持向量机分类算法研究现状..........................................................21.2.2基于支持向量机的特征选择研究现状...............................................41.3论文主要章节及工作安排.............................................................................5第二章支持向量机算法概述.........................................................................72.1引言...............................................................................................................72.2支持向量机(SVM)算法.................................................................................82.3孪生支持向量机(TWSVM)算法...................................................................92.4本章小结.....................................................................................................10第三章基于流形结构的TWSVM分类算法....................................................113.1引言.............................................................................................................113.2基于流形结构的TWSVM分类算法..........................................................113.2.1流形学习概述...................................................................................113.2.2基于流形结构的TWSVM(MTSVM)...............................................133.2.3实验结果及分析...............................................................................173.3最小二乘MTSVM分类算法......................................................................203.3.1算法原理...........................................................................................203.3.2实验结果及分析...............................................................................223.4基于MTSVM的雷达辐射源个体识别.......................................................243.5本章小结.....................................................................................................26第四章基于聚类结构的TWSVM分类算法....................................................274.1引言.............................................................................................................274.2基于聚类结构的TWSVM分类算法..........................................................274.2.1聚类分析概述...................................................................................274.2.2结构正则化SVM..............................................................................284.2.3基于聚类结构的TWSVM(STSVM).................................................294.2.4实验结果及分析...............................................................................33 VI基于孪生支持向量机的特征选择与分类算法研究4.3最小二乘STSVM分类算法.......................................................................384.3.1算法原理...........................................................................................384.3.2实验结果及分析...............................................................................394.4非对称型STSVM分类算法.......................................................................424.4.1算法原理...........................................................................................424.4.2实验结果及分析...............................................................................434.5基于STSVM的雷达辐射源个体识别........................................................474.6本章小结......................................................................................................48第五章基于STSVM的特征选择算法...........................................................495.1引言.............................................................................................................495.2基于支持向量机的特征选择.......................................................................505.2.1SVM-RFE特征选择算法...................................................................505.2.2基于线性规划SVM的特征选择......................................................505.2.3基于正则化技术的TWSVM特征选择............................................515.3基于线性规划STSVM(LP-STSVM)的特征选择........................................525.3.1算法原理...........................................................................................525.2.3实验结果及分析...............................................................................535.3本章小结......................................................................................................56第六章总结与展望.....................................................................................576.1本文总结......................................................................................................576.2未来展望......................................................................................................57致谢.........................................................................................................59参考文献....................................................................................................61作者在读期间的研究成果.............................................................................65 第一章绪论1第一章绪论1.1研究背景及意义随着信息技术和信息网络的飞速发展，信息产生和传播的速度迅速提高，人们可以很方便的获取和存储大量数据。面对这些大规模的海量数据，传统的数据分析工具只能进行一些表层的处理，而不能获得数据之间的内在关系和其中隐含的信息，这就极大的影响了人们对信息的有效利用。面对这些问题，将现代计算机的高性能与人工智能相结合的方法应运而生，其中基于人工智能、机器学习、模式识别、统计学的数据挖掘技术，被认为是解决上述问题的一种重要方法，并[1]显示了强大的生命力，其对数据的处理过程通常包括以下几个步骤：1)信息获取。通过传感器或其他信息获取装置将语音、图像、基因、蛋白质等物理输入转换为数字信号。2)数据预处理。对上一步获得的原始数据进行一些必要的处理，从中获得需要的数据。例如，原始收集的数据在收集过程中由于气候、温度和人工因素等影响往往伴随着很多噪声，一些有用的信号就会被湮没在噪声中，从而导致数据分析的结果出现偏差，因此就需要对这些原始数据进行降噪处理。另外在第一步中获得的原始数据中也可能夹杂着一些对识别无用的信息，例如对人脸进行识别时，采集到的人脸图像可能存在于一个比较复杂的背景中，从这些复杂背景中分割出有效区域也是一个必要的数据预处理过程。3)数据特征选择和提取。在样本有限的情况下，冗余特征的存在会导致分类性能变差，因此进行有效的特征选择是模式识别的核心问题之一。特征提取与选择的基本任务是研究如何从众多特征中挖掘出那些对分类识别最有效的特征，从而提高分类器预测性能及学习速度，达到只需要极少数特征就可以获得最佳分类性能的效果。4)分类器设计和分类决策。模式识别的目的就是通过已知数据的相关信息来建立一种分类器模型和分类决策算法，并且能够根据这种模型和学习算法来有效的实现对未知数据的预测，其在模式识别过程中起着至关重要的作用。图1.1给出了模式识别的流程图。在模式识别的整个过程中，特征维数约减和分类器设计是研究的重点。多年来，通过数学、信息学和计算机科学等领域专家和学者的不懈努力，模式识别研究特别是分类器设计的研究已经取得很大的进展。图1.1模式识别流程图 2基于孪生支持向量机的特征选择与分类算法研究本文从特征选择和分类识别两方面出发，研究了基于支持向量机的特征选择和分类算法。1.2国内外研究现状1.2.1支持向量机分类算法研究现状[2][3]支持向量机(SupportVectorMachine，SVM)是近年来在模式识别与机器学习领域中出现的新工具，它是由Vapnik等人于1995年基于统计学习理论提出的一种新的机器学习方法，其是以VC维理论和结构风险最小化原则为基础的。由于SVM具有简洁的数学形式、直观的几何解释和良好的泛化能力等优点，避免了神经网络中的局部最优解问题，并有效克服了“维数灾难”，因此受到了广泛的关注，[3][4][5][6]而且成功应用到了语音识别，人脸识别，手写体识别，文本分类等多种领域。尽管SVM因其结构简单、泛化能力好等优点而得到广泛的研究和应用，但是，传统的SVM侧重于类间的可分性，其分类面仅反映了少数支持向量所包含的局部距离信息，并没有用到数据内部所包含的大量丰富的结构信息，因此，许多学者在这一方面做了深入研究，提出了一种全新的设计分类器的视角，即一个合理的分类器应当对数据的结构信息足够敏感。这些算法大致上可以分为两个方向，一种是基于流形学习假设的数据建模，其假设数据在输入空间采样于一个潜在的子流形上，比较有代表性的是Belkin等人于2004提出的拉普拉斯支持向量机[7](LaplacianSupportVectorMachine，LapSVM)，其将传统SVM与拉普拉斯映射[43](LaplacianEigenmap，LE)结合起来，通过对每类数据样本建立拉普拉斯图来获得数据的流形结构信息，并以正则项的形式将其嵌入到传统SVM分类模型中去。[44]进一步，通过用LE的线性近似，即局部保持投影(LocalPreservingProject，LPP)来代替其本身，文献[8]提出一种最小类局部保持方差支持向量机(MinimumClassLocalityPreservingVarianceSVM，MCLPVSVM)分类算法，并通过实验验证此方法可以得到更好的分类结果。在此基础上，2011年Wang等人提出基于邻域保持[9]限制的支持向量机(SVMwithNeighborhoodPreservingConstraint，NPC-SVM)，其核心思想是通过引入类内流形结构，使得分类器在最大化类间间隔的同时最小化类内邻近样本之间的距离，从而达到更优的识别效果。另外一种挖掘数据结构信息的途径则是基于聚类假设的数据建模，其假设数据样本由不同的聚类组成，基于此假设产生了一系列最大化间隔分类器，例如椭[10][11]圆核机器(EllipsoidalKernelMachine，EKM)、最大概率机器(Minimax[12]4ProbabilityMachine，MPM)、最大-最小间隔机器(Max-MinMarginMachine，M)。文献[13]提出了一种基于结构的最大间隔机器(StructuredLargeMarginMachine， 第一章绪论3SLMM)，该算法采用一些半监督的聚类技术来挖掘数据内部隐藏的结构信息，并通过求解一个二阶锥规划来获得超平面参数。在此基础上，2010年Xue等人提出[14]基于结构正则化的支持向量机(StructuralRegularizedSVM，SRSVM)，其首先对数据在类内进行聚类，将获得的结构信息以协方差矩阵的形式引入到传统SVM分类算法的目标函数中，在保证数据类内分布更加紧凑的同时，实现数据类间间隔最大化。为了降低SVM计算开销，2001年，Mangasarian等人提出了近似支持向量机[15]分类器(ProximalSVM，PSVM)，其通过求解方程组的形式来代替SVM求解二次规划问题。实质上，在保证得到最大间隔的前提下，PSVM是用两个平行平面来拟合两类样本。基于PSVM思想，2006年，Mangasarian和Wild提出了基于广[16]义特征值的多平面近似支持向量机(GeneralizedEigenvalueProximalSVM，GEPSVM)，该算法摒弃了PSVM平行约束的条件，其核心思想是用两个非平行的超平面来分别拟合两类样本，使得每个超平面距离本类样本尽可能近，而距离它类样本尽可能远，通过求解两个广义特征值问题来获得分类超平面。2007年，受[17]此思想启发，Jayadeva等提出名为孪生支持向量机(TwinSVM，TWSVM)的非平行平面分类器，类似于GEPSVM，该分类器为两类数据各自构造一个分类面，使得每类数据尽量围绕在其分类面周围，但是和GEPSVM不同的是，TWSVM是通过求解两个形如SVM的二次规划问题来获得分类模型，并能将训练时间缩短到原SVM的1/4。虽然TWSVM的发展时间较短，但是由于它的产生基于GEPSVM和标准SVM，归根结底是基于统计学习理论的，因此具有坚实的理论和实践基础，相继也出现了一些新的变种算法。文献[18]对TWSVM引入平滑技术，提出了平滑TWSVM(SmoothTwinSVM，STWSVM)，将TWSVM中两个带有约束条件的二次规划问题转化为两个无约束的二次规划问题。2009年，Kumar和Gopal根据最小二乘支持向量机和近似支持向量机的思想，对TWSVM的约束条件进行修改，提[19]出了最小二乘TWSVM(LeastSquareTwinSVM，LSTSVM)，以降低原TWSVM[20]算法的计算量。2010年，Wang等提出一新方法，直接利用牛顿法在primal形式下求解TWSVM优化问题，而不利用拉格朗日乘子转化为对偶形式。针对TWSVM[21]只考虑到经验风险而忽略结构风险的问题，Shao等人于2011年提出有界孪生支持向量机(TwinBoundedSVM，TBSVM)，其通过引入正则项来最小化结构风险，并采用超松弛迭代法来求解二次规划问题。Chen等人在文献[22]中提出一种新型的基于最小类内方差的递归投影TWSVM(ProjectionTwinSVM，PTSVM)分类算法，其主旨是通过对每类样本各自寻找一个投影方向，使得投影后的样本更具可[23]分性。2011年，Ye等人提出基于凸最小化的局部TWSVM(LocalizedTwinSVMviaConvexMinimization，LCTSVM)，该算法对孤立点不敏感，且其超平面参数是 4基于孪生支持向量机的特征选择与分类算法研究通过求解一对线性方程获得，降低了计算复杂度。1.2.2基于支持向量机的特征选择研究现状在机器学习领域，特征选择就是从对象已有的特征中，筛选出一个适当的子集，使得该特征子集能很好的用于最终的学习目的。特征选择对于提高学习效果是非常关键的，恰当的算法可以消除不相关或者冗余的特征，减少数据维数，削减分类过程的计算量，降低分类所需时间。因此，特征选择方法一直是机器学习领域的重点和难点，其在神经网络、生物医学，目标识别等各方面都有着重要的研究价值和应用需求。至今为止，很多学者从不同角度对特征选择进行定义，其中，比较经典的定[24]义是：从给定的原始N个特征中选择一个M维的特征子集，使得该子集在原集合所有元素个数为M的子集中对某种评价标准最优，其中M事先给定，且MN。[25]一个良好的样本特征应该具备以下四个条件：1)可区分性好，对于不同类的样本来说，其特征应有明显差异；2)可靠性，对于同类样本，特征值应比较接近；3)独立性好，所选择的特征彼此不相关；4)数量少，要含有尽可能少的特征个数。早期的特征选择研究通常集中于统计学及信号处理问题，其假定特征之间相互独立，而且一般涉及的特征较少。然而，由于信息技术的飞速发展，人们可以很方便的获取和存储海量的大规模数据，对这些大规模数据的特征选择使得已有的特征选择算法受到严峻挑战，鉴于此，机器学习领域众多学者开始致力于特征选择问题的研究。近年来，特征选择研究呈现出综合性和多样化的趋势。各种新型的评估标准[29]和搜索算法被特征选择领域的研究人员所采用，比如特征集的模糊熵评价，神[28][26,27]经网络剪枝法，支持向量机的评估标准等。另外关于特征选择算法的融合性[30]研究也成为研究中的热点，比如关于Filter方法和Wrapper方法结合的研究，多算法的结合互补算法，有监督和无监督算法的融合等都是热门的研究方向。SVM作为机器学习中一种重要的分类器，得到广泛的应用，研究人员基于SVM将特征选择和分类融合在一起，通过利用一定的特征选择标准减少并优化支持向量，达到获得最佳特征组合的目的，并取得一定的研究成果。在研究支持向[31]量机几何特性的基础上，Hermes等人于2000年提出了一种专门针对SVM的特征选择方法（简称L-J算法），其是以数据点到分类超平面的距离函数的梯度与各[26]个坐标轴的夹角作为衡量特征重要性的指标，进而筛选出有效特征。Weston等基于SVM提出寻找具有最小留一法误差界的特征子集，并通过梯度下降法代替贪[32]婪算法，分别对模拟数据和真实数据进行了特征选择实验。Grandvalet等基于SVM的经验风险最小化，提出通过调节缩放因子进行特征选择。2002年，Guyon 第一章绪论5等人以样本在训练过程中权值大小的变化作为排序准则，提出基于SVM的递归特[33]征消除算法(SupportVectorMachineRecursiveFeatureElimination，SVM-RFE)。和一些明显采用特征选择策略（无论和分类算法相独立或是嵌入在分类过程中）的算法不同的是，从SVM分类器中直接获得稀疏解也可起到特征选择的作用。鉴于此思想，Bradley和Mangasarian于1998年提出基于凹最小化和支持向量机的[34]特征选择算法，并给出了SVM的l范数形式，其在文章中指出，l范数SVM可11以产生非常稀疏的解，对于一个线性分类器而言，稀疏解意味着分类超平面只取决于少量的输入特征，这就使得该算法在解决分类问题的同时完成特征选择的功能。在此基础上，2004年，Fung和Mangsarian提出通过快速牛顿算法来解决SVM[35]线性规划问题，从而实现特征选择。受l范数SVM思想的启发，Ye等人于20111[36]年提出基于正则化技术的TWSVM特征选择算法(FRTWSVM)，其通过将点到平面的距离以l范数度量，给出了TWSVM的线性规划形式，该算法在保留TWSVM1原有优势的同时，还具有速度快以及非常稀疏性的优势。1.3论文主要章节及工作安排本文立足于国防预研课题，研究了在雷达辐射源识别中分类器的设计问题，并在此基础上，将我们所提出的方法通过理论推导，在各公开数据集上验证了其有效性。论文内容共分为五章，各章内容安排如下：第一章首先介绍了本文的研究背景和意义，概括了国内外SVM分类及基于SVM的特征选择算法的研究现状，最后给出了论文的组织结构。第二章对支持向量机算法进行概述，简要介绍了支持向量机和孪生支持向量机算法，作为之后研究的基础。第三章针对TWSVM未考虑到数据结构信息的缺陷，通过引入流形学习的思想，提出基于流形结构的孪生支持向量机(MTSVM)分类算法，进一步为了节省计算时间，通过对MTSVM约束条件进行修改，提出最小二乘MTSVM(LS-MTSVM)算法，分别给出实验仿真结果；之后对雷达辐射源识别系统进行概述，给出辐射源识别的一般流程，并将提出的算法应用到辐射源识别场景中，验证了所提算法的有效性。第四章在第三章的基础上，通过另外一个角度解决TWSVM未考虑到数据结构信息的缺陷。首先概述了基于结构正则化的SVM分类方法，并将其思想推广至TWSVM中，提出了基于聚类结构的孪生支持向量机(STSVM)分类算法，进一步为了节省计算时间，提出最小二乘STSVM(LS-STSVM)算法，此外，还提出了非对称型STSVM(AS-STSVM)分类算法，分别给出实验仿真结果，然后与上一章对 6基于孪生支持向量机的特征选择与分类算法研究应将其应用在辐射源个体识别中。第五章在STSVM的基础上，结合线性规划SVM思想，构造了基于STSVM的特征选择算法(LP-STSVM)，该分类器只需求解一个线性规划，在保证得到与STSVM相当的分类性能以及较快的计算速度上，此方式还减少了输入空间的特征数，对于非线性问题，其可以减少核函数数目。第六章全面总结本文工作及成果，并指出下一步的研究方向。 第二章支持向量机算法概述7第二章支持向量机算法概述2.1引言模式识别的目的就是通过已知数据的相关信息来建立一种分类器模型和分类决策算法，即在完成对数据样本的预处理和特征选择后，必须借助优秀的分类器进行最后的分类决策，分类器的好坏将直接影响到最终识别结果的好坏。支持向[2,3]量机(SupportVectorMachine，SVM)是近年来在模式识别与机器学习领域中出现的新工具，它是由Vapnik等人于1995年基于统计学习理论提出的一种新的机器学习方法，是以VC维理论和结构风险最小化原则为基础的。和其他传统的分类方法比，SVM具有以下几个优势：1)SVM以统计学习理论为理论依据，克服了传统神经网络学习中靠经验和启发的先验成分等缺点。2)SVM遵循结构风险最小化原则，不同于传统分类算法的经验风险最小化原则，提高了置信水平，因而具有较强的泛化能力。3)SVM通过求解一个二次规划问题来获得分类模型，可得到全局最优解，避免了神经网络等方法的“过学习”和局部最优解问题。4)对于非线性分类，SVM通过将其映射到高维线性特征空间，来实现原低维空间中的不可分问题，并通过构造核函数，有效克服了特征空间中的“维数灾难”问题。鉴于以上优点，SVM自被提出以来，就受到了广泛的关注，而且成功应用到[3][4][5][6]了语音识别，人脸识别，手写体识别，文本分类等多种领域。传统SVM是通过一个二次规划问题来获得超平面参数，对于大规模数据的求解就显得尤为耗时，为了降低SVM计算开销，2001年，Mangasarian等人提出了[15]近似支持向量机分类器(ProximalSVM，PSVM)，其通过求解方程组的形式来代替SVM求解二次规划问题。实质上，在保证得到最大间隔的前提下，PSVM是用两个平行平面来拟合两类样本。基于PSVM思想，2006年，Mangasarian和Wild[16]提出了基于广义特征值的多平面近似支持向量机(GeneralizedEigenvalueProximalSVM，GEPSVM)，该算法摒弃了PSVM平行约束的条件，其核心思想是用两个非平行的超平面来分别拟合两类样本，使得每个超平面距离本类样本尽可能近，而距离它类样本尽可能远，通过求解两个广义特征值问题来获得分类超平[17]面。2007年，受此思想启发，Jayadeva等提出名为孪生支持向量机(TwinSVM，TWSVM)的非平行平面分类器，其问题归结为求解两个形如SVM型的二次规划，因此，计算开销缩短到原SVM的1/4，并在大多数情况下其识别结果都要优于 8基于孪生支持向量机的特征选择与分类算法研究GEPSVM。本章从平行平面和非平行平面的角度出发，对支持向量机算法做一个简要的概述，而基于支持向量机的特征选择算法会在第五章做简要介绍。2.2支持向量机(SVM)算法[2,3]SVM是Vapink等人根据统计学习理论中结构风险最小化原则提出的，其基本思想是构造一个超平面作为分类判别平面，使两类数据样本之间的间隔最大。其最优分类面的思想可借助图2.1所示的二维平面的情况来说明。其中实心和空心的圆圈分别代表正类样本和负类样本，位于两类样本中间的实线H即为分类线，H、H两条直线分别经过各类中离分类线最近的样本，且其平行于分类线H，它12们之间的距离即为分类间隔。所谓最优分类线就是要求其不但能将两类样本正确分开，而且要使两类样本间的分类间隔最大，推广到高维空间，最优分类线就成了最优分类面。HHHH2H12H1图2.1SVM最优超平面示意图n对一组样本数据(x,y),...,(x,y),xR,y{1,1}，SVM对应的分类面方程11mm为：(wx)b0(2-1)最优超平面的计算问题可以描述为如下有约束的二次优化问题：m12minwCiwb,2i1stywx..b1(2-2)iii0,i1,,mi其对偶问题为：mmm1minyyijijxxijj2i1j1j1(2-3)mst..yii0,0iCi,1,,mi1 第二章支持向量机算法概述9上述问题中，为松弛参数，用来衡量对数据x的误分类度；C为惩罚项；iii*为对应的拉格朗日乘子，这是一个二次函数寻优问题，存在唯一解，若为最优im***解，则有wiyixi；b是分类阈值，解上述问题后得到的最优分类面函数为：i1m**f(x)sgn{(wx)b}sgn{iyi(xix)b}(2-4)i1在线性不可分的问题上，Vapnik等人成功引入核空间理论，将低维输入样本nxR通过非线性函数映射到高维空间中得到(x),(x),...,(x)。可以证i12m明，如果选用适当的映射函数，大多数输入空间线性不可分问题在核特征空间中可以转化为线性可分问题，常见的核函数有线性核函数、高斯核函数、多项式核函数以及径向基核函数。2.3孪生支持向量机(TWSVM)算法[17][16]TWSVM算法是Jayadeva等人在GEPSVM的启发下提出的。我们知道传统SVM使用平行平面作为决策边界，而TWSVM是一非平行平面分类器，它的目标是为两类数据各自构造一个分类超平面，使得每个超平面距离本类样本尽可能近，而距离它类样本尽可能远，并通过求解两个形如SVM的二次规划问题来获得[19]分类模型。图2.2所示为传统SVM与TWSVM分界面的比较。(a)SVM(b)TWSVM图2.2传统SVM与TWSVM分界面比较mn对一组样本数据XR，假设+1类有m个样本，-1类有m个样本，将这两12类样本分别用矩阵A和B表示，不同于SVM的平行分类边界，TWSVM的m1nm2n目标是在n维空间中寻找两个非平行的超平面：T(1)(1)T(2)(2)xwb0,xwb0(2-5)可以通过求解如下优化问题来获得超平面参数：1(1)(1)2TminAwebceq112TWSVM12(2-6)(1)(1)s.t.(Bweb)qe,q022 10基于孪生支持向量机的特征选择与分类算法研究1(2)(2)2TminBwebceq221TWSVM22(2-7)(2)(2)s.t.(Aweb)qe,q011其中c,c为惩罚项，e,e为元素全为1的列向量。式(2-6)和(2-7)的目标函数用平1212方距离来度量本类样本离本类超平面的距离，因此对其最小化可以保证本类样本离其超平面尽可能近，不等式约束可以理解为它类样本离超平面的距离至少为1。令H[Ae]，G[Be]，将式(2-6)、(2-7)转化成对偶形式：12T1TT1TDTWSVM1maxeG(HH)Gs.t.0c(2-8)212T1TT1TDTWSVM2maxeH(GG)Hs.t.0c(2-9)122超平面参数可以通过下式获得：(1)(2)wT1TwT1Tu(1)(HH)G,v(2)(GG)H(2-10)bbJayadeva将0c(i1,2,...,m)和0c(j1,2,...,m)对应的样本定义i12j21为支持向量，并在文章中表明，支持向量位于其对应的分类超平面上。从以上求解过程中可以看出除了约束条件不包含所有样本外，TWSVM的每个凸优化问题都接近于传统的SVM。如果两类样本数目相等，则TWSVM的计算333时间为2(m2)m4，而传统SVM的计算时间为m，则TWSVM可以得到较传统SVM快4倍的速度。(1)(1)(2)(2)n得到超平面参数(w,b)和(w,b)之后，对于任意的一个样本xR，我们认为它属于距其最近的平面所在的类，分类面判别函数为：T(l)(l)Classiargminxwb(2-11)l1,2T(l)(l)其中表示样本x到超平面xwb0,l1,2的垂直距离。同样，通过引入核函数，Jayadeva将TWSVM推广至线性不可分问题的求解。2.4本章小结本章分别介绍了传统SVM和TWSVM分类算法，对各算法的基本思想和基本流程进行了简单概述，为本文后续工作打下基础。后续章节中，我们针对TWSVM存在的结构信息缺失和特征冗余的缺陷，分别从分类器设计和特征选择两个方面对其进行改进，并研究了其在雷达辐射源识别研究中的应用。 第三章基于流形结构的TWSVM分类算算法11第三章基于流形结构的TWSVM分类算法3.1引言2007年，Jayadeva等人在GEPSVM的启发下提出TWSVM分类算法，它摒弃了传统SVM平行约束的条件，使用一对非平行的超平面作为分类平面。它的目标是为两类数据各自构造一个分类超平面，使得每个超平面距离本类样本尽可能近，而距离它类样本尽可能远，并通过求解两个形如SVM的二次规划问题来获得分类模型，将训练时间缩短至传统SVM的1/4。虽然TWSVM的发展时间较短，但是由于它的产生是基于GEPSVM和标准SVM的，具有坚实的理论和实践基础，并且其和SVM相比存在种种优势，因此近年来TWSVM已得到广泛的应用。然而，原始TWSVM并没有考虑到数据的分布信息，对于一些分布复杂的数据，TWSVM就不能进行有效的分类识别。而在实际问题中，不同类的数据往往包含有不同的结构信息，一个优秀的分类器就需要对数据的结构信息足够敏感。针对此问题，本章从流形学习进行考虑，通过将数据的流形结构引入至分类目标函数中，提出基于流形结构的TWSVM，其主旨是假设所处理的数据采样于一个潜在的流形上，通过建立类内散度矩阵，获得数据内部的流形结构，并将其引入到目标函数中，使得类内邻近样本之间的距离最小化，不同类样本之间的间隔最大化。进一步，为了提高其计算速度，提出基于流形结构的最小二乘TWSVM，并在各公开数据集上验证了所提出算法的有效性。3.2基于流形结构的TWSVM分类算法3.2.1流形学习概述随着计算机与数字网络的普遍适用，人们获取信息的能力已今非昔比，可以获得的信息量越来越大，信息数据的维数也越来越高，有价值的信息淹没在大规模的海量高维数据之中，因此对高维数据进行维数约减，发现数据的内在规律的需求变的更为迫切。通常情况下，用于数据分析的线性和非线性降维技术都被认为是流形学习的范畴，自2000年以来，流形学习的研究受到机器学习、模式识别、数据挖掘以及其它领域研究人员的广泛关注。流形的概念是欧式空间的推广，一般可认为是局部具有欧式空间性质的空间，即流形在其每一点的邻域都和欧式空间的一个区域同胚，因此流形上每点处都存在一个邻域可以用局部坐标系来刻画。直观来看，可以把流形看作是一块块“欧式空间”粘起来的结果，而欧式空间是流形的特例。 12基于孪生支持向量机的特征选择与分类算法研究[1]有了对流形的定义，我们就可以形式化的概括流形学习这一维数约减过程：假设数据是均匀采样于一个高维欧式空间中的低维流形，流形学习就是找到高维空间中的低维流形，并求出相应的嵌入映射，以实现数据的维数约减。它是从观测到的现象中去寻找事物的本质，找到产生数据的内在规律。近年来，在流形学习领域学者的不懈努力与研究下，对流形学习的研究取得[39]了大量成果，大体来说这些研究可以分为两类：全局算法和局部算法。全局算法是指数据集中的每一个数据点都与整个数据集中其他所有数据之间建立一种连[41]接图关系，如费舍尔线性判别分析(FisherDiscriminantAnalysis，FDA)，等度规[40]映射算法(IsometricalMapping，Isomap)；局部算法则是基于保持流形的局部几何特性，外围观测空间近邻数据所具有的局部几何特性在内在低维空间得以保持，[42]如局部线性嵌入算法(LocallyLinearEmbedding，LLE)，拉普拉斯映射[43][44](LaplacianEigenmap，LE)，局部保持投影(Locality-PreservingProjection，LPP)，[45]局部费舍尔判别分析(LocalFisherDiscriminantAnalysis，LFDA)，在本节中我们仅对LFDA做详细描述。LFDA是Sugiyama于2007年提出的一种多模态数据的降维算法，其针对FDA未考虑到数据的局部信息的缺陷，结合LPP的思想对FDA进行改进。FDA作为模式识别的经典算法，其基本思想是为数据选择一个最佳投影方向，从而使得样本在该方向进行投影后，可以获得最小的类内离散度和最大的类间离散度，即样本在该投影空间中具有最佳的可分离性。对一组样本数据n(x,y),...,(x,y),xR,y{1,2,...,c}，每类有n个样本，分别定义其类内散度矩11mml(w)(b)阵S和类间散度矩阵S为：cc(w)T(b)TSi:yil(xil)(xil)，Snl(l)(l)(3-1)l1l1其中i:yil中的下标iy:il代表所有类标为l的样本，l为类l内所有样本的均值，为所有样本的均值，即：mc111lxi，xinll(3-2)nli:yilmi1ml1将FDA类内和类间散度矩阵写成pointwise的形式：mm(w)1(w)T(b)1(b)TSWi,j(xixj)(xixj)，SWi,j(xixj)(xixj)(3-3)2i,j12i,j1111ifyylifyylij(w)ij(b)mn其中Wi,jn，Wi,jl。l10ifyiyjifyiyjm~(w)基于上述pointwise形式，Sugiyama定义局部类内散度矩阵S和局部类间散 第三章基于流形结构的TWSVM分类算算法13~(b)度矩阵S为：~(w)1m~(w)~(b)1m~(b)TTSWi,j(xixj)(xixj),SWi,j(xixj)(xixj)(3-4)2i,j12i,j111~(w)Ai,jifyyl~(b)Ai,j()ifyiyjl其中Wij，Wmnl，A为相似度i,jnli,j10ifyiyjifyiyjm~(w)矩阵，在这里仅调节类内样本的权值，这就意味着，同一类内相距较远的样本对S~(b)和S的影响就较小。若对所有的样本A都为1，则LFDA退化为FDA。关于A的选取一般有如下ij三种方式：1如果i和j相连1)1-0形式。Aij。0其他2xixjAe如果i和j相连2)热核。ij，其中为控制矩阵A衰减度的参0其他数，0。2xxij(t)(t)3)局部尺度。Aexp()，xx，其中x代表x的第t个ijiiiiiij近邻，经验值t7。3.2.2基于流形结构的TWSVM(MTSVM)对于TWSVM而言，原始TWSVM的分类超平面仅是建立在离本类样本尽可能近的同时以至少为1的距离远离它类样本的基础上获得的，并没有考虑到数据的分布信息，对于一些分布复杂的数据，TWSVM就不能进行有效的分类识别。针对此问题，受NPC-SVM思想的启发，我们提出一种新型的TWSVM分类算法，即基于流形结构的TWSVM(ManifoldTwinSVM，MTSVM)，在该算法中，不同于NPC-SVM，我们通过将TWSVM和LFDA结合起来，建立局部类内散度矩阵，获得数据内部的流形结构，并将其引入到目标函数中，使得类内邻近样本之间的距离最小化，不同类样本之间的间隔最大化。mn对一组样本数据XR，A为mn的+1类样本矩阵，B为mn的-1类样12本矩阵，MTSVM的目标优化函数为：1(1)(1)2T1(1)T(1)(1)2minAwebceq(wSwb)112AMTSVM122(3-5)(1)(1)s.t.(Bweb)qe,q022 14基于孪生支持向量机的特征选择与分类算法研究1(2)(2)2T1(2)T(2)(2)2minBwebceq(wSwb)221BMTSVM222(3-6)(2)(2)s.t.(Aweb)qe,q011其中c，c为惩罚参数，q为松弛向量，e，e为元素全为1的列向量，S，S分1212AB别为正负两类样本的类内散度矩阵。对MTSVM1我们做如下分析，正类样本A的散度矩阵可表示为：m1TSA[xiMijxj][xiMijxj]i1xjNK(xi)xjNK(xi)m1m1m1m1TTT(3-7)[xixi(MijMji)xixjMikMkjxjxk]i1j1j1k1m1m1m1T(ijMijMjiMikMkj)xixji1j1k1TAPAT其中P(IM)(IM)，N(x)代表样本x的K个近邻所组成的集合。在这里Kii[40]参考LFDA，我们采用了相似矩阵M来保留数据内部邻近样本之间的局部结构信息，M的定义如下所示：21xxijexp()xN(x)或者xN(x)(t)(t)iKjjKiMijD(3-8)iiij0其他(t)(t)其中DiiMij，i(j)为样本xi(xj)与其第t个近邻之间的距离，在本文实验j中我们选t7。MTSVM1对应的拉格朗日问题如下所示：1(1)(1)2T1(1)T(1)(1)2LAebceq(Sb)112A22(3-9)T(1)(1)T((Beb)qe)q22TT其中(,,...,)和(,,...,)为拉格朗日乘子向量，KKT条件为：12m212m2LT(1)(1)T(1)A(Aweb)BSw0(3-10)(1)1AwLT(1)(1)T(1)e(Aweb)eb0(3-11)(1)112bLce0(3-12)12q(1)(1)(Bweb)qe,q0(3-13)22T(1)(1)T((Bweb)qe)0,q0(3-14)22由于0，从式(3-12)我们可以得到0c。1结合式(3-10)，(3-11)，可得：T(1)(1)TASA0BTAe1(1)(1)T0(3-15)e1b01be2 第三章基于流形结构的TWSVM分类算算法15(1)wSA0令HAe，GBe,u，S，可以将式(3-15)改写为：12(1)101bTTT1T(HHS)uG0i.e.u(HHS)G(3-16)11利用式(3-9)及上述KKT条件，我们得到MTSVM1的对偶形式为：T1TT1TDMTSVM1maxeG(HHS)Gs.t.0c(3-17)2112同样，我们可以得到MTSVM2的对偶形式：T1TT1TDMTSVM2maxeH(GGS)Hs.t.0c(3-18)1222(2)SB0w其中为拉格朗日乘子，S，超平面系数v通过下式获得：201(2)bT1Tv(GGS)H(3-19)2定义0c(i1,2,...,m)和0c(j1,2,...,m)为支持向量，其位于各i12j21自对应的分类超平面上。(1)(1)(2)(2)得到问题(3-5)、(3-6)的解(w,b)和(w,b)之后，对于任意的一个样本nxR，我们认为它属于距其最近的平面所在的类，分类面判别函数为：T(l)(l)Classiargminxwb(3-20)l1,2T(l)(l)其中表示样本x到超平面xwb0,l1,2的垂直距离。通过采用核方法，我们可以将MTSVM推广至非线性分类，假设输入空间的n样本xR,i1,2,...,m被某种非线性映射映射到某一特征空间得到i(x),(x),...,(x)，输入空间的内积形式在特征空间就可以用Mercer核表示为12mTK(x,x)(x)(x)，经过映射后核空间的超平面如以下所示：ijij(1)(1)(2)(2)K(x,C)ub0,K(x,C)ub0(3-21)其中CAB，K为选取的核函数，那么MTSVM在核空间中的目标函数可表示为：KMTSVM11(1)(1)21(1)TT(1)(1)2TminKMTSVM1KACu,eb1(uCSACub)ceq1222(3-22)(1)(1)s.t.(KBCu,eb2)qe2q0KMTSVM21(2)(2)21(2)TT(2)(2)2TminKBCu,eb2(uCSBCub)ceq2122(3-23)(2)(2)s.t.(KACu,eb1)qe1q0对于KMTSVM1，式(3-22)中S为正类样本A在高维空间投影后的类内邻近矩阵，A可将其表示为： 16基于孪生支持向量机的特征选择与分类算法研究m1m1m1TTSA[(xi)Mij(xj)][(xi)Mij(xj)](A)P(A)(3-24)i1j1j1T式(3-24)中P(IM)(IM)，对M的定义如下：1KiiKjj2KijxiNk(xj)或者exp{Dij[KiiKi(t)i(t)2Kii(t)][KjjKj(t)j(t)2Kjj(t)]xjNk(xi)Mij(3-25)0其他(t)(t)i(j)代表x(x)的邻近矩阵中的第t个近邻，和线性情况下相同，在本文实验中，ij我们选t7，DA为归一化因子。iijij同上述推导过程，将样本A用样本B替换，可得到样本B对应的类内散度矩T阵：S(B)P(B)。BKMTSVM1对应的拉格朗日问题为：1(1)(1)21(1)TT(1)(1)2TLK(A,C)ueb(u(C)S(C)ub)ceq1A1222(3-26)T(1)(1)T((K(B,C)ueb)qe)q22其对应的KKT条件为：LT(1)(1)TT(1)(1)KAC(,)((,)KACueb1)KBC(,)()CSA()Cu0(3-27)uLT(1)(1)T(1)(1)eKACu1((,)eb1)e2b0(3-28)bLce120(3-29)q(1)(1)(K(B,C)web)qe,q0(3-30)22T(1)(1)T((K(B,C)web)qe)0,q0(3-31)220,0(3-32)由于0，从式(3-29)中我们可以得到0c。1结合(3-27)和(3-28)，得到，T(1)T(1)TKAC(,)u()CS()C0uKBC(,)ATKAC(,)e1(1)(1)T0(3-33)eb01be12(1)Tu(C)S(C)0A定义QK(A,C)e,RK(B,C)e,z,S，则121(1)1b01TTT1T式(3-33)可写为：(QQS)zR0i.e.z(QQS)R。1111利用式(3-26)及上述KKT条件，我们得到KMTSVM1的对偶形式为：T1TT1TDKMTSVM1maxeR(QQS)Rs.t.0c(3-34)2112同样，我们可以得到KMTSVM2的对偶形式：T1TT1TDKMTSVM2maxeQ(RRS)Qs.t.0c(3-35)1222 第三章基于流形结构的TWSVM分类算算法17T(2)(C)S(C)0wB其中为拉格朗日乘子，S2，超平面系数z2(2)可通过下01bT1T式获得：z(RRS)Q。22(1)(1)(2)(2)得到问题(3-22)、(3-23)的解(u,b)和(u,b)之后，对于任意的一个样本nxR，我们认为它属于距其最近的平面所在的类，分类面判别函数为：(l)(l)ClassiargminK(x,C)ub(3-36)l1,2(l)(l)其中表示样本x到超平面K(x,C)ub0,l1,2的垂直距离。3.2.3实验结果及分析在本节实验中，我们分别将所提出的MTSVM分类算法在UCI机器学习数据[46][47]库和USPS手写体识别数据库上进行验证，并和前文所提到的SVM、GEPSVM、TWSVM和NPC-SVM分类算法进行对比。实验一UCI机器学习数据库在本节中，为了验证所提出MTSVM分类算法性能，将其在UCI机器学习数据库的10组数据上进行仿真实验，各数据详细描述于表3.1中。表3.1实验中所使用的数据集描述数据集特征维数样本个数类别数目Hepatitis155192Haberman30632Spectf267442Wdbc569302Pima76882Monk260162Sonar208602Votes435162Wine178133Tae15153对于每组数据，我们选其70%作为训练集，剩余的30%作为测试集。线性情况下，SVM、NPC-SVM算法中惩罚参数c，GEPSVM算法中正则项，TWSVM、iMTSVM算法中惩罚参数c、c均从集合2i9,...,9中选取，样本邻近数选自集122TT2合{3,4,...,20}；非线性情况采用高斯核K(x,x)exp(xx)，并且为了降低参数选择时间，除样本邻近数仍选自集合{3,4,...,20}外，其余参数均从集合i[48]10i3,...,3中选取。对于多类问题，采用“一对一”策略。所有算法中二次[49]规划问题均使用Mosek优化工具箱求解。我们从测试识别率、10次训练标准差和训练时间三方面来进行评价，10次独立实验的平均结果如下表3.2和3.3所示。表3.2各算法在UCI数据集上的性能比较（线性核）SVMGEPSVMTWSVMNPC-SVMMTSVM数据集test±std(%)test±std(%)test±std(%)test±std(%)test±std(%) 18基于孪生支持向量机的特征选择与分类算法研究Time(s)Time(s)Time(s)Time(s)Time(s)Hepatitis81.52±0.4472.61±4.3882.61±0.4582.17±0.4283.26±0.430.04100.00570.01130.04680.0423Haberman71.32±0.3171.43±0.4473.30±0.2571.54±0.2974.07±0.150.04420.00010.01600.11700.1136Spectf78.12±0.2525.63±0.3378.75±0.2578.62±0.2379.01±0.260.05720.02010.03760.10960.1548Wdbc96.35±0.0193.47±0.0597.29±0.0196.65±0.0297.29±0.0070.27320.00390.08630.34760.2706Pima77.74±0.0271.96±0.1077.78±0.0477.70±0.0777.78±0.040.42270.00350.10090.78190.5979Monk264.56±0.0660.50±0.0964.56±0.0764.56±0.0765.06±0.050.16920.01240.05630.36790.3012Sonar76.45±0.3074.84±0.3773.06±0.2876.42±0.2274.35±0.160.04390.02110.00960.09540.0438Votes94.85±0.0294.85±0.0296.00±0.0195.23±0.00495.77±0.010.10940.00490.04550.28520.3270Wine97.92±0.0497.92±0.0498.68±0.0298.30±0.0298.87±0.020.00560.00190.03130.06780.0403Tae54.44±0.2150.67±1.3954.89±0.3854.67±0.2452.89±0.380.00340.00010.00380.01430.0360表3.3各算法在UCI数据集上的性能比较（高斯核）SVMGEPSVMTWSVMNPC-SVMMTSVM数据集test±std(%)test±std(%)test±std(%)test±std(%)test±std(%)Time(s)Time(s)Time(s)Time(s)Time(s)Hepatitis83.26±0.1784.78±0.3685.43±0.4484.17±0.0285.43±0.260.14170.08810.04830.35680.1563Haberman71.21±0.1169.23±1.6171.43±0.1171.74±0.0973.41±0.040.16230.51000.22830.41700.2443Spectf79.38±0.0978.75±3.0780.00±0.1078.62±0.2380.12±0.150.15210.22510.47110.10960.4736Wdbc97.14±0.00896.47±8.0997.12±0.0196.99±0.0297.35±0.010.67051.45311.26962.34761.6688Pima76.65±0.0576.69±0.1676.61±0.0576.54±0.0776.70±0.050.56873.28660.99442.78192.2491Monk285.11±0.0584.44±3.3690.22±0.0892.56±0.0793.56±0.090.67560.55740.71971.36791.0831Sonar83.39±0.1982.26±0.2983.06±0.1782.42±0.2283.87±0.170.07910.17880.13540.29540.2828Votes97.74±0.0598.49±0.0198.30±0.0496.23±0.0495.85±0.020.02600.07310.10341.28520.7696Wine97.74±0.0598.49±0.0198.30±0.0498.30±0.1298.87±0.0090.02600.07310.10340.06950.0614Tae57.33±0.6558.67±0.4461.56±0.9862.67±0.0463.56±0.620.01610.04840.04940.05710.0429对上述结果进行分析，我们可以得到以下几个结论：1)在线性核情况下，由于GEPSVM是通过求解一对广义特征值问题来获得超平面参数，求解过程中涉及到矩阵的奇异性问题，因此对于部分数据，GEPSVM识别结果会出现偏差，如Spectf数据，和其他算法相比，其识别率低了至少55个百分点。而比较TWSVM和MTSVM算法可见，MTSVM的识别率在大部分情况下都要优于TWSVM，例如Haberman、Spectf、Monk2、Wine等数据，这是因为 第三章基于流形结构的TWSVM分类算算法19MTSVM通过类内散度矩阵的计算，将数据的流形结构引入至TWSVM目标函数中，从而弥补了原始TWSVM未考虑到数据结构信息的缺陷，在一定程度上提升了识别结果。2)在高斯核情况下，因为引入核函数的缘故，各算法与其在线性核下的结果相比，基本上都略有提升，尤其是Monk2数据，在引入高斯核之后，其识别结果提升了将近30个百分点。但是对于部分数据，如Pima数据，由于线性情况下参ii数范围选自集合2i9,...,9，而核函数下参数范围选自集合10i3,...,3，其参数范围和线性情况下相比略显粗糙，因此核情况下的识别结果可能会有少量偏差。3)在时间上，MTSVM的训练时间会略久于TWSVM，这是因为其在TWSVM的基础上还要引入散度矩阵的计算，势必会增加训练时间；但是和NPC-SVM相比，由于MTSVM是基于TWSVM提出来的，NPC-SVM是基于SVM的改进算法，而TWSVM的计算时间仅为传统SVM的1/4，所以和NPC-SVM相比，MTSVM有明显的时间上的优势。实验二USPS手写体识别数据库USPS数据库是美国邮政服务提供的一个手写体数字识别数据库，它包括从0到9的10类灰度图像，且灰度值已被归一化，每个数字包含有1100张像素为16×16的图片，图3.1给出了该数据的部分样本示例。图3.1USPS手写体识别数据库中部分样本示例在本实验中，我们从每类样本中随机抽取110幅图片组成数据集，并从中随机抽取10%、20%的数据分别作为训练集对MTSVM算法进行验证，实验中采用线性核。SVM、NPC-SVM算法中惩罚参数c，GEPSVM算法中正则项，TWSVM、iMTSVM算法中惩罚参数c、c均从集合2i9,...,9中选取，NPC-SVM、MTSVM12算法中样本邻近数选自集合{3,4,...,20}。由于USPS数据集是一个多类分类问题，在此我们采用“一对一”策略。各算法中二次规划问题的求解均采用Mosek优化工具箱。我们从测试识别率和训练时间两方面来考察，10次独立实验的平均结果如图3.2、3.3所示。 20基于孪生支持向量机的特征选择与分类算法研究1000.14SVMSVM95GEPSVMGEPSVM0.12TWSVMTWSVMNPC-SVM90NPC-SVMMTSVMMTSVM0.185）%80）s0.08（（率间75别时识练0.06试70训测650.04600.02555001212训练样本比例10%，20%训练样本比例10%，20%图3.2各算法在USPS数据库上的识别率比较图3.3各算法在USPS数据库上的训练时间比较通过在USPS手写体识别数据库上的实验，我们进一步证实了MTSVM分类算法的优越性，从图3.2、3.3中可以看出，随着训练集样本数目的增加，各算法识别率也略有提升，相应的训练时间也会加长。整体而言，和其他算法相比，在10%和20%的训练集上，MTSVM的识别结果要优于其他算法，且训练耗时小于NPC-SVM。3.3最小二乘MTSVM分类算法3.3.1算法原理[15]2009年，Kumar和Gopal根据近似支持向量机(ProximalSVM，PSVM)和最[50]小二乘支持向量机(LeastSquareSVM，LSSVM)的思想，通过对TWSVM的约[19]束条件进行修改，提出了最小二乘TWSVM(LeastSquareTwinSVM，LSTSVM)，将原TWSVM中凸优化问题的求解转变成线性方程组的求解，以降低原TWSVM算法的计算量。鉴于此，为期进一步提升MTSVM的计算速度，提高计算效率，在本节中我们提出最小二乘MTSVM(LeastSquareManifoldTwinSVM，LS-MTSVM)分类算法，其目标优化问题如下所示：1(1)(1)21(1)T(1)(1)2c1TminAweb(wSwb)qq1ALS-MTSVM1222(3-37)(1)(1)s.t.(Bweb)qe221(2)(2)21(2)T(2)(2)2c2TminBweb(wSwb)qq2BLS-MTSVM2222(3-38)(2)(2)s.t.(Aweb)qe11值得注意的是，上述优化问题中使用惩罚参数q的l-范数来代替式(3-5)、(3-6)2[19]中的l-范数，并将原惩罚参数权值c改为c2，这就省去了对q0的限制，这个1简单的修正就使得我们可以将问题(3-5)和(3-6)的解写成线性方程的形式，将等式约束条件代入到目标函数中，以上两个QP问题则变为： 第三章基于流形结构的TWSVM分类算算法211(1)(1)21(1)T(1)(1)2c1(1)(1)2minAweb(wSwb)eBweb(3-39)1A222221(2)(2)21(2)T(2)(2)2c2(2)(2)2minBweb(wSwb)e(Aweb)(3-40)2B11222(1)(1)对于LS-MTSVM1，对w和b求偏导，得到：T(1)(1)T(1)(2)(1)A(Aweb)cB(eBweb)Sw0(3-41)1122AT(1)(1)T(1)(2)e(Aweb)ce(eBweb)b0(3-42)111222将上式(3-41)、(3-42)写成矩阵形式，可得到：T(1)T(1)T(1)AwBwBSA0wAecBece0(3-43)T1(1)1T2(1)1T201(1)e1be2be2b(1)wSA0定义HAe，GBe，u，S，则式(3-43)可写为：12(1)101bTTTT1T11T(HHcGGS)ucGe0i.e.u(GGHHS)Ge(3-44)111212cc11同样，我们对LS-STSVM2进行求解，可获得超平面2的参数为：(2)wT1T11Tv(HHGGS)He(3-45)(2)21bc2c2SB0其中S。201从以上分析可以看出，线性LS-MTSVM仅通过求解两个(n1)(n1)维矩阵的逆就可以得到问题(3-39)、(3-40)的解，其中nm。(1)(1)(2)(2)一旦两个非平行平面参数(w,b)、(w,b)确定之后，对于任意的一个样n本xR，我们就可以通过判断它离两个超平面的距离来确定其类别。需要说明的是，LS-MTSVM并没有改变MTSVM中对于支持向量的定义，但是由于我们是对原始问题而非对偶问题求解，因此不能明确表示出支持向量的形式。同样，通过采用核函数，我们可以将LS-MTSVM推广至非线性分类，非线性条件下的目标函数为：KLS-MTSVM11(1)(1)21(1)TT(1)(1)2c1TminKACu,eb1(uCSACub)qq222(3-46)(1)(1)s.t.(KBCu,eb2)qe2KLS-MTSVM21(2)(2)21(2)TT(2)(2)2c2TminKBCu,eb2(uCSBCub)qq222(3-47)(2)(2)s.t.(KACu,eb1)qe1将等式约束代入到目标函数中，可得到： 22基于孪生支持向量机的特征选择与分类算法研究(1)uT1T11T(RRQQS)Qe(3-48)(1)12bc1c1(2)uT1T11T(QQRRS)Re(3-49)(2)21bc2c2T(C)S(C)0A其中QK(A,C)e,RK(B,C)e,S，12101T(C)S(C)0BS2。01(1)(1)(2)(2)n在超平面参数(u,b)、(u,b)确定之后，对于任意的一个样本xR，我们就可以通过计算其距两个分类超平面的距离，认为其属于距其最近的超平面所在的类。3.3.2实验结果及分析[51]本节中，将LS-MTSVM算法在UCI机器学习数据库和NDC数据集上进行验证，并和LSSVM、GEPSVM、LSTSVM及MTSVM进行比较。实验一UCI机器学习数据库本节中使用的UCI数据和3.2节中相同，在此就不再赘述。对于每组数据，我们选其50%作为训练集，剩余的50%作为测试集。线性情况下，MTSVM和LS-MTSVM算法中样本邻近数选自集合{3,4,...,20}，剩余所有涉及到的参数均从集合i2i9,...,9中选取；对于非线性情况，我们采用高斯核函数2TT2K(x,x)exp(xx)，并且为了降低参数选择时间，除MTSVM和LS-MTSVM算法中样本邻近数仍选自集合{3,4,...,20}外，其余所有参数均从集合i10i3,...,3中选取。对于多类问题，采用“一对一”策略。我们从测试识别率、10次训练标准差和训练时间三方面来进行评价，10次独立实验的平均结果如下表3.3和3.4所示。表3.3各算法在UCI数据集上的性能比较（线性核）LSSVMGEPSVMLSTSVMMTSVMLS-MTSVM数据集test±std(%)test±std(%)test±std(%)test±std(%)test±std(%)Time(s)Time(s)Time(s)Time(s)Time(s)Hepatitis80.39±0.1177.79±0.1980.39±0.1181.26±0.1380.52±0.100.00430.01430.00470.04230.0143Haberman74.9±0.0773.01±0.0675.82±0.0375.95±0.0575.88±0.050.01790.00010.00010.04140.1141Spectf80.68±0.0426.47±0.4080.75±0.0580.62±0.1380.75±0.040.01560.02690.00220.10860.1006Wdbc96.16±0.0292.54±0.0296.55±0.0296.65±0.0296.20±0.020.03380.00180.02680.30760.2453Pima76.48±0.0275.83±0.0276.61±0.0276.70±0.0776.74±0.02 第三章基于流形结构的TWSVM分类算算法230.04160.00150.00130.68090.2858Monk266.10±0.0361.73±0.1066.10±0.0365.96±0.0766.10±0.030.02630.02390.00220.30790.2505Sonar78.08±0.0972.21±0.1670.87±0.1970.42±0.2270.67±0.110.00790.05890.00360.08540.0197Votes94.19±0.00793.87±0.0295.3±0.0194.23±0.00489.22±3.470.02770.00240.00190.28520.1504Wine97.53±0.0296.97±0.0297.87±0.0298.30±0.0198.54±0.020.00120.00020.00010.00710.0069Tae51.33±0.4347.87±0.5751.33±0.4352.27±0.1452.00±0.530.00090.000080.00010.00930.0051表3.4各算法在UCI数据集上的性能比较（高斯核）LSSVMGEPSVMLSTSVMMTSVMLS-MTSVM数据集test±std(%)test±std(%)test±std(%)test±std(%)test±std(%)Time(s)Time(s)Time(s)Time(s)Time(s)Hepatitis82.26±0.0383.12±0.0681.95±0.0682.73±0.0982.73±0.080.06560.09560.02120.14550.0882Haberman75.99±0.0575.82±5.4375.82±0.0574.71±0.0676.14±0.090.08230.11050.06470.42120.2938Spectf80.21±0.3087.97±0.2379.85±0.1280.45±0.1081.20±0.130.09520.09730.05330.39460.2838Wdbc95.96±0.1894.72±6.4796.06±0.0397.46±0.0197.02±0.020.21000.74940.22230.70780.5023Pima74.07±0.2675.52±3.4572.50±0.0277.12±0.0377.01±0.020.52361.15350.41581.23101.0735Monk288.93±0.0876.67±0.0588.83±0.0489.27±0.0489.10±0.020.62300.65200.26261.05531.1058Sonar80.62±0.0781.73±0.2080.87±0.2281.44±0.1382.98±0.170.04820.06290.03680.20460.0977Votes93.20±0.0988.94±0.0394.19±0.0294.29±0.0295.33±0.020.23000.29740.13610.55670.4210Wine98.74±0.0598.76±0.0198.76±0.0198.87±0.0598.87±0.030.00990.01380.01380.04290.0219Tae50.47±0.0553.33±0.3351.47±0.0757.47±0.3364.00±0.560.01240.01780.01860.03890.0204从以上表格中，我们可以看出，无论是在线性还是非线性情况下，在保持MTSVM算法原有识别水平的基础上，LS-MTSVM可以有效的缩短计算时间，提高计算效率。并且需要指明的是，LS-MTSVM在计算过程中未使用任何优化技术，仅通过线性方程的求解来获得超平面参数；而MTSVM中二次规划问题的计算采用的是Mosek优化工具箱中的快速迭代法，该方法和传统的二次规划问题求解方法相比，在时间上已经具有一定的优势。实验二NDC数据集[47]在此实验中，我们使用DavidMusicant的NDC(NomallyDistributedClusters)产生的数据来进行大数据集上的仿真实验，通过不同样本数目的实验来考察算法识别率，特别是运行时间的变化。表3.5中给出了NDC数据的详细描述。表3.5NDC数据集的详细描述数据集训练集大小测试集大小特征维数 24基于孪生支持向量机的特征选择与分类算法研究NDC-5005005032NDC-7007007032NDC-1000100010032NDC-2000200020032NDC-3000300030032NDC-4000400040032i该数据集针对二值分类，在此我们采用线性核，所有参数均从10i3,...,3中选取。MTSVM中二次规划问题的求解采用Mosek优化工具箱。实验仿真得到LSSVM、LSTSVM、GEPSVM、MTSVM及LS-MTSVM算法的测试识别率和训练时间的结果如表3.6所示。表3.6各算法在NDC数据集上的性能比较LSSVMLSTSVMGEPSVMMTSVMLS-MTSVM数据集Test(%)Test(%)Test(%)Test(%)Test(%)Time(s)Time(s)Time(s)Time(s)Time(s)NDC_50080.0084.0082.0084.0084.000.02270.00120.00120.51500.2734NDC_70090.0085.7180.0084.2988.570.03960.00180.00130.79050.5170NDC_100089.0087.0084.0085.0088.000.07990.00250.04032.05711.0286NDC_200086.0086.0080.0084.5086.500.43520.00140.01456.62124.2549NDC_300084.3384.0082.0084.0084.331.28420.00300.003515.922910.1623NDC_400081.0081.2580.2581.5081.502.70070.00480.005125.314517.7917分析表3.6中结果，我们可得到如下结论：1)总体来说，各算法的识别率基本接近，对比LS-MTSVM和MTSVM识别结果可发现，在部分数据上LS-MTSVM的识别结果甚至还要优于MTSVM。2)各算法的运行时间随着训练样本数目的增多而增大，但各算法训练用时各不相同。在这里需要特殊指明的是，MTSVM中二次规划问题的求解采用的是Mosek优化工具箱，若使用普通的二次规划求解方法，在样本数目过高时就会产生不可解的问题。比较MTSVM和LS-MTSVM两个算法训练时间可见，MTSVM算法在采用Mosek工具箱计算二次规划问题的情况下，其耗时还要多于LS-MTSVM算法，再次验证了LS-MTSVM算法在时间上的优势。3.4基于MTSVM的雷达辐射源个体识别雷达辐射源个体识别又称辐射源指纹识别，是电子情报侦察(ELINT)、电子支援措施(ESM)和威胁告警(RWR)等系统要解决的关键问题，也是电子干扰的前提和基础，其识别水平在一定程度上表征着电子对抗设备技术的先进程度。笼统的讲，[52,63]雷达辐射源个体识别系统通过对接收机接收的电磁信号进行个体特征提取与 第三章基于流形结构的TWSVM分类算算法25分析，并将其在分类器中进行识别判别，从而达到确定辐射源个体的目标。下图3.4给出了雷达辐射源识别的一般流程，其主要由预处理、特征提取和分类器设计三大模块组成，它们彼此相互依赖，综合决定识别性能。图3.4雷达辐射源识别流程在本节中，我们将所提出的MTSVM分类算法在雷达辐射源数据上进行验证，[53]在此我们先采用PCA(PrincipalComponentsAnalysis)降维算法进行特征提取，对降维之后的数据进行分类识别。实验中所用数据为几批实测的型号、参数相同的雷达辐射源数据，提取其循环谱零切片特征。对各数据的详细说明如下表3.7所示。此外，图3.5给出了数据1中1-6类样本信号特征波形。表3.7本实验中所使用数据的具体信息数据集提取特征类数原始维数样本数目数据1循环谱零切片1310241040数据2循环谱零切片351024700数据3循环谱零切片615361200数据4循环谱零切片305123000图3.5数据1中1-6类样本信号循环谱切片特征将各数据使用PCA算法降至50维后，从中随机抽取50%样本作为训练集，剩余50%为测试集，应用MTSVM算法进行分类识别，并和SVM、GEPSVM、TWSVM、NPC-SVM算法进行比较，进行10次独立实验并取其平均结果。NPC-SVM、MTSVM算法中样本邻近数选自集合{3,4,...,20}，剩余所有参数均从集 26基于孪生支持向量机的特征选择与分类算法研究i合2i9,...,9中选取。表3.8为各算法在不同数据上的测试识别率、10次训练标准差和训练时间的平均结果。表3.8各算法在雷达辐射源上的识别性能比较SVMGEPSVMTWSVMNPC-SVMMTSVM数据集Test±std(%)Test±std(%)Test±std(%)Test±std(%)Test±std(%)Time(s)Time(s)Time(s)Time(s)Time(s)数据193.26±0.0250.63±0.1095.09±0.00695.13±0.00595.13±0.0060.00660.01440.00200.01020.0081数据297.75±0.00593.28±0.0397.70±0.00497.80±0.00297.87±0.00050.06480.01250.01740.12010.0453数据399.94±0.000983.50±0.2699.85±0.00199.87±0.00399.84±0.0060.00470.00570.00830.01040.0113数据491.69±0.00643.11±0.0889.570±0.000590.10±0.000693.12±0.00050.00660.00550.00500.00970.0082从以上结果中可以看出，致力于挖掘数据结构信息的NPC-SVM和我们所提出的MTSVM算法在雷达辐射源信号的识别上具有明显的优势，这是因为实测雷达数据分布复杂，其包含了大量的结构信息，将这些有效的结构信息合理的利用起来，就可以达到优化分类器的目的。NPC-SVM在传统SVM的基础上进行改进，在一定程度上提升了识别率，但是由于其在分类前需要计算类内散度矩阵，所以和SVM相比就会略显耗时。但是和NPC-SVM相比，我们在本章中提出的MTSVM是基于TWSVM分类算法，而TWSVM的计算时间仅为传统SVM的1/4，所以和NPC-SVM相比，MTSVM有明显的时间上的优势。3.5本章小结本章在深入学习TWSVM分类算法和流形学习的基础上，针对TWSVM分类算法未考虑到数据结构信息的缺陷，通过将数据的流形结构引入至分类目标函数中，提出基于流形结构的TWSVM，其主旨是假设所处理的数据采样于一个潜在的流形上，通过建立类内散度矩阵，获得数据内部的流形结构，并将其引入到TWSVM的目标函数中，使得类内邻近样本之间的距离最小化，不同类样本之间的间隔最大化。进一步，为了降低计算复杂度，提高其计算速度，提出基于流形结构的最小二乘TWSVM，并在各公开数据集上验证了所提出算法的有效性。下一章中我们从聚类结构方面入手对TWSVM未考虑到数据结构信息的缺陷进行改进，进一步提出基于聚类结构的TWSVM分类算法。 第四章基于聚类结构的TWSVM分类算法27第四章基于聚类结构的TWSVM分类算法4.1引言“人以群分，物以类聚”，聚类是一个古老的问题，它伴随着人类社会的产生和发展而不断深化，人类要认识世界就必须区别不同的事物并认识事物之间的相似性。作为一种无监督分类算法，聚类同分类的根本区别在于：分类是需要事先知道所依据的数据特征，而聚类是要找到这个数据特征，因此，在很多应用中，聚类分析作为一种数据预处理过程，是进一步分析和处理数据的基础。在第三章，我们针对TWSVM未考虑到数据结构信息的问题，从流形学习的角度进行讨论，提出基于流形结构的TWSVM分类器，其主旨是建立在所处理的数据采样于一个潜在的流形的假设之上。但是在实际问题中，数据的分布更倾向于表现为聚类的形式，而非流形结构，因而MTSVM也存在一定的局限性。因此，在本章中，我们提出基于聚类结构的TWSVM(STSVM)分类器，其核心思想是通过采用聚类技术来获得隐藏在数据内部的结构信息。首先对数据在类内进行聚类，将获得的结构信息以协方差矩阵的形式引入到分类算法的目标函数中，在保证各类数据都尽量围绕在其分类面周围的同时，使得同一类内数据分布更加紧凑。进一步，为了提高其计算速度，提出基于聚类结构的最小二乘TWSVM。此外，对于STSVM在处理非均衡数据时存在的问题对其进行改进，提出非对称型STSVM，实验表明，在通过聚类技术引入数据的结构信息后，算法的性能有所提升。4.2基于聚类结构的TWSVM分类算法4.2.1聚类分析概述[54]聚类就是按照事物之间的相似性作为属性划分的准则，把一个没有类别标记的样本集划分成若干个子集（类），使相似的样本尽可能归为一类，不相似的样本划分到不同的类中，从而使类内样本具有较大的相似性，而类间样本具有较小的相似性。作为一种无监督分类方法，聚类分析已经被广泛应用至模式识别、数据挖掘、机器学习等许多领域。从数学角度来刻画聚类分析问题，可以得到如下数学模型。给定一个对象集合X{x,x,...,x}，假设每个对象x,k1,...,m含有n个特征，聚类分析的过程就12mk是根据对象的特征来分析对象之间的相似程度，按照各样本间的亲疏关系把[54]x,x,...,x划分成多个不相交的子集X,X,...,X，并要求满足下列条件：12m12c 28基于孪生支持向量机的特征选择与分类算法研究XX...XX,XX12cij(4-1)1ijc这些子集X(1ic)就是聚类。在此我们以硬聚类为例，给出样本x(1km)对ik子集X的隶属关系，其可以用隶属函数表示为：i1xkXiXi(xk)ik(4-2)0xkXi其中，隶属函数必须满足条件E。也就是说，要求每一个样本能且只能属于ikh某一类，同时要求聚类后得到的每个子集都是非空的。cnEh{ikik{0,1};ik1,k;0ikm,i}(4-3)i1k1传统的聚类分析方法可大致可以分为以下几种类型：层次聚类方法、划分聚类方法、基于密度的聚类方法、基于网格的聚类方法和基于模型的聚类方法等。4.2.2结构正则化SVM作为最大化间隔分类器，传统SVM侧重于类间的可分性，忽略了类内数据所包含的结构信息，而在实际问题中，不同类数据所隐含的结构信息也各不相同。[14]鉴于此，Xue等人于2011年提出结构正则支持向量机(StructuralRegularizedSVM，SRSVM)，其采用聚类技术来获得数据的类内分布，并将数据的结构信息以聚类后所得各个类的协方差矩阵的形式引入目标函数。[55][56][57]在聚类部分有很多聚类技术可供采用，像K均值，最近邻，模糊聚类[58]等等，Xue采用的是层次聚类中的Ward'slinkage聚类。在Ward'slinkage聚类中，设S、T分别为两个聚类子集，则它们之间的Ward's[13]距离W(S,T)可以通过下式来计算：2STSTW(S,T)(4-4)ST其中和分别为聚类S、T的均值向量。ST在算法的初始化中，设每个样本点为一个模式类，则两样本点x和x之间的ii2Ward's距离定义为W(x,x)xx2。当类S和类T融合成一个新的类Y时，ijij新生成类Y和旧类Z之间的距离可以表示为：(SZ)W(S,Z)(TZ)W(T,Z)ZW(S,T)W(Y,Z)(4-5)STZ在聚类过程中，随着类数的减少，两个旧类融合成一个新类时的Ward's距离也在不断增加，可以通过绘制一个融合距离曲线来描述这一过程。在文献[59]中，Salvador和Chan提供了一种自动确定聚类数目的方法，即选取融合距离曲线中最大曲率点对应的类数作为最优聚类数目，如下图4.1所示。 第四章基于聚类结构的TWSVM分类算法29图4.1融合距离曲线聚类后，得到两个大小分别为c,c的聚类集合，分别用P,...,P和N,...,N来121c11c2表示每类样本中的聚类结果。SRSVM的目标是保证分类间隔最大化的同时使得类n内分布更加紧凑。因此，对一组样本数据(x,y),...,(x,y),xR,y{1,1}，11mmSRSVM分类模型可以描述为：n12TminwwwCiwb,22i1(4-6)Tst..ywxiib1i,i0i1,...,n其中，以及为聚类后所得类的协方差矩阵，P1Pc1N1Nc2PiNji1,...,c，j1,...,c，正则项用来调节聚类结果对分类的贡献程度，0。12其对偶形式为：nnnmax1yyxTI1xi2ijijiji1i1j1st..0iCi,1,...,n(4-7)niyi0i1解上述问题后得到的最优分类面函数为：nT1f(x)sgn[iyixi(I)xb](4-8)i14.2.3基于聚类结构的TWSVM(STSVM)受SRSVM思想的启发，我们将聚类技术应用于TWSVM，提出基于聚类结构的TWSVM(StructuralTwinSVM，STSVM)分类算法，其核心思想是通过采用聚类技术来获得隐藏在数据内部的结构信息，并以协方差矩阵的形式将其引入至TWSVM的目标函数中，在保证各类数据都尽量围绕在其分类面周围的同时，使mn得同一类内数据分布更加紧凑。对一组样本数据XR，A为mn的+1类样本1矩阵，B为mn的-1类样本矩阵，STSVM分类器通过求解如下二次规划问题获2得： 30基于孪生支持向量机的特征选择与分类算法研究1(1)(1)2λ(1)T(1)(1)2TminAweb(wΣwb)ceq1A12STSVM122(4-9)(1)(1)s.t.(Bweb)qe,q0221(2)(2)2λ(2)T(2)(2)2TminBweb(wΣwb)ceq2B21STSVM222(4-10)(2)(2)s.t.(Aweb)qe,q011其中,...,，,...,为正负两类样本各自在其类内聚类后获得AA1Ac1BB1Bc2的协方差矩阵，在这里我们仍采用Ward'slinkage聚类技术。STSVM1对应的拉格朗日问题如下所示：1(1)(1)2T(1)T(1)(1)2LAwebceqwwb112A222(4-11)T(1)(1)T((Bweb)qe)q22TT其中(,,...,)和(,,...,)为拉格朗日乘子向量，KKT条件为：12m212m2LT(1)(1)T(1)(1)A(Awe1b)BAw0(4-12)wLT(1)(1)T(1)e(Aweb)eb0(4-13)(1)112bLce0(4-14)12q(1)(1)(Bweb)qe,q0(4-15)22T(1)(1)T((Bweb)qe)0,q0(4-16)22由于0，从式(4-14)我们可以得到0c。1将式(4-12)，(4-13)表示成矩阵形式，可得到：T(1)(1)TAwA0wBTAe1(1)(1)T0(4-17)e1b0be2(1)wA0令HAe，GBe，u，K，可将式(4-17)改写为：12(1)101bTTT1T(HHK)uG0i.e.u(HHK)G(4-18)11利用式(4-11)及上述KKT条件，我们得到STSVM1的对偶形式为：T1TT1TDSTSVM1maxeG(HHK)Gs.t.0c(4-19)2112同样，我们可以得到STSVM2的对偶形式：T1TT1TDSTSVM2maxeH(GGK)Hs.t.0c(4-20)1222(2)B0w其中为拉格朗日乘子，K，超平面系数v通过下式获得：201(2)bT1Tv(GGK)H(4-21)2(1)(1)(2)(2)得到问题(4-9)、(4-10)的解(w,b)和(w,b)之后，对于任意的一个样本 第四章基于聚类结构的TWSVM分类算法31nxR，我们认为它属于距其最近的平面所在的类，分类面判别函数为：T(l)(l)Classiargminxwb(4-22)l1,2T(l)(l)其中表示样本x到超平面xwb0,l1,2的垂直距离。对于线性不可分问题，通过引入核函数，我们定义分类超平面如下所示：(1)(1)(2)(2)K(x,C)ub0,K(x,C)ub0(4-23)其中CAB，K是核函数，我们构建如下优化问题：KSTSVM11(1)(1)2T(1)TT(1)(1)2minK(A,C)uebceq(u(C)(C)ub)112A22(4-24)(1)(1)s.t.(K(B,C)ueb)qe,q022KSTSVM21(2)(2)2T(2)TT(2)(2)2minK(B,C)uebceq(u(C)(C)ub)221B22(4-25)(2)(2)s.t.(K(A,C)ueb)qe,q011其中...，...,i1,2,...,c,j1,2,...,c，AP1P2Pc1BN1N2Nc212Pi[13]和分别代表在核空间采用核Ward'slinkage聚类技术后所获聚类对应的协方Nj差矩阵。核空间中，样本x、x的投影分别为(x)和(x)，其Ward's距离定义为：ijij1W((x),(x))[K(x,x)K(x,x)2K(x,x)](4-26)ijiijjij2当类S、T合并成一个新的类Y时，新类Y和旧类Z之间的距离可通过下式来计算：(SZ)W(S,Z)(TZ)W(T,Z)ZW(S,T)W(Y,Z)(4-27)STZ定义KSTSVM1对应的拉格朗日函数：1(1)(1)2T(1)TT(1)(1)2LK(A,C)uebcequ(C)(C)ub112A222(4-28)T(1)(1)T((K(B,C)ueb)qe)q22TT其中(,,...,)和(,,...,)为拉格朗日乘子向量，KKT条件为：12m212m2LT(1)(1)TT(1)(1)KAC(,)((,)KACueb1)KBC(,)()CA()Cu0(4-29)uLT(1)(1)T(1)(1)eKACu1((,)eb1)e2b0(4-30)bLce120(4-31)q(1)(1)(K(B,C)web)qe,q0(4-32)22 32基于孪生支持向量机的特征选择与分类算法研究T(1)(1)T((K(B,C)web)qe)0,q0(4-33)22由于0，从式(4-31)我们可以得到0c。1由式(4-29)、(4-30)可得：T(1)T(1)TK(A,C)u(C)(C)0uK(B,C)AK(A,C)e0(4-34)T1(1)(1)Teb01be12T对于上式中的(C)(C),由于在高维空间中，变换的形式并不能精确的表A述出来，所以我们需要将其定义成点积的形式，对于核空间中的单个协方差矩阵，我们定义其为：i1Ti(xj)ui(xj)uiC(x)Ciji(4-35)T1TTTTT1C1TiiiiCiCii其中C为聚类后得到的样本集合，i[1,c]，T为在特征空间中聚类后第i个聚类i1iTT中所包含的样本集合，T[(x),...,(x)]，1为元素全为1C的C维列向ii1isCiii量。因此，核空间中，可表示为：AccT11TTTT/CT1C1CTAiiiiiiiii1i1TIC1C111C1C1TT(4-36)1T...T1c1TTIC11TccC1CC1c1c1c1其中I为CC的单位矩阵，i[1,c]。Cii1i定义矩阵TIC11C1CC111(4-37)TIC11cC1CCc1c1c1PT1Tc(4-38)1T将式(4-37)、(4-38)代入式(4-36)中，可以得到PP。A和上述推导过程相同，通过将样本矩阵A中的元素换为B，就可以得到负类样本B在核聚类之后的协方差矩阵。Bu(1)T()C()C0令SK(A,C)e,RK(B,C)e,z,A,可以121(1)K1b01将式(4-34)改写为：TTT1T(SSKz1)1R0i.e.z1(SSK1)R(4-39) 第四章基于聚类结构的TWSVM分类算法33利用式(4-28)及上述KKT条件，我们得到KSTSVM1的对偶形式为：T1TT1TDKSTSVM1maxeRSS(K)Rs.t.0c(4-40)2112同样，我们可以得到STSVM2的对偶形式：T1TT1TDKSTSVM2maxeSRR(K)Ss.t.0c(4-41)1222Tu(2)()C()C0其中为拉格朗日乘子，B，超平面系数z通过下式K22(2)01b获得：T1Tz2(RRK2)S(4-42)(1)(1)(2)(2)得到问题(4-24)、(4-25)的解(u,b)和(u,b)之后，对于任意的一个样本nxR，我们认为它属于距其最近的平面所在的类，分类面判别函数为：(l)(l)ClassiargminK(x,C)ub(4-43)l1,2(l)(l)其中表示样本x到超平面K(x,C)ub0,l1,2的垂直距离。4.2.4实验结果及分析在本节实验中，我们分别将所提出的STSVM分类算法在人造数据、UCI机器[60]学习数据库和Caltech101图像数据库上进行验证，并和前文所提到的SVM、GEPSVM、TWSVM和SRSVM分类算法进行对比。实验一人造数据在本节中，我们使用的二维人造数据为随机产生的四组高斯分布，其中正负两类数据各由两组高斯分布组成，分别表示为聚类P(N)、P(N)，每组高斯分1122布都包含有200个样本。对各个类数据的具体描述如下表4.1所示。表4.1实验中使用的数据集数据集样本个数均值方差聚类P200[2,5][0.5,0;0,5]1正类样本A聚类P200[1.5,-5][5,0;0,0.5]2聚类N200[-5,0][0.5,0;0,5]1负类样本B聚类N200[8,0][4.5,0;0,0.5]2在这里我们给出SVM、TWSVM、SRSVM和STSVM四种分类器在人造数据2TT2上的性能比较，实验中采用高斯核函数K(x,x)exp(xx)，且参数均取1，取c从而获得硬间隔的分界面。分别取10%、20%、30%、40%的数据做训练集，表4.2给出了各分类器在不同比例训练集上的训练识别率和测试识别率，在这里我们仅给出10%和30%训练集上的分类边界，如图4.2、4.3所示，其中'*'、 34基于孪生支持向量机的特征选择与分类算法研究'+'和分别代表正类样本、负类样本。表4.2各分类器在人造数据集上的识别性能比较训练识别率/测试识别率(%)数据集SVMTWSVMSRSVMSTSVM10%训练集1/91.941/93.061/94.031/96.1120%训练集1/93.911/94.531/93.911/95.6330%训练集1/95.541/94.641/95.541/97.6840%训练集1/94.581/96.041/94.381/98.33PositivesamplesPositivesamples1010NegativesamplesNegativesamplesSVMSVM88TWSVMTWSVM6SRSVM6SRSVMSTSVMSTSVM442200-2-2-4-4-6-6-8-8-5051015-5051015(a)训练集上的分类边界(b)测试集上的分类边界图4.2各分类器在人造数据10%训练集上的分类边界PositivesamplesPositivesamples1010NegativesamplesNegativesamplesSVMSVM88TWSVMTWSVM6SRSVM6SRSVMSTSVMSTSVM442200-2-2-4-4-6-6-8-8-5051015-5051015(a)训练集上的分类边界(b)测试集上的分类边界图4.3各分类器在人造数据30%训练集上的分类边界分析以上结果，可以得到以下几个结论：1)在训练集上各分类器都能取得100%的识别率，且随着训练集样本数据的增多，各分类器的识别结果有所增长。2)由于TWSVM未考虑到数据的结构信息，其分类边界仅侧重于类间的可分性，尽管其在训练集上可以取得100%的识别率，但是其在测试集上的识别率和STSVM相比，仍有一定差距。 第四章基于聚类结构的TWSVM分类算法353)从图4.2、4.3中可以很明显的看出，STSVM的分类边界完全将TWSVM的包围在其中，由此说明STSVM和TWSVM相比具有更好的泛化性。实验二UCI机器学习据库为了验证所提出STSVM分类算法性能，将其在UCI机器学习数据库的13组数据上进行仿真实验，各数据详细描述于表4.3中。表4.3实验中所使用的数据集数据集特征维数样本个数类别数目Sonar208602Ionosphere351342Monk355462Votes435162Australian690142Hepatitis155192Pima76882Bupa34562Spectf267442New_thyroid21553Tae15153Wine178133Glass21496对于每组数据，我们选其70%作为训练集，剩余的30%作为测试集。线性情i况下，所有参数均从集合2i9,...,9中选取；非线性情况下，采用高斯核函数2TT2K(x,x)exp(xx)，并且为了降低参数选择时间，所有参数均选自集合i10i3,...,3，对于多类问题，采用“一对一”策略。各算法中二次规划问题的计算均采用Mosek优化工具箱。我们从测试识别率、10次训练标准差和训练时间三方面来进行评价，10次独立实验的平均结果如下表4.4、4.5所示。表4.4各算法在UCI数据集上的性能比较（线性核）SVMGEPSVMTWSVMSRSVMSTSVM数据集Test±std(%)Test±std(%)Test±std(%)Test±std(%)Test±std(%)Time(s)Time(s)Time(s)Time(s)Time(s)Sonar76.45±0.3074.84±.0.3773.06±0.2876.13±.0.2775.32±.0.350.04390.02110.00960.10240.0139Ionosphere89.14±.0.0676.00±.0.2990.67±0.0689.52±.0.1091.24±0.080.07920.01540.03110.05730.0285Monk381.87±0.0281.81±0.0588.67±0.0482.05±.0.1388.67±0.040.15970.00170.03910.08970.0967Votes94.85±0.0294.85±0.0296.00±.0.0195.08±.0.0296.23±0.0030.10940.00490.04550.08620.0588Australian86.18±0.0366.76±0.1687.44±0.0386.57±0.0787.54±0.040.47490.03060.08990.43050.1856Hepatitis81.52±0.4472.61±4.3882.61±0.4582.39±0.3483.70±0.440.0410s0.00570.01130.01280.0099Pima77.74±0.0271.96±0.1077.78±0.0477.83±0.0678.00±0.040.42270.00350.10090.52040.1953Bupa68.83±0.1756.12±0.1468.06±0.1868.83±0.1469.51±0.180.05020.00210.01550.35070.0254Spectf78.12±0.2525.63±0.3378.75±0.2579.25±0.3380.00±0.12 36基于孪生支持向量机的特征选择与分类算法研究0.05720.02010.03760.03430.0283New_thyroid97.66±0.0498.13±0.0398.44±0.0298.91±0.0398.91±0.020.00240.00010.00190.00730.0043Tae54.44±0.2150.67±1.3954.89±0.3855.78±0.4055.11±0.450.00340.00010.00380.00820.0122Wine97.92±0.0497.92±0.0498.68±0.0298.68±0.0298.87±0.020.00560.00190.03130.01100.0256Glass63.13±0.3435.16±0.6460.78±0.7163.28±0.5162.50±0.490.00070.00020.00140.00240.0031表4.5各算法在UCI数据集上的性能比较（高斯核）SVMGEPSVMTWSVMSRSVMSTSVM数据集Test±std(%)Test±std(%)Test±std(%)Test±std(%)Test±std(%)Time(s)Time(s)Time(s)Time(s)Time(s)Sonar83.39±0.1982.26±.0.2983.06±0.1784.03±0.1384.84±0.110.07910.17880.03410.28410.2271Ionosphere93.24±0.0483.81±0.1794.19±0.0693.62±0.0594.38±0.040.28130.39460.24280.92460.5826Monk396.02±0.0277.71±2.8496.27±0.0496.02±0.0296.87±0.040.53870.23520.93331.79711.3645Votes94.62±0.0289.23±.0.0395.77±0.0294.85±.0.0296.08±0.020.31230.19230.31161.32580.8512Australian84.59±0.0886.47±1.9486.71±0.0485.12±0.0886.81±0.041.00670.84231.14742.67631.4223Hepatitis83.26±0.2984.78±0.3685.43±0.4483.70±0.4685.43±0.330.05570.00810.04830.16470.1213Pima76.65±0.0576.96±0.1676.61±0.0576.30±0.0676.70±0.050.56870.29680.99443.79481.9952Bupa71.26±0.2464.08±0.2968.93±0.2370.49±0.1870.10±0.190.22240.12250.67410.67750.4951Spectf79.50±0.1482.50±0.1779.50±0.1279.50±0.1479.88±0.080.12880.09910.18130.44480.3864New_thyroid98.28±0.0395.16±0.1198.44±0.0498.28±0.0398.59±0.020.01310.00990.02300.02970.0240Tae57.33±0.6558.67±0.4461.56±0.9858.22±0.7665.78±0.440.01610.01040.04940.06850.0562Wine97.74±0.0598.49±0.0198.30±0.0498.49±.0.0299.06±0.100.02600.01960.10340.10860.1001Glass67.19±0.2463.19±0.6570.16±0.2468.75±0.2570.31±0.240.00120.00090.00490.00490.0032对上述结果进行分析，我们可以得到以下几个结论：1)对比SVM和SRSVM，可以发现由于考虑到数据的结构信息，不论是在线性核还是高斯核情况下，SRSVM在各个数据上的识别结果都要明显优于SVM。这是因为在实际问题中，数据内部包含着丰富的结构信息，而SRSVM正是通过采用聚类技术获得数据类内分布信息，其优异的识别结果证实了在分类器设计中挖掘数据结构信息的必要性。2)和TWSVM相比，不论是在线性核和高斯核情况下，STSVM的识别率几乎都要优于TWSVM，例如Ionosphere、Votes、Australian、Pima、Bupa、Spectf、Wine等数据。这是因为STSVM是通过对数据在类内进行聚类，将获得的结构信息以协方差矩阵的形式引入到分类算法的目标函数中，在保证各类数据都尽量围 第四章基于聚类结构的TWSVM分类算法37绕在其分类面周围的同时，使得同一类内数据分布更加紧凑，弥补了TWSVM未考虑到数据结构信息的缺陷。3)比较SRSVM和STSVM两种基于聚类结构的分类算法，SRSVM是在传统SVM的基础上进行改进，在目标函数中嵌入数据的结构信息，STSVM是在TWSVM的基础上进行改进，而TWSVM和传统SVM相比，其本身就有一定的优势，因此，在大部分数据上，STSVM的识别结果都要高于SRSVM，引入高斯核之后其优势尤为明显。4)在时间上，和TWSVM相比，STSVM有一个聚类的过程，因此在其计算时间上就会略高于TWSVM，和SRSVM相比，由于STSVM是基于TWSVM提出来的，而TWSVM的计算时间仅为传统SVM的1/4，所以和SRSVM相比，STSVM有明显的时间上的优势。实验三Caltech101图像数据[58]Caltech101是美国加利福尼亚理工学院提供的一个数字图像数据集，其总共包含有9146幅图像，分为101个属性（包括人脸、飞机、动物等）和一个背景类别。其中包含的图像尺寸大致为300×200像素。本实验中，我们选取了其中9类图像，分别是Airplanes、Bonsai、Car-Side、Dolphin、Electric-Guitar、Faces-Easy、[61]Helicopter、Leopards和Motorbikes。对这些图像提取SIFT、LBP和PHOG特征，SIFT局部特征在灰度量化图像时选取K=300，对LBP特征提取的是空间金字塔中的第一层信息，PHOG特征也考虑的是金字塔的第一层，各个特征的维数依次是300、37、40。图4.4给出了数据集中部分数据的图像示例。图4.4Caltech101数据库中图像示例我们从每类图像中随机抽取80幅作为数据集，并随机将其中的40幅作为训练样本，剩下的40幅作为测试样本，进行10次独立实验。实验中采用线性核，i所有参数均从2i9,...,9选取，各算法中二次规划问题的计算均采用Mosek优化工具箱。表4.6给出了各算法在Caltech101数据集上的识别性能比较。 38基于孪生支持向量机的特征选择与分类算法研究表4.6各算法在Caltech101数据集上性能比较SVMGEPSVMTWSVMSRSVMSTSVM数据特征Test(%)Test(%)Test(%)Test(%)Test(%)SIFT84.1465.3383.5384.3384.69LBP56.3337.8666.9256.5667.09PHOG48.6940.4740.6449.4946.56分析以上结果，可得到如下结论：1)所提出的STSVM算法在三组特征上的分类结果都优于TWSVM，尤其是在PHOG特征上，其识别率和TWSVM相比提高了将近6个百分点，从而验证了STSVM算法的有效性。2)和SRSVM算法相比，STSVM在SIFT和LBP特征上的识别结果具有明显的优势，但是在PHOG特征上，由于TWSVM本身的识别结果就略差于传统SVM，因此在引入结构信息之后，STSVM的识别结果仍不如SRSVM优秀。4.3最小二乘STSVM分类算法4.3.1算法原理和第三章中的MTSVM分类器相似，为降低计算复杂度，我们通过对STSVM约束条件进行修改，提出最小二乘STSVM(LeastSquareStructuralTwinSVM，LS-STSVM)，其目标优化问题如下所示：1(1)(1)2λ(1)T(1)(1)2c1TminAweb(wΣwb)qq1ALS-STSVM1222(4-44)(1)(1)s.t.(Bweb)qe221(2)(2)2λ(2)T(2)(2)2c2TminBweb(wΣwb)qq2BLS-STSVM2222(4-45)(2)(2)s.t.(Aweb)qe11将等式约束条件代入到目标函数中，以上两个QP问题则变为：1(1)(1)2λ(1)T(1)(1)2c1(1)(2)2minAweb(wΣwb)eBweb(4-46)1A222221(2)(2)2λ(2)T(2)(2)2c2(2)(2)2minBweb(wΣwb)e(Aweb)(4-47)2B11222(1)(1)对于LS-STSVM1，对w和b求偏导，得到：T(1)(1)T(1)(2)(1)A(Aweb)cB(eBweb)w0(4-48)1122AT(1)(1)T(1)(2)e(Aweb)ce(eBweb)b0(4-49)111222将式(4-48)、(4-49)写成矩阵形式，可得到：T(1)T(1)T(1)AwBwBA0wAecBece0(4-50)T1(1)1T2(1)1T201(1)e1be2be2b(1)wA0定义HAe,GBe,u,S,(4-50)可写为：12(1)101b 第四章基于聚类结构的TWSVM分类算法39TTTT1T1T(HHcGGS)ucGe0i.e.u(GGHHS)Ge(4-51)111212cc11对LS-STSVM2进行求解，获得超平面2的参数为：(2)wT1T1Tv(HHGGS)He(4-52)(2)21bc2c2B0其中S。201(1)(1)(2)(2)一旦两个非平行平面参数(w,b)、(w,b)确定之后，对于任意的一个样n本xR，我们就可以通过判断它离两个超平面的距离来确定其类别。同样，对于线性不可分问题，可以通过采用核函数将LS-STSVM推广至非线性分类，目标函数为：KLS-STSVM11(1)(1)2(1)TT(1)(1)2c1TminKACu,eb1(uCACub)qq222(4-53)(1)(1)s.t.(KBCu,eb2)qe2KLS-STSVM21(2)(2)2(2)TT(2)(2)2c2TminKBCu,eb2(uCBCub)qq222(4-54)(2)(2)s.t.(KACu,eb1)qe1将等式约束代入到目标函数中，可得到：(1)uT1T1T(RRQQS)Qe(4-55)(1)12bc1c1(2)uT1T1T(RRQQS)Re(4-56)(2)21bc2c2T(C)(C)0A其中QK(A,C)e,RK(B,C)e,S，12101T(C)(C)0BS2。01(1)(1)(2)(2)n在超平面参数(u,b)、(u,b)确定之后，对于任意的一个样本xR，我们就可以通过计算其距两个分类超平面的距离来确定其类别。4.3.2实验结果及分析本节中，将LS-STSVM算法在UCI机器学习数据库和NDC数据集的部分数据上进行验证，并和LSSVM、GEPSVM、LSTSVM及STSVM进行比较。 40基于孪生支持向量机的特征选择与分类算法研究实验一UCI机器学习数据库本节中使用的UCI数据和4.2节中相同，在此就不再做详细描述。对于每组数据，我们选其50%作为训练集，剩余的50%作为测试集。线性情况下，所有参i数均从集合2i9,...,9中选取；对于非线性情况，采用高斯核函数2TT2K(x,x)exp(xx)，并且为了降低参数选择时间，非线性情况下所有参i数均从10i3,...,3中选取。对于多类问题，采用“一对一”策略。我们从测试识别率、10次训练标准差和训练时间三方面来进行评价，10次独立实验的平均结果如下表4.7、4.8所示。表4.7各算法在UCI数据集上的性能比较（线性核）LSSVMGEPSVMLSTSVMSTSVMLS-STSVM数据集Test±std(%)Test±std(%)Test±std(%)Test±std(%)Test±std(%)Time(s)Time(s)Time(s)Time(s)Time(s)Sonar78.08±0.0972.21±0.1670.87±0.1968.85±0.1570.87±0.190.00790.05890.00360.01480.0107Hepatitis80.39±0.1177.79±0.1980.39±0.1180.00±0.1580.52±0.120.00430.01430.00470.01800.0056Ionosphere87.37±0.0876.23±0.4988.17±0.0988.91±0.1488.29±0.140.01190.08340.09060.01990.0196Monk378.12±0.1681.44±0.0884.08±0.1188.19±0.0383.9±0.080.03520.02220.00400.09560.0215Votes94.19±0.00793.87±0.0295.3±0.0195.58±0.00995.48±0.080.02770.00240.00190.03190.0167Pima76.48±0.0275.83±0.0276.61±0.0276.72±0.0276.64±0.020.04160.00150.00130.09240.0580Australian86.2±0.0370.32±0.2086.12±0.0386.29±0.0286.38±0.020.03690.00070.00230.06290.0568Bupa67.56±0.0955.87±0.2368.26±0.1170.41±0.1469.19±0.150.01370.00010.00060.02630.0120Spectf80.68±0.0426.47±0.4080.75±0.0580.90±0.0580.83±0.040.01560.02690.00220.02030.0178Wine97.53±0.0296.97±0.0297.87±0.0297.98±0.0398.20±0.020.00120.00020.00010.01020.0094Glass60.9±0.0938.31±1.4760.19±0.0761.40±0.1259.91±0.060.00020.00020.00010.00280.0024Tae51.33±0.4347.87±0.5751.33±0.4352.67±0.2851.47±0.420.00090.000080.00010.01560.0037New_thyroid92.06±0.1495.98±0.0497.20±0.0897.57±0.0596.92±0.070.00110.000080.00010.00450.0019表4.8各算法在UCI数据集上的性能比较（高斯核）LSSVMGEPSVMLSTSVMSTSVMLS-STSVM数据集Test±std(%)Test±std(%)Test±std(%)Test±std(%)Test±std(%)Time(s)Time(s)Time(s)Time(s)Time(s)Sonar80.62±0.0781.73±0.2080.87±0.2282.69±0.1883.65±0.200.04820.06290.03680.44280.3260Hepatitis82.26±0.0382.73±0.0981.95±0.0682.73±0.0982.73±0.080.06560.14550.02120.10440.0953Ionosphere92.45±0.0388.57±7.7991.49±0.0694.23±0.0194.06±0.020.07990.19280.08880.90990.4889Monk394.23±0.0282.31±7.7193.00±0.0196.93±0.0196.43±0.00070.1560.75440.22191.68721.0559 第四章基于聚类结构的TWSVM分类算法41Votes93.20±0.0988.94±0.0394.19±0.0294.42±0.0294.42±0.020.23000.29740.13610.89150.5324Pima74.07±0.2675.52±3.4572.50±0.0277.29±0.0177.01±0.020.52361.15350.41582.01561.0839Australian85.55±0.0686.96±6.2285.10±0.1186.64±0.0286.55±0.020.45300.84490.32291.73271.5451Bupa69.74±0.0561.05±0.0368.55±0.0970.58±0.0471.63±0.100.10270.70910.08780.46020.1196Spectf80.21±0.3087.97±0.2379.85±0.1280.53±0.0980.90±0.080.09520.09730.053300.45940.2941Wine98.74±0.0597.75±0.000698.76±0.0198.09±0.00998.54±0.010.00990.02030.01380.23060.0550Glass66.45±0.0261.21±0.2365.33±0.1769.84±0.3268.69±0.180.00190.00070.00060.00640.0037Tae51.33±0.4353.33±0.3351.47±0.0759.47±0.3156.13±0.410.00090.01780.01860.07000.0217New_thyroid96.54±0.0592.99±0.1097.48±0.0496.92±0.0498.44±0.040.00960.00660.00890.01820.0103从以上表格中，我们可以看出，无论是在线性还是非线性情况下，在保持STSVM算法原有识别水平的基础上，LS-STSVM极大的缩短了计算时间，提高了计算效率。并且需要指明的是，LS-STSVM在计算过程中未使用任何优化技术，仅通过线性方程的求解来获得超平面参数；而STSVM中二次规划问题的计算采用的是Mosek工具箱中的快速迭代法，该方法和传统的二次规划问题求解方法相比，在时间上已经有很大的优势。实验二NDC数据集最后我们使用DavidMusicant的NDC(NomallyDistributedClusters)产生的数据来进行大数据集上的仿真实验，通过不同样本数目的实验来考察算法识别率，特别是运行时间的变化。实验所采用数据与第三章中3.3小节相同，在此就不再详细i描述。本实验中我们采用线性核，所有参数均从10i3,...,3中选取。实验仿真得到LSSVM、LSTSVM、GEPSVM、STSVM及LS-STSVM算法的测试识别率和训练时间的结果列于表4.9中。表4.9各算法在NDC数据集上的性能比较LSSVMLSTSVMGEPSVMSTSVMLS-STSVM数据集Test(%)Test(%)Test(%)Test(%)Test(%)Time(s)Time(s)Time(s)Time(s)Time(s)NDC_50080.0084.0082.0086.0084.000.02270.00120.00120.13540.0451NDC_70090.0085.7180.0088.5788.570.03960.00180.00130.25310.0748NDC_100089.0087.0084.0089.0088.000.07990.00250.04030.58220.1854NDC_200086.0086.0080.0087.5086.000.43520.00140.01454.04611.0986NDC_300084.3384.0082.0084.6784.331.28420.00300.003510.57504.9655NDC_400081.0081.2580.2581.2581.502.70070.00480.005120.72368.9211 42基于孪生支持向量机的特征选择与分类算法研究对上述结果进行分析，我们可以得到以下结论：1)总体来说，各算法的识别率基本接近，尤其是我们所提出的STSVM算法，除了在NDC_700数据上略差于LSSVM以外，在其余数据上的识别结果一直处于最优；对比LS-STSVM和STSVM识别结果可发现，LS-STSVM可获得与STSVM相当的识别性能，在部分数据上LS-STSVM的识别结果甚至还要优于STSVM。2)各算法的运行时间随着训练样本数目的增多而增大，但各算法训练用时各不相同。GEPSVM算法训练耗时始终最少，在这里需要特殊指明的是，STSVM中二次规划问题的求解采用的是Mosek优化工具箱，若使用普通的二次规划求解方法，在样本数目过高时就会产生不可解的问题。比较STSVM和LS-STSVM两个算法训练时间可见，STSVM算法在采用Mosek优化工具箱计算二次规划问题的情况下，其耗时还要明显多于LS-STSVM算法，再次验证了LS-STSVM算法在时间上的优势。4.4非对称型STSVM分类算法4.4.1算法原理在上述章节中提到，正则项的作用是调节聚类结果对分类的贡献程度，在STSVM中，我们取两个目标优化函数中的为相同值，即两类样本的聚类有效度用同一个参数来调节，这样就相当于默认两类数据的类内分布大致相似，但是在实际问题中，数据不同类之间的分布往往也不尽相同，因此若仍取相同值则可能会导致分类结果出现偏差，对于分布不均衡数据尤为明显。针对此问题，在本节中，我们用两个不同的正则项、来分别调节两类样本的聚类结果，提出非对12称型STSVM(AsymmetricStructuralTwinSVM，AS-STSVM)分类算法。和STSVM相比，不同正则项的引入在提高分类效果的同时需要付出增加参数选择时间的代mn价，因此我们仅在线性可分问题下进行讨论。对于对一组样本数据XR，A为mn的+1类样本矩阵，B为mn的-1类样本矩阵，其目标优化函数如下所示：121(1)(1)2λ1(1)T(1)(1)2TminAweb(wΣwb)ceq1A12AS-STSVM122(4-57)(1)(1)s.t.(Bweb)qe,q0221(2)(2)2λ2(2)T(2)(2)2TminBweb(wΣwb)ceq2B21AS-STSVM222(4-58)(2)(2)s.t.(Aweb)qe,q011A0B0令HAe，GBe,K,K，将式(4-57)、(4-58)12120101转化成对偶形式： 第四章基于聚类结构的TWSVM分类算法43T1TT1TDAS-STSVM1maxeG(HHK)Gs.t.0c(4-59)21112同样，我们可以得到STSVM2的对偶形式：T1TT1TDAS-STSVM2maxeH(GGK)Hs.t.0c(4-60)12222超平面参数可通过下式获得：(1)wT1Tu(HHK)G(4-61)(1)11b(2)wT1Tv(GGK)H(4-62)(2)22b(1)(1)(2)(2)得到问题(4-57)、(4-58)的解(w,b)和(w,b)之后，对于任意的一个样本nxR，我们认为它属于距其最近的平面所在的类。4.4.2实验结果及分析我们将所提出的AS-STSVM分类算法分别在人造数据、UCI机器学习数据库和Caltech101图像识别数据库上进行验证，并和前文所提到的SVM、GEPSVM、TWSVM及STSVM算法进行对比。实验一人造数据在本节中，我们使用的二维人造数据为随机产生的四组高斯分布，其中正类数据有70个样本，包含有一组高斯分布，表示为聚类P，负类数据有130个样本，由三组高斯分布组成，分别表示为聚类N、N、N。对各个类数据的具体描述123如下表4.10所示。表4.10实验中使用的人造数据集数据集样本个数均值方差正类样本A聚类P70[0,3][0.2,0;0,6]聚类N50[2.5,4][0.5,0;0,1]1负类样本B聚类N50[7.5,6][0.5,0;0,0.5]2聚类N30[5,1][1,0;0,1]3在这里我们给出TWSVM、STSVM和非对称STSVM三种分类器在人造数据i上的性能比较。实验中采用线性核，所有参数均从2i9,...,9中选取。表4.11给出了各分类器最优识别率以及对应的最优参数，各分类器所得到的分类超平面及分类边界如图4.5所示，其中'*'、'+'和'o'分别代表正类样本、负类样本和分错的样本。从图中我们可以看出，正负两类样本的内部分布存在明显差异，并且两类数据样本个数也相差较大。 44基于孪生支持向量机的特征选择与分类算法研究10886644202-20-4-2-6PositivesamplesPositivesamples-8Negativesamples-4Negativesamplesthemisclassifiedsamplesthemisclassifiedsamples-10-20246810-202468(a)TWSVM10886644202-20-4-2-6PositivesamplesPositivesamples-8Negativesamples-4Negativesamplesthemisclassifiedsamplesthemisclassifiedsamples-10-20246810-202468(b)STSVM10886644202-20-4-2-6PositivesamplesPositivesamplesNegativesamples-8-4Negativesamplesthemisclassifiedsamplesthemisclassifiedsamples-10-20246810-202468(c)AS-STSVM图4.5各算法在人造数据上的识别结果表4.11各算法在人造数据上的最优识别率及对应的参数分类器识别率（%）12TWSVM86.47//STSVM92.352727AS-STSVM95.292829对以上结果进行分析，我们可以得到如下结论：1)对于TWSVM而言，由于其并未考虑到数据的结构信息，仅保证了本类超 第四章基于聚类结构的TWSVM分类算法45平面离本类样本尽可能近，因此其不能很好的根据数据的分布趋势来调节分类器性能，从图4.5中可以看出，其识别效果最差。2)STSVM分类器通过采用聚类技术，在使得同一类内数据分布更加紧凑的同时，保证各类数据都尽量围绕在其分类面周围，因此和TWSVM相比，其可以获得更好的分类结果。但是，在STSVM中两类样本的聚类有效度仅用同一个参数来调节，而在本实验中给出的人造数据正类样本由一组高斯分布组成，负类样本中包含有三组高斯分布，各类数据内部聚类对分类结果的贡献各不相同，若强制性的使用同一参数去调节其影响，则可能会使得分类结果出现偏差，从表4.11中可以看出，和AS-STSVM相比，STSVM分类器的识别结果会略差一点。3)从表4.11中可以看出，对于正类样本，由于仅包含了一个高斯分布，且样本个数较少，所以在分类过程中，聚类所起的作用不是很明显，需要用一个较大7的参数来对其进行调节，其调节参数2，而负类样本其本身包含了丰富的聚19类信息，因此其调节参数2。由于其对两类数据采用不同的正则参数来调节2聚类影响，和以上两种方法相比，AS-STSVM表现出优秀的识别结果。实验二UCI机器学习数据库本节中，将AS-STSVM算法在UCI机器学习数据库的部分数据上进行验证，并和SVM、TWSVM、SRSVM及STSVM进行比较，所选用的数据及参数设置和4.2.4节中相同，我们从测试识别率、10次训练标准差和训练时间三方面来进行评价，10次独立实验的平均结果如下表4.12所示。表4.12各算法在UCI数据集上的性能比较SVMTWSVMSRSVMSTSVMAS-STSVM数据集test±stdtest±stdtest±stdtest±stdtest±stdTime(s)Time(s)Time(s)Time(s)Time(s)Sonar76.45±0.3073.06±0.2876.13±0.2775.32±0.3575.97±0.180.04390.00960.10240.01390.0201Ionosphere89.14±0.0690.67±0.0689.52±0.1091.24±0.0891.33±0.080.07920.03110.05730.02850.0306Monk381.87±0.0288.67±0.0482.05±0.1388.67±0.0488.67±0.040.15970.03910.08970.09670.0956Votes94.85±0.0296.00±0.0195.08±0.0296.23±0.00396.23±0.010.10940.04550.08620.05880.0841Australian86.18±0.0387.44±0.0386.57±0.0787.54±0.0487.54±0.050.47490.08990.43050.18560.1984Hepatitis81.52±0.4482.61±0.4582.39±0.3483.70±0.4484.57±0.180.0410s0.01130.01280.00990.0106Pima77.74±0.0277.78±0.0477.83±0.0678.00±0.0478.17±0.040.42270.10090.52040.19530.1410Bupa68.83±0.1768.06±0.1868.83±0.1469.51±0.1869.61±0.290.05020.01550.35070.02540.0360Spectf78.12±0.2578.75±0.2579.25±0.3380.00±0.1280.63±0.160.05720.03760.03430.02830.0315New_thyroid97.66±0.0498.44±0.0298.91±0.0398.91±0.0299.22±0.010.00240.00190.00730.00430.0098 46基于孪生支持向量机的特征选择与分类算法研究Tae54.44±0.2154.89±0.3855.78±0.4055.11±0.4556.00±0.570.00340.00380.00820.01220.0257Wine97.92±0.0498.68±0.0298.68±0.0298.87±0.0299.25±0.010.00560.03130.01100.02560.0144Glass63.13±0.3460.78±0.7163.28±0.5162.50±0.4962.97±0.420.00070.00140.00240.00310.0032从以上表格中可以很直观的看出，在采用不同的正则项对两类样本的聚类结果进行调节后，AS-STSVM在各数据上的结果明显优于原STSVM，尤其是Hepatitis和Tae数据，提升了将近一个百分点，但是对于部分数据，如Monk3、Votes、Australian，AS-STSVM取得和STSVM相同的识别结果，这是因为这几组数据两类样本分布均衡，可以用相同的正则参数来进行调节。在这里，我们以Hepaitits数据为例，其在取得最优识别率是的参数值分别为1253c2、c2、2、2，我们固定c、c和为其最优参数值，绘制1212121AS-STSVM算法在该数据上的识别率随的变化曲线，的取值范围为22i2i9,...,9，结果如图4.6所示。0.860.850.84(%)0.83率别识试0.82测0.810.80.7905101520lambda2图4.6AS-STSVM算法在Hepatitis数据上识别率随的变化曲线2在对以上实验结果进行分析，我们可以得到如下结论：实际问题中所获取的数据内部隐藏有丰富的结构信息，若能有效的利用这些信息，分类器的识别性能就会得到很大的改善。实验三Caltech101图像数据本节中，将AS-STSVM算法在Caltech101图像数据上进行验证，并和SVM、TWSVM、SRSVM及STSVM进行比较，本章4.2节中对此数据库进行了详细描述，在此就不再赘述。在本实验中，我们从每类图像中随机抽取80幅作为数据集，并随机将其中的40幅作为训练样本，剩下的40幅作为测试样本，进行10次独立实验。实验中采i用线性核，所有参数均从2i9,...,9选取，各算法中二次规划问题的计算均采用 第四章基于聚类结构的TWSVM分类算法47Mosek优化工具箱。表4.13给出了各算法在Caltech101数据集上的10次平均识别性能比较。表4.13各算法在Caltech101数据集上性能比较SVMTWSVMSRSVMSTSVMAS-STSVM数据特征Test(%)Test(%)Test(%)Test(%)Test(%)SIFT84.1483.5384.3384.6984.72LBP56.3366.9256.5667.0967.19PHOG48.6940.6449.4946.5646.81从以上表格中可以看出，在采用不同的正则项对两类样本的聚类结果进行调节后，AS-STSVM在各特征上的识别结果明显优于原STSVM，进一步证实了在分类识别中挖掘数据结构信息的重要性。4.5基于STSVM的雷达辐射源个体识别本节将提出的基于聚类结构的TWSVM(STSVM)算法应用于雷达辐射源信号的分类识别。实验中所使用数据与3.4节中相同，在此就不再做详细描述。实验比较了SVM、GEPSVM、TWSVM、SRSVM和STSVM算法在辐射源识别应用中的i性能。实验中采用线性核，所有参数均从2i9,...,9中选取，多类分类采用“一对一”策略。我们从测试识别率、10次训练标准差和训练时间三个方面来进行考察，10次独立运行的平均结果示于表4.14中。表4.14各算法在雷达辐射源数据上的识别性能比较SVMGEPSVMTWSVMSRSVMSTSVM数据集Test±std(%)Test±std(%)Test±std(%)Test±std(%)Test±std(%)Time(s)Time(s)Time(s)Time(s)Time(s)数据193.26±0.0250.63±0.1095.09±0.00694.57±0.0395.14±0.0070.00660.01440.00200.01370.0048数据297.75±0.00593.28±0.0397.70±0.00497.77±0.00597.88±0.0050.06480.01250.01740.07430.0246数据399.94±0.000983.50±0.2699.85±0.00199.94±0.00091±00.00470.00570.00830.03620.0112数据491.69±0.00643.11±0.0889.570±0.000592.57±0.000694.09±0.00010.00660.00550.00500.03300.0080对以上结果进行分析，可得到如下结论：1)对比各算法结果可发现，GEPSVM是通过求解一对广义特征值问题来获得超平面参数，在求解过程中由于矩阵奇异性问题导致识别结果不稳定，尤其是在数据1和数据2上，GEPSVM识别性能和其他算法相比有很大的偏差。2)由于实测雷达数据分布复杂，包含了大量的结构信息，因此致力于挖掘数据结构信息的SRSVM和我们所提出的STSVM算法在雷达辐射源信号的识别上具有明显的优势，特别是在数据4上，STSVM识别性能比TWSVM提高了近5个百分点，和SVM相比则提高了2.4个百分点。3)从时间上看，SRSVM在传统SVM的基础上进行改进，将聚类信息融入到 48基于孪生支持向量机的特征选择与分类算法研究分类目标函数中，在一定程度上提升了识别率，但是由于其分类前端有一个聚类的过程，所以和SVM相比就会略显耗时。但是STSVM的提出是基于TWSVM分类算法，而TWSVM的计算时间仅为传统SVM的1/4，因此，和SRSVM相比，STSVM有明显的时间上的优势。4.6本章小结本章针对TWSVM分类算法未考虑到数据结构信息的缺陷，在第三章的基础上，进一步提出基于聚类结构的TWSVM分类算法，其主旨是通过采用聚类技术挖掘隐藏在数据内部对分类有效的结构信息。首先对数据在类内进行聚类，再将获得的结构信息以协方差矩阵的形式引入到分类算法的目标函数中，在保证各类数据都尽量围绕在其分类面周围的同时，使得同一类内数据分布更加紧凑。进一步，为了提高其计算速度，提出基于流形结构的最小二乘TWSVM算法，此外，对于STSVM在处理分均衡数据时存在的问题对其进行改进，提出非对称型STSVM算法，并在各公开数据集上验证了所提出算法的有效性。 第五章基于STSVM的特征选择算法49第五章基于STSVM的特征选择算法5.1引言在机器学习领域，特征选择就是从对象已有的特征中，筛选出一个适当的子集，使得该特征子集能很好的用于最终的学习目的。特征选择对于提高学习效果是非常关键的，恰当的算法可以消除不相关或者冗余的特征，减少数据维数，削减分类过程的计算量，降低分类所需时间。因此，特征选择方法一直是机器学习领域的重点和难点，其在神经网络、生物医学，目标识别等各方面都有着重要的研究价值和应用需求。SVM作为机器学习中一种重要的分类器，得到广泛的应用，近年来研究人员基于SVM将特征选择和分类融合在一起，通过利用一定的特征选择标准减少并优化支持向量，达到获得最佳特征组合的目的。在研究支持向量机几何特性的基础[31]上，Hermes等人于2000年提出了一种专门针对SVM的特征选择方法（简称L-J算法），其是以数据点到分类超平面的距离函数的梯度与各个坐标轴的夹角作为衡[26]量特征重要性的指标，进而筛选出有效特征。Weston等基于SVM提出寻找具有最小留一法误差界的特征子集，并通过梯度下降法代替贪婪算法，分别对模拟数[32]据和真实数据进行了特征选择实验。Grandvalet等基于SVM的经验风险最小化，提出通过调节缩放因子进行特征选择。2002年，Guyon等人以样本在训练过程中[33]权值大小的变化作为排序准则，提出基于SVM的递归特征消除算法(SupportVectorMachineRecursiveFeatureElimination，SVM-RFE)。和上述一些明显采用特征选择策略（无论和分类算法相独立或是嵌入在分类过程中）的算法不同的是，从分类器中直接获得稀疏解也可起到特征选择的作用。鉴于此思想，Bradley和Mangasarian于1998年提出基于凹最小化和支持向量机的[34]特征选择算法，并给出了SVM的l范数形式，其在文章中指出，l范数SVM可11以产生非常稀疏的解，对于一个线性分类器而言，稀疏解意味着分类超平面只取决于少量的输入特征，这就使得该算法在解决分类问题的同时完成特征选择的功能。在此基础上，2004年，Fung和Mangsarian提出通过快速牛顿算法来解决SVM[35]线性规划问题，从而实现特征选择。受l范数SVM思想的启发，Ye等人于2011年提出基于正则化技术的TWSVM1[36]特征选择算法(FRTWSVM)，其通过将点到平面的距离以l范数度量，给出了1TWSVM的线性规划形式，该算法在保留TWSVM原有优势的同时，还具有速度快以及非常稀疏性的优势。对线性问题而言，这意味着该方法可以减少输入空间的特征数，而对于非线性问题而言，则意味着其可以减少核函数的个数，此优势 50基于孪生支持向量机的特征选择与分类算法研究在高维分类问题中尤其重要。因此，对于第四章中提到的STSVM分类算法，我们通过给出其线性规划的形式，从而达到提高运算速度以及压缩输入空间特征数目的效果，并给出实验验证。5.2基于支持向量机的特征选择5.2.1SVM-RFE特征选择算法[33]作为嵌入式特征选择的典型算法，SVM-RFE是由Guyon等人于2002年提出，其核心思想是使用SVM训练样本，并将分类器的权值大小作为特征排序准则。对于训练样本，如果将其中的一维特征排除，则SVM训练时的权向量w将发生变化，根据变化量的大小，可以确定相应特征的重要程度，变化越大的特征越重要。具体算法流程如下所示：输入：训练集{}x，类标{}yii初始化：特征集s，特征排序列表r[]重复以下过程至s[]1.用特征集s训练SVM分类器2.计算权值向量wkyxkkk23.计算排序准则c(w)，isii4.寻找权值最小特征fargminc()5.更新特征排序列表r[s(f),r]6.移除具有最小排序准则的特征ss(1:f1,f1:length(s))输出：特征排序表r2其中，c(w)为排序准则，在每一次循环中，具有最小c的特征将被移除，iii然后SVM对剩余的特征重新训练以获得新的特征排序。SVM-RFE通过迭代执行这一过程，最后得到一个特征的排序表。Guyon在文章中指出，为了提高计算速度，可在每次循环中排除多个特征。5.2.2基于线性规划SVM的特征选择SVM-RFE作为一种嵌入式特征选择算法，其是将特征选择嵌入在分类过程中，和SVM-RFE不同的是，从SVM分类器中直接获得稀疏解也可起到特征选择的作用。鉴于此思想，Bradley和Mangasarian于1998年提出基于凹最小化和支持 第五章基于STSVM的特征选择算法51[34]向量机的特征选择算法，并给出了SVM的l范数形式(LPSVM)，其在文章中指1出，l范数SVM可以产生非常稀疏的解，对于一个线性分类器而言，稀疏解意味1着分类超平面只取决于少量的输入特征，这就使得该算法在解决分类问题的同时完成特征选择的功能。对一组样mn的样本数据X，其中m为样本个数，n为每个样本的特征维数，D是由其类标组成的对角矩阵，LPSVM目标优化函数如下所示：Tminwce1s.t.D(Xweb)e(5-1)0定义wpq,p0,q0，则上式可写为：TTmine(pq)ces.t.D(X(pq)eb)e(5-2)p,q,0Mangasarian指出通过求解此线性规划即可获得相应的超平面参数(w,b)，并且可以获得非常稀疏的解。5.2.3基于正则化技术的TWSVM特征选择Ye等在文献[36]中指出，若直接将TWSVM写成l范数的形式，并不能保证1得到稀疏的解，因此，作者首先对TWSVM进行修正，通过将惩罚项由l范数改1T2(1)(1)T为l范数，并向目标函数中引入正则项[wb]，从而提出正则化TWSVM2(RTWSVM)。给定两类n维空间的m个训练点，分别用mn的矩阵A和mn的12矩阵B来表示+1类和-1类，m和m分别是两类样本的数目，RTWSVM的目标优12化函数如下所示：(1)(1)21(1)T(1)T21TminAweb[wb]c11RTWSVM122(5-3)(1)(1)s.t.(Bweb)e22(2)(2)21(2)T(2)T21TminBweb[wb]c22RTWSVM222(5-4)(2)(2)s.t.(Aweb)e11令H[Ae]，G[Be]，将式(5-3)、(5-4)转化为对偶形式：12T1TT1TDRTWSVM1maxeG(HHI)(GIc)(5-5)212T1TT1TDRTWSVM2maxeH(GGI)(HIc)(5-6)122超平面参数可以通过下式获得：(1)(2)wT1TwT1Tu(1)(HHI)G,v(2)(GGI)H(5-7)bb 52基于孪生支持向量机的特征选择与分类算法研究正则化后的TWSVM除保留了TWSVM的原有优势外，其还是一个强凸优化TT问题，并且由于目标函数中正则项的加入，避免了TWSVM中HH与GG奇异性的问题，经验上提高泛化能力，为提出TWSVM特征选择算法提供了先决条件。因此，在RTWSVM基础上，将正则化项、平面与本类样本距离及惩罚函数用l范1数度量，给出TWSVM的线性规划形式(FRTWSVM)：T(1)(1)(1)(1)TTminAweb[wb]ce112FRTWSVM111(5-8)(1)(1)s.t.(Bweb)e,022T(2)(2)(2)(2)TTminBweb[wb]ce221FRTWSVM211(5-9)(2)(2)s.t.(Aweb)e,011(1)(1)(2)(2)此线性规划问题中的(w,b)和(w,b)可直接通过优化工具箱求解来获n得，和TWSVM相同，在得到超平面的参数之后，对于任意一个样本xR，就可以通过计算其距两类样本超平面的距离来判断其类别。5.3基于线性规划STSVM(LP-STSVM)的特征选择5.3.1算法原理在本小节中，对于第四章中提出的STSVM分类算法，为了提高STSVM的运算速度以及压缩输入空间特征数目，我们用l范数来度量点到平面的距离，给出1mnSTSVM的线性规划形式。对于一组样本数据XR，分别用矩阵A和B表m1nm2n示正负两类样本，线性规划STSVM(LinearProgramStructuralTwinSVM，LP-STSVM)目标优化函数如下所示：(1)w(1)(1)TminAwebRceLP-STSVM1111b(1)12(5-10)1(1)(1)s.t.(Bweb)e,022(2)w(2)(2)TminBwebRceLP-STSVM2212b(2)21(5-11)1(2)(2)s.t.(Aweb)e,011A0B0其中R,R。120101(1)(2)ww定义HAe，GBe，upq，vpq，则上12(1)11(2)22bb述目标函数可以表示为：TTTmine(HpHq)e(RpRq)ce111111112LP-STSVM1(5-12)s.t.G(pq)e,0,p0,q011211 第五章基于STSVM的特征选择算法53TTTmine(GpGq)e(RpRq)ce222222221LP-STSVM2(5-13)s.t.H(pq)e,0,p0,q022122(1)(1)(2)(2)通过求解上述线性规划问题，可得到超平面参数(w,b)和(w,b)的值，n对于任意的一个样本xR，我们通过计算它离两个超平面的距离来确定其所属类别。通过引入核函数，可以将其推广至非线性情况，基于核空间的LP-STSVM的两个超平面可表示为：(1)(1)(2)(2)K(x,C)ub0,K(x,C)ub0(5-14)其中CAB，K为选取的核函数，非线性LP-STSVM优化问题为：(1)u(1)(1)TminK(A,C)uebRceKLP-STSVM1111b(1)12(5-15)1(1)(1)s.t.(K(B,C)ueb)e,022(2)u(2)(2)TminK(B,C)uebRceKLP-STSVM2212b(2)21(5-16)1(2)(2)s.t.(K(A,C)ueb)e,011TT(C)(C)0(C)(C)0AB其中R1，R2。0101(1)(2)uu定义SK(A,C)e,QK(B,C)e,zpq,zpq,121(1)112(2)22bb则上述目标函数可以表示为：TTTmine(SpSq)e(RpRq)ce111111112KLP-STSVM1(5-17)s.t.Q(pq)e,0,p0,q011211TTTmine(QpQq)e(RpRq)ce222222221KLP-STSVM2(5-18)s.t.S(pq)e,0,p0,q022122从以上分析中可以看出，KLP-STSVM在形式上完全类似于LP-STSVM，不同的是，KLP-STSVM将LP-STSVM模型中的A和B置换为K(A,C)和K(B,C)，因此其求解过程完全等同于LP-STSVM。5.2.3实验结果及分析[62]在本小节中，我们将LP-STSVM算法在UCI机器学习数据和COIL-20图像识别数据库上进行实验，并和前文提到的GEPSVM、TWSVM、FRTWSVM及STSVM进行性能比较。实验一UCI机器学习数据库为了验证所提出LP-STSVM算法在特征选择上的有效性，将其在UCI机器学 54基于孪生支持向量机的特征选择与分类算法研究习数据库的5组数据上进行仿真实验，各数据详细描述于表5.1中。表5.1实验中使用的数据集描述数据集特征维数样本个数类别数目Hepatitis155192Wdbc569302Wpbc198322Spect267222Spectf267442对于每组数据，我们选其50%作为训练集，剩余的50%作为测试集。线性情i况下，所有参数均从2i9,...,9中选取；对于非线性情况，采用高斯核函数2TT2K(x,x)exp(xx)，并且为了降低参数选择时间，非线性情况下所有参i数均从10i3,...,3中选取，对于多类问题，采用“一对一”策略，并通过Mosek优化工具箱来求解线性规划问题。我们从测试识别率、10此训练标准差、训练时间和输入特征维数四方面来进行评价，10次独立实验的平均结果如下表5.2、5.3所示。表5.2各算法在UCI数据集上的性能比较（线性核）GEPSVMTWSVMFRTWSVMSTSVMLP-STSVMTest±std(%)Test±std(%)Test±std(%)Test±std(%)Test±std(%)数据集Time(s)Time(s)Time(s)Time(s)Time(s)NfeaNfeaNfeaNfeaNfeaHepatitis77.79±0.1980.39±0.1179.70±0.1480.00±0.1579.87±0.130.00130.01270.00590.01800.0066191916.651910Wdbc92.54±0.0296.55±0.0288.17±0.7897.36±0.0193.56±0.060.00180.02680.01681.62080.0240303028.353024Wpbc68.21±0.2076.57±0.1075.22±0.0776.77±0.1376.16±0.090.00100.01880.01010.19640.0183323225.93216Spect32.71±0.0582.78±0.0982.18±0.0883.31±0.0483.76±0.100.00080.01270.00820.06560.0091222220.452210.5Spectf26.47±0.4080.75±0.0580.53±0.0480.90±0.0580.53±0.040.02690.01220.00990.02030.0124444428.64422表5.3各算法在UCI数据集上的性能比较（高斯核）GEPSVMTWSVMFRTWSVMSTSVMLP-STSVMTest±std(%)Test±std(%)Test±std(%)Test±std(%)Test±std(%)数据集Time(s)Time(s)Time(s)Time(s)Time(s)NfeaNfeaNfeaNfeaNfeaHepatitis82.73±0.0982.47±0.0682.21±0.1482.73±0.0982.57±0.130.14550.02030.01090.10440.0066191915.151911Wdbc96.47±8.0997.18±0.00996.17±0.7897.36±0.0196.56±0.061.45310.25120.01681.62081.0240303025.153022Wpbc76.21±0.0576.67±0.1275.22±0.0776.77±0.1376.76±0.090.01100.02910.01010.19640.1083323230.23215 第五章基于STSVM的特征选择算法55Spect85.71±0.0583.31±0.0482.18±0.0883.31±0.0483.76±0.120.05020.05500.00820.56560.2591222220.453211.8Spectf87.97±0.2380.45±0.0980.43±0.0780.53±0.0980.46±0.040.09730.05410.02990.45940.1124444426.94422从以上结果中可以直观的看出：1)LP-STSVM在保证得到与其他分类算法性能相当的前提下，得到了远快于STSVM的训练速度，大大缩短了训练时间。2)除了时间上的优势以外，LP-STSVM的另外一个优势是其可以得到稀疏的解，即拥有好的特征选择能力，l范数GEPSVM、TWSVM则无稀疏解，需要用2到所有的特征。例如在Spectf数据上，FRTWSVM需28.6个特征，LP-STSVM算法需22个特征，而其他算法都需要44个特征。实验二COIL-20数据库为了进一步验证LP-STSVM在特征选择上的有效性，我们在大数据集COIL-20上测试上述五种算法。COIL-20数据库包含20个物体的1440幅图像，每个物体有72幅图像，每幅图像的尺寸为3636维，图5.1给出了COIL-20数据库中20个个体的图像样本示例。图5.1CIOL-20数据库中20个个体的图像样本在实验中，我们从每类中随机选取9幅图像作为训练集，剩余的63幅图像组i成测试集，实验中采用线性核，所有参数均选自集合10i3,...,3，对于多类分类问题，采用“一对一”策略，实验中涉及到的线性规划问题及二次规划问题的计算均通过Mosek优化工具箱来求解。表5.4给出了各算法在COIL-20数据库中的实验结果。表5.4各算法在COIL-20数据库上的性能比较GEPSVMTWSVMFRTWSVMSTSVMLP-STSVMTest(%)Test(%)Test(%)Test(%)Test(%)Time(s)Time(s)Time(s)Time(s)Time(s)NfeaNfeaNfeaNfeaNfeaCIOL-2090.0092.3091.0092.6291.890.35040.51230.42110.99450.698710241024786.41024418.55从上述表格中可以很直观的看出，l1范数STSVM可以得到很稀疏的解，对于1024维的COIL-20数据，GEPSVM、TWSVM和STSVM三种l范数分类器均需2要1024个输入特征，而FRTWSVM需要786.4个输入特征，LP-STSVM仅需要418.55个输入特征，并且可以得到与其他算法性能相当的识别结果，同时也缩短 56基于孪生支持向量机的特征选择与分类算法研究了训练时间。5.3本章小结本章在深入学习线性规划SVM和线性规划TWSVM的基础上，通过用l范数1来度量样本点到分类超平面的距离，给出了STSVM的线性规划形式，该算法无需求解二次规划问题，仅需求解一个线性方程系统。实验证明，LP-STSVM在保证得到与STSVM相当的分类性能及较快的计算速度上，还可以得到非常稀疏的解。对线性问题而言，这意味着该方法可以减少输入空间的特征数，而对于非线性问题而言，这意味着LP-STSVM可以减少核函数的个数，此优势在高维分类问题中尤其重要。 第六章总结与展望57第六章总结与展望6.1本文总结TWSVM作为近年来的一个研究热点，它还有很多方面存在不足，需要进一步研究完善。本文在深入研究TWSVM的基础上，从TWSVM未考虑到数据结构信息的缺陷出发，对TWSVM进行改进，并取得了一定成果，全文工作总结如下：(1)从流形学习进行考虑，通过将数据的流形结构引入至TWSVM分类目标函数中，提出基于流形结构的TWSVM(MTSVM)，其主旨是假设所处理的数据采样于一个潜在的流形上，通过建立类内散度矩阵，获得数据内部的流形结构，并将其引入到目标函数中，使得类内邻近样本之间的距离最小化，不同类样本之间的间隔最大化。进一步，为了提高其计算速度，提出基于流形结构的最小二乘TWSVM(LS-MTSVM)。(2)通过采用聚类技术，提出基于聚类结构的TWVM(STSVM)分类器，其通过对数据在类内进行聚类，将获得的结构信息以协方差矩阵的形式引入到分类算法的目标函数中，在保证各类数据都尽量围绕在其分类面周围的同时，使得同一类内数据分布更加紧凑。进一步，为了提高其计算速度，提出基于聚类结构的最小二乘TWSVM(LS-STSVM)。此外，对于STSVM在处理非均衡数据时存在的问题对其进行改进，提出非对称型STSVM(AS-STSVM)。(3)本文着眼于支持向量机在雷达辐射源个体识别研究中的应用，给出了一般辐射源识别的流程框架，并将文中提出的MTSVM和STSVM算法应用其中，对实测的雷达辐射源数据的实验结果初步验证了所提方法的有效性。(4)在所提出的STSVM分类算法的基础上，构造了基于STSVM的特征选择算法(LP-STSVM)，该算法只需求解一个线性规划，在保证得到与STSVM相当的分类性能以及较快的计算速度上，此方式还减少了输入空间的特征数，对于非线性问题，其可以减少核函数数目。6.2未来展望由于TWSVM是近几年才发展起来，虽然国内外对它的研究已有一定基础，但还有许多需要进一步研究的地方，而算法的工程应用问题也值得关注。本文虽然对TWSVM分类算法和其应用的相关问题进行了初步的研究，取得了一定的研究成果，但是依然存在许多问题需要进一步研究： 58基于孪生支持向量机的特征选择与分类算法研究(1)本文所提出的STSVM算法是基于聚类技术的分类算法，其可看作是聚类粒度分类器，因此可以将其和粒度计算结合起来，在粒度SVM的基础上提出粒度TWSVM。(2)本文中提出的非对称型STSVM算法仅在线性情况下做了实验分析，对于非线性情况，可考虑引入约减核技术。(3)对于MTSVM和STSVM算法，由于矩阵奇异导致二次规划问题不可解或者训练时间过长，因此对于如何避免矩阵奇异问题仍有待研究。(4)对于文中提出的基于特征选择的STSVM(LP-STSVM)算法，本文直接使用优化工具箱来求解线性规划，可参考文献[30,31]中的思路，结合外罚问题求解该线性规划，并通过牛顿法来快速求解。 致谢59致谢光阴荏苒，弹指间两年半的硕士研究生生涯即将结束，回首这两年半的求学历程，对那些引导我、帮助我的人，我心中充满了感激。首先，衷心感谢我的导师姬红兵教授，感谢他对我的悉心指导以及在生活中给予的关心和帮助！姬老师渊博的专业知识，严谨的治学态度，精益求精的工作作风，宽以待人严以律己的做人准则和诚信正直的品格深深的影响着我，不仅使我在学术方面不断进取，还使我明白了许多为人处世的道理。在此，谨向我的导师姬红兵教授表示最崇高的敬意和最衷心的感谢！感谢王磊老师，他作为我的指导老师，一直负责指导我硕士期间的科研工作，王老师活跃的科研思维，追求完美的工作精神和对学术的热忱带给我很深的影响，与他的沟通和交流，使我在学术上、工作上和生活上都得到极大的启发。此外，感谢王老师对本论文的全面审阅和修改。感谢课题组的李林老师、朱明哲老师、史亚博士、马文涛、叶韬成、王飞、周乐囡等同学以及教研室的李翠芸老师、刘靳老师、臧博老师、欧阳成博士、杨金龙博士、樊振华博士、张文博博士、张永权博士等师兄师姐，还有张一川、董青峰、王苏君、苏雪妍、林克盛、刘龙、钟茜怡、王少华、翁元龙、王捷、池骋等同学。在与他们的相处过程中，我收获了真诚的帮助与关爱，这是我人生中获得的一笔宝贵财富！感谢我的舍友苏雪妍、王苏君、苏秀妮，感谢她们两年多的陪伴，为我的硕士生涯增添了无限乐趣。衷心地感谢为评阅本论文而付出辛勤劳动的各位专家和老师，感谢你们在百忙之中能够抽出宝贵的时间并提出宝贵的意见和建议。在校期间，自己的每一点进步无不凝结着师长、朋友们的关怀。借此机会，对所有给予我帮助和指导的老师、同学致以诚挚的谢意。感谢我的父母和其他的亲人。他们辛勤地抚育我成长，并从小教会了我独立思考、不怕困难的信念。这份血浓于水的亲情令我无以回报，也是我坚持一直走下去的源源不断的动力。 参考文献61参考文献[1]李波.基于流形学习的特征提取方法及其应用研究.中国科学技术大学博士学位论文.2008[2]V.Vapnik.TheNatureofStatisticalLearningTheory.SpringerVerlag.NewYork.1995.[3]J.C.Burges.ATutorialonSupportVectorMachinesforPatternRecognition.DataMiningandKnowledgeDiscovery.1998,vol2:121-167.[4]E.Osuua,R.Freund,F.Girosi.TrainingSupportVectorMachines:anApplicationtoFaceDetection.ProceedingsofIEEEConferenceonComputeVision.1997:130-136.[5]N.Matic,I.Guyon,J.Denker.Writer-adaptationforOn-lineHandwrittenCharacterRecognition.Proceedingsofthe2ndInternationalConferenceonDocumentAnalysisandRecognition.1993:187-191.[6]V.Vapnik,S.Golowich,A.Smola.SupportVectorMethodforFunctionApproximation,RegressionEstimation,andSignalProcessing.NeuralInformationProcessingSystems.1997:9-16.[7]M.Belkin,P.Niyogi,andV.Sindhwani.ManifoldRegularization:AGeometricFrameworkforLearningfromLabeledandUnlabeledExamples.JournalofMachineLearningResearch.2006,vol.7:2399-2434.[8]X.Wang,F.ChungandS.Wang.OnMinimumClassLocalityPreservingVarianceSupportVectorMachine.PatternRecognition.2010,vol.43:2753-2762.[9]X.C.Wang,Y.M.Niu.ImprovedSupportVectorsforClassificationthroughPreservingNeighborhoodGeometricStructuralConstraint.OpticalEngineering.2011,vol.50:0872021-08720216.[10]P.K.ShivaswamyandT.Jebara.EllipsoidalKernelMachines.Processingofthe12thInternationalWorkshoponArtificialIntelligenceandStatistics.2007:1-8.[11]G.R.G.Lanckriet,L.E.Ghaoui,C.Bhattacharyya,andM.I.Jordan.ARobustMinimaxApproachtoClassification.MachineLearningResearch.2002,vol.3:555-582.[12]K.Huang,H.Yang,I.King,andM.R.Lyu.LearningLargeMarginClassifiersLocallyandGlobally.Proceedingsofthe21thInternationalConferenceonMachineLearning.2004:1-8.[13]D.Yeung,D.Wang,etc.StructuralLargeMarginMachines:SensitivetoData 62基于孪生支持向量机的特征选择与分类算法研究Distributions.JournalofMachineLearningResearch.2007,vol.68:171-200.[14]H.Xue,S.C.Chen,andQ.Yang.StructuralRegularizedSupportVectorMachine:AFrameworkforStructuralLargeMarginClassifier.IEEETransactionsonNeuralNetworks.2011,vol.22,573-587.[15]G.Fung,O.L.Mangasarian.ProximalSupportVectorMachineClassifiers.Proceedingsofthe7thInternationalConferenceonKnowledgeandDataDiscovery.2001:77–86.[16]O.L.Mangasarian,E.W.Wild.MultisurfaceProximalSupportVectorClassificationviaGeneralizedEigenvalues.IEEETransactionsonPatternAnalysisandMachineIntelligence.2006,vol.28:69-74.[17]R.K.Jayadeva,R.Khemchandani,andS.Chandra.TwinSupportVectorMachineforPatternClassification.IEEETransactionsonPatternAnalysisandMachineIntelligence.2007,vol.29:905-910.[18]M.A.Kumar,M.Gopal.ApplicationofSmoothingTechniqueonTwinSupportVectorMachines.PatternRecognitionLetters.2008,vol.29:1842-1848.[19]M.ArunKumar,M.Gopal.LeastSquaresTwinSupportVectorMachinesforPatternClassification.ExpertSystemswithApplications.2009,Vol.36:7535-7543.[20]D.Wang,N.Ye,Q.L.Ye.TwinSupportVectorMachinesviaFastGeneralizedNewtonRefinement.Proceedingsofthe2thInternationalConferenceonIntelligentHuman-MachineSystemsandCybernetics.2010:62-65.[21]Y.H.Shao,C.H.Zhang,X.B.WangandN.Y.Deng.ImprovementsonTwinSupportVectorMachines.IEEETransactionsonNeuralNetworks.2011,vol.22:962-968.[22]X.B.Chen,J.Yang,Q.L.Ye,J.Liang.RecursiveProjectionTwinSupportVectorMachineviaWithin-ClassVarianceMinimization.Patternrecognition.2011,vol.44:2643-2655.[23]Q.L.Ye,C.X.Zhao,N.Ye,X.B.Chen.LocalizedTwinSVMviaConvexMinimization.Neurocomputing.2011,vol.74:580-587.[24]姜百宁.机器学习中的特征选择算法研究.中国海洋大学硕士学位论文.2009.[25]徐义田.分类问题中特征选择算法的研究.中国农业大学博士学位论文.2007.[26]J.Weston,S.Mukherjee,O.Chapelle.FeatureSelectionforSVMs.AdvancesinNeuralInformationProcessingSystems.2000,vol.13:668-674.[27]范劲松,方廷建.特征选择和提取要素的分析及其评价.计算机工程与应用.2001,vol.6:95-99.[28]A.W.Moore,M.S.Lee.EfficientAlgorithmsforMinimizingCrossValidation 参考文献63Error．The11thInternationalConferenceonMachineLearning.1994:190-198．[29]H.M.Lee,C.M.Chen.AnEfficientFuzzyClassifierwithFeatureSelectionBasedonFuzzyEntropy.IEEETransactionsonsystemsandcyberneticsPart.2001,vol.31:26-432.[30]E.Xing,M.Jordan,R.Karp.FeatureSelectionforHighDimensionalGenomicMicroarrayData.Proceedingsofthe18thInternationalConferenceonMachineLearning.2001:231-235.[31]L.Hermes,J.M.Buhmann.FeatureSelectionforSupportVectorMachines.Proceedingsofthe15thInternationalConferenceonPatternRecognition.2000:716-719.[32]Y.Granavalet,S.Canu.AdaptiveScalingforFeatureSelectioninSVMs.AdvancesinNeuralInformationProcessingSystems.2003,vol.15:553-560.[33]I.Guyon,J.Weston,S.Barnhill,etal.GeneSelectionforCancerClassificationusingSupportVectorMachines.MachineLearning.2002,vol.46:389-422.[34]P.S.BradleyandO.L.Mangasarian.FeatureSelectionviaConcaveMinimizationandSupportVectorMachines.MachineLearningProceedingsoftheFifteenthInternationalConference.1998:82-90.[35]G.FungandO.L.Mangasarian.AFeatureSelectionNewtonMethodforSupportVectorMachineClassification.ComputationalOptimizationandApplications.2004,vol.28:185-202.[36]业巧林,赵春霞,陈小波.基于正则化技术的对支持向量机特征选择算法.计算机研究与发展.2011,vol.48:1029-1037.[37]莫丽娴.流形学习算法研究.中山大学硕士研究生学位论文.2010.[38]曾宪华.流形学习的谱方法相关问题研究.北京交通大学博士研究生学位论文.2009.[39]闫志敏.刘希玉.流形学习及其算法研究.计算机技术与发展.2011，vol.21:99-102.[40]J．Tenenbaum,V.D.Silva,J.Langford.AGlobalGeometricFrameworkforNonlinearDimensionalDimensionalityReduction.Science.2000,vol.290:2319-2323.[41]R.A.Fisher.TheUseofMultipleMeasurementsinTaxonomicProblems.AnnalsofEugenics.1936,vol.7:179-188.[42]S.Roweis,L.Saul.NonlinearDimensionalityReductionbyLocallyLinearEmbedding.Science.2000,vol.290:2323-2326．[43]M.BelkinandP.Niyogi.LaplacianEigenmapsforDimensionalityReductionand 64基于孪生支持向量机的特征选择与分类算法研究DataRepresentation.NeuralComputer.2003,vol.15:1373-1396.[44]X.He,S.Yan,Y.Hu,P.NiyogiandH.Zhang.FacerecognitionusingLaplacianfaces.IEEETransactionsonPatternAnalysisandMachineIntelligence.2005,vol.27:328-340.[45]M.Sugiyama.DimensionalityReductionofMultimodalLabeledDatabyLocalFisherDiscriminantAnalysis.JournalofMachineLearningResearch.2007,vol.8:1027-1061.[46]UCI标准数据库:http://archive.ics.uci.edu/ml/.[47]手写数字数据库:http://www.cs.toronto.edu/~roweis.data.html.[48]C.W.Hsu,C.J.Lin.AComparisonofMethodsforMulticlassSupportVectorMachines.IEEETransactionsonNeuralNetworks.2002,vol.13:415-425.[49]Mosek工具箱下载地址:http://www.mosek.com/.[50]J.A.K.suykens,J.vandewalle.LeastSquareSupportVectorMachinesClassifiers.NeuralProcessingLetters.1999,vol.9:293-300.[51]NDC数据:http://www.cs.wisc.edu/~musicant/data/ndc.[52]王磊等.基于模糊函数代表性切片的运动雷达辐射源识别.系统工程与电子技术.2010,vol.32:1630-1634.[53]LindsayISmith.AtutorialonPrincipalComponentsAnalysis.2002.[54]高新波.模糊聚类分析及其应用.西安电子科技大学出版社.2004.[55]A.W.Moor.K-meansandHierarchicalClustering.2001.[56]S.Y.LuandK.S.Fu.ASentence-to-SentenceClusteringProcedureforPatternAnalysis.IEEETransactionsonSystems.1978,vol.8:381-389.[57]L.A.Zadeh.FuzzySets.InformationandControl1965:338-353.[58]J.H.Ward.HierarchicalGroupingtoOptimizeanObjectiveFunction.AmericanStatisticalAssociation.1963,vol.58:236-244[59]S.SalvadorandP.Chan.DeterminingTheNumberofClusters/SegmentsinHierarchicalClustering/SegmentationAlgorithms.Proceedingofthe16thIEEEInternationalConferenceonToolswithAI.2004:576-584.[60]Caltech101数据集:http://www.vision.ee.ethz.ch/~pgehler/projects/iccv09/.[61]T.Tommasi,F.Orabona,andB.Caputo.SafetyinNumbers:LearningCategoriesfromFewExamplesWithMultiModelKnowledgeTransfer.ProceedingsofIEEEConferenceonComputeVision.2010.[62]COIL-20数据:http://wwwl.cs.columbia.edu/CAVE/research/softlib/coil-20.html.[63]王磊等.基于模糊函数特征优化的雷达辐射源个体识别.红外与毫米波学报.2011,vol.30:74-79. 作者在读期间的研究成果65作者在读期间的研究成果科研情况1.负责国防预研项目“××××识别技术研究”中关于分类器设计的研究。