分类和预测决策树

第四章分类和预测主讲教师：魏宏喜(博士，副教授)2第四章分类和预测4.1分类和预测的定义4.2数据分类方法决策树神经网络SVM贝叶斯网络4.3数据预测方法线性回归非线性回归3第四章分类和预测4.1分类和预测的定义4.2数据分类方法决策树神经网络SVM贝叶斯网络4.3数据预测方法线性回归非线性回归44.1分类和预测的定义分类（Classification）给定一个数据集D={t1,t2,…,tn}和一个类别集合C={C1,C2,…,Cm}，数据分类就是通过定义一个映射f:DC，为数据集D中的每条数据ti分配C中的一个类Cj。预测（Prediction）它是一种分类的泛化，当分类的类别是一个连续值时（可看成无限多类），就是数据预测。54.1分类和预测的定义——示例分类银行贷款员需要分析数据，来弄清哪些贷款申请者是安全的，哪些是有风险的。构造一个映射（模型）将申请者分为两类：安全有风险预测银行贷款员需要分析数据，来预测贷给某个顾客多少钱是安全的。构造一个映射（模型）来预测一个连续值。如何建立具体的映射（模型）？64.1分类和预测的定义数据分类和预测的步骤如下：第一步——建立模型第二步——使用模型下面以分类为例，详细介绍这两个步骤。74.1分类和预测的定义第一步——建立模型训练数据集：由若干数据（通常用n维属性向量表示）和它们相对应的类标号组成。训练样本：训练数据集中的单个数据及其类标号。从训练数据集“学习”相关知识来构造分类模型。分类模型可能会以分类规则、决策树或数学公式等形式呈现出来。第二步——使用模型对未知类别的数据进行分类（分配类别标号）。8第一步——建立模型训练数据集分类模型IFrank=‘professor’ORyears>6THENtenured=‘yes’分类规则9第二步——使用模型分类规则测试数据集未知数据(Jeff,Professor,4)Tenured?10第四章分类和预测4.1分类和预测的定义4.2数据分类方法决策树神经网络SVM贝叶斯网络4.3数据预测方法线性回归非线性回归114.2数据据分分类类方方法法分类类过过程程的的数数据据预预处处理理分类类的的评评价价标标准准————性性能能度度量量12分类类过过程程的的数数据据预预处处理理在执执行行分分类类过过程程之之前前，，通通过过对对数数据据进进行行预预处处理理，，可可以以提提高高分分类类过过程程的的准确确性性、有效效性性和可伸伸缩缩性性。常用的预处处理操作包包括：数据清理相关分析数据变换13分类过程的的数据预处处理在执行分类类过程之前前，通过对对数据进行行预处理，，可以提高高分类过程程的准确性、有效性和可伸缩性。常用的预处处理操作包包括：数据清理：消除或减减少噪声，，处理空缺缺值，从而而减少学习习时的混乱乱。相关分析数据变换14分类过程的的数据预处处理在执行分类类过程之前前，通过对对数据进行行预处理，，可以提高高分类过程程的准确性、有效性和可伸缩性。常用的预处处理操作包包括：数据清理相关分析：数据中的的有些属性性可能与当当前任务不不相关或者者是冗余的的，则可以以删除这些些属性以加加快学习过过程，并使使学习结果果更精确。。例如：主成成分分析（（PCA）数据变换15分类过程的的数据预处处理在执行分类类过程之前前，通过对对数据进行行预处理，，可以提高高分类过程程的准确性、有效性和可伸缩性。常用的预处处理操作包包括：数据清理相关分析数据变换：数据可以以通过规范范化，将给给定属性的的所有值按按比例进行行缩放，使使其落入一一个较小的的指定区间间中。例如：[0.0,1.0]（神经网络络中常用））。16分类过程的的数据预处处理在执行分类类过程之前前，通过对对数据进行行预处理，，可以提高高分类过程程的准确性、有效性和可伸缩性。常用的预处处理操作包包括：数据清理相关分析数据变换在模式识别别领域特征提取与与特征选择17分类的评价价标准假设：给定定测试集Xtest={(xi,yi)|i=1,2,……,N}N表示测试集集中的样本本个数；xi表示测试集集中第i个样本；yi表示样本xi的类标号。。对于测试集集的第j个类别，分分类结果如如下：被正确分类类的样本数数量为TPj；被错误分类类的样本数数量为FNj；其他类别被被错误分类类为该类的的样本数据据量为FPj。18分类的评价价标准精确度（正正确率）：表示测试试集中被正正确分类的的数据所占占的比例。。例如：在文文字识别中中，经常统统计识别正确率率，以此来表表示识别系系统的性能能。19第四章分分类和预测测4.1分类和预测测的定义4.2数据分类方方法决策树神经网络SVM贝叶斯网络络4.3数据预测方方法线性回归非线性回归归20决策树什么是决策策树？由数据的不同属性逐次划分数数据集，直直至得到的的数据子集只包含同一一类数据为为止，这样样可形成一一棵树，称称为决策树树。结构上类似似于程序流流程图；每个内部结结点表示在在一个属性性上的测试；每个分枝代代表一个测测试的输出；每个叶结点点存放一个个类标号。由树的根结结点到某个个叶结点的的属性的合取可形成一条条分类规则则；所有规规则的析取可形成一整整套分类规规则。21决策树生成目标：根据据客户的如如下属性，，是否有贷款款、婚姻状况、收入水平，来判断客客户是否存存在“金融融欺骗”行行为。如何从训练数据集生成相应决策树，是本节所关注的内容。22决策树———分类过程程23决策树———分类过程程24决策树———分类过程程25决策树———分类过程程26决策树———分类过程程27决策树———分类过程程28决策树———属性选择择的次序问问题哪棵树更好好？or哪种次序更更好？29决策树决策树关注注的主要问问题：决策树的生生成算法ID3算法C4.5算法决策树的剪剪枝策略：：许多分枝枝反映的是是训练数据据集中的噪噪声和离群群点，剪枝枝试图识别别并剪去这这种分枝，，以提高对对未知数据据分类的准准确性。先剪枝方法法后剪枝方法法30ID3算法法特点：在选选择根结点点和各个内内部结点的的分枝属性性时，采用用信息增益作为度量标标准，因因此每次都都会选择具具有最高信息增增益的属性作为为分枝属性性。ID3算法只能处处理属性值值为离散型的数据集的的划分。31ID3算法法给定数据集集X={(xi,yi)|i=1,2,……,total}。xi(i=1,2,...,total)用d维特征向量量xi=(xi1,xi2,...,xid)来表示，xi1,xi2,...,xid分别对应d个属性A1,A2,...,Ad的具体取值值；yi(i=1,2,...,total)表示样本xi的类标号，，假设要研研究的分类类问题有m个类别，则则yi∈{c1,c2,...,cm}。假设nj是数据集X中属于类别别cj的样本数量量，则各类类别的先验概率为：对于数据集集X，将其分为为m类的期望信息为：32ID3算法法计算属性Af划分数据集集X所得的熵：假设Af有q个不同取值值，可按q的不同取值值将X划分为q个不同的子子集{X1,X2,…,Xs,…,Xq}；假设ns表示Xs中的样本本数量，，njs表示Xs中属于类类别cj的样本数数量，则则由属性性Af划分数据据集X的熵为：：其中：33ID3算算法计算属性性Af划分数据据集时的的信息增益益：属性的信信息增益益值越大大，表示示它的区区分度就就越高，，使用该该属性进进行分类类的效果果就越好好。ID3算法是通通过选择择具有最高信息息增益的属性作作为数据据集的划划分，从从而可创创建决策策树中的的一个结结点，根根据该属属性的不不同取值值可形成成该结点点的不同同分枝。。再对各分分枝中的的数据子子集进行行递归划分分，直至形形成叶结结点或者者某分枝枝上的所所有数据据不属于于同一类类别，但但又没有有剩余的的属性可可以进一一步划分分为止。。34ageincomestudentcredit_ratingbuy_computeryouthhighnofairnoyouthhighnoexcellentnomiddle_agedhighnofairyesseniormediumnofairyesseniorlowyesfairyesseniorlowyesexcellentnomiddle_agedlowyesexcellentyesyouthmediumnofairnoyouthlowyesfairyesseniormediumyesfairyesyouthmediumyesexcellentyesmiddle_agedmediumnoexcellentyesmiddle_agedhighyesfairyesseniormediumnoexcellentnoID3算法——示例（buy_computer）35ID3算法——示例（buy_computer）首先，计计算数据据集分类类所需的的期望信信息：在数据集集中，给给定的样样本数量量为14，类标号号为Yes(表示购买买电脑)的样本数数量为n1=9，类标号号为No(表示不购购买电脑脑)的样本数数量为n2=5，因此数数据集中中两个类类别的先先验概率率分别为为：p(Yes)=n1/total=9/14p(No)=n2/total=5/14对数据集集分类所所需的期期望信息息为：Info(n1,n2)=-p(Yes)*log(p(Yes))-p(No)*log(p(No))=-9/14*log(9/14)-5/14*log(5/14)≈0.9436ID3算法——示例（buy_computer）其次，计计算各属属性划分分数据集集时的信信息增益益：先计算属属性age的熵。由由于属性性age有三个不不同取值值（youth，middle_aged，senior），因此此可将数数据集划划分成三三个子集集：X1,X2和X3。对于子集集X1(age=youth)，它的样样本数量量为n1=5，其中类类标号为为Yes的数量n11=2，类标号号为No的数量n12=3，则这两两类样本本在子集集X1中所占的的比例分分别为：：p11=n11/n1=2/5=0.4p12=n12/n1=3/5=0.6这样，子子集X1的期望信信息为：：Info(n11,n12)=-p11*log(p11)-p12*log(p12)=-0.4*log(0.4)-0.6*log(0.6)37ID3算法法———示例例（（buy_computer）其次次，，计计算算各各属属性性划划分分数数据据集集时时的的信信息息增增益益：：先计计算算属属性性age的熵熵。。由由于于属属性性age有三三个个不不同同取取值值（（youth，middle_aged，senior），，因因此此可可将将数数据据集集划划分分成成三三个个子子集集：：X1,X2和X3。对于于子子集集X2(age=middle_aged)，它它的的样样本本数数量量为为n2=4，其其中中类类标标号号为为Yes的数数量量n12=4，类类标标号号为为No的数数量量n22=0，则则这这两两类类样样本本在在子子集集X2中所所占占的的比比例例分分别别为为：：p21=n12/n2=4/4=1p22=n22/n2=0/4=0这样样，，子子集集X2的期期望望信信息息为为：：Info(n12,n22)=-p12*log(p12)-p22*log(p22)=038ID3算法法———示例例（（buy_computer）其次次，，计计算算各各属属性性划划分分数数据据集集时时的的信信息息增增益益：：先计计算算属属性性age的熵熵。。由由于于属属性性age有三三个个不不同同取取值值（（youth，middle_aged，senior），，因因此此可可将将数数据据集集划划分分成成三三个个子子集集：：X1,X2和X3。对于于子子集集X3(age=senior)，它它的的样样本本数数量量为为n3=5，其其中中类类标标号号为为Yes的数数量量n13=3，类类标标号号为为No的数数量量n23=2，则则这这两两类类样样本本在在子子集集X3中所占的的比例分分别为：：p13=n13/n3=3/5=0.6p23=n23/n3=2/5=0.4这样，子子集X3的期望信信息为：：Info(n13,n23)=-p13*log(p13)-p23*log(p23)=-0.6*log(0.6)-0.4*log(0.4)39ID3算法——示例（buy_computer）其次，计计算各属属性划分分数据集集时的信信息增益益：先计算属属性age的熵。由由于属性性age有三个不不同取值值（youth，middle_aged，senior），因此此可将数数据集划划分成三三个子集集：X1,X2和X3。由于子集集X1,X2和X3各自的期期望信息息分别为为Info(n11,n12)，Info(n12,n22)和Info(n13,n23)，因此，，属性age划分数据据集的熵熵为：E(age)=5/14*Info(n11,n12)+4/14*Info(n12,n22)+5/14*Info(n13,n23)≈0.694计算属性性age的信息增增益为：：Gain(age)=Info(Yes,No)––E(age)=0.94–0.694=0.24640ID3算法——示例（buy_computer）其次，计计算各属属性划分分数据集集时的信信息增益益：按上述方方式，可可依次计计算其他他属性的的信息增增益分别别为：Gain(income)=0.029Gain(student)=0.151Gain(credit_rating)=0.048在4个属性中中，age的信息增增益最大大(0.246)，因此先先以该属属性来划划分数据据集。41ID3算法——示例（buy_computer）42ID3算算法ID3算法的优点：ID3算法通常常只需要要测试一一部分属属性就可可完成对对训练数数据集的的分类。。从ID3算法构建建的决策策树中，，很容易易获得相相应的决决策规则则。43ID3算算法ID3算法的缺点：ID3算法在选选择根节节点和内内部结点点的属性性时，使使用信息息增益作作为评价价标准。。信息增益益更倾向向于选择择取值种种类较多多的属性性进行划划分，而而不一定定是最优属性性进行划分分。ID3算法只能能对属性性值为离离散型的的数据集集进行划划分（构构建决策策树），，不能处处理属性性值为连连续型的的数据集集。44C4.5算法C4.5算法使用用信息增益益比来确定分分枝属性性，能够够克服ID3算法使用用信息增增益时偏偏向于取取值类型型较多属属性的不不足。属性Af的信息增益益比的定义为为：其中：当q的值较大时，就会降低信息增益比。45C4.5算法C4.5算法既可可以处理理离散型型描述属属性，也也可以处处理连续续型描述述属性。。当处理离离散型属属性时，，C4.5算法与ID3算法相同同；当处理连连续型属属性时，，C4.5算法需要要先将连连续型属属性转换换成离散散型属性性。46C4.5算法C4.5算法既可可以处理理离散型型描述属属性，也也可以处处理连续续型描述述属性。。当处理离离散型属属性时，，C4.5算法与ID3算法相同同；当处理连连续型属属性时，，C4.5算法需要要先将连连续型属属性转换换成离散散型属性性。对于连续续值属性性Ac，假设在在某个结结点上的的样本数数量为total，则C4.5算法将进进行如下下操作：：(1)将该结点点上的所所有样本本按照属属性的取取值由小到大大排序，得得到排序序结果{A1c,A2c,...,Atotalc}；47C4.5算法C4.5算法既可可以处理理离散型型描述属属性，也也可以处处理连续续型描述述属性。。当处理离离散型属属性时，，C4.5算法与ID3算法相同同；当处理连连续型属属性时，，C4.5算法需要要先将连连续型属属性转换换成离散散型属性性。对于连续续值属性性Ac，假设在在某个结结点上的的样本数数量为total，则C4.5算法将进进行如下下操作：：(2)在{A1c,A2c,...,Atotalc}中生成total-1个分割点点其中：第第i个(1≤i≤total-1)分割点的的取值设设置为vi=(Aic+A(i+1)c)/2。48C4.5算法C4.5算法既可可以处理理离散型型描述属属性，也也可以处处理连续续型描述述属性。。当处理离离散型属属性时，，C4.5算法与ID3算法相同同；当处理连连续型属属性时，，C4.5算法需要要先将连连续型属属性转换换成离散散型属性性。对于连续续值属性性Ac，假设在在某个结结点上的的样本数数量为total，则C4.5算法将进进行如下下操作：：(3)从total-1个分割点点中选择择最佳分分割点。。其中：最最佳分割割点具有有最大信息息增益比比。49C4.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]的样本和和在