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

一、線性支持向量機的概念

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

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

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

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

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

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

    第二步，求，即求：

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

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

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

3、求分離超平面和分類決策函數(shù)：
分離超平面為：
分類決策函數(shù)為：
五、實驗的仿真
1、解決線性可分問題
    與博文“簡單易學的機器學習算法——線性可分支持向量機”實驗一樣，其中取中的最大值。
MATLAB代碼為
[plain] view plain copy 在CODE上查看代碼片派生到我的代碼片
%% 線性支持向量機  
 
% 清空內存  
clear all;  
clc;  
 
%簡單的測試數(shù)據(jù)集  
X = [3,3;4,3;1,1];  
y = [1,1,-1];%標簽  
A = [X,y'];  
 
m = size(A);%得到訓練數(shù)據(jù)的大小  
 
 
% 區(qū)分開特征與標簽  
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);  
% 調用二次規(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  

實驗結果為：

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

(線性不可分問題)

MATLAB代碼：
[plain] view plain copy 在CODE上查看代碼片派生到我的代碼片
%% 線性支持向量機  
 
% 清空內存  
clear all;  
clc;  
 
% 導入測試數(shù)據(jù)  
A = load('testSet.txt');  
 
% 處理數(shù)據(jù)的標簽  
m = size(A);%得到訓練數(shù)據(jù)的大小  
for i = 1:m(1,1)  
    A(i,m(1,2)) = A(i,m(1,2))*2-1;  
end  
 
 
 
% 區(qū)分開特征與標簽  
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);  
% 調用二次規(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  

實驗結果為：

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