2017年12月8日

博客

特征选择的进化算法:第2部分

Ingo Mierswa

特征选择是机器学习中一个非常重要的技术。我们需要能够解决它来制作模型。但这不是一个简单的技巧。特征选择需要启发式过程来找到最优的机器学习子集。

在以前的文章我讨论了蛮力算法以及前向选择和后向消除，它们都不是很适合。还有其他选择吗?我们可以使用一种最常见的多模态适应度景观优化算法;进化算法。

进化算法是如何工作的?

进化算法是模仿自然进化思想的一种通用优化技术。有三个基本概念在起作用。首先，父母创造后代(交叉)．其次，个体有可能经历微小的变化(突变)．第三，身体健康的人生存的可能性更高(选择)．

我们现在知道我们可以用位向量表示可能的属性子集。我们可以表示一个共有10个属性的数据集的所有属性的选择，例如(1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 10 0 0 0 0 0 0 0 0 0 0 0)。

进化算法的第一步是创建一个个体种群。这个种群会随着时间的推移而进化。我们称之为初始化进化算法的阶段。起始群体中的个体是随机生成的。每个个体都是一个像上面描述的位向量。我们通过为每个可用属性抛硬币来创造个体。根据结果，我们可以将属性包含在这个个体中，也可以不包含。对于起始种群的大小没有固定的规则。然而，如果我们想进行交叉，我们至少应该有2个个体。一个好的经验法则是使用属性数量的5%到30%作为总体大小。

在创建初始填充之后，我们需要继续执行一系列步骤。直到我们达到一个停止标准。下图描述了实现这种循环的一种可能的方法。请注意，进化算法的实现有不同的方法。有些人喜欢只对交叉执行选择。有的则先选择新一代，然后进行跨界。有些人只使后代变异，但有些人也使父母变异。根据我的经验，算法的具体细节对它们的表现几乎没有影响，所以我将在下面只解释一个变体。

进化算法

第一步

第一步是从我们的人群中挑选父母交叉．我更喜欢从我的人群中随机选择父母，直到我在一个交叉中使用所有父母。由于幸存者的选择直接发生在之前(见下文)，我们不需要使用适合度来选择父母。选择步骤已经确保我们在下一代中只选择更健康的父母。有许多变体可以实现这一点。

也有许多变体的实际交叉。上图中的变体为两个父位向量在同一位置使用了一个单独的分裂点。我们通过使用第一个父节点的前面部分和第二个父节点的后面部分来创建子节点，反之亦然。跨界可以在健身领域带来巨大的飞跃。这些跳跃使得进化算法能够更好地处理多模态适应度景观。他们只是不太可能陷入局部极值。

第二步

下一步是执行突变．突变意味着我们将一个位从0翻转到1，或者反过来。很多人只变异后代跨界，但我更喜欢也变异父母。请注意，有时候根本就没有突变。翻转单个属性选择的可能性为1 / m如果米属性的数量。这意味着在突变中，我们平均为每个个体翻转一个属性。变异导致了适应度的微小变化。它可能是有用的爬向附近的极端景观。最后，我们可以决定是保留原始的个体还是只保留突变的个体。我经常两者都有。

如果我们决定保留原始的和突变的个体，那么我们的种群规模现在是原来的4倍。我们首先从每一对父母中创造出两个新的后代，使种群规模翻了一番。然后我们为每个个体创造一个突变，使种群规模再次翻倍。下一步，我们应该把人口规模再次降低到一个更小的数字。当我们这样做的时候，我们应该选择更健康的个体来生存。

第三步

但首先我们要评估我们现有种群中的所有个体。我们称之为进化算法的评估阶段。例如，我们可以使用在这个特征子集上训练的交叉验证模型的准确性。我们将这些准确性与个体存储在一起，这样我们就可以在下一步中执行适合度驱动的选择。

第四步

迭代过程的最后一步是选择．这一步贯彻了“优胜劣汰”的理念。这意味着个体，即属性子集，导致具有更高精度的模型应该有更高的生存可能性。幸存者为下一代的新属性集建立了基础。执行选择的方法有很多种。事实上，在我的下一篇博客文章中，我们将看到我们有几个有趣的选择，以更好的方式解决特征选择问题。但现在，我们使用一种最广泛使用的选择方案，即锦标赛选择．

为了比赛的选择，我们让一小群人互相竞争。群体中最适者生存并繁衍到下一代。我们使用抽样和替换来创建我们的比赛组。这意味着个人也可以被多次选择。我们继续让个体去核，直到下一代的种群再次达到所需的大小。

群体规模对弱小个体的生存几率有一定影响。如果比赛的规模与种群规模相等，那么只有最适合的个体才能生存。但由于比赛规模只有2人，即使是实力较弱的选手也有机会对抗另一个实力较弱的选手。我们可以适应所谓的选择压力通过为比赛规模选择不同的值。但要小心:太大，算法可能会变得太贪婪。这增加了次优结果的可能性。但如果比赛规模太小，优化就会持续更长时间。

循环结束时，我们遇到停止准则．这可以是最大代数，也可以是一段时间内没有任何改进的事实。或者优化达到时间限制。但不管原因是什么，到目前为止，我们提供了最好的个人。

我们如何轻松地使用进化特征选择?

让我们讨论一下如何在RapidMiner中为特征选择设置这些不同的启发式。

已经有大量的论文表明进化特征选择是有效的。在这篇博文中，我们想要说明每种不同方法的结果都是不同的。我们将使用单个数据集。请记住，这些方法是启发式的，对于其他数据集，结果可能完全不同，但在实践中，我们经常会看到类似于下面讨论的模式。

我们将分析的数据集是Sonar数据。它有208个例子(行，观察，案例……)，每一个都是水中物体的频谱。总的来说，我们有60个不同的频段，它们构成了我们数据集的属性。我们的目标是从一个物体的频谱中检测出这个物体是岩石还是水雷。下图显示了并行图中的数据可视化。该图中的每一行表示数据集中的一个示例。颜色指定对应的对象是岩石(蓝色)还是矿山(红色)。

进化特征选择

正如我们所看到的，这是一项相当艰巨的任务，但在频谱的某些区域，这两个类别的差异更大一些。这些区域在下面的偏差图中更容易看到。这个图表只显示了两个类的每个属性的平均值。透明区域表示每个类的属性的标准偏差。

标准差

在频谱中有4个不同的区域，这两类人的差异最大。这些是属性11、属性20、属性35和属性45周围的区域。我们在第一张图中看到，一个单独的区域就足以找到一个好的模型。但这些方面的一些属性的组合应该有助于克服噪音。

过程1:Naïve贝叶斯在完整数据上的交叉验证(基准)

在我们进行任何特征选择之前，让我们首先通过评估我们的模型在完整数据集上的工作情况来建立一个基准。我们将使用朴素贝叶斯作为实验的模型类型。我们将用同样的5倍交叉验证来评估所有模型。这意味着在我们的实验中，不同的数据分割没有影响。我们可以在RapidMiner中通过为交叉验证操作符定义一个局部随机种子来做到这一点。

如前所述，这个过程可以在这篇博文的末尾找到。我们实现67.83%精度的声纳数据集与Naïve贝叶斯。当然，我们希望特征选择能进一步提高准确率。不过，我们在这里不会尝试强力方法。对于我们数据集的60个属性(频带)，我们最终会得到260- 1 = 1,152,921,504,606,849,999个组合。

过程2:正向选择

我们进行的下一个实验是正向选择法。我们使用与上面相同的5倍交叉验证来评估每个属性子集的性能。优化在4轮之后就停止了，并交付了属性12、15、17和18。这个子集的准确性为77.43%．这比没有任何特性选择的基准测试要高得多。但另一件事值得注意。特征选择只从频谱的4个相关区域中选择了左边两个区域的属性。右边的两个区域没有进入结果。前向选择在遇到局部极值之前就停止了。

过程3:逆向淘汰

我们现在将尝试反向消去作为一种替代方法，因为它可能会更好地找到一个考虑到频谱的所有四个重要区域的好模型。不幸的是，事实并非如此。该算法只从数据集中的60个属性中删除了8个。所有其他噪声属性在反向消除运行到第一个局部极值之前保持在数据集中。精度较低的只有73.12%虽然它仍然比使用完整的数据要好，但不应该是一个结果。至少我们可以看到，摆脱这8个属性已经有了回报。但是数据中仍然有太多的噪声，掩盖了实际的信号。

过程4:进化特征选择

最后，让我们看看特征选择的进化方法。我们使用20个种群大小，并在最多30代后停止优化。优化比前向选择或后向淘汰运行的时间稍长。但准确率明显更高:82.72%这是我们取得的最好的结果。同样有趣的是算法选择的11个属性的子集:

这个子集涵盖了频谱的所有四个重要区域。我们有属性11、属性20、属性35和属性45。这就是为什么这种特征选择优于其他方法的原因。进化算法只是没有进入局部极值，过早地停止了。它一直这样做，直到找到一个更好的结果。

关键

忘掉正向选择和逆向淘汰吧。进化特征选择应该是用来解决这个问题的技术。在我的下一篇博客文章中，我将讨论我们如何获得更好的结果和更多的见解，而不仅仅是优化最准确的模型。相反，我们同时也将优化最简单的模型。这将是下一篇博文的主题。

相关资源乐鱼体育安装