一、ID3算法介绍

ID3算法就是一个按照信息增益选择特征的决策树算法，其基本思想为：每次选择一个信息增益最大的特征，逐节点的建立决策树（ID3算法其实是一个递归算法）。

二、ID3算法规定

输入：训练集D，特征集A，阈值$\epsilon$

输出：决策树T

1. 如果D中所有样本均属于同一类别C，则T为单节点树，将C作为该节点的类别标志返回T
2. 如果A为空，则T为单节点树，将D 中样本最多的类C作为该节点的类别标志，返回，否则计算 A 中各特征对D的信息增益，选择信息增益最大的特征A
3. 如果$A_g$的信息增益小于阈值$\epsilon$，则将T视作单节点树，将D中样本最多的类C作为该节点的类别标记，返回T，否则按照$A_g$的每个可能取值$a_i$，将D划分为n个子数据集$D_i$，作为 D的子节点
4. 对于D的每个子节点D，如果D为空，则视T为单节点树将D的父节点D中样本最多的类作为 D的类别标记,否则以$D_i$作为训练集，以 A-[$A_g$]为特征集，递归地调用算法的1到 6 步，得到子决策树$T_i$，返回$T_i$

三、ID3算法举例