信息增益：

熵：信息的度量方式，如果待分类的事物可能划分在多个分类（）中，则符号的信息量定义为：；是选择该分类的概率。

香农熵：所有可能类别的信息期望值；；

H越大，变量的不确定性就越大。等概率的情况下，n越大，H越大；n固定时，等概率的情况下，H越大。

经验熵：当熵中的概率由数据估计（特别是最大似然估计）得到时，所对应的熵称为经验熵；即：

              

                注：表示样本容量（样本个数），有k个类，为属于类的样本个数。

条件熵：表示在已知随机变量X的条件下随机变量Y的不确定性。

               

               其中，

信息增益：

数据集

数据集的经验熵为：

年龄的信息增益：

有工作的信息增益：

有自己房子的信息增益：

信贷的信息增益：

ID3算法：

结点选择原则：信息增益最大的特征

流程：从根结点开始，对所有结点计算所有可能的特征的信息增益，选择信息增益最大的特征作为结点的特征，由该特征的不同取值建立子结点，再对子节点递归的调用以上方法；

停止条件：第一个是所有的类别标签完全相同，则直接返回该类标签；第二个是用完了所有特征，若仍不能将数据划分仅包含唯一类别的分组，则决策树构建失败，说明数据维度不够。

以上数据集中，有自己房子的信息增益最大，所以作为根节点；

没有自己房子的样本集：

此时：

年龄的信息增益：

有工作的信息增益：

信贷情况的信息增益：

有工作的信息增益值最大，所以上图“？？？”处的节点应该是有工作，即：

由于，有自己的房子而且有工作下的所有子样本标签都一致，有自己的房子没有工作的所有子样本标签都一致，满足递归停止的第一个条件，所以决策树构建完成。