译者：AI研习社（精神小高）

双语原文链接：Evolutionary Decision Trees: When Machine Learning draws its Inspiration from Biology

---

随着时间的推移，我们对生物学（或生命科学）的了解大大增加，它已成为许多工程师解决挑战性问题并产生发明创造的的重要灵感来源。

以日本的高速列车“新干线”为例，它是世界上最快的火车之一，时速超过300公里/小时。 在设计过程中，工程师遇到了巨大的难题：火车前部空气的位移所产生的噪音，其幅度大到可能破坏某些隧道的结构。

他们以一个出乎意料的方式找到了这个问题的解法：翠鸟。这种鸟的喙部细长，使之在潜入水中捕食时能够少溅水花。

因此，通过模仿这种鸟的形象重新设计列车，工程师不仅解决了最初的问题，而且还将列车的耗电量减少了15％，速度提高了10％。

 

 

图1-日本的高速铁路，新干线，来源

生物学知识也可以成为机器学习中灵感的来源。

内容

本文重点关注的一个例子是进化决策树。

这类分类器使用进化算法来构建鲁棒性更强，性能更好的决策树。进化算法依赖于生物进化启发的机制。

• 决策树是什么？

• 如何根据进化算法搭建决策树？

• 与其它分类器相比，进化决策树的表现如何？

数据集

为了说明本文中提及的概念，我将使用航空公司乘客满意度的调查结果数据集。有关此数据集的更多信息，请参见此处。

其目的是预测顾客对航空公司的服务的满意度。这样的研究对公司的决策至关重要。它不仅可以使提供商品或服务的公司知晓其产品在哪些方面需要改进，而且可以使公司知道应该改进到什么程度以及改进的紧要程度

事不宜迟，让我们从复习关于决策树的基础知识开始吧。

1. 什么是决策树？

决策树是一种分类器，其分类流程可表示为树形图。模型在训练过程中根据数据的特征推断出简单的决策规则，并依此对数据点进行分类。

下图展示了一个决策树的例子。这是使用Scikit Learn决策树模块在航空公司乘客满意度的调查结果数据集上进行训练的结果。

图2-决策树示例

决策树表明网上值机服务是商务旅行中乘客满意度的重要因素，乘客在能简单高效地在网上办理登机手续时更可能感到满意。另外，舱内wifi的信号质量也十分重要。

决策树由于具有许多优点而被广泛用于分类任务：

• 它的推理过程与人类相似，易于理解和解释；

• 它能处理数值数据和分类数据；

• 它通过分层分解能更充分地利用变量。

大多数用于推导决策树的算法都使用自上而下的递归划分“贪心”策略。 

源集（source set）代表了树的根节点。源集是根据特定规则划分为各个子集（子节点）的。在每次划分出的子集上重复该划分过程，直到某个节点下的子集中的目标变量的值全部相同，或者划分过程不再使预测结果的值增加。

用于在节点和划分中确定生成测试的最佳方法的量化指标是因算法而异的。最常见的指标是信息量（或熵）和基尼杂质量。它们度量的是杂质度，当节点的所有样本属于同一类别时，这类指标的值为0；当节点的样本的类别呈均一分布（即，该节点取到某一类别的概率为常数）时，这类指标的值取到最大值。更多相关信息参见本文。

但是，此类指标有两个主要缺点：

1.可能取到次优解；

2.可能生成过于复杂的决策树，以至于在训练数据中泛化效果不好，导致过拟合。

目前已有几种方法可用于克服这些问题：

• 剪枝：首先，构建一颗完整的决策树，即每片叶子中的所有实例都属于同一类。然后删除“不重要”的节点或子树，以减小树的大小。

• 组合树：构建不同的树，并通过特定规则（一般是投票计数）选择最终的分类结果。值得注意的是，这会导致决策树的可解释性降低。

因此，有必要探索生成树模型的其它方法。最近，进化算法（Evolutionary Algorithms, EA）获得了极大的关注。进化算法在所有可能的解法中进行强大的全局搜索，而不仅仅是本地搜索。结果，与贪心策略相比，进化算法更可能把属性交互处理得更好。

进化算法的具体工作方式见下。  

2. 怎样用进化算法构造决策树？

进化算法是搜索启发式方法，其机理源自自然中的生物进化过程。

在这个范式中，群体中的每个“个体”代表给定问题的一种候选解法。每个个体的适合度代表这种解法的质量。这样，随机初始化的第一个群体会朝着搜索空间中更好的区域进化。在每一代中，选择过程使得适合度较高（原文为“适合度较低”，疑有误）的个体具有较高的繁殖概率。

此外，还会对群体进行特定的由遗传学启发的操作，例如重组，两个个体的信息在混合后才会传给他们的后代；以及突变，对个体进行微小的随机改变。对这一过程进行迭代，直到达到某一终止条件。然后选择最适个体为答案。

基于进化算法的决策树是通用方法的一种有意思的替代品，因为：

• 随机搜索法能有效避免自上而下的递归划分“贪心”策略可能找到的局部最优解。

• 对决策树的解释与整体法相反。

• 不仅仅是优化单一指标，它可以将不同的目标集成在适合度中。

2.1 群体的初始化

在进化决策树中，一个个体代表的是一棵决策树。初始群体由随机生成的树组成。

随机树可以按以下步骤生成：

在根节点和两个子节点后，算法以预设概率p决定每个子节点是否继续划分或成为终点。

• 如果继续划分该子节点，算法会随机选择一些性质和阈值作为划分的标准。

• 如果该子节点成为终点（叶节点），就给它随机分配一个类别标签。

2.2 适合度

分类器的目标是在输入未标记的新数据时能获得最高预测准确度。此外，决策树分类器还需要控制树的最终尺寸。因为树的尺寸小会导致欠拟合，而树的结构太复杂会导致过拟合。

因此，在定义适合度时需要在这两项之间取得平衡：

适合度 = α1 f1 + α2 f2

其中：

• f1是在训练集上的准确度；

• f2是对个体的尺寸（树的深度）所设置的惩罚项；

• α1 和

  α2 是待指定的参数。  

2.3. 选择过程

有多种方法可以选择用于创建下一代树的亲本。最常见的是以下几种：

• 基于适应度按比例选择，或轮盘赌式选择：按适合度对群体排序，然后依次为每个个体赋予选择概率。

• 淘汰制选择：先从群体中随机选出一些个体，再从选出的集合中取适合度最高的个体作为亲本。

• 精英制选择：直接把适合度最高的个体用到下一代。这种方法能保留每代最成功的个体。

2.4 重组

获得重组子代的过程需要使亲本两两配对。

首先，选择两个个体作为亲本。然后在两棵树中各随机选一个节点。用第二棵树中选择的子树代替第一棵树中选中的子树，获得子代。

图3-重组

2.5 突变

突变指的是一个群体的部分个体中的随机的小选择。突变是遗传多样性的保证，这意味着遗传算法能搜索到更大的范围。

对决策树而言，突变可以通过随机更改属性或者细分随机选的节点来实现。

图4-突变

2.6 终止条件

如果最优秀的个体的适合度在给定数量的世代中没有上升，就可以认为算法已经收敛了。

为了在收敛得很慢时节约计算时间，这个世代数目是预先设定的参数。

3. 跟其它分类器比，进化决策树的表现如何？

进化决策树看起来很好，但跟常规机器学习算法相比，它的表现又如何？

3.1 一个简单的实验

为了评价分类器的效率，我搭建了一个决策树，并在航空公司乘客满意度调查结果数据集上进行训练。

目标是找出能导致乘客满意度升高的因素。 这样就需要一个简单而抗干扰的模型来解释导致乘客感到满意（或不满意）的途径。

 照片来自这个网站，这位摄影师

关于数据集

这个数据集很大，囊括了多于10万条航线。

• 含有关于乘客及其行程的事实信息：乘客的性别，年龄，客户类型（是否有惯性），旅行类型（个人或商务旅行），航班舱位（商务，环保，极环保 ）和飞行距离。

• 还包含乘客对以下服务的满意度：舱内wifi，出发/到达时间（是否合宜），网上预订（是否方便），登机口位置，餐饮，网上值机，座椅舒适度，舱内娱乐，登机服务，座椅腿部空间 ，行李服务，值机服务，舱内服务，整洁度。

数据标签是乘客的满意度，包括“满意”，“中立”和“不满意”。

方法

我使用的计算步骤可简要归纳如下：

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（原文为“图5”，疑有误）-EDT中最佳决策树的示意图

3.2 对EDF方法的一个更泛化的实验验证

上述实验肯定不足以评估进化决策树跟其它机器学习算法相比时的性能和可靠性。

因为只用了一个数据集，因此没有考虑到所有可能性，例如标签的类别数量，特征数量和观测数量的影响等。

在[2]中，作者使用真实的UCI数据集对EDT方法与其他机器学习方法的性能进行了比较。

这篇文章的发现如下。

关于数据集

下表简要介绍了所用的数据集：

表4-数据集的性质

如你所见，数据集在观测次数，特征个数和类别个数这几个方面的差别很大。

最困难的数据集肯定是第一个数据集，因为它有很多类别，而观察次数较少。

方法

以下是与更‘经典’的机器学习算法相比时，作者用来评估EDT模型表现的方法的主要信息：

• EDT模型已使用以下超参数进行了训练：世代数为500，群体大小为400，重组/变异的概率分别为0.6 / 0.4，选择方法为随机统一的精英制选择。

• 使用5×2交叉验证来测量模型的表现。

结果

表5-模型的正确率取决于所用的数据集

1. 基于树的算法几乎总是优于其它机器学习算法。 可以解释为决策树本身更能选择出最重要的特征。 此外，基于规则的模型更适合用于特定的数据集，尤其是难以对目标与特征间的关系建模时。

2. 鲍鱼数据集上的结果都很差：因为有28个类别，而且观测次数很少（只有210次）。 但是，EDT模型以最高的准确率脱颖而出。 这表明它能有效地处理困难的数据集并避免过拟合。

值得注意的是，EDT模型使用的是默认参数。 调整参数能带来更好的表现。

引用

[1] R. Barros et al., A Survey of Evolutionary Algorithms for Decision Tree Induction, 2011

[2] D. Jankowski et al., Evolutionary Algorithm for Decision Tree Induction, 2016

[3] S. Cha, Constructing Binary Decision Trees using Genetic Algorithms, 2008

[4] D. Carvalho et al., A Hybrid Decision Tree/Genetic Algorithm Method for Data Mining, 2003

[5] Wikipedia, Traveling salesman problem

[6] Wikipedia, Genetic Algorithm

---

AI研习社是AI学术青年和AI开发者技术交流的在线社区。我们与高校、学术机构和产业界合作，通过提供学习、实战和求职服务，为AI学术青年和开发者的交流互助和职业发展打造一站式平台，致力成为中国最大的科技创新人才聚集地。

如果，你也是位热爱分享的AI爱好者。欢迎与译站一起，学习新知，分享成长。

雷锋网版权文章，未经授权禁止转载。详情见。