欢迎大家关注腾讯云技术社区 - 博客园官方主页,我们将持续在博客园为大家推荐技术精品文章哦~
周东谕,2011 年加入腾讯,现任职于腾讯互娱运营部数据中心,主要从事游戏相关的数据分析和挖掘工作。
介绍信息增益之前,首先需要介绍一下熵的概念,这是一个物理学概念,表示 "一个系统的混乱程度"。系统的不确定性越高,熵就越大。假设集合中的变量
,它对应在集合的概率分别是
- X={x1,x2…xn}
。那么这个集合的熵表示为:
- P={p1,p2…pn}
举一个的例子:对游戏活跃用户进行分层,分为高活跃、中活跃、低活跃,游戏 A 按照这个方式划分,用户比例分别为 20%,30%,50%。游戏 B 按照这种方式划分,用户比例分别为 5%,5%,90%。那么游戏 A 对于这种划分方式的熵为:
同理游戏 B 对于这种划分方式的熵为:
游戏 A 的熵比游戏 B 的熵大,所以游戏 A 的不确定性比游戏 B 高。用简单通俗的话来讲,游戏 B 要不就在上升期,要不就在衰退期,它的未来已经很确定了,所以熵低。而游戏 A 的未来有更多的不确定性,它的熵更高。
介绍完熵的概念,我们继续看信息增益。为了便于理解,我们还是以一个实际的例子来说明信息增益的概念。假设有下表样本
!
第一列为 QQ,第二列为性别,第三列为活跃度,最后一列用户是否流失。我们要解决一个问题:性别和活跃度两个特征,哪个对用户流失影响更大?我们通过计算信息熵可以解决这个问题。
按照分组统计,我们可以得到如下信息:
其中 Positive 为正样本(已流失),Negative 为负样本(未流失),下面的数值为不同划分下对应的人数。那么可得到三个熵:
整体熵:
性别熵:
性别信息增益:
同理计算活跃度熵:
活跃度信息增益:
活跃度的信息增益比性别的信息增益大,也就是说,活跃度对用户流失的影响比性别大。在做特征选择或者数据分析的时候,我们应该重点考察活跃度这个指标。
从表 2 中我们不难发现,在计算信息熵和信息增益之前,需要对各维度做汇总计数,计算各公式中出现的分母。Hive SQL 中,cube 能帮助我们很快的做汇总计算,话不多说直接上代码:
- SELECT
- t1.feature_name,SUM((ea_all/es)*EA)as gain,SUM(NVL(-(ea_all/ES)*log2(ea_all/es),0))as info,--计算信息增益率的分母SUM((ea_all/es)*EA)/SUM(NVL(-(ea_all/es)*log2(ea_all/es),0))as gain_rate--信息增益率计算FROM
- (SELECT
- feature_name,feature_value,
- ea_all,--Key Step2 对于整体熵,要记得更换符号,NVL的出现是防止计算log2(0)得NULLcasewhenfeature_value='-100'then -(NVL((ea_positive/ea_all)*log2(ea_positive/ea_all),0)+NVL((ea_negative/ea_all)*log2(ea_negative/ea_all),0))else (NVL((ea_positive/ea_all)*log2(ea_positive/ea_all),0)+NVL((ea_negative/ea_all)*log2(ea_negative/ea_all),0))endas EAFROM
- (SELECT
- feature_name,feature_value,SUM(casewhen is_lost=-100then user_cntelse0end)as ea_all,SUM(casewhen is_lost=1then user_cntelse0end)as ea_positive,SUM(casewhen is_lost=0then user_cntelse0end)as ea_negativeFROM
- (SELECT
- feature_name,--Key Step1 对feature值和label值做汇总统计,1、用于熵计算的分母,2、计算整体熵情况casewhengrouping(feature_value)=1then'-100'elsefeature_valueendasfeature_value,casewhengrouping(is_lost)=1then-100else is_lostendas is_lost,COUNT(1)as user_cntFROM
- (SELECT feature_name,feature_value,is_lostFROM gain_caculate
- )GROUPBY feature_name,cube(feature_value,is_lost)
- )GROUPBY feature_name,feature_value
- )
- )t1join
- (--Key Step3信息增益计算时,需要给出样本总量作为分母SELECT feature_name,COUNT(1)as esFROM gain_caculateGROUPBY feature_name
- )t2on t1.feature_name=t2.feature_nameGROUPBY t1.feature_name
数据表结构如下:
关键步骤说明:
KeyStep1:各特征的熵计算
KeyStep2:各 feature 下的信息增熵
信息增益计算结果:
以上为信息熵计算过程的 SQL 版本,其关键点在于使用 cube 实现了 feature 和 label 所需要的汇总计算。需要的同学只需要按照规定的表结构填入数据,修改 SQL 代码即可计算信息增益。文中如有不足的地方,还请各位指正。
[1] 算法杂货铺——分类算法之决策树 (Decision tree)
http://www.cnblogs.com/leoo2sk/archive/2010/09/19/decision-tree.html
[2] c4.5 为什么使用信息增益比来选择特征?
https://www.zhihu.com/question/22928442
来源: http://www.cnblogs.com/qcloud1001/p/6735352.html