决策树

约 320 个字 预计阅读时间 2 分钟

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

决策判断

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

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

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

• 信息熵：”纯度“衡量指标，信息熵越大，说明集合的不确定性越大，“纯度”越低
  • 定义：\(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) \]