决策树详解

tt丫

26014人浏览 · 2022-07-20 15:23:06

tt丫 · 2022-07-20 15:23:06 发布

入门小菜鸟，希望像做笔记记录自己学的东西，也希望能帮助到同样入门的人，更希望大佬们帮忙纠错啦~侵权立删。

三、决策树的建立(基于信息增益）—— ID3

1、计算根节点的信息熵

2、计算属性的信息增益

3、接下来我们继续重复1，2的做法继续寻找合适的属性节点

四、决策树的另一划分标准——增益率（C4.5决策树算法）

五、决策树的另一划分标准——基尼指数（CART决策树）

5、另外一种剪枝方法——在生成决策树后通过极小化决策树整体的损失函数来实现

一、数学基础

1、信息熵

（1）基本定义

假设样本集合D共有N类，第k类样本所占比例为 $p_{k}$ ，则D的信息熵为： $H(D) = -\sum_{k=1}^{N}p_{k}log_{2} p_{k}$

信息熵描述的是事件在结果出来之前对可能产生的信息量的期望，描述的是不确定性。

信息熵越大，不确定性越大。H(D)的值越小，则D的纯度越高。

注：

（1）计算信息熵时约定 : 如果 p = 0,则 $p\log_{2}p$ = 0

（2）Ent(D)的最小值是0,最大值是 $log_{2}N$

如下图所示——二元信源熵函数（ $H(0.5)=1;H(0)=H(1)=0$ ）：

（2）条件熵

$H(Y|X)=\sum_{i}P(X=i)H(Y|X=i)$

（3）有关定律

🌳 $H(X,Y)=H(X|Y)+H(Y)=H(Y|X)+H(X)$

🌳若X，Y相互独立， $H(Y|X)=H(Y)$

🌳H(Y|Y)=0

2、信息增益

信息增益是一个统计量，用来描述一个属性区分数据样本的能力。信息增益越大，那么决策树就会越简洁。这里信息增益的程度用信息熵的变化程度来衡量。公式如下：

$IG(Y|X)=H(Y)-H(Y|X)\geqslant 0$

二、决策树的组成

1、决策节点

通过条件判断而进行分支选择的节点。如：将某个样本中的属性值(特征值)与决策节点上的值进行比较，从而判断它的流向。

2、叶子节点

没有子节点的节点，表示最终的决策结果。

3、决策树的深度

所有节点的最大层次数。

决策树具有一定的层次结构，根节点的层次数定为0，从下面开始每一层子节点层次数+1。

决策树的学习一般包括：特征选择，决策树的生成，决策树的修建。

三、决策树的建立(基于信息增益）—— ID3

咱们还是以一个例子来吧，方便些

根据以下信息构建一棵预测是否贷款的决策树。我们可以看到有4个影响因素：职业，年龄，收入和学历。

1、计算根节点的信息熵

“是”占 $\frac{2}{3}$ ；“否”占 $\frac{1}{3}$

$H(D)= -(\frac{2}{3}log_{2}\frac{2}{3}+\frac{1}{3}log_{2}\frac{1}{3})\approx 0.933$

2、计算属性的信息增益

（1）职业

H("职业") = $-\frac{1}{3}(\frac{1}{2}log_{2}\frac{1}{2}+\frac{1}{2}log_{2}\frac{1}{2})-\frac{2}{3}(\frac{3}{4}log_{2}\frac{3}{4}+\frac{1}{4}log_{2}\frac{1}{4}) \approx 0.867$

IG(D,"职业") = H(D) - H("职业") = 0.066

（2）年龄（以35岁为界）

H("年龄") = $-2\times \frac{1}{2}(\frac{2}{3}log_{2}\frac{2}{3}+\frac{1}{3}log_{2}\frac{1}{3})\approx 0.933$

IG(D,"年龄") = H(D) - H("年龄") = 0

（3）收入（以10000为界）

H("收入") = $-\frac{2}{3}(\frac{1}{2}log_{2}\frac{1}{2}+\frac{1}{2}log_{2}\frac{1}{2})-\frac{1}{3}(1log_{2}1+0log_{2}0)$ $= -\frac{2}{3}(\frac{1}{2}log_{2}\frac{1}{2}+\frac{1}{2}log_{2}\frac{1}{2})\approx 0.667$

IG(D,"收入") = H(D) - H("收入") = 0.266

（4）学历（以高中为界）

H("学历") = $- \frac{2}{3}(\frac{1}{2}log_{2}\frac{1}{2}+\frac{1}{2}log_{2}\frac{1}{2})\approx 0.667$

IG(D,"学历") = H(D) - H("学历") = 0.266

选择信息增益最大的属性作为划分属性，即选择“收入”

3、接下来我们继续重复1，2的做法继续寻找合适的属性节点

确定第二个属性节点

🌳步骤一：“是”占 0.5；“否”占 0.5，因此H=1

🌳步骤二：

很显然，当学历在高中及以上时，是否贷款为否；当学历在高中以下时，是否贷款为是。

所以不用再算了，直接得出

这样决策树就建好了。

四、决策树的另一划分标准——增益率（C4.5决策树算法）

1、引入原因

还是以上面的例子，我们可以看到“学历”一栏如果我们没有进行分区，则会产生6个分支，每个分支节点仅包含一个样本。但这样的决策树不具有泛化能力，无法对新样本进行有效预测。

信息增益准则对可取值数目较多的属性有所偏好（偏向于选择取值较多的特征），为减少这种偏好可能带来的不利影响，有些决策树算法不以信息增益作为最优划分属性的选择依据，而选择增益率。

2、定义

$IG\_ratio(D,a) = \frac{IG(D,a)}{IV(a)}$

其中 $IV(a)=-\sum_{v=1}^{V}\frac{|D^{v}|}{|D|}log_{2}\frac{|D^{v}|}{|D|}$ 被称为属性a的“固有值”

属性a的取值有 $\left\{a^{1}, a^{2}, \ldots, a^{V}\right\}$ ，其中 $D^{v}$ 表示D中所有在属性a上取值为 $a^{v}$ 的样本集合。

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

3、例子

拿上面的例子——计算“收入”的信息增益率

上面已经求得

H("收入") = $-\frac{2}{3}(\frac{1}{2}log_{2}\frac{1}{2}+\frac{1}{2}log_{2}\frac{1}{2})-\frac{1}{3}(1log_{2}1+0log_{2}0)$ $= -\frac{2}{3}(\frac{1}{2}log_{2}\frac{1}{2}+\frac{1}{2}log_{2}\frac{1}{2})\approx 0.667$

IG(D,"收入") = H(D) - H("收入") = 0.266

IV("收入") = $-(\frac{2}{3}log_{2}\frac{2}{3}+\frac{1}{3}log_{2}\frac{1}{3})\approx 0.933$

$IG\_ratio(D,a) = \frac{0.266}{0.933}=0.285$

4、注意点

增益率准则对可取值数目较少的属性有所偏好。

因此基于增益率的决策树建立方法：先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的（而非直接用增益率作为比对标准）。

五、决策树的另一划分标准——基尼指数（CART决策树）

1、定义

（1）基尼值

$Gini(D) = 1-\sum_{k=1}^{N}p_{k}^{2}$

Gini(D)反映了从数据集D中随机抽取两个样本，其类别标记不一致的概率，表示数据集整体的不确定性。

Gini(D)越小，数据集D的纯度越高，不确定性越小。

（2）基尼指数

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

表示经a分割后数据集D的不确定性。

2、决策树建立方法（分类回归均可用）

分类：在侯选属性集合中，选择那个是的划分后基尼指数最小的属性为最优划分属性。

回归：用平方误差最小化准则

六、剪枝处理

1、提出原因

决策树分支可能过多，以致于把训练集自身的一些特征当作所有数据都具有的一般性质而导致过拟合。决策树越复杂，过拟合的程度会越高。因此我们主动去掉一些分支来降低过拟合的风险。

2、剪枝与其处理基本策略

（1）剪枝：剪枝是指将一颗子树的子节点全部删掉，根节点作为叶子节点。

（2）基本策略：预剪枝和后剪枝

3、预剪枝

（1）做法

在决策树生成的过程中，每个决策节点原本是按照信息增益、信息增益率或者基尼指数等纯度指标，按照值越大，优先级越高来排布节点。由于预剪枝操作，所以对每个节点在划分之前要对节点进行是否剪枝判断，即：使用验证集按照该节点的划分规则得出结果。若验证集精度提升，则不进行裁剪，划分得以确定；若验证集精度不变或者下降，则进行裁剪，并将当前节点标记为叶子节点。
（2）具体例子

比如上述例子中的“学历”

我们选取第5个样本为验证集

若不划分：验证集精度为50%（一半是，一半否）；若划分：验证集精度100%。

所以需要划分，不剪枝。

（3）优缺点

🎈优点：预剪枝使得决策树很多相关性不大的分支都没有展开，这不仅仅降低了过拟合的风险，还显著减少了决策树的训练时间开销和测试时间开销。

🎈缺点：有些分支的当前划分虽不能提升泛化能力，甚至可能导致泛化能力暂时下降，但是在其基础上进行的后续划分却有可能提高性能。预剪枝基于“贪心”本质禁止这些分支展开，给预剪枝决策树带来了欠拟合的风险。

4、后剪枝

（1）做法

已经通过训练集生成一颗决策树，然后自底向上地对决策节点(非叶子结点)用测试集进行考察，若将该节点对应的子树替换为叶子节点能提升验证集的精确度（这个的算法与预剪枝类似），则将该子树替换成叶子节点，该决策树泛化能力提升。

（2）优缺点

🎈优点：后剪枝决策树通常比预剪枝决策树保留了更多的分支。一般情况下，后剪枝决策树的欠拟合风险很小，泛化能力往往优于预剪枝决策树。

🎈缺点：后剪枝过程是在生成完决策树之后进行的，并且要自底向上地对树中的所有决策节点进行逐一考察，因此其训练时间开销比未剪枝的决策树和预剪枝决策树都要大得多。

5、另外一种剪枝方法——在生成决策树后通过极小化决策树整体的损失函数来实现

$C_{\alpha }(T) = \sum_{t=1}^{|T|}N_{t}H_{t}(T)+\alpha |T| = C(T) +\alpha |T|$

其中，|T| 是树的叶结点个数；t 是树的叶结点； $N_{t}$ 是叶结点 t 上的样本点数目； $H_{t}(T)$ 为叶结点 t 上的经验熵； $\alpha$ 为控制参数

上式的意思是： $C(T)$ 是模型对训练数据的预测误差，即模型与训练数据的拟合程度；|T| 表示模型的复杂度； $\alpha$ 控制对模型复杂度的惩罚情况，就有点像正则化那个思路。

这个损失函数是针对训练数据集的。

🌳具体实现过程

（1）递归地从树的叶结点向上回缩；

（2）回缩到父节点前与后的整体树分别为 $T_{B}$ 和 $T_{A}$ ，其对应的损失函数值分别为 $C_{\alpha }(T_{B})$ 和 $C_{\alpha }(T_{A})$ ，如果 $C_{\alpha }(T_{A})\leq C_{\alpha }(T_{B})$ ，则进行剪枝，即将父结点变为新的叶结点；

（3）返回（1），直到不能继续为止，得到损失函数最小的子树。

七、连续与缺失值

1、连续值处理

（1）提出原因

看看我们上面的例子，有些属性取值是离散的，有些是连续的。连续属性的可取值数目不是有限的，所以不能直接根据连续属性的可取值来对节点进行划分。

（2）做法——连续属性离散化技术

最简单的方法是二分法。

🌳提取划分节点的所有可能

给定样本集D和连续属性a，假设a在D中出现了n个不同的取值，将这些值从小到大进行排序，记为 $\left\{a^{1}, a^{2}, \ldots, a^{n}\right\}$ 。划分点选取公式为： $\mathrm{T}_{\mathrm{a}}=\left\{\frac{\mathrm{a}^{i}+\mathrm{a}^{\mathrm{i}+1}}{2} \mid 1 \leqslant \mathrm{i} \leqslant \mathrm{n}-1\right\}$ （一共有n-1个划分点）。

🌳选择最佳划分节点

拥有n-1个划分节点后，需要选取最佳划分点，则又可以像离散属性那样考察这些划分点。比如说计算信息增益，哪个划分节点得到的信息增益最大就选哪个。

2、缺失值处理

（1）提出原因

在样本获得的过程中，难免会因某些原因致使最后拿到的样本集出现某些属性数据的缺失。

（2）做法

当缺失的数据非常少时，一般直接舍弃掉那些缺失的数据；而当缺失的数据较多时，简单舍弃则是对样本的极大浪费，则按照一定的方法进行处理。

🌳当缺失的数据较多时：

对信息增益的计算公式进行修改：

$\begin{aligned} \operatorname{IG}(\mathrm{D}, \mathrm{a}) &=\rho \times \operatorname{IG}(\tilde{\mathrm{D}}, \mathrm{a}) &=\rho \times\left(\operatorname{H}(\tilde{\mathrm{D}})-\sum_{\mathrm{i}=1}^{\mathrm{k}} \frac{\left|\tilde{\omega}_{\mathrm{i}}\right|}{|\tilde{\omega}|} \operatorname{H}\left(\tilde{\mathrm{D}}_{\mathrm{i}}\right)\right) \end{aligned}$

其中：

D表示整个样本， $\widetilde{D}$ 表示不包含缺失值的样本；
ρ 表示完整度，为不含缺失值的样本数/总样本数；
k为该属性的取值数目；
$\frac{|\widetilde{w_{i}}|}{|\widetilde{w}|}$ 类似于以前公式中的 $\frac{|D_{i}|}{|D|}$ ，指在该属性值在所有不缺失样本中所占的比例。比如说有一个“色泽”属性，这个属性有2个取值：黑和白，共有10个样例，含缺失值的有3个。不含缺失值的样例中黑的有5个，白的有2个。那么黑的取值为 $\frac{5}{7}$ ；白的为 $\frac{2}{7}$ 。
$\operatorname{H}(\tilde{\mathrm{D}})=-\sum_{\mathrm{i}=1}^{\mathrm{k}} \tilde{\mathrm{p}}_{\mathrm{i}} \log _{2} \tilde{\mathrm{p}}_{\mathrm{i}}$

八、多变量决策树

前面研究的都是单变量决策树，即每个决策节点都只针对一个属性进行判别。对于多变量决策树，每一个决策节点，都是一个合适的线性分类器，即多个属性组合成的一组分类规则。

而这个线性分类器的构建就按照我们之前的那些分类算法进行构建（随便举个节点例子：a*年龄+b*收入<c）

这样的决策树会相对复杂，训练时间更长。

九、python实现

from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score
from sklearn import tree

iris = load_iris()#数据集导入
features = iris.data#属性特征
labels = iris.target#分类标签
train_features, test_features, train_labels, test_labels = train_test_split(features, labels, test_size=0.3, random_state=1)#训练集，测试集分类
clf = tree.DecisionTreeClassifier(criterion='entropy',max_depth=3)
clf = clf.fit(train_features, train_labels)#X,Y分别是属性特征和分类label
test_labels_predict = clf.predict(test_features)# 预测测试集的标签
score = accuracy_score(test_labels, test_labels_predict)# 将预测后的结果与实际结果进行对比
print("CART分类树的准确率 %.4lf" % score)# 输出结果
dot_data = tree.export_graphviz(clf, out_file='iris_tree.dot')#生成决策树可视化的dot文件

输出结果：

决策树的准确率 0.9556

还生成了一个'iris_tree.dot'文件。

在该目录下的终端输入以下命令：

dot -Tpng iris_tree.dot -o iris_tree.png

即可生成了一张'iris_tree.dot'文件对应的决策树图片

欢迎大家在评论区批评指正，谢谢~

GitCode 开源社区

旨在为数千万中国开发者提供一个无缝且高效的云端环境，以支持学习、使用和贡献开源项目。

更多推荐

[转载]在Windows环境下安装GNU Radio

转自：在Windows环境下安装GNURadio_恐弱智_新浪博客GNU Radio是用Python开发的，大部分开源的工程能够在Linux环境下运行良好，而Windows下却运行的很勉强，而且安装配置都很复杂。GNU Radio算是个例外了，不光提供了Windows的二进制安装，还有比较详细的说明。我是Python小白，所以折腾了好久才弄好，特意记录下来，免得以后再装还折腾。GNU Radio的

GitCode 开源社区

centOS 8 使用dnf安装Docker

DNF是什么？CentOS 8使用YUM软件包管理器版本v4.0.4。现在，该版本使用DNF(已删除YUM)。DNF是软件包管理器。它会在Linux发行版上安装，执行更新并删除软件包。使用DNF安装Docker跳过具有损坏依赖性的程序包一个有效的解决方案是使您的CentOS 8系统使用以下--nobest命令安装最符合条件的版本：sudo dnf install docker...

GitCode 开源社区

定时同步数据库表(mysql+linux+crontab)

sync.sh里面的参数需要改变，ip/username/password/database/tablesync.sh#!/bin/sh# Please change the IP and password of the data source db.# Then change the table name.filename=/home/nington/db/$(date +%Y-%m