基于机器学习算法的SVM优化.docx

基于机器学****算法的SVM优化
 
   
 
 
 
 
 
 
 
     
 
 
 
 
 
 
 
　　机器学****必将会设计算法的优化问题，主要是实现Platt SMO算法，那么，下面本文对SVM的优化进行了介绍，主要实现了Platt SMO算法优化SVM模型，并尝试使用遗传算法框架GAFT对初始SVM进行了优化。
　　SMO中启发式选择变量
　　在SMO算法中，我们每次需要选取一对α来进行优化，通过启发式的选取我们可以更高效的选取待优化的变量使得目标函数下降的最快。
　　针对第一个α1和第二个α2 Platt SMO采取不同的启发式手段。
　　第一个变量的选择
　　第一个变量的选择为外循环，与之前便利整个αα列表不同，在这里我们在整个样本集和非边界样本集间进行交替：
　　首先我们对整个训练集进行遍历， 检查是否违反KKT条件，如果改点的αiαi和xi，yixi，yi违反了KKT条件则说明改点需要进行优化。
　　Karush-Kuhn-Tucker（KKT）条件是正定二次规划问题最优点的充分必要条件。针对SVM对偶问题，KKT条件非常简单：
　　
　　在遍历了整个训练集并优化了相应的α后第二轮迭代我们仅仅需要遍历其中的非边界α。 所谓的非边界α就是指那些不等于边界0或者C的α值。 同样这些点仍然需要检查是否违反KKT条件并进行优化。
　　之后就是不断地在两个数据集中来回交替，最终所有的α都满足KKT条件的时候，算法中止。
　　为了能够快速选取有最大步长的α，我们需要对所有数据对应的误差进行缓存，因此特地写了个SVMUTIl类来保存svm中重要的变量以及一些辅助方法：
　　
　　下面为第一个变量选择交替遍历的大致代码，相应完整的Python实现（完整实现见）：
　　
　　第二个变量的选择
　　SMO中的第二个变量的选择过程为内循环，当我们已经选取第一个α1之后，我们希望我们选取的第二个变量α2优化后能有较大的变化。根据我们之前推导的式子
　　
　　可以知道，新的α2的变化依赖于|E1−E2|， 当E1为正时， 那么选择最小的Ei作为E2，通常将每个样本的Ei缓存到一个列表中，通过在列表中选择具有|E1−E2|的α2来近似最大化步长。
　　有时候按照上述的启发式方式仍不能够是的函数值有足够的下降，这是按下述步骤进行选择：
　　在非边界数据集上选择能够使函数值足够下降的样本作为第二个变量
　　如果非边界数据集上没有，则在整个数据仅上进行第二个变量的选择
　　如果仍然没有则重新选择第一个α1
　　第二个变量选取的Python实现：
　　
　　KKT条件允许一定的误差
　　在Platt论文中的KKT条件的判断中有一个tolerance允许一定的误差，相应的Python实现：
　　
　　关于Platt SMO的完整实现详见：
　　针对之前的数据集我们使用Platt SMO进行优化可以得到：