决策树：从给定训练数据集学的一个模型用于对新示例进行分类。

我们希望决策树的分支节点所包含的样本尽可能属于同一类别，即结点的“纯度”越高越好，这样避免多次无用的分类。

1.用信息熵度量样本集合纯度。

假定当前样本集合D中第k类样本所占的比例为pk（k = 1,2,.....,|y|）,则D的信息熵定义为

Ent（D）= -∑pklog2pk

信息熵增益越大，则意味着使用该属性进行划分所获取的“纯度”提升越大。ID3（Iterative Dichotomiser）就是以信息增益为准则来选择属性划分的。

假如在决策中使用属性编号，则可以看出其分支数将达到最大，将远超出其他，但是缺乏泛化能力，无法对新样本进行有效的预测。

实际中在

机器学习之决策树