交通数据分析 交通数据分析 26 决策树算法.pptVIP

* * 决策树算法 1 决策树运作过程 目录 决策树简介 2 小结 3 决策树方法在分类、预测、规则提取等领域有着广泛应用。在20世纪70年代后期和80年代初期，机器学习研究者J.Ross Quinilan提出了ID3算法以后，决策树在机器学习、数据挖掘邻域得到极大的发展。Quinilan后来又提出了C4.5，成为新的监督学习算法的性能比较基准。1984年几位统计学家提出了CART分类算法。ID3和ART算法大约同时被提出，但都是采用类似的方法从训练元组中学习决策树。 发展历史 常用的决策树算法如下表。 常用决策树算法 决策树算法 算法描述 ID3算法 其核心是在决策树的各级节点上，使用信息增益方法作为属性的选择标准，来帮助确定生成每个节点时所应采用的合适属性。 C4.5算法 C4.5决策树生成算法相对于ID3算法的重要改进是使用信息增益率来选择节点属性。C4.5算法可以克服ID3算法存在的不足：ID3算法只适用于离散的描述属性，而C4.5算法既能够处理离散的描述属性，也可以处理连续的描述属性。 CART算法 CART决策树是一种十分有效的非参数分类和回归方法，通过构建树、修剪树、评估树来构建一个二叉树。当终结点是连续变量时，该树为回归树；当终结点是分类变量，该树为分类树。 1 决策树运作过程 目录 决策树简介 2 小结 3 以决策树算法中经典的ID3算法为例，基本流程如下： 决定测试属性：选择当前样本集中具有最大信息增益值的属性作为测试属性。 划分样本集：依据测试属性的取值进行，测试属性有多少不同取值就将样本集划分为多少子样本集。 生成叶子节点：在决策树上相应于该样本集的节点长出新的叶子节点。 打球数据集： 决策树： 基本流程 日期 天气 温度(华氏度) 湿度 起风 打球? 1 Sunny 85 85 F No 2 Sunny 80 90 T No 3 Overcast 83 78 F Yes 4 Rainy 70 96 F Yes 5 Rainy 68 80 F Yes 6 Rainy 65 70 T No 7 Overcast 64 65 T Yes 8 Sunny 72 95 F No 9 Sunny 69 70 F Yes 10 Rainy 75 80 F Yes 11 Sunny 75 70 T Yes 12 Overcast 72 90 T Yes 13 Overcast 81 75 F Yes 14 Rainy 71 80 T No 天气 Yes 湿度 风 Yes No No Yes 晴 阴 雨 75 =75 是 否 决策树算法在选择属性先后顺序时的标准如下： 在拆分过程中，当叶节点只拥有单一类别时，将不必继续拆分。 目标是寻找较小的树，希望递归过程尽早停止。 当前最好的拆分属性产生的拆分中目标类的分布应该尽可能地单一（单纯），多数类占优。 如果能测量每一个节点的纯度，就可以选择能产生最纯子节点的那个属性进行拆分。 通常按照纯度的增加来选择拆分属性。 属性选择 纯度的基本概念如下： 当样本中没有两项属于同一类：0 当样本中所有项都属于同一类：1 于是，最佳拆分可以转化为选择拆分属性使纯度度量最大化的优化问题。 纯度 用于评价拆分分类目标变量的纯度度量如下： 基尼(Gini，总体发散性) CART决策树 熵(entropy，信息量) 信息增益(Gain) ID3决策树 信息增益率 C4.5和C5.0决策树 纯度 信息论中的熵是信息的度量单位，是一种 对属性“不确定性的度量”。属性的不确定性越大，把它搞清楚所需要的信息量也就越大，熵也就越大。 如果一个数据集D有N个类别，则该数据集的熵为： 打球数据集的熵： 熵 信息增益(gain)表示对纯度提升的程度。 若离散属性a有V个取值，则其信息增益为： 信息增益 天气属性的信息增益 晴：打球记录2条，不打球记录为3条 阴：打球记录4条，不打球记录0条 雨：打球记录3条，不打球记录2条 信息增益 计算得到天气属性的信息增益： 同理可以得到起风属性的信息增益： 0.048 ID3算法根据信息理论，采用划分后样本集的不确定性作为衡量划分好坏的标准，用信息增益值度量：信息增益值越大，不确定性越小。因此，ID3算法在每个非叶节点选择信息增益最大的属性作为测试属性。该属性使得对结果划分中的样本分类所需的信息最小，并反映划分的最小随机性。 信息增益 决策树算法的优缺点如下： 优点：