决策树
1. 基本流程
- 学习目的：为了产生一颗泛化能力强的决策树
- 基本流程：分而治之，不断选择最优划分属性
- 决策树生成是一个递归的过程，递归返回的三种情况：
- 节点包含样本是同一类别
- 属性集为空or样本所有属性取值相同
- 样本集为空
2. 划分选择
- 划原则：树的分支节点所包含的样本尽可能的属于同一类别，即节点的“纯度”越来越高
2.1 信息增益（ID3）
-
“信息熵”是度量样本集合纯度常用的一种指标
-
设样本集合D中第k类样本所占的比例为 \(p_k(k=1,2,......,y)\)，则D的信息熵定义为：
\(Ent(D)=-\sum_{k=1}^yp_klog_2p_k\)
-
\(Ent(D)\) 的值越小，D的纯度越高
-
-
用属性a对样本集D进行划分所获得的“信息增益”（information gain）为：
\(Gain（D，a）=Ent（D）-\sum_{v=1}^V\frac{|D^v|}{|D|}Ent(D^v)\)
-
一般的，信息增益越大，意味着使用属性a来进行划分所获得的“纯度提升”越大，再以信息增益为准则来划分属性
2.2 增益率（C4.5）
-
信息增益准则对可选取数目较多的属性有所偏好，为了减少这种偏好可能带来的不利影响，著名的C4.5决策树算法不直接使用信息增益，而是使用“增益率”来选择最优划分属性。
-
增益率定义为：
\(Gain\_ratio(D,a)=\frac{Gain(D,a)}{IV(a)}\)\(IV（a）=-\sum_{v=1}^V\frac{|D^v|}{|D|}log_2\frac{|D^v|}{|D|}\)
-
增益率称为属性a的“固有值”，属性a的可能取值数目越多（V越多），则IV（a）的值通常会越大
-
增益率准则对可选取数目较少的属性有所偏好，因此C4.5算法并不是直接选择增益率最大的候选划分属性，而是先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的
2.3 基尼系数（CART）
-
基尼系数反映了从数据集D中随机抽走两个样本，其类别不一致的概率，因此其基尼系数越小，数据集D的纯度越高
-
数据集D的计算：
\(Gini(D) = -\sum_{k=1}^{|y|}\sum_{k^,!=k}^{|y|}p_kp_k,=1-\sum_{k=1}^{|y|}p_k^2\) -
属性a的基尼系数为：
\(Gini\_index(D,a) = -\sum_{v=1}^V\frac{|D^v|}{|D|}Gini(D^v)\)计算得到每个属性的基尼系数后，在候选属性集合A中，选择使划分后基尼指数最小的属性作为最优划分属性。
3. 剪枝处理
- 目的：降低过拟合风险
3.1 预剪枝
- 在决策树生成过程中，对每个节点在划分前先进行估计，若当前划分不能带来决策树泛化能力的提升，则停止划分并把当前节点标记为叶子节点
- 判断泛化能力的方法：将数据集切为训练集和验证机，不断计算验证集精度，来确定剪枝与否
- 优点：降低过拟合风险，同时显著减少了决策树的训练时间开销和测试时间开销
- 缺点：预剪枝基于“贪心”本质禁止这些分支展开，可能带来欠拟合的风险
3.2 后剪枝
- 先从训练集生成一颗完整的决策树，然后自底向上对非叶子节点进行考察，若将该节点替换成叶节点能带来决策树泛化能力的提升，则将该子树替换为叶节点。
- 判断泛化能力的方法同预剪枝
- 优点：后剪枝通常比预剪枝保留了更多的分支，欠拟合风险较小，泛化性能往往优于预剪枝
- 缺点：训练时间开销大
4. 连续与缺失值
4.1 连续值处理
- 最简单的策略是采用二分法对连续属性处理（C4.5决策树算法采用的），对于属性a的n个可取值，划分为n-1个元素候选划分集合，然后像离散属性值一样来考察这些分类点，选取最佳分类点来进行样本集合的划分
- 与离散型不同，连续属性还可以作为节点的后代节点的划分标准
4.2 缺失值处理
5. 多变量决策树
- 目的：在属性坐标空间中，决策树的边界都是与轴平行的，面对一些复杂问题时，“多变量决策树”可以实现“斜划分”甚至更复杂的划分
- 多变量决策树的学习过程中，不是为每个非叶子节点寻找一个最优划分属性，而是试图建立一个合适的线性分类器（有点像感知机和神经网络的区别）
参考文献
- 周志华《西瓜书》
- 李航《统计学习方法》