基于遗传算法的支持向量机特征选择与参数优化外文翻译资料
2022-11-18 07:11
英语原文共 10 页，剩余内容已隐藏，支付完成后下载完整资料
基于遗传算法的支持向量机特征选择与参数优化
a国立高雄第一科技大学信息管理 黄成龙
b华中科技大学信息管理系 王杰仁
摘要
支持向量机作为模式分类的新技术之一，在许多应用领域得到了广泛的应用。 训练过程中SVM的内核参数设置会影响分类精度。 特征选择是影响分类准确性的另一个因素。 本研究的目的是同时优化参数和特征子集而不降低SVM分类精度。 我们提出了一种用于特征选择和参数优化的遗传算法方法来解决这种问题。
我们尝试了使用所提出的基于遗传算法的方法和网格算法的几个真实世界的数据集，网格算法是执行参数搜索的传统方法。 与网格算法相比，我们提出的基于遗传算法的方法显着提高了分类精度，并且支持向量机的输入特征更少。
关键词：支持向量机；分类；特征选择；遗传算法；数据挖掘
1．介绍
支持向量机（SVM）最初是由Vapnik（1995）提出的，最近被用于一系列问题，包括模式识别（Pontil和Verri，1998），生物信息学（Yu，Ostrouchov，Geist，＆Samatova，1999）和 文本分类（Joachims，1998）。 SVM通过确定一组支持向量来对具有不同类别标签的数据进行分类，所述支持向量是构成特征空间中的超平面的训练输入集合的成员。 SVM提供了一种通用的机制，使用核函数将超平面表面与训练数据相匹配。 用户可以在选择沿着该函数的表面的支持向量的训练过程期间为SVM选择核函数（例如线性，多项式或S形）。
当使用支持向量机时，面临两个问题：如何选择支持向量机的最优输入特征子集，以及如何设置最佳内核参数。 这两个问题是至关重要的，因为特征子集选择会影响相应的内核参数，反之亦然（Fr.HLICH和夏佩尔，2003）。因此，必须同时获得最优特征子集和SVM参数。
许多实际的模式分类任务要求学习适当的分类函数，该函数将给定的输入模式分配给一组有限的类，这些输入模式通常由属性值向量表示。 特征选择用于识别数据库内强有力的预测性字段子集，并减少呈现给采矿过程的字段数量。 通过尽可能多地从给定数据集中提取尽可能多的信息，同时使用最少数量的特征，我们可以节省大量的计算时间并构建更好地适用于看不见的数据点的模型。 根据Yang和Honavar（1998）的研究，用于表示呈现给分类器的模式的特征的选择会影响多种模式分类方面，包括学习分类算法的准确性，学习分类函数所需的时间， 学习所需的示例以及与功能相关的成本
除了特征选择之外，正确的参数设置可以提高SVM分类的准确性。 应该优化的参数包括惩罚参数C和核函数参数，例如径向基函数（RBF）核的伽马（g）。 要设计一个SVM，必须选择一个核函数，设置内核参数并确定一个软边界常数C（惩罚参数）。 在使用RBF核函数时，网格算法是寻找最佳C和伽马的替代方法。 然而，这种方法耗时且效果不佳（Hsu和Lin，2002; LaValle和Branicky，2002）。 而且，网格算法不能执行特征选择任务。
遗传算法有可能同时生成最优特征子集和SVM参数。 我们的研究目标是同时优化参数和特征子集，而不降低SVM分类精度。 所提出的方法以演进的方式执行特征选择和参数设置。 基于特征选择是否独立于构造分类器的学习算法而执行，特征子集选择算法可以分为两类：过滤方法和包装方法（John，Kohavi，＆Peger，1994; Kohavi and John ，1997）。 由于准确性，本文使用包装器特征子集选择方法。
在文献中，只有少数算法被提出用于SVM特征选择（Bradley，Mangasarian，＆Street，1998; Bradley和Mangasarian，1998; Weston等人，2001; Guyon，Weston，Barnhill，＆Bapnik，2002; Mao ，2004）。 （Raymer，Punch，Goodman，Kuhn和Jain，2000; Yang和Honavar，1998; Salcedo-Sanz，Prado-Cumplido，Perez-Cruz和Bouson-o-Calzo n，2002）。 然而，这些论文集中在特征选择上，并没有涉及SVM分类器的参数优化。 Frohhlich和Chapelle（2003）提出了一种基于遗传算法的特征选择方法，该方法利用了SVMs泛化误差的理论界限。 SVM正则化参数也可以使用Gro在Frohhlich的论文中进行优化。
本文的结构如下：第2节给出了SVM的简要介绍。第3节介绍基本GA概念。 第4节描述了基于遗传算法的特征选择和参数优化。 第5节介绍了使用所提出的方法对几个现实世界数据集进行分类的实验结果。 第6部分总结了结果并得出了一个总体结论。
2支持向量机简介
2.1最优超平面（线性支持向量机）
在本节中，我们将简要介绍典型的两类分类问题的基本支持向量机概念。这些概念也可以在（Kecman，2001;Scho˝lkopf和Smola，2000; Cristianini和Shawe-Taylor，2000）中找到。给定实例标签对（xi，yi），iZ1,2，...，m的训练集，其中xi2Rn和yi2 {C1，K1}，对于线性可分的情况，数据点将被正确地分类为
lt;w.xigt; b 1 for yi = 1 (1)
lt;w.xigt; b-1for yi =-1 (2)
Eqs。（1）和（2）可以组合成一组不等式。
yi (lt;w.xigt; b) -10 or;i=1,hellip;,m (3)
SVM通过求解下列优化问题找到具有最大余量的最优分离超平面：
w subject to: yi (lt;w.xigt; b) -10 (4)
众所周知，要解决这个二次优化问题，必须找到拉格朗日函数的鞍点：
)= yi (lt;w.xigt; b) -1 (5)
其中AI表示拉格朗日乘数，因此AIR 0。搜索最优鞍点是必要的，因为LP必须最小化相对于原始变量W和B，并且相对于非负对偶变量AI最大化。通过对W和B的微分，得到下列方程：
yi c (6)
yi=0 (7)
最佳约束函数的Kal什库恩- Tukk（KTT）条件对于方程（5）的最大值是必要的和充分的。相应的KKT互补条件是
{ yi (lt;w.xigt; b) -1}=0 or;i (8)
替代公式。（6）及（7）在Eq。（5），然后经双LP是LD的拉格朗日计算（一）：
- (9)
subject to:i0 i=1,hellip;,m and =0
找到最优超平面，双Lagrangian LD（a）必须相对于非负ai最大化。这是一个标准的二次优化问题，可以通过使用一些标准的优化程序来解决。对偶优化问题的解AI确定了最优超平面的参数W*和B*。因此，我们得到了一个最优决策超平面F（x，a*，b*）（Eq.（10））和一个指标决策函数符号[f（x，a*，b*）]。
f(x,) = = (10)
（1）在一个典型的分类任务中，只有一小部分是拉格朗日乘子ai通常倾向于大于零。
（2）在几何学上，这些向量最接近最优超平面。 各自的训练向量具有非零的ai被称为支持向量，作为最优决策超平面具有非零ai的训练向量称为支持向量，作为最优决策超平面。F（x，a，b）仅依赖于它们。
2.2。不可分数据的最优超平面（线性）
广义支持向量机上述概念也可以扩展到非可分离的情形，即当Eq.（3）没有解时。目标是构造一个最小的超平面错误。为了得到这个问题的正式设置，我们介绍了非负松弛变量XIr0，IZ1，，m. Such
lt;w.xigt; b 1- for yi = 1 (11)
lt;w.xigt; b-1for yi =-1 (12)
在这些松弛变量中，找到提供最小训练误差的超平面的问题，即尽可能小地保持约束违反，具有形式表达式。
w C (13)
subject to: yi (lt;w.xigt; b) -10 ,0
该优化模型可以用该方法求解。解决可分离情况下的优化问题。因此，最优超平面具有形式Eq.（17）。视情况而定应用内核中，偏置B可以是内核的隐式部分。功能。因此，如果一个偏倚项可以容纳在核函数，非线性SV分类器可以显示为Eq.（18）。
- (14)
subject to:i i=1,hellip;,m and =0
为了找到最优超平面，双Lagrangian LD（a）必须在非负AI下最大化约束PAIYZ0和0% AI %C，I Z1，M，M.惩罚参数C，现在是ai的上界，是由用户决定。最后，最优决策超平面。与等式（10）相同。
2.3非线性支持向量机
非线性SVM通过映射函数F将训练样本从输入空间映射到高维特征空间，也称为核函数。在对偶拉格朗日（9）中，内积由核函数（15）代替，非线性支持向量机对偶Lagrangian LD（a）（Eq.（16））与线性广义情形相似。
(phi;(xi). phi;(xj)):K() (15)
- (16)
subject to:i i=1,hellip;,m and =0
该优化模型可以用该方法求解。解决可分离情况下的优化问题。因此，最优超平面具有形式Eq.（17）。视情况而定应用内核中，偏置B可以是内核的隐式部分。功能。因此，如果一个偏倚项可以容纳在核函数，非线性SV分类器可以显示为Eq.（18）。
f(x,) =
= (17)
f(x,) == (18)
一些核函数包括多项式、径向基函数（RBF）和SigMID核（Burges，1998），它们被示为函数（19）、（20）和（21）。为了提高分类精度，应适当设置核函数中的这些核参数。
多项式核：
= (19)
径向基函数核：
=exp) (20)
乙状核：
=tanh(k) (21)
三遗传算法
遗传算法（GA）是一种通用的自适应优化算法基于直接与达尔文的类比的搜索方法生物系统中的自然选择和遗传学有前途的替代传统的启发式方法。遗传算法使用一组叫做群体的候选解决方案。基于达尔文的“适者生存”原则遗传算法在一系列迭代后获得最优解计算。遗传算法产生连续的交替种群由染色体表示的解决方案，即解决这个问题，直到获得可接受的结果。与开发的特点相联系探索搜索，GA可以处理大的搜索空间效率高，因此获得局部最优的机会较少。解决方案比其他算法。一个适应度函数评估一个解决方案的质量。评估步骤。交叉和变异函数是
After
Offspring
Crossover Mutation
Fig. 1. Genetic crossover and mutation operation.
Selection Parents 剩余内容已隐藏，支付完成后下载完整资料
资料编号：[24296]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
