数据挖掘决策树PPT(自己制作)

决策树演讲：李伟能单位：云南大学（数学与统计学院）导师：孟捷什么是决策树？1.决策树的背景是什么？2.3.决策树是怎么样发展而来的？4.决策树可以做什么？5.现在国内外关于决策树的研究现状是什么？什么是决策树？1.决策树（DecisionTree），又称为判定树，是数据挖掘技术中的一种重要的分类方法，它是一种以树结构（包括二叉树和多叉树）形式来表达的预测分析模型。通过把实例从根节点排列到某个叶子节点来分类实例；叶子节点即为实例所属的分类；树上每个节点说明了对实例的某个属性的测试节点的每个后继分支对应于该属性的一个可能值。叶结点根结点内部结点体温胎生非哺乳动物哺乳动物非哺乳动物恒温否冷血是决策树构造流程决策树的背景是什么？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（ConceptLearningSystem），CLS是由Hunt、Marin和Stone为了研究人类概念模型而得来的，于1966年提出，该模型为很多决策树算法的发展奠定了很好的基础。1986年，Quinlan提出了ID3算法。1984年，L.Breiman等人提出了CART（ClassificationandRegressionTree）算法。3.决策树是怎么样发展而来的？1993年，J.R.Quinlan又提出了C4.5算法，克服了ID3算法的一些不足。1996年，M.Mehta和R.Agrawal等人提出了一种高速可伸缩的有监督的寻找学习分类方法SLIQ（SupervisedLearningInQuest）。同年，J.Shafer和R.Agrawal等人提出可伸缩并行归纳决策树分类方法SPRINT(ScalablePaRallelizableInductionofDecisionTrees)1998年，R.Rastogi等人提出一种将建树和修剪相结合的分类算法PUBLIC(ADecisionTreethatIntegratesBuildingandPruning)ID3算法实例102)|(log)|()(citiptiptEntropy102)]|([1)(citiptGini)]|([max1)(_Ctipterrorionlassificati熵：基尼指数：分类误差：其中c是类的个数，并且在计算熵时，00log2O分裂属性标准ID3算法缺点ID3算法选用最大信息增益的属性作为决策树分裂属性。在算法实际应用中，这种方法偏向于选择多值属性，但属性取值数目的多少与属性的匹配并无真正关联。这样在使用ID3算法构建时，若出现各属性值取值数分布偏差大的情况，分类精度会大打折扣。ID3算法本身并未给出处理连续数据的方法。ID3算法不能处理带有缺失值的数据集，故在进行算法挖掘之前需要对数据集中的缺失值进行预处理。C4.5算法C4.5算法同样是由Quinlan提出，它在ID3算法的基础上演变而来。C4.5算法除了拥有前述的ID3算法基本功能外，在其算法中还加入了连续值处理、属性空缺处理等方法。总结来说，C4.5算法在以下几个方面做出了改进：信息增益比例计算公式如下：1）使用信息增益比例而非信息增益作为分裂标准。)()()(KSplitInfAGainAGainRatio在上式中，称为分裂信息，它反映了属性分裂数据的延展度与平衡性，计算公式如下：)(KSplitInf12log)(iSSiiSSKSplitInf2）处理含有带缺失值属性的样本C4.5算法在处理缺失数据时最常用的方法是，将这些值并入最常见的某一类中或是以最常用的值代替之。C4.5算法处理连续值属性过程3）处理连续值属性以每个数据作为阈值划分数据集，代价是否过大？4）规则的产生决策树每条根节点到叶节点的路径都对应一个分类规则，可将所有这些路径综合转换为一个规则集。规则集存储于一个二维数组中，每一行代表决策树的一个规则。交互验证是一种模型的评估方法。在训练开始之前，预留一部分数据，而在训练之后，使用这部分数据对学习的结果进行验证的方法叫做交互验证。交互验证最简单的方法是两分法，将数据集划分为两个独立子集，一个称为训练集，一个称为测试集。另一种方法是K次折叠交互验证，将数据集划分为K个子集，留取一个作为测试集，其余K-1个作为训练集，最后还对数据子集的错误数计算平均值。5）交互验证（CrossValidation）从上面的改进描述可以看到，C4.5相较ID3有了许多提高，纵然如此，C4.5仍然存在一定的不足之处。它在测试属性的判断和样本集分割方面仍旧存在一定的偏向性，同时C4.5生成的决策树还称不上简洁，特别是对于数据属性及其取值较多的情况。因此，人们还在不断改进现有算法和提出新的算法。CART（ClassificationAndRegressionTree）算法该决策树算法模型采用的是二叉树形式，利用二分递归将数据空间不断划分为不同子集。同样的，每一个叶节点都有着与之相关的分类规则，对应了不同的数据集划分。为了减小CART决策树的深度，在决策树某一分支节点对应数据集大多数为一类时，即将该分支设为叶节点。CART算法采用GINI系数作为属性分裂的标准。在计算机大量普及的今天，虽然内存和CPU越来越大，越来越快，但终究会有许多数据在处理的时候无法全部放入内存计算。在众多决策树算法中，大部分算法需要在决策树生成与分类时将数据集全部放入主存，这在数据集规模较小情况下没有问题，但是一旦数据规模超出主存限制，这些算法就无能为力了。SLIQ（SupervisedLearningInQuest）算法为了解决上述问题，提出了一些改进，并且它能保证分类精度不变。在SLIQ决策树的生成过程中可以应用其他算法，其精度也与这些算法一直，不过对于大数量级的数据，SLIQ效率大大提高，生成的模型也较为精简。除此之外，由于SLIQ破除了主存的限制，则其对训练数据量和属性量都没有限制了。SLIQ（SupervisedLearningInQuest）算法1)预排序。对于连续属性在每个内部结点寻找其最优分裂标准时，都需要对训练集按照该属性的取值进行排序，而排序是很浪费时间的操作。为此，SLIQ算法采用了预排序技术。所谓预排序，就是针对每个属性的取值，把所有的记录按照从小到大的顺序进行排序，以消除在决策树的每个结点对数据集进行的排序。具体实现时，需要为训练数据集的每个属性创建一个属性列表，为类别属性创建一个类别列表。SLIQ算法对C4.5决策树分类算法的实现方法进行了改进，在决策树的构造过程中采用了“预排序”和“广度优先策略”两种技术。2)广度优先策略。在C4.5算法中，树的构造是按照深度优先策略完成的，需要对每个属性列表在每个结点处都进行一遍扫描，费时很多，为此，SLIQ采用广度优先策略构造决策树，即在决策树的每一层只需对每个属性列表扫描一次，就可以为当前决策树中每个叶子结点找到最优分裂标准。SLIQ算法由于采用了上述两种技术，使得该算法能够处理比C4.5大得多的训练集，在一定范围内具有良好的随记录个数和属性个数增长的可伸缩性。然而它仍然存在如下缺点：2)由于采用了预排序技术，而排序算法的复杂度本身并不是与记录个数成线性关系，因此，使得SLIQ算法不可能达到随记录数目增长的线性可伸缩性。1)由于需要将类别列表存放于内存,而类别列表的元组数与训练集的元组数是相同的,这就一定程度上限制了可以处理的数据集的大小。由于SLIQ仍存在对主存容量的限制，J.Shafter等人提出了SPRINT（ScalablePaRallelizableINductionofdecisionTrees）算法，其在SLIQ的基础上又做出了进一步的改进。该算法真正意义上破除了主存限制，使得决策树处理的数据规模达到了前所未有的境界。与此同时，并行算法的引入也使得SPRINT算法具有更好的伸缩性。SPRINT主要改进了SLIQ的数据结构，合并SLIQ中的类表与属性表，将这些数据结构均放于辅存之中。这样就使得算法在遍历属性列表寻找最优分裂时，只需使用辅存中的合并数据表。最后，SPRINT采用的生成树策略是深度优先规则。并行算法就是用多台处理机联合求解问题的方法和步骤，其执行过程是将给定的问题首先分解成若干个尽量相互独立的子问题，然后使用多台计算机同时求解它，从而最终求得原问题的解。SPRINT算法在上述介绍的决策树算法中，所有算法均是先通过一定的规则建立决策树，然后在进行决策树剪枝，从而达到生成最终决策树的目的。而PUBLIC（ADecisionTreethatIntegratesBuildingandPruning）算法则是典型的预剪枝决策树算法。作为预剪枝技术生成的决策树与后剪枝决策树是一致的，PUBLIC算法采用Gini系数作为分裂标准，可以说是CART算法的一种有效改进。PUBLIC算法所谓预剪枝技术，是指在决策树的建树过程中同时进行剪枝，两者交替进行，从而提高建树效率。现在国内外关于决策树的研究现状是什么？4.国外研究现状2002年，S.Ruggieri提出C4.5的改进算法（EfficientC4.5算法）。这种算法采用二分搜索取代线性搜索，还提出几种不同的寻找连续属性的局部阈值改进策略。实验表明，在生成同样一颗决策树时，与C4.5算法相比，EC4.5可将效率提高5倍，但是会以牺牲内存为代价。2009年，Polat和Gunes提出了一种基于C4.5决策树分类器和一对多方法来提高多类别分类问题中分类精度的混合分类系统。Walley(1996)、Abellán和Moral(2003)将不精确概率理论应用到决策树的算法之中，并且都取得了较好的效果。国内研究现状1998年，刘小虎博士和李生教授提出改进的递归信息增益优化算法，每当选择一个新的属性时，算法不仅仅是考虑该属性带来的信息增益，还需要考虑到该属性后选择的属性带来的信息增益，即同时考虑两层节点。2001年，郭茂祖博士和刘杨教授针对ID3多值偏向的缺陷，提出了一种新的基于属性一值对为内节点的决策树归纳算法AVPI，它所产生的决策树大小及测试速度均优于ID3算法。2003年，杨宏伟博士和王熙照教授等用基于层次分解的方法通过产生多重决策树来处理多类问题。2006年，阳东升博士等通过对组织协作网与决策树的描述分析提出了