基本遗传算法的Matlab程序实现外文翻译资料

英语原文共 29 页，剩余内容已隐藏，支付完成后下载完整资料

摘要

不平衡分布的数据集分类一直以来都是一项挑战。一般来讲，比较受欢迎的提高分类表现的方法是建立一个分类器的系统。然而，这个系统性能的好坏取决于基础分类器的选择。因此，我们提出了一种基于遗传算法的搜索方式来从一系列的基础分类器中搜索最优的组合从而构建一个异构系统。这个算法叫做GA-EoC,在所选数据上使用10个褶皱交叉来评估每个候选集合的质量。为了将基类组合起来作为系统的输出，我们使用了了简单而又泛用的多数投票法。这个算法，由于其随机次级抽样法来平衡各类的分布，经常被用于对非平衡分布数据组的分类。另外一点，假如没有可用的功能集，我们使用（alpha;，beta;）-k特性集的方法来选择一个更好的特征子集类。我们已经从UCI-Machine学习库找了三个基准数据集来测试GA-EoC，一个阿尔茨海默氏症的数据集和哥伦比亚大学PubFig数据库的一个子集。总的来说，这个算法的表现是可靠的并且由于仅仅依靠基分类器的组合以及一些有名的系统。基于我们的实践，可以证明遗传算法是一种高效和可靠的方式来组成一个异构系统，同时我们预计GA-EoC在其他案例中也会有相同的表现。

介绍

分类器系统（EoC）是一系列为了达到最终目的的特殊分类器模型的集合，根据沃伯特的无免费午餐定理^[1]，单一的分类器可能在某些领域表现良好，但是不可能在所有应用领域都适用。因此，通过多个分类器的整合，这个系统理论上就好像多种方法的集合提升了整个组合的能力，从而达到了比任何单个分类器都要高的预测精度^[2]。此外，每个分类器的概括能力也是不尽相同的，这都取决于数据特点和关系（如维数、类分布、噪声比等等)^[3]。在最近的几年，许多困难的“现实世界”数据集由于在类间样本分布倾斜已经被定性为不平衡的^[4]。这个特点在许多不同领域的数据产生中都比较常见：欺诈检测、入侵检测、医疗诊断和监测、生物信息学、文本分类、图像处理仅仅只是其中的几个例子。传统的分类算法过多的偏向多数类因而在少数类中产生了难以接受的分类率^[5]。在过去的十年里，基于集成的分类系统一直都是关注的中心，逐渐流行起来并向我们展示了它在不平衡数据类中的适用性^[6-8]。尽管每个分类器系统是结合了多个分类器的结果到一点，他们的构建模式通常是与基分类器多样性生产机制相结合的结果。

基分类器之间的多样性是最终形成一个集合的关键之一。因为某些基分类器在不同情况下会发生一些错误，通过将他们结合起来可以在整体上减少误差^[9]。最常用的多样性产生机制是齐次集合，通过不同分布的原始训练数据集来训练一个基分类器。Bagging和boosting^[10-12]是两个著名的均匀搭配方法。这些集合的方法可能会偏向一些具有具体特征的数据集，因为他们的训练只采用了一种类型的基分类器。通过采用不同基分类器来产生的分类器系统是另外一种方法来得到多样性，我们称之为异构集合。因为他们采用了一组不同的基分类器，这些方法在训练数据集时有利于学习其中不同的特征。

构成系统的另一个关键因素是基分类器的组合，这决定了将所有基分类器的结果导向最终目标的方法。我们有很多种组合的方法，比如多数投票、加权多数投票、求和、生产、最大值和最小值、模糊积分法、Dempster-Shafer融合或决策模板^[9,13,14]。

为了处理不平衡分布的数据集，我们提出了几个均匀分类器系统^[5,15-18]。此外，过采样、保守采样、通过综合生成一些实例的采样等采样技术被用来提高分类系统的分类性能^[7]。到目前为止，很少有不平衡数据集分类器的异构分类系统(比如[19,20])被提出而且那些系统往往是用几个基分类器组合起来的。

分类器系统的主要目标是实现更好的概括。然而，并非所有的组合（甚至包括通过所有基分类器创建）能够实现这一目标。其中的重点就是未分类器任务找到这些组合（一系列的基分类器）中的最优组合。所有可行的组合数目随着域中基分类器的数量呈指数增长，因此全局搜索最优组合是不切实际的而且浪费资源。启发式算法是一个可行的方法，它可以在一段合理的时间里帮助我们找到一个近似的解。其中一些已经被提出并用它们在同构和异构两方面探索集合的组合。

Margineantu和Dietterich^[21]提出了一种贪婪算法使用指向性搜索的方法来选择同构的集合（基于boosting的集合）。他们在每一步搜索指定组合的过程中加入了一个决策树基分类器。Caruana以及其他几人^[22]使用贪婪算法来寻找最优的异构组合。他们通过改变七个分类器的参数生成了2000个基分类器的实例，然后他们在每一步组合中加入一个基分类器来使其达到最优表现。这种方法的主要缺陷在于在之后的阶段没有办法取代基于先前选择的分类器。Partalas及其他几人^[23]通过使用基于当前预测性能的贪婪法提出了一种异构组合方法。他们通过使用不同参数形成不同的学习算法，创造了一个新的系统。这个方法相比于其他的方法在实验中有更好的表现，平均排名靠前。Niculescu等人^[24]通过一种贪婪算法发现了同构组合并赢得了2009年的知识发现杯橙级挑战赛的冠军。决策树之中包含的一个基分类器取决于它的性能验证数据集。对于不同的分类问题，他们采用不同的基分类器。在一个竞争的问题上，他们仅仅使用了六个最优的分类器而不是采用所有的分类器。最近，Bhatnagar等人^[25]提出了一种启发式搜索方法用来搜索一个同构组合，不仅考虑了单个分类器的精度同时也保证了那些分类器的多样性。他们创建了一种新的系统组合，通过在保持精度不变的情况下拒绝新的基分类器使得更少的基分类器的使用。所有这些研究都表明了贪婪启发式系统能够搜索到好的分类器系统。然而，贪婪式算法很容易就被困在一个局部的最优条件而且启发式更多地被用于复杂的搜索问题比如整体组合的搜索。

遗传算法（GA）也被用于寻找最优系统组合的研究当中。Kim and Oh^[26]采用了混合遗传算法（HGA）来搜索一个齐次系统的组合。他们将两个本地搜索操作整合进了他们的混合遗传算法，并且通过使用随机选择功能训练数据集的子集来训练多个接近的分类器（如基分类器）。Ekbal 和 Saha^[27]也使用遗传算法来搜索齐次系统集合。把这种方法应用于命名实体识别的数据集，相比于几种最好的基分类器和两个其他的集合方法取得了更好的性能表现。Thammasiri和Meesad[28]提出了一种基于遗传分类器集成方法。他们从3种基分类器中通过随机抽样训练数据的方法训练出了30个实例，类似于基分类器应用于同构集合的方法。为了增加整体的分类精度，他们使用了多数投票的方法。有来自UCI数据库的三个小实验（最大功能和样品数分别是30和1000）的实验结果表明遗传算法搜索的系统组合比较单个的基分类器以及其他两个系统方法都有更好的性能。注意到以上几种运用到的遗传算法仅仅被用于搜索同构系统中的最优系统组合（[28]同样同构集合也取决于基分类器的生成方式）。因此，遗传算法用于异构集合的搜索还有待探索，也就是这项工作的重点。

在本文中，我们提出了一种基于遗传算法来搜索和选择最优分类器从而生成一个优秀的异构分类器系统的方法，其搜索空间是所有可能的基分类器的组合。对于每一个组合，都使用了一个最完整训练数据10倍的交叉验证。因此,它会创建一个复杂的搜索空间来寻找最好的基分类器的组合。我们采用随机次级抽样的方法来控制不平衡类的数据集，以及采用非加权的多数投票来作为融合机制。为了解决搜索的问题，我们提出了一种遗传算法来搜索最优的基分类器组合。通过遗传算法找到的最优组合被应用于评估测试数据的有效性。因为马修斯自相关系数（MCC）^[29]提供了一个更具有代表性的方法来概括不平衡数据的分类性能，我们将这作为这一方法的关键性能指标。这样一种基于遗传算法搜索整体组合的算法我称之为GA-EoC,我们将使用几个非平衡分布的数据集来进行评估。

材料和方法

在本节的第一部分，我们定义未加权的多数投票分类器（EoC）。系统里的每一个基分类器可以向测试数据集中的类标签投出一票。获得最多票数的类将成为样本的最终类标签。这个算法的目标是将MCC分数作为一个异构分类器测量标准得到最大程度的提升。在第二部分中，我们会描述这个基于遗传算法系统在不平衡数据分类器中的相关组件。最后，我们会在最后一部分中描述数据集使用情况来评估这一方法。

集成分类器

一个二元的分类器C从来自二进制类训练样本集的特性集合D={}，中学习它的映射或决策功能，例如：

(1)

下一个任务是将训练完的分类器加入测试数据集中m个未标记的样本U={}

（2）

在这里的每个样本类标签（）都将有且仅有一个标签。

把k定义为这个系统中独立基分类器的个数并且在同一个训练数据集D中训练。为加权的多数投票分类器对于每个样本（）的输出结果可以表示为：

（3）

这个分类器系统的最终结果是由k个训练的基分类器通过未加权的多数投票产生的。

对于一个二元分类问题，总共会出现四个结果并被记录在一个2x2的列表或者矩阵中^[30]，同时不同表现形式的都可以由它计算出来（敏感性、特异性和准确性是几个最常见的特性）。我们选择马修斯相关系数(MCC)作为衡量分类的质量的标准，这可以从混淆矩阵中计算如下：

(4)

这里的TP,FP,TN,FN分别代表真值、假值以及正和负值，MCC通过量化所有四个混淆矩阵的输出结果来评估这个分类器。通常情况下，它可以提供一个更加平衡的精度评估模型^[31]，甚至在不平衡的数据集中也表现优异^[32,33]。因此，我们考虑把MCC作为我们分类器性能的评估标准。

基于遗传算法的EoC（GA-EoC）

遗传算法（GA）是一种基于自然选择的优化算法或者称它为“适者生存”。遗传算法相比于众多传统的优化方法，其中的主要区别是遗传算法更多的是在宏观上的处理而不是单方面的处理。由于这个多点搜索特性，遗传算法可以很容易的被实现。此外，相比于其他的启发式算法，遗传算法不太容易陷入局部的最优的情况。交叉和变异通过在种群中产生重要的随机性来帮助算法从局部最优解中逃脱出来。这些优势使得遗传算法更加适合大型和相对复杂的优化问题。

在我们的设计中，我们从怀卡托环境数据分析（WEKA）数据挖掘软件组件中选择了20个基分类器（在表1中列出）来建立这个系统组合。

表1 GA-EoC中用到的基分类器

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[150697]，资料为PDF文档或Word文档，PDF文档可免费转换为Word