我们对生物学（或生命科学）的理解随着时间的推移有了巨大的增长，它已成为许多工程师解决具有挑战性的问题和产生发明灵感的重要来源。以日本的高速列车“新干线”为例。它是世界上最快的火车之一，时速超过300公里。在设计过程中，工程师们遇到了一个巨大的困难：列车前方的空气位移产生的噪音非常大，可能会损坏一些隧道的结构。他们以意想不到的方式找到了解决这个问题的办法：翠鸟。这种鸟细长的喙使其在潜水捕食时不会溅起水花。因此，通过按照鸟的形象重新设计火车，工程师不仅解决了最初的问题，而且将火车的功耗降低了15%，速度提高了10%。图1-日本高铁、新干线，来源生物知识也可以成为机器学习的灵感来源。内容本文关注的一个例子是进化决策树。这些分类器使用进化算法来构建更健壮和性能更好的决策树。进化算法依赖于受生物进化启发的机制。什么是决策树？如何基于进化算法构建决策树？与其他分类器相比，进化决策树的表现如何？数据集为了说明本文中提出的概念，我将使用航空公司乘客满意度调查结果的数据集。可以在此处找到有关此数据集的更多信息。其目的是预测客户对航空公司服务的满意度。此类研究对公司的决策至关重要。它不仅可以让提供商品或服务的企业知道自己的产品哪里需要改进，还可以让企业知道自己需要改进的程度和迫切程度。事不宜迟，让我们先回顾一下决策树的基础知识。.1.什么是决策树？决策树是一种分类器，其分类过程可以用树图表示。在训练过程中，模型根据数据的特征推断出简单的决策规则，并对数据点进行相应的分类。下图显示了决策树的示例。这是使用ScikitLearn决策树模块对航空公司乘客满意度调查结果数据集进行培训的结果。图2-决策树示例决策树表明在线办理登机手续是商务旅行中乘客满意度的重要因素，并且当在线办理登机手续简单高效时，乘客更有可能感到满意。另外，机舱内wifi的信号质量也很重要。由于许多优点，决策树被广泛用于分类任务：它的推理过程类似于人类，易于理解和解释；它可以处理数值数据和分类数据；它可以通过层次分解更好地利用变量。大多数派生决策树的算法都使用自上而下的递归划分“贪心”策略。源集表示树的根节点。源集按照一定的规则划分为子集（子节点）。每次对划分后的子集重复这个划分过程，直到某个节点下的子集中目标变量的值全部相同，或者划分过程不再增加预测结果的值。用于确定在节点和分区中生成测试的最佳方式的定量指标是特定于算法的。最常见的指标是信息（或熵）和基尼杂质。他们测量杂质的程度。当节点的所有样本属于同一类别时，该类别指标的值为0；当节点的样本类别均匀分布时（即节点取某类别的概率为常数），该类指标的值取最大值。有关这方面的更多信息，请参阅本文。但是，这类指标有两个主要缺点：1.可能会得到次优解；2.可能会生成过于复杂的决策树，使得在训练数据中的泛化效果不好，导致过拟合。有几种方法可以克服这些问题：剪枝：首先构建一棵完整的决策树，即每个叶子中的所有实例都属于同一个类。然后删除“不重要”的节点或子树以减小树的大小。组合树：构建不同的树，通过特定的规则（通常是投票计数）选择最终的分类结果。值得注意的是，这会导致决策树的可解释性降低。因此，有必要探索其他生成树模型的方法。近来，进化算法（EvolutionaryAlgorithms，EA）获得了很多关注。进化算法在所有可能的解决方案中执行强大的全局搜索，而不仅仅是局部搜索。因此，进化算法比贪婪策略更有可能更好地处理属性交互。进化算法的具体工作方法如下。2.如何使用进化算法构建决策树？进化算法是一种搜索启发式算法，其机制来源于自然界中的生物进化过程。在这种范式中，种群中的每个“个体”都代表给定问题的候选解决方案。每个个体的适应度代表解决方案的质量。以这种方式，随机初始化的第一种群向搜索空间中更好的区域演化。在每一代中，选择过程使得适应度较高的个体（原文为“lowerfitness”，疑似错误）有较高的繁殖概率。此外，还对种群执行特定的遗传启发操作，例如重组，其中来自两个个体的信息在传递给他们的后代之前混合，以及突变，其中对个体进行小的随机变化。迭代此过程，直到达到某个终止条件。然后选择最合适的个人作为答案。基于进化算法的决策树是通用方法的一个有趣的替代方法，因为：随机搜索方法可以有效地避免可能通过自上而下的递归划分“贪心”策略找到的局部最优解。决策树的解释与整体方法相反。它不仅可以优化单个指标，还可以整合不同的健身目标。2.1群体初始化在进化决策树中，一个个体代表一棵决策树。初始种群由随机生成的树组成。一棵随机树的生成步骤如下：在根节点和两个子节点之后，算法以预设的概率p决定每个子节点是继续划分还是成为终点。如果继续划分子节点，算法会随机选择一些属性和阈值作为划分的标准。如果子节点成为端点（叶节点），它会被随机分配一个类标签。2.2适应度分类器旨在在输入新的未标记数据时实现最高的预测准确性。此外，决策树分类器还需要控制树的最终大小。因为树的尺寸小，会导致欠拟合，树的结构太复杂，会导致过拟合。因此，在定义适应度时需要在这两项之间取得平衡：fitness=α1f1+α2f2其中：f1是在训练集上的准确率；f2为个体的大小（树的深度）设置惩罚项；α1和α2是要指定的参数。2.3.选择过程有多种方法可以选择用于创建下一代树的父代。最常见的有以下几种：基于适应度的比例选择，或轮盘式选择：按适应度对种群进行排序，然后依次为每个个体分配一个选择概率。淘汰系统选择：首先从种群中随机选择一些个体，然后从选择的集合中选择适应度最高的个体作为父母。精英选择：直接将适应度最高的个体用于下一代。这种方法保留了每一代人中最成功的人。2.4重组获得重组后代的过程需要将亲本配对。首先，选择两个人作为父母。然后在两棵树中各随机选择一个节点。用第二棵树中选中的子树替换第一棵树中选中的子树，得到后代。图3-重组2.5突变突变是指在群体中的个体子集中进行的小的随机选择。变异是遗传多样性的保证，这意味着遗传算法可以搜索更大的范围。对于决策树，可以通过随机改变属性或细分随机选择的节点来实现变异。图4-变异2.6终止条件如果最佳个体的适应度在给定的世代数内没有增加，则可以认为算法已经收敛。该代数是一个预设参数，以便在收敛速度较慢时节省计算时间。3.与其他分类器相比，进化决策树的表现如何？进化决策树看起来很棒，但与传统的机器学习算法相比，它的表现如何？3.1一个简单的实验为了评估分类器的效率，我构建了一个决策树，并在航空公司乘客满意度调查结果的数据集上对其进行了训练。目标是确定导致更高乘客满意度的因素。这需要一个简单且抗噪的模型来解释导致乘客满意（或不满意）的途径。图片来自本站，摄影师的数据集非常庞大，包括超过10万条路线。包含有关乘客及其行程的事实信息：乘客的性别、年龄、客户类型（旅行与否）、旅行类型（个人或商务旅行）、航班等级（商务、生态、极端生态）和飞行距离。它还包括乘客对以下服务的满意度：机舱Wi-Fi、出发/到达时间（适当）、在线预订（方便）、登机口位置、餐饮、在线值机、座位舒适度、机上娱乐、登机服务、座位腿部空间、行李服务、值机服务、客舱服务、清洁。数据标签为旅客满意度，包括“满意”、“中立”和“不满意”。方法我使用的计算步骤可以简单概括如下：1.数据预处理：将分类变量转化为指标变量。数据集随机分为训练集和测试集。2.模型和测试：训练每个模型以考虑训练子集上的条件和验证子集上的测量。3.比较每个模型的性能。我选择将进化决策树(EDT)方法与简单的基于树、基于决策树(DT)和基于随机森林(RF)的模型进行比较。限制树的深度小于（等于？）3。我还将EDT的人口规模和RF的评估者数量设置为10，以便在合理的计算时间内以一致的方式比较它们。结果如下：图5-“满意”和“中立或不满意”乘客数表1-DT模型分类报告表2-RF模型分类报告表3-EDT模型分类报告图6-3该参数设置下模型的ROC曲线和曲线下面积，EDT的性能与其他两种机器学习算法非常接近。但是，EDT的优势在于它可以提供一个决策树，可以呈现多个决策树聚合的站点（相对于RF模型），并且是健壮的（相对于简单的DT模型），因为它是表现最好的树在一堆。在训练过程中，最大深度设置为2，得到的在EDT种群中表现最好的决策树可以表示为如下形式：图7()-EDT3.2A中最佳决策树示意图EDF方法的更一般描述与其他机器学习算法相比，上述实验肯定不足以评估进化决策树的性能和可靠性。因为只使用了一个数据集，并没有考虑所有的可能性，比如标签的类别数量、特征数量和观察数量的影响等。在[2]中，作者比较了EDT方法与其他使用真实UCI数据集的机器学习方法。本文的研究结果如下。关于数据集下表简要描述了所使用的数据集：表4-数据集的属性如您所见，数据集在观测数、要素数和类别数方面差异很大。最困难的数据集肯定是第一个，因为它有很多类和很少的观察。方法以下是作者用来评估EDT模型与更多“经典”机器学习算法相比性能的方法的关键信息：EDT模型已使用以下超参数进行训练：时期数为500，人口规模为400，重组/变异概率分别为0.6/0.4，选择方式为随机均匀选优。使用5x2交叉验证来衡量模型性能。结果表5-模型准确性取决于使用的数据集基于树的算法几乎总是优于其他机器学习算法。可以解释为决策树本身能够更好地选择最重要的特征。此外，基于规则的模型更适合某些数据集，尤其是当难以对对象和特征之间的关系进行建模时。在鲍鱼数据集上的结果都很差：因为有28个类，观察的数量非常少（只有210个）。然而，EDT模型以最高的准确度脱颖而出。这表明它可以有效地处理困难的数据集并避免过度拟合。值得注意的是，EDT模型使用默认参数。调整参数可以带来更好的性能。参考文献[1]R.Barros等人，决策树归纳进化算法调查，2011[2]D.Jankowski等人，决策树归纳进化算法，2016[3]S.Cha，构建二元决策使用遗传算法的树，2008[4]D.Carvalho等人，用于数据挖掘的混合决策树/遗传算法方法，2003[5]维基百科，旅行商问题[6]维基百科，遗传算法
