• 发展改革委就创新和完善宏观调控等答问 2019-07-13
  • 深圳2018年将开行3趟援疆旅游扶贫专列 2019-07-01
  • 房地产就有国家和集体之土地不计价到计价,这笔是经济收入还是财产收入? 2019-07-01
  • Map Out Your Life in Chongqing 2019-06-28
  • 世界杯黄历:日本换帅对战黑马“小哥” 2019-06-27
  • 小区麻将馆 何时不扰民 2019-06-26
  • 纷纷“结缘”世界杯 家电企业图什么 2019-06-13
  • 推动吉台两地合作发展再上新台阶 2019-05-29
  • 中青报:父亲的“卖牛钱”被打赏 该如何管住孩子的手 2019-05-29
  • 任建明解读中纪委五次全会亮点 展望新时期反腐制度建设 2019-05-28
  • 全国首套房贷款利率连续17个月上升 2019-05-25
  • 昌赣高铁假期加紧施工 2019-05-25
  • 美国再挑贸易战,中方强力回击,全球市场跌声一片 2019-05-24
  • 【学习时刻学思践悟十九大①】人民大学马亮:在新时代增强党的改革创新本领 2019-05-24
  • 我们的节日2018端午——华龙网 2019-05-22
  • 当前位置 > CPDA数据分析师 > “数”业专攻 > 数据分析培训系列—分类算法之决策树(二)

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

    浙江快乐彩和值走势图 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

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

     

  • 发展改革委就创新和完善宏观调控等答问 2019-07-13
  • 深圳2018年将开行3趟援疆旅游扶贫专列 2019-07-01
  • 房地产就有国家和集体之土地不计价到计价,这笔是经济收入还是财产收入? 2019-07-01
  • Map Out Your Life in Chongqing 2019-06-28
  • 世界杯黄历:日本换帅对战黑马“小哥” 2019-06-27
  • 小区麻将馆 何时不扰民 2019-06-26
  • 纷纷“结缘”世界杯 家电企业图什么 2019-06-13
  • 推动吉台两地合作发展再上新台阶 2019-05-29
  • 中青报:父亲的“卖牛钱”被打赏 该如何管住孩子的手 2019-05-29
  • 任建明解读中纪委五次全会亮点 展望新时期反腐制度建设 2019-05-28
  • 全国首套房贷款利率连续17个月上升 2019-05-25
  • 昌赣高铁假期加紧施工 2019-05-25
  • 美国再挑贸易战,中方强力回击,全球市场跌声一片 2019-05-24
  • 【学习时刻学思践悟十九大①】人民大学马亮:在新时代增强党的改革创新本领 2019-05-24
  • 我们的节日2018端午——华龙网 2019-05-22
  • 广东时时彩论坛 网球比分网 香港马会资枓一肖中特三肖 江西多乐彩最大遗漏 浙江快乐12规则和奖金分配 体彩江苏7位数18127 快乐赛车是什么 黑龙江快乐十分开奖查询结果 河北11选5投注口诀 东方6十l中4个有奖金 北京快中彩开奖记录 免费单双中特 北京11选5计划软件破解版 11选5老时时彩快 辽宁11选5计划软件手机版式