您好,欢迎访问代理记账网站
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

Ensemble Learning

Ensemble Learning

1 高级集成技术

1.0 决策树

  • 元素:

    • 根结点:包含样本的全集
    • 内部节点:对应特征属性测试
    • 叶节点:代表决策结果
  • 决策树构建一个二叉树来分割数据,预测时,在树的内部节点处用某一属性值进行判断,根据判断结果决定进入哪个分支节点,每一步都会选择能够最大化叶节点纯度的规则,直到到达叶节点处,得到分类结果。

  • 叶子纯度

    • Entropy信息熵:

      • E n t r o p y ( p ) = − ∑ i n p i l o g ( p i ) Entropy(p) = - \sum_i^np_ilog(p_i) Entropy(p)=inpilog(pi)

      • n是分类个数

      • 信息的纯度与信息熵成反比:

        • 信息熵越大,信息量越大,信息越杂乱,纯度越低。
        • 信息熵越小,信息量越小,信息越规整,纯度越高。
  • ID3: 最早提出的决策树算法,他就是利用信息增益来选择特征的,ID3 算法会选择信息增益最大的属性来作为属性的划分。

    • 过程

      • 特征选择
        • 决定了使用哪些特征来判断,筛选出跟分类结果相关性较高的特征,准则:信息增益
      • 决策树生成
        • 选择好特征后,从根节点触发,对节点计算所有特征的信息增益,选择增益最大的特征作为节点特征,根据该特征的不同取值建立子节点,对每个子节点使用相同的方式生成新的子节点,直到信息增益很小或者没有特征可以选择为止。
    • G a i n ( S , A ) = E n t r o p y ( S ) − ∑ v ∈ V ( A ) S v S E n t r o p y ( S v ) Gain(S,A)=Entropy(S)-\sum_{v\in V(A)}\frac{S_v}{S}Entropy(S_v) Gain(S,A)=Entropy(S)vV(A)SSvEntropy(Sv)

    • 其中S是数据集,A是选择的属性

    • 即父节点的信息熵减去所有子节点的信息熵。

    • 缺点:倾向于选择取值多的属性作为根节点,ID3 没有剪枝策略,容易过拟合;

  • C4.5:

    • G a i n R ( S , A ) = G a i n ( S , A ) E n t r o p y ( A ) Gain_R(S,A)=\frac{Gain(S,A)}{Entropy(A)} GainR(S,A)=Entropy(A)Gain(S,A)

    • E n t r o p y ( A ) Entropy(A) Entropy(A)被称为是 A A A的固有值,和信息熵的计算公式一样,就是看属性 A A A的纯度,如果 A A A只含有少量的取值的话,那么 A A A的纯度就比较高,否则的话,的 A A A取值越多, A A A的纯度越低, E n t r o p y ( A ) Entropy(A) Entropy(A) 的值也就越大,因此,最后得到的信息增益率就越低。

    • 是在信息增益的基础之上乘上一个惩罚参数。特征个数较多时,惩罚参数较小;特征个数较少时,惩罚参数较大。

    • C4.5并不是直接选择增益率最大的属性作为划分属性,而是之前先通过一遍筛选,先把信息增益低于平均水平的属性剔除掉,之后从剩下的属性中选择信息增益率最高的

    • 剪枝

      • 预剪枝:在节点划分前来确定是否继续增长,预剪枝不仅可以降低过拟合的风险而且还可以减少训练时间,但另一方面它是基于“贪心”策略,会带来欠拟合风险。
      • 后剪枝:在已经生成的决策树上进行剪枝,从而得到简化版的剪枝决策树。
    • 优点:

      • ID3 的改进版,他不是直接使用信息增益,而是引入“信息增益比”指标作为特征的选择依据。
      • 加入了剪枝技术,防止过拟合
      • 对连续的属性进行离散化处理,使得C4.5可以处理连续属性的情况,而ID3只能处理离散属性
      • 允许缺失值存在
    • 缺点:效率较低,

  • CART(Classification and Regression Tree): 即可以用于分类,也可以用于回归问题。CART 算法使用了基尼系数取代了信息熵模型。

    • ID3生成的决策树是多叉树,只能处理分类不能处理回归,C4.5可以将连续的属性离散化,但是只能处理分类问题。而CART(classification and regression tree)分类回归树算法,既可用于分类也可用于回归

    • ID3中使用了信息增益选择特征,增益大优先选择。C4.5中,采用信息增益率选择特征,解决了因特征值多导致信息增益大的问题。CART分类树算法使用基尼系数选择特征,基尼系数代表了模型的不纯度,基尼系数越小,不纯度越低,特征越好。这和信息增益(率)相反。

    • 首先定义基尼系数:

      • 叶节点 ℓ \ell 上的数据属于类别c的比例为

      • p c ( ℓ ) = 1 ∣ ℓ ∣ ∑ ( x , y ) ∈ ℓ I y = c p_c(\ell)=\frac{1}{|\ell|}\sum_{(x,y)\in\ell}I_{y=c} pc()=1(x,y)Iy=c

      • 基尼值(Gini index):

        • G i n i ( ℓ ) = ∑ c ∈ C p c ( ℓ ) ( 1 − p c ( ℓ ) ) = 1 − ∑ i = 1 n p c ( ℓ ) 2 Gini(\ell)=\sum_{c\in C}p_c(\ell)(1-p_c(\ell))\\ =1-\sum_{i=1}^np_c(\ell)^2 Gini()=cCpc()(1pc())=1i=1npc()2

        • Gini(l)越小,则数据集D的纯度越高。

      • 基尼系数(Gini index):

        • 对于样本D,个数为|D|,根据特征A 是否取某一可能值a,把样本D分成两部分 D 1 , D 2 D1,D2 D1,D2,故CART建立的是二叉树

        • G i n i I n d e x ( D ∣ A = a ) = ∣ D 1 ∣ ∣ D ∣ G i n i ( D 1 ) + D 2 D G i n i ( D 2 ) GiniIndex(D|A=a)=\frac{|D_1|}{|D|}Gini(D_1)+\frac{D_2}{D}Gini(D_2) GiniIndex(DA=a)=DD1Gini(D1)+DD2Gini(D2)

    • 处理连续和离散特征

      • 连续特征:将连续的特征离散化。区别在选择划分点时,C4.5是信息增益率,CART是基尼系数。
      • 离散特征:不停的二分离散特征
    • 剪枝:

      • 前剪枝:在构造树的过程中就知道哪些节点可以剪掉
      • 后剪枝:指构造出完整的决策树之后再来考查哪些子树可以剪掉
        • 代价复杂性剪枝、最小误差剪枝、悲观误差剪枝等等

1.1 Stacking

  • 将数据分为训练集、验证集和测试集,使用多个模型对训练集和验证集进行交叉验证,多个模型对验证集进行预测,多个模型预测的结果stack在一起作为新模型的训练集,多个模型对测试集的预测结果stack在一起作为新模型的测试集。在第二层再使用新的模型进行训练和预测

1.2 Bagging

  • Bagging背后的想法是结合多个模型的结果(例如,所有决策树)来获得泛化的结果

  • Bagging对多个模型取平均,可以降低模型的方差,适用于 High Variance & Low Bias 的模型。

  • 为了对多个模型取平均,必须学习不同的东西,于是使用bootstrap进行有放回抽样,这样做的目的是使输入数据不重复。

  • 对于分类问题:使用不同的模型进行投票

  • 对于回归问题:对不同模型的预测结果取平均值

  • 效果比使用boosting要好,因为决策树是相关的

  • 如果我们计算正相关变量(相关系数$\rho $)的均值的方差可以得到
    1 n 2 E [ ( ∑ i = 1 n X i − μ ) 2 ] = ρ σ 2 + 1 − ρ n σ 2 \frac{1}{n^2}E\big[\big(\sum_{i=1}^nX_i-\mu\big)^2\big] = \rho\sigma^2+\frac{1-\rho}{n}\sigma^2 n21E[(i=1nXiμ)2]=ρσ2+n1ρσ2

  • n → ∞ n\rightarrow \infty n 上式只剩下第一项,如果想要模型表现得好,那么我们的模型必须是无偏而且不相关的(独立的)。

    • 如果模型独立,多个模型的平均: V a r ( 1 n ∑ i = 1 n X i ) = 1 n 2 V a r ( ∑ i = 1 n X i ) = σ 2 n Var(\frac{1}{n}\sum_{i=1}^nX_i)=\frac{1}{n^2}Var(\sum_{i=1}^nX_i)=\frac{\sigma^2}{n} Var(n1i=1nXi)=n21Var(i=1nXi)=nσ2 可以降低方差
  • 典型代表:随机森林

1.2.1 Random Forest

  • 随机森林是一种由很多决策树构成的集成算法,不同决策树之间没有关联,一种bagging方法
  • 步骤:
    • Step1: 对样本有放回随机抽样,训练决策树
    • Step2: 随机选取属性做为节点的分裂属性,取一个长度为m的子集, m ≤ p m\leq p mp m ∈ [ 1 , p ] m\in [1,\sqrt{p}] m[1,p ], p p p 是feature的数目,这个子集决定我们如何将决策树分裂。
    • Step3: 重复Step2,直到不能再分裂
    • Step4: 从Step1重新开始,建立大量决策树形成森林
  • 优点:
    • 可以用于高维数据,不需要降维,不需要特征选择
    • 可以判断特征的重要程度,以及不同特征之间是否互相影响
    • 不容易过拟合
    • 训练速度快,实现简单
    • 对不平衡数据集来说,RF可以平衡误差
    • 如果有很大一部分特征遗失,RF仍可以维持精准度
  • 缺点:
    • 在某些噪音加大的分类或回归问题上会过拟合
    • 对于有不同取值的属性的数据,取值划分较多的属性会对随机森林产生更大的影响,所以随机森林在这种数据上产出的属性权值是不可信的

1.3 Boosting

  • 三个臭皮匠顶个诸葛亮

  • 思想:弱学习算法 → \rightarrow 强学习算法。 从弱学习算法出发,得到一系列的弱分类器,通过改变训练数据的权值分布,然后组合弱分类器,得到一个强分类器

  • 在每一轮学习之前,如何改变训练数据的权值分布?

    • Adaboost算法的做法是:**提高那些被前一轮弱分类器错误分类样本的权值,而降低那些被正确分类样本的权值。**如此,那些没有得到正确分类的样本,由于其权值加大而受到后一轮的弱分类器的更大关注。
  • 如何将一组弱分类器组合成一个强分类器?

    • AdaBoost采取加权多数表决的方法。具体地:加大分类误差率小 的弱分类器的权值,使其在表决中起较大的作用;减小分类误差率大的弱分类器的权值,使其在表决中起较小的作用。

1.3.1 AdaBoost

  • AdaBoost为什么能够提升学习精度?
  • 如何解释AdaBoost算法?
  • Boosting方法更具体的实例-Boosting Tree。

分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进