上一章为大家介绍了决策树分类算法概述，今天为大家介绍具体的ID3决策树分类算法，并附有详细的案例帮助大家理解。

ID3算法原理介绍

基本决策树构造算法都是一个贪婪算法，采用自顶向下的递归方法构造决策树，ID3决策树分类算法的基本策略如下：

1. 决策树以代表训练样本的的单个节点开始

2. 如果样本都在同一个类中，则这个节点称为树叶节点并标记类别

3. 否则算法使用信息熵（信息增益）作为启发知识来帮助选择合适的将样本分类的属性，以便将样本集划分为若干子集，该属性就是相应节点的“测试”或“判定”属性，同时所有属性应当是离散值

4. 对测试属性的每个已知的离散值创建一个分支，并据此划分样本

5. 算法使用类似的方法，递归地形成每个划分上的样本决策树，一个属性一旦出现在某个节点上，那么它就不能再出现在该节点之后所产生的子树节点中

6. 整个递归过程在满足下列条件之一时停止：

• 给点节点的所有样本属于同一类

• 没有剩余属性可以用来进一步划分样本，这时候该节点作为树叶，并用剩余样本中出现最多的类型作为该叶子节点的类型

• 某一分支没有样本，在这种情况下以训练样本集中占绝大多数的类创建一个树叶

ID3算法的核心是，在决策树各级节点上选择属性时，用信息增益作为属性的选择标准，使得在每一个非节点进行测试时，能获得关于被测试记录最大的类别信息。

熵和信息增益

熵（entropy）的概念

• 在信息论中，熵是接收的每条消息中包含的信息的平均量，熵越大，每条消息中包含的信息量越大

• 表示随机变量不确定性的度量，系统越无序、越混乱，熵就越大。熵越大，随机变量的不确定性就越大

• 比如：小概率事件比大概率事件包含的信息量大。如果某件事情是“百年一见”则肯定比“习以为常”的事件包含的信息量大

• 在分类算法中，熵可以作为训练集的不纯度（impurity），熵越大，样本集的信息量就越大，样本集的混杂程度也越高，不纯度就越高。因此，决策树的分支原则就是使划分后的样本的子集越纯越好，即他们的熵越小越好
  

信息量/熵的度量

熵的计算

• 当随机变量只有两个值，例如1,0时，即X的分布为：P(X=1)=p , P(X=0)=1-p , 0<=p<=1

布尔分类的熵函数

• 熵H(p)随概率p变化的曲线如图所示：

布尔分类的熵函数图像

• 由图可知，当样本属于每个类的概率相等时，即p=0.5，熵最大，即分类的不确定性最大

• 当p=0或p=1时，H(p)=0，随机变量完全没有不确定性，即分类结果是确定的

条件熵

条件熵的概念及计算

信息增益

信息增益表示得知特征X的信息而使得类Y的信息不确定性减少的程度

• 信息增益：特征A对训练数据集D的信息增益g(D,A)，定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差，即：

信息增益

根据信息增益准则的特征选择方法是：对训练数据集（或子集）D，计算其每个特征的信息增益，并比较它们的大小，选择信息增益最大的特征，也就是选出的特征是最大程度地减少训练数据集的不纯度的，使划分后的样本的子集越来越纯

ID3算法的信息增益算法

参数定义

参数定义

信息增益计算

信息增益算法

ID3算法实例分析

训练数据

• 第1步计算决策属性的熵——经验熵

决策属性的熵

• 第2步计算条件属性的熵——条件经验熵

• 2-1步计算年龄的条件熵和信息增益

年龄的条件熵和信息增益

• 2-2步计算收入的条件熵和信息增益

收入的条件熵和信息增益

• 2-3步计算学生的条件熵和信息增益

学生的条件熵和信息增益

• 2-4步计算信誉的条件熵和信息增益

信誉的条件熵和信息增益

• 选择节点 ：选择信息增益最大的属性

选择信息增益最大的属性

选择年龄属性作为分类节点

继续重复以上步骤，选择下一个属性继续构造决策树。