支持向量机SVM算法推演,数据挖掘领域十大经典

2019-08-03 04:49栏目:奥门新萄京娱乐场
TAG:

引入黑科技-核函数

图片 1

首先,SVM将函数间隔(left| W^{T}X b right| ,将特征值代入分离超平面的方程中,得到的绝对值)归一化,归一化的目的是除掉取值尺度的影响;其次,对所有元素求到超平面的距离,(这个距离是frac{left| W^{T}X b right| }{left| W right| } ,也就是几何间隔)。给定一个超平面P,所有样本距离超平面P的距离可以记为d_{ij}=frac{left| W^{T}X b right| }{left| W right| } ,这其中最小的距离记为D_{P},SVM的作用就是找到D_{P}最大的超平面。

图片 2

将以上结果带入L函数然后化简,你会惊奇的发现松弛变量竟然消失了!得到了和之前一样的目标函数:

• 当训练数据训练可分时,通过硬间隔最大化,可学习到硬间隔支持向量机,又叫线性可分支持向量机

图片 3

如果我们将原始的一维特征空间映射到二维特征空间X^{2}和x,那么就可以找到分离超平面X^{2}-X=0。当X^{2}-X<0的时候,就可以判别为类别1,当X^{2}-X>0 的时候,就可以判别为类别0。如下图:

六、线性不可分情况

SVM(Support Vector Machine)中文名为支持向量机,是常见的一种判别方法。在机器学习领域,是一个有监督的学习模型,通常用来进行模式识别、分类以及回归分析。

同样转为对偶问题,让L先对w,b和

在实际应用中,我们往往遇到这样的问题:给定一些数据点,它们分别属于两个不同的类,现在要找到一个线性分类器把这些数据分成两类。

图片 4

图片 5

图片 6

图片 7

用黑圈圈起来的那个蓝点是一个 outlier ,它偏离了自己本应所在的那个半空间,若直接忽略掉它,超平面还是挺好的,但是由于 outlier 的出现,分隔超平面被挤歪,变成途中黑色虚线,同时间隔也相应变小了。若这个 outlier 再往右上移动一点,也许我们将无法建立成超平面。

支持向量机 VS 感知器和逻辑回归

图片 8

运行结果

图片 9

在高维(n>3)空间呢?就需要用到n-1维的超平面将空间切割开了。那么抽象的归纳下:

如下图中间的实线就是所找的超平面,两条虚线间隔边界上的点就是支持向量,这些支持向量在虚线间隔边界上,那么满足:

上图中,对于目前的训练数据,绿色和黑色的直线(二维特征空间,分离超平面就是直线啦)都可以很可以很好的进行分类。但是,通过已知数据建立分离超平面的目的,是为了对于未知数据进行分类的。在下图中,蓝色的星星图案就是新加入的真实数据。

图片 10

图片 11

分类函数为:

图片 12

【干货】支持向量机SVM算法推演

SVM三种模型

图片 13

逻辑回归的公式是g(z)=frac{1}{1 e^{-z}} ,图像大概长这个样子:

图片 14

SVM有三种模型,由简至繁为

图片 15

比如,原始的输入向量是一维的,0< x <1的类别是1,其他情况记做-1。这样的情况是不可能在1维空间中找到分离超平面的(一维空间中的分离超平面是一个点,aX b=0)。你用一个点切一下试试?

图片 16

图片 17

又有几何间隔的定义有:

图片 18

图片 19

测试数据集为经过二分类处理后的MNIST数据集,获取地址train_binary.csv

其中x是n维自变量,函数g即为logistic函数,而

线性分类器起源

图片 20

责任编辑:

图片 21

W^{T}X b=0

那么只剩下b可以这样表示

利用特征映射,就可以将低维空间中的线性不可分问题解决了。是不是很神奇,这就是特征映射的牛逼之处了。核函数除了能够完成特征映射,而且还能把特征映射之后的内积结果直接返回,大幅度降低了简化了工作,这就是为啥采用核函数的原因。

图片 22

图片 23

图片 24

• 逻辑回归(虽然称作回归,但是不是一个回归方法,却是一个分类算法。很蛋疼的说)将线性分类器的超平面方程计算结果通过logistic函数从正负无穷映射到0到1。这样,映射的结果就可以认为是分类器将x判定为类别1的概率,从而指导后面的学习过程。

本文旨在进一步理顺SVM的算法思路,加深理解,关于SMO算法、KKT法则以及核函数的介绍并不细致(以后有机会逐个拿出来介绍),算是一个粗略的学习笔记,欢迎各位大神指正、拍砖、给出好的建议,无论是关于SVM的还是其他算法抑或机器学习的任何方面。

代码已在github上实现,这里也贴出来

图片 25

举个例子,看天气预报,用感知器的天气预报只会告诉你明天要下雨(y=1),或者明天不下雨(y=-1);而用了逻辑回归的天气预报就能告诉你明天有90%的概率要下雨,10%的概率不下雨。

图片 26

继续刚才那个数轴。

关于SVM的深层理论我也不是理解的很透彻,本文仅作学习笔记之用,还有很多细节需要来回追究,还是那句话,欢迎各位大神指正、拍砖、给出好的建议,无论是关于SVM的还是其他算法抑或机器学习的任何方面。

图片 27

图片 28

代码

化简可得(此化简过程用到了线性代数的转置和乘积运算,感兴趣可以自己推导,并不难):

怎么用呢?比如感知器模型中,将特征代入判别方程中,如果得到的值是-3,我们可以判定类别是-1(因为-3<0)。而逻辑回归中呢,将-3代入g(z),我们就知道,该数据属于类别1的概率是0.05(近似数值,谢谢),那么属于类别-1的概率就是1 – 0.05 = 0.95。也就是用概率的观点描述这个事情。

为样本x到超平面的距离,如下图:

那么绿线和黑线留下谁?我们认为,已有的训练数据中,每个元素距离分离超平面都有一个距离。在添加超平面的时候,尽可能的使最靠近分离超平面的那个元素与超平面的距离变大。这样,加入新的数据的时候,分的准的概率会最大化。感知器模型和逻辑回归都不能很好的完成这个工作,该我们的支持向量机(support vector machine,SVM)出场了。

《统计学习方法》李航

• 当训练数据训练近似可分时,通过软间隔最大化,可学习到软间隔支持向量机,又叫线性支持向量机

就能求出w,b)。

如果用x表示数据点,用y表示类别(y取1或者-1,代表两个不同的类),一个线性分类器的学习目标便是要在n维的数据空间中找到一个超平面(hyper plane),把空间切割开,这个超平面的方程可以表示为(W^{T}中的T代表转置):

图片 29

这时候我们就可以看出不同的分离超平面的选择对于分类效果的影响了。有的绿线会将三个点都划归蓝色圆圈,有的绿线会将三个点都划归红色正方形。

图片 30

• 分类器:分类器就是给定一个样本的数据,判定这个样本属于哪个类别的算法。例如在股票涨跌预测中,我们认为前一天的交易量和收盘价对于第二天的涨跌是有影响的,那么分类器就是通过样本的交易量和收盘价预测第二天的涨跌情况的算法。

图片 31

相关概念

,则有了

在三维空间中呢,需要用一个平面把空间切成两半,对应的方程是X1 X2 X3=1,也就是[1,1,1]^{T}[X1,X2,X3]-1=0 。

《支持向量机导论》Nello Cristianini, John Shawe-Taylor

在二维空间中,用一条直线就把空间分割开了:

图片 32

• 常见的线性分类器有感知器模型和逻辑回归。上一节举出的例子是感知器模型,直接给你分好类。有时候,我们除了要知道分类器对于新数据的分类结果,还希望知道分类器对于这次分类的成功概率。逻辑回归就可以做这件事情。

图片 33

根据上面的讨论,我们知道了在多维空间下,用一个超平面就把数据分为了两类。这个超平面我们叫它为分离超平面。但是这个分离超平面可以有很多个,那么用哪个呢?

(求出了

原标题:数据挖掘领域十大经典算法之—SVM算法

图片 34

• 特征:在分类问题中,输入到分类器中的数据叫做特征。以上面的股票涨跌预测问题为例,特征就是前一天的交易量和收盘价。

图片 35

感知器模型和逻辑回归:

的求解可以用一种快速学习算法SMO,至于核函数,是为处理非线性情况,若直接映射到高维计算恐维度爆炸,故在低维计算,等效高维表现。

这就要说到SVM的黑科技—核函数技巧。核函数可以将原始特征映射到另一个高维特征空间中,解决原始空间的线性不可分问题。

图片 36

简介

的求解(求解过程中会涉及到一系列最优化或凸二次规划等问题),如此,求w.b与求

可以看出,大部分数据对于分离超平面都没有作用,能决定分离超平面的,只是已知的训练数据中很小的一部分。这与逻辑回归有非常大的区别。上图中,决定黑色的这条最优分离超平面的数据只有下方的两个红色的数据点和上方的一个蓝色的数据点。这些对于分离超平面有着非常强大影响的数据点也被称为支持向量(看没看到,这就是传说中的支持向量啦,原来如此)。

由于对偶形式是线性学习器的一个重要性质,这意味着假设集可以表示为训练点的线性组合,因此决策规则可以用测试点和训练点的内积来表示:

怎么分呢?把整个空间劈成两半呗(让我想到了盘古)。用二维空间举个例子,如上图所示,我们用一条直线把空间切割开来,直线左边的点属于类别-1(用三角表示),直线右边的点属于类别1(用方块表示)。

图片 37

本周干货:探究Hindon的Capsules理论的实现行踪返回搜狐,查看更多

为单位向量,又有x0位于超平面上,满足f(x0)=0, 带入

再将X^2-X=0映射回原始的特征空间,就可以知道在0和1之间的实例类别是1,剩下空间上(小于0和大于1)的实例类别都是0啦。

上面化简得到

图片 38

图片 39

• 当训练数据训练不可分时,通过软间隔最大化及核技巧(kernel trick),可学习到非线性支持向量机

对数据点进行分类时,数据点距离超平面的间隔越大则超平面分类的确信度就越高,因此我们需要让找到的超平面使得数据点距离超平面的间隔最大化,如下图间隔:

• 线性分类器:线性分类器是分类器中的一种,就是判定分类结果的根据是通过特征的线性组合得到的,不能通过特征的非线性运算结果作为判定根据。还以上面的股票涨跌预测问题为例,判断的依据只能是前一天的交易量和收盘价的线性组合,不能将交易量和收盘价进行开方,平方等运算。

根据函数间隔的定义有:

如果用数学语言呢,就是这样的:空间是由X1和X2组成的二维空间,直线的方程是X1 X2 = 1,用向量符号表示即为[1,1]^{T}[X1,X2]-1=0 。点x在直线左边的意思是指,当把x放入方程左边,计算结果小于0。同理,在右边就是把x放入方程左边,计算出的结果大于0。都是高中数学知识。

由平面几何知识知道有:

上面说的都是在原始特征的维度上,能直接找到一条分离超平面将数据完美的分成两类的情况。但如果找不到呢?

图片 40

图片 41

这样就得出了分离超平面和分类函数。

这样求出

图片 42

此时拉格朗日函数只包含一个变量

图片 43

图片 44

图片 45

图片 46

八、引入松弛变量处理 outliers

图片 47

一、逻辑回归

图片 48

图片 49

通过以上推导我们知道所谓超平面其实就是把自变量x带入:

,让L对w,b求偏导:

由(1)得知:

图片 50

图片 51

图片 52

在L对w,b最小化以及对

等价于:

四、原始问题转化为对偶问题

此时若成比例的改变w和b(比如2w,2b),那么函数间隔也会同比例改变,而此时超平面并未发生改变,间隔却是不确定的!因此需要引出几何间隔,才能更精准的描述样本点到超平面度的距离。

目前我们的支持向量机分类器还只能处理线性分类,为推广到非线性形式,下面稍稍介绍下核函数。

,又有

(1)、先固定

,因此有

了解更多:

,那么整个目标函数和约束条件可以写做:

SVM本质上是一个分类方法,用w^T b定义分类函数,于是求w、b,为寻最大间隔,引出1/2||w||^2,继而引入拉格朗日因子,化为对拉格朗日乘子

在原本我们的约束条件上考虑到outliers的因素:

如下图一堆数据点在二维空间中不可分,映射带到三维空间中划分:

来源:海阔心

表示此问题的最优值,同原始问题等价。为易于求解,我们调换最大和最小的位置:

图片 53

五、对偶问题的求解

而超平面(w,b)关于所有样本点的函数间隔最小值便为超平面(w,b)关于训练数据集(xi,yi)的函数间隔(其中x表示特征,y表示类别标签,i表示第i个样本):

图片 54

,又有可以求出w:

图片 55

会因为w和b的缩放而等比例缩放,因此认为几何间隔比较适合用来最大化“间隔”,则最大间隔分类器的目标函数可以为:

七、核函数

二、函数间隔(function margin)和几何间隔(geometrical margin)

现实世界中的数据集常常是伴随着大量的噪音,他们偏离正常的位置很远,我们成为outliers,这些outliers对超平面的划分会有很大的干扰,因为超平面本身就是由几个支持向量决定的,如图:

图片 56

图片 57

图片 58

版权声明:本文由奥门新萄京娱乐场发布于奥门新萄京娱乐场,转载请注明出处:支持向量机SVM算法推演,数据挖掘领域十大经典