《支持向量机增量学习算法研究(1)》由会员分享，可在线阅读，更多相关《支持向量机增量学习算法研究(1)（58页珍藏版）》请在金锄头文库上搜索。
1、中南民族大学 硕士学位论文 支持向量机增量学习算法研究 姓名：李金凤 申请学位级别：硕士 专业：计算机应用 指导教师：覃俊 2011-05-03 中南民族大学硕士学位论文 I 摘 要 Vapnik 于 1995 年提出支持向量机 （Support Vector Machine， SVM） 这一针对分类和回归问题的统计学习理论，是利用线性函数假设高维 特征空间的学习系统。支持向量机自推出即刻成为机器学习和模式识 别领域的研究热点，而且因其全局最优以及推广能力强的优点，近几 年无论是在理论上还是应用上都得到了广泛的关注并取得了诸多成 果。但由于支持向量机方法复杂，导致在处理大规模数据集时存在相 关
2、问题。因此本文从降低时间和空间复杂度的角度出发，主要针对支 持向量机的增量学习问题展开以下几个方面的研究。 首先介绍了统计学习理论与支持向量机方法，这一部分是后续研 究内容的理论前提。 描述并比较了目前研究与应用较多的几种支持向量机增量学习算 法，分析了基于支持向量和基于 KKT 条件等代表算法的特点和不足； 吸取了基于超球支持向量机增量学习策略中的几何知识，以及借鉴了 渐进式增量学习策略适合处理较大规模数据集的优势，为下面即将提 出的改进算法提供了思路和方法。 在上述分析总结的基础上，提出了一种基于壳向量的支持向量机 渐进式增量学习算法；在增量学习的过程中，首先在原始样本中提取 出壳向量，将
3、其作为新的训练样本集，这样很大程度上降低了求取支 持向量过程中的二次优化时间；同时利用由原始分类器所确定的 KKT 支持向量机增量学习算法研究 II 条件来淘汰一部分新增样本，以降低新增样本的数量及其训练的时间。 总之，该算法在训练过程中对历史样本以及新增样本较好地实现了有 选择性的遗忘淘汰机制，同时保证良好的分类精度。仿真实验表明了 算法的有效性。 最后，将所提出来的支持向量机增量学习算法在手写数字识别系 统中进行了应用研究。 关键词：增量学习，支持向量机，统计学习理论，手写数字识别，分 类 中南民族大学硕士学位论文 III ABSTRACT Support Vector Machine (
4、SVM) is proposed by Vapnik in 1995 for the classification and regression in statistical learning theory. Because of its global optimum and good generalization, it has become a popular ongoing research focus of machine learning and pattern recognition. In recent years, both the theory and application
5、 have been extensively studied, and achieved some important achievements. However, the time and space complexity of support vector machine is a bottleneck in processing large-scale data. Thus, this thesis will give some researches about incremental learning based on SVM to overcome the shortcomings
6、of SVM in accuracy and speed of classification. This research works mainly around the following aspects: First, outline the basis content of our research: statistical learning theory and support vector machine approach, which are the groundwork of the follow-up study works. Several incremental learn
7、ing algorithms based on SVM are described and compared, characteristics and disadvantages of several representative algorithms based on support vectors and KKT conditions are analyzed. Then geometric knowledge from Hyper-sphere SVM and advantages in dealing with large-scale data from a gradual incre
8、mental SVM learning 支持向量机增量学习算法研究 IV strategy, which provide a theoretical support for the following proposed improved algorithm. A gradual incremental learning algorithm based on hull vector SVM is proposed. In the incremental learning process, a set of hull vectors are extracted from original trai
9、ning samples to become new training simples firstly, then KKT conditions which is determined by initial classification to select a new sample set, effectively reduces the need time for original and new training samples. In short, the algorithm achieved selective forgotten and elimination in both his
10、torical training data and new training data, while still ensuring good classification accuracy. Simulations showed the effectiveness of the algorithm. The algorithm is applied in the handwritten digit recognition area. KEY WORDS: Incremental learning, Support Vector Machine, Statistical Learning The
11、ory, handwritten digit recognition, Classification 中南民族大学中南民族大学 学位论文原创性声明学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取 得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其 他个人或集体已经发表或撰写的成果作品。 对本文的研究做出重要贡献的个 人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果 由本人承担。 作者签名： 日期： 年 月 日 学位论文版权使用授权书学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学 校保留并
12、向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查 阅和借阅。 本人授权中南民族大学可以将本学位论文的全部或部分内容编入 有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本 学位论文。 本学位论文属于 1、保密，在_年解密后适用本授权书。 2、不保密。 （请在以上相应方框内打“” ） 作者签名： 日期： 年 月 日 导师签名： 日期： 年 月 日 中南民族大学硕士学位论文 1 第 1 章 绪 论 1.1 研究背景 自 20 世纪 60 年代至 20 世纪 90 年代初期，Vapnik 及其合作者致力于最大间 隔统计学习理论的研究，于 1992 年得到相应的支持向量机（
13、Support Vector Machine, SVM）分类器设计算法1，之后支持向量机便受到广泛的关注，在 90 年 代后期得到更加深入的发展，现已成为模式识别和数据挖掘领域中的标准工具。 该方法由有限数据集得到判别函数对独立的测试集依然能够得到较小的误 差，即在分类器的复杂度和学习能力之间寻求最佳折衷，尽量提高学习机的推广 能力2。此外，支持向量机的全局最优特性保证了全局最优解，这些特点都使得支 持向量机在字符识别、语音识别、图像理解、人脸辨别、数据挖掘和信号处理等 众多领域取得了成功的应用。 近年来，支持向量机（SVM）的理论已经取得重大发展，在我国也有大量的学 者深入这方面的研究3,4
14、。尽管支持向量机以及相关的统计学习理论已经发展地逐 渐成熟，但仍然存在一些困难和问题：1）支持向量机核函数参数的选择和构造还 停留在经验性阶段，缺乏理论指导；2）实际中的问题各有不同，如何针对这些不 同设计对应的改进算法；3）实际问题中的样本往往是海量多类别的，算法本身具 有较高的时间复杂度和空间复杂度而不适于处理较大规模的样本，如何解决这一 问题，保证在最小化误差的前提下，提高训练速度急需继续研究。 1.2 国内外研究现状 在分类方面，通常用二次判别函数（MQDF） 、人工神经网络（ANN） 、支持 向量机（SVM）以及隐马尔科夫模型（HMM）等模式识别理论进行分类器设计， 很多学者对上述方
15、法做了深入的研究。 （1）二次判别函数（MQDF） ：基于 Bayes 决策理论的统计分类方法。通过截 止类协方差的特征值， 避免小样本带来的“过拟合”现象。 Long 和 Jin 针对脱机手写 支持向量机增量学习算法研究 2 汉字这种大字符集的识别问题，研究了利用 MQDF 方法进行分类器设计5。 （2）人工神经网络(ANN)：针对手写汉字识别的问题，已有很多基于 ANN 的 方法。比如，基于联想存储模型的汉字识别、多项式分类器(PC)、基于多层感知器 模型的汉字识别6、径向基基函数(RBF)7等。一般情况下，基于 ANN 的手写汉字 识别需要大量的训练样本，且其训练的时间复杂度也较高。 （
16、3）支持向量机(SVM)：V. Vapnik 等人提出的基于统计学习理论的分类回归 学习方法。自提出以来，支持向量机一度成为研究热点8。它依据结构风险最小化 原则，具有较强的泛化能力。 （4）隐马尔科夫模型9（HMM） ：1990 年，B.-S. Jeng 在汉字识别领域首次尝 试 HMM，随后，冯兵和丁晓青在手写汉字识别中引入了离散 HMM。 上述几种传统方法都要求训练样本采集完整，而实际存在样本需陆续采集得 来的情况，对此，有学者从增量式学习的角度对分类器设计进行了研究，且在数 字和联机手写体识别上做了实验。 桑农等10提出一种基于改进的最小距离分类器的增量学习算法，针对正态分 布的样本集提出一种筛选算法，只保留有代表性的少量样本，大大减少了开销且 识别准确率较高。Cheng 等11提出了一种基于动态
