机器学习算法原理之决策树

news/2024/3/29 15:38:15/文章来源:https://blog.csdn.net/qq_43650934/article/details/129193921

文章目录

      • 决策树
      • 条件概率分布
      • 决策树学习
      • 特征选择
        • 信息增益
        • 信息增益比
      • 决策树的生成
        • ID3算法
        • C4.5算法
      • 剪枝
        • 预剪枝
        • 后剪枝
          • 降低错误剪枝(Reduce Error Pruning)
          • 悲观错误剪枝(Pessimistic Error Pruning)
          • 最小误差剪枝(Minimum Error Pruning)
          • 基于错误的剪枝(Error Based Pruning)
          • 代价-复杂度剪枝(Cost-Complexity Pruning)
      • CART算法
        • CART分类树
        • CART回归树
      • 总结归纳

决策树

已知:训练集:
T={(x1,y1),(x2,y2)⋅⋅⋅⋅,(xN,yN)}T=\{(x_{1},y_{1}),(x_{2},y_{2})\cdot\cdot\cdot\cdot,(x_{N},y_{N})\} T={(x1,y1),(x2,y2),(xN,yN)}
其中 xi=(xi(1),xi(2),⋯,xi(n))T,yi∈{1,2,⋯,K},i=1,2,⋯,N;x_{i}=(x_{i}^{(1)},x_{i}^{(2)},\cdots,x_{i}^{(n)})^{T},\;y_{i}\in\{1,2,\cdots,K\},\;i=1,2,\cdots,N;xi=(xi(1),xi(2),,xi(n))T,yi{1,2,,K},i=1,2,,N;

目的:构造决策树,并对实例正确分类

分类决策树模型是一种描述对实例进行分类树形结构

If-then:决策树是通过一系列规则对数据进行分类的过程。

步骤:

  • 构建根结点;
  • 选择最优特征,以此分割训练数据集;
  • 若子集被基本正确分类,构建叶结点,否则,继续选择新的最优特征;
  • 重复以上两步,直到所有训练数据子集被正确分类。

条件概率分布

  • 决策时:给定特征条件下类的 P(Y∣X)P(Y|X)P(YX)
  • 条件概率分布:特征空间的一个划分(Partition);
  • 划分:单元(Cell)或区域(Region)互不相交。

所有区域合在一起,就是整个特征空间,一个单元对应一条路径。

决策树的条件概率分布由各个单元给定条件下类的条件概率分布组成。

决策树学习

本质:从训练数据集中归纳出一组分类规则,与训练数据集不相矛盾

假设空间:由无穷多个条件概率模型组成

一棵好的决策树:与训练数据矛盾较小,同时具有很好的泛化能力

策略:最小化损失函数

特征选择:递归选择最优特征生成:对应特征空间的划分,直到所有训练子集被基本正确分类

剪枝:避免过拟合,具有更好的泛化能力

特征选择

信息增益

熵表示随机变量的不确实性
H(X)=−∑i=1npilog⁡piH(X)=-\sum_{i=1}^{n}p_{i}\log p_{i} H(X)=i=1npilogpi
或:
H(p)=−∑i=1npilog⁡piH(p)=-\sum_{i=1}^{n}p_{i}\log p_{i} H(p)=i=1npilogpi
随机变量的取值等概率分布的时候,相应的熵最大。
0≤H(p)≤log⁡n0\leq H(p)\leq\log n 0H(p)logn
条件熵:
H(Y∣X)=∑i=1npiH(Y∣X=xi)H(Y|X)=\sum_{i=1}^{n}p_{i}H(Y|X=x_{i}) H(YX)=i=1npiH(YX=xi)
当熵和条件熵中的概率由数据估计(特别是极大似然估计)得到时,则为经验熵(empirical entropy)和经验条件熵(empirical condition entropy)。

信息增益:得知特征 AAA 而使类 YYY 的信息的不确定性减少的程度。
g(D,A)=H(D)−H(D∣A)g(D,A)=H(D)-H(D|A) g(D,A)=H(D)H(DA)

信息增益的算法

设训练数据集为 DDD∣D∣|D|D 表示其样本容量,即样本个数。设有 KKK 个类 CkC_kCkk=1,2,⋯,Kk = 1, 2, \cdots, Kk=1,2,,K∣Ck∣|C_k|Ck 为属于类 CkC_kCk 的样本个数,∑k=1K∣Ck∣=∣D∣\sum_{k = 1}^{K} |C_k| = |D|k=1KCk=D 。设特征 AAAnnn 个不同的取值 {a1,a2,⋯,an}\{a_1, a_2, \cdots, a_n\}{a1,a2,,an} ,根据特征 AAA 的取值将 DDD 划分为 nnn 个子集 D1,D2,⋯,DnD_1, D_2, \cdots, D_nD1,D2,,Dn∣Di∣| D_i |DiDiD_iDi 的样本个数,∑i=1n∣Di∣=∣D∣\sum_{i = 1}^{n} |D_i| = |D|i=1nDi=D 。记子集 DiD_iDi 中属于类 CkC_kCk 的样本的集合为 DikD_{ik}Dik ,即 Dik=Di∩CkD_{ik} = D_i \cap C_kDik=DiCk∣Dik∣|D_{ik}|DikDikD_{ik}Dik 的样本个数。

输入:训练数据集 DDD 和特征 AAA

输出:特征 AAADDD 的信息增益 g(D,A)g(D, A)g(D,A)

  • 计算经验熵 H(D)H(D)H(D)
    H(D)=−∑k=1K∣Ck∣∣D∣log⁡2∣Ck∣∣D∣H(D)=-\sum_{k=1}^{K}\frac{|C_{k}|}{|D|}\log_{2}\frac{|C_{k}|}{|D|} H(D)=k=1KDCklog2DCk

  • 计算经验条件熵 H(D∣A)H(D|A)H(DA)

H(D∣A)=∑i=1n∣Di∣∣D∣H(Di)=−∑i=1n∣Di∣∣D∣∑k=1K∣Dik∣∣Di∣log⁡2∣Dik∣∣Di∣H(D|A)=\sum_{i=1}^{n}{\frac{|D_{i}|}{|D|}}H(D_{i})=-\sum_{i=1}^{n}{\frac{|D_{i}|}{|D|}}\sum_{k=1}^{K}{\frac{|D_{i k}|}{|D_i|}}\log_{2}{\frac{|D_{i k}|}{|D_i|}} H(DA)=i=1nDDiH(Di)=i=1nDDik=1KDiDiklog2DiDik

  • 计算信息增益:
    g(D,A)=H(D)−H(D∣A)g(D,A)=H(D)-H(D|A) g(D,A)=H(D)H(DA)

信息增益比

以信息增益作为划分训练数据集的特征,存在偏向于选择取值较多的特征的问题。使用信息增益比(information gain ratio)可以对这一问题进行校正。

特征 AAA 对训练数据集 DDD 的信息增益比 gR(D,A)g_R(D, A)gR(D,A) 定义为其信息增益 g(D,A)g(D, A)g(D,A) 与训练数据集 DDD 关于特征AAA 的值的熵 HA(D)H_A(D)HA(D) 之比,即
gR(D,A)=g(D,A)HA(D)g_R(D, A) = \frac{g(D,A)}{H_A(D)} gR(D,A)=HA(D)g(D,A)
其中,HA(D)=−∑i=1n∣Di∣∣D∣log⁡2∣Di∣∣D∣H_A(D) = -\sum_{i = 1}^n \frac{|D_i|}{|D|} \log_{2}{\frac{|D_i|}{|D|}}HA(D)=i=1nDDilog2DDinnn 是特征 AAA 取值的个数。

决策树的生成

ID3算法

输入:训练数据集 DDD 、特征集 AAA 、阈值 $\epsilon $

输出:决策树 TTT

  • 判断 TTT 是否需要选择特征生成决策树;
    • DDD 中所有实例属于同一类,则 TTT 为单结点树,记录实例类别 CkC_kCk ,以此作为该结点的类标记,并返回 TTT
    • DDD 中所有实例无任何特征(A=∅A = \emptysetA=),则 TTT 为单结点树,记录 DDD 中实例个数最多类别 CkC_kCk ,以此作为该结点的类标记,并返回 TTT
  • 否则,计算 AAA 中各特征的信息增益,并选择信息增益最大的特征 AgA_gAg
    • AgA_gAg信息增益小于 ϵ\epsilonϵ ,则 TTT 为单结点树,记录 DDD 中实例个数最多类别 CkC_kCk ,以此作为该结点的类标记,并返回 TTT
    • 否则,按照 AgA_gAg 的每个可能值 aia_iai ,将 DDD 分为若干非空子集 DiD_iDi ,将 DiD_iDi 中实例个数最多的类别作为标记,构建子结点,以结点和其子结点构成 TTT ,并返回 TTT
  • iii 个子结点,以 DiD_iDi 为训练集,A−AiA - A_iAAi 为特征集合,递归地调用以上步骤,得到子树 TiT_iTi 并返回。

C4.5算法

输入:训练数据集 DDD 、特征集 AAA 、阈值 $\epsilon $

输出:决策树 TTT

  • 判断 TTT 是否需要选择特征生成决策树;
    • DDD 中所有实例属于同一类,则 TTT 为单结点树,记录实例类别 CkC_kCk ,以此作为该结点的类标记,并返回 TTT
    • DDD 中所有实例无任何特征(A=∅A = \emptysetA=),则 TTT 为单结点树,记录 DDD 中实例个数最多类别 CkC_kCk ,以此作为该结点的类标记,并返回 TTT
  • 否则,计算 AAA 中各特征的信息增益比,并选择信息增益比最大的特征 AgA_gAg
    • AgA_gAg信息增益比小于 ϵ\epsilonϵ ,则 TTT 为单结点树,记录 DDD 中实例个数最多类别 CkC_kCk ,以此作为该结点的类标记,并返回 TTT
    • 否则,按照 AgA_gAg 的每个可能值 aia_iai ,将 DDD 分为若干非空子集 DiD_iDi ,将 DiD_iDi 中实例个数最多的类别作为标记,构建子结点,以结点和其子结点构成 TTT ,并返回 TTT
  • iii 个子结点,以 DiD_iDi 为训练集,A−AiA - A_iAAi 为特征集合,递归地调用以上步骤,得到子树 TiT_iTi 并返回。

剪枝

优秀的决策树:
在具有好的拟合和泛化能力的同时,

  • 深度小;
  • 叶结点少;
  • 深度小并且叶结点少。

误差:训练误差、测试误差

过拟合:训练误差低,测试误差高(模型结构过于复杂)

欠拟合:训练误差高,测试误差低(模型结构过于简单)

剪枝:处理决策树的过拟合问题

预剪枝:生成过程中,对每个结点划分前进行估计,若当前结点的划分不能提升泛化能力,则停止划分,记当前结点为叶结点;

后剪枝:生成一棵完整的决策树之后,自底而上地对内部结点考察,若此内部结点变为叶结点,可以提升泛化能力,则做此替换。

预剪枝

常用的预剪枝方法:

  • 限定决策树的深度
  • 设定一个阈值(阈值过大可能会导致决策树过于简单)
  • 设置某个指标(常用基于测试集上的误差率),比较结点划分前后的泛化能力

后剪枝

降低错误剪枝(Reduce Error Pruning)

原理:自下而上,使用测试集来剪枝。对每个结点,计算剪枝前和剪枝后的误判个数,若是剪枝有利于减少误判(包括相等的情况),则减掉该结点所在分枝。

错误率在验证集上计算出来

  • 计算复杂性是线性的
  • 操作简单,容易理解
  • 受测试集影响大,如果测试集比训练集小很多,会限制分类的精度,容易欠拟合。
悲观错误剪枝(Pessimistic Error Pruning)

原理:根据剪枝前后的错误率来决定是否剪枝。和降低错误剪枝(REP)不同之处在于,悲观错误剪枝(PEP)只需要训练集即可,不需要验证集,并且PEP是自上而下剪枝的。

LLL 为叶子结点的个数, LeafiLeaf_iLeafi 为第 iii 个叶子结点, LeafLeafLeaf 剪枝后的叶子结点, N(T)N(T)N(T) 为目标子树所包含的样本总个数。

  • 计算剪枝前目标子树每个叶子结点的误差,并进行连续修正

Error(Leafi)=error(Leafi)+0.5N(T)Error(Leaf_{i})= \frac{error(Leaf_{i})+0.5}{N(T)} Error(Leafi)=N(T)error(Leafi)+0.5

  • 计算剪枝前目标子树的修正误差:

Error(T)=∑i=1LError(Leafi)=∑i=1Lerror(Leafi)+0.5∗LN(T){Error}(T)=\sum_{i=1}^L {Error}\left( { Leaf }_i\right)=\frac{\sum_{i=1}^L {error}\left( { Leaf }_i\right)+0.5 * L}{N(T)} Error(T)=i=1LError(Leafi)=N(T)i=1Lerror(Leafi)+0.5L

  • 计算剪枝前目标子树误判个数的期望值:

E(T)=N(T)×Error(T)=∑i=1Lerror(Leafi)+0.5∗LE(T)=N(T) \times {Error}(T)=\sum_{i=1}^L {error}( { Leaf }_i)+0.5 * L E(T)=N(T)×Error(T)=i=1Lerror(Leafi)+0.5L

  • 计算剪枝前目标子树误判个数的标准差:

std(T)=N(T)×Error(T)×(1−Error(T))std(T)=\sqrt{N(T)\times Error(T) \times (1-Error(T))} std(T)=N(T)×Error(T)×(1Error(T))

  • 计算剪枝前误判上限(即悲观误差):

E(T)+std(T)E(T) + std(T) E(T)+std(T)

  • 计算剪枝后该结点的修正误差:

Error(Leaf)=error(Leaf)+0.5N(T)Error(Leaf)=\frac{error(Leaf)+0.5}{N(T)} Error(Leaf)=N(T)error(Leaf)+0.5

  • 计算剪枝后该结点误判个数的期望值:

E(Leaf)=error(Leaf)+0.5E(Leaf)=err o r(L e a f)+0.5 E(Leaf)=error(Leaf)+0.5

  • 比较剪枝前后的误判个数,如果满足以下不等式,则剪枝;否则,不剪枝。

E(Leaf)<E(T)+std(T)E(L e a f)\lt E(T)+s t d(T) E(Leaf)<E(T)+std(T)

最小误差剪枝(Minimum Error Pruning)

原理:根据剪枝前后的最小分类错误概率来决定是否剪枝。自下而上剪枝,只需要训练集即可。

Prk(T)Pr_k(T)Prk(T)TTT 属于 kkk 类别的先验概率, mmm 表示先验概率对后验概率的影响, wiw_iwi 为叶子结点在 TTT 中的权重。

  • 在结点 TTT 处,属于类别 kkk 的概率:

Pk(T)=nk(T)+Prk(T)×mN(T)+mm→0,Pk(T)→nk(T)N(T)m→∞,Pk(T)→Prk(T)\begin{align} &P_{k}(T)={\frac{n_{k}(T)+P r_{k}(T)\times m}{N(T)+m}}\\ &m \rightarrow 0, P_k(T) \rightarrow \frac{n_k(T)}{N(T)}\\ &m \rightarrow \infty, P_k(T) \rightarrow Pr_k(T) \end{align} Pk(T)=N(T)+mnk(T)+Prk(T)×mm0,Pk(T)N(T)nk(T)m,Pk(T)Prk(T)

  • 在结点 TTT 处,预测错误率:

Error(T)=min{1−Pk(T)}=min{N(T)−nk(T)+m(1−Prk(T))N(T)+m}Error(T)=min\{1{-}P_{k}(T)\}=min\left\{{\frac{{N}(T)-n_{k}(T)+m(1-Pr_{k}(T))}{{N}(T)+m}}\right\} Error(T)=min{1Pk(T)}=min{N(T)+mN(T)nk(T)+m(1Prk(T))}

  • 若先验概率确定,就是以 mmm 作为变量,求取 Error(T)Error(T)Error(T) 的最小值:

arg⁡min⁡mError(T)\arg\operatorname*{min}_{m}E rr o r(T) argmminError(T)

  • 在无任何假设的情况下,通常假设各类别等概率出现,先验概率: Prk(T)=1K{\cal P}r_{k}(T)=\frac{1}{K}Prk(T)=K1 ,为便于演示,此处取 m=1m = 1m=1

Error(T)=N(T)−nk(T)+K−1N(T)+K{{E rr o r}}(T)=\frac{N(T)-n_{k}(T)+K-1}{N(T)+K} Error(T)=N(T)+KN(T)nk(T)+K1

  • 步骤:

    • 计算剪枝前目标子树每个叶子结点的预测错误率:

    Error(Leafi)=N(Leafi)−nk(Leafi)+K−1N(Leafi)+KE rr o r(L e af_{i})=\frac{N(L e af_{i})-n_{k}(L e af_{i})+K-1}{N(L e af_{i})+K} Error(Leafi)=N(Leafi)+KN(Leafi)nk(Leafi)+K1

    • 计算剪枝前目标子树的预测错误率:

    Error(Leaf)=∑i=1LwiError(Leafi)=∑i=1LN(Leafi)N(T)Error(Leafi)E rr o r(L e a f)=\sum_{i=1}^{L}w_{i}E rr o r(L e a f_{i})=\sum_{i=1}^{L}\frac{N(L e a f_{i})}{N(T)}E rr o r(L e a f_{i}) Error(Leaf)=i=1LwiError(Leafi)=i=1LN(T)N(Leafi)Error(Leafi)

    • 计算剪枝后目标子树的预测错误率:

    Error(T)=N(T)−nk(T)+K−1N(T)+K{{E rr o r}}(T)=\frac{N(T)-n_{k}(T)+K-1}{N(T)+K} Error(T)=N(T)+KN(T)nk(T)+K1

    • 比较剪枝前后的预测错误率,如果满足以下不等式,则剪枝;否则,不剪枝。

    Error(T)<Error(Leaf)Error(T) < Error(Leaf) Error(T)<Error(Leaf)

基于错误的剪枝(Error Based Pruning)

原理:根据剪枝前后的误判个数来决定是否剪枝。自下而上剪枝,只需要训练集即可。

e(T)e(T)e(T) 为午盘个数,N(T)N(T)N(T) 为样本个数,α\alphaα 为上分位数, qαq_\alphaqα 为置信水平,常取 25% 。

  • 计算剪枝前目标子树每个叶子结点的误判率上界:

UCF(e(Leafi),N(Leafi))=e(Leafi)+0.5+qα22+qα(e(Leafi)+0.5)(N(Leafi)−e(Leafi)−0.5)N(Leafi)+qα24N(Leafi)+qα2U_{C F}\left(e\left( { Leaf }_i\right), N\left( { Leaf }_i\right)\right)=\frac{e\left( { Leaf }_i\right)+0.5+\frac{q_\alpha^2}{2}+q_\alpha \sqrt{\frac{\left(e\left( { Leaf }_i\right)+0.5\right)\left(N\left( { Leaf }_i\right)-e\left( { Leaf }_i\right)-0.5\right)}{N\left( { Leaf }_i\right)}+\frac{q_\alpha^2}{4}}}{N\left( { Leaf }_i\right)+q_\alpha^2} UCF(e(Leafi),N(Leafi))=N(Leafi)+qα2e(Leafi)+0.5+2qα2+qαN(Leafi)(e(Leafi)+0.5)(N(Leafi)e(Leafi)0.5)+4qα2

  • 计算剪枝前目标子树的误判个数上界:

E(Leaf)=∑i=1LN(Leafi)UCF(e(Leafi),N(Leafi))E( { Leaf })=\sum_{i=1}^L N\left( { Leaf }_i\right) U_{C F}\left(e\left( { Leaf }_i\right), N\left( { Leaf }_i\right)\right) E(Leaf)=i=1LN(Leafi)UCF(e(Leafi),N(Leafi))

  • 计算剪枝后目标子树的误判率上界:

UCF(e(T),N(T))=e(T)+0.5+qα22+qα(e(T)+0.5)(N(T)−e(T)−0.5)N(T)+qα24N(T)+qα2U_{C F}\left(e\left( { T }\right), N\left( { T }\right)\right)=\frac{e\left( { T }\right)+0.5+\frac{q_\alpha^2}{2}+q_\alpha \sqrt{\frac{\left(e\left( { T }\right)+0.5\right)\left(N\left( { T }\right)-e\left( { T }\right)-0.5\right)}{N\left( { T }\right)}+\frac{q_\alpha^2}{4}}}{N\left( { T }\right)+q_\alpha^2} UCF(e(T),N(T))=N(T)+qα2e(T)+0.5+2qα2+qαN(T)(e(T)+0.5)(N(T)e(T)0.5)+4qα2

  • 计算剪枝后目标子树的误判个数上界:

E(T)=N(T)UCF(e(T),N(T))E(T)=N(T)U_{C F}(e(T),\,\,N(T)) E(T)=N(T)UCF(e(T),N(T))

  • 比较剪枝前后的误判个数上界,如果满足以下不等式,则剪枝;否则,不剪枝。

E(T)<E(Leaf)E(T) < E(Leaf) E(T)<E(Leaf)

代价-复杂度剪枝(Cost-Complexity Pruning)

原理:根据剪枝前后的损失函数来决定是否剪枝。

C(T)C(T)C(T)TTT 在训练集中的预测误差, ∣T∣|T|T 为树 TTT 的叶结点个数,反映 TTT 的复杂度(考验泛化能力), ttt 是树 TTT 的叶结点,该叶结点有 NtN_tNt 个样本点,其中 kkk 类的样本点有 NtkN_{tk}Ntk 个, Ht(T)H_t(T)Ht(T) 为叶结点 ttt 上的经验熵 , α≥0\alpha \ge 0α0 为惩罚参数。

  • 损失函数:

Cα=C(T)+α∣T∣C_\alpha = C(T) + \alpha|T| Cα=C(T)+αT

​ 其中, C(T)=∑t=1∣T∣NtHt(T)=−∑t=1∣T∣∑k=1KNtklog⁡NtkNtC(T)=\sum_{t=1}^{|T|} N_t H_t(T)=-\sum_{t=1}^{|T|} \sum_{k=1}^K N_{t k} \log \frac{N_{t k}}{N_t}C(T)=t=1TNtHt(T)=t=1Tk=1KNtklogNtNtk

  • 正则化:

min⁡f∈F1N∑i=1NL(yi,f(xi))+λJ(f)\operatorname*{min}_{f\in\mathcal{F}}\frac{1}{N}\sum_{i=1}^{N}L(y_{i},\,f(x_{i}))+\lambda J(f) fFminN1i=1NL(yi,f(xi))+λJ(f)

  • 剪枝前的决策树记做下 TAT_ATA ,计算每个叶子结点 ttt 的经验熵(若使用基尼系数,则为 CART 算法):

Ht=−∑k=1KNtkNtlog⁡NtkNtH_t=-\sum_{k=1}^K \frac{N_{t k}}{N_t} \log \frac{N_{t k}}{N_t} Ht=k=1KNtNtklogNtNtk

  • 剪枝前决策树的损失函数为:

Cα(TA)=C(TA)+α∣TA∣C_{\alpha}(\,T_{A})=\,C(\,T_{A})+\alpha |T_{A}| Cα(TA)=C(TA)+αTA

  • 剪枝后的决策树记做 TBT_BTB ,损失函数为:

Cα(TB)=C(TB)+α∣TB∣C_\alpha\left(T_B\right)=C\left(T_B\right)+\alpha\left|T_B\right| Cα(TB)=C(TB)+αTB

  • 比较剪枝前后的损失函数,如果满足以下不等式,则剪枝;否则,不剪枝。

Cα(TB)≤Cα(TA)C_\alpha\left(T_B\right) \leq C_\alpha\left(T_A\right) Cα(TB)Cα(TA)

CART算法

假设现在有 KKK 个类,样本点属于第 kkk 个类的概率为 pkp_kpk ,则概率分布的基尼指数为:
Gini⁡(p)=∑k=1Kpk(1−pk)=1−∑k=1Kpk2\operatorname{Gini}(p)=\sum_{k=1}^K p_k\left(1-p_k\right)=1-\sum_{k=1}^K p_k^2 Gini(p)=k=1Kpk(1pk)=1k=1Kpk2
二分类:
Gini⁡(p)=2p(1−p)\operatorname {Gini}(p) = 2p(1-p) Gini(p)=2p(1p)
样本集 DDD 的基尼系数:
Gini⁡(D)=1−∑k=1K(∣Ck∣∣D∣)2\operatorname{Gini}(D)=1-\sum_{k=1}^K\left(\frac{\left|C_k\right|}{|D|}\right)^2 Gini(D)=1k=1K(DCk)2
特征 AAA 条件下,样本集 DDD 的基尼指数为:
Gini⁡(D,A)=∣D1∣∣D∣Gini⁡(D1)+∣D2∣∣D∣Gini⁡(D2)\operatorname{Gini}(D, A)=\frac{\left|D_1\right|}{|D|} \operatorname{Gini}\left(D_1\right)+\frac{\left|D_2\right|}{|D|} \operatorname{Gini}\left(D_2\right) Gini(D,A)=DD1Gini(D1)+DD2Gini(D2)

CART分类树

输入:训练数据集 DDD 、特征集 AAA 、阈值 ϵ\epsilonϵ

输出:CART决策树 TTT

  • 从根节点出发,进行操作,构建二叉树;
  • 结点处的训练数据集为 DDD ,计算现有特征对该数据集的基尼指数,并选择最优特征。
    • 在特征 AgA_gAg 下,对其可能取的每个值 aga_gag ,根据样本点对 Ag=agA_g = a_gAg=ag 的测试为“是”或“否”,将 DDD 分割成 D1D_1D1D2D_2D2 两部分,计算 Ag=agA_g = a_gAg=ag 时的基尼指数。
    • 选择基尼指数最小的那个值作为该特征下的最优切分点。
    • 计算每个特征下的最优切分点,并比较在最优切分下的每个特征的基尼指数,选择基尼指数最小的那个特征,即最优特征。
  • 根据最优特征与最优切分点,从现结点生成两个子结点,将训练数据集依特征分配到两个子结点中去。
  • 分别对两个子结点递归地调用上述步骤,直至满足停止条件(比如结点中的样本个数小于预定阈值,或样本集的基尼指数小于预定阈值(样本基本属于同一类),或者没有更多特征),即生成 CART 决策树。

CART回归树

假设将输入空间划分为 MMM 个单元 R1,R2,⋯,RmR_1, R_2, \cdots, R_mR1,R2,,Rm ,并在每个单元 RmR_mRm 上有一个固定的输出值 CmC_mCm 。回归树模型可表示为:
f(x)=∑m=1McmI(x∈Rm)f(x)=\sum_{m=1}^M c_m I\left(x \in R_m\right) f(x)=m=1McmI(xRm)
平方误差:
∑xi∈Rm(yi−f(xi))2\sum_{x_i \in R_m}\left(y_i-f\left(x_i\right)\right)^2 xiRm(yif(xi))2
最优输出:
c^m=average⁡(yi∣xi∈Rm)\hat{c}_m=\operatorname{average}\left(y_i \mid x_i \in R_m\right) c^m=average(yixiRm)
选择第 x(j)x^{(j)}x(j) 个变量和取值 sss ,分别作为切分变量和切分点,并定义两个区域:
R1(j,s)={x∣x(j)⩽s}R2(j,s)={x∣x(j)>s}R_1(j, s)=\left\{x \mid x^{(j)} \leqslant s\right\} \quad R_2(j, s)=\left\{x \mid x^{(j)}>s\right\} R1(j,s)={xx(j)s}R2(j,s)={xx(j)>s}
寻找最优切分变量 jjj 和最优切分点 sss
min⁡j,s[min⁡c1∑xi∈R1(j,s)(yi−c1)2+min⁡c2∑xi∈R2(j,s)(yi−c2)2]\min _{j, s}\left[\min _{c_1} \sum_{x_i \in R_1(j, s)}\left(y_i-c_1\right)^2+\min _{c_2} \sum_{x_i \in R_2(j, s)}\left(y_i-c_2\right)^2\right] j,sminc1minxiR1(j,s)(yic1)2+c2minxiR2(j,s)(yic2)2
对固定输入变量 jjj 可以找到最优切分点 sss
c^1=ave⁡(yi∣xi∈R1(j,s))c^2=ave⁡(yi∣xi∈R2(j,s))\begin{align} \hat{c}_1=\operatorname{ave}\left(y_i \mid x_i \in R_1(j, s)\right) \\ \hat{c}_2=\operatorname{ave}\left(y_i \mid x_i \in R_2(j, s)\right) \end{align} c^1=ave(yixiR1(j,s))c^2=ave(yixiR2(j,s))

输入:训练数据集 DDD ,停止条件

输出:CART 决策树 TTT

  • 从根节点出发,进行操作,构建二叉树

  • 结点处的训练数据集为 DDD ,计算变量的最优切分点,并选择最优变量。
    min⁡j,s[min⁡c1∑xi∈R1(j,s)(yi−c1)2+min⁡c2∑xi∈R2(j,s)(yi−c2)2]\min _{j, s}\left[\min _{c_1} \sum_{x_i \in R_1(j, s)}\left(y_i-c_1\right)^2+\min _{c_2} \sum_{x_i \in R_2(j, s)}\left(y_i-c_2\right)^2\right] j,sminc1minxiR1(j,s)(yic1)2+c2minxiR2(j,s)(yic2)2

    • 在第 jjj 变量下,对其可能取的每个值 sss ,根据样本点分割成 R1R_1R1R2R_2R2 两部分,计算切分点为 sss 时的平方误差

    • 选择平方误差最小的那个值作为该变量下的最优切分点。

    • 计算每个变量下的最优切分点,并比较在最优切分下的每个变量的平方误差,选择平方误差最小的那个变量,即最优变量。

  • 根据最优特征与最优切分点(j,s)(j, s)(j,s),从现结点生成两个子结点,将训练数据集依变量配到两个子结点中去,得到相应的输出值。

R1(j,s)={x∣x(j)⩽s},R2(j,s)={x∣x(j)>s}R_1(j, s)=\left\{x \mid x^{(j)} \leqslant s\right\}, \quad R_2(j, s)=\left\{x \mid x^{(j)}>s\right\} R1(j,s)={xx(j)s},R2(j,s)={xx(j)>s}

c^m=1Nm∑xi∈Rm(j,s)yi,x∈Rm,m=1,2\hat{c}_m=\frac{1}{N_m} \sum_{x_i \in R_m(j, s)} y_i, \quad x \in R_m, \quad m=1,2 c^m=Nm1xiRm(j,s)yi,xRm,m=1,2

  • 继续对两个子区域调用上述步骤,直至满足停止条件,即生成 CART 决策树。

f(x)=∑m=1McmI(x∈Rm)f(x)=\sum_{m=1}^M c_m I\left(x \in R_m\right) f(x)=m=1McmI(xRm)

总结归纳

  • 决策树不一定是二叉树,可能是多叉树,即:决策树可以做多分类

  • 决策树的内部结点表示一个特征或属性,叶结点表示一个

  • 决策树符合 if-then 规则,互斥且完备,即:每一个实例都被一条路径或一条规则所覆盖,而且只被一条路径或一条规则所覆盖。

  • 决策树还可以看成是由给定条件下类的条件概率分布组成的,即在上一个特征发生的条件下求取下一个特征发生的概率。

  • 任何一棵多叉树都可以表示成二叉树的形式,这也是为什么在悲观错误剪枝(Pessimistic Error Pruning)和基于错误的剪枝(Error Based Pruning)中具有二项分布的身影 。

  • 随机变量的取值等概率分布的时候,相应的熵最大。通俗理解为:等概率分布时,随机变量取到每一个值的概率都相同,此时随机变量的不确定性最大。

  • 决策树还表示给定特征条件下类的概率分布,即在上一个特征发生的前提下寻找下一个特征发生的概率。

g(D,A)=H(D)−H(D∣A)g(D,A)=H(D)-H(D|A) g(D,A)=H(D)H(DA)

​ 要使 g(D,A)g(D,A)g(D,A) 变小,需使 H(D∣A)H(D|A)H(DA) 变大,表示为:已知特征 AAA 的条件下对集合 DDD 的分类效果好。

  • 决策树生成过程中,若特征 AgA_gAg 只有一种可能值,此时 H(D)H(D)H(D)H(D∣A)H(D|A)H(DA) 均为 0 ,信息增益也为 0 ,必小于 ϵ\epsilonϵ ,应生成叶结点。

  • 决策树生成时,当所有特征的信息增益均小于 ϵ\epsilonϵ 时,决策树完成构建。

  • 以信息增益作为划分训练数据集的特征,存在偏向于选择取值较多的特征的问题。使用信息增益比(information gain ratio)可以对这一问题进行校正。

  • ID3算法和C4.5算法,只有划分依据不同,ID3算法依据信息增益划分,C4.5算法依据信息增益比划分。

  • C4.5算法较ID3算法,它可以处理连续型的数据,但不适用于大型数据。

  • 预剪枝是自上而下的过程,后剪枝是自下而上的过程。其中悲观错误剪枝(Pessimistic Error Pruning)较为特殊,它归属于后剪枝,但却是自上而下剪枝。

  • 连续性修正:

    • 将伯努利分布 B(1,p)B(1,p)B(1,p) 重复 nnn 次,就是二项分布 B(n,p)B(n,p)B(n,p)

    • 棣莫弗-拉普拉斯中心极限定理:

      ​ 设随机变量 Yn∼B(n,p)(0<p<1,b≥1)Y_n \sim B(n,p)(0<p<1, b \ge 1)YnB(n,p)(0<p<1,b1)

    lim⁡n→∞P{a<xn−npnp(1−p)≤b}=∫ab12πe−t22dt\lim _{n \rightarrow \infty} P\left\{a<\frac{x_n-n p}{\sqrt{n p(1-p)}} \leq b\right\}=\int_a^b \frac{1}{\sqrt{2 \pi}} e^{-\frac{t^2}{2}} d t nlimP{a<np(1p)xnnpb}=ab2π1e2t2dt

    ​ 其中,12πe−t22\frac{1}{\sqrt{2 \pi}} e^{-\frac{t^2}{2}}2π1e2t2 就是正态分布的概率密度函数。

    ​ 该定理表明:正态分布是二项分布的极限分布

    ​ 即:n→∞,B(n,p)→B(np,np(1−p))n \rightarrow \infty, B(n,p) \rightarrow B(np, np(1-p))n,B(n,p)B(np,np(1p))

    • 二项分布为离散型随机变量,分布函数是阶梯状;正态分布为连续性随机变量,而正态分布的曲线穿过了每个阶梯的中心点。在 [a,a+0.5)[a, a+0.5)[a,a+0.5) 区间内,二项分布的分布函数大于正态分布;在 (a+0.5,a+1](a+0.5, a+1](a+0.5,a+1] 区间内,正态分布的分布函数大于二项分布。

    • 若直接用正态分布求概率,结果偏大,体现在概率直方图中:

      • 当求取坐标为 (a,b)(a, b)(a,b) 时,二项分布会求取 [a+1,b−1][a+1,b-1][a+1,b1] 的面积,正态分布则会包含一部分 (a−1,a),(b,b+1)(a - 1, a),(b, b+1)(a1,a),(b,b+1) 的面积。
    • 当二项分布的期望 npnpnp 大到可以用正态分布近似的时候,应对正态分布做连续性修正,视概率求取边界对积分边界进行 ±0.5\pm0.5±0.5 处理(根据四舍五入计数法,经过0.50.50.5 修正后的边界内的整数个数等于二项分布区间内的整数个数)。

      对于 X∼B(n,p)X \sim B(n,p)XB(n,p)

      若求取概率 P(a<X<b)P(a<X<b)P(a<X<b) ,有:
      ∑k=a+1b−1Cnk1pn≈∫a+0.5b−0.512πe−t22dt\sum_{k=a+1}^{b-1}C_{n}^k \frac{1}{p^{n}} \approx \int_{a+0.5}^{b-0.5} \frac{1}{\sqrt{2 \pi}} e^{-\frac{t^2}{2}}dt k=a+1b1Cnkpn1a+0.5b0.52π1e2t2dt
      若求取概率 P(a≤X≤b)P(a \leq X \leq b)P(aXb) ,有:
      ∑k=abCnk1pn≈∫a−0.5b+0.512πe−t22dt\sum_{k=a}^{b}{C_{n}^{k}{\frac{1}{p^{n}}} \approx } \int_{a-0.5}^{b+0.5} \frac{1}{\sqrt{2 \pi}} e^{-\frac{t^2}{2}}dt k=abCnkpn1a0.5b+0.52π1e2t2dt
      对于 (a,b)(a,b)(a,b) ,连续性修正后的正态分布区间 (a+0.5,b−0.5)(a+0.5,b-0.5)(a+0.5,b0.5) 内取整即为二项分布在区间 (a,b)(a,b)(a,b) 内取整。

      对于 [a,b][a,b][a,b] ,连续性修正后的正态分布区间 (a−0.5,b+0.5)(a-0.5, b+0.5)(a0.5,b+0.5) 内取整二项分布在区间 [a,b][a,b][a,b] 内取整。

  • 悲观错误剪枝(Pessimistic Error Pruning)中,E(T)=N(T)×Error(T)E(T)=N(T) \times {Error}(T)E(T)=N(T)×Error(T) 的实质就是二项分布的期望 E(X)=npE(X) = npE(X)=npstd(T)=N(T)×Error(T)×(1−Error(T))std(T)=\sqrt{N(T)\times Error(T) \times (1-Error(T))}std(T)=N(T)×Error(T)×(1Error(T)) 的实质就是二项分布的标准差 D(X)=np(1−p)\sqrt{D(X)} = \sqrt{np(1-p)}D(X)=np(1p)

  • 悲观错误剪枝(Pessimistic Error Pruning)中,剪枝后只有一个叶结点,没有标准差和方差。

  • 最小误差剪枝(Minimum Error Pruning)引入了贝叶斯思维,加入了先验概率影响因子。

  • 关于最小误差剪枝(Minimum Error Pruning)中的 mmm ,应该计算得到而不是直接给出。应在已知先验概率的情况下,通过迭代或网格搜索等方法确定 min⁡Error(T)\min Error(T)minError(T),此时才符合标题中的“最小误差”。当类别总数较大时,先验概率至关重要,更不应该随意设定 mmm 的值。

  • α\alphaα 分位数:P(X≥xα)=αP(X \ge x_\alpha) = \alphaP(Xxα)=α ; 下 α\alphaα 分位数:P(X≤xα)=αP(X \le x_\alpha) = \alphaP(Xxα)=α

  • 对于基于错误的剪枝(Error Based Pruning)中误判率上界的分析:

    • 该结点的误判率(连续修正):

    error(T)=e(T)+0.5N(T)error(T) = \frac{e(T) +0.5}{N(T)} error(T)=N(T)e(T)+0.5

    • 二项分布的标准差 std(T)=np(1−p)std(T) = np(1-p)std(T)=np(1p)

    N(T)⋅e(T)+0.5N(T)⋅(1−e(T)+0.5N(T))=(e(T)+0.5)(N(T)−e(T)−0.5)N(T)N(T) \cdot \frac{e(T) + 0.5}{N(T)} \cdot (1 - \frac{e(T) + 0.5}{N(T)})= \sqrt{\frac{\left(e\left( { T }\right)+0.5\right)\left(N\left( { T }\right)-e\left( { T }\right)-0.5\right)}{N\left( { T }\right)}} N(T)N(T)e(T)+0.5(1N(T)e(T)+0.5)=N(T)(e(T)+0.5)(N(T)e(T)0.5)

    • 加入置信水平的标准差:

(e(T)+0.5)(N(T)−e(T)−0.5)N(T)+qα24\sqrt{\frac{\left(e\left( { T }\right)+0.5\right)\left(N\left( { T }\right)-e\left( { T }\right)-0.5\right)}{N\left( { T }\right)} + \frac{{q_\alpha}^2}{4}} N(T)(e(T)+0.5)(N(T)e(T)0.5)+4qα2

  • 熵和基尼系数类似,均表示随机变量的不确定性。
  • CART 假设决策树是二叉树,内部结点特征的取值为“是”和“否”,左分支为“是”,右分支为“否”。
  • CART 决策树既能做分类也能做回归。

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

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

相关文章

利用InceptionV3实现图像分类

最近在做一个机审的项目&#xff0c;初步希望实现图像的四分类&#xff0c;即&#xff1a;正常&#xff08;neutral&#xff09;、涉政&#xff08;political&#xff09;、涉黄&#xff08;porn&#xff09;、涉恐&#xff08;terrorism&#xff09;。有朋友给推荐了个github上…

机器学习笔记之近似推断(一)从深度学习角度认识推断

机器学习笔记之近似推断——从深度学习角度认识推断引言推断——基本介绍精确推断难的原因虽然能够表示&#xff0c;但计算代价太大无法直接表示引言 本节是一篇关于推断总结的博客&#xff0c;侧重点在于深度学习模型中的推断任务。 推断——基本介绍 推断(Inference\text{…

Python中实现将内容进行base64编码与解码

一、需求说明需要使用Python实现将内容转为base64编码&#xff0c;解码&#xff0c;方便后续的数据操作。二、base64简介Base64是一种二进制到文本的编码方式【是一种基于 64 个可打印字符来表示二进制数据的表示方法&#xff08;由于 2^664&#xff0c;所以每 6 个比特为一个单…

国产音质好的蓝牙耳机有哪些?国产音质最好的耳机排行

随着时间的推移&#xff0c;真无线蓝牙耳机逐渐占据耳机市场的份额&#xff0c;成为人们日常生活中必备的数码产品之一。蓝牙耳机品牌也多得数不胜数&#xff0c;哪些国产蓝牙耳机音质好&#xff1f;下面&#xff0c;我们从音质出来&#xff0c;来给大家介绍几款国产蓝牙耳机&a…

硬件系统工程师宝典(11)-----去耦电容布局“有讲究”

各位同学大家好&#xff0c;欢迎继续做客电子工程学习圈&#xff0c;今天我们继续来讲这本书&#xff0c;硬件系统工程师宝典。 上篇我们说到在电源完整性分析的目标就是要做到电源的干净、稳定和快速响应&#xff0c;以及针对不同噪声处理的实现方法。今天我们来看看去耦电容…

父传子与子传父步骤

父传子&#xff1a; 问题&#xff1a;父页面中引入子组件 把想要传给子页面的值用在子组件中用 &#xff1a;值“值” (用同一个值好区分)来绑定。 在子页面中用props接收 子组件不能改变父组件传过来的值。&#xff08;传多个页面的时候是&#xff0c;比如父传孙的时候我会…

【2023】华为OD机试真题Java-题目0221-AI处理器组合

AI处理器组合 题目描述 某公司研发了一款高性能AI处理器。每台物理设备具备8颗AI处理器,编号分别为0、1、2、3、4、5、6、7。编号0-3的处理器处于同一个链路中,编号4-7的处理器处于另外一个链路中,不通链路中的处理器不能通信,如下图所示。现给定服务器可用的处理器编号数…

STM32---备份寄存器BKP和 FLASH学习使用

BKP库函数 学习BKP&#xff0c;首先就是知道BKP每一个函数的作用然后如何使用即可 使用备份域的作用只需要操作上面的两个函数即可&#xff0c;其余的都是它的其他功能 BKP简介 备份寄存器是42个16位的寄存器&#xff0c;可用来存储84个字节的用户应用程序数据。他们处在备份…

如何高效管理自己的时间,可以从这几个方向着手

如果你是上班族&#xff0c;天选打工人&#xff0c;你的绝大多数时间都属于老板&#xff0c;能够自己支配的时间其实并不多&#xff0c;所以你可能察觉不到时间管理的重要性。但如果你是自由职业者或者创业者&#xff0c;想要做出点成绩&#xff0c;那你就需要做好时间管理&…

2. Dart 开发工具环境配置

很多编辑器都可以用来开发dart&#xff0c;所以大家可以选择自己喜欢的编辑器去进行开发。我还是比较喜欢vs code如果你不用vs code来开发dart的话&#xff0c;这篇文章可以直接跳过。如果想要在vs code里有dart的语法提示&#xff0c;我们需要安装相关的插件如图点开插件输入d…

预编译(回顾)

浏览器运行机制变量提升机制私有变量提升步骤全局对象 GO 和全局变量对象 VO的区别带var和不带var的区别系统输出顺序变量提升在条件判断下的处理防止函数的变量提升 浏览器运行机制 为了能够让代码执行&#xff0c;浏览器首先会形成一个执行环境栈 ECStack(Execution Contex…

TCP协议和TCP连接

TCP协议和TCP连接一、TCP协议的简介二、TCP连接的简介1、TCP连接的建立&#xff08;TCP三次握手&#xff09;2、TCP连接的断开&#xff08;TCP四次挥手&#xff09;一、TCP协议的简介 TCP&#xff08;Transmission Control Protocol&#xff09;传输控制协议是一种面向连接的、…

java 接口 详解

目录 一、概述 1.介绍 : 2.定义 : 二、特点 1.接口成员变量的特点 : 2.接口成员方法的特点 : 3.接口构造方法的特点 : 4.接口创建对象的特点 : 5.接口继承关系的特点 : 三、应用 : 1.情景 : 2.多态 : ①多态的传递性 : ②关于接口的多态参数和多态…

股票量化交易SQL特征工程入门

虽然现在各种量化教程和自助平台铺天盖地&#xff0c;但是对于新人来说入门最重要的事情就是挖掘特征。 对于传统的学习路径第一步是学习Python或者某一门编程语言&#xff0c;虽说Python入门容易上手快&#xff0c;但是要在实际应用中对股票数据进行分析&#xff0c;并挖掘有…

2023/2/24 图数据库Neo4j的理解与应用

1 什么是图数据库&#xff08;graph database&#xff09; 十大应用案例&#xff1a;https://go.neo4j.com/rs/710-RRC-335/images/Neo4j-Top-Use-Cases-ZH.pdf “大数据”每年都在增长&#xff0c;但如今的企业领导者不仅需要管理更大规模的数据&#xff0c;还迫切需要从现有…

8000+字,就说一个字Volatile

简介 volatile是Java提供的一种轻量级的同步机制。Java 语言包含两种内在的同步机制&#xff1a;同步块&#xff08;或方法&#xff09;和 volatile 变量&#xff0c;相比于synchronized&#xff08;synchronized通常称为重量级锁&#xff09;&#xff0c;volatile更轻量级&…

【大数据】记一次hadoop集群missing block问题排查和数据恢复

问题描述 集群环境总共有2个NN节点&#xff0c;3个JN节点&#xff0c;40个DN节点&#xff0c;基于hadoop-3.3.1的版本。集群采用的双副本&#xff0c;未使用ec纠删码。 问题如下&#xff1a; bin/hdfs fsck -list-corruptfileblocks / The list of corrupt files under path…

汽车零部件行业mes系统具体功能介绍

众所周知&#xff0c;汽车零部件的组装是汽车制造的关键环节&#xff0c;而汽车零部件江湖变革以精益为终极目标。即汽车零部件制造企业转型升级向精益生产和精益管理方向前进&#xff0c;而车间信息化管理是精益化生产的基础。 汽车零部件行业现状 随着全球汽车产业不断升级…

蓝牙标签操作指南

一、APP安装指南 1.APP权限问题 电子标签APP安装之后&#xff0c;会提示一些权限的申请&#xff0c;点击允许。否则某些会影响APP的正常运行。安装后&#xff0c;搜索不到蓝牙标签&#xff0c;可以关闭App&#xff0c;重新打开。 2.手机功能 运行APP时候&#xff0c;需要打开…

Linux基本介绍与常用操作指令

参考链接&#xff1a; Linux面试必备20个常用命令_无 羡ღ的博客-CSDN博客_linux常用命令 1. Linux简介 Linux是一个支持多用户、多任务、多线程和多CPU的操作系统&#xff0c;特点是免费、稳定、高效&#xff0c; 一般运行在大型服务器上。 1.1 常用目录简介 /&#xff1a;根目…