决策树原理，举例演算及其代码实现
一 .使用的例子：
| 人员 | 眼睛颜色 | 头发颜色 | 所属人种 |
|---|---|---|---|
| 1 | 黑色 | 金色 | 白种人 |
| 2 | 蓝色 | 黑色 | 黄种人 |
| 3 | 灰色 | 金色 | 白种人 |
| 4 | 蓝色 | 金色 | 白种人 |
| 5 | 灰色 | 金色 | 白种人 |
| 6 | 黑色 | 黑色 | 黄种人 |
| 7 | 灰色 | 黑色 | 黄种人 |
| 8 | 蓝色 | 黑色 | 黄种人 |
决策树的基本思想是从一颗空的决策树开始，选择某一属性作为测试属性，该测试属性对应决策树中的决策顶点，再在剩下的数据集上递归选择另一属性建立决策顶点。
一。决策树学习算法大体上可以分为两个阶段：建模阶段和预测阶段
建模阶段可通过以下步骤实现：
- 首先，所有训练样本都处于根节点位置
- 基于一定的策略选择属性
- 根据选择的属性，递归地划分样本
我们主要要解决两个问题：
递归结束的条件：递归的情况有以下几种
- 没有可用的数据：以父节点的标签作为标签
- 被分到的样本都属于同一个类别：以该类别作为标签
- 所有属性都已用于之前的划分，没有可用的属性可以继续划分：采用多数投票的方式选出标签。
通过什么策略选择节点的属性
使用上面的例子，如果我们先选眼睛颜色作为属性，可以建出如下的树
如果先选择头发颜色作为属性，可以建出如下的树：
从上面两棵树来看，选择不同属性作为节点对建树的影响很大，所以我们要选择合适的策略算法，常用的有ID3,C4.5,CART，这三种之后会逐个解释。
通过上述步骤，就可以建立一棵决策树，接下来就是预测阶段：
预测阶段就是根据带预测数据各属性的取值，逐步遍历树，直到叶子节点，叶子节点对应的标签就说我们的预测结果，比如我们要预测蓝眼睛黄头发的属于哪个人种，以第一棵树为例
从根节点出发，先看眼睛颜色，为蓝色，所以选择根节点的第二个节点作为下个节点，然后看头发颜色，为黄色，选择第一个节点，此时已到叶子节点，对应的标签为白种人，所以我们预测结果为白种人。
二。决策函数
上面已经解释了建立一颗树的大致步骤，但还有最重要的一个问题没有解决，就是选择什么策略：
ID3使用信息增益度选择测试属性，要解释如何计算信息增益度，先要解释信息熵，信息熵是衡量一个信息不确定性大小的值，通常我们认为，如果某个信息让我们的判断更加有序，清晰，则它信息熵越小，反之越大。
$X$的信息熵计算公式如下：
$H(X) = \sum_{x\in X}(-p(x)\times log(p(x)))$
条件熵:$H(Y|X)$表示是在$X$确定下$Y$的熵，可以通过如下公式计算
$H(Y|X) = \sum_{x\in X}p(x)H(Y|X=x)=\sum_{x\in X}\sum_{y\in Y}p(x,y)log_2p(y|x)$
联合熵：$H(X,Y) = -\sum_{x\in X}\sum_{y\in Y}p(x,y)log_2p(x,y)=H(X)+H(Y|X)= H(Y)+H(Y|X))$
这表明两个变量的联合熵等于$X$的熵加上给定$X$,出现$Y$的条件熵。
接着根据联合熵的公式定义两个变量的互信息为$I(X,Y)=H(Y)-H(Y|X)$
互信息量表示两个变量之间的相关程度，互信息量越大，表示两个变量相关程度越大，$X$就越适合作为属性，比如$Y$表示人种，$X$表示头发颜色，如果$I(X,Y)$越大，表示两者之间关系很大，此时选择头发颜色作为属性是合适的。
例如，上例中$H(Y) = -0.5log_2(0.5)-0.5log_20.5=1$
$H(Y|X=”眼睛颜色”)=\frac{2}{8}(-\frac{1}{2}log_2\frac{1}{2}-\frac{1}{2}log_2\frac{1}{2})+\frac{3}{8}(-\frac{1}{3}log_2\frac{1}{3}-\frac{2}{3}log_2\frac{2}{3})+\frac{3}{8}(-\frac{1}{3}log_2\frac{1}{3}-\frac{2}{3}*log_2\frac{2}{3})$
$I(X=”眼睛颜色”，Y) = H(Y)-H(Y|X=”眼睛颜色”)$
类似的，可以算出$I(X=”头发颜色”，Y)$,然后取两者中的较大值。
但是采用信息增益进行数据分裂容易偏向取值较多的特征，可以理解为分支数越多，不确定性越大，熵就会越大。
C4.5采用增益率克服了上述问题，通过引入一个变量增益率
$SplitInfo_A(D)=-\sum_{j}\frac{|D_j|}{|D|}\times log_2(\frac{|D_j|}{D})$
对信息增益进行归一化，一个特征的取值越多，变量增益率就越大，把它作为分母，就可以校正信息增益偏向取值较多的特征的问题，
即最终结果为$GainRatio_A(D)=\frac{Gain_A(D)}{SplitInfo_A(D)}$
取计算结果最大的特征作为属性。
CART模型基于基尼指数选择合适的属性。
如果一个数据集包含来自n个类的样本，那么基尼指数$gini(D)=\sum_jP_j(1-p_j)=1-\sum_jp_j^2$
如果一个数据集$D$被分成两个子集$D_1$和$D_2$，大小分别为$N_1$和$N_2$，那么基尼指数$gini_{split}(D)=\frac{N_1}{N}gini(D_1)+\frac{N_2}{N}gini(D_2)$
取基尼指数最小的属性最为本节点的属性。
