第3章_分类与决策树ppt课件

1、第3章分类与预测.主要内容分类与决策树概述ID3、C4.5与C5.0CART.分类 VS. 预测分类和预测是两种数据分析方式，用于提取描画重要数据类或预测未来的数据趋势 的模型分类：预测类对象的分类标号或离散值根据训练数据集和类标号属性，构建模型来分类现有数据，并用来分类新数据预测：建立延续函数值模型比如预测空缺值，或者预测顾客在计算机设备上的破费典型运用欺诈检测、市场定位、性能预测、医疗诊断分类是一种运用非常广泛的数据发掘技术 分类与预测的区别：当估计的属性值是离散值时，这就是分类；当估计的属性值是延续值时，这就是预测。.分类和预测-例如分类银行贷款员需求分析数据，来弄清哪些贷款恳求者是平安

2、的，哪些是有风险的将贷款恳求者分为“平安和“有风险两类我们需求构造一个分类器来预测类属编号，比如预测顾客属类预测银行贷款员需求预测贷给某个顾客多少钱是平安的构造一个预测器，预测一个延续值函数或有序值，常用方法是回归分析.数据分类一个两步过程 (1)第一步，也成为学习步，目的是建立描画预先定义的数据类或概念集的分类器分类算法经过分析或从训练集“学习来构造分类器。训练集由数据库元组用n维属性向量表示和他们相对应的类编号组成；假定每个元组属于一个预定义的类训练元组：训练数据集中的单个元组学习模型可以用分类规那么、决策树或数学公式的方式提供.数据分类一个两步过程 (2)第二步，运用模型，对未来的或未知

3、的对象进展分类首先评价模型的预测准确率对每个测试样本，将知的类标号和该样本的学习模型类预测比较模型在给定测试集上的准确率是正确被模型分类的测试样本的百分比测试集要独立于训练样本集，否那么会出现“过分拟合的情况.第一步建立模型训练数据集分类算法IF rank = professorOR years 6THEN tenured = yes 分类规那么.第二步用模型进展分类分类规那么测试集未知数据(Jeff, Professor, 4)Tenured?.监视学习 VS. 无监视学习监视学习用于分类模型的学习在被告知每个训练样本属于哪个类的“指点下进展新数据运用训练数据集中得到的规那么进展分类无监视学

4、习用于聚类每个训练样本的类编号是未知的，要学习的类集合或数量也能够是事先未知的经过一系列的度量、察看来建立数据中的类编号或进展聚类.数据预测的两步过程数据预测也是一个两步的过程，类似于前面描画的数据分类对于预测，没有“类标号属性要预测的属性是延续值，而不是离散值，该属性可简称“预测属性E.g. 银行贷款员需求预测贷给某个顾客多少钱是平安的预测器可以看作一个映射或函数y=f(X)其中X是输入；y是输出，是一个延续或有序的值与分类类似，准确率的预测，也要运用单独的测试集.3.1 决策树概述决策树(Decision Tree) 一种描画概念空间的有效的归纳推理方法。基于决策树的学习方法可以进展不相关

5、的多概念学习，具有简单快捷的优势，曾经在各个领域获得广泛运用。决策树是一种树型构造，其中每个内部结点表示在一个属性上的测试，每个分支代表一个测试输出，每个叶结点代表一种类别。.决策树学习是以实例为根底的归纳学习。从一类无序、无规那么的事物概念中推理出决策树表示的分类规那么。概念分类学习算法：来源于Hunt,Marin和Stone 于1966年研制的CLS学习系统，用于学习单个概念。1979年, J.R. Quinlan 给出ID3算法，并在1983年和1986年对ID3 进展了总结和简化，使其成为决策树学习算法的典型。Schlimmer 和Fisher 于1986年对ID3进展改造，在每个能够

6、的决策树节点创建缓冲区，使决策树可以递增式生成，得到ID4算法。1988年，Utgoff 在ID4根底上提出了ID5学习算法，进一步提高了效率。1993年，Quinlan 进一步开展了ID3算法，改良成C4.5算法。另一类决策树算法为CART，与C4.5不同的是，CART的决策树由二元逻辑问题生成，每个树节点只需两个分枝，分别包括学习实例的正例与反例。其根本思想是以信息熵为度量构造一棵熵值下降最快的树，到叶子节点处的熵值为零，此时每个叶节点中的实例都属于同一类。.决策树学习采用的是自顶向下的递归方法。决策树的每一层节点按照某一属性值向下分为子节点，待分类的实例在每一节点处与该节点相关的属性值进

7、展比较，根据不同的比较结果向相应的子节点扩展，这一过程在到达决策树的叶节点时终了，此时得到结论。从根节点到叶节点的每一条路经都对应着一条合理的规那么，规那么间各个部分各个层的条件的关系是合取关系。整个决策树就对应着一组析取的规那么。决策树学习算法的最大优点是，它可以自学习。在学习的过程中，不需求运用者了解过多背景知识，只需求对训练例子进展较好的标注，就可以进展学习。假设在运用中发现不符合规那么的实例，程序会讯问用户该实例的正确分类，从而生成新的分枝和叶子，并添加到树中。 .树是由节点和分枝组成的层次数据构造。节点用于存贮信息或知识，分枝用于衔接各个节点。树是图的一个特例，图是更普通的数学构造，

8、如贝叶斯网络。决策树是描画分类过程的一种数据构造，从上端的根节点开场，各种分类原那么被援用进来，并依这些分类原那么将根节点的数据集划分为子集，这一划分过程直到某种约束条件满足而终了。 根结点个子大能够是松鼠能够是老鼠能够是大象在水里会吱吱叫鼻子长脖子长个子小不会吱吱叫鼻子短脖子短能够是长颈鹿在陆地上能够是犀牛能够是河马.可以看到，一个决策树的内部结点包含学习的实例，每层分枝代表了实例的一个属性的能够取值，叶节点是最终划分成的类。假设断定是二元的，那么构造的将是一棵二叉树，在树中每回答一个问题就降到树的下一层，这类树普通称为CARTClassification And Regression Tr

9、ee。断定构造可以机械的转变成产生式规那么。可以经过对构造进展广度优先搜索，并在每个节点生成“IFTHEN规那么来实现。如图6-13的决策树可以转换成下规那么： IF “个子大 THEN IF “脖子短 THEN IF “鼻子长 THEN 能够是大象方式化表示成 根结点个子大能够是松鼠能够是老鼠能够是大象在水里会吱吱叫鼻子长脖子长个子小不会吱吱叫鼻子短脖子短能够是长颈鹿在陆地上能够是犀牛能够是河马.构造一棵决策树要处理四个问题：搜集待分类的数据，这些数据的一切属性应该是完全标注的。设计分类原那么，即数据的哪些属性可以被用来分类，以及如何将该属性量化。分类原那么的选择，即在众多分类准那么中，每一

10、步选择哪一准那么使最终的树更令人称心。设计分类停顿条件，实践运用中数据的属性很多，真正有分类意义的属性往往是有限几个，因此在必要的时候应该停顿数据集分裂：该节点包含的数据太少缺乏以分裂，继续分裂数据集对树生成的目的(例如ID3中的熵下降准那么)没有奉献，树的深度过大不宜再分。通用的决策树分裂目的是整棵树的熵总量最小，每一步分裂时，选择使熵减小最大的准那么，这种方案使最具有分类潜力的准那么最先被提取出来 .预测变量目的变量记录样本类标号属性类别集合：Class=“优，“良，“差 决策树的根本原理 .根节点叶子节点分裂属性分裂谓词 每一个叶子节点都被确定一个类标号 .每一个节点都代表了一个数据集。

11、根节点1代表了初始数据集D其它节点都是数据集D的子集。例如，节点2代表数据集D中年龄小于40岁的那部分样本组成的数据集。子节点是父节点的子集。 If (年龄40) and (职业=“学生 or职业=“教师) Then 信誉等级=“优If (年龄40) and (职业!=“学生and职业!=“教师) Then 信誉等级=“良If (年龄40) and (月薪3000) Then 信誉等级=“优.决策树是指具有以下三个性质的树：每个非叶子节点都被标志一个分裂属性Ai；每个分支都被标志一个分裂谓词，这个分裂谓词是分裂父节点的详细根据；每个叶子节点都被标志一个类标号CjC。任何一个决策树算法，其中心步

12、骤都是为每一次分裂确定一个分裂属性，即终究按照哪一个属性来把当前数据集划分为假设干个子集，从而构成假设干个“树枝。.熵，是数据集中的不确定性、突发性或随机性的程度的度量。当一个数据集中的记录全部都属于同一类的时候，那么没有不确定性，这种情况下的熵就为0。决策树分裂的根本原那么是，数据集被分裂为假设干个子集后，要使每个子集中的数据尽能够的“纯，也就是说子集中的记录要尽能够属于同一个类别。假设套用熵的概念，即要使分裂后各子集的熵尽能够的小。3.2 ID3、C4.5与C5.0.数据集D被按照分裂属性“年龄分裂为两个子集D1 和D2 信息增益:Gain(D,年龄)= H(D)P(D1)H(D1)+ P

13、(D2)H(D2) .显然，假设D1和D2中的数据越“纯，H(D1)和H(D2)就越小，信息增益就越大，或者说熵下降得越多。按照这个方法，测试每一个属性的信息增益，选择增益值最大的属性作为分裂属性。.信息熵计算举例令C1对应“是，C2对应“否。那么C1有9个样本，C2有5个样本，所以数据集D的熵为：.决策树归纳战略 (1)输入数据划分D是训练元组和对应类标号的集合attribute_list,候选属性的集合Attribute_selection_method，指定选择属性的启发性过程算法步骤树以代表训练样本的单个节点N开场假设样本都在同一个类，那么该节点成为树叶，并用该类标志否那么，算法调用A

14、ttribute_selection_method，选择可以最好的将样本分类的属性；确定“分裂准那么，指出“分裂点或“分裂子集。.决策树归纳战略 (2)对测试属性每个知的值，创建一个分支，并以此划分元组算法运用同样的过程，递归的构成每个划分上的元组决策树。一旦一个属性出如今一个节点上，就不在该节点的任何子节点上出现递归划分步骤停顿的条件划分D在N节点提供的一切元组属于同一类没有剩余属性可以用来进一步划分元组运用多数表决没有剩余的样本给定分支没有元组，那么以D中多数类创建一个树叶.属性选择度量属性选择度量是一种选择分裂准那么，将给定类标号的训练元组最好的进展划分的方法理想情况，每个划分都是“纯的

15、，即落在给定划分内的元组都属于一样的类属性选择度量又称为分裂准那么常用的属性选择度量信息增益增益率Gini目的.信息增益 (1)S是一个训练样本的集合，该样本中每个集合的类编号知。每个样本为一个元组。有个属性用来断定某个训练样本的类编号假设S中有m个类，总共s个训练样本，每个类Ci有si个样本(i1,2,3.m)，那么恣意一个样本属于类Ci的概率是si / s，那么用来分类一个给定样本的期望信息是：.信息增益 (2)一个有v个值的属性Aa1,a2,.,av可以将S分成v个子集S1,S2,.,Sv，其中Sj包含S中属性A上的值为aj的样本。假设Sj包含类Ci的sij个样本。根据A的这种划分的期望

16、信息称为A的熵A上该划分的获得的信息增益定义为：具有高信息增益的属性，是给定集合中具有高区分度的属性。所以可以经过计算S中样本的每个属性的信息增益，来得到一个属性的相关性的排序。.假设以“年龄作为分裂属性，那么产生三个子集由于该属性有三个不同的取值，所以D按照属性“年龄划分出的三个子集的熵的加权和为：其中有一个子集的熵为0.同理，假设以“收入程度为分裂属性：.假设以“有固定收入为分裂属性：假设以“VIP为分裂属性：.以“年龄作为分裂属性，所得信息增益最大。 叶子节点.ID3的主要缺陷ID3算法只能处置分类属性离散属性，而不能处置延续属性数值属性。在处置延续属性时，普通要先将延续属性划分为多个区

17、间，转化为分类属性。例如“年龄，要把数值事先转换为诸如“小于30岁、“30至50岁、“大于50岁这样的区间，再根据年龄值落入了某一个区间取相应的类别值。通常，区间端点的选取包含着一定的客观要素。ID3生成的决策树是一棵多叉树，分支的数量取决于分裂属性有多少个不同的取值。这不利于处置分裂属性取值数目较多的情况。因此目前流行的决策树算法大多采用二叉树模型。.ID3是采用“信息增益来选择分裂属性的。虽然这是一种有效的方法，但其具有明显的倾向性，即它倾向于选择具有大量不同取值的属性，从而产生许多小而纯的子集。尤其是关系数据库中作为主键的属性，每一个样本都有一个不同的取值。假设以这样的属性作为分裂属性，

18、那么将产生非常多的分支，而且每一个分支产生的子集的熵均为0由于子集中只需一个样本！。显然，这样的决策树是没有实践意义的。因此，Quinlan提出运用增益比例来替代信息增益。 3.2.2 C4.5.设S代表训练数据集，由s个样本组成。A是S的某个属性，有m个不同的取值，根据这些取值可以把S划分为m个子集，Si表示第i个子集i=1,2,m，|Si|表示子集Si中的样本数量。那么：称为“数据集S关于属性A的熵。 .用来衡量属性A分裂数据集的广度和均匀性。样本在属性A上的取值分布越均匀，Split_Info(S,A)的值就越大。增益比例的定义为：增益比例消除了选择那些值较多且均匀分布的属性作为分裂属性

19、的倾向性。.延续属性的处置 设属性Y有m个不同的取值，按大小顺序升序陈列为v1v2, vi将数据集划分为两个部分，构成两个分支。显然， v1,v2, vm-1就是能够的阈值的集合，共(m-1)个元素。把这些阈值一一取出来，并根据“Yvi和“Y vi把训练数据集划分为两个子集，并计算每一种划分方案下的信息增益或增益比例，选择最大增益或增益比例所对应的那个阈值，作为最优的阈值。可以看出，假设选择延续属性作为分裂属性，那么分裂后只需两个分支，而不象离散属性那样能够会有多个分支由离散属性的取值个数决议。 .假设要计算“年龄属性的信息增益，那么首先将不同的属性值排序20,25,28,40,46,55,5

20、6,58,60,65,70那么能够的阈值集合为20,25,28,40,46,55,56,58,60,65,70，从中一一取出，并构成分裂谓词，例如取出“20，构成谓词“20和“20，用它们划分训练数据集，然后计算信息增益或增益比例。 .处置有缺失值的样本 C4.5并不会武断地将一个有缺失值的样本丢弃,也不会随意地将它分配到某个类别中去。 “收入程度的值，取为“高的概率为3/12，取为“中的概率为5/12，取为“低的概率为4/12。S1收入程度=“高的样本数量为：3+2(3/12)； .3.2.4 C5.0算法C5.0是经典的决策树模型的算法之一，可生成多分支的决策树，目的变量为分类变量运用c5

21、.0算法可以生成决策树decision tree或者规那么集rule sets。C5.0模型根据可以带来最大信息增益information gain的字段拆分样本。第一次拆分确定的样本子集随后再次拆分，通常是根据另一个字段进展拆分，这一过程反复进展直到样本子集不能再被拆分为止。最后，重新检验最低层次的拆分，那些对模型值没有显著奉献的样本子集被剔除或者修剪。 .C5.0的优点优点：C5.0模型在面对数据脱漏和输入字段很多的问题时非常稳健。C5.0模型通常不需求很长的训练次数进展估计。C5.0模型比一些其他类型的模型易于了解，模型推出的规那么有非常直观的解释。C5.0也提供强大的加强技术以提高分类

22、的精度。C5.0算法选择分支变量的根据以信息熵的下降速度作为确定最正确分支变量和分割阀值的根据。信息熵的下降意味着信息的不确定性下降.举例：在Clementine中运用C5.0这里，以学生参与某次社会公益活动的数据文件名为Students.xls为例，讲解C5.0算法的详细实现操作。分析目的是，研讨那些要素将显著影响到学生参与社会公益活动。 其中，能否参与为输出变量，除编号以外的变量均为输入变量。.数据流如下：.一、建立模型 第一步建立数据源，第二步选择Modeling卡中的C5.0节点并将其衔接到恰当位置，鼠标右击该节点，弹出下面窗口。模型称号Model name输出类型Output typ

23、e：此处指定希望最终生成的模型是决策树还是规那么集。群体字符Group symbolics。假设选择该选项，C5.0会尝试将一切与输出字段格式类似的字符值合并。假设没有选择该选项，C5.0会为用于拆分母节点的字符字段的每个值创建一个子节点。运用自举法Use boosting：提高其准确率。这种方法按序列建立多重模型。第一个模型以通常的方式建立。随后，建立第二个模型，聚焦于被第一个模型错误分类的记录。以此类推，最后运用整个模型集对样本进展分类，运用加权投票过程把分散的预测合并成综合预测。The Number of trials选项允许控制用于助推的模型数量。.交叉验证Crossvalidate：

24、假设选择了该选项，C5.0将运用一组基于训练数据子集建立的模型，来估计基于全部数据建立的模型的准确度。假设数据集过小，不能拆分成传统意义上的训练集和测试集，这将非常有用。或用于交叉验证的模型数目。方式Mode：对于简单的训练，绝大多数C5.0参数是自动设置。高级训练方式选项允许对训练参数更多的直接控制。.简单方式选项simple偏好Favor：在accuracy下，C5.0会生成尽能够准确的决策树。在某些情况下，这会导致过度拟和。选择Generality普通化项以运用不易受该问题影响的算法设置。期望噪声百分数Expected noise %：指定训练集中的噪声或错误数据期望比率。.高级方式选项

25、修剪纯度pruning severity：决议生成决策树或规那么集被修剪的程度。提高纯度值将获得更小，更简约的决策树。降低纯度值将获得更加准确的决策树。子分支最少记录数Minimum records per child branch：子群大小可以用于限制决策树任一分支的拆分数。只需当两个或以上的后序子分支包括来自训练集的记录不少于最小记录数，决策树才会继续拆分。默许值为2，提高该值将有助于防止噪声数据的过度训练。全局修剪Use global pruning： 第一阶段：部分建筑 第二阶段：全局修剪排除属性Winnow attributes：假设选择了该选项，C5.0会在建立模型前检验预测字段的

26、有用性。被发现与分析无关的预测字段将不参与建模过程。这一选项对有许多预测字段元的模型非常有用，并且有助于防止过度拟和。 .图1 指定错误归类损失错误归类损失允许指定不同类型预测错误之间的相对重要性。错误归类损失矩阵显示预测类和实践类每一能够组合的损失。一切的错误归类损失都预设设置为1.0。要输入自定义损失值，选择Use misclassification costs，然后把自定义值输入到损失矩阵中。.详细设置.执行结果.二、预测结果 为观测C5.0对每个样本的预测结果，可在流管理器的Models卡中，鼠标右击C5.0模型结果，选择弹出菜单中的Add To Stream，并将模型结果衔接到数据流

27、中，然后衔接Table节点查看预测结果，如以下图所示：.三、C5.0模型评价.3.3 CART分类和回归树Classification and Regression Trees，CART,在Clementine中简写为C&RTCART算法中的每一次分裂把数据分为两个子集，每个子集中的样本比被划分之前具有更好的一致性。它是一个递归的过程，也就是说，这些子集还会被继续划分，这个过程不断反复，直到满足终止准那么，然后经过修剪和评价，得到一棵最优的决策树。.三个步骤生成最大树生成一棵充分生长的最大树树的修剪根据修剪算法对最大树进展修剪，生成由许多子树组成的子树序列子树评价从子树序列中选择一棵最优的子树作为最后的结果。 .3.3.1 生成最大树规范问题集 就某个给定的属性来说，由于属性的取值能够有很多个，所以按照这个属性来分裂数据集的方式也有很多种，属性的规范问题集就是一切候选分支方案的集合。延续属性的规范问题集离散属性的规范问题集.杂度 在ID3算法中，用“熵来度量数据集随机性的程度。在CART中我们把这种随机性的程度称为“杂度impurity，也称为“不纯度，并且用“吉尼(gini)目的来衡量它。 .吉尼目的 设t是决策树上的某个节点，该节点的数据集为S，由s个样本组成，其类标号属性具有m个不同的取值，即定义了m个不同的类Cii=1,2,m。设属于类Ci的样本的个数