第2章 基本数据挖掘技术-分类

分类-决策树、关联规则、聚类-k-means分类-决策树◦了解决策树的概念；◦了解C4.5决策树建立过程、关键技术、和决策树规则；◦了解其他决策树算法。关联规则◦了解关联规则；◦掌握Apriori关联分析过程。聚类分析◦掌握K-均值算法。了解数据挖掘技术的选择考虑。预测肿瘤细胞是良性还是恶性将信用卡交易分为正常或是欺诈对蛋白质的二级结构进行分类手写体的识别:0,1,…,9Email过滤:识别垃圾邮件4决策树决策树基本概念分类也称为有监督学习(supervisedlearning),与之相对于的是无监督学习(unsupervisedlearning),比如聚类。分类与聚类的最大区别在于，分类数据中的一部分的类别是已知的，而聚类数据的类别未知。建立分类模型需要学习一部分已知数据，如果训练时间过长，或者预测模型参数太多而样本较少，将导致过拟合(overfitting)。04:506避免过度训练最重要一点是，模型的参数量应远小于样本的数量。应建立训练集(trainingset)和测试集(testset)。◦训练集应用于建立分类模型◦测试集应用于评估分类模型K折叠交叉验证(K-foldcrossvalidation)：将初始采样分割成K个子样本(S1，S2,...,Sk)，取K-1个做训练集，另外一个做测试集。交叉验证重复K次，每个子样本都作为测试集一次，平均K次的结果，最终得到一个单一估测。决策树(Decisiontrees)规则归纳(Ruleinduction)贝叶斯学习(Bayesianlearning)神经网络(Neuralnetworks)支持向量机(SupportVectorMachine)Ensemble方法(AdaBoost,Bagging...)…7从数据产生决策树的机器学习技术称为决策树学习，简称决策树（DecisionTree）。决策树是数据挖掘中最常用的一种分类和预测技术，使用其可建立分类和预测模型。决策树决策树基本概念决策树每个决策或事件（即自然状态）都可能引出两个或多个事件，导致不同的结果，把这种决策分支画成图形很像一棵树的枝干，故称决策树。决策树是一种典型的分类方法，首先对数据进行处理，利用归纳算法生成可读的规则和决策树，然后使用决策对新数据进行分析。本质上决策树是通过一系列规则对数据进行分类的过程。10数据库2020/2/15训练样本(trainingsamples)建立模型测试样本(testingsamples)评估模型决策树决策树基本概念解决分类问题的一般方法通过以上对分类问题一般方法的描述，可以看出分类问题一般包括两个步骤：1、模型构建（归纳）通过对训练集合的归纳，建立分类模型。2、预测应用（推论）根据建立的分类模型，对测试集合进行测试。决策树决策树基本概念解决分类问题的一般方法TIDA1A2A3类1Y100LN2N125SN3Y400LY4N415MN学习算法学习模型模型应用模型TIDA1A2A3类1Y100L？2N125S？3Y400L？4N415M？训练集（类标号已知）检验集（类标号未知）归纳推论决策树决策树基本概念决策树的优点1、推理过程容易理解，决策推理过程可以表示成IfThen形式；2、推理过程完全依赖于属性变量的取值特点；3、可自动忽略目标变量没有贡献的属性变量，也为判断属性变量的重要性，减少变量的数目提供参考。决策树决策树基本概念关于归纳学习(1)决策树技术发现数据模式和规则的核心是归纳算法。归纳是从特殊到一般的过程。归纳推理从若干个事实中表征出的特征、特性和属性中，通过比较、总结、概括而得出一个规律性的结论。归纳推理试图从对象的一部分或整体的特定的观察中获得一个完备且正确的描述。即从特殊事实到普遍性规律的结论。归纳对于认识的发展和完善具有重要的意义。人类知识的增长主要来源于归纳学习。决策树决策树基本概念关于归纳学习(2)归纳学习的过程就是寻找一般化描述的过程。这种一般性描述能够解释给定的输入数据，并可以用来预测新的数据。锐角三角形内角和等于180度；钝角三角形内角和等于180度；三角形内角和直角三角形内角和等于180度；等于180度已知三角形ABC，A角等于76度，B角等于89度，则其C角等于15度归纳学习由于依赖于检验数据，因此又称为检验学习。归纳学习存在一个基本的假设：任一假设如果能够在足够大的训练样本集中很好的逼近目标函数，则它也能在未见样本中很好地逼近目标函数。该假定是归纳学习的有效性的前提条件。决策树决策树基本概念关于归纳学习(3)决策树提供了一种展示类似“在什么条件下会得到什么值”这类规则的方法。比如，在贷款申请中，要对申请的风险大小做出判断，为了解决这个问题而建立的一棵决策树，从中我们可以看到决策树的基本组成部分：决策节点、分支和叶子。决策树中最上面的节点称为根节点，是整个决策树的开始。模型通过树中的各个分支对对象进行分类，叶节点表示的对象值表达了决策树分类的结果。决策树仅有一个输出，若需要有多个输出，可以建立多棵独立的决策树以处理不同输出。18TidRefundMaritalStatusTaxableIncomeCheat1YesSingle125KNo2NoMarried100KNo3NoSingle70KNo4YesMarried120KNo5NoDivorced95KYes6NoMarried60KNo7YesDivorced220KNo8NoSingle85KYes9NoMarried75KNo10NoSingle90KYes10RefundMarStTaxIncYESNONONOYesNoMarriedSingle,Divorced80K80K划分属性训练数据模型:决策树19TidRefundMaritalStatusTaxableIncomeCheat1YesSingle125KNo2NoMarried100KNo3NoSingle70KNo4YesMarried120KNo5NoDivorced95KYes6NoMarried60KNo7YesDivorced220KNo8NoSingle85KYes9NoMarried75KNo10NoSingle90KYes10MarStRefundTaxIncYESNONONOYesNoMarriedSingle,Divorced80K80K可能有多棵决策树拟合同一个数据集!ApplyModelInductionDeductionLearnModelModelTidAttrib1Attrib2Attrib3Class1YesLarge125KNo2NoMedium100KNo3NoSmall70KNo4YesMedium120KNo5NoLarge95KYes6NoMedium60KNo7YesLarge220KNo8NoSmall85KYes9NoMedium75KNo10NoSmall90KYes10TidAttrib1Attrib2Attrib3Class11NoSmall55K?12YesMedium80K?13YesLarge110K?14NoSmall95K?15NoLarge67K?10TestSetTreeInductionalgorithmTrainingSet20决策树21RefundMarStTaxIncYESNONONOYesNoMarriedSingle,Divorced80K80KRefundMaritalStatusTaxableIncomeCheatNoMarried80K?10测试数据从树的根节点开始.22RefundMarStTaxIncYESNONONOYesNoMarriedSingle,Divorced80K80KRefundMaritalStatusTaxableIncomeCheatNoMarried80K?10测试数据23RefundMarStTaxIncYESNONONOYesNoMarriedSingle,Divorced80K80KRefundMaritalStatusTaxableIncomeCheatNoMarried80K?10测试数据24RefundMarStTaxIncYESNONONOYesNoMarriedSingle,Divorced80K80KRefundMaritalStatusTaxableIncomeCheatNoMarried80K?10测试数据25RefundMarStTaxIncYESNONONOYesNoMarriedSingle,Divorced80K80KRefundMaritalStatusTaxableIncomeCheatNoMarried80K?10测试数据26RefundMarStTaxIncYESNONONOYesNoMarriedSingle,Divorced80K80KRefundMaritalStatusTaxableIncomeCheatNoMarried80K?10AssignCheatto“No”测试数据决策树决策树算法计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1老中否优买假定公司收集了左表数据，那么对于任意给定的客人（测试样例），你能帮助公司将这位客人归类吗？即：你能预测这位客人是属于“买”计算机的那一类，还是属于“不买”计算机的那一类？又：你需要多少有关这位客人的信息才能回答这个问题？决策树的用途决策树计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1老中否优买谁在买计算机？年龄？学生？信誉？买青中老否是优良不买买买不买决策树的用途决策树算法决策树决策树算法决策树的表示决策树的基本组成部分：决策结点、分支和叶子。年龄？学生？信誉？买青中老否是优良不买买买不买决策树中最上面的结点称为根结点。是整个决策树的开始。每个分支是一个新的决策结点，或者是树的叶子。每个决策结点代表一个问题或者决策.通常对应待分类对象的属性。每个叶结点代表一种可能的分类结果在沿着决策树从上到下的遍历过程中，在每个结点都有一个测试。对每个结点上问题的不同测试输出导致不同的分枝，最后会达到一个叶子结点。这一过程就是利用决策树进行分类的过程，利用若干个变量来判断属性的类别决策树决策树算法与决策树相关的重要算法1、Hunt,Marin和Stone于1966年研制的CLS学习系统，用于学习单个概念。2、1979年,J.R.Quinlan给出ID3算法，并在1983年和1986年对ID3进行了总结和简化，使其成为决策树学习算法的典型。3、Schlimmer和Fisher于1986年对ID3进行改造，在每个可能的决策树节点创建缓冲区，使决策树可以递增式生成，得到ID4算法。4、1988年，Utgoff在ID4基础上提出了ID5学习算法，进一步提高了效率。1993年，Quinlan进一步发展了ID3算法，改进成C4.5算法。5、另一类决策树算法为CART，与C4.5不同的是，CART的决策树由二元逻辑问题生成，每个树节点只有两个分枝，分别包括学习实例的正例与反例。CLS,ID3，C4.5，CART决策树决策树算法CLS（ConceptLearningSystem）算法CLS算法是早期的决策树学习算法。它是许多决策树学习算法的基础。CLS基本思想从一棵空决策树开始，选择某一属性（分类属性）作为测试属性。该测试属性对应决策树中的决策结点。根据该属性的值的不同，可将训练样本分成相应的子集，如果该子集为空，或该子集中的样本属于同一个类，则该子集为叶结点，否则该子