决策树

LOGO决策树算法交通信息工程及控制赵娣主要内容概述决策树算法原理常用决策树算法决策树剪枝应用实例分析1概述数据挖掘的目标是从海量数据中发现隐含的，有意义的知识。它的任务主要是分类、预测、时间序列模式、聚类分析、关联分析预测和偏差分析等。分类:分类就是按照一定的标准把数据对象划归成不同类别的过程。预测:预测就是通过对历史数据的分析找出规律，并建立模型，通过模型对未来数据的种类和特征进行分析。时间序列模式:时间序列模式就是根据数据对象随时间变化的规律或趋势来预测将来的值。1概述聚类分析:聚类分析是在没有给定划分类的情况下，根据数据信息的相似度进行数据聚集的一种方法。关联分析预测:关联分析就是对大量的数据进行分析，从中发现满足一定支持度和可信度的数据项之间的联系规则。偏差分析:偏差分析就是通过对数据库中的孤立点数据进行分析，寻找有价值和意义的信息。1概述分类是数据挖掘中一项非常重要的任务，日前在商业上应用最多。分类的目的是提取出一个分类函数或分类模型(也常常称作分类器)，该模型能把数据库中的数据项映射到给定类别中的某一个。分类的结果可用于预测。预测的目的是从历史数据中自动推导出对给定数据的推广描述，从而能对未来数据进行预测。目前，主要的分类方法有决策树归纳分类法、贝叶斯分类法、神经网络分类法等。其中，最为典型的分类方法就是基于决策树的分类方法。2决策树算法原理决策树是一个类似于流程图的树结构，其中每个内部节点表示在一个属性上的测试，每个分支代表一个测试输出，而每个树叶代表类或类分布。树的最顶层节点是根节点。列如，在贷款审请中，要对申请的风险大小做出判断。2决策树算法原理例如负责借贷的银行官员利用上图的决策树来决定支持那些贷款和拒绝那些贷款。他就用贷款申请表来运行这棵决策树，用决策树判断风险的大小。“年收入大于40000”并且“高负债”的用户被认为是“高风险”，同时“年收入小于10000”但“工作时间大于5年”的申请，则被认为是“低风险””而建议贷款给他。决策树是数据挖掘中的一项重要技术，可以用于分析数据，同样也可以用来预测。2决策树算法原理优点：使用者不需要了解很多背景知识，只要训练事例能用属性→结论的方式表达出来，就能用该算法学习;决策树模型效率高，对训练集数据量较大的情况较为适合;分类模型是树状结构，简单直观，可将到达每个叶结点的路径转换为IF→THEN形式的规则，易于理解;决策树方法具有较高的分类精确度。2决策树算法原理分裂准则：在决策树算法中将训练数据集D中的元组划分为个体类的最好的方法与策略，它告诉我们在节点N上测试哪个属性合适，如何选择测试与测试的方法，从节点N上应该生长出哪些分支。分裂属性Xi：决策树中每个内部节点都对应的一个用于分裂数据集的属性，Xi∈A={A1，A2，…，Ah}。2决策树算法原理如果Xi是连续属性，那么分裂准则的形式为Xi≤xi，其中xi就称为节点n的分裂点。如果Xi是离散属性，那么的形式为xi∈Yi，其中YiXi，Yi就称为节点n的分裂子集。注意:分裂准则与分裂属性、分裂点、分裂子集并不等同，它们是四个不同的概念。2决策树算法原理将上面的定义结合实际的决策树例子可得决策树图如下所示，图中设X为分裂属性，是属性X的已知值。2决策树算法原理3常用决策树算法决策树技术是一种“贪心”搜索，使用了贪心算法，首先找出最有判别力的属性，把样例分成多个子集，每个子集又选择最有判别力的属性进行划分，一直进行到所有子集仅包含同一类型的数据为止。最后得到一棵决策树。决策树的生成算法主要有ID3、C4.5、CARPT、CHAID、PUBLIC、SLIQ等方法。ID3算法在1979年提出，是机器学习中广为人知的一个算法，代表着基于决策树方法的一大类。3常用决策树算法ID3算法主要是引进了信息论中的信息增益，作为属性判别能力的度量，构造决策树的递归算法。决策树叶子为类别名，即P或者N。其它结点由样例的属性组成，每个属性的不同取值对应一分枝。ID3就是要从表的训练集构造出这样的决策树。实际上，能正确分类训练集的决策树不止一棵。ID3算法能得出结点最少的决策树。3常用决策树算法信息熵自信息量只能反映符号的不确定性，而信息熵可以用来度量整个信源X整体的不确定性。设某事物具有n种相互独立的可能结果(或称状态):，每一种结果出现的概率分别为，且有：nxxx,,,21)()(),(21nxPxPxP那么，该事物所具有的不确定量为3常用决策树算法假设训练数据集D中的正例集PD和反例集ND的大小分别为p和n，则ID3基于下面两个假设给出该决策树算法中信息增益的定义，因为信息是用二进制编码的，所以在下面的公式定义中都用以2为底的对数。(1)在训练数据集D上的一棵正确决策树对任意例子的分类概率同D中正反例的概率一致;(2)一棵决策树能对一个例子做出正确类别判断所需的信息量如下公式所示:3常用决策树算法如果以属性A作为决策树的根，A具有V个值{v1,v2,…，Vv}，它将A分成v个子集，假设中含有P个正例和n个反例，那么，以属性A为根所需的信息期望如下公式所示:因此，以A为根的信息增益如下公式所示:上面给出的相关定义主要是在两类分类问题的前提下，将其扩展到多类后的相关定义描述也是一样的。4决策树剪枝在现实世界中，获得的数据并不可能保证其完美性与完整性，所以，在当被用来创建决策树的训练数据集中存在有噪声，或者数量太少以至于不能产生目标函数的有代表性的采样的时候，我们使用决策树算法生成的决策树很多分支反映的是训练数据集中的异常。在上面任意一种情况发生的时候，利用简单算法产生的树会出现过拟合训练样例的现象。剪枝是一种克服噪声的基本技术，同时它也能使树得到简化而变得容易理解。4决策树剪枝有两种基本的剪枝策略：(1)预剪枝也称为先剪枝，在该方法中主要是通过提前停止树的构造(例如，通过确定在给定的节点不再分裂或划分训练元组的子集)来对决策树进行剪枝。一旦停止以后，乘下的那个节点就成为了树叶。该树叶可能持有子集元组中最频繁的类或这些元组的概率分布。(2)后剪枝算法己经得到了广泛的应用，这个算法最初是由Breiman等提出，它首先构成完整的决策树，允许决策树过度拟合训练数据，然后对那些置信度不够的结点的子树用叶子结点来替代，这个叶子结点所应标记的类别为子树中大多数实例所属的类别。5应用实例分析下面我们利用下表根据天气是否打网球的训练数据集，利用ID3算法来判断某天是否适合打网球。DayOutlookTemperatureHumidityWindyPlay1sunnyhothighWeakno2sunnyhothighStrongno3overcasthothighWeakyes4rainmildhighWeakyes5raincoolnormalWeakyes6raincoolnormalStrongnoDayOutlookTemperatureHumidityWindyPlay7overcastcoolnormalStrongyes8sunnymildhighWeakno9sunnycoolnormalWeakyes10rainmildnormalWeakyes11sunnymildnormalStrongyes12overcastmildhighStrongyes13overcasthotnormalWeakyes14rainmildhighStrongno5应用实例分析(1)未分区前，训练数据集中共有14个实例，其中有9个实例属于p类(适合打网球的)，5个实例属于n类(不适合打网球)，因此分区前类别属性的熵为:(2)非类别属性信息嫡的计算若选择outlook为测试属性。5应用实例分析因此，这种划分的信息增益是:同理，可以求出其它三个属性的信息增益为由上可知，属性值outlook在各个属性中具有最高的增益，被选作分裂属性。则第一个根节点T被用outlook标记，并对于每个属性值生长一个分支。5应用实例分析(3)递归地创建决策树的树枝和叶子选择作为测试属性后，将训练实例集分为三个子集，生成三个子节点，对每个子节点递归采用上述过程进行分类直至每个节点都成为叶节点而己。5应用实例分析5应用实例分析针对sunny中的子训练数据集分支，有两个类别，该分支中有3个实例属于n类，有2个实例属于P类，因此针对分支的信息熵为:it若以sunny分支中的属性Temperature为测试属性;则测试属性Temperature的信息量为:5应用实例分析其信息增益为若以Sunny分支中的属性Humidity为测试属性，则测试属性Humidity的信息量为:其信息增益为:若以sunny分支中的属性Wind为测试属性，则测试属性wind的信息量为:5应用实例分析其信息增益为:这时生成的决策树如图所示:5应用实例分析模型汇总指定增长方法CRT因变量play自变量outlook,temperature,humidity,windy验证无最大树深度5父节点中的最小个案1子节点中的最小个案1结果自变量已包括windy,outlook,humidity,temperature节点数13终端节点数7深度5风险估计标准误差.000.000增长方法:CRT因变量列表:play5应用实例分析模型汇总指定增长方法CRT因变量play自变量outlook,temperature,humidity,windy验证无最大树深度5父节点中的最小个案4子节点中的最小个案2结果自变量已包括windy,outlook,humidity,temperature节点数7终端节点数4深度3风险估计标准误差.200.103增长方法:CRT因变量列表:play