读书笔记 周志华老师的《机器学习》
4.1 基本流程
一个决策树包含一个根结点、若干个内部结点和若干个叶结点；叶结点对应于决策结果，其他每个结点则对应于一个属性测试；每个结点包含的样本集合根据属性测试的结果被划分到子结点中；根结点包含样本全集，从根结点到每个叶结点的路径对应了一个判定测试序列。
决策树的生成是一个递归过程，在决策树基本算法中，有三种情形会导致递归返回：（1）当前节点包含的样本全属于同一类别，无需划分；（2）当前属性集为空，或是所有样本在所有属性上取值相同，无法划分；把当前结点标记为叶结点，并将其类别设定为该结点所含样本最多的类别，利用了当前结点的后验分布（3）当前结点包含的样本集合为空，不能划分，把当前结点标记为叶结点，但将其类别设定为其父节点所含样本最多的类别，这里是将父结点的样本分布作为当前结点的先验分布。
4.2 划分选择
希望决策树的分支结点所包含的样本尽可能属于同一类别，即结点的“纯度”purity越来越高
信息增益
“信息熵”information entropy是度量样本集合纯度最常用的一种指标，假定当前样本集合D中第k类样本所占比例为p_k（k=1,2,...,|y|）,则D的信息熵定义为
End(D)的值越小，则D的纯度越高。
用属性a对样本集D进行划分所获得的“信息增益”information gain：
一般而言，信息增益越大，使用属性a来进行划分所获得的“纯度提升”越大，所以划分属性，
增益率
如果使得每个样例的编号作为属性，每个分支有一个样本，这些分支结点的纯度已达到最大，但是这样的决策树不具有泛化能力，无法对新样本进行有效预测，信息增益准则对可取值数目较多的属性有所偏好。
著名的C4.5决策树算法使用“增益率”gain ratio来选择最优划分属性。
增益率准则对可取值数目较少的属性有多偏好，因此，C4.5算法并不是直接选择增益率最大的候选划分属性，而是使用了一个启发式：先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。
基尼系数
CART决策树Classification and Regression Tree是一种著名的决策树学习算法，分类和回归都可用，CART决策树使用“基尼系数”Gini index来选择划分属性。数据集D的纯度可用基尼值来度量：
Gini(D)反映了从数据集D中随机抽取两个样本，其类别标记不一致的概率，因此，Gini(D)越小，则数据集D的纯度越高。
属性a的基尼指数定义为，
我们在候选属性集合A中，选择使得划分后基尼指数最小的属性作为最优划分属性，即
4.3 剪枝处理
剪枝pruning是决策树学习算法对付“过拟合”的主要手段，决策树分支过多，以至于把训练集自身的一些特点当做所有数据都具有的一般性质而导致过拟合，“预剪枝”prepruning和“后剪枝”postpruning是决策树剪枝的两种基本策略，预剪枝是指在决策树生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点标记为叶结点；后剪枝则是先从训练集生成一颗完整的决策树，然后自底向上地对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化性能的提升，则将该子树替换为叶结点。
判别决策树泛化性能提升：随机划分数据集为训练集和验证集，根据上节中的一些准则选择属性划分，预剪枝根据划分前后的对验证集预测结果进行评判是否继续划分，降低了过拟合的风险，显著减少了决策树的训练时间开销和测试时间开销，但有些分支的当前划分虽不能提升泛化性能、甚至导致下降，但在其基础上进行后续划分有可能导致性能显著提高，预剪枝可能带来“欠拟合”风险。后剪枝从训练集生成一颗完整的决策树，自底向上决定是否剪枝，后剪枝决策树通常比预剪枝决策树保留了更多的分支，一般泛化能力优于预剪枝决策树，欠拟合风险小，但是后剪枝决策树在生成完全决策树之后进行，并且要自底向上对树中所有非叶结点逐一考察，训练时间开销比预剪枝和未剪枝都要大很多。
4.4 连续与缺失值
连续值属性一般采用二分法进行处理，对属性区间寻找中位点进行划分，与离散属性不同，若当前结点划分属性为连续属性，该属性还可作为其后代结点的划分属性。
缺失值处理：不完整样本
如何在属性缺失的情况下进行划分属性选择？
给定划分属性，若样本在该属性上的值缺失，如何对样本进行划分？
若样本x在划分属性a上的取值未知，则将x同时划入所有子结点，且样本权值在与属性值a=v对应的子结点中调整为为~r_v*w_x.
4.5 多变量决策树
非叶结点不再是仅对某个属性，而是对属性的线性组合进行测试。
决策树优点：计算量简单，可解释性强，比较适合处理有缺失属性的样本，能够处理不相关的特征
缺点：容易过拟合，后续出现了随机森林，减小了过拟合现象