人工智能-决策树.pptVIP

IT在线教育领导品牌 EDUCATION TO CREATE A BRIGHT FUTURE 决策树(Decision Tree)是在已知各种情况发生概率的基础上，通过构建决策树来 进行分析的一种方式，是一种直观应用概率分析的一种图解法；决策树是一种预 测模型，代表的是对象属性与对象值之间的映射关系；决策树是一种树形结构， 其中每个内部节点表示一个属性的测试，每个分支表示一个测试输出，每个叶节 点代表一种类别；决策树是一种非常常用的有监督的分类算法。 决策树的决策过程就是从根节点开始，测试待分类项中对应的特征属性，并按照 其值选择输出分支，直到叶子节点，将叶子节点的存放的类别作为决策结果。 决策树分为两大类：分类树和回归树，前者用于分类标签值，后者用于预测连续 值，常用算法有ID3、C4.5、CART等 * 什么是决策树 IT在线教育领导品牌 EDUCATION TO CREATE A BRIGHT FUTURE 决策树算法的重点就是决策树的构造；决策树的构造就是进行属性选择度量，确定各个特征 属性之间的拓扑结构(树结构)；构建决策树的关键步骤就是分裂属性，分裂属性是指在某个节 点按照某一类特征属性的不同划分构建不同的分支，其目标就是让各个分裂子集尽可能的'纯 '(让一个分裂子类中待分类的项尽可能的属于同一个类别)。 构建步骤如下: 将所有的特征看成一个一个的节点； 遍历每个特征的每一种分割方式，找到最好的分割点；将数据划分为不同的子节点，eg： N1、 N2....Nm；计算划分之后所有子节点的'纯度'信息； 对第二步产生的分割，选择出最优的特征以及最优的划分方式；得出最终的子节点: N1、N2....Nm 对子节点N1、N2....Nm分别继续执行2-3步，直到每个最终的子节点都足够'纯'。 * 决策树构建过程 IT在线教育领导品牌 EDUCATION TO CREATE A BRIGHT FUTURE 根据特征属性的类型不同，在构建决策树的时候，采用不同的方式，具体如下： 属性是离散值，而且不要求生成的是二叉决策树，此时一个属性就是一个分支 属性是离散值，而且要求生成的是二叉决策树，此时使用属性划分的子集进行测试，按照 “属于此子集”和“不属于此子集”分成两个分支 属性是连续值，可以确定一个值作为分裂点split_point，按照>split_point和 <=split_point生成两个分支 * 决策树特征属性类型 IT在线教育领导品牌 EDUCATION TO CREATE A BRIGHT FUTURE 决策树算法是一种“贪心”算法策略，只考虑在当前数据特征情况下的最好分割 方式，不能进行回溯操作。 对于整体的数据集而言，按照所有的特征属性进行划分操作，对所有划分操作的 结果集的“纯度”进行比较，选择“纯度”越高的特征属性作为当前需要分割的 数据集进行分割操作，持续迭代，直到得到最终结果。决策树是通过“纯度”来 选择分割特征属性点的。 * 决策树分割属性选择 IT在线教育领导品牌 EDUCATION TO CREATE A BRIGHT FUTURE 决策树量化纯度 * 决策树的构建是基于样本概率和纯度进行构建操作的，那么进行判断数据集是否 “纯”可以通过三个公式进行判断，分别是Gini系数、熵(Entropy)、错误率，这 三个公式值越大，表示数据越“不纯”；越小表示越“纯”；实践证明这三种公 式效果差不多，一般情况使用熵公式 P?1?? 7 /10 ? 0.7;可以偿还概率 P?2?? 3 /10 ? 0.3;无法偿还概率 n P?i? ? i?1 2 Gini ? 1? Pi n ? i?1 2 Pi log H(Entropy) ? ? ? ? ?? n ? ? ? ? ? max P i i?1 Error ? 1? IT在线教育领导品牌 EDUCATION TO CREATE A BRIGHT FUTURE 当计算出各个特征属性的量化纯度值后使用信息增益度来选择出当前数据集的分 割特征属性；如果信息增益度的值越大，表示在该特征属性上会损失的纯度越大 ， 那么该属性就越应该在决策树的上层，计算公式为： 决策树量化纯度 Gain ? ? ? H?D?? H(D | A) Gain为A为特征对训练数据集D的信息增益，它为集合D的经验熵H(D)与特征A给 定条件下D的经验条件熵H(D|A)之差 * IT在线教育领导品牌 EDUCATION TO CREATE A BRIGHT FUTURE 决策树构建的过程是一个递归的过程，所以必须给定停止条件，否则过程将不会 进行停止，一般情况有两种停止条件： 当每个子节点只有一种类型的时候停止构建 当前节点中记录数小于某个阈值，同时迭代次数达到给定值时，停止构建过程