通过信息增益，采用递归的方式生成树（找出最合适的节点顺序以及叶子对应的类标签）
决策树是一种分类与回归方法，主要用于分类，决策树模型呈现树形结构，是基于输入特征对实例进行分类的模型。决策树其实是定义在特征空间与类空间上的条件概率分布！
低信息熵：表示随机变量X各种取值不是等概率出现。可能出现有的事件概率很大，有的事件概率很小。
3. 当专业(X)为英语的时候，Y的信息熵的值为:H(Y|X=数学)
4. 当专业(X)为IT的时候，Y的信息熵的值为:H(Y|X=数学)
给定条件X的情况下，所有不同x值情况下Y的信息熵的平均值叫做条件熵
决策树构建目标就是让各个分裂子集尽可能的’纯’，也就是让一个分裂子数据集中待分类的项尽可能的属于同一个类别。
在上文提到了两个关键性的事情，叫做 最优的划分方式 和 选择最优特征，这里我们就要讨论的是划分方式。众所周知，数据分为离散的和连续的，显然我们对他们的处理有些不同。
之前我们说了划分方式，那么我们如何选择最优的特征呢。答案是比较纯度。
决策树算法是一种“贪心”算法策略，只考虑在当前数据特征情况下的最好分割方式，不能进行回溯操作。
在某种意义上的局部最优解，也就是说我只保证在当前分裂的时候，能够使数据最纯就好。
而对于整体的数据集而言，通过查看每个特征属性划分后的纯度变化进行比较，选择能让数据集变得更纯的特征属性进行分割。之后重复上述步骤直到满足条件。
在剪枝和判断的时候需要一个种体现变化的系数，于是出现了如下公式来作为C4.5和ID3的判别标准
这个公式表达了以A属性划分后，信息量增加的量，或者说指代的是纯度变纯了多少。
D目标属性，A为某一个待划分的特征属性；Gain为A为特征对训练数据集D的信息增益
决策树构建的过程是不断递归的过程，就像 (是) while 循环一样，必须有跳出循环的条件。以下是两个停止条件。
只保留80和97.5
因为 如果选择67.5,它将60和75分开了，但是60和75的Y都是否，标签相同，最好还是分到一个类中
首先，计算按照拥有房产这个特征进行划分的信息增益，使用信息熵进行纯度的计算：
计算原始数据的信息熵：
计算按拥有房产划分后的结果集的条件熵H(D|A)：
计算信息增益度Gain(房产)：
Gain(D,年收入=97.5)=0.395
Gain(D,年收入=80)=0.116
按照Gain越大，分割后的纯度越高，因此第一个分割的特征属性为年收入，并按照97.5进行划分。
左子树的结果集够纯，因此不需要继续划分。
接下来，对右子树年收入<97.5的数据，继续选择特征进行划分，且不再考虑收入这个特征，注意需要重新计算Gain(D,婚姻)，Gain(D,房产)，方法如上下
H(D|A=已婚)=0
H(D|A=单身)=0
H(D|A=有房产)=0
Gain(D,房产) = 0.97-0.776=0.194
选取婚姻作为分割属性
当构建好一个判断模型后，新来一个用户后，可以根据构建好的模型直接进行判断，比如新用户特性为：无房产、单身、年收入55K，那么根据判断得出该用户无法进行债务偿还。这种决策对于借贷业务有比较好的指导意义。
ID3算法是决策树的一个经典的构造算法，内部使用信息熵以及信息增益来进行构建；每次迭代选择信息增益最大的特征属性作为分割属性
优点：决策树构建速度快；实现简单
缺点：
在ID3算法的基础上，进行算法优化提出的一种算法(C4.5)；
现在C4.5已经是特别经典的一种决策树构造算法；
使用信息增益率来取代ID3算法中的信息增益，在树的构造过程中会进行剪枝操作进行优化；
能够自动完成对连续属性的离散化处理；
C4.5构建的是多分支的决策树；
优点： 产生的规则易于理解 准确率较高 实现简单 缺点： 对数据集需要进行多次顺序扫描和排序，所以效率较低 只适合小规模数据集，需要将数据放到内存中
使用基尼系数(分类树)作为数据纯度的量化指标来构建的决策树算法就叫做CART(Classification And Regression Tree，分类回归树)算法。
CART算法使用GINI增益率作为分割属性选择的标准，选择GINI增益率最大的作为当前数据集的分割属性；
可用于分类和回归两类问题。
算法
支持模型
树结构
划分特征选择
连续值处理
缺失值处理
剪枝
特征属性多次使用
ID3
分类
多叉树
信息增益
不支持
不支持
不支持
不支持
C4.5
分类
多叉树
信息增益率
支持
支持
支持
不支持
CART
分类、回归
二叉树
基尼系数、均方差
支持
支持
支持
支持
分类树采用信息增益、信息增益率、基尼系数来评价树的效果，都是基于概率值进行判断的；
而分类树的叶子节点的预测值一般为叶子节点中概率最大的类别作为当前叶子的预测值。
在回归树中，叶子节点的预测值一般为叶子节点中所有值的均值来作为当前叶子节点的预测值。
所以在回归树中一般采用MSE或者MAE作为树的评价指标，即均方差。
一般情况下，只会使用CART算法构建回归树
决策树过渡拟合一般情况是由于节点太多导致的，剪枝优化对决策树的正确率影响是比较大的，也是最常用的一种优化方式。
利用训练数据随机产生多个决策树，形成一个森林。然后使用这个森林对数据进行预测，选取最多结果作为预测结果。
决策树的剪枝是决策树算法中最基本、最有用的一种优化方案，主要分为两大类： 前置剪枝：在决策树的生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点标记为叶节点。 后置剪枝：先从训练集生成一颗完整的决策树，然后自底向上地对非叶节点进行考察，若将该结点对应的子树替换为叶节点能带来决策树泛化性能提升，则将该子树替换为叶节点。
后剪枝总体思路(交叉验证)： 由完全树T0开始，剪枝部分节点得到T1，在此剪枝得到T2…直到仅剩树根的树Tk 在验证数据集上对这k+1个树进行评价，选择最优树Ta（损失函数最小的树）
采用信息增益准则生成决策树
（1）若根结点“脐部”不进行划分，被标记为叶结点，其类别标记为训练样例数最多的类别，假设标记为“好瓜”。用验证集进行评估，编号{4,5,8}被正确分类，{9,11,12,13}被错误分类，精度为42.9%。用属性“脐部”划分后，{4,5,8,11,12}被正确分类，验证集精度为71.4%。因此，用“脐部”划分得以确定。
（2） 对②进行划分，基于信息增益准则挑选出”色泽“，{5}会被错分，划分后验证集精度下降，于是将禁止结点②被划分。
（3） 对③，最优划分属性为”根蒂“，划分前后精度一样，禁止划分。
（4） 对④，其所含训练样例已属于同一类，不再进行划分。
缺点：基于”贪心“，有欠拟合风险。有些分支当前划分虽然不能提升泛化性能，但在其基础上进行后续划分却有可能导致性能显著提高。
先从训练集生成一颗完整的决策树。图中决策树的验证集精度为42.9%。
（1）首先考虑结点⑥，剪枝后的叶结点包含编号{7,15}的训练样本，于是，该叶结点的类别标记为”好瓜“，此时验证集精度提高至57.1%。因此决定剪枝。
（2）考察结点⑤，替换后的叶结点包含{6,7,15}，标记为”好瓜“，验证集精度仍为57.1%，可以不进行剪枝。
（3）对结点②，替换后的叶结点包括{1,2,3,14}，标记为”好瓜”，此时验证集精度提高至71.4%，于是，决定剪枝。
（4）对结点③和①，替换后精度均未得到提高，于是得以保留。
因为决策树在构建过程中，每次选择划分特征的目的—让数据具有更加好的区分能力，
也就是说我们每次选择的特征是具有明显区分能力的特征，
可以认为这些被选择的特征对y的取值有更大的影响，
因此决策树可以用于特征选择。
决策树的特质之一就是它们需要的数据准备工作非常少。特别是，完全不需要进行特征缩放或集中。
分类树–对离散变量做决策树
回归树–对连续变量做决策树
优点:
缺点:
决策树是一种分类和回归的基本模型，可从三个角度来理解它，即：
主要的优点有两个：
使用ID3 C4.5决策树算法中，会递归的生成决策树，知道不能继续下去为止，
因此会产生过拟合，构造出复杂的决策树，所以需要剪枝降低过拟合。
将已生成的决策树进行简化的过程称为剪枝，
从已生成的树上剪掉一些子树和叶子节点，并将其父节点作为新的叶节点，从而简化模型。
可以
自上而下，对样本数据进行树形分类的过程。每个内部节点表示一个特征，叶节点表示一个类别。从顶部根节点开始，所有的样本聚在一起。经过根节点的划分，样本被分到不同的子节点，再根据子节点的特征进一步划分，直至所有样本被归到某一个类别（叶节点）中。
通过剪枝防止过拟合。
前剪枝是指在决策树生成的过程中，对每个节点在划分前先进行估计，若当前节点的划分不能带来决策树泛化性能提升，则停止划分，并将当前节点标记为叶子节点；此时可能存在不同类别的样本同时存于同个节点中，按照多数投票的原则判断节点所属类别
预剪枝对于何时停止决策树的生长：
（1）当树达到一定深度
（2）当到达当前节点的样本数量小于某个阈值
（3）计算每次分裂对测试集的准确度提升，小于某个阈值时停止
后剪枝则是先从训练集生成一棵完整的决策树，然后自底向上地对非叶子节点进行考察，若该节点对应的子树替换成叶子结点能带来泛化性能提升，则将该子树替换为叶子节点。
因为数值缩放不影响分裂点位置，对树模型的结构不造成影响。 按照特征值进行排序的，排序的顺序不变，那么所属的分支以及分裂点就不会有不同。而且，树模型是不能进行梯度下降的，因为构建树模型（回归树）寻找最优点时是通过寻找最优分裂点完成的，因此树模型是阶跃的，阶跃点是不可导的，并且求导没意义，也就不需要归一化。
对于线性模型，特征值差别很大时，运用梯度下降的时候，损失等高线是椭圆形，需要进行多次迭代才能到达最优点。 但是如果进行了归一化，那么等高线就是圆形的，促使SGD往原点迭代，从而导致需要的迭代次数较少。归一化之后加快了梯度下降求最优解的速度，并有可能提高精度。
决策树（概率模型）、随机森林（基学习器是决策树）、朴素贝叶斯（概率模型）不需要归一化
本文简要介绍了Python梯度提升决策树的方法示例，包括鸢尾花（Iris）数据集进行分类、房价预测（回归）、垃圾邮件分类、特征选择等示例。
1、搜索二叉树可能会出现一边树很长另一边树很短的极端情况，这样的话二叉树就会退化，这时我们就引出了AVL树这样的改良版。AVL树会控制两端树的高度差的绝对值小于1。（一般为右数高度减左树高度）2、AVL树会通过平衡因子来控制，因为是右-左，所以插入左边平衡因子--，右边则++3、基本结构：其中_parent是用来找上一节点进行链接控制AVL的行为：其中除了插入函数其余函数与搜索二叉树相似。4、插入
本篇将继续介绍决策的第三种算法：CART算法，它可以说是学习决策树的核心了。高级集成学习很多复杂框架都是基于CART的。下面将详细介绍CART算法的来龙去脉。CART生成算法CART剪枝算法CART算法小结决策树算法优缺点总结▍CART生成算法为什么叫CART算法呢？这还要从它的英文单词说起。CART是 "Classification and Regression Trees" 的缩写，意思是 "
说到决策树， 有几种类型分类树： 一种简单的分类算法，预测结果为离散的类型数据回归树：结果为数值类型CART（Classification And Regression Tree)：以上二者的结合一般来说分类树的特点：PROS: 计算复杂度比较低， 对中间值缺失的容忍度较高，对预测值的类型没有要求CONS: 在生成决策树的时候需要考虑停止条件以防止overfitting，而这个决定通常没有一个准确
决策树 通过层层的if判断条件，将数据集划分成规模越来越来小的子集，直至无需划分。 核心：划分依据、剪枝 一、理论基础 熵 H(A) 信息增益 I(D, A) = H(D) - H(D|A) 已知特征A后，不确定性减小的程度。 信息增益比 用于C4.5算法，解决以下两个问题： 同等概率下，ID3倾向 ...
决策树回归核心思想：相似的输入必会产生相似的输出。例如预测某人薪资：年龄：1-青年，2-中年，3-老年 学历：1-本科，2-硕士，3-博士 经历：1-出道，2-一般，3-老手，4-骨灰 性别：1-男性，2-女性年龄学历经历性别==>薪资1111==>6000(低)2131==>10000(中)3341==>50000(高)…………==>…1322==>?样本数
【机器学习】决策树与集成决策树ID3C4.5CART（分类回归树）分类树回归树防止过拟合决策树集成梯度提升树AdaBoostGBDT(即基于一般损失的分类模型）GBRT（即基于一般损失的回归模型）XGBoost损失函数推导特点缺点模型参数LightGBM(light gradient boosting machine)RandomForest 决策树决策树包括分支节点，叶节点，分支。分治节点表示
决策树的核心思想就是 if else，实现了 conditional aggregation，关键问题在于分裂的时候哪些特征在前哪些特征在后。从 ID3 开始使用熵（entropy）来作为决策选择的度量。决策树可以做分类，也可以做回归，是一种比较灵活的算法。主要包括 ID3、C4.5、CART，可以作为后续许多 ensemble 方法（例如 random forest 和 gradient boo
分类回归树（\(classification\ and\ regression\ tree,\ CART\)）既可用于分类也可用于回归。\(CART\)分类树、\(CART\) 回归树统称 \(CART\)\(CART\) 学习分三步：特征选择、决策树的生成、剪枝。\(CART\) 决策树是二叉树。对 \(CART\) 回归树用均方误差最小化准则，\(CART\) 分类树用基尼系数最小化（\(Gi
决策树(Decision Tree）是在已知各种情况发生概率的基础上，通过构成决策树来求取净现值的期望值大于等于零的概率，评价项目风险，判断其可行性的决策分析方法，是直观运用概率分析的一种图解法。由于这种决策分支画成图形很像一棵树的枝干，故称决策树。在机器学习中，决策树是一个预测模型，他代表的是对象属性与对象值之间的一种映射关系。Entropy（熵） = 系统的凌乱程度
机器学习1. 决策树1.1 原理1.2 sklearn实现 1. 决策树1.1 原理决策树(Decision Trees)是一种用于分类或回归任务的无参数学习方法，其基于树形结构从数据特征中学习对应决策规则(特征选择)用于分类或预测目标值假设对于博客是否需要及时阅读建立决策树模型，如图：叶子节点为最终的分类或预测结果非叶子节点为对应的决策规则(特征/属性)决策树的学习包含三个步骤：①特征选择；②
信号导致的问题不是任何信号我们都需要的，如果遇到我们不想处理的信号，我们怎么避免这个信号？ 1. 信号屏蔽intsigprocmask(int how,//操作方式SIG_BLOCK屏蔽信号
本篇文章继续学习李宏毅老师2025春季机器学习课程，学习内容是auto-encoder相关概念及运作流程和auto-encoder的优势，简单了解了de-nosing auto-encoder并与BERT进行对比。
“完了，用户又在骂了。” 电商技术部的小张盯着监控屏叹气 —— 刚上线的 “拍图找同款” 功能又崩了：用户上传一件连衣裙的照片，系统要 3 秒多才跳出相似商品，一半人没等加载完就划走了。更头疼的是，商品库刚突破 100 万件，再过两个月 618，数据量翻番，现有的搜索逻辑肯定扛不住。技术组长老周敲了敲他的工位：“别死磕暴力搜索了，试试 HNSW 算法。这东西就是为‘高维向量找邻居’而生的，咱们的商
你是否在处理复杂文本解析时遇到过性能瓶颈？是否因错误处理机制混乱而难以调试？作为Rust生态中最受欢迎的解析器组合子库，nom的架构演进历程为我们揭示了如何构建一个既灵活又高效的解析框架。本文将带你穿越nom的五个主要版本，剖析其核心架构的关键转变，从最初的宏驱动设计到现代函数式组合子模式，从简单错误码到类型化错误管理，为你的解析器开发提供宝贵经验。读完本文，你将能够：- 理解nom架构演进...