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

1、 决策树的建立 Decision Tree数据挖掘1学习数据挖掘的工具-weka weka是用Java语言编写的完整的软件资源 Explorer是weka的主要图形用户界面 weka存储数据的原始方式是ARFF或CSV文件格式 ARFF文件是由一组实例组成，并且每组实例的属性值由逗号分开。（属性的类别）2天气数据outlooktemperaturehumiditywindyplay1sunnyhothighFALSEno2sunnyhothighTRUEno3overcasthothighFALSEyes4rainymildhighFALSEyes5rainycoolnormalFALSEye

2、s6rainycoolnormalTRUEno7overcastcoolnormalTRUEyes8sunnymildhighFALSEno9sunnycoolnormalFALSEyes10 rainymildnormalFALSEyes11 sunnymildnormalTRUEyes12 overcastmildhighTRUEyes13 overcasthotnormalFALSEyes14 rainymildhighTRUEno3 我们希望从上面的实例中找出者若干条规则，使得能够对这些实例的类做出判断（理想情况下）（举例）if outlook=sunny and=high then

3、play=no if humidity=normal then play=yes 第二条规则错分了一个实例样本4n决策节点：决策节点：1.最上面的节点称为根节点，是整个决策树的开始。最上面的节点称为根节点，是整个决策树的开始。2.每个节点子节点的个数与决策树在用的算法有关。每个节点子节点的个数与决策树在用的算法有关。（二叉树、多叉树）（二叉树、多叉树）n分支：判断过程，要么是新的决策节点，要么是叶子分支：判断过程，要么是新的决策节点，要么是叶子n树叶树叶:树的结尾，每个叶子代表一个类别树的结尾，每个叶子代表一个类别根节点叶子节点决策节点叶子节点叶子节点5步骤：步骤：1.决策树的生成：由训练样本

4、数据集（根据历史数据生成、有一定综合程度的用于数据分析处理的数据集）生成2.决策树的剪枝：采用新的样本数据集（测试数据集或者训练数据修剪集）检验决策树生成过程中产生的初步规则，将影响预测准确性的分支剪除。6ID3决策树算法描述 1.试探性地选择一个属性放置在根节点，并对该属性的每个值产生一个分支。2.分裂根节点上的数据集，并移到子女节点，产生一棵局部树。3.对该划分的信息增益进行计算。4.对其他属性重复该过程。5.每个用于划分的属性产生一棵局部树。6.根据局部树的信息增益值，选择一棵增益最大的属性的局部树。7.对选定的局部树的每个子女节点重复以上1-6步。8.这是一个递归过程。如果一个节点上的

5、所有实例都具有相同的类，则停止局部树的生长。7选择属性作为根产生分支计算信息增益选择max增益数据进一步分裂？结束否是算法流程图8信息值（熵）、信息增益的概念熵：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)我们需要一种度量来表示节点的纯度，并需要这种度量告诉我们根据一个变量的属性值将一个不纯的节点上的

6、数据划分到其子女后，纯度提高了多少。最为广泛使用的度量是信息值(熵)。（以天气数据为例）9outlook属性的树桩yesyesnononoyesyesyesyesyesyesyesnonooutlooksunnyovercastrainy在叶子节点上的yes和no类的实例数量分别是2,3、4,0、3,2，因此，这些节点上的信息值分别是：info(2,3)=entropy(2/5,3/5)=0.971 bitinfo(4,0)=entropy(1,0)=0 bitinfo(3,2)=entropy(3/5,2/5)=0.971 bit然后计算这些叶子节点的平均信息值，并考虑到达每个分支的实例数量

7、：有5个实例到达第一和第三个分支；4个实例到达第二个分支：那么平均信息值info(2,3,4,0,3,2)=(5/14)*0.971+(4/14)*0+(5/14)*0.971=0.693 bit在任何初始树创建之前，处于根节点的训练样本由9个yes和5个no组成，与之相对应的信息值：info(9,5)=0.940 bit因此树桩所获得的信息增益为：gain(outlook)=info(9,5)-info(2,3,4,0,3,2)=0.940-0.693=0.247 bit10temperature、humidity、wind属性的树桩yesyesnonoyesyesyesyesnonoyes

8、yesyesnotemperature hotmildcool分别计算它们的信息增益为：gain(temperature)=0.029 bityesyesyesnonononoyesyesyesyesyesyesnohumidity highnormalyesyesyesyesyesyesnonoyesyesyesnononowind falsetruegain(humidity)=0.152 bitgain(wind)=0.048 bit11将这些属性的信息增益的值进行比较，信息增益最大的属性节点将作为决策树的根节点。所以我们选择outlook属性作为根节点，它是唯一一个获得了全纯子节点，这

9、就为超越其他所有属性赢得了相当大的优势。而湿度属性是第二个最佳选择，因为它产生了一个几乎是全纯且较大的子节点。根节点确定了，接着继续进行这种递归过程。下面是outlook属性值为sunny时的节点进一步分支的可能性：outlooksunnyhumiditynononoyesyeshighnormaloutlooksunnywindyesnonoyesnofalsetrueoutlooksunnytemperaturenonoyesnoyeshotmildcool他们的信息增益分别为：gain(temperature)=0.571 bitgain(humidity)=0.971 bitgain(

10、wind)=0.493 bit12因此选择湿度属性作为在这一个节点的分裂属性，在随之产生的子节点上并不需要进一步分裂，因为叶子节点都是全纯子节点，所以这个分支就结束了。继续应用这样的思想方法，将产生关于天气数据的决策树，如下图所示。理想的停止条件理想的停止条件是所有叶子节点都是纯的，也就是当叶子节点包含的实例拥有相同的类别。然而，也许并不可能达到这种理想状态，因为当训练集里包含2个拥有相同属性值，但是属于不同类别的样本时，递归过程将不可能停止。所以停止条件应为当数据不能被进一步分裂时。outlooksunnyrainyovercasthumiditywindyesnoyesnoyesnorma

11、lhighfalsetrue天气数据的决策树13ID3算法的不足及改进 当一些属性拥有的可能值得数量很大，从而使分支的路径增加，产生出很多子节点时，计算信息增益就会出现一个问题。用一个极端的例子来说明：当数据集的某个属性对于每一个实例存在一个不同属性值时，比如，一个标志码属性。标志码 outlooktemperature humidity windy play a sunny hothigh FALSE no b sunny hothigh TRUE no c overcast hothigh FALSE yes d rainy mildhigh FALSE yes e rainy cooln

12、ormal FALSE yes f rainy coolnormal TRUE no g overcast coolnormal TRUE yes h sunny mildhigh FALSE no i sunny coolnormal FALSE yes j rainy mildnormal FALSE yes k sunny mildnormal TRUE yes l overcast mildhigh TRUE yes m overcast hotnormal FALSE yes n rainy mildhigh TRUE no14对标志码属性进行分裂而产生的树桩如下，这个属性值的类别所

13、需的信息量是：info(0,1)+info(0,1)+info(1,0)+.+info(1,0)+info(0,1)=0 bit标志码nonoyesnoyesanbcm 标志码属性的信息增益就是在根节点上的信息量即：gain(标志码)=info(9,5)=0.940 bit它比在 其他任何属性上获得的信息增益值大，毫无疑问标志码将被选为分裂属性，但是在标志码属性 上的分支对预测未知实例的类别没有任何帮助，也没能够描述任何有关决策的结构。由此可见，采用度量信息增益的方法会倾向于选择拥有较多可能属性值的属性。为了弥补这一缺陷，一个称之为增益率(gain ratio)的度量修正被广范的采用。15上例

14、所有的计数值均为1，因此分裂信后的信息值是：info(1,1)=-1/14 x log(1/14)x 14=logl4(3.807位)分支越多，该值越大。具有较高分支的属性，该固有的信息值较高。增益率，由信息增益除以该固有信息值得到。例：得到标志码的增益率为 0.940/3.807=0.247再返回之前的天气数据的树桩：属性outlook将数据集分裂成3个子集，规模分别为5,4,5，因此不考虑子集中所包含的类别，产生一个内在的信息值：info(5,4,5)=1.577 bit 得到outlook属性的增益率为：(0.940-0.693)/1.577=0.157 类似的可以计算出 其他属性树桩的

15、增益率：temperature属性的增益率为：(0.940-0.911)/info(4,6,4)=0.019 humidity属性的增益率为：(0.940-0.788)/info(7,7)=0.152 wind属性的增益率为：(0.940-0.693)/1.577=0.04916 由此可以看出，在上述4个属性中outlook属性的结果依然排在首位，而humidity属性以一个更为接近的值排在第二位，因为它将数据集分裂成2个子集而不是3个。在这个例子中，标志码属性的增益率(0.247)任然是最高的，然而，它的优势已经大大降低了。ID3算法最初的定义是假设属性值是离散值，但在实际环境中，有很多属性

16、是连续的，不能够用一个确定的标准来对其进行划分。C4.5使用下面的一系列处理过程来对连续的属性划分成离散的属性，进而达到能够建立决策树的目的。C4.5对ID3进行了一系列改进。这些改进包括处理数值属性、残缺值、后剪枝的方法。（将训练数据分为成长集和修剪集）17C4.5算法做出的改进(1)用信息增益率来选择属性(2)可以处理连续数值型属性 在选择某节点上的分枝属性时，对于离散型描述属性，C4.5的处理方法与ID3相同，按照该属性本身的取值个数进行计算；对于某个连续性描述属性Ac，假设在某个结点上的数据集的样本数量为t，C4.5将作以下处理。1.将该结点上的所有数据样本按照连续型描述属性的具体数值

17、，由小到大进行排序，得到属性值的取值序列A1c，A2c，Atc。2.在取值序列中生成t-1个分割点。第i（0it）个分割点的取值设置为Vi=（Aic+A（i+1）c）/2,它可以将该节点上的数据集划分为两个子集。3.从t-1个分割点中选择最佳分割点。对于每一个分割点划分数据集的方式，C4.5计算它的信息增益率，并且从中选择信息增益率最大的分割点来划分数据集。18(3)采用了一种后剪枝方法 在后修剪过程中考虑两种完全不同的操作：子树置换 和 子树上升ALTpriceyesabcyesyesno4/57/81/2ALTyes12/15子树的置换yes19子树的上升：ABC45123AC12320为

18、了避免树的高度无节制的增长，避免过度拟合数据，该方法使用训练样本集本身来估计剪枝前后的误差，从而决定是否真正剪枝。方法中使用的公式如下：其中N是实例的数量，f=E/N为观察到的误差率（其中E为N个实例中分类错误的个数），q为真实的误差率，c为置信度为置信度（C4.5算法的一个输入参数，默认值为0.25），z为对应于置信度c的标准差，其值可根据c的设定值通过查正态分布表得到。通过该公式即可计算出真实误差率q的一个置信度上限，用此上限为该节点误差率e做一个悲观的估计：通过判断剪枝前后e的大小，从而决定是否需要剪枝。（e变小，剪枝）21(4)对于残缺值的处理 在某些情况下，可供使用的数据可能缺少某些

19、属性的值。假如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 在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。C4.5只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时程序无法运行。C4.5算法的缺点23