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

一、線性支持向量機(jī)的概念

    線性支持向量機(jī)是針對線性不可分的數(shù)據(jù)集的，這樣的數(shù)據(jù)集可以通過近似可分的方法實現(xiàn)分類。對于這樣的數(shù)據(jù)集，類似線性可分支持向量機(jī)，通過求解對應(yīng)的凸二次規(guī)劃問題，也同樣求得分離超平面
以及相應(yīng)的分類決策函數(shù)
二、與線性可分支持向量機(jī)的比較
    線性支持向量機(jī)與線性可分支持向量機(jī)最大的不同就是在處理的問題上，線性可分支持向量機(jī)處理的是嚴(yán)格線性可分的數(shù)據(jù)集，而線性支持向量機(jī)處理的是線性不可分的數(shù)據(jù)集，然而，在基本的原理上他們卻有著想通之處。這里的線性不可分是指數(shù)據(jù)集中存在某些點不能滿足線性可分支持向量機(jī)的約束條件：。
    具體來講，對于特征空間上的訓(xùn)練數(shù)據(jù)集，且不是線性可分的，即存在某些特異點不滿足的約束條件，若將這些特異點去除，那么剩下的數(shù)據(jù)點是線性可分的，由此可見，線性可分支持向量機(jī)是線性支持向量機(jī)的特殊情況。為了解決這樣的問題，對每個樣本點引入一個松弛變量，且，則上述的約束條件被放寬，即：

此時目標(biāo)函數(shù)變?yōu)椋?img src="/uploadfile/image/20170321/20170321181611_87789.png" alt="" />
其中稱為懲罰參數(shù)，且。在線性支持向量機(jī)中加入了懲罰項，與線性可分支持向量的應(yīng)間隔最大化相對應(yīng)，在線性支持向量機(jī)中稱為軟間隔最大化。數(shù)據(jù)分析師培訓(xùn)
三、線性支持向量機(jī)的原理
    由上所述，我們得到線性支持向量機(jī)的原始問題：

接下來的問題就變成如何求解這樣一個最優(yōu)化問題(稱為原始問題)。引入拉格朗日函數(shù)：

其中，。
    此時，原始問題即變成
利用拉格朗日函數(shù)的對偶性，將問題變成一個極大極小優(yōu)化問題：

    首先求解，將拉格朗日函數(shù)分別對求偏導(dǎo)，并令其為0：

即為：
將其帶入拉格朗日函數(shù)，即得：

    第二步，求，即求：

由可得，因為在第二步求極大值的過程中，函數(shù)只與a有關(guān)。
    將上述的極大值為題轉(zhuǎn)化為極小值問題：

這就是原始問題的對偶問題。
四、線性支持向量機(jī)的過程
1、設(shè)置懲罰參數(shù)，并求解對偶問題：

假設(shè)求得的最優(yōu)解為；
2、計算原始問題的最優(yōu)解：
選擇中滿足的分量，計算：

3、求分離超平面和分類決策函數(shù)：
分離超平面為：
分類決策函數(shù)為：
五、實驗的仿真
1、解決線性可分問題
    與博文“簡單易學(xué)的機(jī)器學(xué)習(xí)算法——線性可分支持向量機(jī)”實驗一樣，其中取中的最大值。
MATLAB代碼為
[plain] view plain copy 在CODE上查看代碼片派生到我的代碼片
%% 線性支持向量機(jī)  
 
% 清空內(nèi)存  
clear all;  
clc;  
 
%簡單的測試數(shù)據(jù)集  
X = [3,3;4,3;1,1];  
y = [1,1,-1];%標(biāo)簽  
A = [X,y'];  
 
m = size(A);%得到訓(xùn)練數(shù)據(jù)的大小  
 
 
% 區(qū)分開特征與標(biāo)簽  
X = A(:,1:2);  
Y = A(:,m(1,2))';  
 
for i = 1:m(1,1)  
    X(i,:) = X(i,:)*Y(1,i);  
end  
 
 
 
%% 對偶問題，用二次規(guī)劃來求解  
H = X*X';  
 
f = ones(m(1,1),1)*(-1);  
B = Y;  
b = 0;  
lb = zeros(m(1,1),1);  
% 調(diào)用二次規(guī)劃的函數(shù)  
[x,fval,exitflag,output,lambda] = quadprog(H,f,[],[],B,b,lb);  
 
% 定義C  
C = max(x);  
 
% 求原問題的解  
n = size(x);  
w = x' * X;  
 
k = 1;  
for i = 1:n(1,1)  
    if x(i,1) > 0 && x(i,1)<C  
        b(k,1) = Y(1,i)-w*X(i,:)'*Y(1,i);  
        k = k +1;  
    end  
end  
b = mean(b);  
 
% 求出分離超平面  
 
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:m(1,1)  
    if A(i,m(1,2)) == -1  
        plot(A(i,1),A(i,2),'og');  
    elseif A(i,m(1,2)) == 1  
        plot(A(i,1),A(i,2),'+r')  
    end  
end  
axis([0,7,0,7])    
hold off  

實驗結(jié)果為：

(線性可分問題的分離超平面)
2、解決線性不可分問題
問題為：

(線性不可分問題)

MATLAB代碼：
[plain] view plain copy 在CODE上查看代碼片派生到我的代碼片
%% 線性支持向量機(jī)  
 
% 清空內(nèi)存  
clear all;  
clc;  
 
% 導(dǎo)入測試數(shù)據(jù)  
A = load('testSet.txt');  
 
% 處理數(shù)據(jù)的標(biāo)簽  
m = size(A);%得到訓(xùn)練數(shù)據(jù)的大小  
for i = 1:m(1,1)  
    A(i,m(1,2)) = A(i,m(1,2))*2-1;  
end  
 
 
 
% 區(qū)分開特征與標(biāo)簽  
X = A(:,1:2);  
Y = A(:,m(1,2))';  
 
for i = 1:m(1,1)  
    X(i,:) = X(i,:)*Y(1,i);  
end  
 
 
 
%% 對偶問題，用二次規(guī)劃來求解  
H = X*X';  
 
f = ones(m(1,1),1)*(-1);  
B = Y;  
b = 0;  
lb = zeros(m(1,1),1);  
% 調(diào)用二次規(guī)劃的函數(shù)  
[x,fval,exitflag,output,lambda] = quadprog(H,f,[],[],B,b,lb);  
 
% 定義C  
% C = mean(x);  
C = max(x);  
 
% 求原問題的解  
n = size(x);  
w = x' * X;  
 
k = 1;  
for i = 1:n(1,1)  
    if x(i,1) > 0 && x(i,1)<C  
        b(k,1) = Y(1,i)-w*X(i,:)'*Y(1,i);  
        k = k +1;  
    end  
end  
b = mean(b);  
 
% 求出分離超平面  
 
y_1 = [-4,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:m(1,1)  
    if A(i,m(1,2)) == -1  
        plot(A(i,1),A(i,2),'og');  
    elseif A(i,m(1,2)) == 1  
        plot(A(i,1),A(i,2),'+r')  
    end  
end  
hold off  

實驗結(jié)果為：

(線性不可分問題的分離超平面)
注：這里的的取值很重要，的取值將決定分類結(jié)果的準(zhǔn)確性。