【机器学习导引】ch4-决策树

基本流程

两个需要解决的问题

1. 属性顺序：
   • 问题：哪些属性在前面，哪些属性在后面？
   • 这个问题指的是在处理数据或进行排序时，需要确定属性的排列顺序，以便更好地进行数据处理或分析。
2. 属性选择：
   • 问题：哪些属性使用，哪些属性不用？
   • 这里强调了选择属性的必要性，即在分析数据时，应该根据需求选择有用的属性，并剔除不必要的属性。

两种方法：

• 划分选择：这与属性顺序相关，可能是指如何合理地划分不同的属性并安排顺序。
• 剪枝处理：与属性选择相关，指的是如何精简数据或过程，去掉不必要的属性或步骤，以优化系统或算法的性能。

决策树的一些关键概念和流程

1. 决策树的基本概念：
   • 决策树基于“树”结构进行决策。
   • 每个“内部结点”对应于某个属性上的“测试”（test）
   • 每个分支对应于该测试的一个可能结果（即属性的某个取值）
   • 每个“叶结点”对应于一个**“预测结果”**
2. 学习过程：
   • 通过对训练样本的分析来确定“划分属性”（即内部结点所对应的属性）
3. 预测过程：
   • 在预测时，将测试示例从根结点开始，沿着划分属性所构成的“判定测试序列”下行，直到叶结点得出预测结果。

决策树算法的原理

1. 决策树策略：分而治之
   • 决策树使用“分而治之”策略，通过递归过程从根结点到叶结点不断进行划分。
   • 在每个中间结点，寻找一个合适的“划分”属性（split or test），根据这个属性来对样本进行分类。
2. 三种停止条件：
   • 当前结点包含的样本全属于同一类别，无需再划分。
   • 当前属性集为空，或者所有样本在所有属性上的取值相同，无法继续划分。
   • 当前结点包含的样本集合为空，不能再划分。

划分选择

信息增益和信息熵[entropy]

1. 信息熵（entropy）：

   • 信息熵是衡量样本集合**“纯度”**的常用指标。

   • 假设当前样本集合 $D$ 中第 $k$ 类样本所占的比例为 $p_k$，则 $D$ 的信息熵定义为：

     $$Ent(D)=-\sum _{k=1}^{|Y|}{p}_k{\log }_2{p}_k$$

     其中，$|Y|$ 是样本类别的总数。

   • 信息熵的值越小，表示 $D$ 的纯度越高。即如果所有样本都属于同一类，则信息熵为 $0$。

   • 信息熵的最小值为 $0$（样本完全纯净），最大值为 ${\log }_2|Y|$（样本完全混乱）。

2. 信息增益：
   • 信息增益是以信息熵为基础，计算当前划分对信息熵所造成的变化。通过信息增益可以判断某个属性是否适合作为决策树的划分依据。

信息熵的公式表示样本集合的无序程度，信息增益则衡量某个属性的划分能够降低多少无序程度。通常在决策树的构建中，会选择信息增益最大的属性进行划分。

何量化一个信息的含量

提出了衡量信息量 $I(x)$ 需要满足的三个条件：

1. 非负性： 信息量 $I(x)$ 应该是非负的，即 $I(x)\ge 0$。这意味着信息量不能为负值。
2. 可相加性： 信息量具有可相加性，即当两个独立事件 $x$ 和 $y$ 同时发生时，其信息量可以相加，满足 $I(xy)=I(x)+I(y)$。
3. 与事件概率 $p(x)$ 的关系： 信息量与事件发生的概率成反比。也就是说，事件发生的概率越大，提供的信息量越小；概率越小，信息量越大。

$$I(x)=-{\log }_{2}p(x)$$

解释如下：

• 公式解释： 信息量 $I(x)$ 与事件的概率 $p(x)$ 成反比。通过对概率 $p(x)$ 取以 $2$ 为底的对数，再取负号，就可以得到该事件的信息量。这个公式能够满足之前提到的三条性质。

验证信息量的可相加性（第二条性质）：

$$I(xy)=-{\log }_2(p(x)p(y))=-{\log }_{2}p(x)+(-{\log }_{2}p(y))=I(x)+I(y)$$

这一步推导证明了如果两个事件 $x$ 和 $y$ 独立发生，它们的联合概率可以表示为各自概率的乘积，因此对应的总信息量就是各自信息量的和。这验证了信息量公式满足相加性条件。

信息熵

1. 信息熵（Shannon Entropy）：

   • 信息熵 $H(x)$ 是消息的平均信息量，也称为香农熵。

   • 公式为：

     $$H(x)=\sum _{i=1}^{n}I(x_i)p(x_i)=-\sum _{i=1}^{n}p(x_i){\log }_{2}p(x_i)$$

     其中，$p(x_i)$ 表示第 $i$ 种结果发生的概率，$I(x_i)$ 是该结果的信息量。

2. 含义：

   • 信息熵衡量了在一组可能结果中，平均每个结果带来的不确定性。
     • 结果的概率越均匀，熵值越大；
     • 如果某个结果特别确定，熵值就会较低。

信息增益

1. 属性取值：
   • 假设离散属性 $a$ 的取值为 { a 1 , a 2 , … , a V } \{a^1, a^2, \dots, a^V\} {a1,a2,…,aV}，表示属性 $a$ 有 $V$ 个可能的取值。
   • 定义 $D^v$ 为数据集中属性 $a$ 的取值为 $a^v$ 的样本集合。
2. 信息增益公式：

   • 信息增益 $Gain(D,a)$ 表示对数据集 $D$ 按照属性 $a$ 进行划分所带来的信息增益。

   • 公式为：

     $$Gain(D,a)=Ent(D)-\sum _{v=1}^V\frac{|D^v|}{|D|}Ent(D^v)$$

   • 解释公式：

     • $Ent(D)$ 是划分前的数据集 $D$ 的信息熵。
     • ${\sum }_{v=1}^V\frac{|D^v|}{|D|}Ent(D^v)$ 是划分后各子集的加权信息熵
     • $\frac{|D^v|}{|D|}$ 是第 $v$ 个子集的权重，表示该子集在总体中的占比，样本越多的子集越重要。

总的来说，信息增益用来衡量某个属性对数据集划分的有效性，信息增益越大，表示该属性能够更好地将数据分类，是决策树算法中选择最佳划分属性的依据。

样例

计算：

1. $Gain(D,色泽)=?$
2. $Gain(D,纹理)=?$

回答：

1. 计算划分前的数据集 $D$ 的信息熵：

   1. 数据：是否是好瓜
      1. n u m ( “是” ) = 2 ， D 1 = { 1 , 2 } num(“是”)=2，D_1=\{1,2\} num(“是”)=2，D1​={1,2}
      2. n u m ( “否” ) = 2 ， D 1 = { 3 , 4 } num(“否”)=2，D_1=\{3,4\} num(“否”)=2，D1​={3,4}
   2. 信息熵计算：

   $$Ent(D)=-\sum _{k=1}^{|Y|}{p}_k{\log }_2{p}_k=-(\frac{2}{4}lo{g}_2^{\frac{2}{4}}+\frac{2}{4}lo{g}_2^{\frac{2}{4}})=1$$

2. $Gain(D,色泽)=?$

   1. 数据：是否是乌黑

      1. n u m ( “乌黑” ) = 2 ， D 1 = { 1 , 2 } num(“乌黑”)=2，D_1=\{1,2\} num(“乌黑”)=2，D1​={1,2}
      2. n u m ( “浅白” ) = 2 ， D 1 = { 3 , 4 } num(“浅白”)=2，D_1=\{3,4\} num(“浅白”)=2，D1​={3,4}

   2. 划分后的信息熵：

      1. $Ent(D^1)=-(1\times lo{g}_2^1+1\times lo{g}_2^1)=0$
      2. $Ent(D^2)=-(1\times lo{g}_2^1+1\times lo{g}_2^1)=0$

   3. 划分后的加权信息熵

      $$\sum _{v=1}^2\frac{|D^v|}{|D|}Ent(D^v)=\frac{1}{2}\times 0+\frac{1}{2}\times 0=0$$

   4. 信息增益

   $$Gain(D,色泽)=1-0=1$$

3. $Gain(D,纹理)=?$

   1. 数据：是否是清晰

      1. n u m ( “清晰” ) = 2 ， D 1 = { 1 , 3 } num(“清晰”)=2，D_1=\{1,3\} num(“清晰”)=2，D1​={1,3}
      2. n u m ( “模糊” ) = 2 ， D 1 = { 2 , 4 } num(“模糊”)=2，D_1=\{2,4\} num(“模糊”)=2，D1​={2,4}

   2. 划分后的信息熵：

      1. $Ent(D^1)=-(\frac{1}{2}\times lo{g}_2^1+\frac{1}{2}\times lo{g}_2^1)=1$
      2. $Ent(D^2)=-(\frac{1}{2}\times lo{g}_2^1+\frac{1}{2}\times lo{g}_2^1)=1$

   3. 划分后的加权信息熵:

      $$\sum _{v=1}^2\frac{|D^v|}{|D|}Ent(D^v)=\frac{1}{2}\times 1+\frac{1}{2}\times 1=1$$

   4. 信息增益

   $$Gain(D,色泽)=1-1=0$$

剪枝处理

通过主动去掉一些分支来降低过拟合的风险。过拟合是由于分类训练样本的分支过多导致模型在训练集上表现很好，但在实际应用中表现较差的现象。

1. 预剪枝（pre-pruning）：在生成决策树时，提前终止某些分支的生成。
2. 后剪枝（post-pruning）：先生成一棵完整的树，然后再回头进行剪枝，去掉不必要的分支。