秋季课程: 机器学习入门——决策树 （二）

前言：

这个秋季，三碗饭会开始更新自己在秋季课程的笔记，主要包括Introduction to ML，可能还会有Complier Construction 以及 Computer Graphics.

本文主要记录Machine Learning基础知识。

1. Example: Animal Classification 示例：动物分类

Decision trees can be used to classify animals based on their features.
决策树可以根据动物的特征来进行分类。

Features 特征

• Vertebrate (脊椎动物)
• Mammal (哺乳动物)
• Can fly (能否飞行)
• Aquatic (是否水生)
• Reptile (爬行动物)
• Amphibian (两栖动物)
• Fish (鱼类)

Diagram 图示：

Is vertebrate? (是否是脊椎动物)
 ├── No → (Not vertebrate 非脊椎动物)
 └── Yes
      ├── Is it a dog? (是否是狗)
      │     ├── Yes → Mammal 哺乳动物
      │     └── No
      │          ├── Can fly? (能否飞行)
      │          │     ├── Yes → Bird 鸟类
      │          │     └── No
      │          │           ├── Is aquatic? (是否水生)
      │          │           │     ├── Yes → Amphibian 两栖动物
      │          │           │     └── No
      │          │           │          └── Reptile 爬行动物

2. Decision Tree Construction 决策树构建

Pseudocode 伪代码：

DT_construction
Input: D
Output: t <- root node of the tree
输出: t <- 树的根节点

DT_construct(D)
 t = newNode()                # 新建节点
 label(t) = representativeClass(D)  # 标签 = D的代表类
 
 if impure(D) then             # 如果数据集D不纯
     criterion = splitCriterion(D)  # 按划分标准分裂
 else return(t)                # 否则返回节点

 [D1, ..., Dm] = decompose(D, criterion)   # 按标准分裂数据
 For each Dj in [D1, ..., Dm] do
     add Successor(t, DT_construct(Dj))    # 递归构建子树
 return(t)

3. Decision Tree Classification 决策树分类

Pseudocode 伪代码：

DT_classify(x, t)
 if isLeaf(t) then             # 如果是叶子节点
     return(label(t))          # 返回标签
 else return DT_classify(x, splitSuccessor(t,x))  
      # 否则递归进入下一分支

4. Data Table 数据表

Example dataset 示例数据集：

5. Example Splits 示例划分

Decision tree chooses features to split on.
决策树通过选择特征进行划分。

Example 例子：

Split on "Scales" (是否有鳞片)
 ├── Yes → Reptile 爬行动物
 └── No
      ├── Split on "Lungs" (是否有肺)
      │     ├── Yes → Mammal 哺乳动物
      │     └── No → Fish 鱼类

6. Feature: Number of Legs 特征：腿的数量

#legs (腿的数量)
 ├── 0 → Fish 鱼类 / Amphibian 两栖动物
 ├── 2 → Bird 鸟类 / Mammal 哺乳动物
 └── 4 → Mammal 哺乳动物 / Reptile 爬行动物

Summary 总结

• Decision Trees use features to split data into subgroups.

• 决策树通过 特征 将数据划分为 子集。

• At each node, the algorithm chooses the best split criterion.

• 在每个节点，算法选择最佳划分标准。

• Final leaves correspond to classes.

• 最终的叶子节点对应 类别。