信息增益
算法思想
信息增益的算法过程为:
- 出入:训练数据集
D
和特征A
- 输出:特征A对训练数据集D的信息增益
具体过程解释为:
栗子
下面具体解释下针对特征年龄的信息增益的计算过程
- 计算经验熵:
- 原始数据中,输出类别分为是与否,二者比例为9:6
- 根据经验熵的公式得出数据集D的经验熵为
- 计算经验条件熵:
- 年龄有三个类别:青年、中年、老年,比例为5:5:5
- 根据表格中年龄属性的3个特征,青年、中年、老年:
- 青年:是:否=2:3
- 中年:是:否=3:2
- 老年:是:否=4:1
计算出以年龄为条件
的,
- 将经验熵减去经验条件熵,便可以得到信息增益
information gain
信息增益率
以信息增益作为划分训练数据集的特征,存在一个问题:分类结果偏向于选择取值较多的特征。利用信息增益率可以校正这个问题。信息增益率定义为:
特征A对训练数据集D的信息增益比为,定义为其信息增益与训练数据集D关于特征A的值的熵之比,即其中,,n是特征A取值的个数。
ID3算法
算法简述
ID3
和CART
算法是决策树中的经典算法。在本篇札记中主要讲解ID3
算法。
ID3
算法的核心是在决策树的各个节点上利用信息增益
来进行特征的选择,通过递归方法
构建决策树。
- 从根节点开始,对节点计算所有可能的特征的信息增益:计算所有的特征的信息增益
- 选择信息增益最大的特征作为节点的特征,构建子节点
- 对子节点递归调用上述方法,构建决策树。
- 直到所有特征的信息增益均很小或者没有特征可以选择
ID3
算法相当于是利用极大似然法进行概率模型的选择
算法步骤
输入:训练数据集D,特征集A阈值
输出:决策树T
- 如果训练数据集中的实例全部属于同一个类,则T为单节点树,并且将作为实例的类进行输出。
- 若A为空集,则T为单节点树,并将D中实例最大的类作为节点的类进行输出
- 不满足上述两种情况,计算A中各个特征对D的信息增益,选择信息增益最大的特征
- 如果的信息增益小于阈值,返回单节点树T
- 否则,对于中的每个取值,依,将数据集D分割为若干个子集,将中实例最大的类作为标记,构建子节点,由节点及其子节点构成树,返回T
- 对于第个子节点,以为训练集,以为特征集,递归地调用上述步骤,得到子树,返回
注意
- 先计算每个特征的经验熵,取其中最大者作为根节点的特征;将数据集划分为多个子集
- 如果子集中全部为一个类,当作叶结点;如果子集中类存在多个节点,继续利用剩下的特征进行划分
- 在剩下的数据和剩下的特征利用信息增益继续划分,直至结束
C4.5算法的不同之处在于将ID3算法中的信息增益换成了信息增益率