Decision Tree

归纳偏置: 优先选择较小的树

决策树

根开始，到叶子节点，对实例进行分类。树上的节点对应每个实例的属性的测试，后继分支代表该属性的一个可能值。

本质上，它代表实例属性值的合取(conjuction, 从根到叶子节点)的析取式(disjunction, 一个根节点的不同的可能性)

适用问题特征

下面三点比较显然。

• 实例由 "属性-对" 组成，属性对应的值可以式离散的，也可以是分区间连续的。

• 目标函数有离散的输出值，如布尔型分类，或两个以上输出值的分类器。

• 需要析取的描述

下面两点值得探讨。

• 实例集可以包含错误？？

• 实例集可以包含缺少属性值的实例？？

ID3 算法

使用贪婪算法。

核心问题是选择每个节点要测试的属性。如何衡量一个属性具有最好的选择能力？这里使用信息增益。

信息增益

• 熵

给定一个样例集，有熵

\[ entropy(S)=\sum_{i=1}^c -p_i\log_2 p_i \]

这里 \(c\) 表示状态数，\(p_i\)表示某一分类值得实例占比。可知上式最大值是\(\log_2 c\), 当每一个状态数的实例相等的时候，最小是\(0\)，当其中一个状态占满。

• 信息增益: 是由于使用这个属性分割样例集而导致期望熵的减小

这里用期望，表明一个属性的不同值对做出样例集划分后，要加权求平均来表达总体的熵减情况。

\[ gain(S,A) = entropy(S) - \sum_{v\in value(A)}\frac{|S_v|}{|S|}entropy(S_v) \]

注意后面的熵\(entropy(S_v)\)是条件熵，基于\(S_v\)来计算后续别的属性的熵.

递归调用。当样例个数为0或熵为0时，确定叶子节点的属性。已被树的较高节点测试的属性被排除在外。

ID3 算法的优劣

优势	劣势
假设空间包含所有的决策树，时关于现有属性的有限离散值函数的一个完整空间。	训练结束后，ID3只维护单一的当前假设。不像变形空间的候选消除算法能够维护与训练样例一致的所有假设
每一步都使用当前的所有训练样例，基于统计，能够降低对个别训练样例错误的敏感性，不像Find_S算法/候选消除算法对个别数据的错误非常敏感	搜索不进行回溯，容易收敛到局部最优答案？？

归纳偏置

近似的归纳偏置: 较短的树比较长的树优先。信息增益高的属性更靠近根节点的树优先。

ID3算法	候选消除算法
优选偏置，搜索偏置，对于某种假设胜过其他假设的优选，并不考虑最终可列举的假设种类	限定偏置，语言偏置，限定假设的空间

奥坎姆剃刀(Occam's razor)

优先选择拟合数据的最简单的假设。

ID3算法优选较短决策树的归纳偏置是泛化的一种依据。

常见问题: 过度拟合

• 噪声、巧合会导致决策树更加复杂。

解决方案

• 及早停止树增长: 较为困难

• 后修剪法: 采用一定的准则进行修剪。

||| |:---:|

• 训练和验证集法

训练集可能因噪声、随即错误和巧合规律性误导，但验证集不太可能表现出同样的波动。这样求验证集要足够大，一般⅓的数据用于验证。

后修剪法

• 错误率降低修剪

• 规则后修剪