决策树理论--Decision tree-蒲公英云

决策树理论--Decision tree

电玩女神 2022-05-24 09:25 298阅读 0赞

决策树面试被提及的题目：

1、决策树的原理：

    从根结点开始，对实例的某一特征进行测试，根据测试的结果，将实例分配到其子结点；每一个子结点对应着该特征的一个取值。如此递归地对实例进行测试并分配，直至达到叶结点。最后将实例分配到叶结点的类中。

2、决策树的过程（步骤）：

    决策树学习通常包括3个步骤：特征选择、决策树的生成和树的剪枝。

附：决策树的选择特征包括哪些，和各自的优缺点：

     信息增益，信息增益比，基尼系数

3、决策树的终止条件：

    节点中的样本个数小于预定的阈值，或样本集的基尼指数小于预定值，或者没有更多的特征；

4、决策树如何防止过拟合：

    树的剪枝；

5、决策树的生成：

       经典的有：ID3的生成算法、C4.5的生成算法、

1）ID3的生成算法

        思路：ID3算法的核心是在决策树各个结点上应用信息增益准则选择特征，递归地构建决策树。具体方法是：从根结点开始，对结点计算所有可能的特征的信息增益，选择信息增益最大的特征作为结点的特征，由该特征的不同取值建立子节点；再对子节点递归地调用以上方法，构建决策树；直到所有特征的信息增益均很小或没有特征可选为止。最后得到一个决策树。  
        算法如下：  
                    输入：训练数据集D，特征集A，阈值e  
                    SS：决策树T  
                （1）若D所有实例属于同一类Ck，则T为单结点树，并将类Ck作为该结点的类的标记，返回T；  
                （2）若A =空，则 T为单结点树，并将D中实例最大的类Ck作为该结点的类标记，返回T；  
                （3） 否则，按照信息增益算法计算A中各特征对D的信息增益，选择信息增益最大的特征Ag；  
                （4）如果银的信息增益小于阈值e，则置T为单节点树，并将D中实例数最大类Ck作为该节点的类标记，返回T；  
                （5）否则，对Ag的每一个可能取值ai，依Ag = ai 将D分割为若干非空子集Di，将Di中实例数最大的类作为标记，构建子节点，由结点以其子节点构成树T，返回T；
                （6）对第我个结点，以D为训练集，以A-\{Ag\}为特征集，递归地调用1~5    ，得到子树Ti，返回Ti

2）C4.5的生成算法：

        思路：C4.5与ID3算法相似，    C4.5    算法对ID3算法进行了改进，C4.5在生成的过程中，用信息增益比来选择特征。  
    1，为什么选择信息增益比？  
           以信息增益作为划分训练数据集的特征，存在偏向于选择值较多的特征的问题，使用信息增益比可以对这一问题进行校正。具体是再信息增益除以关于某个特征的熵

6，决策树的剪枝：

具体地，剪枝从已生成的树山剪掉一些子树或叶结点，并将其根结点或父节点作为新的叶节点，从而简化树模型。  
决策树剪枝往往通过极小化决策树整体的损失函数或代价函数来实现。

算法思想：

        输入：生成算法产生的整个树T，参数a；  
        输出：修剪后子树Ta；  
             （1）计算每个结点的jingyansha经验熵
            （2）递归地从树的叶结点先杀向上回缩。  
                            设一组叶节点回缩到其父节点之前与之后的整体树分别为Ta 和 Tb，其对应的损失函数值分别为Ca(Ta) 与Ca(Tb)，如果Ca(Ta) <= Ca(Tb),则进行剪枝，即将父节点变为新的叶节点。
                （3）返回(2),直到不能继续为止，得到损失函数最小的子树Ta。