决策树资料专业知识讲座

主要内容决策树基本概念决策树算法决策树研究问题主要参照文献第1页第6章决策树决策树算法计数年纪收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1老中否优买假定公司搜集了左表数据，那么对于任意给定客人（测试样例），你能帮助公司将这位客人归类吗？即：你能预测这位客人是属于“买”计算机那一类，还是属于“不买”计算机那一类？又：你需要多少有关这位客人信息才能回答这个问题？决策树用途第2页第6章决策树计数年纪收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1老中否优买谁在买计算机？年纪？学生？信誉？买青中老否是优良不买买买不买决策树用途决策树算法第3页第6章决策树计数年纪收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1老中否优买谁在买计算机？年纪？学生？信誉？买青中老否是优良不买买买不买决策树用途决策树算法第4页第6章决策树决策树算法决策树表达决策树基本组成部分：决策结点、分支和叶子。年纪？学生？信誉？买青中老否是优良不买买买不买决策树中最上面结点称为根结点。是整个决策树开始。每个分支是一个新决策结点，或者是树叶子。每个决策结点代表一种问题或者决策.一般对应待分类对象属性。每个叶结点代表一种也许分类成果在沿着决策树从上到下遍历过程中，在每个结点都有一种测试。对每个结点上问题不一样测试输出造成不一样分枝，最后会达成一种叶子结点。这一过程就是利用决策树进行分类过程，利用若干个变量来判断属性类别第5页第6章决策树计数年纪收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1老中否优买决策树算法第6页第6章决策树计数年纪收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1老中否优买第1步计算决策属性熵决策属性“买计算机？”。该属性分两类：买/不买S1(买)=641S2（不买）=383S=S1+S2=1024P1=641/1024=0.6260P2=383/1024=0.3740I(S1,S2)=I(641,383)=-P1Log2P1-P2Log2P2=-(P1Log2P1+P2Log2P2)=0.9537决策树算法第7页第6章决策树计数年纪收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1老中否优买第2步计算条件属性熵条件属性共有4个。分别是年纪、收入、学生、信誉。分别计算不一样属性信息增益。决策树算法第8页第6章决策树计数年纪收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1老中否优买第2-1步计算年纪熵年纪共分三个组：青年、中年、老年青年买与不买百分比为128/256S1(买)=128S2（不买）=256S=S1+S2=384P1=128/384P2=256/384I(S1,S2)=I(128,256)=-P1Log2P1-P2Log2P2=-(P1Log2P1+P2Log2P2)=0.9183决策树算法第9页第6章决策树计数年纪收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1老中否优买第2-2步计算年纪熵年纪共分三个组：青年、中年、老年中年买与不买百分比为256/0S1(买)=256S2（不买）=0S=S1+S2=256P1=256/256P2=0/256I(S1,S2)=I(256，0)=-P1Log2P1-P2Log2P2=-(P1Log2P1+P2Log2P2)=0决策树算法第10页第6章决策树计数年纪收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1老中否优买第2-3步计算年纪熵年纪共分三个组：青年、中年、老年老年买与不买百分比为257/127S1(买)=257S2（不买）=127S=S1+S2=384P1=257/384P2=127/384I(S1,S2)=I(125，127)=-P1Log2P1-P2Log2P2=-(P1Log2P1+P2Log2P2)=0.9157决策树算法第11页第6章决策树计数年纪收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1老中否优买第2-4步计算年纪熵年纪共分三个组：青年、中年、老年所占百分比青年组384/1024=0.375中年组256/1024=0.25老年组384/1024=0.375计算年纪平均信息盼望E（年纪）=0.375*0.9183+0.25*0+0.375*0.9157=0.6877G（年纪信息增益）=0.9537-0.6877=0.2660（1）决策树算法第12页第6章决策树计数年纪收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1老中否优买第3步计算收入熵收入共分三个组：高、中、低E（收入）=0.9361收入信息增益=0.9537-0.9361=0.0176(2)决策树算法第13页第6章决策树计数年纪收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1老中否优买第4步计算学生熵学生共分二个组：学生、非学生E（学生）=0.7811年纪信息增益=0.9537-0.7811=0.1726（3）决策树算法第14页第6章决策树计数年纪收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1老中否优买第5步计算信誉熵信誉分二个组：良好，优秀E（信誉）=0.9048信誉信息增益=0.9537-0.9048=0.0453（4）决策树算法第15页第6章决策树计数年纪收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1老中否优买第6步计算选择节点年纪信息增益=0.9537-0.6877=0.2660（1）收入信息增益=0.9537-0.9361=0.0176（2）年纪信息增益=0.9537-0.7811=0.1726（3）信誉信息增益=0.9537-0.9048=0.0453（4）决策树算法第16页第6章决策树计数年纪收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128青中否良不买64青低是良买64青中是优买年纪青年中年老年买/不买买买/不买叶子决策树算法第17页第6章决策树计数年纪收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128青中否良不买64青低是良买64青中是优买青年买与不买百分比为128/256S1(买)=128S2（不买）=256S=S1+S2=384P1=128/384P2=256/384I(S1,S2)=I(128,256)=-P1Log2P1-P2Log2P2=-(P1Log2P1+P2Log2P2)=0.9183决策树算法第18页第6章决策树计数年纪收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128青中否良不买64青低是良买64青中是优买假如选择收入作为节点分高、中、低条件熵就是E： E(收入）=0.3333*0+0.5*0.9183+0.1667*0=0.4592Gain(收入)=I(128,256)-E(收入)=0.9183–0.4592=0.4591Gain就是计算信息增益I(0,128)=0百分比:128/384=0.3333I(64,128)=0.9183百分比:192/384=0.5I(64,0)=0百分比:64/384=0.1667注意决策树算法第19页第6章决策树计数年纪收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1老中否优买年纪青年中年老年学生买信誉叶子否是优良买不买买/不买买叶子叶子叶子决策树算法第20页第6章决策树ID3决策树建立算法1决定分类属性；2对目前数据表，建立一种节点N3假如数据库中数据都属于同一种类，N就是树叶，在树叶上标出所属类4假如数据表中没有其他属性能够考虑，则N也是树叶，按照少数服从多数标准在树叶上标出所属类别5不然，根据平均信息盼望值E或GAIN值选出一种最佳属性作为节点N测试属性6节点属性选定后，对于该属性中每个值：从N生成一种分支，并将数据表中与该分支有关数据搜集形成份支节点数据表，在表中删除节点属性那一栏假如分支数据表非空，则利用以上算法从该节点建立子树。决策树算法第21页第6章决策树决策树数据准备姓名年纪收入学生信誉电话地址邮编买计算机张三234000是良281-322-03282714Ave.M77388买李四342800否优713-239-78305606HollyCr78766买王二701900否优281-242-32222023BellBlvd.70244不买赵五18900是良281-550-0544100MainStreet70244买刘兰342500否优713-239-7430606HollyCt78566买杨俊278900否优281-355-7990233RiceBlvd.70388不买张毅389500否优281-556-0544399SugarRd.78244买。。。。。。。。原始表决策树算法第22页第6章决策树计数年纪收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买。。。整顿后数据表决策树数据准备Datacleaning 删除/减少noise，补填missingvaluesDatatransformation 数据标准化（datanormalization） 数据归纳（generalizedatatohigher-levelconceptsusingconcepthierarchies） 例如：年纪归纳为老、中、青三类 控制每个属性也许值不超出七种（最佳不超出五种）Relevanceanalysis 对于与问题无关属性：删 对于属性也许值大于七种又不能归纳属性：删决策树算法第23页第6章决策树决策树数据准备决策树算法处理连续属性值决策树算法比较适合处理离散数值属性。实际应用中属性是连续或者离散情况都比较常见。在应用连续属性值时，在一种树结点能够将属性Ai值划分为几个区间。然后信息增益计算就能够采取和离散值处理同样办法。标准上能够将Ai属性划分为任意数目标空间。C4.5中采取是二元分割（BinarySplit）。需要找出一种合适分割阈值。参照C4.5算法Top10algorithmsindataminingKnowledgeInformationSystem202314:1–37第24页第6章决策树决策树算法ID3算法小结ID3算法是一种典型决策树学习算法，由Quinlan于1979年提出。ID3算法基本思想是，以信息熵为度量，用于决策树节点属性选择，每次优先选用信息量最多属性，亦即能使熵值变为最小属性，以构造一颗熵值下降最快决策树，到叶子节点处熵值为0。此时，每个叶子节点对应实例集中实例属于同一类。第25页第6章决策树决策树算法ID3算法实际应用-在电信行业应用实例（1）通过ID3算法来实现客户流失预警分析，找出客户流失特性，以帮助电信公司有针对性地改善客户关系，避免客户流失利用决策树办法进行数据挖掘，一般有如下步骤：数据预处理、决策树挖掘操作，模式评定和应用。电信运行商客户流失有三方面含义：一是指客户从一种电信运行商转网到其他电信运行商，这是流失分析重点。二是指客户月平均消费量减少，从高价值客户成为低价值客户。三、指客户自然流失和被动流失。在客户流失分析中有两个关键变量：财务原因／非财务原因、积极流失／被动流失。客户流失能够对应分为四种类型：其中非财务原因积极流失客户往往是高价值客户。他们会正常支付服务费用，并容易对市场活动有所响应。这种客户是电信公司真正需要保住客户。第26页第6章决策树决策树算法ID3算法实际应用-在电信行业应用实例（2）数据预处理数据挖掘处理对象是大量数据，这些数据一般存放在数据库系统中（该顾客有关数据存放在其CRM中），是长期积累成果。但往往不适合直接挖掘，需要做数据预处理工作，一般包括数据选择(选择有关数据)、净化(消除冗余数据)、转换、归约等。数据预处理工作准备是否充足，对于挖掘算法效率乃至正确性都有关键性影响。该公司通过数年电脑化管理，已有大量客户个人基本信息(文中简称为客户信息表)。在客户信息表中，有很多属性，如姓名顾客号码、顾客标识、顾客身份证号码(转化为年纪)、在网时间（完工时间）、地址、职业、顾客类别、客户流失（顾客状态）等等，数据准备时必须除掉表中某些无须要属性，一般可采取面向属性归纳等办法去掉不有关或弱有关属性。第27页第6章决策树决策树算法ID3算法实际应用-在电信行业应用实例（3）属性删除：将有大量不一样取值且无概化操作符属性或者可用其它属性来替代它较高层概念那些属性删除。例如客户信息表中顾客标识、身份证号码等，它们取值太多且无法在该取值域内找到概化操作符，应将其删除，得到表1。

表1客户信息表年纪学历职业缴费方式在网时长费用变化率客户流失58大学公务员托收1310%NO47高中工人营业厅缴费942%NO26硕士公务员充值卡263%YES28大学公务员营业厅缴费52.91%NO32初中工人营业厅缴费32.3%NO42高中无业人员充值卡2100%YES68初中无业人员营业厅缴费92.3%NO第28页第6章决策树决策树算法ID3算法实际应用-在电信行业应用实例（4）属性概化：用属性概化阈值控制技术沿属性概念分层上卷或下钻进行概化。文化程度分为3类：W1初中下列(含初中)，W2高中(含中专)，W3大学(专科、本科及以上)；职业类别：按工作性质来分共分3类：Z1一Z3；缴费方式：托收：T1,营业厅缴费：T2,充值卡：T3。连续型属性概化为区间值：表中年纪、费用变化率和在网时间为连续型数据，由于建立决策树时，用离散型数据进行处理速度最快，因此对连续型数据进行离散化处理，根据专家经验和实际计算信息增益，在“在网时长”属性中，通过检测每个划分，得到在阈值为5年时信息增益最大，从而确定最佳划分是在5年处，则这个属性范围就变为｛<=5,>5：H1,H2｝。而在“年纪”属性中，信息增益有两个锋值，分别在40和50处，因而该属性范围变为{<=40,>40-<=50,>50}即变为{青年，中年，老年：N1,N2,N3}；费用变化率：指（（当月话费－近3个月平均话费）/近3个月平均话费）×％>0，F1:<＝30%，F2：30%-99%,F3:＝100%变为｛F1,F2,F3｝。

第29页表2转化后客户信息表年纪学历职业缴费方式开户时间费用变化率客户流失N3W3Z1T1H2F1NON2W2Z2T2H2F2NON1W3Z1T3H1F2YESN1W3Z1T2H1F1NON1W1Z2T2H1F1NON2W2Z3T3H1F3YESN3W1Z3T1H2F1NO第6章决策树决策树算法ID3算法实际应用-在电信行业应用实例（5）第30页YESNO年龄职业YES缴费方式YESYESNOYSESNONO在网时长NOF1F2F3N1N2N3T1T2T3Z1Z2Z3H1H2费用变化率第6章决策树决策树算法ID3算法实际应用-在电信行业应用实例（6）在图中，NO表达客户不流失，YES表达客户流失。从图能够看出，客户费用变化率为100%客户肯定已经流失；而费用变化率低于30%客户；即每个月资费相对稳定客户一般不会流失，费用变化率在30%～99%客户有也许流失，其中年纪在40～50岁之间客户流失也许性非常大，而年纪低于40岁客户，用充值卡缴费客户和在网时间较短客户容易流失；年纪较大客户，则工人容易流失。第31页主要内容决策树基本概念决策树算法决策树研究问题主要参照文献第32页第6章决策树决策树研究问题抱负决策树有三种：(1)叶子结点数最少；(2)叶子结点深度最小；(3)叶子结点数最少且叶子结点深度最小。

然而，洪家荣等人已经证明了要找到这种最优决策树是NP难题。因此，决策树优化目标就是要找到尽也许趋向于最优决策树。第33页第6章决策树有关过渡拟合上述决策树算法增加树每一种分支深度，直到正好能对训练样例比较完美地分类。实际应用中，当数据中有噪声或训练样例数量太少以至于不能产生目标函数有代表性采样时，该策略也许会遇到困难。在以上情况发生时，这个简单算法产生树会过渡拟合训练样例（过渡拟合：OverFitting）.决策树研究问题第34页有关过渡拟合第6章决策树对于一种假设，当存在其他假设对训练样例拟合比它差，但事实上在实例整个分布上（包括训练集合以外实例）体现得却更加好时，则称该假设过度拟合训练样例。过度拟合：给定一种假设空间H，一种假设h∈H，假如存在其它假设h1∈H,使得在训练样例上h错误率比h1小，但在整个实例公布上h1错误率比h小，则称假设h过度拟合训练数据过度拟合产生原因：噪声，训练样例太小等决策树研究问题第35页有关过渡拟合第6章决策树对学习算法是否成功真正测试是看它对于训练中未见到数据执行性能。训练过程应当包括训练样本和验证样本。验证样本用于测试训练后性能。假如验证成果差，则需要考虑采取不一样构造重新进行训练，例如使用更大样本集，或者变化从连续值到离散值得数据转换等。一般应当建立一种验证过程，在训练最后完成后用来检测训练成果泛化能力。决策树研究问题第36页有关过渡拟合第6章决策树分类模型误差一般能够将分类模型误差分为：

1、训练误差（TrainingError）；2、泛化误差（GeneralizationError）决策树研究问题第37页有关过渡拟合第6章决策树分类模型误差训练误差是在训练统计上误分类样本百分比；泛化误差是模型在未知统计上盼望误差；一种好模型不但要能够较好地拟合训练数据，并且对未知样本也要能够精确地分类。一种好分类模型必须具有低训练误差和泛化误差。由于一种具有低训练误差模型，其泛化误差也许比具有较高训练误差模型高。（训练误差低，泛化误差高，称为过渡拟合）决策树研究问题第38页有关过渡拟合第6章决策树模型过渡拟合潜在原因（1）噪声造成过渡拟合；

错误类别值/类标签，属性值等（2）缺乏代表性样本所造成过渡拟合

根据少许训练统计作出分类决策模型容易受过渡拟合影响。由于训练样本缺乏代表性样本，在没有多少训练统计情况下，学习算法仍然继续细化模型就会造成过渡拟合。决策树研究问题第39页有关过渡拟合第6章决策树模型过渡拟合潜在原因名称体温胎生4条腿冬眠哺乳动物蝾螈冷血NYYN虹鳉冷血YNNN鹰恒温NNNN弱夜鹰恒温NNYN鸭嘴兽恒温YYYY哺乳动物分类训练样例体温恒温冷血冬眠NYNN4条腿YNNY名称体温胎生4条腿冬眠哺乳动物人恒温YNNY大象恒温YYNY鸽子恒温NNNN哺乳动物分类训练样例按照训练模型。人和大象都不是哺乳动物。决策树作出这样判断是由于只有一种训练样例具有这些特点（鹰，恒温，不冬眠）被划分为非哺乳动物。该例清楚表白，当决策树叶节点没有足够代表性时，也许会预测错误。决策树研究问题第40页有关过渡拟合第6章决策树处理过度拟合伎俩：1及早停顿树增加；2后修剪法。决策树研究问题第41页有关过渡拟合第6章决策树1及早停顿树增加

由于决策树学习要从候选集合众选择满足给定标准最大化属性，并且不回溯，也就是我们常说爬山策略，其选择往往会是局部最优而不是全局最优。树构造越复杂，则过渡拟合发生也许性越大。因此，要选择简单模型。Occan法则（又称Occan剃刀OccanRazor）:具有相同泛化误差两个模型，较简单模型比复杂模型更可取。决策树研究问题第42页有关过渡拟合第6章决策树后修剪法（后剪枝法）

在训练过程中允许对数据过渡拟合，然后再对树进行修剪该办法称为后剪枝法。决策树研究问题第43页有关过渡拟合第6章决策树后修剪法（后剪枝法）例AB负C正正负YYYNNN一棵通过训练集合学好决策树决策树研究问题第44页有关过渡拟合第6章决策树后修剪法（后剪枝法）例AB负C正正负YYYNNN实例ABC类别错分类1YYY+2YYY+3YYY+4YYY+5YYY+6YYN-*7YYN-*8YYN-*9YNY+10YNY+11YNY+12YNY+13YNN+*14YNN+*15YNN-16YNN-17YNN-18NNN-19NYN-20NYY-对以上决策树通过右侧验证集合进行测试，发觉其有5个错分类。决策树研究问题第45页有关过渡拟合第6章决策树后修剪法（后剪枝法）例AB负C正正负YYYNNN{18，19，20}{1，2，3，45，6，7，8}{9，10，11，12}{13，14，15，16，17}错分类5个，6，7，8，13，14决策树研究问题第46页有关过渡拟合第6章决策树后修剪法（后剪枝法）例第1步将决策树规则化规则1IFA=YANDB=YTHEN+规则2IFA=YANDB=NANDC=YTHEN+规则3IFA=YANDB=NANDC=NTHEN–规则4IFA=NTHEN-

AB负C正正负YYYNNN决策树研究问题第47页有关过渡拟合第6章决策树后修剪法（后剪枝法）例规则1IFA=YANDB=YTHEN+规则2IFA=YANDB=NANDC=YTHEN+规则3IFA=YANDB=NANDC=NTHEN–规则4IFA=NTHEN-

规则分类正确数目分类错误数目精度1535/82404/43323/54303/3第2步规则精度计算决策树研究问题第48页规则2与规则4精度为100%，保存有关过渡拟合第6章决策树后修剪法（后剪枝法）例规则分类正确数目分类错误数目精度1535/82404/43323/54303