数据挖掘分类算法之决策树.ppt

《数据挖掘分类算法之决策树.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据挖掘分类算法之————决策树最为典型的分类方法——决策树决策树(DecisionTree）是在已知各种情况发生概率的基础上，通过构成决策树来求取净现值的期望值大于等于零的概率，评价项目风险，判断其可行性的决策分析方法，是直观运用概率分析的一种图解法。由于这种决策分支画成图形很像一棵树的枝干，故称决策树。决策树是数据挖掘分类算法的一个重要方法。在各种分类算法中，决策树是最直观的一种。组成□——决策点，是对几种可能方案的选择，即最后选择的最佳方案。如果决策属于多级决策，则决策树的中间可以有多个决策点，以决策

2、树根部的决策点为最终决策方案。○——状态节点，代表备选方案的经济效果（期望值），通过各状态节点的经济效果的对比，按照一定的决策标准就可以选出最佳方案。由状态节点引出的分支称为概率枝，概率枝的数目表示可能出现的自然状态数目每个分枝上要注明该状态出现的概率。△——结果节点，将每个方案在各种自然状态下取得的损益值标注于结果节点的右端。优点决策树易于理解和实现，人们在在学习过程中不需要使用者了解很多的背景知识，这同时是它的能够直接体现数据的特点，只要通过解释后都有能力去理解决策树所表达的意义。对于决策树，数据的准备

3、往往是简单或者是不必要的，而且能够同时处理数据型和常规型属性，在相对短的时间内能够对大型数据源做出可行且效果良好的结果。易于通过静态测试来对模型进行评测，可以测定模型可信度；如果给定一个观察的模型，那么根据所产生的决策树很容易推出相应的逻辑表达式。缺点1)对连续性的字段比较难预测。2)对有时间顺序的数据，需要很多预处理的工作。3)当类别太多时，错误可能就会增加的比较快。4)一般的算法分类的时候，只是根据一个字段来分类。决策树分类算法决策树分类过程决策树的构造决策树是以实例为基础的归纳学习算法。它从一组无次序

4、、无规则的元组中推理出决策树表示形式的分类规则；采用自顶向下的递归方式，在决策树的内部节点进行属性值的比较，并根据不同的属性值从该节点向下分支，而叶节点是要学习划分的类。从根节点到叶节点的一条路径就对应着一条合取规则，整个决策树就对应着一组析取表达式规则。目前已有多种决策树算法：CLS、ID3、CHAID、C4.5、CART、SLIQ、SPRINT等。著名的ID3（IterativeDichotomiser3）算法是J.R.Quinlan在1986年提出的，该算法引入了信息论中的理论，是基于信息熵的决策树分

5、类算法。决策树ID3算法ID3算法的核心是：在决策树各级节点上选择属性时，用信息增益作为属性的选择标准，以使得在每一个非叶节点进行测试时能获得关于被测试记录最大的类别信息。具体方法：检测所有的属性，选择信息增益最大的属性产生决策树结点，由该属性的不同取值建立分枝，再对各分支的子集递归调用该方法建立决策树结点的分枝，直到所有子集仅包含同一类别的数据为止，最后得到一棵决策树，它可以用来对新的样本进行分类。选择属性方法在决策树归纳方法中，通常使用信息增益方法来帮助确定生成每个结点时所应采用的合适属性。这样就可以选

6、择具有最高信息增益（熵减少的程度最大）的属性作为当前结点的测试属性，以便使对之后所划分获得的训练样本子集进行分类所需要信息最小，也就是说，利用该属性进行当前（结点所含）样本集合划分，将会使得所产生的各样本子集中的“不同类别混合程度”降为最低。因此采用这样一种信息论方法将帮助有效减少对象分类所需要的次数，从而确保所产生的决策树最为简单，尽管不一定是最简单的。分类所需要的信息量利用属性A划分当前样本集合所需要的信息（熵）信息增益算法ID3的一种描述序号年龄收入是否学生信用购买PC1<=30高否中否2<=30高否

7、优否331~40高否中是4>40中否中是5>40低是中是6>40低是优否731~40低是优是8<=30中否中否9<=30低是中是10>40中是中是11<=30中是优是1231~40中否优是1331~40高是中是14>40中否优否一个商场顾客数据库【例】用决策树考察某顾客是否会购买PC=0.94年龄=“<=30”：c11=2，c21=3I(c11，c21)=0.971年龄=“31~40”：c12=4，c22=0I(c12，c22)=0年龄=“>40”：c13=3，c23=2I(c13，c23)=0.9711)

8、创建根结点由给定训练集，类标号属性为购买PC，它有两个不同的值(“是”、“否”)，即有两个不同的类，m=2；设c1对应“是”，c2对应“否”，则c1=9，c2=5；样本总数s=14。所以训练集中两个类别的先验概率分别为：计算对给定样本分类所需的期望信息下面计算每个属性的熵。从年龄开始计算如果样本按年龄划分，对一个给定的样本分类所需的期望信息如下：因此，这种划分的信息增益是：Gain(年龄)=I(C1，C2)-E(