定义

在选择根结点和各个内部节点的分枝属性时，采用信息增益作为度量标准，并且选择具有最高信息增益的属性作为分枝属性，这种算法称为「ID3 算法」。ID3 算法只能处理属性值为离散型的数据集的划分。

ID3 算法可以利用信息熵来度量样本集合的纯度。样本集合中第类样本所占比例为，定义的「信息熵」为

越小，则集合的纯度越高。

通过信息熵，我们可以定义「信息增益」（Information Gain），即来度量用属性划分集合后所获得的纯度提升。

选择含个取值的属性划分集合后，会得到个子集，集合的纯度与所有划分子集的纯度相减。此时纯度的差值定义为「纯度提升」

对训练数据集或子集，计算其每个属性的信息增益，并比较它们的大小，选择信息增益最大的属性，即根据信息增益选择属性，并以此构建决策树

这种划分方式得到的决策树称为「ID3 决策树」。

特点

如果在上述例子中，以“编号”这种属性作为属性划分，每个样本都有一个编号，将产生 17 个分支，纯度将达到最大，其信息增益为

$编号$ 但是这样得到的模型不具备泛化能力，无法预测新样本。此时可以采用C4.5 算法

在例子中，的标签有三类，概率分别为，因此信息熵为

则属性”性别“中，男性 M 的信息熵为

女性 M 的信息熵为

因此

同理可以求出，以年龄为划分标准时，，从而求出这种划分的信息增益为

由于年龄划分的信息增益大于性别的，因此在根节点优先选择年龄属性进行数据划分，从而得到下图的决策树。

age	income	student	credit_rating	buy_computer
youth	high	no	fair	no
youth	high	no	excellent	no
middle_aged	high	no	fair	yes
senior	medium	no	fair	yes
senior	low	yes	fair	yes
senior	low	yes	excellent	no
middle_aged	low	yes	excellent	yes
youth	medium	no	fair	no
youth	low	yes	fair	yes
senior	medium	yes	fair	yes
youth	medium	yes	excellent	yes
middle_aged	medium	no	excellent	yes
middle_aged	high	yes	fair	yes
senior	medium	no	excellent	no

解：计算标签信息熵。其中有 9 个 Yes，5 个 no，因此

然后计算各个属性的信息熵。以 age 项为例。age=youth 有

age=middle_aged 有

age=senior 有

对信息增益有

同理可以计算出

可以发现，是最大的，因此优先以该属性来划分数据集。