ch7 决策树

总览

• CLS
• ID3
• C4.5
• CART
• 决策树相关技术

CLS（概念学习系统）

思想：选择属性，根据属性值划分子集

原则：

1. 如果子集为空或属于同一类，为叶结点；
2. 否则，对应于内部结点，即测试结点；
3. 选择新属性进行划分，直至得到条件1。

算法过程：

1. 创建一个T节点，代表全体训练样本。
2. 如果T中所有的样本都是正例，创建一个以T为父节点的P节点并停止。
3. 如果T中所有的样本都是反例，创建一个以T为父节点的N节点并停止。
4. 选择一个具有值$v_1,v_2,\cdots ,v_m$的属性X，并根据他们在X上的值将T划分为子集$T_1,T_2,\cdots ,T_N$，创建N个节点$T_i(i=1,2,\cdots ,N)$，以T为他们的父节点，并将$X=v_i$作为T到$T_i$的分支的标签。
5. 对于每个$T_i(i=1,2,\cdots ,N)$，执行：$T\leftarrow T_i$，重复步骤2。

没有指定选择属性原则、方法及先后顺序，而选择的顺序对学习比较有影响。

ID3（迭代二叉树版本3）

信息熵:

$$Entropy(S)=-\sum p_k{\log }_2{p}_k$$

其中，$p_k$是当前样本集合S中k所占的比例。

信息增益：

$$Gain(S,A)=Entropy(S)-\sum _{v\in A}\frac{|S_v|}{|S|}Entropy(S_v)$$

信息增益越大说明使用属性A进行划分所获得的“纯度提升”越大（选择属性a进行划分后，将不再作为候选的划分属性）。

ID3决策树学习算法以信息增益为准则来选择划分属性，通常选择信息增益大的属性。

算法执行过程和CLS类似，但选择属性时使用的是信息增益准则，选择信息增益最大的属性作为划分属性。

归纳学习

归纳偏置：

1. 树要尽可能的矮。
2. 在构建树的过程中，高信息增益的属性优先选择。
3. 偏好偏置
4. 奥卡姆剃刀原则：无必要勿增实体，简单有效原理。

ID3可以通过对数据的子集或窗口（windows）进行归纳来处理非常大的数据集：

1. 选择整组训练实例的随机子集。
2. 使用归纳算法形成规则来解释当前窗口。
3. 扫描所有训练实例，寻找规则的例外情况。
4. 将例外添加到窗口.
5. 重复步骤2至4，直到没有任何异常为止。

优点

选择划分后信息增益大的作为划分特征，说明使用该特征后划分得到的子集纯度越高，即不确定性越小。因此我们总是选择当前使得信息增益最大的特征来划分数据集。

缺点

信息增益偏向取值较多的特征（原因：当特征的取值较多时，根据此特征划分更容易得到纯度更高的子集，因此划分后的熵更低，即不确定性更低，因此信息增益更大），但这些特征可能是无意义的特征，如用户ID，学号，日期等。如果选这些特征，每一个划分只有一个样本，是叶子节点，p是1，纯度最高。会使决策树分支过多。

C4.5

使用增益率代替信息增益。

$$GainRatio(S,A)=\frac{Gain(S,A)}{SplitInformation(S,A)}$$$$GainRatio(S,A)=\frac{Gain(S,A)}{IV(A)}$$$$SpliInformation(S,A)=-\sum _{i=1}^c\frac{|S_i|}{|S|}{\log }_2\frac{|S_i|}{|S|}$$

C4.5并非直接选择增益率最大的候选划分属性，而是使用了启发式的选择：先从候选划分属性中找出信息增益InformationGain高于平均水平的属性，再从中选择增益率GainRatio最高的。

CART（分类与回归树）

• 分类树：特征选择，树的生成，使用基尼指数(Gini index)最小化准则
• 回归树：特征选择，树的生成，使用平方误差最小化准则

分类树

基尼系数:

使用基尼指数来衡量数据的不纯度或者不确定性。若样本属于第k类的概率是$p_k$，则基尼指数定义为：

$$Gini(D)=\sum _{k=1}^K{p}_k(1-p_k)=1-\sum _{k=1}^K{p}_k^2$$

经过特征A分割之后，集合D的不确定性表示为：

$$Gini(D,A)=\sum _{v=1}^n\frac{|D_v|}{|D|}Gini(D_v)$$

选择那个使得划分后基尼指数最小的属性作为最优划分属性。

分类树

平方误差：

回归树用平方误差来表示预测误差。已知数学期望为E，平方误差定义为：

$$SE(D)=\sum _{x_i\in D}(x_i-E{)}^2$$

选择那个使得划分后平方误差最小的属性作为最优划分属性。

决策树相关技术

总览：

• 剪枝
  • 预剪枝（pre-pruning）与后剪枝（post-pruning）
  • k折交叉验证
• 连续值处理
• 属性的成本
• 缺失值处理

剪枝

决策树剪枝是一种防止决策树过拟合、提高其泛化能力的方法。剪枝通过主动去掉一些分支来降低模型复杂度，从而减小在未知数据上的预测误差。

• 主要分为预剪枝（Pre-pruning）、后剪枝（Post-pruning）两种策略。

预剪枝

预剪枝是在决策树构建过程中进行剪枝的方法。其核心思想是在每个节点划分前进行估计，若当前节点的划分不能带来决策树模型泛化性能的提升，则停止划分并将当前节点标记为叶节点。 优点：是简单快速，能够显著减少决策树的训练时间和测试时间开销，并降低过拟合风险。 缺点：由于它是一种贪心策略，可能忽略了后续划分的可能性，从而带来欠拟合的风险。

后剪枝

后剪枝是在决策树构建完成后进行剪枝的方法。其核心思想是自底向上地对非叶节点进行考察，若将该节点对应的子树替换为叶节点能够带来泛化性能的提升，则进行替换。

k折交叉验证（k-fold cross validation）

将数据集随机分成K个等份（或“折”）。对于每一次验证，使用K-1份数据作为训练集，剩余的一份作为测试集。重复上述过程K次，每份数据都被用作过测试集一次。最终模型的性能评估是K次测试结果的平均值。这种方法通常能提供更稳定的性能评估。

连续值处理

需要将连续值处理为离散值。

为连续属性选择分割点： 根据连续属性的值对示例进行排序；识别目标标签和属性值不同的相邻示例，从而得到一组候选分割点；计算每个分割点的增益，并选择具有最高增益的分割点。

属性的成本

属性的可获取性在成本方面可能有显著差异。

缺失值处理

可能的方法：

1. 将属性A的最常见值赋给未知值。
2. 将具有相同目标值的属性A的最常见值赋给未知值。
3. 为每个可能的值分配概率。