决策树 - 简书

决策树既可以用来做分类【分类树】，又可以做回归【回归树】。
决策树由三个部分构成：
根节点：第一个选择点
非叶子节点和分支：中间过程
叶子节点：最终的决策结果
过程：利用给定的训练集构造一棵树，根据构造的树，把测试集从上到下走一遍
所以关键是如何选择特征来构造决策树
三种方法：ID3【按照信息增益计算】、C4.5【按照信息增益比计算】、CART【按照CINI系数计算】
分类树
例子：

image.png

1）ID3
衡量标准：熵 $H(x)$ 【表示随机变量不确定性的指标】，熵值越大，不确定性越高
$H(x)=-\sum\limits_{i=}^{n}{{{p}_{i}}\log _{2}^{{{p}_{i}}}}$
当 ${{p}_{i}}\text{=}0,1$ 时， $H(x)$ 等于0 ，达到最小，完全没有不确定性；
当 ${{p}_{i}}\text{=}0.5$ 时， $H(x)$ 等于1，达到最大，不确定性最大。
另外选择节点的最终标准是信息增益【表示特征X使得类Y的不确定性减少的程度【熵的下降程度】】，将信息增益最大的特征作为根节点，以此类推。
第一轮：
原始数据的熵值：
yes：9个，no：5个
$-\frac{9}{14}\log _{2}^{\frac{9}{14}}-\frac{5}{14}\log _{2}^{\frac{5}{14}}=0.940$
如果按outlook分类：
sunny：yes有2个，no有3个，即取得sunny的概率为5/14
sunny类的熵值： $-\frac{2}{5}\log {{_{2}^{{}}}^{\frac{2}{5}}}-\frac{3}{5}\log {{_{2}^{{}}}^{\frac{3}{5}}}=0.971$
overcast：yes有4个，no有0个，即取得overcast的概率为4/14
overcast类的熵值：0
rainy：yes有3个，no有2个，即取得rainy的概率为5/14
rainy类的熵值： $-\frac{2}{5}\log {{_{2}^{{}}}^{\frac{2}{5}}}-\frac{3}{5}\log {{_{2}^{{}}}^{\frac{3}{5}}}=0.971$
综上，按outlook分类的熵值为【此处计算的实际是条件熵】
$\frac{5}{14}\times 0.971\text{+}\frac{4}{14}\times 0\text{+}\frac{5}{14}\times 0.971=0.693$
信息增益为0.940-0.693=0.247
同理
如果按temperature分类:
hot类：取hot的概率是4/14
熵值为： $-\frac{2}{4}\log {{_{2}^{{}}}^{\frac{2}{4}}}-\frac{2}{4}\log {{_{2}^{{}}}^{\frac{2}{4}}}=1$
mild类：取mild的概率是6/14
熵值为： $-\frac{2}{6}\log {{_{2}^{{}}}^{\frac{2}{6}}}-\frac{4}{6}\log {{_{2}^{{}}}^{\frac{4}{6}}}=0.918$
cool类：取cool的概率是4/14
熵值为： $-\frac{1}{4}\log {{_{2}^{{}}}^{\frac{1}{4}}}-\frac{3}{4}\log {{_{2}^{{}}}^{\frac{3}{4}}}=0.811$
综上，按temperature分类的熵值为
$\frac{4}{14}\times 1\text{+}\frac{6}{14}\times 0.918\text{+}\frac{4}{14}\times 0.811=0.911$
信息增益为0.940-0.911=0.029
按humidity分类：
normal类：取normal的概率是7/14
熵值为： $-\frac{1}{7}\log {{_{2}^{{}}}^{\frac{1}{7}}}-\frac{6}{7}\log {{_{2}^{{}}}^{\frac{6}{7}}}=0.592$
high类：取high的概率是7/14
熵值为： $-\frac{4}{7}\log {{_{2}^{{}}}^{\frac{4}{7}}}-\frac{3}{7}\log {{_{2}^{{}}}^{\frac{3}{7}}}=0.985$
综上，按humidity分类的熵值为
$\frac{7}{14}\times 0.592\text{+}\frac{7}{14}\times 0.985=0.7885$
信息增益为0.940-0.7885=0.1515
按windy分类：
True类：取True的概率是6/14
熵值为： $-\frac{1}{2}\log {{_{2}^{{}}}^{\frac{1}{2}}}-\frac{1}{2}\log {{_{2}^{{}}}^{\frac{1}{2}}}=1$
False类：取False的概率是8/14
熵值为： $-\frac{2}{8}\log {{_{2}^{{}}}^{\frac{2}{8}}}-\frac{6}{8}\log {{_{2}^{{}}}^{\frac{6}{8}}}=0.811$
综上，按windy分类的熵值为
$\frac{6}{14}\times 1\text{+}\frac{8}{14}\times 0.811=0.892$
信息增益为0.940-0.892=0.048
根据信息增益比最大的原则，选择特征outlook为根节点。
现在的决策树长这样：

绘图1.jpg

由上图可知，当outlook等于overcast，可以得出肯定会去打球的结论，不需要再切分，下面对sunny和rainy继续切分
第二轮：
sunny类：当前样本的熵值等于
按temperature分类：熵为0.4，信息增益0.571
按humidity分类：熵为0，信息增益0.971
按windy分类：熵为0.811，信息增益0.16
选择特征humidity为节点
rainy类：当前样本的熵值等于当前样本的熵值等于
按temperature分类：熵为0.9508，信息增益0.0202
按humidity分类：熵为0.9508，信息增益0.0202
按windy分类：熵为0，信息增益0.971
选择特征windy为节点
现在的决策树长这样：

绘图1.jpg

最终生成5个叶子节点
但是ID3算法会偏向于取值较多的特征：当特征取值较多时，分类结果的纯度较高，不确定性越低，熵值越低，信息增益比越大。
2）C4.5【信息增益比】
为了解决这个问题，引入了信息增益比指标

image.png

信息增益比等于信息增益除以自身的熵值，相当于乘了一个惩罚项，当该特征取值较多时，不确定性较高，熵值较大，它的倒数较小，信息增益比较小，被选择为节点的可能性降低。
但是，反之，当特征取值较少时，不确定性较低，熵值较低，它的倒数较高，信息增益比较大，被选择的可能性较高，因此C4.5偏向于选择特征取值较少的为节点。
上述例子如果用C4.5作为衡量标准，结果如下：
第一轮：
按outlook分类：信息增益比为

按temperature分类：信息增益比为

按humidity分类：信息增益比为

按windy分类：信息增益比为

按照薪资增益比最大原则，选择特征windy为根节点【果然选了取值较少的那个】
第二轮：
windy为true的分支：
按outlook分类的信息增益比为0.423，temperature的为0.143，humidity的为0.082，所以选择outlook为节点
windy为false的分支：
按outlook分类的信息增益比为0.299，temperature的为0.078，humidity的为0.311，
所以选择humidity为节点
此时的决策树为【但愿没算错】

绘图1.jpg

最左边和最右边的节点可以同理继续切分
3）CART【GINI系数】

image.png

以outlook和temperature为例

微信图片_20190220142714.jpg

微信图片_20190220142725.jpg

计算得出outlook的最佳切分点为{{rainy}，{sunny，overcast}}，GINI系数为0.457；
temperature的最佳切分点为{{mild}，{hot，cool}}，GINI系数为0.458
我所理解的应该是根据每个特征的最佳切分点对应的GINI系数，选择系数最小的作为节点以及切分点。
回归树
这一块在学习的时候是我觉得不太容易理解的，这里参考了https://blog.csdn.net/weixin_36586536/article/details/80468426和https://blog.csdn.net/Albert201605/article/details/81865261博主的内容

image.png

这个类似于CART算法，
首先遍历所有特征，对每一个特征的每个切分点，得到两个分支各自的标签值，计算两个分支各自的离差平方和，将这两块离差平方和之和作为这个切分点的离差平方和，将最小的离差平方和所对应的切分点为该特征的最佳切分点，以此类推，得到第一层的根节点，然后对每个分支重复执行上述步骤，直至得到最终的决策树，叶子节点输出的是该分支标签值的平均值，当有新的特征输入时，从上到下走一遍决策树，输出相应叶子节点的标签值。