4分类和预测(1)决策树

第四章分类和预测主讲教师：魏宏喜(博士，副教授)E-mail:[e-mail]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:DC，为数据集D中的每条数据ti分配C中的一个类Cj。预测（Prediction）它是一种分类的泛化，当分类的类别是一个连续值时（可看成无限多类），就是数据预测。54.1分类和预测的定义——示例分类银行贷款员需要分析数据，来弄清哪些贷款申请者是安全的，哪些是有风险的。构造一个映射（模型）将申请者分为两类：安全有风险预测银行贷款员需要分析数据，来预测贷给某个顾客多少钱是安全的。构造一个映射（模型）来预测一个连续值。如何建立具体的映射（模型）？64.1分类和预测的定义数据分类和预测的步骤如下：第一步——建立模型第二步——使用模型下面以分类为例，详细介绍这两个步骤。74.1分类和预测的定义第一步——建立模型训练数据集：由若干数据（通常用n维属性向量表示）和它们相对应的类标号组成。训练样本：训练数据集中的单个数据及其类标号。从训练数据集“学习”相关知识来构造分类模型。分类模型可能会以分类规则、决策树或数学公式等形式呈现出来。第二步——使用模型对未知类别的数据进行分类（分配类别标号）。8第一步——建立模型训练数据集NAMERANKYEARSTENUREDMikeAssistantProf3noMaryAssistantProf7yesBillProfessor2yesJimAssociateProf7yesDaveAssistantProf6noAnneAssociateProf3no分类模型IFrank=‘professor’ORyears6THENtenured=‘yes’分类规则9第二步——使用模型分类规则测试数据集NAMERANKYEARSTENUREDTomAssistantProf2noMerlisaAssociateProf7noGeorgeProfessor5yesJosephAssistantProf7yes未知数据(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分类的评价标准精确度（正确率）：表示测试集中被正确分类的数据所占的比例。例如：在文字识别中，经常统计识别正确率，以此来表示识别系统的性能。NTPAccuracym1jj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类的期望信息为：))((log)(),...,,(2121jmjjmcPcPnnnInfo.,...,2,1,/)(mjtotalncPjj32ID3算法计算属性Af划分数据集X所得的熵：假设Af有q个不同取值，可按q的不同取值将X划分为q个不同的子集{X1,X2,…,Xs,…,Xq}；假设ns表示Xs中的样本数量，njs表示Xs中属于类别cj的样本数量，则由属性Af划分数据集X的熵为：其中：),...,,()(2111msssqsmssfnnnInfototalnnAE。的数据样本所占的比例中类别为表示在子集且，j121/)(log),...,(CXnnpppnnInfossjsjsmjjsjsmss33ID3算法计算属性Af划分数据集时的信息增益：属性的信息增益值越大，表示它的区分度就越高，使用该属性进行分类的效果就越好。ID3算法是通过选择具有最高信息增益的属性作为数据集的划分，从而可创建决策树中的一个结点，根据该属性的不同取值可形成该结点的不同分枝。再对各分枝中的数据子集进行递归划分，直至形成叶结点或者某分枝上的所有数据不属于同一类别，但又没有剩余的属性可以进一步划分为止。)(),...,,()(21fmfAEnnnInfoAGain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.