1-1 决策树的基本结构及三个终止条件

1. 决策树的基本结构

决策树很简单，就是根据特征的不同取值生成的一棵树。因为有很多特征，所以这棵树会生成若干层的分支节点，直到叶节点。因为每个特征至少有两个取值，所以生成子节点的时候至少要分成两叉。在使用决策树模型对样本类型进行判别的时候，从根节点出发，根据样本的特征取值一步一步沿着对应的子节点向下走，直到达到叶节点，然后把样本归为该叶节点所标记的类别。

2. 决策树生成时的三个终止条件

在训练一棵决策树的时候，最重要的是每一步划分子节点时的特征选择，但这个地方先不表。先看一下生成决策树时的三个终止条件。为了说得简单明白，我们举个简单栗子：我们生成这颗决策树的目标，是用于判断一个人是好人还是坏人。我们有的样本集是100个人，可用的特征有三个：性别：{男，女}，年龄段：{青年，中年，老年}，地域：{北京，深圳}。

第一个终止条件：子节点中的样本属于同一类

100个人里面30个好人，70个坏人。假设第一次划分是根据性别划分，然后有50个男人50个女人。我们发现，男人这个子节点50个全是坏人，毕竟男人没有一个好东西。这50个坏男人里面，有青年有中年也有老年，有北京的也有深圳的，但无所谓了，没必要再继续划分。这就是第一个终止条件

子节点属于同一类则没必要再进行划分

第二个终止条件：该子节点没有样本了

但是对女人，我们还要继续考察，假设接下来我们是按照年龄段划分的子节点，然后我们发现，老年这个子节点里一个样本都没有。这肯定是没办法继续划分了。问题是，那么我们如何归类这个子节点呢？如果来了一个“老女人”让我们判断，该判断为好人还是坏人呢？答案是利用父节点来判断，老女人这个子节点为空，但是它的父节点是30个好人20个坏人。我们无法判断一个老女人的好坏，但是既然一个女人有60%的可能性是好人，那么我们就也把老女人判断为好人吧！这就叫先验概率。

该节点已经没有样本了自然不能再划分了。依据父节点的情况给该节点归类。

第三个终止条件：特征已经用完了

我们看到，对于女青年和女中年这个子节点，仍然是有好有坏啊，所以我们继续按照地域进行划分，然后发现结果如下：

特征已经用完了，子节点却仍不单纯，被迫终止划分

但是按照地域划分完后，有些节点已经完全是好人或完全时坏人了，但也有些节点不是这样，如红框标注。那也不能继续划分了，因为没有特征可用了。任何一个节点，其性别、年龄段、地域三个特征的属性都是固定了，没有办法再拆解成更小的节点。

这个情况怎么归类该节点是好人还是坏人呢？答案是：多数表决。既然该节点不是只有好人或只有坏人，那就简单点，那个占得多就算哪个吧！所以，如果是一个北京的女青年，我们就判断她为坏人，如果是深圳的女青年，则把她判断为好人。这就叫后验概率。

以上就是决策树生成时的三个终止条件，栗子随口一举，大家都是社会主义接班人，不要打我~~~~