为了量化各种分裂属性选择方案的好坏，需要引入一个新的数学概念——熵（Entropy）。熵的概念是由信息论的创始人香农提出的，现在在很多学科中都有重要的用处。为了更容易理解这个概念，这里结合分类问题来描述它的定义。
设某个分类问题X包含n个类别m个特征属性，任意样本C属于第i个类别Xi（1≤i≤n）的概率为pi，则I（Xi）=-log2pi称为Xi的信息（Information），X的熵定义为
在分类问题中，如何简单地理解上述定义呢？显然有如下关系。
进而可以看出，类别Xi的信息是随着概率增加而减少的，也就是说，这个量衡量了Xi的不确定性。例如，概率为1时，它是注定会出现的，所以信息为0，不确定性最小；概率为0时，信息为+∞，不确定性最大。
而熵的概念可以结合概率中的全概率公式来理解，它代表了分类问题X的不确定性的期望（概率平均值），也就是对类别进行预测时的不确定性，或者说是预测的难度。
有了这样的认识，就可以很自然地给出确定分裂属性的原则：选择当前可以最大程度减少预测的不确定性的属性作为分裂属性。
衡量不确定性的减少程度有几种不同的计算方式，根据计算方式的不同，衍生出了不同的决策树算法。例如，使用信息增益的ID3算法，使用信息增益比的C4.5算法，还有使用基尼指数的CART算法。它们的原理是类似的，本教材介绍采用信息增益的ID3算法，其他算法只要把信息增益的计算公式替换成相应的其他计算公式就可以了。
在条件熵的基础上，就可以按如下方式定义信息增益（Gain）的概念了。
Gain（X，A）=H（X）-H（X|A）
信息增益还有一个名称叫作互信息，这是信息论中常用的名称。从熵和条件熵的定义可以看出，信息增益反映的是，选择A作为分裂属性后，分类问题的不确定性减少了多少。按照前面所说的选择分裂属性的原则，只要计算当前可供选择的所有特征属性对应的信息增益，以信息增益最大的属性作为决策树的下一个分裂属性即可。
对这个基本原则建立了清楚的认识后，使用信息增益就可以给出完整的构造决策树的ID3算法了。
第一步，初始化信息增益阈值。
第二步，生成根节点。通过计算分类问题的熵和不同特征属性对应的条件熵，选择信息增益最大并且大于增益阈值的属性作为第一个分裂属性生成根节点，并将该属性从候选属性中去除。
第三步，根据上层节点的不同取值，生成新的训练数据，计算不同的候选属性的信息增益，选择增益最大并且大于增益阈值的属性作为分裂属性生成新的节点，并将该属性从候选属性中去除。
第四步，重复第三步，直至满足终止条件。
该过程会重复使用第三步，这个方法被称为递归方法。现在还剩下一个问题需要说明，即与决策树构建有关的问题：何时停止树的生长？也就是在上述流程的最后一步中，终止条件是什么？常用的终止条件如下所列。
①如果所有属于分裂属性某个取值的训练数据都属于同一类别，则生成此类别的叶子节点并终止程序；
②如果特征属性已经使用完毕，即候选属性为空，则以当前训练数据中出现最多的类别生成叶子节点并终止程序；
③如果所有候选属性的信息增益都小于阈值，则以当前训练数据中出现最多的类别生成叶子节点并终止程序。
下面以上一节的电商消费数据为例，演示决策树ID3算法的实现过程，以帮助读者建立直观的认识。在实际操作中，一般以训练数据中相应的频率来代替概率。下面计算中四舍五入后都取两位小数，并且规定0×log20=1×log21=0。
（1）设定信息增益阈值
信息增益阈值设为0.03，认为小于这个阈值的增益对于改善分类的不确定性已经没有意义。
（2）生成根节点
H（X）=-{0.3×log2（0.3）+0.7×log2（0.7）}=0.88
