西瓜书第四章

基本流程

决策树的每一个叶子结点表示一个决策结果，每个中间节点表示一个属性测试。

学习目的为生成一颗泛化能力强的决策树（处理未见示例能力强）

决策树学习的基本过程是递归下降的划分过程，节点对给定的数据集和属性集学习并得到一个划分或者将自己标记为叶子结点。

划分选择

决策树学习的关键步骤在于选择合适的最优划分属性。

信息增益

使用信息熵（频率负对数的期望）来度量样本集合纯度。

𝐸𝑛𝑡(𝐷)=?∑|𝑦|𝑘=1𝑝𝑘𝑙𝑜𝑔2𝑝𝑘 值越小表示样本集合D的纯度越高。

定义信息增益，度量使用属性a对样本进行划分后的性能提升。其中划分后的值为各个子节点的信息熵的加权和。

𝐺𝑎𝑖𝑛(𝐷,𝑎)=𝐸𝑛𝑡(𝐷)?∑𝑉𝑣=1|𝐷𝑣||𝐷|𝐸𝑛𝑡(𝐷𝑣)值越大表示提升越多。

每一次划分时，选择信息增益最大的属性用于划分。

增益率

信息增益准则对于可选择值数目更多的属性有所偏好，使用增益率选择划分属性可减少其不利影响

𝐺𝑎𝑖𝑛𝑟𝑎𝑡𝑖𝑜(𝐷,𝑎)=𝐺𝑎𝑖𝑛(𝐷,𝑎)𝐼𝑉(𝑎)
其中定义了属性的固有值

𝐼𝑉(𝑎)=?∑𝑉𝑣=1|𝐷𝑣||𝐷|𝑙𝑜𝑔2|𝐷𝑣||𝐷|用来减少取值数目的影响，但是对取值数目较少的属性有所偏好

折衷：先选出信息增益高于平均水平的属性，再从中选择增益率最高的

基尼指数

CART算法定义基尼指数用于度量数据集的纯度

𝐺𝑖𝑛𝑖(𝐷)=1?∑[𝑌]𝑘=1𝑝2𝑘
定义属性的基尼指数

$\sum{v=1}^{V}\frac{|D^v|}{|D|}Gini(D^v)$

选择使划分后基尼指数最小的属性来划分

剪枝处理

用于处理过拟合的情况，即去掉一些分支降低过拟合风险。

预剪枝：划分之前判断该次划分能否提升性能。

后剪枝：对于生成的决策树自底向上判断非叶节点能不能换为叶子节点。

预剪枝
每次划分之前，对于划分前后的泛化性能进行估计

使用正确率、假正率/假反率等在验证集上进行判断

精度不变、精度降低、内部样例已经为同一类时，不进行划分

后剪枝
对于已经得到的一颗决策树，自底向上考虑每一个非叶子节点。

如果使用节点取代子树后精度提高或者不变，则进行剪枝。

后剪枝得到的决策树更小但是训练成本高。

连续与缺失值

连续属性的处理
使用连续属性离散化技术

对于数据集中取值连续的N个点，选择相邻两点的中位值作为作为候选划分点

通常可以将划分点选择为数据集中不高于中位点的最大值

注意使用连续值划分后，子树中仍然可使用同一连续属性

缺失值的处理
由于存在不完整样本，某些样本的某些属性值缺失

（1）如何选择划分属性（2）对于不完整样本如何在该属性下划分

首先选择在属性a下没有缺失值的样本子集𝐷? 从而得到取值为𝑎𝑣的元素𝐷𝑣~
定义一系列常数，并将原本的公式推广得到𝐺𝑎𝑖𝑛(𝐷,𝑎)=𝜌×𝐺𝑎𝑖𝑛(𝐷? ,𝑎)=𝜌×(𝐸𝑛𝑡(𝐷? )?∑𝑟? 𝑣𝐸𝑛𝑡(𝐷𝑣~))、𝐸𝑛𝑡(𝐷? )=?∑𝑝? 𝑘𝑙𝑜𝑔2𝑝? 𝑘
相当于将属性缺失的样本按不同概率划分到不同的子类中