决策树的划分依据--信息增益

1 概念

1.1 定义

• 信息增益：以某特征划分数据集前后的熵的差值。熵可以表示样本集合的不确定性，熵越大，样本的不确定性就越大。因此可以使用划分前后集合熵的差值来衡量使用当前特征对于样本集合D划分效果的好坏。

• 信息增益 = entroy(前) - entroy(后)

注：信息增益表示得知特征X的信息而使得类Y的信息熵减少的程度

1.2 公式

• 假定离散属性a有v个可能的取值\((a^1,a^2,...,a^v)\),若使用a来对样本集D进行划分，则会产生v个分支结点,其中第v个分支结点包含了D中所有在属性a上取值为\(a^v\)的样本，记\(D^v\),我们可根据前面给出的信息熵公式计算出\(D^v\)的信息熵，再考虑到不同的分支结点所包含的样本数不同，给分支结点赋予权重\(\frac{|D^v|}{|D|}\),即样本数越多的分支结点的影响越大，于是可计算出用属性a对样本集 D 进行划分所获得的"信息增益" (information gain)。
• 特征a对训练数据集D的信息增益Gain(D,a),定义为集合D的信息熵Ent(D)与给定特征a条件下D的信息条件熵Ent(D|a)Ent(D∣a)之差，即公式为：
  
  信息熵的计算：
  
  条件熵的计算：
  
  其中：
  \(D^v\)表示a属性中第v个分支节点包含的样本数
  \(C^{kv}\)表示a属性中第v个分支节点包含的样本数中，第k个类别下包含的样本数
• 信息增益越大，则意味着使用属性 a 来进行划分所获得的"纯度提升"越大。因此，我们可用信息增益来进行决策树的划分属性选择，著名的 ID3( ID 是 Iterative Dichotomiser 迭代二分器的简称) 决策树学习算法 [Quinlan， 1986] 就是以信息增益为准则来选择划分属性。

2 案例

如下图，第一列为论坛号码，第二列为性别，第三列为活跃度，最后一列用户是否流失。我们要解决一个问题：性别和活跃度两个特征，哪个对用户流失影响更大？

其中Positive为正样本（已流失），Negative为负样本（未流失），下面的数值为不同划分下对应的人数。
a.计算类别信息熵 整体熵
b.计算性别属性的信息熵(a="性别")
c.计算性别的信息增益(a="性别")

b.计算活跃度属性的信息熵(a="活跃度")
c.计算活跃度的信息增益(a="活跃度")

结论：活跃度的信息增益比性别的信息增益大，也就是说，活跃度对用户流失的影响比性别大。在做特征选择或者数据分析的时候，我们应该重点考察活跃度这个指标。