支持向量机(Support Vector Machines,SVM)是Vapnik等人提出的一类新型机器学习方法。由于其出色的学习性能,近年来已成为机器学习界的研究热点,并在很多领域都得到了成功的应用,如生物信息学、人脸检测、手写体数字识别等。但支持向量机尚有许多问题有待于理论和算法的发展和完善,如海量样本下求解过程的冗余问题,对强噪声的敏感问题,多类别分类问题等。这些问题制约着支持向量机在各个领域的进一步应用以及该算法对各种类型原始数据的支持。特别是对于海量样本的处理,支持向量机在训练速度和训练精度上还有待提高。高效、快速的实现方法是支持向量机进一步实用化的关键技术,因此本课题着重研究海量样本下的支持向量机的求解算法,主要从样本的预处理和工作集选择策略两方面着手,解决海量样本下支持向量机求解过程的冗余问题。本文首先详细分析了支持向量机算法及其训练过程,剖析了现有的一些算法在运算过程中的迭代机理;深入分析了支持向量机计算迭代过程中迭代缓慢的主要原因;进而从样本预处理和减少工作集选择代价方面提出了相应的改进策略,有效地加快了海量样本下支持向量机的快速训练算法。本文主要工作包括:1.系统分析了支持向量机的理论基础及其训练问题的数学描述,SVM训练问题归结为解一个带有线性等式和不等式约束的大规模凸二次规划问题。概括了SVM的泛化性能,并对当前流行的一些快速分解算法进行了详细的对比分析。2.研究了海量样本下支持向量机的样本约简策略。样本约简的目的就是将支持向量预先提取作为新的训练集,减小训练代价。本文概括了样本约简的三大思路,并提出了一种新的约简算法——基于K-邻界子聚类区的样本约简算法。该算法提出K-邻界子聚类区的概念,该区域基本覆盖了两类样本的邻界区域,有效地改善了现有算法中邻界样本提取不全的缺点。3.深入研究了SVM工作集的选择策略。工作集选择是SVM优化算法的关键步骤,直接影响着SVM的训练速度。本文重点讨论了三种常见的训练算法:SVMlight、Platt的SMO和LIBSVM。这些方法采用了可行方向法、缓存和收缩策略,极大的提高了训练速度,但也存在着迭代冗余的问题。针对这一问题,本文提出了一种新的海量样本下的快速训练算法——基于预备工作集的最小序列优化算法。该算法的预备工作集策略能够有效地避免了大量冗余的迭代计算步骤和违反KKT条件的样本排序,并引入核缓存策略,使得每次迭代的开销减少,加快了大规模样本的训练速度。