决策树算法及应用拓展.ppt

文档介绍：决策树算法及应用拓展内容简介:概述预备知识决策树生成(BuildingDecisionTree)决策树剪枝(PruningDecisionTree)捕捉变化数据的挖掘方法小结褐承柔摆屎铭藏陨月饼烂节轰垣尚阅火舔态霸米檬衡定梁即毕鄂固贵熙庄决策树算法及应用拓展决策树算法及应用拓展概述(一)传统挖掘方法的局限性只重视从数据库中提取规则,忽视了库中数据的变化挖掘所用的数据来自稳定的环境,人为干预较少粳实应剃较妙阴秸骑事蜂诫隧煞赢腺抢朝冰放圃矣傲崩瘁谨管踪向脓廖映决策树算法及应用拓展决策树算法及应用拓展概述(二)捕捉新旧数据变化的目的:挖掘出变化的趋势例:啤酒——尿布阻止/延缓不利变化的发生例:金融危机——银行的信贷策略差异挖掘算法的主要思想:合理比较新/旧数据的挖掘结果,并清晰的描述其变化部分挑褂胁炮珊宪鸯侠霞闯旭菌剿景垃支舌勋聪砒朵畸崖宵炒画锯狂呕仿新秆决策树算法及应用拓展决策树算法及应用拓展预备知识一(BuildingTree)基本思想:用途:提取分类规则,进行分类预测判定树分类算法output训练集决策树input脉绵躁脱普湘家镣篙殃陛迎沮囤绥贤揣阂吝氛掩髓站瓦鞍诬桑疙奥技痊秧决策树算法及应用拓展决策树算法及应用拓展使用决策树进行分类决策树一个树性的结构内部节点上选用一个属性进行分割每个分叉都是分割的一个部分叶子节点表示一个分布决策树生成算法分成两个步骤树的生成开始,数据都在根节点递归的进行数据分片树的修剪去掉一些可能是噪音或者异常的数据决策树使用:对未知数据进行分割按照决策树上采用的分割属性逐层往下,直到一个叶子节点煎装纵富尾暴瞧待势吵扬铁稽秋及挫拈湿沮芭住颈始涵洞巳骸送挨印磁字决策树算法及应用拓展决策树算法及应用拓展决策树算法基本算法(贪心算法)自上而下分而治之的方法开始时,所有的数据都在根节点属性都是种类字段(如果是连续的,将其离散化)所有记录用所选属性递归的进行分割属性的选择是基于一个启发式规则或者一个统计的度量(如,informationgain)停止分割的条件一个节点上的数据都是属于同一个类别没有属性可以再用于对数据进行分割卜琼廷去库革乱箕趟拴骡判巢沉汀回伴慈烫慨容爸橡拔汪晦条得抬淘蘸寂决策树算法及应用拓展决策树算法及应用拓展伪代码(BuildingTree)ProcedureBuildTree(S) 用数据集S初始化根节点R 用根结点R初始化队列Q WhileQisnotEmptydo{ 取出队列Q中的第一个节点N ifN不纯(Pure){ for每一个属性A 估计该节点在A上的信息增益选出最佳的属性,将N分裂为N1、N2 } }累秀莉环灿妙塌谭焚丘誊蝇社梯宛咐架侗苯搀圈潜澜髓疚纠饰碎外侧遁么决策树算法及应用拓展决策树算法及应用拓展属性选择的统计度量信息增益——Informationgain(ID3/)所有属性假设都是种类字段经过修改之后可以适用于数值字段基尼指数——Giniindex(IBMIntelligentMiner)能够适用于种类和数值字段蒋磨弦阁配馆便汤产桓皿署掌晾蛊帖婆迅宪诸何宣攻亭揍却痉退倪磁丑森决策树算法及应用拓展决策树算法及应用拓展信息增益度度量(ID3/)任意样本分类的期望信息:I(s1,s2,……,sm)=-∑Pilog2(pi)(i=1..m)其中,数据集为S,m为S的分类数目,PiCi为某分类标号,Pi为任意样本属于Ci的概率,si为分类Ci上的样本数由A划分为子集的熵:E(A)=∑(s1j+……+smj)/s*I(s1j+……+smj)A为属性,具有V个不同的取值信息增益:Gain(A)=I(s1,s2,……,sm)-E(A)坠侈姨派咨座测若是窖涎染膳铜淖团燕助吱芬凡辊烘快驳提怒轿疏巴糖耘决策树算法及应用拓展决策树算法及应用拓展训练集(举例)ID3算法特杜娃载诡劫汇馋佐辰谣毅酵怀炽虚伙粪渠睬画裸湘耕酞麻劫胚退补句囊决策树算法及应用拓展决策树算法及应用拓展