西瓜书-决策树

4.1 基本流程

1. 广泛应用：决策树是一种常见的机器学习算法，广泛用于分类和回归问题。它通过一系列的决策规则将数据集划分为不同的子集，从而做出预测。
2. 基本流程：
   1. 在构建决策树时，首先需要根据某种标准选择特征来进行划分（详见 4.2 节）。
   2. 决策树的每次划分都基于选定的特征，将数据集划分成多个子集，直到每个子集满足某种停止条件（如纯度、叶节点分类单一等）。

4.2 划分选择

1. 信息熵：用于度量样本集合的纯度。信息熵越小，样本越纯（即样本更趋向于属于同一类别）。
2. 信息增益：
   • 决策树通过信息增益来选择特征进行划分。信息增益衡量的是划分后样本集合的熵减少程度。信息增益越大，特征越适合作为划分依据。
   • ID3算法使用信息增益作为选择标准，但倾向于选择取值较多的属性，这可能导致决策树过度复杂（如每个样本一个分叉的情况）。
3. 增益率（C4.5算法）：C4.5算法不直接使用信息增益，而是使用增益率，以减少信息增益对可取值较多属性的偏好。C4.5会优先选择信息增益高于平均水平的属性，再从中选择增益率最高的属性进行划分。增益率会偏好取值较少的属性，需要对结果进行调整。
4. 基尼指数（CART算法）：CART算法使用基尼指数来选择最优划分属性。基尼指数用于衡量数据集的纯度，基尼指数越小，数据集越纯。

4.3 剪枝处理

1. 剪枝的目的：剪枝的主要目的是为了避免过拟合。过拟合会导致决策树在训练数据上表现良好，但在新数据上泛化能力较差。
2. 预剪枝与后剪枝：
   • 预剪枝：在构建决策树时提前停止划分，限制树的深度或节点数量。
   • 后剪枝：构建完整的决策树后，通过合并或删除叶节点来减少树的复杂度。后剪枝比预剪枝更有效，通常能避免欠拟合。
3. 决策树桩：决策树桩是只有一层分划的极简决策树，常用于简单场景下的分类任务。

4.4 连续与缺失值处理

1. 连续值处理： 决策树最初设计时只处理离散值。对于连续值，通常采用离散化的方法处理，或者通过计算信息增益来确定最佳划分点。
2. 缺失值处理： 决策树在处理缺失值方面具有一定优势。通过引入权重，决策树能够在划分过程中公平地考虑带有缺失值的样本，而不是简单地丢弃这些样本。
3. 权重的确定： 缺失样本的权重可以根据无缺失样本的比例确定，确保缺失值样本能够合理参与决策树的划分过程。

4.5 多变量决策树

1. 多变量决策树的划分能力： 普通的决策树的分类面与坐标轴平行，而多变量决策树能够通过组合多个属性进行划分，形成斜线甚至更复杂的划分面。
2. 其他划分准则： 除了信息增益、增益率和基尼指数，研究者还设计了许多其他划分准则。这些准则在特定场景下可能会影响决策树的构建和尺寸，但对模型的泛化性能影响较小。
3. 剪枝的重要性： 尽管不同的划分标准对决策树的尺寸有一定影响，但剪枝方法和剪枝的程度对决策树的泛化能力影响更为显著。