第1期 李素，等：群智能算法优化支持向量机参数综述 。71 支持向量机(support vector machine,SVM)是 k(x1,x2)=(《x1,x2〉+R) (2) 20世纪90年代中期发展起来的一种机器学习方法。 高斯核函数： 该方法是基于统计学习理论，通过寻求结构化风险 k()=exp (3) 最小来提高学习机泛化能力，完成经验风险和置信 2w2 范围的最小化，从而达到在统计样本数量较少的情 线性核函数： 况下，也能获得优良统计规律的目的。因为其学习 k(x1,x2)=(x1,x2) (4) 性能突出，所以该领域成了大量学者的焦点。该技 根据问题和数据的不同，选择不同的参数，实际上 术目前也成为机器学习界的研究热点，并在很多领 就得到了不同的核函数，同时核函数的参数选取不 域都得到了成功的应用，如人脸识别、手写数字识 同，会直接影响支持向量机的预测精度和分类性能。 别、文本自动分类以及机器翻译等。 2群智能算法 SVM的基本思想是使用核函数把输入样本空 间映射到高维特征空间，在高维空间中求得一个最 随着人类对生物启发式计算的研究，一些社会 优分类面，得到输入与输出变量间的非线性关系， 性动物的自组织行为引起了科学家的广泛关注。这 如图1所示。 些社会性动物在进化过程中形成了一个共同的特 点：个体的行为都很简单，但当它们一起工作时，却 能够表现出非常复杂的行为特征。 群智能算法的基本思想是模仿自然界当中生物 的种群行为来构造随机优化算法。该算法主要是将 优化和搜索过程模拟成种群中个体的觅食或进化过 程，用搜索空间中的点模仿自然界当中的种群个 输入空间 特征空间 体，将求解问题的目标函数度量成种群中个体对环 图1寻找到的最优分类面 境的适应能力：将种群中个体的优胜劣汰过程或觅 Fig.1 Finding the optimal classification surface 食过程类比为搜索过程中用较优的可行解取代较差 假设给定一个特征空间上的训练数据集 的可行解的寻优迭代过程。因此，群智能算法是一 T={(x1y1),(x2y2),…,(xw,yw)l,其中，x:∈R为第i个 种具有生成+检验”特征的迭代搜索优化算法。 特征向量，也称为实例；y:∈(1，-1，i=1,2,…N,为 群智能算法包括遗传算法、蚁群算法、粒子群 x的类标记，当y:=1时，称x为正例，当y:=-1时，称 算法、人工鱼群算法、人工蜂群算法、萤火虫算法以 x:为负例。(x,y)称为样本点。算法的关键是建立 及蝙蝠算法等，作为一类新型进化算法，以其分布 一个分类超平面作为决策面，使得正例和反例的隔 性、自组织性、强的鲁棒性等优点，已经成功地应用 离边缘最大化。其中分类超平面就是求函数： 于函数优化等领域。群智能算法从一出现便引起了 p(w)=三Ilw 研究者的广泛关注，其理论研究在不断深人的同 (1) s.t.ya(w…x+b)≥1，i=1,2,,N 时，其应用领域也在随之不断扩展，例如交通流模 式中：w是超平面的法向量，b是超平面的常数项， 型验证问题、分布式高效定位问题以及配电系统 x为训练样本，为样本的类别。 中的电容器分配问题，充分说明了群智能算法所 实际中，学者们会经常遇到线性不可分的样 蕴藏的巨大潜力。同时，群智能算法在SVM参数 例，此时常用的做法是把样例特征映射到高维空间 优化方面也得到了广泛的应用，进一步提高了SVM 去。如果凡是遇到线性不可分的样例，一律映射到 的分类预测精度以及泛化能力。 高维空间，那么这个维度大小就会特别高，处理起 3群智能算法优化支持向量机参数 来就会特别困难。此时核函数在处理该问题上面发 挥重要作用，它的价值在于：虽然也是将特征从低 参数优化是SVM研究中的一个重要问题，参 维到高维转换，但不同的是该方法事先会在低维上 数选择的不同会直接影响SVM模型的分类预测精 进行计算，然后将实质上的分类效果表现在了高维 度和泛化能力。常用的传统SVM参数优化方法有 上，这样就避免了直接在高维空间中的复杂计算。 实验法、网格法、梯度下降法等。但是这些算法 在实际应用中，往往依赖先验领域理论知识才 已经难以满足人们需求，存在各种各样的问题。 能选择有效的核函数。广泛使用的核函数主要有： 实验法主要原理是通过不断尝试不同的参数， 多项式核函数： 最后选出一个最适合问题的参数。实验选择方法缺支持向量机 (support vector machine, SVM) 是 20 世纪 90 年代中期发展起来的一种机器学习方法。 该方法是基于统计学习理论，通过寻求结构化风险 最小来提高学习机泛化能力，完成经验风险和置信 范围的最小化，从而达到在统计样本数量较少的情 况下，也能获得优良统计规律的目的。因为其学习 性能突出，所以该领域成了大量学者的焦点。该技 术目前也成为机器学习界的研究热点，并在很多领 域都得到了成功的应用，如人脸识别、手写数字识 别、文本自动分类以及机器翻译等。 SVM 的基本思想是使用核函数把输入样本空 间映射到高维特征空间，在高维空间中求得一个最 优分类面，得到输入与输出变量间的非线性关系， 如图 1 所示。 T = {(x1, y1),(x2, y2),···,(xN, yN)} xi ∈ R n yi ∈ {1,−1} i = 1,2,···,N xi yi = 1 xi yi = −1 xi (xi , yi) 假设给定一个特征空间上的训练数据集 ，其中， 为第 i 个 特征向量，也称为实例； ， ，为 的类标记，当 时，称 为正例，当 时，称 为负例。 称为样本点。算法的关键是建立 一个分类超平面作为决策面，使得正例和反例的隔 离边缘最大化。其中分类超平面就是求函数： φ(w) = 1 2 ∥w∥ 2 s.t. yi(w· xi +b) ⩾ 1,i = 1,2,· · ·,N (1) 式中：w 是超平面的法向量，b 是超平面的常数项， xi 为训练样本，yi 为样本的类别。 实际中，学者们会经常遇到线性不可分的样 例，此时常用的做法是把样例特征映射到高维空间 去。如果凡是遇到线性不可分的样例，一律映射到 高维空间，那么这个维度大小就会特别高，处理起 来就会特别困难。此时核函数在处理该问题上面发 挥重要作用，它的价值在于：虽然也是将特征从低 维到高维转换，但不同的是该方法事先会在低维上 进行计算，然后将实质上的分类效果表现在了高维 上，这样就避免了直接在高维空间中的复杂计算。 在实际应用中，往往依赖先验领域理论知识才 能选择有效的核函数。广泛使用的核函数主要有： 多项式核函数： k(x1 , x2) = (⟨x1 , x2⟩+R) d (2) 高斯核函数： k(x1 , x2) = exp{ − ∥x1 − x2∥ 2 2σ2 } (3) 线性核函数： k(x1, x2) = ⟨x1, x2⟩ (4) 根据问题和数据的不同，选择不同的参数，实际上 就得到了不同的核函数，同时核函数的参数选取不 同，会直接影响支持向量机的预测精度和分类性能。 2 群智能算法 随着人类对生物启发式计算的研究，一些社会 性动物的自组织行为引起了科学家的广泛关注。这 些社会性动物在进化过程中形成了一个共同的特 点：个体的行为都很简单，但当它们一起工作时，却 能够表现出非常复杂的行为特征。 群智能算法的基本思想是模仿自然界当中生物 的种群行为来构造随机优化算法。该算法主要是将 优化和搜索过程模拟成种群中个体的觅食或进化过 程，用搜索空间中的点模仿自然界当中的种群个 体，将求解问题的目标函数度量成种群中个体对环 境的适应能力；将种群中个体的优胜劣汰过程或觅 食过程类比为搜索过程中用较优的可行解取代较差 的可行解的寻优迭代过程。因此，群智能算法是一 种具有“生成+检验”特征的迭代搜索优化算法。 群智能算法包括遗传算法、蚁群算法、粒子群 算法、人工鱼群算法、人工蜂群算法、萤火虫算法以 及蝙蝠算法等，作为一类新型进化算法，以其分布 性、自组织性、强的鲁棒性等优点，已经成功地应用 于函数优化等领域。群智能算法从一出现便引起了 研究者的广泛关注，其理论研究在不断深入的同 时，其应用领域也在随之不断扩展，例如交通流模 型验证问题[2] 、分布式高效定位问题[3]以及配电系统 中的电容器分配问题[4] ，充分说明了群智能算法所 蕴藏的巨大潜力。同时，群智能算法在 SVM 参数 优化方面也得到了广泛的应用，进一步提高了 SVM 的分类预测精度以及泛化能力。 3 群智能算法优化支持向量机参数 参数优化是 SVM 研究中的一个重要问题，参 数选择的不同会直接影响 SVM 模型的分类预测精 度和泛化能力。常用的传统 SVM 参数优化方法有 实验法、网格法、梯度下降法[5-6]等。但是这些算法 已经难以满足人们需求，存在各种各样的问题。 实验法主要原理是通过不断尝试不同的参数， 最后选出一个最适合问题的参数。实验选择方法缺 䒿ڑ金䬠 ➥ᒭ⾦䬠 φ 图 1 寻找到的最优分类面 Fig. 1 Finding the optimal classification surface 第 1 期 李素，等：群智能算法优化支持向量机参数综述 ·71·