关键字(keywords)：SVM支持向量机 SMO算法 实现机器学习
如果您不太了解SVM的原理，请先阅读入门的3358www.Sina.com/。 有助于理解。 然后，再深入一点看看这些3358www.Sina.com/。 作者写得很详细，看完要好好了解SVM的基础，再买《支持向量机导论》作者，然后书后面的SMO算法的实现基本上就是了解SVM是什么样的，最后再做一个SVM库出来例如，使用libsvm等工具，啊，是的。 这些是我学习SVM的整个过程，也是经验吧。
以下是SVM的简化SMO算法。 结合Java代码，说明整个SVM的学习训练过程，即所谓的train训练过程。 那么什么是SMO算法呢？
SMO算法的目的就是找到可以对输入数据x进行分类的函数f(x )。 分类一定要有评价的标准。 例如，分类有两种情况a和b。 那么，怎样才能说x属于A类或者不是B类呢？ 像两个国家一样需要有边界的边界，边界越清晰就越容易区分。 因此，我们的目标是最大化边界的宽度，以便于区分是A类还是B类。
在SVM中，边界最大化需要最小化此值。
w :参数，值越大边界越清晰
c表示惩罚系数。 也就是说，如果某个x属于某个类，但它脱离了该类，去了边界上后者的其他类的地方，c越大表示越不想放弃这一点，边界会缩小
代表：松散变量
但是，问题似乎还很难解决。 另外，由于SVM是凸二次规划问题，所以凸二次规划问题有最优解。 因此，问题会转换为以下形式。 (KKT条件)。
…………(1)
这里的ai是拉格朗日乘数。 (问题用拉格朗日乘数来解决) )。
(a )的情况下，ai为正常分类，表示位于边界内部(知道正确分类的点yi*f(Xi )=0) ) ) ) ) ) ) ) ) ) ) ) ) )。
) b )的情况下，表示ai是支持向量，位于边界上
在(c )的情况下，ai表示位于两个边界之间
最优解必须全部满足KKT条件，即(a )、(b )、(c )条件
如果发生以下情况，就会产生不满。
yiui=1，但在aiC中不能满足，原本是ai=C
yiui=1，但ai0未被满足，原本ai=0
yiui=1，但ai=0或ai=C表示不满足，本来应该是0aiC
所以发现并更新不满足KKT的这些ai，但这些ai还有另一个约束，即
因此，用同时更新ai和aj的其他方法，满足以下等式
可以保证和0的约束。
利用yiai yjaj=常数消去ai，得到关于单变量aj的凸二次规划问题，可以不考虑其约束0=aj=C而得到其解。
…………………………
这里………………((3) ) ) ) ) ) ) )。
如果显示旧的值，并考虑约束0=aj=C，则a的分析解如下。
…………(4)
关于
那么，如何求得ai和aj呢？
对于ai，即第一个乘法，可以在几个不满足如上所述的KKT的条件下进行搜索，第二个乘法aj可以满足条件
.. 5
b更新：
"text-align: left;">在满足条件：下更新b。……………（6）
最后更新所有ai，y和b，这样模型就出来了，然后通过函数：
……………………………………………………（7）
输入是x，是一个数组，组中每一个值表示一个特征。
输出是A类还是B类。（正类还是负类）
以下是主要的代码段：
/* * 默认输入参数值 * C: regularization parameter * tol: numerical tolerance * max passes */double C = 1; //对不在界内的惩罚因子double tol = 0.01;//容忍极限值int maxPasses = 5; //表示没有改变拉格朗日乘子的最多迭代次数/* * 初始化a[], b, passes */double a[] = new double[x.length];//拉格朗日乘子this.a = a;//将乘子初始化为0for (int i = 0; i < x.length; i++) {a[i] = 0;}int passes = 0;while (passes < maxPasses) {//表示改变乘子的次数（基本上是成对改变的）int num_changed_alphas = 0;for (int i = 0; i < x.length; i++) {//表示特定阶段由a和b所决定的输出与真实yi的误差//参照公式(7)double Ei = getE(i);/* * 把违背KKT条件的ai作为第一个 * 满足KKT条件的情况是： * yi*f(i) >= 1 and alpha == 0 (正确分类) * yi*f(i) == 1 and 0<alpha < C (在边界上的支持向量) * yi*f(i) <= 1 and alpha == C (在边界之间) * * * * ri = y[i] * Ei = y[i] * f(i) - y[i]^2 >= 0 * 如果ri < 0并且alpha < C 则违反了KKT条件 * 因为原本ri < 0 应该对应的是alpha = C * 同理，ri > 0并且alpha > 0则违反了KKT条件 * 因为原本ri > 0对应的应该是alpha =0 */if ((y[i] * Ei < -tol && a[i] < C) ||(y[i] * Ei > tol && a[i] > 0)) {/* * ui*yi=1边界上的点 0 < a[i] < C * 找MAX|E1 - E2| */int j;/* * boundAlpha表示x点处于边界上所对应的 * 拉格朗日乘子a的集合 */if (this.boundAlpha.size() > 0) {//参照公式(5)j = findMax(Ei, this.boundAlpha);} else //如果边界上没有，就随便选一个j != i的ajj = RandomSelect(i);double Ej = getE(j);//保存当前的ai和ajdouble oldAi = a[i];double oldAj = a[j];/* * 计算乘子的范围U, V * 参考公式(4) */double L, H;if (y[i] != y[j]) {L = Math.max(0, a[j] - a[i]);H = Math.min(C, C - a[i] + a[j]);} else {L = Math.max(0, a[i] + a[j] - C);H = Math.min(0, a[i] + a[j]);}/* * 如果eta等于0或者大于0 则表明a最优值应该在L或者U上 */double eta = 2 * k(i, j) - k(i, i) - k(j, j);//公式(3)if (eta >= 0)continue;a[j] = a[j] - y[j] * (Ei - Ej)/ eta;//公式(2)if (0 < a[j] && a[j] < C)this.boundAlpha.add(j);if (a[j] < L) a[j] = L;else if (a[j] > H) a[j] = H;if (Math.abs(a[j] - oldAj) < 1e-5)continue;a[i] = a[i] + y[i] * y[j] * (oldAj - a[j]);if (0 < a[i] && a[i] < C)this.boundAlpha.add(i);/* * 计算b1， b2 * 参照公式(6) */double b1 = b - Ei - y[i] * (a[i] - oldAi) * k(i, i) - y[j] * (a[j] - oldAj) * k(i, j);double b2 = b - Ej - y[i] * (a[i] - oldAi) * k(i, j) - y[j] * (a[j] - oldAj) * k(j, j);if (0 < a[i] && a[i] < C)b = b1;else if (0 < a[j] && a[j] < C)b = b2;else b = (b1 + b2) / 2;num_changed_alphas = num_changed_alphas + 1;}}if (num_changed_alphas == 0) {passes++;} else passes = 0;}return new SVMModel(a, y, b);
运行后的结果还算可以吧，测试数据主要是用了libsvm的heart_scale的数据。
预测的正确率达到73%以上。
如果我把核函数从线性的改为基于RBF将会更好点。
最后，说到SVM算法实现包，应该有很多，包括svm light，libsvm，有matlab本身自带的svm工具包等。
另外，完整的代码，我将上传到CSDN下载地址上提供下载。
点击这里下载。
如理解有误敬请指正！谢谢！
我的邮箱：chen-hongqin@163.com
我的其他博客：
百度：http://hi.baidu.com/futrueboy/home
javaeye：http://futrueboy.javaeye.com/
CSDN: http://blog.csdn.net/techq