《大规模支持向量机分类算法与应用研究》由会员上传分享,免费在线阅读,更多相关内容在学术论文-天天文库。
^Northeasternv^JkasvUnjiversity硕士学位论文THES'ISFORMASTERSDEGREE论文题目大规模支持向量机分类算法与应用研究作者刘亚新学院中荷生物医学与信息工程学院专业生物医学工程指导教师张耀楠教授备奸二零一六年十二月 分类号级密UDC学位论文大规模支持向量机分类算法与应用研究作者姓名:刘亚新指导教师:张耀楠教授东北大学中荷生物医学与信息工程学院申请学位级别:硕士学科类别:工学学科专业名称:生物医学工程论文提交日期::年/>月论文答辩日期年仏月1学位授予日期:1纟年>月答辩委员会主席>:猶评阅人 ̄:召隻避东北大学2016年12月 AThesisinBiomedicalEnineeringg-TheResearchonLarescaleSuortVectorgppMachineandtheAlicationsppBLiuYaxinySuervisor:ProfessorZhanYaonanpgNortheasternUniversityDecember2016 独创性声明本人声明,所呈交的学位论文是在导师的指导下完成的。论文中取得的研究成果除加以标注和致谢的地方外,不包含其他人己经发表或撰写过一的研究成果,也不包括本人为获得其他学位而使用过的材料。与我同工作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示谢意。学位论文作者签名:0蝴日期:少学位论文版权使用授权书本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论文的规定:即学校有权保留并向国家有关部门或机构送交论文的复印件和磁盘,允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部或部分内容编入有关数据库进行检索、交流。作者和导师同意网上交流的时间为作者获得学位后:半年口一年口一年半口两年Y:?学位论文作者签名导师签名:Mil:錄I)签字日期:签字日期: ̄-I 东北大学硕士学位论文摘要大规模支持向量机分类算法与应用研究摘要随着信息化的发展,人们在生活中产生的数据量正在迅速增长,这些大数据有着取一之不尽,,用之不竭的价值可以被挖掘。和其他科学大数据样,在生物医学领域数据也面临着爆发式的增长。由于仅依靠人类的大脑无法处理海量的数据,因此怎样实现数据的智能化处理并且充分挖掘数据中蕴含的知识,成为了研宄者们的共识,通常数据处Su一理过程离不开机器学习的知识。支持向量机(pportVectorMachine,SVM)作为种针对小样本的机器学习方法,不仅是机器学习领域重要的理论,而且在大数据应用领域具有重要作用。近年来,SVM相关算法己经逐渐被应用到医学文本和医学图像等数据分类。但是算法需要大量反复的迭代和复杂的计算,而且随着数据量的增多,运算占用的内存空间也大幅增加。有时计算机的内存无法满足算法的运行,这限制了SVM的使用。传一个大的凸优化问题转化为一系列小的凸优化问题统的解决思路是将。但是基于这种思路而衍生出的算法在处理大规模数据集时运行缓慢。一本文构造了种基于代理函数的SVM分类算法,这种算法利用代理函数迭代求解SVM中的凸优化问题。引入代理函数不仅可以实现并行化运算,而且能够保证成本函数单调递减,降低了迭代的复杂度,节省运算成本。迭代公式通过代理函数的三条性质一推导获得,并且在MATLAB中实现。因为在凸二次规划问题中,全局最优解定满足KT条件1#1,所以对全局收敛性进行了证明。把经典的LIBSVM和SVM两种算法原理做了描述,重点介绍了软件包配置、使用以及参数设置。在实验阶段,使用数据发生器生成的NDC数据集及UCI数据库中的大规模数据集对算法进行测试,并将基于代理函数的Wh1SVM分类算法与LIBSVM和SVM的结果进行对比。经三组实验最后得出结论:面对大规模数据时基于代理函数的SVM分类算法能够对大规模数据高效的分类。最后,一组医学大规模文本数据,通过处理和数据转换后三种算法上我们选取,应用到,经实验对比一,进步验证了基于代理函数的SVM算法的实用性和优越性。关键词:医学大数据机器学习;支持向量机;代理函数分类算法;;--II 东北大学领士学位论文Abstract-tTheResearchonLargescaleSupporVectorMachineandtheAlicationsppAbstractW’iththedevelomentofinformatizationmassivedataareroducedraidlineolesp,ppypp-medve.Thevalueofiataisinexhaustibeitintobeexlore.Inticaiellibgdl,wagpdhebiolfd,thedataisrowininanexlosivewa.Researchesshowthattheanalsistomedicalbidataggpyyg!comarestoanexerienceddoctor.Becausehumancanthandlehugeamountsofdatathepp,yneedtoresearchhowtorealizetheintelligentdataprocessingandminetheknowledgeindataful.weusetheknowledttlyUsuallyeofmachinelearninindaarocessin.Suorvectorggpgppmachines(SVM)isatheoryofmachinelearningforsmalldatasetsandlaysanimortantpproleinthefieldofbigdataalications.Inrecentears,thetextcateorizationalorithmsandppyggmedicalimageclassificationalgorithmsbasedonsupportvectormachinehavebeenraduallgyapplied.Butusuallythealgorithmsneedalotofrepeatediterationandcomplicatedcalculation.Withtheincreasinoftheamountofdatathememoisaceincreasesreatlg,ypgy'andsometimescantsatisftheoerationofthealgorithmwhichlimitstheuseofSVM.Theyp,traditionalsolutionistochangealargeconvexoptimizationproblemintoaseriesofsmallconvexoptimizationroblems.Butthealorithmsroosedbasedonthistheorindealinpgppyg-withlargescaledatasetsrunslow.AnewVMmethodbasedonsurroateunctionwhichwouldsolveiterativeluadraticSgf,yqroramminotimizationroblembconstructinsurroatefunctionisintroducedinthispggppygg,paper.Introducingsurrogatefunctioncannotonlyrealizetheparallelcomputation,butalsoguaranteethemonotonedecreasinofcostfunctionandreducethecomplexityofgtThtttttieration.eupdaterulewouldbederivedfromhreeproperiesofhesxorrogaefuncionandrealizedinMATLAB.Indealingwiththeconvexuadraticprogramminroblemtheroofqgp,pofglobalconvergenceispresentedbecausetheglobalotimalsolutionmustsatisfytheKTp-condition.Intheexerimentalstaeusinthelarescaledatasetsfromdataeneratorandpg,gggUCIdatabasetotesttheSVMclassificationalorithmbasedonsurroatefunctionLIBSVMgg,lighttandSVM.Bythethreegroupsofexperimentswefinallydrawheconclusion:whendealinwithbidataclassificationtheSVMalorithmbasedonsurroatefunctionshowsangggg--Ill 东北大学碩士学位论文Abstract"efF-tttficientlresult.inalla〇uofmedicallarescaleexdaaafterrocessinandyy,^pgpgtransformationwaschosentotestthethreealgorithms.Byexperimentcontrast,thepracticalityandsuperiorityoftheSVMalorithmbasedonthesurroatefunctionwasfurtherverified.ggKewords:MedicalbidataMachinelearninguortVectorMachinesSVMSurroateg;Sgy;pp();fimctionClassificationalorithm;g—-IV 东北大学硕士学位论文目录独创性声明IMWH:Abstractill第11章绪论u研究背景及意义112.国内外研宄及发展现状31.2.1支持向量机分类算法4122..支持向量机扩展算法521..3支持向量机在医学领域应用71组织结构7.3本文的第2章支持向量机理论921.统计学习理论基础9211Van-evonenks..pikChi理论921经验风险最小化1..20'2.1.3结构风险最小化112.2从感知机到支持向量机122.2.1线性支持向量机152.2.2非线性支持向量机1821#13SVM20.SVM,LIB21甽.3.1SVM方法202.2LIBSVM.3方法21224.4本章小结第3章基于代理函数的大规模SVM设计25325.13.12.1代理函数设计流程531..2代理函数的性质273.2构造基于代理函数的SVM28321..代理函数的构建283.2.2迭代过程及推导33-V- 东北大学硕士学位论文3.3收敛性分析353.4A存处理373.5本章小结38第4章实验说明及结果分析394.1实验环境394.2实验过程40蚺14置.2.1SVM40配4.2.2LIBSVM配置424.2.3实验参数设置454.2.4实验过程与分析464.3生物医学领域应用实验54.44本章小结575第章结束语595.1本文工作总结595.2研究展望60参考文献63致谢67研究生期间发表论文情况69-V-I 东北大学硕士学位论文第1章绪论第1章绪论1.1研究背景及意义近年来,互联网科学技术、CloudComputing技术不断进步,使得大数据(BigData)越来越引起人们的重视。互联网的出现和发展缩短了人们之间的距离,而伴随着互联网科技的迅速发展,、数据库等相关技术的普及、高性能硬件设备的出现人们在生产生活“”中产生的数据量正以指数形式增长,而且数据的结构越来越复杂,大数据问题在这样的背景下产生了。如此海量的大数据有着取之不尽,用之不竭的价值,等待被挖掘。“”■被誉为大数据预言家的维克托迈尔-舍恩伯格教授曾经说过,大数据的价值可以比一一作汪洋大海中的座冰山,远远眺望只能看到冰山角,然而大多数的价值都深藏在海中,,。古往今来人们对于了解、记载、分析世界有着强烈的渴望这就是大数据发展不竭的动力和源泉。数据,可以从最不可能的地方提取出来。“”⑴一对于大数据的定义,可以概括为4V,定的规模性(Volume)特征即具有、2-5arie[]多种类(Vty)、更新速度快(Velocity)和最重要的价值密度低(Value)。结合生物医学领域,,分析以上四个特征。首先随着大数据在生命科学研宄过程中的应用和深入探索,生物医学领域的数据往往具有大规模特性:数据量大,种类多。例如,在基一因工程方向,通常对于个样本的人体基因组和转录组测序数据量会分别超过100GB30GB一和,考虑到次试验中通常会涉及到数百个甚至上万个人体样本,相关的数据量6一[]产出十分巨大。在医学成像领域,光学仪器曰臻进步,早在十几年前,幅CT存储量才10MB,现在的CT则含有320MB,甚至600MB的数据量,标准的病理图数据量5GB一。用这些数据量乘以人口数量和平均寿命近,仅个社区医院相应的图像存储量可以达到TB甚至PB级别高速性主要体现在两个方面一,其是数据产生的高速性,其二体现在数据处理方面,,医疗数据对处理结果处理速度有较高要求数据以极快的速度产生,需要进行实时处理,否则,数据将稍纵即逝或者延时的处理机制得到的结果价值低甚至无用,,。在种类繁多方面以人体为例,生理指标众多采集的信息从非生物电信号层面文本记录信息,到生物电层面的心电及脑电信号,还有医学成像层面的计算机断层成像及核磁共振成像等一。而这些海量的数据中包含了定的价值信息,需要深入挖“”掘,基于生物医学领域典型的4V特征,因此我们应该转变思维方式,依靠数据分析策略和机器学习手段,对生物医学大数据进行深入挖掘。一一此外样,生物医学大数据计算问题不仅仅是,和其他科学大数据个数据处理与--1 东北大学硕士学位论文第1章绪论一9[]分析的问题,还是个复杂系统与数据共同建模与计算的问题。生物医学研宄目标和过程的复杂性包括:不同数据的系统性整合需求、不同样本的对比需求、结果的统计等8[]等。这些均需要基于大数据进行数据建模并归纳规律。而且在样本的采样方式上,处理算法的不同均会使得研宄过程出现不确定性。科学大数据往往来自实验的获取,生物医学大数据亦是如此,在采集数据过程中有些差异性不可避免,这也均决定了生物医学大数据具有高度的不确定性。临床医疗卫生监测j?优选诊疗方法?扩大疾病检测范围^健康医学大数据VyX細鋪药物研发i|Ij?利用可穿戴设备?优化临床试验’?加强个性化健康管理?辅助药物疗效定位图I」健康医学大数据应用Fig.1.1Bigdataapplicationsinhealthandmedicalfields从计算机辅助医疗角度,对大数据进行挖掘和分析会带来创造性的价值。通过对大,:在辅助医疗量历史数据的整合分析医生在做诊断时就有了可靠的依据。研宂表明、新药品研究试验、疾病检测控制,、公众健康管理等方面健康大数据发挥了重大作用解决了医学领域广泛存在的信息分散,、片面化等问题提高了系统化分析和解决问题的能力,大幅度提升了医疗诊治的综合水平和规范性,创造极大的价值。由于仅依靠人类的大脑无法处理海量的数据,因此,如何实现数据的智能化处理并且充分挖掘数据中蕴含的知识,成为了研究者们的共识,通常离不。在进行数据处理时开机器学习的知识,但是传统的机器学习理论是针对小规模样本提出,难以用于大数据处理。针对此种情况,必须深入研究大数据背景下的数据挖掘算法和机器学习理论。本一文以机器学习中的支持向量机理论为基础,设计了种基于代理函数的大规模SVM分类算法,旨在对医学领域大数据问题进行快速准确的处理。-2- 东北大学硕士学位论文第1章绪论1.2国内外研究及发展现状50一机器学习于20世纪年代随着第代计算机的发明而被提出,在随后的十年间受到了广泛的关注,在20世纪60年代以后进入了冷静时期,在20世纪70年代重新受到人们的关注。传统的机器学习理论一般包含以下几个方面(1)理解并模拟人类的学习过程;(2)计算机和人类用户自然语言之间接口的研究;(3)不完全的信息进行推理的能力,即自动规划问题;(4)构造可发现新事物的程序。目前国内外常用的机器学习分类算法有支持向量机(SupportVectorMachine,简称12KNN以及BP[]),SVM、决策树神经网络下面我们对这几种常用方法做简单的介绍。决策树是比较直观的分类方法,利用决策树方法进行分类首先要从树的根节点幵始,对数据的特征进行分类,并按照分类的结果选择分支,在叶子节点处存放标签值作13【]为最终的输出结果。K-restneionear,KNN)是经典的模式识别统计学方法近邻法(kghb,将原始的最近邻方法(NearestNeighbor,NN)进行了改进。NN方法用类向量的中心表示类别,当有新样本D加入时,求出D到类向量中心的距离,新加入的样本D的类别即为距离最近的中心代表的类别。最近邻方法简单且容易执行,但是分类的精度不高,为了解决这个缺点,提出了K近邻算法。KNN算法能够保持简单有效的优势,如果训练集文本数量为m那么采用KNN方法的时间复杂度为0(n)。算法以训练集的分类为基础,计算新加入样本到训练集内样本点的距离,然后根据距离选择K个近邻,如果新加入样本与训练集中某个近邻匹配,那么直接用训练集中的样本类别做为新加入样本的类别。如果类为离散型取值,那么这K个样本中属于哪个类最多,测试样本就属于那个类。反,之,如果类为连续型取值输出取平均值。K近邻算法实际上是推迟了计算处理,训练过程时间复杂度低,是因为它仅仅是保存了训练集,直到有新的文本加入时才建立分类器,KNN的计算开销都推迟进行。这样也会导致,也就是说对每个新样本进行分类时一严重的问题:如果训练样本的数量很大,对于每个待分类样本,都要计算它到全体已知样本的距离,计算成本很大。神经网络算法通过模拟生物的神经元网络进行分类,经输入层、隐层与输出层的非M线性连接达到分类的目的。与支持向量机不同的是,它基于统计学理论中经验风险最-3- 东北大学硕士学位论文第1章绪论小化原则。在大多数研宄领域里,人工神经网络多采用反向传递方式BackProaation,(pg)然而从BP算法的搜索策略来看,虽然可以逼近大多数非线性函数,但是也难以规避的一些缺陷存在,负下降梯度法导致迭代复杂、优化速度慢,也容易陷入局部极小值,当搜索空间范围扩大,如果出现多峰值、不可微的情况就不能找到模型的最优解,也可能造成过学习等现象。这些缺陷在支持向量机理论中能够被很好解决。15一[20世纪60]理论由Vanik等人最早提出来年代,支持向量机p,是种具有潜力的分类技术。支持向量机在小规模样本的处理上成效颇丰,此外通过引入非线性核函数以及高维空间映射函数使得很多问题能够得到很好的解决。到了90年代,统计学习理论和人工神经网络等机器学习理论迅速发展,支持向量机在众多应用中得到逐渐完善。支一持向量机有着强大的理论基础,发展至今,已成为种较成熟的机器学习模式识别方法,并且越来越受到国内外研究人员的重视,研究内容包括算法本身的改善以及实际应用领域的性能研究。1.2.1支持向量机分类算法虽然传统的SVM算法在理论基础上较完备,但算法在实际应用方面,会存在样本的训练速度慢以及时间复杂度高等问题。所以,在SVM的研究中,如何提高分类速度一些亟待解决的问题。对小数据问题可以转化为二次规划和分类精确度仍是,但对于较大数据量时,算法在运行时,就会出现内存溢出而失效,也需要针对此问题的算法改进。国内外学者已经提出多种方法来优化大规模二次规划问题。经典的算法有以下几种:(1)块选算法(Chunkingalgorithm)15?Ch皿k[]BoVing算法由sei和apnik提出。原理是分类过程中忽略拉格朗日乘子为0的数据点,这样不仅不会影响最终的分类结果,还有效的提高了支持向量机的训练速度。所以分类时可以仅考虑支持向量(SupportVectorsSVs),,而忽略其它非支持向量。但是,由于在分类开始前SVs是未知的,所以需要将整个数据集分成训练集和测试集。使用训练集训练,然后用训练生成的模型对测试集进行测试,再将测试集中被误分的样本一与训练集中的SVs重新组成个训练集,其它的向量组成测试集,继续执行迭代过程,当所有向量都达到最大程度划分,迭代终止。支持向量的数量少是使用chunking算法的一个前提,,导致算法;若支持向量的数量过多迭代过程中,训练集的数量会逐渐增多运行缓慢,从而失去算法的优势和价值。(2)分解算法(Decompositionalgorithms)chunk一Osuna等人提出的分解算法与ing算法类似,将处理所有数据转化为处理部一4— 东北大学硕士学位论文第1章绪论分数据。首先将数据集划分为训练集和非训练集,保持训练集中元素数量不变,在解决每个子问题时一一,将训练集中个数据替换为个非训练集中被误分的数据,重新进行优16[]化。Osuna的算法与chunking算法的不同之处在于Osuna的算法中训练集有固、迭代定的元素数量此外,在Osuna的算法优化过程中,非训练集里的数据的拉格朗日乘子;一固定为前次迭代的结果一,不像块算法,除训练集以外其他样本的拉格朗日乘子律置0。但Osuna的算法的训练集选择策略采取的是随机方式,限制了算法的应用。_(a)SVM文献在Osuna提出的方法前提下对训练集的选择作了改进。利用最大速度下降法选取工作集,即训练集。通过采用可行方向法可以提高工作集的选择效率,将不符合-Tucker条Kuhn件且在下降方向上的数据构成工作集,在这个工作集上求解QP最优解。一VM1#1Hght,SVM作为对比算法之这就是S算法思想的来源,其原理将在第二章介绍。(b)SMO18M[]euentialinimalOtimization,SM0由Patt序列最小优化算法(Sqp)l提出。该算法实质上也属于分解算法,是在求解拉格朗日算子过程中,将含有M个变量的求最优解一一问题转化为多个仅包含二变量的优化问题,其中个变量可以用另个变量线性表示出来。SM?算法相比于chunking算法和Osuna算法在运行速度上更具有优势,因为它不需处理大矩阵,所以计算速度有较大提高,也是目前流行的SVM算法。虽然SMO算一,与此同时,就会需要更多的迭代次数法将训练集规模缩减了,所以实际上这过程并没有节约运算成本,具有重要的意义可以围绕。但是转换思想的提出,因为后续的研宄11#迭代过程研究快速算法,从而提高整体运算效率。SVM和SM0是支持向量机中的经典算法,,在本课题中将二者与新提出的SurrSVM方法进行多角度对比具体实验方法、配置以及实验过程将在第3章和第4章中介绍。122..支持向量机扩展算法近年来,随着国内外研宄者们对SVM研究的逐渐深入,新的SVM算法层出不穷。早期的支持向量机是针对于二分类的情况提出的,但是很多实际问题二分类SVM无法解决,因此需要不断对SVM扩展。针对多分类情况提出的多分类支持向量机是二分类一个多分类一支持向量机的推广。通常构建SVM有两种方式:第种方式将大的分类问VM----二t题分解,构造多组分类S,性能较好的常用算法有oneagainstall和oneagainsone方法二二种一个更大的二次规划问题虽然这种方法思想简,叉树算法等;第方式构造,单,所,但是算法比较复杂以效率方面明显低于前面的方法。--5 东北大学硕士学位论文第1章绪论一one-st-amethod(1)对多方法(againll)一类数据当作集合A这种方法是把多分类中的,剩余其他类别的样本构成的整体9[1]作为集合B,这样就可以将多分类变为两分类。然而这种算法在对样本进行训练时,一时间成本与样本集类别数有关,旦训练集规模增大,则时间消耗过多。此外,one-aanst-amethod方法会造成A与数据集合BAgill数据集合元素数量相差过多,集合的元素数往往远小于集合B的元素数,会降低对大数据中小样本数据识别精度。—一--(2)对方法(oneagainstonemethod)该方法的原理是在M类数据中任取两类:集合A与集合B,将多分类转换成为多二值M-个二分类问题,再利用分类器进行分类运用这种方法需M(l)/2个超平面,从数学角度分析,训练集数据的种类数与分类的次数是二次函数的关系,使得一--one-aa-aoneaainstone方法的分类次数超过了ginstll方法。但是,相比于对多方法,g一一B一对对方法每次分类时很少出现集合A与集合元素数量相差过大的情况,使得一一对多方法方法对小样本数据的分类准确度优于。二叉树分类法是决策树分VM的融合思想是首先构建一类问题与S,算法的个二叉24[]树,将非叶子节点用支持向量机进行分类,用叶子节点表示数据的类别。这种方法既一一一克服了对方法中当数据的种类数增加时,分类次数大幅增加的问题,又克服了对一多方法对大数据中小样本数据识别精度过低的问题,。但是这种方法会产生连锁错误次分类错误有可能会导致后续的分类均产生错误的结果,因此这种方法对非叶子节点中SVM的分类准确度要求高。总之,目前的多分类算法主要研究方向包括提升多分类SVM的推广能力、分类精准度以及算法的运行速度,减少分类时间。在进行SVM分类时,实际问题中可能会遇到样本的数量不平衡的情况,根据统计学特性以及支持向量机训练样本集的显著倾向性可知,当样本集里数据量较大时,分类。误差小,数据量小时,分类误差相对较大所以,为了解决由于样本数据量不同导致的25一分类误差问题[],吴洪兴等人提出了遗传交叉运算方法,将方法运用到样本少的类别。中,王娜,李霞,通过计算生成新的样本最终目的是让两类样本数据量尽可能的持平一VSVM种类加权的双,当A类和B类中样本数不平衡时等人设计了,分别为两类样本集取不同的惩罚参数,这样可以调整最优决策面的位置,从而提升分类适用性能。一212223[][][]:、、R此外,有些新型的支持向量机分类算法被提出GSVMSSVMSVM等,这些算法通常从优化二次规划问题着手,改变约束条件,使得问题更易求解。从26mooVM模型[SVM的模型角度,Lee等人提出了SthS,用光滑函数SigmoidMt替二次-6- 东北大学硕士学位论文第1章绪论一规划中非光滑、不可微部分,将目标函数转为个二阶光滑函数,可以更易求解。在解决非线性问题时,对核函数参数优化调整的常用准则有交叉验证(CrossValidation,CV)、一--留法(Leaveoneout)等。总而言之,提升运算效率和减少运算时间,找到更好的凸一直是研宄者们探索的方向函数以解决二次规划问题,。1.2.3支持向量机在医学领域应用(stattearnntheor,SLT)作为有效的基于统计学习理论isicalligy的机器学习算法之一SVM主要被用在模式分类和回归两方面,,并在很多领域发挥优势如信息检索和,27[],,。,文本分类,人脸或语音识别社交网络疾病识别等在医学领域当采用传统分析28[]不能得到较好的预测时,利用支持向量机能够达到良好的预测效果。例如,张晓丹等29一3Q[][]人构造了种光滑支持向量机模型,应用于心脏病模型诊断献;文以乳腺肿瘤数据JC一为应用背景,基于特征值进行病理分类,Aampouraki等人开发种基于SVM理论的31-[]edoctor应用程序,通过有监督的学习,构建模型,再用来进行自动化诊断。通过输入病人信息-doctor软件自动诊断和预测病人的健康状况。,e随着数字化医疗的快速发展与信息化建设系统的普及,国内外各医疗机构积累了大量患者临床数据信息和电子病例等,这些大量复杂的数据里蕴藏着很多有价值的信息。,临床采集的数据越来越全面,也越来越复杂此外,,高精度医学医学影像设备不断更新怎样更好的处理、分类、分析健康医疗大数据,整合碎片信息等问题是计算机辅助医疗方面研宄的重要方向。因此,深入研究数据挖掘算法中的大规模数据分类之后,本课题一一SVM分类算法设计了种全新的基于代理函数的大规模。通过第4章系列实验数据表明,该算法在大规模数据分类中有明显的优势,最后通过实际的医疗数据文本分类实验,SurrSVM算法可以更好地解决医学领域的大规模数据,表明与现存的经典算法相比分类问题。1.3本文的组织结构尽管在很多领域中,支持向量机的应用都很成功,但在处理大规模数据时,仍然存在运算速度和分类精度相矛盾的问题,因此本文深入研究了大规模支持向量机数据分类VM1#L问题SVM。和IBSVM,研究全新的、适用于大数据背景下的与经典算法S相比一,本课题设计的是种基于代理函数的大规模支持向量机分类算法。经过多角度、多组的对比实验证明新提出的算法具有准确性和优越性。本文的组织结构如下:“”第1章为绪论。介绍了生物医学大数据的4V特点及大数据背景下的机器学习算-7- 东北大学硕士学位论文第1章绪论法的重要性。国内外研宄领域在支持向量机分类算法方面的研宄进展,在二分类、多分类以及数据不平衡情况下的支持向量机研究现状,举例说明在医学领域支持向量机的应用前景,并说明了大数据背景下本课题的研宄意义。第2章为支持向量机基本的理论。首先介绍了支持向量机理论的SLT基础,然后介绍了SVM的发展过程:从感知机算法到支持向量机过渡,以及超平面和最优超平面的原理,通过线性可分、近线性可分及线性不可分这三个方面介绍支持向量机的基本理论。1#%最后介绍的本课题用到的两种作为对比的经典SVM方法:SVMLIBSVM。第3章为大规模支持向量机分类算法设计。首先引入代理函数,介绍了它的定义和性质,针对二次规划模型构造SVM中的代理函数,利用非负矩阵分解的思想,同时结合代理函数的性质求解出SVM迭代公式并将迭代算法在MATLAB中实现。其次,由于二次规划的全局最优解一定要满足KT条件,所以对全局收敛性以及KT条件的判定进行了说明。最后,为了避免中间值对内存的损耗,对迭代中间变量做了处理,避免大规模矩阵的产生。第4章实验说明与结果分析1^。首先对实验环境和数据集的选择以及SVM和LIBSVM的配置过程做了详细说明,然后对三种算法的实验参数进行选择,再对实验过,SurrSVM程做说明将新算法与两种经典算法进行多个维度的实验对比,并对实验结一组医学文本数据果做了详细分析,对SurrSVM算法的。最后选取实际应用性能进行验证。第5章总结。总结全文的工作内容和创新点,对大规模支持向量机的分类算法研究以及医学领域应用进行总结,并展望未来的研究工作。-8- 东北大学碩士学位论文第2章支持向量机理论第2章支持向量机理论間支持向量机(SupportVectorMachineSVM是由Vanik教授在20世纪90年代,)p提出的用以解决小样本问题的机器学习理论,自提出以来,在解决非线性和高维模式识别等方面展现出明显的优势。SVM模型实际上是求二次规划最优解的过程,与其他的机器学习算法比较,SVM有泛化能力强和小样本学习等特点,能有效的克服局部极小点、过学习等问题,而且通过核映射有效的克服了维数灾难,对于非线性问题有更好的解决能力。SVM发展至今,具有强大的数学理论基础,在多学科领域均有理想的表现。通过33[对SVM的不断深入研宄],总结出主要以下特点:(1)在实际问题中,样本数量有限,所以SVM的二次型规划问题针对的是在小样本集下进行训练并找到全局最优解,很好的避免了局部极小点等问题。(2)在解决非线性问题时,SVM通过建立非线性映射把样本集从原空间转换到高维特征空间中,,然后在这个高维特征空间中建立线性判别式这样就把原空间中的不可“”分类问题,很好地避免了维数灾害。,在高维空间里分离开(3)SVM与其他常用的机器学习方法最大的不同是,它采用结构风险最小化StructuralRiskMinimization,SRM)原则,避免了过学习和局部极小值现象,而不是经验(风险最小化EmiricalRiskMinimizationERM,p,原则,因而具有更好的泛化能力关于两()种风险问题将在2.1节中详细介绍。2.1统计学习理论基础2-.1.1VapnikChevonenkis理论34[]在支持向量机的统计学习理论(StatisticalLearninTheorgy,SLT)中,最重要的一an-概念之是VC维(VpikChevonenkisDimension),用它来衡量机器的学习能力。以+1-线性分类器为例,如果将样本集中的数据分为类和1类,那么样本数为n的样本集n可以有2种分类方式,也就是说,该学习机器可以完成样本数不大于n的二值分类问题,这个线性学习机器的VC维是n+1。通常来说机器的VC维较大表明机器越复杂。对于任意给出的学习机,如何计算它的VC维尚未解决SLT以有监督的学习理论为基础,有监督学习的定义是预先知道输入和输出存在某种映射,样本集在进行训练的过程,实际上是缩小实际映射与机器映射间差异的过程,如图2.1给出了有监督学习系统的结构。--9 东北大学硕士学位论文第2章支持向量机理论2.1.2经验风险最小化假设学习机产生的映射为/,损失函数;(x,w);)定义为由于用/(X,w)对7进行预测而造成的损失,其中W代表映射的广义参数。'学习机器?(xvr)I/,1/rnI,、\VJII?现实系统 ̄ ̄?;;I|图2.1有监督学习系统的基本结构Fi.2.1Thebasthleiicsructureoftesupervisedarnngsstemgy通过求:.V)的总体期望值得到期望风险的泛函Rw=LxwdF(x(2.1)()(y,(,).y)f),Jw)即最小化期望风险,由式(2.1)可计算。用及(w表示学习机器的映射巩)/和现实系统之间差异,然而是无法确定的联合分布,因此在实际解决问题时,巩w)不能通过运算得到。.Y.Khinchine根据A大数定理能够推出结论,,若总体中的样本独立同分布那么在M,样本量足够大时,经验风险表示为训练集的平均出错率。所依概率收敛到如下定义的)经验风险凡’丄=1.2XW(.2)〇)文(兄,/(,,))77=1/在实际工作中,通常把作为期望风险的估计值,两者的计算关系式为式(2.3)。机器学习算法要尽量使得经验风险凡最小,这就是经验风险最小化原则(EmpiricalRiskMinimization,ERM)。根据统计学理论中的相关知识,兄—(w)和穴(w)之间以不小于-^1/7(〇<?7)的概率满足以下关系:<RRww+h/l(2.3)()emp()^)33[]VC,Vanik等人证明,对二值分类问题,依据维理论p有下式成立:-/;ln2///;+1ln74(()(7/))^//(2.4))^/其中/,。z是xw的VC维/是样本数/(,)--10 东北大学碩士学位论文第2章支持向量机理论通过式(2.2)可以用经验风险最小化替代期望风险最小化,但是实际问题中这种估计缺少充分的理论依据,因为样本数量通常是有限的,导致有些情况下ERM准则会引一起过学习现象,。般的学习方法是基于凡最小,比如神经网络需要满足对已有训0练数据的最佳拟合。通过增加算法的规模可以使得不断降低以至于为。,C维A增加,从而舛/但是这会使得算法的复杂度增加即V;//增大,导致实际风)一险增加。这样来学习机器的泛化性能(Generalizationcapacity)会变差。这就是一过学习问题或过拟合现象,如图2.2所示。其中泛化性能是用来衡量个学习算法好坏的标准,指的是学习机除了对训练集样本以外的其他样本准确分类的能力。****?***氺*氺〇〇*\〇〇:。1丨卜I图2.2最佳拟合与过拟合Fig.2.2Goodfitandoverfitting2.1.3结构风险最小化VM一S的重要特征之是利用了结构最小化原则而不是经验风险最小化原则,这是(2.3)与其他数据挖掘算法相比最大的不同,。由式两种风险的关系需要引入置信范围的概念。外/"/)仅和算法的VC维以及数据量的大小有关。从理论上看待过学习问题:当样本数量少时,如果构建的学习机复杂,那么对样本..集训练时误判的几率低,由式(23)和(24)可知这样造成了置信范围的增大,从而导致泛化性能降低。以多层前向神经网络为例,如果隐层神经元较多,那么VC维较大,///在小样本的情况下,置信范围中7,2.3(较大即便经验风险很小,由式()得到的期)一望风险仍然很大,,这样就无法是两种风险达到致最小。所以在保证ERM原则的前提下,需要降低学习算法的VC维,即学习算法的复杂程度,尽量让期望风险得到控制,一换句话说就是在训练误差和置信范围之间做个折衷。以二分类学习机器为例,找到个,使得样本错分个数最少,以保证经验风险最小分类面;还要使得分类的间隔尽可能大,■11 东北大学硕士学位论文第2章支持向量机理论A,,StructuraRi以保证最小进而使得实际风险最小这就是结构风险最小化(lskMinimization,SRM)原则。牛欠拟合过拟合一^RemvIp(})IiiIh1?图2.3结构风险最小化准则Fi.2.3Structuralriskminimizationrincilegpp由此可见,构建合适的学习机器,对于风险的控制有很大影响VC维选择的。如果太小会形成欠拟合(Underfitting),如果VC维太大又会导致过拟合问题。如图2.3所一示,根据SRM原则,构造合理的学习机器就可以实现致风险的最小化,对应的VC维是最合适的。2.2从感知机到支持向量机感知机(Percetron)在1950s由Rosenblatt,是支持向量机的基础p提出。感知机是一二-+11种分类的线性分类器,它的输入x代表样本特征,输出为样本的标签,用和_y代表。这样就可以通过样本的特征区分类别。感知机应用的前提条件是特征空间线性可+1-1分,,也就是说所有的样本只属于{}这两类。一=在感知机的定义里,线性方程wx+60对应个超平面(二维空间中为直线),两类样本分别位于超平面的两侧。超平面将样本集分为正类和负类,坐,求得模型参数w,标是每个样本的特征,6后一即确定了感知机模型。在平面中,如果样本空间线性可分,则可以用条直线将正类和--12 东北大学硕士学位论文第2章支持向量机理论,,。负类分开,如果线性不可分则无法用感知机处理这时引入损失函数损失函数可以S.=定义为误分类点到分类面(〇;x+60)的总距离。距离有以下两种概念:(1)几何距离(2.5)丨IHI一-=M?x,110设样本点,/,x+6((〇y())y(〇代表类别或任样本点到这个分类面S(w).的距离为几何距离。(2)函数距离U)uTi()d^xw+b(2.6)y\)函数距离用来表示为分类的正确程度,如果mr+6>0时,表示该样本点M在超平面,,分类面不会改变位置,W上方成比例的改变模型参数。但是^会随之成比例增减保持不变。,根据距离公式计算全部的误分类点到分类面的总距离:_+b〇)(2.7)M为误分类的集合,是固定的。得到感知机的损失函数:*minL〇)b=VX(28)(.,)^-//£a/随机选取误分类点,对w和6更新:。经过上述分析可知感知机的数学模型+x=?=fsina)x+ft}(2.9)()g(){—1其中X属于特征空间,w和6为感知机参数,vv为权值,6为偏置。感知机的算法流程如下:(1),如设初值W;(2)计算函数距离找到所有的误分类点(3)更新vv,642,()回到过程()继续计算直至没有误分类点。一当采取的初值不同,通,如图2,过感知机算法会得到不同的超平面.4所示即当个样本被误分类时,就调整w和6使得超平面发生改变,减小误分点到平面的距离。所以,感知机的分类超平面可以有很多条,他们均能够保证两类数据得到正确划分,但是可以发现的是,两类样本点到超平面的距离随着超平面位置的变化而改变,所以针对线一性空间,确定个最优的分类超平面,从而可以确定SVM的数学模型。--13 东北大学硕士学位论文第2章支持向量机理论\\、\、、、\、、分类超平面V—.7*1、*〇、¥**°、〇\、\*、、。、、、*。:\<、、〇、、、\、、°、〇、、、、、、\、\、°〇\\、°、\、、\\\\\\图2.4感知机超平面不意图-Fi.2.4Theherlaneofercegypptronpp直到所有点都被正确划分,所以感知机追求的是最大程度正确划分,最小化错误,一,2.4但是这样来容易造成过拟合。在线性空间,感知机分类超平面有很多条如图虚线所示,最大化marin,如图2.4实线所示,。而支持向量机是在大致正确分类的同时g这在一定程度上避免了过拟合问题。\\最优分类超平而***':於、、、。、。;¥丨。V%jI图2.5最优超平面示意图F-ig.2.5Theoptimalhyperplane即图2.5中所示的H不仅要保证样本分类准确,同时还要达到间隔margin最大化,,如果是在高维空间,就可以得到最优分类超平面在二维空间内就可以得到最优分类线。-14- 东北大学硕士学位论文第2章支持向量机理论5-=图2.中用圆和星号表示两类样本,H是分类面,对应的方程是:w乂y0。位于分类线两侧平行于分类线的氏和112,叫做辅助超平面。位于辅助超平面上的数据叫做支持=_(SuortVectors)。HH--J-=l向量ppi和2对应的函数分别是wvl/yl和w/y,其中儿?4=X代表输入样本,W为权值,6为常数偏置,...X,。{〇^/)(2J2),C/W}"xei?e+1-1。将乩和H2之间的距离记作A则定义:,,{丨;%-_...h4y.y|.卜4|…八、————2^n+(.10)iminimmo..-==】'k.),.1}IHIk,}IMI若存在超平面可以分开数据,,并且算法收敛那么这种情况称为线性可分,否则就是线性不可分。2.2.1线性支持向量机首先介绍线性SVM,在所有保证分类结果准确的超平面中,找到分类间隔最大的,即最佳分类超平面(OptimalSeparatingHyerplane,OSH)。线性可分时的两类样本满足的条件如下所示:-=(〇■>A\对于+1y,_y,i—--=-ty幺1对于l尸,_y4j(2.11).一='似1/12.(../少/2,,,,艮,為)p(212)1所以,根据公式2.1),(计算得到线性可分的情况下,辅助超平面乩到0311的=距离是同理,H2到H的距离也是&。所以,分类间隔的大小想要使得2?间隔最大,相当于让卜最小。上为了便于运算,将代表样本标签V,,用矩阵表示.|x-A,代表//的对角矩阵,对角元素为+1或者1,对应的是输入样本矩阵A的类别。max(^)HI?—>=s1.t.DAi12...Nh(f/),,,,(213)满足约束条件式(2,.13)并且使得d最小化的分类平面就是线性支持向量机的最优分类超平面-=。确定最大间隔分离超平面的核心问题是找出超平面羔%70的法向量w和偏置。y一=--=-式(2.11)等效成在数据所在空间中找出对辅助超平面wd,1与wj1,yy并保证二者几何距离最大,:21;同时,对于所有数据点来说满足A,,即两超。平面之间没有数据点,图2.3表示的即线性可分下面介绍近线性可分的情况:--15 东北大学硕士学位论文第2章支持向量机理论式2.13)等效为:(丄minK()11112(2.14)s-->=tA.co\..Dyi12...Nu(,,,,,)2.6=但是,图所示的数据分布仅会在个别的情况下发生1,有时在两个超平面凡一-—与羔^产丨之间仍会有些数据点,这种现象称为近线性可分。\\小1,产|*\\**\*\\n\*\*\*,\\\\\\、、*、、。。、\*、*\*I。\、、。八。\\、、。、\、°\\\〇、\\■-=-A.〇)/!\\,、\]、图2.6近线性可分Fig.2.6Almostlinearlysearablep,2.6所示为解决近线性可分问题如图,引入间隔松弛变量惩罚因子的概念,一一个样本都有个松弛变量与之对应一每。设MX1维向量C,C中元素表示每个数据点的松弛变量,松弛变量的大小决定了算法的容错性。惩罚因子^是可以调整的参数,用于控制目标函数中寻找间隔最大的超平面和保证所有数据偏差量最小之间的权重,也具有防止出现过拟合的作用。在二分类里面,通常用f表示对正类样本划分错误的惩罚参?一,表示负类的惩罚参数数用。这样约束条件在定程度上放宽,式(2.14变为:)(215)s+>=^.t.0/12A-^,,,,,35表示所有数据的偏差量总和[],越小越好,转化为矩阵表达形式为:'〇)〇>+5e£(,)->sD->0.t.Acoe(/)+^,^(2.16)--16 东北大学硕士学位论文第2章支持向量机理论5?式(2,.1)属于凸优化问题,引入拉格朗日算子a,在处理最优化问题时,每个样?些=■>本都有和它对应的a,,那&0的样本对分类没有影响,只有a,0时的样本点即支持向量对分类有影响。引入拉格朗日算子后,目标函数写成:-?---L〇)aa-?1+?{,,,^i^(4r)irfA#,}Mii\EZzM==,imi<(217).r=其中”..。,,,(AA^)-Tucker,由Kuhn定理计算最优解:=-?=?0(2.18)/,死.^=---=?.Dcy)l+0Vi,("(為r#)|,da'(2.19)Vl(2.20)=〇Vi(2.21)'=220O.<1.<由式(2.18)和(.)可Sa/12...,.7a8知0,,,由(2)可知如果,!J,贝,,jG为零。再通过(2.19)可以求出乂若采用矩阵表示可以得到对偶形式關:\\(}}rm-DAADu-inUueuJ's<u<Du=.t.03ee0/(222)原始形式和对偶形式包含了过多的约束条件,导致计算机会做过多的运算。一>aL.Mangasarian等人将作勺次方改成了二次方,省略了约束项(0,并在wV后加上236A[],原始形式变为:222min+;1+?(()/,)去|—|奋sA-->=N.t.D(d)^l〇i12...),,,urr,(2.23)一36][般形式引入惩罚因子后,对偶形式为将数学模型的:''''---minM+DAA+eeDwew[)^^||SLu ̄°-(2.24)同时可得到:-7-1 东北大学硕士学位论文第2章支持向量机理论''w=u=—=-ADyeDu,,/^(2.25)在对偶形式中,引入了拉格朗日乘子w,它直接决定了分类平面的w和y,从而将,以及〇的值变为确定w的值优化的核心问题从确定wy,将问题由求解式2.23中三个()2一.24个未知数,2.25未知数变为求解式()中。确定w的值后通过()式,求得w和y,得到超平面。用这个超平面分类时,分类结果A/由公式求出。2.2.2非线性支持向量机在线性空间里,不是所有的样本集都线性可分或者近线性可分2.7左,,如图图所示这时采用线性支持向量机无法将数据分类。〇c。牛牛°°°〇〇〇〇〇0°°°°°8OO〇°〇°°°00〇**¥〇〇〇氺氺^^氺**氺〇***°°〇〇〇1_、图2.7二维空间中的点映射到三维空间的半球体上Fi-.2.7Pointsintwodsonalsaceaigimenipremappedtothosenthree一解决问题的办法是首先确定个非线性函数,将二维空间里分布形式不可分的问题一,通过个非线性函数,,即核函数将样本从左侧的特征空间投放到新的特征空间,在新的特征空间中,2样本可以用线性支持向量机进行分类如图.7右侧所示。图2.7中的数据用到的映射方式: ̄x—>xx-a+—b(2.2)(,,,6y)(y(){yy)^原理是将平面上的点映射到三维半球体上一,在新的空间里,可以找到个平面将两组数据分开,这样就把不可分问题转换成了线性可分或近线性可分。当样本线性不可分的时候,SVM采用了核函数的概念,用以实现转换。通过引入,既避免了高维数问题,又不会提高复杂度非线性映射。在机器学习方法中,用提前定--18 东北大学硕士学位论文第2章支持向量机理论义好的核函数代理内积运算,因为不论是对偶形式的目标函数,还是决策函数,都不需要具体求出映射//X的形式,仅仅需要求内积//(x,>//(x。通常对核函数的选择决定了()/)37[]。SVM的类型。随着SLT和非线性SVM的日益发展,核函数法越来越受到重视*非线性映射氺*i〇*〇\〇\y丨图2.8核空间理论Fi.2.8Ttheorofkernelfunctonsaceigheyp数据从空间R经过非线性函数H映射到F空间,这样原本不可分的样本集可以在一2,所以采用核高维的空间F里进行分类.8的空间F里般无法直接找到分类面。在图不输入向量在特征空间中的像。函数:表使用SVM算法时常用的核函数(X、y为己知矩阵或向量,维度任意)有:-x=.义+(1):AMy线性核,)4rf=.x2x+y()多项式核:々m,)(為)A/=--Z(3):Uexa)高斯核)p((4|f"=.:y4Jy(4)sItanh4A+yigmoid核:A(,〇();:引入核函数后,SVM的对偶形式变为'''XD-inj+DkAkAX+eeum({,,)j[)()]/jp〇7)>s.t.//0。引同时,原特征空间中的超平面被新特征空间中的超平面所取代。虽入核函数的好处是不需要知道映射的形式,只需要知道采取的是哪种核函数即可然SVM,二分类问题是的基础,但是随着数据结构越来越复杂实际问题中存在很多非线,性的情况,这时避免不了使用核函数所以核函数己经成为将非线性不可分问题变换为线性可分问题的通用技术,但是在实践过程中,核函数的选择以及核参数的确定还没有充分得理论依据。-_19 东北大学硕士学位论文第2章支持向量机理论ugh2.3SVM4[JLIBSVMSVM理论在各个应用领域不断被提出新的算法,传统的SVM在训练时存在着占用内存大、训练速度慢等问题。所以人们对SVM的快速算法进行了不断探索,同时收获uhtgBSVM了不少成果,在SVM领域,两种快速有效的经典算法有SVM&LI。虽然SVMLBSVM1^和I都属于分解算法,但是算法本身的特点不同,因此本课题选择了SVM—uht和LVMg算法IBS作为对比算法,与大规模SurrSVM起进行实验。下面介绍SVM和LIBSVM算法的相关理论。21蜘.3.1SVM方法一SVM1^是经典的SVM分类算法之,可用来解决分类和回归问题。它是由8-[339]uhtJoachims在1998年提出的基于分解算法的SVM算法g,SVM主要使用了高效的工作集选择策略。由于SVs在训练集中仅有小部分,所以多次迭代之后,很多支持向量的Lagrange乘子将达到边界C,这时通过收缩策略降低算法的复杂程度,下面简单介绍算法应用到的策略。llht1)g工作集(SVM用的是最大可行下降法(SteepestFeasibleDescent)选择。这种方法首先要确定最大的可行下降方向,使得目标函数可以快速的达到最优值。最大可4Q[]行下降法提高了工作集的选择效率,研宄表明采用的Zoutendik可行方向策略收。j敛_(2)8¥1^算法使用QP软件包LOQO来求解二次规划子问题。这个软件包不仅包含求解二次规划的算法,也包含其他的优化方法。一(3)收缩Shrinking)策略。在训练集中,通常SVs的数量仅占训练样本的部分。(通过前面分析,可知支持向量对分类超平面的位置有着重要的决定作用,所以可以仅对SVs进行训练。而在迭代过程中,某些SV的Lagrange乘子会达到常数C,这样的支持向量被称为边界支持向量。在之后的迭代过程中,如果样本Lagrange乘子都处于边一一界不再改变,则把这类支持向量放到个非活动集中,把经过缩减之后的训练集组成活动集,单独优化。将二次规划问题用活动集和非活动集的形式表达如下:nWo=mir()臺1T1raa+ ̄aa(2)+AANNNQNAN.28Q^ ̄ea ̄eaAANN-20- 东北大学硕士学位论文第2章支持向量机理论<—s.t.^c/l..yl0,(^),v;||(229)=-yw^因为拉格朗日因子似在多次迭代后会达到上限c,所以只对含有〇u的项进行优化,所以:= ̄ ̄i—(230mnWaa(x^oca.)()AQaaa(aQann)A=sy.’.〇—^czl...4,,,||(231)+?=0y\aAyN^231),式(.将目标函数以活动集和非活动集划分,接下来的迭代只针对活动集进行“”ught这就是SVM收缩的策略。值得注意的是:收缩过程和分解过程是不同的。收缩指的是把多次迭代之后达到边界的SVs放到非活动集中,迭代的时候从活动集中选择样本到工作集。VM^ht(4)核矩阵Q的运算代价非常大,所以S减少需要迭代的变量,进而节约uhtg。,,计算成本在迭代过程中,SVs可能会被多次选入工作集中为了避免重复计算SVM在存储技术上,不仅利用了缓存技术而且还可扩展内存,既可以在计算机存储和时间成本两方面取得很好的折中,也能够有效的处理成千上万的SVs问题。2.3.2LIBSVM方法一ndowsLSV个经典算法,它使用起来简单、快速,调用方便,在WiIBSVM是M的另系统下有的清晰的源代码和完备的可执行文件。LIBSVM对SVM理论相关的参数调节,LIBSVM,通过修改相对比较少,大多数参数都采用默认的形式当需要用解决问题时默认参数中预设的值即可实现不同的功能。此外,该方法提出了价差验证(CrossValidation的功能。LIBSVM的核心算法是序列最小优化(SequentialMinimal)Otimization,简称SMO)方法,从数学模型角度,每次选择两个样本进行优化。前面pVM二次规划问题时都要进行大量的运算一旦介绍过传统S在单步迭代或者求解,而且。训练集数据增加或者遇到高维问题,就需要更大的运算成本SMO补充了传统SVM的41[]2个,然后利用两个不足,将工作集的数据规模减小到只有样本样本之间的关系将一某个样本用含有另个样本的关系式表示,这样就把单步迭代运算的结果直接用解析法求出来,避免了求二次规划最优解时的大量运算。由于LIBSVM采用的是SMO(串行mxSVM算法对比,。最小化)算法,所以为了便于与S对SMO算法作分析=(工作集#丨,开始时的Larane乘子分别为a1)两点解析解i和a2,要:设{,7}gg-2-1 东北大学硕士学位论文第2章支持向量机理论42[]=为这两个参数计算新的值。为了不违反线性约束?.〇,新的Lagrange乘子,一条直线上必须要在,即满足下面的约束:0w〇w少+a=co;wz(2.32)_y,丨2这条直线所代表的约束条件可以用图2.9表示,是在(cn,ct2)的空间,并且在0<aSC的矩。cxp:形约束中定义变量:As(233)u.2oM0hl==al+a2a+2.34)/ssa(,2将a,aa/和与其他拉格朗日乘子分离仅对ai和a2优化。此时i可以由2和其他参数表示出来。这样?回带到目标函数W中,F就只是关于m二次的函数。一二次方目标函数呎奶元程式。根据Lagrange相关原理,〖作/2)的极值点可以)实际上是?=通过对们求导得到,所以由^〇得:da(2)-卿,oMEfEf),M!a、=a+-^—=—(235).2V其中和分别代表样本的决策错误。因为拉格朗日乘子满足0SSC,V/,2.35)所以应该将式(中的取值范围作判断,从式(2.33)和式(2.34)分析可知,==s可,所以如果^1,则根据式(234)看做两类样本标签的乘积.,有/++,这%个约束可表示为图2.9。a-=^ca2cIiI[k/—〇 ̄8,i〇N.di\Ca==ic-io!;a尸\/II\ILI==a,20a20=^--=->a-y\aaay/{2]2x2y图2.9两类样本的Lagrange乘子的线性约束Fi.2Thliilihelg.9enearconstrantsoftwoagranganmultiplierfromtcasses-22- 东北大学硕士学位论文第2章支持向量机理论>一<若c丨ca<cy,贝J,2;1^<c丨a<y,贝J0S;2/综合这两种情况,可以得出取值的边界范围:L=-2max0Qr+ac(.36){,},2=nm(2.37)Hica+a{,,2}=-l=-2。如果sa,约束可.9右侧,则有,q2以表示为图形式>—0丨<<若,贝0ac;/J2厂1<—<a<若,c/0贝IJ,;2:综合这两种情况,可以求出a2取值的边界范围=-238)Lmax0a(.,a{2}^=a-Hma(2.39)incc+,}{2,根据上述两种情况对约束范围调整:'H\iH<a,r-.clipped?e?=<a<^(24)^if£.0lf^li,__当计算出幻后,根据此值计算山-icd'evddpp=-aa+saa(2.41)f(^);fwc%w?上述求解<32和a。通过推导过程可知,SMOi的过程实际上就是联合优化方法求解析解的过程计算量不大,因此整个算法的收敛速度比较快。uhtg(,2)缓存策略:与SVM类似,为了避免重复计算SMO把中间变量值或者需要多次进入内存的值进行处理。,如上面推导的气这样可以减少内存损耗t一(3)为,Pla等人提出了种基于启发式双循环方法了提升算法的收敛速度。主一要步骤包括:首先找到训练集中所有的非边界SVs,选择违反KKT条件的样本逐进一二。,入外循环这样,外循环就作为第个点的选择算法。用内循环选择第个点再通过解析算法进行联合优化。实际应用中SMO取得了较好的效果,但算法在优化过程中需要对偏置进行实时更43[],新,如果偏置值选取之后却不符合KT条件那么SMO算法的效率将受到影响,这是SMO算法存在的弊端。-23- 东北大学硕士学位论文第2章支持向量机理论2.4本章小结一SVM作为数据挖掘领域的主要方法之,具有强大的数学理论基础。以SLT的VC维和SRM原则为理论基础,SVM模型平衡了小样本分类时机器复杂性与学习能力之间的矛盾,获得理想的泛化能力。本章介绍了统计学理论的知识,包括VC维、欠学习及过学习问题以及两类风险:SRM和ERM等,充分学习SLT知识对于理解并探索新的SVM具有重要意义。从二分一SVM的类的线性分类器感知机算法开始介绍了原理,给出了间隔与间隔松弛因子的定义,SVM的核心是试图寻找最优分类超平面来划分数据。通过线性可分、近线性可分及线性不可分这三个方面简化SVM的数学模型,引入拉格朗日算子对SVM模型进行求解,,将优化目标从线性不可分变为线性可分及近线性可分。遇到非线性可分情况时引入核空间理论,通过非线性映射进行空间转换,使不可分的样本集在高维空间中线性可分。并介绍了在SVM里常用的几种核函数。一ughtSVM利用最大可行下降法作为工作集的选择策略,,研宄表明在定条件下,1#1可以具备线性收敛速度基于这种选择策略的SVM。这种工作集的选择策略在后来的SVM方法中被广泛借鉴并加以扩展。例如,收缩策略,缓存机制等,避免了重复计算,SVM1#很好的降低了运算成本。然而在的实际应用中也有不少问题。例如:采用的缓存策略并不很高效;在某些情况下,目标函数会停止下降等。SMO算法的主要优点在于:通过两点解析法计算理论结构清晰,不用通过模型迭代求解二次规划问题。单步迭代时仅选择两个变量&和巧参与运算。和其他的SVM分,解算法相比,虽然SMO的迭代数量较多但迭代本身需要的计算量相对较少,而且通过设计迭代策略可以快速的求最优解,前提是保证迭代算法收敛,该。另外算法还具有其他的一些重要性质:不需要进行矩阵运算,易于实现等。总的来说,分解后的子问题数量和迭代的次数是彼此制约,SMO虽然简化了子问题数量,但需要更多的迭代次数,可以看做把求子问题的运算成本转移到迭代过程中。虽然看上去计算总量没有明显的减少,但是通过设计迭代算法可以使SMO算法有更好的表现。研宄领域目前提出了不少改进的SMO算法多数针对工作集选择策略或者缓存机制。-24- 东北大学硕士学位论文第3章基于代理函数的大规模SVM设计第3章基于代理函数的大规模SVM设计3.1设计思想随着大数据理论和计算机仿真技术的发展,在生物医学领域用于数据分类的SVMSVM1#LS己经不能满足需要。利用经典的和IBVM方法获得理想的优化结果往往需要更多的迭代,耗费运算成本,所以引入代理模型技术(SurrogateModel)解决这个问题。代理模型技术的定义是在保证精度的基础上构造简单的数学模型,最终代理模型的输出结果能够很好地替换原模型。3.1.1代理函数设计流程初始化X.夕丁试验设计获取样本点II计算机仿真计算^^[构建代理模型III}增加样本优化求解。满足收敛^输出结果vy—图3.1般代理模型构建过程Flbili.3.1Generalsurroatemodeudingrocessggp-25- 东北大学硕士学位论文第3章基于代理函数的大规模SVM设计“”代理模型是模型的模型[5G],采用它的目的是减小计算量,提升运算效率。代理模型技术有很多优势,SVM当数据集的维数很大时,目前常用的模型几乎不可行,因为关于选取样本,大规模样本的计算成本问题都需要考虑。所以在设计新的代理模型或者由高维向低维分解时应保证以下几方面:(1)避免工程优化过程计算量大的问题;(2)采用并行计算,缩短设计优化周期;(3)便于将各个学科分析软件集成。代理模型技术不仅适用于变量维数多的情况,在样本数量较大时,也可以通过引入代理函数,建立迭代模型,提高迭代效率。总之,如何保证分类正确率的同时减少运算时间,是设计大规模SVM的关键问题。一正如前文提到的,SVM实质是解决个二次规划问题,快速精准的找到二次规划中目标函数的最优解,是SVM理论的核心问题。根据第二章SVM原理以及SLT基础,我们知道,迭代算法在整个优化过程中起到了至关重要的作用,如果把SVM模型问题看一口向上的下凸不规则曲线,那么设计合适的迭代算法成个开,快速准确的找到模型最,,就是算法研宄的核心内容,低点即最优解。根据以上分析我们想到采取代理函数(SurrogateFunction)的方法,首先将对偶原始模型分解,分别找到分解后的子函数的,,最后推导出迭代公式代理函数再重新组合成原函数。’6!,(?)I1_7|//(?)_,1w:;IIiiiiii1iiiii0123456789101112图3.2基于代理函数算法的单次迭代图示li-Fiiig.3.2Graphicanterpretatonofasngleiterationofthesurrogatebasedalgorithm-26- 东北大学硕士学位论文第3章基于代理函数的大规模SVM设计51[]如图3.2所示代理模型,首先给出代理函数的定义:定义3.1:函数/(咖〇与函数/(t〇在点V时相等,且/(wm2/(m,则称/〇wt|〇)|〇为/(〇的代理函数。3.1.2代理函数的性质原函数/⑻和代理函数/(+〇在V点相等,如图3.2所示,可以得到原函数/(?)从一+/=点V到下次迭代AVm/n,/(W|W〇是单调下降的,因为代理模型满足以下关系式:'+1+?=。/()wW/w)/V)总的来说,SVM中代理函数的构建离不开以下几点性质。性质1:函数/mid(ww)是/(W)在t/时的代理函数,t〇是/mid(wt/)在V时的|/〇||Surrogate函数,贝!j/(w|t/)是/(w)在i/时的Surrogate函数。证明如下:=/由/(wi/)是mid(w|t/)在wi时的Surrogate函数,/mid(w|i〇是/(w)在时的|/Surrogate函数可得:'>'>fuuuuu(3.1)()f(\f(\micl)):当W!/时:'''l'==f(uuuuu(3.2)\)fmid(\)f()=.1可知wi/z/rroate函数。由定义3:/是/〇在w时的Su(|))g=性质2:函数/i(w|t/)为/i(w)在wV时的Surrogate函数,函数/2(m|i/)为/2(w)在''=aww时的Surrote函数,贝(J函数/i(ww+/2ww为函数w+/2w在时的Surrogategi(|)(|〇/())函数。证明如下:w'wroa'由/w为i在时的Surte函数,ww为w为时的Surroatei(|)/()g力().)g|6(函数,可得:>fMW)f^{u)'>uuu(3.3)f2(\)f2()'''>uu+uuu+ufx{\)f2{)f{){)\xf2在点w=w'时:'''uu=u(34f.)2{)f1()\'''''1uu+uu=uuf\)f\f+x{2(){{)f^)由定义3.1可知:函数/iww2mi/为函数im+2w在时的Surrogate函(|〇+/(|)/()/()数。mte/i3,性质:若函数/(w)的Surroga函数/w1在处值最小贝jww。(|)/(’S/(〇-27- 东北大学硕士学位论文第3章基于代理函数的大规模SVM设计证明:由定义3.1可得:l''fuu=u()f()\(35)又因为为/(w|w〇的最小值:(3.6)所以ma^l'l'i<<uu=(f(u)f(u\u)f(\)f(u)3.7)引入代理函数的目的是使SVM模型更容易最小化,所以接下来在单次迭代中,我们最小化代理函数的同时得到新的迭代起点,而不是直接求原损失函数的最小值,而且每次求代理函数最小值,都能保证原损失函数是单调下降的。3.2构造基于代理函数的SVM不论是线性SVM还是非线性SVM,在二次规划的对偶模型里,令矩阵=Xce>222_2.24:私或者,则式()及式()的优化模型可写为1Effrr=——B-uuhB+minfccueu{)[]2p(3.8)>sX.w0'’'’=《仇函数/“=设函数/“5,1<0(:《,贝1]:1()去2()吾'U=-U ̄Uf++Ue()f\f2(){)^2^P(3.9)SVM算法的核心问题是求得满足AO时,/⑷的最小值,而关键部分就是分别求出'’==MyW和/wCCW的代理函数。j()臺2()臺3.2.1代理函数的构建从式和一3.83.9中可看到,/!⑻和/2w有相似的形式,接下来逐推导它们的代理()()()一一函数。由定义3.1可知,个函数在同个点会有无穷多个Surrogate函数,在SVM中对Surrogate函数的要求是易于求得使Surrogate函数值最小的w,w为拉格朗日常数所组成的矩阵,其元素的值是正数。为保证^的非负性,需满足迭代开始时W中所有元素为正数。-28- 东北大学硕士学位论文第3章基于代理函数的大规模SVM设计基于Surrogate函数的SVM算法流程图如下:'==ut0,umiM.aJI构造/⑷的Sw/Togcz/e函数wI’I求出使值最小j_的向量》V?//mmU=U^厂|W1否I|收敛性判断输出2/vy图3.3基于Surrogate函数的SVM算法流程图Fig.3.3TheflowchartofSVMbasedonsurrogatefunctionSut/。,首先构造/Wrroae函数?t令矩阵5为两非负矩阵的根据算法流程图()的g/(|)+-〃+_-==+5wrroae1/:差,即555。设:55,得到函数/i()的Sugt函数/_(以)丨'',fUU=UU+nUU(3.]〇)P\mid(\\\)\)(\)(其中:,1,+p=-25w-5V丨(+)|『 ̄(')'=——nAuu\2BuBu114(311).证明过程如下所示:=-设???1/+1/1/,将函数?11/展开::()/();〇丨)£〇〇/(),丨'||-29- 东北大学领士学位论文第3章基于代理函数的大规模SVM设计LJ(3.12)在向量W之中,每个元素都是未知数,函数对W中元素WA1求偏导,得:duvyk\MlHMJ(3.13)由式(3.9)可知:22片(3.14)函数/:l(M)对WAl求偏导變參[㈨,)4(3,5)对g(M)求偏导:1dpudgud()^)f}^。?'⑷dudududukik\k\k\代入,整理:=-l^l4£^n4>n()()^===k111,1J}'J{1(3.17)+=K当wz/时SSw)。同时由于5与均为非负矩阵W的中的兀素均大,gbV/d,所以一于等于0。函数5gw/5%i是关于wai的次函数,且%丨的系数为正数,因此函数3g(w)/3M*i()关于wh单调递增。当《?<mV时,改(w)/5w<0,gt<单调递减;当WA1>取/时,《/5取1>0,;u()改()=w单调递增说/时gw取最小值,最小值为0。g;当w?()()r2=/时等因此mWwMW,l。,即/l()/l()当W号成立因此|函数//mw(w?是函数Fi(w)的Surrogate函数。+_fl+_e=-ec=+同理,令向量c为两非负向量的差,即c,设:cc。可以得到函数/2(u)的Surrogate函数/2_〇|/:|)r<=w+uu31n(.8)fimp22idjj()其中:°f'+uu=2cU-CMp{2^|^_0f'—ru(uu=2cw-cu\|1]4丨丨(3.19)313.18Surroate:根据性质.2以及式3.0和式得到函数g函数()()/⑷的-30- 东北大学硕士学位论文第3章基于代理函数的大规模SVM设计'M=+?+Uu-euLdfmd^f)i\i2mid()1()P(3.20)o求极小值,但是通过的极小值处偏导为,令所求的解无法作为迭代公式,需构建/^(^的代理函数,而函数Mw是可分解的mW,因此可以将14/(〇|求最优解问题转化为求两个子函数的最优解。所以接下来需要找到和的代理函数,从而确定整个原函数的代理函数形式。在计算的过程中引入非负矩阵分解/以及常系数,推导出//mW(w1/和力m/rf(w1的1)1)设常系数a/及a//:+_寫Bu-“n_(V^T,JX(3.21)'得到/Surroate函数wt/:imid(咖)的gi./(|)’’'=+/??m;耶,,(+)(+)(卜)(322)其中:2"4k)4(气鬆?4](3,3)证明:+3=>0根据式(.21:1、av3.22:?ww均为凸函/;同时根据式pin?iww)y()/(|〇与(K|〇=/1数Jenseii,:。根据不等式对于凸函数-=/[/zAa<//zx.a.1且a.>0(,),[(,),Q>,)[],L===,i」/ii\(3.24)??1/wi、《11/与pi/wi/之间的关系。根据前面的推论可知!/、可得到坪|(咖%(|i|)()(|)户如)丨ni(wz/的值:|)+°'=-2u-BBuj^|, ̄°'nu=-Bw2Buu{x)I--31 东北大学硕士学位论文第3章基于代理函数的大规模SVM设计M々鸯),]2TVA/1「/、I2+25卜=4l叫4k)(325)?当=ww时:邀警-d4:^U-in2]iii2(y)r|1=—^2bW-b%()()、4U"i台WL」()刀’’=—=7WW/()[,114^Jl(3.26)同理可得:2raiwt/,且ni/2m<yw。根据性质3.2及定义3.1,wi/_((m(yi|)|)〇/()+)||是/imw(wi/)的Surrogate函数。|i/rroate.同理可构造力mwO的Su函数,设常数a及a:)gl〖;Ybcu+jia_a=?V>7T7Tcw()ylcu-lina= ̄2jiMV)jl(3.27)贝!J构造/2m?(ww的Surroate函数为:|〇g(’’/=奶+2,(+)(+)(+)(32g)?其中.=-现‘.2cV(屮)结!繁(L””W-z/2cV2()(|)L音,根据式(3.9)、式(3.21)、式(3.26)、性质3.1及性质3.2,可得函数/〇的Surrogate)函数:’++潛卜(件技秦”(329)-32- 东北大学硕士学位论文第3章基于代理函数的大规糢SVM设计3.2.2迭代过程及推导函数/(wl/对W中元素w/fcl求偏导:|)dUU,dMdfUf\f2{\)_kx(K)++1^UP^U^Ukk\k\\(33〇)在函数/l(ww中对WAl求偏导:|〇5dppuufdn/uunuu\{\\j{xx(j^^^U^U3uk\k\kl(31.3)其中:整理,可得: ̄d/I{Wl/1yv厂M,、Mf、1wrM,++__0,,,'=--r55+55lw55V^{()()}[()]LJik,4](3.33)同理:OUUL」々k1\k\(334)一一+一1'=令豕WW/加/d0,这是个元次方程,容易求解,解即为t/。所得迭代公式()|如下:’’1+,如,L如L—u、—uk\k\tif2Z+2Lz/+w(3)(4)[L1LP(3.35)其中:+ ̄+ ̄L=B+BB+B,(()^)+-+_=4f+cc+c()()++- ̄L=BB+BBy()()-33- 东北大学硕士学位论文第3章基于代理函数的大规模SVM设计++- ̄L^(cc+c\c4)(/、V^>(3.36)’c=eexx如果考虑到D,为元素全为1维度为Afl的列向量Z)M的对,为维度为M+-角矩阵+1-1c-=maxT=,且元素的值为或,那么的元素值为+1或1。可以令c0c、c(),;+_'==mz>z0c,则#£+〇£:(,) ̄++1'1=c+—c\c+cueu[[^“L丄i(3.37)+_==-,可以令5?1〇^05、>_5。可以简化为同理5/??20则式3.32:(,)(,)()’l'1+LW+eu()|^+21^+2(lW(3))[L1LP(338.)w为拉格朗日常数所组成的矩阵,其元素的值是正数。为保证^的非负性,需满足迭代开始时wo中所有元素为正数。惩罚因子#由使用者自行定义,在第4章实验部分,我们将给出惩罚因子的选取说明。迭代公式(3.38)在MAJLAB中用以下函数实现:uncon=ANumftiuSVM,D,Beta,Iter()RowNum?;[=uones[RowNum,1);JB^A*D;PB=maxQ,B()'=-NBmin(0,B);AB=absB();=for/1:IterNumx=tsum(u);>N= ̄^AB^\ABuH%);JD=u/Beta+l^PBPB^u%);f*D=*D+2mBiV5w+2^();endreturn一个因子可以看出,推导出的迭代公式只需要在当前结果基础上乘以,而且在MATLAB中的简洁明了,容易实现。而且值得注意的是,迭代公式有两个重要的特性,一52f]是迭代矩阵均具有非负性,二是随着迭代次数增加,损失函数始终保持单调递减。分析整个推导过程,我们可以总结出规律,最关键的是在单次迭代时找到代理函数-34- 东北大学硕士学位论文第3章基于代理函数的大规模SVM设计而利用代理函数的可分解性质,求出代理函数的迭代公式,代理函数不断迭代的过程始终保持原函数在单调递减。3.3收敛性分析'带有边界的收敛性证明比较困难,我们将给出序列集丨W收敛于全局最小值的证明;}二-,Tu过程,次规划模型全局最优解必须满足Kuhncker。理论上如果成本函数是凸的[53](KT)条件,根据文献中的定理2.19可知KT条件(W20)表示如下:^^=0i'fuj>0(3.39)加,^■>=^0ifUj0(3.40)duj在证明全局最优解满足KT条件之前,对于迭代序列{W^,需要给出两条重要的合理假设:(1)迭代算法的起始值抑为非负;(2)函数F是严格意义上的凸函数;一第个假设是为了保证迭代过程的非负性,假设迭代开始时w中所有元素为正数,一但是极限值可以趋近于零。第二个假设有定限制,在后面的推导中将要用到。为了证4 ̄555[],现给出以下几个引理明全局收敛性:(1)迭代序列集W有界。丨一证明,,:因为函数F是严格凸函数假设tZ是唯最小值然后将函数尸在V点处泰勒级数展开:***rff-=-—F—-uFuw+DAA())w+eeDuu(((())[)]4^3.41()”*—u—^(uY(uu)'*T*"77I=--<!,c,取〇//(W)则{l/l/:I/wWW因为{W单调下降。所以m(>/}{(V()W/()}{}有界。+'/2-()—0随着迭代次数增加,序列集{Kw。|}|+'/,即需要证明,当迭代次数逐渐增加和M趋于相等。从代理函数的定义中我们V可以看到,,,在代理函数进行迭代的过程中始终保持单调递减下面我们引入非负矩一。阵对这结论给予证明根据假设3可以得到以下关系式:-35- 东北大学硕士学位论文第3章基于代理函数的大规模SVM设计JK[1J''fiuj++ ̄-cc'+cc{[(y()y}i2—342+(.)UJ>1(+1ww=0因为▽/(,则|〇',+lTz,+l!!,+1=-uuVuuu-?(3.43)()f(\){)^,'+>-Lu ̄Ufip丨丨Frt因为{(Z〇}单调下降且{Fw〇}—0,因此{w—0。W(|lw-*(3)如果序列w^Z,那么{}一证明,如果序列发散,那么根据引理1的边界性可知,定会:通过反证法有个收敛的序列令''**=->0smm(3.44)0|||如果有两个收敛序列和那么一定存在正整数厂使得当>tssm,满足以toto+下关系?-M<^l/4,以及W?1<〇/4。通过三角不等式,可以得到相矛盾的结果:l||||'-m—O,因为:IK1+*+*11-+-?--+,.5),,,,iT(34||||||峰|丨财邮+/w-w>£2所以>/。||丨|(4)在序列集进行单次迭代时,我们可以推导出以下结论:']1u=u-aVFuli)];)j,=-^(3)a.46+- ̄''^'-2Be+{(5r+Bu+2u[y()]}(y^j基于以上四条引理,,对于证明全局收敛性问题非常重要可以得到下面三个结论。*一(1)如果是任意收敛子序列,且w—M,那么序列满足第KT条件。{,个证明过程可参见文献[(2)序列丨1/}具有全局收敛性。证明?》.根据三条引理可知,序列集丨》中的聚点是连贯紧凑的如果我们能够证明聚-36- 东北大学硕士学位论文第3章基于代理函数的大规模SVM设计一点有限,才能说这个集,则全局收敛性即可证。因为当且仅当有限集内包含个聚点时,假设数《〇是序列的聚点合是可连接的。关于数列的聚点定义是,那么在《〇的邻域丨内有序列的无限多项,以序列^为例,如果把它看做点集,那么只有三个元1==-:2l素■s/n/2A7rnl...0l,,{,这样就成了有限的点集。|,,}{,}所以我们把证明数列的全局收敛性问题转化为证明序列集中的聚点是有限的。给定*=*==整数集合wl,2,...T,其中T代表将序列集{m}总的个数,设《:0w的子{,}{/崎}为_=*集。令函数作为函数/(w)在集合{w:w0ew,y}上的限制条件。函数/(w)是严格的v一一下凸函数?。所以由结论(1)可知/?有唯解。而且子序列集中每增加个聚点,都对应序列集一《的个子集。数列集w的子集数量是有限的,所以聚点数量也有限,进而证明数列休丨具有全局收敛性。*(3)序列的极限值w满足KT条件式(3.40)。通过反证法,假设当《/=0时满足▽?*<〇,由于e<0[/()]/丨所以存在和正整数厂满足在?>厂时,[V/(t/)]y<e,那么根据第四条引理有:'',,-XX=-Vf>-a£>Q(3aXj.47);ii[{)}i+'*/>KT条w,与假设条件相悖,所以{?的极限值w满足件得证所以w//}。通过给出的四条引理,我们对SurrSVM方法中迭代序列以的全局收敛性给出了推}导,,即序列集K}收敛于全局最小值的证明过程。由于成本函数是凸的二次规划模型=全局最优解必须满足Kuhn-Tucker(KT)条件w0和w>0,所以需要分情况对y时满足_/KT条件给予证明上对基于代理函数的大规模SVM分类算法整个实现过程进行,从理论完善的说明。3.4内存处理处理大规模数据集在运算过程中极有可能出现运算中的产生的中间值占用大量的内存的存储空间,造成中间值所需的存储空间远大于计算机的内存的存储空间,造成数据无法处理。基于Surrogate函数的SVM算法是针对处理大规模数据问题集提出的,算法在实现过程中也会出现类似问题,为避免内存的过度消耗,对iV、及做如下处理:+--'''+'Lu=5-u-B(+B+Bx{[)]()}+--'''+'-Lu=bub+b-u-B{[(]y{[(yyy+--'+,,,'=---Lucwc+cuc(3.48)4{[(]}{[(yy-37- 东北大学硕士学位论文第3章基于代理函数的大规模SVM设计xxxxM式3.41避免了维度为MN和NM矩阵的直接相乘,也避免了维度为Ml和l()的向量的直接相乘,从而避免了维度为MxM的矩阵的产生。3.5本章小结代理模型技术能够在保证精度的前提下构造合理的数学模型,旨在减小算法的运算。ae成本,提升运算效率根据代理函数的性质和基于Surrogt函数的SVM算法流程,我们对大规模SVM设计过程进行了详细的描述。首先给出了Surrogate函数的定义和三条,分析整个推导过程性质并加以证明。然后将SVM模型的目标函数分解,我们可以得出结论,算法的核心是在单次迭代时找到代理函数/(_〇,而利用代理函数的可分解性质,,求出每部分代理函数的迭代公式最后得到完整的迭代公式和简化形式。代理函数的优势是在不断迭代的过程始终保持原函数单调递减。函数F?的收敛性可以通过全局()最优解满足KT条件来证明。基于Surrogate函数的SVM算法是针对处理大规模数据集问题提出的,算法在实现过程中也会出现内存损耗问题,通过将迭代公式中的i#、及做调整来避免内存的过度消耗。-38- 东北大学硕士学位论文第4章实验说明及结果分析第4章实验说明及结果分析为了验证本课题设计的大规模分类算法SurrSVM的准确性和高效性,我们通过多组实验将SVMW、LIBSVM和SurrSVM三种算法作对比,并对结果进行了分析。4.1实验环境(1)硬件环境CPU:主频为3GHz内存:4GBIntelCore:i5处理器(2)软件环境操作系统:MicrosoftWindows7编译环境:MATLAB7.0实验用到的数据集分两种,采用的数据集包括开源软件包正态分布集群数据发生器57rmasNDC[]NollyDitributedClustersdatagenerator,简称生成的大规模数据集以及()UCI大规模数据集实验需要注意的是,课题仅针对二分类样本集进行实验,因为不失一般性的多分类问题可以通过空间映射转化为二分类问题进行研宄。HhhIg^为参照W我们选择了LBSVM和SVM。前面章节己经介绍了SVMiPLIBSVM。的原理,本章首先对两种工具进行了配置及参数设置由于三种算法在实验过程中读取数据集的方式以及训练模型获取等方式存在差异,为了让对比结果最大程度反映每种算法的优劣,实验中仅对核心算法的运行时间作记录,从而避免输入/输出引入的误差。需VM1^方法的实验部分通过命令行运行要说明的是,因为S,为了保证计时准确性,最终记录的时间由两部分组成:训练时间和分类时间。不包括打开关闭文件的时间,但是包含一一行读取文件的时间行。LIBSM和SurrSVM两种算法我们是在Matlab7.0中运行,首先Testm文件运行使_1Q1Q得两种方法均得到21到2组分类正确率和对应的惩罚因子(取值为2的指数倍从2),tt确定最佳分类正确率之后通过imealculae文件,将?参数值用计算好的惩罚因子代替,jytto,用ic和e指令对两种方法的核心部分计时最终的计时结果同样含有两部分,模型的训练时间与分类时间之和。实验中用于分类的UCI大规模数据集可以在机器学习数据库://archives.ucedu/mldatasetshtml。在4.2。中找到http.ici./..2节中将对选取的数据集说明-39- 东北大学硕士学位论文第4章实验说明及结果分析4.2实验过程4.2.1SVM_配置Ught工具箱可在LSVMinux系统、Windows系统、Cygwin系统、MacOSX系统及Solaris系统下使用。安装过程如下:Uht一(1)SVMgsvm首先需要下载lit.tanz.创建个新的目录:mkdirsvmliht。_ghgg_2ttunz-()把svmlih.ar.z?移到这个目录下并打开:icsvmlit.tar./tarxvf。_ggpghgzg_(3)执行:make或者makeall,编译后生成两个可执行文件:svmleam(训练模型)_svmclassify(分类模型)_ut分类模型能够利用训练好的模型将新样本分类gh。在windows系统中SVM提供了Utgh可执行文件,SVM因此,使用不需用编译器编译或混合编程,但仍需在cmd窗口运ut行可执行文件对软件包测试gh,测试软件包是否正常运行,对SVM的测试过程如下:1^(1)运行cmd,打开SVM所在文件夹:1^(2)使用SVM自带数据集train.dat训练。命令行输入格式如下:svmleamotionsexamlefilemodelfile_[p]p__ton在训练样本时,opis有很多设置项,需要根据实验的实际情况进行选择。[]一-zcr、回归、复原,分类器中般只需要用到分类[,,p]用来选择分类,刚好默认也是分类。一-t是设置惩罚因子的参数cfloa。它是个变化范围较大的值,需通过交叉验证来确一一定,般情况下,c越大,类似于经验风险系数最小化原则,则c的取值最好和w是||个数量级。一-w0..是回归参数中不敏感系数[,代表权重向量的范数,般情况下分类用不上。]-float松j弓也变量。一-==b[0,1]假如有个线性函数,g(x)wx+6,当选取60时,不使用6这个参数,===g(x)wx,当61时,6这个参数要考虑进去,即g(x)wx+6。一-=i01这个参数可以用来重新训练,当fl时可以把不致的样本去除[,重新,]训练数据。i,利用数据集tran.dat测试软件包是命令行参数设置之后否正常运行,这时数据集U#train.dat的格式严格按照SVM需要的数据格式进行处理,通常,训练样本集的数据格式要求如下:-40- 东北大学硕士学位论文第4章实验说明及结果分析<>=<fea<<l...tu><vilinetarget>feature>:<vaue>re:alue>#<nfo><=-<target>..+110float>|||MM<feature><integer>id|q<va><luefloat><info><strin>gare+1-其中tgt是类别标签值,二分类时表示和1,feature是特征索引,通常为连续S整数,value代表特征。在实验过程中,需要严格按照不同的VM所需要的数据格式进行转换。-实验中所需要记录的结果:Runtimeincpuseconds表示训练时间,不包括打开关闭一一文件的时间,但是包含行行读取文件的时间,即el。训练结果超平面保存在文件mod.200025中。训练的详细参数如图41所示,对个样本进行了4次迭代过程,确定了87817个支持向量,其中1个属于边界支持向量。:C:\Windows\sstem32\cmd.exe?回EB音理员y|[||丨j丨疆_||咖漏;丨图4.1对train.dat数据集训练完成Fiifig.4.1Completethetranngtothedatasetotrain.dat测试命令行输入格式如下:svmclassify[otionsexamplefilemodelfileoutputfile_p]—_.d模型得到后进行样本分类,使用自带数据集estat,t进行测试超平面的分类准确率一每个数据的分类结果保存在文件result.txt中。otions的设置项根据实验的实际情况进行选择。[p]-41 东北大学硕士学位论文第4章实验说明及结果分析-03,这里我们选择默认值2。v..[,]输出的详细等级划分-J输出格式可以使原始形式,也可以选择直接输出决策函数的值。P]W.SIC:indowssstem32\cmdexe口B\\y丨丨丨丨 ̄''1"''*l:r:;'"■■lImF-y:^:v'n;^^'i-'?'■-;il:/li!%^l?||ijl1-r;!t|fillAliil^HHH^B图4.2对test.dat数据集测试完成Fi.4.2Cometetheesinothedaasetoftest.datgplttgtt-seconds实验中所需要记录的结果u表7F测试时间,:Runtimeincp如果分类时间显0.00,小于0.01秒将训练时间和测试时间相加,作为算法的整示为是因为时间过短;体运行时间.2ccuracontestset表示所做超平面的分类准确度。分类;图4中的Ay准确kht度为97.67%软件包正常运行。,SVM4.2.2LIBSVM酉己置L一IBSVM由林智仁教授等人设计,是个快速且易于使用的SVM算法的开源软件,、改进SVM,包源代码可供查看。使用LEB所需调节的参数较少同时提供许多默认参数,SVM不仅提供了C++及Java源代码on、R、MATLAB减小了使用难度。LIB,还为Pyth、Per、Ru、wea、CommonLISP、CLISP、Haskel、PHP、LaIEWC#etlbykl界面bV以及.n等提供了接口,dows或UNIX平台下使用可以方便的在Win。,LIBSVM完整的操作步骤如下图4.3所示通常来说。数据集处理阶段需要对数据格式;、数据类型进行转换参数设定阶段需要对RBF及相应参数进行系统化、准确化的设定,,所以;在模型训练时通常不同的惩罚因子和g参数对分类结果有重要的影响为了确定最优分类超平面模型,需要对这两组参数做最佳设定。最后再通过训练模型对其他数据进行测试实验。-42- 东北大学硕士学位论文第4章实验说明及结果分析按照LIBSVM软件包所要求的格式准备数据集y对数据进行简单的缩放操作5;选择RBF核函数并对参数进行设定>r采用交叉验证,确定最佳参数C和gy_采用最佳参数C和g对整个训练集训练获取模型y一利用获取的模型进行测试和预测图4.3LIBSVM的使用步骤l-FliLIBVMig.4.3TheeneraurseacationofSgppopp在本实验中,LIBSVM可以通过MATLAB与C++的混合编程,生成扩展名为mexw64的文件,需要注意的是,环境配置时尽量把LIBSVM安装在指定的目录下,把当前工作目录调整到LIBSVM所在的文件夹,将LIBSVM添加到路径作为MATLAB的函数使用。配置步骤如下:1、在setpath中添加LIBSVM代码所在目录;2、编译LIBSVM,将SVM的源文件编译成可执行的文件;3,>>mexsetu,,利用make文件生成四组、执行编译输入p按指令进行选择之后扩展名为.mexw64的混编文件,其中svmstrain.mexw64是LIBSVM的训练可执行文件。编译成功如图4.4所示;4,4.5所。、对数据集进行测试验证配置是否成功。如图示一,SV优化完成可以得到完整的结果,包括迭代次数支持向量s和每类所含的支持-43_ 东北大学硕士学位论文第4章实验说明及结果分析向量个数nSV,分类器截距rho。安装MicrosoftVisual2012后,使用MATLAB的混合编译工具mex,选择MicrosoftVisualC++2012编译器:运行LIBSVM目录下的make.m文件,进行编译:\需要注意,整个配置过程目录不能发生改变Document\MATLAB,在下配置,否则在编译make.m文件时会出现错误。?make’’BuildinvithMicrosoftVisualC++01().g22CMEIldfull.competesuccessy'''BuildinwithM-h-gicrosoftVisualC2012(C.)MEXldfull.competesuccessy'"fEuildmMfVilC++20withicrosotsual2.gHEXcompletedsuccessfully..^.BuildinvithMicrosoftVisualC++2012.gMEJ.completedsuccessfully.'A>;l图4.4四组混编文件编译成功F.4.4Fourmixedlesasccessfulligfireuycomiledp混编后得到四个文件:svmtrain.mexw64、svmpredict.mexw64、libsvmwrite.mexw64ead.mexw64。为了区分MATLAB中自带的支持向vm和libsvmr量机中strain命令,我们将生成的svmain.mexw64文件更名为libsvm.mexw64并tr添加到目录。li为了保证软件包安装正确,同样需要对bsvm进行测试,eartsca以自带数据集hle_一i为例,利用bsvmread函数读取数据集,标签在矩阵的第,l列矩阵的其他数据项为特征项。调用svmtrain.mexw64函数对heartscale进行训练得到模型Model,_即分类超平面。优化完成之后计算出迭代次数,超平面的法向量、截距、支持向量、边界支持向量一等结果。最后调用svmpredict.mexw64,再对同组数据集进行测试,也可以设置交叉验证参数,,得到分类正确率的不同结果通过对训练集划分,记录最佳分类正确率。整.5所示个测试结果如图4。需要说明的是,为了记录分类用时,我们需要对核心算法的计时模块进行实现,综合分析惩罚因子对实验结果的影响,需要多次实验,确定惩罚因子之后,再多次实验取平均时间成本作为最终的实验结果,关于时间记录和惩罚因子的选取我们在参数设置以及实验的过程中将会详细介绍。-44- 东北大学硕士学位论文第4章实验说明及结果分析''=sveellblcaleinst']libmradCheartscal;?[heartscaeaeheart_s____,elbl'?dl=vmtain.htleit(heartscalaeearsca_ns.moesr___%=optimizationfinished,*iter152nu=0.431029-00ob=.877288rh=0.424452j1,o=SV=132nBSV107n.SV=32Totaln1va=vmedt'>dictlabel(h1lllhelt.l.,accurac,decluessricearscae_abe,art_scae_msmode>re_y_]p_[pcn1Accura=So.6667%(234/270(lfy)cassiicatioA>y\4l图.5数据集heartscae测试成功_llhealedatasetFi.4.5Successfuytestedontheartscg_4,LIBSVM从图.5数据集heartSCale测试成功的结果中可以看到对数据集_heartscale的分类精度为86.67%,测试结果表明:LIBSVM软件包导入成功,并且可以_正常运行。4.2.3实验参数设置惩罚因子是可以调整的参数,在算法中用它来控制目标函数中寻找间隔最大的超。平面和保证所有数据偏差量最小之间的权重,也具有防止出现过拟合的作用对惩罚因子的选取采取如下方式:一1、i整数值设为某;2=、,令i+l令惩罚因子i;3VM算法、使用该列直运行S;4。、记录下运行算法所用的时间及所计算出超平面的分类准确度重复过程2到过程4若干次,计算出超平面的分类准确度最高的例直即为选取的0。1G1G?-?02。101,本实验中,/的取值范围为即取值范围为rSVM1#1的参数设置关于:)-。(1zM选择分类器,刚好默认也是分类?-上面的值,,(2)cfloat设置惩罚因子。相当了类似于经验风险系数最小化原则一一w则C的般与是同数量级。||)-0。(3w.,.代表权重向量的范数在本课题实验中米用默认值[]-45- 东北大学硕士学位论文第4章实验说明及结果分析(4)-float松她变量,米用默认值。j关于LIBSVM的参数设置:我们调用的LIBSVM工具包是libsvm.mexw64混编程序,理论上,需要通过穷举的方式确定惩罚因子,使得最终选定的惩罚因子所对应的分类正确率最高,我们选择了21_1Qf值1()个,从2到2。,其他参数信息不需要单独调整ySurrSVM需要输入的有数据集矩阵A、f参数、最大迭代次数和迭代终止条件参数。参数选定之后:,判定条件如果当前迭代次数小于最大迭代次数,继续执行迭代程序,第3章3.2.3节给出了迭代部分的伪代码。4.2.4实验过程与分析本小节将通过三组实验,从不同的数据集角度对三种算法进行测试:不同规模不同种类的数据集之间对比、不同规模相同类别数据集之间对比以及相同种类相同规模离散程度不同的数据集之间作对比,并对实验结果进行总结分析。一三种算实验:当样本集规模不同的时候,从分类精准度和分类时间两个角度对比法效果。具体步骤如下:1、选取数据集。从机器学习数据库UCI中选择8组不同规模的数据集。21#、按照SVMLSurrSVM所需的数据集格式进行转换和调整。,IBSVM和3一组数据集进行实验、用三种算法分别对同,通过改变炉直确定最佳的分类正确率timecalculate,参数确定好之后再调用分别记录下分类时间。_4、记录下三组结果,惩罚因子、分类正确率和分类时间。表4.1实验1数据集介绍Table4.1Theintroductionthedatatofses序号数据集样本数维数数据类型aa4192a1Dimdt14Rel2Mushroom812422IntegerMAGICGamma31902010RealTelescope4UCNN4999022Real5Cod-RNA595358Real6NDC10000032Integer7n-SegmenReSkitation2450573al8Covertype58101210Integer-46- 东北大学硕士学位论文第4章实验说明及结果分析59[]Mushroom数据集包含的样本是23种伞菌目的数据以及与之相关的假设样本共组一一8124,这8124组样本可以根据特征描述分为两类,类是绝对可食用,另类包括不可食用和无法判断是否可食用的情况。MAGICGammaTelescope数据集由Bock等人采集的用于伽马成像项目,数据集共19020个样本,其中12332个样本代表gamma射线成像数据,6688个样本代表hadron_成像。该数据集可以用于典型的二分类实验。数据集IJCNN包含49990个样本,每个样本含有22个特征。Cod-RNA是在生物信息学领域中与检测非编码RNA序列的相关研宄中所使用的数一据集。这个数据集有8个特征属性,样本数59535,是个数据量较大的二分类数据集。NDC数据集是由正态分布集群数据发生器随机生成的样本数量100000,维度为32,一组多元正态分布中心点离散因子为10的数据集。数据发生器可以随机生成,围绕每一一个中心生成部分数据点,,然后随机生成个分离面,基于这个分类面给每个中心点划分类别,NDC再随机生成服从多元正态分布的点。通过改变离散因子,NDC可以生成不同离散程度的数据集,在实验3中,我们讨论不同离散因子对数据分类效果的影响。-BGSkinSegmentation数据集是由随机采集人脸图像的,,R值,人脸图像的采集多样化。有出自不同年龄组合:年轻、中年和老年;出自不同种族:白人、黑人和亚洲人;以及出自FERET和PAL数据库中不同性别的人群。样本总数245057,其中50859个样本是真正的人脸皮肤图像,194198个样本不是皮肤图像。一一e最后组Covrtype数据集原本是组代表多种植被特征的数据集,源自美国地质调查局和USF数据,我们将植被种类数据集划分为两类:品种A类和非品种A类。表41三种算法实验结果.2实验Table4.2Theresultofexperimentone_序号数据集SurrSVMLIBSVMSVMmd1911Diata295.37%295.32%295.42%A'5sr12Muhoom292.81292.82%292%.86%MAGICGamma'4'3279.10%279.43%279.13%Telescope1°14l.inndata292.12%291.65%29168%j1°15Cod-RNA2937%2.87%293.689.66%-122622%2126NDC286.07%.35%8.8''10b17-Sk1inSegmentation292.44%293.8%292.65%'7'10'8Covere275.84%275.80%264.53%typ-47- 东北大学硕士学位论文第4章实验说明及结果分析表4.1中给出的8组数据集规模各不相同4192,样本数到581012不等量从。通过,SurrSVM对以上机器学习数据库中的进行测试、LIBSVM和SVMlight三种算法在惩罚因子的选取、分类正确率以及分类时间上的效果各不同。表4.2记录了实验1的运行结果,包括分类正确率以及相应的惩罚因子,需要说明的是,在实验过程中,选择不同的惩罚因子得到的分类正确率不同。对支持向量机来说,一般较困难惩罚因子的选取,因为它起着调和最大化间隔和最小化误差的作用,而通过第2章支持向量机的理论推导可知,间隔最大化和最小化误差本身就是相互矛盾的。惩罚因子没有准确的物理含义,有的研宄过程通过穷举法来确定列I。本文在实验过程中SVM一从分类结果方面分析,般越大,表示对错误的惩罚越重^。实验过程中,我们记录分类正确率最高时对应的惩罚因子。接下来分析正确率,对比结果如折线图4.6所示,横坐标从左到右依次代表8种数据集,纵坐标代表对应的分,三条折线代表三种算法的分类正确率类正确率。我们可以直观的看到,第4组数据之,三种算法的分类正确率彼此相差不大,从第4组数据集之后前,SurrSVM和LfiSVM1咖的分类正确率仍然较高,,无论怎样改变惩罚因子的值S在个别数据集上,VM的分类正确率落后于前两种方法,SurrSVM和LIBS。结果表明VM的分类正确率优于1一SVM#1,但是为了保证数据集来源的致性,我们将在实验二中对数据集的样本数量和维数进行设定一,从而进步证明随着数据集规模的增加,基于代理函数的大规模支持向量机方法的适用性。100—;1SurrSVM…::」—……^libSVM_i75l:……:―…一.……DL……—….…—:7〇……1…65」…-…-……—;i(!!IIii60050100150200250300350DiferentDatasets图4.6实验1不同数据集的分类正确率对比Fi.4.6Theclassificationaccuracofdiffedigrentatasetsnexerienceoneyp-48- 东北大学硕士学位论文第4章实验说明及结果分析,三所以得出结论:当数据规模相对较小时种方法的分类正确率近似;当数据规模11#较大时,SMO和SurrSVM方法的分类正确率优于SVM。接下来分析时间成本。表4.3实验1中三种算法分类时间Table4.3Theclassificationtimeofexperimentoneht序号数据集SurrSVMLIBSVMSVM^mda.30s1Dta1.51s0.21s0i2Mushroom3.14s1.01s0.76sMAGICGamma35.31s16.63s8.58sTelescoep4innldata16.34s37.04s14.44sjCd-RNA155o.48s27.75s48.99s6NDC78.52s578.69s148.71sk-7SinSegmentation11.47s71.65s485.04s8Covertype225.31s13363.4s7364.47sS一VM方法普遍用时最短,从分类时间角度,当数据集的样本数增多时,Surr超过LIBSVM和SurrSVM方法,从折线图4.7定规模后,分类用时远远小于能够直观的看一8出这趋势Coverte数据集为例,样本总量为51012,通过LIBSVM分类用时。以ypHht3634VMg447VM为:736.s,SurrS时:225.3s。:13.s,S分类用时分类用———?SurrSVM9——丨;:丨?lSVMib/12000-^H-SVMitlgh/^10〇0J00//〇/5i/①8000/,f6000芘/4000//-§2000/ ̄ ̄ ̄ ̄ ̄ ̄^tf〇DifferentDatasets图4.7实验1不同数据集的分类时间对比F.4.7Tltontmeerentatasetsinexerienceoneighecassificaiiofdiffdp-忉- 东北大学硕士学位论文第4章实验说明及结果分析一结论分析可以发现8个不同种类数据集,数据量大小从4192581012:通过实验到一1—组数据实不等,对三种支持向量机LIBSVM、SVM以及SurrSVM进行实验。在每验结果对比中可见,在分类正确率相差不大的情况下,SurrSVM算法普遍用时短。L^tIBSVM和SurrSVM的分类正确率比较稳定,SVM在对个别数据集进行分类时,正一确率较低。实验的结果可以初步证明本课题设计的SurrSVM适用于大规模数据分类。一SmrSV实验二:为了进步证明M在大规模数据分类中的适用性,实验二采用正态分布集群数据发生器产生不同规模的NDC数据集一组NDC数据集的特点是样本。这****20k32k的数量不同,特征维度相同,即分别随机产生10032200k32300k32,,,和*一50032NDC-k,.44.6的数据集,与实验步骤相同运行结果如表4所示:表4.4实验1三种算法的惩罚因子Table4.4ThepenaltyfactorofthealgorithminexperimentoneNDC数据集n咖SurrSVMLIBSVMSVM样本数-95°2w222-2'°2?2°lOw-20107°w222-30w2'°262°-50w2'°252°^tQS,2,SVMVM默认的惩罚因子值是1即试验中离散因子的取值与LIB和-1()21Q4SmrSVM方式相同.4,从2到,记录结果见表。从对惩罚因子角度来看,LIBSVM方法对错误的惩罚较重,SurrSVM方法对错误的惩罚最轻,但是并不意味着对分类准确4.51率有影响,给出了实验中三种算法分类正确率表。表4.5不同规模的NDC数据集分类正确率Table4.5TheclassificationaccuracofdifferentNDCdatasetsyNDC数据集1Sur1咖rSVMLIBSVMSVM样本数2w85.85%86.11%85.98%lOw86.24%86.31%86.32%20w85.74%85.87%86.26%30w85.31%86.05%86.06%50w84.71%86.17%86.23%-50- 东北大学硕士学位论文第4章实验说明及结果分析一组NDC数据集整体来看,三种算法的分类正确率相差不大,说明在相,对于任同条件下,SurrSVM方法可以得到与经典算法相同的分类正确率。表4.6给出的是分类时间数据。表4.6不同规模的NDC数据集分类时间Table4.6TheclassificationtimeofdifferentNDCdatasetsNDC数据集SurrSVMLIBSVMSVM_样本数2w3.0841.8610.86lOw16.581025.04262.5920w34.963640.121037.2730w53.848260.512501.9850w72.4522624.627126.92一*30w32C从表4.6结果可以看到,对于同组数据集,以样本的ND数据集为例,26051—1三种方法的分类时间有显著差别1VM250198,LIBSVM分类用时8.秒S.,用时秒,而SurrSVM用时仅为53.84秒,纵观五组不同规模的NDC数据集,SurrSVM大〇w大减少了分类时间成本。特别是在进行大规模数据集分类(超过l的数据集)时,相同的实验背景下,SurrSVM方法的优势很显著。所以惩罚因子的大小没有对分类正确率产生重要影响,我们设计的SurrSVM方法在保证分类正确率的情况下,对时间成本进行了有效的控制。86—.5—SSVMur—86libSVM4——?SVMlhtig…—86-3丨IiJ-…….......….???-■-丨卜丨;i85—.70510152025303540NDCDaasestt图4.8不同规模的NDC数据集分类正确率对比F.4.8TaccuraccomarisonofNDCetsnitszeigheydatasidfferenip--51 东北大学硕士学位论文第4章实验说明及结果分析10000';..—SurSVM90一—*---004%libSVM:一*—SVMlihtg-—-ff--…8000r一::;r^6000-」-------:—;/;\/\5000'…一—…十—…―……r—Ih十L」4000—丨…_||:::!30。。——-—…-!2000…r000………….1::「—:^??0510152025303540NDCDatasets图4.9不同规模的NDC数据集分类时间对比Fig.4.9ThetimecomarisonofNDCdatasetsindifferentsizep结论分析:实验过程中选取分类效率最佳的惩罚因子/?,作为最终记录参数。从结果可以看出,NDC数据集当且仅当样本集大小不相同的时候正确率的表现上,在分类没有明显差别,如图4.8所示。但分类时间差别明显,图4.9直观地可以看到:随着样本规模增加(数据量从2万增加到50万,维度相同),每种算法用于分类的时间均会增加,但SurrSVM方法的用时远远小于另两种方法2:。所以从实验可以得出结论不同规模的NDC数据集之间分类正确率差别不大,但SurrSVM方法在降低分类时间成本上有显著优势一SuSVM。进步证明了rr适用于大规模数据分类;:NDC,实验三数据发生器在生成数据集时离散因子取值不同,相应的数据离散程度不同。为了研宄数据集离散程度与分类效果的关系,我们分别选取离散因子ExpandF=actor100,50,20,10,5,生成了离散程度不同的数据量为10万的五组NDC数据,实验结果如表4.7和表4.8所示集:表4.7离散程度不同的NDC数据集分类正确率Table4.7TheclassificationaccuracofNDCdaasetswithdifferentetytxpandfacorHh,离散因子SurrSVMLIBSVMSVM84-7°100261.5%256.5%260.9%A-762°50264.10%2.39%260.98%-2°202741.02%273.95%273.71%-33°10286.31%286.30%282.07%2-397726°5%1.197.7%297.19%-52- 东北大学硕士学位论文第4章实验说明及结果分析(首先分析惩罚因子SurrSVM方法对错误的惩罚偏低,随着数据离散程度降低数VM1^),S据更聚集,LIBSVM方法对错误的惩罚程度逐渐增加方法的惩罚参数基本’SuVMLIBSVM方法分类正确率略高于SVM,恒定,rrS。在分类正确率的表现上和一一组数据,离散因子越小,即数据越聚集,分类正所以可以得出结论:针对同算法同确率越高,在三种算法之间作对比,除了在离散因子为100时,LIBSVM表现略差以外,uhtVMLgSurrSIBSVM分类效果略高于SVM。从整体角度来看,和表4.8离散程度不同的数据集分类时间swirentexanacorTable4.8TheclasscatontmeofNDCdatasetithdffedftifiiipVML1砂1离散因子SurrSIBSVMSVM1.s.201.2s100898696s.5079.1s1017s2075s2058.4s886.8s308.7s771.3s148.7s10.9s48111.5s576.1s178.6s,变化情况。SurrSVM方分析分类的时间成本即随着离散因子的改变,分类时间的1—1L80SVM500IBSVM117,方法最高用时达0秒。法用时在秒以内,用时在秒以内可见即便数据的离散程度不同,在其他条件相同的情况下,即样本数量相同(NDC数据集的样本数量均为10万),样本维数相同,SurrSVM可以较好的控制时间成本。从图4.8中可以看出变化趋势。'■-100j—SurrSVMJ-t—iVM95lbSSVMlihtg—Z"85y1zI^17--0〇*55〇510152025303540NDCatasetsD图4.10不同离散因子对分类正确率的影响'Fltclasscationccurac.4.1Direntdiscretefactorsinfuenceonheifiaig0ffey-53- 东北大学硕士学位论文第4章实验说明及结果分析-■1200nI11i1丨7n一—*?rrMSuSV—#—?iblSVM1000—VM?Slight!y?丨■丨i\--…8800…-Jri:^::\i丨丨\ii:::丨\I4。。…………:—………“……一」卜^IK'200*.^…-,^^----—丨:ia ̄ ̄ ̄^f〇!!!:0510152025303540NDCDatasets4.图11不同离散因子对分类时间的影响'uFig.4.11Differentdiscretefactorsinflenceontheclassificationtime3一组数据结论分析:通过实验的实验结果,我们可以得出结论,离散因子越:同小,即对应的离散程度越低,分类正确率越高.10,从图4可以直观的看到结论:横坐标01020,30,40的点分别1005020,,对应离散因子,,10和5,,纵坐标代表分类正确率,三种方法分类正确率均随着离散程度的降低而增加,整体米看,SurrSVM和uh一LSgtIBVM分类效果略好于SVM。三种算法之间对比可见,同组数据,分类正确率相近,SurrSVM分类时间最少,如图4.11所示,在实验中降低时间成本更显著。经以上三组实验过程以及结果分析,我们可以得出结论,基于代理函数的大规模支持向量机分类算法适用于对大数据的分类,,保证分类精度的前提下采用迭代算法之后,分类时间成本可以有很好的控制。4.3生物医学颔域应用实验通过以上三组实验,可知SurrSVM算法在保证分类正确率的前提下,大大提高了“”分类速度信息碎片化,。针对目前医学健康领域存在的等问题接下来讨论大规模数据分类算法在生物医学领域的实际应用。在健康医学领域,文本数据蕴含着丰富的价值,,以临床病案为例包含着病人的症状,、主诉信息病程记录、临床检验结果、病理参数、化验结果、以及诊断记录等等。如果利用数据挖掘和SVM的知识,对疾病进行分类或者对病情的严重程度分类将为临床诊疗法案的选择具有重大意义。总之,高效的利用健康医疗大数据将会为计算机辅助医疗卫生监测一一,公众健康等领域带来创造性变化和价值组,,所以这部分我们选取-54- 东北大学硕士学位论文第4章实验说明及结果分析医学大数据,通过数据处理和转化,应用到三种算法上,经实验对比,验证SurrSVM算法在大规模数据分类中的优越性。我们选取的数据是从1999年至2008年美国130家医院的临床糖尿病诊疗数据,这组数据包含10万多样本,每个样本有50个特征项。数据集中收录的样本需要满足以下准则:(1)彳目息从住院患者中米集;(2)采集与糖尿病相关的诊查信息及特征;(3)住院时间在141到天的范围内;(4)信息记录保证是在住院期间;(5)住院期间需要进行药物治疗。为了保证信息获取的准确性,首先要保证患者接受住院治疗,并且住院期间进行糖尿病诊断和用药等相关治疗,然后对整个诊疗过程进行了记录。通过对患者的详细记录,“”“包括糖尿病相关检查和结果,糖尿病患者,在全部的样本中选择诊断结果为和非”-糖尿病患者的数据项,标签分别设置为+1和1,组成新的数据集,删除没有明确诊断或者其他特殊情况的样本及特征。剩余样本数100239,用于分类的特征项包括的信息很多,个人信息、诊查结果以及药物治疗和护理信息等。对这个新的数据集进行训练,得一到训练模型后,再随机抽取部分样本组成测试集,进行分类测试,记录惩罚因子、分4类正确率和分类时间.9、.1.11,实验结果如表4表40和所示。表4.9三种算法的惩罚因子Table4.9Theenaltfactorofthealorithmspyg111VMLVM*1算法SurrSIBSSVMQ'5°惩罚因子2224表.10三种算法的分类正确率对比结果Table4.10TheclassificationaccuracyofthealgorithmsuU加算法SrrSVMLIBSVMSVM分类正确率99.98%99.92%99.87%--55 东北大学碩士学位论文第4章实验说明及结果分析从分类正确率和惩罚因子的角度可以看出,与之前三组实验结果类似:LIBSVM对Kght,SVM对错误的惩罚程度最小。但是分类时间的角度rSVM错误的惩罚程度最大,Sur具有明显的优势。表4.11三种算法分类时间对比结果Table4.11TheclassificationtimeofthealgorithmsLVM1甽算法SurrSVMIBSSVM分类时间36.43s518.35s273.90s,,在分类正确率上三种算法相差不大通过多次实验取平均测试结果;但是在分类时间上rSVM平均用时最少,如表4.11所示,也就是说我们设计的算法在实际应,Sur用中具备较高的分类效率。当数据规模增大时,传统的SVM算法虽然具有较高的分类准确率,但是时间成本消耗大,采用SurrSVM方法可以在保证分类精准度的前提下,快速准确的对文本数据进行分类。以上经过对医学文本信息分类,证明了本课题设计的基于代理函数的大规模支持向量机分类算法的实用性。随着计算机辅助诊疗技术的不断发展,生物医学领域数据也有更多的体现形式,需要我们结合数据处理算法,使支持向量机良好的分类效果在生物医学信息处理领域发挥更大的优势。总的来说,在医学信息处理方面,SVM算法可以应用在以下方面:(1)对医学图像进行分割以及数据处理;(2)训练学习机,进行计算机辅助医疗诊断;(3)、筛选以及疗效定位通过训练模型实现药物研发;(4)疾病预后状态的预测及对其他指标的预测。(5)针对医学影像进行识别和研宄,对图像的特征因子进行构建,再利用支持向量机进行分类处理。因此,,在实际应用中除了将算法用于文本分类以外我们还要构建完备的医学知识体系,针对医学影像构建明确、可靠的特征向量集,并采用合理的特征优化方式,建立计算机辅助诊疗模型,从而使大规模支持向量机分类方法逐步应用在医学图像模式识别分类领域。与此同时,通过对SVM分类精确度的不断改善,进而扩展大规模支持向量机分类算法的应用。这样可以更加充分的利用健康医疗大数据,,为计算机辅助医疗卫生监测以及公众健康等领域带来创造性的价值。-56- 东北大学硕士学位论文第4章实验说明及结果分析4.4本章小结W通过将SurrSVM与两种经典算法LIBSVM和SVM进行多组实验对比,实验1首先选取了不同种类不同规模的数据集进行测试,从分类正确率和分类时间两个角度,一初步得出结论,SurrSVM方法适用于大规模支持向量机分类;为了使数据集保持致性,进行了实验2,用NDC数据发生器生成样本数为2万,10万,20万,30万和50万的NDC数据集,实验结果显示,处理大规模数据集时,在处理精度方面,三种算法差距light,urrSVM方法和LIBSVM的分类精确VM不大但S度更稳定,S在个别数据集分类效一^t,表现欠佳。在分类速度方面,SurrSVM方法明显优于LIBSVM和SVM果上,进步说明了基于代理函数的大规模支持向量机算法的适用性;实验3说明了数据离散程度,,对分类效率的影响:数据越聚集分类正确率越高SurrSVM分类用时最少。一最后组实验,我们选用糖尿病患者的临床治疗文本数据对SurrSVM进行了测试,结果表明,我们设计的迭代策略有效的降低了分类的时间成本,基于代理函数的大规模支持向量机算法适用于大规模数据分类,而且具有较高的分类效率。-57- 东北大学碩士学位论文第4章实验说明及结果分析-58- 东北大学硕士学位论文第5章结束语第5章结束语5.1本文工作总结,随着大数据时代的到来,机器学习和数据挖掘算法越来越受到重视在医学领域亦是如此,从海量的结构复杂的数据中获取正确的、创造性的、有潜在价值的信息成了研宂者们的努力目标。各领域的工作者,也越来越希望能够充分挖掘出现存数据库中所蕴含的信息,并在未来做出决策时有效利用。以医学类大数据为例,基于对现有的医学数据库进行数据挖掘和知识发现,可以对医生做出正确的诊断和检查具有重要,的辅助作用。同时、模,对于医学图像分析分类式识别分类来说大规模数据分类算法也很具有研宄性以及可发展性。针对数据挖掘中的分类,本课题做了以下的研宄工作:(1)首先介绍了大数据及健康医学大数据背景下的机器学习重要性,对支持向量机的发展历史、国内外研究现状作了介绍。对SVM基本的SLT、凸优化数学模型、进行VM11#LIBVM了介绍,并分析了两种经典的算法S和S,由于现存的机器学习方法在大规模数据处理时效率不高,所以给出了本文的研宄意义。(2)引入代理模型的概念,通过构造Surrogate函数的方式建立新的SVM迭代模型,创造性的利用矩阵分解思想,再引入常系数,通过数学推导求解迭代公式,再对迭代算法进行编程实现。由于二次规划的全局最优解需要满足KT条件,所以算法实现之一后,SVM,S,我们对序列的全局收敛性进行了说明。此外与其他方法样urrSVM,在迭代过程中应该尽量避免会遇到内存消耗问题。M和1#1(3)分析两种经典算法LIBSVSVM的思想,以及使用过程中的配置问题和,将本课题提出的基于Suoate函数的SurrSVM方法与两种经典的支持向参数设置rrgL1—量机算法IBSVM和SVM进行对比。通过实验1,2,3这三组不同角度的实验对比可以得出结论,:处理大规模数据集时,在保证算法的分类正确率前提下本文提出的基于Surrogate函数的大规模支持向量机方法可以大大降低时间成本,能够快速、准确的进行大规模数据分类。(4),,组成实验所用最后,以实际医院的文本数据为例对数据进行处理和转换之后的测试集,对三种算法的性能进行对比验证。多次实验记录平均结果,分析惩罚因子,SuSVM分类正确率和分类用时等实验结果,充分体现了rr方法在实际应用中的可靠性和优越性。--59 东北大学硕士学位论文第5章结束语进入大数据时代,数据量的加大也增加了SVM算法的需求,目前提出的己知算法在计算过程中迭代次数多,花费时间过长,已,对此本,计算复杂经不能满足需要文主要解决了SVM算法的运行速度问题,并使用机器学习UCI数据库中的多组大规模数据集对算法进行了测试。结果表明基于Surrogate函数的SVM算法完全能够对大数据进行动态、快速、准确的处理。5.2研究展望随着计算机及互联网的不断进步,数据量会愈发的增大,人们需要计算机代替人类处理大规模数据,SVM相关算法作为机器学习领域的重要组成部分也愈发的受到人们的关注。在生物医学工程领域,支持向量机正在被应用到医学文本方面和医学影像,。方面的大数据处理问题当中科学研宄急需速度快,精度高的支持向量分类机而且随着数字化医疗的快速发展与信息化建设系统的普及,目前国内外各医疗机构积累了大量患者临床数据信息和电子病例等,这些大量复杂的数据里蕴藏着很多有,,价值的信息。此外,高精度医学医学影像设备不断更新临床采集的数据越来越全面也越来越复杂,怎样更好的处理、分类、分析健康医疗大数据,整合碎片信息等问题是计算机辅助医疗方面研宄的重要方向。支持向量机相关算法发展至今,虽然已经积累了无数前人们的经验,但是仍然有很多方面需要深入研究,既包括SVM分类算法本身的不断改善,也包括多学科应用领域的结合与扩展:(1)本文提出了的SurrSVM方法在线性空间中得以验证,虽然多分类SVM可以由二,分类算法延伸得到但现存的多分类方法尚不完善,本文绪论中介绍的几种SVM多分类算法各有利弊二一,它们在速度及效率方面都不及分类算法,开发出套快速有^[的SVM多分类算法理论成了迫切的需要。(2)系统化的、准确的对核函数及相应参数进行选取。当空间维度低于3时,人们可以直观的观察到数据的分布,并根据数据的分布选取核函数;当空间维度高于3时,人类无法直观的观察4维空间中数据点的分布,从而无法有效的选取核函数。而且,目前研宄领域对核函数以及相应参数的选取尚且缺乏完善的理论依据,因此如何系统SVM一有效的选取核函数及核函数的参数是算法中急需解决的问题之。一(3)医学图像模式的分类研究具有广泛的应用前景。本文在实验阶段选取了组医学文本数据对算法进行测试,在未来的研宄过程中,我们致力于将医学图像的处理技术,从而使分类机器在医学图像分割与机器学习分类技术有机地结合、计算机辅助医疗--60 东北大学硕士学位论文第5章结束语诊断、药物研发、筛选以及疾病预后状态的预测等领域均发挥重要作用。通过对医学影像进行识别和研宄,从而有效的提高医学图像分类的性能,完成信息化辅助医疗诊断过程,这些都具有重要的现实意义。对医学大数据进行挖掘和知识发现是实现辅助医疗的重要途径,也是智能诊断系统的发展方向。总之,在未来的研宄工作中,需要我们结合生物医学工程的学科特点对数据挖掘,综合理论方法探究和机器学习算法进行不断的探索、算法设计实现以及实际生产应用,全面提高相关技术领域的发展。--61 东北大学硕士学位论文第5章结束语--62 东北大学硕士学位论文参考文献参考文献——1?大数据成信息技术领域热门概念EBL.201222t://wwwcll.人民日报/O[02?htp.4.[]]net/news/212/a747301.html.L--tt:w2.中国信息产业网.大数据的四个典型特征[EB/O.20120222.hp//c.cena.com.cn/][]yya/--20121204/135458292978407.shtml.--AMISHBIII:efourVsofataBL2013comt3.H.SThbigd./O.0724.ht://www.uer[E][]ppworld.com.au/article/396198/iiisfourvsbidata/.___g_4.YanXiaofenZhanDexin.BidataresearchJ.ComuterTechnoloandDevelomentg,gg[]pgyp,2013234168-172:.,()5.J20121陈如明.大数据时代的挑战价值与应对策略[.移动通信7.],()--?J201546.宁氣陈挺生物医学大数据的现状与展望.中国科学,,6056:53546.[]()7.Overpeck,JonathanT,Meehl,GeralA;Bonyetal.Dealingwithdata:Climatedatacha-llenesinthe21stcentury[J.Science,2011334;700702.g],-.8.郭华东.科学大数据与数字地球J中国科学1:1王力哲,陈方等,2014592047,,[]()1054.?9.WiganMR,ClarkeR.BigDatasBigUnintendedConsequences[J].Computer,2013,46-6:4653).(i〇.何清李宁罗文娟等.大数据下的机器学习算法综述m.模式识别与人工智能,,,274-:327336.()11iteFDamerauWeiss.S.owardsanuaendtAtt.ChdanandAredM.TLIeendenuomaedp,,ggpLearninofTextCateorizationModels.In:ProceedingsofACMSIGIRConference.94gg,1994-:2330.一12..刘钢胡四泉范植华等神经网络在文本分类上的种应用[J].计算机工程与应,,,20033936-用:737492.,,(),13EthemAladm.IntroductiontoMachineLeaminM.Beiin:ChinaMachine.pyg[]jgPress,2009.14.钱海军.基于BP神经网络的图像压缩的Matlab实现[J.电脑开发与应]24-用201112:7779.,,()15ankVTheNatuofstaiscaearninTheorework:S1.Vi.retllyM.NYpringer995.pg[],-6-3 东北大学硕士学位论文参考文献16.OsunaEFrenudRGirosiF.Animprovedtraininalgorithmforsuortvector,?gppnesroceesofIrk-shoonNeuramachiC.PdingEEEWoplNetworksforSinalProcessing.[]gNework-Y1997276285.,,-nM17oachmsTMakinareertectorachneLearnractca.Ji.gLgScalSuppoVMiigPil.[]Advances-inKernelMethodsSuportVectorLearninCambrideMA:MITPress1999:pg,g,,-169184.18ttJtttttr.Pla.Sequentialminimalopimizaion:AfasalgorihmforaininsupportvectorInAdvt-CtVtttsmachines.ancesinkernelMehodsSuorecorlearnin.Massachuse:The[]ppg-MITPress1999185208.,,19--2004.,田英杰.数支持向量机M.北京:科学出版社.邓乃扬据挖掘中的新方法[],20DebnaTakah--ideahashHAecsonasedonae.thR.N.&Taki.diiboneainstonmethod5,gtortt164-1formulticlasssuortvecmachineJ.PaernAnalAlic20047:75.pp,pp[],21TanYuhuiJinBoZhananinetal.Granularsuortvectormachinesformedical.Yg,,gqgppbinaryclassificationroblemsC,ProceedingsoftheIEEECIBIB.PiscatawaHJ:IEEEp[]y,aionlnellenceocet2004-ComputtIt:.igSiy,737822.LiXuehuaShuLannec.FuzztheorasedsuortvectormachilassifierC.,yybpp[]ProceedingsoftheFifthInternationalConferenceonFuzzySystemsandKnowledgeD-iscovery.ShandongChinas.n.2008:600604,,[]?23---DinLiuXZhLiweni.Shifei,iaolianan.Researchonranknsuortvectormachinegg,ggppandrosectsC.Proceedinsofthe29thChineseControlConference,Beiin:s.n.2010pp[]gjg[]?,2829-283124柴毅.基于SVM的二叉树多类分类算法及其在故障诊断中的应用.马笑潇黄席樾,,-J,21:72276.?控制与决策003,832[]()25..吴洪兴适用于不平衡样本数据处理的支持向量机方法.电子学,彭宇,彭喜元2-0063412:23952398报.,,()26.NguyenT.,NgoAnhVien,NguyenH.V.etal.ProbabilisticrankingsupportvectordvancesinNeuralNetworks-BN2ln-machineC:ner2009:45,AIS00.BeriSpri3353.[]g,27WRLY-velun.ShiYHGaoYanZhanWanD.Transductivecostsenstcancer,ii,g,g,gg-imaeclassificationA12.g.lIntel201338l:68pp,,()28.李磊黄水平.支持向量机原理及其在医学分类中的应用.徐州医学院公共卫生学院,(221002)2009.,-64- 东北大学硕士学位论文参考文献X-29iHonMin.Zhangaodan,ZHAOgling,Wang.Thestructureandapplicationofanew-smoothsuortvectormachine.racticeandtheor2014445ppMathematicsin:179186.py,,()30.田晓春.支持向量机在医学数据分类中的建模研宄.D.太原理工大学2015.[]A-WV31.amourakiD.VassisP.BelsisCSkourlas.eDoctor:AebBasedSuortector.Kp,,,ppMachineforAutomaticMedicalDiagnosis.[J]SocialandBehavioralSciences.2013,73,467-474.32.CORTESC,VAPNIKVSupportvectornetworks[J].MachineLearning,1995,20-3:273297.()33(2003.张浩然.支持向量机算法及应用研宄D).上海:上海交通大学.,34.VapnikV.N..StatisticalLeaningTheory,许建华,张学工译.北京:电子工业出版社,2004.35-.VanLevtVikVN.inELeC.Y.MeasurinheCdimensionofalearninmachine.Neuralp,ggt-Comutaion19946:851876p,,Ri36.O.ManasarianDavid.Muscant.LaranianSuortVectorMachineJThe丄.g,ggpp[]Journaof1-17lMachineLearninResearch2001:617.g,1,37.SEWELLM.KernelmethodsR.London:DeartmentofComuterScienceUniversit]p,[pyofLondon2007.,38.JoachimsTextCateorizationwithSuortVectorMachines.Learninwt.TgppgihManyRelevantFeatures.Proceedinsofthe10thEuroeanConferenceonMachineLearnin1998.gpg,-39.JoachimsTMakingLareScaleSVMLearninPracticalIn:Scholko,,gpfBBuresCJCggMe-SmolaAeds.AdvancesinKernelthodsSuortVectorLearninge.MA:MITpp,CambridgP-ress1998169184.,,40Peetenceofamodi.LauraalagiandMarcoSiandron.Onheconvergfiedversionof--SVMlihtalorithm.OtimizationMethodsandSoftware.2023:3153322005.ggp(),41.赵丽,李天舒,刘玉蕾.基于支持向量机的机器学习研宄[J].哈尔滨师范大学自然科-0082465.学学报:659,2,()VaV-42.nik.TheNatureofStatisticalLearninTheor.NewYorkSrinerVerla5pgy:pgg199.,43.Pontietal.theeodelofSuortVectorachneReression.aerlM,OnNotMppMigCBCLPp168AIMemo1651,MITCambride,MA,Oct.1998.,,,g44--.anandn.LIBVM:aarforsuortvectormachs2005.CC.ChgC.J.LiSlibryppine.,45.李建民张钹林福宗.序贯最小优化的改进算法软件学报.2003vOl.14No.5.,,,-65- 东北大学硕士学位论文参考文献46'.KeerthiS.ShevadeSBhattcharaetal.ImrovementstoPlattsSMOalorithmfor,5yy?pglassifierdesin-SVMcg.NeuralComputation2001133:637649.,5()47.JianminLi,BoZhang,FuzongLin.ANewCacheReplacementAlgorithminSMO.LectureotesnomutercienceVol238t-353NICpS;834248.HansUlrichSimon.Onthecomplexityofworkinsetselection.InProceedinsofthegg15thInternationalConferenceonAlgorithmicLearninTheorALT20042004.gy()?49一No.张召国兴鲍钮.种改进的SMO算法计算机科学.2003v01.308.,,黄,,50.KleinenJackP.C.Statisticaltoolsforsimulationractitioners.JournalofEconomicj,pLiterature,NewYork:AcademicPress,1987.51YueanTengTieZhanGeneEM-tenst.ygg.ralizedrecoructionalorithmsforemission,ypgomoraransactons-tgphyJ.IEEETionMedicalImagin2012319:17241733.[]g,,()-.JLteconverenceofmutcattnett52C.inOnhlipliiveudaealgorithmsfornonaivemarix,gpgfacorizaion-tt.IEEETrans.NeuralNetworksvol.18.158915962007.,,pp,53anwillonlinearProrammin:AfedAroacewYor.W.I.ZgUniih.NkUSA:,Nggpp,-HaPrenticell1969.,54*K.LaneandR.CarsonEMreconstructionalorithmsforemissonandtransmssoniiig,gtomography,JournalofComputerAssistedTomographyTomography,vol.8,No.2,306-.3161984.pp,55Acttili.Y.TenY.ZhanH.LiandY.Kan.onverennonneaivedeconvolutonaorthmg,,gggggwithTikhonovregularization.InverseProblems,vol.31?no.3,ArticleID035002,2015.56DsAttoS.YueyangTengShoulianiauXiaoLihenXu.eneralSoluionuares,gQ,y,ggqProblemswithBoxConstraintsandItsApplications.MathematicalProblemsinEngineering.Volume2016ArticalID3934827.,57.D.R.Musicant.NDC:NormallyDistributedClusteredDatasets.www.cs.wisc_edu/dmi/,1998.58.LichmanM.UCIMachineLearningRepository,archive.ics.uci.edu/mlj2013.59.JeffSchlimmer.MushroomrecordsdrawnfromtheAudubonSocietyFieldGuidetoNorthAmericanMushrooms1981.G.H.LincoffNewYork:AlfredA.Knof.()5p60.R.KBock.Methodsformultidimensionaleventclassification:acasestudusinimaes,ygg-t-fromaCherenkovammaraelescoe.Nucl.Instr.Meth.A2004516:511528.gyp,()-66- 东北大学颂士学位论文致谢时光荏苒,岁月如梭。转眼间三年的硕士生活即将结束,在实验室的科研生活也。,将画上句号回首这两年的学习生活,我内心充满感激之情,感谢老师的谆谆教导感谢家人、同学的支持陪伴。,我要感谢张耀楠老师和滕月阳老师。在刚步入研究生阶段时首先,感谢张老师的悉心指导,确,感谢张老师的督促和引导,使我养成,让我走过迷茫期定未来方向了制定学习规划并严格执行的好习惯。另外,我还要深深的感谢滕月阳老师,两年来一一我点点取得的进步离不开您的指导。在刚接触课题研宄时,您要求我阅读精心挑,为我指点迷津选的参考文献,让我在不断的摸索试探中学到了,给我讲解算法思想,,知识,避免了很多弯路滕老师学识渊博思维。当我遇事迷茫时您耐心的解疑答惑里,,我不仅学到了专业知识同时也学到了严谨的学习活跃,刻苦钻研,从滕老师那态度!您们辛苦了!。在此,我谨向张耀楠老师和滕月阳老师表示真诚的谢意其次。,我要感谢我的家人你无微不至的关爱以及理解与支持是我不断前进的动力,。感谢父母为我无私地付出未来的日子我将不断努力奋斗,报答你们的养育之恩。再次,感谢,我要感谢陪伴我两年学习和生活的同学们你们在我遇到疑惑时的帮一助,,这段并肩奋斗的日子将铭,和我起讨论问题。虽然相处的时间短暂但我相信记一生。最后,感谢评审本论文的各位老师及专家,感谢他们认真的评阅和专业的意见。-67- 东北大学硕士学位论文致谢-68- 东北大学硕士学位论文研究生期间发表论文情况研究生期间发表论文情况1ueanTenLiu-,YaxinXuanxieBinLuandYanKan.SurroatebasedSuort.Yygg,,ggppVectorMachineMethod.[J]2016InternationalConferenceonModeling,SimulationandOptimizationTechnologiesandApplications(MSOTA2016)[C].Inpressing.2.YueyangTeng,Xuanxie,YaxinLiu,BinLuandYanKang.SmoothingNonnegativeMatrixFactorizationsandItsAlicationtoExtractionofTimeActivityCurveinppDynamicBraininPET.[JoumalofMedicalImagingandHealthyInformatics]Inressn.pig-6-9
此文档下载收益归作者所有