2.3　ID3算法

在决策树学习中，ID3（Iterative Dichotomiser 3）是由Ross Quinlan发明的一种算法，以Hunt算法为基础，用于从数据集生成决策树。ID3是C4.5算法的前身［7］。ID3算法只能处理特征属性均为离散数据类型的数据集且不支持剪枝。

ID3算法以原始集合S为根节点。在算法的每次迭代中，根据集合S的每一个未使用的属性进行遍历，根据该属性的所有取值，计算按该属性分割后的熵H（S）或信息增益IG（S）。然后，从中选择熵值最小（或信息增益最大）的属性。之后，根据该属性的所有取值对集合S进行分割，以产生数据的子集。需要指出的是，ID3算法生成的树可能是多元树，即一个节点的子节点可能会多于两个，具体数量依赖于该节点所对应的属性的所有可能的取值。该算法继续对每个子集进行递归，只考虑以前从未选择过的属性，因为此时每个子集中，已经选择过的属性的数据都是纯的。

ID3算法与CART算法的不同之处［7］主要表现在：

●ID3只能处理特征属性为离散数据类型的数据集。

●ID3不支持剪枝。

●选择特征属性依据信息熵和信息增益。

●ID3生成的树是一个多元树，集合S按照属性A进行分割后，子集的数量（子节点的数量）与属性A的取值有关。所有属性A的取值都是分割点，因此，每个子集里的样本数据的属性A的取值都是相同的。因此，针对子集的后续分割将不再考虑已经选择过的属性。

ID3算法主要用于分类决策树。ID3不保证最优解，它可能收敛于局部最优解。它采用贪婪的策略，在每次迭代中选择局部最佳属性来分割数据集。在搜索最优决策树的过程中，可以通过使用回溯来提高算法的最优解，但代价是可能需要更长的时间。

ID3对训练数据可能会出现过拟合。为了避免过拟合，应该优先选择较小的决策树，而不是较大的决策树。ID3在连续数据上比在离散数据上更难使用。如果任何一个给定属性的值是连续的，那么在这个属性上有更多的地方可以拆分数据，寻找最佳的拆分值会很耗时。