17 丨决策树（上）：要不要去打篮球？决策树来告诉你

精选留言(54)

• 

  程序员小熊猫

  决策树学习通常包括三个步骤：
  1. 特征选择。选取最优特征来划分特征空间，用信息增益或者信息增益比来选择
  2. 决策树的生成。ID3、C4.5、CART
  3. 剪枝
  
  总结优缺点：
  ID3:
  优点：算法简单，通俗易懂
  缺陷：1. 无法处理缺失值
            2. 只能处理离散值，无法处理连续值
            3. 用信息增益作为划分规则，存在偏向于选择取值较多的特征。因为特征取值越多，说明划分的
                越细，不确定性越低，信息增益则越高
            4. 容易出现过拟合
  
  C4.5:
  优点：1. 能够处理缺省值
            2. 能对连续值做离散处理
            3. 使用信息增益比，能够避免偏向于选择取值较多的特征。因为信息增益比=信息增益/属性
                熵，属性熵是根据属性的取值来计算的，一相除就会抵消掉
            4. 在构造树的过程中，会剪枝，减少过拟合
  缺点：构造决策树，需要对数据进行多次扫描和排序，效率低
  
  学习的时候发现了这两点错误：
  1. Gain(D , 天气)=0 ---> 1
  Gain(D , 湿度)=0 ----> 1
  Gain(D , 刮风)=0.0615
  
  2. 针对将属性选择为温度的信息增益率为：
  Gain(D′, 温度)=Ent(D′)-0.792=1.0-0.792=-0.208
  这里算出来的还是信息增益，不是信息增益率，没有除以属性熵
  属性熵=-3/6log3/6 - 1/6log1/6 - 2/6log2/6
  
  作业：
  经验熵 H(D) = -1/2log1/2 - 1/2log1/2 = 1
  属性 红的信息增益：
  g(D, A1) = H(D) - H(D|A1)
               = 1 - 1/2*0 - 1/2 * 0
               = 1
  属性 大的信息增益：
  g(D,A2) = 1 - 1/2*(-1/2log1/2-1/2log1/2)*2
               = 0
  属性熵都是1，所以信息增益比跟信息增益一样
  特征选择 红作为最优特征，红的就是好苹果，不红的就是坏苹果
  
  

  2019-02-14

  

   34
• 

  志

  「红」的信息增益为：1
  「大」的信息增益为：0
  因此选择「红」的作为根节点，「大」作为子节点。接着再通过计算得出「大」作为子节点效果更差，故进行剪枝。因此最终的完整决策树就只有「红」一个节点：
  红（是）---好苹果（是）
  红（否）---好苹果（否）
  
  通过使用sklearn来验证一下：
  from sklearn import tree
  import sys
  import os
  import graphviz
  import numpy as np
  os.environ["PATH"] += os.pathsep + 'D:/Program Files/Anaconda3/Library/bin/graphviz'
  
  #创建数据[红，大]，1==是，0==否
  data = np.array([[1,1],[1,0],[0,1],[0,0]])
  #数据标注为，1==好苹果，0==坏苹果
  target = np.array([1,1,0,0])
  
  clf = tree.DecisionTreeClassifier() #创建决策树分类器模型
  clf = clf.fit(data, target) #拟合数据
  
  #最后利用graphviz库打印出决策树图
  dot_data = tree.export_graphviz(clf,out_file=None)
  graph = graphviz.Source(dot_data)
  graph

  2019-01-22

   1

   25
• 

  JingZ

  今天去面试一个金融分析师职位
  
  问：算法知道吗？
  我答：还在学习中，但我会python 爬虫，Numpy/Pandas~还有标准化(心想为嘛早上不认真看看今天的课程，起码说的出来C4.5是啥)😂😂
  
  以后要好好做作业~及时看课程

  2019-01-21

   1

   14
• 

  wonderland

  step1：将红作为属性来划分，有两个叶子节点D1，D2，分别对应是和否。用+代表是好苹果，-代表不是好苹果。
  故 D1 = {红=是}={1+，2+}，D2={红=否}={3-，4-};
  先分别计算2个叶子结点的信息熵：
  Ent（D1）=0，Ent（D2）=0，作为子节点的归一化信息熵为：1/2*0+1/2*0=0
  并且：训练集中有4条数据，2个是好苹果，2个不是，故根节点的信息熵为：Ent（D）=-（2/4*LOG2(2/4）+2/4*LOG2(2/4))=1
  step2：计算每个节点的信息增益
  Gain（D,红）=Ent（D）-0=1
  同理可得，大属性作为根节点的信息增益Gain（D，大）=0
  所以红作为属性的信息增益更大，选择红作为根节点。
  Step3：构造决策树
                   红
        是 否
  {1+，2+} {3-，4-}
  可以看到上面的决策树纯度已经很高，不需要进一步划分。所以最终的决策树即为下所示，只有红一个节点：
                        红
        是 否
  好苹果（是） 好苹果（否）
  

  2019-01-23

  

   11
• 

  李龍

  算法一点听不懂咋整

  2019-01-22

   1

   10
• 

  你看起来很好吃

  老师在计算ID3父节点为天气时信息熵的时候，每一项的系数是3/6,这里是不是错了，不应该是4/7和3/7吗？

  2019-01-21

  

   9
• 

  james

  Gain(D , 天气)=0, Gain(D , 湿度)=0, Gain(D , 刮风)=0.0615
  这个三个值计算错了吧？
  我计算的结果: Gain(D, 天气) = 1， Gain(D, 湿度) = 1， Gain(D, 刮风) = 0.3115,
  请老师指正

  2019-03-25

   1

   6
• 

  veical

  老师，C4.5的例子，属性熵是多少？如何计算的？

  2019-01-24

  

   6
• 

  aDongaDong

  脑瓜疼

  2019-04-18

   1

   5
• 

  滢

  根集合D = {2个好苹果，2个不是号苹果}，求得Ent(D) = 1。
  
  按红作为属性划分可得$D_1、D_2$两个子集
  
  $D_1$ (红 = 是) = {2个好苹果}
  
  $D_2$ (红= 否) = {2个不是好苹果}
  
  可得Ent( $D_1$ ) = 0 、Ent( $D_2$ ) = 0
  
  可得归一化信息熵为$\dfrac{1}{2} \times 0 + \dfrac{1}{2} \times 0 $ = 0
  
  则G(D,红) = 1-0 = 1
  
  按大作为属性，同样可得 $D_1、D_2$两个子集
  
  $D_1$ (大 = 是) = {1个好苹果，1个不是好苹果}
  
  $D_2$ (大 = 否) = {1个好苹果，1个不是好苹果}
  
  可得Ent( $D_1$ ) = 1 、Ent( $D_2$ ) = 1
  
  归一化信息熵 = $\dfrac{2}{4}\times1 + \dfrac{2}{4}\times1$ = 0.5
  
  则G（D，大）= 1- 0.5 = 0.5
  
  由此可得按红作为属性的信息增益大于按大作为属性的信息增益，所以选择红作为根节点。
  
  接着在红为是的基础上，分析按大作为属性的信息增益。在红为是的集合里共有两个苹果集合D = {2个好苹果} Ent(D) = 0
  
  $D_1$ (大 = 否) = {1个好苹果}
  
  $D_2$ (大 = 是) = {1个好苹果}
  
  Ent( $D_1$ ) = 0 、Ent( $D_2$ ) = 0
  
  G(D，大) = 0
  
  因为大是与否在红决定的前提下对好苹果的决定没有影响，所以剪去该分支。

  2019-04-17

  

   4
• 

  白夜

  > 如果你将天气作为属性的划分，会有三个叶子节点 D1、D2 和 D3，分别对应的是晴天、阴天和小雨。我们用 + 代表去打篮球，- 代表不去打篮球。那么第一条记录，晴天不去打篮球，可以记为 1-，于是我们可以用下面的方式来记录 D1，D2，D3：
  D1(天气 = 晴天)={1-,2-,6+}
  D2(天气 = 阴天)={3+,7-}
  D3(天气 = 小雨)={4+,5-}
  ----------------------
  建议例子举两个， 2-指的是第二天是不打篮球。 跳着看，看了好一会，才明白1-2-6+啥意思。 = =
  
  是==+ 否==-
  ENT(D)= -(1/2log1/2+1/2log1/2)=1
  D1(红=是)={1+,2+}
  D2(红=否)={3-,4-}
  ENT(D1)=0
  ENT(D2)=1
  Gain(D , 红)=1
  Gain(D , 大)=0
  红 作为父节点，大 没有作用，剪掉
  代码就不放了，抄了大伙的。
  同学们的代码少了一行，运行半天都没树出来。原来要打印出来的(；′⌒`)(Ｔ▽Ｔ)
  
  graph.render("tree")#在同目录下生成tree.pdf
  
  问一下老师，那个树我看不懂额。。要不解释一下gini和value
  
  

  2019-01-24

   2

   4
• 

  rainman

  在ID3算法那个例子中，当用“温度”作为根节点的时候，在温度为高的情况下，我计算的天气、湿度的信息增益都是1，而刮风为0.3115，所以这个子节点应该从天气或者湿度中选一个，我不明白为什么课程上写的结果是0、0、0.0615。望解答，谢谢。

  2019-02-14

   1

   3
• 

  云深不知处

  决策树算法，根据判别属性建立二叉树、多叉树，从根节点属性值开始，不断向下分支，根据中间子节点属性值判断，最终到达叶子节点实现分类目标。纯度和信息熵来判断属性值的不确定性，分类过程中，本质上是个算法收敛过程，如果算法收敛快，运算少，达到相同效果，肯定选择它。构建决策树，是确定跟节点、子节点、叶子节点过程，为了兼顾收敛和效果，通过信息增益计算值，判断某个节点作为根节点，信息熵最小，不确定性小，就是信息增益最大，收敛快。依靠此方法，逐步确定中间的子节点，最终的叶子节点就是分类结果。ID3算法缺点在于倾向测试集数值出现次数多，概率大，会造成错误分类，因为测试数据是抽象数据，不是全量数据，不能反应真是数据的全貌，从而出现过拟合现象。过拟合或者欠拟合问题，有点像评判好学生一样，如果数据样本都是清华北大学生，各方面都突出，维度多且高，预测好学生结果少，且都是985学生，收敛性强，最终区间少，过拟合；如果训练样本是单方面突出的学生，维度少，要求中等，模型预测结果是好学生的数据多，收敛性差，最终区间多，过拟合。为了避免抽象样本特殊性，不能代表真是数据情况，采用信息增益率方式，以百分比判断，算法c4.5就是这样一种方式。

  2019-06-17

  

   2
• 

  奔跑的徐胖子

  老师，我这里有个问题：在说C4.5算法的时候，您的例子是：D’的样本个数为6， D的样本个数为7， 那么利用D‘计算出来的信息增益率所占权重比例是6/7,所以 Gain(D, 温度) = 6/7*0.208 = 0.178。这样不对吧，应该是D’所占比例是6/7，所以Gain(D, 温度) = 0.208 / (7/6) 才对吧

  2019-03-27

   2

   2
• 

  sunny

  红的信息增益为：1
  大的信息增益为：0
  红比大更纯，红放决策树上面作为父节点，大放下面作为子节点

  2019-01-22

  

   2
• 

  ken

  苹果-大的信息熵：5/3
  苹果-红的信息熵：1
  归一化的信息熵：1
  苹果-大信息增益更大，作为根节点，红作为子节点。
  
  决策树：
  大（是）-红(是）-好苹果（是）
  大（是）-红(否）-好苹果（否）
  大（否）-红(是）-好苹果（是）
  大（否）-红（否）-好苹果（否）
  

  2019-01-21

  

   2
• 

  Destroy、

  老师看完有两个疑问：
  1、D：5个打篮球，5个不打篮球。为什么计算ent(D)概率是3/6呢？不应该是5/10吗？
  2、在介绍C4.5算法那部分，在计算ent(D1')的时候，两个概率都是3/6，不是1/3和2/3吗？难道我对信息熵的理解有误？

  2019-01-21

   1

   2
• 

  姜泮昌

  “然后我们要将上图中第一个叶节点，也就是 D1={1-,2-,3+,4+}进一步进行分裂，往下划分，计算其不同属性（天气、湿度、刮风）作为节点的信息增益”
  这里为什么父节点已经是温度了，子节点还要再计算温度属性呢？

  2019-05-11

  

   1
• 

  周飞

  1.根结点的信息熵是 -（1/2*log（1/2）+1/2*log（1/2） = 1
  2.假如以红来作为根结点，那么有两个叶子 红和不红，
  红的信息熵是 -（1*log（1））= 0
  不红的信息熵是 -(1*log(1)) = 0
  所以 以红作为根结点的信息增益是 1-0 = 1
  3.假如以大来作为根结点，那么有两个叶子节点： 大和不大
  大的信息熵是 -(1/2*log(1/2)+1/2*log(1/2)) = 1
  不大的信息熵是 -(1/2*log(1/2)+1/2*log(1/2)) = 1
  以大作为根结点的信息增益是 1- (1/2*1 +1/2*1) = 0;
  因为 以红作为根结点的信息增益大于以 大来作为根结点的信息增益，所以选择红来作为根结点。
  4.第一个叶子节点 的节点是大 ，第二个叶子节点的节点也是大。

  2019-03-02

  

   1
• 

  王彬成

  1、计算案例中的下一个节点的信息增益有疑惑：
  算得Gain(D , 天气)=1，与文章提到的Gain(D , 天气)=0矛盾，不知道哪里理解有误。
  2、作业
  苹果训练集中有4条数据，2个是好苹果，2个不是好苹果。
  根结点的信息熵是：1
  1）将“是为红”作为属性进行划分，有2个叶子结点D1和D2，分别对应‘是’红苹果，‘不是’红苹果。
  用+代表‘是’好苹果，-代表‘不是’好苹果。
  D1（红苹果->是）=【1+，2+】
  D2（红苹果->否）=【3-，4-】
  2个叶子节点的信息熵：
  Ent（D1）=0
  Ent（D2）=0
  子节点归一化信息熵=0
  所以，‘是红苹果’作为属性节点的信息增益为，Gain（D，是红苹果）=1
  2）将‘是大苹果’作为属性进行划分，2个叶子节点D1，D2对应‘是大苹果’，‘不是大苹果’。
  D1（大苹果->是）=【1+，3-】
  D2（大苹果->否）=【2+，4-】
  2个叶子节点的信息熵：
  Ent（D1）=1
  Ent（D2）=1
  子节点归一化信息熵=1
  所以，‘是大苹果’作为属性节点的信息增益为，Gain（D，是大苹果）=0.
  综上，‘是红苹果’作为属性的信息增益最大，所以将‘是红苹果’作为根节点。
  3）将D1（红苹果->是）=【1+，2+】进一步分裂，往下划分。
  得到Gain（D，大苹果）=0
  所以无需进一步划分。
  最终决策树。
  红苹果（是）-》好苹果（是）
  红苹果（否）-〉好苹果（否）

  2019-02-16

  

   1