决策树和模型评估课件55523.pptx

Data Mining 第四章第四章分类：基本概念、决策树和模型评估分类：基本概念、决策树和模型评估 4.1 预备知识预备知识4.2 解决分类问题的一般方法解决分类问题的一般方法分类例子分类例子l预测癌细胞是良性还是恶性l将信用卡交易分为合法和欺诈l分类：定义分类：定义l给定一个记录集 每个记录包含一个属性集，通常最后一个属性是该记录的分类（class）属性.l目标：找到一个模型（从其余属性值到分类属性的转换函数），实现对未知分类的记录进行尽可能精确地分类。通常，将给定的数据集分为训练集（训练集（training set）和检验集（检验集（test set）。训练集用来创建模型，检验集用来验证模型的有效性。l分类性能度量：预测的类类=1类=0实际的数类=1f11f10类=0f01f00分类过程分类过程训练集训练集检验集检验集学习模型学习模型学习模型学习模型学习算法学习算法模型模型分类技术分类技术l基于决策树的方法 Decision Tree based Methodsl基于规则的方法 Rule-based Methodsl基于记忆的推理 Memory based reasoningl神经网络 Neural Networksl朴素贝叶斯和贝叶斯信念网络 Nave Bayes and Bayesian Belief Networksl支持向量机 Support Vector Machines决策树定义决策树定义l决策树是由结点和有向边组成的层次结构。l树中包含三种结点：根结点内部结点叶结点非终结点非终结点。包含属性测试条件测试条件，用于分开不同特性的记录每个叶结点都赋予一个类标号类标号决策树决策树 例例1二元属性二元属性分类属性分类属性连续属性连续属性分类标号分类标号有房产有房产婚姻状况婚姻状况收入收入YESNONONOYesNoMarried Single,Divorced 80K属性划分属性划分训练数据训练数据模型：决策树模型：决策树决策树决策树 例例2MarStRefundTaxIncYESNONONOYesNoMarried Single,Divorced 80K对于相同的数据，能构造多种不对于相同的数据，能构造多种不同的决策树同的决策树决策树应用过程：使用模型测试数据决策树应用过程：使用模型测试数据1RefundMarStTaxIncYESNONONOYesNoMarried Single,Divorced 80K检验数据检验数据从树根开始从树根开始使用模型测试数据使用模型测试数据2RefundMarStTaxIncYESNONONOYesNoMarried Single,Divorced 80KTest Data使用模型测试数据使用模型测试数据3RefundMarStTaxIncYESNONONOYesNoMarried Single,Divorced 80KTest Data使用模型测试数据使用模型测试数据4RefundMarStTaxIncYESNONONOYesNoMarried Single,Divorced 80KTest Data使用模型测试数据使用模型测试数据5RefundMarStTaxIncYESNONONOYesNoMarried Single,Divorced 80KTest Data使用模型测试数据使用模型测试数据6RefundMarStTaxIncYESNONONOYesNoMarried Single,Divorced 80KTest Data将Cheat赋值为“No”决策树构造算法决策树构造算法l多种算法:Hunt 算法(最早方法之一)CART（classification and regression trees）ID3,C4.5SLIQ,SPRINTHunt 算法结构算法结构lHunt算法的思想是将训练记录相继划分将训练记录相继划分成成“较纯较纯”的子集，以递归方式建立决的子集，以递归方式建立决策树。策树。假设t表示结点，Dt 表示与结点t相关联的训练记录集，y=y1,y2,yc是类标号lHunt算法的递归定义:如果Dt 中所有记录都属于同一个类yt,则t就是叶子节点，并用yt标号如果Dt 是一个空集，那么t就是叶子节点，其标号为其父结点上训练记录中的多数类Dt?如果Dt 中包含属于多个类的记录，则选择一个属性测试属性测试条件条件，将记录划分成若干个子集。并对每个子集进行递归分类。例 P93P95 预测拖欠银行贷款的贷款者如何生成决策树？如何生成决策树？l贪婪策略.每次选择属性划分条件时，选择划分数据的最优标准.l决策树归纳的设计问题问题1：如何分裂记录？u1.1定义属性测试条件给不同类型的属性指定测试条件的方法u1.2找到最好的划分方法对每种测试条件进行评估测量问题2：何时停止分裂过程？决策树归纳的设计问题决策树归纳的设计问题1：1.1 定义属性测试条件定义属性测试条件l4.4.3 表示属性测试条件的方法根据属性类型u标称型 Nominalu序数型 Ordinalu连续型 Continuous按划分路数u二元划分 2-way splitu多路划分 Multi-way split标称属性的划分方法：标称属性的划分方法：(数据集见数据集见P122习题习题2)l多路划分法多路划分法:划分成几个不同的值输出数取决于该属性不同属性值的个数.l二分法二分法:划分为两个不同的值.（需要找到最佳的划分方法）CarTypeFamilySportsLuxuryCarTypeFamily,LuxurySportsCarTypeSports,LuxuryFamilyORl多路划分法多路划分法l二分法二分法（分组必须保留属性值之间的序关系）注意：第三种划分方法合理吗?序数属性的划分方法：序数属性的划分方法：SizeSmallMediumLargeSizeMedium,LargeSmallSizeSmall,MediumLargeORSizeSmall,LargeMedium连续属性的划分方法连续属性的划分方法l多路划分：多路划分：离散化属性值，每个离散化区间赋予一个新的序数值l二分法：二分法：(A v)or(A v)需要从所有可能的划分点中选择产生最佳划分的点决策树归纳的设计问题决策树归纳的设计问题1：1.2 找到最好划分方法找到最好划分方法 划分前划分前:数据集有数据集有20个记录，标号为个记录，标号为class 0和和class 1的各有的各有10个。哪个划分测试条件最佳？个。哪个划分测试条件最佳？为了度量不同的测试条件，常用划分前和划分后记录的类分布类分布定义：p(i|t)表示结点t中，属于类i的记录所占的比例，常简记为pi。在二元分类问题中，任意结点的类分布可以记作(p0，p1)，其中p1=1-p0。选择最佳划分的度量选择最佳划分的度量l选择最佳划分的度量通常是根据划分后子女结点不纯性的程度：不纯的程度越低，类分布就越倾斜，划分就越好。不同类，具有较高的不纯度不同类，具有较高的不纯度同类，具有较低的不纯度同类，具有较低的不纯度结点不纯度的度量方法：结点不纯度的度量方法：l熵 Entropyl基尼指数 Gini Indexl分类差错率 Classification error计算不纯性方法计算不纯性方法1:熵熵l结点t的熵:其中，c为结点t中不同类标号个数 p(i|t)是给定结点t中属于类i的记录所占比例，简记为pil结点熵值的取值范围：当记录均匀分布于各分类时，将取得最大值(log nc)当所有记录都属于同一分类时，将取得最小值(0)例：分别计算例：分别计算3个结点的熵个结点的熵P(C0)=0/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练习练习1l已知：数据见课本表4-7（P122 题2），采用熵作为结点的不纯度度量。l问题：整个训练样本集的不纯度是多少？如果对数据按车型车型属性进行多路划分，则u（车型=运动）的结点的不纯度是多少？u（车型=豪华）的结点的不纯度是多少？u（车型=家用）的结点的不纯度是多少？计算不纯性方法计算不纯性方法2:基尼指数（基尼指数（gini）l结点t的吉尼指数:其中，c为结点t中不同类标号个数 p(i|t)是给定结点t中属于类i的记录所占比例，简记为pil结点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)2=0.278P(C0)=2/6 P(C1)=4/6Gini=1 (2/6)2 (4/6)2=0.444练习练习2l已知：数据见课本表4-7（P122 题2），采用Gini指数指数作为结点的不纯度度量。l问题：整个训练样本集的不纯度是多少？如果对数据按车型车型属性进行多路划分，则u（车型=运动）的结点的不纯度是多少？u（车型=豪华）的结点的不纯度是多少？u（车型=家用）的结点的不纯度是多少？计算不纯性方法计算不纯性方法3:分类差错率分类差错率l节点t的分类差错率:p(i|t)是给定结点t中属于类i的记录所占比例，简记为pil结点分类误差率指数的取值范围：当记录均匀分布于各分类时，将取得最大值(1-1/nc)当所有记录都属于同一分类时，将取得最小值(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练习练习3l已知：数据见课本表4-7（P122 题2），采用分分类误差率类误差率作为结点的不纯度度量。l问题：整个训练样本集的不纯度是多少？如果对数据按车型车型属性进行多路划分，则u（车型=运动）的结点的不纯度是多少？u（车型=豪华）的结点的不纯度是多少？u（车型=家用）的结点的不纯度是多少？二元分类问题结点不纯性度量之间的比较：二元分类问题结点不纯性度量之间的比较：利用不纯性度量，选择最佳划分利用不纯性度量，选择最佳划分l方法：分别比较父节点（划分前）的不纯程度和子女结点（划分后）的不纯程度，它们的差值越大，测试条件的效果就越好。l用增益增益来作为确定划分效果的标准 其中：I(.)是结点不纯性度量,N是父节点上的记录总数，k是父节点的分支数，N(vj)是子女结点vj的记录个数。决策树归纳算法，通常就是选择最大化增益决策树归纳算法，通常就是选择最大化增益的测试条件，作为当前节点的属性测试条件。的测试条件，作为当前节点的属性测试条件。利用增益利用增益来选择最佳划分示意：来选择最佳划分示意：B?YesNoNode N3Node N4A?YesNoNode N1Node N2划分前划分前M父亲父亲Ma1Ma2Mb1Mb2MAMB比较增益比较增益:A(M父亲父亲MA)vs.B(M父亲父亲MB)计算计算不纯性不纯性计算计算不纯性不纯性计算计算不纯性不纯性计算计算不纯性不纯性加权平均加权平均加权平均加权平均练习练习4l已知：数据见课本表4-7（P122 题2）。l问题(a)(g)l熵和Gini指数等不纯度趋向有利于具有大量不同值的属性产生大量输出测试条件，从而导致与每个划分关联的记录很少。极端情况如：以顾客ID进行划分，比其他划分方法能得到更“纯”的派生结点改进方法改进方法l信息增益（熵差）:ni=孩子节点i的记录数 n =节点p的记录数l用于ID3和C4.5算法 l增益率:将父节点p划分为k部分n表示p的记录数ni 表示第i部分（p的第i个节点）的记录数调整信息增益，引入划分信息SplitInfo，把属性测试条件产生的输出数也考虑进去。如果一个属性产生了大量的划分，它的划分信息SplitInfo将会很大，从而增益率降低。用于C4.5算法比较不同类型的属性的划分（以比较不同类型的属性的划分（以Gini指数为例）指数为例）二元属性标称属性离散属性基于基于GINI指数的指数的二元属性二元属性划分方法划分方法l划分为两部分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=0.333基于基于GINI指数的指数的标称属性标称属性划分方法划分方法l用矩阵帮助选择最佳划分Multi-way splitTwo-way split(find best partition of values)基于基于GINI指数的指数的连续属性连续属性划分方法划分方法l问题：需要选择候选划分点l方法1:穷举法将记录中所有的属性值作为候选划分点，计算每个候选的Gini指标，并从中选择具有最小值的候选划分点。效率低计算代价昂贵改进方法：改进方法：l根据划分属性，先对记录进行排序排序l从两个相邻的排过序的属性值中选择中间值作为候选划分点选择中间值作为候选划分点(55、65、72、80、）。在计算相邻结点时值，部分类分布保持不变，减少计算量。l进一步优化进一步优化：仅仅考虑位于具有不同类标号的两个相邻记录之间的候选划分点（55、80、97），计算其Gini指数。候选划分点候选划分点排序后的值排序后的值决策树归纳的设计问题决策树归纳的设计问题2：如何停止分裂过程？如何停止分裂过程？l停止方法：方法1：当所有记录都属于同一分类时，停止划分方法2：当所有记录都有相似（相同）属性值时，停止划分方法3：提前终止4.3.5 决策树归纳算法决策树归纳算法l算法输入：训练记录集E和属性集F。l算法输出：构造的决策树l主要函数：createNode()：建立一个新结点。结点要么表示一个测试条件(node.test_cond),要么表示一个类标号(node.label)find_best_split()：从剩余属性中挑选一个属性作为结点的测试条件。Classify()：为叶子结点确定类标号。多数情况下，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作为root派生结点加到树中，将边(rootchild)记为vend forend ifreturn root案例学习：案例学习：4.3.6 Web机器人检测机器人检测l阅读课本例子，回答下列问题：什么是Web使用挖掘？Web使用挖掘的数据源是什么？这些数据是如何得到的？为什么说在Web挖掘中，区分正常用户访问和Web机器人访问时重要的？本例子中，决策树模型是如何建立起来的？请你用1分钟长度的时间，叙述其建立的过程。根据课本的决策树模型，正常用户访问有何特征？4.3.7 决策树归纳的特点决策树归纳的特点l是一种构建分类模型的非参数方法l大多决策树算法都采用启发式的方法来简化搜索l决策树容易构建，对未知样本的分类也快l决策树相对容易理解l对于噪声的干扰具有相当好的鲁棒性l冗余属性不会对决策树的准确率造成不利影响l对于数据碎片问题，可以通过规定阈值来检测和解决l可能会产生子树在决策树中重复出现的情况l对于非水平和垂直的决策边界问题，可以使用斜决策树或构造归纳方法来解决。l不纯度度量方法的选择对决策树性能影响很小4.4l分类模型的误差：训练误差：在训练记录上误分样本的比例泛化误差（检验误差）：模型在未知记录上的期望误差l一个好的分类模型，必须具有低的训练误差和泛化误差。l决策树分类方法存在的问题（与模型复杂度相关）模型拟合不足 Underfittingu当模型过于简单时，训练误差和检验误差都比较大u出现原因：模型尚未学习到数据的真实结构模型过分拟合 Overfittingu树的规模变得太大，即使训练误差还在继续降低，但是检验误差开始增大u出现原因：模型过分拟合了训练数据中的噪声数据，或者是训练数据缺乏代表性的数据拟合不足拟合不足 和和 过分拟合过分拟合Overfitting训练误差检验误差Underfitting噪声导致过分拟合噪声导致过分拟合决策边界被噪声点扭曲决策边界被噪声点扭曲缺乏代表性样本导致过分拟合缺乏代表性样本导致过分拟合4.4.5 处理决策树归纳中的过分拟合处理决策树归纳中的过分拟合l先剪枝（提前终止规则）树增长算法在产生完全拟合整个训练数据集的完全增长的决策树之前就停止决策树的生长方法：选取不纯度增益的阈值优点：避免产生过分拟合训练数据的过于复杂的子树缺点：阈值大小难于选取l后剪枝初始决策树按照最大规模生长，然后进行剪枝，按照自底向上的方式修剪完全增长的决策树方法：用新结点代替子树；用子树的常用分支代替子树优点：避免过早终止决策树的生长缺点：需要浪费额外开销