01 决策树 - 数学理论概述 - 熵

简介:

今天开始进入决策树的算法部分,首先介绍一下这部分涉及到的知识点。

一、大纲

1、信息熵

决策树在生成过程中,对于评判是否要对树进行划分的关键指标。即树生成时的决策根本。

2、决策树
之前提过KD树的划分标准。02 KNN算法 - KD Tree KD树是基于一个划分的标准(中位数),最后构建起了整个KD树。决策树同样也是一个树形结构,同样需要某些决策指标来构建起决策树。最后帮助我们实现回归或分类的目标。

3、决策树优化
和KD树一样,决策树模型生成以后同样会存在欠拟合和过拟合的问题。如何解决这些问题就是决策树优化需要考虑的。

4、剪枝
防止决策树过拟合的过程,实际生产过程中剪枝的操作用的很少,但面试可能会提问,了解即可。

5、决策树可视化
导入一些新的模块,最后将决策树展现在用户面前。

二、决策树的直观理解

根据一个人是否有房产、婚姻情况、年收入情况判断一个人是否有能力偿还债务。
根据样本构建出一个模型:

决策树

相比Logistic模型、回归模型中参数的理解,决策树是一个解释性更强的模型。

三、比特化

数据:BACADCBD...
这里ABCD出现的概率都是1/4,等概率。
即P(X=A) =P(X=B) =P(X=C) =P(X=D) =1/4

令A-00 B-01 C-10 D-11(等概率,用两个比特位表示4个变量即可)
BACADC = 01001011100111
E = 1×1/4 *4 = 1
(每个变量占用一个比特位,出现概率是1/4,一共4个变量,平均每个变量占1个比特位)


如果X变量出现概率不同:
即P(X=A)=1/2; P(X=B) = 1/4; P(X=C) =P(X=D) =1/8;

用更少的比特位描述出现概率更大的事件,能够让总的比特位数量最少:
令A-0 B-10 C-110 D-111

E=1×1/2 + 2×1/4 + 3×1/8 + 3×1/8 = 1.75
平均每个变量占1.75个比特位。其他任何一种编码方式最终得到的期望都会大于1.75,耗费了多余的计算机资源。

还可以用下面的公式表示__平均每个变量占用的比特位__数量:

$color{red}{每个变量出现的概率:}$ p
$color{red}{每个变量占用的比特位:}$ -log2p

所以,m个变量在不同的出现概率p1~pm时,平均每个变量占用的比特位公式如下:

四、信息熵

__信息熵__是描述一个信息量的指标。如果一个事件发生的概率越大,那么认为该事件蕴含的信息越少。

当一个事件百分百确定的时候,我们得不到其他推论。那么认为信息量为0。

只有当事件的出现存在概率性,说明有额外的信息影响事件发生,那么针对这些信息我们才需要推理判断 。

__信息熵__是系统有序程度的度量,一个系统越是有序,信息熵就越低。信息熵就是用来描述系统信息量的不确定度。

信息熵 = 比特化随机变量X占用比特位的数学期望

H(X)是随机变量X的信息熵

五、条件熵

回顾H(X)的概念,并看下面的例子:


令L(S) = -P(S) × log2(S)
H(X) = L(X=数学) + L(X=IT) + L(X=英语)

= -0.5 × log2(0.5) - 0.25 × log2(0.25) - 0.25×log2(0.25)
=  0.5 + 0.5 + 0.5 = 1.5

H(Y) = L(Y = M) + L(Y = F)

= -0.5 × log2(0.5) - 0.5 × log2(0.5)
= 0.5 + 0.5 = 1

H(X, Y) = L(X=数学, Y=M) + L(X=IT, Y=M) + L(X=英语, Y=F) +
L(X=数学, Y=F) = -0.25 × log2(0.25) × 4 = 2

看明白上面的例子后,接下来引入__条件熵__的概念:
给定条件X的情况下,随机变量Y的信息熵就是__条件熵__。
给定条件X的情况下,所有不同x值情况下,Y的信息熵的平均值,叫做__条件熵__。

当专业X为数学时,Y的信息熵的值为:H(Y|X=数学)
怎么计算H(Y|X=数学)?先把数学相关的项提取出来:

现在姓别出现的概率都是2/4,根据公式:

$color{red}{每个变量出现的概率:}$ p

$color{red}{每个变量占用的比特位:}$ -log2p

平均每个元素占比特
-log2(0.5)=1:单个性别的信息熵。
H(Y|X=数学) = -0.5 × log2(0.5) × 2 = 1


H(Y|X=数学) 是 H(Y|X) 的一部分,H(Y|X)还包括H(Y|X=IT)、H(Y|X=英语) 根据上述的方式能够依次计算出H(Y|X=IT)、H(Y|X=英语) 的值。

回顾一下定义:
给定条件X的情况下,所有不同x值情况下,Y的信息熵的平均值,叫做__条件熵__。

条件熵

条件熵例子

以下log表示log2

条件熵 H(X/Y)
= H(X/Y=M)×P(Y=M) + H(X/Y=F)×P(Y=F) 即加权平均熵

    = [L(X=数学/Y=M)+L(X=数学/Y=M)]×P(Y=M) + H(X/Y=F)×P(Y=F)
    = [-0.5 × log(0.5) × 2] × 0.5 + H(X/Y=F)×P(Y=F)
    = 0.5 + H(X/Y=F)×P(Y=F) = 0.5 + 0.5 = 1
    = __H(X, Y) - H(Y)__

条件熵 H(Y/X)
= H(Y/X=数学)×P(X=数学)+H(Y/X=IT)×P(X=IT)+H(Y/X=英语)×P(X=英语)

    = [-0.5 × log(0.5) × 2] × 0.5+H(Y/X=IT)×P(X=IT)+H(Y/X=英语)×P(X=英语)
    = 0.5 + 0 + 0 = 0.5
    = __H(X, Y) - H(X)__

条件熵__的另一个公式: __H(Y/X) = H(X, Y) - H(X)
事件(X,Y)发生所包含的熵,减去事件X单独发生的熵,即为事件X发生前提下,Y发生“新”带来的熵。

结合概率论中的Venn图思考上面公式的意义:

最后给出一个推导公式:

相关文章
|
人工智能 自然语言处理 Linux
进程(process) vs 线程(Thread)
本文主要介绍了进程和线程的基本概念、区别以及操作系统如何调度线程的方式。同时,还介绍了线程锁的核心原理和实现方式。在多线程编程中,理解进程和线程的概念以及线程锁的使用,对于保证程序的安全性和性能非常重要。
273 0
|
9月前
|
弹性计算 监控 安全
API稳定安全最佳实践:用阿里云SDK为业务保驾护航
阿里云智能集团高级技术专家赵建强和曹佩杰介绍了API稳定安全最佳实践,涵盖业务上云真实案例、集成开发最佳实践、配额管理和共担模型四部分。通过分析企业在不同阶段遇到的问题,如签名报错、异常处理不严谨、扩容失败等,提出了解决方案和工具,确保API调用的安全性和稳定性。特别强调了SDK的使用、无AK方案、自动刷新机制以及配额中心的作用,帮助用户构建更稳定、安全的服务,提升运维效率。最终介绍了集成开发共担模型,旨在通过最佳实践和平台工具,保障业务的稳定与安全,推动行业创新与发展。
|
10月前
|
缓存 安全 搜索推荐
阿里云先知安全沙龙(北京站) ——浅谈Web快速打点
信息收集是网络安全中的重要环节,常用工具如Hunter、Fofa和扫描工具可帮助全面了解目标系统的网络结构与潜在漏洞。遇到默认Nginx或Tomcat 404页面时,可通过扫路径、域名模糊测试、搜索引擎缓存等手段获取更多信息。AllIN工具(GitHub: P1-Team/AllIN)能高效扫描网站路径,发现敏感信息。漏洞利用则需充分准备,以应对突发情况,确保快速拿下目标站点。 简介:信息收集与漏洞利用是网络安全的两大关键步骤。通过多种工具和技术手段,安全人员可以全面了解目标系统,发现潜在漏洞,并制定有效的防御和攻击策略。
|
11月前
|
运维 负载均衡 安全
slb传统硬件负载均衡器的性能瓶颈
【11月更文挑战第3天】
291 4
|
存储 测试技术
Ceph Reef(18.2.X)的基于回收站临时删除块设备
这篇文章是关于Ceph Reef(18.2.X)版本中基于回收站临时删除块设备的操作指南,包括创建存储池、启用RBD功能、创建和删除块设备以及如何从回收站恢复块设备的详细步骤。
140 3
|
前端开发 网络安全
【XSS平台】使用,网络安全开发必学
【XSS平台】使用,网络安全开发必学
|
域名解析 缓存 负载均衡
【域名解析DNS专栏】域名解析在CDN服务中的应用与优化
【5月更文挑战第30天】本文探讨了域名解析在CDN服务中的重要性,强调其对访问速度和稳定性的影响。文中提出了三种优化方法:使用智能解析以动态选择最佳节点,配置负载均衡保证服务稳定,以及利用DNS缓存提升访问速度。通过Python代码示例展示了基本的DNS解析过程,结论指出优化域名解析对于提升网站性能至关重要。
313 1
|
弹性计算 安全 前端开发
阿里云服务器ECS通用型、计算型和内存实例区别、CPU型号、性能参数表
阿里云ECS实例有计算型(c)、通用型(g)和内存型(r)系列,区别在于CPU内存比。计算型1:2,如2核4G;通用型1:4,如2核8G;内存型1:8,如2核16G。实例有第五代至第八代,如c7、g5、r8a等,每代CPU型号和主频提升。例如,c7使用Intel Ice Lake,g7支持虚拟化Enclave。实例性能参数包括网络带宽、收发包能力、IOPS等,适合不同场景,如视频处理、游戏、数据库等
689 0
RPA数字员工:降本增效的智能利器
【1月更文挑战第6天】RPA数字员工:降本增效的智能利器
394 1
RPA数字员工:降本增效的智能利器