一． 目标描述

支持向量机（Support Vector Machine，SVM）是一种有监督的机器学习算法。其原理简单，但是通用的公式推到及求解过程异常的复杂，这里将直接用优化算法来对支持向量机进行求解。
（该篇没有对偶问题转化推导，没有核函数，如需要了解自行搜索。）

二． 支持向量机简介

支持向量机是二分类算法，它的主要目标是找到两个数据集的支持向量及分割平面，使分割平面间的距离最大化。

　　如上图，红蓝点分别代表两个数据集，其中红色线和蓝色线表示由支持向量决定的两个平行的线（超平面），超平面之间的距离为2d。我们的目标就是找到最佳的斜率和支持向量，让d的值最大。

1. 硬间隔

硬间隔表示所有的数据点都需要在超平面的一侧。

　　如上图，确定L的斜率后，蓝色数据集可以确定4个超平面L1,L2,L3,L4。由于硬间隔的要求，蓝色数据集只能在超平面的一侧，故只有L4能被选作超平面。
　　选定超平面后就可以计算两个超平面之间的距离。
　　设蓝色数据集为(x1,y1), (x2,y2), (x3,y3), (x4,y4),红色数据集(m1,n1), (m2,n2), (m3,n3), (m4,n4)。
　　假设（x1,y1）和（m1,n1）为两个支持向量，则超平面由下式确定

　　点（a,b）到直线Ax+By+C=0的距离计算公式如下：

　　则可计算两个超平面间间隔2d如下

2. 软间隔

当数据集中有一定异常数据，数据无法被两个超平面分为两类时，将引入松弛参数，并重新计算数据集之间的最大距离。

　　如图，若蓝色有两个分类错误的数据点时，分别计算其到对应超平面的距离，整个数据集间的距离如下：

　　其中k为松弛参数，k为非负数，当k取值为0时，则表示可以允许所有数据点分类错误，当k取值为正无穷时，表示不允许任何数据点分类错误，此时，等同于硬间隔。

三． 支持向量机适应度函数

1. 适应度函数设计

从支持向量机的定义知，这是一个最大化问题。其中的变量为超平面，而超平面由支持向量决定。所以适应度函数的输入应该是超平面的各个维度的斜率，输出则是两个数据集之间的距离。其流程如下：

　　以上面的例子来说计算步骤如下
　　设蓝色数据集为(x1,y1), (x2,y2), (x3,y3), (x4,y4),红色数据集(m1,n1), (m2,n2), (m3,n3), (m4,n4)。
　　确定一组斜率（A,B）,可以计算出8个超平面，分别由C1,C2,C3,C4,C5,C6,C7,C8。

数据点	截距
(x1,y1)	C1
(x2,y2)	C2
(x3,y3)	C3
(x4,y4)	C4
(m1,n1)	C5
(m2,n2)	C6
(m3,n3)	C7
(m4,n4)	C8

然后计算各个超平面组合之间的距离,即在下表中选出最大的D作为适应度值返回。

	C5	C6	C7	C8
C1	D15	D16	D17	D18
C2	D25	D26	D27	D28
C3	D35	D36	D37	D38
C4	D45	D46	D47	D48

2. 适应度函数优化

从适应度函数可以看出，如果数据集1有i个数据，数据集2有j个数据，那么为了选出最佳的支持向量，我们需要计算i*j次数据集之间的距离，当数据集中的数据量很大时，这将是会耗费非常多的时间。
　　下面，将适应度函数优化一下，每次只计算单次数据集间距离。
　　可以看到，原适应度函数中，若数据集中数据的维度为2时，输入的维度也为2，输入中的每一维都可以认为是该维度斜率（如A,B相除得到斜率），然后会根据斜率和数据点计算出该超平面的截距（如C1，C2）,然后选出最佳的截距组合来确定超平面之间的距离。
　　这里优化一下，将适应度函数的输入确定为两个超平面，如此每次只需计算这两个超平面之间的距离即可。
　　具体如下：
　　若数据集中数据的维度为2，那么适应度函数输入的维度为2+2（如(A,B,C1,C2)）, 若数据集中数据的维度为N时，适应度函数输入的维度为N+2,其中最后两维代表这两个超平面的截距。
这样一来，适应度函数输入的就是两个确定的超平面，而不是超平面的截距，但是此时，该超平面不一定会穿过数据集中的数据点，或者可以说该超平面不存在支持向量。我愿称之为广义支持向量机。

　　如图，优化后的适应度函数计算出的超平面不一定经过数据点。

四． 代码实现

1 .原SVM模型

文件路径：\optimization algorithm\application_svm\SVM_Model.m

classdef SVM_Model < handle
    properties
        % 数据集m行*n列的矩阵，n = dim
        dataset1 = [];
        dataset2 = [];
        % 惩罚系数
        c = 5;
    end
    
    methods
        % 构造函数
        function self = SVM_Model(dataset1,dataset2)
            self.dataset1 = dataset1;
            self.dataset2 = dataset2;
        end
        
        % 输入为向量，输出为适应度值
        % 输入的x为角度
        function value = fit_function(self,x) 
            % 计算哪个数据集在上方
            is_up = self.get_is_up(x);
            
            % 计算结果及最佳支持向量截距
            [value,intercept1,intercept2] = self.get_value_and_intercept(x,is_up);
        end
        
        % 绘图,num为图片编号
        function draw(self,input,num)      
            bound_max = max(abs([self.dataset1(1,:),self.dataset1(2,:),self.dataset2(1,:),self.dataset2(2,:)]));
            set(gca,'XLim',[-bound_max bound_max]);
            set(gca,'YLim',[-bound_max bound_max]);
            % 绘制左下右上两点，保持图像区域不变
            scatter(-bound_max,-bound_max,1,'w');
            hold on;
            scatter(bound_max,bound_max,1,'w');
            hold on;
            axis square;
            
            for i = 1:length(self.dataset1)
                scatter(self.dataset1(i,1),self.dataset1(i,2),10,'b','filled');
                hold on;
            end
            for i = 1:length(self.dataset2)
                scatter(self.dataset2(i,1),self.dataset2(i,2),10,'r','filled');
                hold on;
            end
            
            % 有数据则绘制分割线
            if ~isempty(input)
                is_up = self.get_is_up(input);
                [value,intercept1,intercept2] = self.get_value_and_intercept(input,is_up);
                x =-bound_max:0.1:bound_max;
                k = -(input(1))/(input(2));
                x1=x;
                y1 = k*x1+intercept1/-(input(2));
                % 剔除直线上超出边界的点
                I = y1>bound_max;
                y1(I) = [];
                x1(I) = [];
                J = y1<-bound_max;
                y1(J) = [];
                x1(J) = [];
                plot(x1,y1,'b');
                hold on;
                
                y2 = k*x+intercept2/-(input(2));
                x2=x;
                % 剔除直线上超出边界的点
                I = y2>bound_max;
                y2(I) = [];
                x2(I) = [];
                J = y2<-bound_max;
                y2(J) = [];
                x2(J) = [];
                plot(x2,y2,'r');
                hold on;
            end
            text(bound_max*0.9+-bound_max*0.1,bound_max*0.9-bound_max*0.1,num2str(num),'FontSize',20);
        end
        
    end
    
    % 受保护的方法，继承用
    methods (Access = protected)
        
        % 计算该斜率下哪个数据集在上哪个数据集在下，
        % 若数据集1 在上则返回true
        function value = get_is_up(self,x)
            % 计算两个数据集的平均位置
            mean_data1 = sum(self.dataset1)/length(self.dataset1);
            mean_data2 = sum(self.dataset2)/length(self.dataset2);
            
            % 根据数据集的平均位置来计算该斜率下的截距，用来判断哪个数据集在上，哪个数据集在下
            mean_intercept1 = self.get_intercept(mean_data1,x);
            mean_intercept2 = self.get_intercept(mean_data2,x);
            value = mean_intercept1 < mean_intercept2;
        end
        
        % 计算当前斜率下的最佳截距和结果
        % 输入的gradient为斜率
        function [value,intercept1,intercept2] = get_value_and_intercept(self,x,is_up)
            value = -realmax('double');
            % 遍历数据集，找出最佳的支持向量组合
            % 数据集之间距离越大越优
            for i = 1:length(self.dataset1)
                for j = 1:length(self.dataset2)
                    tmp_intercept1 = self.get_intercept(self.dataset1(i,:),x);
                    tmp_intercept2 = self.get_intercept(self.dataset2(j,:),x);
                    svm_value = self.get_svm_value(x,tmp_intercept1,tmp_intercept2,is_up);
                    % 记录着两个支持向量对应的截距
                    if value < svm_value
                        intercept1 = tmp_intercept1;
                        intercept2 = tmp_intercept2;
                        value = svm_value;
                    end
                end
            end
        end
        
        % 根据数据和超平面斜率，计算超平面截距
        % a*x+b*y+c = 0 --> c = -(a*x+b*y)
        function value = get_intercept(self,data,x)
            value = -sum(data.*x);
        end
        
        % 计算一个整个数据集在该超平面上的距离
        function value = get_svm_value(self,x,intercept1,intercept2,is_up)
            % 直线的分母
            deno = sqrt(sum(x.^2));
            if is_up
                % 如果数据集1在数据集2的下方
                % 则计算数据集1中在支持向量上方的数据的距离
                value = -(intercept1-intercept2)/deno;
                for i = 1:length(self.dataset1)
                    temp_intercept1 = self.get_intercept(self.dataset1(i,:),x);
                    if  temp_intercept1 > intercept1
                        value = value - self.c*abs(temp_intercept1-intercept1)/deno;
                    end
                end
                % 如果数据集2在数据集1的上方
                % 则计算数据集2中在支持向量下方的数据的距离
                for i = 1:length(self.dataset2)
                    temp_intercept2 = self.get_intercept(self.dataset2(i,:),x);
                    if temp_intercept2 < intercept2
                        value = value - self.c*abs(temp_intercept2-intercept2)/deno;
                    end
                end
            else
                % 如果数据集1在数据集2的上方
                % 则计算数据集1中在支持向量下方的数据的距离
                value = (intercept1-intercept2)/deno;
                for i = 1:length(self.dataset1)
                    temp_intercept1 = self.get_intercept(self.dataset1(i,:),x);
                    if  temp_intercept1 < intercept1
                        value = value - self.c*abs(temp_intercept1-intercept1)/deno;
                    end
                end
                % 如果数据集2在数据集1的下方
                % 则计算数据集2中在支持向量上方的数据的距离
                for i = 1:length(self.dataset2)
                    temp_intercept2 = self.get_intercept(self.dataset2(i,:),x);
                    if temp_intercept2 > intercept2
                        value = value - self.c*abs(temp_intercept2-intercept2)/deno;
                    end
                end
            end

        end

    end
    
end

测试代码
文件路径：\optimization algorithm\application_svm\Test.m

%% 清理之前的数据
% 清除所有数据
clear all;
% 清除窗口输出
clc;

a = unifrnd(-pi,pi,20,1);
ra = unifrnd(0,5,20,1);
b = unifrnd(-pi,pi,20,1);
rb = unifrnd(0,5,20,1);

data1 = [sin(a(:)).*ra(:)+5,cos(a(:)).*ra(:)+5;];
data2 = [sin(b(:)).*rb(:)-5,cos(b(:)).*rb(:)-5;];

% 数据维度为2
data_dim = 2;
model = SVM_Model(data1,data2);

range_max = ones(1,data_dim);
range_min = ones(1,data_dim)*-1;

%% 添加目录
% 将上级目录中的frame文件夹加入路径
addpath('../frame')
% 引入差分进化算法
addpath('../algorithm_differential_evolution')
%% 算法实例
dim = data_dim;
% 种群数量
size = 10;
% 最大迭代次数
iter_max = 50;
% 取值范围上界
range_max_list = range_max;
% 取值范围下界
range_min_list = range_min;
% 实例化差分进化算法类
base = DE_Impl(dim,size,iter_max,range_min_list,range_max_list);
base.is_cal_max = true;
% 确定适应度函数
base.fitfunction = @model.fit_function;
% 运行
base.run();
disp(['复杂度',num2str(base.cal_fit_num)]);

disp(model.fit_function(base.position_best));

%% 下面绘制动态图
% 绘制每一代的路径
for i = 1:length(base.position_best_history)
    model.draw(base.position_best_history(i,:),i);
    % 每0.01绘制一次
    pause = 0.01;
    %下面是保存为GIF的程序
    frame=getframe(gcf);
    % 返回单帧颜色图像
    imind=frame2im(frame);
    % 颜色转换
    [imind,cm] = rgb2ind(imind,256);
    filename = ['svm.gif'];
    if i==1
         imwrite(imind,cm,filename,'gif', 'Loopcount',inf,'DelayTime',1e-4);
    else
         imwrite(imind,cm,filename,'gif','WriteMode','append','DelayTime',pause);
    end

    if i <length(base.position_best_history)
        % 如果不是最后一张图就清除窗口
        clf;
    end
end

运行结果：

从图中可以看出，每一代的超平面都会进过数据点。

2. 优化后SVM模型

文件路径：\optimization algorithm\application_svm\SVM_Model_Broad.m

% 广义的svm,超平面不一定会经过数据点
% 集成至svm
classdef SVM_Model_Broad < SVM_Model

    properties
    end
    
    methods
        % 构造函数
        function self = SVM_Model_Broad(dataset1,dataset2)
             % 调用父类构造函数
            self@SVM_Model(dataset1,dataset2);
        end
        
        % 输入为向量，输出为适应度值
        % 输入的x为角度，x维度 =数据维度+2，最后两维为截距
        function value = fit_function(self,x) 
            
            % 取出除后2维的其他维
            k = x(1:length(x)-2);
            
             % 计算哪个数据集在上方
            is_up = self.get_is_up(k);
            
            % 数据集1的截距
            intercept1 = x(length(x)-1);
            % 数据集2的截距
            intercept2 = x(length(x));
            
            % 计算结果
            value = self.get_svm_value(k,intercept1,intercept2,is_up);
        end
        
        % 绘图,num为图片编号,输入的input为角度
        function draw(self,input,num)      
            bound_max = max(abs([self.dataset1(1,:),self.dataset1(2,:),self.dataset2(1,:),self.dataset2(2,:)]));
            set(gca,'XLim',[-bound_max bound_max]);
            set(gca,'YLim',[-bound_max bound_max]);
            % 绘制左下右上两点，保持图像区域不变
            scatter(-bound_max,-bound_max,1,'w');
            hold on;
            scatter(bound_max,bound_max,1,'w');
            hold on;
            axis square;
            
            for i = 1:length(self.dataset1)
                scatter(self.dataset1(i,1),self.dataset1(i,2),10,'b','filled');
                hold on;
            end
            for i = 1:length(self.dataset2)
                scatter(self.dataset2(i,1),self.dataset2(i,2),10,'r','filled');
                hold on;
            end
            
            % 有数据则绘制分割线
            if ~isempty(input)
                % 获取两个数据集的截距
                intercept1 = input(length(input)-1);
                intercept2 = input(length(input));
                
                % 获取斜率
                k = -(input(1))/(input(2));
                x =-bound_max:0.1:bound_max;
                x1=x;
                y1 = k*x1+intercept1/-(input(2));
                % 剔除直线上超出边界的点
                I = y1>bound_max;
                y1(I) = [];
                x1(I) = [];
                J = y1<-bound_max;
                y1(J) = [];
                x1(J) = [];
                plot(x1,y1,'b');
                hold on;
                
                x2=x;
                y2 = k*x2+intercept2/-(input(2));
                % 剔除直线上超出边界的点
                I = y2>bound_max;
                y2(I) = [];
                x2(I) = [];
                J = y2<-bound_max;
                y2(J) = [];
                x2(J) = [];
                plot(x2,y2,'r');
                hold on;
            end
            text(bound_max*0.9+-bound_max*0.1,bound_max*0.9-bound_max*0.1,num2str(num),'FontSize',20);
        end
        
    end
    
end

测试代码
文件路径：\optimization algorithm\application_svm\Test_Broad.m

%% 清理之前的数据
% 清除所有数据
clear all;
% 清除窗口输出
clc;

a = unifrnd(-pi,pi,20,1);
ra = unifrnd(0,5,20,1);
b = unifrnd(-pi,pi,20,1);
rb = unifrnd(0,5,20,1);

data1 = [sin(a(:)).*ra(:)+5,cos(a(:)).*ra(:)+5;];
data2 = [sin(b(:)).*rb(:)-5,cos(b(:)).*rb(:)-5;];

data_dim = 2;
model = SVM_Model_Broad(data1,data2);
model.c = 10;
range_max = ones(1,data_dim+2);
range_min = -ones(1,data_dim+2);

%% 添加目录
% 将上级目录中的frame文件夹加入路径
addpath('../frame')
% 引入差分进化算法
addpath('../algorithm_differential_evolution')
%% 算法实例
dim = data_dim+2;
% 种群数量
size = 40;
% 最大迭代次数
iter_max = 200;
% 取值范围上界
range_max_list = range_max;
% 取值范围下界
range_min_list = range_min;
% 实例化差分进化算法类
base = DE_Impl(dim,size,iter_max,range_min_list,range_max_list);
base.is_cal_max = true;
% 确定适应度函数
base.fitfunction = @model.fit_function;
% 运行
base.run();
disp(['复杂度',num2str(base.cal_fit_num)]);

disp(model.fit_function(base.position_best));

%% 下面绘制动态图
% 绘制每一代的路径
for i = 1:length(base.position_best_history)
    model.draw(base.position_best_history(i,:),i);
    % 每0.01绘制一次
    pause = 0.01;
    %下面是保存为GIF的程序
    frame=getframe(gcf);
    % 返回单帧颜色图像
    imind=frame2im(frame);
    % 颜色转换
    [imind,cm] = rgb2ind(imind,256);
    filename = ['svm_broad.gif'];
    if i==1
         imwrite(imind,cm,filename,'gif', 'Loopcount',inf,'DelayTime',1e-4);
    else
         imwrite(imind,cm,filename,'gif','WriteMode','append','DelayTime',pause);
    end

    if i <length(base.position_best_history)
        % 如果不是最后一张图就清除窗口
        clf;
    end
end

　　出图中可以看出，超平面不一定会经过数据点。

五． 总结

这次介绍了如何使用优化算法来优化支持向量机。直接使用了支持向量机的定义作为适应度函数模型，避免了大量的对偶问题转换。同时为了减少计算量，使用了广义的支持向量机，让超平面不必一定经过支持向量，当数据集中数据较多时效果会非常明显。
　　文中使用的差分进化算法实现可以看优化算法matlab实现（七）差分进化算法matlab实现。如果想使用其他优化算法，则引入相关的优化算法路径后，实例化即可。

文件目录如下：

\optimization algorithm\application_svm\SVM_Model.m
\optimization algorithm\application_svm\Test.m
\optimization algorithm\application_svm\SVM_Model_Broad.m
\optimization algorithm\application_svm\Test_Broad.m
\optimization_algorithm\frame\Unit.py
\optimization_algorithm\frame\Algorithm_Impl.py
\optimization_algorithm\algorithm_differential_evolution\DE_Unit.py
\optimization_algorithm\algorithm_differential_evolution\DE_Base.py
\optimization_algorithm\algorithm_differential_evolution\DE_Impl.py