第六章2 数据挖掘 计算

•决策树(DecisionTree)一种描述概念空间的有效的归纳推理办法。基于决策树的学习方法可以进行不相关的多概念学习，具有简单快捷的优势，已经在各个领域取得广泛应用。•决策树学习是以实例为基础的归纳学习。•从一类无序、无规则的事物（概念）中推理出决策树表示的分类规则。•概念分类学习算法：来源于–Hunt,Marin和Stone于1966年研制的CLS学习系统，用于学习单个概念。–1979年,J.R.Quinlan给出ID3算法，并在1983年和1986年对ID3进行了总结和简化，使其成为决策树学习算法的典型。–Schlimmer和Fisher于1986年对ID3进行改造，在每个可能的决策树节点创建缓冲区，使决策树可以递增式生成，得到ID4算法。–1988年，Utgoff在ID4基础上提出了ID5学习算法，进一步提高了效率。–1993年，Quinlan进一步发展了ID3算法，改进成C4.5算法。–另一类决策树算法为CART，与C4.5不同的是，CART的决策树由二元逻辑问题生成，每个树节点只有两个分枝，分别包括学习实例的正例与反例。•其基本思想是以信息熵为度量构造一棵熵值下降最快的树，到叶子节点处的熵值为零，此时每个叶节点中的实例都属于同一类。•决策树学习采用的是自顶向下的递归方法。•决策树的每一层节点依照某一属性值向下分为子节点，待分类的实例在每一节点处与该节点相关的属性值进行比较，根据不同的比较结果向相应的子节点扩展，这一过程在到达决策树的叶节点时结束，此时得到结论。•从根节点到叶节点的每一条路经都对应着一条合理的规则，规则间各个部分（各个层的条件）的关系是合取关系。整个决策树就对应着一组析取的规则。•决策树学习算法的最大优点是，它可以自学习。在学习的过程中，不需要使用者了解过多背景知识，只需要对训练例子进行较好的标注，就能够进行学习。如果在应用中发现不符合规则的实例，程序会询问用户该实例的正确分类，从而生成新的分枝和叶子，并添加到树中。•树是由节点和分枝组成的层次数据结构。节点用于存贮信息或知识，分枝用于连接各个节点。树是图的一个特例，图是更一般的数学结构，如贝叶斯网络。•决策树是描述分类过程的一种数据结构，从上端的根节点开始，各种分类原则被引用进来，并依这些分类原则将根节点的数据集划分为子集，这一划分过程直到某种约束条件满足而结束。根结点个子大可能是松鼠可能是老鼠可能是大象在水里会吱吱叫鼻子长脖子长个子小不会吱吱叫鼻子短脖子短可能是长颈鹿在陆地上可能是犀牛可能是河马•可以看到，一个决策树的内部结点包含学习的实例，每层分枝代表了实例的一个属性的可能取值，叶节点是最终划分成的类。如果判定是二元的，那么构造的将是一棵二叉树，在树中每回答一个问题就降到树的下一层，这类树一般称为CART（ClassificationAndRegressionTree）。•判定结构可以机械的转变成产生式规则。可以通过对结构进行广度优先搜索，并在每个节点生成“IF…THEN”规则来实现。如图6-13的决策树可以转换成下规则：IF“个子大”THENIF“脖子短”THENIF“鼻子长”THEN可能是大象形式化表示成可能是大象鼻子长脖子短个子大•构造一棵决策树要解决四个问题：–收集待分类的数据，这些数据的所有属性应该是完全标注的。–设计分类原则，即数据的哪些属性可以被用来分类，以及如何将该属性量化。–分类原则的选择，即在众多分类准则中，每一步选择哪一准则使最终的树更令人满意。–设计分类停止条件，实际应用中数据的属性很多，真正有分类意义的属性往往是有限几个，因此在必要的时候应该停止数据集分裂：•该节点包含的数据太少不足以分裂，•继续分裂数据集对树生成的目标(例如ID3中的熵下降准则)没有贡献，•树的深度过大不宜再分。•通用的决策树分裂目标是整棵树的熵总量最小，每一步分裂时，选择使熵减小最大的准则，这种方案使最具有分类潜力的准则最先被提取出来•证据由属性值对表示–证据由固定的的属性和其值表示，如属性（温度），值（热）最简单的学习情况时每个属性拥有少量的不相关的值。•目标函数有离散输出值–决策树分配一个二值的树，很容易扩展成为多于两个的输出值。•需要不相关的描述–决策树原则上是表述不相关的表示•容忍训练数据的错误–对训练样本和表述样本的属性值的错误都有较强的鲁棒性。•训练数据可以缺少值–可以采用缺少属性值的样本学习。（不是所有样本都有）基于决策树的概念表示•决策树是一种树型结构，其中每个内部结点表示在一个属性上的测试，每个分支代表一个测试输出，每个叶结点代表一种类别。如，白化体动物的8个样本集合：事例动物种类身体颜色眼睛颜色白化体1兔棕黑负2兔白红正3兔灰红负4兔白红正5象白黑负6象白红正7象灰红负8象灰黑负ID3算法得出的决策树为：身体的颜色眼睛的颜色棕灰白+红黑CLS算法得出的决策树为：动物种类兔象身体的颜色眼睛的颜色棕灰白+红黑身体的颜色眼睛的颜色棕灰白+红黑2.决策树的学习算法•根据给定的事例集合，构建能正确反映出样本集合全部性质的决策树。•学习算法的评价标准，需兼顾以下内容：通用性——是否能正确反映出母集合的全部性质。可理解性——分类标准和标准是否易于理解。成本——生成本决策树的代价及性能比。根据经验的标准选择分类属性•HUNT等人提出的CLS算法，从人类直觉出发，将样本集合的众多属性逐一展开。其步骤如下：–1)产生根节点T，T包含所有的训练样本；–2)如果T中的所有样本都是正例，则产生一个标有“Yes”的节点作为T的子节点，并结束；–3)如果T中的所有样本都是反例，则产生一个标有“No”的节点作为T的子节点，并结束；根据经验的标准选择分类属性–4)选择一个属性A，根据该属性的不同取值v1,v2,…,vn将T中的训练集划分为n个子集，并根据这n个子集建立T的n个子节点：T1,T2,…,Tn，并分别以A=vi作为从T到Ti的分支符号；–5)以每个子节点Ti为根建立新的子树。•该算法的缺点是抗干扰性差，噪音数据将使所构建的决策树难以反应数据的内在规律；易受无关属性的干扰；受属性选择顺序的影响。根据信息量标准选择分类属性•ID3对CLS的改进主要体现在两方面：①增加了窗口技术；②使用信息增量的方法来选择节点上的测试属性。•采用训练实例的子集(即，可选择窗口)，通过属性，使用熵概念，来形成决策树。实质是构造一株熵值下降平均最快的判定树。信息熵的定义•香农定义信息熵为，表征了信源整体的统计特征的一个量。即总体的平均不确定性的量度。对某一特定的信源，其信息熵只有一个，因统计特性不同，其熵也不同。•信息熵表征了变量X的随机性。如信息熵大，表明X随机性大；而信息熵小，变量X的随机性就小。因此，熵反映了变量的随机性，也是表征随机变量统计特性的一个特征参数。例如，•如两场足球赛，其中一场，双方势均力敌；而另一场双方实力悬殊很大。当然,人们希望看第一场，因为胜负难卜，一旦赛完，人们获得信息量大。样本集的信息熵•设样本数据集为：X=[x1,x2,…,xn]记X的两个训练子集P+X和P-X分别为正例集和反例集，其中P+和P-分别为两个集合的概率，则样本空间的信息熵为：PPPPH220loglog样本集属性F的信息熵•假设样本集X有属性F，其属性值集合为{v1,v2,…,vn}，它将X划分为n个子集。假设第i个子集中包含Ni+个正例，Ni-个反例，则该子集的信息熵为：iiiiiivFNNNNNNHi2logiiiiiiNNNNNN2log样本集属性F的信息熵•因此，针对样本集的属性F，其各个取值的信息熵为(其pi为F=vi的概率，N为样本总数)：ivFniiFHpH1niiiiiiiiiNNNNNNNNN122loglog1iiiiiiniiiNNNNNNNNN21logiiiiiiNNNNNN2log•因此，以属性F为根节点的样本集合信息增量是：•由于样本集的信息熵H0是不可改变的，所以当属性F的信息熵取HF最小时，获得的信息增量最大。即选择使HF最小的属性F，做为决策树的分叉节点。FFHHgain0决策树分类节点的选取例如，白化体样本集的分类•根据具体的样本集合，计算其在各属性下的信息熵：象种兔种种HHH848443log341log142log242log2812222906.0灰体白体棕体体HHHH83848130log033log341log143log310log011log181222222406.0红眼黑眼眼HHH858352log253log330log033log3812222607.0•从上述计算中发现，因此选身体的颜色这个属性来进行分类，其信息增量为最大。•由于身体颜色这个属性中，仍有分枝存在正负例混杂的情况，需要对其继续进行分类。种眼体HHH•分别计算四个身体颜色为白的分枝下，种类和眼睛颜色属性的信息熵：象种兔种种HHH424221log121log120log022log24122225.0黑眼红眼眼HHH414310log011log130log033log34122220•因此，作为下一次分类的属性，就选择眼睛的颜色了。而且由于它的信息熵为0，表示没有必要再进行分类了。•最后得到的决策树如图所示。身体的颜色眼睛的颜色棕灰白+红黑•对于ID3，其谓词表示为身体的颜色(x,白)眼睛的颜色(x,红)白化体(x)•对于CLS，其谓词表示为{动物种类(x,兔)动物种类(x,象)}身体的颜色(x,白)眼睛的颜色(x,红)白化体(x)2.3谓词逻辑法从决策树向谓词表示的变换•上述的决策树中将各属性的获得代价视为均一的，但实际可能相差很远。如身体的各项检查，代价差别很大。•在样本数据属性值不完整，或包含有噪声情况下，应如何建立决策树。•为了得到完全正确的分类树，会产生训练数据的“过度”现象。为了解决这一类的问题，可采用剪枝的方法。4.决策树学习的发展课题习题1：实例序号颜色体形毛型类别1黑大卷毛危险2棕大光滑危险3棕中卷毛不危险4黑小卷毛不危险5棕中光滑危险6黑大光滑危险7棕小卷毛危险8棕小光滑不危险9棕大卷毛危险10黑中卷毛不危险11黑中光滑不危险12黑小光滑不危险计算样本分别按三种属性分类的后验熵918.064log462log264log462log21211261262222黑棕颜色HHH541.041log143log343log341log11211241241242222小中大体形HHHH163log363log363log363log31211261262222光滑卷毛毛型HHH由此可见，应选“体形”为第一次分类的属性毛型颜色体形HHH由于“体形”不能完全分类，因此在剩下的8个样本中，分“中”和“小”再按“颜色”和“毛形”属性分别计算其第二次分类的后验熵5.021log121log141424222黑棕颜色HHH5.021log121log141424222光滑卷毛毛型HHH体形为“中”的：毛型颜色HH可任选其中一种属性5.021log121log141424222黑棕颜色HHH5.021log121log141424222光滑卷毛毛型HHH体形为“小”的：毛型颜色HH也可任选其中一种属性作为第二次分类标准最后，得到的决策树如下图示体形+颜色颜色大中小+毛型+毛型黑棕黑棕+-+-卷毛光滑卷毛光滑习题2：设样本集合如下所示，其中A、B、C是F的属性，试根据信息增