【机器学习】决策树算法讲述.ppt

第9章　决策树算法 * 9.5 应用实例分析 根据步骤B所求得的信息增益值,属性Temperature的信息增益值最大，故子分支三可以分得两个分支，决策树构造图3如图所示： 决策树构造图3 第9章　决策树算法 * 9.5 应用实例分析 C.分析图中的：rain下的分裂属性Temperature的两个子分支，其中t3：cool时，分支都属于反例n，故可以直接作为一个叶子节点no； 另一个t1：mild时，若假设Humidity为测试属性，则分支t1总的信息熵和测试属性Humidity信息量分别为： 0.918bit ＝ ＝0.666bit 则其信息增益为： 0.918－0.666=0.252bit 第9章　决策树算法 * 9.5 应用实例分析 若假设Windy为测试属性 ，则测试属性windy的信息量为： ＝ ＝0.666bit 其信息增益为： 0.918-0.666=0.251bit. 由上分析可得Humidity和windy的信息增益是相同的，又因为在t1分支的元组中，p元组的比例比n元组的大，所以，最终得到的决策树图如图所示： 第9章　决策树算法 * 9.2.3 CART算法 Gini指标主要是度量数据划分或训练数据集D的不纯度为主，系数值的属性作为测试属性，Gini值越小，表明样本的“纯净度”越高。Gini指标定义为如下公式： 第9章　决策树算法 * 9.2.3 CART算法 由于二叉树不易产生数据碎片，精确度往往也会高于多叉树，所以在CART算法中，统计学家们采用了二元划分，在分支节点上进行Gini值的测试，如果满足一定纯度则划分到左子树，否则划分到右子树，最终生成一棵二叉决策树。 在只有二元分裂的时候，对于训练数据集D中的属性A将D分成的D1和D2，则给定划分D的Gini指标如下公式所示： 第9章　决策树算法 * 9.2.3 CART算法 对于离散值属性，在算法中递归的选择该属性产生最小Gini指标的子集作为它的分裂子集。 对于连续值属性，必须考虑所有可能的分裂点。其策略类似于上面ID3中介绍的信息增益处理方法，可以用如下公式所示： 第9章　决策树算法 * 9.2.3 CART算法 CART算法在满足下列条件之一，即视为叶节点不再进行分支操作。 （1）所有叶节点的样本数为1、样本数小于某个给定的最小值或者样本都属于同一类的时候； （2）决策树的高度达到用户设置的阈值，或者分支后的叶节点中的样本属性都属于同一个类的时候； （3）当训练数据集中不再有属性向量作为分支选择的时候。 第9章　决策树算法 * 9.2.4 PUBLIC算法 前面几个小节的决策树算法都是先建树再剪枝。PUBLIC( Pruning and Building Integrated in Classification)算法[8,17]将建树、剪枝结合到一步完成，即是预剪枝，在建树阶段不生成会被剪枝的子树，从而大大提高了效率 。 PUBLIC算法的建树是基于SPRINT方法、对其决策树的剪枝使用的是基于最小编码代价的MDL算法，但MDL原则不能直接应用 。 第9章　决策树算法 * 9.2.5 SLIQ算法 SLIQ (Supervised Learning In Quest)算法利用3种数据结构来构造树，分别是属性表、类表和类直方图。 SLIQ算法在建树阶段，对连续属性采取预排序技术与广度优先相结合的策略生成树，对离散属性采取快速的求子集算法确定划分条件。具体步骤如下： Step1 建立类表和各个属性表，并且进行预排序，即对每个连续属性的属性表进行独立排序，以避免在每个节点上都要给连续属性值重利用新排序； Step 2 如果每个叶节点中的样本都能归为一类，则算法停止；否则转(3) ； Step 3利用属性表寻找拥有最小Gini值的划分作为最佳划分方案。 第9章　决策树算法 * 9.2.5 SLIQ算法 Step4 根据第3步得到的最佳方案划分节点，判断为真的样本划归为左孩子节点，否则划归为右孩子节点。这样，(3) (4)步就构成了广度优先的生成树策略。 Step 5 更新类表中的第二项，使之指向样本划分后所在的叶节点。 Step 6 转到步骤(2)。 第9章　决策树算法 * 9.2.6 SPRINT算法 SPRINT算法是对SLIQ算法的改进，其目的有两个： 一是为了能够更好的并行建立决策树，二是为了使得决策树T适合更大的数据集。 SPRINT (Scalable Parallelizable Induction of Classification Tree)算法是一种可扩展的、可并行的归纳决策树，它完全不受内存限制，运行速度快，且允许多个处理器协同创建一个决策树模型。 第9章　决策树算法 * 9.2