决策树学习
Decision Tree Learning
1 基本概念
属性（attribute）：树上的每个结点说明了对实例的某个属性的测试，该结点的每一个后继分支对应该属性的一个可能值。
熵（entropy）：刻画了任意样例集的纯度。S相对于c个状态的分类的熵定义为：
信息增益（information gain）：
2 决策树学习的适用问题
- 实例是由"属性-值"对来表示。
- 目标函数具有离散的输出值。
- 可能需要析取的描述。
- 训练数据可以包含错误。
- 训练数据可以包含缺少属性值的实例。
3 基本的决策树学习算法
3.1 ID3算法
ID3算法就是在每次需要分裂时，计算每个属性的信息增益率，然后选择信息增益最大的属性进行分裂。
举例：
第一步后形成的部分决策树
3.2 C4.5算法
ID3算法存在一个问题，就是偏向于多值属性，例如，如果存在唯一标识属性ID，则ID3会选择它作为分裂属性，这样虽然使得划分充分纯净，但这种划分对分类几乎毫无用处。ID3的后继算法C4.5使用增益率（gain ratio）的信息增益扩充，试图克服这个偏倚。
C4.5算法首先定义了"分裂信息（split information）"，其定义可以表示成：
C4.5选择具有最大增益率的属性作为分裂属性，其具体应用与ID3类似，不再赘述。