决策树和模型评估课件(PPT-58张)

1、DataMining章分类：基本概念、决策树和模型评估4.1 预备知识4.2 解决分类问题的一般方法分类例子预测癌细胞是良性还是恶性将信用卡交易分为合法和欺诈分类：定义给定一个记录集 每个记录包含一个属性集，通常最后一个属性是该记录的分类（class ）属性.目标：找到一个模型（从其余属性值到分类属性的转换函数），实现对未知分类的记录进行尽可能精确地分类。通常，将给定的数据集分为训练集（training set ）和检验集（test set ） 。训练集用来创建模型，检验集用来验证模型的有效性。分类性能度量：预测的类类=1类=0实际的数类=1f11f10类=0f01f00分类过程训练集检验集学

2、习模型学习模型学习算法模型分类技术基于决策树的方法 Decision Tree based Methods基于规则的方法 Rule-based Methods基于记忆的推理 Memory based reasoning神经网络 Neural Networks朴素贝叶斯和贝叶斯信念网络 Nave Bayes and Bayesian Belief Networks支持向量机 Support Vector Machines决策树定义决策树是由结点和有向边组成的层次结构。树中包含三种结点：根结点内部结点叶结点非终结点。包含属性测试条件，用于分开不同特性的记录每个叶结点都赋予一个类标号决策树 例1二元

3、属性分类属性连续属性分类标号有房产婚姻状况收入YESNONONOYesNoMarried Single, Divorced 80K属性划分训练数据模型：决策树决策树 例2MarStRefundTaxIncYESNONONOYesNoMarried Single, Divorced 80K对于相同的数据，能构造多种不同的决策树决策树应用过程：使用模型测试数据1RefundMarStTaxIncYESNONONOYesNoMarried Single, Divorced 80K检验数据从树根开始使用模型测试数据2RefundMarStTaxIncYESNONONOYesNoMarried Sing

4、le, Divorced 80KTest Data使用模型测试数据3RefundMarStTaxIncYESNONONOYesNoMarried Single, Divorced 80KTest Data使用模型测试数据4RefundMarStTaxIncYESNONONOYesNoMarried Single, Divorced 80KTest Data使用模型测试数据5RefundMarStTaxIncYESNONONOYesNoMarried Single, Divorced 80KTest Data使用模型测试数据6RefundMarStTaxIncYESNONONOYesNoMarr

5、ied Single, Divorced 80KTest Data将Cheat赋值为“No”决策树构造算法多种算法:Hunt 算法(最早方法之一)CART（ classification and regression trees）ID3, C4.5SLIQ,SPRINTHunt 算法结构Hunt算法的思想是将训练记录相继划分成“较纯”的子集，以递归方式建立决策树。 假设t表示结点， Dt 表示与结点t相关联的训练记录集，y=y1,y2,yc是类标号Hunt算法的递归定义:如果Dt 中所有记录都属于同一个类yt, 则t就是叶子节点，并用yt标号如果Dt 是一个空集，那么t就是叶子节点，其标号为其

6、父结点上训练记录中的多数类Dt?如果Dt 中包含属于多个类的记录，则选择一个属性测试条件，将记录划分成若干个子集。并对每个子集进行递归分类。例 P93P95 预测拖欠银行贷款的贷款者如何生成决策树？贪婪策略.每次选择属性划分条件时，选择划分数据的最优标准.决策树归纳的设计问题问题1：如何分裂记录？1.1定义属性测试条件给不同类型的属性指定测试条件的方法1.2找到最好的划分方法对每种测试条件进行评估测量问题2：何时停止分裂过程？决策树归纳的设计问题1：1.1 定义属性测试条件4.4.3 表示属性测试条件的方法根据属性类型标称型 Nominal序数型 Ordinal连续型 Continuous按划

7、分路数二元划分 2-way split多路划分 Multi-way split标称属性的划分方法：(数据集见P122习题2)多路划分法: 划分成几个不同的值输出数取决于该属性不同属性值的个数. 二分法: 划分为两个不同的值. （需要找到最佳的划分方法）CarTypeFamilySportsLuxuryCarTypeFamily, LuxurySportsCarTypeSports, LuxuryFamilyOR多路划分法二分法（分组必须保留属性值之间的序关系）注意：第三种划分方法合理吗?序数属性的划分方法：SizeSmallMediumLargeSizeMedium, LargeSmallSi

8、zeSmall, MediumLargeORSizeSmall, LargeMedium连续属性的划分方法多路划分：离散化属性值，每个离散化区间赋予一个新的序数值二分法： (A v) or (A v) 需要从所有可能的划分点中选择产生最佳划分的点决策树归纳的设计问题1：1.2 找到最好划分方法 划分前: 数据集有20个记录，标号为class 0和class 1的各有10个。哪个划分测试条件最佳？ 为了度量不同的测试条件，常用划分前和划分后记录的类分布定义： p(i|t)表示结点t中，属于类i的记录所占的比例，常简记为pi。 在二元分类问题中，任意结点的类分布可以记作(p0，p1)，其中p1 =

9、1- p0 。选择最佳划分的度量选择最佳划分的度量通常是根据划分后子女结点不纯性的程度：不纯的程度越低，类分布就越倾斜，划分就越好。不同类，具有较高的不纯度同类，具有较低的不纯度结点不纯度的度量方法：熵 Entropy基尼指数 Gini Index分类差错率 Classification error计算不纯性方法1: 熵结点t的熵: 其中，c为结点t中不同类标号个数 p( i | t)是给定结点t中属于类i的记录所占比例，简记为pi结点熵值的取值范围：当记录均匀分布于各分类时，将取得最大值(log nc) 当所有记录都属于同一分类时，将取得最小值(0)例：分别计算3个结点的熵P(C0) = 0

10、/6 = 0 P(C1) = 6/6 = 1Entropy = 0log 0 1log 1 = 0 0 = 0 P(C0) = 1/6 P(C1) = 5/6Entropy = (1/6)log2 (1/6) (5/6)log2 (5/6) = 0.65P(C0) = 2/6 P(C1) = 4/6Entropy = (2/6)log2 (2/6) (4/6)log2 (4/6) = 0.92练习1已知：数据见课本表4-7（ P122 题2），采用熵作为结点的不纯度度量。问题：整个训练样本集的不纯度是多少？如果对数据按车型属性进行多路划分，则（车型=运动）的结点的不纯度是多少？（车型=豪华）的

11、结点的不纯度是多少？（车型=家用）的结点的不纯度是多少？计算不纯性方法2: 基尼指数（gini）结点t的吉尼指数: 其中，c为结点t中不同类标号个数 p( i | t)是给定结点t中属于类i的记录所占比例，简记为pi结点Gini指数的取值范围：当记录均匀分布于各分类时，将取得最大值(1 - 1/nc)当所有记录都属于同一分类时，将取得最小值(0)例：分别计算3个结点的Gini指数P(C0) = 0/6 = 0 P(C1) = 6/6 = 1Gini = 1 P(C0)2 P(C1)2 = 1 0 1 = 0 P(C0) = 1/6 P(C1) = 5/6Gini = 1 (1/6)2 (5/6

12、)2 = 0.278P(C0) = 2/6 P(C1) = 4/6Gini = 1 (2/6)2 (4/6)2 = 0.444练习2已知：数据见课本表4-7（ P122 题2），采用Gini指数作为结点的不纯度度量。问题：整个训练样本集的不纯度是多少？如果对数据按车型属性进行多路划分，则（车型=运动）的结点的不纯度是多少？（车型=豪华）的结点的不纯度是多少？（车型=家用）的结点的不纯度是多少？计算不纯性方法3:分类差错率节点t的分类差错率: p(i|t)是给定结点t中属于类i的记录所占比例，简记为pi结点分类误差率指数的取值范围：当记录均匀分布于各分类时，将取得最大值(1 - 1/nc) 当所

13、有记录都属于同一分类时，将取得最小值(0)例：分别计算3个子女结点的分类差错率P(C0) = 0/6 = 0 P(C1) = 6/6 = 1Error = 1 max (0, 1) = 1 1 = 0 P(C0) = 1/6 P(C1) = 5/6Error = 1 max (1/6, 5/6) = 1 5/6 = 1/6P(C0) = 2/6 P(C1) = 4/6Error = 1 max (2/6, 4/6) = 1 4/6 = 1/3练习3已知：数据见课本表4-7（ P122 题2），采用分类误差率作为结点的不纯度度量。问题：整个训练样本集的不纯度是多少？如果对数据按车型属性进行多路划

14、分，则（车型=运动）的结点的不纯度是多少？（车型=豪华）的结点的不纯度是多少？（车型=家用）的结点的不纯度是多少？二元分类问题结点不纯性度量之间的比较：利用不纯性度量，选择最佳划分方法：分别比较父节点（划分前）的不纯程度和子女结点（划分后）的不纯程度，它们的差值越大，测试条件的效果就越好。用增益来作为确定划分效果的标准 其中：I(.)是结点不纯性度量,N是父节点上的记录总数，k是父节点的分支数，N(vj)是子女结点vj的记录个数。 决策树归纳算法，通常就是选择最大化增益的测试条件，作为当前节点的属性测试条件。利用增益来选择最佳划分示意：B?YesNoNode N3Node N4A?YesNoN

15、ode N1Node N2划分前M父亲Ma1Ma2Mb1Mb2MAMB比较增益: A(M父亲MA) vs. B(M父亲MB)计算不纯性计算不纯性计算不纯性计算不纯性加权平均加权平均练习4已知：数据见课本表4-7（ P122 题2）。问题(a)(g)熵和Gini指数等不纯度趋向有利于具有大量不同值的属性产生大量输出测试条件，从而导致与每个划分关联的记录很少。极端情况如：以顾客ID进行划分，比其他划分方法能得到更“纯”的派生结点改进方法信息增益（熵差）: ni = 孩子节点i的记录数 n = 节点p的记录数用于ID3和C4.5算法 增益率: 将父节点p划分为k部分n表示p的记录数ni 表示第i部分

16、（p的第i个节点）的记录数调整信息增益，引入划分信息SplitInfo，把属性测试条件产生的输出数也考虑进去。如果一个属性产生了大量的划分，它的划分信息SplitInfo将会很大，从而增益率降低。用于C4.5算法比较不同类型的属性的划分（以Gini指数为例）二元属性标称属性离散属性基于GINI指数的二元属性划分方法划分为两部分B?YesNoNode N1Node N2Gini(N1) = 1 (5/7)2 (2/7)2 = 0.194 Gini(N2) = 1 (1/5)2 (4/5)2 = 0.528Gini(Children) = 7/12 * 0.194 + 5/12 * 0.528=

17、0.333基于GINI指数的标称属性划分方法用矩阵帮助选择最佳划分Multi-way splitTwo-way split (find best partition of values)基于GINI指数的连续属性划分方法问题：需要选择候选划分点方法1:穷举法将记录中所有的属性值作为候选划分点，计算每个候选的Gini指标，并从中选择具有最小值的候选划分点。效率低计算代价昂贵改进方法：根据划分属性，先对记录进行排序从两个相邻的排过序的属性值中选择中间值作为候选划分点(55、65、72、80、）。在计算相邻结点时值，部分类分布保持不变，减少计算量。进一步优化：仅仅考虑位于具有不同类标号的两个相邻记录

18、之间的候选划分点（55、80、97），计算其Gini指数。候选划分点排序后的值决策树归纳的设计问题2：如何停止分裂过程？停止方法：方法1：当所有记录都属于同一分类时，停止划分方法2：当所有记录都有相似（相同）属性值时，停止划分方法3：提前终止4.3.5 决策树归纳算法算法输入：训练记录集E和属性集F。算法输出：构造的决策树主要函数：createNode()：建立一个新结点。结点要么表示一个测试条件(node.test_cond),要么表示一个类标号(node.label)find_best_split()：从剩余属性中挑选一个属性作为结点的测试条件。Classify()：为叶子结点确定类标号。

19、多数情况下，left.label=stopping_cond()：测试是否应该决策树的增长TreeGrowth算法框架（P101）if stopping_cond(E,F)= true thenleft=createNode()left.lable=Classify()return leafelseroot=createNode()root.test_cond=find_best_split(E,F)令V=v|v是root.test_cond的一个可能输出for 每个v V doEv=e|root.test_cond(e)=v 并且 eEchild=TreeGrowth(Ev,F)将child

20、作为root派生结点加到树中，将边(rootchild)记为vend forend ifreturn root案例学习：4.3.6 Web机器人检测阅读课本例子，回答下列问题：什么是Web使用挖掘？Web使用挖掘的数据源是什么？这些数据是如何得到的？为什么说在Web挖掘中，区分正常用户访问和Web机器人访问时重要的？本例子中，决策树模型是如何建立起来的？请你用1分钟长度的时间，叙述其建立的过程。根据课本的决策树模型，正常用户访问有何特征？4.3.7 决策树归纳的特点是一种构建分类模型的非参数方法大多决策树算法都采用启发式的方法来简化搜索决策树容易构建，对未知样本的分类也快决策树相对容易理解对于

21、噪声的干扰具有相当好的鲁棒性冗余属性不会对决策树的准确率造成不利影响对于数据碎片问题，可以通过规定阈值来检测和解决可能会产生子树在决策树中重复出现的情况对于非水平和垂直的决策边界问题，可以使用斜决策树或构造归纳方法来解决。不纯度度量方法的选择对决策树性能影响很小4.4分类模型的误差：训练误差：在训练记录上误分样本的比例泛化误差（检验误差）：模型在未知记录上的期望误差一个好的分类模型，必须具有低的训练误差和泛化误差。决策树分类方法存在的问题（与模型复杂度相关）模型拟合不足 Underfitting当模型过于简单时，训练误差和检验误差都比较大出现原因：模型尚未学习到数据的真实结构模型过分拟合 Ov

22、erfitting树的规模变得太大，即使训练误差还在继续降低，但是检验误差开始增大出现原因：模型过分拟合了训练数据中的噪声数据，或者是训练数据缺乏代表性的数据拟合不足 和 过分拟合Overfitting训练误差检验误差Underfitting噪声导致过分拟合决策边界被噪声点扭曲缺乏代表性样本导致过分拟合4.4.5 处理决策树归纳中的过分拟合先剪枝（提前终止规则）树增长算法在产生完全拟合整个训练数据集的完全增长的决策树之前就停止决策树的生长方法：选取不纯度增益的阈值优点：避免产生过分拟合训练数据的过于复杂的子树缺点：阈值大小难于选取后剪枝初始决策树按照最大规模生长，然后进行剪枝，按照自底向上的方

23、式修剪完全增长的决策树方法：用新结点代替子树；用子树的常用分支代替子树优点：避免过早终止决策树的生长缺点：需要浪费额外开销1、不是井里没有水，而是你挖的不够深。不是成功来得慢，而是你努力的不够多。2、孤单一人的时间使自己变得优秀，给来的人一个惊喜，也给自己一个好的交代。3、命运给你一个比别人低的起点是想告诉你，让你用你的一生去奋斗出一个绝地反击的故事，所以有什么理由不努力!4、心中没有过分的贪求，自然苦就少。口里不说多余的话，自然祸就少。腹内的食物能减少，自然病就少。思绪中没有过分欲，自然忧就少。大悲是无泪的，同样大悟无言。缘来尽量要惜，缘尽就放。人生本来就空，对人家笑笑，对自己笑笑，笑着看天下，看日出日落，花谢花开，岂不自在，哪里来的尘埃!5、心情就像衣服，脏了就拿去洗洗，晒晒，阳光自然就会蔓延开来。阳光那么好，何必自寻烦恼，过好每一个当下，一万个美丽的未来抵不过一个温暖的现在。6、无论你正遭遇着什么，你都要从落魄中站起来重振旗鼓，要继续保持热忱，要继续保持微笑，就像从未受伤过一样。7、生命的美丽，永远展现在她的进取之中;就像大树的美丽，是展现在它负势向上高耸入云的蓬勃生机中;像雄鹰的美丽，是展现在它搏风击雨如苍天之魂的翱翔中;像江河的美丽，是展现在它波