2023年7月29日发(作者：)

python3决策树（ID3、C4.5、CART）原理详细说明与公式推导1、简介1.1 树的定义决策树 (decision tree) 是⼀种描述对实例进⾏分类的树形结构，由结点 (node) 和有向边 (directed edge) 组成。结点有三种类型：根结点 (root node)：表⽰树根内结点 (internal node)：表⽰特征叶结点 (leaf node)：表⽰类边 (directed edge) ：表⽰划分的条件决策树的是从根结点⼀层⼀层往叶结点⾛的，根结点在的位置叫做第 0 层，依次往下推。上⼀层的结点称为下⼀层结点的⽗结点 (parentnode)，⽽下⼀层的结点称为上⼀层结点的⼦结点 (child node)。1.2 决策树学习决策树学习是归纳推理中应⽤最⼴泛、最实⽤的⽅法之⼀。它是⼀种离散值函数逼近⽅法，对噪声数据具有较强的鲁棒性.学习过的树可被重新表⽰为⼀组if-then规则。学习⽅法是将实例从根结点向下排序到某个叶结点。树中的每个结点都指定了对实例的某个属性的测试，并且每个分⽀都是该结点对应于此属性的⼀个的可能值。通过从树的根节点开始，测试该结点指定的属性，然后根据给定⽰例中属性的值向下移动，对实例进⾏分类。然后，对根在新节点上的⼦树重复此过程。2、属性(特征)选择算法通过⾃上⽽下构建决策树进⾏学习，则哪个属性作为根节点？需要使⽤统计测试来评估每个实例属性通过其单个属性在训练样本中的分类效果。分类效果最佳的属性作为树的根节点。然后为该属性的每个可能值创建根结点的后代，并将训练⽰例排序到适当的后代节点(即向下到与此属性的⽰例值对应的分⽀)。然后，使⽤与每个⼦代结点关联的训练⽰例重复整个过程，以选择树中该点要测试的最佳属性。这就形成了对可接受的决策树的贪婪搜索，在这种情况下，算法永远不会回头重新考虑之前的选择。2.1 ID3 (Iterative Dichotomiser 3, Quinlan 1986) 算法ID3算法的核⼼选择是在树的每个节点上选择要测试的属性。希望选择对分类⽰例最有⽤的属性。什么是衡量⼀个属性价值的好⽅法？定义⼀个统计属性(statistical property)叫信息增益(informution gain)，其描述了⼀个给定属性下训练样本分类效果。ID3使⽤这个信息增益度量来在树⽣长的每⼀步中选择候选属性。为了精确地定义信息增益，定义了信息论中常⽤的⼀种度量，称为熵(熵度量同质性)，它描述了任意样本集合的纯度(purity)或杂质(impurity)。给定集合S，包含正例和反例，则⼆分类的熵为：

表⽰正例的概率，表⽰反例的概率。在计算熵中定义 。，则集合S的熵是多少？例1：假设集合⾥有14个样本如下⾯表格所⽰，其中9个正例，5个反例，即

表格 集合 S (左) 熵的值与正例的概率的关系(右)

根据以上可算得，当S中只有⼀类时，熵为0；当正例与负例的数量相等时，熵为1；当正例和反例数量不等时，熵在0-1之间。ID3算法是专门⽤来学习布尔值函数的。ID3是⼀种⾃顶向下的贪婪算法，在每个节点上选择最能分类本地训练⽰例的属性。这个过程将继续下去，直到树完美地对训练⽰例进⾏分类，或者直到使⽤了所有属性。对于多个类别 的熵的公式可以写为：

代表类别k在集合中的概率。注意为 ()。假设熵是⼀组训练样本中杂质的度量，那么现在可以定义⼀个属性对训练数据分类有效性的度量。将使⽤的度量⽅法称为信息增益，它只是根据这个属性对⽰例进⾏划分所导致的熵减少的期望值。集合 S(Set) 的属性 A(Attribute) 的信息增益(information gain)：

表⽰属性A的所有可能值的集合， 是属性A值为v的 的集合（）。上式第⼀项是原始集合 S 的熵，第⼆项是利⽤属性A对S进⾏分割后熵的期望值。第⼆项描述的期望熵就是每个⼦集

即数据集 S 对特征 A 的条件熵。注：最⼩化熵就是最⼤化信息增益，熵表⽰样本的杂质（不确定性），类似于最⼩化不确定性。例2：利⽤例的集合 S，假设属性 A 为 Wind ，则有值Weak，Strong，则信息增益为？已知条件：

的熵与属于 的样本的分数 加权的和。第⼆项⼜叫条件熵 ，

信息增益正是ID3⽤来在树⽣长的每⼀步中选择最佳属性的度量。如下图所⽰总结了利⽤信息增益来评估属性相关性的⽅法。

相对于⽬标分类，湿度提供了⽐风更⼤的信息增益。对每个属性都这样计算⼀遍，然后选信息增益最⼤的属性即为根节点。

由上可知，属性Outlook提供的信息增益最⼤，因此根结点为Outlook。其分⽀是在根⽬录下为每个可能的值创建的(即晴、阴、⾬)。对后续结点重复选择新属性和样本划分，但只使⽤与该结点关联的训练样本。分⽀结点上的属性被排除，因此任何给定的属性在树中的任何路径上最多只能出现⼀次（也可以不出现）。这个过程会⼀直持续下去，直到叶⼦结点满⾜：(1) 在树的这条路径上已经包含了每个属性(2) 与这个叶⼦节点相关的训练⽰例都具有相同的⽬标属性值

ID3假设空间：ID3的特征是寻找⼀个适合训练实例的假设空间。ID3搜索的假设空间是⼀组可能的决策树。ID3通过这个假设空间执⾏简单到复杂的爬⼭搜索，从空树开始，然后逐步考虑更详细的假设，以搜索正确分类训练数据的决策树。评价函数引导这种爬⼭搜索的是信息增益度量。此搜索如下图所⽰。ID3搜索策略：(a) 选择较短的树⽽不是较长的树（Shorter trees are preferred over larger trees。原理：Occam's razor: Prefer the simplesthypothesis that fits the data）(b) 选择将信息增益最⾼的属性放置在最接近根的位置的树。（Trees that place high information gain attributes close to the rootare preferred over those that do not.）由ID3的第⼀步产⽣的部分学习的决策树。训练实例按照相应的⼦代节点排序。overcast 后代只有正例，因此成为⼀个分类为Yes的叶结点。通过选择与⽰例的新⼦集相关的信息增益最⾼的属性，将进⼀步扩展其他两个节点。 (即它们的熵为零)。

最终⽣成的决策树：、

通过查看ID3的搜索空间和搜索策略，可以了解它的能⼒和局限性:所有决策树ID3的假设空间是⼀个相对于可⽤属性的有限离散值函数的完整空间。由于每⼀个有限离散值函数都可以由某个决策树来表⽰，因此ID3避免了搜索不完全假设空间的⽅法(例如只考虑假设的⽅法)的⼀个主要风险:假设空间可能不包含⽬标函数。ID3在搜索决策树空间时只维护⼀个当前的假设。

纯形式的ID3在其搜索中不执⾏回溯。⼀旦它选择了要在树的特定级别上测试的属性，它就不会回头重新考虑这个选择。因此，它容易受到不回溯的爬⼭搜索的常见风险:收敛于局部最优解，⽽不是全局最优解。在ID3的情况下，局部最优解对应于它沿着探索的单⼀搜索路径选择的决策树。然⽽，这种局部最优解可能不如沿着搜索的不同分⽀遇到的树更可取。D3在搜索的每个步骤中使⽤所有的训练⽰例来做出基于统计的关于如何改进当前假设的决策。这与基于单个训练实例(例如，查找或候选⼈淘汰)增量决策的⽅法形成了对⽐。使⽤所有⽰例的统计属性(例如，信息增益)的⼀个优点是，结果搜索对单个训练⽰例中的错误不那么敏感。通过修改ID3的终⽌准则来接受不完全符合训练数据的假设，可以很容易地扩展ID3来处理有噪声的训练数据。2.2 C4.5 (Classifier 4.5, Quinlan 1993) 算法⽐如上⾯的表格加⼊Date属性，通过计算信息增益会发现，Date的信息增益最⼤，因此被选为根结点，但其泛化能⼒极差，因此信息增益在选择属性上存在⼀定困难。寻找替代⽅案，增益⽐。增益⽐度量通过合并⼀个术语(称为分割信息)来惩罚诸如⽇期之类的属性，该术语对属性分割数据的范围和⼀致性⾮常敏感。

C4.5算法先从候选划分属性中找出信息增益⾼于平均⽔平的属性，再从中选择增益率最⾼的。2.3 CART(Classification and Regression Tree,Breiman1984) 算法CART递归地划分输⼊空间，并在每个输⼊空间的结果区域中定义⼀个局部模型。在每个区域内，都有⼀个单独的模型来预测⽬标变量。解释CART⽅法：如下图（左）所⽰，第⼀步通过区域，每个⼦区域都可以被独⽴分割。如区域或可以根据将整个输⼊空间分成两个部分，这样就创建了两个⼦或分割成区域A和B。这种递归⼦分割可以被描述为⼆叉树遍历，如下图（右）所⽰。对于任何新的输⼊x，通过从树的顶部的根节点开始，并根据每个节点的决策条件沿着路径向下到特定的叶节点，来确定它属于哪个区域。注意，这样的决策树不是概率图形模型。

⼆维空间通过轴平⾏被分割（axis parallel splits）成5个区域 (左) 对应于输⼊空间划分的⼆叉树(右)补充：基于树的模型将输⼊空间划分为长⽅体区域，长⽅体区域的边缘与坐标轴对齐，然后为每个区域分配⼀个简单的模型(例如⼀个常量)。它们可以被看作是⼀种模型组合⽅法，其中只有⼀个模型负责在输⼊空间的任意给定点上进⾏预测。给定⼀个新的输⼊ x，选择⼀个特定模型的过程可以通过⼀个与⼆叉树遍历(在每个节点上分成两个分⽀)相对应的顺序决策过程来描述。假设有x是D维向量

值的平均值。现在考虑如何确定决策树的结构。如果⽤

假设结点

表⽰修剪的起始树，定义

, 叶结点

是 的⼦树， 可以从

有 个点， 中剪枝结点(即通过合并相应区域来折叠内部结点)。 代表叶结点总数。,训练样本有 N 个,相应连续标签

。如果输⼊空间已被划分，则最⼩化函数的误差平⽅和，任意给定区域内预测变量的最优值取落在该区域的 代表输⼊空间的区域

回归树：确定最优结构的问题(包括选择输⼊变量为每个分裂以及相应的阈值)就是最⼩误差平⽅和，由于存在⼤量可能的解，其在计算上是不可⾏的。贪婪优化通常是从⼀个根节点开始，对应整个输⼊空间，然后通过⼀次添加⼀个节点来增长树。在每个步骤中，输⼊空间中都有⼀些可分割的候选区域，对应于将⼀对叶节点添加到现有树中。对于每⼀个变量，都有⼀个选项来选择要分割的D输⼊变量，以及阈值。联合优化的选择区域分割,和输⼊变量的选择和阈值,可以有效地完成通过穷举搜索指出,对于⼀个给定的选择分离变量和阈值,预测变量的最优的选择是由当地的平均数据。这是重复的所有可能的选择的变量被分割，并给予最⼩的残差平⽅和误差保留。当残差降低到某个阈值以下时停⽌添加结点。但根据经验发现没有⼀个可⽤的分割产⽣显著的错误减少，但在多次分割后，发现⼀个实质性的错误减少。出于这个原因，通常的做法是使⽤基于与叶结点关联的数据点数量的停⽌条件来⽣成⼤型树，然后对⽣成的树进⾏修剪。修剪是基于⼀个标准，平衡残差衡量模型的复杂性。区域 的最佳预测为：

相应的残差平⽅和 （预测误差）为：

修剪标准：

是预测误差，衡量数据的拟合程度； 衡量树的复杂度;lambda权衡拟合程度与树的复杂度，其值通过交叉验证选择。 表⽰在区域 中类别 k 的数分类树：⽣长和修剪过程是相似的，只是平⽅和误差被⼀个更合适的度量⽅法代替了。定义

据点的占⽐，, 两个常⽤选择：

基尼指数也叫期望误差率（expected error rate）。 是叶结点内⼀条随机样本属于类别k的概率， 是其被错分的概率(misclassification rate)。基尼指数越⼩越好。基尼指数反映了从数据集中随机抽取两个样本，其类别标记不⼀致的概率。因此基尼指数越⼩，则数据集纯度越⾼。基尼指数偏向于特征值较多的特征，类似信息增益。基尼指数可以⽤来度量任何不均匀分布，是介于 0~1 之间的数，0 是完全相等，1 是完全不相等当 或 时，基尼指数为0；当 时基尼指数最⼤，如下图所⽰。

交叉熵和基尼系数⾮常相似，对类别概率的变化⽐误分类率更敏感。交叉熵和基尼指数是⽐误分类率更好的衡量⽅法。此外，与误分类率不同，它们是可微的，因此更适合基于梯度的优化⽅法。对于后续的修剪，通常使⽤误分类率。

树模型的⼈类可解释性是其主要优势。但学习的特定树结构对数据集的细节⾮常敏感，因此对训练数据的⼀个⼩的改变可以导致⼀组⾮常不同的分割。其他问题：⼀个是分割与特征空间的轴对齐，这可能是⾮常次优的。例如，要分离两个类，它们的最优决策边界与轴成45度⾓，与单个⾮轴向对齐的分割相⽐，需要⼤量输⼊空间的轴向并⾏分割。此外，决策树中的分割是困难的，因此每个输⼊空间区域只与⼀个叶节点模型相关联。最后⼀个问题在回归中特别有问题，因为⽬标通常是建⽴平滑函数的模型，⽽树模型产⽣的是分段常数预测，其不连续点位于分割边界处 。

2.4 三种算法的⽐较对于这部分，可以先看下⾯决策树学习需要注意的问题，再看这部分会好懂⼀些。划分标准的差异：ID3 使⽤信息增益偏向特征值多（取值多）的特征，C4.5 使⽤信息增益率克服信息增益的缺点，偏向于特征值⼩的特征，CART 使⽤基尼指数克服 C4.5 需要求 log 的巨⼤计算量，偏向于特征值较多的特征。使⽤场景的差异：ID3 和 C4.5 都只能⽤于分类问题，CART 可以⽤于分类和回归问题；ID3 和 C4.5 是多叉树，速度较慢，CART是⼆叉树，计算速度很快；样本数据的差异：ID3 只能处理离散数据且缺失值敏感，C4.5 和 CART 可以处理连续性数据且有多种⽅式处理缺失值；从样本量考虑的话，⼩样本建议 C4.5、⼤样本建议 CART。C4.5 处理过程中需对数据集进⾏多次扫描排序，处理成本耗时较⾼，⽽ CART 本⾝是⼀种⼤样本的统计⽅法，⼩样本处理下泛化误差较⼤ ；样本特征的差异：ID3 和 C4.5 层级之间只使⽤⼀次特征，CART 可多次重复使⽤特征；剪枝策略的差异：ID3 没有剪枝策略，C4.5 是通过悲观剪枝策略来修正树的准确性，⽽ CART 是通过代价复杂度剪枝（预剪枝）。3、决策树学习需要注意的问题3.1 过拟合树的每个分⽀都⽣长得⾜够深，⾜以完美地分类训练⽰例。虽然这有时是⼀种合理的策略，但实际上，当数据中存在噪声，或者当训练⽰例的数量太少，⽆法⽣成真实⽬标函数的代表性样本时，就会导致困难。避免过拟合：剪枝，通常考虑⼀组数据分成训练（2/3）和验证集(1/3)，前者⽤来形成学习的假设，后者⽤来评估这个假设相对于后续数据的准确性及评估修剪这个假设的影响。其动机：学习可能被训练集中的随机误差和巧合的规律所导致，验证集不太可能出现相同的随机波动。因此，可以期望验证集提供⼀个安全检查，防⽌对训练集的虚假特征进⾏过度拟合。验证集⾜够⼤，⾜以提供具有统计意义的实例样本。决策树的剪枝往往通过极⼩化决策树整体的损失函数 ( loss function ) 或代价函数(cost function)来实现3.1.1 预剪枝（prepruning，乐观剪枝）在树完全分类训练数据之前就停⽌⽣长的⽅法。决策树⽣成过程中，对每个结点在划分前先进⾏估计，⼀旦遇到以下三个提前停⽌条件(early stopping condition)，就应该将当前结点标记为叶结点。当树的深度超过⼀个特定值 (最⼤树深)：防⽌过拟合，会限制树的深度。最⼤深度选择⽅法：在验证集上计算分类误差率，选⼀个分类误差率最⼩的深度当继续分裂不能减⼩分类误差率：可规定⼀个阈值，继续分裂的分类误差率的减少⼩于阈值，停⽌分裂当内结点包含的数据个数⼩于⼀个特定值预修剪使得决策树的很多分⽀都没有展开，不仅降低了过拟合的风险，还减少了决策树的训练时间。但另⼀⽅⾯，有些分⽀过早停⽌但其实后续分裂区有可能导致性能显著提⾼。这样看来，预修剪有可能给决策树带来⽋拟合的风险，这个时候后修剪的作⽤就来了。3.1.2 后剪枝（post-pruning，悲观剪枝）后剪枝决策树通常⽐预剪枝保留了更多的分⽀。⼀般情况下，后剪枝决策树的⽋拟合风险⼩，泛化性能优于预剪枝决策树，但后剪枝过程是在⽣成完全决策树之后进⾏，且要⾃底向上对树中的所有⾮叶结点逐⼀考察，因此训练时间⽐预剪枝⼤得多。

后修剪过程中，我们需要平衡模型的分类能⼒和树的复杂度，前者可⽤误差分类率来量化，⽽后者可⽤树叶的个数来量化。其代价函数为：

为当前结点

的错分类率， 总结点数。当 λ 等于 0 时，后修剪就只⽐较分类误差率⽽不考虑叶结点的个数；当 λ 等于⽆穷时，后修剪最终⽣成单单⼀个树根，因为多⼀个叶结点的代价太⼤了。

3.2 连续值对ID3的初始定义是仅限于接受离散值属性。学习树的预测⽬标值和结点属性均是离散值。现在对于结点属性可以接受连续值，将其划分为离散的区间集。问题是如何选定属性的划分阈值。如将上⾯表格中的温度变为数值，⽽⾮hot、mild、cool,如下所⽰：

基于温度的候选阈值有：(48 +60)/2和(80 + 90)/2。理解：不同阈值具有不同信息增益，选取信息增益最⼤的阈值。过将温度按⼤⼩顺序排序，然后选取不同⽬标但相邻的两个实例，确定候选阈值。阈值最⼤化信息增益必须躺在这样的⼀个边界（前⼈已证明）。然后计算每个候选阈值的信息增益即可。也可将连续属性分割成多个间隔，此时阈值通过线性组合计算。3.3 ⽆⽤属性⽐如上⾯的表格加⼊Date属性，通过计算信息增益会发现，Date的信息增益最⼤，因此被选为根结点，但其泛化能⼒极差，因此信息增益在选择属性上存在⼀定困难。寻找替代⽅案，增益⽐。增益⽐度量通过分割信息来惩罚如Date之类的属性，其对属性分割数据的范围和⼀致性⾮常敏感。具体见上⾯ C4.5。3.3 缺失值训练和测试数据的⼀些属性可能缺失某些值。⼀般缺失值处理⽅式有三种：删除 (delete)：其⽅式有两种，删除⾏ (数据点)，或者删除列 (特征)。优点：操作简单、可以⽤在任何模型⽐如决策树、线性回归和对率分类等等；缺点：对缺失数据的测试集没⽤、不知道删除⾏好还是删除列好、删除的数据可能包含着重要信息推算 (impute)：根据特征值是分类型 (categorical) 变量或数值类 (numerical) 变量，推算的⽅式有两种：⽤众数来推算分类型缺失数据；⽤平均数来推算数值型缺失数据。优点：操作简单、可以⽤在任何模型⽐如决策树、线性回归和对率分类等等、对缺失数据的测试集有⽤，运⽤同样的规则 (众数分类型变量，平均数数值型变量)；缺点：可能会造成系统型误差归类 (categorize)：归类的核⼼思想是把“缺失 (unknown)”也当作是⼀种特征值。优点：⽐起删除/推算数据，预测更准、对缺失数据的训练集和测试集都有⽤；缺点：需要修改算法，虽然对决策树不难4、决策树的应⽤范围虽然各种决策树学习⽅法的能⼒和要求有所不同，但决策树学习通常最适合以下特点的问题:实例由属性-值 (Attribute-Value) 对表⽰。实例有固定的⼀组属性及其对应的值。决策树最早应⽤于离散值（不可能相交的值）。但后期对基函数（basic function）的扩展使决策树可以对数值进⾏处理。⽬标函数是离散输出值。决策树⽅法很容易扩展到具有两个以上可能输出值的学习函数。可能需要分离描述(Disjunctive descriptions)

训练数据可能包含错误。决策树学习⽅法对错误具有鲁棒性，包括训练样本分类的错误和描述这些样本的属性值的错误。训练数据可能包含丢失的属性值。即使某些训练实例的值未知，也可以使⽤决策树⽅法多数为学习决策树⽽开发的算法都是核⼼算法的变体，核⼼算法采⽤⾃顶向下的贪婪搜索，遍历可能的决策树空间。5、树的优缺点优点：决策树能够⽣成可理解的规则。决策树执⾏分类不需要太多的计算。决策树能够同时处理连续变量和分类变量。决策树为预测或分类哪些字段最重要提供了清晰的指⽰。缺点：决策树不太适合⽤于以预测连续属性值为⽬标的评估任务。决策树在分类问题中容易出错，分类类别多，训练实例相对较少。决策树的训练在计算上是很昂贵的。⽣成决策树的过程在计算上⾮常昂贵。在每个节点上，必须对每个候选分割字段进⾏排序，然后才能找到它的最佳分割。在⼀些算法中，使⽤字段的组合，并且必须搜索最优的组合权值。修剪算法也很昂贵，因为必须形成许多候选⼦树并进⾏⽐较。6、python3实现