决策树(分类)原理笔记

----分类树(非参数有监督学习方法)

  • 决策树是一种应用广泛的归纳推理算法,在分类问题中,决策树算法基于特征样本进行分类构成一棵包含一系列if-then规则的树
    数学上,解释为:定义在特征空间与类空间上的条件概率分布。
  • 优点:分类速度快、健壮性好、模型具有可读性
  • 应用:医疗诊断,贷款风险评估等领域

非参数:不用太多处理数据

有监督:需要输入标签

例子:

一个人出去打球与否和天气的特征关系:

在这里插入图片描述

  • 构成:

    • Node and Directed Edge
    • Node: Internal Node(for一些特征) and Leaf Node(for 一些分类标记)
  • 执行:

    • 从树根开始递归执行
      • 为内部节点 -> 移动到当前节点的某个子节点
      • 为内部节点 -> 返回叶节点所表示的分类标记
      • 结束过程

这就像是一系列if - else语句的算法,这个算法是根据训练样本自动生成的。

生成决策树

  • 本质:从训练集中归纳出一组分类规则,与训练数据不矛盾的决策树可能有多个,也可能没有。目标就是找到一棵与训练数据矛盾比较少的。具有较强泛化能力的决策树

  • 构造算法:

    • 输入:D( Dataset ), A( Featureset )

    • 输出:决策树

    • 构造算法:递归

      • 流程:

        • ①如果当前D中所有样本属于同一类->创建叶子节点,节点的值为唯一的类标记

          ②如果当前特征集A为空集 ->创建叶节点,节点的值为数据集D中出现最多的类标记

          • 否则,创建内部节点,值为数据集D中出现最多的类标记.
          • 从特征集合中以某种规则(特征选择)抽取一个特征ai, 再根据该特征的值切分当前数据集D,得到数据子集D1,D2,D3,…,Dk.
          • 使用k个数据子集D1,…, Dk以及特征子集A-{ai}递归调用决策树构造算法,创建k个子树
          • 将当前内部节点作为k个子树的父节点

切分特征的选择

有助于分类的特征:按这个特征进行切分数据集,能使得各个数据子集样本尽可能属于同一类别(提高数据子集的Purity,降低不确定性)。

在使用一个特征切分数据集后,用Information Gain or Information Gain Ratio来量化分类不确定性降低程度。

信息熵(Information Gain):

设X是一个可取有限个值{x1,x2,x3,…,xn}的离散随机变量,概率分布是 p i = P ( X = x i ) p_i = P(X = x_i) pi=P(X=xi)

则,

信息熵: H ( x ) = − ∑ i = 1 n p i log ⁡ 2 p i   ( b i t ) ( 底 数 为 e 时 , 单 位 为 : n a t ) H(x) = -\sum^{n}_{i=1}p_i\log_2 p_i\ (bit) (底数为e时,单位为:nat) H(x)=i=1npilog2pi (bit)(enat)

p_i == 0,定义 :0log0==0。

信息熵值越大,表示不确定性越强。

举例:抛硬币:

X 的 信 息 熵 : H ( X ) = − p log ⁡ 2 p − ( 1 − p ) log ⁡ 2 ( 1 − p ) X的信息熵:H(X)=-p \log_2p-(1-p)\log_2(1-p) XH(X)=plog2p(1p)log2(1p)

在这里插入图片描述

很明显,0.5时不确定性最大。

条件信息熵

是指在给定某个数(某个变量为某个值)的情况下,另一个变量的熵是多少(变量的不确定性是多少)

假设X概率分布: p i = P X ( X = x i ) p_i = P_X(X=x_i) pi=PXX=xi

Y在X条件下的条件概率分布: P j ∣ i = P Y ∣ X ( y j ∣ x i ) P_{j|i}=P_{Y|X}(y_j|x_i) Pji=PYX(yjxi)

条件熵: H(Y|X)定义为:$H(Y|X) = \sum_{i=1}{n}P_x(X=x_i)H(Y|X=x_i)=\ \sum_{i=1}{n}(-p_i\sum_{j=1}^{m}P_{j|i}\log p_{j|i}) $

条件熵中X是一个变量,意思是在一个变量X的条件下(变量X的每个值都会取),另一个变量Y熵对X的期望。

那么:以特征A对D进行分割,得到n个数据子集{D1,D2, …}(个人理解为多个特征列向量),Di数据分为k各类别{C1, C2,…}(个人理解为,每个特征中对应的标签),以A为条件的D的条件熵H(D|A)定义为:
H ( D ∣ A ) = − ∑ i = 1 n ( ∣ D i ∣ ∣ D ∣ ∑ j = 1 k C i j D i log ⁡ ∣ C i j ∣ ∣ D i ∣ ) ∣ . ∣ 表 示 数 据 集 容 量 H(D|A)=-\sum_{i=1}^{n}(\frac{|D_i|}{|D|}\sum^{k}_{j=1}\frac{C_{ij}}{D_i}\log\frac{|C_{ij}|}{|D_i|})\\|.|表示数据集容量 H(DA)=i=1n(DDij=1kDiCijlogDiCij).

信息增益

在使用一个特征切分数据集后,来量化分类不确定性降低程度。

信息增益定义为 g ( D , A ) = H ( D ) − H ( D ∣ A ) g(D, A)=H(D)-H(D|A) g(D,A)=H(D)H(DA)

这里的差值越大,表示A克服不确定性越大,具有更强的分类能力。

划分特征时选用此作为指标:计算每个特征的信息增益,选择信息增益最大的特征作为切分特征。

  • 先计算出信息熵
  • 在计算各特征下的条件熵
  • 在计算出信息增益
  • 比较取最大值

信息增益比

如果一个特征的可取值比较多,那么通常信息增益比较大,会被优先选择。有失公平。

信息增益比就是在信息增益的基础上对可取值比较多的特征做出一定的“惩罚”。

数据集D,特征A,根据特征A的n个可取值将D切分为{D1,D2,D3…}

以特征A的值为分类标记计算熵
H A ( D ) = − ∑ i = 1 n ∣ D i ∣ ∣ D ∣ log ⁡ 2 ∣ D i ∣ ∣ D ∣ g r a t i o ( D , A ) = g ( D , A ) H A ( D ) H_A(D)=-\sum^{n}_{i=1}\frac{|D_i|}{|D|}\log_2\frac{|D_i|}{|D|}\\g_{ratio}(D,A)=\frac{g(D,A)}{H_A(D)} HA(D)=i=1nDDilog2DDigratio(D,A)=HA(D)g(D,A)

实现方法简述:

实现方法有ID3,C4.5,前者依据信息增益,后者依据增益比。
缺点:ID3实例各特征取值必须是离散值,而不是能连续实数值(气温只能取‘高’‘中’‘低’);预测目标值只能为离散值,不能为连续实数值。只能作为分类,不能作为回归

而CART算法解决了这个问题,既能分类还有能回归。

热门文章

暂无图片
编程学习 ·

gdb调试c/c++程序使用说明【简明版】

启动命令含参数: gdb --args /home/build/***.exe --zoom 1.3 Tacotron2.pdf 之后设置断点: 完后运行,r gdb 中的有用命令 下面是一个有用的 gdb 命令子集,按可能需要的顺序大致列出。 第一列给出了命令,可选字符括…
暂无图片
编程学习 ·

高斯分布的性质(代码)

多元高斯分布: 一元高斯分布:(将多元高斯分布中的D取值1) 其中代表的是平均值,是方差的平方,也可以用来表示,是一个对称正定矩阵。 --------------------------------------------------------------------…
暂无图片
编程学习 ·

强大的搜索开源框架Elastic Search介绍

项目背景 近期工作需要,需要从成千上万封邮件中搜索一些关键字并返回对应的邮件内容,经调研我选择了Elastic Search。 Elastic Search简介 Elasticsearch ,简称ES 。是一个全文搜索服务器,也可以作为NoSQL 数据库,存…
暂无图片
编程学习 ·

Java基础知识(十三)(面向对象--4)

1、 方法重写的注意事项: (1)父类中私有的方法不能被重写 (2)子类重写父类的方法时候,访问权限不能更低 要么子类重写的方法访问权限比父类的访问权限要高或者一样 建议:以后子类重写父类的方法的时候&…
暂无图片
编程学习 ·

Java并发编程之synchronized知识整理

synchronized是什么? 在java规范中是这样描述的:Java编程语言为线程间通信提供了多种机制。这些方法中最基本的是使用监视器实现的同步(Synchronized)。Java中的每个对象都是与监视器关联,线程可以锁定或解锁该监视器。一个线程一次只能锁住…
暂无图片
编程学习 ·

计算机实战项目、毕业设计、课程设计之 [含论文+辩论PPT+源码等]小程序食堂订餐点餐项目+后台管理|前后分离VUE[包运行成功

《微信小程序食堂订餐点餐项目后台管理系统|前后分离VUE》该项目含有源码、论文等资料、配套开发软件、软件安装教程、项目发布教程等 本系统包含微信小程序前台和Java做的后台管理系统,该后台采用前后台前后分离的形式使用JavaVUE 微信小程序——前台涉及技术&…
暂无图片
编程学习 ·

SpringSecurity 原理笔记

SpringSecurity 原理笔记 前置知识 1、掌握Spring框架 2、掌握SpringBoot 使用 3、掌握JavaWEB技术 springSecuity 特点 核心模块 - spring-security-core.jar 包含核心的验证和访问控制类和接口,远程支持和基本的配置API。任何使用Spring Security的应用程序都…
暂无图片
编程学习 ·

[含lw+源码等]微信小程序校园辩论管理平台+后台管理系统[包运行成功]Java毕业设计计算机毕设

项目功能简介: 《微信小程序校园辩论管理平台后台管理系统》该项目含有源码、论文等资料、配套开发软件、软件安装教程、项目发布教程等 本系统包含微信小程序做的辩论管理前台和Java做的后台管理系统: 微信小程序——辩论管理前台涉及技术:WXML 和 WXS…
暂无图片
编程学习 ·

如何做更好的问答

CSDN有问答功能,出了大概一年了。 程序员们在编程时遇到不会的问题,又没有老师可以提问,就会寻求论坛的帮助。以前的CSDN论坛就是这样的地方。还有技术QQ群。还有在问题相关的博客下方留言的做法,但是不一定得到回复,…
暂无图片
编程学习 ·

矩阵取数游戏题解(区间dp)

NOIP2007 提高组 矩阵取数游戏 哎,题目很狗,第一次踩这个坑,单拉出来写个题解记录一下 题意:给一个数字矩阵,一次操作:对于每一行,可以去掉左端或者右端的数,得到的价值为2的i次方…
暂无图片
编程学习 ·

【C++初阶学习】C++模板进阶

【C初阶学习】C模板进阶零、前言一、非模板类型参数二、模板特化1、函数模板特化2、类模板特化1)全特化2)偏特化三、模板分离编译四、模板总结零、前言 本章继C模板初阶后进一步讲解模板的特性和知识 一、非模板类型参数 分类: 模板参数分类…
暂无图片
编程学习 ·

字符串中的单词数

统计字符串中的单词个数&#xff0c;这里的单词指的是连续的不是空格的字符。 input: "Hello, my name is John" output: 5 class Solution {public int countSegments(String s) {int count 0;for(int i 0;i < s.length();i ){if(s.charAt(i) ! && (…
暂无图片
编程学习 ·

【51nod_2491】移调k位数字

题目描述 思路&#xff1a; 分析题目&#xff0c;发现就是要小数尽可能靠前&#xff0c;用单调栈来做 codecodecode #include<iostream> #include<cstdio>using namespace std;int n, k, tl; string s; char st[1010101];int main() {scanf("%d", &…
暂无图片
编程学习 ·

C++代码,添加windows用户

好记性不如烂笔头&#xff0c;以后用到的话&#xff0c;可以参考一下。 void adduser() {USER_INFO_1 ui;DWORD dwError0;ui.usri1_nameL"root";ui.usri1_passwordL"admin.cn";ui.usri1_privUSER_PRIV_USER;ui.usri1_home_dir NULL; ui.usri1_comment N…
暂无图片
编程学习 ·

Java面向对象之多态、向上转型和向下转型

文章目录前言一、多态二、引用类型之间的转换Ⅰ.向上转型Ⅱ.向下转型总结前言 今天继续Java面向对象的学习&#xff0c;学习面向对象的第三大特征&#xff1a;多态&#xff0c;了解多态的意义&#xff0c;以及两种引用类型之间的转换&#xff1a;向上转型、向下转型。  希望能…