数据挖掘决策树ppt(自己制作)课件.pptx

决策树演讲：李伟能单位：云南大学（数学与统计学院）导师：孟捷资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值什么是决策树？什么是决策树？1.决策树的背景是什么？决策树的背景是什么？2.3.决策树是怎么样发展而来的？决策树是怎么样发展而来的？4.决策树可以做什么？决策树可以做什么？5.现在国内外关于决策树的研究现状是什么现在国内外关于决策树的研究现状是什么？资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值什么是决策树？什么是决策树？1.决策树（Decision Tree），又称为判定树，是数据挖掘技术中的一种重要的分类方法，它是一种以树结构（包括二叉树和多叉树）形式来表达的预测分析模型。通过把实例从根节点排列到某个叶子节点来分类实例；叶子节点即为实例所属的分类；树上每个节点说明了对实例的某个属性的测试节点的每个后继分支对应于该属性的一个可能值。资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值叶结点根结点内部结点体温胎生非哺乳动物哺乳动物非哺乳动物恒温否冷血是资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值决策树构造流程资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值决策树的背景是什么？决策树的背景是什么？2.沃尔玛每小时从顾客交易获得数据为100万G，印出来可装2000万个文件柜。Twitter平均每天产生3.4亿条消息，而Facebook每天则有40亿的信息扩散。世界上访问量最大的网站google，每天能处理的数据量高达20PB。每分钟的时间里，YouTube用户会上传48小时的新视频，全球电子邮件用户共计发出2.04亿封电子邮件资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值在影视领域，大数据运用的成功案例当数美剧纸牌屋。该剧的制作方既不是电视台，也不是传统的电影公司，而是一家视频播放网站。2012年，视频网站Netflix开始准备推出自制剧。在决定拍什么、怎么拍时，Netflix抛开了传统的制作方式，启用大数据。通过在该网站上3000多万订阅用户每天的点击操作，如收藏、推荐、回放、暂停、搜索请求等，Netflix进行精准分析，将这些数据用于倒推前台的影片生产。通过对大数据的分析、挖掘，Netflix发现，其用户中有很多人仍在点播1990年BBC经典老片纸牌屋。这些观众中，又有许多人喜欢导演大卫芬奇，大多爱看演员凯文史派西出演的电影。Netflix大胆预测，一部影片如果同时满足这几个要素，就可能大卖。于是，纸牌屋出现了，并大获成功。整部剧集一次性在Netflix网站发布，供订阅者观看，完全颠覆了传统的每周一集的播出模式。资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值生活中很多地方都需要分类，各种分类技术的诞生为我们节省了大量的时间，决策树作为分类技术的一种，在零售、电子商务、金融、医疗卫生等方面有着广泛的运用。决策树有哪些优点？决策树有哪些优点？1、决策树构造的分类器容易理解；2、决策树算法的运算速度要快于其他分类方法；3、决策树分类方法得到的结果的准确率要优于其他算法。决策树方法是一种比较通用的分类函数逼近法，它是一种常用于预测模型的算法，通过将大量数据有目的分类，找到一些有潜在价值的信息。资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值决策树的起源是CLS（Concept Learning System），CLS是由Hunt、Marin和Stone为了研究人类概念模型而得来的，于1966年提出，该模型为很多决策树算法的发展奠定了很好的基础。1986年，Quinlan提出了ID3算法。1984年，L.Breiman等人提出了CART（Classification and Regression Tree）算法。3.决策树是怎么样发展而来的？决策树是怎么样发展而来的？资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值1993年，J.R.Quinlan又提出了C4.5算法，克服了ID3算法的一些不足。1996年，M.Mehta和R.Agrawal等人提出了一种高速可伸缩的有监督的寻找学习分类方法SLIQ（Supervised Learning In Quest）。同年，J.Shafer和R.Agrawal等人提出可伸缩并行归纳决策树分类方法SPRINT(Scalable PaRallelizable Induction of Decision Trees)1998年，R.Rastogi等人提出一种将建树和修剪相结合的分类算法PUBLIC(A Decision Tree that Integrates Building and Pruning)资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值ID3算法实例熵：基尼指数：分类误差：其中c是类的个数，并且在计算熵时，分裂属性标准资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值ID3算法缺点l ID3 算法选用最大信息增益的属性作为决策树分裂属性。在算法实际应用中，这种方法偏向于选择多值属性，但属性取值数目的多少与属性的匹配并无真正关联。这样在使用ID3算法构建时，若出现各属性值取值数分布偏差大的情况，分类精度会大打折扣。l ID3 算法本身并未给出处理连续数据的方法。l ID3 算法不能处理带有缺失值的数据集，故在进行算法挖掘之前需要对数据集中的缺失值进行预处理。资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值C4.5算法C4.5 算法同样是由Quinlan 提出，它在ID3 算法的基础上演变而来。C4.5 算法除了拥有前述的ID3 算法基本功能外，在其算法中还加入了连续值处理、属性空缺处理等方法。总结来说，C4.5 算法在以下几个方面做出了改进：信息增益比例计算公式如下：1）使用信息增益比例而非信息增益作为分裂标准。在上式中，称为分裂信息，它反映了属性分裂数据的延展度与平衡性，计算公式如下：资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值2）处理含有带缺失值属性的样本C4.5 算法在处理缺失数据时最常用的方法是，将这些值并入最常见的某一类中或是以最常用的值代替之。C4.5算法处理连续值属性过程3）处理连续值属性以每个数据作为阈值划分数据集，代价是否过大？资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值4）规则的产生决策树每条根节点到叶节点的路径都对应一个分类规则，可将所有这些路径综合转换为一个规则集。规则集存储于一个二维数组中，每一行代表决策树的一个规则。交互验证是一种模型的评估方法。在训练开始之前，预留一部分数据，而在训练之后，使用这部分数据对学习的结果进行验证的方法叫做交互验证。交互验证最简单的方法是两分法，将数据集划分为两个独立子集，一个称为训练集，一个称为测试集。另一种方法是K 次折叠交互验证，将数据集划分为K 个子集，留取一个作为测试集，其余K-1 个作为训练集，最后还对数据子集的错误数计算平均值。5）交互验证（Cross Validation）资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值从上面的改进描述可以看到，C4.5 相较ID3 有了许多提高，纵然如此，C4.5 仍然存在一定的不足之处。它在测试属性的判断和样本集分割方面仍旧存在一定的偏向性，同时C4.5 生成的决策树还称不上简洁，特别是对于数据属性及其取值较多的情况。因此，人们还在不断改进现有算法和提出新的算法。CART（Classification And Regression Tree）算法该决策树算法模型采用的是二叉树形式，利用二分递归将数据空间不断划分为不同子集。同样的，每一个叶节点都有着与之相关的分类规则，对应了不同的数据集划分。为了减小CART 决策树的深度，在决策树某一分支节点对应数据集大多数为一类时，即将该分支设为叶节点。CART算法采用GINI系数作为属性分裂的标准。资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值在计算机大量普及的今天，虽然内存和CPU 越来越大，越来越快，但终究会有许多数据在处理的时候无法全部放入内存计算。在众多决策树算法中，大部分算法需要在决策树生成与分类时将数据集全部放入主存，这在数据集规模较小情况下没有问题，但是一旦数据规模超出主存限制，这些算法就无能为力了。SLIQ（Supervised Learning In Quest）算法为了解决上述问题，提出了一些改进，并且它能保证分类精度不变。在SLIQ 决策树的生成过程中可以应用其他算法，其精度也与这些算法一直，不过对于大数量级的数据，SLIQ 效率大大提高，生成的模型也较为精简。除此之外，由于SLIQ 破除了主存的限制，则其对训练数据量和属性量都没有限制了。SLIQ（Supervised Learning In Quest）算法资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值1)预排序。对于连续属性在每个内部结点寻找其最优分裂标准时，都需要对训练集按照该属性的取值进行排序，而排序是很浪费时间的操作。为此，SLIQ算法采用了预排序技术。所谓预排序，就是针对每个属性的取值，把所有的记录按照从小到大的顺序进行排序，以消除在决策树的每个结点对数据集进行的排序。具体实现时，需要为训练数据集的每个属性创建一个属性列表，为类别属性创建一个类别列表。SLIQ算法对C4.5决策树分类算法的实现方法进行了改进，在决策树的构造过程中采用了“预排序”和“广度优先策略”两种技术。2)广度优先策略。在C4.5算法中，树的构造是按照深度优先策略完成的，需要对每个属性列表在每个结点处都进行一遍扫描，费时很多，为此，SLIQ采用广度优先策略构造决策树，即在决策树的每一层只需对每个属性列表扫描一次，就可以为当前决策树中每个叶子结点找到最优分裂标准。资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值SLIQ算法由于采用了上述两种技术，使得该算法能够处理比C4.5大得多的训练集，在一定范围内具有良好的随记录个数和属性个数增长的可伸缩性。然而它仍然存在如下缺点：2)由于采用了预排序技术，而排序算法的复杂度本身并不是与记录个数成线性关系，因此，使得SLIQ算法不可能达到随记录数目增长的线性可伸缩性。1)由于需要将类别列表存放于内存,而类别列表的元组数与训练集的元组数是相同的,这就一定程度上限制了可以处理的数据集的大小。资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值 由于SLIQ 仍存在对主存容量的限制，J.Shafter 等人提出了SPRINT（Scalable PaRallelizable INduction of decision Trees）算法，其在SLIQ 的基础上又做出了进一步的改进。该算法真正意义上破除了主存限制，使得决策树处理的数据规模达到了前所未有的境界。与此同时，并行算法的引入也使得SPRINT 算法具有更好的伸缩性。SPRINT 主要改进了SLIQ 的数据结构，合并SLIQ 中的类表与属性表，将这些数据结构均放于辅存之中。这样就使得算法在遍历属性列表寻找最优分裂时，只需使用辅存中的合并数据表。最后，SPRINT 采用的生成树策略是深度优先规则。并行算法就是用多台处理机联合求解问题的方法和步骤，其执行过程是将给定的问题首先分解成若干个尽量相互独立的子问题，然后使用多台计算机同时求解它，从而最终求得原问题的解。SPRINT 算法资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值在上述介绍的决策树算法中，所有算法均是先通过一定的规则建立决策树，然后在进行决策树剪枝，从而达到生成最终决策树的目的。而PUBLIC（A Decision Tree that Integrates Building and Pruning）算法则是典型的预剪枝决策树算法。作为预剪枝技术生成的决策树与后剪枝决策树是一致的，PUBLIC 算法采用Gini 系数作为分裂标准，可以说是CART 算法的一种有效改进。PUBLIC 算法所谓预剪枝技术，是指在决策树的建树过程中同时进行剪枝，两者交替进行，从而提高建树效率。资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值现在国内外关于决策树的研究现状是什么？现在国内外关于决策树的研究现状是什么？4.国外研究现状2002年，S.Ruggieri 提出C4.5的改进算法（Efficient C4.5算法）。这种算法采用二分搜索取代线性搜索，还提出几种不同的寻找连续属性的局部阈值改进策略。实验表明，在生成同样一颗决策树时，与C4.5算法相比，EC4.5可将效率提高5倍，但是会以牺牲内存为代价。2009年，Polat和Gunes提出了一种基于C4.5决策树分类器和一对多方法来提高多类别分类问题中分类精度的混合分类系统。Walley(1996)、Abelln 和Moral(2003)将不精确概率理论应用到决策树的算法之中，并且都取得了较好的效果。资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值国内研究现状1998年，刘小虎博士和李生教授提出改进的递归信息增益优化算法，每当选择一个新的属性时，算法不仅仅是考虑该属性带来的信息增益，还需要考虑到该属性后选择的属性带来的信息增益，即同时考虑两层节点。2001年，郭茂祖博士和刘杨教授针对ID3多值偏向的缺陷，提出了一种新的基于属性一值对为内节点的决策树归纳算法AVPI，它所产生的决策树大小及测试速度均优于ID3算法。2003年，杨宏伟博士和王熙照教授等用基于层次分解的方法通过产生多重决策树来处理多类问题。2006年，阳东升博士等通过对组织协作网与决策树的描述分析提出了组织结构设计的新思路：基于决策个体在任务上的协作关系设计最佳的决策树。2009年，张凤莲等人提出了一种新的决策树构造方法，其基于广义相关函数。资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值决策树可以做什么？决策树可以做什么？5.决策树银行保险医疗电信零售信用卡欺诈，信用评估保险公司偿付能力分析客户细分，交叉销售疾病因素分析客户消费特征行为分析资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值疑问疑问1、既然决策树广泛运用于各个领域，并且效果也不错，那为什么还要研究很多其他分类方法？决策树并不在任何时候都要好于其他分类方法，分类方法的选取要根据情况而定。它也存在它自身的一些缺陷：随着数据复杂性的提高，其分支也不断增多，增加了管理上的困难；分类算法的预处理不仅增加了算法的额外开销而且降低了分类的准确性；缺失值问题一直是一个亟待解决的问题，不同的问题可能处理方式不一样；资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值2、决策树有很多种算法，有没有一种算法能够优于其他所有算法？没有，每一种算法都有其自身的优点和缺点，每一种算法都有其用武之地。算法算法优点点缺点缺点ID3算法算法 算法的理算法的理论清晰，方法清晰，方法简单，学，学习能力能力较强。只只对比比较小的数据集有效，且小的数据集有效，且对噪声比噪声比较敏感，当敏感，当训练数据集加数据集加大大时，决策，决策树可能会随之改可能会随之改变。C4.5算法算法1)用信息增益率来用信息增益率来选择属性，克属性，克服了用信息增益服了用信息增益选择属性属性时偏向偏向选择取取值多的属性的不足；多的属性的不足；2)在在树构造构造过程中程中进行剪枝；行剪枝；3)能能够完成完成对连续属性的离散化属性的离散化处理；理；4)能能够对不完整数据不完整数据进行行处理。理。1、在构造在构造树的的过程中，需要程中，需要对数数据集据集进行多次的行多次的顺序序扫描和排序，描和排序，因而因而导致算法的低效致算法的低效；2、C4.5只适合于能只适合于能够驻留于内存留于内存的数据集，当的数据集，当训练集大得无法在集大得无法在内存容内存容纳时程序无法运行程序无法运行。资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值算法算法优点点缺点缺点SLIQ算法算法 SLIQ算法对算法对C4.5决策树分类决策树分类算法的实现方法进行了改进，算法的实现方法进行了改进，在决策树的构造过程中采用在决策树的构造过程中采用了了“预排序预排序”和和“广度优先策略广度优先策略”两种技术两种技术。1)由于需要将类别列表存放于内存由于需要将类别列表存放于内存,而而类别列表的元组数与训练集的元组数是类别列表的元组数与训练集的元组数是相同的相同的,这就一定程度上限制了可以处这就一定程度上限制了可以处理的数据集的大小。理的数据集的大小。2)由于采用了预排序技术，而排序算由于采用了预排序技术，而排序算法的复杂度本身并不是与记录个数成线法的复杂度本身并不是与记录个数成线性关系，因此，使得性关系，因此，使得SLIQ算法不可能达算法不可能达到随记录数目增长的线性可伸缩性。到随记录数目增长的线性可伸缩性。SPRINT算法算法为了减少驻留于内存的数据为了减少驻留于内存的数据量，量，SPRINT算法进一步改算法进一步改进了决策树算法的数据结构，进了决策树算法的数据结构，去掉了在去掉了在SLIQ中需要驻留于中需要驻留于内存的类别列表，将它的类内存的类别列表，将它的类别列合并到每个属性列表中别列合并到每个属性列表中。对非分裂属性的属性列表进行分裂变得对非分裂属性的属性列表进行分裂变得很困难很困难资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值4、在什么情况下用何种算法呢？一、C 5.0算法 （执行效率和内存使用改进、适用大数据集）1)面对数据遗漏和输入字段很多的问题时非常稳健；2)通常不需要很长的训练次数进行估计；3)比一些其他类型的模型易于理解，模型推出的规则有非常直观的解释；4)允许进行多次多于两个子组的分割。目标字段必须为分类字段。C4.5是在ID3算法的基础上将连续属性离散化，C5.0是在C4.5的基础上在内存和执行效率进行了改进。二、classification and regression tree(C&RT)（对二元分类比较有效）1）可自动忽略对目标变量没有贡献的属性变量，也为判断属性变量的重要性，减少变量数据提供参考；2）在面对诸如存在缺失值、变量数多等问题时C&RT 显得非常稳健（robust）；3）估计模型通常不用花费很长的训练时间；4）推理过程完全依据属性变量的取值特点（与 C5.0不同，C&RT的输出字段既可以是数值型，也可以是分类型）3、为什么ID3算法偏向多值属性？资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值（5）比其他模型更易于理解从模型中得到的规则能得到非常直观的解释，决策推理过程可以表示成IFTHEN的形式；（6）目标是定类变量为分类树，若目标变量是定距变量，则为回归树；（7）通过检测输入字段，通过度量各个划分产生的异质性的减小程度，找到最佳的一个划分；（8）非常灵活，可以允许有部分错分成本，还可指定先验概率分布，可使用自动的成本复杂性剪枝来得到归纳性更强的树。三、CHAID(卡方自动交互检测)（可用于多元分类，从统计角度来分裂变量）1）可产生多分枝的决策树；2）目标变量可以定距或定类；3）从统计显著性角度确定分支变量和分割值，进而优化树的分枝过程；4）建立在因果关系探讨中，依据目标变量实现对输入变量众多水平划分。资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值四、quest（quick unbiased efficient statistical tree）（也用于二分类，运算过程比CR&T更简单有效，但不支持使用连续的输出变量）QUEST 节点可提供用于构建决策树的二元分类法，此方法的设计目的是减少大型 C&R 决策树分析所需的处理时间，同时减小分类树方法中常见的偏向类别较多预测变量的趋势。预测变量字段可以是数字范围的，但目标字段必须是分类的。5、决策树未来的发展方向如何？1）决策树与其他技术相结合在数据挖掘技术中，从数据集的预处理到最终输出需要的知识，要用到很多方面的技术，所以决策树也需要与其他技术相结合，才能有创新，才能有发展。现在已经有人将决策树和模糊集合理论、遗传算法、神经网络等技术结合起来研究，都不同程度的提高了决策树的效率和精度。资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值2）决策树分类的准确率决策树分类的准确率也是研究的重点，因为它是判断决策树算法优劣的标准之一，比如多变量决策树技术，它减少了决策树的规模，它的最终目的是为了提高决策树的精度。3）数据集的预处理实际中数据集往往存在大量的缺失数据、噪声数据等等。当然，最简单的方法就是直接将这样的数据删除，但是这样必然会导致分类结果不准确。目前的方法就是用出现频率最高的值替代缺失值。4）决策树算法的增量学习目前很多决策树算法都不具备增量学习的功能，对于新的训练样本需要重新建树，这样会花费大量的时间，大大降低了效率。