学位论文 > 优秀研究生学位论文题录展示

基于Excessive Gap的SVM割平面算法

作　者: 坚文进
导　师: 周水生
学　校: 西安电子科技大学
专　业: 应用数学
关键词: SVM Excessive Gap 割平面算法
分类号: TP181
类　型: 硕士论文
年　份: 2012年
下　载: 10次
引　用: 0次
阅　读: 论文下载

内容摘要

SVM是数据挖掘的一种新方法，许多SVM所处理的问题都包含大规模样本集和属性集．传统分解法处理大规模线性分类问题也是归结为求解对偶问题，这大大增加了时间和空间复杂度．SVM割平面算法直接求解原二次规划，已有研究表明它在求解这类问题时较传统分解方法要快很多．本文主要研究SVM的割平面算法：本文首先介绍了现有割平面算法——Kelly割平面算法、SVM-Perf算法和BMRM算法及其在SVM领域所取得的研究成果，指出此类割平面算法虽然收敛速度比分解法快，但其收敛性不稳定，且容易产生锯齿型波动．同时研究了基于原对偶方法的ExcessiveGap算法来极小化非光滑凸二次函数，指出该算法能保证迭代前后的解都满足ExcessiveGap条件，具有较好的稳定性同时保持了较快的收敛速度．进一步将Excessive Gap方法用于求解SVM问题，提出了一种新的SVM-ExcessiveGap割平面算法．该算法的迭代点列都是满足Excessive Gap条件的原对偶解对，它不但消除了传统割平面算法的不稳定性，而且在分类精度相差不大的情况下大大提高了割平面算法的收敛速度．实验分析表明SVM-ExcessiveGap算法和其他割平面算法相比有明显的优势．

全文目录

摘要  3-4
Abstract  4-7
第一章绪论  7-17
  1.1 支持向量机简介  7-8
  1.2 支持向量机基本理论  8-13
    1.2.1 SVM 的基本概念  8
    1.2.2 SVM 的分类及核函数  8-13
    1.2.3 多分类 SVM  13
  1.3 SVM 割平面算法概述  13-16
    1.3.1 SVM 传统算法的研究现状  13-15
    1.3.2 SVM 割平面算法的研究现状  15-16
  1.4 本文内容安排  16-17
第二章支持向量机割平面算法  17-29
  2.1 Kelly 割平面算法  17-18
  2.2 Joachims割平面算法  18-24
    2.2.1 结构化支持向量机  19-20
    2.2.2 割平面算法及性质  20-24
  2.3 BMRM 算法  24-27
    2.3.1 标准 Bundle算法  25-26
    2.3.2 BMRM 算法  26-27
  2.4 本章小结  27-29
第三章 Excessive Gap 算法  29-37
  3.1 Excessive Gap 算法  29-34
    3.1.1 问题模型构造  29-30
    3.1.2 Excessive Gap 条件  30-31
    3.1.3 有效投影  31-34
  3.2 Excessive Gap 算法收敛性分析  34-36
  3.3 本章小结  36-37
第四章基于Excessive Gap 的割平面算法  37-45
  4.1 基于 Excessive Gap 方法的 SVM算法  37-39
    4.1.1 SVM-Excessive Gap 算法  37-39
    4.1.2 其他 CPA算法性能分析  39
  4.2 SVM-Perf 算法与 SVM-ExcessiveGap算法比较  39-45
结束语  45-47
致谢  47-49
参考文献  49-53
在读期间研究成果  53-54

基于Excessive Gap的SVM割平面算法

内容摘要

全文目录

相似论文