0
0

决策树 （人工智能期末复习）

参考书：机器学习（周志华）

几个重要概念

  1. 信息熵

随机事件未按照某个属性的不同取值划分时的熵减去按照某个属性的不同取值划分时的平均熵。
表示事物的混乱程度，熵越大表示混乱程度越大，越小表示混乱程度越小。
对于随机事件，如果当前样本集合D中第k类样本所占的比例为 

  1.       p 
  2.      
  3.     
  4.       k 
  5.      
  6.     
  7.    
  8.   
  9.     {p_k} 
  10.    
  11.   
  12. pk​，那么D的信息熵为：

在这里插入图片描述
我们需要选择熵最小的。

  1. 信息增益——ID3

考虑到不同的分支结点所包含的样本数不同，我们给分支结点赋予权重| 

  1.       D 
  2.      
  3.     
  4.       v 
  5.      
  6.     
  7.    
  8.   
  9.     {D^v} 
  10.    
  11.   
  12. Dv| / | 
  13.  
  14.   
  15.    
  16.    
  17.      D 
  18.     
  19.    
  20.   
  21.     D 
  22.    
  23.   
  24. D|，可计算出用**属性a**对样本集D进行**划分**所获得的信息增益：

在这里插入图片描述
一般来说，信息增益越大，使用属性a 来进行划分所获得的“纯度提升”越大，因此我们需要选择信息增益最大的

  1. 信息增益率——C4.5

信息增益准则对可取值数目较多的属性有所偏好，为减少这种偏好可能带来的不利影响，我们考虑属性a的取值数目，
在这里插入图片描述
其中
在这里插入图片描述
增益率准则对可取值数目较少的属性有所偏好，在选择时，先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的

  1. 基尼系数——CART

数据集D的纯度可用基尼值来度量，它反映了从数据集D中随机抽取两个样本，其类别标记不一致的概率，因此，Gini(D)越小，数据集D的纯度越高

在这里插入图片描述
属性a的基尼指数定义为：
在这里插入图片描述
我们在候选属性集合A中，选择那个使得划分后基尼指数最小的属性作为最优划分属性。

例题

其实主要还是

  1. 背公式+计算不出错

，步骤基本上都差不多

(20年期末)设训练集如下表所示，请用经典的 ID3 算法 完成其学习过程。

在这里插入图片描述

题目还给出了：
在这里插入图片描述

使用ID3算法就只需要计算信息增益就好了，计算步骤如下：

**

  1. STEP1

** 第一步需要计算出集合D的总信息熵
在决策树学习开始时，根结点包含D中的所有样例，其中正例占 

  1.       p 
  2.      
  3.     
  4.       1 
  5.      
  6.     
  7.    
  8.   
  9.     p_1 
  10.    
  11.   
  12. p1​ =  
  13.  
  14.   
  15.    
  16.     
  17.     
  18.       3 
  19.      
  20.     
  21.       6 
  22.      
  23.     
  24.    
  25.   
  26.     3 \over 6 
  27.    
  28.   
  29. 63​ =  
  30.  
  31.   
  32.    
  33.     
  34.     
  35.       1 
  36.      
  37.     
  38.       2 
  39.      
  40.     
  41.    
  42.   
  43.     1 \over 2 
  44.    
  45.   
  46. 21​，反例占  
  47.  
  48.   
  49.    
  50.     
  51.     
  52.       p 
  53.      
  54.     
  55.       2 
  56.      
  57.     
  58.    
  59.   
  60.     p_2 
  61.    
  62.   
  63. p2​=  
  64.  
  65.   
  66.    
  67.     
  68.     
  69.       1 
  70.      
  71.     
  72.       2 
  73.      
  74.     
  75.    
  76.   
  77.     1 \over 2 
  78.    
  79.   
  80. 21​，于是根结点的信息熵为：

Ent(D) = -（ 

  1.       1 
  2.      
  3.     
  4.       2 
  5.      
  6.     
  7.    
  8.   
  9.     1 \over 2 
  10.    
  11.   
  12. 21​ log2 
  13.  
  14.   
  15.    
  16.     
  17.     
  18.       1 
  19.      
  20.     
  21.       2 
  22.      
  23.     
  24.    
  25.   
  26.     1 \over 2 
  27.    
  28.   
  29. 21​ +  
  30.  
  31.   
  32.    
  33.     
  34.     
  35.       1 
  36.      
  37.     
  38.       2 
  39.      
  40.     
  41.    
  42.   
  43.     1 \over 2 
  44.    
  45.   
  46. 21​ log2 
  47.  
  48.   
  49.    
  50.     
  51.     
  52.       1 
  53.      
  54.     
  55.       2 
  56.      
  57.     
  58.    
  59.   
  60.     1 \over 2 
  61.    
  62.   
  63. 21​) = 1

**

  1. STEP2

** 接下来计算每个属性的信息熵

属性 

  1.        x 
  2.       
  3.      
  4.        1 
  5.       
  6.      
  7.     
  8.    
  9.      {x_1} 
  10.     
  11.    
  12.  x1​：包含 
  13.  
  14.   
  15.    
  16.     
  17.     
  18.       D 
  19.      
  20.     
  21.       1 
  22.      
  23.     
  24.    
  25.   
  26.     {D^1} 
  27.    
  28.   
  29. D1（T）和 
  30.  
  31.   
  32.    
  33.     
  34.     
  35.       D 
  36.      
  37.     
  38.       2 
  39.      
  40.     
  41.    
  42.   
  43.     {D^2} 
  44.    
  45.   
  46. D2（F），各占 
  47.  
  48.   
  49.    
  50.     
  51.     
  52.       1 
  53.      
  54.     
  55.       2 
  56.      
  57.     
  58.    
  59.   
  60.     1 \over 2 
  61.    
  62.   
  63. 21​
  66.  
  67.   
  68.    
  69.     
  70.     
  71.       D 
  72.      
  73.     
  74.       1 
  75.      
  76.     
  77.    
  78.   
  79.     {D^1} 
  80.    
  81.   
  82. D1（T）：正例占 
  83.  
  84.   
  85.    
  86.     
  87.     
  88.       p 
  89.      
  90.     
  91.       1 
  92.      
  93.     
  94.    
  95.   
  96.     p_1 
  97.    
  98.   
  99. p1​ =  
  100.  
  101.   
  102.    
  103.     
  104.     
  105.       2 
  106.      
  107.     
  108.       3 
  109.      
  110.     
  111.    
  112.   
  113.     2 \over 3 
  114.    
  115.   
  116. 32​，反例占  
  117.  
  118.   
  119.    
  120.     
  121.     
  122.       p 
  123.      
  124.     
  125.       2 
  126.      
  127.     
  128.    
  129.   
  130.     p_2 
  131.    
  132.   
  133. p2​=  
  134.  
  135.   
  136.    
  137.     
  138.     
  139.       1 
  140.      
  141.     
  142.       3 
  143.      
  144.     
  145.    
  146.   
  147.     1 \over 3 
  148.    
  149.   
  150. 31​

**Ent( 

  1.        D 
  2.       
  3.      
  4.        1 
  5.       
  6.      
  7.     
  8.    
  9.      {D^1} 
  10.     
  11.    
  12.  D1) = -（ 
  13.   
  14.    
  15.     
  16.      
  17.      
  18.        2 
  19.       
  20.      
  21.        3 
  22.       
  23.      
  24.     
  25.    
  26.      2 \over 3 
  27.     
  28.    
  29.  32​ log2 
  30.   
  31.    
  32.     
  33.      
  34.      
  35.        2 
  36.       
  37.      
  38.        3 
  39.       
  40.      
  41.     
  42.    
  43.      2 \over 3 
  44.     
  45.    
  46.  32​ +  
  47.   
  48.    
  49.     
  50.      
  51.      
  52.        1 
  53.       
  54.      
  55.        3 
  56.       
  57.      
  58.     
  59.    
  60.      1 \over 3 
  61.     
  62.    
  63.  31​ log2 
  64.   
  65.    
  66.     
  67.      
  68.      
  69.        1 
  70.       
  71.      
  72.        3 
  73.       
  74.      
  75.     
  76.    
  77.      1 \over 3 
  78.     
  79.    
  80.  31​) = 0.9183**
  83.  
  84.   
  85.    
  86.     
  87.     
  88.       D 
  89.      
  90.     
  91.       2 
  92.      
  93.     
  94.    
  95.   
  96.     {D^2} 
  97.    
  98.   
  99. D2（F）：正例占 
  100.  
  101.   
  102.    
  103.     
  104.     
  105.       p 
  106.      
  107.     
  108.       1 
  109.      
  110.     
  111.    
  112.   
  113.     p_1 
  114.    
  115.   
  116. p1​ =  
  117.  
  118.   
  119.    
  120.     
  121.     
  122.       1 
  123.      
  124.     
  125.       3 
  126.      
  127.     
  128.    
  129.   
  130.     1 \over 3 
  131.    
  132.   
  133. 31​，反例占  
  134.  
  135.   
  136.    
  137.     
  138.     
  139.       p 
  140.      
  141.     
  142.       2 
  143.      
  144.     
  145.    
  146.   
  147.     p_2 
  148.    
  149.   
  150. p2​=  
  151.  
  152.   
  153.    
  154.     
  155.     
  156.       2 
  157.      
  158.     
  159.       3 
  160.      
  161.     
  162.    
  163.   
  164.     2 \over 3 
  165.    
  166.   
  167. 32​

**Ent( 

  1.        D 
  2.       
  3.      
  4.        2 
  5.       
  6.      
  7.     
  8.    
  9.      {D^2} 
  10.     
  11.    
  12.  D2) = -（ 
  13.   
  14.    
  15.     
  16.      
  17.      
  18.        1 
  19.       
  20.      
  21.        3 
  22.       
  23.      
  24.     
  25.    
  26.      1 \over 3 
  27.     
  28.    
  29.  31​ log2 
  30.   
  31.    
  32.     
  33.      
  34.      
  35.        1 
  36.       
  37.      
  38.        3 
  39.       
  40.      
  41.     
  42.    
  43.      1 \over 3 
  44.     
  45.    
  46.  31​ +  
  47.   
  48.    
  49.     
  50.      
  51.      
  52.        2 
  53.       
  54.      
  55.        3 
  56.       
  57.      
  58.     
  59.    
  60.      2 \over 3 
  61.     
  62.    
  63.  32​ log2 
  64.   
  65.    
  66.     
  67.      
  68.      
  69.        2 
  70.       
  71.      
  72.        3 
  73.       
  74.      
  75.     
  76.    
  77.      2 \over 3 
  78.     
  79.    
  80.  32​) = 0.9183**

因此**Ent( 

  1.        x 
  2.       
  3.      
  4.        1 
  5.       
  6.      
  7.     
  8.    
  9.      {x_1} 
  10.     
  11.    
  12.  x1​) =  
  13.   
  14.    
  15.     
  16.      
  17.      
  18.        1 
  19.       
  20.      
  21.        2 
  22.       
  23.      
  24.     
  25.    
  26.      1 \over 2 
  27.     
  28.    
  29.  21​Ent( 
  30.   
  31.    
  32.     
  33.      
  34.      
  35.        D 
  36.       
  37.      
  38.        1 
  39.       
  40.      
  41.     
  42.    
  43.      {D^1} 
  44.     
  45.    
  46.  D1) + 
  47.   
  48.    
  49.     
  50.      
  51.      
  52.        1 
  53.       
  54.      
  55.        2 
  56.       
  57.      
  58.     
  59.    
  60.      1 \over 2 
  61.     
  62.    
  63.  21​Ent( 
  64.   
  65.    
  66.     
  67.      
  68.      
  69.        D 
  70.       
  71.      
  72.        2 
  73.       
  74.      
  75.     
  76.    
  77.      {D^2} 
  78.     
  79.    
  80.  D2) = 0.9183**

属性 

  1.        x 
  2.       
  3.      
  4.        2 
  5.       
  6.      
  7.     
  8.    
  9.      {x_2} 
  10.     
  11.    
  12.  x2​：包含 
  13.  
  14.   
  15.    
  16.     
  17.     
  18.       D 
  19.      
  20.     
  21.       1 
  22.      
  23.     
  24.    
  25.   
  26.     {D^1} 
  27.    
  28.   
  29. D1（T）和 
  30.  
  31.   
  32.    
  33.     
  34.     
  35.       D 
  36.      
  37.     
  38.       2 
  39.      
  40.     
  41.    
  42.   
  43.     {D^2} 
  44.    
  45.   
  46. D2（F），分别占 
  47.  
  48.   
  49.    
  50.     
  51.     
  52.       2 
  53.      
  54.     
  55.       3 
  56.      
  57.     
  58.    
  59.   
  60.     2 \over 3 
  61.    
  62.   
  63. 32​和 
  64.  
  65.   
  66.    
  67.     
  68.     
  69.       1 
  70.      
  71.     
  72.       3 
  73.      
  74.     
  75.    
  76.   
  77.     1 \over 3 
  78.    
  79.   
  80. 31​
  83.  
  84.   
  85.    
  86.     
  87.     
  88.       D 
  89.      
  90.     
  91.       1 
  92.      
  93.     
  94.    
  95.   
  96.     {D^1} 
  97.    
  98.   
  99. D1（T）：正例占 
  100.  
  101.   
  102.    
  103.     
  104.     
  105.       p 
  106.      
  107.     
  108.       1 
  109.      
  110.     
  111.    
  112.   
  113.     p_1 
  114.    
  115.   
  116. p1​ =  
  117.  
  118.   
  119.    
  120.     
  121.     
  122.       1 
  123.      
  124.     
  125.       2 
  126.      
  127.     
  128.    
  129.   
  130.     1 \over 2 
  131.    
  132.   
  133. 21​，反例占  
  134.  
  135.   
  136.    
  137.     
  138.     
  139.       p 
  140.      
  141.     
  142.       2 
  143.      
  144.     
  145.    
  146.   
  147.     p_2 
  148.    
  149.   
  150. p2​=  
  151.  
  152.   
  153.    
  154.     
  155.     
  156.       1 
  157.      
  158.     
  159.       2 
  160.      
  161.     
  162.    
  163.   
  164.     1 \over 2 
  165.    
  166.   
  167. 21​

**Ent( 

  1.        D 
  2.       
  3.      
  4.        1 
  5.       
  6.      
  7.     
  8.    
  9.      {D^1} 
  10.     
  11.    
  12.  D1) = -（ 
  13.   
  14.    
  15.     
  16.      
  17.      
  18.        1 
  19.       
  20.      
  21.        2 
  22.       
  23.      
  24.     
  25.    
  26.      1 \over 2 
  27.     
  28.    
  29.  21​ log2 
  30.   
  31.    
  32.     
  33.      
  34.      
  35.        1 
  36.       
  37.      
  38.        2 
  39.       
  40.      
  41.     
  42.    
  43.      1 \over 2 
  44.     
  45.    
  46.  21​ +  
  47.   
  48.    
  49.     
  50.      
  51.      
  52.        1 
  53.       
  54.      
  55.        2 
  56.       
  57.      
  58.     
  59.    
  60.      1 \over 2 
  61.     
  62.    
  63.  21​ log2 
  64.   
  65.    
  66.     
  67.      
  68.      
  69.        1 
  70.       
  71.      
  72.        2 
  73.       
  74.      
  75.     
  76.    
  77.      1 \over 2 
  78.     
  79.    
  80.  21​) = 1**
  83.  
  84.   
  85.    
  86.     
  87.     
  88.       D 
  89.      
  90.     
  91.       2 
  92.      
  93.     
  94.    
  95.   
  96.     {D^2} 
  97.    
  98.   
  99. D2（F）：正例占 
  100.  
  101.   
  102.    
  103.     
  104.     
  105.       p 
  106.      
  107.     
  108.       1 
  109.      
  110.     
  111.    
  112.   
  113.     p_1 
  114.    
  115.   
  116. p1​ =  
  117.  
  118.   
  119.    
  120.     
  121.     
  122.       1 
  123.      
  124.     
  125.       2 
  126.      
  127.     
  128.    
  129.   
  130.     1 \over 2 
  131.    
  132.   
  133. 21​，反例占  
  134.  
  135.   
  136.    
  137.     
  138.     
  139.       p 
  140.      
  141.     
  142.       2 
  143.      
  144.     
  145.    
  146.   
  147.     p_2 
  148.    
  149.   
  150. p2​=  
  151.  
  152.   
  153.    
  154.     
  155.     
  156.       1 
  157.      
  158.     
  159.       2 
  160.      
  161.     
  162.    
  163.   
  164.     1 \over 2 
  165.    
  166.   
  167. 21​

**Ent( 

  1.        D 
  2.       
  3.      
  4.        2 
  5.       
  6.      
  7.     
  8.    
  9.      {D^2} 
  10.     
  11.    
  12.  D2) = -（ 
  13.   
  14.    
  15.     
  16.      
  17.      
  18.        1 
  19.       
  20.      
  21.        2 
  22.       
  23.      
  24.     
  25.    
  26.      1 \over 2 
  27.     
  28.    
  29.  21​ log2 
  30.   
  31.    
  32.     
  33.      
  34.      
  35.        1 
  36.       
  37.      
  38.        2 
  39.       
  40.      
  41.     
  42.    
  43.      1 \over 2 
  44.     
  45.    
  46.  21​ +  
  47.   
  48.    
  49.     
  50.      
  51.      
  52.        1 
  53.       
  54.      
  55.        2 
  56.       
  57.      
  58.     
  59.    
  60.      1 \over 2 
  61.     
  62.    
  63.  21​ log2 
  64.   
  65.    
  66.     
  67.      
  68.      
  69.        1 
  70.       
  71.      
  72.        2 
  73.       
  74.      
  75.     
  76.    
  77.      1 \over 2 
  78.     
  79.    
  80.  21​) = 1**

因此**Ent( 

  1.        x 
  2.       
  3.      
  4.        2 
  5.       
  6.      
  7.     
  8.    
  9.      {x_2} 
  10.     
  11.    
  12.  x2​) =  
  13.   
  14.    
  15.     
  16.      
  17.      
  18.        2 
  19.       
  20.      
  21.        3 
  22.       
  23.      
  24.     
  25.    
  26.      2 \over 3 
  27.     
  28.    
  29.  32​Ent( 
  30.   
  31.    
  32.     
  33.      
  34.      
  35.        D 
  36.       
  37.      
  38.        1 
  39.       
  40.      
  41.     
  42.    
  43.      {D^1} 
  44.     
  45.    
  46.  D1) + 
  47.   
  48.    
  49.     
  50.      
  51.      
  52.        1 
  53.       
  54.      
  55.        3 
  56.       
  57.      
  58.     
  59.    
  60.      1 \over 3 
  61.     
  62.    
  63.  31​Ent( 
  64.   
  65.    
  66.     
  67.      
  68.      
  69.        D 
  70.       
  71.      
  72.        2 
  73.       
  74.      
  75.     
  76.    
  77.      {D^2} 
  78.     
  79.    
  80.  D2) = 1**

**

  1. STEP3

** 最后计算每个属性的信息增益
Gain（D， 

  1.       x 
  2.      
  3.     
  4.       1 
  5.      
  6.     
  7.    
  8.   
  9.     {x_1} 
  10.    
  11.   
  12. x1​）=Ent(D) - Ent( 
  13.  
  14.   
  15.    
  16.     
  17.     
  18.       x 
  19.      
  20.     
  21.       1 
  22.      
  23.     
  24.    
  25.   
  26.     {x_1} 
  27.    
  28.   
  29. x1​) = 1 - 0.9183 = 0.0817

Gain（D， 

  1.       x 
  2.      
  3.     
  4.       2 
  5.      
  6.     
  7.    
  8.   
  9.     {x_2} 
  10.    
  11.   
  12. x2​）=Ent(D) - Ent( 
  13.  
  14.   
  15.    
  16.     
  17.     
  18.       x 
  19.      
  20.     
  21.       2 
  22.      
  23.     
  24.    
  25.   
  26.     {x_2} 
  27.    
  28.   
  29. x2​) = 1-1 = 1

选择信息增益大的作为第一个属性，即选择属性 

  1.       x 
  2.      
  3.     
  4.       1 
  5.      
  6.     
  7.    
  8.   
  9.     {x_1} 
  10.    
  11.   
  12. x1​对根节点进行扩展

在这里插入图片描述
扩展 

  1.       x 
  2.      
  3.     
  4.       1 
  5.      
  6.     
  7.    
  8.   
  9.     {x_1} 
  10.    
  11.   
  12. x1​之后还未得到最终方案结果，只剩 
  13.  
  14.   
  15.    
  16.     
  17.     
  18.       x 
  19.      
  20.     
  21.       2 
  22.      
  23.     
  24.    
  25.   
  26.     {x_2} 
  27.    
  28.   
  29. x2​属性可拓展，因此不需要再进行条件熵的计算，对 
  30.  
  31.   
  32.    
  33.     
  34.     
  35.       x 
  36.      
  37.     
  38.       2 
  39.      
  40.     
  41.    
  42.   
  43.     {x_2} 
  44.    
  45.   
  46. x2​扩展后所得到的决策树如下图所示：

在这里插入图片描述

(19年)下表给出外国菜是否有吸引力的数据集，每个菜品有 3 个属性“温度”、“口味”，“份量”，请用决策树算法画出决策树（根据信息增益）。并预测 dish= {温度=热，口味=甜，份量=大} 的一道菜，是否具有吸引力。

在这里插入图片描述

这题也是根据信息增益选择属性，和上一题步骤一样
**

  1. STEP1

** 第一步计算出集合D的总信息熵
根结点包含10个样例，其中正例占 

  1.       p 
  2.      
  3.     
  4.       1 
  5.      
  6.     
  7.    
  8.   
  9.     p_1 
  10.    
  11.   
  12. p1​ =  
  13.  
  14.   
  15.    
  16.     
  17.     
  18.       1 
  19.      
  20.     
  21.       2 
  22.      
  23.     
  24.    
  25.   
  26.     1 \over 2 
  27.    
  28.   
  29. 21​ ，反例占  
  30.  
  31.   
  32.    
  33.     
  34.     
  35.       p 
  36.      
  37.     
  38.       2 
  39.      
  40.     
  41.    
  42.   
  43.     p_2 
  44.    
  45.   
  46. p2​=  
  47.  
  48.   
  49.    
  50.     
  51.     
  52.       1 
  53.      
  54.     
  55.       2 
  56.      
  57.     
  58.    
  59.   
  60.     1 \over 2 
  61.    
  62.   
  63. 21​，于是根结点的信息熵为：

Ent(D) = -（ 

  1.       1 
  2.      
  3.     
  4.       2 
  5.      
  6.     
  7.    
  8.   
  9.     1 \over 2 
  10.    
  11.   
  12. 21​ log2 
  13.  
  14.   
  15.    
  16.     
  17.     
  18.       1 
  19.      
  20.     
  21.       2 
  22.      
  23.     
  24.    
  25.   
  26.     1 \over 2 
  27.    
  28.   
  29. 21​ +  
  30.  
  31.   
  32.    
  33.     
  34.     
  35.       1 
  36.      
  37.     
  38.       2 
  39.      
  40.     
  41.    
  42.   
  43.     1 \over 2 
  44.    
  45.   
  46. 21​ log2 
  47.  
  48.   
  49.    
  50.     
  51.     
  52.       1 
  53.      
  54.     
  55.       2 
  56.      
  57.     
  58.    
  59.   
  60.     1 \over 2 
  61.    
  62.   
  63. 21​) = 1

**

  1. STEP2

** 接下来计算每个属性的条件熵

温度属性：包含 

  1.       D 
  2.      
  3.     
  4.       1 
  5.      
  6.     
  7.    
  8.   
  9.     {D^1} 
  10.    
  11.   
  12. D1（冷）和 
  13.  
  14.   
  15.    
  16.     
  17.     
  18.       D 
  19.      
  20.     
  21.       2 
  22.      
  23.     
  24.    
  25.   
  26.     {D^2} 
  27.    
  28.   
  29. D2（热），各占 
  30.  
  31.   
  32.    
  33.     
  34.     
  35.       1 
  36.      
  37.     
  38.       2 
  39.      
  40.     
  41.    
  42.   
  43.     1 \over 2 
  44.    
  45.   
  46. 21​
  49.  
  50.   
  51.    
  52.     
  53.     
  54.       D 
  55.      
  56.     
  57.       1 
  58.      
  59.     
  60.    
  61.   
  62.     {D^1} 
  63.    
  64.   
  65. D1（冷）：正例占 
  66.  
  67.   
  68.    
  69.     
  70.     
  71.       p 
  72.      
  73.     
  74.       1 
  75.      
  76.     
  77.    
  78.   
  79.     p_1 
  80.    
  81.   
  82. p1​ =  
  83.  
  84.   
  85.    
  86.     
  87.     
  88.       3 
  89.      
  90.     
  91.       5 
  92.      
  93.     
  94.    
  95.   
  96.     3 \over 5 
  97.    
  98.   
  99. 53​，反例占  
  100.  
  101.   
  102.    
  103.     
  104.     
  105.       p 
  106.      
  107.     
  108.       2 
  109.      
  110.     
  111.    
  112.   
  113.     p_2 
  114.    
  115.   
  116. p2​=  
  117.  
  118.   
  119.    
  120.     
  121.     
  122.       2 
  123.      
  124.     
  125.       5 
  126.      
  127.     
  128.    
  129.   
  130.     2 \over 5 
  131.    
  132.   
  133. 52​

**Ent( 

  1.        D 
  2.       
  3.      
  4.        1 
  5.       
  6.      
  7.     
  8.    
  9.      {D^1} 
  10.     
  11.    
  12.  D1) = -（ 
  13.   
  14.    
  15.     
  16.      
  17.      
  18.        3 
  19.       
  20.      
  21.        5 
  22.       
  23.      
  24.     
  25.    
  26.      3 \over 5 
  27.     
  28.    
  29.  53​ log2 
  30.   
  31.    
  32.     
  33.      
  34.      
  35.        3 
  36.       
  37.      
  38.        5 
  39.       
  40.      
  41.     
  42.    
  43.      3 \over 5 
  44.     
  45.    
  46.  53​ +  
  47.   
  48.    
  49.     
  50.      
  51.      
  52.        2 
  53.       
  54.      
  55.        5 
  56.       
  57.      
  58.     
  59.    
  60.      2 \over 5 
  61.     
  62.    
  63.  52​ log2 
  64.   
  65.    
  66.     
  67.      
  68.      
  69.        2 
  70.       
  71.      
  72.        5 
  73.       
  74.      
  75.     
  76.    
  77.      2 \over 5 
  78.     
  79.    
  80.  52​) = 0.971**
  83.  
  84.   
  85.    
  86.     
  87.     
  88.       D 
  89.      
  90.     
  91.       2 
  92.      
  93.     
  94.    
  95.   
  96.     {D^2} 
  97.    
  98.   
  99. D2（热）：正例占 
  100.  
  101.   
  102.    
  103.     
  104.     
  105.       p 
  106.      
  107.     
  108.       1 
  109.      
  110.     
  111.    
  112.   
  113.     p_1 
  114.    
  115.   
  116. p1​ =  
  117.  
  118.   
  119.    
  120.     
  121.     
  122.       2 
  123.      
  124.     
  125.       5 
  126.      
  127.     
  128.    
  129.   
  130.     2 \over 5 
  131.    
  132.   
  133. 52​，反例占  
  134.  
  135.   
  136.    
  137.     
  138.     
  139.       p 
  140.      
  141.     
  142.       2 
  143.      
  144.     
  145.    
  146.   
  147.     p_2 
  148.    
  149.   
  150. p2​=  
  151.  
  152.   
  153.    
  154.     
  155.     
  156.       3 
  157.      
  158.     
  159.       5 
  160.      
  161.     
  162.    
  163.   
  164.     3 \over 5 
  165.    
  166.   
  167. 53​

**Ent( 

  1.        D 
  2.       
  3.      
  4.        2 
  5.       
  6.      
  7.     
  8.    
  9.      {D^2} 
  10.     
  11.    
  12.  D2) = -（ 
  13.   
  14.    
  15.     
  16.      
  17.      
  18.        2 
  19.       
  20.      
  21.        5 
  22.       
  23.      
  24.     
  25.    
  26.      2 \over 5 
  27.     
  28.    
  29.  52​ log2 
  30.   
  31.    
  32.     
  33.      
  34.      
  35.        2 
  36.       
  37.      
  38.        5 
  39.       
  40.      
  41.     
  42.    
  43.      2 \over 5 
  44.     
  45.    
  46.  52​ +  
  47.   
  48.    
  49.     
  50.      
  51.      
  52.        3 
  53.       
  54.      
  55.        5 
  56.       
  57.      
  58.     
  59.    
  60.      3 \over 5 
  61.     
  62.    
  63.  53​ log2 
  64.   
  65.    
  66.     
  67.      
  68.      
  69.        3 
  70.       
  71.      
  72.        5 
  73.       
  74.      
  75.     
  76.    
  77.      3 \over 5 
  78.     
  79.    
  80.  53​) = 0.971**

因此**Ent(温度) = 

  1.        1 
  2.       
  3.      
  4.        2 
  5.       
  6.      
  7.     
  8.    
  9.      1 \over 2 
  10.     
  11.    
  12.  21​Ent( 
  13.   
  14.    
  15.     
  16.      
  17.      
  18.        D 
  19.       
  20.      
  21.        1 
  22.       
  23.      
  24.     
  25.    
  26.      {D^1} 
  27.     
  28.    
  29.  D1) + 
  30.   
  31.    
  32.     
  33.      
  34.      
  35.        1 
  36.       
  37.      
  38.        2 
  39.       
  40.      
  41.     
  42.    
  43.      1 \over 2 
  44.     
  45.    
  46.  21​Ent( 
  47.   
  48.    
  49.     
  50.      
  51.      
  52.        D 
  53.       
  54.      
  55.        2 
  56.       
  57.      
  58.     
  59.    
  60.      {D^2} 
  61.     
  62.    
  63.  D2) = 0.971**

份量属性：包含 

  1.       D 
  2.      
  3.     
  4.       1 
  5.      
  6.     
  7.    
  8.   
  9.     {D^1} 
  10.    
  11.   
  12. D1（大）和 
  13.  
  14.   
  15.    
  16.     
  17.     
  18.       D 
  19.      
  20.     
  21.       2 
  22.      
  23.     
  24.    
  25.   
  26.     {D^2} 
  27.    
  28.   
  29. D2（小），各占 
  30.  
  31.   
  32.    
  33.     
  34.     
  35.       1 
  36.      
  37.     
  38.       2 
  39.      
  40.     
  41.    
  42.   
  43.     1 \over 2 
  44.    
  45.   
  46. 21​
  49.  
  50.   
  51.    
  52.     
  53.     
  54.       D 
  55.      
  56.     
  57.       1 
  58.      
  59.     
  60.    
  61.   
  62.     {D^1} 
  63.    
  64.   
  65. D1（冷）：正例占 
  66.  
  67.   
  68.    
  69.     
  70.     
  71.       p 
  72.      
  73.     
  74.       1 
  75.      
  76.     
  77.    
  78.   
  79.     p_1 
  80.    
  81.   
  82. p1​ =  
  83.  
  84.   
  85.    
  86.     
  87.     
  88.       1 
  89.      
  90.     
  91.       5 
  92.      
  93.     
  94.    
  95.   
  96.     1 \over 5 
  97.    
  98.   
  99. 51​，反例占  
  100.  
  101.   
  102.    
  103.     
  104.     
  105.       p 
  106.      
  107.     
  108.       2 
  109.      
  110.     
  111.    
  112.   
  113.     p_2 
  114.    
  115.   
  116. p2​=  
  117.  
  118.   
  119.    
  120.     
  121.     
  122.       4 
  123.      
  124.     
  125.       5 
  126.      
  127.     
  128.    
  129.   
  130.     4 \over 5 
  131.    
  132.   
  133. 54​

**Ent( 

  1.        D 
  2.       
  3.      
  4.        1 
  5.       
  6.      
  7.     
  8.    
  9.      {D^1} 
  10.     
  11.    
  12.  D1) = -（ 
  13.   
  14.    
  15.     
  16.      
  17.      
  18.        1 
  19.       
  20.      
  21.        5 
  22.       
  23.      
  24.     
  25.    
  26.      1 \over 5 
  27.     
  28.    
  29.  51​ log2 
  30.   
  31.    
  32.     
  33.      
  34.      
  35.        1 
  36.       
  37.      
  38.        5 
  39.       
  40.      
  41.     
  42.    
  43.      1\over 5 
  44.     
  45.    
  46.  51​ +  
  47.   
  48.    
  49.     
  50.      
  51.      
  52.        4 
  53.       
  54.      
  55.        5 
  56.       
  57.      
  58.     
  59.    
  60.      4 \over 5 
  61.     
  62.    
  63.  54​ log2 
  64.   
  65.    
  66.     
  67.      
  68.      
  69.        4 
  70.       
  71.      
  72.        5 
  73.       
  74.      
  75.     
  76.    
  77.      4 \over 5 
  78.     
  79.    
  80.  54​) = 0.722**
  83.  
  84.   
  85.    
  86.     
  87.     
  88.       D 
  89.      
  90.     
  91.       2 
  92.      
  93.     
  94.    
  95.   
  96.     {D^2} 
  97.    
  98.   
  99. D2（热）：正例占 
  100.  
  101.   
  102.    
  103.     
  104.     
  105.       p 
  106.      
  107.     
  108.       1 
  109.      
  110.     
  111.    
  112.   
  113.     p_1 
  114.    
  115.   
  116. p1​ =  
  117.  
  118.   
  119.    
  120.     
  121.     
  122.       4 
  123.      
  124.     
  125.       5 
  126.      
  127.     
  128.    
  129.   
  130.     4 \over 5 
  131.    
  132.   
  133. 54​，反例占  
  134.  
  135.   
  136.    
  137.     
  138.     
  139.       p 
  140.      
  141.     
  142.       2 
  143.      
  144.     
  145.    
  146.   
  147.     p_2 
  148.    
  149.   
  150. p2​=  
  151.  
  152.   
  153.    
  154.     
  155.     
  156.       1 
  157.      
  158.     
  159.       5 
  160.      
  161.     
  162.    
  163.   
  164.     1 \over 5 
  165.    
  166.   
  167. 51​

**Ent( 

  1.        D 
  2.       
  3.      
  4.        2 
  5.       
  6.      
  7.     
  8.    
  9.      {D^2} 
  10.     
  11.    
  12.  D2) = -（ 
  13.   
  14.    
  15.     
  16.      
  17.      
  18.        4 
  19.       
  20.      
  21.        5 
  22.       
  23.      
  24.     
  25.    
  26.      4 \over 5 
  27.     
  28.    
  29.  54​ log2 
  30.   
  31.    
  32.     
  33.      
  34.      
  35.        4 
  36.       
  37.      
  38.        5 
  39.       
  40.      
  41.     
  42.    
  43.      4 \over 5 
  44.     
  45.    
  46.  54​ +  
  47.   
  48.    
  49.     
  50.      
  51.      
  52.        1 
  53.       
  54.      
  55.        5 
  56.       
  57.      
  58.     
  59.    
  60.      1 \over 5 
  61.     
  62.    
  63.  51​ log2 
  64.   
  65.    
  66.     
  67.      
  68.      
  69.        1 
  70.       
  71.      
  72.        5 
  73.       
  74.      
  75.     
  76.    
  77.      1 \over 5 
  78.     
  79.    
  80.  51​) = 0.722**

因此**Ent(份量) = 

  1.        1 
  2.       
  3.      
  4.        2 
  5.       
  6.      
  7.     
  8.    
  9.      1 \over 2 
  10.     
  11.    
  12.  21​Ent( 
  13.   
  14.    
  15.     
  16.      
  17.      
  18.        D 
  19.       
  20.      
  21.        1 
  22.       
  23.      
  24.     
  25.    
  26.      {D^1} 
  27.     
  28.    
  29.  D1) + 
  30.   
  31.    
  32.     
  33.      
  34.      
  35.        1 
  36.       
  37.      
  38.        2 
  39.       
  40.      
  41.     
  42.    
  43.      1 \over 2 
  44.     
  45.    
  46.  21​Ent( 
  47.   
  48.    
  49.     
  50.      
  51.      
  52.        D 
  53.       
  54.      
  55.        2 
  56.       
  57.      
  58.     
  59.    
  60.      {D^2} 
  61.     
  62.    
  63.  D2) = 0.722**

口味属性：包含 

  1.       D 
  2.      
  3.     
  4.       1 
  5.      
  6.     
  7.    
  8.   
  9.     {D^1} 
  10.    
  11.   
  12. D1（咸）和 
  13.  
  14.   
  15.    
  16.     
  17.     
  18.       D 
  19.      
  20.     
  21.       2 
  22.      
  23.     
  24.    
  25.   
  26.     {D^2} 
  27.    
  28.   
  29. D2（甜）和 
  30.  
  31.   
  32.    
  33.     
  34.     
  35.       D 
  36.      
  37.     
  38.       3 
  39.      
  40.     
  41.    
  42.   
  43.     {D^3} 
  44.    
  45.   
  46. D3（酸），分别占 
  47.  
  48.   
  49.    
  50.     
  51.     
  52.       3 
  53.      
  54.     
  55.       10 
  56.      
  57.     
  58.    
  59.   
  60.     3 \over 10 
  61.    
  62.   
  63. 103​、 
  64.  
  65.   
  66.    
  67.     
  68.     
  69.       4 
  70.      
  71.     
  72.       10 
  73.      
  74.     
  75.    
  76.   
  77.     4 \over 10 
  78.    
  79.   
  80. 104​和 
  81.  
  82.   
  83.    
  84.     
  85.     
  86.       3 
  87.      
  88.     
  89.       10 
  90.      
  91.     
  92.    
  93.   
  94.     3 \over 10 
  95.    
  96.   
  97. 103​
  100.  
  101.   
  102.    
  103.     
  104.     
  105.       D 
  106.      
  107.     
  108.       1 
  109.      
  110.     
  111.    
  112.   
  113.     {D^1} 
  114.    
  115.   
  116. D1（咸）：正例占 
  117.  
  118.   
  119.    
  120.     
  121.     
  122.       p 
  123.      
  124.     
  125.       1 
  126.      
  127.     
  128.    
  129.   
  130.     p_1 
  131.    
  132.   
  133. p1​ = 0，反例占  
  134.  
  135.   
  136.    
  137.     
  138.     
  139.       p 
  140.      
  141.     
  142.       2 
  143.      
  144.     
  145.    
  146.   
  147.     p_2 
  148.    
  149.   
  150. p2​= 1

**Ent( 

  1.        D 
  2.       
  3.      
  4.        1 
  5.       
  6.      
  7.     
  8.    
  9.      {D^1} 
  10.     
  11.    
  12.  D1) = 0**
  15.  
  16.   
  17.    
  18.     
  19.     
  20.       D 
  21.      
  22.     
  23.       2 
  24.      
  25.     
  26.    
  27.   
  28.     {D^2} 
  29.    
  30.   
  31. D2（甜）：正例占 
  32.  
  33.   
  34.    
  35.     
  36.     
  37.       p 
  38.      
  39.     
  40.       1 
  41.      
  42.     
  43.    
  44.   
  45.     p_1 
  46.    
  47.   
  48. p1​ =  
  49.  
  50.   
  51.    
  52.     
  53.     
  54.       1 
  55.      
  56.     
  57.       2 
  58.      
  59.     
  60.    
  61.   
  62.     1 \over 2 
  63.    
  64.   
  65. 21​，反例占  
  66.  
  67.   
  68.    
  69.     
  70.     
  71.       p 
  72.      
  73.     
  74.       2 
  75.      
  76.     
  77.    
  78.   
  79.     p_2 
  80.    
  81.   
  82. p2​=  
  83.  
  84.   
  85.    
  86.     
  87.     
  88.       1 
  89.      
  90.     
  91.       2 
  92.      
  93.     
  94.    
  95.   
  96.     1 \over 2 
  97.    
  98.   
  99. 21​

**Ent( 

  1.        D 
  2.       
  3.      
  4.        2 
  5.       
  6.      
  7.     
  8.    
  9.      {D^2} 
  10.     
  11.    
  12.  D2) = -（ 
  13.   
  14.    
  15.     
  16.      
  17.      
  18.        1 
  19.       
  20.      
  21.        2 
  22.       
  23.      
  24.     
  25.    
  26.      1 \over 2 
  27.     
  28.    
  29.  21​ log2 
  30.   
  31.    
  32.     
  33.      
  34.      
  35.        1 
  36.       
  37.      
  38.        2 
  39.       
  40.      
  41.     
  42.    
  43.      1 \over 2 
  44.     
  45.    
  46.  21​ +  
  47.   
  48.    
  49.     
  50.      
  51.      
  52.        1 
  53.       
  54.      
  55.        2 
  56.       
  57.      
  58.     
  59.    
  60.      1 \over 2 
  61.     
  62.    
  63.  21​ log2 
  64.   
  65.    
  66.     
  67.      
  68.      
  69.        1 
  70.       
  71.      
  72.        2 
  73.       
  74.      
  75.     
  76.    
  77.      1 \over 2 
  78.     
  79.    
  80.  21​) = 1**
  83.  
  84.   
  85.    
  86.     
  87.     
  88.       D 
  89.      
  90.     
  91.       3 
  92.      
  93.     
  94.    
  95.   
  96.     {D^3} 
  97.    
  98.   
  99. D3（酸）：正例占 
  100.  
  101.   
  102.    
  103.     
  104.     
  105.       p 
  106.      
  107.     
  108.       1 
  109.      
  110.     
  111.    
  112.   
  113.     p_1 
  114.    
  115.   
  116. p1​ = 1，反例占  
  117.  
  118.   
  119.    
  120.     
  121.     
  122.       p 
  123.      
  124.     
  125.       2 
  126.      
  127.     
  128.    
  129.   
  130.     p_2 
  131.    
  132.   
  133. p2​= 0

**Ent( 

  1.        D 
  2.       
  3.      
  4.        3 
  5.       
  6.      
  7.     
  8.    
  9.      {D^3} 
  10.     
  11.    
  12.  D3) = 0**

因此**Ent(口味) = 

  1.        3 
  2.       
  3.      
  4.        10 
  5.       
  6.      
  7.     
  8.    
  9.      3 \over 10 
  10.     
  11.    
  12.  103​Ent( 
  13.   
  14.    
  15.     
  16.      
  17.      
  18.        D 
  19.       
  20.      
  21.        1 
  22.       
  23.      
  24.     
  25.    
  26.      {D^1} 
  27.     
  28.    
  29.  D1) + 
  30.   
  31.    
  32.     
  33.      
  34.      
  35.        4 
  36.       
  37.      
  38.        10 
  39.       
  40.      
  41.     
  42.    
  43.      4 \over 10 
  44.     
  45.    
  46.  104​Ent( 
  47.   
  48.    
  49.     
  50.      
  51.      
  52.        D 
  53.       
  54.      
  55.        2 
  56.       
  57.      
  58.     
  59.    
  60.      {D^2} 
  61.     
  62.    
  63.  D2) + 
  64.   
  65.    
  66.     
  67.      
  68.      
  69.        3 
  70.       
  71.      
  72.        10 
  73.       
  74.      
  75.     
  76.    
  77.      3 \over 10 
  78.     
  79.    
  80.  103​Ent( 
  81.   
  82.    
  83.     
  84.      
  85.      
  86.        D 
  87.       
  88.      
  89.        3 
  90.       
  91.      
  92.     
  93.    
  94.      {D^3} 
  95.     
  96.    
  97.  D3)= 0.4**

**

  1. STEP3

** 最后计算每个属性的信息增益
Gain（D，温度）=Ent(D) - Ent(温度 = 1 - 0.971= 0.029
Gain（D，份量）=Ent(D) - Ent(份量) = 1 - 0.722 = 0.278
Gain（D，口味）=Ent(D) - Ent(口味) = 1 - 0.4= 0.6

选择信息增益大的作为第一个属性，即选择口味属性对根节点进行扩展，第二层选择份量属性，最后选择温度属性，画出的决策树如下
在这里插入图片描述
也可以只在口味=甜的时候选择下一个属性是“份量”还是“温度”，因为口味=酸的时候已经可以得出结果为“是”，口味为咸的时候已经可以得出结果为“否”。
在这里插入图片描述

预测 dish= {温度=热，口味=甜，份量=大}，根据决策树可以预测结果为“否”。

剩下的题我就不具体写了，大家可以自己练练手。

(18年期末)下表为是否适合打垒球的决策表，请用决策树算法画出决策树，并请预测 E= {天气=晴，温度=适中，湿度=正常，风速=弱} 的场合，是否合适打垒球。

在这里插入图片描述
画出的决策树如下
在这里插入图片描述

(17年期末)设使用ID3算法进行归纳学习的输入实例集S={ i | 1≤ i ≤ 7 }如下表所示。学习的目标是用属性A、B、C预测属性F。
（1）写出集合S分别以属性A、B、C作为测试属性的熵的增益Gain(S, A)、Gain(S, B)、Gain(S, C)的表达式。
（2）属性A、B、C中哪个应该作为决策树根节点的测试属性?

在这里插入图片描述
（1）
Gain(S, A)=0.067、Gain(S, B)=0.128、Gain(S, C)=0.522
（2）C作为根节点，AB位置可互换
在这里插入图片描述

（22年秋期末）你的飞船刚刚降落在一个外星星球上，你的船员已经开始调查当地的野生动物。不幸的是，你的大多数科学设备都坏了，所以你只能知道一个物体是什么颜色，它有多少只眼睛，它是否活着。更糟糕的是，你们都不是生物学家，所以你们必须使用决策树来将着陆点附近的物体分类为活着或不活着。使用下表回答以下问题：
在这里插入图片描述
(1)下列哪个熵值最大？
H(Alive|eyes>10), H(Alive|eyes<10), H(Alive|color=green), H(Alive|color=black)
(2)计算信息增益值 IG(Alive|color)；
(3)假设我们想将“眼睛数”转换为一个二进制属性，以构建决策树。以下哪种二元分类划分导致 IG（活眼数）值更大？
（a） {Number of eyes = 11, Number of eyes != 11},
（b） {Number of eyes <= 4, Number of eyes > 4},
（c） {Number of eyes <= 13, Number of eyes > 13}
(4)按照信息熵理论根据上一问的二元划分构造一个决策树并对下面的例子进行分类
(a) A red object with 23 eyes，
(b) A black object with 1.5 eyes

在这里插入图片描述

考虑下面一个数据集，它记录了某学生多次考试的情况，请根据提供的数据按要求构建决策树。
（1）根据信息增益率选择第一个属性，构建一个深度为1的决策树（根结点深度为1）。
（2）根据信息增益率构建完整的决策树。请回答，这两个决策树的决策结果是否和训练数据一致，并解释说明。

在这里插入图片描述

设样本集合如下表格，其中A、B、C是F的属性，请根据信息增益标准（ID3算法），画出F的决策树。

在这里插入图片描述

标签： 人工智能 决策树 信息熵
本文转载自: https://blog.csdn.net/m0_69782322/article/details/134756156
版权归原作者 倒杯Whisky 所有， 如有侵权，请联系我们删除。
登录后发布评论

“决策树 （人工智能期末复习）”的评论:

还没有评论
关于作者
...
overfit同步小助手
文章同步
相关阅读

网络安全法-网络运行安全

使用selenium/drissionpage时如何阻止chrome自动跳转http到https

docker desktop 里部署的Open WebUI 管理员密码忘记了的处理方法

在ubuntu20.04中搭建onsite比赛运行环境

利用开源的低代码表单设计器FcDesigner高效管理和渲染复杂表单结构

Kafka学习笔记

【前端】浏览器输入url到页面呈现发生了什么？