传统机器学习-决策树

1-什么是决策树决策树是非参数学习算法，可以解决分类问题，天然可解决多分类问题，也可解决回归问题，具有非常好的可解释性。如何构建决策树：每个节点在哪个维度做划分，某个维度在哪个值上做划分。2-信息熵熵在信息论中代表随机变量不确定度的度量。熵越大，数据的不确定性越高；熵越小，数据的不确定性越低。其中，log是e为底的自然对数。如何构建决策树：每个节点在哪个维度...

一杯敬朝阳一杯敬月光

777人浏览 · 2020-04-01 13:31:15

一杯敬朝阳一杯敬月光 · 2020-04-01 13:31:15 发布

1-什么是决策树

决策树是非参数学习算法，可以解决分类问题，天然可解决多分类问题，也可解决回归问题，具有非常好的可解释性。

如何构建决策树：每个节点在哪个维度做划分，某个维度在哪个值上做划分。

2-信息增益

熵在信息论中代表随机变量不确定度的度量。熵越大，数据的不确定性越高（纯度越低）；熵越小，数据的不确定性越低（纯度越高）。

信息熵：

$Ent(D)=-\sum_{k=1}^{|\gamma|}p_klog(p_k) \\ example. \\ \{1/3,1/3,1/3\} & Ent(D)=-1/3log(1/3) -1/3log(1/3) -1/3log(1/3) \approx 1.0986 \\ \{1/10,2/10,7/10\} & Ent(D)=-0.1log(0.1) -0.2log(0.2) -0.7log(0.7) \approx 0.8018 \\ \{1,0,0\} & Ent(D)=-1log(1)=0$

其中，log是e为底的自然对数。

如何构建决策树：

每个节点在哪个维度做划分，某个维度在哪个值上做划分？划分后使得信息熵降低。

信息增益：

$Gain(D,a)=Ent(D) - \sum_{v=1}^V\frac{|D^v|}{|D|}Ent(D^v)$

表示用特征a对样本D进行划分获得的信息增益。其中a是共有V个不同取值的离散特征，使用特征a对样本D进行划分，会有V个分支节点，第v个节点中包含的样本数计为 $D^v$ ，则 $Ent(D^v)$ 是 $D^v$ 的信息熵，考虑不同的分支节点包含的样本数不同，给分支节点赋予不同权重 $|D^v|/|D|$ ，即样本数越多的分支节点的影响越大。一般而言，信息增益越大，即使用a进行划分获得的“纯度提升”最大，ID3就是以信息增益 $a_*={argmax}_{a \in A}Gain(D,a)$ 为准则来选择划分属性。

增益率：

ID3采用最大信息增益。信息增益对可取数目较多的属性有所偏好，增益率对对可取数目较少的属性有所偏好。C4.5综合了这两种，采用启发式，先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择信息增益率最高的。

$Gain\_ration(D,a)=\frac{Gain(D,a)}{IV(a)}$ ，其中 $IV(a)=-\sum_{v=1}^V\frac{|D^v|}{|D|}log\frac{|D^v|}{|D|}$

属性a的可能取值数目越多（即V越大），则IV(a)的值通常越大。

3-基尼系数

基尼系数与信息熵具有同样的性质，基尼系数越大，数据的不确定性越高；基尼系数越小，数据的不确定性越低。

$Gini(D)=\sum_{k=1}^{|\gamma|}\sum_{k'\neq k}p_kp_{k'}=1-\sum_{i=1}^kp_i^2 \\ \{1/3,1/3,1/3\} & Gini(D)=1-(1/3)^2-(1/3)^2-(1/3)^2\approx 0.6666 \\ \{0.1,0.2,0.7\} & Gini(D) = 1- (0.1)^2-(0.2)^2-(0.7)^2=0.46 \\ \{1,0,0\} & Gini(D) = 1 - 1^2 -0^2-0^2=0$

直观来说，Gini(D)反应了从数据集D中随机抽取两个样本，其类别标记不一样的概率，因此Gini(D)越小，数据集纯度越高。

属性a的基尼指数：

$Gini\_index(D,a)=\sum_{v=1}^V\frac{|D^v|}{|D|}Gini(D^v)$

CART就是以基尼指数最小的特征 $a_*={argmin}_{a \in A}Gini\_index(D,a)$ 为准则来选择划分属性。

信息熵VS基尼系数：

信息熵的计算比基尼系数稍慢（lg是非线性的关系）

大多数情况下，没有特别的效果优劣。

4-CART与决策树中的超参数

CART：Classification And Regression Tree

特点：根据某一个维度d和某一个阈值v进行二分。

预测复杂度：由于是二叉树，平均情况下将样本对半分，树高logm，则预测O(logm)；

训练复杂度：由于每次划分均遍历所有特征与阈值，故有n*m，且树高logm，则训练O(nmlogm)。

超参数：

1）树深：max_depth；2）一个节点至少有多少个样本我们才对这个节点继续划分：min_samples_split；3）对于叶子节点至少应该有几个样本：min_samples_leaf；4）最多有多少个叶子节点：max_leaf_nodes。

ID3

最大信息增益，特征取值越多意味着确定性越高，故对可取数目较多的属性有所偏好
只能处理离散型变量
多叉
特征在层级间不可复用
只能用于分类
对缺失值敏感

C4.5

最大信息增益比
可处理连续特征，通过排序找到类别不同的分割线作为切分点，依据切分点将连续属性转换为布尔型，将连续变量转换为多个取值区间的离散型变量
多叉
特征在层级间不可复用
只能用于分类
对缺失值进行了处理

CART

基尼指数
可处理连续特征，对特征进行二值划分，可以很好的适用于连续变量
二叉树
特征在层级间可复用
分类和回归均可
对缺失值进行了处理

5-决策树解决回归问题

6 - 剪枝处理

预剪枝：是在决策树生成过程中，如果这个节点进行划分，不能带来泛化性能的提升，则停止划分并将该节点设置为叶子节点。

优点：
预剪枝使得决策树很多分支都没有“展开”，这不仅降低了过拟合的风险，还显著减少来决策树的训练时间开销和测试时间开销。
缺点：
虽然某次划分可能并不能带来性能上的提升，但是后序的划分可能会带来性能上的提升；预剪枝基于“贪心”的本质给决策树带来欠拟合的风险。

后剪枝：则是先训练好一棵树，然后自底向上对非叶子节点进行考察，如果将该节点对应的子树替换为叶节点能不能带来泛化性能的提升，能就将该子树替换为叶节点。

优点：
后剪枝通常比预剪枝保留更多的分支，所以后剪枝决策树的欠拟合风险较小，泛化性能往往犹豫预剪枝决策树。
缺点：
因为在生成了完整的决策树后进行，所以其训练开销高于预剪枝决策树。

7-连续值与缺失值

连续值

将连续值离散化，最简单的策略是二分法，这也正是C4.5中采用的机制，例如给定样本集D和特征a，a是连续值且有n个不同的值，可将这n个值由小到大排序，计为 $\{a^1, a^2, \cdots, a^n\}$ ，选取划分点t，将D划分为子集 $D^-_t$ （该子集中a的取值均 $\leqslant t$ ）和 $D^+_t$ （该子集中a的取值均 $>t$ ）,对a我们考察n-1个元素的候选划分点集合。需要注意，与离散属性不同，若当前节点划分属性为连续属性，该属性还可作为其后代节点的划分属性（这一点也好理解，离散属性我们的划分用到了每一个值，即离散属性的每一个取值都对应着一个节点，用到了全部的信息；而连续属性离散化后，相当于该属性在此刻只有两个取值，大于等于t的和小于t的，并没有用到全部取值信息，后面可使用也应该）。

缺失值

对于缺失值的处理我们主要考虑两个问题：

如何在属性存在缺失的情况下，选择划分属性。
给定划分属性，如何对该属性有缺失的样本进行划分。

下面给出C4.5关于这两个问题的解决方法。

对于问题1，我们仅依据不存在缺失值的那些样本来判断属性a的优劣，公式表达如下：

$\begin{aligned} Gain(D,a) &= \rho \times Gain( \widetilde{D},a) \\ &= \rho \times (Ent( \widetilde{D}) - \sum_{v=1}^V \widetilde{r}_vEnt( \widetilde{D}^v)) \end{aligned}$

$\begin{aligned} \rho &= \frac{\sum_{x \in \widetilde{D}} w_x}{\sum_{x \in D} w_x} \\ \widetilde{p}_k &= \frac{\sum_{x \in \widetilde{D}_k} w_x}{\sum_{x \in \widetilde{D}} w_x} \ \ (1 \leqslant k \leqslant |\gamma|) \\ \widetilde{r}_v &= \frac{\sum_{x \in \widetilde{D}_v} w_x}{\sum_{x \in \widetilde{D}} w_x} \ \ (1 \leqslant v \leqslant V) \\ Ent(\widetilde{D}) &= -\sum_{k=1}^{|\gamma|}\widetilde{p}_klog\widetilde{p}_k \end{aligned}$

其中，训练集D，属性a； $\widetilde{D}$ 表示D中在属性a上没有缺失值的样本子集，我们通过 $\widetilde{D}$ 来判断属性a的优劣。 $w_x$ 是每个样本 $x$ 的权重，初始阶段，根节点中每个样本的权重初始化为1。对于属性a， $\rho$ 表示无缺失值的样本所占的比例； $\widetilde{p}_k$ 表示无缺失值样本中第k类所占的比例； $\widetilde{r}_v$ 表示无缺失值样本中在属性a上取值 $a^v$ 的样本所占的比例。总体而言，就是在无缺失值样本的计算后添加了占比系数作为权重。

对于问题2：

若样本 $x$ 在划分属性a上的取值已知，则将 $x$ 划入与其取值对应的子结点，且样本权值在子结点中保持为 $w_x$
若样本 $x$ 在划分属性a上的取值未知，则将 $x$ 同时划入所有子结点，且样本权值在与属性值 $a^v$ 对应的子结点中调整为 $\widetilde{r}_v \cdot w_x$ ，直观来看就是让同一样本以不同的概率划分到子结点中（即可看到许多子结点中有同一样本，只是带的权重大小不一样）。