决策树
1 概述
决策树的学习目的是产生一棵泛化能力强的决策树，基本流程遵循“分而治之”的策略。
决策树
- 最顶层是根节点，包含所有样本
- 每个叶节点代表类或类分布（几类的概率分布）（预测时直接选概率最大的类），对应决策结果
- 每个样本均被划分到一个叶节点
树的生成
- 选择特征
- 选择阈值
2 四种建树算法
基本算法框架：
有三种特殊情况导致递归返回：
- 当前结点包含的所有样本都是同一类别了
- 当前属性集为空，或是所有样本所有属性都一样
- 当前结点不包含任何样本
图中最关键的是第8行，也就是如何选择最佳属性。在这个问题上，有四种衍生出的算法：
- CLS
- ID3
- C4.5
- CART
接下来一一介绍。
2.1 CLS
CLS是第一个决策树算法。
CLS算法的基本思想是通过递归地将数据集分割成多个子集，直到满足某个停止条件为止。在每个节点上，CLS算法选择最优的特征进行分割，并根据特征的取值将数据集划分成不同的子集。
一旦数据集被划分成子集，CLS算法会递归地在每个子集上重复上述过程，直到满足停止条件为止。
采用不同的测试属性及其先后顺序会生成不同的决策树。
不展开。
2.2 ID3
信息增益
先给出信息熵与条件熵的定义。
假设是取有限个值的离散随机变量，每个的概率为
，则X的(信息)熵定义为
信息熵的值越小，代表样本集合纯度越高。
条件熵指在已知随机变量
的条件下随机变量Y的不确定性，定义为
在给定条件下
的条件概率分布的熵对
的数学期望。
信息增益表示得知特征的值而使得类的信息的不确定性减少的程度。
特征A对训练数据集D的信息增益，即
一般的，熵与条件熵之差被称作互信息，决策树学习中的信息增益等价于训练数据集中类与特征的互信息。
在决策树学习中，信息增益就表示由于特征A而使得对数据集D进行分类的不确定性减少的程度。减少程度越大，意味着信息增益越大。所以我们选择信息增益最大的特征。
ID3算法
设样本集合为D，第k类样本占比为，则
特征a对D条件熵为
其中
是特征a的可能取值，
是这种取值对应的样本数，
即a取这种值得概率。
那么，信息增益就是
过程：
输入：数据集D，特征集A，阈值
输出：决策树T
- 特殊情况：D中样本同属一个类，T为叶子。A为空集，T为叶子，按少数服从多数原则确定类别。
- 计算A中各个特征对D的信息增益，选择信息增益最大的
作为测试属性。
- 如果
，则置T为单结点树。选D中实例数最大的类作为标记，返回T
- 否则，对
，将
- 对结点i，以
为特征集，递归计算。
数据清理：
要做数据的清理，转换，相关性分析...
2.2 C4.5
ID3的缺陷：如果我们用一种特别特殊的特征，比如编号，学号...每个特征里只对应一个样本，那这种情况下，肯定为0，信息增益只剩第一项
，肯定是所有特征里最大的。但是这样生成的模型毫无泛化能力，无法对新样本进行有效预测。
信息增益比
用信息增益比来选择特征
代指Gain_ratio
分母是惩罚。划分类别越多，熵越大，比值越小。其中
称为属性a的固有值。
递归过程和ID3相同。
2.3 CART
CART(Classification and Regression Tree)分类回归树
- 分类树：基尼指数Gini Index
- 回归树：平方误差最小化
由两部分组成
- 决策树生成
- 决策树剪枝
CART决策树是二叉树
基尼指数
CART决策树采用基尼指数Gini Index来选择属性
基尼值：
直观上，基尼值反映了从数据集中任选两个样本，其类别不一致的概率。基尼值越小，纯度越高。
基尼指数Gini Index：
对于属性a，基尼系数
在通过a分成的每一块中，算Gini并乘上比例。
3 剪枝
剪枝可以减少决策树的规模（复杂度），处理过拟合的问题。
分为预剪枝和后剪枝
预剪枝
在生成时对每个结点进行估计，如果当前结点的划分不能提升泛化性能，就不划分。可以使用性能评估的方法（如留出法等）来判断。但是有欠拟合的风险。
后剪枝
在树建成之后，自底向上地进行剪枝。
极小化Cost Complexity函数：
第一项是树T的错误，第二项是正则项，代表树的复杂度，为正则化参数。
过程：
输入：树
输出：修建后的树
- 计算每个叶子节点的代价
- 计算如果这个节点回缩到父节点之后的代价，如果回缩之后代价减少了，就剪枝
- 递归地向上回溯
根据验证集上的代价决定是否剪枝
CART决策树的剪枝
详情可见：https://www.cnblogs.com/yang-ding/archive/2022/10/19/16805491.html
Step2：利用独立的验证集在子树序列中选择误差最小的。
4 连续属性与缺失属性的处理
连续值处理
C4.5和CART都使用了连续属性离散化，最简单的是二分法。
对数据集上此属性的所有值进行由小到大排序（假设共n个），取每两个邻接的值的中位数作为划分点（共n-1个）。对每个点对应的划分方法，算信息增益，或者增益比，基尼指数等来进行选择。
缺失值处理
训练集有缺失，如何划分
是数据完整的样本所占（加权）比例，
是数据完整的样本集合。
同时划入所有子节点，分别算划分到各个子节点的概率，且样本权值在与属性值对应的子结点中调整为原权值×这个属性值的概率
预测时属性值缺失
按概率决定类别
5 多变量决策树
参考：
