基于smo算法的数据分类Matlab仿真：线性与非线性对比

1.算法仿真效果

matlab2022a仿真结果如下：

2.算法涉及理论知识概要

SVM通常用对偶问题来求解，这样的好处有两个：1、变量只有N个（N为训练集中的样本个数），原始问题中的变量数量与样本点的特征个数相同，当样本特征非常多时，求解难度较大。2、可以方便地引入核函数，求解非线性SVM。求解对偶问题，常用的算法是SMO，彻底地理解这个算法对初学者有一定难度，本文尝试模拟算法作者发明该算法的思考过程，让大家轻轻松松理解SMO算法。文中的“我”拟指发明算法的大神。

登录后复制

序列最小优化算法（Sequential minimal optimization, SMO）是一种用于解决支持向量机训练过程中所产生优化问题的算法。SMO由微软研究院的约翰·普莱特于1998年发明，被广泛使用于SVM的训练过程中，并在通行的SVM库LIBSVM中得到实现。1998年，SMO算法发表在SVM研究领域内引起了轰动，因为先前可用的SVM训练方法必须使用复杂的方法，并需要昂贵的第三方二次规划工具。而SMO算法较好地避免了这一问题 。

SMO算法由Microsoft Research的John C. Platt在1998年提出，并成为最快的二次规划优化算法，特别针对线性SVM和数据稀疏时性能更优。关于SMO最好的资料就是他本人写的《Sequential Minimal Optimization A Fast Algorithm for Training Support Vector Machines》了。

对偶函数最后的优化问题：

登录后复制

要解决的是在参数上求最大值W的问题，至于和都是已知数。C由我们预先设定，也是已知数。按照坐标上升的思路，我们首先固定除以外的所有参数，然后在上求极值。等一下，这个思路有问题，因为如果固定以外的所有参数，那么将不再是变量（可以由其他值推出），因为问题中规定了。

3.MATLAB核心程序

登录后复制

if (nargin<4)
    kernel_type = 'linear';
end
if (nargin<5)
    max_iter = 20;
end
if (nargin<6)
    epsilon = 1e-3;
end
if (nargin<7)
    tolerate = 1e-5;
end
 
N = size(y,1);
iter_counts = 0;
alpha_change = 100; % a large number
alpha = C*rand(N,1);
 
while (iter_counts < max_iter && alpha_change>epsilon)
   iter_counts  = iter_counts +  1;
   i = choose_work_set(X,y,alpha,C,kernel_type);
   alpha_prev = alpha; % use in check convergence 
   for j=1:size(alpha,1) % second index
       if j==i
           continue
       end
       xi = X(i,:);
       xj = X(j,:);
       yi = y(i);
       yj = y(j);
       
       kappa = K(xi,xi,kernel_type) + K(xj,xj,kernel_type) - 2*K(xi,xj,kernel_type);
       if kappa == 0
           continue
       end
       
       [U,V] = compute_UV(C,alpha(i),alpha(j),yi,yj);
       
       idx = find(alpha>0 & alpha<C);
       if isempty(idx)
           idx = 1;
       else
           idx = idx(1);
       end
       
       b = y(idx) - sum(alpha.*y.*K(X,X(idx,:),kernel_type));
       
       Ei = sum(alpha.*y.*K(X,xi,kernel_type)) + b - yi;
       Ej = sum(alpha.*y.*K(X,xj,kernel_type)) + b - yj;
      
       alpha_j_unc = alpha(j) + (yj*(Ei - Ej))/kappa;
       
       % Fix
       if alpha_j_unc > V
           alpha_j_new = V;
       elseif alpha_j_unc < U
           alpha_j_new = U;
       else
           alpha_j_new = alpha_j_unc;
       end
       
       alpha_i_new = alpha(i) + yi*yj*(alpha(j) - alpha_j_new);    
       
       alpha(i) = alpha_i_new;
       alpha(j) = alpha_j_new;
   end
% Check convergence
alpha_change = norm(alpha - alpha_prev);
end
end

免责声明：本文系网络转载或改编，未找到原创作者，版权归原作者所有。如涉及版权，请联系删