知识卡片
决策树递归划分样本
决策树在结点上选一个测试条件,把数据分到子结点,重复这一过程。若样本已属同一类就成为叶子;无法再按属性区分时可用多数类标记,空子结点也需要回退规则。根到叶的路径把多个条件连接成一个判断,因此树既能预测,也能表达可读的场景;划分过程是可计算的局部选择,不等于搜索到全局最优树。
结构图:
flowchart TD
A[当前结点样本] --> B{仍需且能够划分}
B -->|是| C[选择测试条件]
C --> D[分配到子结点]
D --> A
B -->|否| E[生成叶子及预测]
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第4章 使用体系化分析方法进行场景挖掘 4.2 体系化分析常用工具 · 查看原书依据
不同问题、不同场景的决策树结构都是如此,根据一些特征对样本进行划分,直到获取样本结果的叶结点。通过决策树,我们可以清晰地看到样本经历了哪些特征、通过怎样的判断而最终落到了哪个叶结点上。 对于给定的属性集,可以构造大量不同的决策树(如根据不同选取顺序或不同阈值对样本进行切分)。尽管其中一个或一些树较其他树的表现可能更优秀,但是由于搜索空间的指数规模有限,寻找最优方案在计算、实现层面是不可行的。尽管如此,前辈们还是开发了一系列有效的算法,实现了在可控的时间内给出一个比较优秀的次优解。Hunt算法是多种决策树算法的基础,递归流程如下。 设Dt是与结点t相关联的数据,y={y1,y2,…,yc}是样本的类别标签。 若Dt中全部样本都属于同一个类别yt,则t为叶结点,无须继续分裂。 若Dt中的样本存在多个类别,则选择一个特征(属性测试条件),将当前的数据集划分为若干更小的子集。对于测试条件的每个输出,创建子结点,根据测试结果将Dt中的样本划分到子结点中。对于每个子结点,递归调用该算法。 上述算法较为严苛,如果在算法第二步中创建的子结点不包含任何数据记录(除非属性值的各种组合在数据中均存在,且都具有唯一的类别编号),则该子结点就成为叶结点,类别标签为其父结点数据中数量最多的类别标签。 另外,在算法第二步中,如果与Dt相关联的数据具有相同的属性值(但类别标签不同),则无法继续划分。此时,该结点就成为叶结点,类别标签为该结点数据中数量最多的类别标签。