decision tree

Posted on 2020-07-05 Edited on 2021-10-24

决策树（DT）是一种用于分类和回归的非参数监督学习方法。包含一个根结点、若干个内部结点和若干叶结点。根结点和内部结点代表用于划分的属性测试，叶结点代表决策结果。每个结点包含的样本集合根据属性测试被划分到子结点中，根结点包含样本全集。

基本流程遵循简单直观的分而治之（divide and conquer）策略：选择最优属性，划分，递归进行。

休息一下：

“分而治之”（divide and conquer）这词语总是看到，第一次是在sort algorithm那里，计算复杂度，但印象中并不是最快的（？）……最近一次是在甜甜圈们的典范表示，啊不，基本群的典范表示： is for a surface

三种情况递归返回：
（1）当前结点包含样本全属于同一类别，无需划分
（2）当前属性集为空，或是所有样本在所有属性上取值相同，无法划分
（3）当前结点包含的样本集合为空，不能划分

情形（2）是在利用当前结点的后验分布，情形（3）是把父结点的样本分布作为当前结点的先验分布。

我们希望决策树的分支结点所包含样本尽可能属于同一类别，信息熵（information entropy）是度量样本集合纯度最常用的指标，样本集合中第类样本所占的比例为，则的信息熵定义为显然

用属性划分有个可能取值，取值为的样本为，用属性对样本集进行划分所获得的信息增益（information gain）为选择最优划分属性。著名的ID3决策树学习算法就是以信息增益为准则来划分最优属性的。

但信息增益准则对可取值数目较多的属性有所偏好，为减少这种偏好可能带来的不利影响，著名的C4.5决策树算法使用增益率（gain ratio） 其中称为属性的固有值（intrinsic value）。属性可能取值越多，固有值通常越大。

增益率对可能值数目较少的属性有所偏好，使用启发式算法：先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。

CART决策树使用基尼指数（Gini index）来选择划分属性。反映了从数据集中随机抽取两个样本，其类别标记不一样的概率。越小，则数据集的纯度越高。属性的基尼指数为选取划分后基尼指数最小的属性作为最优划分属性，即

剪枝处理

剪枝（pruning）是决策树学习算法对付过拟合的主要手段，基本策略有预剪枝（prepruning）和后剪枝（post-pruning）。

预剪枝是在决策树生成过程中，对每个结点在划分前先进行估计，若划分不能使泛化性能得到提升，则停止划分并将当前结点标记为叶结点；后剪枝则是先从训练集生成一棵完整的决策树，然后自底向上对非叶结点进行考察，若子树换位叶结点提升泛化性能则替换。

对连续属性，考虑选取最优的划分点进行集合划分。

与离散属性不同，若当前结点划分属性为连续属性，该属性可作为其后代结点的划分属性。

对于缺失值：

（1）如何在属性值缺失的情况下进行划分属性选择？

令为在属性上没有缺失值的样本子集，根据来判断属性的优劣。

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

为每个样本赋予权重，在根结点权重均初始化为，定义

若样本属性值未知，同时划入所有子结点，并将样本权值在属性值对应的子结点中调整为

决策树形成边界直观特点是分类边界由若干个与坐标轴平行的分段组成。多变量决策树可以由属性的线性组合构成，可以用斜边划分边界。