说到决策树,大家肯定不陌生,由于其结构简单,学习成本低,且可解释性强,有着广泛的应用。
因此各类书籍、技术博客都有介绍,且深入浅出、图文并茂、生动形象。
鉴于已经有很多带图的博客介绍决策树,这里就不上图了,主要以公式推导为主。
本文主要分三块内容来介绍决策树:
- 首先会简单回顾下决策树的内容,由于这部分相对简单,大家了解的也多,因此会快速过一遍。
- 随后本文会对决策树的数学原理做详尽的剖析和推导,这也是本文的重点,做到知其然更知其所以然。
- 最后是决策树在工业应用中常见的一些形态,这部分内容在本文不做详细展开,留在后续文章中详述。
决策树的构建
通俗来讲,决策树的构建过程就是将数据根据其特征分布划分到不同的区域,使得同一个区域的样本有尽可能一致的类别标签。在决策树构建的过程中,我们需要一个衡量标准来确定每次数据划分所带来的收益,这个标准就是信息熵,以0-1二分类问题为例,衡量一个节点的信息熵公式如下:
其中p为当前节点中正样本的比例,Entropy越大,说明节点的样本越杂,因此Entropy越小越好。假设我们每次对数据划分都是将数据一分为二,分别为left和right, 分裂的收益就是分裂前节点的Entropy减去这两个节点的Entropy的加权和。即:Entropy(parent) - Prob(left) * Entropy(left) + Prob(right) * Entropy(right),这个值越大越好。这个收益,学术上我们称作“信息增益”。其中Prob(left)为左节点的样比例,Prob(right)为右节点的样本比例。
由于单纯使用信息增益作为标准来构建决策树,容易导致过拟合的问题。因此前辈们又引入了“信息增益率”,以及对树进行剪枝等方式来优化树的创建过程。这里我们只是提一下,不做更深的探讨,感兴趣的同学可以百度,Google相关内容学习。
信息熵的概率解释
上节提到的决策树构建过程,除了一个简单的信息熵公式之外,没有任何数学的元素。稍微有点编程经验的同学都可以快速编写一个决策树模型。因此我们说决策树模型简单,学习成本低。
但有些同学可能会追问,衡量数据划分收益的标准为什么是信息增益(熵的降低)而不是别的东西。或者说为什么它是靠谱的?本节,我们就来回答这个问题。过程中,我们会用到一些概率统计和微积分的基础知识。
我们还是以二分类问题为例,即样本中只有两类样本:正例(标记为“1”),负例(标记为“0”)。为了对二分类问题建模,我们需要一个假设,即假设第i个样本的模型结果pi的靠谱程度由如下公式衡量:
其中yi表示第i个样本的类标签,,通俗来讲就是假设样本类别判断正确的概率服从给定参数的二项分布,也叫伯努利分布,每个样本都服从相同的分布,且相互之间独立。这样,我们可以写出整个数据集的似然函数,也就是该二分类问题的目标函数:
模型优化的目的,或者说构建一棵决策树的目的,就是使得该公式的值尽可能的大。那这个跟我们要讨论的信息增益(熵的降低)有什么关系?
不急,我们先对目标函数两边分别取对数并取反得到:
求原函数的最大值等价于求该函数的最小值。
由于该函数对参数 的二阶导大于0恒成立,如下:
因此,这是一个有且仅有一个最小值的凸函数,为求极值对应的函数参数,只需求其一阶导等于0即可,即求 pi 使得:
根据决策树模型,整个数据集会被划分到不同的区域(叶子节点),而且被划分到同一个区域的样本的预测值相同,则我们只需对每个叶子节点求解:即可。其中pk为第k个节点的预测值,即该节点所有样本的预测值。
公式展开如下:
化解得到:
求解得到:
其中m为该节点样本总数,分子部分为该节点正样本数,则pk即为该节点正样本的比例。将pk带入公式得到:
进一步为了消除节点样本个数对该值的影响,使用节点样本数对该结果做归一化,得到:
没错,你没有看错!这就是我们开头抛出的信息熵公式。可见信息熵并不是什么凭空降临的上帝准则,而是从二项分布中,一步步推出来的。不知道香浓在提出信息熵的时候,是不是用了二项分布。如果是,那就是新瓶装旧酒,没什么新意;如果真是灵机一动的神来之笔,那就是英雄所见略同,虽然这两个英雄隔了好几个世纪。
几个概念
在工作中,我们常常听到诸如模型、目标、参数等概念。那什么是模型、什么是目标函数、什么是参数,它们之间有什么关系?
- 关于模型
我们讨论的决策树,是通过将数据划分到不同的互不重合区域(对应于树的生长过程),使得每个区域的样本有尽可能一直的类标签(对应于目标函数的最大化)的模型。只是一种建模方法,而与要优化的目标没有必然关系。
- 关于目标函数
而上文中我们为了解释信息熵的原理而引入的二项分布,以及基于此构造的损失函数Loss,则是我们的目标函数。我们的目标是最大化该函数的值。
- 关于模型参数
有了目标函数,才有模型的参数。模型参数是在模型结构的约束下,依据给定的训练数据,使得目标函数取的最大值时的函数参数。
- 三者关系
一个模型可以有很多个目标,一个目标可以通过不同的模型去优化。即模型结构与目标函数是独立的,互补依赖,互补干涉。
而参数则共同依赖于模型结构和目标函数,有什么样的目标函数,就有什么样的参数形式;而模型的结构则决定了最终的参数结果。
决策树的应用
读到此处相信你一定对决策树有了新的理解,不幸的是如果我们单纯地按照本文所讲的内容去建一棵决策树,你会发现模型极易出现过拟合,没什么用处。因此工业上在使用决策树模型来建模数据时,往往要加上一些限制和约束。比如说限制树的深度、限制树叶子节点的个数、为模型参数加上L2或者L1的显式正则,更或者我们使用多棵而不是仅仅使用单棵树来建模数据。
使用多棵树来建模时,树的组合方式又有不同的选择,比如:boosting,bagging。使用Boosting来组合决策树的模型我们称之为GBDT(gradient boosting decision tree);而使用bagging方式来组合决策树的模型我们则称之为random Forest(随机森林)。这也是工业界最常使用的两种树模型,我们统称为TreebasedModel......
欲知后事如何,且听下回分解。
相关推荐
总的来说,这个项目涵盖了决策树的基本原理、MATLAB编程技巧、数据预处理、模型训练、预测与评估等多个方面,是学习数据挖掘和机器学习的良好实践。通过实际操作,你可以深入了解决策树如何在天气预测这样的实际问题...
学习这些源码有助于深入理解CART算法背后的数学原理,同时也能提升C++编程技巧。 此外,资源中的数据集可能用于训练和测试决策树模型。在实际应用中,我们通常会将数据集划分为训练集和测试集,利用训练集构建决策...
决策树算法是一种广泛应用的监督学习方法,主要用于分类和回归问题。在数据挖掘、机器学习以及人工智能领域,决策树...通过分析源代码"R8",可以学习到如何在实际项目中应用决策树,并了解其背后的数学原理和优化策略。
MATLAB是一种强大的数学计算软件,它提供了丰富的工具箱,包括用于机器学习的函数,使得在MATLAB中实现C4.5决策树变得可能。 在这个资料包中,"C4.5决策树分类大作业"可能包含了以下内容: 1. **C4.5算法原理**:C...
决策树是一种广泛应用于机器学习领域的算法,它通过构建树状模型来解决分类和回归问题。在本案例中,我们有两个...通过理解并运行这些代码,你不仅可以掌握决策树的工作原理,还能了解如何将其应用到实际的预测任务中。
同时,思路文档会详细解释每一步的逻辑和背后的数学原理,帮助你更好地掌握决策树的学习。此外,文档还可能涵盖了如何应用决策树解决实际问题,例如在数据集上的训练、验证和测试过程,以及如何调整参数以优化模型...
MATLAB是一款强大的数学计算软件,提供了丰富的数据处理和机器学习工具箱,包括决策树算法。在MATLAB 2009a和2012b版本中,都有支持决策树的函数,例如`fitctree`和`predict`。 2. **文件介绍** - `main_2012b.m`...
本文旨在详细介绍在ENVI软件环境下,如何基于专家知识构建决策树模型进行遥感图像分类,这一过程不仅融合了专业知识与统计学原理,还充分利用了多源数据的优势,从而提高分类的准确性和实用性。 #### 2. 专家知识...
MATLAB作为一个强大的数学计算环境,提供了多种工具箱支持机器学习,包括决策树的实现。在MATLAB中,我们可以利用`fitctree`函数构建决策树模型,它基于Gini不纯度或信息增益等标准来选择最优特征。同时,`predict`...
决策树算法是一种广泛应用的机器学习方法,主要用于分类和回归任务。...通过理解这些原理并结合提供的源代码,你可以深入学习和掌握决策树的工作机制,并可能对其进行优化和改进,以适应不同的应用场景。
决策树是一种广泛应用于人工智能、机器学习领域的模型,它通过学习数据中的特征来进行分类或回归分析。ID3(Iterative Dichotomiser 3)是决策树算法的一种早期实现,由Ross Quinlan在1986年提出。本文将深入探讨ID3...
在这个"数学建模-决策树的Python实现"主题中,我们将深入探讨如何利用Python的科学计算库Scikit-learn来构建和应用决策树模型。 1. **决策树的基本概念** - **树的结构**:决策树由节点和边组成,根节点代表整个...
MATLAB作为一种强大的数学计算软件,为实现决策树提供了便利的工具和函数。本节将深入探讨如何在MATLAB中实现决策树,以及相关的重要知识点。 一、决策树的基本原理 决策树主要由节点、边和叶节点构成。根节点代表...
通过学习这些MATLAB程序,你可以深入了解决策树和随机森林的工作原理,掌握在实际问题中如何应用和优化这些模型,为优化horsebhr(可能是马的心率数据)这样的问题提供有效的解决方案。同时,这也为你在其他领域应用...
ID3(Iterative Dichotomiser 3)算法是一种经典的决策树学习方法,由Ross Quinlan在1986年提出。它基于信息熵和信息增益来选择最佳属性进行分裂,主要用于分类任务。本项目是关于如何使用Python实现ID3算法训练决策...
决策树算法是机器学习领域中常用的一种监督学习方法,它以树状结构来表示实例到目标变量的可能决策过程。这种算法广泛应用于分类...建议读者深入研究每个步骤,理解其背后的数学原理,并尝试自己动手实践,以加深理解。
ID3(Iterative Dichotomiser 3)算法是一种常用的决策树学习算法,由Ross Quinlan于1986年提出,主要用于分类问题。它通过信息增益(Information Gain)的概念来选择特征,并以此构建决策树。 知识点主要包括以下...
### 数据挖掘决策树知识点梳理 #### 一、数据仓库概览 - **概念与特性**:数据仓库是一种专为决策支持而设计的数据存储系统。它整合来自不同源系统的数据,以便于高级分析和报告。数据仓库的主要特点是面向主题、...