支持向量机的若干算法研究

《支持向量机的若干算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

分类号：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α∩αα=<−∇yf()α.(2.8)iR∈()αjS∈()α即有−∇yf()α=−yQ[(α)1]−iiiil=−−yyik[(∑αiykiKx,xk)1]k=1l=−yik∑αyKxxk(,)ik.k=1同理l−∇yfjj()α=yjk−∑αyKxxk(,)jk.k=1这样(2.8)式即为llyik−∑αyKxxk(,)ik>−yjk∑αyKxxk(,)jk.k=1k=1iR∈()αjS∈()α进一步，如果对(,)ij满足−∇yfiijj()α>−∇yf()α，(2.9)iI∈()αjJ∈()α则称这样的对(,)ij为最大违背KKT条件的对(MaximumViolatingPair,简称MVP).下面，我们对线性情形分析其几何意义，对于非线性情形，可以类似分析.设α为24 山东科技大学博士学位论文2支持向量机简化算法中支持向量与违背对的几何意义问题(2.1)的一个可行点，则有−∇yf()α=−yQ[()1]α−iiiil=−yyik[(∑αiykxxi,k)−1]k=1l=−yyik∑αk(,)xxikk=1l=−(,∑αkkkyyxxi)+i.(2.10)k=1l令Wy=∑αkkkx,Fyfii=∇()αi,有k=1TFWxy=−iii和TF=Wxy−jjj成立，则(2.8),(2.9)式分别等价于下面两式：Fij0},−+UxiUxa(){=∈():<0},UxiUxa(){=∈():>0}.ii根据这种分解，可以得到下面的KKT条件.**定理3.2.1(最优性条件)点x∈F是问题(3.1)的一个稳定点，当且仅当存在λ满足下面的条件：((*∇fx))i+−λ*(≥−∀∈iLxUx*)∪(*),ai((*∇fx))i−+λ*(≤−∀∈iLxUx*)∪(*),(3.5)ai((*∇fx))i+−λ*(=−∀∉iLxUx*)∪(*).ai利用集合F的特殊结构，可以给出KKT条件的等价形式，这个等价形式在后面算法中是有用的.为此，先引入下面的指标集：+−Rx()=∪∪()α−yf∇()α，(3.8)iijjiI∈()αjJ∈()α则对(,)ij为最大违背KKT条件的对.最大违背对选择方法(MaximalViolatingPair,简称MVP)：步骤1选择iI∈()α,jJ∈()α,使得(3.8)式成立.注：这样选择的违背对即为最大违背对(,)ij，其等价于求解下面的子问题(,)argminSub()ij=B，BB:||2=其中kTSub()Bf=∇min(α)dBBdBTst..yd=0,BBkdi≥=0,fα0,s∈B,sskdi≤0,fCα=∈,sB,ss−≤≤11ds,.∈Bs步骤2根据前面第二章给出的分解算法求得分类决策面.3.3.1.2τ违背原则[54]给定一个容许参数τ>0，指标集定义如上.Keerthi等给出了问题(3.1)的KKT条件：max−yf∇≤−(α**)minyf∇+(ατ)hhhh，**hR∈()αhS∈()α满足该条件的解α*称为τ最优解.同时，称满足条件−∇yf()α>−∇yf()ατ+(3.9)ikijkjiR∈()αkjS∈()αk的违背对为α处的τ违背对.k36 山东科技大学博士学位论文3大规模支持向量机的一类新的收敛的分解算法τ违背对选择方法(τ-ViolatingPair)步骤1选择iR∈()α,jS∈()α,使得(3.9)式成立.步骤2根据第二章给出的分解算法求得分类决策面.3.3.2利用二阶信息确定工作集的方法为了使目标函数下降最大，前面的最大违背对规则主要是利用一阶信息来使目标函数下降最大.事实上，对目标函数进行泰勒一阶展开得到kkkTkkT(fαα+≈df)()+∇fdf()αα=()+∇fd()α，BB即有kkkT(fααα+−df)()≈∇f()d.(3.10)BBkkT又如果α不是最优解，则在该点处有∇fd()α<0，这样问题(3.7)中求目标函数的最BB小值也就是寻找一个可行下降方向使目标函数下降最大.由于求解SVM中的凸二次规划中的目标函数f是二次的，所以对目标函数进行二阶泰勒展开后有kkkT1T2kf(ααα+−df)()=∇f()ddfd+∇()α2(3.11)kT12k=∇f()ααdfd+∇().BB2BBBkT12k这样，通过对目标函数求最小值，也就是对∇+f()ααdfd∇()求最小值，相对BB2BBB比一阶信息更为精确，使目标函数下降最大.使用二阶信息的工作集选择方法(Workingsetselectionusingsecondinformation)：步骤1选择iI∈()α.步骤2类似于一阶信息选择的最大违背对规则，选取jJ∈()α，且(,)ij是通过求解下面的子问题而得到，即(,)ij=argminSub(Bit={,})，BB:||2=其中37 山东科技大学博士学位论文3大规模支持向量机的一类新的收敛的分解算法1Tk2kTSub()B=∇df(αα)dfd+∇()min2BBBBBBdBTst..yd=0,BB(3.12)di≥=0,fα0,s∈B,sskdi≤=0,fCα,s∈B.ss步骤3根据第二章给出的分解算法求得分类决策面.3.3.3带参数σ的一般的确定工作集的方法[61]众所周知，Lin证明了，如果一个违背对是最大违背对，那么这样选择的工作集构成的分解算法是收敛的.然而，如果工作集选择的集合B中的对不是最大违背对，那么这样的SMO算法或者分解算法是不是能收敛到一个稳定点呢？针对这样的工作集的选[99]择问题，Chen在文献中给出了具体的分析和证明，他们证明了只要这个违背对是一个“充分”的违背对，那么这样选择的工作集构成的算法能够收敛到一个稳定点.带参数σ的一般的工作集选择方法1：步骤1选择适合所有迭代的一个固定参数01<σ≤.步骤2选择iI∈()α，jJ∈()α且满足kk−∇yf()αα+∇yf()≥σ(()mαα−M())0>.iijj其中，my()maxα=−∇f(),αMy()minα=−∇f()α.iiiiiR∈()αiS∈()α步骤3根据第二章给出的分解算法求得分类决策面.带参数σ的一般的工作集选择方法2（常数因子违背对推广）：11步骤1设hR:→R是满足下列条件的函数.a)h在x≥0时严格递减；b)()hx≤∀≥xx,0,(0)h=0.步骤2选择iI∈()α，jJ∈()α满足kk−∇yf()αααα+∇yf()≥hm(()−M())0>.(3.13)iijj其中，my()maxα=−∇f(),αMy()minα=−∇f()α.iiiiiR∈()αiS∈()α38 山东科技大学博士学位论文3大规模支持向量机的一类新的收敛的分解算法步骤3根据第二章给出的分解算法求得分类决策面.注：条件hx()≤x保证至少有一个对(,)ij满足(3.13)式.显然，hx()=σx，01<≤σ也能满足要求，则此方法即为上面的带参数σ的一般的工作集选择方法1.不过，一般来说，函数hx()具有较复杂的形式.例如，如果kkkkkkhm(()()αα−≡M)min(m()()αααα−M,()()m−M)，(3.14)那么(3.14)满足上述条件.[99]文对上述方法2的收敛性进行了分析.[99]说明：对于3.3.1和3.3.2小节中的核矩阵不是正定的时候，文献给出了处理的技巧，即借助一个小正数τ，在分解算法中求解子问题的时候增加后缀项τ−aijkk22((αα−+−)(αα))，iijj4从而得到算法的收敛性.3.3.4基于可行方向确定工作集的方法工作集指标集合每次迭代都要修正.当分解算法找到子问题的一个最优解时，那么目标函数一定是严格下降的，而且在合适的假定下，算法收敛到问题的最优解.分解算法的最弱项是它不能一起考虑所有的变量.然而，工作数据收集的好的集合可能和最优化问题的快速收敛相逆.另外，如果工作集选择得不合适，即使目标函数值严格下降，算法也可能不收敛.这样工作集的选择问题是SVM分解算法中一个很重要的问题.在目前存在的算法中，Osuna和Saunders通过选择违背KKT条件的对来选择工作集；Platt的SMO算法限制工作集的势为2，SMO的优点是使得子问题成为一个小规模的问题，不需要借助优化软件可以解析求解，其工作集选择包括一些试探；Joachims基于Zoutendijk的方法，限制q是一个偶数，提出了一种方法.这种方法以系统的方式集中于最优化问题.更多的软件，如SVMTorch,Libsvm，继Zoachims的工作集选择方法（设[56]q=2）.最近，Hsu和Lin提出一类工作集选择策略，可以使算法比其它算法有较快的收敛速度.他们的方法大体上应用到Mangasarian和Musicant、Fries等（最优化问题不包括线性约束）提出的SVM模型上.他们从KKT条件中选择q2个最违背的元素，在α是自由(0<<αC)的变量中选择q2个最小违背的元素.这个方法总是试图把自由ii39 山东科技大学博士学位论文3大规模支持向量机的一类新的收敛的分解算法变量推向边界变量，同时保持自由变量数很小.Joachims的方法如下，基于Zoutendijk的方法，求解优化问题使用的策略：步骤1将yf∇()α按照下降次序排序后，把所有对应的()α分类整理；ikiki步骤2相继从下面的指标集中选择处于最大、次大值等等的q2个元素.即从0()<<αC，或者()0α==ify−1，或者()α=Cify=1和集合dy=−；kikikiii步骤3类似地从上面排列的底部开始依次选择q2个元素.选择的下标集为0()<<αC，或者()0α==ify1，或者()α=Cify=−1和集合dy=.kikikiii其中d的值只用来选择工作集，q是偶数.对实际运算而言，这个算法花费至多Olq()运算，是可以接受的.如果我们考虑α*是子问题的最优解，那么下面的KKT条件成立：∇+fb(*)αyi>0f(*)α=0，iii∇+f(*)αby<0if(*)α=C，iii∇+f(*)αby=<<0if0(*)αC.iii下面分析一下Joachims的方法如何从那些元素中选取最违背的边界变量.首先考虑第k次迭代()0α=时违背KKT条件的对.当()0α=时，记∇fb(*)α+≤y0违背了kikiiiKKT条件.这样，如果y=−1，yf∇(*)α+≥b0，或者如果y=1时，yf∇+(*)αb≤0iiiiii都违背了KKT条件.而Joachims提出，()α根据yf∇()α的大小按照降序排列归类后，kiiki从前到后选择y=−1的那些α，或者从后到前选择y=1的那些α.注意到b对所有的ikik变量是相同的，然而它不是常数，每次迭代得重新计算.当()0α=是从顶部选择的，ki那么()α是最大违背类别属性为-1的变量.当()0α=是从底部选择的，那么()α是最kikiki大违背类别属性为1的变量.类似地，如果选择()α=C，它们也是分别违背各类别的ki变量.但是，不容易称0()<<αC最违背KKT条件.由于分解算法最弱的部分是不可ki能在每次迭代考虑所有的变量，所以自由变量太多会引起很大的困难.这是因为，如果一个分量被恰当确定为C或0，就不会有数值精度的问题了.然而，一般来说，如果不一起考虑所有的变量，不容易确定一个自由变量的值.40 山东科技大学博士学位论文3大规模支持向量机的一类新的收敛的分解算法Hsu和Lin的方法增加了一些自由变量，其中这些自由变量对应的|(*∇+fα)by|是iiJoachims算法中最小的.从KKT条件来看，稍微违背KKT条件的自由变量就会增加到Joachims的工作集中.对任何∇+fb(*)αy<0的自由变量()α，自由变量()α显示了上iikiki界变量的特性.类似地，对任何∇+fb(*)αy>0的自由变量()α，自由变量()α显示了iikiki下界变量的特性.相应于最小的|(*∇fα)+by|的或者上界或者下界变量比其它变量对ii应的样本更接近于超平面.从下次迭代选出的对应最小值|(*∇fα)+by|的自由变量中ii的一部分要么是上界要么是下界变量，并且保持自由变量数最小.这是因为两分类中接近超平面的那些变量在下次迭代被选出.另外，超平面不可能根据通过整个训练集来摆动.Joachims的工作集选择方法不考虑这个标准，所以超平面可能根据整个训练集来摆动.为此，Hsu和Lin的方法比Joachims的方法要快些.对于Hsu和Lin提出的工作集，我们增加一些最大的∇f(*)α+by相应的变量.我们ii的思想是那些对应∇+fb(*)αy0的自由变量可能是下次迭代中的下界变量.基于此，ii给出下面的算法：1）设r是第k次迭代的自由变量数；2）设qqqq=++，其中qqr+≤且q是一个偶数；1231233）从0()<<αC的那些分量中，选取使得|∇f(*)α+=by|,i1,2,?,l最小的q个元kiii1素；4）从rq−个变量中选取使得∇f(*)α+=byi,1,2,,?l最大的q个元素；1ii25）从余下的指标集中通过SVMLight规则选取q个元素.3当q=0时，该工作集选择方法就成为Hsu和Lin的算法.下面说明这个方法要比他2们的方法好.确定qqq,,的值也是工作集选择中一个重要的任务.问题的收敛性依赖这些值的选123Light择.我们根据所有的选择策略来确定它们的值.首先解释SVM的工作集选择策略，这种方法的思想是找到一个最深入的只含有q个分量的可行下降方向，使得目前的迭代更341 山东科技大学博士学位论文3大规模支持向量机的一类新的收敛的分解算法多的朝着f()α的最小值方向.Joachims的方法有一个好的特性，他的方法从不同的类别中选择变量.然而，其它的选择策略没有这个标准.如果工作集中的变量在同一个类别，求解的子问题成为一个可分的问题.由此，ξ=0,iB∈意味着α一般不等于C.那么，iB很难确定正确的有界变量，且目标函数的下降变得缓慢.Hsu和Lin方法在q个元素中增3加了q个元素，其中q个元素是选择最小的|(*∇fα)+by|而得到.他们的方法总是试图11ii把自由变量换为边界变量，且保持自由变量数目较少.如果在迭代过程中，很多自由变量在最终的解中仍然是自由变量，那么因为这种方法错把许多自由变量当作边界变量，所以带有较大的q和较小的q的学习方法收敛得很慢.这可能引起另一个问题，也就是13一类的元素比另一类元素多得多.在此情形，许多变量可能被误作为边界变量，或者子Light问题成为一个具有可分数据的问题.然而，SVM工作集选择方法具有很好的衡量标准使得各类变量的目标函数f()α下降，并且从两类中选择变量.如果q很大，许多计算的2变量变成0，需要重新计算变量.在迭代过程中，如果工作集选择中很少有自由变量被变成零，那么q的值将会足够小.考虑这种情况，一个好的大的工作集应该是有足够大的2值q，考虑大的值q，最后考虑q的值.3123.3.5带缓存缩水技术的确定工作集的方法缓存技术：存储一些最近使用的部分核函数Q，节省核估计的时间.ij缩水技术（shrinkingtechnique）：是另一种加快SMO算法的执行速度，它主要是不考虑一些边界变量而求解最优化问题.可行方向策略和核缓存技术可以改进SMO的执行，但在某种情形可能冲突.当缓存的矩阵相对于问题的规模较小时，缓存中最大违背对的命中精度可能非常低.因为缓存技术是以LRU方式保持，缓存中的项可能会经常修正.这样，SMO可能并不能从核缓存中获益.另一方面，最大违背对在分解算法中扮演非常重要的角色.当使用这样的对作为工作集时，该算法的收敛性得到充分证明而且具有较高的收敛率.然而，如果B不是最大违背对，那么SMO类算法是否收敛到一个稳定点还不确定.基于这样的考虑，提出一个新的工作集选择策略，不仅保证收敛，而且保证收敛率和缓存的平衡.首先，定义42 山东科技大学博士学位论文3大规模支持向量机的一类新的收敛的分解算法I={|tQincache}，cachetR()α=RI()α∩，cachecacheSS()()α=α∩I，cachecachemy()maxα=−∇f()α，iiiR∈()αMy()minα=−∇f()α，iiis∈()αmy()maxα=−∇f()α，cacheiiiR∈cache()αMy()minα=−∇f()α.cacheiiiS∈cache()α那么，一个新的工作集选择方法如下：根据可行方向策略，分别对应m()α和M()α寻找α和α.ij如果mM()α−≤()αε，工作集设为φ，否则，如果ijI,∈或I是空集，设工作集为(,)ij；cachecache否则，扫描缓存来寻找α和α，它们分别对应于m()α和M()α.mncachecache如果mMu()α−≥−()(()αααmM())，设工作集为(,)mn；否则设工作集为(,)ij.II其中uR:→R是任意满足下列条件的函数1）当x≥0时，u是严格增函数，(3.15a)2）uxxx(),≤∀≥0,(0)0u=.(3.15b)k为简化符号，使用α代替α.[99]函数u是为保证所选的对可以连接到最大违背对.如果函数u满足(3.15)，文献保证了算法是收敛的.使用函数u的另一个作用是平衡收敛率和缓存技术.不使用最大违背对作为工作集选择的策略，而用一个“充分违背”的对代替下降算法的率替代命中缓存43 山东科技大学博士学位论文3大规模支持向量机的一类新的收敛的分解算法的精度.这个工作集的复杂性为Ol(2)，近似为WSS1的二倍，显然，它并没有特别大地增加时间的花费.另，Lucidi的一种方法，称为混合方法（简称HMVP），具体如下：0步骤1给定可行点α，实数σ>0，整数p≥1；步骤2如果算法不终止，按照最大违背对规则选择kk()ik∈∈I(),()αjkJ()α；k步骤3求解相应的子问题(3.2)，得解α；____k+1步骤4如果0<αik()0.这样由可行方向集(3.17)i的定义，有d>0.如果iSx∈(),可以得到a<0.同样根据(3.17)的定义有d>0.iii另一方面，对任意的iUx∈(),由式(3.17),如果iRx∈(),那么可以得到a<0.于是i根据(3.17)的定义，有d<0.如果iSx∈(),有a>0，这样根据(3.17)式可以得到d<0.iii由上面的结论，根据(3.18)，再由Dx()0的定义，可知dRiijj11,,,,,""qq∈n是x0处的一个可行方向.证毕.*定理3.4.2可行点x是问题(3.1)的一个稳定点，当且仅当∇≥f(*)xdTiijj11,,,,,??qq0,∀diijj11,,,,,??qq∈Dx(*)RS.(3.19)证明由可行方向(3.16)的定义,根据定理3.2.2,我们有TTTT∇∇fx(*)∇∇fx(*)fx(*)fx(*)∇=fxd(*)Tiijj11,,,,,??qq(ij11+??+ijqq)(−++)aaaaii11qqjjTTTT∇∇fx(*)fx(*)∇∇fx(*)fx(*)ij11ijqq=()−+?+−()aaaaij11ijqq≥0.证毕.下面的定理证明了，对任意的可行点x，集合Dx()包含了所有的可行方向，是集RS合Dx()的生成器._定理3.4.3给定x∈F,我们有__DxDx()⊂(),(3.20)RS__coneD((x))(=Dx).(3.21)RS45 山东科技大学博士学位论文3大规模支持向量机的一类新的收敛的分解算法证明条件(3.20)是定理3.4.1的直接结果.为证明(3.21)，根据式(3.20)，只需证明如__果dDx∈()，则d∈coneD{()x}.RS____用反证法.假设结论不正确，即存在一个向量dDx∈()，但是d∉coneD{()x}.则RS可知线性方程组__|(DxRS)|pdd=∑μp,p=1_μ≥=0,pD1,2,?,|()|,xpRS_pn无解，其中dDx∈().利用Fakas引理，存在向量cR∈使得RS_Tppcd≥∀∈0,dDx(),(3.22)RS_Tcd<0.(3.23)T现在我们考虑线性函数Fxcx()=和下面的凸规划问题TminFx()=cxTst..axb=,(3.24)lxu≤≤.这样条件(3.19)可以记作__Tpp∇≥Fxd()0,∀d∈Dx().(3.25)RS___利用(3.25)和定理3.4.2,可知x是问题(3.24)的最优解.另一方面，d是x处的可行方向，_____T由(3.23)，我们有∇0，有||dM||≤；kTk(2)对所有的k,有∇0,(0,1)δ∈,(0,1/2)ρ∈,(,1)σ∈ρ，初始的步长kkα=min{γα,}.k步骤1设λα==,0j.步骤2如果kkkkTk(fxdf+≤+λρ)()xλ∇f()xd,(3.34)kTk+1kTk|()|∇≤fxd−σ∇f()xd,(3.35)k那么λ=λ，算法停止.步骤3令λ==δλ,1j：j+，返回到步骤2.[80]由文,很容易得到下面的定理.kk定理3.5.1设{}x是可行集F中的一个可行点列，{}d是满足假设3.5.1的一个方向序列，那么有k(1)对每次迭代k，在有限步内算法A能确定一个步长λ，使得条件(3.34)和(3.35)成立，即有kkkkkkTkf()xdf+≤+λρ(x)(λ∇fx)d,(3.36)kTk+1kTk|()|∇≤fxd−σ∇f()xd.(3.37)_k(2)如果点列{}x收敛到x，且有kkkklim((fx)−fx(+=λd))0,(3.38)k→∞49 山东科技大学博士学位论文3大规模支持向量机的一类新的收敛的分解算法那么kkTklimγ∇fxd()=0,(3.39)k→∞k其中γ是由(3.33)确定.3.6基于可行方向选择的新的分解算法现在我们来给出新的分解算法的模型，这个新的算法是基于带有q个分量的可行方kk向提出的.第3.4小节的结果表明，给定任意可行点x，该点处的可行方向集Dx()可以k由具有q个非零分量构成的可行方向集来产生.特别地，定理3.4.3证明了集合Dx()包RSk含了Dx()的所有的方向.对某个指标组{,,}{(),,()}iii??=kik，在假设11qqklxu<<(p=1,2,?,q)成立的情况下，定理3.4.4给出了生成整个可行方向集的新的iiippp可行方向集Dxik1(),,()?ikq()k.这样，集合Dx()k和Dxik1(),,()?ikq()k都包含了“充分”的可行方RSk2向集的信息.在最差的情形，Dx()中有nn(1−−)(21"nq+)/(!q)个元素，然而集合RSik1(),,()?ikqkDx()则有2(nnq−−)(21)/!?nq+q个向量.因此，对大规模问题，为研究基于ik1(),,()?ikqk可行方向的方法，利用集合Dx()具有很大的优势.进一步，我们利用一些策略k改进我们的方法.若目前的可行点x使得(3.26)成立，我们任意选择一个“合适”的指标集kik(),,?ik()，从而得到一个具有“自由”的分量的组构成的解x，这样我们求解下1qik1(),,()?ikq面的问题:kTminγ∇fxd()nγ∈∈RdR,st..0≤≤γγ,ukxdF+∈γ,(3.40)ik1(),,()?ikqkdD∈(),x其中γ是一个给定的正数，并且uDxik11(),,()??ikqq(){kn=∈∈dpk(),,(),(),,()pkik1?ikqR:(),,()pk?pkR()}xk1q(3.41)ik11(),,(),(),,()??ikpkqqpknk∪∈∈{dR:(),,()pk?pkS()}.x1qk易知问题(3.40)有解.(3.40)的合理定义是在有q个分量的可行方向集Dx()的生成器中确定出局部最可能下降的那个方向.用(,)γd表示问题(3.40)的解，则γ是沿着方向kkk50 山东科技大学博士学位论文3大规模支持向量机的一类新的收敛的分解算法kd的最大可行步长和给定正数γ之间的最小的那个数.下面我们给出基于可行方向选u择的分解算法.算法3.6.1(可行方向的分解算法(FDD)算法)：0初始数据：给定可行点x使得对某个下标组p,,??pn∈{1,2,,}1q有_0lxu<<；η>0,0γ>.pp111,,???qqqpp,,pp,,u初始化令k：=0.如果终止条件不满足，则执行下面的步骤1-步骤7.kk步骤1任意选择一个指标组ik(),,?ikRx()∈∩()Sx().1qDxik1(),,()?ikq()kk步骤2设是由式(3.41)定义的点x处的可行方向集，则选择d,γ使kk得kkTkkTγγ∇=∇f()xdminfxd()nγ∈∈RdR,st..0≤≤γγ,u(3.42)kxdF+∈γ,ik1(),,()?ikqkdD∈(),x成立.kTkkkk步骤3如果∇≥fxd()0，停止；否则根据Wolfe线搜索算法WLS(xd,,β)k来计算步长λ.~k+1~k+1kkkk步骤4设x=+xdλ，计算参考值f=f()x.ref_k+1k+1k步骤5找到x∈F使得lx<0,*Fλ=⎨k⎪⎩γF,.其它~k+1kk*于是,根据Wolfe规则的收敛特性得到保持，在步骤4可以设x=+xdλ.最后，我k+1们指出在步骤5，可以以任意方式定义修正点x只要保证公式(3.26)满足并且k+1kf()x≤f.因此，原则上，我们可以从理论和实践的角度任意选择一个工作集.ref3.7收敛性分析为了证明算法3.6.1的收敛性，首先做如下的假设.令V表示带有q个“自由”非零分量的可行点集，即VxFR=∈{:()xS∩()x有少于q个元素},0对任何可行的初始点x,引入下面的水平集00LxFf=∈{:(xf)(≤x).0假设3.7.1LV∩=φ.假设3.7.1是为保证该算法产生的每个迭代点至少有q个“自由”的分量，也就是说，条件(3.26)必须满足.下面的定理证明了我们提出算法的收敛性.kk定理3.7.1设{}x是由算法产生的点列，如果假设3.7.1成立，那么，点列{}x的每个极限点是问题(3.1)的稳定点.kk+1k证明由算法3.5.1可知，对所有的k≥0，都有f()()xf≤x.于是点列{}x属于52 山东科技大学博士学位论文3大规模支持向量机的一类新的收敛的分解算法_0k水平集L.设x是点列{}x的任意极限点，即存在一个无限子集K⊂{0,1,?,}使得对____kkKk∈→,∞都有x→x.由假设3.7.1,可知x∉V，从而存在一个指标组ix(),,()"ix1q满足__ix(),,()?ixRxSx∈∩()().1q所以，根据定理3.4.4,有__ii1,,?qconeD{(x)}=Dx()._下面用反证法.假设x不是问题(3.1)的稳定点，那么由定理3.4.5可知,存在可行方_ii1,,?q向dDx'(∈)使得T∇fxd()'0<.(3.43)由定义(3.41),可得Dxikik11(),,()??qq(){kn=∈∈dpk(),,(),(),,()pkikik1?qR:(),,()()}pk?pkRxk1qik11(),,(),(),,()??ikpkqqpknk∪∈∈{:dRp(k),?,p(k)S(x)}.1q__kk进一步，根据定理3.2.3，对kK∈，当k充分大时，有R()xR⊂()x和Sx()⊂Sx().从_ii11,,??qqii,,k而可得DxDx()⊂()，因此ii1,,?qkdDx'(∈).(3.44)_kk设γ是从x开始的沿着方向d'的最大的可行步长.由式(3.43)和(3.44)，可以得到步骤2k所选的方向d'和步长γ使得_kkTkkγγ∇fxd()≤，x的类别为正，否则为负类.为求解这个优化问题，我们常常求解它的对偶问题来减少计算量min1α'Qeαα−'2αst..0≤≤αC,i(4.2)m∑dimiiα==0,1,2,?,，i=1其中d和α分别对应一个数据向量x的类标签和系数.系数变量α可以通过求解这个对iii偶问题来计算得到，其中Qij=K(xi,xj)didj，对于线性SVM，核函数K(xi,xj)=xi⋅xj，对于非线性SVM，可以应用非线性核Kxx(,).例如，ij2⎛⎞||xx−||ijKxx(,)expij=−⎜⎟⎜⎟.⎝⎠gmm权向量wd=∑αiiix和分类决策函数f()xd=∑αiiK(xi⋅+x)b也可类似地得到.进一i=1i=1步的了解可参看文献[1].4.3垂直划分数据的不带多方安全计算的隐私保护线性和非线性分类器m×n矩阵A被分成q个垂直分块nn,,,?n，其中nn+++=?nn，也就是12q12q说A=(,,,)AA12?Aq，其中Ai是mn×i矩阵.A中的每个列代表的块的数据由一个实体拥有，这个实体不愿公开、和其它实体共享自己的数据.假定这q个实体对每个数据的类别属性达成一致，即Do=−11r，im=1,2,?,.ii59 山东科技大学博士学位论文4不带安全多方计算的数据垂直划分的隐私保护支持向量机算法SVM模型是由核矩阵Kxx(,)来确定，而核矩阵又由整体数据的Gram矩阵确定.对ij线性的核矩阵，利用矩阵理论，我们可以得到下面的公式：12qKKK=+++=?KAA''⎛⎞A1⎜⎟'⎜⎟A2=()AA?A12q⎜⎟(4.3)@⎜⎟⎜⎟A'⎝⎠q'''=+++AAAA?AA.1122qq一些常用的非线性核也可以由Gram矩阵计算得到：多项式核可以由数据向量的点积表q示(即Kxx(,)((=⋅+xx)1).径向基(RBF)核矩阵也可以由数据向量的点积表示，即有ijij2⎛⎞||xx−||ijKxx(,)exp=−⎜⎟ij⎜⎟g⎝⎠⎛⎞|2xx⋅−⋅+⋅xxxx|iiijjj=−exp⎜⎟.⎝⎠g这样，如果不揭露原始数据得到全部数据的Gram矩阵，就可以不揭露原始数据而得到核矩阵.下面我们建立PPSVM算法.以下的结论说明我们计算的全部数据的Gram矩阵是安全的.引理4.3.1在公式(4.3)中，设非零矩阵A是nn×矩阵，且满足AA'=C，那么矩阵A是不可解的或不唯一的.证明：由CA'(')'=AA==AC'，可知C是一个是对称矩阵.n对任意给定的向量X∈R，X≠0，我们有X'AA'X=(A'X)'(AX)≥0，(4.4)所以矩阵C是一个半正定矩阵.设λ12,,,λλ?n是矩阵C的特征值，那么λi≥0.根据矩阵分解理论，存在正交矩阵T使得60 山东科技大学博士学位论文4不带安全多方计算的数据垂直划分的隐私保护支持向量机算法λ⎛⎞λλ⎛⎞⎛⎞1⎜⎟11⎜⎟⎜⎟λ⎜⎟λλ⎜⎟CT==''⎜⎟2TT22TLL='，(4.5)⎜⎟⎜⎟⎜⎟BBB⎜⎟⎜⎟⎜⎟λ⎜⎟⎜⎟⎝⎠nλλ⎝⎠nn⎝⎠⎛⎞λ1⎜⎟⎜⎟λ其中2是一个n×n矩阵.在(4.5)式中，交换λ和λ的顺序，则矩阵L不L=⎜⎟ij⎜⎟B⎜⎟λ⎝⎠n唯一.另外，如果所有的特征值一样，也可以交换矩阵T中的特征向量的次序.这样，矩阵A不能从矩阵方程AA'=C中求解出.证毕.根据上面的引理，容易得到下面的定理.定理4.3.1设非零矩阵A满足AA'=C，则矩阵A是不可解的或是不唯一的.证明：只需要证明结论对于mn≤成立，如果mn≥可以得到类似的结论.设AAA=()，其中A是mm×矩阵，A为mnm×()−矩阵.由矩阵方程AAC'=，1212可以得到⎛A1'⎞C=(A1A2)⎜⎜⎟⎟=A1A1'+A2A2'.(4.6)A'⎝2⎠'由引理4.3.1，给定AA，得到的A并不唯一.这样，由(4.6)式，根据矩阵方程AA'=C，111''甚至不知道AA或AA，矩阵AAA=()是不唯一的.证毕.112212'这个定理说明了，如果每个实体只给出他们自己的Gram矩阵AA，那么他们的原jj'始数据矩阵A是无从得知的.这样，就可以通过对每个实体j公开的矩阵AA求和得到jjj整体数据的Gram矩阵.从而核矩阵可以由整体的Gram矩阵计算得到.在隐藏原始数据的过程中，并没有采用安全多方计算的技术.4.3.1线性隐私保护支持向量机算法下面给出线性隐私保护支持向量机算法.'步骤1每个实体j公开自己的局部Gram矩阵AA，这并不暴露A，但是可以使得jjj公开计算得到整体数据的Gram矩阵，从而可以得到核矩阵：61 山东科技大学博士学位论文4不带安全多方计算的数据垂直划分的隐私保护支持向量机算法'''KAA(,')==+++AAAAAA'?AA.(4.7)1122qq步骤2通过下面标准的SVM算法，公开计算线性分类器x'Aw+b=0.min1α'Qeαα−'2αst..0≤≤αiC,m∑dimiiα==0,1,2,?,，i=1n'步骤3对每个新的样本点x∈R，每个实体公开xA，得到如下的线性分类器jjxAwbxAxA''+=(''''11+22++?xAwbqq'')+=0,(4.8)然后根据x'Awb+的符号可以确定所给定样本点x的类别.注意到上面的算法中每个实体j并没有揭示出自己拥有的数据A，也没有暴露新的j样本点x的原始数据信息.而在不知道具体的A只给出AA'是不可能唯一确定出A的.jjj''类似地，不知道A只给出xA也不可能唯一确定出x.下面我们来看非线性分类算法.jjjj4.3.2非线性隐私保护支持向量机算法类似线性分类器的方法，我们给出非线性隐私保护支持向量机的算法.'步骤1每个实体j公开自己的局部Gram矩阵AA，这并不暴露A，但是可以使得jjj公开计算得到整体数据的Gram矩阵，从而可以得到核矩阵：'''KAA(,')==+++AAAAAA'?AA.1122qq步骤2根据步1的全局Gram矩阵计算出非线性核矩阵KAA(,').步骤3通过下面标准的SVM算法，公开计算非线性分类器KxAwb(',')+=0.min1α'Qeαα−'2αst..0≤≤αiC,m∑dimiiα==0,1,2,?,.i=1n''步骤4对每个新的样本点x∈R，每个实体公开KxA(,)，得到如下的线性分类器jj62 山东科技大学博士学位论文4不带安全多方计算的数据垂直划分的隐私保护支持向量机算法KxAwb(',')+=((',KxAKxA')⊗⊗(',')"⊗+KxAwb(','))1122qq(4.9)=0,其中⊗能通过局部核矩阵得到全局核矩阵KxA(',')，则根据KxAwb(',)+的符号可以确定所给定样本点x的类别.在上面的算法中，注意到没有一个实体j揭露自己的数据集A，也不揭露新样本点j'x的任何信息.只给定核阵KAA(,)，不知道矩阵A的情况下，不可能计算出唯一的矩jjjj''阵A.同样的道理，根据KxA(,)不知道A的情况下，也不可能计算出x.jjjjj4.4数值实验本节给出所提出的隐私保护支持向量机算法的数值实验结果.所有的数值实验均在个人电脑上运行实现，个人电脑的配置如下：(4)CPU:奔腾IV3.06GHz;(5)内存：512M;(6)操作系统：WindowsXPSP3.本节的实验中，我们从MachineLearningRepository的UCI数据集中选取Breast-cancer-wisconsin和Heart_scale数据集来进行测试，其中Breast-cancer-wisconsin数据集包含683个样本，两个类别，9个属性.Ionosphere数据集包含351个样本，35个属性，参数C=100,使用线性核来测试算法的有效性.Breast-cancer数据集是来源于Wisonsin医学院，由WilliamH.Wolberg博士提供.求解标准SVM算法利用的是libsvm软件包.在实验中，假定Breast-cancer-wisconsin数据集中的数据是垂直分布的，分别由两个实体所持有.其中实体E所占有的数据矩阵维数为6835×，即持有数据集1Breast-cancer-wisconsin中的前5列数据，实体E所占有的数据矩阵维数为6834×，即持2有数据集Breast-cancer-wisconsin中的第6列至第9列的数据.假定Ionosphere数据集中的数据也是垂直分布的，分别由5个实体所持有.参照Mangasarian[127]给出的简约隐私保护支持向量机算法的结果，我们给出了本章提出的PPSVM算法和简约PPSVM算法63 山东科技大学博士学位论文4不带安全多方计算的数据垂直划分的隐私保护支持向量机算法确定分类器对数据分类的精度比较.数值实验结果如表4.1所示，表4.1标准SVM算法和简约PPSVM算法的比较结果Table4.1ComparisionbetweenstandardSVMalgorithmandReducedPPSVMalgorithm数据集(维数m,n)算法分类精度Mangasarian的简约PPSVM算法91.17%Ionosphere()mn==351,35隐私保护SVM算法94.87%Mangasarian的简约PPSVM算法97.19%Breast-cancer-wisconsin()mn==683,9隐私保护SVM算法99.5608%数值结果说明，本章给出的针对数据垂直分布数据的隐私保护支持向量机算法的分类精度要比Mangasrian给出的简约隐私保护支持向量机算法的分类精度高.需要指出的是，如果多个实体占有整个数据集的不同特征，利用我们的PPSVM算法进行分类时，分类精度仍然保持不变，只是会再多花费一些时间，最终都能达到保护隐私的目的.4.5本章小结针对垂直划分的数据分布，我们提出了一个不带安全多方计算的隐私保护支持向量机算法(PPSVM).该算法简单、直接，在不揭露每个实体区别于其他实体的原始数据的情况下，安全地计算出整体数据的SVM模型.建立该SVM模型后，对该模型的求解可以利用Libsvm软件求解，或者可以采用第3章给出的分解算法来求解.最后，数值实验表明，在花费一些时间安全计算核矩阵后，该算法的分类精度可以和使用原始数据而得到的SVM模型比拟.而且该算法的分类精度要比简约的隐私保护支持向量机算法的分64 山东科技大学博士学位论文4不带安全多方计算的数据垂直划分的隐私保护支持向量机算法类精度高.在此算法的基础上，我们可以针对水平划分的数据分布，进一步考虑如何隐藏原始数据，构造相应的隐私保护支持向量机算法.同时，也可以考虑半监督和未监督机器学习的隐私保护算法.65 山东科技大学博士学位论文5带有安全多方计算的数据水平划分的隐私保护支持向量机算法5带有安全多方计算的数据水平划分的隐私保护支持向量机算法5.1引言众所周知，数据挖掘是从大型数据库中提取人们感兴趣的知识，这些知识是隐含的、事先未知的、潜在的、有用的信息，提取的知识表示为概念、规则、规律、模式等形式.数据挖掘要处理的问题，就是在庞大的数据库中寻找有价值的隐藏事件，加以分析，并将这些有意义的信息归纳成结构模式，提供给有关部门决策时参考.前一章中，我们提到了目前人们对自己隐私的保密要求变得越来越迫切.由于某种原因，参与方往往不愿意将数据与他人共享而只愿意共享数据挖掘的结果.这种情况在科学研究、医学研究及经济和市场动态研究方面常常遇到.隐私保护数据挖掘的主要目的就是用某种技术改进已有的原始数据，利用修改后的数据进行数据挖掘或数据分类，保持数据挖掘结果或分类的正确性，同时使得敏感的数据和知识不被泄露.第四章，针对数据的垂直分布我们给出了一个隐私保护支持向量机的算法，在那个算法中，我们并未采用安全多方计算的加密技术.[41,42,43,117-119]安全多方计算(securemulti-partycomputation)是分布式密码学的理论基础，也是分布式计算研究的一个基本问题.它蕴含了密码学中任何协议问题在原则上的实现方案.安全多方计算的研究任务是使得n个成员组成的群组能够依靠各自的私有输入，共同计算出一个有意义的公共输出，其计算过程即使在有主动的恶意成员的影响下，也要保证输出的正确性.同时，还要保证计算的安全性，即不能泄漏有关私有信息输入[42]的除公共输出以外的任何其他秘密信息.最早是由A.Yao于1982年通过姚氏百万富翁问题提出了安全两方计算问题.姚氏百万富翁问题是指两个百万富翁希望知道谁更富有，但是除此之外不希望泄露任何其它的信息，这当然包括他们的所有财富的数量.5年[43]后，Goldreich,Micali和Wigderson于1987年提出了可以计算任意函数的安全多方计算协议.到上世纪90年代，安全多方计算的研究非常活跃.面对分布式数据的隐私保护技术大多数是基于密码学的隐私保护技术.特别在分布式环境下的隐私保护问题，安全多方计算(SMC)是最为常用的一个协议.66 山东科技大学博士学位论文5带有安全多方计算的数据水平划分的隐私保护支持向量机算法如上章所说，一些实体拥有属于自己的个体的所有特征，而另一些实体拥有属于他们的个体的所有特征，这样的数据分布称为是数据的水平划分(如图5.1所示).一般，一个数据矩阵的列称为特征，数据矩阵的行称为个体.E1E2……Eq图5.1水平划分的数据集Fig5.1Horizontallypartitioneddata[123]对于水平分布的数据，HwanjoYu于2006年对水平分布的布尔数据提出了一种隐私保护支持向量机(PPSVM)，将向量问题转换为集合问题来处理，引入hash函数计算集合交的势，进而得到核函数，在得到核函数的时候没有揭露原始数据，最后利用所得到[128]的核函数的数据建立了隐私保护支持向量机.2007年，OlviL.Mangasarian等将简约支持向量机(RSVM)引入数据水平分布的隐私保护支持向量机，每个实体生成相同的随机矩阵后，分别求得自己的核矩阵，将所有实体的核矩阵组合后得到整体数据的简约核矩阵，继而得到水平分布数据的隐私保护支持向量机.本章中，利用安全多方计算的加密技术，针对水平划分的数据分布，我们提出一类新的有效的隐私保护支持向量机分类器(PPSVM)，它不同于存在的SVM分类器.我们提出的分类器，针对每个实体是公开的，但是并没有揭露每个实体持有的原始数据，而且算法的精度可以和利用原始数据构建的标准SVM分类算法的精度比拟.利用了安全多方计算的技术，这个PPSVM分类器是直接准确的.最后，通过矩阵分解理论，我们证明了该算法的可行性.本章的组织结构如下：5.2节回顾安全多方计算的加密技术；针对水平划分的数据，在5.3节，我们给出了线性和非线性隐私保护支持向量机算法；5.4节给出了数值实验结67 山东科技大学博士学位论文5带有安全多方计算的数据水平划分的隐私保护支持向量机算法果；最后，5.5节讨论了相关的工作和进一步值得研究的工作.5.2安全多方计算的加密技术概述[116]安全多方计算研究一组互不信任的参与方之间保护隐私的协同计算问题，其基本要求是要确保输入的独立性，计算的正确性，同时不泄露各输入值给参与计算的其他成员.如果存在安全可信的第三方(称其为PPT)，则安全多方协议所要解决的问题可以轻易地得到解决：只需各参与者将各自的输入交给PPT,由PPT计算出函数值，再将函数值公布给各参与者.但现实中很难找到这样可信的PPT，从而安全多方计算协议的研究应运而生.安全多方计算问题是从众多具体的密码学问题中抽象出来的，对它的研究以及由此得到的一些结论对于具体的密码学问题都有着指导意义，它能在原则上告诉我们哪些问题是可以解决的，哪些问题是不可能解决的.但是，另一方面，由于安全多方计算是非常抽象的一个问题，使得我们很难找到有效的算法实现它，这导致了它在应用上的局限性.对于一个具体的密码学问题，我们可以先根据安全多方计算的结论，从原则上确定这个问题是否可以解决.如果不可以解决，就没必要去考虑如何设计算法或模型，因为不存在或不可能有满足安全性要求的算法；如果可以解决，则说明存在满足安全性要求的算法或模型，这时就要寻找和设计具体的算法和模型.可以说，安全多方计算是密码学协议的理论基础或者说是基石.安全多方计算在互联网的环境下有十分现实的意义.具体来讲，安全多方计算是考虑如下的问题.设EEEE={,,,}?是n个参与者集12n合，他们想要“安全地”计算某个给定的n个输入和n个输出的函数f(,,,)(,,,)xx??x=yyy，其中这个函数的n个输入是分别由这n个参与者秘密掌握12nn12的，设E的秘密输入是x，并且在计算结束后，E得到输出y.这里的安全性是要求即iiii使在某些参与者有欺骗行为的情况下，保证计算结果的正确性，即计算结束后每个诚实的参与者E都能得到正确的输出y，同时还要求保证每个参与者输入的保密性，即每个ii参与者E除了知道(,)xy以及从中推出的信息之外，得不到任何其它的信息.这样如何iii构造满足安全性的算法是一个关键问题.不难看出，如果我们能安全地计算函数x+x和12xx，则我们可以安全地计算任何布尔函数或多项式函数.12目前安全多方计算已得到许多学者的研究，其在密码学上的地位也日益重要，现有68 山东科技大学博士学位论文5带有安全多方计算的数据水平划分的隐私保护支持向量机算法的许多密码工具都是安全多方计算的基础，SMC的关键技术涉及到秘密分享与可验证秘密分享、门限密码学、零知识证明、茫然传输、茫然多项式估值、百万富翁协议等多方面的内容，协议中应用的基本密码算法包括各种公钥密码体制，特别是语义安全的同态公钥加密系统.在不同的计算领域中，SMC问题的安全需求不相同，应针对具体SMC应用环境进行安全性定义，寻找高效的SMC解决方法.在SMC应用研究方面，寻找特殊领域的SMC问题及其解决方案是值得深入研究的方向，如分布式生成RSA密钥、多方合作签名、自安全的无线Ad-hoc网络等.随着电子商务的兴起，电子拍卖、电子选举、私有信息检索成为SMC研究的又一热点.此外，SMC在保护隐私的科学计算，保护隐私的统计分析、保护隐私的几何计算、保护隐私的数据库查询、保护隐私的数据挖掘、保护隐私的入侵检测等方面的课题等，都值得做进一步深入的研究.5.3数据水平划分的隐私保护支持向量机算法mn×矩阵A被分成p个水平块m,…,m，且满足mm++=?m，即1p1pA=(,,)'AA?，其中A是mn×矩阵.每一个行块由一个实体“拥有”，这个实体不愿公1pii开这个行块的数据，也不愿意和其他实体共享这些数据.假定p个实体对每个数据点达成一致的属性，也就是说D=+1or−1,im=1,2,?,.ii正如5.2节所示，一个SVM模型是由核矩阵Kxx(,)来确定，而核矩阵又可由整体ij数据的Gram矩阵得到.对线性核矩阵，借助矩阵理论，可以由下面的公式得到：''⎛⎞AA⎛⎞A?AA1111p⎜⎟⎜⎟KA==A''⎜⎟@??()AA1p'=⎜⎟??.(5.1)⎜⎟AA⎜⎟A''?AA⎝⎠pp⎝⎠1pp一些常用的非线性核也可以通过Gram矩阵计算得到.多项式核可以由数据向量的点积得到(i.e.,(,Kxx)=((xxi)1)+q).径向基核(RBFkernel)矩阵也可以利用数据向量的点ijij积得到，即2Kxx(,)exp(||=−−xx||/)gijij.=−⋅−⋅+⋅exp(|xxxxxxg2|/)iiijjj这样，如果我们可以不揭露原始数据而得到整体数据的Gram矩阵，那么就可以在不揭69 山东科技大学博士学位论文5带有安全多方计算的数据水平划分的隐私保护支持向量机算法露原始数据的情况下确定出核矩阵.下面我们开始建立PPSVM算法.在给出算法之前，先给出下面几个结论，这些结论说明我们计算整体数据的Gram矩阵是安全的.[41]为了安全地计算(5.1)，首先来考虑安全地计算两个矩阵的乘积.下面的方法5.1说明不具体知道两个矩阵，可以安全地计算出它们的乘积.方法5.1:设A和B是由两个实体E和E所拥有的矩阵.12步骤1给定两个数s和t，设st足够大，以致不可能计算出st次加法.步骤2实体E1随机产生t个随机矩阵XX1,,?t使得A=XX1++?t.步骤3对任意的jt=1,2,?,，做下面的循环.步骤3.1实体E产生一个私密的随机数r，1≤rs≤；1步骤3.2实体E1把(,,,,,)HH12??HrsH发给实体E2，其中HXrj=，并且Hi是随机矩阵.这样r是一个私密的数字，只有E知道，而E并不知道.所以E不知道H是122i哪个X.j步骤3.3对所有的j=1,2,?,s，实体E计算出2HBR−，jj其中R是一个随机矩阵.j步骤3.4根据某个规则，实体E得到结果1HBRXBR−=−.rjjj步骤4在步骤3循环完之后，实体E能够计算出1mmM1=−∑()XBRjj=AB−∑Rj.(5.2)jj==11实体E可以计算出2mM2=∑Rj.(5.3)j=170 山东科技大学博士学位论文5带有安全多方计算的数据水平划分的隐私保护支持向量机算法这样可以得到AB=M+M.(5.4)12定理5.3.1方法5.1是适定的.证明由于实体E发给实体E一个随机矩阵，这样实体E若想知道E发的具体的矩1221阵X有s种可能.又由于j=1,2,?,t，所以E有st种可能性来推测实体E拥有的矩阵A.j21由于我们假定s和t足够大，而且st也足够大，所以实体E不可能得到实体E的矩阵A.21对于实体E来说，E把矩阵HBR−发过来，所以同样E也不可能求解出矩阵B.这样，12jj1我们可以在不知道两个矩阵的具体数据信息的情况下，计算出这两个矩阵的乘积.所以结论正确.证毕.'下面我们可以得到主要的算法来计算AA，从而可以不揭露矩阵原始数据信息的前ij提下得到整体数据的Gram矩阵.'借助上面的方法5.1，可以得到下面的方法5.2来计算AA(ij,1=,2,,?p).ij方法5.2设EE,,,"E是p个不同的实体，每个实体拥有自己的数据矩阵行块12pAi,1=,2,,?p，i这些实体想不互相揭露彼此私密数据信息的前提下建立一个SVM分类器.也就是说，在'不知晓具体矩阵A和A的情况下来计算AA'.ijij步骤1给定两个数s和t，设st是足够大的数，以致不可能计算st次加法.步骤2首先，在不揭露A的情况下，计算得到AA'，其次，实体E产生t个随机矩iii1阵X,,,XX?使得11121tA=XX+++?X.111121t步骤3对j=2,?,p，设AA:=1，B:'=Aj，执行方法5.1共p−1次，在不揭露A1和A'的情况下得到AA'.j1j步骤4对ip=2,?,，j=+ip1,?,，设AA:=，B:'=A，执行算法方法5.1p−i次，ij71 山东科技大学博士学位论文5带有安全多方计算的数据水平划分的隐私保护支持向量机算法可以在不揭露A和A'的情况下得到AA'.ijij步骤5最后得到所有可能的矩阵的乘积AA',1,2,ip=?,,1,2,j=?,p.ij这里，我们并没有揭露矩阵A和A'的数据信息.ij这样，我们得到了Gram矩阵(5.1).引理5.3.1设非零矩阵A是一个mn×矩阵，且满足AAC'=，那么矩阵A是不可解的或是不唯一的.证明证明类似于定理4.3.1.引理5.3.1证明了如果每个实体可以隐藏自身的原始数据矩阵A，而只产生自身的矩j'阵AA，这并不揭露这个实体的任何原始数据.jj引理5.3.2方法5.2在有限步终止.证明根据引理1，可知矩阵AA'是对称矩阵，所以给定矩阵AA'，对其转置，可以ij得到矩阵AA'.这样，由算法方法5.2中的步骤2到步骤4，经过jistp+−stp(1)+?++st2st=+stpp(1)/2次的矩阵乘法运算，可以得到所有的AA'.证毕.ij定理5.3.2方法5.2是适定的.证明由引理5.3.1和引理5.3.2，我们看到，每个实体j公开自身的局部的Gram矩阵，得到所有的AA'，从而得到整体数据的Gram矩阵.同时，在计算的过程中并没有ij揭露每个实体所拥有矩阵的原始数据信息.证毕.根据以上的结论，可以通过整体数据的Gram矩阵得到核矩阵.在隐藏原始数据的过程中，我们采用了多方安全计算的技术.5.3.1线性PPSVM算法现在我们给出线性隐私保护支持向量机算法.'步骤1每个实体i不揭露原始数据矩阵A而公开自己局部的Gram矩阵AA.执行算iii法方法5.2，允许公开计算整体数据的Gram矩阵从而得到核矩阵72 山东科技大学博士学位论文5带有安全多方计算的数据水平划分的隐私保护支持向量机算法⎛⎞A1⎛⎞AA11'''AA12?AA1p⎜⎟⎜⎟AAA'''AA?AA⎜⎟22⎜⎟1222pKA==⎜⎟@()12''A?Ap'⎜⎟??.⎜⎟⎜⎟⎜⎟Ap⎜⎟ApppAA'''AA?Ap⎝⎠⎝⎠12步骤2通过下面标准的SVM算法来公开计算线性分类器f()xxA=+'wb，min1α'Qeαα−'2αst..0≤≤αC,i.m∑dimiiα==0,1,2,?,i=1n步骤3对每个新的样本点x∈R，同样根据算法方法5.2，通过公开的线性分类器，每个实体可以公开自己的x''A如下：jj''''⎛⎞xA?xA111p⎜⎟f()xxA=+''wb=⎜⎟???wb+,(5.5)⎜⎟xA''?xA''⎝⎠pp1p这样可以根据x''Awb+的符号来对新的样本点x进行分类.在上面的算法中，每个实体j并不揭露自身的数据A也没有揭露出新的样本点x的jj'任何元素.在不知道A的情况下，从矩阵的乘积AA中不可能计算得出唯一的矩阵A.jjjj同样根据算法方法5.2，从矩阵的乘积AA'中也不可能计算出A或A.ijij5.3.2非线性PPSVM算法类似于线性隐私保护支持向量机算法，下面给出非线性隐私保护支持向量机的算法.'步骤1每个实体i公开自己的局部Gram矩阵AA而不公开原始数据A.执行算法iiiMethod2，允许公开计算整体数据的全局Gram矩阵，从而得到核矩阵(5.1).步骤2根据所求得的全局Gram矩阵来计算非线性核矩阵KAA(,').步骤3通过下面标准的SVM算法73 山东科技大学博士学位论文5带有安全多方计算的数据水平划分的隐私保护支持向量机算法min1α'Qeαα−'2αst..0≤≤αC,im∑dimiiα==0,1,2,?,i=1来公开计算非线性分类器f()xKxAwb=(',')+.对于大规模的数据分类问题，也可以借助第3章给出的分解算法来确定线性和非线性分类器.n步骤4对每个新的样本点x∈R，首先根据(4.7)式来计算x''A，接着每个实体公开自己的KxA(',')，这样，通过KxAwb(',')+=0可以公开计算非线性分类器.通过某种运算，可以根据局部的Gram矩阵得到整体数据的全局Gram矩阵.这样，给定新的样本点x，可以根据signKxAwb((',')+)的符号来对它进行分类.在上面的算法中，没有一个实体揭露自己的原始数据，也不揭露新的样本点x的具j体信息.这样只给定K(,'AA)，在不知道A的情况下，是不可能计算出唯一的A的.根jjjj据算法5.2，也不可能从KAA(,')ij中直接计算出Ai或Aj.5.4数值实验本节我们给出本章所提出的针对水平分布数据的PPSVM算法的数值实验结果.所有的数值实验均在个人电脑上运行实现，个人电脑的配置如下：(1)CPU:Intel(R)Core(TM)2Duo3.06GHz;(2)内存：512M;(3)操作系统：WindowsXPSP3.所有程序都是用Matlab7.0编写的.本节的实验中，我们从MachineLearningRepository的UCI数据集中选取Pima-Indians-Diabetes和Bupaliver数据集来进行测试，其中Pima-Indians-Diabetes数据集包含768个样本，两个类别，7个属性.Bupaliver数据集包含345个样本，6个属性，参数C=100,使用线性核来测试算法的有效性.74 山东科技大学博士学位论文5带有安全多方计算的数据水平划分的隐私保护支持向量机算法在实验中，假定Pima-Indians-Diabetes数据集中的数据是水平分布的，分别由三个实体所持有.其中这三个实体所占有的数据矩阵维数都为2567×，即第一个实体E持有1数据集Pima-Indians-Diabetes中的前256行数据，实体E持有数据集2Pima-Indians-Diabetes中的第257行到第512行的数据，实体E持有数据集3Pima-Indians-Diabetes中的第513行到第768行的数据.假定Bupaliver数据集中的数据也是水平分布的，分别由两个实体所持有.参照Mangasarian[128]给出的简约隐私保护支持向量机算法的结果，我们给出了本章提出的PPSVM算法和简约PPSVM算法确定分类器对数据分类的精度比较.数值实验结果如表5.1所示，表5.1标准SVM算法和简约PPSVM算法的比较结果Table5.1ComparisionbetweenstandardSVMalgorithmandReducedPPSVMalgorithm，数据集(维数m,n)算法分类精度Mangasarian的简约76.97%Pima-Indians-DiabetesPPSVM算法()mn==768,7隐私保护SVM算法99.7396%Mangasarian的简约57.37%Bupa-liverPPSVM算法()mn==345,6隐私保护SVM算法100%由上面的结果可知，本章给出的针对数据水平分布数据的隐私保护支持向量机算法的分类精度要比Mangasrian给出的简约隐私保护支持向量机算法的分类精度高很多.不过，需要指出的是，利用我们的PPSVM算法进行分类时，分类精度和经典的SVM算法保持一致，只是在为隐藏原始数据计算出核矩阵，需要多花费一些时间，最终我们的75 山东科技大学博士学位论文5带有安全多方计算的数据水平划分的隐私保护支持向量机算法PPSVM算法能够达到保护隐私的目的.5.5本章小结针对数据水平分布的情况，借助安全多方计算的加密技术，本章提出了一个隐私保护支持向量机算法，该算法给出的分类器是公开的，同样并未揭露任何参与方的原始数据.数值实验表明该算法的精度和未加隐私保护经典的支持向量机算法基本一致.最后利用矩阵分解理论证明了该算法的可行性.建立该SVM模型后，对该模型的求解可以利用Libsvm软件求解，或者可以采用第3章给出的分解算法来求解.最后，数值实验表明，在花费一些时间安全计算核矩阵后，该算法的分类器基本和使用原始数据而得到的SVM分类器一致，所以PPSVM算法的分类精度也和标准的SVM算法的分类精度一致，并且比简约隐私保护支持向量机算法的精度要好.需要指出的是，因为我们的算法只考虑样本数据的安全性和隐私性，并没有着重考虑PPSVM算法的计算量.在以后的研究中，可进一步考虑针对大规模问题，建立相应的隐私保护支持向量机的分解算法，以便简化计算量.由于实际问题的数据分类比较复杂，多个实体对数据的持有方式也呈现出任意复杂的趋势,对于数据的任意划分情况，如何建立相应的隐私保护支持向量机算法，这是我们下一章预备解决的问题.76 山东科技大学博士学位论文6针对任意分割数据的隐私保护支持向量机算法6针对任意分割数据的隐私保护支持向量机算法6.1引言随着人们对隐私保护支持向量机广泛的研究，也由于人们对自己隐私的保密要求越来越迫切，对一些分布式数据的隐私保护支持向量机算法已经相继建立.由前面的分析可知，固定一些个体，那些实体拥有全部个体的属于他们自己的输入特征，而另外一些实体拥有全部个体的属于他们自己的另外的输入特征，这样的数据分布称为垂直划分.一些实体拥有属于自己的个体的所有特征，而另一些实体拥有属于他们的个体的所有特征，这样的数据分布称为是数据的水平划分.本文的第4章和第5章对数据垂直分布和数据水平分布分别构造了相应的隐私保护支持向量机算法，这些算法具有和标准SVM算法同样的分类精度.在实际生活中，数据分布的复杂化程度不断增大，多个实体对数据的持有方式也呈现出任意复杂的趋势，因此，很多学者对任意分割数据的隐私保护支持向量机产生极大[125]的兴趣.2008年，JaideepVaidya和HwanjoYu对任意划分的数据提出了一种隐私保护支持向量机(PPSVM)算法，该算法利用同态加密技术，结合数量积协议，求解得到整体数据的Gram矩阵，进而在不揭露原始数据的情况下得到整体数据的核函数，最后得到[129]数据任意划分的隐私保护支持向量机.同年，OlviL.Mangasarian等也针对棋盘格式分布的数据建立了隐私保护支持向量机，利用简约随机核的概念，每个实体分别求得自己的核矩阵，将所有实体的核矩阵组合后得到整体数据的简约核矩阵，继而得到棋盘格式数据分布的线性和非线性隐私保护支持向量机.然而，由于使用了简约核矩阵，该算法的分类精度和标准的SVM分类精度有一定的差距.不同实体拥有不同的特征，各个特征之间没有必然的联系，这样的数据分布称为是数据的任意分割(如图6.1所示).一般，一个数据矩阵的列称为特征，数据矩阵的行称为个体.本章中，利用安全多方计算的加密技术，针对任意划分的数据分布，我们提出一类新的有效的隐私保护支持向量机分类器(PPSVM)，它不同于存在的SVM分类器.我们提出的分类器，针对每个实体是公开的，但是并没有揭露每个实体持有的原始数据，而且77 山东科技大学博士学位论文6针对任意分割数据的隐私保护支持向量机算法算法的精度可以和利用原始数据构建的标准SVM分类算法的精度比拟.利用了安全多方计算的技术，这个PPSVM分类器是直接准确的.最后，通过矩阵分解理论，我们证明了该算法的可行性.1234图6.1任意分割的数据集Fig6.1Arbitrarypartitioneddata本章的组织结构如下：在6.2节，借助安全计算矩阵乘积的策略，我们给出了线性隐私保护支持向量机算法.6.3节采用类似的思想给出了非线性隐私保护支持向量机算法，最后，6.4节给出了本章小结.6.2数据任意划分的线性隐私保护支持向量机算法针对如图6.1所示的任意分割的数据，本节将借助安全计算矩阵乘积的策略，建立线性隐私保护支持向量机算法.设任意分割的数据集的整体矩阵为A，该矩阵的数据由如图6.1所示的一些实体mn×所持有，即实体P拥有的数据为A.由于数据集是任意分割的，在求整体Gram矩阵ijijAA'时需要计算一些子块数据矩阵的乘积.另外，数据的任意分割可能会造成某些mnmn××子块矩阵无法进行分块矩阵的乘法，因此，首先构造如下分割的数据矩阵，如图6.2所示.78 山东科技大学博士学位论文6针对任意分割数据的隐私保护支持向量机算法1122111234423444图6.2任意分割数据集相应的矩阵构造Fig6.2partitionedmatrixcorrespondingtothedataset设mn×的矩阵A由任意划分的pq个块矩阵构成，其中有m,…,m个行块和1pn,…,n个列块，且1qmm++=?m,nn+?+=n.1p1q这意味着⎛⎞AA11,,12?A1q⎜⎟AA,,?A⎜⎟21222qA=⎜⎟,??⎜⎟⎜⎟A,,AA?⎝⎠pp12pq这里A为mn×矩阵.这样我们注意到每个块由一个分离的实体所拥有，然而一个实体ijij有可能拥有多于一个块矩阵.这样假定P为其中的一个实体，且实体P可能包括几个ijkP(如图1，实体P可能拥有AA,和A的数据，所以P包括PP,和P).每个实体不ij11121221112122愿意和其他的实体共享他们的数据，即不愿意公开该实体的数据.进一步假定所有pq个实体对所有的数据的类别达成了一致，即D=+1或者1−,1,2,im=?,.ii正如前面章节所示，SVM模型由核矩阵Kxx(,)来确定,这个核矩阵又可由全局的ijGram矩阵来确定.对线性核矩阵，由矩阵分解理论，可以得到下面的公式79 山东科技大学博士学位论文6针对任意分割数据的隐私保护支持向量机算法⎛⎞AAA1112??1qp⎛⎞AA11'''21A1⎜⎟⎜⎟AAA??AA'''A⎜⎟21222qp⎜⎟12222KA==A'⎜⎟⎜⎟??????⎜⎟⎜⎟⎜⎟AAAAA??⎜⎟'''A⎝⎠pqp21pq⎝⎠q2qpq⎛⎞AA''++AA??+AA'''AA++AA?+AA'111112121qq111p112p21qpq⎜⎟=⎜⎟???.(6.1)⎜⎟AAAA''++??+AA'''AAAA++?+AA'⎝⎠pp111212pq1qp1p12pp2pqpq类似于前面两章的分析，一些通常的非线性核也可由Gram矩阵得到.这样，不揭露原始数据矩阵，可以确定全局Gram矩阵.下面，我们建立PPSVM算法.建立PPSVM算法的核心仍然是安全地计算出全局的Gram矩阵.[41]为安全计算(6.1),首先安全地计算两个矩阵的乘积.第5章中的方法5.1表明在不揭露两个矩阵具体数据的情况下，我们可以计算出这两个矩阵的乘积.'针对任意分割的情形，下面我们来计算AA，ij,1=,2,,;?pkq=1,2,?,，这样全ikjk局的Gram矩阵可以在不揭露矩阵原始数据的信息下得到.由方法5.1，可以类似得到下面的方法6.1来计算'AA(ij,1=,2,,;?pkq=1,2,?,).ikjk方法6.1:假设PP,,,,,,,,,,,???PPPPPPP11121qq21222p1p2pq为pq个不同的实体，每个实体拥有他们自己的矩阵块Ai,=1,2,,;??pk=1,2,,q，大家ik想不揭露任何实体的原始数据而建立一个SVM分类器，这就是说不知道具体的A和ikA'的情况下，来计算矩阵jkAA'.ikjk步骤1给定两个数s和t,设st足够大，不可能计算出st次加法.步骤2首先，我们可以不揭露A而得到AA'.接着实体P产生t个随机矩阵iiiiii11XX,,,?X11121t80 山东科技大学博士学位论文6针对任意分割数据的隐私保护支持向量机算法使得A=XX+++?X.1111121t步骤3对于j=2,?,p,设AA:=,B:'=A,且执行p−1次算法5.1，就可以在不11j1揭露A和A'的情况下，得到11j1AA'.11j1步骤4对kq=2,?,,1,j=?,p,设AA:=,:B=A',执行(1qp−−)(1)次方法1kjk6.1，就可以在不揭露A和A'的情况下得到1kjkAA'.1kjk步骤5对于ip=2,?,,1kq=,2,,?,j=1,?,p,设:AA=,:B=A',执行方法ikjk5.11pp(1−)(1q−)2次,可以在不揭露A和A'的情况下得到ikjkAA'.ikjk步骤6最后我们得到所有可能的矩阵乘积AA',ip=−1,2,?,i,1,2,j=?,p,1,2,kq=?,.ikjk在计算中间，我们并没有揭露A和A'的原始数据.根据方法6.1可知，为得到全局的ikjkGram矩阵，需要再做1pp(1−)(1q−)2次的加法运算，就可以得到(6.1)式的Gram矩阵.引理6.2.1设非零矩阵A为mn×矩阵，并且满足AA'=C,那么矩阵A不可解或者不唯一.证明：参照第四章的引理4.3.1.'引理6.1说明每个实体产生他们自己的矩阵AA时，自身的原始数据A是隐藏的.iij引理6.2.2方法6.1在有限步终止.81 山东科技大学博士学位论文6针对任意分割数据的隐私保护支持向量机算法证明由引理6.2.1,我们知道矩阵AA'为对称矩阵，所以如果矩阵AA'给定的话，ij矩阵AA'可以通过对矩阵AA'进行转置而得到.这样根据方法6.2中的步骤2-步骤5,jiij我们可以在经过计算stqp+−stqp(1)+?++stq2stq=+stqpp(1)/2次乘法和1pp(1−)(1q−)2次加法运算得到所有的矩阵乘积AA'.ikjk证毕.定理6.2.1方法6.1是适定的.证明由引理6.1和引理6.2，我们注意到全局的Gram矩阵可以通过计算出来的矩阵乘积AA'而得到.这个矩阵AA'是由实体P公开的，但是并没有揭露出每个实体ikjkikjkij的原始数据矩阵.证毕.由上面的分析知道，得到Gram矩阵后，继而可以得到核矩阵.下面给出线性PPSVM算法.'步骤1每个实体P公开自己的局部Gram矩阵AA，不揭露原始数据A.执行方iiiiiiii法2,允许公共计算全局的Gram矩阵来得到核矩阵(6.1).步骤2公开计算线性分类器xAwb'0+=.计算的时候可以通过标准的SVM算法来计算，如第一章中(1.3)所示的算法.n步骤3对每个新的样本点x∈R,同样根据方法6.2,每个实体公开x''A，通过下jij面公共的线性分类器''⎛⎞AA?11p1''⎜⎟xAwbx''+=(,,)1??xp⎜⎟??wb+=0,(6.2)⎜⎟AA''?⎝⎠1qpq计算，这个分类器可由x''Awb+的符号来确定新样本点x的类别.注意到上面的算法中没有实体j揭露自己的原始数据集A，也没有揭露新的样本点j82 山东科技大学博士学位论文6针对任意分割数据的隐私保护支持向量机算法'x的原始数据.在不知道A的情况下，不可能根据矩阵AA来计算出唯一的矩阵A，同jjjjj''时也不可能在不知道x的情况下，仅根据xA来计算出唯一的数据x.最后，由方法6.1jjjj可知，由给定的矩阵乘积AA'，不可能计算出A或者A.ikjkikjk6.3数据任意划分的非线性隐私保护支持向量机算法同样借助安全多方计算的技术，类似于建立线性PPSVM的思想，下面给出非线性的PPSVM算法.'步骤1每个实体P公开自己的局部Gram矩阵AA，未揭露原始数据A.执行方iiiiiiii法6.2,允许公开计算全局的Gram矩阵.⎛⎞AA''++AA??+AA'''AA++AA?+AA'111112121qq111p112p21qpq⎜⎟AA'=⎜⎟???⎜⎟AAAA''++??+AA'''AAAA++?+AA'⎝⎠pp111212pq1qp1p12pp2pqpq步骤2由全局的Gram矩阵计算相应的非线性核矩阵.步骤3通过下面标准的SVM算法模型min1α'Qeαα−'2αst..0≤≤αC,im∑dimiiα==0,1,2,?,i=1公开计算非线性分类器f()xxA=+'wb.或者采用第3章给出的分解算法求解相应的非线性分类器.n步骤4对每个新的样本点x∈R,首先由公式(6.3)计算x''A,接着通过前面计算的非线性分类器f()xKxAwb=+(',')，每个实体公开自己的KxA(',')，其中全局的核矩阵(',')KxA可以通过局部核矩阵由某种运算计算得到.最后根据sgnKxAwb((',')+)，我们计算出新的样本点x的类别.注意到上面的算法中没有实体ij揭露自己的原始数据集A，也没有揭露新的样本点ij83 山东科技大学博士学位论文6针对任意分割数据的隐私保护支持向量机算法xj的原始数据.在不知道Aj的情况下，不可能根据给定的KAA(,'jj)来计算出唯一的矩阵'A，同时也不可能在不知道x的情况下，仅根据K(,')xA来计算出唯一的数据x.最jjjjkj后，由方法6.1可知，由给定的矩阵乘积KAA(,'ikjk)，不可能计算出Aik或者Ajk.6.4数值实验本节的实验中，我们从MachineLearningRepository的UCI数据集中选取Arrhythmia和GermanCredit数据集来进行测试，其中Arrhythmia数据集包含452个样本，16个类别，279个属性.GermanCredit数据集包含1000个样本，两个类别，24个属性，参数C=100,使用线性核来测试算法的有效性.在实验中，假定Arrhythmia数据集和GermanCredit数据集中的数据都是任意划分的，由于Arrhythmias数据集中提供的数据有缺失的数据，所以我们用0替换了缺失的数据，这样使得我们数值结果中的分类精度达到了100%.从此结果也能够看出我们的分类精度是要相比好些的.参照Mangasarian[129]给出的棋盘格分布的简约隐私保护支持向量机算法的结果，我们给出了本章提出的PPSVM算法和简约PPSVM算法确定分类器对数据分类的精度比较.数值实验结果如表6.1所示，表6.1标准SVM算法和简约PPSVM算法的比较结果数据集(维数m,n)算法分类精度Mangasarian的任意划分的简约100%ArrhythmiaPPSVM算法()mn==452,279任意划分的隐私保护SVM算法73%Mangasarian的任意划分的简约76%GermanCreditPPSVM算法()mn==1000,24任意划分的隐私保护SVM算法93.5%84 山东科技大学博士学位论文6针对任意分割数据的隐私保护支持向量机算法Table6.1ComparisionbetweenstandardSVMalgorithmandReducedPPSVMalgorithm，由上面的结果可知，本章给出的针对数据任意划分的隐私保护支持向量机算法的分类精度要比Mangasrian给出的棋盘格式简约隐私保护支持向量机算法给出的分类精度高.不过，需要指出的是，利用我们的PPSVM算法进行分类时，分类精度和经典的SVM算法保持一致，只是在为隐藏原始数据计算出核矩阵，需要多花费一些时间，最终我们的PPSVM算法能够达到保护隐私的目的.6.5本章小结本章中，针对任意划分的数据，我们提出了线性和非线性的隐私保护支持向量机算法.虽然需要执行多次的乘法和加法运算，但是我们的算法是安全的，也是直接的.在不揭露每个实体的原始数据的情况下，我们的PPSVM算法安全地计算出了全局的SVM分类器的模型，可以通过标准的SVM算法或者第3章给出的分解算法求解其分类器，也可以对新的样本点安全地预测它的类别.通过分析证明，本章建立的PPSVM算法和标准的SVM算法具有同样的分类精度.由于我们的PPSVM算法只考虑了对每个实体隐私的保护，并没有过多地考虑该算法的计算量.在今后的研究工作中，可以进一步考虑如何简化隐私保护支持向量机算法的计算量，尤其是如何针对大规模数据集设计简洁安全的PPSVM算法.又由于实际问题中采集数据的困难，也可以进一步考虑建立模糊的隐私保护支持向量机算法模型.85 山东科技大学博士学位论文7总结和展望7总结和展望7.1本文的特色和创新点本文对支持向量机的简化分解算法和隐私保护支持向量机的算法进行了研究.分解算法是求解支持向量机的一类简单有效的算法，其关键在于选择一种合适的工作集，从而把大规模的支持向量机转化为一系列的小规模子问题来求解，其极端的特例是SMO算法，每次选择两个样本点进入工作集，子问题可以解析求解，相对于其它的算法，该算法有较快的分类速度，广泛被采用.隐私保护支持向量机算法是在隐私保护数据挖掘算法的基础上新兴起来的一个研究方向，考虑到人们对自己隐私的保密性要求，考虑到银行、保险公司、医学研究机构等行业对顾客的隐私保密性要求等，在不泄露原始数据的情况下，建立相应的支持向量机分类器，同时这种分类器保持分类精度不变.本文的创新点如下：1．阐述了支持向量机的一般简化算法，对支持向量机一般简化训练算法中起实质作用的支持向量和对应乘子之间的关系进行了理论分析，借助图形，直观地分析了支持向量相对于决策面的几何关系.通过对简化算法终止条件的分析，进一步分析和探讨了违背KKT条件对的几何含义.2.考虑了带有线性等式和界约束的非线性优化问题，主要针对那些变量个数较多，传统的优化方法不能求解的问题，如大规模支持向量机的凸二次规划问题，给出了一类分解算法.该算法每次迭代的可行下降方向从具有2q个分量的相对稀疏可行方向中选取，在假设方向水平集中至少有一组下标对应的分量严格在上下界之间的前提下，证明了算法的全局收敛性.数值实验说明了该算法的有效性.3.针对数据垂直分布的情况，基于矩阵分解理论，提出了一个隐私保护支持向量机算法，该算法简单直接，无需利用安全多方计算技术，给出的分类器是公开的，但是并未揭露任何参与方的原始数据.同时，该算法和未加隐私保护经典的支持向量机算法的精度是一致的.最后利用矩阵分解理论证明了该算法的可行性.数值实验表明该算法比Mangasarian提出的简约隐私保护支持向量机算法的分类精度高.4.针对数据水平分布的情况，借助安全多方计算的加密技术，提出了一个隐私保护86 山东科技大学博士学位论文7总结和展望支持向量机算法，该算法给出的分类器是公开的，同样并未揭露任何参与方的原始数据.最后利用矩阵分解理论证明了该算法的可行性.数值实验表明该算法的分类精度比Mangasarian提出的简约隐私保护支持向量机算法的分类精度高.5.针对数据任意分割的情况，利用水平分布的矩阵乘积的安全性策略，提出了一个隐私保护支持向量机算法，在未揭露任何参与方的原始数据的情况下给出了公开的分类器.最后利用矩阵分解理论证明了算法的可行性和有效性.7.2展望支持向量机是20世纪九十年代中期才发展起来的一个数据挖掘和机器学习方面的新的研究领域，其核心思想是学习机器要和有限的常常是大规模的训练样本相适应，虽然近些年发展较快，取得了一定的研究成果，但是还是有很多尚未解决的问题，需要研究者做进一步的研究.7.2.1分解算法的进一步研究分解算法是求解支持向量机的一类简单有效的算法，其关键在于选择一种合适的工作集，或者说确定一种有效的换入换出策略，从而把大规模的支持向量机转化为一系列的小规模子问题来求解，其极端的特例是SMO算法，每次选择两个样本点进入工作集，子问题可以解析求解，但是每次换取多少个变量也是一个值得研究的问题.有效集识别技术是求解最优化问题的一类非常高效成熟的技术，如何把有效集识别技术与分解算法的工作集选择策略进一步结合，把有效集识别函数成功应用到分解算法中也有待进一步的研究.7.2.2隐私保护支持向量机算法的进一步研究课题隐私保护支持向量机是2006年之后新兴起来的一个研究方向，基于隐私保护数据挖掘技术的发展,基于人们对个人隐私信息迫切需要保护的要求，该研究方向已经成为机器学习领域非常重要的研究方向之一.针对数据水平分布、数据垂直分布和任意分割的方式，我们给出了三类隐私保护支持向量机算法，对于这些算法的收敛速度、收敛性等理论分析值得做进一步深入的研究和探讨，对隐私保护支持向量机算法和并行求解算法之间的关系等都是一些值得研究的课题.另外，目前的隐私保护支持向量机的加密大部分依赖安全多方计算的加密技术，密87 山东科技大学博士学位论文7总结和展望码学中存在很多实用的加密技术，所以，对于隐私保护支持向量机的加密技术问题，即如何能够合理地隐藏原始数据，或者对原始数据做随机干扰，而不影响最后的分类精度等等也是研究者们需要进一步研究的问题.88 山东科技大学博士学位论文致谢致谢本篇博士论文得以顺利完成，首先要特别感谢的是我的导师贺国平教授.从论文的选题，定题，具体问题的分析和研究，数值实验的思路和方法至论文的撰写和定稿，无不倾注着贺老师耐心的指导和不懈的鼓励.我论文中很多灵感的迸发和思路的完善都是依靠贺老师敏锐的学术思维和深邃的科学洞察力而完成的.贺老师严谨的治学态度，认真求实的学术精神和深入钻研的作风，使我终生受益.值此论文完成之际，谨向贺老师致以最诚挚的谢意！衷心感谢赵茂先老师一直以来在学习和生活上给予我的关怀和帮助，他渊博的知识和可行性的建议都使我获益匪浅.感谢讨论班的董玉林博士，在与他的讨论中，我对支持向量机的分解算法有了更深入和透彻的理解.衷心感谢讨论班的同门周长银副教授，韩丛英副教授，潘美芹副教授，房亮博士，王永丽博士，杨洪礼博士，段华博士，薛欣博士，孙莉博士，汤京永博士，邵福波师弟，张新师弟，徐芳芳师妹等人，经过跟他们热烈地讨论和研究，很多问题迎刃而解.衷心感谢博士期间的同学魏海霞，王桂芳，张杏莉，茅晓辉，景冬等人，在与他们共同的学习和生活中，结下了深厚的友谊.衷心感谢我的父母和家人，有他们作为坚强的后盾，我才得以顺利完成学业.感谢我的爱人卫武军，感谢他多年的支持和关爱.感谢我最亲爱的女儿卫毓桐，她的健康快乐是我学习和钻研的动力.衷心感谢信息学院的领导和老师，衷心感谢所有帮助、关心和支持我的人，我的每一步成长和进步都离不开他们的鼎立相助.89 山东科技大学博士学位论文参考文献参考文献1.V.Vapnik,ThenatureofstatisticallearningTheory[M].NY:Spring-Verlag,19952.张学工译,统计学习理论的本质[M].北京：清华大学出版社,20003.C.Cortes,V.Vapnik.Supportvectornetworks[J].MachineLearning,1995,20:273-2974.V.Kecman,Learningandsoftcomputing,supportvectormachines[J].NeuralNetworksandFuzzyLogicModels,TheMITPress,Cambridge,MA,20015.R.Dembo,S.Eisenstat,SteihaugT,InexactNewtonmethod[J].SIAMJournalonNumericalAnalysis,1982,(19):400-4086.D.DeCoste,andB.Schölkopf.Traininginvariantsupportvectormachines[J].MachineLearning,2002,46,161-1907.张学工,关于统计学习理论与支持向量机[J].自动化学报,2000,26(1):32-428.O.L.Mangasarian.Generalizedsupportvectormachines[J].InA.Smola,P.Bartlett,B.Schölkopf.AdvancesinlargeMarginClassifiers[M],MITPress,2000:135-1469.O.L.MangasarianandD.R.Musicant,Successiveoverrelaxationforsupportvectormachines[J].Tech.Report,ComputerSciencesDept.,UniversityofWisconsin,Madison,WI,USA,199810.MeiqinPan,GuopingHe,WeizhenHou,YongliWang,ImprovedsupportvectormachinebasedonSuccessive-overrelaxation[J].ChineseJournalofElectronics,2006,15(4A):822-82511.G.FungandO.L.Mangasarian,Incrementalsupportvectormachineclassification[R],ProceedingsoftheSecondSIAMInternationalConferenceonDataMining,Arlington,Virginia,April11-13,2002,R.Grossman,H.MannilaandR.Motwani(editors),SIAM,Philadelphia2002,247-26012.G.Cauwenberghs,T.Poggio,Incrementalanddecrementalsupportvectormachinelearning[J].MachineLearning,2001,44(13):409-41513.G..Zanghirati,L.Zanni,Aparallelsolverforlargequadraticprogramsintrainingsupportvectormachines[J].ParallelComputing,2003,29:535-55114.M.Carozza,S.Rampone,TowardsanincrementalSVMforregression[J].IJCNN2000,ProceedingsoftheIEEE-INNS-ENNSInternationalJointConference,vol.6,405-41015.J.A.K.Suykens,J.Vandewalle,Leastsquaressupportvectormachinesclassifiers[J].NeuralProcessingLetters,1999,9(3):293-30090 山东科技大学博士学位论文参考文献16.J.A.K.Suykens,J.Vandewalle,Recurrentleastsquaressupportvectormachines[J].IEEETransactionsonCircuitsandSystems,2000,47(7):1109-111417.H.G.KrebelUlrich,Pairwiseclassificationandsupportvectormachines[A].In:SchoköpfBernhard(edi.).Advancedinkernelmethods:supportvectorlearning[C].Cambridge,1998,MA,MITPress,255-26818.C.J.C.Burges,Atutorialonsupportvectormachinesforpatternrecognition[J].DataminingandKnowledgeDiscovery,1998,2(2):121-16719.C.J.Lin,&J.J.Moré,Newton’smethodforlarge-scaleboundconstrainedproblems[J].SIAMJ.Optim.,1999(9):1100-112720.Y.J.LeeandS.Y.Huang.Reducesupportvectormachines:Astatisticaltheory[J].IEEETransactionsonNeuralNetworks,18:1-13,200721.G.FungandO.L.Mangasarian.Proximalsupportvectormachineclassifiers[J].InF.ProvostandR.Srikant,editorsProceedingsKDD-2001:KnowledgeDiscoveryandDataMining,August26-29,2001,SanFrancisco,CA,pp77-86,NewYork,2001.AssociationforComputingMachinery.22.Y.J.LeeandO.L.Mangasarian,RSVM:Reducedsupportvectormachines[J].InProceedingsFirstSIAMInternationalConferenceonDataMining,Chicago,April5-7,2001,CD-ROM,200123.Kuan-MingLin,Chin-JenLin,Astudyonreducedsupportvectormachines[J].IEEETransactionsonNeuralNetwork,2003,45(2):199-20424.Y.J.LeeandO.L.Mangasarian,SSVM:Asmoothsupportvectormachineforclassification[J].ComputationalOptimizationandApplications,2001,20(1):5-2225.JinHyukJung,DianneP.O’leary,andAndréL.Tits,Adaptiveconstraintreductionfortrainingsupportvectormachines[J].ElectronicTransactionsonNumericalAnalysis,2008,Volume31,156-17726.方景龙，陈铄，潘志庚，梁荣华,复杂分类问题支持向量机的简化[J].电子学报,2007,35(5):858-86127.BSchölkopfetal,Newsupportvectoralgorithms[J].NeutralComputation,2000,12:1207-124528.AJ.Smola,B.Schölkopf,K.-R.Mϋller,Theconnectionbetweenregularizationoperatorsandsupportvectorkernels[J].NeuralNetworks,1998,11:637-64929.N.Cristianini,J.Shawe-Taylor,Anintroductiontosupportvectormachinesandotherkernel-basedlearningmethods[M].CambridgeUniversityPress,200091 山东科技大学博士学位论文参考文献30.O.L.Mangasarian,Linearandnonlinearseparationofpatternsbylinearprogramming[J].OperationResearch,1965,13:444-45231.B.E.Boser,I.M.Guyon,VapnikV,Atrainingalgorithmforoptimalmarginclassifiersth[J].In:Proceedingsofthe5AnnualACMWorkshoponComputationalLearningTheory.Pittsburgh,PA,JulyACMPress,1992:144-15232.邓乃扬,田英杰,数据挖掘中的新方法—支持向量机[M].北京：科学出版社,200433.T.G..Dietterich,G.Bakiri,Solvingmulti-classlearningproblemsviaerror-correctingoutputcodes[J].JournalofArtificialIntelligentResearch,1995,2:263-286th34.V.Frac,V.Hlavac,Multi-classsupportvectormachine[J].Proceedings16InternationalConferenceonPatternRecognition,volume2:236-239,CA90720-1314,LosAlamitos,US,August200235.K.Bennett,J.Blue,Asupportvectormachineapproachtodecisiontrees[R].RensselaerPolytechnicInstitute,Troy,1997,NY:R.P.IMathReport,97-10036.C.-W.HsuandC.-J.Lin,Acomparisonofmethodsformulti-classsupportvectormachines[J].IEEETransactionsonNeuralNetworks,2002,13(2):415-42537.赵晖，荣丽丽，李晓,一种设计层次支持向量机多类分类器的新方法[J].计算机应用研究，2006，23(6):34-3738.张苗，张德贤，多类支持向量机文本分类方法[J].计算机技术与发展，第18卷，第3期，2008,139-14139.TakuyaInoue,ShigeoAbe,Fuzzysupportvectormachinesforpatternclassification[J].InProceedingsofInternationalJointConferenceonNeuralNetworks,2001,2:1449-145440.Chun-FuLin,Sheng-DeWang,Fuzzysupportvectormachines[J].IEEETransactionsonNeuralNetworks,2002,13(2):464-47141.罗文俊，李祥，多方安全矩阵乘积协议及应用.计算机学报，2005，28(7):1230-123542.A.Yao.ProtocolsforSecureComputation[A].Proc.OfIEEEFOGS’82[C],1982,160-16443.Goldreich,S.Micali,A.Wigderson.HowtoplayANYmentalgame[A].ProceedingsofthenineteenthannualACMconferenceonTheoryofcomputing[C],1987,NewYork,UnitedStates,(1):218-22944.T.Downs,K.E.GatesandA.Masters.Exactsimplificationofsupportvectorsolutions[J].JournalofMachineLearningResearch,2001(2):293-29792 山东科技大学博士学位论文参考文献45.G.Baudat,F.Anouar,Kernel-basedmethodsandfunctionapproximation[J].In:ProceedingsInternationalConferenceonNeuralNetworks,USA:WashingtonDC,2001,1244-124946.刘向东，陈兆乾,一种快速支持向量机分类算法的研究[J].计算机研究与发展，2004，41(7):1074-108047.E.Osuna,R.Freund,andF.Girosi.Trainingsupportvectormachines:Anapplicationtofacedetection[J].InProceedingsofCVPR’97,IEEE,NewYork,NY,130-13648.E.Osuna,R.FreundandF.Girosi,Animprovedtrainingalgorithmforsupportvectormachines[J].inJ.Principe,L.Giles,N.MorganandE.Wilson,editors,NeuralNetworksforSignalProcessingVII-Proceedingofthe1997IEEEWorkshop,276-28549.J.C.Platt,Fasttrainingofsupportvectormachinesusingsequentialminimaloptimization[J].inB.Schölkopf,C.Burges,A.Smola.AdvancesinKernelMethods:SupportVectorMachines,MITPress,Cambridge,MA,December199850.J.C.Platt,UsingsparsenessandanalyticQPtospeedtrainingofsupportvectormachines[J].inAdvancesinNeuralInformationProcessingSystems11,M.S.Kearns,S.A.SollaandD.A.Cohn,eds.,MITPress,1999,557-56351.S.S.Keerthi,S.K.Shevade,C.Bhattacharyya,Afastiterativenearestpointalgorithmforsupportvectormachinesclassifierdesign[J].IEEETransactionsonNeuralNetwork,2000,11(1):124-13652.S.S.Keerthi,S.K.Shevade,C.Bhattacharyya,andK.R.K.Murthy.ImprovementstoPlatt’sSMOalgorithmforSVMclassifierdesign[J].NeuralComputation,2001,13,637-64953.S.S.KeerthiandC.-J.Lin,AsymptoticbehaviorsofsupportvectormachineswithGaussiankernel[J].NeuralComputation,2003,15(7):1667-168954.S.S.Keerthi,E.Gilbert,ConvergenceofageneralizedSMOalgorithmforSVMclassifierdesign[J].MachineLearningResearch,2002,46(1/3):351-36055.S.K.Shevade,S.S.Keerthi,C.Bhattacharyya,K.R.K.Murthy,ImprovementstotheSMOalgorithmforSVMregression[J].IEEETransactionsonNeuralNetworks,2000,11(5):1188-119356.Chih-WeiHsuandChih-JenLin,ASimpleDecompositionMethodforSupportVectorMachines[J].MachineLearning,2002,46:291-31457.C.-C.ChangandC.-JLin,LIBSVM:alibraryforsupportvectormachines(Version2.3)[EB/OL].http://www.csie.ntu.edu.tw/~cilin/papers/libsvm.pdf,200193 山东科技大学博士学位论文参考文献58.C.C.Chang,C.W.Hsu,C.J.Lin,Theanalysisofdecompositionmethodsforsupportvectormachines[J].ProceedingsoftheWorkshoponSupportVectorMachines,SixteenthInternationalJointConferenceonArtificialIntelligence,1999(IJCAI99)59.F.Cristianini,N.Campbel,Thekerneladatronalgorithm:afastandsimplelearningthprocedureforsupportvectormachines[J].InProceedingof15Intl.Conf.MachineLearning.MorganKaufmanPublishers,1998:188-19660.XuleiYang,QingSong,ShengLiu.Pre-selectionofWorkingSetforSVMDecompositionAlgorithm[J].ProceedingsofInternationalJointConferenceonNeuralNetworks,Montreal,Canada,July,200561.C.-J.Lin,Ontheconvergenceofthedecompositionmethodforsupportvectormachines[J].IEEETransactionsonNeuralNetworks,2001,12(6),1288-129862.C.-J.Lin,AsymptoticconvergenceofanSMOalgorithmwithoutanyassumptions[J].IEEETransactionsonNeuralNetworks,2002,13(1):248-250light63.L.PalagiandM.Sciandrone,OntheconvergenceofamodifiedversionofSVMalgorithm[J].OptimizationMethodsandSoftware,2005,20(2):317-33464.GaryWilliamFlake,SteveLawrence,EfficientSVMRegressionTrainingwithSMO[J].MachineLearning,2002,46,271-29065.Rong-EnFan,Pai-HsuenChen,Chih-JenLin,WorkingSetSelectionUsingSecondOrderInformationforTrainingSupportVectorMachines[J].JournalofMachineLearningResearch2005,6:1889-191866.TobiasGlasmachers,ChristianIgel.Maximum-gainworkingsetselectionforSVMs[J].JournalofMachineLearningResearch,2006,7:1437-146667.S.Lucidi,L.PalagiandA.Risi,M.Sciandrone,Ontheconvergenceofhybrid~decompositionmethodsforSVMtraining[J].http://www.dis.uniromal.it/palagi/papers06/trDIS06-06.pdf68.HansUlrichSimon,OntheComplexityofWorkingSetSelection[J].TheoreticalComputerScience,2007,(382):262-27969.Xiao-fengSong,Wei-minChen,PhoebeYi-PingChen,BinJiang,CandidateworkingsetstrategybasedSMOalgorithminsupportvectormachine[J].InformationProceedingandManagement,2009,45:584-59270.P.Laskov,Animproveddecompositionalgorithmforregressionsupportvectormachines[J].AdvancesinNeuralInformationProcessingSystems12Cambridge,MA:MITPress,2000:484-49094 山东科技大学博士学位论文参考文献71.P.Laskov,Feasibledirectiondecompositionalgorithmsfortrainingsupportvectormachines[J].MachineLearning.2002,46(1/3):315-34972.RameswarDebnathandHaruhisaTakahashi,Animprovedworkingsetselectionmethodforsvmdecompositionmethod[J].SecondIEEEInternationalConferenceonIntelligentsystems,June2004,520-52373.Zhi-QiangZeng,JiGao,AnewworkingsetselectionforSMO-typedecompositionmethods[J],ProceedingsoftheFourthInternationalConferenceonMachineLearningandCybemetics,Guangzhou,August2005,4379-438474.曾志强，支持向量分类机的训练与简化算法研究[D].浙江大学博士学位论文，200775.孙剑，郑南宁，张志华,一种训练支撑向量机的改进序贯最小优化算法[J].软件学报，2002,13(10):2007-201376.N.ListandH.U.Simon,Ageneralconvergencetheoremforthedecompositionthmethod[J].InProceedingsofthe17AnnualConferenceonLearningTheory,2004,363-37777.D.HushandC.Scovel,Polynomial-timedecompositionalgorithmforsupportvectormachines[J].MachineLearning,2003(51):51-7178.FrancescoCamastra.ASVM-basedcursivecharacterrecognizer[J].PatternRecognition,2007,(40):3721-372779.K.Scheinberg,AnefficientimplementationofanactivesetmethodforSVMs[J].J.Mach.Learn.Res.7,2006,2237-225780.袁亚湘,孙文瑜,最优化理论与方法[M].北京：科学出版社，199781.梁昔明,求解凸二次规划问题的势下降内点算法[J].高等学校计算数学学报,2002(1):81-8582.贺力群,朱克强,陈开周,大规模严格凸二次规划问题的一个新算法[J].高校应用数学学报,1998,第14卷A辑,第2期,221-22883.KlausSchittkowski,Anactivesetstrategyforsolvingoptimizationproblemswithupto200000000nonlinearconstraints[J].AppliedNumericalMathematics59(2009),2999-300784.JianrongCao,AnniCai.Arobustshottransitiondetectionmethodbasedonsupportvectormachineincompresseddomain[J].Patternrecognitionletters,2007,(28):1534-154085.O.L.Mangasarian,D.R.Musicant,Activesupportvectormachineclassification[J].In:95 山东科技大学博士学位论文参考文献Lee,T.K.,Dietter,T.G.(eds.)NeuralInformationProcessingSystems2000(NIPS2000),2001,577-583.MITPress,Cambridge86.YunhaiXiao,Dong-HuiLi,AnactivesetlimitedmemoryBFGSalgorithmforlarge-scaleboundconstrainedoptimization[J].MathMethodOperationalResearch,2008,(67):443-45487.F.Facchinei,A.Fischer,C.Kanzow,Ontheaccurateidentificationofactiveconstraints[J].SIAMJournalonOptimization,1998,9,14-3288.F.Faccinei,S.Lucidi,L.Palagi,AtruncatedNewtonalgorithmforlargescaleboxconstrainedoptimization[J].SIAMJournalonOptimization,2002,12,1100-112589.W.Hager,H.Zhang,Anewactivesetalgorithmforboxconstrainedoptimization,SIAMJournalonOptimization[J].2006,17,526-55790.Z.Y.Gao,G.P.He,F.Wu,Sequentialsystemsoflinearequationalgorithmwitharbitraryinitialpoint[J].ScienceinChina,1997,27,24-3391.GuopingHe,ZiyouGao,YanlianLai,Newsequentialquadraticprogrammingalgorithmwithconsistentsubproblems[J].ScienceinChina,Ser.A.1997,40(2):137-15092.YongliWang,LifengChen,GuopingHe,Sequentialsystemsoflinearequationsmethodsforgeneralconstrainedoptimizationproblemswithoutstrictcomplementarity[J].JournalofComputationalandAppliedMathematics,2005,182:447-47193.SamuelBurer,DieterVandenbussche,Globallysolvingbox-constrainednonconvexquadraticprogramswithsemidefinite-basedfinitebranch-and-bound[J].ComputOptimAppl,2009(43):181-19594.C.J.Lin,S.Lucidi,L.Palagi,A.Risi,Decompositionalgorithmmodelforsinglylinearly-constrainedproblemssubjecttolowerandupperbounds[J].JournalofOptimizationTheoryandApplications,2009,141:107-12695.Yu-HongDai,RogerFletcher,Newalgorithmsforsinglylinearlyconstrainedquadraticprogramssubjecttolowerandupperbounds[J].Math.Program.,2006,Ser.A106:403-42196.S.Lucidi,L.PalagiandA.Risi,M.Sciandrone,Aconvergentdecompositionalgorithmforsupportvectormachines[J].ComputationOptimizationApplication,2007,38:217-23497.T.Joachims,Makinglarge-scaleSVMlearningpractial[J].InSchölkopfB.,BurgesC.J.,SmolaA.J.,eds.,AdvancesinKernelMethod-SupportVectorLearning,Cambridge,199896 山东科技大学博士学位论文参考文献98.HongQiao,Yan-GuoWang,BoZhang,Asimpledecompositionalgorithmforsupportvectormachineswithpolynomial-timeconvergence[J].TheJournalofthepatternrecognitionsociety,2007,2543-254999.ChenPai-Hsuen,FanRong-En,andLinChih-Jen.AstudyonSMO-typedecompositionmethodsforsupportvectormachines[J].IEEETransactionsonNeuralNetworks,2006(17):893-908100.M.C.Ferris,T.S.Munson,Semismoothsupportvectormachines[J].Math.Program.2004(101):185-204101.MichaelC.FerrisandToddS.Munson,Interior-pointmethodsformassivesupportvectormachines[J].SIAMJ.OPTIM,2003,Vol.12,No.3,783-804102.P.Tseng,Decompositionalgorithmforconvexdifferentiableminimization[J].JournalofOptimizationtheoryandapplications,1991,Vol.70,No.1,109-135103.R.AgrawalandR.Srikant,“Privacy-preservingdatamining”[J].inProceedingsofthe2000ACMSIGMODConferenceonManagementofData,2000,439-450104.D.AgrawalandC.C.Aggarwal,Onthedesignandquantificationofprivacypreservingdataminingalgorithms[J].InProceedingsofthetwentiethACMSIGACT-SIGMOD-SIGARTSymposiumonPrinciplesofDatabaseSystems,2001,247-255105.C.C.Aggarwal,P.S.Yu,Acondensationapproachtoprivacypreservingdatamining[J].In:LectureNotesinComputerScience,2004,Vol2992,183-199106.Y.LindellandB.Pinkas,Privacypreservingdatamining[J].InAdvancesinCryptology–CRYPTO2000,36-54.Springer-Verlag,Aug.20-24107.Y.LindellandB.Pinkas,Privacypreservingdatamining[J].JournalofCryptology,2002,15(3):177-206108.VassiliosS.Verykios,ElisaBerlino,IgorNaiFovino,LoredanaParasilitiProvenza,YucelSavgin,YannisTheodoridis,State-of-artinprivacypreservingdatamining[J].ACMSIGMODRecord,NewYork,USA,2004,33(1):50-57109.ShahDivyesh,ZhongSheng.Twomethodsforprivacypreservingdataminingwithmaliciouparticipants[J].Informationscience,2007,177,5468-5483110.ShibnathMukherjee,MadhushriBanerjee,ZhiyuanChen,AryyaGangopadhyay.Aprivacypreservingtechniquefordistance-basedclassificationwithworstcaseprivacyguarantees[J].Data&KnowledgeEngineering,2008,66,264-288111.StanleyR.M.Oliveira,OsmarR.Zaïane.Aprivacy-preservingclusteringapproachtowardsecureandeffectivedataanalysisforbusinesscollaboration[J].Computersand97 山东科技大学博士学位论文参考文献security,2007,26,81-93112.JustinZhan,MatwinStan,Acrypto-Basedapproachtoprivacy-preservingcollaborativedatamining[J].SixthIEEEInternationalConferenceonDataMining,2006113.C.Benjamin,M.Fung,KeWang,andPhilipS.Yu.Anonymizingclassificationdataforprivacypreservation[J].IEEETransactionsonKnowledgeandDataEngineering,2007,vol.19,No.5,711-725114.YuvalIshai,EyalKushilevitz,RandomizingPolynomials:anewrepresentationwithstapplicationstoround-efficientsecurecomputation[J].Proceedingsofthe41AnnualSymposiumonFoundationsofComputerScience,2000,294-304115.AlexandreEvfimievski,RamakrishnanSrikant,RakeshAgrawal,andJohannesGehrke,Privacypreservingminingofassociationrules[J].IntheEighthACMSIGKDDInternationalConferenceonKnowledgeDiscoveryandDataMining,Edmonton,Alberta,Canada,2002,217-228116.J.VaidyaandC.Clifton,SecureSetIntersectionCardinalitywithApplicationtoAssociationRuleMining[J].JournalofComputerSecurity,2005,593-622117.YuvalIshai,TalMalkin,MartinJ.Strauss,RebeccaN.Wright.Privatemultipartysamplingandapproximationofvectorcombinations[J].Theoreticalcomputerscience,2009,410,1730-1745118.李强,颜浩,陈克菲,安全多方计算协议的研究与应用[J].计算机科学,2003,Vol.30,No.8,52-55119.WenliangDuandZhijunZhan,Usingrandomizedresponsetechniquesforprivacy-preservingdatamining[J].InProceedingofthe9thACMSIGKDDInternationalConferenceonKnowledgeDiscoveryinDatabasesandDataMining,WashingtonDC,USA,August24-27,2003120.H.LipmaaS.LaurandT.Mielikäinen,Cryptographicallyprivatesupportvectormachines[J].InD.GunopulosL.Ungar,M.CravenandT.Eliassi-Rad,editors,TwelfthACMSIGKDDInternationalConferenceonKnowledgeDiscoveryandDataMining,KDD2006,Philadelphia,August20-23,2006.ACM,2006,618-624121.L.Liu,J.Wang,Z.Lin,andJ.Zhang,Avelet-baseddatadistortionforprivacy-preservingcollaborativeanalysis[J].TechnicalReport482-07,DepartmentofComputerScience,UniversityofKentucky,Lexington,KY40506,2007122.K.ChenandL.Liu,Privacypreservingdataclassificationwithrotationperturbation[J].InProceedingsoftheFifthInternationalConferenceofDataMining(ICDM’05),2005,98 山东科技大学博士学位论文参考文献589-592123.HwanjoYu,XiaoqianJiangandJaideepVaidya,Privacy-preservingsvmusingnonlinearkernelsonhorizontallypartitioneddata[J].InSAC’06:Proceedingsofthe2006ACMsymposiumonAppliedcomputing,NewYork,USA,2006,603-610124.HwanjoYu,JaideepVaidyaandXiaoqianJiang,Privacy-preservingsvmclassificationonverticallypartitioneddata[J].InProceedingsofPAKDD’06,volume3918ofLectureNotesinComputerScience,Springer-Verlag,2006,647-656125.JaideepVaidya,HwanjoYu,XiaoqianJiang,Privacy-preservingSVMclassification[J].KnowledgeandInformationSystems,2008,14:161-178126.KimDongSeong,MuhammadAnwarulAnwarulAzim,andJongSouPark,PrivacyPreservingSupportVectorMachinesinWirelessSensorNetworks[J].TheThirdInternationalConferenceonAvailability,ReliabilityandSecurity,2008,1260-1265,IEEE.127.O.L.Mangasarian,E.W.Wild,andG.M.Fung,Privacy-preservingclassificationofverticallypartitioneddataviarandomkernels[J].TechnicalReport07-02,DataMiningInstitute,ComputerSciencesDepartment,UniversityofWisconsin,Madison,Wisconsin,September2007.128.O.L.MangasarianandE.W.Wild,Privacy-preservingclassificationofhorizontallypartitioneddataviarandomkernel[J].TechnicalReport07-03,DataMiningInstitute,ComputerSciencesDepartment,UniversityofWisconsin,Madison,Wisconsin,October2007.129.O.L.MangasarianandE.W.Wild,Privacy-preservingkernelclassificationofcheckerboardpartitioneddata[J].TechnicalReport08-02,DataMiningInstitute,ComputerSciencesDepartment,UniversityofWisconsin,Madison,Wisconsin,October2008.130.A.SloinandD.Burshtein,SupportVectorMachineTrainingforImprovedHiddenMarkovModeling[J].IEEETrans.SignalProcessing,2008,vol.56,172-188131.A.H.Khandoker,M.Palaniswami,andC.K.Karmakar,SupportVectorMachinesforAutomatedRecognitionofObstructiveSleepApneaSyndromeFromECGRecordings[J].IEEETrans.InformationTechnologyinBiomedicine,2009,Vol.13,37-48132.陈晓明，李军怀，彭军，刘海玲等，隐私保护数据挖掘算法综述[J].计算机科学，2007,Vol.34,No.6,183-186133.吕品，陈年生，董武世，面向隐私保护的数据挖掘技术研究[J].计算机研究与发展，99 山东科技大学博士学位论文参考文献2006年7月，第16卷，第7期，147-149134.M.Kantarcioglu,andClifton,Privacy-preservingdistributedminingofassociationrulesonhorizontallypartitioneddata[J].IEEETransactionsonKnowledgeandDataEngineering,September2004,1026-1037135.K.P.BennettandA.Demiriz,Semi-supervisedsupportvectormachines[J].InM.S.Kearns,S.A.Solla,andD.A.Cohn,editors,AdvancesinNeuralInformationProcessingSystems,10,368-374,Cambridge,MA,1998,MITpress136.G..Fung,O.L.Mangasarian,Semi-supervisedsupportvectormachinesforunlabeleddataclassification[J].OptmizationMethodsSoftware,2001,15:29-44137.RaneswarDebnath,MasakazuMuramatsu,HaruhisaTakahashi,Anefficientsupportvectormachinelearningmethodwithsecond-orderconeprogrammingforlarge-scaleproblems[J].AppliedIntelligence,2005,23,219-239138.YusukeTorii,ShigeoAbe,Decompositiontechniquesfortraininglinearprogrammingsupportvectormachines[J].Neurocomputing,2009,72,973-984100 山东科技大学博士学位论文攻读博士期间主要成果攻读博士期间主要成果博士期间发表的论文1.HuYunhong,FangLiang,HeGuoping.Privacy-PreservingSVMClassificationonHorizontallyPartitionedDatawithSecureMulti-PartyComputation,JournalofInformationandComputationalScience,2009,Volume6,Number6,2341-2347(EI:20101812907232)2.Huyunhong,FangliangandHeguoping,Privacy-preservingSVMClassificationonVerticallyPartitionedDatawithoutSecureMulti-PartyComputation,Proceedings-5thInternationalConferenceonNaturalComputation,ICNC2009,Vol.1,543-546(EI:20101512839979)3.HuYunhong,FangLiangandHeGuoping,Twonewthree-steppredictor-correctormethodswithfifth-orderconvergenceforsolvingnonlinearequations,Proceedings-2thInternationalConferenceonComputationalIntelligenceandNaturalComputing,CINC2010,Vol.2,16-19(EI:20110213571073)4.HuYunhong,FangLiang,Aseventh-orderconvergentNewton-typemethodforsolvingnonlinearequations,Proceedings-2thInternationalConferenceonComputationalIntelligenceandNaturalComputing,CINC2010,Vol.2,13-15(EI:20110213571072)5.Huyunhong,Heguoping,FangliangandTangjingyong,Privacy-preservingSVMclassificationonarbitrarilypartitioneddata,ProceedingsoftheInternationalConferenceonProgressinInformaticsandComputing,PIC,2010,67-71(EI:20110713666454)6.HuYunhong,WangYongli,HeGuoping,AnSSLEAlgorithmforInequalityConstrainedOptimizationWithoutStrictComplementarity.ProgressinIntelligenceComputationandApplications,ISICA,Wuhan,2008,316-320(ISTP：000263829400070)7.胡运红，董玉林，支持向量机简化算法中支持向量与违背对的几何意义，山东科技大学学报，2010，29(1):95-998.胡运红,段惠琴.多分类支持向量机的算法研究,运城学院学报,2010，28(2):1-39.胡运红，朱永强，含负权最短路问题的一个改进标号法.太原科技大学学报，2008，29(6):432-43410.LiangFang,GuopingHeandYunhongHu,AnewsmoothingNewton-typemethodforsecond-orderconeprogrammingproblems,AppliedMathematicsandComputation,101 山东科技大学博士学位论文攻读博士期间主要成果215(2009),1020-1029(SCI:000269403200015EI:20093612290199)11.LiangFang,YunhongHu,ZengzheFengandGuopingHe,ANon-interiorpointContinuationAlgorithmBasedonorthogonalProjectionforSecond-orderConeProgramming,Proceedings-5thInternationalConferenceonNaturalComputation,ICNC2009,Vol.3,481-485(EI:20101512843984)12.LiangFang,GuopingHe,YunhongHu,LiSun,SomemodifiedNewton-typemethodswithorderofconvergencevariedfromtwotosixunderweakconditions.ProceedingsoftheSecondInternationalJointConferenceonComputationalScienceandOptimization，CSO，2009，637-640(EI:20094712474271)13.张杏莉，胡运红，卢新明.一种新的几何约束系统参数取值范围的计算方法.工程图学学报.2010,31(6),85-9114.Tangjingyong,Huyunhong,AMemoryGradientMethodwithaNewNonmonotoneLineSearchRule，ProceedingsoftheInternationalConferenceonProgressinInformaticsandComputing,PIC,2010,59-62(EI:20110713666456)15.Anewconvergentdecompositionalgorithmforsolvinglargescalesupportvectormachines已投稿102 山东科技大学博士学位论文攻读博士期间主要成果攻读博士期间参与和主持的科研项目1.国家自然科学基金：非线性优化的序列线性方程组算法研究与并行优化设计（项目编号：10571109），2006.1~2008.12（参与）2.国家自然科学基金：大规模非线性优化问题的并行算法及应用研究（项目编号：10971122），2010.1~2012.12（参与）3.山东省自然科学基金：求解大规模优化问题的学列线性方程组算法及其并行优化研究及利用（编号：Y2008A01），2008.12~2011.12（参与）4.山东省科技攻关项目：面向大规模数据集的隐私保护支持向量机模型及其算法研究,（编号：2009GG10001012），2008.8－2011.6（参与）5.山西省高校科技开发项目：针对大规模数据的隐私保护支持向量机算法及应用研究，（编号：20101123），2010.9－2012.9（主持）103