第4章：决策树-2017-v2

第4章(1)分类：决策树4.1预备知识4.2解决分类问题的一般方法4.3决策树归纳–4.3.1决策树的工作原理–4.3.2如何建立决策树–补充：ID3决策树详解（后继C4.5）–4.3.3表示属性测试条件的方法–4.3.4选择最佳划分的度量4.4模型的过分拟合分类的是利用一个分类函数（分类模型、分类器），该模型能把数据库中的数据映射到给定类别中的一个。训练样本、学习测试、分类属性分类界限or分类规则思路：人如何学习、分类类比计算机如何学习、分类？分类ApplyModelInductionDeductionLearnModelModelTidAttrib1Attrib2Attrib3Class1YesLarge125KNo2NoMedium100KNo3NoSmall70KNo4YesMedium120KNo5NoLarge95KYes6NoMedium60KNo7YesLarge220KNo8NoSmall85KYes9NoMedium75KNo10NoSmall90KYes10TidAttrib1Attrib2Attrib3Class11NoSmall55K?12YesMedium80K?13YesLarge110K?14NoSmall95K?15NoLarge67K?10TestSetLearningalgorithmTrainingSet基本概念训练集：数据库中为建立模型而被分析的数据元组形成训练集。训练集中的单个元组称为训练样本,每个训练样本有一个类别标记。一个具体样本的形式可为:(v1,v2,...,vn;c);其中vi表示属性值,c表示类别。测试集（检验集）：用于评估分类模型的准确率数据分类——一个两步过程(1)第一步，建立一个模型，描述预定数据类集和概念集–假定每个元组属于一个预定义的类，由一个类标号属性确定–学习模型可以用分类规则、决策树或数学公式的形式提供数据分类——一个两步过程(2)第二步，使用模型，对将来的或未知的对象进行分类–首先评估模型的预测准确率对每个测试样本，将已知的类标号和该样本的学习模型类预测比较模型在给定测试集上的准确率是正确被模型分类的测试样本的百分比测试集要独立于训练样本集，否则会出现“过分适应数据”的情况如果准确性能被接受，则分类规则就可用来对新数据进行分类有监督的学习VS.无监督的学习有监督的学习（用于分类）–模型的学习在被告知每个训练样本属于哪个类的“监督”下进行–新数据使用训练数据集中得到的规则进行分类无监督的学习（用于聚类）–每个训练样本的类编号是未知的，要学习的类集合或数量也可能是事先未知的–通过一系列的度量、观察来建立数据中的类编号或进行聚类分类模型的构造方法1.机器学习方法：决策树法规则归纳2.统计方法：知识表示是判别函数和原型事例贝叶斯法非参数法(近邻学习或基于事例的学习)3.神经网络方法：BP算法,模型表示是前向反馈神经网络模型4.粗糙集(roughset)知识表示是产生式规则4.1预备知识4.2解决分类问题的一般方法4.3决策树归纳–4.3.1决策树的工作原理–4.3.2如何建立决策树–补充：ID3决策树详解（后继C4.5）–4.3.3表示属性测试条件的方法–4.3.4选择最佳划分的度量4.4模型的过分拟合一个决策树的例子TidRefundMaritalStatusTaxableIncomeCheat1YesSingle125KNo2NoMarried100KNo3NoSingle70KNo4YesMarried120KNo5NoDivorced95KYes6NoMarried60KNo7YesDivorced220KNo8NoSingle85KYes9NoMarried75KNo10NoSingle90KYes10RefundMarStTaxIncYESNONONOYesNoMarriedSingle,Divorced80K80KSplittingAttributes训练数据模型:决策树决策树的另一个例子TidRefundMaritalStatusTaxableIncomeCheat1YesSingle125KNo2NoMarried100KNo3NoSingle70KNo4YesMarried120KNo5NoDivorced95KYes6NoMarried60KNo7YesDivorced220KNo8NoSingle85KYes9NoMarried75KNo10NoSingle90KYes10MarStRefundTaxIncYESNONONOYesNoMarriedSingle,Divorced80K80K用决策树归纳分类什么是决策树？–类似于流程图的树结构–每个内部节点表示在一个属性上的测试–每个分枝代表一个测试输出–每个树叶节点代表类或类分布决策树的生成由两个阶段组成–决策树构建开始时，所有的训练样本都在根节点递归的通过选定的属性，来划分样本（必须是离散值）–树剪枝许多分枝反映的是训练数据中的噪声和孤立点，树剪枝试图检测和剪去这种分枝决策树的使用：对未知样本进行分类–通过将样本的属性值与决策树相比较决策树分类任务ApplyModelInductionDeductionLearnModelModelTidAttrib1Attrib2Attrib3Class1YesLarge125KNo2NoMedium100KNo3NoSmall70KNo4YesMedium120KNo5NoLarge95KYes6NoMedium60KNo7YesLarge220KNo8NoSmall85KYes9NoMedium75KNo10NoSmall90KYes10TidAttrib1Attrib2Attrib3Class11NoSmall55K?12YesMedium80K?13YesLarge110K?14NoSmall95K?15NoLarge67K?10TestSetTreeInductionalgorithmTrainingSetDecisionTree一个决策树的例子TidRefundMaritalStatusTaxableIncomeCheat1YesSingle125KNo2NoMarried100KNo3NoSingle70KNo4YesMarried120KNo5NoDivorced95KYes6NoMarried60KNo7YesDivorced220KNo8NoSingle85KYes9NoMarried75KNo10NoSingle90KYes10RefundMarStTaxIncYESNONONOYesNoMarriedSingle,Divorced80K80KSplittingAttributes训练数据模型:决策树应用决策树进行分类RefundMarStTaxIncYESNONONOYesNoMarriedSingle,Divorced80K80KRefundMaritalStatusTaxableIncomeCheatNoMarried80K?10测试数据Startfromtherootoftree.应用决策树进行分类RefundMarStTaxIncYESNONONOYesNoMarriedSingle,Divorced80K80KRefundMaritalStatusTaxableIncomeCheatNoMarried80K?10测试数据应用决策树进行分类RefundMarStTaxIncYESNONONOYesNoMarriedSingle,Divorced80K80KRefundMaritalStatusTaxableIncomeCheatNoMarried80K?10测试数据应用决策树进行分类RefundMarStTaxIncYESNONONOYesNoMarriedSingle,Divorced80K80KRefundMaritalStatusTaxableIncomeCheatNoMarried80K?10测试数据应用决策树进行分类RefundMarStTaxIncYESNONONOYesNoMarriedSingle,Divorced80K80KRefundMaritalStatusTaxableIncomeCheatNoMarried80K?10测试数据应用决策树进行分类RefundMarStTaxIncYESNONONOYesNoMarriedSingle,Divorced80K80KRefundMaritalStatusTaxableIncomeCheatNoMarried80K?10测试数据AssignCheatto“No”决策树分类ApplyModelInductionDeductionLearnModelModelTidAttrib1Attrib2Attrib3Class1YesLarge125KNo2NoMedium100KNo3NoSmall70KNo4YesMedium120KNo5NoLarge95KYes6NoMedium60KNo7YesLarge220KNo8NoSmall85KYes9NoMedium75KNo10NoSmall90KYes10TidAttrib1Attrib2Attrib3Class11NoSmall55K?12YesMedium80K?13YesLarge110K?14NoSmall95K?15NoLarge67K?10TestSetTreeInductionalgorithmTrainingSetDecisionTree4.1预备知识4.2解决分类问题的一般方法4.3决策树归纳–4.3.1决策树的工作原理–4.3.2如何建立决策树–补充：ID3决策树详解（后继C4.5）–4.3.3表示属性测试条件的方法–4.3.4选择最佳划分的度量4.4模型的过分拟合决策树有许多决策树算法:Hunt算法–信息增益——Informationgain（ID3）–增益比率——Gainration（C4.5）–基尼指数——Giniindex(SLIQ，SPRINT)Hunt算法设Dt是与结点t相关联的训练记录集算法步骤:–如果Dt中所有记录都属于同一个类yt,则t是叶结点，用yt标记–如果Dt中包含属于多个类的记录，则选择一个属性测试条件，将记录划分成较小的子集。对于测试条件的每个输出，创建一个子结点，并根据测试结果将Dt中的记录分布到子结点中。然后，对于每个子结点，递归地调用该算法TidRefundMaritalStatusTaxableIncomeCheat1YesSingle125KNo2NoMarried100KNo3NoSingle70KNo4YesMarried120KNo5NoDivorced95KYes6NoMarried60KNo7YesDivorced220KNo8NoSingle85KYes9NoMarried75KNo10NoSingle90KYes10Dt?Hunt算法Don’tCheatRefundDon’tCheatDon’tCheatYesNoRefundDon’tCheatYesNoMaritalStatusDon’tCheatCheatSingle,DivorcedMarriedTaxableIncomeDon’tCheat80K=80KRefundDon’tCheatYesNoMaritalStatusDon’tCheatCheatSingle,DivorcedMarriedTidRefundMaritalStatusTaxableIncomeCheat1YesSingle125KNo2NoMarried100KNo3NoSingle70KNo4YesMarried120KNo5NoDivorced95KYes6NoMarried60KNo7YesDivorced220KNo8NoSingle85KYes9N