精华内容
下载资源
问答
  • 常用的决策树算法
    千次阅读
    2020-08-11 18:32:35

    用途&组成

    决策树是一个监督学习模型,可用于分类和回归,它是一个由内节点和叶节点构成的树型结构。每个内节点对应了一个关于某种特征的测试(Decision),通过测试,可以把样本分开(split)。最后位于同一叶子节点的样本被分为某一类。

    • root:
    • node:对某一特征的条件测试, i f ( f e a t u r e i ⋅ ⋅ ⋅ ⋅ ) if(feature_i····) if(featurei)
    • leaf:最终的决策结果。

    构造算法

    决策树的构造有三个重要的步骤:

    1. 特征选择
    2. 决策树生成
    3. 剪枝
      接下来按照这三个步骤一一阐述。

    1. 特征选择

    构造决策树时,一个首先需要考虑的问题是选择哪一个特征来作为划分样本的依据。为了比较不同的特征间的优劣,需要设计一个metric来衡量它们的performance。常用到的metric有三种:

    • 信息增益
    • 信息增益比
    • Gini指数(纯净度)

    metric

    ID3:信息增益

    定义
    • 熵(Entropy):事物的不确定性,越不确定,熵越大。一个随机变量X的熵的计算如下:
      E ( X ) = ∑ X = 1 n −   p i   l o g ( p i ) E(X)=\sum_{X=1}^{n}-\ p_i\ log(p_i) E(X)=X=1n pi log(pi)
      X = 1... n : X=1...n: X=1...n:随机变量X有n种不同的取值
      p i : p_i: pi每种取值对应的可能性为 p i p_i pi
      随机变量均匀分布时,熵达到最大。即均匀分布的不确定性最强。而n类平均分布的熵会小于n+1类平均分布的熵。
      在这里插入图片描述

    • 联合熵:随机变量X与Y的联合熵
      H ( X , Y ) = ∑ x i ∈ X ∑ y j ∈ Y −   p ( x i , y j )   l o g ( p ( x i , y j ) ) = ∑ x i ∈ X ∑ y j ∈ Y −   p ( x i , y j )   l o g ( p ( x i ∣ y j ) p ( y j ) ) = − ∑ x i ∈ X ∑ y j ∈ Y   p ( x i , y j )   l o g ( p ( y j ) ) − ∑ x i ∈ X ∑ y j ∈ Y   p ( x i , y j )   l o g ( p ( x i ∣ y j ) ) = − ∑ y j ∈ Y ∑ x i ∈ X   p ( x i , y j )   l o g ( p ( y j ) ) − ∑ x i ∈ X ∑ y j ∈ Y   p ( x i , y j )   l o g ( p ( x i ∣ y j ) ) = − ∑ y j ∈ Y   p ( y j )   l o g ( p ( y j ) ) − ∑ x i ∈ X ∑ y j ∈ Y   p ( x i , y j )   l o g ( p ( x i ∣ y j ) ) = H ( Y ) + H ( X ∣ Y ) = H ( X ) + H ( Y ∣ X ) \begin{aligned} H(X,Y)&=\sum_{x_i\in X}\sum_{y_j\in Y}-\ p(x_i,y_j)\ log(p(x_i,y_j))\\ &=\sum_{x_i\in X}\sum_{y_j\in Y}-\ p(x_i,y_j)\ log(p(x_i|y_j)p(y_j))\\ \\ &=-\sum_{x_i\in X}\sum_{y_j\in Y}\ p(x_i,y_j)\ log(p(y_j))-\sum_{x_i\in X}\sum_{y_j\in Y}\ p(x_i,y_j)\ log(p(x_i|y_j))\\ \\ &=-\sum_{y_j\in Y}\sum_{x_i\in X}\ p(x_i,y_j)\ log(p(y_j))-\sum_{x_i\in X}\sum_{y_j\in Y}\ p(x_i,y_j)\ log(p(x_i|y_j))\\ \\ &=-\sum_{y_j\in Y}\ p(y_j)\ log(p(y_j))-\sum_{x_i\in X}\sum_{y_j\in Y}\ p(x_i,y_j)\ log(p(x_i|y_j))\\ \\ &=H(Y)+H(X|Y) \\ &=H(X)+H(Y|X) \\ \end{aligned} H(X,Y)=xiXyjY p(xi,yj) log(p(xi,yj))=xiXyjY p(xi,yj) log(p(xiyj)p(yj))=xiXyjY p(xi,yj) log(p(yj))xiXyjY p(xi,yj) log(p(xiyj))=yjYxiX p(xi,yj) log(p(yj))xiXyjY p(xi,yj) log(p(xiyj))=yjY p(yj) log(p(yj))xiXyjY p(xi,yj) log(p(xiyj))=H(Y)+H(XY)=H(X)+H(YX)

    • 条件熵:已知一个变量Y之后,剩下的变量X的不确定性
      H ( X ∣ Y ) = ∑ x i ∈ X ∑ y j ∈ Y −   p ( x i , y j )   l o g ( p ( x i ∣ y j ) ) = ∑ y j ∈ Y p ( y j ) H ( X ∣ y j ) \begin{aligned} H(X|Y)&=\sum_{x_i\in X}\sum_{y_j\in Y}-\ p(x_i,y_j)\ log(p(x_i|y_j)) \\ &= \sum_{y_j\in Y}p(y_j)H(X|y_j) \end{aligned} H(XY)=xiXyjY p(xi,yj) log(p(xiyj))=yjYp(yj)H(Xyj)

    • 信息增益:
      已知一个变量以后,使得另外一个变量的不确定性减少,减少的幅度即为信息增益,也被称为互信息。
      I ( X , Y ) = H ( X ) − H ( X ∣ Y ) I(X,Y)=H(X)-H(X|Y) I(X,Y)=H(X)H(XY)
      信息增益越大,说明变量Y带来的信息越多,即越有用。

    使用场景

    信息增益可以用来衡量使用某特征来划分样本以后,样本的不确定性与划分前相比,下降的幅度。下降的越多,说明生成的划分越确定,即被划分到同一节点的样本越可能属于同一类别。
    信息增益可以很好地选出最符合目标的特征,即:经过此特征划分后,不同类别的样本可以被分开。
    计算公式:
    I ( D , A ) = H ( D ) − H ( D ∣ A ) I(D, A) = H(D)-H(D|A) I(D,A)=H(D)H(DA)
    D : D: D:原始的样本分布。
    A : A: A:某一特征测试。
    D ∣ A : D|A: DA:经过特征测试后,新的样本分布。

    例子

    原始有两类样本,类0的样本数为10,类1的样本数为5。现在有两个特征,特征A有三个取值,划分之后A1的样本分布为4:0,A2为4:1,A3为2:4。特征B有两个取值,划分之后B1的样本分布为8:2,B2为2:3。
    H ( D ) = − 10 15 l o g ( 10 15 ) − 5 15 l o g ( 5 15 ) = 0.92 H(D)=-\frac{10}{15}log(\frac{10}{15})-\frac{5}{15}log(\frac{5}{15})=0.92 H(D)=1510log(1510)155log(155)=0.92
    H ( D ∣ A ) = − 4 15 ( 1 ∗ l o g ( 4 4 ) + 0 ) − 5 15 ( 4 5 ∗ l o g ( 4 5 ) + 1 5 ∗ l o g ( 1 5 ) ) − 6 15 ( 2 6 ∗ l o g ( 2 6 ) + 4 6 ∗ l o g ( 4 6 ) ) = 0.61 H(D|A)=-\frac{4}{15}(1*log(\frac{4}{4})+0)-\frac{5}{15}(\frac{4}{5}*log(\frac{4}{5})+\frac{1}{5}*log(\frac{1}{5}))-\frac{6}{15}(\frac{2}{6}*log(\frac{2}{6})+\frac{4}{6}*log(\frac{4}{6}))=0.61 H(DA)=154(1log(44)+0)155(54log(54)+51log(51))156(62log(62)+64log(64))=0.61
    H ( D ∣ B ) = − 10 15 ( 8 10 ∗ l o g ( 8 10 ) + 2 10 ∗ l o g ( 2 10 ) ) − 5 15 ( 2 5 ∗ l o g ( 2 5 ) + 3 5 ∗ l o g ( 3 5 ) ) = 0.8 H(D|B)=-\frac{10}{15}(\frac{8}{10}*log(\frac{8}{10})+\frac{2}{10}*log(\frac{2}{10}))-\frac{5}{15}(\frac{2}{5}*log(\frac{2}{5})+\frac{3}{5}*log(\frac{3}{5}))=0.8 H(DB)=1510(108log(108)+102log(102))155(52log(52)+53log(53))=0.8
    I ( D , A ) = 0.92 − 0.61 = 0.31 I(D,A)=0.92-0.61=0.31 I(D,A)=0.920.61=0.31
    I ( D , B ) = 0.92 − 0.8 = 0.12 I(D,B)=0.92-0.8=0.12 I(D,B)=0.920.8=0.12
    因此可知,在这个例子中,选择特征A能使样本更好地被分类。直观地观察A与B的划分后分布也可以粗略看出这一点。

    缺点
    1. 样本不足的情况下,ID3的信息增益法会倾向于选择取值更多的特征。
      当样本量不足时,对于取值多的特征来说,其每种划分下的样本会比取值少的特征少。而根据大数定理,当样本数目不足时,用每个划分中的各类样本数量来估计各类的出现概率是不准确的。会造成估计概率和真实概率间的方差很大。举个例子,投掷硬币,正反面出现的概率应为0.5:0.5,但因为投掷次数不多(此处极端假设2次),最后得到的正反面次数是2:0。若在这种样本不足的情况下,用样本数目来近似每类的出现概率,则会得到1:0的结果,计算出的信息增益会偏大。即,估计出的概率分布更不均匀,导致其对应的熵偏小,信息增益偏大。
      当然,在样本充足的情况下,ID3不会有这样的倾向。
      样本不足 → 估计值的方差较大 → 估计出的分布更不均匀 → 熵偏小 → 信息增益偏大 \text{样本不足}\rightarrow \text{估计值的方差较大}\rightarrow\text{估计出的分布更不均匀}\rightarrow\text{熵偏小}\rightarrow\text{信息增益偏大} 样本不足估计值的方差较大估计出的分布更不均匀熵偏小信息增益偏大

    2. 无法处理数值特征。
      可以看到,ID3算法计算信息增益时,只考虑了类别特征的计算方法,而对于像身高,体重等连续的数值特征却没有涵盖。

    3. 没有考虑特征缺失值的处理。

    4. 算法里没有考虑树的过拟合问题。

    C4.5: 信息增益比

    C4.5针对ID3的缺点做了很多优化,其中最值得一提的是用信息增益比来代替单纯的信息增益,作为特征选择的衡量标准。信息增益比能缓解在样本不足的情况下,ID3对取值更多的特征的偏好。C4.5还通过离散化连续数值特征,使得信息增益比也可以在这些特征上使用。C4.5也加入了处理缺失值的方法,以及添加了简单的正则化剪枝,以缓解过拟合的问题。

    定义
    1. 特征熵:特征熵可以用来衡量样本在使用某特征划分后的分布的不确定性。取值数目越多,分割后各取值得到的样本分布得越均匀,则特征熵越大。可以用它作为分母,来惩罚取值多的特征,以纠正ID3的偏好。
      H A ( D ) = − ∑ i = 1 n ∣ D i ∣ ∣ D ∣ l o g ( ∣ D i ∣ ∣ D ∣ ) H_A(D)=-\sum_{i=1}^n\frac{\lvert{D_i}\rvert }{\lvert D \rvert}log(\frac{\lvert{D_i}\rvert }{\lvert D \rvert}) HA(D)=i=1nDDilog(DDi)
      i : i: i:特征A的n种取值。
      ∣ D ∣ : \lvert{D}\rvert: D分割前的总样本数。
      ∣ D i ∣ : \lvert{D_i}\rvert: Di每个划分的样本的数目。

    2. 信息增益比:
      I R ( D , A ) = I ( D , A ) H A ( D ) I_R(D,A)=\frac{I(D,A)}{H_A(D)} IR(D,A)=HA(D)I(D,A)
      R : R: R: ratio.
      H A ( D ) : H_A(D): HA(D): 特征熵,用于平衡特征取值数目对信息增益带来的影响。

    连续数值特征的处理(转化为二分类寻找阈值的问题)

    假设存在一个连续特征A,在样本中,其取值分别为 a 1 , a 2 , . . . a n a_1,a_2,...a_n a1,a2,...an。要处理这个特征,容易想到的思路是先将它离散化,再寻找最优分割:

    1. 特征A的取值排序:
      假设排序结果从小到大为 a 1 , a 2 , . . . a n a_1,a_2,...a_n a1,a2,...an
    2. 设置候选分割点:
      使用相邻数值计算均值,作为待检测的分割点。即n个样本,排序分割后会产生(n-1)个分割点。
    3. 选择最优分割点:
      每个分割点都把样本分为了两类,依据信息增益比的计算公式计算每个分割点对应的信息增益比。选择信息增益比最大的点作为此特征最终的分割点。
    解决过拟合问题:剪枝
    • 预剪枝
      设置一定的early stop的条件,当满足条件后就不再继续分割。一般使用的条件如下:
      • 所有特征均已使用。
      • 分割后样本数小于阈值。
      • 分割后准确率反而降低。
    • 后剪枝(子树替代法)
      在整个决策树构建完成后,自底向上检验每棵子树是否能用叶子节点替代。如果子树的错误率大于使用单一的叶子节点的错误率,则替代
      但这个方法存在着一个很大的问题,即如何准确估计子树的错误率。在计算错误率时,若使用训练集来计算,则所得的错误率一般会比真实的值小。为了纠正这样的偏差,有三种解决的方法:
      • 使用验证集来计算子树的错误率。
      • 悲观计算:人为地增加子树的错误样本数。
      • 用confidence level来估计真实的错误率的区间。
        这里讲一下第三种方法:
        f:用训练集估计的错误率, = 错 误 样 本 数 量 样 本 总 数 量 =\frac{错误样本数量}{样本总数量} =
        p :真实的错误率
        可知: p = f ± ( z ∗ f ( 1 − f ) N ) p =f\pm(z*\sqrt{\frac{f(1-f)}{N}}) p=f±(zNf(1f) )
        z:某一confidence level下对应的系数。例如:置信区间95%意味着,取均值左右1.96个标准差的范围( ± z ∗ σ \pm z*\sigma ±zσ),100次中有95次,真实的错误率就被包含在这个范围中。
        e:某一confidence level下的真实错误率区间的上限, e = f + ( z ∗ f ( 1 − f ) N ) e=f+(z*\sqrt{\frac{f(1-f)}{N}}) e=f+(zNf(1f) )
        在这里插入图片描述
        如上图所示,f = 2/6, N=6时, p = 0.33 + 0.69 ∗ 0.33 ∗ 0.66 / 6 = 0.33 + 0.13 = 0.46 p = 0.33 + 0.69*\sqrt{0.33*0.66/6}=0.33+0.13=0.46 p=0.33+0.690.330.66/6 =0.33+0.13=0.46
        计算子树的错误率上限时,使用样本数加权平均每个叶子的e。
        如果剪枝后的e更小,则使用单一叶子来替代整个子树。上图例子中,剪枝前e为0.51,剪枝后降低为0.46,因此执行此剪枝。
    • 预剪枝 vs. 后剪枝
      • 预剪枝:
        +可缩短模型训练的时间,降低过拟合的风险
        -可能引起欠拟合问题。虽然某一次分割不会大幅提升准确率,但是按这个分支展开,后续可能会带来性能的提升。预剪枝根据贪心策略不再继续探索某些分支,带来了欠拟合风险。
      • 后剪枝:
        +首先充分探索各种特征及其分割,生成一颗完整的决策树,之后再从下至上,寻找可以通过剪枝来优化的子树,欠拟合风险小
        -消耗更多的计算资源,更加耗时。
    问题
    1. 只能用于分类。
    2. 在选择连续特征时需要排序,熵模型涉及许多对数运算,分割点选择需要轮流计算比较,大量耗费计算资源。

    CART(Classification And Regression Tree):

    • 二叉树,简化决策树的规模,提高树的生成效率,比起ID3和C4.5的多叉树来说,计算规模更小。
    • 可以用作分类和回归:
      • 分类:Gini指数最小化
      • 回归:平方误差最小化(对每一特征生成可能分割+用平方误差选择最优分割)。每一个节点的预测值为属于此节点的所有样本的均值。
    定义
    • Gini指数:衡量一个分割的纯净度。Gini指数越小,说明此分割越纯净,此分割中的绝大部分样本属于同一类。随机抽取两个样本,其类别不一致的概率, 类似于 p(1-p)
      G i n i ( D i ) = ∑ k = 1 m ∣ D k ∣ ∣ D i ∣ ( 1 − ∣ D k ∣ ∣ D i ∣ ) Gini(D_i)=\sum_{k=1}^m\frac{\lvert{D_k}\rvert }{\lvert D_i \rvert}(1-\frac{\lvert{D_k}\rvert }{\lvert D_i \rvert}) Gini(Di)=k=1mDiDk(1DiDk)
      i : i: i:特征A的一个分割。
      m : m: m:一共有m类样本。
      ∣ D i ∣ : \lvert{D_i}\rvert: Di此分割拥有的总样本数。
      ∣ D k ∣ : \lvert{D_k}\rvert: Dk每类的样本的数目。

    • 与熵的关系:
      一阶泰勒展开: l n ( x ) = − 1 + x + o ( x ) ln(x)=-1+x+o(x) ln(x)=1+x+o(x)
      H ( D i ) = − ∑ k = 1 m p k l o g ( p k ) ≈ − ∑ k = 1 m p k ( 1 − p k ) ≈ ∑ k = 1 m ∣ D k ∣ ∣ D i ∣ ( 1 − ∣ D k ∣ ∣ D i ∣ ) \begin{aligned} H(D_i)&=-\sum_{k=1}^m p_k log(p_k) \\ &\approx-\sum_{k=1}^m p_k (1-p_k) \\ &\approx \sum_{k=1}^m\frac{\lvert{D_k}\rvert }{\lvert D_i \rvert}(1-\frac{\lvert{D_k}\rvert }{\lvert D_i \rvert})\\ \end{aligned} H(Di)=k=1mpklog(pk)k=1mpk(1pk)k=1mDiDk(1DiDk)
      Gini指数可以看作是熵的一阶泰勒展开。
      在这里插入图片描述

    • 特征的Gini指数:特征的每个分割的Gini指数的加权平均。
      G i n i ( D ) = ∑ i = 1 n ∣ D i ∣ ∣ D ∣ ∑ k = 1 m ∣ D k ∣ ∣ D i ∣ ( 1 − ∣ D k ∣ ∣ D i ∣ ) = ∑ i = 1 n ∣ D i ∣ ∣ D ∣ G i n i ( D i ) \begin{aligned} Gini(D)&=\sum_{i=1}^n\frac{\lvert{D_i}\rvert }{\lvert D \rvert}\sum_{k=1}^m\frac{\lvert{D_k}\rvert }{\lvert D_i \rvert}(1-\frac{\lvert{D_k}\rvert }{\lvert D_i \rvert}) \\ \\ &=\sum_{i=1}^n\frac{\lvert{D_i}\rvert }{\lvert D \rvert}Gini(D_i) \end{aligned} Gini(D)=i=1nDDik=1mDiDk(1DiDk)=i=1nDDiGini(Di)
      i : i: i:特征A的一个分割。
      n : n: n:特征A一共有n种取值。
      ∣ D ∣ : \lvert{D}\rvert: D总样本的数目。
      ∣ D k ∣ : \lvert{D_k}\rvert: Dk每种分割里的每类的样本数目。

    • 回归问题的特征选择标准:假设最优特征为 a a a,其对应的最优分割为 s s s
      min ⁡ a , s ( min ⁡ c 1 ∑ x i ∈ D 1 ( y i − c 1 ) 2 + min ⁡ c 2 ∑ x i ∈ D 2 ( y i − c 2 ) 2 ) \underset{a,s}{\min}(\underset{c_1}{\min}\sum_{x_i \in D_1}(y_i-c_1)^2+\underset{c_2}{\min}\sum_{x_i \in D_2}(y_i-c_2)^2) a,smin(c1minxiD1(yic1)2+c2minxiD2(yic2)2)
      D 1 : D_1: D1:属于分割1的样本集合。
      D 2 : D_2: D2:属于分割2的样本集合。
      c 1 : c_1: c1:样本集合1的均值,依赖于分割点s的选取。
      c 2 : c_2: c2:样本集合2的均值。
      y i : y_i: yi:样本对应的真实值。

    使用场景
    • 分类树
      • 类别特征
      • 连续数值特征
    • 回归树:
      对于不同类型的特征的处理同上,不同的是衡量特征优劣的metric。先计算叶节点的样本均值,以此均值作为预测值,并计算每个样本的真实值与此预测值之间平方差和作为衡量标准。
    后剪枝:基于代价复杂度
    • 设计一个损失函数,来平衡过拟合(叶节点过多)和欠拟合问题(误差较大):
      C α ( T ) = C ( T ) + α ∣ T ∣ C_\alpha(T)=C(T)+\alpha \lvert{T}\rvert Cα(T)=C(T)+αT
      C ( T ) : C(T): C(T):预测误差,拟合度。
      α : \alpha: α:参数,惩罚复杂模型的力度。
      ∣ T ∣ : \lvert{T}\rvert: T:叶节点数目,模型复杂度,泛化能力。

    • 过程:
      对于每一个内节点 t t t所对应的子树 T t T_t Tt,计算剪枝前后loss的差:
      C α ( T t ) − C α ( t ) = C ( T t ) + α ∣ T t ∣ − C ( t ) − α ∗ 1 = C ( T t ) − C ( t ) + α ( ∣ T t ∣ − 1 ) \begin{aligned} C_\alpha(T_t)-C_\alpha(t) &= C(T_t)+\alpha \lvert{T_t}\rvert-C(t)-\alpha*1 \\ &=C(T_t)-C(t)+\alpha(\lvert{T_t}\rvert-1) \end{aligned} Cα(Tt)Cα(t)=C(Tt)+αTtC(t)α1=C(Tt)C(t)+α(Tt1)
      α \alpha α为0时,对于某一个确定的子树 T t T_t Tt 和叶子 t t t ,一定有 C α ( T t ) < C α ( t ) C_\alpha(T_t)<C_\alpha(t) Cα(Tt)<Cα(t)。但是随着 α \alpha α的逐渐增大,到某一时刻会有 C α ( T t ) ⩾ C α ( t ) C_\alpha(T_t)\geqslant C_\alpha(t) Cα(Tt)Cα(t)。此时虽然叶子的error更大,但由于模型复杂度的惩罚系数大,叶子的最终loss更小。
      对于不同的子树来说,使剪枝前后的loss的关系反转的 α \alpha α也不同。这个临界 α \alpha α越小,说明剪枝前后error的差距越小,且子树的叶子节点越多,也就是越理想的剪枝对象(weakest link)。更形象的解释见下图。
      因此在每一次剪枝中,剪掉临界 α \alpha α最小的那个子树。
      在这里插入图片描述
      在这里插入图片描述
      这个过程之后,得到了每个可能的 α i \alpha_i αi及其对应的最优决策树(完全决策树的内节点数目有限,因此迭代次数也有限)。之后可以使用 Cross-Validation等方法选出最优的 α b e s t \alpha_{best} αbest

    优劣

    CART和ID3一样,没有特征熵来均衡特征取值数目对熵的影响,因此也存在偏向细小分割的问题。

    总结比较

    以上介绍的便是决策树常见的三种算法,它们的不同主要体现在一下几个方面:

    • 使用场景:
      • 分类
      • 回归
    • 使用特征:
      • 类别特征
      • 连续数值特征
    • 算法偏好
      • 取值多,分割细的特征
    • metric:
      • 信息增益
      • 信息增益比
      • Gini指数
    • 剪枝方法:
      • 预剪枝
      • 后剪枝
        • 悲观剪枝(子树替代法)
        • 代价复杂度
    • 填补缺失值
      • 基于有缺失值的样本做特征选择
      • 决定有缺失值的样本属于哪一个划分

    算法分析

    适用场景

    • 样本量:

    C4.5做特征选择时涉及样本排序,分割检测和对数运算,且其本身为多叉树结构,需消耗很多计算资源,适用于小样本。而 CART 本身是一种大样本的统计方法,小样本处理下泛化误差较大。

    • 分类 or 回归
    • 属性取值:
      ID3和CART均会偏好取值多的特征,有此情况的话需考虑C4.5算法

    问题

    过拟合

    • 决策树算法实质上是一个多重选择过程:为存在的n个特征计算分别的score,再选择score最大的特征做测试,加入模型以提高模型的准确度。而这里存在概念的混淆:

      • 特征 i s c o r e i score_{i} scorei的分布:在评价函数与特征种类确定的情况下,与样本集合有关
      • n个特征的 s c o r e m a x 的 分 布 score_{max}的分布 scoremax :与特征的数目有关

      s c o r e i score_{i} scorei s c o r e m a x score_{max} scoremax根本不是同一分布的变量,因此用 s c o r e m a x score_{max} scoremax来代表某一特征的 s c o r e i score_{i} scorei从而进行选择是有问题的,这个推断是不成立的,他不能为未来的预测做任何保证。 s c o r e m a x score_{max} scoremax的分布受特征数目的影响,而决策树在使用时却没有考虑这一点。因此用此方法选择出的特征有可能有噪音。在此举个简单的例子:
      选择一个预测员来预测股票走势,若他14天预测正确11次以上则中选。假设所有来应征的预测员都是骗子,他们都做随机决策,那么一个预测员能正确11次以上,即他中选的概率为0.028。现在假设有n人应征,那么从中至少能选出一人的概率为: 1 − ( 1 − 0.028 ) n 1- (1-0.028)^{n} 1(10.028)n。n为10时,概率为0.253;n为30时,至少选择一人的概率为0.5。
      由此可以看出,每个预测员预测正确11次以上的概率(即 s c o r e i score_{i} scorei),和n个决策员中至少一个正确11次以上的概率(即 s c o r e m a x score_{max} scoremax)是不同的。
      实际上当n很大时, P ( s c o r e i > t h r e s h o l d ) = p P(score_{i} > threshold)=p P(scorei>threshold)=p 是会明显小于 P ( s c o r e m a x > t h r e s h o l d ) = 1 − ( 1 − p ) n P(score_{max} > threshold)=1-(1-p)^n P(scoremax>threshold)=1(1p)n的,当特征很多时,用 s c o r e m a x score_{max} scoremax会高估 s c o r e i score_{i} scorei,即选出来的特征可能包含很多噪音。

    • 决策树是用的是贪婪策略,因此它倾向于寻找局部最优,而不是根据数据的所有信息全局地寻找最优点, 对样本分布非常敏感,样本的改变可能会剧烈影响决策树的结构。

    • 随着决策树的不断生长,叶子节点会越来越多,这也意味着分割的粒度会越来越细。想象极限情况下,可能会为每一个样本分一个叶子节点,即一条决策路径。因此决策树生成的方式,天然决定了它很容易过拟合。

    • 过拟合的解决方案:

      • early stop
      • pruning
      • K-Fold Cross Validation
      • Random Forest

    类别不均衡

    • CART: 先验机制来确定分类阈值,以平衡偏差数据:
      N 1 ( c h i l d ) N t o t a l ( c h i l d ) > N 1 ( p a r e n t ) N t o t a l ( p a r e n t ) \frac{N_1(child)}{N_{total}(child)}>\frac{N_1(parent)}{N_{total}(parent)} Ntotal(child)N1(child)>Ntotal(parent)N1(parent)
      时,child节点才能被标记为类1。即,用父节点中的类别比例来作为分类阈值。仅影响每个节点的分类选择,使得每类数据落在各节点的概率先验相等。

    实现

    算法的分析比较 :https://www.cnblogs.com/pinard/p/6050306.html
    c3为什么倾向于特征多的属性: https://www.zhihu.com/question/22928442
    优化方案:https://blog.csdn.net/xbinworld/article/details/44660339
    信息熵:https://blog.csdn.net/qq280929090/article/details/78135417
    C4.5剪枝:http://www.cs.bc.edu/~alvarez/ML/statPruning.html
    置信区间:https://www.zhihu.com/question/26419030
    Cost-Complexity-Pruning: http://mlwiki.org/index.php/Cost-Complexity_Pruning
    Cost-Complexity-Pruning的原理: https://online.stat.psu.edu/stat508/lesson/11/11.8/11.8.2
    多重选择过程(Multiple Comparisons): https://link.springer.com/content/pdf/10.1023/A:1007631014630.pdf

    更多相关内容
  • 常用决策树算法总结

    千次阅读 2019-02-16 15:20:28
    决策树(decision tree)是一个树结构(可以是二叉树或非二叉树)。其每个非叶节点表示一个特征属性上的测试,每个分支代表这个特征属性在某个值域上的输出,而每个叶节点存放一个类别。 使用决策树进行决策的过程...

    算法思想
    决策树(decision tree)是一个树结构(可以是二叉树或非二叉树)。其每个非叶节点表示一个特征属性上的测试,每个分支代表这个特征属性在某个值域上的输出,而每个叶节点存放一个类别。

    使用决策树进行决策的过程就是从根节点开始,测试待分类项中相应的特征属性,并按照其值选择输出分支,直到到达叶子节点,将叶子节点存放的类别作为决策结果。

    总结来说:决策树模型核心是下面几部分:结点和有向边组成
    结点有内部结点和叶结点俩种类型内部结点表示一个特征,叶节点表示一个类。

    在这里插入图片描述
    下面介绍一下三种主要的决策树算法:ID3,C4.5,CART

    ID3

    ID3 的构造准则是信息增益。
    在这里插入图片描述
    在这里插入图片描述

    C4.5

    C4.5的构造准则是信息增益比。
    在这里插入图片描述

    CART

    CART 的构造准则是基尼指数。
    在这里插入图片描述
    在这里插入图片描述

    决策树不同算法的对比

    在这里插入图片描述
    参考资料:
    1.https://zhuanlan.zhihu.com/p/26703300
    2.《统计学习方法》李航
    3.《百面机器学习》

    展开全文
  • 分类树(决策树)是一种十分常用的分类方法。他是一种监管学习,所谓监管学习就是给定一堆样本,每个样本都有一组属性和一个类别,这些类别是事先确定的,那么通过学习得到一个分类器,这个分类器能够对新出现的对象...
  • 决策树算法

    2022-05-22 16:01:21
    决策树是一种比较常用的分类算法,理解起来也相对容易。所谓决策树分类就是用决策条件构成的一个树状预测模型,通过这个模型,我们可以对未知类别的数据进行分类。 二、决策树的定义与核心思想 决策树又称为判定树,...

    一、决策树原理

    决策树是一种比较常用的分类算法,理解起来也相对容易。所谓决策树分类就是用决策条件构成的一个树状预测模型,通过这个模型,我们可以对未知类别的数据进行分类。

    二、决策树的定义与核心思想

    决策树又称为判定树,是运用于分类的一种树结构,其中的每个内部节点代表对某一属性的一次测试,每条边代表一个测试结果,叶节点代表某个类或类的分布。
    决策树的决策过程需要从决策树的根节点开始,待测数据与决策树中的特征节点进行比较,并按照比较结果选择选择下一比较分支,直到叶子节点作为最终的决策结果。

    三、决策树构造

    决策树的构造过程不依赖领域知识,它使用属性选择度量来选择将元组最好地划分成不同的类的属性。所谓决策树的构造就是进行属性选择度量确定各个特征属性之间的拓扑结构。

    3.1构造决策树的关键步骤——分裂属性

    所谓分裂属性就是在某个节点处按照某一特征属性的不同划分构造不同的分支,其目标是让各个分裂子集尽可能地“纯”。尽可能“纯”就是尽量让一个分裂子集中待分类项属于同一类别。
    分裂属性分为三种不同的情况:

    1. 属性是离散值且不要求生成二叉决策树。此时用属性的每一个划分作为一个分支。
    2. 属性是离散值且要求生成二叉决策树。此时使用属性划分的一个子集进行测试,按照“属于此子集”和“不属于此子集”分成两个分支。
    3. 属性是连续值。此时确定一个值作为分裂点split point,按照>split point和<=split point生成两个分支。
    4. 构造决策树的关键性内容是进行属性选择度量,属性选择度量是一种选择分裂准则,是将给定了类标记的训练集合划分,“最好”地分成个体类的启发式方法,它决定了拓扑结构及分裂点split point的选择。
      属性选择度量算法有很多,一般使用自顶向下递归分治法,并采用不回溯的贪心策略,常用的算法有ID3和C4.5。
      在实际构造决策树时,通常要进行剪枝,这是为了处理由于数据中的噪声和离群点导致的过分拟合问题。剪枝有两种:
    5. 先剪枝——在构造过程中,当某个节点满足剪枝条件,则直接停止此分支的构造。
    6. 后剪枝——先构造完成完整的决策树,再通过某些条件遍历树进行剪枝。

    3.2 交叉验证

    因为在实际的训练中,训练的结果对于训练集的拟合程度通常还是挺好的(初试条件敏感),但是对于训练集之外的数据的拟合程度通常就不那么令人满意了。因此我们通常并不会把所有的数据集都拿来训练,而是分出一部分来(这一部分不参加训练)对训练集生成的参数进行测试,相对客观的判断这些参数对训练集之外的数据的符合程度。这种思想就称为交叉验证。

    3.3函数介绍

    (1)train_test_split函数
    train_test_split来自sklearn.model_selection,是交叉验证中常用的函数,它能从样本中按比例随机选取训练集和测试集。其用法如下:
    X_train, X_test, y_train, y_test = cross_validation.train_test_split(train_data, train_target, test_size=0.25, random_state=None)
    参数解释:
    . train_data: 所要划分的样本特征集。
    . train_target: 所要划分的样本结果。
    . test_size: 样本占比,如果是整数的话就是样本的数量。
    . random_state: 是随机数的种子
    (2)tree.DecisionTreeClassifier函数
    DecisionTreeClassifier函数用于创建决策树分类器。其用法如下:
    clf = tree.DecisionTreeClassifier()
    常用参数解释:
    . criterion: string类型,可选(默认为"gini")。指定使用哪种方法衡量分类的质量。支持的标准有"gini"代表的是Gini impurity(不纯度)与"entropy"代表的是information gain(信息增益)。
    . splitter: string类型,可选(默认为"best")。指定在节点中选择分类的策略。支持的策略有"best",选择最好的分类,“random"选择最好的随机分类。
    . max_depth: int or None,可选(默认为"None”)。表示树的最大深度。
    . min_samples_split: int,float,可选(默认为2)。一个内部节点需要的最少的样本数。
    . max_features: int,float,string or None类型,可选(默认为None)。在进行分类时需要考虑的特征数。
    . random_state: 可为int类型,RandomState 实例或None,可选(默认为"None")。
    如果是int,random_state是随机数字发生器的种子;如果是RandomState,random_state是随机数字发生器,如果是None,随机数字发生器是np.random使用的RandomState instance.

    四、编写线性回归算法代码

    4.1 基于鸢尾花数据集实现决策树分类
    启动环境后,登录到服务器,编辑代码文件:
    1.导入用到的库
    在这里插入图片描述
    2.加载数据集
    在这里插入图片描述
    3.构建模型
    在这里插入图片描述
    4.模型评估
    在这里插入图片描述
    4.2基于癌症数据集实现决策树分类
    1.导入数据集
    在这里插入图片描述
    2.提取数据
    在这里插入图片描述

    3.划分数据集
    在这里插入图片描述

    4.构建模型
    在这里插入图片描述
    5.模型评估
    在这里插入图片描述

    6.决策树的属性
    在这里插入图片描述

    7.绘图
    在这里插入图片描述
    运行结果:
    在这里插入图片描述

    展开全文
  • 点击上方“小白学视觉”,选择...本篇介绍一下决策树算法的原理。❞决策树算法不像前面介绍的SVM那样,散发着浓厚的数学气味。这个算法还是比较接地气的。信息论基础 这个语法结构大家应该不陌生。怎样准确地定量选...

    点击上方“小白学视觉”,选择加"星标"或“置顶

    重磅干货,第一时间送达

    决策树()是一类很常见很经典的机器学习算法,既可以作为分类算法也可以作为回归算法。同时也适合许多集成算法,如, ,以后会逐一介绍。本篇介绍一下决策树算法的原理。❞

    决策树算法不像前面介绍的SVM那样,散发着浓厚的数学气味。这个算法还是比较接地气的。

    信息论基础

    2486e97fafa609a456ab19947cfde436.png 这个语法结构大家应该不陌生。怎样准确地定量选择 后面的条件,也就是要找到一个性能指标来衡量这个条件的好坏。(就像SVM中引入了来衡量一条直线的好坏)。

    70年代,一个名为昆兰的大牛找到了信息论中的「熵」来度量决策树的决策选择过程。注意,信息论中的熵是香农提出的。昆兰只是将熵应用于决策树的人。

    熵度量了事物的不确定性(可以联想化学里的熵,混乱程度),越不确定的事物,它的熵就越大。具体的,随机变量X的熵的表达式如下:

    决策树构造

    决策树的组成:

    • 根节点:第一个选择点

    • 非叶子节点与分支:中间过程

    • 叶子节点:最终的决策结果b7c2ddecf7bc1bc5eae2a7e526345058.png就像这张图展示的,第一个节点就是根节点,绿色的代表 也就是叶子节点,其它的节点也就是非叶子节点(用于决策),也就是 。

    那么如何构造决策树呢?

    「第一步,选择根节点」


    问题来了,特征不唯一,选哪一个作根节点最优?

    这就涉及到了衡量标准,一般而言,随着划分过程不断进行,我们希望节点的熵能够迅速地降低。因为随机变量的熵越大,随机变量的不确定性越大,代表纯度越低。所以希望节点的熵能够迅速降低,使得纯度不断增加。所以以「信息增益」作为衡量标准。

    引入一个信息增益( )的概念。

    「定义」:特征 对训练数据集 的信息增益 ,定义为集合 的经验熵 与特征 给定条件下 的经验条件熵 之差,即

    信息增益也就度量了熵降低的程度。
    以信息增益作为衡量标准的算法被称为ID3算法。

    「第二步,选择子节点」


    依然是采用信息增益的标准进行选择。

    「第三步,何时停止」


    其实这一步就涉及到剪枝,下文详解。

    如果对这些概念还是有点模糊,可以结合下面的实例再思考思考。

    实例

    92059cea278302fdd9504d286ad40f8c.png这是数据(14天的打球情况),有四种环境特征(,,,),最后一列()代表最后有没有出去打球。

    「首先,选择根节点」。一共有四个特征,所以根节点的选择有四种。a55f699978fbffbbad394d06709da7de.png

    在我们的原始数据(14天)有9天打球,5天不大,所以此时的熵为:

    402 Payment Required

    接着,四个特征逐一分析,先从(天气)下手:1993fac1a068aee8b89b20fc325130c0.png当 时,

    402 Payment Required


    当 时,
    当 时,

    根据数据, 取 ,,的概率分别为,
    熵值计算(几个特征属性熵的加权求和):

    402 Payment Required

    信息增益:

    402 Payment Required

    同样的方式计算其它三个特征的信息增益:

    四个特征中, 的增益最大,所以选择作为根节点。
    「接下来的子节点选择同上」

    「何时停止?」
    上文也说了,"何时停止"涉及到剪枝。为什么要剪枝?
    决策树存在较大的过拟合风险,理论上,决策树可以将样本数据完全分开,但是这样就带来了非常大的过拟合风险,使得模型的泛化能力极差。0c6f3305a8c44c68fcca15afe8b6d104.png剪枝和日常树木的修建是一个道理。这里介绍最常用的「预剪枝」,在构造决策树的过程中,提前停止。
    具体的预剪枝策略有:

    • 限制深度,例如,只构造到两层就停止。

    • 限制叶子节点个数,例如,叶子节点个数超过某个阈值就停止
      等等

     

    简单介绍一下集成学习( )。有两种类型,

    • Bagging :训练多个分类器,最后可采取投票机制选择最终结果。这里的分类器常常是决策树。代表算法是

    • Boosting:仍是训练多个分类器,将最后的结果加权求和,代表算法是,

    这些算法在一些比赛中都是很常见的。

    
     

    好消息!

    小白学视觉知识星球

    开始面向外开放啦👇👇👇

    
     

    50e4de619be8de96f8f444f0644ba73d.png

    下载1:OpenCV-Contrib扩展模块中文版教程
    
    在「小白学视觉」公众号后台回复:扩展模块中文教程,即可下载全网第一份OpenCV扩展模块教程中文版,涵盖扩展模块安装、SFM算法、立体视觉、目标跟踪、生物视觉、超分辨率处理等二十多章内容。
    
    
    下载2:Python视觉实战项目52讲
    在「小白学视觉」公众号后台回复:Python视觉实战项目,即可下载包括图像分割、口罩检测、车道线检测、车辆计数、添加眼线、车牌识别、字符识别、情绪检测、文本内容提取、面部识别等31个视觉实战项目,助力快速学校计算机视觉。
    
    
    下载3:OpenCV实战项目20讲
    在「小白学视觉」公众号后台回复:OpenCV实战项目20讲,即可下载含有20个基于OpenCV实现20个实战项目,实现OpenCV学习进阶。
    
    
    交流群
    
    欢迎加入公众号读者群一起和同行交流,目前有SLAM、三维视觉、传感器、自动驾驶、计算摄影、检测、分割、识别、医学影像、GAN、算法竞赛等微信群(以后会逐渐细分),请扫描下面微信号加群,备注:”昵称+学校/公司+研究方向“,例如:”张三 + 上海交大 + 视觉SLAM“。请按照格式备注,否则不予通过。添加成功后会根据研究方向邀请进入相关微信群。请勿在群内发送广告,否则会请出群,谢谢理解~
    展开全文
  • 决策树公式推导 (1)信息熵--用来度量样本集合纯度最常用的一种指标,定义如下: Ent⁡(D)=−∑k=1∣Y∣pklog⁡2pk(式1) \operatorname{Ent}(D)=-\sum_{k=1}^{\vert{\mathcal{Y}}\vert}p_k\log_2p_k\tag{式1} Ent...
  • 机器学习-决策树算法

    千次阅读 2021-09-12 20:24:11
    决策树是非参数学习算法 决策树可以解决分类问题 决策树天然可以解决多分类问题 决策树可以解决回归问题:落在叶子节点(对应图中的A、B、C三点)的数据的平均值作为回归的结果 决策树可以应用于信用卡评级的案例...
  • 然 后介绍了传统的 ID3决策树算法,并对常用决策树算法的优缺点进行了总结。以经典的决策树 ID3模型为基础,对已有决策属性挑选策略进行了分析和总结,对决策属性挑选策略进行了改进,提出了基于“相关信息增益度”的...
  • 常用决策树算法C4.5的实现代码。利用matlab实现。
  • I . 决策树模型 II . 决策树模型 示例 III . 决策树算法列举 IV . 决策树算法 示例 V . 决策树算法性能要求 VI . 决策树模型创建 ( 递归创建决策树 ) VII . 决策树 树根属性 选择
  • 点击上方“小白学视觉”,选择加"星标"或“置顶”重磅干货,第一时间送达简介和算法决策树是机器学习最常用算法之一,它将算法组织成一颗树的形式。其实这就是将平时所说的if-then语句构建成...
  • Python机器学习算法之决策树算法

    千次阅读 热门讨论 2021-05-11 19:33:13
    决策树算法1.算法概述2.算法种类3.算法示例4.决策树构建示例5.算法实现步骤6.算法相关概念7.算法实现代码8.算法优缺点9.算法优化 1.算法概述 决策树算法是在已知各种情况发生概率的基础上,通过构成决策树来求取净...
  • 决策树算法原理及实现

    千次阅读 2020-07-12 16:59:30
    决策树是一种十分常用的分类方法,是一种监督学习。 1、决策树的构造 在构造决策树时,我们需要解决的第一个问题就是,当前数据集上那个特征在划分数据分类时起决定性的作用。为了找到决定性的特征,划分
  • 机器学习算法(3)之决策树算法

    万次阅读 多人点赞 2018-08-25 20:26:40
    决策树与逻辑回归的分类区别也在于此,逻辑回归是将所有特征变换为概率后,通过大于某一概率阈值的划分为一类,小于某一概率阈值的为另一类;而决策树是对每一个特征做一个划分。另外逻辑回归只能找到线性分割(输入...
  • 决策树算法原理及应用(详细版)

    万次阅读 多人点赞 2020-09-18 12:22:00
    决策树是一种树形结构,其中每个内部节点表示一个属性上的测试,每个分支代表一个测试输出,每个叶节点代表一种类别。决策树是一种十分常用的分类方法,本文主要内容:C4.5算法简介算法描述属性选...
  • 使用决策树算法进行鸢尾花数据分类(学习笔记) 决策树算法介绍 构建树的过程 从根节点开始,计算所有特征值的信息增益(信息增益比、基尼系数),选择计算结果最大的特征作为根节点。(信息熵增益->ID3,...
  • 决策树——ID3算法

    2021-01-20 12:41:22
    决策树——ID3算法1.信息熵2.信息增益3.西瓜数据集来构造决策树 用信息增益大小作为决策树属性选择划分的依据是ID3算法构造决策树的核心思想 1.信息熵 在讲信息增益之前就不得不提到信息熵,信息熵定义为: 其中: ...
  • 决策树算法及Python实现

    万次阅读 多人点赞 2018-08-09 16:39:25
    1 什么是决策树 决策树(Decision Tree)是一种基本的分类与回归方法,本文主要讨论分类决策树决策树模型呈树形结构,在分类问题中,表示基于特征对数据进行分类的过程。它可以认为是if-then规则的集合。每个内部...
  • 常见决策树算法(ID3、C4.5、CART)

    千次阅读 2019-08-04 16:45:10
    一、决策树原理 决策树模型是运用于分类以及回归的一种树结构。决策树由节点和有向边组成,一般一棵决策树包含一个根节点、若干内部节点和若干叶节点。决策树的决策过程需要从决策树的根节点开始,待测数据与决策树...
  • 一、CART决策树算法简介 CART(Classification And Regression Trees 分类回归树)算法是一种树构建算法,既可以用于分类任务,又可以用于回归。相比于 ID3 和 C4.5 只能用于离散型数据且只能用于分类任务,CART ...
  • 决策树算法总结

    万次阅读 2018-09-17 17:46:52
    在学习决策树算法时首先需要知道一些基本概念: 信息  这个是熵和信息增益的基础概念,是对一个抽象事物的命名,无论用不用‘信息’来命名这种抽象事物,或者用其他名称来命名这种抽象事物,这种抽象事物是客观...
  • 决策树算法原理以及应用举例

    千次阅读 2021-11-17 10:46:57
    1 什么是决策树 决策树(Decision Tree)是一种基本的分类与回归方法,本文主要讨论分类决策树决策树模型呈树形结构,在分类问题中,表示基于特征对数据进行分类的过程。它可以认为是if-then规则的集合。每个内部...
  • 机器学习3决策树算法模型

    千次阅读 2020-10-23 20:19:43
    决策树算法模型 1.什么是决策树? 2.决策树的归纳 2.1 (选择分裂特征)特征的选择 2.2 决策树的生成 2.2.1 ID3 算法 2.2.2 C4.5 算法 2.2.3 Card算法 2.2 树剪枝 2.2.1 先剪枝 2.2.1 后剪枝 3. 决策树在sklearn中...
  • python实现决策树算法

    千次阅读 2018-09-05 18:37:49
    最近看完了《机器学习实战》和天池直播课堂中的决策树算法,觉得意犹未尽,特别是信息熵部分理解并不透彻,于是又把西瓜书中的决策树看了,略有感悟,希望与大家分享一下,下面我按照自己的理解,尽量用通俗的语言...
  • 决策树算法的比较分析 [] [] 一 . 前言 所谓决策树 就是在对数据进行决策分类时利用树的结构将数据记录进行分 , 其中树的一个叶结点就代表符合某个条件的属性集 , 根据属性的不同取值建立决策树的各个分支 ; 随后...
  • 使用决策树算法预测西瓜的好坏

    千次阅读 2021-10-29 17:32:34
    决策树算法是一种逼近离散函数值的方法。 它是一种典型的 分类方法 ,首先对数据进行处理,利用归纳算法生成可读的规则和决策树,然后使用决策对新数据进行分析。 本质上决策树是通过一系列规则对数据进行分类的过程...
  • sklearn之决策树

    2020-12-21 05:58:26
    sklearn之决策树简介 第一次写博客,这里就写一下最近在学习的,易快速上手的sklearn吧。 sklearn入门 scikit-learn,又写作sklearn,是一个开源的基于python语言的机器学习工具包。...常用决策树算法: ID3算

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 43,900
精华内容 17,560
关键字:

常用的决策树算法