2019-06-24

1. 决策树学习算法包括哪几个部分？常用的算法有哪些？

决策树学习通常包括三个步骤：特征选择、决策树的生成、决策树的剪枝。

常用的算法有ID3、C4.5、CART算法。

2. 决策树的根节点、内部节点和叶节点分别表示什么？

决策树是一种基本的分类与回归方法。分类决策树是一种描述对实例进行分类的树形结构。决策树由节点和有向边组成。节点有两种类型：内部节点和叶节点。内部节点表示一个特征或属性，叶节点表示一个类。根节点指决策树最开始的节点。

3. 特征选择的准则有哪些（如何选择最优划分属性）？

特征选择的准则是信息增益或信息增益比。

信息增益

$g(D,A_1)=H(D)-H(D|A)$

$H(X)=-\sum_{i=1}^{n}p_ilogp_i$

$H(Y|X)=-\sum_{i=1}^{n}p_iH(Y|X=x_i)$

信息增益率

以信息增益作为划分训练数据集的特征，存在偏向于选择取值较多的特征的问题。使用信息增益比可以对这一问题进行校正。

$gR(D,A)=\frac{g(D,A)}{H_A(D)}$

其中训练数据集D关于特征A的值的熵

$H_A(D)=-\sum_{i=1}^{n}\frac{|D_i|}{|D|}log_2\frac{|D_i|}{|D|},n\text{是特征A取值的个数}$

4. 决策树如何防止过拟合？

决策树生成算法递归地产生决策树，直到不能继续下去为止。这样产生的树往往对训练数据的分类很准确，但对于未知的测试数据的分类却没有那么准确，即出现过拟合的现象。过拟合的原因在于学习时过多地考虑如何提高对训练数据的正确分类，从而构建出过于复杂的决策树。解决这个问题的办法是考虑决策树的复杂度，对已生成的决策树进行简化。

在决策树学习中将已生成的树进行简化的过程称为剪枝。具体地，剪枝从已生成的树上裁掉一些子树或者叶节点，并将其根节点或父节点作为新的叶节点，从而简化分类数模型。决策树的剪枝往往通过极小化决策树整体的损失函数或者代价函数来实现。

决策树生成只考虑了通过提高信息增益（或信息增益比）对训练数据进行了更好的拟合。而决策树剪枝通过优化损失函数还考虑了减小模型复杂度。决策树生成学习局部的模型，而决策树的剪枝学习整体的模型。

5. 连续值和缺失值如何处理？

连续值处理：

采用连续属性离散化技术，如二分法对连续属性进行处理。

给定样本D和连续属性a，假定a在D上出现了n个不同的取值，将这些值从小到大进行排序，记为

$\{a^1,a^2,...,a^n\}$ 基于划分点t可将D分为子集 $D^-_t$ 和 $D^+_t$ 其中 $D^-_t$ 包含那些在属性a上取值不大于t的样本，而 $D^+_t$ 则包含那些在属性a上取值大于t的样本。显然，对于相邻属性 $a^i$ 与 $a^{i+1}$ 来说，t在区间 $[a^i,a^{i+1}]$ 中取任意值所产生的划分结果相同。因此，对连续属性a，我们可考察包含n-1个元素的候选划分集合：

$T_a=\{\frac{a^i+a^{i+1}}{2}|1\leq i\leq n-1|\}$

即把区间 $[a^i,a^{i+1}]$ 的中位点 $\frac{a^i+a^{i+1}}{2}$ 作为候选划分点。然后我们就可以像离散属性值一样来考察这些划分点，选取最优的划分点进行样本集合的划分。

$Gain(D,a)=\max_{t\in T_a}Gain(D,a,t)=\max_{t\in T_a}Ent(D)-\sum_{\lambda\in\{-,+\}}\frac{|D_t^\lambda|}{|D|}Ent(D_t^\lambda)$

其中 $Gain(D,a,t)$ 是样本D基于划分点t二分后的信息增益，于是我们就可选择使 $Gain(D,a,t)$ 最大的划分点。

缺失值处理

1. 如何在属性值确实的情况下进行划分属性选择？

$\rho$ 表示无缺失值样本所占比例，给定训练集D和属性a， $\widehat{D}$ 表示D中在属性a上没有缺失值的样本子集.

$Gain(D,a)=\rho*Gain(\widehat{D},a)$

2. 给定划分属性，若样本在改属性上的值缺失，如何对样本进行划分？

若样本x在划分属性a上的取值已知，则将x划入与其取值对应的子节点，且样本权值在子节点中保持为 $w_x$ ;若样本X在划分属性a上的取值未知，则将X同时划入所有子节点，且样本权值在于属性值 $a^v$ 对应的子节点中调整为 $\widehat{r}_v*w_x$ ，其中 $\widehat{r}_v$ 表示无缺失值样本中属性a上取值 $a^v$ 的样本所占的比例。