程序员的数学基础课
黄申
LinkedIn资深数据科学家
立即订阅
23340 人已学习
课程目录
已完结 57 讲
0/4登录后,你可以任选4讲全文学习。
开篇词 (1讲)
开篇词 | 作为程序员,为什么你应该学好数学?
免费
导读 (1讲)
导读:程序员应该怎么学数学?
基础思想篇 (18讲)
01 | 二进制:不了解计算机的源头,你学什么编程
02 | 余数:原来取余操作本身就是个哈希函数
03 | 迭代法:不用编程语言的自带函数,你会如何计算平方根?
04 | 数学归纳法:如何用数学归纳提升代码的运行效率?
05 | 递归(上):泛化数学归纳,如何将复杂问题简单化?
06 | 递归(下):分而治之,从归并排序到MapReduce
07 | 排列:如何让计算机学会“田忌赛马”?
08 | 组合:如何让计算机安排世界杯的赛程?
09 | 动态规划(上):如何实现基于编辑距离的查询推荐?
10 | 动态规划(下):如何求得状态转移方程并进行编程实现?
11 | 树的深度优先搜索(上):如何才能高效率地查字典?
12 | 树的深度优先搜索(下):如何才能高效率地查字典?
13 | 树的广度优先搜索(上):人际关系的六度理论是真的吗?
14 | 树的广度优先搜索(下):为什么双向广度优先搜索的效率更高?
15 | 从树到图:如何让计算机学会看地图?
16 | 时间和空间复杂度(上):优化性能是否只是“纸上谈兵”?
17 | 时间和空间复杂度(下):如何使用六个法则进行复杂度分析?
18 | 总结课:数据结构、编程语句和基础算法体现了哪些数学思想?
概率统计篇 (14讲)
19 | 概率和统计:编程为什么需要概率和统计?
20 | 概率基础(上):一篇文章帮你理解随机变量、概率分布和期望值
21 | 概率基础(下):联合概率、条件概率和贝叶斯法则,这些概率公式究竟能做什么?
22 | 朴素贝叶斯:如何让计算机学会自动分类?
23 | 文本分类:如何区分特定类型的新闻?
24 | 语言模型:如何使用链式法则和马尔科夫假设简化概率模型?
25 | 马尔科夫模型:从PageRank到语音识别,背后是什么模型在支撑?
26 | 信息熵:如何通过几个问题,测出你对应的武侠人物?
27 | 决策树:信息增益、增益比率和基尼指数的运用
28 | 熵、信息增益和卡方:如何寻找关键特征?
29 | 归一化和标准化:各种特征如何综合才是最合理的?
30 | 统计意义(上):如何通过显著性检验,判断你的A/B测试结果是不是巧合?
31 | 统计意义(下):如何通过显著性检验,判断你的A/B测试结果是不是巧合?
32 | 概率统计篇答疑和总结:为什么会有欠拟合和过拟合?
线性代数篇 (13讲)
33 | 线性代数:线性代数到底都讲了些什么?
34 | 向量空间模型:如何让计算机理解现实事物之间的关系?
35 | 文本检索:如何让计算机处理自然语言?
36 | 文本聚类:如何过滤冗余的新闻?
37 | 矩阵(上):如何使用矩阵操作进行PageRank计算?
38 | 矩阵(下):如何使用矩阵操作进行协同过滤推荐?
39 | 线性回归(上):如何使用高斯消元求解线性方程组?
40 | 线性回归(中):如何使用最小二乘法进行直线拟合?
41 | 线性回归(下):如何使用最小二乘法进行效果验证?
42 | PCA主成分分析(上):如何利用协方差矩阵来降维?
43 | PCA主成分分析(下):为什么要计算协方差矩阵的特征值和特征向量?
44 | 奇异值分解:如何挖掘潜在的语义关系?
45 | 线性代数篇答疑和总结:矩阵乘法的几何意义是什么?
综合应用篇 (6讲)
46 | 缓存系统:如何通过哈希表和队列实现高效访问?
47 | 搜索引擎(上):如何通过倒排索引和向量空间模型,打造一个简单的搜索引擎?
48 | 搜索引擎(下):如何通过查询的分类,让电商平台的搜索结果更相关?
49 | 推荐系统(上):如何实现基于相似度的协同过滤?
50 | 推荐系统(下):如何通过SVD分析用户和物品的矩阵?
51 | 综合应用篇答疑和总结:如何进行个性化用户画像的设计?
加餐 (3讲)
数学专栏课外加餐(一) | 我们为什么需要反码和补码?
数学专栏课外加餐(二) | 位操作的三个应用实例
数学专栏课外加餐(三):程序员需要读哪些数学书?
结束语 (1讲)
结束语 | 从数学到编程,本身就是一个很长的链条
程序员的数学基础课
登录|注册

27 | 决策树:信息增益、增益比率和基尼指数的运用

黄申 2019-02-15
你好,我是黄申。
上一节,我通过问卷调查的案例,给你解释了信息熵和信息增益的概念。被测者们每次回答一道问题,就会被细分到不同的集合,每个细分的集合纯净度就会提高,而熵就会下降。在测试结束的时候,如果所有被测者都被分配到了相应的武侠人物名下,那么每个人物分组都是最纯净的,熵值都为 0。于是,测试问卷的过程就转化为“如何将熵从 3.32 下降到 0”的过程。
由于每道问题的区分能力不同,而我们对问题的选择会影响熵下降的幅度。这个幅度就是信息增益。如果问卷题的顺序选择得好,我们可以更快速地完成对用户性格的判定。这一节我们就继续这个话题,看看如何获得一个更简短的问卷设计,把这个核心思想推广到更为普遍的决策树分类算法中。

如何通过信息熵挑选合适的问题?

为了实现一个更简短的问卷,你也许很自然地就想到,每次选择问题的时候,我们可以选择信息增益最高的问题,这样熵值下降得就最快。这的确是个很好的方法。我们来试一试。
我们现在开始选择第一个问题。首先,依次计算“性别”“智商”“情商”“侠义”和“个性”对人物进行划分后的信息增益。我们得到如下结果:
显然,第一步我们会选择“侠义”,之后用户就会被细分为 3 组。
针对第一组,我们继续选择在当前这组中,区分力最强、也是就信息增益最高的问题。根据计算的结果我们应该选择有关“性别”的问题,然后进一步地细分。后续的步骤依次类推,直到所有人物都被分开,对于第二组和第三组我们也进行同样地操作。整个过程稍微有点复杂,为了帮你理解,我把它画成了一个图。
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《程序员的数学基础课》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(13)

  • Peng
    开始看不懂了,我再多看几遍试试。

    作者回复: 可以逐个理解,每次理解一点都是进步👍

    2019-03-05
    3
  • Paul Shan
    信息增益,新分类的引入导致熵的减少。
    信息增益率,计算熵的时候还考虑了多个子项的数目。在计算分组后集合的熵,采用加权平均之后,还要除以,集合分组不同数目引入的熵。
    Gini指数是一种新的计算混乱度的方法,熵是基于对数加权的,Gini指数是基于平方的相反数求和再加一。Gini指数求导以后是线性的,随着概率减少变化度比熵更敏感(熵的导数是对数),也就更惩罚小概率事件。

    2019-09-10
    1
  • 💢 星星💢
    老师随机森林有没有好的文章推荐,另外老师有没有公众号,或者其他方式可以白嫖看您的文章呢,当然也期待老师出新的专栏,虽然这个专栏对于我来说已经是新的挑战。但是非常喜欢读老师的文章。

    作者回复: 你好,感谢支持,我暂时还没有时间在其他地方发表博文。如果有好的想法写作,当然首选极客时间专栏啦😆。正在和编辑筹划下一个专栏,期待与大家再次交流

    2019-11-11
  • 张九州
    计算整个数据集基尼指数,pj是什么 如何计算?

    作者回复: pj表示第j组元素出现的概率,这里用在某个划分的组之中,第j组元素的数量除以这个划分的元素数量来计算

    2019-09-08
  • lifes a Struggle
    知道了,老师的案例中个体都是一个单独的分类,所有在原始集合中可以采用-n*(Pi*log(2,Pi))的形式进行信息熵的计算。如果存在分类的数据不均匀,通过各个分类的信息熵求和即可。

    作者回复: 是的👍

    2019-08-07
  • lifes a Struggle
    老师,请问一下,当原始集合中的数据,本身是分布不均匀的,这个时候该如何计算它的信息熵呢?如:集合{A,A,A,B,B,C}
    2019-08-07
  • abson
    老师,有个疑问,像前几篇文章讲隐马尔科夫、信息熵和本节讲的决策树,数据是怎么来的,用什么方法去统计才能拿到相对偏差较少的数据

    作者回复: 你是指在实际项目中如何获得数据吗?这个要看具体的应用场景和需求,通常的规则是尽量覆盖不同的情况。比如不同时间段、不同用户分组、不同地域等等

    2019-08-07
  • 动摇的小指南针
    基尼系数中,基于特征T划分出来的子集m中,m的每个子集又有n个不同的分组。请问这个n是根据什么来进行划分的呢

    作者回复: 由于是标注数据,所以这个n是根据原有分类的标签来看的

    2019-05-17
  • Bora.Don
    老师,你好,既然CART算法是二叉树,那么在计算基尼指数的时候,n和m是不是就是定值:2?
    CART算法又是如何保证是二叉树的呢?CART算法没看懂

    作者回复: 这里n和m表示分别表示使用特征划分后形成的分组,以及分类标签形成的分组,这和决策树的分叉是不同的

    2019-03-18
  • 冰冷的梦
    老师,什么是过拟合啊?

    作者回复: 我在第32篇有详细讲解,你可以参考

    2019-03-12
  • qinggeouye
    某个特征 T 取值越多,数据集 P 划分时分组越多,划分后的「信息熵」越小,「信息增益」越大。「分裂信息」是为了解决某个特征 T 取值过多,造成机器学习过拟合,而引入的一种惩罚项,惩罚取值多的特征。

    老师,「基尼指数」没怎么看明白,第一个式子中「n 为集合 P 中所包含的不同分组或分类的数量」该怎么理解?求和符号后面的 pi 是什么含义?谢谢~

    作者回复: 因为决策树是一种分类算法,我们有训练样本告诉我们每个数据样本属于何种分类,所以这里的分类、分组都是根据训练样本中的分类标签。

    2019-03-10
  • Joe
    老师,请问有没有相关代码实现的方式,能否给出参考链接。

    作者回复: 你是指计算信息熵、信息增益和基尼指数?可以使用现成的机器学习包计算,如果希望自己计算也不难,遵循专栏中的公式就可以了。后面我有时间整理一下代码。

    2019-02-21
  • Thinking
    建议老师每堂课后能配多几个具有代表性的,针对性的练习题辅助理解概念和公式。

    作者回复: 好的,后面我会考虑多从公式的角度出发

    2019-02-15
收起评论
13
返回
顶部