数据挖掘决策树算法ID3和C45教学课件

决策树的建立

DecisionTree数据挖掘1数据挖掘1学习数据挖掘的工具-wekaweka是用Java语言编写的完整的软件资源Explorer是weka的主要图形用户界面weka存储数据的原始方式是ARFF或CSV文件格式ARFF文件是由一组实例组成，并且每组实例的属性值由逗号分开。（属性的类别）2学习数据挖掘的工具-wekaweka是用Java语言编写的完天气数据 outlook temperature humidity windy play1 sunny hot high FALSE no2 sunny hot high TRUE no3 overcast hot high FALSE yes4 rainy mild high FALSE yes5 rainy cool normal FALSE yes6 rainy cool normal TRUE no7 overcast cool normal TRUE yes8 sunny mild high FALSE no9 sunny cool normal FALSE yes10 rainy mild normal FALSE yes11 sunny mild normal TRUE yes12 overcast mild high TRUE yes13 overcast hot normal FALSE yes14 rainy mild high TRUE no3天气数据 outlook temperature humid我们希望从上面的实例中找出者若干条规则，使得能够对这些实例的类做出判断（理想情况下）（举例）ifoutlook=sunnyand=highthenplay=noifhumidity=normalthenplay=yes第二条规则错分了一个实例样本4我们希望从上面的实例中找出者若干条规则，使得能够对这些实例的决策节点：1.最上面的节点称为根节点，是整个决策树的开始。2.每个节点子节点的个数与决策树在用的算法有关。（二叉树、多叉树）分支：判断过程，要么是新的决策节点，要么是叶子树叶:树的结尾，每个叶子代表一个类别根节点叶子节点决策节点叶子节点叶子节点5根节点叶子节点决策节点叶子节点叶子节点5步骤：1.决策树的生成：由训练样本数据集（根据历史数据生成、有一定综合程度的用于数据分析处理的数据集）生成2.决策树的剪枝：采用新的样本数据集（测试数据集或者训练数据修剪集）检验决策树生成过程中产生的初步规则，将影响预测准确性的分支剪除。6步骤：6ID3决策树算法描述1.试探性地选择一个属性放置在根节点，并对该属性的每个值产生一个分支。2.分裂根节点上的数据集，并移到子女节点，产生一棵局部树。3.对该划分的信息增益进行计算。4.对其他属性重复该过程。5.每个用于划分的属性产生一棵局部树。6.根据局部树的信息增益值，选择一棵增益最大的属性的局部树。7.对选定的局部树的每个子女节点重复以上1-6步。8.这是一个递归过程。如果一个节点上的所有实例都具有相同的类，则停止局部树的生长。7ID3决策树算法描述1.试探性地选择一个属性放置在根节点，并选择属性作为根产生分支计算信息增益选择max增益数据进一步分裂？结束否是算法流程图8选择属性作为根产生分支计算信息增益选择max增益数据进一步分信息值（熵）、信息增益的概念熵：entropy（p1,p2,...,pn）=-p1logp1-p2logp2••••-pnlogpn使用负号是因为分数p1,p2,...,pn的对数值是负数，而熵是一个正数。熵是以位bit位单位的，公式里的p1,p2,...,pn他们的和为1。entropy(p,q,r)=entropy(p,q+r)+(q+r)*entropy(q/(q+r),r/(q+r))我们需要一种度量来表示节点的纯度，并需要这种度量告诉我们根据一个变量的属性值将一个不纯的节点上的数据划分到其子女后，纯度提高了多少。最为广泛使用的度量是信息值(熵)。（以天气数据为例）9信息值（熵）、信息增益的概念熵：9outlook属性的树桩yesyesnononoyesyesyesyesyesyesyesnonooutlooksunnyovercastrainy在叶子节点上的yes和no类的实例数量分别是[2,3]、[4,0]、[3,2]，因此，这些节点上的信息值分别是：info([2,3])=entropy(2/5,3/5)=0.971bitinfo([4,0])=entropy(1,0)=0bitinfo([3,2])=entropy(3/5,2/5)=0.971bit然后计算这些叶子节点的平均信息值，并考虑到达每个分支的实例数量：有5个实例到达第一和第三个分支；4个实例到达第二个分支：那么平均信息值info([2,3],[4,0],[3,2])=(5/14)*0.971+(4/14)*0+(5/14)*0.971=0.693bit在任何初始树创建之前，处于根节点的训练样本由9个yes和5个no组成，与之相对应的信息值：info([9,5])=0.940bit因此树桩所获得的信息增益为：gain(outlook)=info([9,5])-info([2,3],[4,0],[3,2])=0.940-0.693=0.247bit10outlook属性的树桩yesyesyesoutlooksutemperature、humidity、wind属性的树桩yesyesnonoyesyesyesyesnonoyesyesyesnotemperaturehotmildcool分别计算它们的信息增益为：gain(temperature)=0.029bityesyesyesnonononoyesyesyesyesyesyesnohumidityhighnormalyesyesyesyesyesyesnonoyesyesyesnononowindfalsetruegain(humidity)=0.152bitgain(wind)=0.048bit11temperature、humidity、wind属性的树桩将这些属性的信息增益的值进行比较，信息增益最大的属性节点将作为决策树的根节点。所以我们选择outlook属性作为根节点，它是唯一一个获得了全纯子节点，这就为超越其他所有属性赢得了相当大的优势。而湿度属性是第二个最佳选择，因为它产生了一个几乎是全纯且较大的子节点。根节点确定了，接着继续进行这种递归过程。下面是outlook属性值为sunny时的节点进一步分支的可能性：outlooksunnyhumiditynononoyesyeshighnormaloutlooksunnywindyesnonoyesnofalsetrueoutlooksunnytemperaturenonoyesnoyeshotmildcool他们的信息增益分别为：gain(temperature)=0.571bitgain(humidity)=0.971bitgain(wind)=0.493bit12将这些属性的信息增益的值进行比较，信息增益最大的属性节点将作因此选择湿度属性作为在这一个节点的分裂属性，在随之产生的子节点上并不需要进一步分裂，因为叶子节点都是全纯子节点，所以这个分支就结束了。继续应用这样的思想方法，将产生关于天气数据的决策树，如下图所示。理想的停止条件是所有叶子节点都是纯的，也就是当叶子节点包含的实例拥有相同的类别。然而，也许并不可能达到这种理想状态，因为当训练集里包含2个拥有相同属性值，但是属于不同类别的样本时，递归过程将不可能停止。所以停止条件应为当数据不能被进一步分裂时。outlooksunnyrainyovercasthumiditywindyesnoyesnoyesnormalhighfalsetrue天气数据的决策树13因此选择湿度属性作为在这一个节点的分裂属性，在随之产生的子节ID3算法的不足及改进当一些属性拥有的可能值得数量很大，从而使分支的路径增加，产生出很多子节点时，计算信息增益就会出现一个问题。用一个极端的例子来说明：当数据集的某个属性对于每一个实例存在一个不同属性值时，比如，一个标志码属性。 标志码outlook temperaturehumidity windy play a sunny hot high FALSE no b sunny hot high TRUE no c overcast hot high FALSE yes d rainy mild high FALSE yes e rainy cool normal FALSE yes f rainy cool normal TRUE no g overcast cool normal TRUE yes h sunny mild high FALSEno i sunny cool normal FALSE yes j rainy mild normal FALSE yes k sunny mild normal TRUE yes l overcast mild high TRUE yes m overcast hot normal FALSE yes n rainy mild high TRUE no14ID3算法的不足及改进当一些属性拥有的可能值得数量对标志码属性进行分裂而产生的树桩如下，这个属性值的类别所需的信息量是：info([0,1])+info([0,1])+info([1,0])+......+info([1,0])+info([0,1])=0bit标志码nonoyesnoyesanbcm···标志码属性的信息增益就是在根节点上的信息量即：gain(标志码)=info([9,5])=0.940bit它比在其他任何属性上获得的信息增益值大，毫无疑问标志码将被选为分裂属性，但是在标志码属性上的分支对预测未知实例的类别没有任何帮助，也没能够描述任何有关决策的结构。由此可见，采用度量信息增益的方法会倾向于选择拥有较多可能属性值的属性。为了弥补这一缺陷，一个称之为增益率(gainratio)的度量修正被广范的采用。15对标志码属性进行分裂而产生的树桩如下，这个属性值的类别所需的上例所有的计数值均为1，因此分裂信后的信息值是：info([1,…,1])=-1/14xlog(1/14)x14=logl4(3.807位) 分支越多，该值越大。 具有较高分支的属性，该固有的信息值较高。 增益率，由信息增益除以该固有信息值得到。 例：得到标志码的增益率为0.940/3.807=0.247再返回之前的天气数据的树桩：属性outlook将数据集分裂成3个子集，规模分别为5,4,5，因此不考虑子集中所包含的类别，产生一个内在的信息值：info([5,4,5])=1.577bit得到outlook属性的增益率为：(0.940-0.693)/1.577=0.157类似的可以计算出其他属性树桩的增益率：

temperature属性的增益率为：(0.940-0.911)/info(4,6,4)=0.019humidity属性的增益率为：(0.940-0.788)/info(7,7)=0.152wind属性的增益率为：(0.940-0.693)/1.577=0.049

16上例所有的计数值均为1，因此分裂信后的信息值是：16由此可以看出，在上述4个属性中outlook属性的结果依然排在首位，而humidity属性以一个更为接近的值排在第二位，因为它将数据集分裂成2个子集而不是3个。在这个例子中，标志码属性的增益率(0.247)任然是最高的，然而，它的优势已经大大降低了。ID3算法最初的定义是假设属性值是离散值，但在实际环境中，有很多属性是连续的，不能够用一个确定的标准来对其进行划分。C4.5使用下面的一系列处理过程来对连续的属性划分成离散的属性，进而达到能够建立决策树的目的。C4.5对ID3进行了一系列改进。这些改进包括处理数值属性、残缺值、后剪枝的方法。（将训练数据分为成长集和修剪集）17由此可以看出，在上述4个属性中outlook属性的结果依然排C4.5算法做出的改进(1)用信息增益率来选择属性(2)可以处理连续数值型属性在选择某节点上的分枝属性时，对于离散型描述属性，C4.5的处理方法与ID3相同，按照该属性本身的取值个数进行计算；对于某个连续性描述属性Ac，假设在某个结点上的数据集的样本数量为t，C4.5将作以下处理。1.将该结点上的所有数据样本按照连续型描述属性的具体数值，由小到大进行排序，得到属性值的取值序列{A1c，A2c，……Atc}。2.在取值序列中生成t-1个分割点。第i（0<i<t）个分割点的取值设置为Vi=（Aic+A（i+1）c）/2,它可以将该节点上的数据集划分为两个子集。3.从t-1个分割点中选择最佳分割点。对于每一个分割点划分数据集的方式，C4.5计算它的信息增益率，并且从中选择信息增益率最大的分割点来划分数据集。18C4.5算法做出的改进(1)用信息增益率来选择属性18(3)采用了一种后剪枝方法在后修剪过程中考虑两种完全不同的操作：子树置换和子树上升ALTpriceyesabcyesyesno4/57/81/2ALTyes12/15子树的置换yes19(3)采用了一种后剪枝方法ALTpriceyesabcyes子树的上升：ABC45123AC1'2'3'20子树的上升：ABC45123AC1'2'3'20为了避免树的高度无节制的增长，避免过度拟合数据，该方法使用训练样本集本身来估计剪枝前后的误差，从而决定是否真正剪枝。方法中使用的公式如下：其中N是实例的数量，f=E/N为观察到的误差率（其中E为N个实例中分类错误的个数），q为真实的误差率，c为置信度（C4.5算法的一个输入参数，默认值为0.25），z为对应于置信度c的标准差，其值可根据c的设定值通过查正态分布表得到。通过该公式即可计算出真实误差率q的一个置信度上限，用此上限为该节点误差率e做一个悲观的估计：通过判断剪枝前后e的大小，从而决定是否需要剪枝。（e变小，剪枝）21为了避免树的高度无节制的增长，避免过度拟合数据，该方法使用训(4)对于残缺值的处理在某些情况下，可供使用的数据可能缺少某些属性的值。假如〈x，c(x)〉是样本集S中的一个训练实例，但是其属性A的值A(x)未知。1.处理缺少属性值的一种策略是赋给它结点n所对应的训练实例中该属性的最常见值。2.另外一种更复杂的策略是为A的每个可能值赋予一个概率。例如，给定一个布尔属性A，如果结点n包含6个A=1和4个A=0的实例，那么A(x)=1的概率是0.6，而A(x)=0的概率是0.4。于是，实例x的60%被分配到A=1的分支，40%被分配到另一个分支，数值加权方案，这样做的目的是计算信息增益。另外，如果有第二个缺少值的属性必须被测试，这些样例可以在后继的树分支中被进一步细分。22(4)对于残缺值的处理22在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。C4.5只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时程序无法运行。C4.5算法的缺点23在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而

决策树的建立

DecisionTree数据挖掘24数据挖掘1学习数据挖掘的工具-wekaweka是用Java语言编写的完整的软件资源Explorer是weka的主要图形用户界面weka存储数据的原始方式是ARFF或CSV文件格式ARFF文件是由一组实例组成，并且每组实例的属性值由逗号分开。（属性的类别）25学习数据挖掘的工具-wekaweka是用Java语言编写的完天气数据 outlook temperature humidity windy play1 sunny hot high FALSE no2 sunny hot high TRUE no3 overcast hot high FALSE yes4 rainy mild high FALSE yes5 rainy cool normal FALSE yes6 rainy cool normal TRUE no7 overcast cool normal TRUE yes8 sunny mild high FALSE no9 sunny cool normal FALSE yes10 rainy mild normal FALSE yes11 sunny mild normal TRUE yes12 overcast mild high TRUE yes13 overcast hot normal FALSE yes14 rainy mild high TRUE no26天气数据 outlook temperature humid我们希望从上面的实例中找出者若干条规则，使得能够对这些实例的类做出判断（理想情况下）（举例）ifoutlook=sunnyand=highthenplay=noifhumidity=normalthenplay=yes第二条规则错分了一个实例样本27我们希望从上面的实例中找出者若干条规则，使得能够对这些实例的决策节点：1.最上面的节点称为根节点，是整个决策树的开始。2.每个节点子节点的个数与决策树在用的算法有关。（二叉树、多叉树）分支：判断过程，要么是新的决策节点，要么是叶子树叶:树的结尾，每个叶子代表一个类别根节点叶子节点决策节点叶子节点叶子节点28根节点叶子节点决策节点叶子节点叶子节点5步骤：1.决策树的生成：由训练样本数据集（根据历史数据生成、有一定综合程度的用于数据分析处理的数据集）生成2.决策树的剪枝：采用新的样本数据集（测试数据集或者训练数据修剪集）检验决策树生成过程中产生的初步规则，将影响预测准确性的分支剪除。29步骤：6ID3决策树算法描述1.试探性地选择一个属性放置在根节点，并对该属性的每个值产生一个分支。2.分裂根节点上的数据集，并移到子女节点，产生一棵局部树。3.对该划分的信息增益进行计算。4.对其他属性重复该过程。5.每个用于划分的属性产生一棵局部树。6.根据局部树的信息增益值，选择一棵增益最大的属性的局部树。7.对选定的局部树的每个子女节点重复以上1-6步。8.这是一个递归过程。如果一个节点上的所有实例都具有相同的类，则停止局部树的生长。30ID3决策树算法描述1.试探性地选择一个属性放置在根节点，并选择属性作为根产生分支计算信息增益选择max增益数据进一步分裂？结束否是算法流程图31选择属性作为根产生分支计算信息增益选择max增益数据进一步分信息值（熵）、信息增益的概念熵：entropy（p1,p2,...,pn）=-p1logp1-p2logp2••••-pnlogpn使用负号是因为分数p1,p2,...,pn的对数值是负数，而熵是一个正数。熵是以位bit位单位的，公式里的p1,p2,...,pn他们的和为1。entropy(p,q,r)=entropy(p,q+r)+(q+r)*entropy(q/(q+r),r/(q+r))我们需要一种度量来表示节点的纯度，并需要这种度量告诉我们根据一个变量的属性值将一个不纯的节点上的数据划分到其子女后，纯度提高了多少。最为广泛使用的度量是信息值(熵)。（以天气数据为例）32信息值（熵）、信息增益的概念熵：9outlook属性的树桩yesyesnononoyesyesyesyesyesyesyesnonooutlooksunnyovercastrainy在叶子节点上的yes和no类的实例数量分别是[2,3]、[4,0]、[3,2]，因此，这些节点上的信息值分别是：info([2,3])=entropy(2/5,3/5)=0.971bitinfo([4,0])=entropy(1,0)=0bitinfo([3,2])=entropy(3/5,2/5)=0.971bit然后计算这些叶子节点的平均信息值，并考虑到达每个分支的实例数量：有5个实例到达第一和第三个分支；4个实例到达第二个分支：那么平均信息值info([2,3],[4,0],[3,2])=(5/14)*0.971+(4/14)*0+(5/14)*0.971=0.693bit在任何初始树创建之前，处于根节点的训练样本由9个yes和5个no组成，与之相对应的信息值：info([9,5])=0.940bit因此树桩所获得的信息增益为：gain(outlook)=info([9,5])-info([2,3],[4,0],[3,2])=0.940-0.693=0.247bit33outlook属性的树桩yesyesyesoutlooksutemperature、humidity、wind属性的树桩yesyesnonoyesyesyesyesnonoyesyesyesnotemperaturehotmildcool分别计算它们的信息增益为：gain(temperature)=0.029bityesyesyesnonononoyesyesyesyesyesyesnohumidityhighnormalyesyesyesyesyesyesnonoyesyesyesnononowindfalsetruegain(humidity)=0.152bitgain(wind)=0.048bit34temperature、humidity、wind属性的树桩将这些属性的信息增益的值进行比较，信息增益最大的属性节点将作为决策树的根节点。所以我们选择outlook属性作为根节点，它是唯一一个获得了全纯子节点，这就为超越其他所有属性赢得了相当大的优势。而湿度属性是第二个最佳选择，因为它产生了一个几乎是全纯且较大的子节点。根节点确定了，接着继续进行这种递归过程。下面是outlook属性值为sunny时的节点进一步分支的可能性：outlooksunnyhumiditynononoyesyeshighnormaloutlooksunnywindyesnonoyesnofalsetrueoutlooksunnytemperaturenonoyesnoyeshotmildcool他们的信息增益分别为：gain(temperature)=0.571bitgain(humidity)=0.971bitgain(wind)=0.493bit35将这些属性的信息增益的值进行比较，信息增益最大的属性节点将作因此选择湿度属性作为在这一个节点的分裂属性，在随之产生的子节点上并不需要进一步分裂，因为叶子节点都是全纯子节点，所以这个分支就结束了。继续应用这样的思想方法，将产生关于天气数据的决策树，如下图所示。理想的停止条件是所有叶子节点都是纯的，也就是当叶子节点包含的实例拥有相同的类别。然而，也许并不可能达到这种理想状态，因为当训练集里包含2个拥有相同属性值，但是属于不同类别的样本时，递归过程将不可能停止。所以停止条件应为当数据不能被进一步分裂时。outlooksunnyrainyovercasthumiditywindyesnoyesnoyesnormalhighfalsetrue天气数据的决策树36因此选择湿度属性作为在这一个节点的分裂属性，在随之产生的子节ID3算法的不足及改进当一些属性拥有的可能值得数量很大，从而使分支的路径增加，产生出很多子节点时，计算信息增益就会出现一个问题。用一个极端的例子来说明：当数据集的某个属性对于每一个实例存在一个不同属性值时，比如，一个标志码属性。 标志码outlook temperaturehumidity windy play a sunny hot high FALSE no b sunny hot high TRUE no c overcast hot high FALSE yes d rainy mild high FALSE yes e rainy cool normal FALSE yes f rainy cool normal TRUE no g overcast cool normal TRUE yes h sunny mild high FALSEno i sunny cool normal FALSE yes j rainy mild normal FALSE yes k sunny mild normal TRUE yes l overcast mild high TRUE yes m overcast hot normal FALSE yes n rainy mild high TRUE no37ID3算法的不足及改进当一些属性拥有的可能值得数量对标志码属性进行分裂而产生的树桩如下，这个属性值的类别所需的信息量是：info([0,1])+info([0,1])+info([1,0])+......+info([1,0])+info([0,1])=0bit标志码nonoyesnoyesanbcm···标志码属性的信息增益就是在根节点上的信息量即：gain(标志码)=info([9,5])=0.940bit它比在其他任何属性上获得的信息增益值大，毫无疑问标志码将被选为分裂属性，但是在标志码属性上的分支对预测未知实例的类别没有任何帮助，也没能够描述任何有关决策的结构。由此可见，采用度量信息增益的方法会倾向于选择拥有较多可能属性值的属性。为了弥补这一缺陷，一个称之为增益率(gainratio)的度量修正被广范的采用。38对标志码属性进行分裂而产生的树桩如下，这个属性值的类别所需的上例所有的计数值均为1，因此分裂信后的信息值是：info([1,…,1])=-1/14xlog(1/14)x14=logl4(3.807位) 分支越多，该值越大。 具有较高分支的属性，该固有的信息值较高。 增益率，由信息增益除以该固有信息值得到。 例：得到标志码的增益率为0.940/3.807=0.247再返回之前的天气数据的树桩：属性outlook将数据集分裂成3个子集，规模分别为5,4,5，因此不考虑子集中所包含的类别，产生一个内在的信息值：info([5,4,5])=1.577bit得到outlook属性的增益率为：(0.940-0.693)/1.577=0.157类似的可以计算出其他属性树桩的增益率：

temperature属性的增益率为：(0.940-0.911)/info(4,6,4)=0.019humidity属性的增益率为：(0.940-0.788)/info(7,7)=0.152wind属性的增益率为：(0.940-0.693)/1.577=0.049

39上例所有的计数值均为1，因此分裂信后的信息值是：16由此可以看出，在上述4个属性中outlook属性的结果依然排在首位，而humidity属性以一个更为接近的值排在第二位，因为它将数据集分裂成2个子集而不是3个。在这个例子中，标志码属性的增益率(0.247)任然是最高的，然而，它的优势已经大大降低了。ID3算法最初的定义是假设属性值是离散值，但在实际环境中，有很多属性是连续的，不能够用一个确定的标准来对其进行划分。C4.5使用下面的一系列处理过程来对连续的属性划分成离散的属性，进而达到能够建立决策树的目的。C4.5对I