(7.2.1)--7.2决策树.pdf
第第7章章 分类分类目录目录 CONTENTS2 7.17.27.37.4分类概述分类概述决策树决策树朴素贝叶斯分类朴素贝叶斯分类惰性学习法惰性学习法7.57.6神经网络神经网络分类模型的评估分类模型的评估Chapter 7.2决策树决策树决策树基本概念：决策树基本概念：决策树算法的基础是二叉树，但不是所有的决策树都是二叉树，还有可能是多叉树，如图所示。4 7.2 决策树（1）构造决策树决策树构造过程如下。输入数据，主要包括训练集的特征和类标号。选取一个属性作为根节点的分裂属性进行分裂。对于分裂的每个分支，如果已经属于同一类就不再分了，如果不是同一类，依次选取不同的特征作为分裂属性进行分裂，同时删除已经选过的分列属性。不断的重复，直到到达叶子节点，也就是决策树的最后一层，这时这个节点下的数据都是一类了。最后得到每个叶子节点对应的类标签以及到达这个叶子节点的路径。（2）决策树的预测得到由训练数据构造的决策树以后就可以进行预测了，当待预测的数据输入决策树的时候，根据分裂属性以及分裂规则进行分裂，最后即可确定所属的类别。5 7.2 决策树决策树算法过程决策树算法过程设A是分裂属性，根据训练数据，A具有n个不同值a1,a2,an，选取A作为分裂属性进行分裂时有如下三种情况。A是离散值：对A的每个值aj创建一个分支，分区Dj是D中A上取值为aj的类标号元组的子集，如图7-3（a）所示。A是连续的：产生两个分支，分别对应于Asplit_point和Asplit_point，其中split_point是分裂点，数据集D被划分为两个分区，D1包含D中Asplit_point的类标号组成的子集，而D2包括其他元组，如图7-3（b）所示。A是离散值且必须产生二叉树（由属性选择度量或所使用的算法指出）：结点的判定条件为“ASA?”，其中SA是A的分裂子集。根据A的值产生两个分支，左分支标记为yes，使得D1对应于D中满足判定条件的类标记元组的子集；右分支标记为no，使得D2对应于D中不满足判定条件的类标记元组的子集，如图7-3（c）所示。6 7.2 决策树Aa1a2anAAsplit_pointAsplit_pointASA?yesno(a)(b)(c)。图7-3 属性分裂的三种情况属性分裂的三种情况属性分裂的三种情况ID3算法的构建方法和决策树的构建基本是一致的，不同的是分裂节点的特征选择的标准。该算法在分裂节点处将信息增益作为分裂准则进行特征选择，递归的构建决策树。ID3算法的步骤如下：输入数据，主要包括训练集的特征和类标号。如果所有实例都属于一个类别，则决策树是一个单结点树，否则执行。计算训练数据中每个特征的信息增益。从根节点开始选择最大信息增益的特征进行分裂。依次类推，从上向下构建决策树，每次选择具有最大信息增益的特征进行分裂，选过的特征后面就不能继续进行选择使用了。不断的构建决策树，至没有特征可以选择或者分裂后的所有元组属于同一类别时候停止构建。决策树构建完成，进行预测。7 7.2 决策树ID3例例7.4 使用使用ID3算法进行分类预测算法进行分类预测表7-2和表7-3为训练数据和测试数据，其中“患病与否”是类标记，使用ID3算法构建决策树然后进行分类预测。8 7.2 决策树ID3表7-2 某疾病患病情况的训练数据ID年年龄龄吸烟史吸烟史有无家族有无家族病史病史体重范围体重范围患病与否患病与否123无无较低否225无无中否3270-5年无中否4300-5年有低是539无无较低否641无无低否743无无高否8455年以上有高是946无有高是1047无有高是1162无有较高是1263无有高是13665年以上无高是14665年以上无较高是15680-5年无中否表7-3 某疾病患病情况的测试数据ID年年龄龄吸烟史吸烟史有无家有无家族病史族病史体重范围体重范围患病与否患病与否125无无较低？242无无高？3675年以上无较高？解：连续型数据的离散化。ID3算法不能直接处理连续型数据，只有通过离散化将连续型数据转化成离散型数据再进行处理。此例采用等宽分箱法对连续型特征“年龄”离散化：设定区域范围（设箱子数为3，箱子宽度为（68-23）/3=15），分箱结果为：箱1：23 25 27 30 箱2：39 41 43 45 46 47箱3：62 63 66 66 689 7.2 决策树ID3年龄23 25 27 30 39 41 43 45 46 47 62 63 66 66 68离散化23 25 27 30 39 41 43 45 46 4762 63 66 66 68青年老年中年图7-4 对特征“年龄”分箱离散后训练数据集如表7-4所示。10 7.2 决策树ID3表7-4 某疾病患病情况的训练数据（离散化后）ID年龄年龄吸烟史吸烟史有无家族病史有无家族病史体重范围体重范围患病与否患病与否1青年无无较低否2青年无无中否3青年0-5年无中否4青年0-5年有低是5中年无无较低否6中年无无低否7中年无无高否8中年5年以上有高是9中年无有高是10中年无有高是11老年无有较高是12老年无有高是13老年5年以上无高是14老年5年以上无较高是15老年0-5年无中否根据训练数据构造ID3算法的决策树，其中Z代表训练集，A、B、C、D分别代表特征“年龄”、“吸烟史”、“有无家族病史”、“体重范围”，按照每个特征计算其分裂的信息增益。?X Gy?=815log?815715log?715=0.997?X Gy?|?=415?34log?3414log?14?+615?36log?3636log?36?+515?45log?4515log?15?=0.857?X Gy?|?=915?59log?5949log?49?+315?23log?2313log?13?+315?33log?33?=0.77811 7.2 决策树ID3根据训练数据构造ID3算法的决策树，其中Z代表训练集，A、B、C、D分别代表特征“年龄”、“吸烟史”、“有无家族病史”、“体重范围”，按照每个特征计算其分裂的信息增益。?X Gy?|?=915?79log?7929log?29?+615?66log?66?=0.459?X Gy?|?=215?22log?22?+215?12log?1212log?12?+315?33log?33?+615?56log?5616log?16?+215?22log?22?=0.39312 7.2 决策树ID3根据训练数据构造ID3算法的决策树，其中Z代表训练集，A、B、C、D分别代表特征“年龄”、“吸烟史”、“有无家族病史”、“体重范围”，按照每个特征计算其分裂的信息增益。?|?=?X Gy?X Gy?|?=0.997 0.857=0.140?|?=?X Gy?X Gy?|?=0.997 0.778=0.219?|?=?X Gy?X Gy?|?=0.997 0.459=0.538?|?=?X Gy?X Gy?|?=0.997 0.393=0.604选择信息增益最大特征“体重范围”作为根结点的分裂属性，将训练集Z划分为5个子集?、?、?、?和?，对应的“体重范围”取值分别为“低”、“较低”、“中”、“较高”、“高”。由于?、?和?只有一类数据，所以它们各自成为一个叶结点，三个结点的类标签分别为“否”、“否”、“是”。13 7.2 决策树ID314 7.2 决策树ID3ID年龄年龄吸烟史吸烟史有无家族病史有无家族病史体重范围体重范围患病与否患病与否4青年0-5年有低是6中年无无低否表 Z1训练数据集ID年龄年龄吸烟史吸烟史有无家族病史有无家族病史体重范围体重范围患病与否患病与否2青年无无中否3青年0-5年无中否15老年0-5年无中否表 Z3训练数据集ID年龄年龄吸烟史吸烟史有无家族病史有无家族病史体重范围体重范围患病与否患病与否1青年无无较低否5中年无无较低否表 Z2训练数据集ID年龄年龄吸烟史吸烟史有无家族病史有无家族病史体重范围体重范围患病与否患病与否11老年无有较高是14老年5年以上无较高是ID年龄年龄吸烟史吸烟史有无家族病史有无家族病史体重范围体重范围患病与否患病与否7中年无无高否8中年5年以上有高是9中年无有高是10中年无有高是12老年无有高是13老年5年以上无高是表 Z5训练数据集表 Z4训练数据集对于?继续进行分裂，选择剩余特征中信息增益最大的作为分裂属性。?X Gy?=12log?1212log?12=1?X Gy?|?=12?11log?11?+12?11log?11?=0?X Gy?|?=12?11log?11?+12?11log?11?=0?X Gy?|?=12?11log?11?+12?11log?11?=015 7.2 决策树ID3对于?继续进行分裂，选择剩余特征中信息增益最大的作为分裂属性。?|?=?X Gy?X Gy?|?=1 0=1?|?=?X Gy?X Gy?|?=1 0=1?|?=?X Gy?X Gy?|?=1 0=1选择信息增益最大特征作为?结点的分裂属性，由于三个属性的信息增益相同，随机挑选一个作为分裂属性，此处选取“有无家族病史”作为分裂属性，它将数据集?分成2个子集?和?，对应的“有无家族病史”的取值分别为“有”和“无”，在这2个子集中的数据都各自属于同一类，于是就不需要再继续分裂。16 7.2 决策树ID317 7.2 决策树ID3ID年龄年龄吸烟史吸烟史有无家族病史有无家族病史体重范围体重范围患病与否患病与否4青年0-5年有低是ID年龄年龄吸烟史吸烟史有无家族病史有无家族病史体重范围体重范围患病与否患病与否6中年无无低否表 Z21训练数据集表 Z22训练数据集对于?继续进行分裂，选择剩余特征中信息增益最大的作为分裂属性。?X Gy?=16log?1656log?56=0.650?X Gy?|?=46?14log?1434log?34?+26?22log?22?=0.541?X Gy?|?=46?34log?3414log?14?+26?22log?22?=0.541?X Gy?|?=46?44log?44?+26?12log?1212log?12?=0.33318 7.2 决策树ID3对于?继续进行分裂，选择剩余特征中信息增益最大的作为分裂属性。?|?=?X Gy?X Gy?|?=0.650 0.541=0.109?|?=?X Gy?X Gy?|?=0.650 0.541=0.109?|?=?X Gy?X Gy?|?=0.650 0.333=0.317选择信息增益最大特征“有无家族病史”作为?结点的分裂属性，将数据集?分成2个子集?和?，对应的“有无家族病史”的取值分别为“有”和“无”，“有”对应的?中的数据都属于同一类，不需要再继续分裂，“无”对应的?中的数据属于不同类，需要对其进行分裂。19 7.2 决策树ID320 7.2 决策树ID3ID年龄年龄吸烟史吸烟史有无家族病史有无家族病史体重范围体重范围患病与否患病与否8中年5年以上有高是9中年无有高是10中年无有高是12老年无有高是ID年龄年龄吸烟史吸烟史有无家族病史有无家族病史体重范围体重范围患病与否患病与否7中年无无高否13老年5年以上无高是表 Z52训练数据集表 Z51训练数据集对于?继续进行分裂，选择剩余特征中信息增益最大的作为分裂属性。?X Gy?=12log?1212log?12=1?X Gy?|?=12?11log?11?+12?11log?11?=0?X Gy?|?=12?11log?11?+12?11log?11?=0?|?=?X Gy?X Gy?|?=1 0=1?|?=?X Gy?X Gy?|?=1 0=1由于两个属性的信息增益相同，随机挑选一个作为分裂属性，此处选取“吸烟史”作为?结点的分裂属性，将数据集?分成2个子集?和?，对应的“吸烟史”的取值分别为“无”和“5年以上”，在这两个子集中的数据都各自属于同一类，于是就不需要再继续分裂，决策树构造完毕。21 7.2 决策树ID322 7.2 决策树ID3ID年龄年龄吸烟史吸烟史有无家族病史有无家族病史体重范围体重范围患病与否患病与否7中年无无高否ID年龄年龄吸烟史吸烟史有无家族病史有无家族病史体重范围体重范围患病与否患病与否13老年5年以上无高是表 Z521训练数据集表 Z522训练数据集利用ID3算法构建的决策树如图7-5所示。23 7.2 决策树ID3体重范围是有无有无是否否否是有无家族病史低较低中较高高有无家族病史吸烟史无5年以上否是图7-5 ID3算法构造的决策树根据构建的决策树，可以提取分类规则如下。IF“体重范围”=“低”AND“有无家族病史”=“有”THEN 患病IF“体重范围”=“低”AND“有无家族病史”=“无”THEN 没有患病IF“体重范围”=“较低”THEN 没有患病IF“体重范围”=“中”THEN 没有患病IF“体重范围”=“较高”THEN 患病IF“体重范围”=“高”AND“有无家族病史”=“有”THEN 患病IF“体重范围”=“高”AND“有无家族病史”=“无”AND“吸烟史”=“无”THEN 没有患病IF“体重范围”=“高”AND“有无家族病史”=“无”AND“吸烟史”=“5年以上”THEN 患病24 7.2 决策树ID31.倾向于选择数值较多的特征 例如考虑唯一标识符的属性product_ID，因其每个值只有一个元组，在product_ID的划分会产生元组总数个分区，且每个分区都是纯的，即该分区的元组属于同一个类，基于该划分对数据集D分类的Info(D|product_ID)=0，则g(D|product_ID)最大，选择product_ID作为分裂属性不是一个好的策略，属性取值最多的属性并不一定最优。再如例7.4中使用ID3算法构造的决策树第一个分裂属性选择的是“体重范围”，很大程度是因为其数值较多，但在实际情况中，“体重范围”不一定是决定性属性。2.对于每个属性均为离散值属性，如果是连续值属性需先离散化25 7.2 决策树ID3算法的问题算法的问题C4.5算法在构建决策树的时候，分类属性选择的是具有最大信息增益率的特征，这样通过分裂属性的信息，一定程度上避免了由于特征值太分散而造成的误差，其过程如下：如果所有实例都属于一个类别，则决策树是一个单结点树，否则执行步骤。从根节点开始选择最大信息增益率的特征进行分裂。依次类推，从上向下构建决策树，每次选择具有最大信息增益率的特征进行分裂，选过的特征后面就不能继续进行选择使用了。重复步骤，直至没有特征可以选择或者分裂后的所有元组属于同一类别时候停止构建。决策树构建完成，进行预测。26 7.2 决策树C4.5算法过程算法过程 根据连续属性值进行排序，用不同的值对数据集进行动态划分，把数据集分为两部分，一部分大于某值，一部分小于某值，然后根据划分进行信息增益计算，最大的那个值作为最后的划分。假设属性A是连续值，必须确定A的“最佳”分裂点，其中分裂点是A上的阈值。将A的值按递增序排序，每对相邻值的中点被看做可能的分裂点。当A具有n个值时，需要计算n-1个可能的划分。对于A的每个可能分裂点，计算信息增益，具有信息增益最大的点选做A的分裂点split_point，产生两个分支，分别对应于Asplit_point和Asplit_point，数据集D被划分为两个分区，D1包含D中Asplit_point的类标号组成的子集，而D2包括Asplit_point元组。27 7.2 决策树C4.5处理连续值属性处理连续值属性例例7.5 使用使用C4.5算法进行分类预测算法进行分类预测 表7-2和表7-3为训练数据和测试数据，其中“患病与否”是类标记，使用C4.5算法构建决策树然后进行分类预测。解：首先计算按照每个特征进行分裂的信息增益率。i.特征中“年龄”为连续型属性，C4.5算法可以解决ID3算法无法处理连续属性的缺点。首先将特征“年龄”的值进行升序排序，用每对相邻值的中值对数据集进行动态划分（一部分大于中值，另一部分小于等于中值），此例中“年龄”有15个值，有14个可能的分裂点，分别为24,26,28.5,34.5,40,42,44,45.5,46.5,54.5,62.5,64.5,66,67，其中中值为66的相邻值都是66，该中值划分无意义，可以忽略。根据不同的划分进行信息增益计算，能够使信息增益最大的划分即为最后的划分策略。下面给出其中一个可能的分裂点44的信息增益的计算式，其他可能分裂点的信息增益计算结果如表7-5所示。28 7.2 决策树29 7.2 决策树划分策略划分策略?|?划分策略划分策略?|?a|0240.077a|045.50.288a|0260.164a|047.50.186a|028.50.262a|054.50.109a|034.50.088a|062.50.052a|0400.169a|064.50.013a|0420.278a|0670.077a|0440.431表7-5 不同划分策略的信息增益值30 7.2 决策树ii.计算各特征的分裂信息。?X Gy?=?=1X?|?|log?|?|?=715log?715815log?815=0.997?X Gy?=?=1X?|?|log?|?|?=915log?915315log?315315log?315=1.371?X Gy?=?=1X?|?|log?|?|?=615log?615915log?915=0.971?X Gy?=?=1X?|?|log?|?|?=215log?215215log?215315log?315615log?615215log?215=2.15631 7.2 决策树iii.计算各特征的信息增益率。?,?=?|?X Gy?=?X Gy?X Gy?|?X Gy?=0.997 0.5660.997=0.432?,?=?|?X Gy?=?X Gy?X Gy?|?X Gy?=0.997 0.7781.371=0.160?,?=?|?X Gy?=?X Gy?X Gy?|?X Gy?=0.997 0.4590.971=0.554?,?=?|?X Gy?=?X Gy?X Gy?|?X Gy?=0.997 0.3932.156=0.280选择信息增益率最大的特征“有无家族病史”作为根结点的分类属性，将训练集Z划分为2个子集?和?，对应的“有无家族病史”的取值分别为“有”和“无”，在?子集中的数据都属于同一类，不需要再继续分裂，在?子集中的数据属于不同类，需要再继续分裂。32 7.2 决策树ID年龄年龄吸烟史吸烟史有无家族有无家族病史病史体重范体重范围围患病与患病与否否123无无较低否225无无中否3270-5年无中否439无无较低否541无无低否643无无高否7665年以上无高是8665年以上无较高是9680-5年无中否表 某疾病患病情况的训练数据集?ID年年龄龄吸烟史吸烟史有无家族有无家族病史病史体重范围体重范围患病与否患病与否4300-5年有低是8455年以上有高是946无有高是1047无有高是1162无有较高是1263无有高是表 某疾病患病情况的训练数据集Z133 7.2 决策树根据?计算其他属性的分裂信息：?X Gy?=?=1X?|?|log?|?|?=69log?6939log?39=0.918?X Gy?=?=1X?|?|log?|?|?=59log?5929log?2929log?29=1.436?X Gy?=?=1X?|?|log?|?|?=29log?2919log?1939log?3929log?2919log?19=2.197对数据集?进行分裂34 7.2 决策树计算各属性的信息增益率?,?=?|?X Gy?=?X Gy?X Gy?|?X Gy?=0.764 0.3060.918=0.499?,?=?|?X Gy?=?X Gy?X Gy?|?X Gy?=0.764 01.436=0.532?,?=?|?X Gy?=?X Gy?X Gy?|?X Gy?=0.764 0.2222.197=0.247 通过计算可知属性“吸烟史”的信息增益率最大，选择“吸烟史”属性继续进行分裂，将训练集?划分为3个子集?、?和?，对应的“吸烟史”的取值分别为“无”、“0-5年”以及“5年以上”，在这3个子集中的数据都各自属于同一类，所以不再分裂，决策树构建完毕。35 7.2 决策树ID年龄年龄吸烟史吸烟史有无家族病史有无家族病史体重范围体重范围患病与否患病与否123无无较低否225无无中否439无无较低否541无无低否643无无高否ID年龄年龄吸烟史吸烟史有无家族病史有无家族病史体重范围体重范围患病与否患病与否3270-5年无中否9680-5年无中否ID年龄年龄吸烟史吸烟史有无家族病史有无家族病史体重范围体重范围患病与否患病与否7665年以上无高是8665年以上无较高是表 某疾病患病情况的训练数据集Z21表 某疾病患病情况的训练数据集Z22表 某疾病患病情况的训练数据集Z2336 7.2 决策树5年以上是0-5年否否无有无家族病史无吸烟史是有图7-5 构建的C4.5决策树37 7.2 决策树根据构建的决策树，可以提取分类规则如下。IF“有无家族病史”=“有”THEN 患病IF“有无家族病史”=“无”AND“吸烟史”=“无”THEN 没有患病IF“有无家族病史”=“无”AND“吸烟史”=“0-5年”THEN 没有患病IF“有无家族病史”=“无”AND“吸烟史”=“5年以上”THEN患病 样本问题（1）样本里的噪声数据干扰过大，达到模型过分记住了噪声特征，反而忽略了真实的输入输出间的关系；（2）样本抽取错误，包括（但不限于）样本数量太少，抽样方法错误，抽样是没有足够正确考虑业务场景或业务特点等，导致抽出的样本数据不能有效足够代表业务逻辑或业务场景；（3）建模时使用了样本中太多无关的输入变量。构建决策树的方法问题在决策树模型构建中使用的算法对决策树的生长没有合理的限制和修剪，决策树的自由生长有可能使得每个叶子结点里只包含单纯的事件数据或非事件数据，这种决策树可以很好地拟合训练数据，但对于新的业务真实数据的效果却很差。38 7.2 决策树过过拟合的原因拟合的原因 样本问题合理、有效地抽样，用相对能够反映业务逻辑的训练数据构建决策树。构建决策树的方法问题主要方法是剪枝，即提前停止树的增长或者对已经生成的树按照一定的规则进行剪枝。39 7.2 决策树解决方法解决方法 先剪枝先剪枝就是在构建决策树的过程中进行剪枝，当决策树高度达到最大高度、或达到某个结点的实例具有相同的特征向量、或达到某个结点的实例个数阈值、或达到信息增益阈值等条件即停止决策树的生长。以ID3算法构建决策树为例，就是当信息增益达到预先设定的阈值时候就不再进行分裂，直接将这个结点作为叶子结点，取叶子结点中出现频率最多的类别作为此叶子结点的类标签。后剪枝后剪枝就是决策树建好之后，再对整个树进行剪枝操作，具体方法就是计算每个内部的结点剪枝前和剪枝后的损失函数，按照最小化损失函数的原则进行剪枝即用叶子结点代替该分支结点，该叶子结点的类标号用该结点子树中最频繁的类标记，或者保留此内部结点。40 7.2 决策树决策树的剪枝决策树的剪枝THANKS FOR YOUR ATTENTION感谢指导！感谢指导！
