数据挖掘Chapter4

数据挖掘导论Pang-ningTan,MichaelStieinbach,andVipinKumar著PearsonEducationLTD.范明等译人民邮电出版社第4章分类：基本概念、决策树与模型评估引言:预备知识,解决分类问题的一般方法决策树归纳模型的过分拟合评估分类器的性能引言2019年10月20日星期日数据挖掘导论4分类:定义给定记录的集合(训练集，trainingset)每个记录都用一组属性描述，其中一个属性是类标号.找出一个模型（model），类标号属性是其他属性值的函数.目标:应该能够尽可能正确地为先前未看到的记录确定类标号.使用检验集（testset）确定模型的准确率.通常,给定的数据集被划分成训练集合检验集,训练集用于构建模型，而检验集用于评估模型2019年10月20日星期日数据挖掘导论5分类:解释ApplyModelInductionDeductionLearnModelModelTidAttrib1Attrib2Attrib3Class1YesLarge125KNo2NoMedium100KNo3NoSmall70KNo4YesMedium120KNo5NoLarge95KYes6NoMedium60KNo7YesLarge220KNo8NoSmall85KYes9NoMedium75KNo10NoSmall90KYes10TidAttrib1Attrib2Attrib3Class11NoSmall55K?12YesMedium80K?13YesLarge110K?14NoSmall95K?15NoLarge67K?10TestSetLearningalgorithmTrainingSet2019年10月20日星期日数据挖掘导论6分类任务的例子肿瘤：预测肿瘤是良性还是恶性信用卡交易：把信用卡交易分为合法或欺诈两类蛋白质结构：把蛋白质的二级结构分成螺旋（alpha-helix）、褶板（beta-sheet）或随机缠绕（randomcoil）新闻：把新闻分成财经、天气、娱乐、体育等2019年10月20日星期日数据挖掘导论7分类:技术基于决策树的方法基于规则的方法神经网络朴素贝叶斯和贝叶斯信念网络支持向量机4.3决策树归纳2019年10月20日星期日数据挖掘导论9决策树:例子TidRefundMaritalStatusTaxableIncomeCheat1YesSingle125KNo2NoMarried100KNo3NoSingle70KNo4YesMarried120KNo5NoDivorced95KYes6NoMarried60KNo7YesDivorced220KNo8NoSingle85KYes9NoMarried75KNo10NoSingle90KYes10SplittingAttributesTrainingDataModel:DecisionTreeYESNONONOYesNoMarriedSingle,Divorced80K80KRefundMarStTaxInc2019年10月20日星期日数据挖掘导论10决策树树中包含三种结点根结点(rootnode):没有入边,有零条或多条出边内部结点(internalnode):恰有一条入边和两条或多条出边叶结点(leafnode)或终端结点(terminalnode):恰有一条入边，但没有出边2019年10月20日星期日数据挖掘导论11决策树分类任务:应用模型ApplyModelInductionDeductionLearnModelModelTidAttrib1Attrib2Attrib3Class1YesLarge125KNo2NoMedium100KNo3NoSmall70KNo4YesMedium120KNo5NoLarge95KYes6NoMedium60KNo7YesLarge220KNo8NoSmall85KYes9NoMedium75KNo10NoSmall90KYes10TidAttrib1Attrib2Attrib3Class11NoSmall55K?12YesMedium80K?13YesLarge110K?14NoSmall95K?15NoLarge67K?10TestSetTreeInductionalgorithmTrainingSetDecisionTree2019年10月20日星期日数据挖掘导论12决策树:使用模型RefundMaritalStatusTaxableIncomeCheatNoMarried80K?10TestDataStartfromtherootoftree.YESNONONOYesNoMarriedSingle,Divorced80K80KRefundMarStTaxInc2019年10月20日星期日数据挖掘导论13决策树:使用模型RefundMaritalStatusTaxableIncomeCheatNoMarried80K?10TestDataYESNONONOYesNoMarriedSingle,Divorced80K80KRefundMarStTaxInc2019年10月20日星期日数据挖掘导论14决策树:使用模型TestDataYESNONONOYesNoMarriedSingle,Divorced80K80KRefundMarStTaxIncRefundMaritalStatusTaxableIncomeCheatNoMarried80K?102019年10月20日星期日数据挖掘导论15决策树:使用模型TestDataYESNONONOYesNoMarriedSingle,Divorced80K80KRefundMarStTaxIncRefundMaritalStatusTaxableIncomeCheatNoMarried80K?102019年10月20日星期日数据挖掘导论16决策树:使用模型TestDataYESNONONOYesNoMarriedSingle,Divorced80K80KRefundMarStTaxIncRefundMaritalStatusTaxableIncomeCheatNoMarried80K?102019年10月20日星期日数据挖掘导论17决策树:使用模型TestDataYESNONONOYesNoMarriedSingle,Divorced80K80KRefundMarStTaxIncRefundMaritalStatusTaxableIncomeCheatNoMarried80K?10AssignCheatto“No”2019年10月20日星期日数据挖掘导论18决策树分类任务:学习模型ApplyModelInductionDeductionLearnModelModelTidAttrib1Attrib2Attrib3Class1YesLarge125KNo2NoMedium100KNo3NoSmall70KNo4YesMedium120KNo5NoLarge95KYes6NoMedium60KNo7YesLarge220KNo8NoSmall85KYes9NoMedium75KNo10NoSmall90KYes10TidAttrib1Attrib2Attrib3Class11NoSmall55K?12YesMedium80K?13YesLarge110K?14NoSmall95K?15NoLarge67K?10TestSetTreeInductionalgorithmTrainingSetDecisionTree2019年10月20日星期日数据挖掘导论19决策树归纳许多算法:Hunt’sAlgorithm(oneoftheearliest)CARTID3,C4.5SLIQ,SPRINT2019年10月20日星期日数据挖掘导论20Hunt算法的一般结构设Dt是到达结点t的记录的集合一般过程:如果Dt包含的记录属于相同的类yt,则t是一个树叶结点，标记为yt如果Dt为空,则t是一个树叶结点，标记为缺省类yd如果Dt包含属于多个类的记录,则使用一个属性测试把数据划分成较小的子集，并递归地对每个子集使用该过程.2019年10月20日星期日数据挖掘导论21Hunt算法:例Don’tCheatRefundDon’tCheatDon’tCheatYesNoRefundDon’tCheatYesNoMaritalStatusDon’tCheatCheatSingle,DivorcedMarriedTaxableIncomeDon’tCheat80K=80KRefundDon’tCheatYesNoMaritalStatusDon’tCheatCheatSingle,DivorcedMarriedTidRefundMaritalStatusTaxableIncomeCheat1YesSingle125KNo2NoMarried100KNo3NoSingle70KNo4YesMarried120KNo5NoDivorced95KYes6NoMarried60KNo7YesDivorced220KNo8NoSingle85KYes9NoMarried75KNo10NoSingle90KYes102019年10月20日星期日数据挖掘导论22决策树归纳贪心策略.根据最优化某种标准的属性测试进行记录划分.问题确定如何划分记录如何指定属性划分条件?如何确定最优划分?确定何时停止划分Discussabovethreeissuesindetails2019年10月20日星期日数据挖掘导论23如何指定属性测试条件依赖于属性类型NominalOrdinalContinuous依赖于划分的路数2-路划分（2-waysplit）多路划分（Multi-waysplit）2019年10月20日星期日数据挖掘导论24划分:标称属性多路划分:使用与不同值一样多的划分.二元划分:把值划分成两个子集.需要从所有可能的划分中找出最优划分.CarTypeFamilySportsLuxuryCarType{Sports,Luxury}{Family}CarType{Family,Luxury}{Sports}CarType{Sports,Family}{Luxury}2019年10月20日星期日数据挖掘导论25划分:序数属性多路划分:使用与不同值一样多的划分.二元划分:划分成两个子集.需要从所有可能的划分中找出最优划分.这种划分怎么样?SizeSmallMediumLargeSize{Medium,Large}{Small}Size{Small,Medium}{Large}Size{Small,Large}{Medium}2019年10月20日星期日数据挖掘导论26划分:连续属性不同的处理方法离散化：形成序数的范畴（分类）属性静态离散化–开始阶段一次性离散化可以按序数属性处理动态离散化–可以通过等宽、等频分箱或聚类找出区间二元划分:(Av)or(Av)考虑所有可能的划分，找出最佳划分点可能计算量很大2019年10月20日星期日数据挖掘导论27划分:连续属性(续)TaxableIncome97K?YesNo(ii)二元划分TaxableIncome?(i)多路划分10K[10K,25K)[25K,50K)[50K,80K)80K2019年10月20日星期日数据挖掘导论28如何确定最佳划分划分前:类0有10个记录，类1有10个记录哪个测试条件最好?OwnCar?C0:6C1:4C0:4C1:6C0:1C1:3C0:8C1:0C0:1C1:7CarType?YesNoFamilySportsLuxuryC0:1C1:0C0:1C1:0C0:0C1:1StudentID?...c1c10c20C0:0C1:1...c112019年10月2