• 中央环保督察“回头看”10省区问责630人 2019-09-19
  • 天津举办改善营商环境专题讲座 2019-09-19
  • 日本核能行业誓言日本将在今年内重新启用核电 2019-09-03
  • 中国保险行业协会发布汽车后市场配件合车标准 2019-09-02
  • 晋中市通报五起违反中央八项规定精神问题 2019-08-30
  • 两小鸟缠绕困路中,公交司机车流中救助 2019-08-30
  • 互联网药品信息服务资格证书 (京)-经营性-2009-0016 2019-08-29
  • 淮南23家存在重大安全隐患单位被挂牌督办 2019-08-29
  • 专属球队定制装饰火爆 足球盛宴更是消费大餐——浙江在线 2019-08-26
  • 驻村工作队帮村民“马”上致富 2019-08-26
  • 特色小镇里的税收服务 定海国地税多措并举提升效能 2019-08-23
  • 【央视快评】让传统文化焕发新时代风采 2019-08-22
  • 后高考时代 孩子们这样致青春 2019-08-12
  • 湖南高校:将十九大精神融入基础课教学建设 2019-08-12
  • 兰州大学“习近平新时代中国特色社会主义思想研究中心”成立 2019-08-10
  • 当前位置 > CPDA数据分析师 > “数”业专攻 > 数据分析培训系列—分类算法之决策树(二)

    天津快乐10分走势图:数据分析培训系列—分类算法之决策树(二)

    浙江快乐彩和值走势图 www.pn-vs.com 来源:数据分析师 CPDA | 时间:2015-07-29 | 作者:admin

     

    从零开始学挖掘——分类算法之决策树(二)

    2 如何建立决策树

    原则上,对于给定的属性集,可以构造的决策树的数目达到指数级。尽管某些决策树比其他决策树更准确,但是由于搜索空间是指数规模的,找出最佳决策树在计算上是不可行的。尽管如此,人们还是开发了一些有效的算法,能否在合理的时间内构造出具有一定准确率的次最优决策树。这些算法通常都采用贪心策略,在选择划分数据的属性时,采取一系列局部最优决策来构造决策树,hunt算法就是一种这样的算法。它是许多决策树算法的基础,包括ID3、C4.5和CART。本节讨论hunt算法并解释它的一些设计问题。

    在hunt算法中,通过将训练记录相继划分成为较纯的子集,以递归方式建立决策树。设Dt是与节点t相关联的训练记录集,而y={y1,y2……yc}是类标号,hunt算法的递归定义如下。

    • 如果Dt中所有记录都属于同一类yt,则t是叶结点,用yt标记。
    • 如果Dt中包含属于多个类的记录,则选择一个属性测试条件(attribute test condition),将记录划分成较小的子集。对于测试条件的每个输出,创建一个子女节点,并根据测试结果将Dt中的记录分布到子女节点中。然后,对于每个子女节点,递归地调用该算法。

    例如,我们来预测贷款申请者是否会按时归还贷款。数据如下表所示

    1

    该分类问题的初始决策树只有一个结点,类标号为“拖欠贷款者=否”,如图a,意味着大多数贷款这都按时归还贷款。然而,该树需要进一步的细化,因为根结点包含两个类的记录。根据“有房者”测试条件,这些记录被划分为较小的子集,如图b。选取属性测试条件的理由稍后讨论,目前,我们假定此处这样选是划分数据的最优标准。接下来,对根结点的每个子女递归hunt算法。上表中数据显示,有房的贷款者都按时偿还了贷款,因此,根结点的左子女为叶结点,标记为“拖欠贷款者=否”。对于右子女,我们需要继续递归调用hunt算法,直到所有的记录都属于同一类为止。每次递归调用所形成的决策树显示在图c和图d中。

    2

    如果属性集的每种组合都在训练数据中出现,并且每种组合都具有惟一的类标号,则hunt算法是有效的。但是对于大多数实际情况,这些假设太苛刻了,因此,需要附加的条件来处理以下的情况。

    • 算法的第二步所创建的子女节点可能为空,即不存在与这些结点相关联的记录。如果没有一个训练记录包含与这样的结点相关联的属性值组合,这种情况就可能发生。这时,该结点成为叶结点,类标号为其父结点上训练记录中的多数类。
    • 在第二步中,如果与Dt相关联的所有记录都具有相同的属性值(目标属性除外),则不可能进一步划分这些记录。在这种情况下,该结点为叶结点,其标号为与该节点相关联的训练记录中的多数类。

    下面,我们和大家讨论一下决策树归纳的学习算法必须解决下面两个问题

    • 如果分裂训练记录,树增长过程的每个递归步都必须选择一个属性测试条件,将记录划分为较小的子集。为了实现这个步骤,算法必须提供为不同类型的属性制定测试条件的方法,并且提供评估每种测试条件的客观度量。
    • 如何停止分裂过程,需要有结束条件,以终止决策树的生长过程,一个可能的策略是分裂结点,直到所有的记录都属于同一个类,或者所有的记录都具有相同的属性值。尽管两个结束条件对于结束决策树归纳算法都是充分的,但是还可以使用其他的标准提前终止树的生长过程。提前终止的优点我们在后续继续讨论。

     

    3表示属性测试条件的方法

    决策树归纳算法必须为不同类型的属性提供表示属性测试条件和其对应输出的方法。

    二元属性:此种测试条件产生两个可能的输出。

    3

    标称属性:有多个属性值,它的测试条件可以用两种方法表示,第一种方法,对于多路划分,该属性有多少个不同的属性值就有多少个输出;第二种方法,k个属性可以生成2k-1-1个二元划分。

    4

    序数属性:也可以产生二元或多路划分,只要不违背序数属性值得有序性,就可以对属性值进行分组。

    5

    连续属性:对于连续属性来说,测试条件可以是具有二元输出比较测试(A<v)或者(A>=v),也可以是具有形如vi<=A<=vi+1(i=1……k)输出的范围查询产生二元或多路划分,只要不违背序数属性值得有序性,就可以对属性值进行分组。对连续性属性使用离散策略,每个离散化区域赋予一个新的序数值,只要保持有序性,相邻的值还可以聚集成较宽的区间。

    6

    本节中我们介绍了决策树的构造方式,以及各种属性测试条件的对应输出方法,对于决策树来说,另一个重要问题则是,选择什么度量来确定划分记录的最佳方式,即选择最佳划分的度量,我们将在第三节中详细介绍。

     

  • 中央环保督察“回头看”10省区问责630人 2019-09-19
  • 天津举办改善营商环境专题讲座 2019-09-19
  • 日本核能行业誓言日本将在今年内重新启用核电 2019-09-03
  • 中国保险行业协会发布汽车后市场配件合车标准 2019-09-02
  • 晋中市通报五起违反中央八项规定精神问题 2019-08-30
  • 两小鸟缠绕困路中,公交司机车流中救助 2019-08-30
  • 互联网药品信息服务资格证书 (京)-经营性-2009-0016 2019-08-29
  • 淮南23家存在重大安全隐患单位被挂牌督办 2019-08-29
  • 专属球队定制装饰火爆 足球盛宴更是消费大餐——浙江在线 2019-08-26
  • 驻村工作队帮村民“马”上致富 2019-08-26
  • 特色小镇里的税收服务 定海国地税多措并举提升效能 2019-08-23
  • 【央视快评】让传统文化焕发新时代风采 2019-08-22
  • 后高考时代 孩子们这样致青春 2019-08-12
  • 湖南高校:将十九大精神融入基础课教学建设 2019-08-12
  • 兰州大学“习近平新时代中国特色社会主义思想研究中心”成立 2019-08-10
  • 68彩票送彩金 彩客网 山西快乐十分开奖结果查询 2018开奖直播香港结果 捕鱼王游戏技巧 电子游戏包括什么 福彩3d012路遗漏统计 云南时时彩计划软件手机版 山东十一选五直播开奖结果查询 上海体育彩票中心在哪 北京pk10冠军算法 牌九娱乐城 未卜先知平特一肖图 3d组六 英超