『machine learning-5』decision tree

决策树

一、决策树流程

• 决策树结构：一个根节点、若干个内部节点、若干个叶节点

  • 根节点：包含样本全集
  • 内部节点：一个内部节点对应于一个属性测试，其包含的样本集根据属性测试的结果被划分到子节点中
  • 叶子节点：一个叶子节点对应于一个决策结果

• 决策树学习算法：“分治思想”，每个样例有其对应的属性值（即类别）

输入：训练集 D = {(x1, y1), ..., (xm, ym)};
	 属性集 A = {a1, a2, ..., ad};
-------------------------------------------
TreeGenerate(D, A) {
	生成新节点node;
	if (D中样本/* 全部属于同一类别C */) {
		/* 已经分好类了 */
		将node标记为C类叶子节点;
		return;
	}
	if (D中样本/* 在A上属性值彼此相等 */ || size(A) == 0) {
		/* 当前决策属性已无法划分数据集 */
		将node标记为叶子节点，其类别标记为 /* D中样本数最多的类 */;
		return;
	} 
	
	从A中选出最优决策属性A*;
	for each value in A* {
		生成node的一个分支，令D_value表示为/* 在A*中属性取值为value的样本子集 */;
		if (size(D_value) == 0) {
			/* 说明D_value对应的属性值不具备划分能力，只能继承父节点的优势类别 */
			将新生成的分支节点标记为叶子节点，其类别标记为 /* D中样本数最多的类 */;
			return;
		} else {
			/* 还可以继续根据属性值value 划分样本 */
			return TreeGenerate(D_value, A-{A*})
		}
	}
}

---

二、划分选择

• 决策树学习算法中的关键在于选择最优划分属性，以提高分支节点所包含的样本类别纯度

• 信息熵：度量样本集合纯度的常用指标，设样本集合D中第k类(\(1 \le k \le m\))样本所占比例为\(p_k\)，则D的信息熵： \[ \text{Ent}(D) = -\sum_{k=1}^ m p_k\log_{2}p_k \] 信息熵\(\text{Ent}(D)\)的值越小，则D的纯度越高（对于二分类m=2）

• 信息增益：描述某属性的划分纯度，设离散属性a有V个可能的取值\(\{a^1, a^2, ..., a^V\}\)

  属性a可以将样本D划分为V个分支节点：第v个子节点包含了D在属性a上取值为\(a^v\)的样本集合\(D_v\)，信息增益有如下式子计算： \[ \text{Gain}(D, a) = \text{Ent}(D) - \sum_{v=1}^V\frac{|{D^v}|}{|{D}|}\text{Ent}(D^v) \] 上式中第一项是划分前的熵，第二项是划分后的熵期望（各子集熵的加权和）

• 划分流程：算出当前节点样本集的信息熵，再算出当前节点样本集在各属性下的信息增益

• 增益率：上面的信息增益准则可能对取值数目较多（V较大）的属性有所偏好，需要对信息增益准则做调整，引入增益率的概念： \[ \text{Gain}\_\text{ratio}(D, a) = \frac{\text{Gain}(D, a)}{\text{IV}(a)} \\ \text{IV}(a) = -\sum_{v=1}^V\frac{|{D^v}|}{|{D}|}\log_2{\frac{|{D^v}|}{|{D}|}} \] 其中\(\text{IV}(a)\)代表属性a的固有值：属性a的取值数目越多（V越大），则\(\text{IV}(a)\)通常越大（分的越散），能够对信息增益Gain(D, a)做出平衡调整

• 基尼指数：反映了从数据集D中随机抽取两个样本，其类别不一致的概率
  基尼指数越小，数据集D中类别不一致的可能性越低，纯度也越高。设样本集合D的类别数为m： \[ \begin{align} \text{Gini}(D) &= \sum_{k=1}^m \sum_{k' \ne k} p_kp_k' \\ &= 1 - \sum_{k=1}^mp_k^2 \end{align} \] 注意：对于任意一种选取的标准指数index，都要求解使index取最大（最小）的属性a，以确定最优划分属性

---

三、剪枝处理

• 剪枝处理的目的：通过主动去掉一些分支，以降低过拟合的风险

• 剪枝策略：分为“预剪枝”和“后剪枝”

  • 预剪枝：在决策树的生成过程中对每个结点划分前后的泛化性能进行估计，只有泛化性能提升才划分

    • 验证方式：预留一部分数据用作验证集（留出法）

    • 划分前：根据决策树学习算法，将当前节点的类别标记为其优势类别，再求出划分前准确度

    • 划分后：选择某个属性划分出若干子节点，并如上确定各子节点的类别，再求出划分后精确度

      注意：划分后的精确度需要使用假设进行划分后的所有子节点对验证集进行预测
      预剪枝基于“贪心”策略，显著降低了训练和测试时间的开销，但提高了欠拟合风险

    ---

  • 后剪枝：先从训练集生成完整的决策树，再依次尝试将各中间节点替换为叶节点（剪去其所有子节点）

    • 验证方式：同“预剪枝”使用留出法

    • 对每一个中间节点：先将其直接替换为叶子节点，再标记为优势类别，最后比较替换前后在验证集上的精确度（反复修剪直至泛化能力降低为止）

      注意：后剪枝策略通常比预剪枝策略保留了更多的分支，欠拟合风险较小，但训练时间开销要大得多（基于完整的决策树）

  • 奥卡姆剃刀原理：简单的模型泛化能力更好（“如无必要，勿增实体”）

---

四、连续与缺失值

• 连续属性：属性值的分布是连续（而非离散）的

• 连续属性向离散属性转化：二分法，设样本集D和连续属性集a，a在D上出现了n种不同取值\(\{a^1, a^2, ..., a^n\}\)

  则候选的划分点集合\(T_a = \{\frac{a^i + a^{i+1}}{2} | 1 \le i \le n-1\}\)，其中n-1个二分取值分别可将数据集D划分为两个子集

  注意：连续属性的待选划分点即为\(T_a\)，而不是原先离散的a

  ---

• 缺失值处理：在属性值缺失的条件下选择划分属性；在划分属性上值缺失该如何划分样本

  • 选择划分属性：设数据集D和属性a，令\(\overset{\sim}{D}\)表示D中在属性a上没有缺失值的样本子集

    即\(\overset{\sim}{D}\)中的样本在属性a上都有取值

    • 设属性a有V个可取值\(\{a^1, a^2, ..., a^V \}\)，

      设\(\overset{\sim}{D^v}\)表示\(\overset{\sim}{D}\)中在属性a上取值为\(a^v\)的样本子集；\(\overset{\sim}{D_k}\)表示\(\overset{\sim}{D}\)中属于第k类的样本子集

    • 定义权重：为每个样本x赋予一个权重\(\omega_x\)，并定义： \[ \begin{align} &\rho = \frac{\sum_{x\in \overset{\sim}{D}} \omega_x}{\sum_{x\in D} \omega_x} \quad 即在属性a上无缺失值的样本比重 \\ &\overset{\sim}{p_k} = \frac{\sum_{x \in \overset{\sim}{D_k}}\omega_x}{\sum_{x \in \overset{\sim}{D}}{\omega_x}} \quad 即在属性a上无缺失值的样本中第k类所占比重 \\ &\overset{\sim}{r_v} = \frac{\sum_{x \in \overset{\sim}{D^v}}\omega_x}{\sum_{x \in \overset{\sim}{D}}\omega_x} \quad 即在属性a上无缺失值的样本中属性取值为a^v所占比重 \end{align} \]

    • 公式推广：利用推广公式决定划分属性a

      广义信息熵如下：其中m表示样本集\(\overset{\sim}{D}\)中的类别总数 \[ \text{Ent}(\overset{\sim}{D}) = -\sum_{k=1}^{m} \overset{\sim}{p_k}\log_{2}{\overset{\sim}{p_k}} \] 广义信息增益如下： \[ \begin{align} \text{Gain}(D, a) &= \rho \times \text{Gain}(\overset{\sim}{D}, a) \\ &= \rho \times (\text{Ent}(\overset{\sim}{D}) - \sum_{v=1}^V\overset{\sim}{r_v}\text{Ent}(\overset{\sim}{D_v})) \end{align} \] 注意：推广公式中的三个调整值都是无缺失情况公式的一般例（取\(\overset{\sim}{D} \ne D\)）

  ---

• 划分样本：设划分属性已经确定为a，解决对样本x的分类问题

  • 若样本x在划分属性a上的取值已知，则直接将该样本划入到对应的子节点，其样本权值保持为\(\omega_x\)

  • 若样本x在划分属性a上取值未知，则将该样本同时划入所有子节点

    其中对于每个属性值为\(a^v\)的子节点，x的样本权值由\(\omega_x\)调整为\(\overset{\sim}{r_v} * \omega_x\)（样本权重在子节点中依比例收缩）

---

五、多变量决策树

• 属性空间：每个属性对应了空间中的一条坐标轴

  样本拥有d个属性，表明样本是位于d维空间的一个坐标点

  对样本分类 \(\Leftrightarrow\) 寻找样本点集之间的边界

• 单变量决策树：每个中间节点都只基于单个最优属性做出决策

• 多变量决策树：每个中间节点可基于多个属性的组合做出决策，如线性分类器 \(\sum_{i=1}^d \omega_ia_i \le t\)，其中\(\omega_i\)表示属性\(a_i\)的权重