5 数据挖掘技术-分类和预测

第5章数据挖掘技术-分类和预测分类预测种类字段基于训练集形成一个模型，训练集中的类标签是已知的。使用该模型对新的数据进行分类.预测对连续性字段进行建模和预测。典型应用信用评分医疗诊断…………分类和预测分类的两个步骤模型创建:建立一个模型，描述预定得数据类集或概念集。每一条记录都属于一个确定的类别，我们使用类标签属性记录类别。用于创建模型的数据集叫:训练集模型可以用分类规则、决策树、或者数学方程的形式来表达。模型使用:用创建的模型预测未来或者类别未知的记录估计模型的准确率使用创建的模型在一个测试集上进行预测，并将结果和实际值进行比较测试集和训练集是独立的。分类过程：模型创建训练集NAMERANKYEARSTENUREDMikeAssistantProf3noMaryAssistantProf7yesBillProfessor2yesJimAssociateProf7yesDaveAssistantProf6noAnneAssociateProf3no分类算法IFrank=‘professor’ORyears6THENtenured=‘yes’模型分类过程(2):使用模型模型测试集NAMERANKYEARSTENUREDTomAssistantProf2noMerlisaAssociateProf7noGeorgeProfessor5yesJosephAssistantProf7yes未知数据(Jeff,Professor,4)Tenured?有监督和无监督学习有监督学习(分类)训练集是带有类标签的新的数据是基于训练集进行分类的。无监督学习(聚集)训练集是没有类标签的。提供一组属性，然后寻找出训练集中存在类别或者聚集。关于分类和预测的问题(1):数据准备数据清洗对数据进行预处理，消除噪音和丢失值。相关性分析(属性选择)去掉不相关或者冗余的属性数据转换数据概化或者对数据进行规范化关于分类和预测的问题(2):评估分类方法预测准确率速度创建速度使用速度强壮性涉及处理噪音和丢失值，模型正确预测的能力。伸缩性涉及给定大量数据，有效构造模型的能力。可解释性:对模型的可理解程度。规则好坏的评价决策树的大小分类规则的简明性使用决策树进行分类决策树一个树型的结构内部节点上选用一个属性进行分割每个分叉都是分割的一个部分叶子节点表示一个分布决策树生成算法分成两个步骤树的生成开始，数据都在根节点递归的进行数据分片树的修剪去掉一些可能是噪音或者异常的数据决策树使用:对未知数据进行分割按照决策树上采用的分割属性逐层往下，直到一个叶子节点训练集incomestudentcredit_ratingbuys_computerhighnofairnohighnoexcellentnohighnofairyesmediumnofairyeslowyesfairyeslowyesexcellentnolowyesexcellentyesmediumnofairnolowyesfairyesmediumyesfairyesmediumyesexcellentyesmediumnoexcellentyeshighyesfairyesmediumnoexcellentnoID3算法Output:ADecisionTreefor“buys_computer”age?overcaststudent?creditrating?noyesfairexcellent=3040nonoyesyesyes30..40决策树算法基本算法（贪心算法）自上而下分而治之的方法开始时，所有的数据都在根节点属性都是种类字段(如果是连续的，将其离散化)所有记录用所选属性递归的进行分割属性的选择是基于一个启发式规则或者一个统计的度量(如,informationgain)停止分割的条件一个节点上的数据都是属于同一个类别没有属性可以再用于对数据进行分割属性选择的统计度量Informationgain(ID3/C4.5)所有属性假设都是种类字段经过修改之后可以适用于数值字段Giniindex(IBMIntelligentMiner)能够适用于种类和数值字段InformationGain(ID3/C4.5)选择属性的标准：具有最高InformationGain假设有两个类,P和N假设集合S中含有p个类别P的记录,n个类别N的记录决定任意一个记录属于类别P或者N所需要的information.npnnpnnppnppnpI22loglog),(InformationGain在决策树中的使用假设使用属性A将把集合S分成V份{S1,S2,…,Sv}如果Si中包含pi个类别为P的记录,ni个类别为N,的记录。那么熵就是(entropy),从而这个信息增益就是1),()(iiiiinpInpnpAE)(),()(AEnpIAGain使用信息增益进行属性选择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)(ratingcreditGainstudentGainincomeGain246.0)(),()(ageEnpIageGain在分类中避免过度适应(Overfit)在训练集中生成的树可能会Overfit太多的分支,有些可能是对异常例外的反映在进行预测的时候准确率比较差过度适应问题训练数据测试数据此处剪枝决策树深度剪枝避免过拟合决策树泛化属性OutlookTemperatureHumidityWindy类1OvercastHotHighNotN2SunnyMildNormalVeryP8RainHotHighMediumP24RainMildHighVeryN24条记录3个属性值3个属性值2个属性值3个属性值2个类过度适应(Overfit)示例由表1生成的决策树将记录8的类标签改为N的决策树SunnyOvercastRainSunnyOvercastRainHighNormalNotMediumVeryHighNormalCoolMildHot图1图2OutlookPWindyHumidityTempNNPPPNNPOutlookNNPHumidity87两种剪枝方法先剪枝:提前停止树的构造而对树”剪枝”阈值的选择可以设定树的最大高度来限制树的生长.阈值的选择还可以设定每个节点必须包含的最少记录数.树叶可能持有子集样本中最频繁的类，或这些样本的概率分布。后剪枝:先生成完整的树，然后进行修剪从树中生成分类规则用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=“no”IFage=“40”ANDcredit_rating=“fair”THENbuys_computer=“yes”决策树在犯罪分析中的应用有无固定职业家庭经济状况年龄文化程度有无特长社会关系犯罪记录违法记录家庭和睦状况犯罪记录次数是否经常赌博犯罪程度无差30-40初中否有差有4是严重有中20-30中专否无差无0是较轻有差20高中否无中无1否较轻无差30-40初中有无中有1是严重无差40初中有有差无2是严重有差20-30高中有有中有6是严重有差20-30中专否无中有1否较轻有差30-40大专有有差无3是严重无中20初中有无好有5是严重无差20-30初中否有差无0否严重有好20高中否无差有1否较轻无差30-40初中有无中有0是严重无中30-40初中否无差有1是较轻有差40小学否有中无2否严重无差40初中否无差无0否严重无差30-40高中否无好无4否较轻无好20-30中专有无差有2否较轻犯罪潜在风险决策树贝叶斯分类贝叶斯分类是统计学分类方法。贝叶斯分类可以预测类成员关系的可能性，如给定样本属于一个特定类的概率。贝叶斯分类具有较高的准确率和高速度。贝叶斯定理先验概率：根据历史资料或主观估计的方法得到的概率。后验概率:通过调查实验或统计分析取得新的信息，并根据新的信息计算出状态概率。P(H|X)表示条件X下H的概率.例如：数据样本域由水果组成。H:表示假定X是苹果；X:表示样本是红色和圆的；那么：P(H):表示任意给定的数据样本为苹果的概率。－－－先验概率P(H/X):表示当X是红色并是圆的时候，X是苹果的概率。－－－后验概率贝叶斯定理:贝叶斯定理)()()/()()()/(XPHPHXPXPXHPXHp朴素贝叶斯分类每个数据样本用一个n维特征向量X={x1,x2,…xn}表示，分别描述对n个属性A1,A2,…An样本的n个度量。eg.X={age=“=30”,income=“high”,stu=“no”}假定有m个类C1,…Cm,对于数据样本X,分类法将预测X属于类Ci,当且仅当P(Ci|X)P(Cj|X),1=j=m,j!=i朴素贝叶斯分类根据贝叶斯定理,P(Ci|X)=P(X|Ci)P(Ci)/P(X)由于P(X)对于所有类都是常数,只需最大化P(X|Ci)P(Ci)计算P(X|Ci),朴素贝叶斯分类假设类条件独立.即给定样本属性值相互条件独立.P(x1,…,xk|Ci)=P(x1|Ci)·…·P(xk|Ci)朴素贝叶斯分类示例样本X=rain,hot,high,false?P(X|p)·P(p)P(X|n)·P(n)P(X|p)·P(p)P(X|n)·P(n)=样本X分配给类n(don’tplay)OR样本X分配给类p(play)???HumidityP(high/p)=3/9P(high/n)=4/5P(normal/p)=6/9P(normal/n)=1/5WindyP(true/p)=3/9P(true/n)=3/5P(false/p)=6/9P(false/n)=2/5朴素贝叶斯分类示例样本X=rain,hot,high,falseP(X|p)·P(p)=P(rain|p)·P(hot|p)·P(high|p)·P(false|p)·P(p)=3/9·2/9·3/9·6/9·9/14=0.010582P(X|n)·P(n)=P(rain|n)·P(hot|n)·P(high|n)·P(false|n)·P(n)=2/5·2/5·4/5·2/5·5/14=0.018286样本X分配给类n(don’tplay)朴素贝叶斯分类示例使用决策树进行分类属性OutlookTemperatureHumidityWindy类1OvercastHotHighNotN2SunnyMildNormalVeryP8RainHotHighMediumN24RainMildHighVeryNSunnyOvercastRainHighNormalPOutlookNNPHumidity朴素贝叶斯分类样本X=rain,hot,high,false