不同的算法可以使用不同的指标来定义“纯度”的高低，如“信息熵”（Information Entropy）、“基尼不纯度”<sup>○一</sup>（Gini Impurity）、“错误率”（Error Rate）等都是可根据情况选择的指标。以信息熵为例，信息熵是香农在信息论中创造出来用于描述传输数据不确定程度的概念，数据的不确定性越大，信息熵也越大（这里数学公式和证明就不列了，读者可自行查阅相关内容）。香农在《信息论》中证明了只有不确定的数据才能携带信息，如果数据都是确定的，信息熵即为零，那这些数据也就无法携带任何信息了。对于构建决策树的场景而言，可以选择的分裂准则就是让按选定的属性分裂树之后划分到每个分支数据的信息熵最低，即纯度最高，决策树学习方法中把这个分裂过程称为“信息增益”。举个现实的例子，假设训练样本中有 10 个球，黑色、白色各 5 个，此时熵是1，这是最高的熵，表示任意取一个球的颜色的不确定性是最大的，而当使用颜色作为分裂树的属性后，得到的两个分支分别有 5 个黑球和 5 个白球，那两个分支各自的熵都是零，因为这时任意取一个球的颜色都是确定的。
对于数据集的样本数量小、样本的属性少的情况，构建决策树是很容易的，连人类手工都可以轻易完成，但是在面对大量样本和属性的时候，要构建一棵最优的决策树则是非常困难的，因为每一个节点选择的分类属性都对以后所有分支中的数据集有全局性的影响，通过样本训练出最优的决策树已经被证明是一个“NP 完全问题”<sup>○二</sup>。由于此限制，实际应用决策树学习时，其训练过程通常采用启发式搜索算法来达到局部最优而不追求得到全局最优解。
对比现在最热门的基于神经网络的机器学习，以决策树学习为代表的基于符号的机器学习有一个很好的性质：它生成的模型是一个白盒模型，输出结果的含义很容易通过模型的结构来解释，而神经网络输出的是一个黑盒模型，最终结果往往是模型确实可以解决问题，甚至工作得非常好，但是人类无法根据模型去解释为什么会如此。可解释性是符号主义思想先天决定的，这也是基于规则的学习算法相比现在流行的基于神经网络的学习算法的一个巨大优势。
100
第二部分 学派争鸣
○一 基尼不纯度是指从数据集中随机抽两个样本，两者不一致的概率。基尼不纯度越小，数据集纯度越高。
○二 证明的相关论文地址：http://ieeexplore.ieee.org/document/1522531/。