基于QPSO算法训练SVM摘要：针对群体智能和约束优化问题的特点，提出了将QPSO算法应用于求解约束优化问题，证明QPSO算法在SVM领域中具有很高的应用价值，并为解决大规模的QP问题开辟了一条新的途径。关键词：支持向量机；量子行为粒子群优化；二次规划：TP301.6文献标志码：A：1001－3695(2007)07－0094－03支持向量机(SupportVectorMachine,SVM)是在统计学习理论基础上提出的一种全新的机器学习方法，以结构风险最小化原则为理论基础，将最大分界面分类器思想和基于核的方法结合在一起，表现出了很好的泛化能力。SVM在1995年由Vapnik等人提出后，由于其出色的学习性能，该技术已成为机器学习界的研究热点，在机器学习理论和实践中都有巨大的发展，体现了其重要的意义。??训练支持向量机主要解决一个二次规划(QP)问题。经典的二次规划方法一般无法解决实际问题，尤其是大规模的实际问题，这直接影响着支持向量机的实际应用。因此，近年来很多研究者对SVM优化算法的研究非常重视，将进化算法用于优化二次规划问题，以期加深和扩大SVM应用领域的研究。在原始的粒子群算法（PSO）基础上，笔者从量子的角度提出了一种新型的能保证全局收敛的进化算法――具有量子行为的粒子群优化算法（QPSO）。QPSO算法不仅调整参数少、容易实现，而且搜索效率高，比以往进化算法的全局收敛能力都要强，其鲁棒性强、实现时间短。??1SVM原理??支持向量机主要解决的是一个二分类问题。该理论最初于数据分类问题的处理，SVM就是要寻找一个满足要求的分割平面，使训练集中的点距离该平面尽可能地远，即寻求一个分割平面使其两侧的Margin尽可能最大。支持向量机从线性可分情况下的最优分类面发展起来，通过将输入空间映射到一个高维内积空间中，解决一个线性约束的二次规划问题，得到全局最优解，保证收敛速度。它不存在局部极小值问题。??2支持向量机的优化算法??随着支持向量机的发展，出现了很多优化算法。如果训练样本的规模过大，矩阵H的规模是训练样本的平方，求解Lagrange乘子QP问题的优化算法很难处理。为了解决大规模问题，人们提出了以下算法。??最初为解决大规模SVM，Vapnik采用求解矩阵分块的算法，算法中删除矩阵中对应Lagrange乘子为零的行与列，它不会影响最终结果，因此大型QP问题可转换为一系列的小规模QP问题。该算法的每一步解决一个QP问题，其样本为上一步所剩的具有非零Lagrange乘子的样本与不满足Kuhn－Tucker条件的??M??（事先确定）个样本（若不满足Kuhn－Tucker条件的样本小于??M??个，则这些样本全部加入）。每一个子QP问题都在前一个子QP问题结果的基础上进行。这样，Chunking算法就将矩阵规模由样本个数的平方减少到具有非零Lagrange乘子的样本个数的平方，大大提高了算法效率。??与分块算法不同，分解算法每次迭代只更新若干个Lagrange乘子，而其他的乘子保持不变。将SVM中大型的QP问题转换为一系列的求解规模一定的子QP问题，每一步都保持问题满足Kuhn－Tucker条件。迭代过程中将工作集之外情况最糟的样本点和工作集中的一部分样本点进行等量交换，重新优化这个子问题，直到所有Lagrange乘子都满足Kuhn－Tucker条件，得到问题的最优解。??最小优化算法(SequentialMinimalOptimization，SMO)是分解算法的一个特例。它将工作样本集的规模减小到了两个样本，迭代过程中直接进行求解，提高了子问题的运算速度。此外，SMO算法的工作集选择采用启发式，通过两个嵌套的循环来寻找待优化的样本；外层循环寻找违反KKT条件的样本，作为工作集的第一个样本。内层循环开始选择进入工作集的第二个样本，选择的原则是尽量使这样一对样本取得最大的优化步长。这种启发式的样本选择策略大大加快了算法收敛速度。??SVMlight算法是分解算法的一个推广。其基本思想是：将所求问题的Lagrange乘子分为工作集和非工作集；如果存在不满足Kuhn－Tucker条件的样本，基于某种方式选择??q??个样本的拉格朗日乘子作为工作集，其余样本的拉格朗日乘子保持不变，作为非工作集。在这个工作集上解决QP问题。重复以上操作，直到所有样本点都满足Kuhn－Tucker条件。工作集的选取基于可行方向法。??3QPSO??QPSO是S...