关键词(keywords ) :基于SVM支持向量机SMO算法的机器学习
如果您不太清楚SVM的原理，那么它对于先看入门视频，帮助您理解非常实用。 然后，你可以再深入一点看这些入门文章。 作者写得很具体。 读完之后，SVM的基础好像会变得更一样。 另外，本《支持向量机导论》的作者是Nello yydrjb和John Shawe-Taylor，电子工业出版社。 书后面的SMO算法的实现基本上理解了SVM是什么样的，最后再做一个SVM库，比如用libsvm等工具，哎呀，差点就差不多了。 这些是我学习SVM的整个过程，也是经验吧。
以下是SVM的简化SMO算法。 结合Java代码，说明整个SVM的学习训练过程，也就是所谓的train训练过程。 那么什么是SMO算法呢？
SMO算法的目的就是找出能够对输入数据x进行分类的函数f(x )。 分类一定要有评价的标准。 例如，有两种情况a和b。 那么，怎么说x属于a类，还是不是b类呢？ 需要边界。 像两个国家一样有边界，边界越明显，easy就越有区别。 因此，我们的目标是最大化边界宽度，使easy区分是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但是ai
yiui=1但ai0不满意，原来ai=0
yiui=1，但是ai=0或ai=C表示不满意，本来应该是0
所以要找到并更新这些不满足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更新：
符合条件：
Web更新。 …………(6)
最后更新所有ai、y、b，模型出现并通过函数：
……………………7
输入为x，是数组，组中的每个值表示特征。
输出是a类还是b类。 (是正系还是负系)
以下是基本代码段：
/*
*默认输入参数值
* c :规则化参数
* tol: numerical tolerance
*最大路径
*/
双精度c=1； //对圈外的处罚因素
双精=0.01； //允许极限值
int maxPasses=5； //表示拉格朗日乘数的最大迭代次数没有改变
/*
初始化a[]、b、passes
*/
双精度a [ ]=new双精度[ x.lengt
h];//拉格朗日乘子this.a = a;
//将乘子初始化为0
for (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
* 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的aj
j = RandomSelect(i);
double Ej = getE(j);
//保存当前的ai和aj
double 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下载地址上提供下载。
如理解有误敬请指正！谢谢！
我的其它博客：