改进SVM快速训练算法

摘要

随着信息化时代的到来，信息以几何级数的方式增加，人们希望从纷繁冗杂的信息中快速地提取出有用的数据。为了更快的找寻出有效的数据，就需要借助于更为有效的分类方法。鉴于支持向量机的分类方法具有推广能力强、能找到全局最优等优势，使它成为学者们关注的焦点。在运用支持向量机的过程中，由于数据集规模的不断增加，模型在训练时间上仍不能满足人们的需求，因此本文针对支持向量机的众多训练算法中运用最为广泛的序贯最小优化算法(SMO)进行了一系列的改进工作，并提出了一种综合改进策略来弥补训练时间上的不足。
　　所做的工作内容如下:
　　第一，针对标准的SMO算法存在的不足，本文提出一系列的改进策略，包括有通过跳过部分非支持向量来缩减训练集规模，松弛KKT条件来收缩工作集，提前结束不必要的循环来提高算法的训练速度等3个步骤。在保证一定精度的前提下，这些策略能有效的克服训练时间过长的不足。
　　第二，考虑到训练集可能并不完备，仍会有数据不断加入到训练集中导致训练集规模的不断扩大，本文提出了一种基于SMO的增量学习方法，该方法改进了标准SMO算法以适应增量学习，用KKT条件来判断新增样本，并对不满足条件的样本与支持向量一同训练，保留了学习的历史性，也体现了学习的延续性，通过增量学习来减少训练时间。
　　第三，将增量学习方法与前面的改进SMO的策略相结合，在增量学习的模型训练过程中把改进SMO的策略加入其中，达到两者优势互补，形成了一种综合优化的新策略来更有效的提高算法的训练速度。
　　通过使用UCI数据集上的部分测试数据对本文提出的改进策略、增量学习方法、综合优化策略进行测试和对比，实验结果良好，从而表明了这一系列的策略能够在精度变化不大的前提下明显地提高支持向量机的训练速度。

目录

声明

摘要

第一章 绪论

1．1 论文选题的意义

1．2 研究现状

1．3 本文研究的主要内容

1．4 本文的组织结构

第二章 支持向量机与训练算法

2．1 支持向量机

2．1．1 分类问题

2．1．2 线性可分情况下的支持向量机

2．1．3 线性不可分情况下的支持向量机

2．1．4 核函数

2．2 训练算法

2．2．1 算法综述

2．2．2 块算法

2．2．3 固定工作集的分解算法

2．2．4 SMO算法

2．3 本章小结

第三章 一种改进SMO的方法

3．1 SMO算法的不足点

3．2 改进策略

3．3 本文的改进思路

3．3．1 跳过部分非支持向量

3．3．2 收缩工作集策略

3．3．3 提前结束不必要的循环

3．4 改进算法的步骤

3．5 本章小结

第四章 SMO的增量学习算法

4．1 问题的引出

4．2 基于SMO的增量学习方法

4．2．1 支持向量及新增训练样本分析

4．2．2 增量学习算法

4．3 算法的流程图

4．4 综合改进策略

4．5 本章小结

第五章 实验与分析

5．1 数据集的情况描述

5．2 实验与分析

5．2．1 改进SMO算法的相关实验

5．2．2 增量算法的相关实验

5．2．3 综合改进策略的相关实验

5．3 本章小结

第六章 总结和展望

6．1 总结

6．2 展望

参考文献

在校期间发表的论文、科研成果等

致谢