统计学习算法——决策树

内容来自B站Up主：风中摇曳的小萝卜https://www.bilibili.com/video/BV1ar4y137GD，仅为个人学习所用。

问题引入

有15位客户向某银行申请贷款，下面是他们的一些基本信息，类别列表示是否通过贷款申请，是表示通过贷款申请，否表示未通过贷款申请。

某银行想，这样做工作量太大，有没有方法能够快速判断一个用户的贷款申请通过不通过呢？

决策树

以工作为标准进行划分，发现有工作的全部被批准，而没有工作的只有4位被批准，得出结论：有工作的被批准，这显然和样本结果不符合。

若使用两个标准，首先考虑工作因素划分，然后将分类不当的继续按照信誉划分，如下图

得出结论：客户有工作可以直接批准；若没有工作，继续查看其信誉。若信誉非常好，可以批准，否则拒绝。这就是构建了一个决策树。

虽然按照决策树进行判断很方便，但是如何确定按什么标准进行划分呢？

基尼系数

基尼系数是一种衡量数据集纯度的指标。基尼系数越小，表明该节点包含的样本越可能属于同一类别，纯度越高；基尼系数越大，表明样本的类别越混杂，纯度越低。

计算公式为：$$Gini(D)=1-\sum _{k=1}^K{p}_k^2$$
用1减去所有事件概率的平方。本例中，代入公式有 $1-p(批准{)}^2-p(不批准{)}^2$。

• 当批准的概率，被批准的概率分别为1和0时，基尼系数为0；
• 当批准的概率，被批准的概率分别为0和1时，基尼系数为0；
• 当批准的概率，被批准的概率分别为0.5和0.5时，基尼系数为0.5。

由此图可以看出，当一定被批准或拒绝时，基尼系数为0；当批准或拒绝不确定，概率为0.5时候，基尼基数达到最大。一般选择基数小的作为决策树下一级分类的标准。

对于本例，不考虑任何标准，只看最后的结果。15份申请中有9份通过，6份未通过。计算基尼系数

根据上图，这是个很大的值，说明数据类似于随机生成。

考虑有工作的客户，5位客户有工作，5人通过，0人未通过，计算基尼系数

考虑没有工作的客户，10位无工作，4位通过，6人未通过，计算基尼系数

计算以工作为标准的基尼系数，进行加权平均计算

同理，计算其他标准的基尼系数

发现，以房子为标准，基尼系数最小，按照此标准来构建决策树。

左侧被分类很好，继续分类右边。

接下来按照无房子继续计算概率。无房子的客户有9位，其中被批准的3位，未通过的6位，计算基尼系数

无房子且有工作的3位，通过批准的3位，未通过批准的0位；无工作的6位，通过批准的0位，未通过批准的6位。计算工作的基尼系数
$$Gini(工作，是)=1-(\frac{3}{3}{)}^2-0=0$$
$$Gini(工作，否)=1-(\frac{6}{6}{)}^2-0=0$$
$$Gini(工作)=\frac{3}{9}\ast 0+\frac{6}{9}\ast 0=0$$

无房子，信誉非常好的1位，通过批准的1位，未通过批准的0位；信誉好的4位，通过批准的2位，未通过批准的2位；信誉一般的4位，通过批准的0位，未通过批准的4位。计算基尼系数

$$Gini(信誉，非常好)=1-(\frac{1}{1}{)}^2-0=0$$
$$Gini(信誉，好)=1-(\frac{2}{4}{)}^2-(\frac{2}{4}{)}^2=0.5$$
$$Gini(信誉，一般)=1-(\frac{4}{4}{)}^2-0=0$$
$$Gini(信誉)=\frac{1}{9}\ast 0+\frac{4}{9}\ast \frac{1}{2}+\frac{4}{9}\ast 0=0.22$$

通过上述计算可知，应该选择是否有工作作为下一级的分类标准。

这是由基尼系数得出的决策树，称为CART决策树。

生成的决策树一般是二叉树。

决策树的生成容易造成过拟合问题，需要进行剪枝。