资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,PPT,文档演模板,Office,PPT,11 十一月 2026,分类和预测决策树,第四章 分类和预测,4.1 分类和预测的定义,4.2 数据分类方法,决策树,神经网络,SVM,贝叶斯网络,4.3 数据预测方法,线性回归,非线性回归,2,第四章 分类和预测,4.1 分类和预测的定义,4.2 数据分类方法,决策树,神经网络,SVM,贝叶斯网络,4.3 数据预测方法,线性回归,非线性回归,3,4.1 分类和预测的定义,分类(Classification),给定一个数据集,D=t,1,t,2,t,n,和一个类别集合,C=C,1,C,2,C,m,,,数据,分类,就是通过,定义一个映射,f:D,C,,为数据集,D,中的每条数据,t,i,分配,C,中的一个类,C,j,。,预测(Prediction),它是一种分类的泛化,当分类的类别是一个连续值时(可看成无限多类),就是,数据预测,。,4,4.1 分类和预测的定义,示例,分类,银行贷款员需要分析数据,来弄清哪些贷款申请者是安全的,哪些是有风险的。,构造一个映射(,模型,)将申请者分为两类:,安全,有风险,预测,银行贷款员需要分析数据,来预测贷给某个顾客多少钱是安全的。,构造一个映射(,模型,)来预测一个连续值。,如何建立具体,的映射(模型)?,5,4.1 分类和预测的定义,数据分类和预测的步骤如下:,第一步,建立模型,第二步,使用模型,下面以,分类,为例,详细介绍这两个步骤。,6,4.1 分类和预测的定义,第一步,建立模型,训练数据集:由若干数据(通常用n维属性向量表示)和它们相对应的类标号组成。,训练样本:训练数据集中的单个数据及其类标号。,从训练数据集“学习”相关知识来构造分类模型。,分类模型,可能会以,分类规则,、,决策树,或,数学公式,等形式呈现出来。,第二步,使用模型,对未知类别的数据进行分类(分配类别标号)。,7,第一步,建立模型,训练数据集,分类模型,IF rank=professor,OR years 6,THEN tenured=yes,分类规则,8,第二步,使用模型,分类规则,测试数据集,未知数据,(Jeff,Professor,4),Tenured?,9,第四章 分类和预测,4.1 分类和预测的定义,4.2 数据分类方法,决策树,神经网络,SVM,贝叶斯网络,4.3 数据预测方法,线性回归,非线性回归,10,4.2 数据分类方法,分类过程的数据预处理,分类的评价标准性能度量,11,分类过程的数据预处理,在执行分类过程之前,通过对数据进行预处理,可以提高分类过程的,准确性,、,有效性,和,可伸缩性,。,常用的预处理操作包括:,数据清理,相关分析,数据变换,12,分类过程的数据预处理,在执行分类过程之前,通过对数据进行预处理,可以提高分类过程的,准确性,、,有效性,和,可伸缩性,。,常用的预处理操作包括:,数据清理,:消除或减少噪声,处理空缺值,从而减少学习时的混乱。,相关分析,数据变换,13,分类过程的数据预处理,在执行分类过程之前,通过对数据进行预处理,可以提高分类过程的,准确性,、,有效性,和,可伸缩性,。,常用的预处理操作包括:,数据清理,相关分析,:数据中的有些属性可能与当前任务不相关或者是冗余的,则可以删除这些属性以加快学习过程,并使学习结果更精确。,例如:主成分分析(PCA),数据变换,14,分类过程的数据预处理,在执行分类过程之前,通过对数据进行预处理,可以提高分类过程的,准确性,、,有效性,和,可伸缩性,。,常用的预处理操作包括:,数据清理,相关分析,数据变换,:数据可以通过规范化,将给定属性的所有值按比例进行缩放,使其落入一个较小的指定区间中。,例如:0.0,1.0(神经网络中常用)。,15,分类过程的数据预处理,在执行分类过程之前,通过对数据进行预处理,可以提高分类过程的,准确性,、,有效性,和,可伸缩性,。,常用的预处理操作包括:,数据清理,相关分析,数据变换,在模式识别领域,特征提取与,特征选择,16,分类的评价标准,假设:给定测试集X,test,=(x,i,y,i,)|i=1,2,N,N,表示测试集中的样本个数;,x,i,表示测试集中第,i,个样本;,y,i,表示样本,x,i,的类标号。,对于测试集的第,j,个类别,分类结果如下:,被正确分类的样本数量为,TP,j,;,被错误分类的样本数量为,FN,j,;,其他类别被错误分类为该类的样本数据量为,FP,j,。,17,分类的评价标准,精确度(正确率),:表示测试集中被正确分类的数据所占的比例。,例如:在文字识别中,经常统计,识别正确率,,以此来表示识别系统的性能。,18,第四章 分类和预测,4.1 分类和预测的定义,4.2 数据分类方法,决策树,神经网络,SVM,贝叶斯网络,4.3 数据预测方法,线性回归,非线性回归,19,决策树,什么是决策树?,由数据的,不同属性,逐次划分数据集,直至得到的,数据子集,只包含同一类数据为止,这样可形成一棵树,称为决策树。,结构上类似于程序流程图;,每个内部结点表示在一个属性上的,测试,;,每个分枝代表一个测试的,输出,;,每个叶结点存放一个,类标号,。,由树的根结点到某个叶结点的属性的,合取,可形成一条分类规则;所有规则的,析取,可形成一整套分类规则。,20,决策树,生成,目标:根据客户的如下属性,,是否有贷款,、,婚姻状况,、,收入水平,,来判断客户是否存在“金融欺骗”行为。,如何从训练数据集生成,相应决策树,是本节所,关注的内容。,21,决策树分类过程,22,决策树分类过程,23,决策树分类过程,24,决策树分类过程,25,决策树分类过程,26,决策树分类过程,27,决策树属性选择的次序问题,哪棵树更好?or 哪种次序更好?,28,决策树,决策树关注的主要问题:,决策树的生成算法,ID3算法,C4.5算法,决策树的剪枝策略:许多分枝反映的是训练数据集中的噪声和离群点,剪枝试图识别并剪去这种分枝,以提高对未知数据分类的准确性。,先剪枝方法,后剪枝方法,29,ID3算法,特点:在选择根结点和各个内部结点的分枝属性时,采用,信息增益,作为度量标准,因此每次都会选择具有,最高信息增益,的属性作为分枝属性。,ID3算法只能处理属性值为,离散型,的数据集的划分。,30,ID3算法,给定数据集X=(x,i,y,i,)|i=1,2,total。,x,i,(i=1,2,.,total)用d维特征向量x,i,=(x,i1,x,i2,.,x,id,)来表示,x,i1,x,i2,.,x,id,分别对应d个属性A,1,A,2,.,A,d,的具体取值;,y,i,(i=1,2,.,total)表示样本x,i,的类标号,假设要研究的分类问题有m个类别,则y,i,c,1,c,2,.,c,m,。,假设n,j,是数据集X中属于类别c,j,的样本数量,则各类别的,先验概率,为:,对于数据集X,将其分为m类的,期望信息,为:,31,ID3算法,计算属性A,f,划分数据集X所得的,熵,:,假设A,f,有q个不同取值,可按q的不同取值将X划分为q个不同的子集X,1,X,2,X,s,X,q,;,假设n,s,表示X,s,中的样本数量,n,js,表示X,s,中属于类别c,j,的样本数量,则由属性A,f,划分数据集X的熵为:,其中:,32,ID3算法,计算属性A,f,划分数据集时的,信息增益,:,属性的信息增益值越大,表示它的区分度就越高,使用该属性进行分类的效果就越好。,ID3算法是通过选择具有,最高信息增益,的属性作为数据集的划分,从而可创建决策树中的一个结点,根据该属性的不同取值可形成该结点的不同分枝。,再对各分枝中的数据子集进行,递归划分,,直至形成叶结点或者某分枝上的所有数据不属于同一类别,但又没有剩余的属性可以进一步划分为止。,33,age,income,student,credit_rating,buy_computer,youth,high,no,fair,no,youth,high,no,excellent,no,middle_aged,high,no,fair,yes,senior,medium,no,fair,yes,senior,low,yes,fair,yes,senior,low,yes,excellent,no,middle_aged,low,yes,excellent,yes,youth,medium,no,fair,no,youth,low,yes,fair,yes,senior,medium,yes,fair,yes,youth,medium,yes,excellent,yes,middle_aged,medium,no,excellent,yes,middle_aged,high,yes,fair,yes,senior,medium,no,excellent,no,ID3算法示例(buy_computer),34,ID3算法示例(buy_computer),首先,计算数据集分类所需的期望信息:,在数据集中,给定的样本数量为14,类标号为Yes(表示购买电脑)的样本数量为n,1,=9,类标号为No(表示不购买电脑)的样本数量为n,2,=5,因此数据集中两个类别的先验概率分别为:,p(Yes)=n,1,/total=9/14,p(No)=n,2,/total=5/14,对数据集分类所需的期望信息为:,Info(n,1,n,2,)=-p(Yes)*log(p(Yes)-p(No)*log(p(No),=-9/14*log(9/14)-5/14*log(5/14),0.94,35,ID3算法示例(buy_computer),其次,计算各属性划分数据集时的信息增益:,先计算属性age的熵。由于属性age有三个不同取值(youth,middle_aged,senior),因此可将数据集划分成三个子集:X,1,X,2,和X,3,。,对于子集X,1,(,age=youth,),它的样本数量为n,1,=5,其中类标号为Yes的数量n,11,=2,类标号为No的数量n,12,=3,则这两类样本在子集X,1,中所占的比例分别为:,p,11,=n,11,/n,1,=2/5=0.4,p,12,=n,12,/n,1,=3/5=0.6,这样,子集X,1,的期望信息为:,Info(n,11,n,12,)=-p,11,*log(p,11,)-p,12,*log(p,12,),=-0.4*log(0.4)-0.6*log(0.6),36,ID3算法示例(buy_computer),其次,计算各属性划分数据集时的信息增益:,先计算属性age的熵。由于属性age有三个不同取值(youth,middle_aged,senior),因此可将数据集划分成三个子集:X,1,X,2,和X,3,。,对于子集X,2,(,age=middle_aged,),它的样本数量为n,2,=4,其中类标号为Yes的数量n,12,=4,类标号为No的数量n,22,=0,则这两类样本在子集X,2,中所占的比例分别为:,p,21,=n,12,/n,2,=4/4=1,p,22,=n,22,/n,2,=0/4=0,这样,子集X,2,的期望信息为:,Info(n,12,n,22,)=-p,12,*log(p,12,)-p,22,*log(p,22,)=0,37,ID3算法示例(buy_computer),其次,计算各属性划分数据集时的信息增益:,先计算属性age的熵。由于属性age有三个不同取值(youth,middle_aged,senior),因此可将数据集划分成三个子集:X,1,X,2,和X,3,。,对于子集X,3,(,age=senior,),它的样本数量为n,3,=5,其中类标号为Yes的数量n,13,=3,类标号为No的数量n,23,=2,则这两类样本在子集X,3,中所占的比例分别为:,p,13,=n,13,/n,3,=3/5=0.6,p,23,=n,23,/n,3,=2/5=0.4,这样,子集X,3,的期望信息为:,Info(n,13,n,23,)=-p,13,*log(p,13,)-p,23,*log(p,23,),=-0.6*log(0.6)-0.4*log(0.4),38,ID3算法示例(buy_computer),其次,计算各属性划分数据集时的信息增益:,先计算属性age的熵。由于属性age有三个不同取值(youth,middle_aged,senior),因此可将数据集划分成三个子集:X,1,X,2,和X,3,。,由于子集,X,1,X,2,和X,3,各自的期望信息分别为Info(n,11,n,12,),Info(n,12,n,22,)和Info(n,13,n,23,),因此,属性age划分数据集的熵为:,E(age)=5/14*Info(n,11,n,12,)+4/14*Info(n,12,n,22,),+5/14*Info(n,13,n,23,),0.694,计算属性age的信息增益为:,Gain(age)=Info(Yes,No)E(age)=0.94 0.694=0.246,39,ID3算法示例(buy_computer),其次,计算各属性划分数据集时的信息增益:,按上述方式,可依次计算其他属性的信息增益分别为:,Gain(income)=0.029,Gain(student)=0.151,Gain(credit_rating)=0.048,在4个属性中,age的信息增益最大(0.246),因此先以该属性来划分数据集。,40,ID3算法示例(buy_computer),41,ID3算法,ID3算法的,优点,:,ID3算法通常只需要测试一部分属性就可完成对训练数据集的分类。,从ID3算法构建的决策树中,很容易获得相应的决策规则。,42,ID3算法,ID3算法的,缺点,:,ID3算法在选择根节点和内部结点的属性时,使用信息增益作为评价标准。,信息增益更倾向于选择取值种类较多的属性进行划分,而不一定是,最优属性,进行划分。,ID3算法只能对属性值为离散型的数据集进行划分(构建决策树),不能处理属性值为连续型的数据集。,43,C4.5算法,C4.5算法使用,信息增益比,来确定分枝属性,能够克服ID3算法使用信息增益时偏向于取值类型较多属性的不足。,属性A,f,的,信息增益比,的定义为:,其中:,当q的值较大时,就会降低,信息增益比,。,44,C4.5算法,C4.5算法既可以处理离散型描述属性,也可以处理连续型描述属性。,当处理离散型属性时,C4.5算法与ID3算法相同;,当处理连续型属性时,C4.5算法需要先将连续型属性转换成离散型属性。,45,C4.5算法,C4.5算法既可以处理离散型描述属性,也可以处理连续型描述属性。,当处理离散型属性时,C4.5算法与ID3算法相同;,当处理连续型属性时,C4.5算法需要先将连续型属性转换成离散型属性。,对于连续值属性A,c,,假设在某个结点上的样本数量为total,则C4.5算法将进行如下操作:,(1)将该结点上的所有样本按照属性的取值,由小到大,排序,得到排序结果A,1c,A,2c,.,A,totalc,;,46,C4.5算法,C4.5算法既可以处理离散型描述属性,也可以处理连续型描述属性。,当处理离散型属性时,C4.5算法与ID3算法相同;,当处理连续型属性时,C4.5算法需要先将连续型属性转换成离散型属性。,对于连续值属性A,c,,假设在某个结点上的样本数量为total,则C4.5算法将进行如下操作:,(2)在A,1c,A,2c,.,A,totalc,中生成total-1个分割点,其中:第i个(1itotal-1)分割点的取值设置为v,i,=(A,ic,+A,(i+1)c,)/2。,47,C4.5算法,C4.5算法既可以处理离散型描述属性,也可以处理连续型描述属性。,当处理离散型属性时,C4.5算法与ID3算法相同;,当处理连续型属性时,C4.5算法需要先将连续型属性转换成离散型属性。,对于连续值属性A,c,,假设在某个结点上的样本数量为total,则C4.5算法将进行如下操作:,(3)从total-1个分割点中选择最佳分割点。,其中:最佳分割点具有,最大信息增益比,。,48,C4.5算法离散化示例,将“buy_computer”中的属性age的取值由youth,middle_aged,senior改为具体年龄32,25,46,56,60,52,42,36,23,51,38,43,41,65,C4.5算法离散化的具体过程。,(1)对年龄序列由小到大排序,新的序列为23,25,32,36,38,41,42,43,46,51,52,56,60,65;,(2)对新的年龄序列生成分割点:由于样本数量为14,因此可生成13个分割点。,例如:第一个分割点为(23+25)/2=24,它可将数据集划分为年龄在区间23,24的样本和在区间(24,65的样本。,49,C4.5算法离散化示例,将“buy_computer”中的属性age的取值由youth,middle_aged,senior改为具体年龄32,25,46,56,60,52,42,36,23,51,38,43,41,65,C4.5算法离散化的具体过程。,(3)选择最佳分割点。,例如:对于第一个分割点,可以计算得到年龄在区间23,24和(24,65的样本数量以及每个区间的样本属于各个类别的数量,从而计算第一个分割点的,信息增益比,。,依此方式,计算其他分割点的,信息增益比,,并从中选出具有,最大信息增益比,的分割点。,50,C4.5算法离散化示例,将“buy_computer”中的属性age的取值由youth,middle_aged,senior改为具体年龄32,25,46,56,60,52,42,36,23,51,38,43,41,65,C4.5算法离散化的具体过程。,(4)根据最佳分割点,离散化属性的连续值。,例如:当最佳分割点为37时,数据集中的样本可以根据age取值分成两类,一类是37,另一类是37。,说明:在有些情况下,可能需要确定多个最佳分割点。可以按上述过程获得依次信息增益比最大的分割点、次大的分割点等等。,51,
展开阅读全文