数据挖掘概念与技术CHAPTER6-分类基本概念

1Chapter6.分类:基本概念分类:基本概念决策树归纳贝叶斯分类基于规则的分类模型评价与选择提高分类准确率的技术:集成方法EnsembleMethodsSummary2有监督vs.无监督学习有监督学习(分类)监督：训练数据（观察，测量等）都带有标签,指示观察的类别根据训练集分类新数据无监督学习(聚类)训练集的类别（标签）未知给定一个观察，测量等的集合，目标是建立数据中存在的数据的类或簇3分类预测分类的类标签(离散or名义)基于训练数据和类标签构造一个模型，并分类新数据数值预测建连续值函数/模型,预测未知/缺失值典型应用信用卡/贷款审批:医疗诊断:肿瘤是癌或良性？欺诈检测:交易欺诈?网页分类：这是哪一类？预测问题：分类vs.数值预测4分类:一个两步的过程模型构建:描述一组预先定义的类假定每个元组/样本属于一个类,由类标签属性设定用于构建模型的元组集合称为训练集trainingset模型可以表示为分类规则,决策树,数学公式模型使用:分类将来/未知对象估计模型的准确率测试集：独立于训练集的样本(避免过分拟合overfitting)比较测试样本的已知标签/由模型预测（得到）标签准确率：测试样本集中模型正确预测/分类的样本的比率如果准确率合时,使用模型来分类标签为未知的样本5Process(1):模型构建TrainingDataNAMERANKYEARSTENUREDMikeAssistantProf3noMaryAssistantProf7yesBillProfessor2yesJimAssociateProf7yesDaveAssistantProf6noAnneAssociateProf3noClassificationAlgorithmsIFrank=‘professor’ORyears6THENtenured=‘yes’Classifier(Model)6Process(2):UsingtheModelinPredictionClassifierTestingDataNAMERANKYEARSTENUREDTomAssistantProf2noMerlisaAssociateProf7noGeorgeProfessor5yesJosephAssistantProf7yesUnseenData(Jeff,Professor,4)Tenured?Issues:EvaluatingClassificationMethodsAccuracyclassifieraccuracy:predictingclasslabelpredictoraccuracy:guessingvalueofpredictedattributesSpeedtimetoconstructthemodel(trainingtime)timetousethemodel(classification/predictiontime)Robustness:handlingnoiseandmissingvaluesScalability:efficiencyindisk-residentdatabasesInterpretabilityunderstandingandinsightprovidedbythemodelOthermeasures,e.g.,goodnessofrules,suchasdecisiontreesizeorcompactnessofclassificationrules8Chapter6.分类:决策树归纳分类:基本概念决策树归纳贝叶斯分类基于规则的分类模型评价与选择提高分类准确率的技术:集成方法EnsembleMethodsSummary9决策树归纳:例子age?overcaststudent?creditrating?=3040noyesyesyes31..40fairexcellentyesnoageincomestudent信誉购买计算机=30highnofairno=30highnoexcellentno31…40highnofairyes40mediumnofairyes40lowyesfairyes40lowyesexcellentno31…40lowyesexcellentyes=30mediumnofairno=30lowyesfairyes40mediumyesfairyes=30mediumyesexcellentyes31…40mediumnoexcellentyes31…40highyesfairyes40mediumnoexcellentno训练集:购买计算机结果:10决策树归纳的算法基本算法(贪心算法)树构建：自顶向下递归地分治方式开始，所有的训练样本位于根节点属性是分类属性(若是连续值,事先离散化)基于选择的属性，样本被递归地分割基于启发式/统计测来选择测试属性(例如信息增益)终止划分的条件一个给定节点的所有样本属于一个类别没有属性剩下，用于进一步划分–运用多数投票来标记此节点没有样本剩下属性选择度量属性选择度量分裂规则，决定给定节点上的元组如何分裂具有最好度量得分的属性选定位分裂属性三种度量信息增益、增益率、Gini指标数学符号D为元组的训练集，元组属于m个不同的类Ci(i=1,,,m)Ci,D是D中的Ci类的元组集合|Ci,D|和|D|分别表示各自的元组个数13选择具有最高信息增益的属性令pi为D中的任一元组属于类Ci概率,估计为|Ci,D|/|D|分类D中元组需要的期望信息(entropy):(利用A分裂D为v个部分后)分类D需要的信息为:以属性A分枝得到的信息增益)(log)(21imiippDInfo)(||||)(1jvjjADInfoDDDInfo(D)InfoInfo(D)Gain(A)A属性选择度量:信息增益(ID3/C4.5)14ClassP:买电脑=“yes”ClassN:买电脑=“no”048.0)_(151.0)(029.0)(ratingcreditGainstudentGainincomeGain246.0)()()(DInfoDInfoageGainageageincomestudentcredit_ratingbuys_computer=30highnofairno=30highnoexcellentno31…40highnofairyes40mediumnofairyes40lowyesfairyes40lowyesexcellentno31…40lowyesexcellentyes=30mediumnofairno=30lowyesfairyes40mediumyesfairyes=30mediumyesexcellentyes31…40mediumnoexcellentyes31…40highyesfairyes40mediumnoexcellentno940.0)145(log145)149(log149)(22DInfo属性选择:信息增益15计算信息增益-连续值属性令A为连续属性必须为A确定一个最佳分裂点bestsplitpoint上升序排序A典型地,每对相邻值的中点是一个可能的分裂点(ai+ai+1)/2isthemidpointbetweenthevaluesofaiandai+1具有最小期望信息需求的点选为A的分裂点Split:D1为D中元组满足A≤split-point,D2是元组满足Asplit-point16增益率(C4.5)信息增益倾向于有大量不同取值的属性（划分更细，更纯）极端：每个划分子集只有一个样本，即一个类此时Info(d)=0C4.5(ID3后继)使用增益率来克服这一问题(规范化信息增益)GainRatio(A)=Gain(A)/SplitInfo(A)Ex.gain_ratio(income)=0.029/1.557=0.019具有最大增益率的属性选为分裂属性)||||(log||||)(21DDDDDSplitInfojvjjA17GiniIndex指标(CART)数据D包含n类别的样本,gini指标,gini(D)定义为pj类别j在D中的频率数据集D基于属性A分裂为子集D1和D2,gini指标定义为不纯度减少:具有最小ginisplit(D)的属性(or不纯度减少最大的)用于分裂节点(需要枚举所有可能的分裂情况)njpjDgini121)()(||||)(||||)(2211DginiDDDginiDDDginiA)()()(DginiDginiAginiA18计算GiniIndex指标D有9个元组买电脑=“yes”/5个买电脑=“no”设属性income分裂D为包含10个元组的D1:{low,medium}/4个元组的D2Gini{low,high}=0.458;Gini{medium,high}=0.450.因此{low,medium}/{high}分裂，由于其有最小的Giniindex假设所有属性都是连续值，需要其他技术,e.g.,聚类,来获得可能的分裂点459.01451491)(22Dgini19比较属性选择度量通常三种度量获得较好的结果信息增益Informationgain:偏向于多值属性增益率Gainratio:倾向于不平衡的分裂，其中一个子集比其他小得多Giniindex:偏向于多值属性当类数目较大时，计算困难倾向于导致大小相等的分区和纯度20其他属性选择度量CHAID:一种流行的决策树算法,基于独立χ2检验的选择度量C-SEP:某些情况下比信息增益gini指标更好G-statistic:非常近似于χ2分布MDL(最小描述长度)(i.e.,首选最简单的解):最佳树为需要最小二进位的树(1)编码树,(2)编码树的异常多元划分(基于多变量组合来划分)CART:基于属性的线性组合来发现多元划分哪一个是最好的?大部分可以获得较好结果,没有一个显著地优于其他21过拟合与数剪枝过拟合Overfitting:一棵归纳的树可能过分拟合训练数据分枝太多,某些反映训练数据中的异常，噪音/孤立点对未参与训练的样本的低精度预测两种处理方法先剪枝:提前终止树构造如果对一个节点的分裂会产生低于给定的阈值的度量，划分停止选择一个合适的阈值很难后剪枝:从完全生长的树中剪去树枝—得到一个逐步修剪树例如，最小化代价复杂度（树节点个数和错误率的函数）使用不同于训练集的数据来确定哪一个是“bestprunedtree”22决策树归纳的增强允许连续值属性动态地定义新的离散值属性，其把连续值属性分成离散的区间处理缺失属性值分配属性的最常见值为每一个可能的值分配概率属性构造基于现有的稀少出现的属性创建新的属性，这减少了分散，重复和复制23大型数据库中分类分类—被统计学和机器学习研究人员广泛地研究一个经典问题可伸缩性:以合理的速度分类由带有数百个属性的百万个样本组成的数据集为什么决策树归纳受欢迎？相对快的训练速度(与其他分类方法相比)转换为简单、易于理解的分类规则可用SQL查询来访问数据库与其它方法可比的分类精度RainForest(VLDB’98—Gehrke,Ramakrishnan&Ganti)BuildsanAVC-list(attribute,value,classlabel)24RainForest雨林的可扩展性框架可扩展性和确定质量树的标准相分离建并维持AVC-list:AVC(属性-值,类标号)AVC集(ofanattributeX)把训练集投影到属性X和类标签上，给出属性X的每个值上的类标签计数A