您好,欢迎访问三七文档
数据挖掘第五章:分类本章内容5.1分类的定义与基本问题5.2分类的性能评测5.3决策树5.4贝叶斯分类5.5k-nearestneighbor(k-NN)算法5.6其它分类问题基本要求:掌握分类的定义、模型、评价指标等问题,掌握决策树、贝叶斯分类中的典型分类方法5.1分类的定义与基本问题分类预测分类的类标签基于训练数据和类标签构造一个模型,并分类新数据数值预测:建连续值函数/模型,预测未知/缺失值典型应用信用卡/贷款审批:医疗诊断:肿瘤是癌或良性?欺诈检测:交易欺诈?网页分类5.1分类的定义与基本问题有监督学习(supervisedlearning)监督:训练数据(观察,测量等)都带有标签,指示数据的类别根据训练集分类新数据无监督学习(unsupervisedlearning)训练集的类别(标签)未知给定一个观察,测量等的集合,目标是建立数据中存在的数据的类或簇5.1分类的定义与基本问题Supervisedy=F(x):truefunctionD:labeledtrainingsetD:{xi,F(xi)}Learn:G(x):modeltrainedtopredictlabelsDGoal:E[(F(x)-G(x))2]0Welldefinedcriteria:Accuracy,RMSE,...UnsupervisedGenerator:truemodelD:unlabeleddatasampleD:{xi}Learn??????????Goal:??????????Welldefinedcriteria:??????????5.1分类的定义与基本问题分类:一个两步的过程模型构建:描述一组预先定义的类•假定每个元组/样本属于一个类,由类标签属性设定•用于构建模型的元组集合称为训练集trainingset•模型可以表示为分类规则,决策树,数学公式模型使用:分类将来/未知对象•估计模型的准确率:比较测试样本的已知标签/由模型预测(得到)标签•测试集:独立于训练集的样本(避免过分拟合overfitting?)•准确率:测试样本集中模型正确预测/分类的样本的比率•如果准确率合时,使用模型来分类标签为未知的样本基本假设:I.I.D假设。Dataareindependentandidenticallydistributed。词袋模型与股票收益率5.1分类的定义与基本问题学习阶段:利用分类算法通过分析训练数据集来构造分类模型AgeCarTypeRisk20CombiHigh18SportsHigh40SportsHigh50FamilyLow35MinivanLow30CombiHigh32FamilyLow40CombiLowtrainingdataClassificationalgorithmClassifier(model)ifage31orCarType=SportsthenRisk=High5.1分类的定义与基本问题测试阶段:利用检验数据评估分类模型的准确率,如果准确率可以接受,则可用于新数据的分类AgeCarTypeRisk27SportsHigh34FamilyLow66FamilyHigh44SportsHighTestdataClassifier(model)RiskHighLowLowHigh5.1分类的定义与基本问题AgeCarTypeRisk27Sports34Minivan55Family34SportsNewdataClassifier(model)RiskHighLowLowHigh分类阶段:利用模型预测新数据的类标签类标签未知应用举例1:文本分类BOW模型应用举例2:不良内容识别利用皮肤(文理)、姿态等特征应用举例3:语义关系识别DataStructureGraphComputeralgorithmSearchalgorithmBinarysearchBeamsearchBest-firstsearch……SortingalgorithmComparisonsortCountingsortFlashsort……In-placealgorithm……TreeUndirectedgraphRegulargraphCompletegraph……DirectedgraphWeightedgraphPlanargraphHypergraph……B-TreeBinaryTreeMVPTree……TrieHeapT-treeR-TreeDirectedacyclicgraph……TransposegraphBinaryheap……2-3heap……应用举例4:学习依赖关系三角形的定义三角形内角和定理内角和的定义外角和的定义三角形外角和定理学习依赖关系知识单元:具有独立知识表达的最小知识对象需要研究如何从文本中自动挖掘出知识单元之间的学习依赖关系。主要挑战标注瓶颈特征选择(短文本、语义鸿沟…)非平衡多标签分类多类分类多层分类本章内容5.1分类的定义与基本问题5.2分类的性能评测5.3决策树5.4贝叶斯分类5.5k-nearestneighbor(k-NN)算法5.7其它分类问题5.2分类的性能评测评价指标:怎样度量准确率?估计分类器准确率的方法:Holdoutmethod,randomsubsampling交叉验证Cross-validation自助法BootstrapComparingclassifiers:置信区间Confidenceintervals代价效益分析(Cost-benefitanalysis)和ROC曲线5.2分类的性能评测Holdoutmethod给定数据随机分成两个部分•训练集(e.g.,2/3)用于模型构造,测试集(e.g.,1/3)用于正确率估计DivideDintoD1andD2UseD1toconstructtheclassifierdThenestimateR(d,D2)tocalculatetheestimatedmisclassificationerrorofd•Unbiasedandefficient,butremovesD2fromtrainingdatasetD随机抽样:avariationofholdout•重复holdoutk次,accuracy=所有正确率的平均值5.2分类的性能评测Cross-validation(k-fold,k=10最常用)随机分割数据为k互不相交的子集,每一个大小近似相等在i-th迭代中,使用Di为测试集其他的为训练集步骤:1.ConstructclassifierdfromD2.PartitionDintoVdatasetsD1,…,DV3.ConstructclassifierdiusingD\Di4.CalculatetheestimatedmisclassificationerrorR(di,Di)ofdiusingtestsampleDi5.Finalmisclassificationestimate:Weightedcombinationofindividualmisclassificationerrors5.2分类的性能评测dd1d2d35.2分类的性能评测混淆矩阵ConfusionMatrix:感兴趣的类定为“正类”,对应的为“负类”正样本/负样本Actualclass\PredictedclassC1¬C1C1TruePositives(TP)FalseNegatives(FN)¬C1FalsePositives(FP)TrueNegatives(TN)Actualclass\Predictedclassbuy_computer=yesbuy_computer=noTotalbuy_computer=yes6954467000buy_computer=no41225883000Total73662634100005.5分类的性能评测准确度,误差率分类器准确度,or识别率:测试元组被正确识别的比例Accuracy=(TP+TN)/All误差率:1–accuracy,or(FP+FN)/AllClassImbalanceProblem类分布不平衡问题:Oneclassmayberare,e.g.fraud,orHIV-positiveA\PC¬CCTPFNP¬CFPTNNP’N’All5.5分类的性能评测PrecisionandRecall,andF-measuresPrecision:精度–被分类器标记为正类的样本中实际上属于“正类”的比例Recall:召回率–what%ofpositivetuplesdidtheclassifierlabelaspositive?精度和召回率逆关系Fmeasure(F1orF-score):精度和召回的调和平均值•Fß:精确度和召回率的加权量•assignsßtimesasmuchweighttorecallastoprecision5.2分类的性能评测分类器评价指标:例子真实类\预测类cancer=yescancer=noTotalRecognition(%)cancer=yes9021030030.00cancer=no1409560970098.56Total230977010000Precision=?Recall=?Accuracy=?本章内容5.1分类的定义与基本问题5.2分类的性能评测5.3决策树5.4贝叶斯分类5.5k-nearestneighbor(k-NN)算法5.6其它分类问题5.2决策树ageincomestudent信誉购买计算机=30highnofairno=30highnoexcellentno31…40highnofairyes40mediumnofairyes40lowyesfairyes40lowyesexcellentno31…40lowyesexcellentyes=30mediumnofairno=30lowyesfairyes40mediumyesfairyes=30mediumyesexcellentyes31…40mediumnoexcellentyes31…40highyesfairyes40mediumnoexcellentnoage?overcaststudent?creditrating?=3040noyesyesyes31..40fairexcellentyesno决策树:通过把实例从根节点排列到叶子节点来分类实例叶子节点即为实例所属的分类树中节点是对某个属性的测试每一个后继分支对应于该属性的一个可能值。5.2决策树决策树:通过把实例从根节点排列到叶子节点来分类实例叶子节点即为实例所属的分类树中节点是对某个属性的测试每一个后继分支对应于该属性的一个可能值。5.2决策树决策树:通过把实例从根节点排列到叶子节点来分类实例5.2决策树决策树基本算法(贪婪算法)自顶向下、递归、分治的构建方式•开始,所有的训练样本位于根节点•属性是分类属性(若是连续值,事先离散化)•基于选择的属性,样本被递归地分割•基于启发式/统计测来选择测试属性(例如信息增益)终止划分的条件一个给定节点的所有样本属于一个类别没有属性剩下用于进一步划分–运用多数投票来标记此节点没有样本剩下5.2决策树MakeTree(TrainingDataD){Partition(D)}Partition(DataS){if(allpointsinDareinthesameclass)thenreturnforeachattributeAdoevaluatesplitsonattributeA;usebestsplitfoundtopartitionSintoS1andS2Partition(S1)Partition(S2)}5.2决策树属性选择度量分裂规则,决定给定节点上的样
本文标题:第五章:分类8
链接地址:https://www.777doc.com/doc-6099845 .html