决策树算法简介

1.什么是决策树？

从根节点一步步走向叶子节点（此过程叫决策），形成了决策树。
所有的数据都会进入叶子节点，构造完成决策树后，决策树可以用于分类或回归。
例如

根节点：第一个选择的分类节点。
非叶子节点与分支：中间过程。
叶子节点：决策过程。
在此图中的年龄小于15分类判断是根节点，是否男性属于非叶子节点与分支，三个最终的图片都属于叶子节点。

那么叶子节点是否是越多越好呢？
不是，如果叶子节点过多，会造成数据分类太过于详细，叶子节点的样本数据会过少，进而导致过拟合的发生。

决策树的训练与测试

1.训练
从训练集中构造出一棵树（从根节点开始选择特征，选择特征的原则是从分类效果最好的开始选起）。
2.测试
根据构造出来的树的模型从根节点开始到叶子节点走一遍。
重难点：如何构造出一个决策树？

根节点如何选择？

通过一种衡量标准，计算用不同特征进行分支选择后的分类情况，找出分类效果最好的特征成为根节点，其他以此类推。

2.熵值法

熵

表示随机变量不确定性的度量（表示物体内部的混乱程度）。
公式：

比如：
A集合：{1，1，1，1，1，1，1，1，1，1，2，2}
B集合：{1，2，3，4，5，6，7，8，9，9，8，7}
A的熵值就比B要低很多，在构造决策树的过程中，我们自然希望通过节点分支后的数据熵值越低越好。

熵：物体的不确定性越多则熵值越大。
P=0或1，H（p）=0，随机变量没有不确定性。
P=0.5,H（p）=1，不确定性达到最大值。

如何对节点进行选择？

答：通过信息增益。

信息增益：表示特征X使得类Y不确定性减少的程度（希望分类后同类尽量在一起）
例子

划分方式可以有四种：1.基于天气；2.基于温度；3.基于湿度；4.基于是否有风。

在标签数据中我们可以得知，14天中有9天打球，5天不打球，求熵值：

再求outlook的熵值：sunny：0.971，overcast：0，rainy：0.971
取sunny等天气的概率：5/14,4/14,5/14。
得出天气类的总熵值：

信息增益：0.940-0.693=0.247
其他特征以此类推，选择增益最大的特征为根节点即可。

3.决策树算法类型

ID3：信息增益。
C4.5：信息增益率：可以解决信息增益无法考虑自身熵值的问题。
CART：GINI系数。
GINI系数：

解释：比如当有ID列存在且作为特征时，根据ID进行分类的结果会产生n个叶子节点，且每个叶子节点只有一个数据存在，此时的概率为1，也就是熵值为0，信息增益达到最大值，ID特征被选为根节点，但是ID对于我们的分类毫无用处，绝对是错误的选择。
推广到稀疏型的特征，包含有很多的属性，并且每个属性包含的数据量很少的时候，就可能出现此种错误。

连续值的切分问题

如何选择分界点进行数据量的切分？
答：贪婪算法，找出一个原数据集特征列没有包含的点进行数据切分。

4.决策树剪枝

为什么要进行剪枝？
答：决策树过大会造成数据分类到叶子节点的数据过少（理论上可以做到一个叶子节点一个数据），当我们用此决策树做回归时的过拟合风险过大。

剪枝策略：预剪枝，后剪枝。
预剪枝：边建立决策树边剪枝（最实用）
预剪枝会通过限制决策树深度，叶子节点个数，叶子节点样本数，信息增益量等方法来进行剪枝
后剪枝：建立完成决策树后在进行剪枝
后剪枝策略会通过一定的衡量标准来进行剪枝：

C（T）：叶子节点的GINI系数或者熵值乘以此节点的样本数的总和。（叶子节点越多，损失越大）
Tleaf：叶子节点个数。
Ca（T）越小越好，越小代表损失越小。
例子

原Ca（T）=0.49389+a1 ------------------------------------------------------------1
分裂为3个叶子节点后Ca（T）=30+30+0.44443+3a ------------------------2
看1，2式谁更小，越小越好，来确定是否进行分裂。
接下来有空继续分享决策树算法代码实现。