通常特征选择的指标是:信息增益或者信息增益比。这两个指标刻画了特征的分类能力。
对于分布 ,熵为
。
定义数据集 的经验熵为:
。
其中:
样本的类别分别为 。
类别
的样本的数量为 ,所有样本的总数为
。
是概率
的估计。
就是熵
的估计。它刻画了数据集 中样本的类别分布情况。
对于特征
,定义数据集 在
上的经验熵为: 。
其中:
特征
的取值范围为 。
是概率 的估计。
刻画了数据集 中的样本在属性
上的取值分布情况。
对于特征 ,其条件熵为:
。
定义数据集 关于特征
的经验条件熵为:
其中:
属性
且类别为 的样本的数量为
,所有样本的总数为 。
因此有:
。
是条件熵
的估计。它刻画了数据集 中,属性
中的那些样本中的类别的分布情况。
是条件熵
的估计。
特征 对训练数据集
的信息增益 定义为:集合
的经验熵 与关于特征
经验条件熵 之差。即:
。
由于熵 也称作互信息,因此信息增益也等于训练数据集中类与特征的互信息。
决策树学习可以应用信息增益来选择特征。给定训练集
和特征 :
- 经验熵
刻画了对数据集 进行分类的不确定性。
- 经验条件熵
刻画了在特征 给定条件下,对数据集
分类的不确定性。
- 信息增益 刻画了由于特征
的确定,从而使得对数据集 的分类的不确定性减少的程度。
- 经验熵
2.2 信息增益比
以信息增益作为划分训练集的特征选取方案,存在偏向于选取值较多的特征的问题。
公式
中:
当极限情况下 ,特征 在每个样本上的取值都不同,即
。
此时特征 将每一个样本都划分到不同的子结点。即:
。
由于 ,因此有:
。
即: 取值为 0 或者 1 。因此有:
。
最终使得 。
条件熵的最小值为 0,这意味着该情况下的信息增益达到了最大值。
然而很显然这个特征
显然不是最佳选择,因为它并不具有任何分类能力。
可以通过定义信息增益比来解决该问题。
特征 对训练集
的信息增益比 定义为:信息增益
与关于特征 的熵
之比:
表征了特征 对训练集
的拆分能力。
信息增益比本质上是对信息增益乘以一个加权系数:
- 当特征 的取值集合较大时,加权系数较小,表示抑制该特征。