数据挖掘经典十大算法_条件熵、信息增益介绍

数据挖掘经典算法_条件熵、信息增益介绍

一、条件熵

首先与信息熵进行类比，从信息熵的计算公式中我们知道它是考虑到该随机变量的所有可能取值，即所有可能发生事件所带来信息量的期望。由此顾名思义

条件熵的定义是： 定义为在给定X的条件下，Y的条件概率分布的熵对X的数学期望。

定义比较抽象，我们可以通过数学符号表示：
若设有随机变量（X,Y），其联合概率分布我们可以表示为：

条件熵H（Y|X）表示在已知随机变量X的条件下，随机变量Y的不确定性。
也就是说：在给定的随机变量X条件下，随机变量Y的条件熵我们用H（Y|X）表示。
信息熵计算公式：

综上，可以结合信息熵的计算公式推导出条件熵的计算公式：

需要注意的是条件熵中的X也是一个变量，表示的是在一个变量X的条件下，另一个变量Y熵对X的期望。（变量X的每一个值都会取，因此进行求和操作）

二、举个栗子

假设有以下数据：前四列是评价标准，最后一列为结论

若将最终的结论看做随机变量Y={嫁，不嫁}，从表格中统计得到嫁的个数为6，概率是6/12 = 1/2 ,那么不嫁的概率也为 1/2，通过信息熵计算公式得到：

H(Y) = -(1/2)log(1/2) + (-(1/2)log(1/2))

此时，引入另一个变量X代表长相，X={帅，不帅}
从表格中统计得到，在不帅的前提下有四条数据，其中嫁的个数为三条，概率为3/4；不嫁的个数为一条，概率为1/4，故可以得到：

P(X=不帅) = 4/12 = 1/3
H(Y|X=不帅) = -(1/4)log(1/4) + (-(3/4)log(3/4))

同理：可以从表格中得到，在帅的前提下有八条数据，其中嫁的到个数为三条，概率为3/8；不嫁的个数为五条，概率为5/8，故可以得到：

P(X=帅) =1- 4/12 = 8/12 = 2/3
H(Y|X=帅) = -(5/8)log(5/8) + (-(3/8)log(3/8))

综上： 可以计算条件熵 H ( Y | X = 长相 )

H ( Y | X = 长相 ) = p ( X = 帅 ) * H ( Y | X = 帅 ) + p ( X = 不帅 ) * H ( Y | X = 不帅 )
= 2/3 * [-(5/8)log(5/8) + (-(3/8)log(3/8))] + 1/3 * [-(1/4)log(1/4) + (-(3/4)log(3/4))]

三、信息增益

在了解信息熵和条件熵之后，信息增益指的是信息熵和条件熵的差值

信息增益 = 信息熵 - 条件熵
从前面我们了解到：信息熵是指随机变量的复杂度，即不确定度
条件熵是指在某一条件下，随机变量的复杂度
那么 信息增益则代表：在某一条件下，信息复杂度减少的程度。

例如我们在采用决策树算法解决相关的问题时，当存在多个特征值供我们选择，应该选择哪一个特征值来进行分类，或者按照什么样的标准来完成特征选择，此时在选择标准时就需要用到信息增益的相关计算方法。

标准： 若选择某一特征，其信息增益的值 最大 ，也就是说信息复杂度减少的程度是最大的，那么选择这个特征进行分类。

四、还是上面的栗子

若将最终的结论看做随机变量Y={嫁，不嫁}，从表格中统计得到嫁的个数为6，概率是6/12 = 1/2 ,那么不嫁的概率也为 1/2，通过信息熵计算公式得到：

H(Y) = -(1/2)log(1/2) + (-(1/2)log(1/2)) = -log(1/2) = 0.3010

现在引入另外一个变量X表示身高 X = {矮，中，高} 从表格中得到：
矮的个数为7，其中嫁的个数为1，概率为1/7；不嫁的个数为61，概率为6/7
中的个数为2，其中嫁的个数为2，概率为1；不嫁的个数为0，概率为0
高的个数为3，其中嫁的个数为3，概率为1；不嫁的个数为0，概率为0
根据条件熵公式：
我们可以得到：

H(Y | X = 矮) = -(1/7)log(1/7) + (-(6/7)log(6/7)) = 0.1781
H(Y | X = 中) = -1log1 - 0 = 0
H(Y | X = 高) = -1log1 - 0 = 0
P(X = 矮) = 7/12；P(X = 中) = 2/12；P(X = 高) = 3/12
故条件熵：H ( Y | X = 身高 ) = 7/12 * 0.1781 + 2/12 * 0 + 3/12 * 0 = 0.1039

信息增益 = 信息熵 - 条件熵 = H ( Y ) - H ( Y | X = 身高) = 0.3010-0.1039 =0.1971

从计算结果中我们可以得到结论，当一个女生不了解男生的任何信息时，决定嫁给这个男生的不确定性为0.3010；若这个女生了解了男生的身高信息后，不确定性减少了0.1971，不确定度为0.1039。当某一个属性的不确定度为0时，就一定会嫁给这个男生。
因此，可以计算出这四个评价标准当中，信息增益最大的属性，当一个女生了解这个属性后，嫁与不嫁的不确定度减少的是最大的。