《支持向量机的若干算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
分类号：TP181密级：公开UDC：单位代码：10424学位论文支持向量机的若干算法研究胡运红申请学位级别：博士学位专业名称：计算机软件与理论指导教师姓名：贺国平职称：教授山东科技大学二零一一年五月 论文题目：支持向量机的若干算法研究作者姓名：胡运红入学时间：2008年9月专业名称：计算机软件与理论研究方向：知识处理与数据挖掘指导教师：贺国平职称：教授论文提交日期：2011年4月20日论文答辩日期：2011年6月11日授予学位日期：2011年6月24日 SOMEAlGORITHMSRESEARCHONSUPPORTVECTORMACHINESADissertationsubmittedinfulfillmentoftherequirementsofthedegreeofDOCTOROFPHILOSOPHYfromShandongUniversityofScienceandTechnologybyHuYunhongSupervisor:ProfessorHeGuopingCollegeofInformationScienceandEngineeringMay2011 声明本人呈交给山东科技大学的这篇博士学位论文，除了所列参考文献和世所公认的文献外，全部是本人在导师指导下的研究成果.该论文资料尚没有呈交于其它任何学术机关作鉴定.博士生签名：日期：AFFIRMATIONIdeclarethatthisdissertation,submittedinfulfillmentoftherequirementsfortheawardofDoctorofPhilosophyinShandongUniversityofScienceandTechnology,iswhollymyownworkunlessreferencedofacknowledge.Thedocumenthasnotbeensubmittedforqualificationatanyotheracademicinstitute.Signature:Date: 山东科技大学博士学位论文摘要摘要支持向量机是一种通用的学习机器,是数据挖掘中的一项新技术，是借助于最优化方法解决机器学习问题的新工具.其核心问题是对一个大规模凸二次规划问题进行求解.分解算法是求解支持向量机的一类基于工作集选择的有效算法.隐私保护支持向量机算法则是在隐私保护数据挖掘算法基础上新兴起来的一个研究方向，在银行、保险公司、医学研究机构等行业有着广泛的应用.本文主要研究求解支持向量机的简化分解算法和针对分布式数据的隐私保护支持向量机算法，主要工作如下：首先，通过回顾支持向量机算法的发展过程及总结其研究现状，引出本文所做的主要工作.考虑到无论是原始支持向量机模型，还是本文重点讨论的隐私保护支持向量机模型，其本质问题是对一个大规模凸二次规划的求解，因此本文首先从研究支持向量机和对应乘子之间的关系着手，并给出一个新的分解算法.第二章中，基于支持向量机模型中支持向量的重要性，对支持向量和对应乘子之间的关系进行了理论分析，并借助图形，直观地分析了支持向量相对于决策面的几何关系.同时，通过对简化算法的终止条件及工作集选择的分析，探讨了违背和最大违背KKT条件对的几何含义，为直观理解终止条件及工作集选择方案提供理论依据.第三章中，通过对求解大规模支持向量机的分解算法中各种工作集选择方法的优劣进行比较，提出一类求解基于带有线性等式和上下界约束优化问题的大规模支持向量机模型的新分解算法.该算法每次迭代的可行下降方向从具有偶数个分量的相对稀疏可行方向中选取.在假设水平方向集中至少有一组下标对应的分量严格在上下界之间的前提下，证明了算法的全局收敛性，并通过数值实验验证了算法的有效性.本文的下半部分，主要研究隐私保护支持向量机算法.第四章和第五章，分别针对数据垂直分布与水平分布的情况，提出了两个隐私保护支持向量机算法.对于数据垂直分布的情形，算法直接基于矩阵分解的理论，给出的分类器是公开的，但是未泄露任何参与方的原始数据.对于数据水平分布的情况，与已有的SVM分类器不同，算法借助了安全多方计算的加密技术，给出的分类器是公开的，同样也未揭露任何参与方的原始数据.利用矩阵分解理论证明了算法的可行性.数值实验表明我们给出的隐私保护支持向量机算法的分类精度要比Mangasrian的简约隐私保护支持向量机算法的分类精度高.第六章，针对数据任意分割的情况，利用数据水平分布情况下的矩阵乘积的安全性策略，提出了一个隐私保护支持向量机算法，在未揭露任何参与方的原始数据的情况下 山东科技大学博士学位论文摘要给出了公开的分类器.该算法的分类精度比Mangasarian给出的简约隐私保护支持向量机算法的分类精度高.最后利用矩阵分解理论证明了该算法是可行的和有效的.最后，在第七章中，给出了现有支持向量机算法中存在的及本文尚未解决的问题，提出了进一步研究的课题.关键词：数据挖掘，机器学习，支持向量机，分解算法，安全多方计算，隐私保护支持向量机 山东科技大学博士学位论文AbstractAbstractSupportVectorMachine(SVM)isakindofgeneralizedlearningmachineandanewtechniqueofdatamining.Itisanewtooltosolveproblemsinmachinelearningbyoptimizationmethods.ThecriticalproblemofSVMistosolvealargescaleconvexquadraticproblem.DecompositionalgorithmisasimpleandeffectivemethodforsolvingSVManditsmaintechniqueishowtoselectaworkingset.Privacypreservingsupportvectormachine(PPSVM)isanewresearchfieldonthebaseofprivacypreservingdatamining(PPDM)algorithm.PPSVMiswidelyappliedinbank,insurancecompany,medicalresearchinstitute.ThispapermainlyfocusesonthesimplifieddecompositionalgorithmforsovingSVMandPPSVMfordistributeddata,andthemainworkisasfollows:Firstly,WeoverviewcurrentresearchonSVMandshowourmainworks.Asweknow,thecriticalproblemistosolveaconvexquadraticprogrammingproblemforbothoriginalSVMmodelandprivacypreservingsupportvectromachinemodelwhichwemainlydiscussedinourdissertation.InChapter2,BasedonthesignificanceofSupportVectoringeneralsimplifiedalgorithms,WetheoreticallyanalyzetherelationbetweentheSupportVectorsandthecorrespondingmultipliersandsetforththegeometricalrelationbetweenthesupportvectorsandthedecisionsurfacebymakingthegraph.Furthermore,wealsoanalyzethegeometricalmeaningofthepairofviolatingKKTconditionbyanalyzingtheterminationconditions.InChapter3,Byanalyzingandconstrastingallkindsofworkingsetselectionmethod,weputforwardanewdecompositionalgorithmforsovingakindoflargescaleSVMmodelwithasinglelinearequalityconstraintandboxconstraints.Ateachiteration，adescentsearchdirectionisselectedamongasuitablesetofsparsefeasibledirectionswhichhaveevencomponentstoreducetheiterationnumbers.Theglobalconvergenceofthealgorithmmodelisprovedbyassumingthepointsofthelevelsethaveatleastonegroupindexstrictlybetweenthelowerandupperbounds.Numericalexperimentsshowthatour 山东科技大学博士学位论文Abstractalgorithmiseffective.Innextchapters,wefocusourattentiononprivacypreservingsupportvectormachinealgorithm.InChapter4andChapter5,twonovelprivacy-preservingsupportvectormachine(PPSVM)classifiersareputforwardforverticallypartitioneddataandhorizontallypartitioneddata.Forverticallypartitioneddata,theclassifierissimpleanddirect,anditdoesnotrevealtheprivately-helddata.Forhorizontallypartitioneddata,bysecuremulti-partycomputationtechnique,theproposedSVMclassifierispublicbutdoesnotrevealtheprivately-helddata.WeprovethefeasibilityofouralgorithmsbyusingmatrixfactorizationtheoryandOurPPSVMalgorithmshaveaccuracycomparabletothatofanordinarySVMclassifierbasedontheoriginaldata.Numericalexperimentsshowthesecuritywithoutusingthesecuremulti-partycomputation.InChapter6,byakindofsecuritytechniqueforsovingthemultiplicationoftwomatricesinchapter5,weputforwardanovelprivacy-preservingsupportvectormachine(SVM)classifieronarbitrarypartitioneddata.TheproposedSVMclassifier,whichispublicbutdoesnotrevealtheprivately-helddata,hasaccuracycomparabletothatofanordinarySVMclassifierbasedontheoriginaldata.Weprovethefeasibilityofouralgorithmsbyusingmatrixfactorizationtheoryandshowthesecuritybyusingthesecuremulti-partycomputation.Keywords:DataMining,MachineLearning,SupportVectorMachine,DecompositionAlgorithm,SecureMulti-PartyComputation,PrivacyPreservingSupportVectorMachine 山东科技大学博士学位论文目录目录1绪论····················································································································11.1课题的提出··············································································································11.2支持向量机的模型和算法概述··············································································31.3支持向量机的分解算法概述··················································································81.4隐私保护支持向量机算法概述············································································101.5本文主要工作概述································································································162支持向量机简化算法中支持向量与违背对的几何意义····························182.1引言·······················································································································182.2支持向量及其与相应乘子之间的关系·································································202.3求解SVM的简化算法中终止条件的分析研究····················································232.4本章小结················································································································283大规模支持向量机的一类新的收敛的分解算法········································303.1引言·······················································································································303.2基本符号和预备知识····························································································323.3几种工作集选择方法的比较················································································353.4带有q个非零分量的稀疏可行方向集·································································443.5Wolfe线搜索算法··································································································483.6基于可行方向选择的新的分解算法·····································································503.7收敛性分析············································································································523.8数值实验················································································································543.9本章小结················································································································554不带安全多方计算的数据垂直划分的隐私保护支持向量机算法···········564.1引言·······················································································································564.2预备知识················································································································584.3垂直划分数据的不带多方安全计算的隐私保护线性和非线性分类器··············594.4数值实验················································································································63 山东科技大学博士学位论文目录4.5本章小结················································································································645带有安全多方计算的数据水平划分的隐私保护支持向量机算法···········665.1引言·······················································································································665.2安全多方计算的加密技术概述············································································685.3数据水平划分的隐私保护支持向量机算法·························································695.4数值实验················································································································745.5本章小结················································································································766针对任意分割数据的隐私保护支持向量机算法········································776.1引言·······················································································································776.2数据任意划分的线性隐私保护支持向量机算法·················································786.3数据任意划分的非线性隐私保护支持向量机算法·············································836.4数值实验················································································································846.5本章小结················································································································857总结和展望·····································································································867.1本文的特色和创新点····························································································867.2展望·······················································································································87致谢····················································································································89参考文献················································································································90攻读博士期间主要成果·····················································································101 山东科技大学博士学位论文ContentsContents1Introduction………………………………………………………………………………11.1RaisingofProject…………………………………………………………………………………11.2OverviewforModelandAlgorithmofSupportVectorMachines…………………………………31.3SecureMulti-partyComputationTechnique……………………………………………………81.4PresentConditionofDomesticandInternationalResearch………………………………………101.5MainWorkSummaryoftheThesis………………………………………………………………162GeometricalMeaningonSupportVectorsandViolatingPairsfortheSimplifiedalgorithmsofSVM……………………………………………………………………………………………………182.1Introduction…………………………………………………………………………………………182.2RelationbetweenSupportVectorsandtheCorrespondingMultiplier……………………………202.3AnalysisofTerminatingConditionofSimplifiedAlgorithmforSolvingSVM…………………232.4Conclusion…………………………………………………………………………………………283AnewConvergentDecompositionAlgorithmforSolvingLargeScaleSupportVectorMachines……………………………………………………………………………………………303.1Introduction………………………………………………………………………………………303.2NotationandPreliminaryResults………………………………………………………………323.3Severalmethods’comparisonofworkingsetselection……………………………………………353.4SetsofqcomponentsofSparseFeasibleDirections……………………………………………443.5Wolfe-TypeLineSearchAlgorithm………………………………………………………………483.6NewDecompositionAlgorithmBasedonFeasibleDirectionSelection…………………………503.7ConvergenceAnalysis……………………………………………………………………………523.8NumericalExperiments…………………………………………………………………………543.9Conclusion…………………………………………………………………………………………554Privacy-PreservingSVMClassificationonVerticallyPartitionedDatawithoutSecureMulti-PartyComputation………………………………………………………………564.1Introduction………………………………………………………………………………………56 山东科技大学博士学位论文Contents4.2SVMOverview……………………………………………………………………………………584.3Privacy-PreservingLinearandNonlinearClassifierforVerticallyPartitionedDatawithoutSecureMulti-PartyComputation…………………………………………………………………………594.4NumetricalResults………………………………………………………………………………634.5Conclusion…………………………………………………………………………………………645Privacy-PreservingSVMClassificationonHorizontallyPartitionedDatawithSecureMulti-PartyComputation………………………………………………………………665.1Introduction………………………………………………………………………………………665.2SVMOverview……………………………………………………………………………………685.3Privacy-PreservingClassifierforHorizontallyPartitionedDatawithSecureMulti-PartyComputation………………………………………………………………………………………695.4NumericalResults…………………………………………………………………………………745.5Conclusion…………………………………………………………………………………………756Privacy-PreservingSVMClassificationonArbitraryPartitionedData……………776.1Introduction………………………………………………………………………………………776.2Privacy-PreservingLinearClassifierforArbitraryPartitionedData………………………………786.3Privacy-PreservingNonlinearClassifierforArbitraryPartitionedData…………………………836.4NumericalResults…………………………………………………………………………………846.5Conclusion…………………………………………………………………………………………857MainResearchResultandConclusion……………………………………………867.1MainResearchResult…………………………………………………………………………867.2MainConclusion………………………………………………………………………………87Acknowledgements…………………………………………………………………………89MainReferenceDocuments………………………………………………………………90MainWorkAchievementoftheAuthorduringWorkingonDoctorPaper……………101 山东科技大学博士学位论文1绪论1绪论“机器学习”是人工智能的核心研究领域之一，其最初的研究动机是让计算机系统具有人的学习能力以便实现人工智能，基于数据的机器学习是现代智能技术中的重要方面，研究从观测数据（样本）出发寻找规律，并利用这些规律对未来数据或无法观测的数据进行预测.基于数据的机器学习就其实现方法可大致分为三种：第一种是经典的（参数）统计估计方法.第二种是经验非线性方法，如人工神经网络.第三种方法是统计学习理论（StatisticalLearningTheory,SLT）.由于机器学习需要设法对数据进行分析，这就使得它逐渐成为智能数据分析技术的创新源之一，并且为此而受到越来越多的关注.“数据挖掘”和“知识发现”通常被相提并论，在许多场合被认为是可以相互替代的术语.近年来，随着数据库技术的不断发展及数据量急剧增大，如何在大量的数据背后挖掘出那些有用的信息和知识，并将其从数据库中抽取出来为管理部门辅助决策具有非常重要的意义.数据挖掘就是从大量的、不完全的、有噪声的、模糊的、随机的数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程.大体上来说，数据挖掘可以视为机器学习和数据库的交叉，它主要利用机器学习提供的技术来分析海量数据，利用数据库提供的技术来管理海量数据.数据挖掘受到了很多学科领域的影响，其中数据库、机器学习、统计学对数据挖掘的影响最大.粗糙地说，数据库提供数据管理技术，机器学习和统计学提供数据分析技术，而通常情况下，统计学提供的很多技术要在机器学习领域进行进一步的研究，得到有效的机器学习算法之后才能进入数据挖掘领域.从这个意义上说，统计学主要是通过机器学习来对数据挖掘发挥影响，而机器学习和数据库则是数据挖掘的两大支撑技术.1.1课题的提出分类问题和回归问题都不是新问题，但是随着计算机的普及和广泛的应用，特别是机器学习和数据挖掘的迅速发展赋予了它们新的意义，目前这些问题再次引起人们的热切关注.传统的统计学研究的是当样本数目趋于无穷大时的渐进理论，但在实际问题中，样本的数目往往是有限的，因此一些理论上很优秀的学习方法实际中却可能不尽人意.1 山东科技大学博士学位论文1绪论与传统统计学相比，统计学习理论是一种专门研究小样本情况下机器学习规律的理论，该理论针对小样本统计问题建立了一套新的理论体系，在这种体系下的统计推理规则不仅考虑了对渐进性的要求，而且追求在现有有限信息的条件下得到最优结果.V.[1]Vapnik等人从二十世纪六、七十年代开始致力于统计学习理论方面的研究，到九十年代中期，随着该理论的不断发展和成熟，也由于神经网络等学习方法在理论上缺乏实质性进展，统计学习理论开始受到越来越广泛的重视.同时，在这一理论的基础上发展了[2]-[7]一种新的通用学习方法，即支持向量机(SupportVectorMachine或SVM),与其它机器学习算法仅仅考虑到经验风险最小化(EmpiricalRiskMinimization,ERM)的原则不同,支持向量机是一种通用的学习机器,是数据挖掘中的一项新技术，是借助于最优化方法[99]解决机器学习问题的新工具.它较好地实现了结构风险最小化思想.从理论上来说,由于采用了二次规划寻优,因而可以得到全局最优解,解决了在神经网络中无法避免的局部极小问题.由于采用了核函数,巧妙地解决了维数问题,使得算法复杂度与样本维数无关,非常适合处理非线性问题.另外,支持向量机应用了结构风险最小化原则,因而支持向量机具有非常好的推广能力.这样，支持向量机就在很大程度上克服了神经网络等传统机器学习方法学习过程中的过学习(Overfitting)、非线性(Nonlinear)、维数灾难(CurseofDimensionality)以及解的局部极小等问题,有很强的非线性处理能力和良好的泛化性能(GeneralizationPerformance).在模式识别方面,最突出的应用研究是贝尔实验室对美国邮政手写数字库进行的实验,这个实验人工平均错误率是2.5%,用决策树方法识别错误率是16.2%,两层神经网络中错误率最小的是5.9%,而用三种支持向量机方法得到的错误率分别为4.0%,4.1%和4.2%,优于决策树和神经网络方法.在人脸检测与识别领域,MIT用支持向量机进行的人脸检测实验也取得了很好的效果,可以较好地学会在图象中找出可能的人脸位置.此外，支持向量机还广泛用于图像处理,在图像分割,图像检测,图像分析,遥感图像分析,语音识别,文本分类,三维物体识别等方面也有较多的应用研究成果.在医学研究领域,支持向量机主要被用于通过基因数据对基因进行分类,对人类基因的表示数据进行分析,确定基因的功能,对蛋白结构类别进行预测等.与此同时,支持向量机在工业领域的应用研究也逐渐受到研究者的重视,支持向量机在信号处理领域,金融领域等都已初步显示出强大的优势.目前，支持向量机已成为二十世纪末二十一世纪初发展最快的研究方向之一.尽管支持向量机在国内的研究滞后于国外,但近年来发展较快.国内的研究人员基2 山东科技大学博士学位论文1绪论于学习机器要与有限的训练样本相适应的核心思想，开展了许多有效的研究工作,取得了一系列优秀的成果，但其中还有许多问题尚未解决.因此，对SVM的理论与应用进行研究具有重要的理论意义与应用前景.作为目前机器学习领域内的焦点之一，自支持向量机(SVM)出现以来，有关它的研[2,7,8-26,30-40]究成果就不断涌现.由于SVM算法的潜在应用价值，吸引了国际上众多的知名学者，近几年出现了许多发展和改进的支持向量机算法.目前，关于支持向量机学习算法的研究方兴未艾，它是支持向量机理论的研究重点和难点内容之一.隐私保护支持向量机算法是2006年之后新兴起来的一个研究方向，基于隐私保护数据挖掘技术的发展，基于人们对个人隐私信息迫切需要保护的要求，该研究方向已经成为机器学习领域非常重要的研究方向之一.本文重点讨论简化分解算法和隐私保护支持向量机算法，为此本章的剩余部分将对这两方面学习算法的研究现状和最新进展进行较为详细深入的阐述，作为本论文的研究背景和工作基础.1.2支持向量机的模型和算法概述1.2.1支持向量机的基本概念和一般模型支持向量机的训练算法实质上是求解一个凸二次规划(ConvexQuadraticProgramming,简称CQP),这需要计算和存储核矩阵函数,其大小与训练样本数的平方[80,85-93]相关,随着样本数目的增多,所需要的内存增加.最优化理论中的许多成熟算法，例如牛顿法、共轭梯度法及内点法需要利用整个Hessian矩阵，所以受计算机内存容量的限制，只适用于样本较少的问题，因此设计适用于大量样本的算法成为SVM研究中的重要内容.我们都知道，支持向量机的核心思想是引入核函数的概念，把学习样本映射到一个高维空间中，在高维空间中建立与空间维数无关的最优分类超平面，从而解决非线性分类或回归学习问题.我们讨论的分类问题基本分为线性可分问题、近似线性可分问题和实质线性不可分问题(即线性不可分问题).例如，图1.1所示的问题，很容易用一条直线把训练集正确地分开(即两类点分别在直线的两侧，没有错分点)，这类问题称为线性可分问题.而图1.2所示的训练集不能用直线把这两类样本点正确划分开，需要借助曲线进行分类，称为非线性可分问题.3 山东科技大学博士学位论文1绪论10.9L0.8W0.70.60.50.40.30.20.1000.20.40.60.81图1.1线性分类支持向量机的几何含义Fig1.1Geometricalmeaningoflinearseperablesupportvectormachine图1.2非线性分类支持向量机的几何含义Fig1.2Geometricalmeaningofnonlinearseperablesupportvectormachine在机器学习问题中，我们要从数据中发现一些规律或知识，这常常需要考虑数据中的相似性.例如，在分类问题中，设包含l个样本的训练集为(,),1,2,,xyi=?l,输入向iin量x∈χ=R,对应的期望输出为y∈{1,1}+−=，il1,2,,?,其中+1和-1分别代表两类的类ii别标识,n为输入维数.学习的目标就是构造一个决策函数,将测试数据尽可能正确分4 山东科技大学博士学位论文1绪论类，从而推断任一模式x相对应的y值.解决这类问题的一个直观想法是,判断一下新的输入x是与正类的那些输入相似,还是与负类的那些输入相似,并由此推断出x的归属.那么，如图1.1所示，如何选取分划直线L的法方向w呢？我们知道，对于适当给定的法方向，会有两条极端的直线，我们称这两条直线之间的距离为与该法方向相应的“间隔”，可以想象，我们应该选取使“间隔”最大的那个法方向.基于上述最大间隔的思想，建立其相应的数学模型，可得其原始问题的一般描述为:l1Tmin2wwC+∑ξiwb,,ξi=1Tst..ywxii(⋅+≥−b)1ξi(1.1)ξ≥=0,il1,2,?,i其中,C为惩罚参数,C越大表示对错误分类的惩罚越大,是算法中唯一可以调节的参数.对于线性不可分问题，其主要思想是通过一个非线性变换φ()x，将其映射到一个高维空间中,使得问题在高维空间中线性可分,并且在高维空间中只需进行内积运算,即将原来线性的内积(,)xx变成了((),())φxφx，甚至不需要知道采用的非线性变换的形式,ijij所以避免了高维变化计算问题,使问题大大简化.根据Hilbert-Schmidt原理,只要一种运算满足Mercer条件,就可以作为内积函数(或称为核函数)使用.目前常用的内积函数主要有:(1)多项式内积函数(核函数):qKxy(,)[(=xy⋅+)1](2)径向基内积函数(核函数，即RadiusBasisFunction,简记为RBF):2⎧||x−y⎫Kxy(,)exp=−⎨⎬2⎩⎭2σ(3)Sigmoid内积函数(核函数)：Kxy(,)tanh{(=vxyc⋅+)}对于不同的分类问题，可以选择不同的核函数,不过目前还没有一个针对特定问题选择最佳核函数的有效方法.在给出Mercer核定义之前，我们先给出Gram矩阵的概念，这是因为在核矩阵的构造算法中,其关键就是Gram矩阵的计算.5 山东科技大学博士学位论文1绪论[32]定义1.2.1对于给定的函数KR:χ×χ→和xx,,,?x∈χ，则称第i行第j列元12l素为KK=(,)xx的ll×矩阵K为函数K的关于x,,,xx?的Gram矩阵.ijijll×12l[32]TT定义1.2.2称Kxx(,)是Mercer核，如果Kxx(,)是χ×χ上的连续对称函数，χnT是R上的紧集，且Kxx(,)关于任意的xx,,,?x∈χ的Gram矩阵半正定.12lT在本文后面的章节中，涉及到的核函数均指Mercer核函数，记作Kxx(,)，Kxx(,)ijT或者KAA(,)，简称核.为求解支持向量机的原始问题(1.1),采用Lagrange乘子法,由于式(1.1)是具有线性约束的二次规划问题,故很容易写出其对偶问题为:1TTminαααQe−2αs..0tC≤≤=αi,il1,2,,?(1.2)Tyα=0其中e是单位向量,C>0是上界,Q是ll×正半定矩阵,且Qy=yxx(,)，如果为非线ijijij性分类问题，则Qy=yKxx(,)，其中Kxx(,)为核函数.ijijijij用于分类问题的支持向量机算法可描述为:n步骤1设已知训练样本集{(,),xyi=1,2,,?l},期望输出y∈{1,1}+−,x∈R;iiiiT步骤2选择核函数Kxx(,)和惩罚参数C,构造并求解最优化问题lllmin1∑∑∑yyαααKxx(,)−2ijijijjαii==11j=1lst..∑yiiα=0(1.3)i=10,≤≤=αCi1,2,?,li****得最优解α=(,,,)αα?α;12ll****步骤3选择α一个小于C的正分量αj,并据此计算by=−ji∑yKxxαi(,)ij;i=1l**步骤4求决策函数f()xy=+sgn(∑iiαK(,)xixb).i=16 山东科技大学博士学位论文1绪论由支持向量机的一般数学模型可以看出，支持向量机就是首先通过内积函数定义的非线性变换将输入空间变换到一个高维空间,再在这个高维空间中(广义)求最优分类面.最后，将输入样本x进行相同的非线性变换，并根据f()x的符号来确定其归属.1.2.2求解支持向量机的算法概述由于SVM的训练其本质就是求解一个凸二次规划问题,因此，最优化理论中的许多成熟算法,如牛顿法、共轭梯度法、内点法等都可以用于求解SVM.但是这些算法在求解时需要利用整个Hessian矩阵信息,对于海量数据的处理,即对大规模数据集的分类问题，受普通计算机内存容量和计算时间的限制,这些算法的求解效率很低,因此不再适用.于是，设计适用大规模问题的SVM算法就成为一个重要的研究方向.一些学者针对SVM自身的特点及不同的问题和不同的要求，提出了多种快速学习算法.如简化分解算法[26,46-52][15,16][13]、最小二乘支持向量机算法、并行学习支持向量机算法、增量学习支持向[11,12,14]量机算法等等.目前,这些算法在理论和实践上都取得了一定的进展,并出现了一些比较有效的训练算法的相关软件.另外，对于支持向量机模型本身，许多学者也进行了大量研究，如Anthony等人给[29]出了关于硬间隔支持向量机学习误差的严格理论界限;Shawe-Taylor等人给出了类似[1]的关于软间隔支持向量机核回归情况下的误差界限;Vapnik等研究了支持向量机的推广性能及其在多值分类和回归问题中的扩展问题.随着支持向量机在理论上的深入研究,出现了许多变种支持向量机.Vapnik提出的可[6,27,28]调参数C的SVM统称为C-SVM系列.Schölkopf提出的用于分类和回归的ν-SVM,引入反映超出ε管道的样本数据点个数(即边界支持向量数量)和支持向量数的新参数ν,从而简化SVM的参数调节.另外,一些学者还扩展了支持向量机概念,如Mangasarian等[8]人引入的通用支持向量机(GeneralizedSVMs).由于在某些情况下，每个样本并不是完全能够划归到某一类,即样本与类别之间存在着某种模糊的隶属关系,由此,Takuya和[39,40]Lin等人提出了一种模糊支持向量机,通过给样本增加一个模糊隶属关系,来充分利[15,16]用样本的信息.1999年,Suykens提出了一种最小二乘支持向量机(LeastSquaresSVM,LS-SVM).通过引入最小二乘线性系统到支持向量机中,用以代替传统的支持向量机中采用二次规划方法解决函数估计的问题.在此基础上提出的周期最小二乘支持向量机已用于时间序列的预测.后来又有学者提出加权支持向量机用来克服普通支持向量机不能根据每个采样点数据的重要性区别对待的缺陷,同时还可以解决类别补偿问题.7 山东科技大学博士学位论文1绪论One-classSVM算法解决的是只有正训练样本一个类别的分类问题.内积矩阵分解算法是在已经得到了支持向量集S后,通过变换去掉其中的n个支持向量,以减少支持向量的数目来提高分类器的分类速度.这n个支持向量并不是简单的舍弃,因为在变换中,变换矩阵保留了所有支持向量的信息,所以分类器的精度并不会下降.基于KKT条件的[11,12,14]增量学习算法是根据样本是否违反KKT条件来选择并积累支持向量,其中还考虑了普通样本和支持向量之间可能存在的相互转化的问题.所以新增样本中只有那些违反KKT条件的样本对支持向量机的可累积性学习起作用.此外，还有光滑支持向量机[24][20,22,23,25](SmoothSVM,SSVM)模型,简化支持向量机(ReducedSVM,RSVM)模型,小波支持向量机(WaveletSVM)模型,Lagrangian支持向量机模型(LSVM),多类分类支持[15,16,17,18,33-38]][39,40]向量机(Multi-classSVM,Mc-SVM)模型、模糊支持向量机、半监督支[135,136]持向量机以及其它一些新的支持向量机模型等等.1.3支持向量机的分解算法概述支持向量机能够充分描述整个训练样本集的特征,对部分支持向量的划分等价于对整个样本集的划分.大多数情况下,支持向量只占训练样本集的很少一部分,而支持向量的数量是影响最终分类速度的主要因素，所以减少分类函数中支持向量的数量成为研究支持向量机快速分类算法的目标.因此，许多研究者通过寻找一个包含较少支持向量的约简向量集代替原有的支持向量集，从而达到简化分类函数，提高分类速度的目的.[44]Downs削减了那些在特征空间中能被其它支持向量线性表示的冗余支持向量，削减完毕后剩余的支持向量即为所求的约简向量，然后修改约简向量所对应的Lagrange乘子使[45]SVM判定函数保持不变.Baudat通过空间映射的方法来减少支持向量，该方法首先从训练样本中寻找支持向量，然后将支持向量映射到特征向量集所构造的子空间来削减冗[46]余支持向量.刘通过优化的方法适当变换特征空间中的内积矩阵，并进一步变换分类函数的形式，来减小分类函数中支持向量的数量，提高分类精度.以上文献所提的方法都是在保留全部支持向量信息的情况下削减支持向量，因此能够在不损失分类精度的前提下简化分类函数，提高分类速度.和上述方法通过削减原始支持向量的数量来简化分类函数不同的是，部分研究者采用迭代构建新的向量作为约简向量的方法来简化分类函数.虽然此类简化法导致一定程度的分类精度损失，但是取得了较大的支持向量约简率，极大地加快了SVM的分类速度，广泛被采用.8 山东科技大学博士学位论文1绪论分解方法的基本思路来源于Vapnik首先提出的分块(Chunking)算法,分块算法基于这样一个事实,即去掉Lagrange乘子等于零的训练样本不会影响原问题的解.对于给定的训练样本集,如果其中的支持向量是己知的，训练算法就可以排除非支持向量只需对支持向量计算Lagrange乘子即可.该方法每次求解一子QP问题，得到若干支持向量，用这些支持向量和一些不满足优化条件的样本，构成新的子QP问题，而初始子QP问题由任意若干个样本构成，重复上述过程直到所有样本满足优化条件.分块算法大大减少了矩阵的模，当支持向量的数目远远小于训练样本数目时，分块算法显然能够大大提高运算速度，然而如果支持向量的数目本身就比较多，子QP问题所对应的Hessian矩阵也会很大，因此分块算法不适用于支持向量较多的情况.[47]针对分块算法的缺点，osuna提出分解算法来加快SVM的训练速度.分解算法将训练样本分为两个集合，工作集B和非工作集N.|B|和|N|的大小都是不变的.在每次迭代中，首先确定B，然后求解关于B的子QP问题，而保持N中样本所对应的Lagrange乘子不变.即使支持向量的个数超过工作集的大小也不改变工作集的规模，而只对支持向量中的一部分进行优化.这种算法的关键在于选择一种合适的工作集换入换出策略即工作集的确定方法.Joachims在上述分解算法的基础上做出了几点重要改进.第一，采用类似zoutendijkd可行方向法的策略确定工作集B，即求解一线性规划问题，得到可行下降方向，把该方向中的非零分量作为本次迭代的工作集.由于q被限定为偶数，该线性规划存在高效算法，其核心是一个排序问题.第二，提出shrinking方法，估计出有界支持向量和非支持向量，有效地减小QP问题的规模.最后，利用缓存(KernelCache)来减light少赫塞矩阵中元素的计算次数.Joachims利用这些方法实现的SVM是目前设计svm分[70]类器的重要软件.Laskov提出另一种工作集确定方法，最大不一致(maximalinconsisteney)算法，并进一步指出，对于二分类问题，这个算法等价于Joachims的可行方向策略.在分解算法的基础上，Platt提出了更为高效的序贯最小优化算法(sequential[49]minimaloptimization，简称SMO).该算法可以说是分解算法的一个极端特例，它在每次迭代中固定||2B=，由于只有两个变量，应用等式约束可以将其中一个用另一个表示出来，所以迭代过程中每一QP子问题的最优解可以通过解析方法求出，避免了复杂的数值求解优化问题的过程.此外，Platt采用启发式的方法来确定工作集，通过一个两层嵌套循环分别选择进入工作集的两个样本：外层循环在某个乘子集合中遍历，将第一个不满足优化条件的乘子作为第一个被优化对象，第一次遍历全部乘子，以后遍历非有界9 山东科技大学博士学位论文1绪论乘子，如果所有非有界乘子都满足优化条件，则再次遍历全部乘子.一旦找到第一个乘子，内层循环寻找第二个乘子，使其在当前迭代步中具有最大的改变量.完成一次优化再循环进行下一次优化，直到全部样本都满足最优条件为止.这种启发式策略大大加快Light[51]了算法的收敛速度，随后的SMO算法借鉴了SVM算法.Keerthi等人给出一个双阈值优化条件，并提出两种利用该条件确定工作集的方法，实验表明，两种方法，特别是方法二，可以大大减少核函数的计算次数，提高SMO的效率.在Joachims和Keerthi研[57,58]究工作的基础上，Chang和Lin提出了基于可行方向策略的SMO算法，该方法每次选取两个最违反优化条件的样本点进入工作集，并且也引入了shrinking与缓存机制.相对于其它训练算法，采用可行方向策略的SMO算法具有较快的训练速度，并且能够确保收敛，因此称为标准的SMO训练算法.Light经过几年的发展，综合借鉴其它方法，特别是SVM和SMO的优点，引入有效的核缓存(KernelCache)和Shrinking方法，特别由于Lin等对终止迭代条件进行了分析、对分解算法的收敛性进行了证明，使得分解算法已经成为当前最常使用的SVM分类器训练方法，并且已经推广到SVM回归等领域.1.4隐私保护支持向量机算法概述1.4.1安全多方计算[41,42,43,117-119]安全多方计算(securemulti-partycomputation)是分布式密码学的理论基础，也是分布式计算研究的一个基本问题.它蕴含了密码学中任何协议问题在原则上的实[42]现方案.最早，A.Yao于1982年通过姚氏百万富翁问题提出了安全两方计算问题.姚氏百万富翁问题是指两个争强好胜的百万富翁Alice和Bob在街头相遇，如何在不暴露各[43]自财富的前提下比较出谁更富有？5年后，Goldreich,Micali和Wigderson于1987年提出了可以计算任意函数的安全多方计算协议.到上世纪90年代，安全多方计算的研究已经非常活跃.具体地说，安全多方计算是考虑如下的问题.设EEEE={,,,}?是n个参与者集12n合，他们想要“安全地”计算某个给定的n个输入和n个输出的函数f(,,,)(,,,)xx??x=yyy，其中这个函数的n个输入是分别由这n个参与者秘密掌握12nn12的，设E的秘密输入是x，并且在计算结束后，E得到输出y.这里的安全性是要求即iiii使在某些参与者有欺骗行为的情况下，仍然能保证计算结果的正确性，即计算结束后每10 山东科技大学博士学位论文1绪论个诚实的参与者E都能得到正确的输出y，同时还要求保证每个参与者输入的保密性，ii即每个参与者E除了知道(,)xy以及从中推出的信息之外，得不到任何其它的信息.这iii样如何构造满足安全性的算法是一个关键问题.不难看出，如果我们能安全地计算函数x+x和xx，则我们可以安全地计算任何布尔函数或多项式函数.1212例如，我们考虑一个两方计算：EEE={,}，需要计算的函数为f:(,)xx→(,)yy，121212其中y==yxx.参与者E的秘密输入是x，参与者E的秘密输入是x.为计算f，12121122当然最简单的办法就是参与方E和E都公开自己的输入，于是他们都能够计算出正确的12输出.这样做尽管可以保证计算结果的正确性，但无法保证每个参与者输入的保密性.因此，为了保证输入的保密性，x和x就不能直接公开，要通过一些随机数将他们隐藏起12来再输入.通过设计适当的算法，使得每个参与者最后在得到正确输出的同时，各自输入的保密性也得到保证.简单地说，参与方E和E要安全计算f，可通过下面的示意图123所示来计算.f(x1,x2)+r2x1+r1=X1E1E2f((x1+r1),x2)+r2=X2f(x1,x2)图1.3安全两方计算示意图Fig1.3.SecureTwo-PartyComputation第一轮：E传给E消息X，其中X包括x的信息和一些随机数；12111第二轮：E传给E消息X，其中X包括X,x的信息和一些随机数；212212……最后一轮，假设是第k轮，E传给E消息X(或者E传给E消息X)，即为最后的12k21k输出.11 山东科技大学博士学位论文1绪论这样，E可以根据在交互过程中得到的信息计算并得到y，i=1,2.这里的正确性ii是指y==yfxx(,).保密性是指E得到的信息不会比(,)xy以及由此推出的信息更1212iii多，i=1,2.也就是说，如果x=0，则E得到(,)xy和y的值，但对E的输入一无所111122知；如果x=1，则E除了知道(,)xy和y的值以外，还能推出E的输入x，除此之外，1111222E一无所知.对于E，情况完全相同.需要指出，E得到由(,)xy推出的信息是安全性12iii要求所允许的,从直观上看,这也是合理的.需要注意的是，由于安全性是针对具体的攻击者而言的，并不是任何安全性要求(即针对任何的攻击者)都有算法实现.因此首先应对安全性要求进行具体刻画，而后设计满足这个安全性要求的算法.如果所有参与者都是诚实的，即在计算过程中，每个人严格按照协议执行并且不会蓄意窃取其它信息，那么平凡地满足安全性要求.相反，如果所有人都是不诚实的，那么讨论安全多方计算就没什么意义.在两方计算中，如果只有一人不诚实，在计算过程中严格执行协议但蓄意窃取其它信息(即被动攻击)，则存在满足这种安全性要求算法，在其它情况下都不存在安全的两方计算协议.对于解决某个具体密码学问题的协议，我们说它是安全的，传统的做法是列表验证该协议是否具有我们所希望具备的特点.例如，我们设计了一个对称加密算法，希望说明它是安全的，为此可以列一张表记录它所应该具有的性质或它应抵抗的已知攻击，比如这张表应该包括该算法能够抵抗差分攻击，线性攻击等性质.然后，我们去验证该算法是否满足这张表列出的各种性质.如果是，则称它满足安全性要求，否则称它不满足安全性要求.这样做的好处是简单，便于操作，缺点是无法确定这张表是否是完备的，或者说无法确定这张表是否已经包含了所有可能的安全性要求.在处理安全多方计算时，则采取完全不同的途径.首先构造一个理想方案，它蕴涵了我们所希望的安全性要求，然后把要证明安全的协议，称为现实方案，与理想方案比较，如果在某种意义下比不出差别来，就证明了我们设计的现实协议与理想方案在这种意义下具有相同的安全性.目前安全多方计算已得到许多学者的研究，其在密码学上的地位也日益重要，现有的许多密码工具都是安全多方计算的基础，SMC的关键技术涉及到秘密分享与可验证秘密分享、门限密码学、零知识证明、茫然传输、茫然多项式估值、百万富翁协议等多方面的内容，协议中应用的基本密码算法包括各种公钥密码体制，特别是语义安全的同态公钥加密系统.在不同的计算领域中，SMC问题的安全需求不相同，应针对具体SMC12 山东科技大学博士学位论文1绪论应用环境进行安全性定义，寻找高效的SMC解决方法.在SMC应用研究方面，寻找特殊领域的SMC问题及其解决方案是值得深入研究的方向，如分布式生成RSA密钥、多方合作签名、自安全的无线Ad-hoc网络等.随着电子商务的兴起，电子拍卖、电子选举、私有信息检索成为SMC研究的又一热点.此外，SMC在保护隐私的科学计算，保护隐私的统计分析、保护隐私的几何计算、保护隐私的数据库查询、保护隐私的数据挖掘、保护隐私的入侵检测等方面的课题，都值得做进一步深入的研究.1.4.2隐私保护支持向量机算法“隐私权”最早在1890年12月美国人沃伦和布兰代斯所写的《隐私权》中被正式定义.“隐私权”界定为“生活的权利”和“不受干扰”的权利.他们认为，隐私权本质上是一种个人对其自身事务是否公开给他人的权利，保护个人的隐私权就是保障个人的“思想、情绪及感受”不受他人打扰的权利，保护自己人格不受侵犯的权利.随着越来越多的信息可以电子形式或从网上得到，人们对自己隐私的保密要求变得越来越迫切.在这种情况下，如何在保证个人隐私的前提下进行数据挖掘、数据分类等成了一个亟需解决的问题.另外，在双方或多方合作进行数据挖掘的时候，由于某种原因，参与方往往不愿意将数据与他人共享而只愿意共享数据挖掘的结果.这种情况在科学研究、医学研究及经济和市场动态研究方面常常遇到.因此，如何保护私有信息或敏感信息在挖掘过程中不被泄露，就成为数据挖掘、支持向量机算法研究中的一个很有意义的研究课题.隐私保护数据挖掘或隐私保护支持向量机的主要目的就是用某种技术改进已有的原始数据，利用修改后的数据进行数据挖掘或数据分类，保持数据挖掘结果或分类的正确性，同时使得敏感的数据和知识不被泄露.根据数据的分布情况，隐私保护技术可以分为针对集中式数据的隐私保护技术和分布式数据的隐私保护技术.分布式数据的隐私保护技术又分为数据水平分割的隐私保护技术和数据垂直分割的隐私保护技术.数据的水平分割主要原因是多个机构或组织对于不同的个体收集了相似的信息；数据的垂直分割主要原因是多个机构或组织收集了同样的个体的不同信息.隐私保护技术从整体上分为三类，分别为面向单个数据记录、面向集中式数据、面向分布式数据的隐私保护技术.13 山东科技大学博士学位论文1绪论表1.1针对不同数据类型的隐私保护技术Table1.1Privacypreservingtechniquefordifferenttypeofdata数据分布方式隐私保护技术随机响应技术、基于阻塞的技术、单个数单个数据记录据交换和属性变换技术集中式数据启发式技术和重建式技术水平分割的数据基于密码学的隐私保护技术，包括安全多分布式数据垂直分割的数据方计算等等任意分割的数据面向单个数据记录的隐私保护技术主要包括随机响应技术、基于阻塞的技术、单个数据交换和属性变换技术等等，其主要特征是为了实现单个数据的隐私保护，对数据进[119]行分别处理，使其它参与方无法得知有关单个数据记录的准确信息.WenliangDu提出了基于随机响应技术的隐私保护分类算法.在统计某个特征的分布概率时，利用问题的随机性保护被调查者的隐私，同时又得到准确的分布概率.面向集中式数据的隐私保护技术适用的情况是，数据挖掘的目标针对数据的集合特征，而非单个数据信息.其具体方法是收集数据时对单个记录加入随机变量实现干扰，其后对带有干扰的数据利用重构技术重建原始数据特征，再对其进行挖掘和分析.针对集中式数据的隐私保护技术主要包括启发式技术和重建式技术.启发式技术通过仅修改特定值，而非全部值来减少数据挖掘效果的失真.重建式技术主要分为数值型数据的重[103]构技术以及二进制数据与分类数据的重构技术.2000年，R.Agrawal提出了用离散化的方法与值变形的方法修改原始数据，然后用重构算法构造原始数据的分布.该算法通过加随机偏移量的方法对原始数据进行变换，然后利用贝叶斯公式来推导原始数据的密度函数以重构判定树.14 山东科技大学博士学位论文1绪论面对分布式数据的隐私保护技术大多数是基于密码学的隐私保护技术.特别在分布式环境下的隐私保护问题，安全多方计算(SMC)是最为常用的一个协议.正如1.4.1部分所介绍的，安全多方计算是在一个互不信任的多用户网络中，各用户能够通过网络来协同完成可靠的计算任务，同时又能保持各自数据的安全性.在多方分类挖掘方面，[106,107]WenliangDu利用安全数量积技术提出了垂直分布数据的安全分类算法，而Lindell首次提出了使用加密方法建立水平分布数据的决策树，将对最佳分类属性的寻找转化为安全多方计算问题.从1999年RkaeshAgrawal在数据库和数据挖掘的知识发现国际会议上(ConferenceonKnowledgeDiscoveryinDatabasesandDataMining,简称KDD99)上作了一场精彩的主题演讲后，隐私保护数据挖掘便迅速地发展起来，各种新的方法不断涌现.与此同时，作为数据挖掘中非常重要的一种新方法-隐私保护支持向量机的研究也得到了学术界的[120,123-129]重视，国内外很多学者致力于隐私保护支持向量机算法的研究.目前隐私保护支持向量机算法的研究主要针对分布式数据.[123]对于水平分布的数据，HwanjoYu于2006年对水平分布的布尔数据提出了一种隐私保护支持向量机(PPSVM)，将向量问题转换为集合问题来处理，引入hash函数计算集合交的势，进而得到核函数，在得到核函数的时候没有揭露原始数据，最后利用所得到[128]的核函数的数据建立了隐私保护支持向量机.2007年，OlviL.Mangasarian等将简约支持向量机(RSVM)引入数据水平分布的隐私保护支持向量机，每个实体生成相同的随机矩阵后，分别求得自己的核矩阵，将所有实体的核矩阵组合后得到整体数据的简约核矩阵，继而得到水平分布数据的隐私保护支持向量机.[124]对于垂直分布分布的数据，HwanjoYu于2006年对垂直分布的数据提出了一种隐私保护支持向量机(PPSVM)，利用密码学中的安全多方计算技术，通过分别求解各个实体的Gram矩阵，得到整体数据的Gram矩阵，进而在不揭露原始数据的情况下得到整体数据的核函数，最后得到数据垂直分布的隐私保护支持向量机.同样在2007年，OlviL.[127]Mangasarian等将简约支持向量机(RSVM)引入数据垂直分布的隐私保护支持向量机，每个实体生成相同的随机矩阵后，分别求得自己的核矩阵，将所有实体的核矩阵相加后得到整体数据的简约核矩阵，继而得到数据垂直分布的隐私保护支持向量机.[125]2008年，JaideepVaidya和HwanjoYu等又对任意划分的数据提出了一种隐私保护支持向量机(PPSVM)，基于同态加密技术，利用数量积协议，求解得到整体数据的Gram15 山东科技大学博士学位论文1绪论矩阵，进而在不揭露原始数据的情况下得到整体数据的核函数，最后得到数据任意划分[129]的隐私保护支持向量机.同年，OlviL.Mangasarian等也针对棋盘格式分布的数据建立了隐私保护支持向量机，同样利用简约随机核的概念，每个实体分别求得自己的核矩阵，将所有实体的核矩阵组合后得到整体数据的简约核矩阵，继而得到棋盘格式数据分布的线性和非线性隐私保护支持向量机.以上这些隐私保护支持向量机算法有的只针对二进制的数据，算法不具有一般性；有的算法采取的加密技术比较复杂，利用非常难寻找的hash函数；有的算法采取简约方法，只选取数据的一部分样本来构造整体算法，致使算法的分类精度降低等等.针对以上问题，本文研究较为简单的加密技术，针对一般的数据集，在不揭露原始数据的情况下巧妙构造核函数，针对各种数据分布，建立了相应的隐私保护支持向量机算法.1.5本文主要工作概述本文主要对支持向量机的简化分解算法和隐私保护支持向量机算法进行研究，主要内容包括以下几个方面：第一，阐述了支持向量机的一般简化算法，对支持向量机一般简化训练算法中起实质作用的支持向量和对应乘子之间的关系进行了理论分析，借助图形，直观地分析了支持向量相对于决策面的几何关系.通过对简化算法终止条件的分析，进一步分析和探讨了违背KKT条件对的几何含义，有助于构造新的有效的支持向量机算法.第二，首先，通过对各种工作集的选择方法进行分析，比较了各种工作集选择方法的优劣.然后，考虑了带有线性等式和界约束的非线性优化问题，主要针对那些变量个数较多，传统的优化方法不能求解的问题，如大规模支持向量机的凸二次规划问题，给出了一类分解算法.该算法每次迭代的可行下降方向从具有2q个分量的相对稀疏可行方向中选取，在假设方向水平集中至少有一组下标对应的分量严格在上下界之间的前提下，证明了算法的全局收敛性.数值实验说明了该算法的有效性.第三，针对数据垂直分布的情况，基于矩阵分解理论，提出了一个隐私保护支持向量机算法，该算法简单直接，无需利用安全多方计算技术，给出的分类器是公开的，但是并未揭露任何参与方的原始数据.最后利用矩阵分解理论证明了该算法的可行性.数值实验表明该算法是有效的，并且该算法的分类精度比Mangasrian的简约隐私保护支持向量机算法的分类精度高.16 山东科技大学博士学位论文1绪论第四，针对数据水平分布的情况，借助安全多方计算的加密技术，提出了一个隐私保护支持向量机算法，该算法给出的分类器是公开的，同样并未揭露任何参与方的原始数据.数值实验表明该算法的分类精度比Mangasrian给出的简约隐私保护支持向量机算法的分类精度高.最后利用矩阵分解理论证明了该算法的可行性.第五，针对数据任意分割的情况，利用水平分布的矩阵乘积的安全性策略，提出了一个隐私保护支持向量机算法，在未揭露任何参与方的原始数据的情况下给出了公开的分类器.该算法具有和未加隐私保护的经典支持向量机算法相同的精度.最后利用矩阵分解理论证明了算法的可行性和有效性.17 山东科技大学博士学位论文2支持向量机简化算法中支持向量与违背对的几何意义2支持向量机简化算法中支持向量与违背对的几何意义2.1引言[1，3，4，6，7]支持向量机是近年来机器学习研究的一项重大成果.由于SVM具有较为完美的数学形式、直观的几何解释和良好的泛化能力，它解决了神经网络结构难以确定与欠学习、过学习等方面的问题，避免了局部最优解，并且人为设定的参数少，便于实际应用，因此它迅速成为智能计算领域的研究热点之一，并成功地应用于许多分类和回归问题之中.支持向量机的训练算法实质上是求解一个凸二次规划，这需要计算和存储核矩阵函数，其大小与训练样本数的平方相关.随着样本数目的增多，所需要的内存增加.因此，研究有效的针对大规模训练样本集的SVM算法意义重大.支持向量能够充分描述整个训练样本集的特征,对它的划分等价于对整个样本集的划分.大多数情况下,支持向量只占训练样本集的很少一部分,支持向量的数量是影响最终分类速度的主要因素.因此减少分类函数中支持向量的数量成为研究支持向量机快速分类算法的目标,实现在不损失分类精度的前提下提高支持向量机的分类速度,在不影响分类精度的同时降低训练时间.所以，许多研究者通过寻找一包含较少支持向量的约简向量集代替原有的支持向量集，从而达到简化分类函数，提高分类速度的目的.许多研究者对简化算法的研究已经取得了一些成果.Osuna等人提出了分解算法，并[47,48,56,58]Light经过了一定的发展和改进；Joachims等基于Osuna的分解思想用软件SVM[49][50-55]实现了分解算法；Platt提出了SMO算法；文对SMO算法做了进一步的研究和[44-46]探讨，文也对简化算法做了改进.我们知道，求解SVM，即求解下面的凸二次规划问题：1TTminfQ()α=−αααe2αTst..yα=0(2.1)0,≤≤αCei=1,2,?,lT[65]其中Qy=yKxx(,)；K(,)xz=ϕϕ()()xz为核函数.文给出了求解支持向量机的一ijijij18 山东科技大学博士学位论文2支持向量机简化算法中支持向量与违背对的几何意义般简化训练算法的步骤：1步骤1设定优化变量初始值α，令k：=1.k步骤2如果α是优化问题(2.1)的最优解，即满足某种终止条件，则算法终止，否则，按照一定的工作集选择策略(如最大违背KKT对等策略)从训练样本集{1,2,?,}l(用样本序号代表训练样本)中选择包含两个或多个样本点的工作集Bl⊂{1,2,?,}.定义kkkNl={1,2,?,}B，α和α为α向量的部分分量，其下标分别在集合B和N中取值.BN步骤3求解以下关于α的优化问题：B1TTk⎡⎤QQBBBN⎡αBB⎤⎡TTα⎤min[αα()]⎢⎥⎢⎥⎢−[ee]⎥2BNkkBNαB⎣⎦QQNBNN⎣αNN⎦⎣α⎦(2.2)1TkTT=+ααQe[]−++Qαα常数2BBBBBBNNB⎧0,C≤≤αα⎪ijs..t⎨Tk.⎪yyα+=αα−y⎩iijjNNk+1求得优化变量α.Bk+1k步骤4令α=α，kk：=+1，转步骤2.NN注：求解(2.2)式的子问题，相当于求解关于SVM的原问题的如下子问题11T2min22ww++bC∑ξiiB∈Ts..tywii(xb+)1≥−∑Qijαξj−i,iB∈,jN∈ξ≥∈0,iB.i该简化算法中提出了最大违背KKT条件的对(i,j)的概念，而且根据该算法，我们知道在最后构造决策面时，只有支持向量起作用，所以找到支持向量，对于设计有效准确的大规模分类问题的支持向量机具有非常重要的意义.但是对于支持向量和最大违背KKT条件对(i,j)的几何意义，以及它们相对于迭代过程中的决策面的位置关系问题，没有给出明确的几何意义.基于这种考虑，本章对支持向量与相应乘子之间的关系做了深入的研究，并从几何上给出直观的解释；同时对最大违背KKT条件的对(i,j)的几何含19 山东科技大学博士学位论文2支持向量机简化算法中支持向量与违背对的几何意义义也做了进一步的探讨.本章的组织结构如下：2.2节对支持向量及其相应乘子之间的关系进行探讨，2.3节则对SVM的简化算法中终止条件进行研究和分析，给出了各种条件下的几何意义.2.4节给出了本章小结.2.2支持向量及其与相应乘子之间的关系2.2.1支持向量的含义线性可分SVM的原始问题的一般模型为l1Tmin2wwC+∑ξiwb,,ξi=1s.t.ywxb((⋅)+≥−)1ξiii,(2.3)ξ≥=0,il1,2,?,i其中C>0是一个惩罚参数.原始问题是凸二次规划,其可行域非空,因此问题必有解,即问题(2.3)关于(,)wb的解是存在的.为了求问题(2.3)的对偶问题,先构造其相应的Lagrange函数lll1TL(,,,,)wbξαγ=+−2wwC∑ξii∑∑α(((ywxii⋅))1)+b−+ξii−γξi,ii==11i=1其中α≥0和γ≥0.根据Wolfe对偶定义,对L关于wb,,ξ求梯度,即ii∇Lwb(,,,,)0,ξαγ=b∇Lwb(,,,,)0,ξαγ=w∇Lwb(,,,,)0.ξαγ=ξ则有llwy==∑∑αiiixyC,0ααii,=i+γi.ii==11然后将上面的极值条件代入Lagrange函数,对α求极大，则得到问题(2.3)的对偶问题为20 山东科技大学博士学位论文2支持向量机简化算法中支持向量与违背对的几何意义lllmax−⋅1∑∑yyααα(xx)+∑2ijijijiαij==11j=1lst..∑yiiα=0,i=10,≤≤=αCi1,2,?,l.i***因此，求解SVM的问题(2.1)即为(2.3)的对偶问题.综合上面的分析，设（w,,)bξ是问****题(2.3)的KKT点，设(,)αγ是相应的Lagrange乘子，则在（w,)b处的KKT条件为ll∗∗∗∗∗wyyC==∑∑αiiix,0ααii,=i+γi,(2.4)ii==11*****ywxbii((⋅+≥−))1ξξi,γii=0,(2.5)*******αξii(((yw⋅+−+=xi)b)1i))0,ξiii,α,γ≥=0,i1,2,?,l.(2.6)为分析支持向量与相应乘子之间的关系，首先给出支持向量的定义.[32]定义2.1(支持向量)考虑支持向量机中的原始问题(2.3).称输入xi为支持向量或T标准的支持向量，如果其对偶问题(2.1)有一个解α=(,,,)αα12"αl，它与输入xi对应的αi>0.如果对应的0<<αiC，称输入xi为界内的支持向量；如果对应的αi=C，称输入x为界上的支持向量.下面对支持向量的各种可能性作以分析.i2.2.2乘子αi的取值与支持向量之间的关系满足KKT条件的点可能就是最优点,所以一般选取最大违背KKT条件的样本点，对其求解相应的小规模的子问题，进行修正，逐渐逼近原问题的最优解.首先考虑问题(2.3)中ξ的含义,ξ是用来衡量一个样本点到它所属那类的超平面ii**ywxb((⋅+=))1的距离的大小,即iiξid=.||w||∗∗通过对式(2.4)-(2.6)分析,对正类点来说(负类点类似)，位于面ywxbii((⋅+=))1下方**的那些样本点,有ywxbii((⋅+>))1，由式(2.6)知，对应的αi=0.这些样本点不可能是21 山东科技大学博士学位论文2支持向量机简化算法中支持向量与违背对的几何意义支持向量.图2.1支持向量与Lagrangian乘子α之间的关系iFig2.1TherelationbetweenthesupportvectorsandLagrangianmultiplierαi**对于位于超平面ywxbii((⋅+=))1上的样本点，ξi=0.由互补松弛条件(2.5)可知,γi有三种可能：γi=0,0<<γiC或者γi=C.再由式(2.4)，可以得到αi也有这样三种**可能：αi=0,0<<αiC或者αi=C.所以位于超平面ybii((wx⋅)+=)1上的样本点可能不是支持向量,可能是界内的支持向量,也可能是界上的支持向量.∗∗**对于位于超平面ywxbii((⋅+=))1上方的样本点、位于超平面ywxbii((⋅+=))1****和决策面ywxbii((⋅+=))0之间的样本点、位于决策面ywxbii((⋅)+=)0和超平面****ywxb((⋅+=))−1之间的样本点、位于错分的负类样本点（满足()1wxb⋅+<−的样本iii点）中,都有对应的ξ>0,由式(2.5)知γ=0,再由式(2.4)知,α=C.所以这些样本点必iii为支持向量,而且一定为界上的支持向量.根据支持向量分类机算法，我们知道只有支持向量所对应的α才有效，对最后的结i果产生影响，而对应的大量的间隔外正确划分的样本点(即非支持向量)来说，它们是否参加训练，对最后结果并不影响.因此，可以酌情对这些样本点进行删减，从而达到简约训练样本集的目的.最优分类决策面仅由支持向量，即α≠0所对应的样本点来确定，i22 山东科技大学博士学位论文2支持向量机简化算法中支持向量与违背对的几何意义见图2.1，分类决策面是由分类间隔之上和之内的样本点，以及错分的样本点来决定的，其它的样本点对分类决策面的形成没有影响，支持向量的数量是影响最终分类速度的主要因素.仅仅训练支持向量就和训练整个数据集获得的分类决策面是一致的.2.3求解SVM的简化算法中终止条件的分析研究2.3.1简化算法的终止条件分析[96]针对问题(2.1)，对于求解SVM的一般简化算法，定义如下的指标集：RiC(){:α=<=αα,yiy1}{:0∪<=,−1},iiiiSiC(){:α=<=αα,y−1}{:0∪<=iy,1},iiiiIi(){:argα=i∈−maxyhh∇f()}α，hR∈()αJi(){:argα=i∈−minyhh∇f()}α.hS∈()α则有RS()(){0α∩αα=<
此文档下载收益归作者所有
《支持向量机的若干算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
分类号：TP181密级：公开UDC：单位代码：10424学位论文支持向量机的若干算法研究胡运红申请学位级别：博士学位专业名称：计算机软件与理论指导教师姓名：贺国平职称：教授山东科技大学二零一一年五月 论文题目：支持向量机的若干算法研究作者姓名：胡运红入学时间：2008年9月专业名称：计算机软件与理论研究方向：知识处理与数据挖掘指导教师：贺国平职称：教授论文提交日期：2011年4月20日论文答辩日期：2011年6月11日授予学位日期：2011年6月24日 SOMEAlGORITHMSRESEARCHONSUPPORTVECTORMACHINESADissertationsubmittedinfulfillmentoftherequirementsofthedegreeofDOCTOROFPHILOSOPHYfromShandongUniversityofScienceandTechnologybyHuYunhongSupervisor:ProfessorHeGuopingCollegeofInformationScienceandEngineeringMay2011 声明本人呈交给山东科技大学的这篇博士学位论文，除了所列参考文献和世所公认的文献外，全部是本人在导师指导下的研究成果.该论文资料尚没有呈交于其它任何学术机关作鉴定.博士生签名：日期：AFFIRMATIONIdeclarethatthisdissertation,submittedinfulfillmentoftherequirementsfortheawardofDoctorofPhilosophyinShandongUniversityofScienceandTechnology,iswhollymyownworkunlessreferencedofacknowledge.Thedocumenthasnotbeensubmittedforqualificationatanyotheracademicinstitute.Signature:Date: 山东科技大学博士学位论文摘要摘要支持向量机是一种通用的学习机器,是数据挖掘中的一项新技术，是借助于最优化方法解决机器学习问题的新工具.其核心问题是对一个大规模凸二次规划问题进行求解.分解算法是求解支持向量机的一类基于工作集选择的有效算法.隐私保护支持向量机算法则是在隐私保护数据挖掘算法基础上新兴起来的一个研究方向，在银行、保险公司、医学研究机构等行业有着广泛的应用.本文主要研究求解支持向量机的简化分解算法和针对分布式数据的隐私保护支持向量机算法，主要工作如下：首先，通过回顾支持向量机算法的发展过程及总结其研究现状，引出本文所做的主要工作.考虑到无论是原始支持向量机模型，还是本文重点讨论的隐私保护支持向量机模型，其本质问题是对一个大规模凸二次规划的求解，因此本文首先从研究支持向量机和对应乘子之间的关系着手，并给出一个新的分解算法.第二章中，基于支持向量机模型中支持向量的重要性，对支持向量和对应乘子之间的关系进行了理论分析，并借助图形，直观地分析了支持向量相对于决策面的几何关系.同时，通过对简化算法的终止条件及工作集选择的分析，探讨了违背和最大违背KKT条件对的几何含义，为直观理解终止条件及工作集选择方案提供理论依据.第三章中，通过对求解大规模支持向量机的分解算法中各种工作集选择方法的优劣进行比较，提出一类求解基于带有线性等式和上下界约束优化问题的大规模支持向量机模型的新分解算法.该算法每次迭代的可行下降方向从具有偶数个分量的相对稀疏可行方向中选取.在假设水平方向集中至少有一组下标对应的分量严格在上下界之间的前提下，证明了算法的全局收敛性，并通过数值实验验证了算法的有效性.本文的下半部分，主要研究隐私保护支持向量机算法.第四章和第五章，分别针对数据垂直分布与水平分布的情况，提出了两个隐私保护支持向量机算法.对于数据垂直分布的情形，算法直接基于矩阵分解的理论，给出的分类器是公开的，但是未泄露任何参与方的原始数据.对于数据水平分布的情况，与已有的SVM分类器不同，算法借助了安全多方计算的加密技术，给出的分类器是公开的，同样也未揭露任何参与方的原始数据.利用矩阵分解理论证明了算法的可行性.数值实验表明我们给出的隐私保护支持向量机算法的分类精度要比Mangasrian的简约隐私保护支持向量机算法的分类精度高.第六章，针对数据任意分割的情况，利用数据水平分布情况下的矩阵乘积的安全性策略，提出了一个隐私保护支持向量机算法，在未揭露任何参与方的原始数据的情况下 山东科技大学博士学位论文摘要给出了公开的分类器.该算法的分类精度比Mangasarian给出的简约隐私保护支持向量机算法的分类精度高.最后利用矩阵分解理论证明了该算法是可行的和有效的.最后，在第七章中，给出了现有支持向量机算法中存在的及本文尚未解决的问题，提出了进一步研究的课题.关键词：数据挖掘，机器学习，支持向量机，分解算法，安全多方计算，隐私保护支持向量机 山东科技大学博士学位论文AbstractAbstractSupportVectorMachine(SVM)isakindofgeneralizedlearningmachineandanewtechniqueofdatamining.Itisanewtooltosolveproblemsinmachinelearningbyoptimizationmethods.ThecriticalproblemofSVMistosolvealargescaleconvexquadraticproblem.DecompositionalgorithmisasimpleandeffectivemethodforsolvingSVManditsmaintechniqueishowtoselectaworkingset.Privacypreservingsupportvectormachine(PPSVM)isanewresearchfieldonthebaseofprivacypreservingdatamining(PPDM)algorithm.PPSVMiswidelyappliedinbank,insurancecompany,medicalresearchinstitute.ThispapermainlyfocusesonthesimplifieddecompositionalgorithmforsovingSVMandPPSVMfordistributeddata,andthemainworkisasfollows:Firstly,WeoverviewcurrentresearchonSVMandshowourmainworks.Asweknow,thecriticalproblemistosolveaconvexquadraticprogrammingproblemforbothoriginalSVMmodelandprivacypreservingsupportvectromachinemodelwhichwemainlydiscussedinourdissertation.InChapter2,BasedonthesignificanceofSupportVectoringeneralsimplifiedalgorithms,WetheoreticallyanalyzetherelationbetweentheSupportVectorsandthecorrespondingmultipliersandsetforththegeometricalrelationbetweenthesupportvectorsandthedecisionsurfacebymakingthegraph.Furthermore,wealsoanalyzethegeometricalmeaningofthepairofviolatingKKTconditionbyanalyzingtheterminationconditions.InChapter3,Byanalyzingandconstrastingallkindsofworkingsetselectionmethod,weputforwardanewdecompositionalgorithmforsovingakindoflargescaleSVMmodelwithasinglelinearequalityconstraintandboxconstraints.Ateachiteration，adescentsearchdirectionisselectedamongasuitablesetofsparsefeasibledirectionswhichhaveevencomponentstoreducetheiterationnumbers.Theglobalconvergenceofthealgorithmmodelisprovedbyassumingthepointsofthelevelsethaveatleastonegroupindexstrictlybetweenthelowerandupperbounds.Numericalexperimentsshowthatour 山东科技大学博士学位论文Abstractalgorithmiseffective.Innextchapters,wefocusourattentiononprivacypreservingsupportvectormachinealgorithm.InChapter4andChapter5,twonovelprivacy-preservingsupportvectormachine(PPSVM)classifiersareputforwardforverticallypartitioneddataandhorizontallypartitioneddata.Forverticallypartitioneddata,theclassifierissimpleanddirect,anditdoesnotrevealtheprivately-helddata.Forhorizontallypartitioneddata,bysecuremulti-partycomputationtechnique,theproposedSVMclassifierispublicbutdoesnotrevealtheprivately-helddata.WeprovethefeasibilityofouralgorithmsbyusingmatrixfactorizationtheoryandOurPPSVMalgorithmshaveaccuracycomparabletothatofanordinarySVMclassifierbasedontheoriginaldata.Numericalexperimentsshowthesecuritywithoutusingthesecuremulti-partycomputation.InChapter6,byakindofsecuritytechniqueforsovingthemultiplicationoftwomatricesinchapter5,weputforwardanovelprivacy-preservingsupportvectormachine(SVM)classifieronarbitrarypartitioneddata.TheproposedSVMclassifier,whichispublicbutdoesnotrevealtheprivately-helddata,hasaccuracycomparabletothatofanordinarySVMclassifierbasedontheoriginaldata.Weprovethefeasibilityofouralgorithmsbyusingmatrixfactorizationtheoryandshowthesecuritybyusingthesecuremulti-partycomputation.Keywords:DataMining,MachineLearning,SupportVectorMachine,DecompositionAlgorithm,SecureMulti-PartyComputation,PrivacyPreservingSupportVectorMachine 山东科技大学博士学位论文目录目录1绪论····················································································································11.1课题的提出··············································································································11.2支持向量机的模型和算法概述··············································································31.3支持向量机的分解算法概述··················································································81.4隐私保护支持向量机算法概述············································································101.5本文主要工作概述································································································162支持向量机简化算法中支持向量与违背对的几何意义····························182.1引言·······················································································································182.2支持向量及其与相应乘子之间的关系·································································202.3求解SVM的简化算法中终止条件的分析研究····················································232.4本章小结················································································································283大规模支持向量机的一类新的收敛的分解算法········································303.1引言·······················································································································303.2基本符号和预备知识····························································································323.3几种工作集选择方法的比较················································································353.4带有q个非零分量的稀疏可行方向集·································································443.5Wolfe线搜索算法··································································································483.6基于可行方向选择的新的分解算法·····································································503.7收敛性分析············································································································523.8数值实验················································································································543.9本章小结················································································································554不带安全多方计算的数据垂直划分的隐私保护支持向量机算法···········564.1引言·······················································································································564.2预备知识················································································································584.3垂直划分数据的不带多方安全计算的隐私保护线性和非线性分类器··············594.4数值实验················································································································63 山东科技大学博士学位论文目录4.5本章小结················································································································645带有安全多方计算的数据水平划分的隐私保护支持向量机算法···········665.1引言·······················································································································665.2安全多方计算的加密技术概述············································································685.3数据水平划分的隐私保护支持向量机算法·························································695.4数值实验················································································································745.5本章小结················································································································766针对任意分割数据的隐私保护支持向量机算法········································776.1引言·······················································································································776.2数据任意划分的线性隐私保护支持向量机算法·················································786.3数据任意划分的非线性隐私保护支持向量机算法·············································836.4数值实验················································································································846.5本章小结················································································································857总结和展望·····································································································867.1本文的特色和创新点····························································································867.2展望·······················································································································87致谢····················································································································89参考文献················································································································90攻读博士期间主要成果·····················································································101 山东科技大学博士学位论文ContentsContents1Introduction………………………………………………………………………………11.1RaisingofProject…………………………………………………………………………………11.2OverviewforModelandAlgorithmofSupportVectorMachines…………………………………31.3SecureMulti-partyComputationTechnique……………………………………………………81.4PresentConditionofDomesticandInternationalResearch………………………………………101.5MainWorkSummaryoftheThesis………………………………………………………………162GeometricalMeaningonSupportVectorsandViolatingPairsfortheSimplifiedalgorithmsofSVM……………………………………………………………………………………………………182.1Introduction…………………………………………………………………………………………182.2RelationbetweenSupportVectorsandtheCorrespondingMultiplier……………………………202.3AnalysisofTerminatingConditionofSimplifiedAlgorithmforSolvingSVM…………………232.4Conclusion…………………………………………………………………………………………283AnewConvergentDecompositionAlgorithmforSolvingLargeScaleSupportVectorMachines……………………………………………………………………………………………303.1Introduction………………………………………………………………………………………303.2NotationandPreliminaryResults………………………………………………………………323.3Severalmethods’comparisonofworkingsetselection……………………………………………353.4SetsofqcomponentsofSparseFeasibleDirections……………………………………………443.5Wolfe-TypeLineSearchAlgorithm………………………………………………………………483.6NewDecompositionAlgorithmBasedonFeasibleDirectionSelection…………………………503.7ConvergenceAnalysis……………………………………………………………………………523.8NumericalExperiments…………………………………………………………………………543.9Conclusion…………………………………………………………………………………………554Privacy-PreservingSVMClassificationonVerticallyPartitionedDatawithoutSecureMulti-PartyComputation………………………………………………………………564.1Introduction………………………………………………………………………………………56 山东科技大学博士学位论文Contents4.2SVMOverview……………………………………………………………………………………584.3Privacy-PreservingLinearandNonlinearClassifierforVerticallyPartitionedDatawithoutSecureMulti-PartyComputation…………………………………………………………………………594.4NumetricalResults………………………………………………………………………………634.5Conclusion…………………………………………………………………………………………645Privacy-PreservingSVMClassificationonHorizontallyPartitionedDatawithSecureMulti-PartyComputation………………………………………………………………665.1Introduction………………………………………………………………………………………665.2SVMOverview……………………………………………………………………………………685.3Privacy-PreservingClassifierforHorizontallyPartitionedDatawithSecureMulti-PartyComputation………………………………………………………………………………………695.4NumericalResults…………………………………………………………………………………745.5Conclusion…………………………………………………………………………………………756Privacy-PreservingSVMClassificationonArbitraryPartitionedData……………776.1Introduction………………………………………………………………………………………776.2Privacy-PreservingLinearClassifierforArbitraryPartitionedData………………………………786.3Privacy-PreservingNonlinearClassifierforArbitraryPartitionedData…………………………836.4NumericalResults…………………………………………………………………………………846.5Conclusion…………………………………………………………………………………………857MainResearchResultandConclusion……………………………………………867.1MainResearchResult…………………………………………………………………………867.2MainConclusion………………………………………………………………………………87Acknowledgements…………………………………………………………………………89MainReferenceDocuments………………………………………………………………90MainWorkAchievementoftheAuthorduringWorkingonDoctorPaper……………101 山东科技大学博士学位论文1绪论1绪论“机器学习”是人工智能的核心研究领域之一，其最初的研究动机是让计算机系统具有人的学习能力以便实现人工智能，基于数据的机器学习是现代智能技术中的重要方面，研究从观测数据（样本）出发寻找规律，并利用这些规律对未来数据或无法观测的数据进行预测.基于数据的机器学习就其实现方法可大致分为三种：第一种是经典的（参数）统计估计方法.第二种是经验非线性方法，如人工神经网络.第三种方法是统计学习理论（StatisticalLearningTheory,SLT）.由于机器学习需要设法对数据进行分析，这就使得它逐渐成为智能数据分析技术的创新源之一，并且为此而受到越来越多的关注.“数据挖掘”和“知识发现”通常被相提并论，在许多场合被认为是可以相互替代的术语.近年来，随着数据库技术的不断发展及数据量急剧增大，如何在大量的数据背后挖掘出那些有用的信息和知识，并将其从数据库中抽取出来为管理部门辅助决策具有非常重要的意义.数据挖掘就是从大量的、不完全的、有噪声的、模糊的、随机的数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程.大体上来说，数据挖掘可以视为机器学习和数据库的交叉，它主要利用机器学习提供的技术来分析海量数据，利用数据库提供的技术来管理海量数据.数据挖掘受到了很多学科领域的影响，其中数据库、机器学习、统计学对数据挖掘的影响最大.粗糙地说，数据库提供数据管理技术，机器学习和统计学提供数据分析技术，而通常情况下，统计学提供的很多技术要在机器学习领域进行进一步的研究，得到有效的机器学习算法之后才能进入数据挖掘领域.从这个意义上说，统计学主要是通过机器学习来对数据挖掘发挥影响，而机器学习和数据库则是数据挖掘的两大支撑技术.1.1课题的提出分类问题和回归问题都不是新问题，但是随着计算机的普及和广泛的应用，特别是机器学习和数据挖掘的迅速发展赋予了它们新的意义，目前这些问题再次引起人们的热切关注.传统的统计学研究的是当样本数目趋于无穷大时的渐进理论，但在实际问题中，样本的数目往往是有限的，因此一些理论上很优秀的学习方法实际中却可能不尽人意.1 山东科技大学博士学位论文1绪论与传统统计学相比，统计学习理论是一种专门研究小样本情况下机器学习规律的理论，该理论针对小样本统计问题建立了一套新的理论体系，在这种体系下的统计推理规则不仅考虑了对渐进性的要求，而且追求在现有有限信息的条件下得到最优结果.V.[1]Vapnik等人从二十世纪六、七十年代开始致力于统计学习理论方面的研究，到九十年代中期，随着该理论的不断发展和成熟，也由于神经网络等学习方法在理论上缺乏实质性进展，统计学习理论开始受到越来越广泛的重视.同时，在这一理论的基础上发展了[2]-[7]一种新的通用学习方法，即支持向量机(SupportVectorMachine或SVM),与其它机器学习算法仅仅考虑到经验风险最小化(EmpiricalRiskMinimization,ERM)的原则不同,支持向量机是一种通用的学习机器,是数据挖掘中的一项新技术，是借助于最优化方法[99]解决机器学习问题的新工具.它较好地实现了结构风险最小化思想.从理论上来说,由于采用了二次规划寻优,因而可以得到全局最优解,解决了在神经网络中无法避免的局部极小问题.由于采用了核函数,巧妙地解决了维数问题,使得算法复杂度与样本维数无关,非常适合处理非线性问题.另外,支持向量机应用了结构风险最小化原则,因而支持向量机具有非常好的推广能力.这样，支持向量机就在很大程度上克服了神经网络等传统机器学习方法学习过程中的过学习(Overfitting)、非线性(Nonlinear)、维数灾难(CurseofDimensionality)以及解的局部极小等问题,有很强的非线性处理能力和良好的泛化性能(GeneralizationPerformance).在模式识别方面,最突出的应用研究是贝尔实验室对美国邮政手写数字库进行的实验,这个实验人工平均错误率是2.5%,用决策树方法识别错误率是16.2%,两层神经网络中错误率最小的是5.9%,而用三种支持向量机方法得到的错误率分别为4.0%,4.1%和4.2%,优于决策树和神经网络方法.在人脸检测与识别领域,MIT用支持向量机进行的人脸检测实验也取得了很好的效果,可以较好地学会在图象中找出可能的人脸位置.此外，支持向量机还广泛用于图像处理,在图像分割,图像检测,图像分析,遥感图像分析,语音识别,文本分类,三维物体识别等方面也有较多的应用研究成果.在医学研究领域,支持向量机主要被用于通过基因数据对基因进行分类,对人类基因的表示数据进行分析,确定基因的功能,对蛋白结构类别进行预测等.与此同时,支持向量机在工业领域的应用研究也逐渐受到研究者的重视,支持向量机在信号处理领域,金融领域等都已初步显示出强大的优势.目前，支持向量机已成为二十世纪末二十一世纪初发展最快的研究方向之一.尽管支持向量机在国内的研究滞后于国外,但近年来发展较快.国内的研究人员基2 山东科技大学博士学位论文1绪论于学习机器要与有限的训练样本相适应的核心思想，开展了许多有效的研究工作,取得了一系列优秀的成果，但其中还有许多问题尚未解决.因此，对SVM的理论与应用进行研究具有重要的理论意义与应用前景.作为目前机器学习领域内的焦点之一，自支持向量机(SVM)出现以来，有关它的研[2,7,8-26,30-40]究成果就不断涌现.由于SVM算法的潜在应用价值，吸引了国际上众多的知名学者，近几年出现了许多发展和改进的支持向量机算法.目前，关于支持向量机学习算法的研究方兴未艾，它是支持向量机理论的研究重点和难点内容之一.隐私保护支持向量机算法是2006年之后新兴起来的一个研究方向，基于隐私保护数据挖掘技术的发展，基于人们对个人隐私信息迫切需要保护的要求，该研究方向已经成为机器学习领域非常重要的研究方向之一.本文重点讨论简化分解算法和隐私保护支持向量机算法，为此本章的剩余部分将对这两方面学习算法的研究现状和最新进展进行较为详细深入的阐述，作为本论文的研究背景和工作基础.1.2支持向量机的模型和算法概述1.2.1支持向量机的基本概念和一般模型支持向量机的训练算法实质上是求解一个凸二次规划(ConvexQuadraticProgramming,简称CQP),这需要计算和存储核矩阵函数,其大小与训练样本数的平方[80,85-93]相关,随着样本数目的增多,所需要的内存增加.最优化理论中的许多成熟算法，例如牛顿法、共轭梯度法及内点法需要利用整个Hessian矩阵，所以受计算机内存容量的限制，只适用于样本较少的问题，因此设计适用于大量样本的算法成为SVM研究中的重要内容.我们都知道，支持向量机的核心思想是引入核函数的概念，把学习样本映射到一个高维空间中，在高维空间中建立与空间维数无关的最优分类超平面，从而解决非线性分类或回归学习问题.我们讨论的分类问题基本分为线性可分问题、近似线性可分问题和实质线性不可分问题(即线性不可分问题).例如，图1.1所示的问题，很容易用一条直线把训练集正确地分开(即两类点分别在直线的两侧，没有错分点)，这类问题称为线性可分问题.而图1.2所示的训练集不能用直线把这两类样本点正确划分开，需要借助曲线进行分类，称为非线性可分问题.3 山东科技大学博士学位论文1绪论10.9L0.8W0.70.60.50.40.30.20.1000.20.40.60.81图1.1线性分类支持向量机的几何含义Fig1.1Geometricalmeaningoflinearseperablesupportvectormachine图1.2非线性分类支持向量机的几何含义Fig1.2Geometricalmeaningofnonlinearseperablesupportvectormachine在机器学习问题中，我们要从数据中发现一些规律或知识，这常常需要考虑数据中的相似性.例如，在分类问题中，设包含l个样本的训练集为(,),1,2,,xyi=?l,输入向iin量x∈χ=R,对应的期望输出为y∈{1,1}+−=，il1,2,,?,其中+1和-1分别代表两类的类ii别标识,n为输入维数.学习的目标就是构造一个决策函数,将测试数据尽可能正确分4 山东科技大学博士学位论文1绪论类，从而推断任一模式x相对应的y值.解决这类问题的一个直观想法是,判断一下新的输入x是与正类的那些输入相似,还是与负类的那些输入相似,并由此推断出x的归属.那么，如图1.1所示，如何选取分划直线L的法方向w呢？我们知道，对于适当给定的法方向，会有两条极端的直线，我们称这两条直线之间的距离为与该法方向相应的“间隔”，可以想象，我们应该选取使“间隔”最大的那个法方向.基于上述最大间隔的思想，建立其相应的数学模型，可得其原始问题的一般描述为:l1Tmin2wwC+∑ξiwb,,ξi=1Tst..ywxii(⋅+≥−b)1ξi(1.1)ξ≥=0,il1,2,?,i其中,C为惩罚参数,C越大表示对错误分类的惩罚越大,是算法中唯一可以调节的参数.对于线性不可分问题，其主要思想是通过一个非线性变换φ()x，将其映射到一个高维空间中,使得问题在高维空间中线性可分,并且在高维空间中只需进行内积运算,即将原来线性的内积(,)xx变成了((),())φxφx，甚至不需要知道采用的非线性变换的形式,ijij所以避免了高维变化计算问题,使问题大大简化.根据Hilbert-Schmidt原理,只要一种运算满足Mercer条件,就可以作为内积函数(或称为核函数)使用.目前常用的内积函数主要有:(1)多项式内积函数(核函数):qKxy(,)[(=xy⋅+)1](2)径向基内积函数(核函数，即RadiusBasisFunction,简记为RBF):2⎧||x−y⎫Kxy(,)exp=−⎨⎬2⎩⎭2σ(3)Sigmoid内积函数(核函数)：Kxy(,)tanh{(=vxyc⋅+)}对于不同的分类问题，可以选择不同的核函数,不过目前还没有一个针对特定问题选择最佳核函数的有效方法.在给出Mercer核定义之前，我们先给出Gram矩阵的概念，这是因为在核矩阵的构造算法中,其关键就是Gram矩阵的计算.5 山东科技大学博士学位论文1绪论[32]定义1.2.1对于给定的函数KR:χ×χ→和xx,,,?x∈χ，则称第i行第j列元12l素为KK=(,)xx的ll×矩阵K为函数K的关于x,,,xx?的Gram矩阵.ijijll×12l[32]TT定义1.2.2称Kxx(,)是Mercer核，如果Kxx(,)是χ×χ上的连续对称函数，χnT是R上的紧集，且Kxx(,)关于任意的xx,,,?x∈χ的Gram矩阵半正定.12lT在本文后面的章节中，涉及到的核函数均指Mercer核函数，记作Kxx(,)，Kxx(,)ijT或者KAA(,)，简称核.为求解支持向量机的原始问题(1.1),采用Lagrange乘子法,由于式(1.1)是具有线性约束的二次规划问题,故很容易写出其对偶问题为:1TTminαααQe−2αs..0tC≤≤=αi,il1,2,,?(1.2)Tyα=0其中e是单位向量,C>0是上界,Q是ll×正半定矩阵,且Qy=yxx(,)，如果为非线ijijij性分类问题，则Qy=yKxx(,)，其中Kxx(,)为核函数.ijijijij用于分类问题的支持向量机算法可描述为:n步骤1设已知训练样本集{(,),xyi=1,2,,?l},期望输出y∈{1,1}+−,x∈R;iiiiT步骤2选择核函数Kxx(,)和惩罚参数C,构造并求解最优化问题lllmin1∑∑∑yyαααKxx(,)−2ijijijjαii==11j=1lst..∑yiiα=0(1.3)i=10,≤≤=αCi1,2,?,li****得最优解α=(,,,)αα?α;12ll****步骤3选择α一个小于C的正分量αj,并据此计算by=−ji∑yKxxαi(,)ij;i=1l**步骤4求决策函数f()xy=+sgn(∑iiαK(,)xixb).i=16 山东科技大学博士学位论文1绪论由支持向量机的一般数学模型可以看出，支持向量机就是首先通过内积函数定义的非线性变换将输入空间变换到一个高维空间,再在这个高维空间中(广义)求最优分类面.最后，将输入样本x进行相同的非线性变换，并根据f()x的符号来确定其归属.1.2.2求解支持向量机的算法概述由于SVM的训练其本质就是求解一个凸二次规划问题,因此，最优化理论中的许多成熟算法,如牛顿法、共轭梯度法、内点法等都可以用于求解SVM.但是这些算法在求解时需要利用整个Hessian矩阵信息,对于海量数据的处理,即对大规模数据集的分类问题，受普通计算机内存容量和计算时间的限制,这些算法的求解效率很低,因此不再适用.于是，设计适用大规模问题的SVM算法就成为一个重要的研究方向.一些学者针对SVM自身的特点及不同的问题和不同的要求，提出了多种快速学习算法.如简化分解算法[26,46-52][15,16][13]、最小二乘支持向量机算法、并行学习支持向量机算法、增量学习支持向[11,12,14]量机算法等等.目前,这些算法在理论和实践上都取得了一定的进展,并出现了一些比较有效的训练算法的相关软件.另外，对于支持向量机模型本身，许多学者也进行了大量研究，如Anthony等人给[29]出了关于硬间隔支持向量机学习误差的严格理论界限;Shawe-Taylor等人给出了类似[1]的关于软间隔支持向量机核回归情况下的误差界限;Vapnik等研究了支持向量机的推广性能及其在多值分类和回归问题中的扩展问题.随着支持向量机在理论上的深入研究,出现了许多变种支持向量机.Vapnik提出的可[6,27,28]调参数C的SVM统称为C-SVM系列.Schölkopf提出的用于分类和回归的ν-SVM,引入反映超出ε管道的样本数据点个数(即边界支持向量数量)和支持向量数的新参数ν,从而简化SVM的参数调节.另外,一些学者还扩展了支持向量机概念,如Mangasarian等[8]人引入的通用支持向量机(GeneralizedSVMs).由于在某些情况下，每个样本并不是完全能够划归到某一类,即样本与类别之间存在着某种模糊的隶属关系,由此,Takuya和[39,40]Lin等人提出了一种模糊支持向量机,通过给样本增加一个模糊隶属关系,来充分利[15,16]用样本的信息.1999年,Suykens提出了一种最小二乘支持向量机(LeastSquaresSVM,LS-SVM).通过引入最小二乘线性系统到支持向量机中,用以代替传统的支持向量机中采用二次规划方法解决函数估计的问题.在此基础上提出的周期最小二乘支持向量机已用于时间序列的预测.后来又有学者提出加权支持向量机用来克服普通支持向量机不能根据每个采样点数据的重要性区别对待的缺陷,同时还可以解决类别补偿问题.7 山东科技大学博士学位论文1绪论One-classSVM算法解决的是只有正训练样本一个类别的分类问题.内积矩阵分解算法是在已经得到了支持向量集S后,通过变换去掉其中的n个支持向量,以减少支持向量的数目来提高分类器的分类速度.这n个支持向量并不是简单的舍弃,因为在变换中,变换矩阵保留了所有支持向量的信息,所以分类器的精度并不会下降.基于KKT条件的[11,12,14]增量学习算法是根据样本是否违反KKT条件来选择并积累支持向量,其中还考虑了普通样本和支持向量之间可能存在的相互转化的问题.所以新增样本中只有那些违反KKT条件的样本对支持向量机的可累积性学习起作用.此外，还有光滑支持向量机[24][20,22,23,25](SmoothSVM,SSVM)模型,简化支持向量机(ReducedSVM,RSVM)模型,小波支持向量机(WaveletSVM)模型,Lagrangian支持向量机模型(LSVM),多类分类支持[15,16,17,18,33-38]][39,40]向量机(Multi-classSVM,Mc-SVM)模型、模糊支持向量机、半监督支[135,136]持向量机以及其它一些新的支持向量机模型等等.1.3支持向量机的分解算法概述支持向量机能够充分描述整个训练样本集的特征,对部分支持向量的划分等价于对整个样本集的划分.大多数情况下,支持向量只占训练样本集的很少一部分,而支持向量的数量是影响最终分类速度的主要因素，所以减少分类函数中支持向量的数量成为研究支持向量机快速分类算法的目标.因此，许多研究者通过寻找一个包含较少支持向量的约简向量集代替原有的支持向量集，从而达到简化分类函数，提高分类速度的目的.[44]Downs削减了那些在特征空间中能被其它支持向量线性表示的冗余支持向量，削减完毕后剩余的支持向量即为所求的约简向量，然后修改约简向量所对应的Lagrange乘子使[45]SVM判定函数保持不变.Baudat通过空间映射的方法来减少支持向量，该方法首先从训练样本中寻找支持向量，然后将支持向量映射到特征向量集所构造的子空间来削减冗[46]余支持向量.刘通过优化的方法适当变换特征空间中的内积矩阵，并进一步变换分类函数的形式，来减小分类函数中支持向量的数量，提高分类精度.以上文献所提的方法都是在保留全部支持向量信息的情况下削减支持向量，因此能够在不损失分类精度的前提下简化分类函数，提高分类速度.和上述方法通过削减原始支持向量的数量来简化分类函数不同的是，部分研究者采用迭代构建新的向量作为约简向量的方法来简化分类函数.虽然此类简化法导致一定程度的分类精度损失，但是取得了较大的支持向量约简率，极大地加快了SVM的分类速度，广泛被采用.8 山东科技大学博士学位论文1绪论分解方法的基本思路来源于Vapnik首先提出的分块(Chunking)算法,分块算法基于这样一个事实,即去掉Lagrange乘子等于零的训练样本不会影响原问题的解.对于给定的训练样本集,如果其中的支持向量是己知的，训练算法就可以排除非支持向量只需对支持向量计算Lagrange乘子即可.该方法每次求解一子QP问题，得到若干支持向量，用这些支持向量和一些不满足优化条件的样本，构成新的子QP问题，而初始子QP问题由任意若干个样本构成，重复上述过程直到所有样本满足优化条件.分块算法大大减少了矩阵的模，当支持向量的数目远远小于训练样本数目时，分块算法显然能够大大提高运算速度，然而如果支持向量的数目本身就比较多，子QP问题所对应的Hessian矩阵也会很大，因此分块算法不适用于支持向量较多的情况.[47]针对分块算法的缺点，osuna提出分解算法来加快SVM的训练速度.分解算法将训练样本分为两个集合，工作集B和非工作集N.|B|和|N|的大小都是不变的.在每次迭代中，首先确定B，然后求解关于B的子QP问题，而保持N中样本所对应的Lagrange乘子不变.即使支持向量的个数超过工作集的大小也不改变工作集的规模，而只对支持向量中的一部分进行优化.这种算法的关键在于选择一种合适的工作集换入换出策略即工作集的确定方法.Joachims在上述分解算法的基础上做出了几点重要改进.第一，采用类似zoutendijkd可行方向法的策略确定工作集B，即求解一线性规划问题，得到可行下降方向，把该方向中的非零分量作为本次迭代的工作集.由于q被限定为偶数，该线性规划存在高效算法，其核心是一个排序问题.第二，提出shrinking方法，估计出有界支持向量和非支持向量，有效地减小QP问题的规模.最后，利用缓存(KernelCache)来减light少赫塞矩阵中元素的计算次数.Joachims利用这些方法实现的SVM是目前设计svm分[70]类器的重要软件.Laskov提出另一种工作集确定方法，最大不一致(maximalinconsisteney)算法，并进一步指出，对于二分类问题，这个算法等价于Joachims的可行方向策略.在分解算法的基础上，Platt提出了更为高效的序贯最小优化算法(sequential[49]minimaloptimization，简称SMO).该算法可以说是分解算法的一个极端特例，它在每次迭代中固定||2B=，由于只有两个变量，应用等式约束可以将其中一个用另一个表示出来，所以迭代过程中每一QP子问题的最优解可以通过解析方法求出，避免了复杂的数值求解优化问题的过程.此外，Platt采用启发式的方法来确定工作集，通过一个两层嵌套循环分别选择进入工作集的两个样本：外层循环在某个乘子集合中遍历，将第一个不满足优化条件的乘子作为第一个被优化对象，第一次遍历全部乘子，以后遍历非有界9 山东科技大学博士学位论文1绪论乘子，如果所有非有界乘子都满足优化条件，则再次遍历全部乘子.一旦找到第一个乘子，内层循环寻找第二个乘子，使其在当前迭代步中具有最大的改变量.完成一次优化再循环进行下一次优化，直到全部样本都满足最优条件为止.这种启发式策略大大加快Light[51]了算法的收敛速度，随后的SMO算法借鉴了SVM算法.Keerthi等人给出一个双阈值优化条件，并提出两种利用该条件确定工作集的方法，实验表明，两种方法，特别是方法二，可以大大减少核函数的计算次数，提高SMO的效率.在Joachims和Keerthi研[57,58]究工作的基础上，Chang和Lin提出了基于可行方向策略的SMO算法，该方法每次选取两个最违反优化条件的样本点进入工作集，并且也引入了shrinking与缓存机制.相对于其它训练算法，采用可行方向策略的SMO算法具有较快的训练速度，并且能够确保收敛，因此称为标准的SMO训练算法.Light经过几年的发展，综合借鉴其它方法，特别是SVM和SMO的优点，引入有效的核缓存(KernelCache)和Shrinking方法，特别由于Lin等对终止迭代条件进行了分析、对分解算法的收敛性进行了证明，使得分解算法已经成为当前最常使用的SVM分类器训练方法，并且已经推广到SVM回归等领域.1.4隐私保护支持向量机算法概述1.4.1安全多方计算[41,42,43,117-119]安全多方计算(securemulti-partycomputation)是分布式密码学的理论基础，也是分布式计算研究的一个基本问题.它蕴含了密码学中任何协议问题在原则上的实[42]现方案.最早，A.Yao于1982年通过姚氏百万富翁问题提出了安全两方计算问题.姚氏百万富翁问题是指两个争强好胜的百万富翁Alice和Bob在街头相遇，如何在不暴露各[43]自财富的前提下比较出谁更富有？5年后，Goldreich,Micali和Wigderson于1987年提出了可以计算任意函数的安全多方计算协议.到上世纪90年代，安全多方计算的研究已经非常活跃.具体地说，安全多方计算是考虑如下的问题.设EEEE={,,,}?是n个参与者集12n合，他们想要“安全地”计算某个给定的n个输入和n个输出的函数f(,,,)(,,,)xx??x=yyy，其中这个函数的n个输入是分别由这n个参与者秘密掌握12nn12的，设E的秘密输入是x，并且在计算结束后，E得到输出y.这里的安全性是要求即iiii使在某些参与者有欺骗行为的情况下，仍然能保证计算结果的正确性，即计算结束后每10 山东科技大学博士学位论文1绪论个诚实的参与者E都能得到正确的输出y，同时还要求保证每个参与者输入的保密性，ii即每个参与者E除了知道(,)xy以及从中推出的信息之外，得不到任何其它的信息.这iii样如何构造满足安全性的算法是一个关键问题.不难看出，如果我们能安全地计算函数x+x和xx，则我们可以安全地计算任何布尔函数或多项式函数.1212例如，我们考虑一个两方计算：EEE={,}，需要计算的函数为f:(,)xx→(,)yy，121212其中y==yxx.参与者E的秘密输入是x，参与者E的秘密输入是x.为计算f，12121122当然最简单的办法就是参与方E和E都公开自己的输入，于是他们都能够计算出正确的12输出.这样做尽管可以保证计算结果的正确性，但无法保证每个参与者输入的保密性.因此，为了保证输入的保密性，x和x就不能直接公开，要通过一些随机数将他们隐藏起12来再输入.通过设计适当的算法，使得每个参与者最后在得到正确输出的同时，各自输入的保密性也得到保证.简单地说，参与方E和E要安全计算f，可通过下面的示意图123所示来计算.f(x1,x2)+r2x1+r1=X1E1E2f((x1+r1),x2)+r2=X2f(x1,x2)图1.3安全两方计算示意图Fig1.3.SecureTwo-PartyComputation第一轮：E传给E消息X，其中X包括x的信息和一些随机数；12111第二轮：E传给E消息X，其中X包括X,x的信息和一些随机数；212212……最后一轮，假设是第k轮，E传给E消息X(或者E传给E消息X)，即为最后的12k21k输出.11 山东科技大学博士学位论文1绪论这样，E可以根据在交互过程中得到的信息计算并得到y，i=1,2.这里的正确性ii是指y==yfxx(,).保密性是指E得到的信息不会比(,)xy以及由此推出的信息更1212iii多，i=1,2.也就是说，如果x=0，则E得到(,)xy和y的值，但对E的输入一无所111122知；如果x=1，则E除了知道(,)xy和y的值以外，还能推出E的输入x，除此之外，1111222E一无所知.对于E，情况完全相同.需要指出，E得到由(,)xy推出的信息是安全性12iii要求所允许的,从直观上看,这也是合理的.需要注意的是，由于安全性是针对具体的攻击者而言的，并不是任何安全性要求(即针对任何的攻击者)都有算法实现.因此首先应对安全性要求进行具体刻画，而后设计满足这个安全性要求的算法.如果所有参与者都是诚实的，即在计算过程中，每个人严格按照协议执行并且不会蓄意窃取其它信息，那么平凡地满足安全性要求.相反，如果所有人都是不诚实的，那么讨论安全多方计算就没什么意义.在两方计算中，如果只有一人不诚实，在计算过程中严格执行协议但蓄意窃取其它信息(即被动攻击)，则存在满足这种安全性要求算法，在其它情况下都不存在安全的两方计算协议.对于解决某个具体密码学问题的协议，我们说它是安全的，传统的做法是列表验证该协议是否具有我们所希望具备的特点.例如，我们设计了一个对称加密算法，希望说明它是安全的，为此可以列一张表记录它所应该具有的性质或它应抵抗的已知攻击，比如这张表应该包括该算法能够抵抗差分攻击，线性攻击等性质.然后，我们去验证该算法是否满足这张表列出的各种性质.如果是，则称它满足安全性要求，否则称它不满足安全性要求.这样做的好处是简单，便于操作，缺点是无法确定这张表是否是完备的，或者说无法确定这张表是否已经包含了所有可能的安全性要求.在处理安全多方计算时，则采取完全不同的途径.首先构造一个理想方案，它蕴涵了我们所希望的安全性要求，然后把要证明安全的协议，称为现实方案，与理想方案比较，如果在某种意义下比不出差别来，就证明了我们设计的现实协议与理想方案在这种意义下具有相同的安全性.目前安全多方计算已得到许多学者的研究，其在密码学上的地位也日益重要，现有的许多密码工具都是安全多方计算的基础，SMC的关键技术涉及到秘密分享与可验证秘密分享、门限密码学、零知识证明、茫然传输、茫然多项式估值、百万富翁协议等多方面的内容，协议中应用的基本密码算法包括各种公钥密码体制，特别是语义安全的同态公钥加密系统.在不同的计算领域中，SMC问题的安全需求不相同，应针对具体SMC12 山东科技大学博士学位论文1绪论应用环境进行安全性定义，寻找高效的SMC解决方法.在SMC应用研究方面，寻找特殊领域的SMC问题及其解决方案是值得深入研究的方向，如分布式生成RSA密钥、多方合作签名、自安全的无线Ad-hoc网络等.随着电子商务的兴起，电子拍卖、电子选举、私有信息检索成为SMC研究的又一热点.此外，SMC在保护隐私的科学计算，保护隐私的统计分析、保护隐私的几何计算、保护隐私的数据库查询、保护隐私的数据挖掘、保护隐私的入侵检测等方面的课题，都值得做进一步深入的研究.1.4.2隐私保护支持向量机算法“隐私权”最早在1890年12月美国人沃伦和布兰代斯所写的《隐私权》中被正式定义.“隐私权”界定为“生活的权利”和“不受干扰”的权利.他们认为，隐私权本质上是一种个人对其自身事务是否公开给他人的权利，保护个人的隐私权就是保障个人的“思想、情绪及感受”不受他人打扰的权利，保护自己人格不受侵犯的权利.随着越来越多的信息可以电子形式或从网上得到，人们对自己隐私的保密要求变得越来越迫切.在这种情况下，如何在保证个人隐私的前提下进行数据挖掘、数据分类等成了一个亟需解决的问题.另外，在双方或多方合作进行数据挖掘的时候，由于某种原因，参与方往往不愿意将数据与他人共享而只愿意共享数据挖掘的结果.这种情况在科学研究、医学研究及经济和市场动态研究方面常常遇到.因此，如何保护私有信息或敏感信息在挖掘过程中不被泄露，就成为数据挖掘、支持向量机算法研究中的一个很有意义的研究课题.隐私保护数据挖掘或隐私保护支持向量机的主要目的就是用某种技术改进已有的原始数据，利用修改后的数据进行数据挖掘或数据分类，保持数据挖掘结果或分类的正确性，同时使得敏感的数据和知识不被泄露.根据数据的分布情况，隐私保护技术可以分为针对集中式数据的隐私保护技术和分布式数据的隐私保护技术.分布式数据的隐私保护技术又分为数据水平分割的隐私保护技术和数据垂直分割的隐私保护技术.数据的水平分割主要原因是多个机构或组织对于不同的个体收集了相似的信息；数据的垂直分割主要原因是多个机构或组织收集了同样的个体的不同信息.隐私保护技术从整体上分为三类，分别为面向单个数据记录、面向集中式数据、面向分布式数据的隐私保护技术.13 山东科技大学博士学位论文1绪论表1.1针对不同数据类型的隐私保护技术Table1.1Privacypreservingtechniquefordifferenttypeofdata数据分布方式隐私保护技术随机响应技术、基于阻塞的技术、单个数单个数据记录据交换和属性变换技术集中式数据启发式技术和重建式技术水平分割的数据基于密码学的隐私保护技术，包括安全多分布式数据垂直分割的数据方计算等等任意分割的数据面向单个数据记录的隐私保护技术主要包括随机响应技术、基于阻塞的技术、单个数据交换和属性变换技术等等，其主要特征是为了实现单个数据的隐私保护，对数据进[119]行分别处理，使其它参与方无法得知有关单个数据记录的准确信息.WenliangDu提出了基于随机响应技术的隐私保护分类算法.在统计某个特征的分布概率时，利用问题的随机性保护被调查者的隐私，同时又得到准确的分布概率.面向集中式数据的隐私保护技术适用的情况是，数据挖掘的目标针对数据的集合特征，而非单个数据信息.其具体方法是收集数据时对单个记录加入随机变量实现干扰，其后对带有干扰的数据利用重构技术重建原始数据特征，再对其进行挖掘和分析.针对集中式数据的隐私保护技术主要包括启发式技术和重建式技术.启发式技术通过仅修改特定值，而非全部值来减少数据挖掘效果的失真.重建式技术主要分为数值型数据的重[103]构技术以及二进制数据与分类数据的重构技术.2000年，R.Agrawal提出了用离散化的方法与值变形的方法修改原始数据，然后用重构算法构造原始数据的分布.该算法通过加随机偏移量的方法对原始数据进行变换，然后利用贝叶斯公式来推导原始数据的密度函数以重构判定树.14 山东科技大学博士学位论文1绪论面对分布式数据的隐私保护技术大多数是基于密码学的隐私保护技术.特别在分布式环境下的隐私保护问题，安全多方计算(SMC)是最为常用的一个协议.正如1.4.1部分所介绍的，安全多方计算是在一个互不信任的多用户网络中，各用户能够通过网络来协同完成可靠的计算任务，同时又能保持各自数据的安全性.在多方分类挖掘方面，[106,107]WenliangDu利用安全数量积技术提出了垂直分布数据的安全分类算法，而Lindell首次提出了使用加密方法建立水平分布数据的决策树，将对最佳分类属性的寻找转化为安全多方计算问题.从1999年RkaeshAgrawal在数据库和数据挖掘的知识发现国际会议上(ConferenceonKnowledgeDiscoveryinDatabasesandDataMining,简称KDD99)上作了一场精彩的主题演讲后，隐私保护数据挖掘便迅速地发展起来，各种新的方法不断涌现.与此同时，作为数据挖掘中非常重要的一种新方法-隐私保护支持向量机的研究也得到了学术界的[120,123-129]重视，国内外很多学者致力于隐私保护支持向量机算法的研究.目前隐私保护支持向量机算法的研究主要针对分布式数据.[123]对于水平分布的数据，HwanjoYu于2006年对水平分布的布尔数据提出了一种隐私保护支持向量机(PPSVM)，将向量问题转换为集合问题来处理，引入hash函数计算集合交的势，进而得到核函数，在得到核函数的时候没有揭露原始数据，最后利用所得到[128]的核函数的数据建立了隐私保护支持向量机.2007年，OlviL.Mangasarian等将简约支持向量机(RSVM)引入数据水平分布的隐私保护支持向量机，每个实体生成相同的随机矩阵后，分别求得自己的核矩阵，将所有实体的核矩阵组合后得到整体数据的简约核矩阵，继而得到水平分布数据的隐私保护支持向量机.[124]对于垂直分布分布的数据，HwanjoYu于2006年对垂直分布的数据提出了一种隐私保护支持向量机(PPSVM)，利用密码学中的安全多方计算技术，通过分别求解各个实体的Gram矩阵，得到整体数据的Gram矩阵，进而在不揭露原始数据的情况下得到整体数据的核函数，最后得到数据垂直分布的隐私保护支持向量机.同样在2007年，OlviL.[127]Mangasarian等将简约支持向量机(RSVM)引入数据垂直分布的隐私保护支持向量机，每个实体生成相同的随机矩阵后，分别求得自己的核矩阵，将所有实体的核矩阵相加后得到整体数据的简约核矩阵，继而得到数据垂直分布的隐私保护支持向量机.[125]2008年，JaideepVaidya和HwanjoYu等又对任意划分的数据提出了一种隐私保护支持向量机(PPSVM)，基于同态加密技术，利用数量积协议，求解得到整体数据的Gram15 山东科技大学博士学位论文1绪论矩阵，进而在不揭露原始数据的情况下得到整体数据的核函数，最后得到数据任意划分[129]的隐私保护支持向量机.同年，OlviL.Mangasarian等也针对棋盘格式分布的数据建立了隐私保护支持向量机，同样利用简约随机核的概念，每个实体分别求得自己的核矩阵，将所有实体的核矩阵组合后得到整体数据的简约核矩阵，继而得到棋盘格式数据分布的线性和非线性隐私保护支持向量机.以上这些隐私保护支持向量机算法有的只针对二进制的数据，算法不具有一般性；有的算法采取的加密技术比较复杂，利用非常难寻找的hash函数；有的算法采取简约方法，只选取数据的一部分样本来构造整体算法，致使算法的分类精度降低等等.针对以上问题，本文研究较为简单的加密技术，针对一般的数据集，在不揭露原始数据的情况下巧妙构造核函数，针对各种数据分布，建立了相应的隐私保护支持向量机算法.1.5本文主要工作概述本文主要对支持向量机的简化分解算法和隐私保护支持向量机算法进行研究，主要内容包括以下几个方面：第一，阐述了支持向量机的一般简化算法，对支持向量机一般简化训练算法中起实质作用的支持向量和对应乘子之间的关系进行了理论分析，借助图形，直观地分析了支持向量相对于决策面的几何关系.通过对简化算法终止条件的分析，进一步分析和探讨了违背KKT条件对的几何含义，有助于构造新的有效的支持向量机算法.第二，首先，通过对各种工作集的选择方法进行分析，比较了各种工作集选择方法的优劣.然后，考虑了带有线性等式和界约束的非线性优化问题，主要针对那些变量个数较多，传统的优化方法不能求解的问题，如大规模支持向量机的凸二次规划问题，给出了一类分解算法.该算法每次迭代的可行下降方向从具有2q个分量的相对稀疏可行方向中选取，在假设方向水平集中至少有一组下标对应的分量严格在上下界之间的前提下，证明了算法的全局收敛性.数值实验说明了该算法的有效性.第三，针对数据垂直分布的情况，基于矩阵分解理论，提出了一个隐私保护支持向量机算法，该算法简单直接，无需利用安全多方计算技术，给出的分类器是公开的，但是并未揭露任何参与方的原始数据.最后利用矩阵分解理论证明了该算法的可行性.数值实验表明该算法是有效的，并且该算法的分类精度比Mangasrian的简约隐私保护支持向量机算法的分类精度高.16 山东科技大学博士学位论文1绪论第四，针对数据水平分布的情况，借助安全多方计算的加密技术，提出了一个隐私保护支持向量机算法，该算法给出的分类器是公开的，同样并未揭露任何参与方的原始数据.数值实验表明该算法的分类精度比Mangasrian给出的简约隐私保护支持向量机算法的分类精度高.最后利用矩阵分解理论证明了该算法的可行性.第五，针对数据任意分割的情况，利用水平分布的矩阵乘积的安全性策略，提出了一个隐私保护支持向量机算法，在未揭露任何参与方的原始数据的情况下给出了公开的分类器.该算法具有和未加隐私保护的经典支持向量机算法相同的精度.最后利用矩阵分解理论证明了算法的可行性和有效性.17 山东科技大学博士学位论文2支持向量机简化算法中支持向量与违背对的几何意义2支持向量机简化算法中支持向量与违背对的几何意义2.1引言[1，3，4，6，7]支持向量机是近年来机器学习研究的一项重大成果.由于SVM具有较为完美的数学形式、直观的几何解释和良好的泛化能力，它解决了神经网络结构难以确定与欠学习、过学习等方面的问题，避免了局部最优解，并且人为设定的参数少，便于实际应用，因此它迅速成为智能计算领域的研究热点之一，并成功地应用于许多分类和回归问题之中.支持向量机的训练算法实质上是求解一个凸二次规划，这需要计算和存储核矩阵函数，其大小与训练样本数的平方相关.随着样本数目的增多，所需要的内存增加.因此，研究有效的针对大规模训练样本集的SVM算法意义重大.支持向量能够充分描述整个训练样本集的特征,对它的划分等价于对整个样本集的划分.大多数情况下,支持向量只占训练样本集的很少一部分,支持向量的数量是影响最终分类速度的主要因素.因此减少分类函数中支持向量的数量成为研究支持向量机快速分类算法的目标,实现在不损失分类精度的前提下提高支持向量机的分类速度,在不影响分类精度的同时降低训练时间.所以，许多研究者通过寻找一包含较少支持向量的约简向量集代替原有的支持向量集，从而达到简化分类函数，提高分类速度的目的.许多研究者对简化算法的研究已经取得了一些成果.Osuna等人提出了分解算法，并[47,48,56,58]Light经过了一定的发展和改进；Joachims等基于Osuna的分解思想用软件SVM[49][50-55]实现了分解算法；Platt提出了SMO算法；文对SMO算法做了进一步的研究和[44-46]探讨，文也对简化算法做了改进.我们知道，求解SVM，即求解下面的凸二次规划问题：1TTminfQ()α=−αααe2αTst..yα=0(2.1)0,≤≤αCei=1,2,?,lT[65]其中Qy=yKxx(,)；K(,)xz=ϕϕ()()xz为核函数.文给出了求解支持向量机的一ijijij18 山东科技大学博士学位论文2支持向量机简化算法中支持向量与违背对的几何意义般简化训练算法的步骤：1步骤1设定优化变量初始值α，令k：=1.k步骤2如果α是优化问题(2.1)的最优解，即满足某种终止条件，则算法终止，否则，按照一定的工作集选择策略(如最大违背KKT对等策略)从训练样本集{1,2,?,}l(用样本序号代表训练样本)中选择包含两个或多个样本点的工作集Bl⊂{1,2,?,}.定义kkkNl={1,2,?,}B，α和α为α向量的部分分量，其下标分别在集合B和N中取值.BN步骤3求解以下关于α的优化问题：B1TTk⎡⎤QQBBBN⎡αBB⎤⎡TTα⎤min[αα()]⎢⎥⎢⎥⎢−[ee]⎥2BNkkBNαB⎣⎦QQNBNN⎣αNN⎦⎣α⎦(2.2)1TkTT=+ααQe[]−++Qαα常数2BBBBBBNNB⎧0,C≤≤αα⎪ijs..t⎨Tk.⎪yyα+=αα−y⎩iijjNNk+1求得优化变量α.Bk+1k步骤4令α=α，kk：=+1，转步骤2.NN注：求解(2.2)式的子问题，相当于求解关于SVM的原问题的如下子问题11T2min22ww++bC∑ξiiB∈Ts..tywii(xb+)1≥−∑Qijαξj−i,iB∈,jN∈ξ≥∈0,iB.i该简化算法中提出了最大违背KKT条件的对(i,j)的概念，而且根据该算法，我们知道在最后构造决策面时，只有支持向量起作用，所以找到支持向量，对于设计有效准确的大规模分类问题的支持向量机具有非常重要的意义.但是对于支持向量和最大违背KKT条件对(i,j)的几何意义，以及它们相对于迭代过程中的决策面的位置关系问题，没有给出明确的几何意义.基于这种考虑，本章对支持向量与相应乘子之间的关系做了深入的研究，并从几何上给出直观的解释；同时对最大违背KKT条件的对(i,j)的几何含19 山东科技大学博士学位论文2支持向量机简化算法中支持向量与违背对的几何意义义也做了进一步的探讨.本章的组织结构如下：2.2节对支持向量及其相应乘子之间的关系进行探讨，2.3节则对SVM的简化算法中终止条件进行研究和分析，给出了各种条件下的几何意义.2.4节给出了本章小结.2.2支持向量及其与相应乘子之间的关系2.2.1支持向量的含义线性可分SVM的原始问题的一般模型为l1Tmin2wwC+∑ξiwb,,ξi=1s.t.ywxb((⋅)+≥−)1ξiii,(2.3)ξ≥=0,il1,2,?,i其中C>0是一个惩罚参数.原始问题是凸二次规划,其可行域非空,因此问题必有解,即问题(2.3)关于(,)wb的解是存在的.为了求问题(2.3)的对偶问题,先构造其相应的Lagrange函数lll1TL(,,,,)wbξαγ=+−2wwC∑ξii∑∑α(((ywxii⋅))1)+b−+ξii−γξi,ii==11i=1其中α≥0和γ≥0.根据Wolfe对偶定义,对L关于wb,,ξ求梯度,即ii∇Lwb(,,,,)0,ξαγ=b∇Lwb(,,,,)0,ξαγ=w∇Lwb(,,,,)0.ξαγ=ξ则有llwy==∑∑αiiixyC,0ααii,=i+γi.ii==11然后将上面的极值条件代入Lagrange函数,对α求极大，则得到问题(2.3)的对偶问题为20 山东科技大学博士学位论文2支持向量机简化算法中支持向量与违背对的几何意义lllmax−⋅1∑∑yyααα(xx)+∑2ijijijiαij==11j=1lst..∑yiiα=0,i=10,≤≤=αCi1,2,?,l.i***因此，求解SVM的问题(2.1)即为(2.3)的对偶问题.综合上面的分析，设（w,,)bξ是问****题(2.3)的KKT点，设(,)αγ是相应的Lagrange乘子，则在（w,)b处的KKT条件为ll∗∗∗∗∗wyyC==∑∑αiiix,0ααii,=i+γi,(2.4)ii==11*****ywxbii((⋅+≥−))1ξξi,γii=0,(2.5)*******αξii(((yw⋅+−+=xi)b)1i))0,ξiii,α,γ≥=0,i1,2,?,l.(2.6)为分析支持向量与相应乘子之间的关系，首先给出支持向量的定义.[32]定义2.1(支持向量)考虑支持向量机中的原始问题(2.3).称输入xi为支持向量或T标准的支持向量，如果其对偶问题(2.1)有一个解α=(,,,)αα12"αl，它与输入xi对应的αi>0.如果对应的0<<αiC，称输入xi为界内的支持向量；如果对应的αi=C，称输入x为界上的支持向量.下面对支持向量的各种可能性作以分析.i2.2.2乘子αi的取值与支持向量之间的关系满足KKT条件的点可能就是最优点,所以一般选取最大违背KKT条件的样本点，对其求解相应的小规模的子问题，进行修正，逐渐逼近原问题的最优解.首先考虑问题(2.3)中ξ的含义,ξ是用来衡量一个样本点到它所属那类的超平面ii**ywxb((⋅+=))1的距离的大小,即iiξid=.||w||∗∗通过对式(2.4)-(2.6)分析,对正类点来说(负类点类似)，位于面ywxbii((⋅+=))1下方**的那些样本点,有ywxbii((⋅+>))1，由式(2.6)知，对应的αi=0.这些样本点不可能是21 山东科技大学博士学位论文2支持向量机简化算法中支持向量与违背对的几何意义支持向量.图2.1支持向量与Lagrangian乘子α之间的关系iFig2.1TherelationbetweenthesupportvectorsandLagrangianmultiplierαi**对于位于超平面ywxbii((⋅+=))1上的样本点，ξi=0.由互补松弛条件(2.5)可知,γi有三种可能：γi=0,0<<γiC或者γi=C.再由式(2.4)，可以得到αi也有这样三种**可能：αi=0,0<<αiC或者αi=C.所以位于超平面ybii((wx⋅)+=)1上的样本点可能不是支持向量,可能是界内的支持向量,也可能是界上的支持向量.∗∗**对于位于超平面ywxbii((⋅+=))1上方的样本点、位于超平面ywxbii((⋅+=))1****和决策面ywxbii((⋅+=))0之间的样本点、位于决策面ywxbii((⋅)+=)0和超平面****ywxb((⋅+=))−1之间的样本点、位于错分的负类样本点（满足()1wxb⋅+<−的样本iii点）中,都有对应的ξ>0,由式(2.5)知γ=0,再由式(2.4)知,α=C.所以这些样本点必iii为支持向量,而且一定为界上的支持向量.根据支持向量分类机算法，我们知道只有支持向量所对应的α才有效，对最后的结i果产生影响，而对应的大量的间隔外正确划分的样本点(即非支持向量)来说，它们是否参加训练，对最后结果并不影响.因此，可以酌情对这些样本点进行删减，从而达到简约训练样本集的目的.最优分类决策面仅由支持向量，即α≠0所对应的样本点来确定，i22 山东科技大学博士学位论文2支持向量机简化算法中支持向量与违背对的几何意义见图2.1，分类决策面是由分类间隔之上和之内的样本点，以及错分的样本点来决定的，其它的样本点对分类决策面的形成没有影响，支持向量的数量是影响最终分类速度的主要因素.仅仅训练支持向量就和训练整个数据集获得的分类决策面是一致的.2.3求解SVM的简化算法中终止条件的分析研究2.3.1简化算法的终止条件分析[96]针对问题(2.1)，对于求解SVM的一般简化算法，定义如下的指标集：RiC(){:α=<=αα,yiy1}{:0∪<=,−1},iiiiSiC(){:α=<=αα,y−1}{:0∪<=iy,1},iiiiIi(){:argα=i∈−maxyhh∇f()}α，hR∈()αJi(){:argα=i∈−minyhh∇f()}α.hS∈()α则有RS()(){0α∩αα=<
微信/支付宝扫码支付下载
扫描成功：
请在手机上确认支付
绑定手机
强烈建议绑定手机号，方便下次登录再次下载，查询订单记录
