数据挖掘导论第4章分类：基本概念、决策树与模型评估

Click to edit Master title style,Click to edit Master text styles,Second Level,Third Level,数据挖掘 分类：基本概念、决策树与模型评价,第,4,章,分类：基本概念、决策树与模型评价,分类的是利用一个分类函数（分类模型、分类器），该模型能把数据库中的数据影射到给定类别中的一个。,分类,训练集：数据库中为建立模型而被分析的数据元组形成训练集。,训练集中的单个元组称为,训练样本,每个训练样本有一个类别标记。,一个具体样本的形式可为,:( v1, v2, ., vn; c );,其中,vi,表示属性值,c,表示类别。,测试集：用于评估分类模型的准确率,数据分类,一个两步过程,(1),第一步，建立一个模型，描述预定数据类集和概念集,假定每个元组属于一个预定义的类，由一个类标号属性确定,学习模型可以用分类规则、决策树或数学公式的形式提供,数据分类,一个两步过程,(2),第二步，使用模型，对将来的或未知的对象进行分类,首先评估模型的预测准确率,对每个测试样本，将已知的类标号和该样本的学习模型类预测比较,模型在给定测试集上的准确率是正确被模型分类的测试样本的百分比,测试集要独立于训练样本集，否则会出现“过分适应数据”的情况,如果准确性能被接受，则分类规则就可用来对新数据进行分类,有监督的学习,VS.,无监督的学习,有监督的学习（用于分类）,模型的学习在被告知每个训练样本属于哪个类的“监督”下进行,新数据使用训练数据集中得到的规则进行分类,无监督的学习（用于聚类）,每个训练样本的类编号是未知的，要学习的类集合或数量也可能是事先未知的,通过一系列的度量、观察来建立数据中的类编号或进行聚类,分类模型的构造方法,1.,机器学习方法：,决策树法,规则归纳,2.,统计方法：,知识表示是判别函数和原型事例,贝叶斯法,非参数法,(,近邻学习或基于事例的学习,),3.,神经网络方法,：,BP,算法,模型表示是前向反馈神经网络模型,4.,粗糙集,(rough set),知识表示是产生式规则,一个决策树的例子,categorical,categorical,continuous,class,Refund,MarSt,TaxInc,YES,NO,NO,NO,Yes,No,Married,Single, Divorced, 80K,Splitting Attributes,训练数据,模型,:,决策树,决策树的另一个例子,categorical,categorical,continuous,class,MarSt,Refund,TaxInc,YES,NO,NO,NO,Yes,No,Married,Single, Divorced, 80K,用决策树归纳分类,什么是决策树？,类似于流程图的树结构,每个内部节点表示在一个属性上的测试,每个分枝代表一个测试输出,每个树叶节点代表类或类分布,决策树的生成由两个阶段组成,决策树构建,开始时，所有的训练样本都在根节点,递归的通过选定的属性，来划分样本 （必须是离散值）,树剪枝,许多分枝反映的是训练数据中的噪声和孤立点，树剪枝试图检测和剪去这种分枝,决策树的使用：对未知样本进行分类,通过将样本的属性值与决策树相比较,为了对未知数据对象进行分类识别，可以根据决策树的结构对数据集中的属性进行测试，从,决策树的根节点到叶节点的一条路径,就形成了相应对象的类别测试。决策树可以很容易转换为分类规则,决策树分类任务,Decision Tree,一个决策树的例子,categorical,categorical,continuous,class,Refund,MarSt,TaxInc,YES,NO,NO,NO,Yes,No,Married,Single, Divorced, 80K,Splitting Attributes,训练数据,模型,:,决策树,应用决策树进行分类,Refund,MarSt,TaxInc,YES,NO,NO,NO,Yes,No,Married,Single, Divorced, 80K,测试数据,Start from the root of tree.,应用决策树进行分类,Refund,MarSt,TaxInc,YES,NO,NO,NO,Yes,No,Married,Single, Divorced, 80K,测试数据,应用决策树进行分类,Refund,MarSt,TaxInc,YES,NO,NO,NO,Yes,No,Married,Single, Divorced, 80K,测试数据,应用决策树进行分类,Refund,MarSt,TaxInc,YES,NO,NO,NO,Yes,No,Married,Single, Divorced, 80K,测试数据,应用决策树进行分类,Refund,MarSt,TaxInc,YES,NO,NO,NO,Yes,No,Married,Single, Divorced, 80K,测试数据,应用决策树进行分类,Refund,MarSt,TaxInc,YES,NO,NO,NO,Yes,No,Married,Single, Divorced, 80K,测试数据,Assign Cheat to “No”,决策树分类,Decision Tree,决策树,有许多决策树算法,:,Hunt,算法,信息增益,Information gain,（,ID3,）,增益比率,Gain ration,（,C4.5,）,基尼指数,Gini index,(SLIQ,，,SPRINT),Hunt,算法,设,D,t,是与结点,t,相关联的训练记录集,算法步骤,:,如果,D,t,中所有记录都属于同一个类,y,t,则,t,是叶结点，用,y,t,标记,如果,D,t,中包含属于多个类的记录，则,选择一个属性测试条件,，将记录划分成较小的子集。对于测试条件的每个输出，创建一个子结点，并根据测试结果将,D,t,中的记录分布到子结点中。然后，对于每个子结点，递归地调用该算法,D,t,?,Hunt,算法,Dont,Cheat,Refund,Dont,Cheat,Dont,Cheat,Yes,No,Refund,Dont,Cheat,Yes,No,Marital,Status,Dont,Cheat,Cheat,Single,Divorced,Married,Taxable,Income,Dont,Cheat,= 80K,Refund,Dont,Cheat,Yes,No,Marital,Status,Dont,Cheat,Cheat,Single,Divorced,Married,决策树,Hunt,算法采用贪心策略构建决策树,.,在选择划分数据的属性时，采取一系列局部最优决策来构造决策树,.,决策树归纳的设计问题,如何分裂训练记录,怎样为不同类型的属性指定测试条件,?,怎样评估每种测试条件,?,如何停止分裂过程,决策树,Hunt,算法采用贪心策略构建决策树,.,在选择划分数据的属性时，采取一系列局部最优决策来构造决策树,.,决策树归纳的设计问题,如何分裂训练记录,怎样为不同类型的属性指定测试条件,?,怎样评估每种测试条件,?,如何停止分裂过程,怎样为不同类型的属性指定测试条件,?,依赖于属性的类型,标称,序数,连续,依赖于划分的路数,2,路划分,多路划分,基于标称属性的分裂,多路划分,:,划分数（输出数）取决于该属性不同属性值的个数,.,二元划分,:,划分数为,2,，这种划分要考虑创建,k,个属性值的二元划分的所有,2,k-1,-1,种方法,.,CarType,Family,Sports,Luxury,CarType,Family, Luxury,Sports,CarType,Sports, Luxury,Family,OR,CarType,Family,Sports,Luxury,多路划分,:,划分数（输出数）取决于该属性不同属性值的个数,.,二元划分,:,划分数为,2,，需要保持序数属性值的有序性,.,基于序数属性的划分,Size,Small,Medium,Large,Size,Medium, Large,Small,Size,Small, Medium,Large,OR,Size,Small, Large,Medium,基于连续属性的划分,多路划分,:,v,i,A,v,i+1,（,i=1,k),二元划分,: (A v) or (A, v),考虑所有的划分点，选择一个最佳划分点,v,基于连续属性的划分,决策树,决策树归纳的设计问题,如何分裂训练记录,怎样为不同类型的属性指定测试条件,?,怎样评估每种测试条件,?,如何停止分裂过程,怎样选择最佳划分？,在划分前,: 10,个记录,class 0, 10,个记录,class 1,怎样选择最佳划分？,选择最佳划分的度量通常是根据划分后子结点不纯性的程度。不纯性的程度越低，类分布就越倾斜,结点不纯性的度量,:,不纯性大,不纯性小,怎样找到最佳划分？,B?,Yes,No,Node N3,Node N4,A?,Yes,No,Node N1,Node N2,划分前,:,M0,M1,M2,M3,M4,M12,M34,Gain = M0 M12 vs M0 M34,结点不纯性的测量,Gini,Entropy,classification error,不纯性的测量,: GINI,给定结点,t,的,Gini,值计算,:,(,p( j | t),是在结点,t,中，类,j,发生的概率,).,当类分布均衡时，,Gini,值达到最大值,(1 - 1/n,c,),相反当只有一个类时，,Gini,值达到最小值,0,计算,GINI,的例子,P(C1) = 0/6 = 0 P(C2) = 6/6 = 1,Gini = 1 P(C1),2, P(C2),2,= 1 0 1 = 0,P(C1) = 1/6 P(C2) = 5/6,Gini = 1 (1/6),2, (5/6),2,= 0.278,P(C1) = 2/6 P(C2) = 4/6,Gini = 1 (2/6),2, (4/6),2,= 0.444,基于,GINI,的划分,当一个结点,p,分割成,k,个部分,(,孩子,),划分的质量可由下面公式计算,n,i,=,孩子结点,i,的记录数,n,=,父结点,p,的记录数,.,二元属性,:,计算,GINI,对于二元属性，结点被划分成两个部分,得到的,GINI,值越小，这种划分越可行,.,B?,Yes,No,Node N1,Node N2,Gini(N1) = 1 (5/6),2, (2/6),2,= 0.194,Gini(N2) = 1 (1/6),2, (4/6),2,= 0.528,Gini,split,= 7/12 * 0.194 + 5/12 * 0.528= 0.333,标称属性,:,计算,Gini,多路划分,二元划分,一般多路划分的,Gini,值比二元划分小，这一结果并不奇怪，因为二元划分实际上合并了多路划分的某些输出，自然降低了子集的纯度,Multi-way split,Two-way split,(find best partition of values),连续属性,:,计算,Gini,使用二元划分,划分点,v,选择,N,个记录中所有属性值作为划分点,对每个划分进行类计数, A v and A,v,计算每个候选点,v,的,Gini,指标，并从中选择具有最小值的候选划分点,时间复杂度为,(n,2,),连续属性,:,计算,Gini.,降低计算复杂性的方法,将记录进行排序,从两个相邻的排过序的属性值之间选择中间值作为划分点,计算每个候选点的,Gini,值,时间复杂度为,nlogn,划分点,排序后的值,定义：给定一个概率空间 事件,的自信息定义为,因,自信息反映了事件 发生所需要的信息量。,值越大说明需要越多的信息才能确定事件 的发生，其随机性也越大，而当 发生时所携带的信息量也越大。反过来， 值越小，需要较少信息量就能确定 的发生，即事件 随机性较小。当其发生时所携信息量就少。 是对不确定性大小的一种刻画,熵,-,定义,熵,-,定义,1.,定义：在概率空间 上定义的随机变量,I( X),的数学期望,称为随机变量,X,的平均自信息，又称,X,的信息熵或熵记为,H(x),非负性：,H,大于等于,0,连续性：,H,对任意,q,连续,极值性：当,q,都等于,1K,时,H,达到最大值,logK,熵,-,定义,基于,Information Gain,的划分,给定结点,t,的,Entropy,值计算,:,(,p( j | t),是在结点,t,中，类,j,发生的概率,).,当类分布均衡时，,Entropy,值达到最大值,(log n,c,),相反当只有一个类时，,Gini,值达到最小值,0,Entropy,与,GINI,相似,计算,Entropy,的例子,P(C1) = 0/6 = 0 P(C2) = 6/6 = 1,Entropy = 0 log 0, 1 log 1 = 0 0 = 0,P(C1) = 1/6 P(C2) = 5/6,Entropy = (1/6) log,2,(1/6), (5/6) log,2,(1/6) = 0.65,P(C1) = 2/6 P(C2) = 4/6,Entropy = (2/6) log,2,(2/6), (4/6) log,2,(4/6) = 0.92,基于,Information Gain,的划分,.,Information Gain:,n,i,=,孩子结点,i,的记录数,n,=,结点,p,的记录数,.,在,ID3 and C4.5,中使用,基于,Information Gain,的划分,.,增益率（,Gain Ratio,）,:,熵和,Gini,指标等不纯性趋向于有利于具有大量不同值的属性,!,如：利用雇员,id,产生更纯的划分，但它却毫无用处,每个划分相关联的记录数太少，将不能做出可靠的预测,解决该问题的策略有两种：,限制测试条件只能是二元划分,使用增益率。,K,越大,Split Info,越大增益率越小,基于,Classification Error,的划分,给定结点,t,的,Classification Error,值计算,:,当类分布均衡时，,error,值达到最大值,(1 - 1/n,c,),相反当只有一个类时，,error,值达到最小值,0,例子,P(C1) = 0/6 = 0 P(C2) = 6/6 = 1,Error = 1 max (0, 1) = 1 1 = 0,P(C1) = 1/6 P(C2) = 5/6,Error = 1 max (1/6, 5/6) = 1 5/6 = 1/6,P(C1) = 2/6 P(C2) = 4/6,Error = 1 max (2/6, 4/6) = 1 4/6 = 1/3,不纯性度量之间的比较,二元分类问题,:,决策树,Hunt,算法采用贪心策略构建决策树,.,在选择划分数据的属性时，采取一系列局部最优决策来构造决策树,.,决策树归纳的设计问题,如何分裂训练记录,怎样为不同类型的属性指定测试条件,?,怎样评估每种测试条件,?,如何停止分裂过程,停止分裂过程,当所有的记录属于同一类时，停止分裂,当所有的记录都有相同的属性时，停止分裂,提前终止树的生长,三种著名的决策树,Cart,：基本的决策树算法,Id3,：利用增益比不纯性，树采用二叉树，停止准则为当所有的记录属于同一类时，停止分裂，或当所有的记录都有相同的属性时，停止分裂,C4.5,：,id3,的改进版本，也是最流行的分类数算法。采用多重分支和剪枝技术。,决策树,特点,:,决策树是一种构建分类模型的非参数方法,不需要昂贵的的计算代价,决策树相对容易解释,决策树是学习离散值函数的典型代表,决策数对于噪声的干扰具有相当好的鲁棒性,冗余属性不会对决策树的准确率造成不利影响,数据碎片问题。随着数的生长，可能导致叶结点记录数太少，对于叶结点代表的类，不能做出具有统计意义的判决,子树可能在决策树中重复多次。使决策树过于复杂,子树重复问题,Same,subtree,appears in multiple branches,决策边界,斜决策树,x + y 1,Class =,+,Class =,模型过分拟合和拟合不足,分类模型的误差大致分为两种：,训练误差：是在训练记录上误分类样本比例,泛化误差：是模型在未知记录上的期望误差,一个好的分类模型不仅要能够很好的拟合训练数据，而且对未知样本也要能准确分类。,换句话说，一个好的分类模型必须具有低训练误差和低泛化误差。,当训练数据拟合太好的模型，其泛化误差可能比具有较高训练误差的模型高，这种情况成为模型,过分拟合,模型过分拟合和拟合不足,当决策树很小时，训练和检验误差都很大，这种情况称为,模型拟合不足,。出现拟合不足的原因是模型尚未学习到数据的真实结构。,随着决策树中结点数的增加，模型的训练误差和检验误差都会随之下降。,当树的规模变得太大时，即使训练误差还在继续降低，但是检验误差开始增大，导致,模型过分拟合,模型模型过分拟合和拟合不足,过分拟合,导致过分拟合的原因,导致过分拟合的原因,噪声导致的过分拟合,例子：哺乳动物的分类问题,十个训练记录中有两个被错误标记：蝙蝠和鲸,如果完全拟合训练数据，决策树,1,的训练误差为,0,，但它在检验数据上的误差达,30%.,人和海豚，针鼹误分为非哺乳动物,相反，一个更简单的决策树,2,，具有较低的检验误差（,10%,），尽管它的训练误差较高，为,20%,决策树,1,过分拟合了训练数据。因为属性测试条件,4,条腿具有欺骗性，它拟合了误标记的训练纪录，导致了对检验集中记录的误分类,噪声导致的过分拟合（例子）,噪声导致决策边界的改变,缺乏代表性样本导致的过分拟合,根据少量训练记录做出分类决策的模型也容易受过分拟合的影响。,由于训练数据缺乏具有代表性的样本，在没有多少训练记录的情况下，学习算法仍然细化模型就会产生过分拟合。,例子：五个训练记录，所有的记录都是正确标记的，对应的决策树尽管训练误差为,0,，但检验误差高达,30%,人、大象和海豚被误分类，因为决策树把恒温但不冬眠的动物分为非哺乳动物。决策树做出这样的分类决策是因为只有一个训练记录（鹰）具有这些特征。,这个例子清楚的表明，当决策树的叶结点没有足够的代表性样本时，很可能做出错误的预测。,过分拟合与多重比较,模型的过分拟合可能出现在使用多重比较过程的算法中,多重比较的例子：考虑未来十个交易日股市是升还是降,一个人十次猜测至少正确预测八次的概率是：,0.0547,假设从,50,个股票分析家中选择一个投资顾问，策略是选择在未来的十个交易日做出最多正确预测的分析家。,该策略的缺点是，即使所有的分析家都用随机猜测做出预测，至少有一个分析家做出八次正确预测的概率是：,1-,（,1-0.0547,）,50,=0.9399,，这一结果相当高。,多重比较过程与模型过分拟合有什么关系？,在决策树增长过程中，可以进行多种测试，以确定哪个属性能够最好的划分训练数据。,在这种情况下，算法实际上是使用多重比较过程来决定是否需要扩展决策树。,当候选属性多，训练记录数少时，这种影响就变得更加明显。,泛化误差估计,过分拟合的主要原因一直是个争辩的话题，但大家还是普遍同意模型的复杂度对模型的过分拟合有影响。,如何确定正确的模型复杂度？理想的复杂度是能产生最低泛化误差的模型的复杂度。,估计泛化误差的方法,使用再代入估计。用训练误差提供对泛化误差的乐观估计,结合模型复杂度,估计统计上界,使用确定集,结合模型复杂度,奥卡姆剃刀 （,Occams Razor,）：给定两个具有相同泛化误差的模型，较简单的模型比复杂的模型更可取,因为复杂模型中的附加成分很大程度上是偶然的拟合。因此，分类模型评估应把模型复杂度考虑进去,方法：悲观误差估计、最小描述长度原则（,MDL,）,悲观误差评估,悲观误差估计公式：,Q(ti),为每个结点,ti,的罚分，,e(T),为训练样本集的错分样本数，,N,t,为训练样本总数，,k,为叶结点数。,例子,1,：如果罚分等于,0.5,，训练样本集中样本数为,24,个，我们构建了,7,个叶结点的决策树，训练样本集的错分样本数为,4,根据公式我们得,e(T)=(4+7*0.5)/24=0.3125,例子,2,：如果罚分等于,0.5,，训练样本集中样本数为,24,个，我们构建了,4,个叶结点的决策树，训练样本集的错分样本数为,6,根据公式我们得,e(T)=(6+4*0.5)/24=0.3333,当罚分等于,1,时，例,1,，,2,为,0.458,，,0.417,0.5,的罚分项表示只要至少能够改进一个训练记录的分类，结点就应当扩充，因为扩展一个结点等价于总误差增加,0.5,，代价比犯一个训练错误小,最小描述长度,(MDL),Cost(Model,Data) = Cost(Data|Model) + Cost(Model),Cost,是传输总代价,.,最小化,cost,值,.,Cost(Data|Model),是误分类记录编码的开销,.,Cost(Model),是模型编码的开销,.,使用确认集,该方法中，不是用训练集估计泛化误差，而是把原始的训练数据集分为两个较小的子集，一个子集用于训练，而另一个称为确认集，用于估计泛化误差。,该方法为评估模型在未知样本上的性能提供了较好办法。,处理决策树中的过分拟合,先剪枝,(Early Stopping Rule),树增长算法在产生完全拟合整个训练数据集的之前就停止决策树的生长,为了做到这一点，需要采用更具限制性的结束条件,:,当结点的记录数少于一定阈值，则停止生长,当不纯性度量的增益低于某个确定的阈值时，则停止生长,(e.g., information gain).,缺点：很难为提前终止选取正确的阈值,:,阈值太高，导致拟合不足,阈值太低，导致不能充分解决过分拟合的问题。,处理决策树中的过分拟合,后剪枝,在该方法中，初始决策树按照最大规模生长，然后进行剪枝的步骤，按照自底向上的方式修剪完全增长的决策树。,修剪有两种做法,:,用新的叶结点替换子树，该叶结点的类标号由子树下记录中的多数类确定,用子树中最常用的分支代替子树,处理决策树中的过分拟合,与先剪枝相比，后剪枝技术倾向于产生更好的结果。,因为不像先剪枝，后剪枝是根据完全增长的决策树作出的剪枝决策，先剪枝则可能过早终止决策树的生长。,然而，对于后剪枝，当子树被剪掉后，生长完全决策树的额外开销就被浪费了。,不平衡类问题,PREDICTED CLASS,ACTUALCLASS,Class=Yes,Class=No,Class=Yes,a,(TP),b,(FN),Class=No,c,(FP),d,(TN),准确率的缺点,考虑,2,类问题,类,0,的样本数,= 9990,类,1,的样本数,= 10,如果模型预测所有的样本为类,0,准确率为,9990/10000 = 99.9 %,准确率的值具有欺骗性,模型并没有分对类,1,的任何样本,度量,精度确定在分类器断言为正类的那部分记录中实际为正类的记录所占的比例。精度越高，分类器的假正类错误率就越低。,召回率度量被分类器正确预测的正样本的比例。具有高召回率的分类器很少将正样本误分为负样本。,ROC (Receiver Operating Characteristic),ROC,曲线是显示分类器真正率（,TPR,）和假正率（,FPR,）之间折中的一种图形化方法。,ROC,曲线上有几个关键点，它们有公认的解释：,（,TPR=0,，,FPR=0,）：把每个实例都预测为负类的模型,（,TPR=1,，,FPR=1,）：把每个实例都预测为正类的模型,（,TPR=1,，,FPR=0,）：理想模型,使用,ROC,曲线比较模型,没有哪个模型能够压倒对方,FRR0.36, M,2,较好,ROC,曲线下方的面积,理想情况,:,面积,= 1,随机猜测,:,面积,= 0.5,怎样产生,ROC,曲线,Threshold =,ROC,曲线,:,