·802· 智能系统学报 第13卷 在1995年由Cortes和Vapnik首次提出来的一种 分界面的法向量w只受支持向量的影响，不受非 模式识别分类技术2。SVM是在统计学习理论 支持向量训练点的影响。 (statistical learning theory,SLT)原理的基础上发展 2)非线性可分 起来的机器学习算法。SVM方法的重点在于在 SVM通过运用合适的非线性映射，如 高维特征空间中能构造函数集VC维尽可能小的 P:x→(x)把分类问题原训练样本点转变（映 最优分类面，使得不同类别样本在这分类面上分 射)到新的地方（新特征空间），使得原样本在这新 类上界最小化，从而保证分类算法的最优推广能 特征空间（目标高维空间）中能够线性可分，然后 力。图7所示的是SVM方法的分类原理示意 在这新的映射空间中利用线性可分问题求解原理 图。SVM在有限训练样本情况下，在学习机复杂 求出最终的最优分类面。 度和学习机泛化能力之间找到一个平衡点，从而 为此，需要在式(3)中增加一个松弛变量：和 保证学习机的推广能力0。 惩罚因子C,从而式(3)变为 最优超平面 wx+b=0 min(,)= f+e2s,uyl+-l+6>0 00 (5) 2 分类间隔= 式中：≥0；i=1,2,,n;C为控制样本对错分的 分离超平面 调整因子，通常称为惩罚因子。C越大，惩罚越重。 0● 虽然原理看起来简单，然而在分类问题的训 练样本不充足或不能保证训练样本质量的情形下 支持向量 ●类别1 确定非线性映射是很困难的，那么如何确定非线 :分类错误 O类别2 性映射呢？SVM通过运用核函数概念解决这个 图7SVM分类原理示意图 问题，核函数是SVM的其他分类算法无法替代 Fig.7 SVM classification schematic diagram 的独特功能。 根据样本分布情况与样本集维数，SVM算法 SVM通过引入一个核函数K(x,x),将原低维 的判别函数原理大致可分为线性可分与非线性可 的分类问题空间映射到高维的新问题空间中，使 分两种形式。 核函数代替ω()内积运算，这个高维空间就称 1)线性可分 为Hilbert空间。引入核函数以后的最优分类函数为 带有以式(2)所示训练样本集的SVM线性可 f (x)=sign ay.K(xx+b (6) 分分类问题的数学模型可通过式(3)来表示： S={(xy),i=1,2,…,ri,xeR,ye+1,-1}(2) 2.2KNN方法 KNN(K nearest neighbor)分类法是基于实例 minp(w）=lwl,s.ty.[ox+-1≥0，i=1,2…n 的学习算法，它需要所有的训练样本都参与分 (3) 假如，对n维空间中的分类界面为wx+b=0, 类。在分类阶段，利用欧氏距离公式，将每个测 试样本与和它邻近的k个训练样本进行比较，然 使得与此分类界面最近的两类样本之间的距离 后将测试样本归属到票数最多的那一类里。 之最大，即为最小，则该分类界面就称为最优 lll KNN算法是根据测试样本最近的k个样本点的 分类界面；ω为权重向量（是x)的法向量），b为函 类别信息来对该测试样本类型进行判别，所以 数阈值。从而最终可得到所求的最优分类函数为 k值的选取非常重要。k值若太小，测试样本特征 f(x)=sign (4) 不能充分体现；k值若太大，与测试样本并不相似 的个别样本也可能被包含进来，这样反而对分类 式中对应a,0时的样本点就是支持向量。因为 不利。KNN算法在分类决策上只凭k个最邻近 最优化问题解a,的每一个分量都与一个训练点 样本类别确定待分样本的所属类。目前，对于 相对应，显然所求得的划分超平面仅仅与对应 k值的选取还没有一个全局最优的筛选方法，这 a,0时的那些训练点(c,x)相关，而跟a=O时的那 也是KNN方法的弊端，具体操作时，根据先验知 些训练点没有任何关系。相应于a0时的训练 识先给出一个初始值，然后需要根据仿真分类实 点(：x)里的输入点x就是支持向量，通常它们是 验结果重新调整，调整k值的操作有时一直到分 全体样本中的很少一部分。得出结论，最终分类 类结果满足用户需求为止。该方法原理可由式在 1995 年由 Cortes 和 Vapnik 首次提出来的一种 模式识别分类技术[29]。SVM 是在统计学习理论 (statistical learning theory，SLT) 原理的基础上发展 起来的机器学习算法。SVM 方法的重点在于在 高维特征空间中能构造函数集 VC 维尽可能小的 最优分类面，使得不同类别样本在这分类面上分 类上界最小化，从而保证分类算法的最优推广能 力。图 7 所示的是 SVM 方法的分类原理示意 图。SVM 在有限训练样本情况下，在学习机复杂 度和学习机泛化能力之间找到一个平衡点，从而 保证学习机的推广能力[30]。 H1 H X1 H2 X2 最优超平面 w·x + b = 0 分类间隔 = 2 w 类别 1 分类错误 类别 2 支持向量 分离超平面 图 7 SVM 分类原理示意图 Fig. 7 SVM classification schematic diagram 根据样本分布情况与样本集维数，SVM 算法 的判别函数原理大致可分为线性可分与非线性可 分两种形式。 1) 线性可分 带有以式 (2) 所示训练样本集的 SVM 线性可 分分类问题的数学模型可通过式 (3) 来表示： S = {(xi , yi),i = 1,2,··· ,r}, xi ∈ R n , yi ∈ {+1,−1} (2) minφ(ω) = 1 2 ∥ω∥ 2 ,s.t.yi[ωxi +b]−1 ⩾ 0, i = 1,2,··· ,n (3) ω· x+b = 0 2 ∥ω∥ ∥ω∥ ω 假如，对 n 维空间中的分类界面为 ， 使得与此分类界面最近的两类样本之间的距离 最大，即 为最小，则该分类界面就称为最优 分类界面； 为权重向量 (是 f(x) 的法向量)，b 为函 数阈值。从而最终可得到所求的最优分类函数为 f (x) = sign   ∑n i=1 aiyi(xi · x)+b   (4) 式中对应 ai≠0 时的样本点就是支持向量。因为 最优化问题解 ai 的每一个分量都与一个训练点 相对应，显然所求得的划分超平面仅仅与对应 ai≠0 时的那些训练点 (xi ·x) 相关，而跟 ai=0 时的那 些训练点没有任何关系。相应于 ai≠0 时的训练 点 (xi ·x) 里的输入点 xi 就是支持向量，通常它们是 全体样本中的很少一部分。得出结论，最终分类 分界面的法向量 ω 只受支持向量的影响，不受非 支持向量训练点的影响。 2) 非线性可分 φ : xi → φ(xi) S V M 通过运用合适的非线性映射，如 把分类问题原训练样本点转变 (映 射) 到新的地方 (新特征空间)，使得原样本在这新 特征空间 (目标高维空间) 中能够线性可分，然后 在这新的映射空间中利用线性可分问题求解原理 求出最终的最优分类面。 为此，需要在式 (3) 中增加一个松弛变量 ξi 和 惩罚因子 C，从而式 (3) 变为 minφ(ω, ξ) = 1 2 ∥ω∥ 2 +C ∑n i=1 ξi , s.t.yi[ωxi +b]−1+ξi ⩾ 0 (5) 式中：ξi ≥ 0；i = 1, 2, ···, n；C 为控制样本对错分的 调整因子，通常称为惩罚因子。C 越大，惩罚越重。 虽然原理看起来简单，然而在分类问题的训 练样本不充足或不能保证训练样本质量的情形下 确定非线性映射是很困难的，那么如何确定非线 性映射呢？SVM 通过运用核函数概念解决这个 问题，核函数是 SVM 的其他分类算法无法替代 的独特功能。 ω·φ(x) SVM 通过引入一个核函数 K(xi ·x)，将原低维 的分类问题空间映射到高维的新问题空间中，使 核函数代替 内积运算，这个高维空间就称 为 Hilbert 空间。引入核函数以后的最优分类函数为 f (x) = sign   ∑n i=1 aiyiK(xi · x)+b   (6) 2.2 KNN 方法 KNN(K nearest neighbor) 分类法是基于实例 的学习算法，它需要所有的训练样本都参与分 类 [31]。在分类阶段，利用欧氏距离公式，将每个测 试样本与和它邻近的 k 个训练样本进行比较，然 后将测试样本归属到票数最多的那一类里[ 3 2 ]。 KNN 算法是根据测试样本最近的 k 个样本点的 类别信息来对该测试样本类型进行判别，所以 k 值的选取非常重要。k 值若太小，测试样本特征 不能充分体现；k 值若太大，与测试样本并不相似 的个别样本也可能被包含进来，这样反而对分类 不利。KNN 算法在分类决策上只凭 k 个最邻近 样本类别确定待分样本的所属类。目前，对于 k 值的选取还没有一个全局最优的筛选方法，这 也是 KNN 方法的弊端，具体操作时，根据先验知 识先给出一个初始值，然后需要根据仿真分类实 验结果重新调整，调整 k 值的操作有时一直到分 类结果满足用户需求为止。该方法原理可由式 ·802· 智 能 系 统 学 报 第 13 卷