chap4_决策树

DataMining第四章分类：基本概念、决策树和模型评估4.1预备知识4.2解决分类问题的一般方法分类例子预测癌细胞是良性还是恶性将信用卡交易分为合法和欺诈……分类：定义给定一个记录集–每个记录包含一个属性集，通常最后一个属性是该记录的分类（class）属性.目标：找到一个模型（从其余属性值到分类属性的转换函数），实现对未知分类的记录进行尽可能精确地分类。–通常，将给定的数据集分为训练集（trainingset）和检验集（testset）。训练集用来创建模型，检验集用来验证模型的有效性。分类性能度量：110011100111=ffffff正确预测数准确率预测总数100111100111=ffffff错误预测数差错率预测总数预测的类类=1类=0实际的数类=1f11f10类=0f01f00分类过程ApplyModelInductionDeductionLearnModelModelTidAttrib1Attrib2Attrib3Class1YesLarge125KNo2NoMedium100KNo3NoSmall70KNo4YesMedium120KNo5NoLarge95KYes6NoMedium60KNo7YesLarge220KNo8NoSmall85KYes9NoMedium75KNo10NoSmall90KYes10TidAttrib1Attrib2Attrib3Class11NoSmall55K?12YesMedium80K?13YesLarge110K?14NoSmall95K?15NoLarge67K?10TestSetLearningalgorithmTrainingSetApplyModelInductionDeductionLearnModelModelTidAttrib1Attrib2Attrib3Class1YesLarge125KNo2NoMedium100KNo3NoSmall70KNo4YesMedium120KNo5NoLarge95KYes6NoMedium60KNo7YesLarge220KNo8NoSmall85KYes9NoMedium75KNo10NoSmall90KYes10TidAttrib1Attrib2Attrib3Class11NoSmall55K?12YesMedium80K?13YesLarge110K?14NoSmall95K?15NoLarge67K?10TestSetLearningalgorithmTrainingSet训练集检验集学习模型学习模型学习算法模型分类技术基于决策树的方法DecisionTreebasedMethods基于规则的方法Rule-basedMethods基于记忆的推理Memorybasedreasoning神经网络NeuralNetworks朴素贝叶斯和贝叶斯信念网络NaïveBayesandBayesianBeliefNetworks支持向量机SupportVectorMachines决策树定义决策树是由结点和有向边组成的层次结构。树中包含三种结点：–根结点–内部结点–叶结点非终结点。包含属性测试条件，用于分开不同特性的记录每个叶结点都赋予一个类标号决策树例1Tid有房者婚姻状况收入拖欠贷款者1YesSingle125KNo2NoMarried100KNo3NoSingle70KNo4YesMarried120KNo5NoDivorced95KYes6NoMarried60KNo7YesDivorced220KNo8NoSingle85KYes9NoMarried75KNo10NoSingle90KYes10有房产婚姻状况收入YESNONONOYesNoMarriedSingle,Divorced80K80K属性划分训练数据模型：决策树决策树例2MarStRefundTaxIncYESNONONOYesNoMarriedSingle,Divorced80K80K对于相同的数据，能构造多种不同的决策树Tid有房者婚姻状况收入拖欠贷款者1YesSingle125KNo2NoMarried100KNo3NoSingle70KNo4YesMarried120KNo5NoDivorced95KYes6NoMarried60KNo7YesDivorced220KNo8NoSingle85KYes9NoMarried75KNo10NoSingle90KYes10决策树应用过程：使用模型测试数据－1RefundMarStTaxIncYESNONONOYesNoMarriedSingle,Divorced80K80KRefundMaritalStatusTaxableIncomeCheatNoMarried80K?10检验数据从树根开始使用模型测试数据－2RefundMarStTaxIncYESNONONOYesNoMarriedSingle,Divorced80K80KRefundMaritalStatusTaxableIncomeCheatNoMarried80K?10TestData使用模型测试数据－3RefundMarStTaxIncYESNONONOYesNoMarriedSingle,Divorced80K80KRefundMaritalStatusTaxableIncomeCheatNoMarried80K?10TestData使用模型测试数据－4RefundMarStTaxIncYESNONONOYesNoMarriedSingle,Divorced80K80KRefundMaritalStatusTaxableIncomeCheatNoMarried80K?10TestData使用模型测试数据－5RefundMarStTaxIncYESNONONOYesNoMarriedSingle,Divorced80K80KRefundMaritalStatusTaxableIncomeCheatNoMarried80K?10TestData使用模型测试数据－6RefundMarStTaxIncYESNONONOYesNoMarriedSingle,Divorced80K80KRefundMaritalStatusTaxableIncomeCheatNoMarried80K?10TestData将Cheat赋值为“No”决策树构造算法多种算法:–Hunt算法(最早方法之一)–CART（classificationandregressiontrees）–ID3,C4.5–SLIQ,SPRINTHunt算法结构Hunt算法的思想是将训练记录相继划分成“较纯”的子集，以递归方式建立决策树。假设t表示结点，Dt表示与结点t相关联的训练记录集，y={y1,y2,…,yc}是类标号Hunt算法的递归定义:–如果Dt中所有记录都属于同一个类yt,则t就是叶子节点，并用yt标号–如果Dt是一个空集，那么t就是叶子节点，其标号为其父结点上训练记录中的多数类TidRefundMaritalStatusTaxableIncomeCheat1YesSingle125KNo2NoMarried100KNo3NoSingle70KNo4YesMarried120KNo5NoDivorced95KYes6NoMarried60KNo7YesDivorced220KNo8NoSingle85KYes9NoMarried75KNo10NoSingle90KYes10Dt?–如果Dt中包含属于多个类的记录，则选择一个属性测试条件，将记录划分成若干个子集。并对每个子集进行递归分类。例P93～P95预测拖欠银行贷款的贷款者Tid有房者婚姻状况收入拖欠贷款者1YesSingle125KNo2NoMarried100KNo3NoSingle70KNo4YesMarried120KNo5NoDivorced95KYes6NoMarried60KNo7YesDivorced220KNo8NoSingle85KYes9NoMarried75KNo10NoSingle90KYes10如何生成决策树？贪婪策略.–每次选择属性划分条件时，选择划分数据的最优标准.决策树归纳的设计问题–问题1：如何分裂记录？1.1定义属性测试条件——给不同类型的属性指定测试条件的方法1.2找到最好的划分方法——对每种测试条件进行评估测量–问题2：何时停止分裂过程？决策树归纳的设计问题1：1.1定义属性测试条件4.4.3表示属性测试条件的方法–根据属性类型标称型Nominal序数型Ordinal连续型Continuous–按划分路数二元划分2-waysplit多路划分Multi-waysplit标称属性的划分方法：(数据集见P122习题2)多路划分法:划分成几个不同的值——输出数取决于该属性不同属性值的个数.二分法:划分为两个不同的值.（需要找到最佳的划分方法）CarTypeFamilySportsLuxuryCarType{Family,Luxury}{Sports}CarType{Sports,Luxury}{Family}OR多路划分法二分法（分组必须保留属性值之间的序关系）注意：第三种划分方法合理吗?序数属性的划分方法：SizeSmallMediumLargeSize{Medium,Large}{Small}Size{Small,Medium}{Large}ORSize{Small,Large}{Medium}连续属性的划分方法多路划分：离散化属性值，每个离散化区间赋予一个新的序数值二分法：(Av)or(Av)–需要从所有可能的划分点中选择产生最佳划分的点决策树归纳的设计问题1：1.2找到最好划分方法OwnCar?C0:6C1:4C0:4C1:6C0:1C1:3C0:8C1:0C0:1C1:7CarType?C0:1C1:0C0:1C1:0C0:0C1:1StudentID?...YesNoFamilySportsLuxuryc1c10c20C0:0C1:1...c11划分前:数据集有20个记录，标号为class0和class1的各有10个。哪个划分测试条件最佳？为了度量不同的测试条件，常用划分前和划分后记录的类分布定义：p(i|t)表示结点t中，属于类i的记录所占的比例，常简记为pi。在二元分类问题中，任意结点的类分布可以记作(p0，p1)，其中p1=1-p0。选择最佳划分的度量选择最佳划分的度量通常是根据划分后子女结点不纯性的程度：不纯的程度越低，类分布就越倾斜，划分就越好。C0:5C1:5C0:9C1:1不同类，具有较高的不纯度同类，具有较低的不纯度结点不纯度的度量方法：熵Entropy基尼指数GiniIndex分类差错率Classificationerror计算不纯性方法1:熵结点t的熵:其中，c为结点t中不同类标号个数p(i|t)是给定结点t中属于类i的记录所占比例，简记为pi结点熵值的取值范围：–当记录均匀分布于各分类时，将取得最大值(lognc)–当所有记录都属于同一分类时，将取得最小值(0)120()[(|)log(|)]ciEntropytpitpit例：分别计算3个结点的熵结点N1计数类=C00类=C16P(C0)=0/6=0P(C1)=6/6=1Entropy=–0·log0–1·log1=–0–0=0P(C0)=1/6P(C1)=5/6Entropy=–(1/6)·log2(1/6)–(5/6)·log2(5/6)=0.65P(C0)=2/6P(C1)=4/6Entropy=–(2/6)·log2(2/6)–(4/6)·log2(4/6)=0.92120()[(|)log(|)]ciEntropytpitpit结点N2计数类=C01类=C15结点N3计数类=C03类=C13练习1已知：数据见课本表4-7（P122题2），