决策树

基本流程

决策树是基于树结构来进行分类，叶子节点对应决策结果，分支节点对应一个属性测试

决策树的递归过程有三种情况导致返回

• 当前节点包含的样本全部判定为同一类别，无需划分
• 当前属性集为空，或是所有样本在所有属性上取值相同，无法划分，该节点作为叶子节点
• 当前节点包含的样本集为空，无法划分，该节点作为叶子节点，决策结果为父节点样本最多的类别

划分选择

决策树的每个节点需要从属性集中选择最优的划分属性，再根据该属性进行样本集划分

信息熵

通常使用信息熵度量样本集合纯度，设样本集 D 中第 k 类样本所占比例为 $p_k$，则信息熵定义为

$$Ent(D)=-\sum\limits^{\vert C\vert}_{k=1}p_k\log_2p_k$$

信息熵的值越小，D 的分类纯度越高

信息增益

对于一个特定属性 a 可以计算它的信息增益，设属性 a 的取值为 $a^1,a^2,...,a^V$，所有在属性 a 上取同一个值的样本的集合为 $D^v$，则属性 a 的信息增益为

$$Gain(D,a)=Ent(D)-\sum\limits^V_{v=1}\frac{\vert D^v\vert}{\vert D\vert}Ent(D^v)$$

属性的信息增益越大，使用该属性进行划分获得的纯度提升越大，ID3 决策树算法就是使用信息增益作为划分准则

增益率

信息增益的划分准则对取值数目较多的属性具有偏好，在 C4.5 决策树算法中使用增益率作为划分准则

$$\begin{aligned} Gain\_ratio(D,a)&=\frac{Gain(D,a)}{TV(a)}\\ IV(a)&=-\sum\limits^V_{v=1}\frac{\vert D^v\vert}{\vert D\vert}\log_2\frac{\vert D^v\vert}{\vert D\vert} \end{aligned}$$

$IV(a)$ 称为属性 a 的固有值，属性取值越多，固有值越大，增益率准则对属性取值较少的属性具有偏好

基尼指数

基尼指数反映了从 D 中随机抽取两个样本，它们不属于同一类的概率，基尼指数越小，样本集纯度越高

$$Gini(D)=\sum\limits^{\vert C\vert}_{k=1}\sum\limits_{k'\ne k}p_kp_{k'}=1-\sum\limits^{\vert C\vert}_{k=1}p_k^2$$

属性 a 的基尼指数为

$$Gini\_index(D,a)=\sum\limits^{\vert V\vert}_{v=1}\frac{\vert D^v\vert}{\vert D\vert}Gini(D^v)$$

剪枝处理

决策树算法使用剪枝来解决过拟合，分为预剪枝和后剪枝

• 预剪枝

  在每个节点确定划分前先比较划分前和划分后的预测精度，若划分后精度大于划分前精度，则确定当前属性划分

  预剪枝会阻止精度较低的判定分支展开，这可能导致后续精度提升较大的划分无法展开，导致欠拟合

• 后剪枝

  先训练一棵决策树，自底向上对分支节点判断将分支节点替换为叶子节点是否能提升泛化性能，若能，则替换为叶子节点

连续与缺失值

在连续值属性上使用决策树算法，首先需要将连续值转换为离散值，最简单的方法是使用连续值属性取值的中间值作为阈值，将大于阈值和小于阈值的归为两类

对于缺失值，记 $\tilde D$ 为数据集 $D$ 上属性 a 无缺失值的样本集，属性 a 的取值为 $a^1,a^2,..,a^V$，为每个样本设置一个权重 $\omega_x$，定义比值 $\tilde r_v$

$$\tilde r_v=\frac{\sum_{x\in\tilde D^v}\omega_x}{\sum_{x\in\tilde D}\omega_x}$$

若样本 x 在属性 a 上取值已知，则将该样本划分到对应的子节点，权值为 $\omega_x$，若取值未知，则将该样本划分到所有节点，每个节点中的权重为 $\tilde r_v\cdot\omega_x$，即将该样本以不同的概率划分到不同的节点中

多变量决策树

从属性空间来看，决策树分类形成的分类边界与空间的每个轴是平行的，这样难以实现复杂的划分，使用多变量决策树可以实现复杂划分

多变量决策树在进行决策时，不是使用一个单一属性，而是使用多个属性的线性组合，即每个分支节点是一个无偏移的线性分类器