决策树基本原理,决策树的实现原理
文章发表在微信官方账号【数字智能物语】(ID:decision_engine)，重点介绍微信官方账号可以跨所有干货。
来源Python与算法之美(ID:Python_Ai_Road))))))))。
作者yqdhy1991
决策树是一种非参数的监控学习方法，主要用于分类和回归问题。
根据一系列if then决策规则，决策树模型将特征空间划分为有限数量的不相交子区域，并对属于同一子区域的样本给出相同的预测值。
这些if then决策规则之间的层次关系形成了一个叫做决策树的树结构，这些不相交的子区域与树结构的叶节点一一对应。
01
一，决策树原理概述
01
空间假说
本文从假设空间、目标函数和优化算法三个方面阐述了决策树算法的基本原理。
假设空间是我们对模型形式的先验假设，最后得到的模型必须符合我们对模型形式的先验假设。
决策树模型的先验形式可以表示如下。
这里，q[x]是从特征空间映射到节点号空间的函数。决策树模型的关键是将特征空间划分为不相交的子区域，落入同一子区域的样本具有相同的预测值。
为了确定决策树的完整结构，需要明确以下两个方面。一个是如何划分子区域，一个是子区域的预测值应该是多少。
02
目标函数
该函数使用什么标准来评估模型？目标决定了从假设空间中选择模型时的偏好。
决策树的目标函数可以用来评价决策树的质量。这个目标函数必须包含两个方面。第一个是响应决策树的样本数据拟合精度损失项，第二个是响应决策树模型复杂性的正则化项。
正则项可以取模型的叶节点的数量。也就是说，决策树模型划分的不相交区域越多，模型越复杂。
关于损失项，如果是回归问题，可以对损失项进行平方得到损失，如果是分类问题，可以用杂质作为衡量基准。
为什么纯度低？决策树同一个叶节点上的所有样本的预测值都是一样的，所以如果这些样本的实际标签只有一个值，那么这个叶节点上的样本就很纯，所以预测值就是这个叶节点上的标签值，而预测误差为0。相反，如果叶节点上不同样本的标注方法比较杂乱，所谓的模式比较困难，那么无论如何都会指定叶节点上的预测值，导致预测误差较大。
那么，如何测量杂质呢？一般有三种方法。信息熵、基尼杂质与分类错误率。分类错误率是指标签值最多的类别作为叶节点预测值时的错误率。信息熵和基尼纯度后面会介绍。
03
最优化算法
优化算法是指如何调整模型结构或模型超参数的可能值，以降低模型目标函数的可能值。
优化算法确定使用哪些步骤在假设空间中找到合适的模型。
对于决策树，优化算法包括树生成策略和树剪枝策略。
一般生成树的策略是利用贪婪的思想不断选择特征来划分特征空间。
树木修剪策略一般分为修剪前和修剪后。一般来说，后剪枝策略下的决策树是有效的，但计算成本也很高。
02
二，ID3，C4.5，CART决策树的对比
01
适用问题范围的差异
ID3算法只能处理离散特征的分类，C4.5可以处理离散特征和连续特征的分类，CART算法可以处理离散特征和连续特征的分类和回归。
02
假设空间差异
ID3和C4.5算法使用的决策树可以是多分支的，但是CART算法的决策树必须是二叉树。
03
目标函数的差异
在处理同一个分类问题时，在决定选择哪个特征进行决策树分割时，三种模型使用了不同的判断标准。Id算法受制于信息增益，C4.5算法
其实ID算法是没有剪枝策略的。当叶子节点上的所有样本属于同一类别或者所有特征都被使用时，决策树停止生长。
C4.5如果分割增益小于预定阈值，则该算法使用预修剪策略
当叶子上的样本数小于某个阈值或者叶子节点数达到某个极限值或者树的深度达到某个极限值时，决策树停止生长。
CART决策树主要采用后剪枝策略。
05
效果差异
ID3决策树是最早的决策树，C4.5是对它的改进，CART决策树出现的比较晚。总的来说，CART tree比C4.5好，C4.5比ID3好。
03
三，熵，条件熵，信息增益，信息增益率
01
熵
熵是对离散随机变量不确定性的一种度量。由于反应是不确定的，我们的先验知识是，当随机变量只有一个值时，熵为0。当随机变量的可能性越多，可能性之间的概率分布越平均，熵就越大。熵的公式满足这些先验特征。注意，熵只能度量离散随机变量的不确定性。
在决策树的应用场景中，我们实际上是用经验熵来衡量标签值分布的“纯度”，也就是用频率分布代替概率分布来计算。
02
条件熵
所谓条件熵，是指在随机变量X的值给定的前提下，对随机事件Y的不确定性的一种度量。
在决策树的应用场景中，条件熵的含义更加明确，即根据离散特征X的值，将样本空间划分为多个叶节点，每个叶节点上样本标签Y的熵杂质加权平均。
03
信息增益
随机变量x对随机变量y的信息增益定义为y的熵与y对x的条件熵之差。
在决策树的应用场景中，信息增益的含义是特征X对样本标签y的不确定性降低的贡献。
信息增益也称为互信息。互信息具有以下特征：Y到X的互信息和X到Y的互信息相等。互信息是衡量两个离散随机变量之间先前相关性的常用指标。
简单的证明如下：
04
信息增益率
ID3模型使用信息增益作为待分裂特征的选择标准，但信息增益倾向于选择具有大量特征的特征。C4.5通过使用信息增益率作为待分割特征的选择标准，可以避免这种趋势。值得注意的是，C4.5在选择连续特征的分裂点时，仍然使用信息增益作为选择标准。
x对y的信息增益率是x对y的信息增益与x的熵之比。
04
四，基尼不纯度和基尼不纯度增益
01
基尼杂质
基尼不纯和熵具有相似的函数，可以度量一个随机变量的值的不确定性或‘不纯’程度。它符合我们先前的期望。当随机变量只有一个可能值时，基尼杂质为0。当随机变量可能取值的个数越多时，取值的平均概率分布越多，基尼杂质越大。
基尼系数的定义如下。
基尼系数满足我们先前假设的不确定性测量指标。事实上，基尼系数与熵有着非常密切的关系。将熵的对数部分rxdxte展开为一阶，得到了基尼杂质的定义公式。
02
基尼不正当收益
基尼杂质增益和信息增益的作用非常相似。计算方法也很相似。
值得注意的是，CART决策树是一棵二叉树。在计算离散特征的基尼不纯增益时，它会尝试根据特征是否取特定类别将特征空间分成两部分，而在计算连续特征的基尼不纯增益时，它会尝试选择一个分裂点将特征空间分成两部分。
从我开始，每天都变得聪明一点。
