1、决策树

决策树（DTs）是一种用于回归和分类的有监督学习方法。通常，决策树用于分类问题；当决策树用于回归问题时，称为回归树。回归树在机器学习知识结构中的位置如下：

1.1、什么是决策树

决策树，顾名思义，是一种树形结构。决策树使用层层推理来实现最终的分类。决策树由下面几种元素构成：

• 根节点：包含样本的全集
• 内部节点：对应一个特征属性的测试
• 叶节点：对应一种类别（决策的结果）

这是一种基于If-Then规则的有监督学习算法，决策树的这些规则通过训练得到，而不是人工制定的

预测时，在树的内部节点处用某一属性值进行判断，根据判断结果决定进入哪个分支节点，直到到达叶节点处，得到分类结果

例如，银行要用机器学习算法来确定是否给客户发放贷款，为此需要考察客户的年收入、是否有房产这两个指标：

首先判断客户的年收入指标。如果大于20万，可以贷款；否则继续判断。然后判断客户是否有房产。如果有房产，可以贷款；否则不能贷款

1.2、决策树学习的步骤

决策树学习通常是一个选择最优特征，并根据该特征对训练数据进行分割，使得各个子数据集有一个最好的分类的过程。这一过程对应着对特征空间的划分，也对应着决策树的构建

决策树学习通常有三个步骤：特征选择；决策树生成；决策树剪枝

• 特征选择

特征选择决定了使用哪些特征来做判断。在训练数据集中，每个样本的属性可能有很多个，特征选择的作用就是筛选出跟分类结果相关性较高的特征，也就是分类能力较强的特征

不同的决策树算法有着不同的特征选择的准则

• 决策树生成

选择好特征后，就从根节点触发，对节点计算所有特征的信息增益（以ID3算法为例），选择信息增益最大的特征作为节点特征，根据该特征的不同取值建立子节点；对每个子节点使用相同的方式生成新的子节点，直到信息增益很小或者没有特征可以选择为止

• 决策树剪枝

决策树生成只考虑了对训练数据更好的拟合，可以通过对决策树剪枝，减小模型的复杂度，达到避免过拟合的效果

剪枝的主要目的是对抗过拟合，通过主动去掉部分分支来降低过拟合的风险

1.3、决策树算法

决策树算法的核心在于生成一棵决策树过程中，如何划分各个特征到树的不同分支上去

构建决策树常用的算法有：ID3、C4.5、C5.0和CART算法。其中ID3、C4.5和C5.0只能用于分类问题；CART既可以用于分类，也可以用于回归，因此更被广泛应用

• ID3（迭代分离3）

ID3算法是由Ross Quinlan于1986年开发的。该算法建立了一个多路树，为每个节点(即贪婪地)寻找分类特征，从而为分类目标提供最大的信息增益。树生长到它们的最大尺寸，然后，通常采取一个剪枝步骤，以提高树的对位置数据的泛化能力

ID3算法的核心是在决策树各个节点上使用信息增益作为选择特征的准则，信息增益大的优先选择，使用递归方法构建决策树。信息增益体现出特征与类的关联程度，即特征对类不确定性的影响程度

• C4.5

C4.5是ID3的继承者，并且通过动态定义将连续属性值分割成一组离散间隔的离散属性（基于数字变量），从而消除了特征必须是分类的限制。C4.5将经过训练的树(即ID3算法的输出)转换成一组If-Then规则的集合。然后对每条规则的这些准确性进行评估，以确定应用它们的顺序。如果规则的准确性没有提高的话，则需要决策树的树枝来解决

C4.5算法是对ID3算法的改进，C4.5使用信息增益比来选择特征，以减少信息增益容易选择特征值多的特征的问题

• C5.0

C5.0是Quinlan在专有许可下发布的最新版本。与C4.5相比，它使用更少的内存和构建更小的规则集，同时更精确

• CART（Classification And Regression Tree，分类与回归树）

CART与C4.5非常相似，但它的不同之处在于它支持数值目标变量(回归)，不计算规则集。CART使用特征和阈值构造二叉树，在每个节点上获得最大的信息增益

CART算法是根据基尼系数（Gini）来划分特征的，每次选择基尼系数最小的特征作为最优切分点

Scikit-Learn使用CART算法的优化版本。CART的特点是：假设决策树是二叉树，内部结点特征的取值为是和否，右分支是取值为是的分支，左分支是取值为否的分支。这样的决策树等价于递归地二分每个特征，将输入特征空间划分为有限个单元，并在这些单元上确定预测的概率分布，也就是在输入给定的条件下输出的条件概率分布

未完待续…

参考文章：
https://easyai.tech/ai-definition/decision-tree/
https://blog.****.net/ShowMeAI/article/details/123401318
https://www.showmeai.tech/article-detail/190
https://blog.****.net/m0_64336780/article/details/127133338
https://wszyx.blog.****.net/article/details/113547952
https://blog.****.net/qq_39709813/article/details/106694992