数据仓库与数据挖掘课件_第四章_决策树

《数据仓库与数据挖掘课件_第四章_决策树》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第4章决策树《数据挖掘与知识发现》(第2版)吉林大学计算机科学与技术学院李雄飞1数据挖掘与知识发现(第2版)决策树决策树学习是以实例为基础的归纳学习算法，是应用最广泛的逻辑方法。本章介绍如下几个方面的内容：信息论基础ID3算法决策树剪枝C4.5算法CART算法SLIQ算法决策树与数据预处理2数据挖掘与知识发现(第2版)引言决策树学习是以实例为基础的归纳学习算法，是应用最广泛的逻辑方法。典型的决策树学习系统采用自顶向下的方法，在部分搜索空间中搜索解决方案。它可以确保求出一个简单的决策树，但未必是最简单的。Hunt等人于1966年提出的概念学习系统CLS(ConceptLearnin

2、gSystem)是最早的决策树算法。决策树常用来形成分类器和预测模型，可以对未知数据进行分类或预测、数据挖掘等。从20世纪60年代，决策树广泛应用在分类、预测、规则提取等领域。J.R.Quinlan于1979年提出ID3(IterativeDichotomizer3)算法后，决策树方法在机器学习、知识发现领域得到了进一步应用。C4.5是以ID3为蓝本的能处理连续属性的算法。ID4和ID5是ID3的增量版本。强调伸缩性的决策树算法有SLIQ、SPRINT、RainForest算法等。用决策树分类的步骤：第一步：利用训练集建立一棵决策树，建立决策树模型。这是从数据中获取知识，进行机器

3、学习的过程。第二步：利用生成的决策树模型对未知的数据样本进行分类。从根结点开始对该对象的属性逐渐测试其值，并且顺着分支向下走，直至到达某个叶结点，此时叶结点代表的类即为该对象所处的类。3数据挖掘与知识发现(第2版)引言决策树的结点:内部结点是属性或属性的集合，包括属性已被检验的节点。内部节点的输出分枝和该节点的所有可能的检验结果相对应。内部结点的属性称为测试属性。叶结点是所要学习划分的类。训练决策树模型的步骤：第一个步骤(建树)。选取部分训练数据，按广度优先递归算法建立决策树，直到每个叶子结点属于一个类为止。第二个步骤(剪枝)。用剩余的数据对生成的决策树进行检验，将不正确的问题进

4、行调整，对决策树进行剪枝和增加结点，直到建立一个正确的决策树。建树是通过递归过程，最终得到一棵决策树，而剪枝则是为了降低噪声数据对分类正确率的影响。4数据挖掘与知识发现(第2版)信息论基础信息论是C.E.Shannon为解决信息传递(通信)过程问题建立的一系列理论。传递信息系统由三部分组成：信源：发送端信宿：接受端信道连接两者的通道通信过程是随机干扰环境中传递信息的过程。在通信前，收信者(信宿)不可能确切了解信源会发出什么样的信息；不可能判断信源的状态，上述情形称为信宿对于信源状态具有不定性，又叫先验不确定性。通信结束后，信宿还仍然具有一定程度的不确定性，称为后验不确定性。后验不

5、确定性总要小于先验不确定性，不可能大于先验不确定性。如果后验不确定性的大小等于先验不确定性的大小，表示信宿根本没有收到信息。如果后验不确定性的大小等于零，表示信宿收到了全部信息。信息用来消除(随机)不定性。信息的大小，由消除的不定性大小来计量。5数据挖掘与知识发现(第2版)信息论基础信息熵：衡量一个随机变量取值的不确定性程度。设X是一个离散随机变量，它可能的取值为X的概率为P(X)，那么定义这里H(X)是随机变量X的熵，它是衡量随机变量取值不确定性的度量。在随机试验之前，只了解各取值的概率分布，而做完随机试验后，就能确切地知道取值，不确定性完全消失。通过随机试验获得信息的数量恰好

6、等于随机变量的熵，故熵又可作为信息的度量。熵从平均意义上表征信源总体信息测度。6数据挖掘与知识发现(第2版)信息论基础熵增原理：统计热力学中，熵是系统混乱度的度量。混乱度越小，熵越小。信息不增性原理：信息学中的熵是不确定性的度量。不确定性越小，即概率越大，熵越小，信息量越小。在信息论中，熵H(X)表示属性X包含的信息量的多少。熵可以衡量属性的纯度，属性的熵越小，表明属性中的数据在属性域上的分布越不均匀。属性中属于某个属性值或某几个属性值的数据较多，而属于另外属性值的数据较少，则这个数据集合越纯。如果一个属性的所有数据都属于同一属性值，则该属性的熵为0，该属性包含的信息为0，即该属

7、性在数据集合中不存在对数据有用的信息。一个属性的熵越大，说明数据在属性域上的分布越均匀，这个属性也就越不纯。如果属性X中的数据在属性域上均匀分布，那么属性的熵最大，其蕴含的信息越多。7数据挖掘与知识发现(第2版)信息论基础联合熵：对于联合随机变量(X,Y)，如果每个可能的输出(x,y)对应的概率为P(x,y)，定义(X,Y)所能提供的信息量为联合熵，公式为：条件熵：用于衡量在属性Y己知的情况下，属性X的不确定性程度，或者说属性X对属性Y的依赖性强弱程度。在给定Y条件下，X的熵是可