Question

ID3算法基于信息熵来选择最佳测试属性。它选择当前样本集中具有最大信息增益值的属性作为测试属性；样本集的划分则依据测试属性的取值进行，测试属性有多少不同取值就将样本集划分为多少子样本集，同时决策树上相应于该样本集的节点长出新的叶子节点。ID3算法根据信息论理论，采用划分后样本集的不确定性作为衡量划分好坏的标准，用信息增益值度量不确定性：信息增益值越大，不确定性越小。因此，ID3算法在每个非叶节点选择信息增益最大的属性作为测试属性，这样可以得到当前情况下最纯的拆分，从而得到较小的决策树。

设S是s个数据样本的集合。假定类别属性具有m个不同的值：C_i（i=1，2，…，m）。设s_i是类C_i中的样本数。对一个给定的样本，它总的信息熵为

其中，P_i是任意样本属于C_i的概率，一般可以用s_i/s估计。

设一个属性A具有k个不同的值{a₁，a₂，…，a_k}，利用属性A将集合S划分为个子集{S₁，S₂，…，S_k}，其中S_j包含了集合S中属性A取a_j值的样本。若选择属性A为测试属性，则这些子集就是从集合S的节点生长出来的新的叶节点。设s_ij是子集S_j中类别为C_i的样本数，则根据属性A划分样本的信息熵值为

其中，是子集S_j中类别为C_i的样本的概率。

最后，用属性A划分样本集S后所得的信息增益（Gain）为

显然E（A）越小，Gain（A）的值越大，说明选择测试属性A对于分类提供的信息越大，选择A之后对分类的不确定程度越小。属性A的k个不同的值对应样本集S的k个子集或分支，通过递归调用上述过程（不包括已经选择的属性），生成其他属性作为节点的子节点和分支来生成整个决策树。ID3决策树算法作为一个典型的决策树学习算法，其核心是在决策树的各级节点上都用信息增益作为判断标准进行属性的选择，使得在每个非叶节点上进行测试时，都能获得最大的类别分类增益，使分类后数据集的熵最小。这样的处理方法使得树的平均深度较小，从而有效地提高了分类效率。