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