分类和预测算法.ppt

第九章分类和预测,分类和预测是两种数据分析形式，可以用于提取描述重要数据类的模型或预测未来的数据趋势。没有统一的观点，一般认为：用预测法预测数据归属于哪个类称为分类；用预测法预测连续值为预测。,一、分类,数据分类的步骤：数据准备建立模型模型评估使用模型分类,数据准备,数据清理：消除或减少燥声、处理空缺值相关性分析：数据中与分类和预测任务不相关的属性分析数据变换：如连续变成离散（年龄分段、收入分段等），区间变化,建立模型,建立模型，描述预定的数据类，通过分析由属性描述的数据库元组来构造模型。每个元组属于一个预定义的类，由一个称为类标号属性的属性确定。比如将人员数据按信用分成优、良、中、一般、差五个类，类标号属性为数据库的信用属性。对于分类，数据元组也称为样本、实例或对象。为建立模型而被分析的数据元组组成训练数据集。训练集中的单个元组称作训练样本，并随机的由样本群选取。由于提供了每个训练样本的类标号（即指定了按哪个类属性分类），该步也称为有指导的学习。,模型评估,首先评估模型的预测正确率，建立一个测试集，测试集中数据从样本集随机取出并独立于训练样本。模型在给定测试集上的准确率是正确被模型分类的测试样本的百分比。,模型评价指标,a是正确预测到的负例的数量,TrueNegative(TN,0-0)b是把负例预测成正例的数量,FalsePositive(FP,0-1)c是把正例预测成负例的数量,FalseNegative(FN,1-0)d是正确预测到的正例的数量,TruePositive(TP,1-1)a+b是实际上负例的数量，ActualNegativec+d是实际上正例的个数，ActualPositivea+c是预测的负例个数，PredictedNegativeb+d是预测的正例个数，PredictedPositive,模型评价指标,准确（分类）率=正确预测的正反例数/总数Accuracy=truepositiveandtruenegative/totalcasesACC=(TP+TN)/(P+N)误分类率=错误预测的正反例数/总数Errorrate=falsepositiveandfalsenegative/totalcasesErrorrate=(FP+FN)/(P+N),模型评价指标,正例的覆盖率=正确预测到的正例数/实际正例总数，Recall(TruePositiveRate，orSensitivity)=truepositive/totalactualpositiveTPR=TP/P=TP/(TP+FN)falsepositiverate(FPR)等同于：fall-outFPR=FP/N=FP/(FP+TN),模型评价指标,负例的覆盖率=正确预测到的负例个数/实际负例总数Specificity(TrueNegativeRate)=truenegative/totalactualnegativeSPC=TN/N=TN/(FP+TN)=1-FPRROC曲线，全称是receiveroperatingcharacteristiccurve，中文叫“接受者操作特性曲线”,纵坐标:truepositivesrate(sensitivity),横坐标falsepositivesrate(1-specificity),模型评价指标,positivepredictivevalue(PPV)等同于：precisionPPV=TP/(TP+FP)negativepredictivevalue(NPV)NPV=TN/(TN+FN)falsediscoveryrate(FDR)FDR=FP/(FP+TP)Matthewscorrelationcoefficient(MCC)MCC=(TP*TN-FP*FN)/sqrt(P*N*P1*N1)F1scoreF1=2*TP/(P+P1),图例,训练数据,图例,分类规则,二、决策（判定）树归纳,1、决策树一个树形的结构内部节点上选用一个属性进行分割每个分叉都是分割的一个部分叶子节点表示一个分布一个电器销售商根据数据库的数据分析概念“买计算机”，构造的决策树,训练数据集,概念“buys_computer”的判定树,age?,overcast,student?,creditrating?,no,yes,fair,excellent,40,no,no,yes,yes,yes,30.40,2、使用决策树进行分类过程,决策树生成算法分成两个步骤树的生成开始，数据都在根节点递归的进行数据分片树的修剪去掉一些可能是噪音或者异常的数据决策树使用:对未知数据进行分割按照决策树上采用的分割属性逐层往下，直到一个叶子节点,3、决策树算法,基本算法（贪心算法）自上而下分而治之的方法开始时，所有的数据都在根节点属性都是种类字段(如果是连续的，将其离散化)所有记录用所选属性递归的进行分割属性的选择是基于一个启发式规则或者一个统计的度量停止分割的条件一个节点上的数据都是属于同一个类别没有属性可以再用于对数据进行分割,4、属性选择方法-最高信息增益法（ID3/C4.5）,设S是有s个数据样本的集合。假定类标号属性具有m个不同的值，定义m个不同类Ci(i=1,m)。设si是类Ci中的样本数。对一个给定的样本分类所需要的期望信息由下式给出：,其中pi是任意样本属于Ci的概率，一般用si/s估计代替pi,例：假定有50个元组作为样本，则s=50。分成买计算机和不买两类，这样，m=2，C1是买的样本数据集，C2是不买的，若不买的有20(即s2=20),则买的为30（s1=30),计算信息增益,设属性A有v个不同值a1,a2,av。可以根据属性值将S划分为v个子集S1,S2,Sv；sij是子集Sj中类Ci的样本数。由A划分成子集的熵（期望信息）为：,2019/12/13,21,可编辑,例：假定v=“年龄”，值为a1,a2,a3=40,这样可以将50个样本分成3个子集合S1,S2,S3。C1买计算机的样本集合，C2是不买的。,如果在C1中31.40岁的人有5个，则s12=5,以A分枝将获得的信息增益是：Gain(A)=I(s1,s2,sm)-E(A),决策树如何分枝？计算属性的信息增益，取最大的信息增益分枝,例：电器销售顾客训练数据元组，类标号属性买PC，构造决策树,计算每个属性的熵(从年龄开始)：,C1对应买（y)，C2不买（n）,例：电器销售顾客训练数据元组，类标号属性买PC，构造决策树,计算每个属性的熵(从年龄开始)：,C1对应买（y)，C2不买（n）,对年龄40:s13=3，s23=2,用同样的方法计算：Gain(收入)=0.029Gain(学生)=0.151Gain(信用)=0.048由于Gain(年龄)最大，所以选作测试属性,计算E和Gain,年龄,40,40,40&信用=良)买PC=y,决策树,6、剪枝问题,先剪枝：通过提前停止树的构造而对树剪枝。在构造树时，如果按某阀值（比如信息增益量小于一定值）停止分裂。但是阀值的选择比较困难，底了可能使树的化简太少，高了可能导致过分简化。后剪枝：由完全生长的树剪枝。,三、贝叶斯分类,统计学的方法，可以预测类成员关系的可能性，即给定样本属于一个特定类的概率。,1、贝叶斯定理后验概率(posterioriprobabilities):P(H|X)表示条件X下H的概率.贝叶斯定理:P(H|X)=P(X|H)P(H)/P(X),2、朴素贝叶斯分类,每个数据样本用一个n维特征向量X=x1,x2,xn表示，分别描述对n个属性A1,A2,.,An样本的n个度量。假定有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常用频度代替,未知样本为X=（年龄=“=30”,收入=“中”,学生=y,信用=中),p(C1)=p(买PC=y）=9/14=0.643p(C2)=p(买PC=n）=5/14=0.357p(年龄=“=30”|买PC=y)=2/9=0.222p(年龄=“=30”|买PC=n)=3/5=0.6p(收入=“中”|买PC=y)=4/9=0.444p(收入=“中”|买PC=n)=2/5=0.4p(学生=“y”|买PC=y)=6/9=0.667p(学生=“y”|买PC=n)=1/5=0.2p(信用=“中”|买PC=y)=6/9=0.667p(信用=“中”|买PC=n)=2/5=0.4,朴素贝叶斯分类示例,p(X|买PC=y)p(买PC=y)=0.044*0.643=0.028p(X|买PC=n)p(买PC=n)=0.019*0.357=0.007,由前面的数据：X=（年龄=“=30”,收入=“中”,学生=y,信用=中)属于买PC的概率大。,计算p(X|Ci),i=1，2p(X|买PC=y)=0.222*0.444*0.667*0.667=0.044p(X|买PC=n)=0.6*0.4*0.2*0.4=0.019,结果,四、其它的一些分类方法,贝叶斯信念网络方法神经网络方法以及在商品化的数据挖掘中用的较少的：k_最邻近分类遗传算法粗糙集合方法模糊集方法,五、预测,1、线性回归由一个数据可以确定另一个，比如工作年数x和薪金y。给定s个样本，形如(x1,y1)，.，(xs,ys),2、多元回归,3、非线性回归,预测,六、评估分类法的准确率,保持方法：给定数据随机地划分成两