【主要内容】

• 决策树简介
• 数据集中度量一致性
• 使用递归构造决策树
• 使用Matplotlib绘制树

【数据集度量】

• 信息增益
  • 克劳德·香农：信息论之父
  • 熵：信息的期望值
  • 信息：l(x_i) = -logp(x_i)
  • 参考材料
    • 《信息论》香农
    • 《财富公式》威廉·庞德斯通
• 计算数据集的熵——DONE

【划分数据集】

• 对每一个特征划分数据集，度量划分数据集熵
• 计算信息增益
  • g(D|A) = H(D) - H(D|A)
  • H(D|A) = sum { |D1|/|D| * H(D_1), |D1|/|D| * H(D_1) ... |Dn|/|D| * H(D_n) }
• 选择g(D|A)最大的A
• 划分splitData

【构建决策树】

• 中止条件：
  • dataSet中，只有一类数据，返回该类（作为叶子）；
  • dataSet中只有一种特征，返回主要类（作为叶子）
• 找到最优特征，（通过遍历所有特征，计算并寻求最大增益熵）
• 找到最优特征对应的feature label，生成一个root节点，设置feature label为节点标签
• 遍历最优特征的所有特征值，对每个特征值，抽取数据集合
• 对每一个数据子集合递归生成一个决策树，挂在当前树下
• 返回当前tree

【绘制tree】

• DONE

Paste_Image.png

【剪枝】chapter 9