网站建设佰金手指科杰十八,河南省建设科技网站,南京建设教育网站,视频网站开发 视频采集1 线性可分的数据集
1.1 超平面
SVM的思想是找到最大间隔的分隔超平面。 在两个分类中#xff0c;找到能够一条线#xff0c;以最好地区分这两个分类。这样如果有了新的点#xff0c;这条线也能很好地做出分类。 这样的线在高维样本中的时候就叫做超平面。
1.2 几何间隔与…1 线性可分的数据集
1.1 超平面
SVM的思想是找到最大间隔的分隔超平面。 在两个分类中找到能够一条线以最好地区分这两个分类。这样如果有了新的点这条线也能很好地做出分类。 这样的线在高维样本中的时候就叫做超平面。
1.2 几何间隔与函数间隔
图中绿线h1效果不好h2效果还行h3效果最好。怎么区分效果好不好 如果超平面w.xb0w.xb0w.xb0已经存在那么样本点距离超平面的距离能够表示预测的确信程度。∣w.xb∣|w.xb|∣w.xb∣能够相对地表示点x距离超平面的距离。而w.xbw.xbw.xb的符号与标记y的符号是否一致表示分类是否正确。那么就可以用y(w.xb)y(w.xb)y(w.xb)表示分类的正确性和确信程度这就是函数间隔。
函数间隔超平面(w,b)关于样本点(xix_ixi,yiy_iyi)样本点的函数间隔为ri^yi(w.xib)\hat{r_i}y_i(w.x_ib)ri^yi(w.xib) 超平面(w,b)关于数据集T的函数间隔为所有样本点的函数间隔的最小值r^mini1,2...Nri^\hat{r}min_{i1,2...N} \hat{r_i}r^mini1,2...Nri^
函数间隔的问题是如果成比例的改变w和b例如改为2w2b超平面不变函数间隔却变成了原来的两倍。如果规范化之后就会使得间隔是确定的。这时候函数间隔就变成了几何间隔。 几何间隔对于给定数据集T和超平面(w,b)w是超平面的法向量样本点(xix_ixi,yiy_iyi)的几何间隔为riyiw.xb∣∣w∣∣r_iy_i\dfrac{w.xb}{||w||}riyi∣∣w∣∣w.xb
超平面(w,b)关于数据集T的几何间隔为所有样本点的几何间隔的最小值rmini1,2...Nrirmin_{i1,2...N} {r_i}rmini1,2...Nri
1.3 目标函数
目标函数最大化几何间隔rmaxrmaxr^∣∣w∣∣max rmax\dfrac{\hat{r}}{||w||}maxrmax∣∣w∣∣r^ s.t. yi(w.xib)r^,i1,2,3...Ny_i(w.x_ib)\hat{r},i1,2,3...Nyi(w.xib)r^,i1,2,3...N 令r^1\hat{r}1r^1这里等于1没有特别的含义只是好计算不影响结果那么目标函数变为:max1∣∣w∣∣max\dfrac{1}{||w||}max∣∣w∣∣1min∣∣w∣∣min||w||min∣∣w∣∣min12∣∣w∣∣2min\dfrac{1}{2}||w||^2min21∣∣w∣∣2 s.t. yi(w.xib)r^,i1,2,3...Ny_i(w.x_ib)\hat{r},i1,2,3...Nyi(w.xib)r^,i1,2,3...N
用拉格朗日乘子法 L(w,b,α)12∣∣w∣∣2−∑i1Nαiyi(w.xib)∑i1NαiL(w,b,\alpha)\dfrac{1}{2}||w||^2-\sum_{i1}^N\alpha_iy_i(w.x_ib) \sum_{i1}^N\alpha_iL(w,b,α)21∣∣w∣∣2−∑i1Nαiyi(w.xib)∑i1Nαi
分别对w、b、求导得到w∑i1Nαiyixiw\sum_{i1}^N\alpha_iy_ix_iw∑i1Nαiyixi∑i1Nαiyi0\sum_{i1}^N\alpha_iy_i0∑i1Nαiyi0
这样代入上面的式子得到L(w,b,α)12∑i1N∑j1Nαiαjyiyj(xi.xj)∑i1NαiL(w,b,\alpha)\dfrac{1}{2}\sum_{i1}^N\sum_{j1}^N\alpha_i\alpha_jy_iy_j(x_i.x_j)\sum_{i1}^N\alpha_iL(w,b,α)21∑i1N∑j1Nαiαjyiyj(xi.xj)∑i1Nαi
1.4 支持向量
在线性可分情况下训练数据集中的样本点中距离分离超平面最近的样本点称为支持向量。
2 线性近似可分
训练样本中有一些点不满足函数间隔1的约束。 解决方法是对每一个样本引入一个松弛变量ϵi0\epsilon_i0ϵi0使得函数间隔大于等于1。约束条件变为:yi(w.xib)1−ϵiy_i(w.x_ib)1-\epsilon_iyi(w.xib)1−ϵi 目标函数min 12∣∣w∣∣2C∑i1Nϵi\dfrac{1}{2}||w||^2C\sum_{i1}^{N}\epsilon_i21∣∣w∣∣2C∑i1Nϵi s.t. yi(w.xib)1−ϵi,i1,2,3...Ny_i(w.x_ib)1-\epsilon_i, i1,2,3...Nyi(w.xib)1−ϵi,i1,2,3...N ϵi0,i1,2,3...N\epsilon_i0, i1,2,3...Nϵi0,i1,2,3...N
拉格朗日函数变为L(w,b,α,μ)12∣∣w∣∣2C∑i1Nϵi−∑i1Nαi(yi(w.xib)−1ϵi)∑i1NμiϵiL(w,b,\alpha,\mu)\dfrac{1}{2}||w||^2 C\sum_{i1}^{N}\epsilon_i -\sum_{i1}^N\alpha_i(y_i(w.x_ib) -1 \epsilon_i ) \sum_{i1}^N\mu_i\epsilon_iL(w,b,α,μ)21∣∣w∣∣2C∑i1Nϵi−∑i1Nαi(yi(w.xib)−1ϵi)∑i1Nμiϵi
经过求导替换得到minL(w,b,α,μ,ϵ)−12∑i1N∑j1Nαiαjyiyj(xi.xj)∑i1Nαimin L(w,b,\alpha,\mu,\epsilon)-\dfrac{1}{2}\sum_{i1}^N\sum_{j1}^N\alpha_i\alpha_jy_iy_j(x_i.x_j)\sum_{i1}^N\alpha_iminL(w,b,α,μ,ϵ)−21∑i1N∑j1Nαiαjyiyj(xi.xj)∑i1Nαi
3 非线性支持向量机与核函数
对于线性不可分的问题通过一个变换将低纬度的非线性问题变换为高纬度的线性问题。通过变换后的线性问题求解原来的非线性问题。 核函数定义设X是输入空间H为特征空间如果存在一个从X到H的映射ϕ(X):X−H\phi(X):X-Hϕ(X):X−H使得对所有的x,z∈Xx,z \in Xx,z∈X函数K(x,z)满足条件K(x,z)ϕ(x)ϕ(z)K(x,z)\phi(x)\phi(z)K(x,z)ϕ(x)ϕ(z)则称K(x,z)为核函数ϕ(x)\phi(x)ϕ(x)为映射函数。 核函数技巧的核心是只需要定义核函数而不是定义映射函数。因为通常直接计算K(x,z)更容易而计算ϕ(x)ϕ(z)\phi(x)\phi(z)ϕ(x)ϕ(z)不容易计算量还很大。
所以目标函数变为L(w,b,α,μ,ϵ)12∑i1N∑j1NαiαjyiyjK(xi.xj)−∑i1NαiL(w,b,\alpha,\mu,\epsilon)\dfrac{1}{2}\sum_{i1}^N\sum_{j1}^N\alpha_i\alpha_jy_iy_jK(x_i.x_j)-\sum_{i1}^N\alpha_iL(w,b,α,μ,ϵ)21∑i1N∑j1NαiαjyiyjK(xi.xj)−∑i1Nαi
常用核函数为高斯核函数、多项式核函数。
三个类型讨论到后面使用SMO解决问题。
