分类和预测(一)

2020年1月5日星期日DataMining:ConceptsandTechniques1分类和预测（1）主讲人：蔡伟杰[e-mail]第七章：分类和预测什么是分类？什么是预测关于分类和预测的一些问题使用决策树进行分类贝叶斯分类带回馈的分类基于关联规则的分类其他分类方法预测分类的准确率总结2020年1月5日星期日DataMining:ConceptsandTechniques3分类预测种类字段基于训练集形成一个模型，训练集中的类标签是已知的。使用该模型对新的数据进行分类Prediction:对连续性字段进行建模和预测。典型应用信用评分DirectMarketing医疗诊断…………分类和预测2020年1月5日星期日DataMining:ConceptsandTechniques4分类的两个步骤模型创建:对一个类别已经确定的模型创建模型没一条记录都属于一个确定的类别，我们使用类标签属性记录类别。用于创建模型的数据集叫:训练集模型可以用分类规则，决策树，或者数学方程的形式来表达。模型使用:用创建的模型预测未来或者类别未知的记录估计模型的准确率使用创建的模型在一个测试集上进行预测，并将结果和实际值进行比较准确率：测试集和训练集是独立的。2020年1月5日星期日DataMining:ConceptsandTechniques5分类过程：模型创建训练集NAMERANKYEARSTENUREDMikeAssistantProf3noMaryAssistantProf7yesBillProfessor2yesJimAssociateProf7yesDaveAssistantProf6noAnneAssociateProf3no分类算法IFrank=‘professor’ORyears6THENtenured=‘yes’模型2020年1月5日星期日DataMining:ConceptsandTechniques6分类过程(2):使用模型模型测试集NAMERANKYEARSTENUREDTomAssistantProf2noMerlisaAssociateProf7noGeorgeProfessor5yesJosephAssistantProf7yes未知数据(Jeff,Professor,4)Tenured?2020年1月5日星期日DataMining:ConceptsandTechniques7有监督和无监督学习有监督学习(分类)训练集是带有类标签的新的数据是基于训练集进行分类的。无监督学习(聚集)训练集是没有类标签的。提供一组属性，然后寻找出训练集中存在类别或者聚集。2020年1月5日星期日DataMining:ConceptsandTechniques8分类和预测什么是分类？什么是预测关于分类和预测的一些问题使用决策树进行分类贝叶斯分类带回馈的分类基于关联规则的分类其他分类方法预测分类的准确率总结2020年1月5日星期日DataMining:ConceptsandTechniques9关于分类和预测的一些问题(1):数据准备数据清洗对数据进行预处理，消除噪音和丢失值。相关性分析(属性选择)去掉不相关或者冗余的属性数据转换泛化或者对数据进行标准化2020年1月5日星期日DataMining:ConceptsandTechniques10关于分类和预测的问题(2):评估分类方法预测准确率速度创建速度使用速度强壮性处理噪音和丢失值伸缩性对磁盘驻留数据的处理能力可解释性:对模型的可理解程度。规则好坏的评价决策树的大小分类规则的简明性2020年1月5日星期日DataMining:ConceptsandTechniques11分类和预测什么是分类？什么是预测关于分类和预测的一些问题使用决策树进行分类贝叶斯分类带回馈的分类基于关联规则的分类其他分类方法预测分类的准确率总结2020年1月5日星期日DataMining:ConceptsandTechniques12使用决策树进行分类决策树一个树性的结构内部节点上选用一个属性进行分割每个分叉都是分割的一个部分叶子节点表示一个分布决策树生成算法分成两个步骤树的生成开始，数据都在根节点递归的进行数据分片树的修剪去掉一些可能是噪音或者异常的数据决策树使用:对未知数据进行分割按照决策树上采用的分割属性逐层往下，直到一个叶子节点2020年1月5日星期日DataMining:ConceptsandTechniques13训练集ageincomestudentcredit_ratingbuys_computer=30highnofairno=30highnoexcellentno30…40highnofairyes40mediumnofairyes40lowyesfairyes40lowyesexcellentno31…40lowyesexcellentyes=30mediumnofairno=30lowyesfairyes40mediumyesfairyes=30mediumyesexcellentyes31…40mediumnoexcellentyes31…40highyesfairyes40mediumnoexcellentnoID3算法2020年1月5日星期日DataMining:ConceptsandTechniques14Output:ADecisionTreefor“buys_computer”age?overcaststudent?creditrating?noyesfairexcellent=3040nonoyesyesyes30..402020年1月5日星期日DataMining:ConceptsandTechniques15决策树算法基本算法（贪心算法）自上而下分而治之的方法开始时，所有的数据都在根节点属性都是种类字段(如果是连续的，将其离散化)所有记录用所选属性递归的进行分割属性的选择是基于一个启发式规则或者一个统计的度量(如,informationgain)停止分割的条件一个节点上的数据都是属于同一个类别没有属性可以再用于对数据进行分割2020年1月5日星期日DataMining:ConceptsandTechniques16属性选择的统计度量Informationgain(ID3/C4.5)所有属性假设都是种类字段经过修改之后可以适用于数值字段Giniindex(IBMIntelligentMiner)能够适用于种类和数值字段2020年1月5日星期日DataMining:ConceptsandTechniques17InformationGain(ID3/C4.5)选择属性的标准：具有最高InformationGain假设有两个类,P和N假设集合S中含有p个类别P的记录,n个类别N的记录决定任意一个记录属于类别P或者N所需要的information.npnnpnnppnppnpI22loglog),(2020年1月5日星期日DataMining:ConceptsandTechniques18InformationGain在决策树中的使用假设使用属性A将把集合S分成V份{S1,S2,…,Sv}如果Si中包含pi个类别为P的记录,ni个类别为N,的记录。那么熵就是(entropy),从而这个信息增益就是1),()(iiiiinpInpnpAE)(),()(AEnpIAGain2020年1月5日星期日DataMining:ConceptsandTechniques19使用信息增益进行属性选择ClassP:buys_computer=“yes”ClassN:buys_computer=“no”I(p,n)=I(9,5)=0.940Computetheentropyforage:HenceSimilarlyagepiniI(pi,ni)=30230.97130…4040040320.971971.0)2,3(145)0,4(144)3,2(145)(IIIageE048.0)_(151.0)(029.0)(ratingcreditGainstudentGainincomeGain)(),()(ageEnpIageGain2020年1月5日星期日DataMining:ConceptsandTechniques20GiniIndex(IBMIntelligentMiner)集合T包含N个类别的记录，那么其Gini指标就是pj类别j出现的频率如果集合T分成两部分N1andN2。那么这个分割的Gini就是提供最小Ginisplit就被选择作为分割的标准(对于每个属性都要遍历所有可以的分割方法).njpjTgini121)()()()(2211TginiNNTginiNNTginisplit2020年1月5日星期日DataMining:ConceptsandTechniques21几种经典算法介绍CARTmin(P(c1),P(c2))2P(c1)P(c2)[P(c1)logP(c1)]+[P(c2)logP(c2)]C4.5(ID3)C4.5(ID3)对种类字段处理时，缺省是对每个值作为一个分割Gain和GainRatioCHAID在Overfitting前停止树的生成必须都是种类字段选择分割。X2检验2020年1月5日星期日DataMining:ConceptsandTechniques22从树中生成分类规则用IF-THEN这种形式来表现规则每个叶子节点都创建一条规则每个分割都成为一个规则中的一个条件叶子节点中的类别就是Then的内容规则对于人来说更容易理解例子IFage=“=30”ANDstudent=“no”THENbuys_computer=“no”IFage=“=30”ANDstudent=“yes”THENbuys_computer=“yes”IFage=“31…40”THENbuys_computer=“yes”IFage=“40”ANDcredit_rating=“excellent”THENbuys_computer=“yes”IFage=“=30”ANDcredit_rating=“fair”THENbuys_computer=“no”2020年1月5日星期日DataMining:ConceptsandTechniques23在分类中避免过度适应(Overfit)在训练集中生成的会可能会Overfit太多的分支,有些可能是对异常例外的反映在进行预测的时候准确率比较差两种预修剪:难点：选择一个域值比较困难后修建:先生成完整的树，然后进行修剪使用另外一个的一个测试集来决定哪个树最好2020年1月5日星期日DataMining:ConceptsandTechniques24决定最终树大小的方法使用部分数据：使用全部数据：使用一个统计测试(e.g.,chi-square)来估计保留或者修剪掉一个分支的影响使用最小描述长度(MDL)原则:当树的Coding最小的时候最佳。2020年1月5日星期日DataMining:ConceptsandTechniques25对基本决策树的提高加入对连续字段的支持采用A=V的形式处理空值用最常见的值代替每个可能的值都给一个概率属性构造在现有属性上创建新的属性,主要是针对一些稀疏属性从而降低fragmentation,repetition,andreplication2020年1月5日星期日Da