《支持向量机的若干算法研究》由会员分享，可在线阅读，更多相关《支持向量机的若干算法研究（115页珍藏版）》请在金锄头文库上搜索。
1、分类号：TP181密级： 公 开U D C ：单位代码： 10424学 位 论 文支持向量机的若干算法研究胡 运 红申请学位级别：博士学位 专业名称：计算机软件与理论指导教师姓名：贺 国 平职称：教授山 东 科 技 大 学二零一一年五月论文题目：支持向量机的若干算法研究作者姓名： 胡运红专业名称： 计算机软件与理论入学时间： 2008 年 9 月研究方向： 知识处理与数据挖掘指导教师： 贺国平职称： 教授论文提交日期：2011 年 4 月 20 日论文答辩日期：2011 年 6 月 11 日授予学位日期：2011 年 6 月 24 日SOME AlGORITHMS RESEARCH ON SU
2、PPORT VECTORMACHINESA Dissertation submitted in fulfillment of the requirements of the degree ofDOCTOR OF PHILOSOPHYfromShandong University of Science and TechnologybyHu YunhongSupervisor: Professor He GuopingCollege of Information Science and EngineeringMay 2011声明本人呈交给山东科技大学的这篇博士学位论文，除了所列参考文献和世所公认的
3、文献外，全部是本人在导师指导下的研究成果. 该论文资料尚没有呈交于其它任何学术机关作鉴定.博士生签名：日期：AFFIRMATIONI declare that this dissertation, submitted in fulfillment of the requirements for theaward of Doctor of Philosophy in Shandong University of Science and Technology, iswholly my own work unless referenced of acknowledge. The document h
4、as not beensubmitted for qualification at any other academic institute.Signature:Date:山东科技大学博士学位论文摘要摘要支持向量机是一种通用的学习机器, 是数据挖掘中的一项新技术，是借助于最优化方法解决机器学习问题的新工具. 其核心问题是对一个大规模凸二次规划问题进行求解.分解算法是求解支持向量机的一类基于工作集选择的有效算法.隐私保护支持向量机算法则是在隐私保护数据挖掘算法基础上新兴起来的一个研究方向，在银行、保险公司、医学研究机构等行业有着广泛的应用. 本文主要研究求解支持向量机的简化分解算法和针对分布式数
5、据的隐私保护支持向量机算法，主要工作如下：首先，通过回顾支持向量机算法的发展过程及总结其研究现状，引出本文所做的主要工作.考虑到无论是原始支持向量机模型，还是本文重点讨论的隐私保护支持向量机模型，其本质问题是对一个大规模凸二次规划的求解，因此本文首先从研究支持向量机和对应乘子之间的关系着手，并给出一个新的分解算法.第二章中，基于支持向量机模型中支持向量的重要性，对支持向量和对应乘子之间的关系进行了理论分析，并借助图形，直观地分析了支持向量相对于决策面的几何关系.同时，通过对简化算法的终止条件及工作集选择的分析，探讨了违背和最大违背 KKT 条件对的几何含义，为直观理解终止条件及工作集选择方案提
6、供理论依据.第三章中，通过对求解大规模支持向量机的分解算法中各种工作集选择方法的优劣进行比较，提出一类求解基于带有线性等式和上下界约束优化问题的大规模支持向量机模型的新分解算法. 该算法每次迭代的可行下降方向从具有偶数个分量的相对稀疏可行方向中选取. 在假设水平方向集中至少有一组下标对应的分量严格在上下界之间的前提下，证明了算法的全局收敛性，并通过数值实验验证了算法的有效性.本文的下半部分，主要研究隐私保护支持向量机算法.第四章和第五章，分别针对数据垂直分布与水平分布的情况，提出了两个隐私保护支持向量机算法. 对于数据垂直分布的情形，算法直接基于矩阵分解的理论，给出的分类器是公开的，但是未泄露
7、任何参与方的原始数据. 对于数据水平分布的情况，与已有的 SVM 分类器不同，算法借助了安全多方计算的加密技术，给出的分类器是公开的，同样也未揭露任何参与方的原始数据. 利用矩阵分解理论证明了算法的可行性. 数值实验表明我们给出的隐私保护支持向量机算法的分类精度要比 Mangasrian 的简约隐私保护支持向量机算法的分类精度高.第六章，针对数据任意分割的情况，利用数据水平分布情况下的矩阵乘积的安全性策略，提出了一个隐私保护支持向量机算法，在未揭露任何参与方的原始数据的情况下山东科技大学博士学位论文摘要给出了公开的分类器. 该算法的分类精度比 Mangasarian 给出的简约隐私保护支持向量
8、机算法的分类精度高. 最后利用矩阵分解理论证明了该算法是可行的和有效的.最后，在第七章中，给出了现有支持向量机算法中存在的及本文尚未解决的问题，提出了进一步研究的课题.关键词：数据挖掘，机器学习，支持向量机，分解算法，安全多方计算，隐私保护支持向量机山东科技大学博士学位论文AbstractAbstractSupport Vector Machine(SVM) is a kind of generalized learning machineand a new technique of data mining. It is a new tool to solve problems inmachi
9、ne learning by optimization methods. The critical problem of SVM is tosolve a large scale convex quadratic problem. Decomposition algorithm is asimple and effective method for solving SVM and its main technique is how toselect a working set. Privacy preserving support vector machine(PPSVM) is anew r
10、esearch field on the base of privacy preserving data mining(PPDM)algorithm. PPSVM is widely applied in bank, insurance company, medicalresearch institute. This paper mainly focuses on the simplified decompositionalgorithm for soving SVM and PPSVM for distributed data, and the main workis as follows:
11、Firstly, We overview current research on SVM and show our main works.As we know, the critical problem is to solve a convex quadraticprogramming problem for both original SVM model and privacy preservingsupport vectro machine model which we mainly discussed in our dissertation.In Chapter 2, Based on
12、the significance of Support Vector in generalsimplified algorithms, We theoretically analyze the relation between the SupportVectors and the corresponding multipliers and set forth the geometrical relationbetween the support vectors and the decision surface by making the graph.Furthermore, we also a
13、nalyze the geometrical meaning of the pair of violatingKKT condition by analyzing the termination conditions.In Chapter 3, By analyzing and constrasting all kinds of working setselection method, we put forward a new decomposition algorithm for soving akind of large scale SVM model with a single linear equality constraint and boxconstraints. At each iteration，a descent search direction is selected among asuitable set of sparse feasible directions which have even compo
