决策树--很详细算法介绍.ppt

* * * * * * * * * * 计算各属性的信息增益 * * 第四步：决策树 * * 案例2：银行违约率 * * * * 案例3 对电信客户的流失率分析 * * 数据仓库 条件属性 类别属性 客户是否流失 案例4：在银行中的应用 * * 案例5：个人信用评级 * * 个人信用评级决策树 （五）其他算法 * C4.5与C5.0算法 Gini Index算法 CART算法 PRISM算法 CHAID算法 * 1、C4.5与C5.0算法 * C5.0算法则是C4.5算法的修订版 ，适用在处理大数据集，采用Boosting（提升）方式提高模型准确率，又称为Boosting Trees，在软件上的计算速度比较快，占用的内存资源较少。 * 类别属性的信息熵 2、Gini Index算法 * ID3 and PRISM适用于类别属性的分类方法。 Gini Index能数值型属性的变量来做分类。着重解决当训练集数据量巨大，无法全部放人内存时，如何高速准确地生成更快的，更小的决策树。 * 集合T包含N个类别的记录，那么其Gini指标就是 如果集合T分成两部分N1 和 N2。则此分割的Gini就是 提供最小Gini split就被选择作为分割的标准(对于每个属性都要经过所有可以的分割方法)。 Gini Index算法 * * 案例：在汽车销售中的应用 * * * * * * N N Y Y Y N Y Y Y N N N 3、CART算法 * 由Friedman等人提出，1980年以来就开始发展，是基于树结构产生分类和回归模型的过程，是一种产生二元树的技术。 CART与C4.5/C5.0算法的最大的区别是：其在每一个节点上都是采用二分法，也就是一次只能够有两个子节点，C4.5/5.0则在每一个节点上可以产生不同数量的分枝。 * * * 构建树的步骤： * * * * * * * * * * * * * * * * * * * 决策树(Decision Tree) * * 1、分类的意义 数据库 了解类别属性与特征 预测 分类模型— 决策树 分类模型— 聚类 一、分类(Classification) * * 数据库 分类标记 性别 年龄 婚姻 否 是 否 是 Female Male 35 ≧35 未婚 已婚 * 2、分类的技术 （1）决策树 * （2）聚类 * 3、分类的程序 * 模型建立(Model Building) 模型评估(Model Evaluation) 使用模型(Use Model) * 决策树分类的步骤 * 数据库 * 训练样本(training samples) 建立模型 测试样本(testing samples) 评估模型 例： * 资料 训练样本 婚姻 年龄 家庭 所得 否 是 否 是 未婚 已婚 35 ≧35 低 高 否 小康 1.建立模型 测试样本 2.模型评估 错误率为66.67% 修改模型 3.使用模型 * 4、分类算法的评估 * 预测的准确度：指模型正确地预测新的或先前未见过的数据的类标号的能力。 训练测试法(training-and-testing) 交叉验证法(cross-validation) 例如，十折交叉验证。即是将数据集分成十分，轮流将其中9份做训练1份做测试，10次的结果的均值作为对算法精度的估计，一般还需要进行多次10倍交叉验证求均值，例如10次10倍交叉验证，更精确一点。 * * * 速度：指产生和使用模型的计算花费。 建模的速度、预测的速度 强壮性：指给定噪声数据或具有缺失值的数据，模型正确预测的能力。 可诠释性：指模型的解释能力。 * * 决策树归纳的基本算法是贪心算法，它以自顶向下递归各个击破的方式构造决策树。 贪心算法：在每一步选择中都采取在当前状态下最好/优的选择。 在其生成过程中，分割方法即属性选择度量是关键。通过属性选择度量，选择出最好的将样本分类的属性。 根据分割方法的不同，决策树可以分为两类：基于信息论的方法（较有代表性的是ID3、C4.5算法等）和最小GINI指标方法（常用的有CART、SLIQ及SPRINT算法等）。 二、决策树(Decision Tree) （一）决策树的结构 * 根部节点(root node) 中间节点(non-leaf node) (代表测试的条件) 分支(branches) (代表测试的结果) 叶节点(leaf node) (代表分类后所获得的分类标记) * * * （二）决策树的形成 例： * 根部节点 中间节点 停止分支 ？ * （三）ID3算法(C4.5,C5.0) * * Quinlan(1979)提出，以Shannon(1949)的信息论为依据。 ID3算法的属性选择度量就是使用信息增益，选择最高信息增益的属