svmclassnpa.m

支持向量机SVM和核函数的MATLAB程序集

    r = mu*(evmax - psi - deluv + eumin);
    s1 = (evmax - eumax - deluv + deluu);
    s2 = mu*(delvv - deluv - evmin + eumin);
    d1 = psi1 + deluu - 2.0*eumax;
    d2 = mu*mu*(delvv + psi2 - 2.0*evmin);
    dold = delzz;
    [d,la1,la2,flag,vert1,vert2]=twolines(r,s1,s2,d1,d2,dold);
    if flag==0 | d>=delzz | d < 0
        
        
        success=0;
        return;
    end;
    success=1;
    delzz=d;
    deluu = (1.0 - la1)*(1.0 -la1)*deluu + la1*la1*psi1 + 2.0*(1.0- la1)*la1*eumax;
    delvv = (1.0 + la2*mu)*(1.0 + la2*mu)*delvv +la2*la2*mu*mu*psi2 -  2.0*(1.0 + la2*mu)*la2*mu*evmin;
    deluv = (1.0- la1)*(1.0 + la2*mu)*deluv - (1.0 - la1)*la2*mu*eumin +  (1.0 + la2*mu)*la1*evmax - la1*la2*mu*psi;
    ind_SV=find(alind==1);
    eu(ind_SV)=(1-la1)*eu(ind_SV)+la1*(svmkernel(x(imax,:),kernel,kerneloption,x(ind_SV,:))+(ind_SV==imax)./C);
    ev(ind_SV)=(1+la2*mu)*ev(ind_SV)-la2*mu*(svmkernel(x(jmin,:),kernel,kerneloption,x(ind_SV,:))++(ind_SV==jmin)./C);
    ind_I=intersect(find(y==1),find(alind==1));
    beta(ind_I)=(1-la1)*beta(ind_I);
    ind_J=intersect(find(y==-1),find(alind==1));
    beta(ind_J)=(1+la2*mu)*beta(ind_J);
    beta(imax)=beta(imax)+la1;
    if (vert2==2);
        alind(jmin)=0;
        beta(jmin)=0;
    else
        beta(jmin)=beta(jmin)-la2*mu;
    end;
end;
if y(kmax)==-1 & y(kmin)==1
    cas=4; 
    jmax = kmax;
    imin = kmin;
    r = mu*(eumax - psi - deluv + evmin);       %OK
    s1 = (eumax - evmax - deluv + delvv);       %OK
    s2 = mu*(deluu - deluv - eumin + evmin);    %OK
    d1 = psi1 + delvv - 2.0*evmax;              %OK
    d2 = mu*mu*(deluu + psi2 - 2.0*eumin);      %OK
    dold = delzz;
    
    [d,la1,la2,flag,vert1,vert2]=twolines(r,s1,s2,d1,d2,dold);
    if flag==0 | d>=delzz | d < 0
        
        success=0;
        return;
    end;
    success=1;
    delzz=d;
    delvv = (1.0 - la1)*(1.0 -la1)*delvv + la1*la1*psi1 + 2*(1- la1)*la1*evmax;
    deluu = (1.0 + la2*mu)*(1 + la2*mu)*deluu +  la2*la2*mu*mu*psi2 -  2.*(1 + la2*mu)*la2*mu*eumin;
    deluv = (1- la1)*(1+ la2*mu)*deluv -(1 - la1)*la2*mu*evmin + (1 + la2*mu)*la1*eumax - la1*la2*mu*psi;
    ind_SV=find(alind==1);
    ev(ind_SV)=(1-la1)*ev(ind_SV)+la1*(svmkernel(x(jmax,:),kernel,kerneloption,x(ind_SV,:))+(ind_SV==jmax)./C);
    eu(ind_SV)=(1+la2*mu)*eu(ind_SV)-la2*mu*(svmkernel(x(imin,:),kernel,kerneloption,x(ind_SV,:))+(ind_SV==imin)./C);
    ind_J=intersect(find(y==-1),find(alind==1));
    beta(ind_J)=(1-la1)*beta(ind_J);
    ind_I=intersect(find(y==1),find(alind==1));
    beta(ind_I)=(1+la2*mu)*beta(ind_I);
    beta(jmax)=beta(jmax)+la1;
    if (vert2==2);
        alind(imin)=0;
        beta(imin)=0;
    else
        beta(imin)=beta(imin)-la2*mu;
    end;
end;
return;

%---------------------------------------------------------------------%
%                                                                     %  
%                           Function Gilbert_Step                     %  
%                                                                     %  
%---------------------------------------------------------------------%
function success=Gilbert_Step(kmax,x,y,C,kernel,kerneloption);




global  n;
% global  C;
% global  kernel;
% global  kerneloption;
% global  x;
% global  y;
global  deluu;
global  delvv;
global  deluv;
global  delzz;
global  eu;
global  ev;
global  alind;
global  beta;



if y(kmax)==1 
    imax = kmax;
    d11 = delzz;
    dimax=svmkernel(x(imax,:),kernel,kerneloption,x(imax,:))+(imax==imax)./C;
    d22 = dimax + delvv - 2.0*ev(imax);
    d12 = eu(imax) - ev(imax) - deluv + delvv;
    [d,lambda]=linesegment(d11,d22,d12);
    if (d >= delzz) | d < 0
        
        success=0;
        return;
    end;
    success=1;
    delzz=d;
    om = 1.0 - lambda;
    deluu = om*om*deluu + lambda*lambda*dimax +  2*lambda*om*eu(imax);
    deluv = om*deluv + lambda*ev(imax);
    ind_SV=find(alind==1);
    eu(ind_SV)=om*eu(ind_SV)+lambda*(svmkernel(x(imax,:),kernel,kerneloption,x(ind_SV,:))+(ind_SV==imax)./C);
    
    ind_I=intersect(find(y==1),find(alind==1));
    beta(ind_I)=om*beta(ind_I);
    beta(imax)=beta(imax)+lambda;
    
    
    
else
    jmax=kmax;
    d11 = delzz;
    djmax=svmkernel(x(jmax,:),kernel,kerneloption,x(jmax,:))+(jmax==jmax)./C;
    d22 = djmax + deluu - 2.0*eu(jmax);
    d12 = ev(jmax) - eu(jmax) - deluv + deluu;
    [d,lambda]=linesegment(d11,d22,d12);
    if (d >= delzz) | d < 0
        
        
        success=0;
        return;
    end;
    success=1;
    delzz=d;
    om = 1.0 - lambda;
    delvv = om*om*delvv + lambda*lambda*djmax + 2*lambda*om*ev(jmax);
    deluv = om*deluv + lambda*eu(jmax);
    ind_SV=find(alind==1);
    ev(ind_SV)=om*ev(ind_SV)+lambda*(svmkernel(x(jmax,:),kernel,kerneloption,x(ind_SV,:))+(ind_SV==jmax)./C);
    ind_J=intersect(find(y==-1),find(alind==1));
    beta(ind_J)=om*beta(ind_J);
    beta(jmax)=beta(jmax)+lambda;
end;
return

%---------------------------------------------------------------------%
%                                                                     %  
%                           Function Triangle                         %  
%                                                                     %  
%---------------------------------------------------------------------%



function [d,lambda1,lambda2,lambda3,flag]=triangle(d11,d22,d33,d12,d13,d23)

%   Tech Rep : A Fast Iterative NPA for SVM Classifier
%   S. Keerthi et al
% 
%   23/03/2001


[d,lambda2,vert]=linesegment(d11,d22,d12);
lambda1=1-lambda2;
lambda3=0;
if (vert==1) 
    flag = 1;
else 
    if (vert== 2) 
        flag = 2;
    else
        flag = 4;
    end;
end;



[dtilde,lambda3tilde,vert]=linesegment(d22,d33,d23);
if dtilde<d 
    d=dtilde;
    lambda1=0;
    lambda2=1-lambda3tilde;
    lambda3=lambda3tilde;
    if (vert==1) 
        flag = 2;
    else 
        if (vert== 2) 
            flag = 3;
        else
            flag = 5;
        end;
    end;
    
end;

[dtilde,lambda1tilde,vert]=linesegment(d33,d11,d13);
if dtilde<d 
    d=dtilde;
    lambda1=lambda1tilde;
    lambda2=0;
    lambda3=1-lambda1tilde;   
    if (vert==1) 
        flag = 3;
    else 
        if (vert== 2) 
            flag = 1;
        else
            flag = 6;
        end;
    end;
    
end;

e11=d22+d11-2*d12;
e22=d33+d11-2*d13;
e12=d23-d12-d13+d11;
den=e11*e22-e12^2;
if den <=0
    return
end;
f1=d11-d12;
f2=d11-d13;
lambda2tilde=(e22*f1-e12*f2)/den;
lambda3tilde=(-e12*f1+e11*f2)/den;
lambda1tilde=1-lambda2tilde-lambda3tilde;
dtilde=d11-lambda2tilde*f1-lambda3tilde*f2;
if (lambda1tilde>0) & (lambda2tilde>0) & (lambda3tilde>0) & (dtilde<d)
    d=dtilde;
    lambda1=lambda1tilde;
    lambda2=lambda2tilde;
    lambda3=lambda3tilde;
    flag=0;
end;

%---------------------------------------------------------------------%
%                                                                     %  
%                           Function Twolines                         %  
%                                                                     %  
%---------------------------------------------------------------------%

function [d,lambda1,lambda2,flag,vert1,vert2]=twolines(r,s1,s2,d1,d2,dold);

%   Tech Rep : A Fast Iterative NPA for SVM Classifier
%   S. Keerthi et al
% 
%   23/03/2001



if (d1<=0) | (d2<=0)
    d=[];
    lambda1=[];
    lambda2=[];
    vert1=[];
    vert2=[];
    flag=0;
    
    
    return;
end;
den=d1*d2-r.^2;
if den <=0
    d=[];
    lambda1=[];
    lambda2=[];
    vert1=[];
    vert2=[];
    flag=0;
    
    return;
end;
lambda1=(s1*d2-s2*r)/den;
if lambda1<0
    lambda1=0;
    vert1=0;
else
    if lambda1>1
        lambda=1;
        vert1=2;
    else
        vert1=0;
    end;
end,
lambda2=(lambda1*r-s2)/d2;
if lambda2<0
    lambda2=0;
    vert2=1;
else
    if lambda2>1
        lambda2=1;
        vert2=2;
    else
        d=dold+d1*lambda1^2+d2*lambda2^2-2*r*lambda1*lambda2+2*s2*lambda2-2*s1*lambda1;
        flag=1;
        vert2=0;
        return;
    end;
end,
lambda1=(lambda2*r+s1)/d1;
if lambda1<0
    lambda1=0;
    vert1=1;
else
    if lambda1>1
        lambda1=1;
        vert1=2;
    else
        vert1=0;
    end;
end;
d=dold+d1*lambda1^2+d2*lambda2^2-2*r*lambda1*lambda2+2*s2*lambda2-2*s1*lambda1;
flag=1;


%---------------------------------------------------------------------%
%                                                                     %  
%                           Function LineSegment                      %  
%                                                                     %  
%---------------------------------------------------------------------%


function  [d,lambda,vert]=linesegment(d11,d22,d12);


%   
%   Tech Rep : A Fast Iterative NPA for SVM Classifier
%   S. Keerthi et al
% 
%   23/03/2001

d=d11;
lambda=0;
vert=1;
if d22< d
    d=d22;
    lambda=1;
    vert=2;
end;
den=d11+d22-2*d12;
if den <=0
    return
end;
num=d11*d22-d12.^2;
dtilde=num/den;
lambdatilde=(d11-d12)/den;
if (lambdatilde>0 & lambdatilde<1) & dtilde<d 
    d=dtilde;
    lambda=lambdatilde;
    vert=0;
end;