专栏首页null的专栏简单易学的机器学习算法——线性可分支持向量机

简单易学的机器学习算法——线性可分支持向量机

一、线性可分支持向量机的概念

    线性可分支持向量机是用于求解线性可分问题的分类问题。对于给定的线性可分训练数据集,通过间隔最大化构造相应的凸二次优化问题可以得到分离超平面:

以及相应的分类决策函数

称为线性可分支持向量机。

二、线性可分支持向量机的原理

1、原始问题

   支持向量机学习的基本想法是求解能够正确划分训练数据集并且几何间隔最大的分离超平面,这里的间隔最大化又称为硬间隔最大化。

   我们可以把这样的问题抽象称为如下的数学表达式:

然而,函数间隔

的取值并不影响最优化问题的解,我们可以取

。则上述的优化问题就可以转化为:

可以将上述的最大化问题转化为最小化问题:

这样的问题是一个凸二次规划的问题。在线性可分情况下,训练数据集的样本点中的分离超平面距离最近的样本点的事例称为支持向量,即满足:

2、对偶算法

   对于上述的带约束的优化问题,我们可以引进拉格朗日函数来解决:

这样,原始的问题就转化成一个极小极大问题:

再通过拉格朗日函数的对偶性,将上述的极小极大问题转换成一个极大极小问题:

此时,我们先求

    将拉格朗日函数

分别对

求偏导,并令其为0,则为

可得:

将上面两个等式带入拉格朗日函数

,得

再求

的极大,即:

将这样的最大化问题转化为最小化问题,即为

根据拉格朗日对偶性,通过对偶函数的最优解即可以求出原始函数的最优解:

其中,下标

是使得

的样本。这里使得

的样本也称为支撑向量,与上述的满足

的样本本质上是一样的。

三、线性可分支持向量机的步骤

1、构造带约束的优化问题:

2、计算原始问题的最优解:

3、求分离超平面:

分类决策平面:

四、实验的仿真

    我们通过二次规划来求解上述的带约束的优化问题,对于一个实例:(选自:《统计学习方法》)正例点为

,负例点为

,图像为:

(正例点和负例点)

MATLAB代码

%% 基于凸二次规划的线性可分支持向量机

% 清空内存
clear all;
clc;

%简单的测试数据集
X = [3,3;4,3;1,1];
x_1 = X(:,1);
x_2 = X(:,2);
Y = [1,1,-1];%标签


m = size(X);
for i = 1:m(1,1)
    X(i,:) = X(i,:)*Y(1,i);
end

%% 对偶问题,用二次规划来求解
H = X*X';

f = [-1;-1;-1];
A = Y;
b = 0;
lb = zeros(3,1);
% 调用二次规划的函数
[x,fval,exitflag,output,lambda] = quadprog(H,f,[],[],A,b,lb);

% 求原问题的解
n = size(x);
w = x' * X;

for i = 1:n(1,1)
    if x(i,1) > 0
        b = Y(1,i)-w*X(i,:)'*Y(1,i);
        break;
    end
end

% 求出分离超平面

y_1 = [0,4];
for i = 1:2
    y_2(1,i) = (-b-w(1,1)*y_1(1,i))./w(1,2);
end

hold on
plot(y_1,y_2);
for i = 1:3
    if Y(1,i) == 1
        plot(x_1(i,:),x_2(i,:),'+r');
    elseif Y(1,i) == -1
        plot(x_1(i,:),x_2(i,:),'og');
    end
end
axis([0,7,0,7])
hold off

分类的结果:

(最终的分类超平面)

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 简单易学的机器学习算法——线性可分支持向量机

    一、线性可分支持向量机的概念     线性可分支持向量机是用于求解线性可分问题的分类问题。对于给定的线性可分训练数据集,通过间隔最大化构造相应的凸二次优化问题可...

    zhaozhiyong
  • 简单易学的机器学习算法——支持向量机(开篇:基本概念)

        支持向量机(Support Vector Machines, SVM)被公认为比较优秀的分类模型,有很多人对SVM的基本原理做了阐述,我在学习的过程中也...

    zhaozhiyong
  • 简单易学的机器学习算法——线性支持向量机

        线性支持向量机是针对线性不可分的数据集的,这样的数据集可以通过近似可分的方法实现分类。对于这样的数据集,类似线性可分支持向量机,通过求解对应的凸二次规划...

    zhaozhiyong
  • 简单易学的机器学习算法——线性可分支持向量机

    一、线性可分支持向量机的概念     线性可分支持向量机是用于求解线性可分问题的分类问题。对于给定的线性可分训练数据集,通过间隔最大化构造相应的凸二次优化问题可...

    zhaozhiyong
  • Python数据分析《爱情公寓5》中的蜕变和成长

    在青春情怀和强大的“十年IP”的加持下,该剧在开播后不久,热度便迅速上升。在上线两天实时热度值就超过了《精英律师》《庆余年》等热播剧,在所有影视剧中排名首位。并...

    用户6888863
  • 【毕设进行时-工业大数据,数据挖掘】第一天收获

    【个人看法】 支持向量机的核心与决策树类似。但是还是有不同之处,现在多学习下支持向量机,后面用自己的算法也行。或者给出多个版本的话,可以作为几个方案去解释!

    用户1687088
  • Cloudflare网站访问需要验证码的解决办法

    网友@Bill问道:用了Cloudflare的CDN,打开网站经常遇到要输入验证码才能正常浏览的情况,这个怎么解决呢。Cloudflare是国外著名的免费CDN...

    魏艾斯博客www.vpsss.net
  • geotools获取给定点的DEM高程值

    1、在web端绘制一条曲线; 2、获取各节点处的高程值; 3、根据高程值绘制高程堆积图。

    lzugis
  • ProxySQL Cluster +PXC 高可用集群的搭建

    https://blog.51cto.com/lee90/2299815 # 开启web监控页面

    二狗不要跑
  • System方法总结

    最近在研究Android源码,突然看到有很多和System有关,什么System.arraycopy、System.nanoTime(),所以专门花时间看了一下...

    haifeiWu

扫码关注云+社区

领取腾讯云代金券