Task01

信息论基础

决策树分类思想：

用树的节点代表样本集合，通过某些判定条件来对节点内的样本进行分配，将它们划分到当前节点下的子节点，这样决策树希望各个子节点中类别的纯度之和应高于该节点中的类别纯度，达到分类效果。

节点类别纯度：

节点纯度反映的是节点样本标签的不确定性。当一个节点的纯度较低时，说明每种类别都倾向于以比较均匀的频率出现，从而我们较难在这个节点上得到关于样本标签的具体信息，其不确定性较高。当一个节点的纯度很高时，说明有些类别倾向于以比较高的频率出现，从而我们能够更有信心地把握这个节点样本标签的具体信息，即确定性较高。

不确定性的函数H§：

满足三个信息熵条件

若度量不确定性的函数H满足三个信息熵条件，

其中，信息熵条件如下：

• HH关于pipi是连续函数。

• 若p1=…=pnp1=…=pn，则HH关于nn单调递增。

• 若将某一个pipi拆分为pi1pi1和pi2pi2，即pi1+pi2=pipi1+pi2=pi，则

  解释：从构造和计算的角度而言，条件一是容易满足的。对于条件二而言，假设原来箱子里分别有10个球和100个球，加入每次摸到的球都是等概率抽出的，那么100个球的箱子产生的不确定性必然是要大于10个球的箱子产生的不确定性，即HH在等概率条件下关于nn递增。

  条件三看上去比较复杂，但其意义是容易理解的，即nn个事件拆分为n+1个事件时的不确定性增加了，并且增加的不确定性与拆分时的比例和拆分事件的概率有关。举例来说：将p=[0.9,0.1]分别拆分为p1=[0.45,0.45,0.1]和p2=[0.9,0.05,0.05]，那么显然p1p1增加的不确定性远超过p2p2；同时，将p=[0.9,0.1]分别拆分为p3=[0.8,0.1,0.1]，那么显然p1p1增加的不确定性也远超过p3。

  由于指标H§H§中的自变量pp是对于某个随机变量YY分布的描述，因此不妨将其记为信息熵H(Y)H(Y)来反应YY的不确定性。对于定义在有限状态集合*{y1,…,yK}*上的离散变量而言，对应信息熵的最大值在离散均匀分布时取到，最小值在单点分布时取到。

信息熵：

1. 反应变量的不确定性。

条件熵：

1. 在决策树的分裂过程中，我们不但需要考察本节点的不确定性或纯度，而且还要考察子节点的平均不确定性或平均纯度来决定是否进行分裂。子节点的产生来源于决策树分支的条件，因此我们不但要研究随机变量的信息熵，还要研究在给定条件下随机变量的平均信息熵或条件熵（Conditional Entropy）。从名字上看，条件熵就是条件分布的不确定性。

信息增益（Information Gain）:

1. 有了信息熵和条件熵的基础，我们就能很自然地定义信息增益（Information Gain），即节点分裂之后带来了多少不确定性的降低或纯度的提高。在得到了随机变量XX的取值信息时，随机变量YY不确定性的平均减少量为:
   G ( Y , X ) = H ( Y ) − H ( Y ∣ X ) G(Y,X)=H(Y)−H(Y|X) G(Y,X)=H(Y)−H(Y∣X)

2. 从直觉上说，随机变量Y关于X的信息增益一定是非负的，因为我们额外地知道了随机变量X的取值，这个条件降低了Y的不确定性。

分类树的节点分裂

对于每个节点进行分裂决策时，我们会抽出max_features个特征进行遍历以比较信息增益的大小。特征的类别可以分为三种情况讨论：类别特征、数值特征和含缺失值的特征，它们各自的处理方法略有不同。

类别：

1. 给定阈值min_impurity_decrease，树的每一个节点会选择最大信息增益对应的特征进行分裂，直到所有节点的相对最大信息增益。

数值：

1. 在处理节点数值特征时，可以用两种方法来将数值特征通过分割转化为类别，它们分别是最佳分割法和随机分割法，分别对应了sklearn中splitter参数的best选项和random选项。
2. 随机分割法下，取s∼U[xmin,xmax]s∼U[xmin,xmax]，其中U[xmin,xmax]U[xmin,xmax]代表特征最小值和最大值范围上的均匀分布，将节点样本按照特征xx中的元素是否超过ss把样本划分为两个集合，这等价于把数值变量转换为了类别变量。此时，根据这两个类别来计算树节点分裂的信息增益，并将它作为这个数值特征分裂的信息增益。
3. 最佳分割法下，依次令ss取遍所有的xi(i=1,…,DN)xi(i=1,…,DN)，将其作为分割点，按照特征xx中的元素是否超过ss把样本划分为两个集合，计算所有ss对应信息增益的最大值，并将其作为这个数值特征分裂的信息增益。

含缺失值：

1. 算法处理缺失数据的思想非常简单，样本的缺失值占比越大，那么对信息增益的惩罚就越大，这是因为缺失值本身就是一种不确定性成分。设节点NN的样本缺失值比例为γγ，记非缺失值对应的类别标签和特征分别为Y_Y和X_X，则修正的信息增益为
   G   ( Y , X ) = ( 1 − γ ) G ( Y   , X   ) G~(Y,X)=(1−γ)G(Y~,X~) G (Y,X)=(1−γ)G(Y ,X )
   当数据完全缺失时γ=1γ=1，信息增益为0；当数据没有缺失值时γ=0γ=0，信息增益与原来的值保持一致。

树的生长策略

在前面的部分中，我们讨论了单个节点如何选取特征进行分裂，但没有涉及到树节点的分裂顺序。例如下图所示，假设当前已经处理完了节点2的分裂，所有黄色节点（包括2号节点）都是当前已经存在的树节点，那么我们接下来究竟应该选取叶节点3号、4号和5号中的哪一个节点来继续进行决策以生成新的叶节点6号和7号？

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-D3l0j3ee-1634221620235)(E:\新建文件夹\datawhale\集成学习上\CSDN\tree_pic1.png)]

1. 在sklearn中提供了两种生长模式，它们分别被称为深度优先生长和最佳增益生长，当参数max_leaf_nodes使用默认值None时使用前者，当它被赋予某个数值时使用后者。
2. 深度优先生长采用深度优先搜索的方法：若当前节点存在未搜索过的子节点，则当前节点跳转到子节点进行分裂决策；若当前节点为叶节点，则调转到上一层节点，直到根节点不存在未搜索过的子节点为止。对上图而言，当前节点为2号，它的两个子节点4号和5号都没有被搜索过，因此下一步则选择两个节点中的一个进行跳转。当决策树使用最佳增益生长时，每次总是选择会带来最大相对信息增益的节点进行分裂，直到叶节点的最大数量达到max_left_nodes。

CART树

对于回归树而言，每个叶节点输出的不再是类别而是数值，其输出值为该叶节点所有样本标签值的均值。在每次分裂时，我们希望不同的子节点之间的差异较大，但每个子节点内部的差异较小。此时，分割策略仍然可以采用随机分割法或最佳分割法，只是现在不再以熵（条件熵）来评价节点（子节点）的纯度。

1. 我们应当如何定义回归树的节点纯度？对于数值标签而言，我们可以认为节点间元素大小越接近则纯度越高，因此可以考虑使用均方误差（MSE）或平均绝对误差（MAE）来替换熵和条件熵的位置。

决策树的剪枝

决策树具有很强的拟合能力，对于任何一个没有特征重复值的数据集，决策树一定能够在训练集上做到分类错误率或均方回归损失为0，因此我们应当通过一些手段来限制树的生长，这些方法被称为决策树树的剪枝方法。其中，预剪枝是指树在判断节点是否分裂的时候就预先通过一些规则来阻止其分裂，后剪枝是指在树的节点已经全部生长完成后，通过一些规则来摘除一些子树。

预剪枝：

后剪枝：

练习及其答案理解

节点是否分裂的时候就预先通过一些规则来阻止其分裂，后剪枝是指在树的节点已经全部生长完成后，通过一些规则来摘除一些子树。

预剪枝：

后剪枝：

练习及其答案理解