← 返回刚才阅读的位置

知识卡片

结构图卡 · 9827.e · 生成模型:DeepSeek-V4.1-Flash

ID3的递归生成流程

理解等级:中级

ID3 的输入是训练集 D(M 个样本)、类别集合 C、特征集合 F,外加一个停止分裂的阈值 ε;输出是一棵多叉树。它的递归骨架可以压缩成四道判断:

  1. 全同类? D 中样本已经属于同一类别,直接返回单节点,不做任何分裂。
  2. 特征用光? 样本不纯但 F 只剩一个(或没有)特征,返回单节点,取 D 中样本数最多的类作为该节点类别——这是一种”少数服从多数”的兜底。
  3. 增益够大吗? 计算 F 中每个特征的信息增益,取最大的那个;若连它都小于阈值 ε,说明继续分下去收益太低,同样返回单节点并用多数类兜底。
  4. 切开并递归。 按选中特征 Fn 的所有取值种类把 D 分成若干子集,每个子集生成一个子节点;在每个子节点上令 D=Di、F=F−Fn,回到第 1 步。

两个细节决定了它的性质。一是”F−Fn”:该特征被用掉后从候选集中永久移除,因此同一个特征在一棵 ID3 树里只出现一次,取值多的特征一次就把数据切得很碎。二是”按所有取值种类开叉”:婚姻状况有已婚、未婚、离婚三种取值,就直接长出三棵子树,是典型的多叉树。

阈值 ε 是 ID3 里唯一的复杂度旋钮,它属于 [[预剪枝与后剪枝的代价]] 中的先剪枝:分裂前就拦住收益低的分支。停得早树小、可能欠拟合,停得晚树大、可能过拟合,ε 的取值就是这条权衡线。

结构图:

flowchart TD
    A[输入 数据集D 特征集F 阈值ε] --> B{D 全属同一类?}
    B -->|是| C[返回单节点 取该类]
    B -->|否| D{F 已无可用特征?}
    D -->|是| C
    D -->|否| E[算各特征信息增益 取最大]
    E --> F{增益小于ε?}
    F -->|是| C
    F -->|否| G[按该特征所有取值开多叉]
    G --> H[子节点令 D=Di F=F−Fn]
    H --> B
这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《机器学习基础:从入门到求职》第6章《决策树》(源文件:extracted/机器学习基础:从入门到求职/_epub-src/OEBPS/text00009.html) - 结论依据:原文以"输入—输出—步骤"形式列出 ID3 五步,明确全同类返回、特征耗尽返回多数类、增益小于 ε 返回多数类、按取值种类分叉、子节点递归时从 F 中剔除该特征。 - 原始内容:输入:假设训练数据集D包含M个样本;样本一共含有K个类别,类别集合为C;每个样本含有N个特征,特征集合为F;停止分裂的阈值为ε。