决策树

概念：决策树将分类问题分解为若干基于单个信息的推理任务，采用树状结构逐步完成

决策判断

• 非叶子节点：对分类目标在某个属性上的一个判断
• 分支：基于该属性做出的一个判断
• 叶子节点：分类结果

  决策树可以看作一系列以叶子节点为输出的决策规则

构建：决定划分属性的==顺序==选择，性能好的决策树随着划分不断进行，决策树分支结点样本集的“纯度”会越来越高

• 信息熵：”纯度“衡量指标，信息熵越大，说明集合的不确定性越大，“纯度”越低
  • 定义：\(K\)个信息组成样本集合\(D\)，记第\(k\)个信息发生的概率为\(p_k(1\leqslant k\leqslant K)\) \(\sum p_k=1\)

\[ E(D)=-\sum_{k=1}^kp_k\log_2p_k \]

• 信息增益：选择属性划分样本集前后信息熵的减少量称为信息增益（衡量样本集合不确定性减少的程度）
  • 定义：属性取值\(a_i\)划分出的子样本记为\(D_i\)，样本子集包含的样本数记作\(|D_i|\)

\[ \text{Gain}(D,A)=E(D)-\sum_{i=1}^n\dfrac{|D_i|}{|D|}E(D_i) \]

越靠近根节点，区分度越大

• 问题：信息增益偏向选择分支多的属性（导致过拟合）
• 解决：对分支过多进行惩罚
  • 信息：分行为本身带来的信息

\[ \text{info}=-\sum_{i=1}^n\dfrac{|D_i|}{|D|}\log_2\dfrac{|D_i|}{|D|} \]

\[ \text{Gain-ratio}=\text{Gain}(D,A)/\text{info} \]