## 数据挖掘入门系列教程（三点五）之决策树
本来还是想像以前一样，继续学习《 Python数据挖掘入门与实践 》的第三章“决策树”，但是这本书上来就直接给我怼了一大串代码，对于`决策树`基本上没有什么介绍，可直接把我给弄懵逼了，主要我只听过决策树还没有认真的了解过它。
这一章节主要是对决策树做一个介绍，在下一个章节，将使用决策树来进行预测分类 。
### 决策树（Decision Tree）介绍
Decision Tree是一类较为常见的机器学习的方法。它既可以作为分类算法，也可以作为回归算法。
如何来介绍决策树，这里举一个例子：在大学，你找女朋友的时候，心目中顺序应该是这样的（仅仅是举一个例子）：
- Q：性别要求？
- A：不是女的不要。
- Q：年龄要求？
- A：大于我3岁的不要
- Q：专业要求？
- A：非CS不要
- ……
为了更好的表示上面的这一些问题，我们可以将其画成一张树状图如下所示：
上面的这棵树就是我们找女朋友的决策过程，圆角矩形代表了判断条件，椭圆形代表了决策结果。通过性别，年龄，专业这几个属性，最终我们得出了最终的决策。而这棵树也就被称之为决策树。
大家通过上图会发现有3个东西：
- 根节点：包含样本的全集
- 内部节点：对应特征属性测试
- 叶节点：代表决策的结果
在一棵决策树中，包含了一个`根节点`，多个`内部节点（判断条件）` 和若干个`叶子节点`。先说叶子节点，在决策树中，叶子节点对应了决策结果，决策结果可以有多种类型（图中是yes和no，也可以为1，2，3）。内部节点和根节点对应的都是`属性测试`，只不过先后顺序不同。
总的来说，决策树体现的是一种“分而治之”的思想，
那么这里就有一个问题，谁来当根节点？谁又来当中间的节点？先后顺序又是怎样的？（这里先不说算法流程，从简单开始说起，然后再说算法流程）
### 结点的选择
首先我们需要明白根节点和中间节点是不同的，一个是统领全局的开始包含所有的样本。一个是负责局部的决策，并且随着决策树的不断的进行决策，所包含的样本逐渐属于同一个类别，即节点的“纯度”越来越高。
那么，我们如何来寻找合适根节点（也就是属性）呢？靠感觉？靠感觉当然不行，我们需要一个具体的数值来决定，很幸运，香农帮助我们做到了。
“信息熵”（information entropy）：可以度量样本集合中的“纯度”。 在信息世界，熵越高，表示蕴含越多的信息，熵越低，则信息越少。 而根节点需要包含所以的样本，则`根结点的熵最大`。
#### 信息熵（Information Entropy）
设样本集合为$D$，第$k$类样本所占比例为$p_k(k = 1,2,3,……n)$，则集合$D$的信息熵为：
$$
Ent(D) = - \sum_{k=1}^{n}p_klog_2p_k\\
Ent(D)越大，则D的纯度越小，也就是说集合D越混乱。
$$
现在，我们已经知道一个集合$D$中的信息熵是多少，那么我们如何来进行划分呢？首先，我们需要明确一个划分的标准（也就是目标），我们当然希望划分之后，划分之后的集合的熵越来越小，也就是划分后的集合越来越纯，这里我们引入信息增益这个概念。
#### 信息增益（information gain）
下面是西瓜书中对信息增益的定义：
> 假设离散属性$a$有$V$个可能的取值$\{a^1,a^2,a^3……a^V\}$，若以属性$a$对样本进行划分，则有V个分支，其中第$v$个分支包含了$D$中在属性$a$上取值为$a^v$的样本，记为$D^v$。我们可以计算出$D^v$的信息熵，然后考虑到不同分支结点的样本数不同，给分支结点赋予权重$\frac{|D^v|}{|D|}$，样本数愈多，则影响力越大，则可以计算出属性$a$对样本集$D$进行划分的“信息增益”：
>
> $$
> Gain(D,a) = Ent(D) - \sum_{v=1}^V\frac{|D^v|}{|D|}Ent(D^v)
> $$
一般来说，信息增益越大，则代表划分后的集合越“纯”，也就是说使用$a$属性来划分的效果最好，那么我们就可以使用$a$属性来进行划分。*ID3算法*就是使用信息增益来作为标准划分属性的。
### 决策树生成算法流程
下面是来自《西瓜书》的决策树生成算法流程：
决策树生成是一个递归的过程，在下面3中情况中，递归会返回：
- 当前结点包含的样本全属于同一类别，无需划分
- 当前属性集为空，或是所有样本在所有属性上取值相同，无法划分
- 当前结点包含的样本集合为空，不能划分
算法可能不是那么的形象好理解，下面将以实际的例子来展示。
在最上面上面的找女朋友的例子并不是特别的好，属性太少。这里以西瓜书中的
