决策树之一-基础篇

决策树（Decision Tree, DT）是一个树结构，根据具体算法的不同可以是二叉树或非二叉树。其每个内部叶节点表示一个特征属性上的测试，每个分支代表这个特征属性在某个值域上的输出，而每个叶节点在分类问题中存放一个类别在回归问题中存放一个数值。

使用决策树进行决策的过程就是从根节点开始，对输入样本测试节点指定的特征属性，并按照其值选择输出分支，直到到达叶子节点，将叶子节点存放的类别作为决策结果。

决策树是一种通过对特征属性的分类对样本进行分类的树形结构，包括有向边与三类节点：

举个示例，决策树表示如下：

决策树代表实例属性值约束的合取的析取式。从树根到树叶的每一条路径对应一组属性测试的合取，树本身对应这些合取的析取。其实决策树就是可以看做一个if-then规则的集合。我们从决策树的根结点到每一个都叶结点构建一条规则。并且我们将要所有需要预测的实例都可以被一条路径或者一条规则所覆盖。

假如我现在告诉你，我买了一个西瓜，它的特点是纹理是清晰，根蒂是硬挺的瓜，你来给我判断一下是好瓜还是坏瓜，恰好，你构建了一颗决策树，告诉他，没问题，我马上告诉你是好瓜，还是坏瓜？

判断步骤如下：
第一步，根据纹理特征，已知是清晰，那么走下面这条路，红色标记，如下图红线所示：

第二步，现在到了第二层了，这个时候，由决策树图，我们看到，我们需要知道根蒂的特征是什么了？很好，他也告诉我了，是硬挺，于是，我们继续走，如下面蓝色所示：

此时，我们到达叶子结点了，根据上面总结的点，可知，叶子结点代表一种类别，我们从如上决策树中，可以知道，这是一个坏瓜！
于是我们可以很牛的告诉他，你买的这个纹理清晰，根蒂硬挺的瓜是坏瓜。

结合上面讲的决策示例。决策树具有以下特点：

分类的本质是对特征空间的划分，如下图

根据上面例子，非常容易直观的得到了一个实例的类别判断，只要你告诉我各个特征的具体值，决策树的判定过程就相当于树中从根结点到某一个叶子结点的遍历。每一步如何遍历是由数据各个特征的具体特征属性决定。

好的，可能有人要问了，说了这么多，给你训练数据，你的决策树是怎么构建的呢？

**于是构建决策树也就成为了最重要的工作！**

比如，给我下面训练数据，我如何构建出决策树？

我们可以从上面决策树看出，每一次子结点的产生，是由于我在当前层数选择了不同的特征来作为我的分裂因素造成的。比如下图用红色三角形表示选择的特征：

每一层选择了指定的特征之后，我们就可以继续由该特征的不同属性值进行划分，依次一直到叶子结点。

看起来一切很顺利！但是细心的小伙伴可能会问了，为什么在第一次选择特征分裂的时候，不选择触感呢？而是选择纹理，比如如下：

不换成触感，或者其它特征为什么也不行呢？为什么选择的是纹理，这是以什么标准来选择特征的？这就是我们要说的决策树的关键步骤是分裂属性。

所谓分裂属性就是在某个节点处按照某一特征属性的不同划分构造不同的分支，其目标是降低各个分裂子集的“不纯度(impurity)”。尽可能降低“不纯度”，也就是尽量“纯”就是尽量让一个分裂子集中待分类项属于同一类别。

决策树学习的本质是从训练数据集中归纳出一组分类规则。但随着分裂属性次序的不同，所得到的决策树也会不同。如何得到一棵决策树既对训练数据有较好的拟合，又对未知数据有很好的预测呢？

首先，我们要解决两个问题：

如何选择较优的特征属性进行分裂？每一次特征属性的分裂，相当于对训练数据集进行再划分，对应于一次决策树的生长。ID3算法定义了目标函数来进行特征选择。
什么时候应该停止分裂？有两种自然情况应该停止分裂，一是该节点对应的所有样本记录均属于同一类别，二是该节点对应的所有样本的特征属性值均相等。但除此之外，是不是还应该其他情况停止分裂呢？

而判断“不纯度”的方法不同引出了我们的ID3算法，C4.5算法以及CART算法，这些后面会详细介绍！