机器学习——有监督——决策树相关原理及sklearn实现（信息熵、基尼系数、信息增益、特征重要程度的量化）

一、决策树原理

决策树（Decision Tree）是一种非参数的有监督学习方法，它能够从一系列有特征和标签的数据中总结出决策规则，并用树状图的结构来呈现这些规则，以解决分类和回归问题。决策树算法容易理解，适用各种数据，在解决各种问题时都有良好表现，尤其是以树模型为核心的各种集成算法，在各个行业和领域都有广泛的应用。

我们来简单了解一下决策树是如何工作的。决策树算法的本质是一种图结构，我们只需要问一系列问题就可以对数据进行分类了。比如说，来看看下面这组数据集，这是一系列已知物种以及所属类别的数据：

根据已经收集到的数据，决策树算法为我们算出了下面的这棵决策树： 

 根据以上的决策树规则，当我们发现一个新的物种，我们就可以根据决策树判断它所属的类别。

根节点：没有进边，有出边。包含最初的，针对特征的提问。
中间节点（内部节点）：既有进边也有出边，进边只有一条，出边可以有很多条。都是针对特征的提问。
叶子节点：有进边，没有出边，每个叶子节点都是一个类别标签。
*子节点和父节点：在两个相连的节点中，更接近根节点的是父节点，另一个是子节点。

二、构建决策树

任意一个数据集上的所有特征都可以被拿来分枝，每个特征上的任意值都可以当成一个节点*组合（例如身高可以分为<1.8米，>=1.8米，也可以分为<1米，>=1米，等等），所以一个数据集上可以发展出非常非常多棵决策树，其数量可达指数级。在这些树中，总有那么一棵树比其他的树分类效果都好，那样的树叫做”全局最优树“。

全局最优：经过组合形成的，整体来说分类效果最好的模型
局部最优：每一次分枝的时候都向着更好的分类效果分枝，但无法确认如此生成的树在全局上是否是最优的。

决策树算法的核心是要解决两个问题：
1）如何从数据表中找出最佳节点和最佳分枝？
2）如何让决策树停止生长，防止过拟合？

一个数据集可以发展的决策树数量是指数级别的，在这么多的决策树当中挑选出一颗“全局最优树”，是非常低效的，于是我们牺牲掉小部分的准确率，用逐步的“局部最优”来达到最接近“全局最优”的结果，这类算法我们统称为“贪心算法”。

贪心算法：通过实现局部最优来达到接近全局最优结果的算法，所有的树模型都是这样的算法。

最典型的决策树算法是Hunt算法，该算法是由Hunt等人提出的最早的决策树算法。现代，Hunt算法是许多决策树算法的基础，包括ID3、C4.5和CART等。Hunt算法诞生时间较早，且基础理论并非特别完善，此处以应用较广、理论基础较为完善的ID3算法的基本原理开始，讨论如何利用局部最优化方法来创建决策模型。

ID3算法原型见于J.R Quinlan的博士论文，是基础理论较为完善，使用较为广泛的决策树模型，在此基础上J.R
Quinlan进行优化后，陆续推出了C4.5和C5.0决策树算法，后二者现已称为当前最流行的决策树算法，我们先从ID3
开始讲起，再讨论如何从ID3逐渐优化至C4.5。