决策树

什么是决策树

决策树是一种机器学习的方法，决策树是一种树形结构，其中每个内部节点表示一个属性上的判断，每个分支代表一个判断结果的输出，最后每个叶节点代表一种分类结果。

熵

熵 Entropy 是 “混乱” 程度的量度。
系统越有序，熵值越低；系统越混乱或者分散，熵值越高。
假如事件A的分类划分是（A1,A2,…,An），每部分发生的概率是(p1,p2,…,pn),那信息熵定义为公式如下：

Ent(A)=- \sum {k=1}^{n}p{k} \log {2}p{k}
=-p_{1} \log {2}p{1}-p_{2} \log {2}p{2}- \cdots -p_{n} \log {2}p{n}

篮球比赛里，有4个球队 {A,B,C,D} ，获胜概率分别为{1/2, 1/4, 1/8, 1/8}，求H(X)
信息熵 H(X) = 1\2log(2)+1\4log(4)+1\8log(8)+1\8log(8)=(1\2+1\2+3\8+3\8)log(2)=7\4

决策树的划分依据

信息增益

信息增益 = entroy(前) - entroy(后)
特征A对训练数据集D的信息增益g(D,A),定义为集合D的信息熵H(D)与特征A给定条件下D的信息条件熵H(D|A)之差，即公式为：
g(D,A)=H(D)-H(D|A)
信息熵的计算：
H(D)=- \sum {k=1}^{K} \frac{|C{k}|}{|D|} \log \frac{|C_{k}|}{|D|} 注：C_k 表示属于某个类别的样本数

条件熵的计算：
H(D|A)=-\sum {i=1}^{n} \frac{|D{i}|}{|D|} \sum {k=1}^{K} \frac{|D{ik}|}{|D_{i}|} \log \frac{|D_{ik}|}{|D_{i}|}

信息增益率(略)

基尼值和基尼指数

基尼值Gini（D）：从数据集D中随机抽取两个样本，其类别标记不一致的概率。Gini（D）值越小，数据集D的纯度越高。

Gini(D)= \sum {k=1}^{|y|} \sum _{k^{ \prime } \neq k}p{k}p_{k^{ \prime }}=1- \sum {k=1}^{|y|}p{k}^{2}

基尼指数Gini_index（D）：一般，选择使划分后基尼系数最小的属性作为最优化分属性。
Gini_{-}index(D,a)= \sum _{ \nu =1}^{V} \frac{|D^{ \nu }|}{|D|}Gini(D^{ \nu })

决策树构建

基本步骤

1. 开始将所有记录看作一个节点
2. 遍历每个变量的每一种分割方式，找到最好的分割点
3. 分割成两个节点N1和N2
4. 对N1和N2分别继续执行2-3步，直到每个节点足够“纯”为止。

变量划分

1. 数字型：变量类型是整数或浮点数，用“>=”，“>”,“<”或“<=”作为分割条件。
2. 名称型（Nominal）：变量只能从有限的选项中选取，使用“=”来分割。

例子：请根据下图列表，按照基尼指数的划分依据，做出决策树。

1. 对数据集非类标号属性{是否有房，婚姻状况，年收入}分别计算它们的Gini系数增益，取Gini系数增益值最大的属性作为决策树的根节点属性。

2. 根节点的Gini系数为：Gini(是否拖欠货款)=1-( \frac{3}{10})^{2}-( \frac{7}{10})^{2}=0.42

3. 当根据是否有房来进行划分时，Gini系数增益计算过程为：

   Gini(左子节点)=1-( \frac{0}{3})^{2}-( \frac{3}{3})^{2}=0
   Gini(右子节)=1-( \frac{3}{7})^{2}-( \frac{4}{7})^{2}=0.4898
   是否有房=0.42- \frac{7}{10} \times 0.4898- \frac{3}{10} \times 0=0.077

4. 按婚姻状况属性来划分，属性婚姻状况有三个可能的取值{married，single，divorced}

   1. 分组为{married} | {single,divorced}时：

      =0.42- \frac{4}{10} \times 0- \frac{6}{10} \times \left[ 1-( \frac{3}{6})^{2}-( \frac{3}{6})^{2} \right]=0.12

   2. 当分组为{divorced} | {single,married}时：

      =0.42- \frac{2}{10} \times 0.5- \frac{8}{10} \times \left[ 1-( \frac{2}{8})^{2}-( \frac{6}{8})^{2} \right]=0.02

   3. 当分组为{single} | {married,divorced}时：

      =0.42- \frac{4}{10} \times 0.5- \frac{6}{10} \times \left[ 1-( \frac{1}{6})^{2}-( \frac{5}{6})^{2} \right]=0.053

   对比计算结果，根据婚姻状况属性来划分根节点时取Gini系数增益最大的分组作为划分结果，即:{married} | {single,divorced}

5. 对于年收入属性为数值型属性，首先需要对数据升序排序，然后从小到大依次用相邻值的中间值作为分隔将样本划分为两组。

例如节点为65时: Gini(年收入)=0.42- \frac{1}{10} \times 0- \frac{9}{10} \times \left[ 1-( \frac{6}{9})^{2}-( \frac{3}{9})^{2} \right] =0.02

6. 根据计算知道，三个属性划分根节点的增益最大的有两个：年收入属性和婚姻状况，他们的增益都为0.12。此时，选取首先出现的属性作为第一次划分。接下来，采用同样的方法，分别计算剩下属性。

   去掉married的数据

   Gini(是否拖欠货）=1-( \frac{3}{6})^{2}-( \frac{3}{6})^{2}=0.5

7. 对于是否有房属性，可得：Gini(是否有房)=0.5- \frac{4}{6} \times \left[ 1-( \frac{3}{4})^{2}-( \frac{1}{4})^{2} \right] - \frac{2}{6} \times 0=0.25

8. 对于年收入属性则有：

常见决策树

信息熵：Ent(D)=- \sum {i=1}^{k}p{i} \cdot \log (p_{i})

信息增益：Gain(D,a)=Ent(D)- \sum {i}^{k}p{i} \times Ent(D|i)（ID3决策树）

信息增益率：Gain_{-}ratio(D,a)= \frac{Gain(D,a)}{Ent(a)}（C4.5决策树）

基尼值：Gini(D)=1- \sum {i=1}^{k}p{i} \cdot p_{i}

基尼指数：Giniindex(D|a)= \sum {i=1}^{k}p{i} \cdot Gini(D|i)（CART决策树）