天才一秒记住【畅想小说网】地址：http://www.cxtra.net
进而可以看出，类别Xi的信息是随着概率增加而减少的，也就是说，这个量衡量了Xi的不确定性。
例如，概率为1时，它是注定会出现的，所以信息为0，不确定性最小；概率为0时，信息为+∞，不确定性最大。
而熵的概念可以结合概率中的全概率公式来理解，它代表了分类问题X的不确定性的期望（概率平均值），也就是对类别进行预测时的不确定性，或者说是预测的难度。
有了这样的认识，就可以很自然地给出确定分裂属性的原则：选择当前可以最大程度减少预测的不确定性的属性作为分裂属性。
衡量不确定性的减少程度有几种不同的计算方式，根据计算方式的不同，衍生出了不同的决策树算法。
例如，使用信息增益的ID3算法，使用信息增益比的C4.5算法，还有使用基尼指数的CART算法。
它们的原理是类似的，本教材介绍采用信息增益的ID3算法，其他算法只要把信息增益的计算公式替换成相应的其他计算公式就可以了。
在条件熵的基础上，就可以按如下方式定义信息增益（Gain）的概念了。
Gain（X，A）=H（X）-H（X|A）
信息增益还有一个名称叫作互信息，这是信息论中常用的名称。
从熵和条件熵的定义可以看出，信息增益反映的是，选择A作为分裂属性后，分类问题的不确定性减少了多少。
按照前面所说的选择分裂属性的原则，只要计算当前可供选择的所有特征属性对应的信息增益，以信息增益最大的属性作为决策树的下一个分裂属性即可。
对这个基本原则建立了清楚的认识后，使用信息增益就可以给出完整的构造决策树的ID3算法了。
第一步，初始化信息增益阈值。
第二步，生成根节点。
通过计算分类问题的熵和不同特征属性对应的条件熵，选择信息增益最大并且大于增益阈值的属性作为第一个分裂属性生成根节点，并将该属性从候选属性中去除。
第三步，根据上层节点的不同取值，生成新的训练数据，计算不同的候选属性的信息增益，选择增益最大并且大于增益阈值的属性作为分裂属性生成新的节点，并将该属性从候选属性中去除。
第四步，重复第三步，直至满足终止条件。
该过程会重复使用第三步，这个方法被称为递归方法。
现在还剩下一个问题需要说明，即与决策树构建有关的问题：何时停止树的生长？也就是在上述流程的最后一步中，终止条件是什么？常用的终止条件如下所列。
①如果所有属于分裂属性某个取值的训练数据都属于同一类别，则生成此类别的叶子节点并终止程序；
②如果特征属性已经使用完毕，即候选属性为空，则以当前训练数据中出现最多的类别生成叶子节点并终止程序；
③如果所有候选属性的信息增益都小于阈值，则以当前训练数据中出现最多的类别生成叶子节点并终止程序。
下面以上一节的电商消费数据为例，演示决策树ID3算法的实现过程，以帮助读者建立直观的认识。
在实际操作中，一般以训练数据中相应的频率来代替概率。
本章未完，请点击下一章继续阅读！若浏览器显示没有新章节了，请尝试点击右上角↗️或右下角↘️的菜单，退出阅读模式即可，谢谢！