《第4章分类基本概念决策树与模型评估ppt课件》由会员分享，可在线阅读，更多相关《第4章分类基本概念决策树与模型评估ppt课件（91页珍藏版）》请在金锄头文库上搜索。
1、数据发掘数据发掘 分类：根本概念、决策树与模型评价分类：根本概念、决策树与模型评价第4章 分类：根本概念、决策树与模型评价l 分类的是利用一个分类函数分类模型、分类器，该模型能把数据库中的数据影射到给定类别中的一个。l 分类分类l训训练练集集：数数据据库库中中为为建建立立模模型型而而被被分分析析的的数数据元组构成训练集。据元组构成训练集。l训训练练集集中中的的单单个个元元组组称称为为训训练练样样本本, ,每每个个训训练样本有一个类别标志。练样本有一个类别标志。l一一个个详详细细样样本本的的方方式式可可为为:( :( v1, v1, v2, v2, ., ., vn; c );vn; c );其
2、中其中vivi表示属性值表示属性值,c,c表示类别。表示类别。l测试集：用于评价分类模型的准确率测试集：用于评价分类模型的准确率数据分类数据分类一个两步过程一个两步过程 (1)l第一步，建立一个模型，描画预定数据类集和概念集l假定每个元组属于一个预定义的类，由一个类标号属性确定l学习模型可以用分类规那么、决策树或数学公式的方式提供数据分类数据分类一个两步过程一个两步过程 (2)l第二步，运用模型，对未来的或未知的对象进展分类l首先评价模型的预测准确率l对每个测试样本，将知的类标号和该样本的学习模型类预测比较l模型在给定测试集上的准确率是正确被模型分类的测试样本的百分比l测试集要独立于训练样本集
3、，否那么会出现“过分顺应数据的情况l假设准确性能被接受，那么分类规那么就可用来对新数据进展分类 有监视的学习有监视的学习 VS. 无监视的学习无监视的学习l有监视的学习用于分类l模型的学习在被告知每个训练样本属于哪个类的“监视下进展l新数据运用训练数据集中得到的规那么进展分类l无监视的学习用于聚类l每个训练样本的类编号是未知的，要学习的类集合或数量也能够是事先未知的l经过一系列的度量、察看来建立数据中的类编号或进展聚类分类模型的构造方法分类模型的构造方法l1.1.机器学习方法：机器学习方法：l决策树法决策树法l规那么归纳规那么归纳l2.2.统计方法：知识表示是判别函数和原型事例统计方法：知识表
4、示是判别函数和原型事例l贝叶斯法贝叶斯法l非参数法非参数法( (近邻学习或基于事例的学习近邻学习或基于事例的学习) ) l3.3.神经网络方法：神经网络方法：lBPBP算法算法, ,模型表示是前向反响神经网络模型模型表示是前向反响神经网络模型l4.4.粗糙集粗糙集(rough set)(rough set)知识表示是产生式规那么知识表示是产生式规那么一个决策树的例子一个决策树的例子categoricalcategoricalcontinuousclassRefundMarStTaxIncYESNONONOYesNoMarried Single, Divorced 80KSplitting At
5、tributes训练数据训练数据模型模型: 决策树决策树决策树的另一个例子决策树的另一个例子categoricalcategoricalcontinuousclassMarStRefundTaxIncYESNONONOYesNoMarried Single, Divorced 80K用决策树归纳分类用决策树归纳分类l什么是决策树？l类似于流程图的树构造l每个内部节点表示在一个属性上的测试l每个分枝代表一个测试输出l每个树叶节点代表类或类分布l决策树的生成由两个阶段组成l决策树构建l开场时，一切的训练样本都在根节点l递归的经过选定的属性，来划分样本 必需是离散值l树剪枝l许多分枝反映的是训练数据
6、中的噪声和孤立点，树剪枝试图检测和剪去这种分枝l决策树的运用：对未知样本进展分类l经过将样本的属性值与决策树相比较决策树分类义务决策树分类义务Decision Tree一个决策树的例子一个决策树的例子categoricalcategoricalcontinuousclassRefundMarStTaxIncYESNONONOYesNoMarried Single, Divorced 80KSplitting Attributes训练数据训练数据模型模型: 决策树决策树运用决策树进展分类运用决策树进展分类RefundMarStTaxIncYESNONONOYesNoMarried Single,
7、 Divorced 80K测试数据测试数据Start from the root of tree.运用决策树进展分类运用决策树进展分类RefundMarStTaxIncYESNONONOYesNoMarried Single, Divorced 80K测试数据测试数据运用决策树进展分类运用决策树进展分类RefundMarStTaxIncYESNONONOYesNoMarried Single, Divorced 80K测试数据测试数据运用决策树进展分类运用决策树进展分类RefundMarStTaxIncYESNONONOYesNoMarried Single, Divorced 80K测试数据
8、测试数据运用决策树进展分类运用决策树进展分类RefundMarStTaxIncYESNONONOYesNoMarried Single, Divorced 80K测试数据测试数据运用决策树进展分类运用决策树进展分类RefundMarStTaxIncYESNONONOYesNoMarried Single, Divorced 80K测试数据测试数据Assign Cheat to “No决策树分类决策树分类Decision Tree决策树决策树l有许多决策树算法:lHunt算法l信息增益Information gain ID3l增益比率Gain rationC4.5l基尼指数Gini index
9、(SLIQ，SPRINT) Hunt 算法算法l设 Dt 是与结点 t相关联的训练记录集l算法步骤:l假设Dt 中一切记录都属于同一个类 yt, 那么t是叶结点，用yt标志l假设 Dt 中包含属于多个类的记录，那么选择一个属性测试条件，将记录划分成较小的子集。对于测试条件的每个输出，创建一个子结点，并根据测试结果将Dt中的记录分布到子结点中。然后，对于每个子结点，递归地调用该算法Dt?Hunt算法算法Dont CheatRefundDont CheatDont CheatYesNoRefundDont CheatYesNoMaritalStatusDont CheatCheatSingle,D
10、ivorcedMarriedTaxableIncomeDont Cheat= 80KRefundDont CheatYesNoMaritalStatusDont CheatCheatSingle,DivorcedMarried决策树决策树lHunt算法采用贪婪战略构建决策树.l在选择划分数据的属性时，采取一系列部分最优决策来构造决策树.l决策树归纳的设计问题l如何分裂训练记录l怎样为不同类型的属性指定测试条件?l怎样评价每种测试条件?l如何停顿分裂过程决策树决策树lHunt算法采用贪婪战略构建决策树.l在选择划分数据的属性时，采取一系列部分最优决策来构造决策树.l决策树归纳的设计问题l如何分裂
11、训练记录l怎样为不同类型的属性指定测试条件?l怎样评价每种测试条件?l如何停顿分裂过程怎样为不同类型的属性指定测试条件怎样为不同类型的属性指定测试条件?l依赖于属性的类型l标称l序数l延续l依赖于划分的路数l2路划分l多路划分基于标称属性的分裂基于标称属性的分裂l多路划分: 划分数输出数取决于该属性不同属性值的个数. l二元划分: 划分数为2，这种划分要思索创建k个属性值的二元划分的一切2k-1-1种方法.CarTypeFamilySportsLuxuryCarTypeFamily, LuxurySportsCarTypeSports, LuxuryFamilyORCarTypeFamily,
12、 SportsLuxury l多路划分: 划分数输出数取决于该属性不同属性值的个数.l二元划分: 划分数为2，需求坚持序数属性值的有序性.基于序数属性的划分基于序数属性的划分SizeSmallMediumLargeSizeMedium, LargeSmallSizeSmall, MediumLargeORSizeSmall, LargeMedium基于延续属性的划分基于延续属性的划分l多路划分:viAvi+1i=1,k) l二元划分: (A v) or (A v)l思索一切的划分点，选择一个最正确划分点v基于延续属性的划分基于延续属性的划分决策树决策树决策树归纳的设计问题如何分裂训练记录怎样为
13、不同类型的属性指定测试条件?怎样评价每种测试条件?如何停顿分裂过程怎样选择最正确划分？怎样选择最正确划分？在划分前在划分前: 10 个记录个记录 class 0, 10 个记录个记录 class 1怎样选择最正确划分？怎样选择最正确划分？l选择最正确划分的度量通常是根据划分后子结点不纯性的程度。不纯性的程度越低，类分布就越倾斜 l结点不纯性的度量:不纯性大不纯性大不纯性小不纯性小怎样找到最正确划分？怎样找到最正确划分？B?YesNoNode N3Node N4A?YesNoNode N1Node N2划分前划分前:M0M1M2M3M4M12M34Gain = M0 M12 vs M0 M34结
14、点不纯性的丈量结点不纯性的丈量lGinilEntropylclassification error不纯性的丈量不纯性的丈量: GINIl给定结点t的Gini值计算 :l(p( j | t) 是在结点t中，类j发生的概率).l当类分布平衡时，Gini值到达最大值 (1 - 1/nc) l相反当只需一个类时，Gini值到达最小值0计算计算 GINI的例子的例子P(C1) = 0/6 = 0 P(C2) = 6/6 = 1Gini = 1 P(C1)2 P(C2)2 = 1 0 1 = 0 P(C1) = 1/6 P(C2) = 5/6Gini = 1 (1/6)2 (5/6)2 = 0.278P(
15、C1) = 2/6 P(C2) = 4/6Gini = 1 (2/6)2 (4/6)2 = 0.444基于基于 GINI的划分的划分l当一个结点 p 分割成 k 个部分 (孩子), 划分的质量可由下面公式计算l l ni = 孩子结点 i的记录数,l n = 父结点 p的记录数.二元属性二元属性: 计算计算 GINIl对于二元属性，结点被划分成两个部分l得到的GINI值越小，这种划分越可行.B?YesNoNode N1Node N2Gini(N1) = 1 (5/6)2 (2/6)2 = 0.194 Gini(N2) = 1 (1/6)2 (4/6)2 = 0.528Gini split= 7
16、/12 * 0.194 + 5/12 * 0.528= 0.333标称属性标称属性:计算计算Ginil多路划分l二元划分l普通多路划分的Gini值比二元划分小，这一结果并不奇异，由于二元划分实践上合并了多路划分的某些输出，自然降低了子集的纯度Multi-way splitTwo-way split (find best partition of values)延续属性延续属性: 计算计算 Ginil运用二元划分l划分点v选择lN个记录中一切属性值作为划分点l对每个划分进展类计数, A v and A vl计算每个候选点v的Gini目的，并从中选择具有最小值的候选划分点l时间复杂度为(n2)延续
17、属性延续属性: 计算计算 Gini.l降低计算复杂性的方法,l将记录进展排序l从两个相邻的排过序的属性值之间选择中间值作为划分点l计算每个候选点的Gini值l时间复杂度为nlogn划分点划分点排序后的值排序后的值 l定义：给定一个概率空间 事件的自信息定义为 因 自信息反映了事件 发生所需求的信息量。 值越大阐明需求越多的信息才干确定事件 的发生，其随机性也越大，而当 发生时所携带的信息量也越大。反过来， 值越小，需求较少信息量就能确定 的发生，即事件 随机性较小。当其发生时所携信息量就少。 是对不确定性大小的一种描写 熵熵-定义定义熵熵-定义定义l1.定义：在概率空间 上定义的随机变量 I(
18、 X)的数学期望 l 称为随机变量X的平均自信息，又称X的信息熵或熵记为H(x) l非负性：H大于等于0 l延续性：H对恣意q延续l极值性：当q都等于1K时 H到达最大值logK熵熵-定义定义基于基于 Information Gain的划分的划分l给定结点t的 Entropy值计算 :l(p( j | t) 是在结点t中，类j发生的概率).l当类分布平衡时， Entropy值到达最大值 (log nc)l相反当只需一个类时，Gini值到达最小值0lEntropy 与 GINI类似计算计算 Entropy的例子的例子P(C1) = 0/6 = 0 P(C2) = 6/6 = 1Entropy =
19、 0 log 0 1 log 1 = 0 0 = 0 P(C1) = 1/6 P(C2) = 5/6Entropy = (1/6) log2 (1/6) (5/6) log2 (1/6) = 0.65P(C1) = 2/6 P(C2) = 4/6Entropy = (2/6) log2 (2/6) (4/6) log2 (4/6) = 0.92基于基于 Information Gain的划分的划分.lInformation Gain: l l l ni = 孩子结点 i的记录数,l n = 结点 p的记录数. l在 ID3 and C4.5中运用基于基于 Information Gain的划分
20、的划分.l增益率Gain Ratio: l熵和Gini目的等不纯性趋向于有利于具有大量不同值的属性!如：利用雇员id产生更纯的划分，但它却毫无用途l每个划分相关联的记录数太少，将不能做出可靠的预测l处理该问题的战略有两种：l限制测试条件只能是二元划分l运用增益率。K越大Split Info越大增益率越小基于基于 Classification Error的划分的划分l给定结点t的 Classification Error值计算 :l当类分布平衡时， error值到达最大值 (1 - 1/nc) l相反当只需一个类时， error值到达最小值0例子例子P(C1) = 0/6 = 0 P(C2) =
21、 6/6 = 1Error = 1 max (0, 1) = 1 1 = 0 P(C1) = 1/6 P(C2) = 5/6Error = 1 max (1/6, 5/6) = 1 5/6 = 1/6P(C1) = 2/6 P(C2) = 4/6Error = 1 max (2/6, 4/6) = 1 4/6 = 1/3不纯性度量之间的比较不纯性度量之间的比较二元分类问题二元分类问题:决策树决策树lHunt算法采用贪婪战略构建决策树.l在选择划分数据的属性时，采取一系列部分最优决策来构造决策树.l决策树归纳的设计问题l如何分裂训练记录l怎样为不同类型的属性指定测试条件?l怎样评价每种测试条件?
22、l如何停顿分裂过程停顿分裂过程停顿分裂过程l当一切的记录属于同一类时，停顿分裂l当一切的记录都有一样的属性时，停顿分裂l提早终止树的生长三种著名的决策树三种著名的决策树lCart：根本的决策树算法lId3：利用增益比不纯性，树采用二叉树，停顿准那么为当一切的记录属于同一类时，停顿分裂，或当一切的记录都有一样的属性时，停顿分裂lC4.5：id3的改良版本，也是最流行的分类数算法。采用多重分支和剪枝技术。决策树决策树l特点:l决策树是一种构建分类模型的非参数方法l不需求昂贵的的计算代价l决策树相对容易解释l决策树是学习离散值函数的典型代表l决策数对于噪声的干扰具有相当好的鲁棒性l冗余属性不会对决策
23、树的准确率呵斥不利影响l数据碎片问题。随着数的生长，能够导致叶结点记录数太少，对于叶结点代表的类，不能做出具有统计意义的判决l子树能够在决策树中反复多次。使决策树过于复杂子树反复问题子树反复问题 Same subtree appears in multiple branches决策边境决策边境 斜决策树斜决策树x + y 1Class = + Class = 模型过分拟合和拟合缺乏模型过分拟合和拟合缺乏l分类模型的误差大致分为两种：l训练误差：是在训练记录上误分类样本比例l泛化误差：是模型在未知记录上的期望误差l一个好的分类模型不仅要可以很好的拟合训练数据，而且对未知样本也要能准确分类。l换句
24、话说，一个好的分类模型必需具有低训练误差和低泛化误差。l当训练数据拟合太好的模型，其泛化误差能够比具有较高训练误差的模型高，这种情况成为模型过分拟合模型过分拟合和拟合缺乏模型过分拟合和拟合缺乏l当决策树很小时，训练和检验误差都很大，这种情况称为模型拟合缺乏。出现拟合缺乏的缘由是模型尚未学习到数据的真实构造。l随着决策树中结点数的添加，模型的训练误差和检验误差都会随之下降。l当树的规模变得太大时，即使训练误差还在继续降低，但是检验误差开场增大，导致模型过分拟合模型模型过分拟合和拟合缺乏模型模型过分拟合和拟合缺乏过分拟合过分拟合导致过分拟合的缘由导致过分拟合的缘由导致过分拟合的缘由导致过分拟合的缘
25、由l噪声导致的过分拟合l例子：哺乳动物的分类问题l十个训练记录中有两个被错误标志：蝙蝠和鲸l假设完全拟合训练数据，决策树1的训练误差为0，但它在检验数据上的误差达30%.人和海豚，针鼹误分为非哺乳动物l相反，一个更简单的决策树2，具有较低的检验误差10%，虽然它的训练误差较高，为20%l决策树1过分拟合了训练数据。由于属性测试条件4条腿具有欺骗性，它拟合了误标志的训练纪录，导致了对检验集中记录的误分类噪声导致的过分拟合例子噪声导致的过分拟合例子噪声导致决策边境的改动噪声导致决策边境的改动缺乏代表性样本导致的过分拟合缺乏代表性样本导致的过分拟合l根据少量训练记录做出分类决策的模型也容易受过分拟合
26、的影响。l由于训练数据缺乏具有代表性的样本，在没有多少训练记录的情况下，学习算法依然细化模型就会产生过分拟合。l例子：五个训练记录，一切的记录都是正确标志的，对应的决策树虽然训练误差为0，但检验误差高达30%l人、大象和海豚被误分类，由于决策树把恒温但不冬眠的动物分为非哺乳动物。决策树做出这样的分类决策是由于只需一个训练记录鹰具有这些特征。l这个例子清楚的阐明，当决策树的叶结点没有足够的代表性样本时，很能够做出错误的预测。过分拟合与多重比较过分拟合与多重比较l模型的过分拟合能够出如今运用多重比较过程的算法中l多重比较的例子：思索未来十个买卖日股市是升还是降l一个人十次猜测至少正确预测八次的概率
27、是：0.0547l假设从50个股票分析家中选择一个投资顾问，战略是选择在未来的十个买卖日做出最多正确预测的分析家。l该战略的缺陷是，即使一切的分析家都用随机猜测做出预测，至少有一个分析家做出八次正确预测的概率是：1-1-0.054750=0.9399，这一结果相当高。l多重比较过程与模型过分拟合有什么关系？l在决策树增长过程中，可以进展多种测试，以确定哪个属性可以最好的划分训练数据。l在这种情况下，算法实践上是运用多重比较过程来决议能否需求扩展决策树。l当候选属性多，训练记录数少时，这种影响就变得更加明显。泛化误差估计泛化误差估计l过分拟合的主要缘由不断是个争辩的话题，但大家还是普遍赞同模型的
28、复杂度对模型的过分拟合有影响。l如何确定正确的模型复杂度？理想的复杂度是能产生最低泛化误差的模型的复杂度。l估计泛化误差的方法l运用再代入估计。用训练误差提供对泛化误差的乐观估计l结合模型复杂度l估计统计上界l运用确定集结合模型复杂度结合模型复杂度l奥卡姆剃刀 Occams Razor ：给定两个具有一样泛化误差的模型，较简单的模型比复杂的模型更可取l 由于复杂模型中的附加成分很大程度上是偶尔的拟合。因此，分类模型评价应把模型复杂度思索进去l方法：悲观误差估计、最小描画长度原那么MDL悲观误差评价悲观误差评价悲观误差估计公式：Q(ti)为每个结点ti的罚分，e(T)为训练样本集的错分样本数，N
29、t为训练样本总数，k为叶结点数。l例子1：假设罚分等于0.5，训练样本集中样本数为24个，我们构建了7个叶结点的决策树，训练样本集的错分样本数为4l根据公式我们得e(T)=(4+7*0.5)/24=0.3125l例子2：假设罚分等于0.5，训练样本集中样本数为24个，我们构建了4个叶结点的决策树，训练样本集的错分样本数为6l根据公式我们得e(T)=(6+4*0.5)/24=0.3333l当罚分等于1时，例1，2为0.458，0.417l0.5的罚分项表示只需至少可以改良一个训练记录的分类，结点就该当扩展，由于扩展一个结点等价于总误差添加0.5，代价比犯一个训练错误小最小描画长度最小描画长度 (
30、MDL)lCost(Model,Data) = Cost(Data|Model) + Cost(Model)lCost 是传输总代价.l最小化cost值.lCost(Data|Model) 是误分类记录编码的开销.lCost(Model) 是模型编码的开销 .运用确认集运用确认集l该方法中，不是用训练集估计泛化误差，而是把原始的训练数据集分为两个较小的子集，一个子集用于训练，而另一个称为确认集，用于估计泛化误差。l该方法为评价模型在未知样本上的性能提供了较好方法。处置决策树中的过分拟合处置决策树中的过分拟合l先剪枝 (Early Stopping Rule)l树增长算法在产生完全拟合整个训练数
31、据集的之前就停顿决策树的生长l为了做到这一点，需求采用更具限制性的终了条件:l 当结点的记录数少于一定阈值，那么停顿生长l当不纯性度量的增益低于某个确定的阈值时，那么停顿生长 (e.g., information gain).l缺陷：很难为提早终止选取正确的阈值:l 阈值太高，导致拟合缺乏l阈值太低，导致不能充分处理过分拟合的问题。处置决策树中的过分拟合处置决策树中的过分拟合l后剪枝l在该方法中，初始决策树按照最大规模生长，然后进展剪枝的步骤，按照自底向上的方式修剪完全增长的决策树。l修剪有两种做法:l 用新的叶结点交换子树，该叶结点的类标号由子树下记录中的多数类确定l用子树中最常用的分支替代
32、子树处置决策树中的过分拟合处置决策树中的过分拟合与先剪枝相比，后剪枝技术倾向于产生更好的结果。由于不像先剪枝，后剪枝是根据完全增长的决策树作出的剪枝决策，先剪枝那么能够过早终止决策树的生长。然而，对于后剪枝，当子树被剪掉后，生长完全决策树的额外开销就被浪费了。不平衡类问题PREDICTED CLASSACTUALCLASSClass=YesClass=NoClass=Yesa(TP)b(FN)Class=Noc(FP)d(TN)准确率的缺陷准确率的缺陷l思索2类问题l类0的样本数 = 9990l类1的样本数 = 10l假设模型预测一切的样本为类0, l 准确率为 9990/10000 = 99
33、.9 %l准确率的值具有欺骗性l模型并没有分对类1的任何样本度量度量l精度确定在分类器断言为正类的那部分记录中实践为正类的记录所占的比例。精度越高，分类器的假正类错误率就越低。l召回率度量被分类器正确预测的正样本的比例。具有高召回率的分类器很少将正样本误分为负样本。ROC (Receiver Operating Characteristic)lROC曲线是显示分类器真正率TPR和假正率FPR之间折中的一种图形化方法。lROC 曲线上有几个关键点，它们有公认的解释：lTPR=0，FPR=0：把每个实例都预测为负类的模型lTPR=1，FPR=1：把每个实例都预测为正类的模型lTPR=1，FPR=0：理想模型运用运用ROC曲线比较模型曲线比较模型l没有哪个模型可以压倒对方lFRR0.36, M2较好lROC曲线下方的面积l理想情况: l 面积= 1l随机猜测:l 面积 = 0.5怎样产生怎样产生ROC曲线曲线Threshold = ROC 曲线曲线:
