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核心程序
function alpha = smo(X,y,C,kernel_type,max_iter,epsilon,tolerate) 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
标签:SMO,SVM,end,分类,smo,算法,matlab,new,alpha From: https://www.cnblogs.com/51matlab/p/17342233.html