• FINDS
• 决策树
  • ID3
  • CART

---

概念学习：利用有关某个布尔函数的输入输出训练样例，推断该布尔函数的学习过程。 假设空间：全部可能的概念构成的空间

FINDS

目标：寻找极大特殊假设 假设集合：H

1. 将 h 初始化为 H 中最特殊的假设
2. 对每个正例 x，对 h 的每个属性约束 $a_i$，如果 x 满足 $a_i$ 则不做任何处理，否则将 h 中的 $a_i$ 替换为 x 满足的下一个更一般的约束
3. 输出假设 h

决策树

决策树的预测过程就是针对数据的各个特征对实例进行分类的过程

ID3

Iterative Dichotomiser 3

• 经验熵 $H(p) = - \sum_{i=1}^n p_i \times \log_2p_i$
• 条件熵 $H(S|A) = \sum_{i=1}^np_iH(Y|X=x_i) = \sum_{i=1}^np_i(-\sum_{j=1}^mp_j\log_2p_j)$
• 信息增益 $g(D, A) = H(D) - H(D|A)$

计算对数据集中标签信息增益最大的特征作为节点的标记，直到所有特征都被使用或者数据集能够被完全划分。 策略：信息熵最小化（确定性最大化） 改善过拟合：剪枝

• 通过删除某个属性后在测试集上的准确率是否提升
• 通过加入对模型规模的考虑
• 通过测试的泛化误差

CART

递归构建的二叉决策树，使用基尼指数来选择划分属性。

---