理论部分见:http://www.cnblogs.com/biyeymyhjob/archive/2012/07/17/2591592.html
http://blog.csdn.net/sunmenggmail/article/details/7445035
//这个版本的代码仅可以算是初步实现,一些代码优化还有停止条件的选择还有待改进。
#include <iostream>
#include <cmath>
using namespace std;
#define N 12 //样本空间大小
#define C 4 //惩罚参数
#define M 2 //样本维数
double b = 4;//原始问题常数参数b
double W[M]; //原始问题参数
double A[N] = {0}; //初始化对偶问题参数
//训练样本
double X[N][M] = {
{1, 2},
{1, 1},
{-2, 2},
{2, 1},
{-2, 1},
{-1, 1},
{1, 4},
{2, 3},
{3, 2},
{-1, 4},
{-2, 3},
{-3, 2}
};
double Y[] = {-1, -1, -1,-1,-1,-1, 1, 1, 1, 1, 1, 1};
//kernel tricks
double Kernel (double *x, double *y, int length)
{
double sum = 0;
for (int k = 0; k < M; k++)
sum += pow(x[k] * y[k] ,2);//将x=(x1, x2)映射到z = (z1, z2) = (x1*x1, x2*x2)上,将x空间的椭圆变换成新空间里的直线,当然,这只是实验,核函数还有很多,具体选什么样的核函数还要视情况而定。
//return pow(sum, 2);
return sum;
}
//kernel tricks for samples
double K (int i, int j)
{
return Kernel(X[i], X[j], M);
}
//tool function
double Convert(double *x)
{
int j = 0;
double sum = 0;
for (j = 0; j < N; j++)
{
sum += A[j] * Y[j] * Kernel(X[j], x, M);
}
return sum;
}
//求Ei
double E(int i)
{
return Convert(X[i]) + b - Y[i];
}
//求函数间隔,与Ei仅差一个Yi
double g(double *x)
{
return Convert(x) + b;
}
//选择两个变量进行坐标下降
bool choose(int &a1, int &a2)
{
int i;
for (i = 0; i < N; ++i)
{
//选择违反KKT的a作为第一个的变量
if ((A[i] == 0 && Y[i] * g(X[i]) < 1) || (A[i] < C && A[i] > 0 && Y[i] * g(X[i]) != 1) || (A[i] == C && Y[i]*g(X[i]) > 1))
{
a1 = i;
break;
}
else if( i == N - 1)
{
return true; //当所有参数都满足KKT时停止,无法满足时?TODO:将可行间隙比率 增加为停止条件
}
}
double e1 = E(a1);
double e, e2, max = 0;
for (i = 0; i < N; i++)
{
if (i != a1)
{
e = E(i);
if (abs(e1-e) > max)
{
max = abs(e1 - e);
a2 = i;
e2 = e;
}
}
}
double L, H;
if (Y[a1] != Y[a2])
{
L = A[a2] - A[a1] > 0 ? A[a2] - A[a1] : 0;
H = C + A[a2] -A[a1] < C ? C + A[a2] -A[a1] :C;
}
else
{
L = A[a2] + A[a1] - C > 0 ? A[a2] + A[a1] - C : 0;
H = A[a2] + A[a1] < C ? A[a2] + A[a1] :C;
}
double temp = A[a2] + Y[a2] * (e1 - e2) / (K(a1, a1) + K(a2, a2) -2 * K (a1, a2));
double old = A[a2];
A[a2] = temp < L ? L : (temp > H ? H : temp); //更新a2
A[a1] = A[a1] + Y[a1]* Y[a2] * (old - A[a2]);//更新a1
return false;
}
double compute_b(int num, int a1, int a2)
{
double sum = 0;
int t = num == 1 ? a1: a2;
for (int i = 0; i < N; i++)
{
if (i != a1 && i!= a2)
sum += A[i] * Y[i] * K(i, t);
}
return Y[t] - sum - A[a1] * Y[a1] * K(a1, t) - A[a2] * Y[a2] * K(a2, t);
}
//SMO 算法解最优化对偶问题
void SMO()
{
int a1, a2;
double b1, b2;
int i =0;
while(true)
{
i++;
if (i > 100)
break;//当停止条件改进后,就不再需要
if (choose(a1, a2))
{
//满足KKT就停止
return;
}
else//更新b
{
b1 = compute_b(1, a1, a2);
b2 = compute_b(2, a1, a2);
if ((A[a1] < C && A[a1] > 0) && (A[a2] < C && A[a2]) > 0)
{
b = b1 ;
}
if ((A[a1] == 0 || A[a1] == C) && (A[a2] == 0 || A[a2] == C) )
{
b = (b1 + b2) / 2;
}
}
}
}
int main()
{
SMO();
double test[] = {0, -5};
cout << g(test) << endl;
return 0;
}
实验结果为:2.94999 ,说明(0,-5)点是正的,其他结果同样可以验证。
SVM分类结果图:
分享到:
相关推荐
svm支持向量机python代码 机器学习语义分割-随机森林,支持向量机,GBC Machine learning semantic segmentation - Random Forest, SVM, GBC.zip
为解决有限样本学习问题提供了一个统一的框架,它能将很多现有方法纳入其中,同时,在这一理论基础上发展了一种新的通用学习方法——支持向量机(Support Vector Machine 或 SVM),它已初步表现出很多优于已有方法的...
大神给的SVM支持向量机的精髓部分,希望能有点作用
支持向量机 使用松弛变量解决非线性可分的情况 使用核SVM解决非线性问题 决策树学习 最大信息增益 构建一棵决策树 随机森林 k近邻--一个懒惰学习算法 总结 第四章 构建一个好的训练集---数据预处理 处理缺失值 消除...
使用多种方法完成MNIST分类任务 Python 3.6 Pytorch 1.0 Scikit-learn 0.21 无需下载数据直接跑,代码自动下载 逻辑回归 Logistic Regression ...支持向量机 SVM 卷积神经网络 CNN 循环神经网络 RNN
支持向量机:支持向量机(Support Vector Machine, SVM)是一类按监督学习(supervised learning)方式对数据进行二元分类的广义线性分类器(generalized linear classifier),其决策边界是对学习样本求解的最大...
《python machine learning》中第三章,支持向量机、基于核的支持向量机、案例
支持向量机(support vector machines
支持向量机(Support Vector Machine, SVM)是一类按监督学习(supervised learning)方式对数据进行二元分类的广义线性分类器(generalized linear classifier),其决策边界是对学习样本求解的最大边距超平面...
以往大部分研究主要集中在支持向量机分类理论和应用上,近年来关于支持向量机回归(SVMR)的研究也显示出其优异的性能。作为一个新的理论和方法,支持向量机回归在训练算法和实际应用等方面有诸多值得深入探讨的课题...
支持向量机(Support Vector Machine, SVM)是一类按监督学习(supervised learning)方式对数据进行二元分类的广义线性分类器(generalized linear classifier),其决策边界是对学习样本求解的最大边距超平面...
K近邻(knn)+支持向量机(SVM) 这里介绍的机器学习代码是用MATLAB编写的。 目的是通过输入使用温纳四电极技术获得的土壤的电阻率来预测土壤的类型。 该代码是论文的一部分,旨在开发一种通过测量土壤(例如粘土)...
支持向量机(Support Vector Machine, SVM)是一类按监督学习(supervised learning)方式对数据进行二元分类的广义线性分类器(generalized linear classifier),其决策边界是对学习样本求解的最大边距超平面...
SVM支持向量机核方法笔记(含推导与证明).pdf 支持向量机(Support Vector Machine, SVM)是一类按监督学习(supervised learning)方式对数据进行二元分类的广义线性分类器(generalized linear classifier),其...
支持向量机(Support Vector Machine, SVM)是一类按监督学习(supervised learning)方式对数据进行二元分类的广义线性分类器(generalized linear classifier),其决策边界是对学习样本求解的最大边距超平面...
接下来对支持向量机算法和神经网络算法进行了全面的性能比较,通过仿真实验反映两者的性能差异,详细说明了支持向量机在学习性能上的特点和优势。此外,本文讨论了支持向量机参数调整的各种方法,在构造支持向量机的过程...
支持向量机(Support Vector Machine, SVM)是一类按监督学习(supervised learning)方式对数据进行二元分类(binary classification)的广义线性分类器(generalized linear classifier),其决策边界是对学习样本...
根据《Pattern Recognition and Machine Learning》这本书的第7章(稀疏核机)的7.1节,介绍了样本数据线性可分的线性可分支持向量机和样本数据重叠的线性支持向量机,以及支持向量回归。详细介绍了公式的推导过程,...
实现的是支持向量机对输入数据的广义分类,对输出结果有一个散点图展示
新闻推荐系统使用支持向量机 介绍 从大量新闻中找到相关且有趣的新闻可能是一个困难,耗时且令人讨厌的过程。 给定用户他/她以前阅读过的文章,我们希望从数据集中推荐与该用户相关的新文章。 机器学习算法: ...