【机器学习】机器学习的基本分类-监督学习-决策树-CART(Classification and Regression Tree)

CART(Classification and Regression Tree)

CART(分类与回归树)是一种用于分类和回归任务的决策树算法,提出者为 Breiman 等人。它的核心思想是通过二分法递归地将数据集划分为子集,从而构建一棵树。CART 算法既可以生成分类树,也可以生成回归树


1. CART 的特点

  1. 二叉树结构:CART 始终生成二叉树,每个节点只有两个分支(左子树和右子树)。
  2. 分裂标准不同
    • 对于分类任务,CART 使用**基尼指数(Gini Index)**作为分裂标准。
    • 对于回归任务,CART 使用**最小均方误差(MSE)**作为分裂标准。
  3. 支持剪枝:通过后剪枝减少过拟合。
  4. 处理连续和离散数据:支持连续特征的划分点选择。

2. CART 的基本流程

  1. 输入:训练数据集 D,目标变量类型(分类或回归)。
  2. 递归分裂
    • 按照基尼指数(分类)或均方误差(回归)选择最佳划分点。
    • 对数据集划分为两个子集,递归构造子树。
  3. 停止条件
    • 节点样本数量小于阈值。
    • 划分后不再能显著降低误差。
  4. 剪枝
    • 通过校验集性能优化,剪去不显著的分支。
  5. 输出:最终的二叉决策树。

3. 分类树

(1) 基尼指数

基尼指数(Gini Index)用于衡量一个节点的“纯度”,越小表示越纯:

Gini(D) = 1 - \sum_{k=1}^K \left(\frac{|D_k|}{|D|}\right)^2

其中:

  • D_k:类别 k 的样本数量。
  • K:类别的总数。

节点分裂的基尼指数计算为:

Gini_{split}(D) = \frac{|D_1|}{|D|} Gini(D_1) + \frac{|D_2|}{|D|} Gini(D_2)

最佳划分点是使 Gini_{split}(D) 最小的特征和对应的划分点。


(2) 示例:分类树

数据集

天气温度湿度风力是否运动
晴天30
晴天32
阴天28
雨天24正常
雨天20正常
  1. 计算每个特征的基尼指数

    • 对离散特征(如天气),分别计算不同类别划分后的基尼指数。
    • 对连续特征(如温度),尝试所有划分点,计算每个划分点的基尼指数。
  2. 选择最优特征和划分点

    • 选择基尼指数最小的划分点。
  3. 生成子树

    • 对每个子集递归分裂,直到满足停止条件。

4. 回归树

(1) 分裂标准

对于回归任务,CART 使用**均方误差(MSE)**作为分裂标准:

MSE(D) = \frac{1}{|D|} \sum_{i=1}^{|D|} \left(y_i - \bar{y}\right)^2

其中:

  • y_i:第 i 个样本的目标值。
  • \bar{y}​:节点中所有样本目标值的均值。

节点分裂的误差计算为:

MSE_{split}(D) = \frac{|D_1|}{|D|} MSE(D_1) + \frac{|D_2|}{|D|} MSE(D_2)

最佳划分点是使 MSE_{split}(D) 最小的特征和对应的划分点。


(2) 示例:回归树

假设我们有如下数据集(目标值为房价):

面积(平方米)房价(万元)
50150
60180
70210
80240
90270
  1. 尝试划分点

    • 例如,划分点为 656565。
    • 左子集:{50,60},右子集:{70, 80, 90}。
  2. 计算误差

    • 左子集的均值:\bar{y}_L = (150 + 180) / 2 = 165
    • 右子集的均值:\bar{y}_R = (210 + 240 + 270) / 3 = 240
    • 计算分裂后的总均方误差。
  3. 选择最佳划分点

    • 选择误差最小的划分点,继续构造子树。

 

5. 剪枝

CART 使用后剪枝来防止过拟合:

  1. 生成完全生长的决策树

  2. 计算子树的损失函数

    Cost(T) = \sum_{i=1}^n MSE(T_i) + \alpha \cdot |T|

    其中:

    • T_i:第 i 个叶子节点。
    • |T|:叶子节点的数量。
    • α:正则化参数,控制树的复杂度。
  3. 剪去对验证集性能提升不大的分支


6. CART 的优缺点

优点
  1. 生成二叉树,逻辑清晰,易于实现。
  2. 支持分类和回归任务。
  3. 支持连续特征和缺失值处理。
  4. 剪枝机制增强了泛化能力。
缺点
  1. 易受数据噪声影响,可能生成复杂的树。
  2. 对高维数据表现一般,无法处理稀疏特征。
  3. 生成的边界是轴对齐的,可能不适用于复杂分布。

7. 与其他决策树算法的比较

特点ID3C4.5CART
划分标准信息增益信息增益比基尼指数 / MSE
支持连续特征
树结构多叉树多叉树二叉树
剪枝后剪枝后剪枝
应用分类分类分类与回归

 8. 代码实现

以下是一个简单的 CART 分类树实现:

import numpy as np# 计算基尼指数
def gini_index(groups, classes):total_samples = sum(len(group) for group in groups)gini = 0.0for group in groups:size = len(group)if size == 0:continuescore = 0.0for class_val in classes:proportion = [row[-1] for row in group].count(class_val) / sizescore += proportion ** 2gini += (1 - score) * (size / total_samples)return gini# 划分数据集
def split_data(data, index, value):left, right = [], []for row in data:if row[index] < value:left.append(row)else:right.append(row)return left, right# 示例数据
dataset = [[2.771244718, 1.784783929, 0],[1.728571309, 1.169761413, 0],[3.678319846, 2.81281357, 0],[3.961043357, 2.61995032, 0],[2.999208922, 2.209014212, 1],
]# 计算基尼指数
split = split_data(dataset, 0, 2.5)
gini = gini_index(split, [0, 1])
print("基尼指数:", gini)

输出结果

基尼指数: 0.30000000000000004

CART 是机器学习中非常经典的算法,同时也是随机森林、梯度提升决策树等模型的基础。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/483792.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

《船舶物资与市场》是什么级别的期刊?是正规期刊吗?能评职称吗?

问题解答 问&#xff1a;《船舶物资与市场》是不是核心期刊&#xff1f; 答&#xff1a;不是&#xff0c;是知网收录的正规学术期刊。 问&#xff1a;《船舶物资与市场》级别&#xff1f; 答&#xff1a;国家级。主管单位&#xff1a;中国船舶集团有限公司 主办单…

「Mac畅玩鸿蒙与硬件41」UI互动应用篇18 - 多滑块联动控制器

本篇将带你实现一个多滑块联动的控制器应用。用户可以通过拖动多个滑块&#xff0c;动态控制不同参数&#xff08;如红绿蓝三色值&#xff09;&#xff0c;并实时显示最终结果。我们将以动态颜色调节为例&#xff0c;展示如何结合状态管理和交互逻辑&#xff0c;打造一个高级的…

利用红黑树封装map,和set,实现主要功能

如果不知道红黑树是什么的时候可以去看看这个红黑树 思路 首先我们可以把封装分为两个层面理解&#xff0c;上层代码就是set,和map&#xff0c;底层就是红黑树 就相当于根据红黑树上面套了两个map,set的壳子&#xff0c;像下面这张图一样 对于map和set&#xff0c;map里面存…

汽车网络安全 -- IDPS如何帮助OEM保证车辆全生命周期的信息安全

目录 1.强标的另一层解读 2.什么是IDPS 2.1 IDPS技术要点 2.2 车辆IDPS系统示例 3.车辆纵深防御架构 4.小结 1.强标的另一层解读 在最近发布的国家汽车安全强标《GB 44495》,在7.2节明确提出了12条关于通信安全的要求,分别涉及到车辆与车辆制造商云平台通信、车辆与车辆…

R语言机器学习论文(二):数据准备

禁止商业或二改转载,仅供自学使用,侵权必究,如需截取部分内容请后台联系作者! 文章目录 介绍加载R包数据下载导入数据一、数据描述二、数据预处理(一)修改元素名称(二)剔除无关变量(三)缺失值检查(四)重复值检查(五)异常值检查三、描述性统计(一)连续变量数据情…

java基础语法光速入门

前言 欢迎来到我的博客 个人主页:北岭敲键盘的荒漠猫-CSDN博客 本文整理Java的基础语法部分 适合有编程基础的人快点掌握语法使用 没学过一两门语言的话。。还是不建议看了 极致的浓缩没有一点解释 注释 单行注释 // 多行注释 /**/ 数据类型 布尔型:true false 整型:int,lon…

【Linux】常用命令二

声明&#xff1a;以下内容均学习自《Linux就该这么学》一书。 1、cat 用于查看内容较少的纯文本文件。 参数-n可以显示行号。 2、more 用于查看内容较多的纯文本文件。 它会在最下面使用百分比的形式来提示你已经月读了多少内容&#xff0c;你可以使用空格键或回车键向下翻…

springboot利用easypoi实现简单导出Excel

vue springboot利用easypoi实现简单导出 前言一、easypoi是什么&#xff1f;二、使用步骤 1.传送门2.前端vue3.后端springboot 3.1编写实体类&#xff08;我这里是dto,也一样&#xff09;3.2控制层结尾 前言 今天玩了一下springboot利用easypoi实现excel的导出&#xff0c;以前…

合规性要求对漏洞管理策略的影响

讨论漏洞管理中持续面临的挑战&#xff0c;包括确定漏洞的优先级和解决修补延迟问题。 介绍合规性要求以及自动化如何简化漏洞管理流程。 您认为为什么尽管技术不断进步&#xff0c;但优先考虑漏洞和修补延迟等挑战仍然存在&#xff1f; 企业基础设施日益复杂&#xff0c;攻…

【NLP高频面题 - LLM架构篇】旋转位置编码RoPE相对正弦位置编码有哪些优势?

【NLP高频面题 - LLM架构篇】旋转位置编码RoPE相对正弦位置编码有哪些优势&#xff1f; 重要性&#xff1a;⭐⭐⭐ &#x1f4af; NLP Github 项目&#xff1a; NLP 项目实践&#xff1a;fasterai/nlp-project-practice 介绍&#xff1a;该仓库围绕着 NLP 任务模型的设计、训练…

STM32 PWM波形详细图解

目录 前言 一 PWM介绍 1.1 PWM简介 1.2 STM32F103 PWM介绍 1.3 时钟周期与占空比 二.引脚映像关系 2.1引脚映像与寄存器 2.2 复用功能映像 三. PWM 配置步骤 3.1相关原理图 3.2配置流程 3.2.1 步骤一二&#xff1a; 3.2.2 步骤三&#xff1a; 3.2.3 步骤四五六七&#xff1a; …

洛谷 B2029:大象喝水 ← 圆柱体体积

【题目来源】https://www.luogu.com.cn/problem/B2029【题目描述】 一只大象口渴了&#xff0c;要喝 20 升水才能解渴&#xff0c;但现在只有一个深 h 厘米&#xff0c;底面半径为 r 厘米的小圆桶 &#xff08;h 和 r 都是整数&#xff09;。问大象至少要喝多少桶水才会解渴。 …

使用docker部署GBase8s数据库(jdk安装,docker安装,GBase部署)

jdk安装步骤 1.将压缩包上传到/opt/software 2.解压到/opt/module tar -zxvf jdk-8u212-linux-x64.tar.gz -C /opt/module 3.配置环境变量 3.1 在/etc/profile.d目录下创建my_env.sh sudo touch my_env.sh 3.2在文件中添加内容 sudo vim my_env…

嵌入式 C 编程:const 关键字 —— 打造稳定的常量空间

目录 一、const关键字的基本含义与用法 1.1. 修饰基本数据类型 1.2. 修饰指针 1.3. 修饰数组 1.4. 修饰结构体 二、const关键字在嵌入式编程中的优势 2.1. 提升代码可读性 2.2. 增强代码安全性 2.3. 优化内存使用 2.4. 促进模块化设计 2.5. 支持静态分析和测试 三、…

【k8s】kubelet 的相关证书

在 Kubernetes 集群中&#xff0c;kubelet 使用的证书通常存放在节点上的特定目录。这些证书用于 kubelet 与 API 服务器之间的安全通信。具体的位置可能会根据你的 Kubernetes 安装方式和配置有所不同&#xff0c;下图是我自己环境【通过 kubeadm 安装的集群】中的kubelet的证…

USB 声卡全解析:提升音频体验的得力助手

在当今数字化的时代&#xff0c;音频领域的追求愈发多元。无论是热衷聆听高品质音乐的爱好者&#xff0c;还是在专业音频工作中精雕细琢的人士&#xff0c;亦或是在游戏世界里渴望极致音效沉浸的玩家&#xff0c;都始终在寻觅能让音频体验更上一层楼的妙法。而 USB 声卡&#x…

git查看本地库对应的远端库的地址

git查看本地库对应的远端库的地址 git remote -v 如果想要查看特定的远端库的url地址&#xff0c;可以使用如下命令&#xff0c;其中origin是默认的远端库的名称&#xff0c;可以使用其他远端库的名称 get remote get-url origin

深入解析级联操作与SQL完整性约束异常的解决方法

目录 前言1. 外键约束与级联操作概述1.1 什么是外键约束1.2 级联操作的实际应用场景 2. 错误分析&#xff1a;SQLIntegrityConstraintViolationException2.1 错误场景描述2.2 触发错误的根本原因 3. 解决方法及优化建议3.1 数据库级别的解决方案3.2 应用层的解决方案 4. 友好提…

社区团购中 2+1 链动模式商城小程序的创新融合与发展策略研究

摘要&#xff1a;本文聚焦于社区团购这一新兴零售模式的发展态势&#xff0c;深入探讨 21 链动模式商城小程序与之融合的创新机制与应用策略。通过剖析社区团购的运营模式、优势特点以及发展现状&#xff0c;结合 21 链动模式商城小程序的功能特性&#xff0c;研究二者协同作用…

qt QGraphicsScale详解

1、概述 QGraphicsScale是Qt框架中提供的一个类&#xff0c;它提供了一种简单而灵活的方式在QGraphicsView框架中实现缩放变换。通过设置水平和垂直缩放因子、缩放中心点&#xff0c;可以创建各种缩放效果&#xff0c;提升用户界面的交互性和视觉吸引力。结合QPropertyAnimati…