Decision Tree
1. Information Theory 信息论基础
训练集 D ， K 个类别 \(C_k\) ，
某特征 A 有 n 个取值，不同取值将 D 划分为 n 个子集 \(D_1, \dots, D_n\) ，
\(D_i\) 中属于类 \(C_k\) 的样本集合为 \(D_{ik}\) 。
1.1 Entropy 熵
随机变量的熵：
\[ H(X) = - \sum_{i=1}^n p_i \log p_i \]其中 \(p_i = P(X = x_i)\) ，是随机变量取某个值时的概率。
数据集 D 对于类别 C 的熵：
1.2 条件熵
已知 X 时 Y 的不确定性：
$$ H(Y|X) = \sum_{i=1}^n p_iH(Y|X = x_i) $$ 其中 \(p_i = P(X = x_i)\) 。
在特征 A 已知的情况下，类别 C 的熵：
1.3 信息增益
特征 A 对数据集 D 的信息增益：
$$ g(D, A) = H(D) - H(D|A) $$ 表示特征 A 对数据集 D 的分类的不确定性减少的程度。
信息增益大的特征具有更强的分类能力。
2. 生成决策树
2.1 ID3
对于分类到某个阶段的当前节点，以及其对应的训练集 D：
- 若 D 中所有实例属于同一类，则为叶节点。
- 若特征集合 A 为空，也就是能用与分类的特征都在之前的节点用完了，则为叶节点；分类标记为该节点中数量最多的类。
- 不属于以上两种，计算 A 中各特征对 D 的信息增益，选使之最大的 \(A_g\) 。
- \(g(D, A_g) < \epsilon\) ，也就是增益太小了而可以忽略，则为叶节点，分类标记为该节点中数量最多的类。
- 否则，用 \(A_g\) 的每一取值，划分 D 为若干 \(D_i\) 作为子节点。对每个子节点：
- \(D_i = \Phi\) 为空（没有这一取值的样本），则此叶节点的类标记取 D 中数量最多的类。
- 否则，以 \(D_i\) 为训练集， \(A - A_g\) 为特征集，递归！
Problem
ID3 倾向于选择“分支较多”的特征。
解决办法：用信息增益比选择特征的 C4.5 算法。
2.2 C4.5
信息增益比：
在信息增益的基础上，除掉 D 关于特征 A 的熵。
如果特征 A 有很多取值，把 D 划分成很多子集 \(D_1, \dots, D_n\) ，该特征的熵就大，导致信息增益比小。
如此避免了选择划分太细的特征。
对连续值特征的处理
对连续值属性 A ，找到一个属性值 \(a_0\) ，\(\le a_0\) 的划分到左子树，\(> a_0\) 的划分到右子树。
Problem
信息增益比倾向于选择“分割不均匀”的特征。
解决办法：组合法：
先选择几个信息增益大的特征，再从中选择信息增益比最大的特征。
2.3 剪枝
为了减缓过拟合，需要（后）剪枝，对模型做“简化”。
- 计算每个节点的经验熵。
- 从下至上，递归地“回缩”叶节点。若回缩后损失函数不比原来大，则剪枝。
- 不断迭代上一步，直至不能继续。
Notations: 树 \(T\) 的节点数量为 \(|T|\) ， \(t\) 为树 \(T\) 的节点，该节点有 \(N_t\) 个样本，其中 \(k\) 类的样本点有 \(N_{tk} ~(k = 1, \dots, K)\) 个。
损失函数 \(C_a(T)\) 有两部分：
- \(C(T)\) 反映了模型对训练数据的预测误差。
- \(|T|\) 反映模型的复杂程度。
经验熵（即节点 \(t\) 处的熵）：
所有节点的经验熵与样本个数乘积的和：
加上对模型复杂度的惩罚，损失函数为：
（ \(a \ge 0\) 为参数。）
选择损失函数最小的模型。