机器学习之决策树笔记(1)-决策树基本概念及划分选择标准

我会带着你远行 2023-05-30 09:27 7阅读 0赞

### 机器学习之决策树笔记（1） ###

*  基本概念
 *   *  什么是决策树
     *  决策树结构特点
     *  决策树学习的目的
     *  决策树学习基本算法
     *  决策树构建三个步骤
     *  决策树的优点
     *  代表性的决策树算法
 *  划分选择
 *   *  信息熵(Information Entropy)
     *  信息增益(Information Gain)
     *  增益率(Gain Ratio)
     *  基尼指数(Gini index)

# 基本概念 #

## 什么是决策树 ##

决策树是一种很常用也是很有效的分类和回归方法，属于有监督的学习，且决策树是基于树结构来进行决策的。

## 决策树结构特点 ##

1.  其中叶节点对应于决策结果实例；
2.  每个内部节点表示在一个属性上的测试；
3.  每个分支（从根节点到叶节点的路径）对应一个判断测试序列；

## 决策树学习的目的 ##

为了产生一棵泛化能力强，即处理未见示例能力强的决策树。其基本流程遵循简单且直观的”分而治之“策略。

## 决策树学习基本算法 ##

![20191109172249413.png][]

图(1)

**决策树算法的基本过程：**

1.  先构建根节点，将所有训练数据都放在根节点，选择一个最优特征，按着这一特征将训练数据集分割成子集，使得各个子集有一个在当前条件下最好的分类。
2.  如果这些子集已经能够被基本正确分类，那么构建叶节点，并将这些子集分到所对应的叶节点去。
3.  如果还有子集不能够被正确的分类，那么就对这些子集选择新的最优特征，继续对其进行分割，构建相应的节点，如果递归进行，直至所有训练数据子集被基本正确的分类，或者没有合适的特征为止。
4.  每个子集都被分到叶节点上，即都有了明确的类，这样就生成了一颗决策树。

## 决策树构建三个步骤 ##

1.  特征划分选择
2.  决策树的生成
3.  决策树的修剪

## 决策树的优点 ##

1.  决策树易于理解和实现，它的能够直接体现数据的特点，只要通过解释后都有能力去理解决策树所表达的意义；
2.  而且能够同时处理数据型和常规型属性，在相对短的时间内能够对大型数据源做出可行且效果良好的结果；
3.  易于通过静态测试来对模型进行评测，可以测定模型可信度。

## 代表性的决策树算法 ##

ID3、C4.5和CART决策树算法，后面会对这三大决策树的算法进行介绍。

# 划分选择 #

由决策树学习基本算法可看出，决策树学习的关键是第8行，即如何选择最优划分属性.一般而言，随着划分过程不断进行，我们希望决策树的分支结点所包含的样本尽可能属于同一类别，即结点的“纯度”越来越高.。

为了找到**最优划分属性**，所以我们在这里首先**引入三个概念**：

*  信息增益
 *  信息增益率
 *  基尼指数

我们要理解这三个概念的话，首先要明白什么是**信息熵**。

## 信息熵(Information Entropy) ##

熵在信息论中是度量样本集合纯度最常用的一种指标，由香农提出来的。  
熵越大，数据的不确定性越高，数据越混乱；  
熵越小，数据的不确定性越低，数据越趋向于集中统一。

假定当前样本集合D中第k类样本所占的比例为 p k ( k = 1 , 2 , … , ∣ y ∣ ) p\_k(k=1,2,…,|y|) pk(k=1,2,…,∣y∣),则D的信息熵定义为：  
 E n t ( D ) = − ∑ k = 1 ∣ y ∣ p k log ⁡ 2 p k . 公 式 （ 1 ） Ent(D) = -\\sum\_\{k=1\}^\{|y|\}p\_k \\log\_2p\_k. \\qquad公式（1） Ent(D)=−k=1∑∣y∣pklog2pk.公式（1）

Ent(D)的值越小，则D程度越高。

注：  
计算信息熵时我们约定：若 p = 0 p=0 p=0， p log ⁡ 2 p = 0 p\\log\_2p=0 plog2p=0。  
Ent(D)的最小值为0，最大值为 log ⁡ 2 ∣ y ∣ \\log\_2| y | log2∣y∣。

## 信息增益(Information Gain) ##

假定离散属性a有V个可能的取值 \{ a 1 , a 2 . . . , a V \} \{\\\{a^1,a^2...,a^V\\\}\} \{ a1,a2...,aV\},若使用a来对样本集 D D D进行划分。  
令 D v D^v Dv为第v个分支结点包含了 D D D中所有在属性a.上取值为 a v a^v av的样本；  
 E n t ( D v ) Ent(D^v) Ent(Dv)表示 D v D^v Dv的信息熵；  
又考虑到不同的分支结点所包含的样本数不同，给分支结点赋予权重 ∣ D v ∣ / ∣ D ∣ |D^v|/|D| ∣Dv∣/∣D∣,即样本数越多的分支结点的影响越大。  
于是可计算出用属性a对样本 D D D进行划分所获得的“信息增益”。  
 G a i n ( D , a ) = E n t ( D ) − ∑ v = 1 V ∣ D v ∣ ∣ D ∣ E n t ( D v ) . 公 式 （ 2 ） Gain(D,a)=Ent(D)- \\sum\_\{v=1\}^\{V\}\\frac\{|D^v|\}\{|D|\}Ent(D^v). \\qquad公式（2） Gain(D,a)=Ent(D)−v=1∑V∣D∣∣Dv∣Ent(Dv).公式（2）  
一般而言，信息增益越大，则意味着使用属性a来进行划分所获得的“纯度提升”越大。  
因此,我们可用信息增益来进行决策树的划分属性选择,即在图1算法第8行选择属性 a ∗ = a r g m a x G a i n ( D , a ) ， a ∈ A a\_\* = arg max \\quad Gain(D,a) ，a∈A a∗=argmaxGain(D,a)，a∈A。著名的ID3决策树学习算法就是以信息增益为准则来选择划分属性。

## 增益率(Gain Ratio) ##

实际上，信息增益准则对取值数目较多的属性有所偏好，为减少这种偏好带来的不利影响。著名的C4.5算法不直接使用信息增益，而是使用增益率(gain ratio)来进行划分属性划分。  
采用与式(2)相同的符号表示，增益率定义为:  
 G a i n \_ r a t i o ( D , a ) = G a i n ( D , a ) I V ( a ) . 公 式 （ 3 ） Gain\\\_ratio(D,a)=\\frac\{Gain(D,a)\}\{IV(a)\}. \\qquad公式（3） Gain\_ratio(D,a)=IV(a)Gain(D,a).公式（3）  
其中：  
 I V ( a ) = − ∑ v = 1 V ∣ D v ∣ ∣ D ∣ log ⁡ 2 ∣ D v ∣ ∣ D ∣ . 公 式 （ 4 ） IV(a)=- \\sum\_\{v=1\}^\{V\}\\frac\{|D^v|\}\{|D|\}\\log\_2\\frac\{|D^v|\}\{|D|\}. \\qquad公式（4） IV(a)=−v=1∑V∣D∣∣Dv∣log2∣D∣∣Dv∣.公式（4）  
称为属性a的“固有值”(intrinsic value)。  
属性a的可能取值数目越多(即 V V V越大)，则 I V ( a ) IV(a) IV(a)的值通常会越大。  
但需注意的是,增益率准则对可取值数目较少的属性有所偏好。

因此,C4.5算法也并不是直接选择增益率最大的候选划分属性,而是使用了一个启发式:

1.  先从候选划分属性中找出信息增益高于平均水平的属性（就是保证了一个底线，不低于平均水平）。
2.  再从中选择增益率最高的。

## 基尼指数(Gini index) ##

采用与式(1)相同的符号，数据集D的纯度可用**基尼值**来度量:  
 G i n i ( D ) = ∑ k = 1 ∣ y ∣ ∑ k ′ ≠ k p k p k ′ . 公 式 （ 5 ） Gini(D)=\\sum\_\{k=1\}^\{|y|\}\\sum\_\{k' \\neq k\}p\_kp\_k'. \\qquad公式（5） Gini(D)=k=1∑∣y∣k′=k∑pkpk′.公式（5）  
直观来说， G i n i ( D ) Gini(D) Gini(D)反映了从数据集D中随机抽取两个样本,其类别标记不一致的概率。  
因此， G i n i ( D ) Gini(D) Gini(D)越小，则数据集D的纯度越高。

采用与式(2)相同的符号表示，属性a的**基尼指数**定义为:  
 G i n i \_ i n d e x ( D , a ) = ∑ v = 1 V ∣ D v ∣ ∣ D ∣ G i n i ( D v ) . 公 式 （ 6 ） Gini\\\_index(D,a)= \\sum\_\{v=1\}^\{V\}\\frac\{|D^v|\}\{|D|\}Gini(D^v). \\qquad公式（6） Gini\_index(D,a)=v=1∑V∣D∣∣Dv∣Gini(Dv).公式（6）  
于是,我们在候选属性集合A中，选择那个使得划分后**基尼指数最小**的属性作为最优划分属性,即 a ∗ = a r g m i n G i n i i n d e x ( D , a ) ， a ∈ A a\* = arg min Gini index(D, a)，a∈A a∗=argminGiniindex(D,a)，a∈A.

CART决策树使用“基尼指数”(Gini index)来选择划分属性。

--------------------

公式编辑：LaTeX。[LaTeX数学公式编辑][LaTeX]

**参考文献：**  
<机器学习> 周志华 著。（强烈推荐这本书，开卷必有所得）

本博文参考内容自周志华老师的《机器学习》，虽有部分自己的思考和对书中内容的扩展或注解、但大部分表述及截图均来自此书。博主理解能力有限，可能无法将书中真正的精髓展示给读者。想获取更多机器学习决策树的知识，大家可以购一本周老师的《机器学习》，**开卷必有所得**。

[20191109172249413.png]: https://img-blog.csdnimg.cn/20191109172249413.png
[LaTeX]: https://blog.csdn.net/TommyXu8023/article/details/102991402