线性不可分支持向量机的实现
  在支持向量机这篇文章中，我们已经详细推导了线性不可分支持向量机的数学模型，并将原始问题转换成待求解的对偶问题，重温对偶问题如下：

线性不可分支持向量机对偶问题最终形式：

对比两种支持向量机的数学模型可以发现，两者的目标函数都是一致的，唯一有差别的就是约束条件部分，这个约束条件其实也只有支持向量才会有作用，对其他的样本点是没有太大影响的，所以我们也可以认为，线性不可分支持向量机最后的学习结果同样也只与某几个样本点有关，这里我们还没有进行实验，结果暂时也不知道。
  同样的我们使用MATLAB来求解对偶问题，而与线性可分实现类似，只需要改动一下自变量的上界问题即可，于是代码如下：

%% 线性不可分数据用支持向量机分类，其求解采用二次规划函数
% 清楚变量
clc;
clear;
% 导入数据集
data = [
    27    53    -1
    49    37    -1
    56    39    -1
    28    60    -1
    68    75     1
    57    69     1
    64    62     1
    77    68     1
    70    54     1
    56    63     1
    25    41    -1
    66    34     1
    55    79     1
    77    31    -1
    46    66     1
    30    23    -1
    21    45    -1
    68    42    -1
    43    43    -1
    56    59     1
    79    68     1
    60    34    -1
    49    32    -1
    80    79     1
    77    46     1
    26    66     1
    29    29    -1
    77    34     1
    20    71    -1
    49    25    -1
    58    65     1
    33    57    -1
    31    79     1
    20    78     1
    77    37    -1
    73    34    -1
    60    26    -1
    77    66     1
    71    75     1
    35    36    -1
    49    61     1
    26    37    -1
    42    73     1
    36    50    -1
    66    73     1
    71    43     1
    33    62     1
    43    41    -1
    42    29    -1
    58    20    -1
    ];
X = data(:,1:2);
y = data(:,3);
C = 5;
% 线性不可分数据与线性可分数据相比，在二次规划形式上只多出一个约束的C，所以在求解的过程中都是相同的.
% 构建二次系数矩阵H
H = [];
for i =1:length(X)
    for j = 1:length(X)
        H(i,j) = X(i,:)*(X(j,:))'*y(i)*y(j);
    end
end
% 构造一次项系数f
f = zeros(length(X),1)-1;
A = [];b = []; % 不等式约束
Aeq = y';beq = 0; % 等式约束
ub = ones(length(X),1).*C;lb = zeros(length(X),1); % 自变量范围
[x,fval] = quadprog(H,f,A,b,Aeq,beq,lb,ub);
% x表示自变量的解，以及在x处的函数值
% 将很小的x直接赋值为0
x(x < 1e-5) = 0;

% 利用求解得到x求解系数w
w = [0,0];
[a,~] = find(x~=0); % 找到可以求解b的值
temp = 0;
for i = 1:length(X)
    w = w + x(i)*y(i)*X(i,:);
    temp = temp + x(i)*y(i)*X(i,:)*X(a(1),:)';
end
% 计算偏置系数
b = y(a(1)) - temp;
disp(['涉及到的样本点有',num2str(length(a))])

% 数据结果可视化
k = - w(1)/w(2); % 构造截距式
b_ = -b/w(2); % 构造系数b
m = 0:2:90; % 生成一些点
n = k*m+b_;
plot(m,n,'--black')
n_2 = k*m+b_+1/w(2);
hold on
plot(m,n_2,'--blue')
n_3 = k*m+b_-1/w(2);
plot(m,n_3,'--red');
% 对数据进行分类，分为两类方便绘图
X_1 = [];
X_2 = [];
for i =1:length(y)
    if y(i)==-1
        X_1 = [X_1;X(i,:)];
    else
        X_2 = [X_2;X(i,:)];
    end
end
% HandleVisibility=off参数的意识是不显示图例
scatter(X_1(:,1),X_1(:,2),'red','HandleVisibility','off')
hold on
scatter(X_2(:,1),X_2(:,2),'blue','HandleVisibility','off')
xlim([10,90])
grid on
title('线性不可分支持向量机分类结果图')
% 绘制支持向量的位置,这是从\alpha中判断出哪些点是支持向量的。
scatter(X([14,4],1),X([14,4],2),'r','filled','HandleVisibility','off')
scatter(X(34,1),X(34,2),'b','filled','HandleVisibility','off')
% 样本点4，14，34是落在间隔边界上的点
% 计算松弛变量
functiona_margin  = zeros(length(X),1);
loos = zeros(length(X),1);
for i=1:length(X)
    functiona_margin(i) = y(i)*(w*X(i,:)'+b);
    if functiona_margin(i)>1 % 如果函数间隔满足要求
        loos(i) = 0; % 那么这个点就不是支持向量点
    else
        loos(i) = 1 - functiona_margin(i); % 该点是支持向量，计算松弛变量的值
    end
end
% 绘制误分类点
scatter(X([12,26,28,47],1),X([12,26,28,47],2),'*','black')

% 18 29 35 36 46落在间隔边界与分离超平面之间
% 12，26，28，47属于误分类点
legend('分界线','类别1','类别2','误分类点')

运行的结果如下：



从上图中可以看出，线性不可分问题相对于线性可分问题来比，支持向量的定义复杂很多，因为此时的样本点存在很多种情况，有：样本点在间隔边界外切分类正确、样本点在间隔边界外切分类错误、样本点在超平面和间隔边界之间且分类错误、样本点在超平面和函数边界之间且分类正确、样本点在函数边界上且分类正确、样本点在超平面上、样本点在函数边界上且分类错误⋯这么多种情况，其中只有三种情况属于支持向量，它们分别是：在函数边界上、在函数边界到超平面之间、在超平面另一侧（分类错误时）。还记得在线性可分SVM问题上，支持向量指的是落在函数边界上的样本点，即αi>0的点，在线性不可分的例子中，αi>0 的点有很多很多，我们需要对这些点进行讨论。
  下面的讨论都是基于上面代码中的数据来做的，样本点一共有50个，其中一半是正类，一半是负类，此外我们设置松弛变量的惩罚力度C=5，对所有α>0的样本点进行讨论，计算这些点的松弛变量大小我们发现：





而在前面说过，惩罚参数C的作用是调节误分类情况和间隔最大之间的关系，当C的值越大，则说明超平面对误分类点的惩罚力度就越大，算法更要考虑减少误分类点的情况。当C的值越小时，则对误分类点的重要性降低。具体可以参考下图：
当设置C的值为0.0001时，超平面如下：



此时的超平面会造成5个样本点误分类。相比与C CC=5时的超平面，此时的误分类个数要增加2个。