簡單易學的機器學習算法—線性可分支持向量機

一、線性可分支持向量機的概念
    線性可分支持向量機是用于求解線性可分問題的分類問題。對于給定的線性可分訓練數據集，通過間隔最大化構造相應的凸二次優化問題可以得到分離超平面：
以及相應的分類決策函數

稱為線性可分支持向量機。
二、線性可分支持向量機的原理
1、原始問題
   支持向量機學習的基本想法是求解能夠正確劃分訓練數據集并且幾何間隔最大的分離超平面，這里的間隔最大化又稱為硬間隔最大化。
   我們可以把這樣的問題抽象稱為如下的數學表達式：

然而，函數間隔的取值并不影響最優化問題的解，我們可以取。則上述的優化問題就可以轉化為：

可以將上述的最大化問題轉化為最小化問題：

這樣的問題是一個凸二次規劃的問題。在線性可分情況下，訓練數據集的樣本點中的分離超平面距離最近的樣本點的事例稱為支持向量，即滿足：
2、對偶算法
   對于上述的帶約束的優化問題，我們可以引進拉格朗日函數來解決：

這樣，原始的問題就轉化成一個極小極大問題：

再通過拉格朗日函數的對偶性，將上述的極小極大問題轉換成一個極大極小問題：

此時，我們先求：
    將拉格朗日函數分別對和求偏導，并令其為0，則為

可得：
將上面兩個等式帶入拉格朗日函數，得

再求對a的極大，即：

將這樣的最大化問題轉化為最小化問題，即為

根據拉格朗日對偶性，通過對偶函數的最優解即可以求出原始函數的最優解:

其中，下標是使得的樣本。這里使得的樣本也稱為支撐向量，與上述的滿足的樣本本質上是一樣的。
三、線性可分支持向量機的步驟
1、構造帶約束的優化問題：

2、計算原始問題的最優解：

3、求分離超平面：

分類決策平面：

四、實驗的仿真
    我們通過二次規劃來求解上述的帶約束的優化問題，對于一個實例：(選自：《統計學習方法》)正例點為，負例點為，圖像為：數據分析師培訓

(正例點和負例點)
MATLAB代碼
[plain] view plain copy 在CODE上查看代碼片派生到我的代碼片
%% 基于凸二次規劃的線性可分支持向量機  
 
% 清空內存  
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 
分類的結果：

(最終的分類超平面)