一条SQL搞定信息增益的计算

作者介绍:周东谕,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为负样本(未流失),下面的数值为不同划分下对应的人数。那么可得到三个熵:

整体熵:

性别熵:

性别信息增益:

同理计算活跃度熵:

活跃度信息增益:

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

使用Hive SQL实现信息熵的计算

从表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)得NULL
    case 
    when feature_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))
    end as EA 
    FROM
    (
        SELECT 
        feature_name,
        feature_value,
        SUM(case when is_lost=-100 then user_cnt else 0 end) as ea_all,
        SUM(case when is_lost=1 then user_cnt else 0 end) as ea_positive,
        SUM(case when is_lost=0 then user_cnt else 0 end) as ea_negative
        FROM
        (
            SELECT 
            feature_name,
            --Key Step1 对feature值和label值做汇总统计,1、用于熵计算的分母,2、计算整体熵情况
            case when grouping(feature_value)=1 then '-100' else feature_value end as feature_value,
            case when grouping(is_lost)=1 then -100 else is_lost end as is_lost,
            COUNT(1) as user_cnt
            FROM
            (                
                SELECT feature_name,feature_value,is_lost FROM gain_caculate

            )GROUP BY feature_name,cube(feature_value,is_lost)
        )GROUP BY feature_name,feature_value
    )
)t1 join 
(
    --Key Step3信息增益计算时,需要给出样本总量作为分母
    SELECT feature_name,COUNT(1) as es FROM gain_caculate
    GROUP BY feature_name
)t2 on t1.feature_name=t2.feature_name
GROUP BY 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

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

编辑于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏AI科技评论

开发 | 揭开Faiss的面纱 探究Facebook相似性搜索工具的原理

AI科技评论按:本月初AI科技评论曾报道Facebook 开源了 AI 相似性搜索工具 Faiss。而在一个月之后的今天,Facebook 发布了对 Faiss...

4668
来自专栏racaljk

人工智能各种技术与算法

>搜索策略(Search Strategies)//详细请参见http://blog.csdn.net/racaljk/article/details/1888...

1693
来自专栏音视频应用

libsonic的原理介绍与应用

在音频处理的时候常常会涉及到音频的变速、变调等方面的操作,使用的场景比较广泛如汤姆猫、男声变女声等,此外某些应用场合下的低延迟的播放器,往往也需要涉及到这方面的...

2024
来自专栏SIGAI学习与实践平台

理解计算:从根号2到AlphaGo番外篇——眼见未必为实--漫谈图像隐写术

传递秘密消息的历史非常悠久,在公元前500年左右的波希战争时期,就有将奴隶的头发剃掉,然后在头皮上刺上字,等奴隶的头发张长后,将这个人派去传递消息,一次消息传递...

602
来自专栏大数据挖掘DT机器学习

机器学习实战,使用朴素贝叶斯来做情感分析

前段时间更新了一系列基础的机器学习算法,感觉有些无味,而且恰好那时买了了国内某公司的云服务器,就打算部署一套文本处理的WEB API,顺别应用一下之前学习到的机...

3278
来自专栏WOLFRAM

当 Wolfram 语言遇上引力波

882
来自专栏AI研习社

揭开Faiss的面纱 探究Facebook相似性搜索工具的原理

本月初 AI 研习社报道,Facebook 开源了 AI 相似性搜索工具 Faiss。而在一个月之后的今天,Facebook 发布了对 Faiss 的官方原理介...

46010
来自专栏量子位

Facebook开源移动端深度学习加速框架,比TensorFlow Lite快一倍

Facebook发布了一个开源框架,叫QNNPACK,是手机端神经网络计算的加速包。

992
来自专栏机器人网

机器人控制的基本方法

机器人的控制方法,根据控制量、控制算法的不同分为多种类型。下面分别针对不同的类型,介绍常用的机器人控制方法。 一、根据控制量分类 按照控制量所处空间的不同,...

3384
来自专栏人工智能

你该掌握的AI技能:强化学习01

题图由人工智能设计师完成 最近在看一些强化学习的书籍,学习的过程就是要不断的输入,查找资料,理解各种资料,然后输出,总结学习心得,再次输入,输出。不断的重复输入...

1878

扫码关注云+社区