参考资料：

1. 《机器学习》周志华
2. 《统计学习方法》李航

1. 决策树生成算法

决策树的算法如图所示：

第2行和第4行是对新生成节点进行类别标记。第9行开始是循环分裂node节点，为最优特征的每一个值生成叶子节点。

第8行是重点，它决定了决策树的生长方式：当我有不止一个特征时，我该如何选择一个”最优“特征作为节点分裂的依据？

2. 划分最优特征

最优特征是通过信息熵和信息增益来确定的。所谓的”最优“就是我们希望最早作为节点分裂依据的特征是最具有区分度的，其分支节点尽可能属于同一类别，也就是节点的”纯度“越高。

2.1 信息增益

信息熵是度量样本集合纯度的常用指标。它利用了负对数函数 f(x) = -log(p), 该函数同时满足了概率上升时不确定性的减少和不同概率对应的不确定性的可加性。信息熵的定义为：

\[Ent(D) = - \sum^{|y|}_{k=1}{p_k log_2 p_k} \]

其中，pk是样本集D中第k类样本所占的比例。Ent(D)的值越小，D的纯度越高。

信息增益可以由信息熵计算得到。假定离散属性a由V个可能的取值，则用a对样本集D进行划分可以得到V个分支节点。定义信息增益为：

\[Gain(D,a) = Ent(D) - \sum_{v=1}^V \frac{|D^V|}{|D|}Ent(D^v) \]

其中，|D^v|/|D|权重使样本数越多的分支节点的影响越大。最终选出的属性是 a = argmax_a∈AGain(G, a)，即所有特征中使得信息增益最大的一个特征*。

2.2 增益率

单纯通过信息增益存在一个问题：如果数据中存在一个例如“id”的属性，拥有极高的信息纯度，但并不能有效的作为分类特征，决策树不具备泛化能力。一种方法是从数据中删除这一列。另一种方法则是使用增益率代替信息增益作为特征划分依据。G4.5算法不直接通过信息增益，而是通过增益率选择最优划分属性。

\[Gain\underline{} ratio(D,a) = \frac{Gain(D,a)}{IV(a)} \\ IV(a) = -\sum^{V}_{v=1} \frac{|D^v|}{|D|} log_2 \frac{|D^v|}{|D|} \]

IV(a)称为属性a的”固有值“，a可取的数目越多，IV(a)的值也就会越大。

2.3 基尼指数

CART决策树使用基尼指数来划分特征：

\[Gini(D) = \sum^{|y|}_{k=1} \sum_{k'=k} p_k p_k' = 1- \sum^{|y|}_{k=1}p_k^2 \]

基尼指数计算式最后一项是取出两个样本，属于同一个标签的概率总和，被1减后就是两个样本不属于同意标签的概率。所以基尼指数越小，数据集D的纯度就越高。

3. 决策树剪枝

剪枝是一种很好的防止过拟合的方法。决策树生成过程只考虑提高信息增益对训练数据进行更好的拟合，剪枝则是通过优化损失函数来减小模型复杂度。决策树生成学习局部的模型，决策树剪枝学习整体的模型。

决策树的损失函数可以定义为：

\[C_{\alpha}(T) = \sum^{|T|}_{t=1}N_t H_t(T)+\alpha|T| \]

其中，|T|是树的节点个数，t是叶子节点，N_t是节点t的样本点数，其中由N_tk个属于k类的样本点。H_t(T)是节点t的经验熵，α>=0是参数。

经验熵为：

\[H_t(T) = -\sum_{k}\frac{N_{tk}}{N_t} log \frac{N_{tk}}{N_t} \]

剪枝过程：计算每个节点的经验熵，递归地从树的叶节点回缩。

记一组叶节点回缩到其父节点前后的整体决策树分别为T_B, T_A，如果其对应的损失函数C_α(T_A) <= C_α(T_B)，则进行剪枝，父节点变为新的叶节点。

4. 连续与缺失值

4.1 连续值处理

连续属性：例如人的身高，从180 cm到181 cm之间有无数个数值。与之相对的是离散属性，例如抛硬币，之可能出现0和1，是有限种可能。

假设连续属性a在样本集D上出现了n个不同取值，可以将这n个数值排序，在其中选取一个分割点t，大于t的和不大于t的分别可以作为离散属性处理。

例如，可以将信息增益函数改写为Gain(D, a, t) _t∈T，选取出使得信息增益最大的t作为分割点。

4.2 缺失值处理

一条数据中可能会有有一个或多个属性的数据缺失。这个问题主要体现在影响属性划分上。

假设样本数据中包含了无缺失值样本，和在某个属性上有缺失值的样本。现在定义三个变量：

• ρ表示无缺失值样本所占的比例
• \tilde{p_k}表示无缺失值样本中第k类所占的比例
• \tilde{r_v}表示无缺失值样本在属性α上取值为α_v的样本所占的比例

以此推广信息增益的计算式：

\[Gain(G,a) = \rho \times Gain(\tilde{D},a) = \rho \times (Ent(\tilde{D})-\sum^{V}_{v=1}(\tilde{D^v})) \]

其中：

\[Ent(\tilde{D}) = -\sum^{|y|}_{k=1}\tilde{p_k} log_2 \tilde{p_k} \]

直观的来看，最终的结果是让有缺失值的数值在缺失的属性上划入所有子节点，但是以不同的概率。