1. 决策树介绍

决策树【Decision Tree，DT】是一类较为常见的「机器学习」方法，DT既可以作为分类算法，也可以作为回归算法。

举个分类的例子：
在相亲的时候，找对象的顺序应该是：

• Q：性别要求？
• A：不是女的不要。
• Q：年龄要求？
• A：大于我5岁的不要。
• Q：专业要求？
• A：非计算机专业的不要？
• …
  为了更好的表示上面的这些问题，我们将其画成一张树状图：
  
  上面的这棵树就是我们找对象的决策过程，圆角矩形代表了判断条件，椭圆代表了决策结果。通过性别、年龄和专业这几个属性，最终，得出最后的决策。因此，这棵树被称之为决策树。

通过绘制决策树，发现一颗决策树上3种节点：

• 根节点：包含样本的全集
• 内部（中间）节点：对应特征属性
• 叶节点：代表决策的结果

在一颗决策树中，包含了一个根节点，多个内部节点，若干个叶子节点。

先说叶子节点，在决策树中，叶子节点对应了决策结果，决策结果可以有多种类型（要，不要，也可以是Yes，No，1,2）。

内部节点和根节点对应的都是对应特征属性，只不过先后顺序不同。

总的来说，决策树体现的是一种“分而治之”的思想。

2. 结点的选择

首先，我们要明白根节点和中间节点是不同的，一个统领全局的开始包含所有的样本。一个负责局部的决策，并且随着决策树的延伸，不断进行决策，所包含的样本逐渐属于同一个类别，即节点的“纯度”越来越高。

那么，我们如何寻找合适的根节点（也就是特征属性）呢？
靠感觉？靠猜？那肯定是不行的，我们需要一个具体的数值来决定，很幸运，香农帮我们解决了这个问题。

“信息熵”（information entropy）：可以度量样本集合中的“纯度”。在信息世界，熵越高，表示蕴含越多的信息；熵越低，表示信息越少。而根节点需要包含所有的样本，则根节点的熵最大。

3. 信息熵（Information Entropy）

设样本集合为 D D D，第k类样本所占比例为p_k （1,2,3,…,n），则集合 D D D的信息熵为：

现在，我们已经知道一个集合 D D D中的信息熵是多少，那么我们如何进行划分呢？
首先，我们需要明确一个划分的标准（也就是目标），我们当然希望划分之后，划分之后的集合的熵越来越小，也就是划分后的集合越来越纯，这里我们引入信息增益这个概念。

4. 信息增益（Information Gain）

参考

https://www.cnblogs.com/xiaohuiduan/p/12490064.html