决策树

作者: 张伟松 | 来源:发表于2017-12-18 18:17 被阅读71次

    模型

    决策树的学习目标是根据给定的训练数据集,建立一个决策树,能够对实例进行正确分类。决策树算法通常是递归选择最优特征,使得这个特征能够最好的对数据进行分割。
    一个决策树从根节点开始构建,选择最优特征,将数据分为K组,对每一个子组,再次从其他特征总选择最优的,直至达到退出条件,或数据基本不可再分。
    生成的决策树可能出现过拟合现象,则需要剪枝。剪枝的基本原理是去除不必要的叶子节点,使得决策树从繁至简。

    特征选择

    如何评价一个特征是最优特征呢?

    熵和条件熵

    每一个特征对应一定的混乱程度,称为变量的熵,记作H(X)
    H(x)=-∑Pi·log(Pi)
    其中Pi是随机变量X可取的第i个值,熵值H(P)大于零小于等于log(N)
    条件熵H(Y|X)定义为X给定条件下Y的条件概率分布的熵对X的数学期望;
    如果说X的熵H(X)表示随机变量X的变化程度,H(Y|X)则表示,已知X时Y的变化程度,也就是在X的限定条件下Y的混乱程度。

    信息增益

    信息增益g(D,A) = H(D)-H(D|A)
    这句话很好理解:特征值D有原始混乱程度,在引入新的信息A之后,D的混乱程度有所减小,信息增益表示特征A使得数据集D混乱程度减小的程度。信息增益值越大,则表示这一特征A越是具有分类能力,越是重要。
    信息增益有时会由于取值问题产生偏差,故引入了信息增益比这一概念,
    信息增益比是对信息增益的优化。

    算法

    生成决策树的最终结果应该是特征值和该特征值取值的

    ID3

    此算法即根据信息增益迭代计算在每个节点上,每个特征值的信息增益,从而选择出最佳特征,作为此节点的类别。

    1. 若数据集中所有实例属于同一类,则T为单节点树,返回T
    2. 若特征为空,将数据集T记为D中最大的类,返回该类
    3. 计算A中各个特征的信息增益,选择信息增益最大的特征Ag
    4. 若Ag的值小于阈值,回到2
    5. 对A的每一个可能值将D划分为非空子集,取其中最大的类作为标记
    6. 对第i个子节点,以Di为训练集,以A-{Ai}为特征集,递归调用1~5

    C4.5

    C4.5是用信息增益比代替了ID3中第三条的信息增益,其他都一样。


    以上的算法用于生成分类决策树,对于每个可取的特征值,存在固定的类别,决策树还可以生成回归模型,对于取值在连续空间上的特征进行分类,选取最优分割点,将数据分成2类,CART算法生成的决策树树为二叉决策树。

    CART

    CART的特征节点满足对指定变量,取值为是或者否。一般地,左子树为是的分支,右子树为否的分支。
    回归决策树的表达式
    f(x) = ∑Cm·I(x∈Rm)
    表达着这样的意义:回归树首先生成一个个特征,在特定的特种中选取一个最优分割点;模型表示在输入数据属于该单元时,返回该单元的值。
    由于对于某一个固定的变量,其最优分割点是所有输入实例Xi对应的输出Yi 的算数平均值。选取最优特征和该特征的最优分割点在于求最小化值:
    min[min∑(Yi-C1)^2 + min∑(Yi-C2)^2]

    剪枝

    对于CART树,剪枝的核心是从当前回归树的所有子树种选取【整体损失函数最小,也就是预测能力最强的】最优决策树。

    相关文章

      网友评论

          本文标题:决策树

          本文链接:https://www.haomeiwen.com/subject/miymwxtx.html