SVM-及SMO算法实现

⽀持向量机SMO算法实现（注释详细）⼀：SVM算法（⼀）见西⽠书及笔记（⼆）统计学习⽅法及笔记（三）推⽂（四）推⽂⼆：SMO算法（⼀）见西⽠书及笔记（⼆）统计学习⽅法及笔记（三）见机器学习实战及笔记（四）推⽂三：代码实现（⼀）SMO中的辅助函数（⼀）加载数据集import numpy as npimport matplotlib.pyplot as plt#⼀：SMO算法中的辅助函数#加载数据集def loadDataSet(filename):dataSet = np.loadtxt(filename)m,n = dataSet.shapedata_X = dataSet[:,0:n-1]data_Y = dataSet[:,n-1]return data_X,data_Y（⼆）随机选取⼀个J值，作为α_2的下标索引#随机选取⼀个数J，为后⾯内循环选取α_2做辅助（如果α选取不满⾜条件，就选择这个⽅法随机选取）def selectJrand(i,m): #主要就是根据α_1的索引i,从所有数据集索引中随机选取⼀个作为α_2的索引j = iwhile j==i:j = np.int(np.random.uniform(0,m)) #从0~m中随机选取⼀个数，是进⾏整数化的print("random choose index for α_2:%d"%(j))return j #由于这⾥返回随机数，所以后⾯结果可能导致不同（三）根据关于α_1与α_2的优化问题对应的约束问题分析，对α进⾏截取约束def clipAlpha(aj,H,L): #根据我们的SVM算法中的约束条件的分析，我们对获取的aj,进⾏了截取操作if aj > H:aj = Hif aj < L:aj = Lreturn aj四：代码实现（⼆）SMO中的⽀持函数（⼀）定义⼀个数据结构，⽤于保存所有的重要值#⾸先我们定义⼀个数据结构（类），来保存所有的重要值class optStruct:def __init__(self,data_X,data_Y,C,toler): #输⼊参数分别是数据集、类别标签、常数C⽤于软间隔、和容错率tolerself.X = data_Xbel = data_Yself.C = Cself.toler = toler #就是软间隔中的ε，调节最⼤间隔⼤⼩self.m = data_X.shape[0]self.alphas = np.zeros(self.m) #存放每个样本点的α值self.b = 0 #存放阈值self.eCache = np.zeros((self.m,2)) #⽤于缓存误差，每个样本点对应⼀个Ei值，第⼀列为标识符，标志是否为有效值，第⼆列存放有效值（⼆）计算每个样本点k的Ek值，就是计算误差值=预测值-标签值#计算每个样本点k的Ek值，就是计算误差值=预测值-标签值def calcEk(oS,k):# 根据西⽠书6.24，我们可以知道预测值如何使⽤α值进⾏求解fxk = np.multiply(oS.alphas,bel).T@(oS.X@oS.X[k,:])+oS.b #np.multiply之后还是(m,1),(oS.X@oS.X[k,:])之后是(m,1),通过转置(1,m)@(m,1)-->实数后+b即可得到预测值fx#获取误差值EkEk = fxk - bel[k]return Ek（三）重点：内循环的启发式⽅法，获取最⼤差值|Ei-Ej|对应的Ej的索引J#内循环的启发式⽅法，获取最⼤差值|Ei-Ej|对应的Ej的索引Jdef selectJ(i,oS,Ei): #注意我们要传⼊第⼀个α对应的索引i和误差值Ei,后⾯会⽤到maxK = -1 #⽤于保存临时最⼤索引maxDeltaE = 0 #⽤于保存临时最⼤差值--->|Ei-Ej|Ej = 0 #保存我们需要的Ej误差值#重点：这⾥我们是把SMO最后⼀步（根据最新阈值b，来更新Ei)提到第⼀步来进⾏了，所以这⼀步是⾮常重要的oS.eCache[i] = [1,Ei]#开始获取各个Ek值，⽐较|Ei-Ej|获取Ej的所有#获取所有有效的Ek值对应的索引validECacheList = np.where(oS.eCache[:,0]!=0)[0] #根据误差缓存中第⼀列⾮0，获取对应的有效误差值if len(validECacheList) > 1: #如果有效误差缓存长度⼤于1(因为包括Ei),则正常进⾏获取j值，否则使⽤selectJradn⽅法选取⼀个随机J值for k in validECacheList:if k == i: #相同则不处理continue#开始计算Ek值，进⾏对⽐，获取最⼤差值Ek = calcEk(oS,k)deltaE = abs(Ei - Ek)if deltaE > maxDeltaE: #更新Ej及其索引位置maxK = kmaxDeltaE = deltaEEj = Ekreturn maxK,Ej #返回我们找到的第⼆个变量α_2的位置else: #没有有效误差缓存，则随机选取⼀个索引，进⾏返回j = selectJrand(i,oS.m)Ej = calcEk(oS,j)return j,Ej（四）实现更新Ek操作#实现更新Ek操作,因为除了最后我们需要更新Ei之外，我们在内循环中计算α_1与α_2时还是需要⽤到E1与E2，#因为每次的E1与E2由于上⼀次循环中更新了α值，所以这⼀次也是需要更新E1与E2值，所以单独实现⼀个更新Ek值的⽅法还是有必要的def updateEk(oS,k):Ek = calcEk(oS,k)oS.eCache[k] = [1,Ek] #第⼀列1，表⽰为有效标识五：代码实现（三）SMO中的内循环函数外循环是要找违背KKT条件最严重的样本点(每个样本点对应⼀个α),这⾥我们将外循环的该判别条件放⼊内循环中考虑。

SMO 方法的实现及证明1．问题的阐述SVM 是从线性可分情形下的最优分类面发展而来。

基本思想可以用图(2-16)的二维情况说明。

图2-16 线性可分情况下的最优分类线图中实心点和空心点代表两类样本，H 为分类线H1,H2分别为过各类中离分界线最近的样本且平行于分类线的直线，它们之间的距离叫做分类间隔(margin)。

所谓最优分类线就是要求分类线不仅能将两类正确分开(训练错误率为0)，而且使分类间隔最大。

推广到一般线性可分情形，假设分类方程为0,=+><b ωx 1,1{,−+∈∈y R d x ，对其进行归一化，样本集，满足},,,2,1),,(=n i y i i x K 01),(≥−+><b y i ωx i(1)构造损失函数作为目标函数及约束条件，即：()∑+=ii C w W ξ2:minimize 2α(2-a) ()i b x w y i i T i ∀−≥+,1 subject to ξ(2-b)i i ∀≥,0ξ(2-c)经过拉格朗日变换以及KKT 定理推导，式子变为：0 subject to 21)(:minimize ,=≤≤−=∑∑∑iii i ij i ji j i j i i yCx x y y W αααααα(3)引入核函数，最后的目标函数变为：()iC y K y y W i ni i i n i nj j i j i ni i ∀≤≤=−=∑∑∑∑====,00 subject to 21)(: maximize 1111ααααααj i x ,x (4)改写为矩阵相乘的格式，得到：l i C f i T ,....,1,00 subject to 21)(minT =≤≤=−=ααy αe Q αααT(5)其中e 为全1向量，为所有变量的上界，为C Q l l ×的半正定矩阵。

训练向量通过i x φ函数被映射到更高维的空间(可能为无穷维)， ，其中为核函数。

svm求解序列最小优化算法摘要：1.SMO 算法概述2.SMO 算法的关键步骤3.SMO 算法的代码实践4.SMO 算法在支持向量机中的应用5.总结正文：一、SMO 算法概述序列最小优化算法（Sequential Minimal Optimization，简称SMO）是一种求解支持向量机（Support Vector Machine，简称SVM）模型参数的迭代算法。

它通过每次优化一个变量，直至找到最优解，从而提高模型的预测性能。

二、SMO 算法的关键步骤1.初始化参数：初始化拉格朗日乘子α和阈值b。

2.预测误差：计算当前参数下的预测误差。

3.确定最小化目标：根据预测误差，确定需要最小化的目标函数。

4.优化拉格朗日乘子：通过最小化目标函数，更新拉格朗日乘子。

5.检查停止条件：当满足停止条件（如达到迭代次数限制或预测误差足够小）时，结束迭代。

6.输出结果：输出当前最优参数。

三、SMO 算法的代码实践以下是使用Python 实现SMO 算法的简单示例：```pythonimport numpy as npdef predict_error(X, y, alpha, b, X_test):# 计算预测误差passdef minimize_alpha(alpha, X, y, b, X_test):# 优化拉格朗日乘子passdef smo(X, y, max_iter, tol):# 初始化参数alpha = np.zeros(len(X[0]))b = 0# 迭代for _ in range(max_iter):# 计算预测误差error = predict_error(X, y, alpha, b, X_test)# 确定最小化目标if error > tol:# 优化拉格朗日乘子alpha = minimize_alpha(alpha, X, y, b, X_test)else:# 检查停止条件breakreturn alpha, b# 示例：使用SMO 算法构建半监督式支持向量机模型#...# 示例：使用SMO 算法求解序列最小优化问题#...```四、SMO 算法在支持向量机中的应用SMO 算法在支持向量机中应用广泛，可以用于求解分类问题和回归问题。

机器学习——⽀持向量机（SVM）之拉格朗⽇乘⼦法，KKT条件以及简化版SMO算法分析SVM有很多实现，现在只关注其中最流⾏的⼀种实现，即序列最⼩优化（Sequential Minimal Optimization，SMO）算法，然后介绍如何使⽤⼀种核函数（kernel）的⽅式将SVM扩展到更多的数据集上。

1.基于最⼤间隔分隔数据⼏个概念：1.线性可分（linearly separable）：对于图6-1中的圆形点和⽅形点，如果很容易就可以在图中画出⼀条直线将两组数据点分开，就称这组数据为线性可分数据2.分隔超平⾯（separating hyperplane）：将数据集分隔开来的直线称为分隔超平⾯3.如果数据集是1024维的，那么就需要⼀个1023维的超平⾯来对数据进⾏分隔4.间隔（margin）：数据点到分隔⾯的距离称为间隔5.⽀持向量（support vector）:离分隔超平⾯最近的那些点⽀持向量机的优点：泛化错误率低，计算开销不⼤，结果易解释⽀持向量机的缺点：对参数调节和核函数的选择敏感，原始分类器不加修改仅适⽤于处理⼆类问题适⽤数据类型：数值型和标称型数据2.寻找最⼤间隔如何求解数据集的最佳分隔直线？分隔超平⾯的形式可以写成其中 w = (w1,w2,w3...wd)为法向量，决定了超平⾯的⽅向，其中d等于数据的维度，这很好理解，假设⼆维的(x1,x2)点可以被 ax+b=0 分隔，这⾥⾯直线 ax+b=0 是⼀维的，但是这⾥⾯a和x都是⼆维的b为位移项，决定了超平⾯与原点之间的距离对于图6-3中A点到分隔直线的距离为表⽰向量的模，，w与w共轭的内积再开⽅假设超平⾯（w,b）能将训练样本正确分类，即对于 ,有则两个异类⽀持向量到超平⾯的距离之和为欲找到具有“最⼤间隔（maximum margin）”的划分超平⾯，也就是要找到能满⾜中约束的参数w和b，使得最⼤，即 ，其中约束条件为　s.t. ，其实这个约束条件就是把两个不等式合并成了⼀个显然，为了最⼤化间隔，仅需最⼤化，这等价于最⼩化，于是上式可重写为 ，其中约束条件为　s.t.这就是⽀持向量机（Support Vector Machine，简称SVM）的基本型对于这类带有不等式约束的最优化问题，可以使⽤拉格朗⽇乘⼦法（Lagrange Multiplier）对其进⾏求解。

SVM算法说明和优化算法介绍SVM（Support Vector Machine，支持向量机）是一种常用的机器学习算法，用于分类和回归分析。

SVM的基本思想是通过在特征空间中构造一个最优超平面，将不同类别的样本分开。

本文将为您介绍SVM的基本原理、分类和回归问题的实现方法以及一些常见的优化算法。

SVM的基本原理是寻找一个能够最大化类别间间隔（margin）的超平面，从而达到更好的分类效果。

在特征空间中，样本点可以用向量表示，所以SVM也可以看作是在特征空间中寻找一个能够最优分割两类样本的超平面。

为了找到这个最优超平面，SVM使用了支持向量（Support Vector），即离超平面最近的样本点。

支持向量到超平面的距离被称为间隔，而最优超平面使得间隔最大化。

对于线性可分的情况，SVM的目标是最小化一个损失函数，同时满足约束条件。

损失函数由间隔和误分类样本数量组成，约束条件则包括对超平面的限制条件。

通过求解优化问题，可以得到最优超平面的参数值。

对于非线性可分的情况，SVM使用核函数进行转换，将低维特征空间中的样本映射到高维特征空间中，从而使得样本在高维空间中线性可分。

SVM在分类问题中的应用广泛，但也可以用于回归问题。

在回归问题中，SVM的目标是找到一个超平面，使得点到该平面的距离尽可能小，并且小于一个给定的阈值。

SVM回归的思想是通过引入一些松弛变量，允许样本点在一定程度上偏离超平面来处理异常数据，从而得到更好的回归结果。

在实际应用中，SVM的性能和效果受到许多因素的影响，如数据集的分布、样本的数量和特征的选择等。

为了进一步优化SVM的性能，许多改进算法被提出。

下面我们介绍几种常见的SVM优化算法。

1.序列最小优化算法（SMO）：SMO是一种简单、高效的SVM优化算法。

它通过将大优化问题分解为多个小优化子问题，并使用启发式方法进行求解。

每次选择两个变量进行更新，并通过迭代优化这些变量来寻找最优解。

SVM的SMO算法实现SVM（Support Vector Machine）是一种常用的分类算法，其原理是将数据集映射到一个高维空间中，使得不同类别的样本能够被一个超平面正确分割。

SMO（Sequential Minimal Optimization）算法是一种用于求解SVM问题的优化算法，其核心思想是将大问题分解为一系列的小问题，通过迭代求解这些小问题来得到最优解。

SMO算法允许一次只优化两个变量，即选择两个变量α_i和α_j进行优化。

具体的优化步骤如下：1. 选择一对需要优化的变量α_i和α_j，使用启发式方法选取这两个变量。

一般选择两个变量时，先遍历整个α向量，找到违反KKT条件最严重的点，KKT（Karush-Kuhn-Tucker）条件是SVM问题的最优性条件，通过判断α向量是否满足该条件来选择需要优化的变量。

2.固定其他变量，通过求解子问题的方式更新选择的两个变量。

通过求解两个变量的二次规划问题，得到更新后的α_i和α_j。

3.更新阈值b。

每次更新α_i和α_j之后，都需要计算新的阈值b。

根据KKT条件，选择满足条件的α_i或α_j来更新阈值b。

4.判断终止条件。

迭代过程中，根据一定的终止条件来决定是否终止算法，一般可以设置最大迭代次数或目标误差。

SMO算法的具体实现如下：1.初始化α向量、阈值b和错误率向量E。

2.选择需要优化的两个变量α_i和α_j。

3.计算变量α_i和α_j的边界。

4.根据变量α_i和α_j是否满足边界来选择优化方法。

5.在选择的两个变量上进行优化。

求解两个变量的二次规划子问题，得到更新后的α_i和α_j。

6.更新阈值b。

7.更新错误率向量E。

8.判断终止条件。

如果满足终止条件则停止迭代，否则返回第2步继续迭代。

完整的SMO算法实现如下：```pythondef smo(X, y, C, tol, max_iter):m, n = X.shapealpha = np.zeros(m)b=0iters = 0while iters < max_iter:alpha_changed = 0for i in range(m):E_i = np.sum(alpha * y * kernel(X, X[i, :])) + b - y[i]if (y[i] * E_i < -tol and alpha[i] < C) or (y[i] * E_i > tol and alpha[i] > 0):j = select_second_alpha(i, m)E_j = np.sum(alpha * y * kernel(X, X[j, :])) + b - y[j]alpha_i_old = alpha[i]alpha_j_old = alpha[j]if y[i] != y[j]:L = max(0, alpha[j] - alpha[i])H = min(C, C + alpha[j] - alpha[i])else:L = max(0, alpha[i] + alpha[j] - C)H = min(C, alpha[i] + alpha[j])if L == H:continueeta = 2 * kernel(X[i, :], X[j, :]) - kernel(X[i, :], X[i, :]) - kernel(X[j, :], X[j, :])if eta >= 0:continuealpha[j] = alpha[j] - y[j] * (E_i - E_j) / etaalpha[j] = clip_alpha(alpha[j], H, L)continuealpha[i] = alpha[i] + y[i] * y[j] * (alpha_j_old - alpha[j]) b1 = b - E_i - y[i] * (alpha[i] - alpha_i_old) *kernel(X[i, :], X[i, :]) - y[j] * (alpha[j] - alpha_j_old) * kernel(X[i, :], X[j, :])b2 = b - E_j - y[i] * (alpha[i] - alpha_i_old) *kernel(X[i, :], X[j, :]) - y[j] * (alpha[j] - alpha_j_old) * kernel(X[j, :], X[j, :])if 0 < alpha[i] < C:b=b1elif 0 < alpha[j] < C:b=b2else:b=(b1+b2)/2alpha_changed += 1if alpha_changed == 0:iters += 1else:iters = 0return alpha, b```以上是SMO算法的简单实现，其中使用了一些辅助函数（如选择第二个变量、计算核函数等），这些函数需要根据具体的问题进行实现。

SVM——详细讲解SMO算法优化两个变量以及变量的选择支持向量机（SVM）是一种二分类模型，它在分类超平面的构建过程中，通过优化二次规划问题求解得到最优的超平面。

而序列最小最优化（Sequential Minimal Optimization，SMO）算法则是一种用于求解SVM 二次规划问题的简化算法。

在SVM中，分类超平面可以表示为w*x+b=0，其中w为法向量，b为截距，x为输入样本。

SVM的目标是找到具有最大边界的超平面，使得训练样本与超平面的距离最大化。

优化SVM的问题可以转化为求解以下二次规划问题：\begin{align*}\min\limits_{\alpha} & \quad \frac{1}{2}\sum_{i=1}^{N}{\sum_{j=1}^{N}{\alpha_i \alpha_j y_i y_j K(x_i, x_j)}} - \sum_{i=1}^{N}{\alpha_i}\\s.t. & \quad \sum_{i=1}^{N}{\alpha_i y_i} = 0 \\& \quad 0 \leq \alpha_i \leq C, \quad i = 1, 2, ..., N\end{align*}\]其中，N是训练样本数量，C是惩罚参数，K(x_i,x_j)是核函数。

SMO算法通过迭代优化变量alpha_i和alpha_j，来逐渐优化整个二次规划问题。

SMO算法的核心步骤有两个：选择变量和优化变量。

1.变量的选择：在每次迭代中，SMO算法通过两个嵌套循环选择优化变量alpha_i和alpha_j。

首先，外层循环选择第一个变量alpha_i，通过遍历所有训练样本点，选择违反KKT条件的样本点。

KKT条件是SVM最优解必须满足的条件，对于正样本来说，条件是alpha_i=0，对于负样本来说，条件是alpha_i=C。

如果选择到了违反KKT条件的alpha_i，就进入内层循环。

SVM算法原理及SMO算法概述SVM (Support Vector Machine) 是一种广泛应用于分类和回归问题的机器学习算法。

它基于统计学习理论中的VC理论，使用间隔最大化的方法进行分类。

在SVM中，我们将训练数据集视为一个在高维空间中的点集。

SVM的目标是找到一个超平面，能够将不同类别的点分开，并且使其离超平面的距离最大化。

这个超平面被称为最优分隔超平面。

具体来说，SVM算法的原理如下：1.数据预处理：将训练样本映射到高维特征空间，使得样本点能够被线性分隔。

2.寻找最优超平面：在高维特征空间中，寻找能够将不同类别的点分开的超平面。

通常情况下，有多个超平面可以进行分类，而SVM的目标是找到使得间隔最大化的那个超平面。

3.使用支持向量进行分类：SVM找到了最优超平面后，它会选择离该超平面最近的一些点，这些点被称为支持向量。

分类时，SVM根据测试点和支持向量的关系进行判断。

SMO (Sequential Minimal Optimization) 是一种用来训练SVM的优化算法。

传统的SVM算法需要同时优化所有的模型参数，计算量较大。

而SMO算法则是一种序列化的简化方法，每次只优化两个模型参数。

SMO算法的主要思想如下：1.初始化模型参数：选择两个待优化的参数α1和α22.选择两个参数：基于一定的策略，选择两个不同的参数α进行优化。

3.通过求解两个参数的约束最优化问题，更新模型参数。

4.更新阈值和偏置：根据更新后的模型参数，计算出新的阈值和偏置。

5.判断终止条件：检查是否满足终止条件，如果满足则停止优化，否则返回第2步。

SMO算法的核心在于选择两个参数进行优化，并通过解决约束最优化问题来更新参数。

通过反复迭代这个过程，最终得到训练好的SVM模型。

SMO算法的优点是可以有效地处理大规模数据集，并且能够避免陷入局部最优解。

同时，SMO算法还可以引入核函数，使得SVM具有非线性分类和回归能力。

总结来说，SVM是一种基于统计学习理论的分类和回归算法，通过间隔最大化的方法寻找最优分隔超平面。

Svm算法原理及实现Svm（support Vector Mac）⼜称为⽀持向量机，是⼀种⼆分类的模型。

当然如果进⾏修改之后也是可以⽤于多类别问题的分类。

⽀持向量机可以分为线性核⾮线性两⼤类。

其主要思想为找到空间中的⼀个更够将所有数据样本划开的超平⾯，并且使得本本集中所有数据到这个超平⾯的距离最短。

⼀、基于最⼤间隔分隔数据1.1⽀持向量与超平⾯在了解svm算法之前，我们⾸先需要了解⼀下线性分类器这个概念。

⽐如给定⼀系列的数据样本，每个样本都有对应的⼀个标签。

为了使得描述更加直观，我们采⽤⼆维平⾯进⾏解释，⾼维空间原理也是⼀样。

举个简单⼦：如下图所⽰是⼀个⼆维平⾯，平⾯上有两类不同的数据，分别⽤圆圈和⽅块表⽰。

我们可以很简单地找到⼀条直线使得两类数据正好能够完全分开。

但是能将据点完全划开直线不⽌⼀条，那么在如此众多的直线中我们应该选择哪⼀条呢？从直观感觉上看图中的⼏条直线，是不是要更好⼀些呢？是的我们就是希望寻找到这样的直线，使得距离这条直线最近的点到这条直线的距离最短。

这读起来有些拗⼝，我们从图三中直观来解释这⼀句话就是要求的两条外⾯的线之间的间隔最⼤。

这是可以理解的，因为假如数据样本是随机出现的，那么这样分割之后数据点落⼊到其类别⼀侧的概率越⾼那么最终预测的准确率也会越⾼。

在⾼维空间中这样的直线称之为超平⾯，因为当维数⼤于三的时候我们已经⽆法想象出这个平⾯的具体样⼦。

那些距离这个超平⾯最近的点就是所谓⽀持向量，实际上如果确定了⽀持向量也就确定了这个超平⾯，找到这些⽀持向量之后其他样本就不会起作⽤了。

图 1 图21.2寻找最⼤间隔1.2.1点到超平⾯的距离公式既然这样的直线是存在的，那么我们怎样寻找出这样的直线呢？与⼆维空间类似，超平⾯的⽅程也可以写成⼀下形式：（1.1）有了超平⾯的表达式之后之后，我们就可以计算样本点到平⾯的距离了。

假设为样本的中的⼀个点，其中表⽰为第个特征变量。

那么该点到超平⾯的距离就可以⽤如下公式进⾏计算：（1.2）其中||W||为超平⾯的范数，常数b类似于直线⽅程中的截距。

基于SVM模式识别系统的设计与实现1．1 主要研究内容（1）现有的手写识别系统普遍采用k近邻分类器，在2000个数字中，每个数字大约有200个样本，但实际使用这个算法时，算法的执行效率并不高，因为算法需要为每个测试向量做2000次距离计算，每个距离计算包括了1024个维度浮点运算，总计要执行900次，此外需要保留所有的训练样本，还需要为测试向量准备2MB的存储空间。

因此我们要做的是在其性能不变的同时，使用更少的内存。

所以考虑使用支持向量机来代替kNN方法，对于支持向量机而言，其需要保留的样本少了很多，因为结果只是保留了支持向量的那些点，但是能获得更快更满意的效果。

（2）系统流程图step1. 收集数据（提供数字图片）step2. 处理数据（将带有数字的图片二值化）step3. 基于二值图像构造向量step4. 训练算法采用径向基核函数运行SMO算法step5. 测试算法（编写函数测试不同参数）1．2 题目研究的工作基础或实验条件（1）荣耀MagicBook笔记本（2）Linux ubuntu 18.6操作系统pycharm 2021 python31．3 数据集描述数据集为trainingDigits和testDigits，trainingDigits包含了大约2000个数字图片，每个数字图片有200个样本；testDigits包含了大约900个测试数据。

1．4 特征提取过程描述将数字图片进行二值化特征提取，为了使用SVM分类器，必须将图像格式化处理为一个向量，将把32×32的二进制图像转换为1×1024的向量，使得SVM可以处理图像信息。

得到处理后的图片如图所示：图1 二值化后的图片编写函数img2vector ，将图像转换为向量：该函数创建1x1024的NumPy 数组，然后打开给定的文件，循环读出文件的前32行，并将每行的头32个字符值存储在 NumPy 数组中，最后返回数组，代码如图2所示：图2 处理数组1．5 分类过程描述 1.5.1 寻找最大间隔寻找最大间隔，就要找到一个点到分割超平面的距离，就必须要算出点到分隔面的法线或垂线的长度。

手推SVM算法（含SMO证明）SVM（支持向量机）是一种二元分类模型，它通过在特征空间中找到一个最优的超平面来进行分类。

SVM算法的核心是构造最优的分类超平面，使得它能够有力地将两类样本分开，并且使得与超平面相距最近的样本点的距离最大化。

SMO（序列最小优化）算法是一种高效求解SVM问题的方法。

为了简化讲解，我们假设SVM的两类样本是线性可分的，即存在一个超平面可以将两类样本完全分开。

在此基础上，我们来推导最优化问题和SMO算法的推导。

1.SVM的最优化问题：我们可以将超平面w·x+b=0中的w归一化，并将超平面转化为w·x+b=0，其中，w，=1、其中，w表示超平面的法向量，b表示超平面的截距。

考虑到SVM的目标是使得距离超平面最近的点离超平面最远，我们可以引入几何间隔的概念。

对于一个样本点(xi, yi)，它距离超平面的几何间隔定义为γi=yi(w·xi+b)/，w。

SVM的最优化问题可以转化为如下的凸优化问题：min ，w，^2/2s.t. yi(w·xi+b)≥ 1, i=1,2,...,n这个优化问题的目标是最小化w的范数的平方，即使得超平面的间隔最大化。

约束条件确保了分类准确性。

2.SMO算法的推导：要解决SVM的最优化问题，可以使用Lagrange乘子法转化为对偶问题。

使用对偶问题可以通过求解其对偶变量来求解原始问题。

通过引入拉格朗日乘子αi≥0，对每个约束条件（yi(w·xi+b)≥1）引入拉格朗日乘子αi，可以得到拉格朗日函数：L(w, b, α) = 1/2，w，^2 - Σαi(yi(w·xi+b) - 1)其中，α=(α1,α2,...,αn)T是拉格朗日乘子向量。

然后，可以通过对L(w,b,α)分别对w和b求偏导并令其等于0，得到w和b的解：w = ΣαiyixiΣαiyi = 0将w代入拉格朗日函数中，可得到关于α的对偶问题：max Σα - 1/2ΣΣαiαjyiyj(xi·xj)s.t. Σαiyi = 0αi≥0,i=1,2,...,n这是一个凸优化问题，通过求解对偶问题得到的α可以进一步求解最优的超平面。

SMO 算法是⼀一种启发式算法，其基本思想是：如果所有变量量的解都满⾜足最优化问题的KKT 条件，那么这个优化问题的解就得到了了，因为KKT 条件是该优化问题的充分必要条件。

否则，选择两个变量量，固定其他变量量，针对这两个变量量构建⼀一个⼆二次规划问题。

这个⼆二次规划问题关于这两个变量量的解应该是更更接近原始⼆二次规划问题的解，因为这会使得原始⼆二次规划问题的⽬目标函数值变得更更⼩小。

重要的是，这时⼦子问题可以通过解析⽅方法求解，这样就可以⼤大⼤大提升整个算法的计算速度。

⼦子问题有两个变量量，⼀一个是违反KKT 条件最严重的那个，另⼀一个由约束条件⾃自动确定。

如果SMO 算法将原问题不不断分解为⼦子问题并对⼦子问题求解，进⽽而达到求解原问题的⽬目的。

通常对于优化问题，我们没有办法的时候就会想到最笨的办法，也就是梯度下降。

注意我们这⾥里里的问题是要求最⼤大值，只要在前⾯面加上⼀一个负号就可以转化为求最⼩小值，所以和并没有什什么本质的区别，其基本思想直观上来说就是：梯度是函数值增幅最⼤大的⽅方向，因此只要沿着梯度的反⽅方向⾛走，就能使得函数值减⼩小得越⼤大，从⽽而期望迅速达到最⼩小值。

当然普通的并不不能保证达到最⼩小值，因为很有可能陷⼊入⼀一个局部极⼩小值。

不不过对于⼆二次规划问题，极值只有⼀一个，所以是没有局部极值的问题。

另外还有⼀一种叫做的变种，它每次只选择⼀一个维度，例例如，它每次选取为变量量，⽽而将其他都看成是常数，从⽽而原始的问题在这⼀一步编程⼀一个⼀一元函数，然后针对这个⼀一元函数求最⼩小值，如此反复轮换不不同的维度进⾏行行迭代。

的主要⽤用处在于那些原本很复杂，但是如果只限制在⼀一维的情况下则变得很简单甚⾄至可以直接求极值的情况，例例如我们这⾥里里的问题，暂且不不管约束条件，如果只看⽬目标函数的话，当只有⼀一个分量量是变量量的时候，这就是⼀一个普通的⼀一元⼆二次函数的极值问题，初中⽣生也会做，带⼊入公式即可。

SVM算法原理及SMO算法概述支持向量机（Support Vector Machine，SVM）是一种非常常用的机器学习算法，被广泛应用于分类和回归问题中。

SVM算法的原理基于统计学习理论，具有较强的理论基础和实际应用。

具体来说，SVM算法的原理可以分为以下几个步骤：1.数据预处理：对原始数据进行标准化处理，使得不同特征之间具有相同的尺度。

2.特征转换：将数据从低维特征空间转换到高维特征空间。

这个转换的方法可以通过核函数来实现，常用的核函数有线性核函数、多项式核函数和高斯核函数等。

3.寻找最优超平面：在高维特征空间中，通过优化问题求解，找到一个最优的超平面，使得样本点距离该超平面的间隔最大。

4.生成分类模型：根据最优超平面，将数据点分为不同的类别。

简单来说，SVM算法的目标是在保证分类精度的前提下，找到使得间隔最大化的超平面，从而提高模型的鲁棒性和泛化能力。

SMO算法（Sequential Minimal Optimization）是一种用于求解SVM 二次规划问题的优化算法。

SMO算法的基本思想是将大规模的二次规划问题分解为一系列求解两个变量的二次规划子问题。

SMO算法的基本流程如下：1.初始化：选择两个变量作为优化变量，然后初始化所有变量的值。

2.选择变量：选择两个变量作为待优化变量。

选择的原则一般是按照最大步长原则，即第一个变量选择违反KKT条件最严重的变量，第二个变量选择使得优化问题目标函数增大最快的变量。

3.优化变量：固定其他变量的值，针对选定的两个变量，求解二次规划问题，更新这两个变量的值。

4.更新阈值：根据更新后的变量值，更新阈值。

5.检验终止条件：检验是否满足终止条件，如果满足则输出最优解，否则返回第二步。

SMO算法的关键在于选择变量和优化变量这两个步骤。

通过选择合适的变量和高效的求解二次规划子问题的方法，可以有效地提高算法的运算效率。

总结来说，SVM算法是一种基于统计学习理论的强大分类算法，通过优化目标函数找到最优的超平面。

⽀持向量机原理（四）SMO算法原理 在SVM的前三篇⾥，我们优化的⽬标函数最终都是⼀个关于\alpha向量的函数。

⽽怎么极⼩化这个函数，求出对应的\alpha向量，进⽽求出分离超平⾯我们没有讲。

本篇就对优化这个关于\alpha向量的函数的SMO算法做⼀个总结。

1. 回顾SVM优化⽬标函数 我们⾸先回顾下我们的优化⽬标函数： \underbrace{ min }_{\alpha} \frac{1}{2}\sum\limits_{i=1,j=1}^{m}\alpha_i\alpha_jy_iy_jK(x_i,x_j) - \sum\limits_{i=1}^{m}\alpha_i s.t. \; \sum\limits_{i=1}^{m}\alpha_iy_i = 0 0 \leq \alpha_i \leq C 我们的解要满⾜的KKT条件的对偶互补条件为：\alpha_{i}^{*}(y_i(w^Tx_i + b) - 1 + \xi_i^{*}) = 0 根据这个KKT条件的对偶互补条件，我们有：\alpha_{i}^{*} = 0 \Rightarrow y_i(w^{*} \bullet \phi(x_i) + b) \geq 1 0 <\alpha_{i}^{*} < C \Rightarrow y_i(w^{*} \bullet \phi(x_i) + b) = 1 \alpha_{i}^{*}= C \Rightarrow y_i(w^{*} \bullet \phi(x_i) + b) \leq 1 由于w^{*} = \sum\limits_{j=1}^{m}\alpha_j^{*}y_j\phi(x_j),我们令g(x) = w^{*} \bullet \phi(x) + b=\sum\limits_{j=1}^{m}\alpha_j^{*}y_jK(x, x_j)+ b^{*}，则有：\alpha_{i}^{*} = 0 \Rightarrow y_ig(x_i) \geq 1 0 < \alpha_{i}^{*} < C\Rightarrow y_ig(x_i) = 1 \alpha_{i}^{*}= C \Rightarrow y_ig(x_i) \leq 12. SMO算法的基本思想 上⾯这个优化式⼦⽐较复杂，⾥⾯有m个变量组成的向量\alpha需要在⽬标函数极⼩化的时候求出。

⽀持向量机（SVM）中的SMO算法1. 前⾔最近⼜重新复习了⼀遍⽀持向量机（SVM）。

其实个⼈感觉SVM整体可以分成三个部分：1. SVM理论本⾝：包括最⼤间隔超平⾯（Maximum Margin Classifier），拉格朗⽇对偶（Lagrange Duality），⽀持向量（Support Vector），核函数（Kernel）的引⼊，松弛变量的软间隔优化（Outliers），最⼩序列优化（Sequential Minimal Optimization）等。

2. 核⽅法（Kernel）：其实核⽅法的发展是可以独⽴于SVM来看待的，核⽅法在很多其它算法中也会应⽤到。

3. 优化理论：这⾥主要介绍的是最⼩序列优化（Sequential Minimal Optimization），优化理论的发展也是独⽴于SVM的。

2. SVM理论基础SVM的理论基础在上⼀篇博客的总结中可以参考：。

对于⽀持向量机（SVM）的简单总结：1. Maximum Margin Classifier2. Lagrange Duality3. Support Vector4. Kernel5. Outliers6. Sequential Minimal Optimization个⼈觉得SMO⼜可以分为两部分：（1）如何选择每次迭代时候的⽬标⼯作集，即选择哪两个拉格朗⽇乘⼦来迭代。

（2）如何对选择好的⼯作集（拉格朗⽇乘⼦）进⾏更新迭代。

3. SMO最初的版本（Platt，1998）SMO就是要解这个凸⼆次规划问题，这⾥的C是个很重要的参数，它从本质上说是⽤来折中经验风险和置信风险的，C越⼤，置信风险越⼤，经验风险越⼩；并且所有的拉格朗⽇乘⼦都被限制在了以C为边长的⼤盒⼦⾥。

SMO的出现使得我们不必去求助于昂贵的第三⽅⼯具去解决这个凸⼆次规划问题，⽬前对它的改进版本很多，这⼀节先介绍它的最初形式和思想。

SMO是Microsoft Research的John C. Platt在《Sequential Minimal Optimization:A Fast Algorithm for Training Support Vector Machines》⼀⽂中提出的，其基本思想是将Vapnik在1982年提出的Chunking⽅法推到极致，即：通过将原问题分解为⼀系列⼩规模凸⼆次规划问题⽽获得原问题解的⽅法，每次迭代只优化由2个点组成的⼯作集，SMO算法每次启发式地选择两个拉格朗⽇乘⼦同时固定其它拉格朗⽇乘⼦来找到这两个拉格朗⽇乘⼦的最优值，直到达到停⽌条件。