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

一种用于特征选择和实例选择的微分进化方法

摘要：由于存储硬件和数据收集技术的不断改进，越来越多的数据正在被收集。数据的流入非常多，数据挖掘技术无法跟上。 收集的数据通常具有冗余或不相关的限制分类性能的特征/实例。 特征选择和实例选择是通过消除无用数据来帮助减少此问题的过程。 本文利用Dierential Evolution开发了一套算法来实现特征选择，实例选择以及组合特征和实例选择。 将数据的减少，分类精度和训练时间与原始数据和现有算法进行比较。 对十个不同难度数据集进行的实验表明，新开发的算法可以成功地减小数据的大小，并在大多数情况下保持或提高分类性能。 另外，计算时间也大大减少。 这项工作是第一次有系统地研究关于分类中的特征和/或实例选择的一系列算法，并且结果显示实例选择是比要素选择更难解决的任务，但是通过有效的方法，它可以显着地减少数据的大小，并提供许多好处。

关键词：微积分、演化特征选择、实例选择、分类

介绍

随着硬件技术的提高，越来越多的数据以机器学习的速度收集，而数据挖掘技术无法处理。 通常收集的数据包含冗余或不相关的特征和实例[7, 9, 14, 22, 25]，这可能会减慢和阻碍许多任务（如分类，降低学习成绩，和/或学习复杂模型）的学习过程。 通常需要预处理步骤来去除一些不相关或甚至有噪声的数据，这可以通过用于仅选择信息特征的小子集的特征选择（FS），用于仅选择小子集的实例选择（IS）来实现代表性示例/实例或FS和IS用于删除无用或冗余功能和实例[13, 17]。

由于两个主要原因而导致问题的挑战 首先是大型搜索空间，它随着特征和实例的总数呈指数增长。 第二个是几乎总是存在特征之间的相互作用，这导致了一个复杂的搜索空间和许多局部最优解，并且通常需要一个好的tness函数来指导搜索以找到一个好的解决方案。 在FS上有大量的作品，但在IS，FS和IS上没有太多的工作[13]。 不寻常的搜索技术已被用于FS，但现有的算法仍然从局部最优停滞问题中获益。 演化计算技术能够搜索大尺寸的解决方案。 以前的工作表明，各种演化计算技术，如微积分进化（DE）[15]，粒子群优化[1, 11, 19]，遗传

算法[18, 26] 和别的 [2, 8]，比传统的FS和IS方法获得更好的性能[20]。 这项研究将利用DE方法。 DE是一种简单而有效的方法，它已被用于解决各种复杂问题，尤其是那些搜索空间较大的问题[24]。 最近的作品[3, 21]也显示出它在解决FS问题上的能力，但是它在IS上的潜力还没有得到充分调查。

基于评估标准或tness函数，特征和/或IS方法可以分组为包装方法和过滤方法[23]，其中包装器涉及在每次评估中训练学习/分类算法，以使用准确性来展示候选解决方案的好坏，并且过滤器独立于任何学习/分类算法。 由于学习算法和候选解决方案之间的直接联系，包装通常可以获得比过滤更好的准确性，但是在计算上是昂贵的。 过滤器通常速度非常快，但可能无法达到与包装一样的高精度[7].

DE最近才被用于封装FS [4, 5, 12, 21]。 与DE在其他领域的普及和有希望的表现相比[6]，DE的潜力还没有得到充分调查。 虽然大多数机器学习任务都需要FS和/或IS，但分类是应用程序数量最多的区域，这可能是调查的一个很好的起点。

目标：这项研究的目的是调查使用DE进行数据预处理，其中包括仅FS，仅IS和FS和IS在一起。 预计所提出的方法将减小数据的大小并增加或至少不显着地降低分类准确性。 更具体地说，总体目标分解为以下目标：

• 1. 开发一种新的基于DE的FS算法，用于选择特征子集以降低维度并保持甚至提高分类性能，
  2. 开发一种新的基于DE的IS算法，用于选择代表性实例的一小部分子集以减小数据的大小而不显着降低分类准确性，
  3. 开发一种新的基于DE的FS和IS算法，以同时实现FS和IS，
  4. 研究与现有技术相比新算法的性能提高。

提议的算法

在本节中，我们将调查DE对FS，IS以及FS和IS的使用情况。 由于特征和/或IS是二元任务，即选择或不选择，但DE最初是作为连续搜索技术提出的，所以需要二元DE算法。 对于大多数使用分类精度评估tness（即包装方法）的现有方法，我们将开发一系列基于类间和类内（IIC）度量的滤波算法来评估每个候选解。

二元不变性演化

在候选解决方案中，候选解决方案由矢量来表示，在每一代中对它们执行各种运算符。 运算符的范围可以从数学函数（如加法，减法或乘法）到遗传算子（如交叉和变异）。 文献中有不同版本的DE [16]。其中最有前途的一个是DE/best/1，用于这项工作。DE/best/1迭代就是这样定义的

其中i表示总体中的第i个解，G和G 1表示当前和下一代。 F是控制粒子运动大小的比例因子，xr1，G和xr2，G是其他随机候选解

从群体中选择x最好，当前的全球最佳解决方案，这是DE/best/1的一个主要特征，将其与其他实现（如DE / rand / 1）区分开来。 从等式中可以看出，当前全球最佳解决方案是所有新解决方案的主要因素或基础。 在DE / rand / 1中，随机选择三种解决方案来生成新的解决方案。 候选解决方案的初始种群是随机生成的。 在每一代中，对于群体的每个解决方案i，利用上面的等式生成试验性的新候选解vi,G 1。 如果tness vi,G 1优于xi,G，则xi,G 1在G 1代更新为vi,G，即改进在旧的解决方案。 否则，xi,G 1与xi,G相同。

由于DE和PSO之间的相似性，以前有关二元PSO的工作[10]可以在这里使用。 必须从候选解决方案的连续矢量表示转换为选择问题所需的二进制解决方案。 该转换由下式给出：

其中输出是第i个解的第d个比特，rand（）是0和1之间的随机数，并且xi,d是候选的第i个矢量的第d个值

解决方案，通过sigmoid函数进行归一化。 输出中的值决定了功能或实例的选择。

适合函数

适合函数是所提算法中的关键组件之一，它基于IIC度量。IIC度量可以分解为两个部分，即类间距离和类内传播。

内部类距离：类间距离是数据集中类的可分性的度量。距离越大，分类越远。 因此，距离越远意味着类别之间的区别越大，类别之间的重叠越少，预计分类效果越好。为了实现分类目标，我们建议基于一组具有代表性的实例为每个类构建一个原型，它是一个平均实例或质心。 在这里不使用所有实例的原因是为了避免异常值和长计算成本。

算法1显示了如何计算类间距离。对于每个类，构造一个平均实例或质心。 均值实例是一个特征向量，每个值都是属于该类的所有实例的平均值。代表性

的一组实例是最接近构造的均值实例的实例，它被发现代表该类。每个代表集合的大小为属于该类别的实例总数的10％加1，即平均情况。代表集用于计算类之间的欧几里德距离，这可以从算法1中的第1-5行。然后，找到代表集之间的欧几里德距离。两个类别之间的平均距离定义为一个代表性集合中每个实例与另一个代表性集合中每个实例的平均距离。由于属于每个类别的实例的不同数量，平均值在这里被采用。在第10-17行中，两班之间的平均距离是在每班之间计算的。然后，将每两个类别之间的平均值的平均值用作所有类别之间的距离，如第20行所示。

以下等式提供了这种计算的数学形式。

其中C是所有代表集合的集合，Ca，Cb是任意两个不同代表集合，并且i，j是

个体实例。

内部传播：组内传播是衡量一个特定阶层是如何分布的。 一个班级的进一步传播，更有可能与其他班级重叠，从而提供更有凝聚力的班级表达。 因此较小的价差是优选的。 类的扩展是由其特征的扩展给出的，特别是通过每个类中的实例的所有特征值。 这允许更简单的计算，但由于加法的关联属性，不会改变给定数据集的总传播。

特定特征的扩展由该特征的每个类的一组值的标准偏差的总和给出。 该特征集合的扩展由每个特征的扩展总和给出。

其中Fl是一组特征，c是属于C类的一个实例，sigma;F，C是表示c类中的特征f的值的标准偏差。

合适函数： 为了实现良好的分类性能，理想情况下，应该尽量减少组内距离，并尽量扩大组间距离。 因此，一个（最小化）合适函数形成，并由方程5

其中F是特征的数量，而alpha;是一个系数。常数alpha;将F添加到分子的分布中以控制分布和距离之间的重量比。一个较小的常数会给分布带来更多的权重，而一个更大的常数会给这个距离带来更多的权重。 这也意味着可以控制在FS中选择的特征的数量，因为特征的数量直接影响扩展和距离，即类内扩展需要更少的选择特征，而类间距离需要更多特征。 因此，通过调整传播和距离的权重，可以调整特征的数量。

新算法

我们将调查使用DE，FS，IS，以及FS和IS在一起。由于适合函数Eq.5最终显示了不同类别可以分离的程度，它们分别用于所有三种算法，分别为FS，IS，FS和IS形成IIC-FS，IIC-IS和IIC-FIS。

这三种算法的目标是相同的，即最小化tness值。他们都遵循基本的DE过程。 它们之间的关键中断是表示，因为候选解决方案是不同的，即分别是IIC-FS，IIC-IS和IIC-FIS的特征子集，实例子集和具有选定特征的实例子集。 在IIC-FS中，每个人在DE中的表示是具有m个特征的数据集的m维布尔向量，其中每个维度确定是否选择了相应的特征。 1表示该功能被选中，否则为0。 在IIC-IS中，表示是具有n个实例的数据集的n维布尔向量，其中每个维度确定是否选择相应的实例。 在IIC-FIS中，表示是一个（n m）维布尔向量，其中每个维度确定是否选择相应的特征或实例。 在IIC-FS中，由于实例不改变，每个特征都有一个与之相关的特定的类内扩散值，这个值也不会改变。 这些值只需要计算一次。 训练时间得到了改善，因为每个功能的传播都存储在内存中，并且只需读取每个tness评估，而不是在每次需要时重新计算每个值。 因此算法的第一部分2 仅在开始时执行一次。 进一步的评估只需要执行第二部分。 类间距离也不能达到，因为改变实例的尺寸（特征）也会改变它们的相对距离。 因此算法1 对FS的每一个评价都是完全执行的。 在IIC-IS和IIC-FIS中，由于实例的变化，因此数据的传播距离和距离都算法的计算都是针对每个tness评估完成的。

另外，由于DE从未用于IS，FS和IS，我们研究了两种基于包装的方法，使用KNN作为分类算法来评估分类性能，作为仅用于IS（KNN-FS）的合适函数，以及用于FS和IS（KNN-FIS）。 KNN-FS和KNN-FIS在一定程度上也是新的。

实验设计

所提出的算法针对来自表1中所示的UCI机器学习库的10个数据集运行1。 选择这些数据集以表示一系列特征和实例计数，以及被广泛使用的数据集，以便可以将新算法与现有算法进行比较。 数据在加载时被标准化，确保距离和标准偏差度量对于所有要素具有相同的比例。

表1.实验数据集

对于每个选择过程，对每个数据集进行30次运行。 DE有80个候选解决方案的人口，运行了100代。 由于不能很容易地确定最佳解决方案，并且分类率不是培训过程的一部分，因此不存在提早停止标准。 数据每10次运行一次，每个数据集总共进行3次不等分。 分裂是随机完成的，每个实例有70％的机会被用于训练，30％的机会被用于测试。

在ICC-FS，IIC-IS和IIC-FIS中，在alpha;的实验之前进行了搜索。 表中的alpha;的系数值1 被发现与KNNFS具有相似数量的特征并被用于实验。IIC-FIS有两个特定的实现。 标有“200”的第一个以200运行DE的候选解决方案而不是80.这是为了适应更大的搜索空间，因为维度大小是特征和实例数量的总和。 第二个标记为“ICC-Half”的标记在使用IIC-FS来减少特征后使用修改的KNN进行分类。 这个修改过的KNN只使用了一半的实例。 对于每个类，质心或均值实例是从训练集中该类的每个实例计算出来的。 然后，在KNN中使用该类的一半实例（离质心最近的一半）进行分类。 尽管在训练过程中只选择了特征，但这种修改的KNN选择了实例，将其置于FS和IS之下。 在KNN-FS，KNN-IS和KNN-FIS中，训练集上的10倍验证的平均分类准确性用作tness值，其中使用10倍验证来确保没有FS偏差涉及和测试集是完全不见的FS方法。

经过DE生成后，评估具有最好质量的解决方案在测试集上的分类准确性，其中KNN（K = 5）用作分类器。 然后使用Mann？-Whitney U测试的非参数测试来比较IIC测量选择的特

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

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