[机器学习&数据挖掘]SVM---核函数

1、核函数概述:

核函数通俗的来说是通过一个函数将向量的低维空间映射到一个高维空间,从而将低维空间的非线性问题转换为高维空间的线性问题来求解,从而再利用之前说的一系列线性支持向量机,常用的核函数如下:

多项式核函数:

            

高斯核函数:

            

比如硬间隔种的目标函数为:

            

而核函数替换后的目标函数为:

             

从这个两个目标函数找共同点,其实会发现核函数是作用在特征向量上,开始的目标函数一次计算是利用了两个特征向量,而接下来的核函数是对两个特征向量做函数运算,假如将核函数利用在一次运算利用三个特征向量的计算,这时核函数就会对这三个特征向量做核函数,其实就是一个替换的问题,将两个特征向量点积运算换成一个核函数的值,仅此而已。

2、SMO算法概述:

因此接下来的处理还是求解拉格朗日乘子、w、b,因此引入SMO(序列最小最优化算法)

首先SMO算法要解决的对偶问题如下:

             

SMO算法是一种启发式算法,基本思路:如果所有变量的解都满足此最优化问题的KKT条件,那么这个最优化的问题的解就得到了,SMO算法其实就是在求解拉格朗日算子。SMO算法子问题:先选择两个变量,然后固定其他变量,针对此两个变量构建二次规划问题,子问题由两个变量,一个是违反KKT条件最严重的变量,另一个由约束条件自动确定,然后对此子问题求解,当此两个变量都满足KKT条件,则子问题求解完成。SMO算法就是将问题不断的分解为此子问题,直到所有的变量的解都满足此问题的KKT条件,从而结束算法

通过以上的对偶问题可以将子问题写成(此处假定选择两个变量alpha1、alpha2):

              

              

注意:此子问题的目标函数是从上面的对偶问题得来,在推导的过程中会发现有一些项没有,是因为这个时候只有alpha1和alpha2是变量,其他的都看作固定的值,就类似求min(f(x))和min(f(x)+C)的解x是一样的(C为常数)

3、alpha计算公式:

接下来几个公式用于每次计算:

              

注:Ei是g(x)对xi的预测值对yi的值之差

               

              

此计算的是alpha2未经过处理的值,因为各个alpha都由一个范围的,具体如下分段函数:

              

通过alpha2可以求得alpha1的新值如下:

              

4、变量选择:

(1)首先面临的是第一个变量的选择,在SMO算法的概述中我也介绍过,就是最不满足此问题的KKT条件,KKT条件为何看如下(KKT是相对于每个样本点来说的即(xi,yi)):

                  

                  g(xi)如上述的式子

第一个变量的选择是SMO的外层循环,在检验过程中,首先遍历所有满足0<alpha<C条件的样本点,即在间隔边界上的支持向量点,检验其是否满足KKT条件,如果都满足,则遍历整个训练集是否满足KKT条件,选择最不满足的点为第一个变量。

(2)其次是第二个变量的选择:第二个变量的选择是SMO的内层循环,首先假定已经选定了第一个变量,第二个变量的选择是希望能使alpha2有足够大的变化,一种简单的做法是其对应的|E1-E2|最大。在特殊的情况下,通过以上方法不能使目标函数有足够的下降,则采用向下启发规则继续选择alpha2,遍历所有的间隔边界上的支持向量点,依次将其作为alpha2试用,直到目标函数有足够的下降,若找不到则便利整个训练集;若仍找不到,则放弃alpha1,通过外层循环继续选择另外的alpha1.

(3)计算b和差值Ei

因为在每次完成两个变量的优化之后,都需要重新计算b和Ei,主要是Ei的计算需要用的b,公式如下:

      

      

      

时间: 07-20

[机器学习&数据挖掘]SVM---核函数的相关文章

机器学习&amp;数据挖掘笔记_16(常见面试之机器学习算法思想简单梳理)

http://www.cnblogs.com/tornadomeet/p/3395593.html 机器学习&数据挖掘笔记_16(常见面试之机器学习算法思想简单梳理) 前言: 找工作时(IT行业),除了常见的软件开发以外,机器学习岗位也可以当作是一个选择,不少计算机方向的研究生都会接触这个,如果你的研究方向是机器学习/数据挖掘之类,且又对其非常感兴趣的话,可以考虑考虑该岗位,毕竟在机器智能没达到人类水平之前,机器学习可以作为一种重要手段,而随着科技的不断发展,相信这方面的人才需求也会越来越大.

常见的机器学习&amp;数据挖掘知识点

常见的机器学习&数据挖掘知识点 转载请说明出处 Basis(基础): MSE(Mean Squared Error, 均方误差) RMSE(Root Mean Squared Error, 均方根误差) RRSE(Root Relative Squared Error, 相对平方根误差) MAE(Mean Absolute Error, 平均绝对误差) RAE(Root Absolute Error, 平均绝对误差平方根) LSM(Least Mean Squared, 最小均方) LSM(Le

【基础】常用的机器学习&amp;数据挖掘知识点

转自http://www.36dsj.com/archives/20135 Basis(基础): MSE(Mean Square Error 均方误差),LMS(LeastMean Square 最小均方),LSM(Least Square Methods 最小二乘法),MLE(MaximumLikelihood Estimation最大似然估计),QP(Quadratic Programming 二次规划), CP(Conditional Probability条件概率),JP(Joint P

机器学习——支持向量机(SVM)之核函数(kernel)

对于线性不可分的数据集,可以利用核函数(kernel)将数据转换成易于分类器理解的形式. 如下图,如果在x轴和y轴构成的坐标系中插入直线进行分类的话, 不能得到理想的结果,或许我们可以对圆中的数据进行某种形式的转换,从而得到某些新的变量来表示数据.在这种表示情况下,我们就更容易得到大于0或者小于0的测试结果.在这个例子中,我们将数据从一个特征空间转换到另一个特征空间,在新的空间下,我们可以很容易利用已有的工具对数据进行处理,将这个过程称之为从一个特征空间到另一个特征空间的映射.在通常情况下,这种

[matlab]机器学习及SVM工具箱学习笔记

机器学习与神经网络的关系: 机器学习是目的,神经网络是算法.神经网络是实现机器学习的一种方法,平行于SVM. 常用的两种工具:svm tool.libsvm clear; N = 50; n=2*N; randn('state',6); x1 = randn(2,N) y1 = ones(1,N); x2 = 5+randn(2,N); y2 = -ones(1,N); figure; plot(x1(1,:),x1(2,:),'bx',x2(1,:),x2(2,:),'k.'); axis([

机器学习实战——SVM(3/3)

前面两篇总结了线性支持向量机模型,总体来说,就是在样本输入空间下对每个维度进行线性组合之后使用符号函数判别最终的类别.第一个是理想情况下的线性可分SVM,这是第二个的近似线性可分SVM的基础.而且也是一种递进关系,是为了从数学抽象化的理想模型到现实情形的一种推广,但它们终究是一种线性模型,对于更复杂的现实情形有时候依然会难以描述,需要使用非线性模型去描述. 非线性SVM 由于现实问题的复杂性,导致训练的样本数据无法使用在输入空间χ=Rn(或其子集或其离散集合)下使用一个线性超平面进行分隔,对于给

机器学习:SVM实践:Libsvm的使用

引言 ? ? 本文从应用的角度出发,使用Libsvm函数库解决SVM模型的分类与回归问题 ? ? 首先说明一下实验数据,实验数据是Libsvm自带的heart_sacle,是个mat文件 ? ? 加载数据集 ? ? 将mat文件导入MATLAB后会有270*13的实例矩阵变量heart_scale_inst和270*1的标签矩阵heart_scale_label ? ? ? ? ? ? 分类 ? ? 将数据集分为训练数据和测试数据 ? ? 首先我们将实验数据分为训练数据和测试数据 ? ? loa

【模式识别】SVM核函数

下面是几种经常使用的核函数表示: 线性核(Linear Kernel) 多项式核(Polynomial Kernel) 径向基核函数(Radial Basis Function) 也叫高斯核(Gaussian Kernel),由于能够看成例如以下核函数的领一个种形式: 径向基函数是指取值只依赖于特定点距离的实值函数,也就是. 随意一个满足特性的函数 Φ都叫做径向量函数,标准的一般使用欧氏距离,虽然其它距离函数也是能够的.所以另外两个比較经常使用的核函数.幂指数核,拉普拉斯核也属于径向基核函数.

常用的机器学习&amp;数据挖掘知识点

Basis(基础):MSE(Mean Square Error 均方误差),LMS(LeastMean Square 最小均方),LSM(Least Square Methods 最小二乘法),MLE(MaximumLikelihood Estimation最大似然估计),QP(Quadratic Programming 二次规划), CP(Conditional Probability条件概率),JP(Joint Probability 联合概率),MP(Marginal Probabilit

机器学习之SVM初解与浅析(一):

sdsshngshan'gccha       这段时间在看周志华大佬的<机器学习>,在看书的过程中,有时候会搜搜其他人写的文章,对比来讲,周教授讲的内容还是比较深刻的,但是前几天看到SVM这一章的时候,感觉甚是晦涩啊,第一感觉就是比较抽象,特别是对于像本人这种IQ不怎么高的,涉及到高维向量之后,对模型的理解就比较懵了,特别是对于那个几何距离(或者说是最大间隔),一直是模棱两可,似懂非懂的感觉,本人也看了其他人写的SVM的文章,好多都没用讲清楚那个最大间隔模型 d = 1/||w|| 为什么分