数据仓储与数据挖掘讲义 第7章：分类与预测

第7章分类和预测7.1分类VS.预测分类：预测分类标号（或离散值）根据训练数据集和类标号属性，构建模型来分类现有数据，并用来对新数据进行分类.例如：信任度等级划分问题预测：建立连续函数值模型，比如预测空缺值例如：回归分析，销售预测问题1）数据分类——一个两步过程第一步，建立一个模型，描述预定数据类集和概念集假定每个元组属于一个预定义的类，由一个类标号属性确定基本概念训练数据集：由为建立模型而被分析的数据元组形成训练样本：训练数据集中的单个样本（元组）学习模型可以用分类规则、判定树或数学公式的形式提供第二步，使用模型，对将来的或未知的对象进行分类首先评估模型的预测准确率对每个测试样本，将已知的类标号和该样本的学习模型类预测比较模型在给定测试集上的准确率是正确被模型分类的测试样本的百分比测试集要独立于训练样本集，否则会出现“过分适应数据”的情况第一步——建立模型训练数据集NAMERANKYEARSTENUREDMikeAssistantProf3noMaryAssistantProf7yesBillProfessor2yesJimAssociateProf7yesDaveAssistantProf6noAnneAssociateProf3no分类算法IFrank=‘professor’ORyears6THENtenured=‘yes’分类规则图7-1第二步——用模型进行分类分类规则测试集NAMERANKYEARSTENUREDTomAssistantProf2noMerlisaAssociateProf7noGeorgeProfessor5yesJosephAssistantProf7yes未知数据(Jeff,Professor,4)Tenured?2）有指导的学习VS.无指导的学习有指导的学习（用于分类）模型的学习在被告知每个训练样本属于哪个类的“指导”下进行新数据使用训练数据集中得到的规则进行分类无指导的学习（用于聚类）每个训练样本的类编号是未知的，要学习的类集合或数量也可能是事先未知的通过一系列的度量、观察来建立数据中的类编号或进行聚类7．2关于分类和预测的问题通过对数据进行预处理，可以提高分类和预测过程的准确性、有效性和可伸缩性数据清理:消除或减少噪声，处理空缺值，从而减少学习时的混乱相关性分析:数据中的有些属性可能与当前任务不相关；也有些属性可能是冗余的；删除这些属性可以加快学习步骤，使学习结果更精确数据变换:可以将数据概化到较高层概念，或将数据进行规范化7．2．1准备分类和预测的数据7．2．２比较分类方法使用下列标准比较分类和预测方法预测的准确率：模型正确预测新数据的类编号的能力速度：产生和使用模型的计算花销健壮性：给定噪声数据或有空缺值的数据，模型正确预测的能力可伸缩性：对大量数据，有效的构建模型的能力可解释性：学习模型提供的理解和洞察的层次7．３用判定树归纳分类什么是判定树？类似于流程图的树结构每个内部节点表示在一个属性上的测试每个分枝代表一个测试输出每个树叶节点代表类或类分布判定树的生成由两个阶段组成判定树构建开始时，所有的训练样本都在根节点递归的通过选定的属性，来划分样本（必须是离散值）树剪枝许多分枝反映的是训练数据中的噪声和孤立点，树剪枝试图检测和剪去这种分枝判定树的使用：对未知样本进行分类通过将样本的属性值与判定树相比较训练数据集ageincomestudentcredit_rating=30highnofair=30highnoexcellent31…40highnofair40mediumnofair40lowyesfair40lowyesexcellent31…40lowyesexcellent=30mediumnofair=30lowyesfair40mediumyesfair=30mediumyesexcellent31…40mediumnoexcellent31…40highyesfair40mediumnoexcellentage?overcaststudent?creditrating?=3040noyesyesyes31..40fairexcellentyesno概念“buys_computer”的判定树判定归纳树算法判定归纳树算法（一个贪心算法）自顶向下的分治方式构造判定树树以代表训练样本的单个根节点开始使用分类属性（如果是量化属性，则需先进行离散化）递归的通过选择相应的测试属性，来划分样本，一旦一个属性出现在一个节点上，就不在该节点的任何后代上出现测试属性是根据某种启发信息或者是统计信息来进行选择（如：信息增益）递归划分步骤停止的条件给定节点的所有样本属于同一类没有剩余属性可以用来进一步划分样本——使用多数表决没有剩余的样本7.3.2属性选择度量信息增益在树的每个节点上使用信息增益度量选择测试属性；选择具有最高信息增益（或最大熵压缩）的属性作为当前节点的测试属性。（即根据当前节点对应的训练样本，计算各属性的信息增益，然后选用具有最高信息增益的属性来做样本划分）信息增益算法—ID3算法信息量的大小取决于信息内容消除人们认识的不确定程度。信息量的度量：I(x)=-∑P(Xi)log2P(Xi)i=1,2,3,…,nXi表示第i个状态（共n个状态）；P(Xi)代表出现第i个状态时的概率；I(x)为消除不确定性所需的信息量，单位为比特(bit)硬币：P(Xi)=0.5I(x)=-[P(X1)log2P(X1)+P(X2)log2P(X2)]=-(-0.5-0.5)=1bit骰子：P(Xi)=1/6I(x)=2.6bit一、信息的度量一般的，设事件共有m个状态，C1、C2、…….、Cm，每种状态出现的次数分别是s1、s2、…….、sm，则其信息量为：sslogss),...,s,ssI(imiim2121P192,7-1属性选择度量:信息增益(ID3/C4.5)选择具有最大信息增益的属性（设D为给定元组，|D|元组个数）pi是D中任意元组属于类Ci的概率,用|Ci,D|/|D|计算对D中元组分类所需的期望信息为：对D中元组按照属性A分类（即按照A将D分成v个部分）的信息为：InformationgainedbybranchingonattributeA)(log)(21imiippDInfo)(||||)(1jvjjADIDDDInfo(D)InfoInfo(D)Gain(A)AAttributeSelection:InformationGainClassP:buys_computer=“yes”ClassN:buys_computer=“no”意味着“age=30”占有样本比例为5/14，其中2个样本为yes，3个为no。Hence：Similarly：agepiniI(pi,ni)=30230.97131…4040040320.971694.0)2,3(145)0,4(144)3,2(145)(IIIDInfoage048.0)_(151.0)(029.0)(ratingcreditGainstudentGainincomeGain246.0)()()(DInfoDInfoageGainageageincomestudentcredit_ratingbuys_computer=30highnofairno=30highnoexcellentno31…40highnofairyes40mediumnofairyes40lowyesfairyes40lowyesexcellentno31…40lowyesexcellentyes=30mediumnofairno=30lowyesfairyes40mediumyesfairyes=30mediumyesexcellentyes31…40mediumnoexcellentyes31…40highyesfairyes40mediumnoexcellentno)3,2(145I940.0)145(log145)149(log149)5,9()(22IDInfoincomestudentcredit_ratclasshighhighmediumlowmediumnononoyesyesfairexcellfairfairexcellnononoyesyesincomestudentcredit_ratclassmediumlowlowmediummediumnoyesyesyesnofairfairexcellfairexcellyesyesnoyesnoincomestudentcredit_ratclasshighlowmediumhighnoyesnoyesfairexcellexcellfairyesyesyesyesage=?=3031...4040对于上图中=30的分支，可以计算得到：Gain(income)=0.029Gain(student)=0.151Gain(credit_rating)=0.048因此选择student属性作为当前的测试属性age?overcaststudent?creditrating?=3040noyesyesyes31..40fairexcellentyesno算法：P189图7-3incomestudentcredit_ratclasshighhighmediumlowmediumnononoyesyesfairexcellfairfairexcellnononoyesyes课堂作业：计算下面样本的信息增益，并选择分裂属性，画出分裂后的子树incomestudentcredit_ratclasshighhighmediumlowmediumnononoyesyesfairexcellfairfairexcellnononoyesyes解：1、计算INFO（D）=I（S1，S2）=-[2/5*log(2/5)+3/5*log(3/5)]=2、分别计算E(income),E(student)、E(credit_rat)。例如计算E(income)如下：对于income=“high”：s11=0,s12=2,I(s11,s12)=-[0/2*log(0/2)+2/2*log(2/2)]=0对于income=“midium”：s21=1,s22=1,I(s21,s22)=-[1/2*log(1/2)+1/2*log(1/2)]=1对于income=“low”：s31=1,s32=0,I(s31,s32)=-[1/1*log(1/1)+1/1*log(0/1)]=0E(income)=2/5*0+2/5*1+1/5*0=0.4依次可以计算E(student)、E(credit_rat)，经比较可知E(student)最小（0）3、Gain(income)=INFO（D）-E(income)=依次可以计算Gain(student)、Gain(credit_rat),经比较可知Gain(student)最大。因此应该选择student结点作为分裂结点。分裂后的状况如图所示：student?yesnoyesno防止分类中的过分适应产生的判定树会出现过分适应数据的问题由于数据中的噪声和孤立点，许多分枝反应的是训练数据中的异常对新样本的判定很不精确防止过分适应的两种方法先剪枝：通过提前停止树的构造——如果在一个节点划分样本将导致低于预定义临界值的分裂（e.g.使用信息增益度量）选择一个合适的临界值往往很困难后剪枝：由“完全生长”的树剪去分枝——对于树中的每个非树叶节点，计算该节点上的子树被剪枝可能出现的期望错误率使用一个独立的测试集来评估每颗树的准确率，就能得到具有最小期望错误率的判定树由判定树提取分类规则可以提取判定树表示的知识，并以IF-THE