决策树原理概述

树模型

决策树：从根节点开始一步步走到叶子节点（决策）

所有的数据最终都会落到叶子节点，既可以做分类也可以做回归

树的组成

根节点：第一个选择点

非叶子节点与分支：中间过程

叶子节点：最终的决策结果（没有后代的节点）

节点

增加节点相当于在数据中切一刀

节点越多越好吗？

决策树的训练与测试

训练阶段：从给定的训练集构造出来一棵树（从根节点开始选择特征，如何进行特征切分）

测试阶段：根据构造出来的树模型从上到下去走一遍就好了

一旦构造好了决策树，那么分类或者预测任务就很简单了，只需要走一遍就好了。那么难点就在于如何构造出来一棵树，这就没那么容易了，需要考虑的问题还有很多。

如何切分特征（选择节点）

问题：根节点的选择该用哪个特征呢？接下来呢？如何切分呢？

想象一下：我们的目标应该是根节点就像一个老大似的能更好的切分数据（分类的效果更好），根节点下面的节点自然就是二当家了。

目标：通过一种衡量标准，来计算通过不同特征进行分支选择后的分类情况，找出来最好的那个当做根节点，以此类推。

衡量标准——熵

熵：表示随机变量不确定性的度量

（解释:说白了就是物体内部的混乱程度，比如杂货市场里面什么都有，那肯定混乱呀，专卖店里只卖一个牌子的那就稳定多了）

公式：

一个栗子：

A集合[1,1,1,1,1,1,1,1,2,2]  

B集合[1,2,3,4,5,6,7,8,9,1]

显然A集合的熵值要低，因为A集合只有两种类别，相对稳定一些，而B中类别太多了，熵值就会大很多（在分类任务中我们希望通过节点分支后数据类别的熵值大还是小呢？）

熵：不确定性越大，得到的熵值也就越大

当P=0或者P=1时，H(P)=0,随机变量完全没有不确定性

当P=0.5时，H(P)=1，此时随机变量的不确定性最大

如何决策一个节点的选择呢？

信息增益：表示特征X使得类Y的不确定性减少的程度。（分类后的专一性，希望分类后的结果是同类在一起）

决策树构造实例

数据：14天打球情况

特征：4种环境变化

目标：构造决策树

划分方式：4种

问题：谁当根节点呢？

依据：信息增益

在历史数据中（14天）有9天打球，5天不打球，所以此时的熵应为：

4个特征逐一分析，先从outlook特征开始：

outlook=sunny时，熵值为0.971

outlook=overcast时，熵值为0

outlook=rainy时，熵值为0.971

根据数据统计，outlook取值分别为sunny,overcast,rainy的概率分别为：5/14,4/14,5/14

熵值计算：5/14 * 0.971 + 4/14 * 0 + 5/14 * 0/971 = 0.693

信息增益：系统的熵值从原始的0.940下降到了0.693，增益为0.247

（gain(temperature)=0.029 gain(humidity)=0.152 gain(windy)=0.048）

同样的方式可以计算出其他特征的信息增益，那么我们选择最大的那个就可以啦，相当于是遍历了一遍特征，找出来了大当家，然后再其余的中继续通过信息增益找出二当家

信息增益率

ID3：信息增益（有什么问题呢？）

C4.5：信息增益率（解决ID3问题，考虑自身熵）

CART：使用GINI系数来当做衡量标准

GINI系数：

（和熵的衡量标准类似，计算方式不相同）

决策树剪枝策略

连续值怎么办？

选取（连续值的）哪个分界点？

&贪婪算法

排序

60 70 75 80 85 90 95 100 120 125 220

若进行“二分”，则可能有9个分界点

例子： 60 70 75 80 85 90 95 100 120 125 220

数值小于等于80的分为一类：60 70 75

数值大于80的分为一类： 80 85 90 95 100 120 125 220

数值小于等于95的分为一类：60 70 75 80 85 90 95

数值大于95的分为一类：100 120 125 220

实际上，这就是“离散化”过程

为什么要剪枝：决策树过拟合风险很大，理论上可以完全分得开数据

（想象一下，如果树足够庞大，每个叶子节点不就一个数据了嘛）

剪枝策略：预剪枝，后剪枝

预剪枝：边建立决策树边进行剪枝的操作（更实用）

后剪枝：当建立完决策树后来进行剪枝操作 

预剪枝：限制深度，叶子节点个数，叶子节点样本数，信息增益量等

后剪枝：通过一定的衡量标准

（叶子节点越多，损失越大）