当前位置: 首页 > news >正文

机器学习04 决策树

前言:简要介绍《机器学习》第四章–决策树,决策树算法主要为三部分:划分选择、树的生成、剪枝。划分选择的准则有信息增益、增益率、基尼指数;生成树的常用算法有ID3、C4.5、CART;剪枝是为了避免过拟合。本章数学公式推导较少,重点在于理解决策树的生成过程。


决策树(decision tree)是一种基本的分类和回归方法,《机器学习》第四章中主要讨论用于分类的决策树。
决策树学习的目的:产生一棵泛化能力强的树
策略:分而治之(divide-and-conquer)

决策树模型

分类决策树模型是一种对样例进行分类属性结构。决策树由结点(node)和有向边(directed edge)组成。结点分为根结点(唯一)、内部结点(internal node)和叶结点(leaf node),叶结点表示一个类对应于决策结果,内部和根结点对应一个属性测试。

青绿
乌黑
蜷缩
硬挺
浊响
色泽=?
根蒂=?
......
敲声
......
好瓜

停止条件:

  1. 当前结点包含的样本全属于同一类别
  2. 当前属性集为空,或所有样本在所有属性上取值相同
  3. 当前结点包含的样本集合为空

划分选择(特征选择)

划分选择(特征选择)是指选取对训练数据具有分类能力的特征或属性,希望分支结点所包含的样本尽可能属于同一类别,即结点纯度(purity)越高,其准则主要有信息增益、增益率、基尼指数。

熵(entropy)表示随机变量不确定性的度量,熵越大,不确定性越大。

X X X 是一个取有限个值的离散随机变量,概率分布为 P ( X = x i ) = p i , i = 1 , 2 , 3... n P(X=x_i)=p_i,i=1,2,3...n P(X=xi)=pi,i=1,2,3...n,则随机变量 X X X 的熵为 H ( X ) = − ∑ i = 1 n p i ∗ log ⁡ p i H(X)=-\sum ^{n}_{i=1}p_i*\log p_{i} H(X)=i=1npilogpi,通常式中对数以 2 或 e 为底数,单位分别为比特(bit)或纳特(nat)。

  • p i = 0 p_i=0 pi=0 时,定义 0 ∗ l o g 0 = 0 0*log0=0 0log0=0
  • 熵只依赖于 X X X 的分布,与 X X X 取值无关,有时也将熵记为 H ( p ) H(p) H(p)

信息熵

信息熵(information entropy)为度量样本集合纯度的指标,信息熵越大,则不确定性越大,纯度越低。

假定当前样本集合 D D D 中第 k k k 类样本所占比例为 p k ( k = 1 , 2 , 3... ∣ y ∣ , ∣ y ∣ 为样本集总的类别数 ) p_k(k=1,2,3...|y|,|y|为样本集总的类别数) pk(k=1,2,3...∣yy为样本集总的类别数),则信息熵计算公式: E n t ( D ) = − ∑ k = 1 ∣ y ∣ p k ∗ l o g 2 p k Ent(D)=-\sum^{|y|}_{k=1}p_k*log_2{p_k} Ent(D)=k=1ypklog2pk

条件熵

条件熵(conditional entropy)表示在已知随记变量 X X X 的条件下随机变量 Y Y Y 的不确定性,记为 H ( Y ∣ X ) = ∑ i = 1 n p i ∗ H ( Y ∣ X = x i ) H(Y|X)=\sum^n_{i=1}p_i*H(Y|X=x_i) H(YX)=i=1npiH(YX=xi)

从单个属性(特征) a a a 的角度来看, 假设其可能取值为 { a 1 , a 2 , … , a V } \left\{a^1, a^2, \ldots, a^V\right\} {a1,a2,,aV} D v D^v Dv 表示属性 a a a 取值为 a v ∈ { a 1 , a 2 , … , a V } a^v \in\left\{a^1, a^2, \ldots, a^V\right\} av{a1,a2,,aV} 的样本集合, ∣ D v D \frac{\mid D^v}{D} DDv 表示占比,那么在已知属性 a a a 的取值后,样本集合 D D D 的条件樀为: ∑ v = 1 V ∣ D v ∣ ∣ D ∣ Ent ⁡ ( D v ) \sum_{v=1}^V \frac{\left|D^v\right|}{|D|} \operatorname{Ent}\left(D^v\right) v=1VDDvEnt(Dv)

信息增益

信息增益(information gain)越大,则是用属性 a a a 来进行划分所获得的的纯度提升越大。

计算公式: G a i n ( D , a ) = E n t ( D ) − ∑ v = 1 V ∣ D v ∣ ∣ D ∣ E n t ( D v ) Gain(D,a)=Ent(D)-\sum^V_{v=1} \frac{|D^v|}{|D|}Ent(D^v) Gain(D,a)=Ent(D)v=1VDDvEnt(Dv),可理解为信息熵与条件熵的差值。

信息增益对可取值数目较多的属性有偏好。

增益率

增益率(gain ratio)计算公式: G a i n _ r a t i o ( D , a ) = G a i n ( D , a ) I V ( a ) Gain\_ratio(D,a)=\frac{Gain(D,a)}{IV(a)} Gain_ratio(D,a)=IV(a)Gain(D,a)

其中, I V ( a ) = − ∑ v = 1 V ∣ D v ∣ ∣ D ∣ l o g 2 ∣ D v ∣ ∣ D ∣ IV(a)=-\sum^V_{v=1} \frac{|D^v|}{|D|}log_2{\frac{|D^v|}{|D|}} IV(a)=v=1VDDvlog2DDv 称为属性 a a a 的固有值(intrinsic value)。属性 a a a 取值数目(V 值)越大,则 I V ( a ) IV(a) IV(a) 的值通常越大。

增益率对可取值数目较少的属性有偏好。

基尼指数

基尼指数(Gini index)

数据集 D D D 的纯度可用基尼值来度量: G i n i ( D ) = ∑ k = 1 ∣ y ∣ ∑ k ′ ≠ k p k p k ′ Gini(D)= \sum^{|y|}_{k=1} \sum_{k'≠k} p_k p_k^{'} Gini(D)=k=1yk=kpkpk,基尼值越小,数据集 D D D 的纯度越高。

属性 a a a 的基尼指数为: G i n i _ i n d e x ( D , a ) = ∑ v = 1 V ∣ D v ∣ ∣ D ∣ G i n i ( D v ) Gini\_index(D,a)= \sum^{V}_{v=1} \frac{|D^v|}{|D|} Gini(D^v) Gini_index(D,a)=v=1VDDvGini(Dv)

常用决策树模型

划分属性的准则
ID3信息增益
C4.5先从候选划分属性中找出信息增益高于平均水平的属性,再从中选择增益率最高的
CART 决策树基尼指数

多变量决策树

传统的单变量决策树(univariate decision tree)的分类边界是轴平行(axis-parallel)的,即分类边界由若干与坐标轴平行的线或面组成。优点是解释性强,缺点是需要考虑所有属性划分,时间耗费大。

多变量决策树(multivariate decision tree)实现「斜划分」等复杂划分的决策树,每个非叶结点都是一个线性分类器,而不再针对某个属性。

连续与缺失值处理

连续值处理

利用决策树处理连续数据,例如西瓜的含糖率,需要利用二分法(bi-partition)等连续属性离散化技术,

与离散属性不同的是,若当前结点划分属性为连续属性,则该属性还可作为其后代结点的划分属性。如:考试分数=60划分是否及格,分数(>60)=90划分是否优秀。

缺失值处理

解决两个问题:

  1. 如何在属性缺失的情况下进行划分属性选择?
  2. 给定划分属性,若样本在该属性上的值缺失,如何对样本进行划分?

思想:样本赋权,权重划分。



参考资料:

《机器学习》周志华

《统计学习方法》(第二版)李航

周志华《机器学习》(西瓜书) 视频_bilibili

《机器学习公式详解》(南瓜书)p6

相关文章:

  • java基础学习 day37 (集合)
  • Python闭包与闭包陷阱
  • 测试篇(三):测试用例的万能公式、对水杯和登录页面设计测试用例、测试用例的设计方法
  • 第十三届蓝桥杯省赛 Java A 组 I 题、Python A 组 I 题、Python B 组 J 题——最优清零方案(AC)
  • 阿里“云开发“小程序(uniCould)
  • 提权漏洞和域渗透历史漏洞整理
  • 传参的理解
  • 基于蜣螂算法的极限学习机(ELM)分类算法-附代码
  • 主流的操作系统(带你快速了解)
  • 六、numpy拷贝
  • STM32+python产生三角波
  • 【计算机网络(考研版)】第一站:计算机网络概述(一)
  • C++空间命名
  • 树,堆,二叉树的认识
  • 计算机存储系统
  • 自己简单写的 事件订阅机制
  • [js高手之路]搞清楚面向对象,必须要理解对象在创建过程中的内存表示
  • CSS选择器——伪元素选择器之处理父元素高度及外边距溢出
  • HashMap ConcurrentHashMap
  • java第三方包学习之lombok
  • laravel 用artisan创建自己的模板
  • Node + FFmpeg 实现Canvas动画导出视频
  • select2 取值 遍历 设置默认值
  • SpiderData 2019年2月23日 DApp数据排行榜
  • vue 配置sass、scss全局变量
  • 聚簇索引和非聚簇索引
  • 软件开发学习的5大技巧,你知道吗?
  • 怎样选择前端框架
  • 完善智慧办公建设,小熊U租获京东数千万元A+轮融资 ...
  • (C++17) optional的使用
  • (独孤九剑)--文件系统
  • (附源码)springboot 个人网页的网站 毕业设计031623
  • (免费领源码)python#django#mysql公交线路查询系统85021- 计算机毕业设计项目选题推荐
  • (十八)SpringBoot之发送QQ邮件
  • (译)2019年前端性能优化清单 — 下篇
  • (转)jdk与jre的区别
  • (转载)VS2010/MFC编程入门之三十四(菜单:VS2010菜单资源详解)
  • .NET Framework Client Profile - a Subset of the .NET Framework Redistribution
  • .Net Remoting(分离服务程序实现) - Part.3
  • .NET/C# 在代码中测量代码执行耗时的建议(比较系统性能计数器和系统时间)...
  • .NET版Word处理控件Aspose.words功能演示:在ASP.NET MVC中创建MS Word编辑器
  • .NET国产化改造探索(一)、VMware安装银河麒麟
  • .NET简谈设计模式之(单件模式)
  • @基于大模型的旅游路线推荐方案
  • [ 蓝桥杯Web真题 ]-Markdown 文档解析
  • [20170713] 无法访问SQL Server
  • [2021ICPC济南 L] Strange Series (Bell 数 多项式exp)
  • [Android Pro] listView和GridView的item设置的高度和宽度不起作用
  • [C#]扩展方法
  • [C++]Leetcode17电话号码的字母组合
  • [codeforces]Checkpoints
  • [docker]docker网络-直接路由模式
  • [Firefly-Linux] RK3568修改控制台DEBUG为普通串口UART
  • [GYCTF2020]Ez_Express
  • [HeadFrist-HTMLCSS学习笔记][第一章Web语言:开始了解HTML]