大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

决策树原理及其应用

##决策树的原理
我们先构造一颗简单的决策树来玩一玩。举一个不恰当的例子：小明过年回家，老妈催着他结婚，帮着张罗相亲对象。有三个女孩的资料（简称A、B、C）。
关于A:
小明问:“身材好吗？”，妈妈说：“好！”，小明说：“见一面”
关于B:
小明问:“身材好吗？” ， 妈妈说：“不好！”，小明又问：“漂亮吗？”，
妈妈说：“漂亮！”，小明说：“见一面”
关于C:
小明问:“身材好吗？” ， 妈妈说：“不好！”，小明又问：“漂亮吗？”，妈妈说：“不漂亮”，小明又问：“会写代码吗？”，妈妈说：“会”，小明说：“见一面”。

我们构造出小明相亲的决策树如下：

在这里 优先级顺序是 身材 > 颜值 > 编程能力。这个时候就会疑惑，这个“优先级”是怎么决定的呢？在决定是否去相亲的因素有很多，工作地点的距离（我编不出来了）etc…，我们是否要每一个因素都去考虑？如果你有这方面的疑惑，恭喜你！如果在1984，提出CART算法的人可能不是Breiman了。这三个问题涉及到决策树中的特征选择，决策树的生成，决策树的修剪，一堆扯淡的引入到此为止。

下面是某相亲网上约会成功的数据：

以上数据改编自 李航《统计学习方法》

1. 特征选择
   特征选择是根据所给数据来决定用哪个特征来对数据进行分类，当然是按特征的分类能力强弱来对数据进行分类，下面我们来讲一讲如何评判特征的分类能力。
   先看一看是否有房这一栏和类别的关系，在有房的情况下，类别为是的一共有6组数据;在没有房的情况下，类别为否的一共有6组数据，是否有房和是否约会成功一致的一共有12组数据。再看一看是否有工作和是否约会成功一致的数据，发现一共有11组数据。“12>11”感觉上“是否有房子”比“是否有工作”的分类能力要强一些，到底是不是这样呢？下面我们用精确的数学语言来解释一下。
   我们这里引入三个信息论的概念熵、条件熵、信息增益、信息增益比。
   熵 表示随机变量不确定性的度量。设$X$是一个取有限个值的随机变量，其分布为: $P(X=x_i)=p_i,i=1,2,...,n$
   则随机变量$X$的熵定义为:
   $H(X)=-{\sum }_{i=1}^n{p}_{i}log{p}_i$

例子: 随机变量是年龄
$P(x_1= 青年) = \frac{5}{15}; P(x_2 = 中年) = \frac{5}{15};P(x_3 = 老年) = \frac{5}{15} $
$H(X)=-(\frac{5}{15}log\frac{5}{15}+\frac{5}{15}log\frac{5}{15}+\frac{5}{15}log\frac{5}{15})$

**条件熵 **$H(Y|X)$表示在已知随机变量$X$的条件下随机变量$Y$的不确定性，定义为:
$H(Y|X)={\sum }_{i=1}^n{p}_{i}H(Y|X=x_i)$ ,这里$ p_i=P(X = x_i) , i=1,2,…,n$

例子：随机变量$Y$为类别，随机变量$X$为年龄

$H(Y|X)=\frac{5}{15}H(Y|x_1=青年)+\frac{5}{15}H(Y|x_2=中年)+\frac{5}{15}H(Y|x_3=老年)$

$H(Y|x_1=青年)=-{\sum }_{i=1}^{n}p(x=青年，y_i)logp(y_i|x=青年)$
$H(Y|x_1=中年)=-{\sum }_{i=1}^{n}p(x=中年，y_i)logp(y_i|x=中年)$
$H(Y|x_1=老年)=-{\sum }_{i=1}^{n}p(x=老年，y_i)logp(y_i|x=老年)$

$H(Y|x_1=青年)=-\frac{3}{5}log\frac{3}{5}-\frac{2}{5}log\frac{2}{5}$
$H(Y|x_2=中年)=-\frac{2}{5}log\frac{2}{5}-\frac{3}{5}log\frac{3}{5}$
$H(Y|x_3=老年)=-\frac{1}{5}log\frac{1}{5}-\frac{4}{5}log\frac{4}{5}$

$H(Y|X)=\frac{5}{15}H(Y|x_1=青年)+\frac{5}{15}H(Y|x_2=中年)+\frac{5}{15}H(Y|x_3=老年)\approx 0.888$

信息增益$即是g(Y,X)=H(Y)-H(Y|X),g(Y,X)为特征X的信息增益$
终于讲完了这三个概念，我们一起来算一算$g(Y,X_1),g(Y,X_2)$，其中$X_1是特征是否有房子，X_2是特征是否有工作$。
$g(Y,X_1)=H(Y)-H(Y|X_1)$
$H(Y)=-\frac{9}{15}log\frac{9}{15}-\frac{6}{15}log\frac{6}{15}=0.971$
$H(Y|X_1)=\frac{10}{15}H(Y|x_1=否)+\frac{5}{15}H(Y|x_2=是)$
$H(Y|x_1=否)=-\frac{6}{10}log\frac{6}{10}-\frac{4}{10}log\frac{4}{10}$
$H(Y|x_2=是)=-\frac{5}{5}log\frac{5}{5}$
$H(Y|X_1)=\frac{10}{15}(-\frac{6}{10}log\frac{6}{10}-\frac{4}{10}log\frac{4}{10})+\frac{5}{15}\times 0$
$g(Y|X_1)=0.971-[\frac{10}{15}(-\frac{6}{10}log\frac{6}{10}-\frac{4}{10}log\frac{4}{10})+\frac{5}{15}\times 0]=0.324$

$g(Y,X_2)=H(Y)-H(Y|X_2)$
$H(Y|X_2)=\frac{9}{15}H(Y|x_1=否)+\frac{6}{15}H(Y|x_2=是)$
$H(Y|x_1=否)=-\frac{6}{9}log\frac{6}{9}-\frac{3}{9}log\frac{3}{9}$
$H(Y|x_2=是)=-\frac{6}{6}log\frac{6}{6}$
$H(Y|X_2)=\frac{9}{15}(-\frac{6}{9}log\frac{6}{9}-\frac{3}{9}log\frac{3}{9})+\frac{6}{15}(-\frac{6}{6}log\frac{6}{6})$
$g(Y|X_2)=0.971-[\frac{9}{15}(-\frac{6}{9}log\frac{6}{9}-\frac{3}{9}log\frac{3}{9})+\frac{6}{15}(-\frac{6}{6}log\frac{6}{6})]=0.420$

这里$g(Y|X_1)<g(Y|X_2)$所以特征“是否有房子”的分类能力强于“是否有工作”，然后按给出的方法计算出每一个特征的增益值，就可以进行下一步啦。
信息增益比
特征$A$对训练数据集$D$的信息增益比$g_R(D,A)$定义为其信息增益$g(D,A)$与训练数据集$D$关于特征$A$的值的熵$H_A(D)$之比，即
$g_R(D,A)=\frac{g(D,A)}{H_A(D)}$
其中$H_A(D)=-{\sum }_{i=1}^n\frac{|D_i|}{|D|}lo{g}_2\frac{|D_i|}{|D|}$，其中$n是特征A取值的个数$
2. 决策树生成
在sklearn中介绍了三种决策树生成算法ID3、C4.5、C5.0、CART，我们简单介绍一下这几中算法的原理。

输入：训练数据集$D$,特征集$A$，阈值$ϵ$
输出：决策树T

ID3:
（1）如果数据集中所有实例都属于同一类$C_k$（$y_i,i=1,2,..,n$，$y_i=C_k$），则$T$为单节点树，并将类$C_k$作为该节点的标记，返回$T$;
（2）如果$A=\varnothing$，则$T$为单节点树，并将$D$中实例数的最大类$C_k$作为该节点的标记，返回$T$;
（3）否则，计算$A$中各特征对$D$的信息增益，选择信息增益最大的特征$A_g$;
（4）如果$A_g$的信息增益小于阈值$ϵ$,则$T$为单节点树，并将$D$中实例数的最大类$C_k$作为该节点的标记，返回$T$;
（5）否则，对$A_g$的每一可能值$a_i$,依$A_g=a_i$将$D$分割为若干非空子集$D_i$，将$D_i$中实例数最大的类作为标记，构建子节点，由节点及其子节点构成树$T$，返回$T$.
（6）对第$i$个子节点，以$D_i$为训练集，以$A-A_g$为特征集，递归地调用(1)~(5)，得到子树$T_i$，返回$T_i$。

C4.5
C4.5和ID3类似，只在特征选择上不同，其他都是一样的，ID3用信息增益来选择特征，而C4.5用信息增益比来选择特征。C4.5是ID3的改进，既然是改进，说明信息增益比作为特征选择的比信息增益更合理。大概是因为信息增益趋向于选择取值比较多的特征。具体原因在这里

C5.0
在C4.5的基础上有所改进，它不是开源的。这里说它的运行速度比C4.5更快，所需要的内存比C4.5更小，和C4.5很相似，不过C5.0会建立更多的深度较小的决策树，在同样的数据集下的准确率和C4.5类似，等等。

CART
建议先看完决策树剪枝，在来看CART算法

3.决策树剪枝
不想写了。。。。