簡單易學(xué)的機(jī)器學(xué)習(xí)算法—線性可分支持向量機(jī)

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

稱為線性可分支持向量機(jī)。
二、線性可分支持向量機(jī)的原理
1、原始問題
   支持向量機(jī)學(xué)習(xí)的基本想法是求解能夠正確劃分訓(xùn)練數(shù)據(jù)集并且?guī)缀伍g隔最大的分離超平面，這里的間隔最大化又稱為硬間隔最大化。
   我們可以把這樣的問題抽象稱為如下的數(shù)學(xué)表達(dá)式：

然而，函數(shù)間隔的取值并不影響最優(yōu)化問題的解，我們可以取。則上述的優(yōu)化問題就可以轉(zhuǎn)化為：

可以將上述的最大化問題轉(zhuǎn)化為最小化問題：

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

這樣，原始的問題就轉(zhuǎn)化成一個極小極大問題：

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

此時，我們先求：
    將拉格朗日函數(shù)分別對和求偏導(dǎo)，并令其為0，則為

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

再求對a的極大，即：

將這樣的最大化問題轉(zhuǎn)化為最小化問題，即為

根據(jù)拉格朗日對偶性，通過對偶函數(shù)的最優(yōu)解即可以求出原始函數(shù)的最優(yōu)解:

其中，下標(biāo)是使得的樣本。這里使得的樣本也稱為支撐向量，與上述的滿足的樣本本質(zhì)上是一樣的。
三、線性可分支持向量機(jī)的步驟
1、構(gòu)造帶約束的優(yōu)化問題：

2、計算原始問題的最優(yōu)解：

3、求分離超平面：

分類決策平面：

四、實驗的仿真
    我們通過二次規(guī)劃來求解上述的帶約束的優(yōu)化問題，對于一個實例：(選自：《統(tǒng)計學(xué)習(xí)方法》)正例點為，負(fù)例點為，圖像為：數(shù)據(jù)分析師培訓(xùn)

(正例點和負(fù)例點)
MATLAB代碼
[plain] view plain copy 在CODE上查看代碼片派生到我的代碼片
%% 基于凸二次規(guī)劃的線性可分支持向量機(jī)  
 
% 清空內(nèi)存  
clear all;  
clc;  
 
%簡單的測試數(shù)據(jù)集  
X = [3,3;4,3;1,1];  
x_1 = X(:,1);  
x_2 = X(:,2);  
Y = [1,1,-1];%標(biāo)簽  
 
 
m = size(X);  
for i = 1:m(1,1)  
    X(i,:) = X(i,:)*Y(1,i);  
end  
 
%% 對偶問題，用二次規(guī)劃來求解  
H = X*X';  
 
f = [-1;-1;-1];  
A = Y;  
b = 0;  
lb = zeros(3,1);  
% 調(diào)用二次規(guī)劃的函數(shù)  
[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 
分類的結(jié)果：

(最終的分類超平面)