• 决策树详解

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

    目录

    一、数学基础

    1、信息熵

    2、信息增益

    二、决策树的组成

    1、决策节点

    2、叶子节点

    3、决策树的深度

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

     1、计算根节点的信息熵

    2、计算属性的信息增益

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

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

    1、引入原因

    2、定义

    3、例子

    4、注意点

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

    1、定义

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

    六、剪枝处理

    1、提出原因

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

    3、预剪枝

    4、后剪枝

    七、连续与缺失值

    1、连续值处理

    2、缺失值处理

    八、多变量决策树

    九、python实现

    一、数学基础

    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。

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

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

    根据以下信息构建一棵预测是否贷款的决策树。我们可以看到有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})

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

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

    六、剪枝处理

    1、提出原因

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

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

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

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

    3、预剪枝

    （1）做法

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

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

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

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

    所以需要划分，不剪枝。

    （3）优缺点

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

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

    4、后剪枝

    （1）做法

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

    （2）优缺点

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

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

    七、连续与缺失值

    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*收入

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

    九、python实现

    1. from sklearn.datasets import load_iris
    2. from sklearn.model_selection import train_test_split
    3. from sklearn.metrics import accuracy_score
    4. from sklearn import tree
    5.  
    6. iris = load_iris()#数据集导入
    7. features = iris.data#属性特征
    8. labels = iris.target#分类标签
    9. train_features, test_features, train_labels, test_labels = train_test_split(features, labels, test_size=0.3, random_state=1)#训练集，测试集分类
    10. clf = tree.DecisionTreeClassifier(criterion='entropy',max_depth=3)
    11. clf = clf.fit(train_features, train_labels)#X,Y分别是属性特征和分类label
    12. test_labels_predict = clf.predict(test_features)# 预测测试集的标签
    13. score = accuracy_score(test_labels, test_labels_predict)# 将预测后的结果与实际结果进行对比
    14. print("CART分类树的准确率 %.4lf" % score)# 输出结果
    15. 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'文件对应的决策树图片

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

  • 相关阅读:
    Linux学习笔记之编译相关篇(2)_静态链接与动态链接
    Python从入门到入土-进阶语法
    10-11 周三 shell xargs tr curl 做大事情
    真的假的？NVIDIA研究在人工智能帮助下瞬间将2D照片转化为3D场景
    数据结构——克鲁斯卡尔（Kruskal）算法
    Flutter 小白之旅---基础知识篇
    python-爬虫（可直接使用）
    [附源码]JAVA毕业设计敬老院管理系统（系统+LW）
    linux 修改用户的密码
    图像检测：医疗影像分割
  • 原文地址：https://blog.csdn.net/weixin_55073640/article/details/125826023