《机器学习by周志华》学习笔记-决策树-01

本书中的「决策树」有时指学习方法，有时指学得的树。

1、基本流程

1.1、概念

基本流程，亦称「判定树」

决策树(decision tree)，是一种常见的机器学习方法。以二分类任务为例，我们希望从给定训练数据集学得一个模型，用以对新样例进行分离。

以二分类任务为例，可看作对「当前样本属于正类吗」这个问题的「决策」或「判定」过程。

1.2、目的

是为了产生一棵泛化能力强，即处理未见示例能力强的决策树。

1.3、基本流程

顾名思义，决策树是基于树结构来进行决策的，这恰是人类在面临决策问题时一种很自然的处理机制。

例如，我们要对「这是好瓜吗」这样的问题进行决策时，通常会进行一系列的子判断或自决策，例如：

• 他是什么颜色？>>青绿色
•         它的根蒂是什么形态？>>蜷缩
•                 它敲起来是什么声音？>>**
•                         这是好瓜吗？>>好瓜

如下图所示：

显然，决策过程的最终结论对应了我们所希望的判定结果。例如：「是」或「不是」好瓜。

每个判定问题都是对某个属性的「测试」。例如：他是什么颜色？、它的根蒂是什么形态？

每个「测试结果」或是「导出最终结论」或是「导出进一步的判断问题」，其考虑范围是在上次决策结果的限定范围之内。例如：他是什么颜色？>>青绿色>>>它的根蒂是什么形态？

一般的，一颗决策树包含：

• 一个根节点：包含样本全集
• 若干个内部节点：对应一个属性测试
• 若干个叶节点：对应决策结果

每个结点包含的样本集合根据属性测试的结果被划分到子结点中；从「根节点」到「每个叶节点」的路径对应了一个判定测试序列。

其基本流程遵循简单且直观的「分而治之(divide-and-conquer)」策略。如下所示：

   输入  

• 训练集
• 离散属性集
• 每个属性对应属性值的样本个数为,其中最大样本个数用表示

   过程  

• 创建函数；
• 创建节点；
• （D中样本全属于同一类别）
•         （且为叶节点）
•          情形（1）
•  
• （或任意样本类别个数）
•         （为叶节点且标记为中样本数量最多的类）
•          情形（2）
•  
• 从中选择最优划分属性//最优划分属性将在下面「2、划分选择」说明
•   （的每一个属性值用表示）
•         （为生成分支，令表示中在上取值为的样本子集）
•                 （）
•                         （分支节点=叶节点，类别为中样本数量最多的类）
•                          情形（3）
•                         （分支节点=）
•                 
• 

   输出  

• 以node为根节点的一棵决策树

显然，决策树的生成是一个递归过程。

在决策树基本算法中，有3种情形会导致递归返回：

• 情形（1）：当前结点包含的样本属于同一类别，无需划分。
• 情形（2）：当前属性集为空，或是所有样本在所有属性上取值相同，无法划分。
• 情形（3）：当前结点包含的样本集合为空，不能划分。

在（2）情形下，我们把当前结点标记为叶节点，并将其类别设定为该结点所含样本最多的类别；

在（3）情形下，同样吧当前结点标记为叶节点，但将其类别设定为其父节点所含样本最多的类别。

注意这两种情形的处理实质不同：

• 情形（2）是在利用当前结点的后验分布。
• 情形（3）是把父节点的样本分布作为当前结点的先验分布。

2、划分选择

从上面的决策树「输入-过程-输出」的环节中我们可以知道，其中最重要也是需要研究的部分就是——最优划分属性。

本章主要的内容则是介绍了让「划分选择」最优的方法：

随着划分过程不断进行，我们希望决策树的分支节点所包含的样本尽可能属于同一类别。即节点的「纯度（Purity）」越来越高。

下面我们会介绍一些度量样本集合「纯度（Purity）」比较常用的指标，通过这些指标可以增加样本「纯度」，从而使「划分选择」更优。

2.1、信息增益

2.1.1、信息熵(Information Entropy)

「信息熵」是度量样本「纯度」最常用的一种指标。

假设当前样本集：的类别集合用Y表示：

其中第类样本个数为且，其所占比例用表示，则：

其离散属性集合用A表示：

  ，其中任意离散属性用

则样本集D的「信息熵」定义为：

由于且所以：

，越小，样本D的「纯度」越高。

2.1.2、信息增益(Information Gain)

假设离散属性有V个可能的取值，分别用表示。若使用来对样本集D进行划分，则会产生V个分支节点。其中第v个分支节点包含了D中所有在属性上取值为的样本，该样本集合记为（数据为i类别v值的样本集合）且其对应的样本数用表示，则样本集合的信息熵：

考虑到不同分支节点所包含的样本数不同，给分支结点赋予权重的规则定为：样本数越多的分支节点，影响越大。即越大，影响越大。所以权重表示为：

则用属性对样本D进行划分所获得的「信息增益(Information Gain)」为：

一般来说，信息增益越大，则意味着使用属性来进行划分数据集D获的的「纯度」越大。因此我们可以用信息增益来进行决策树的「划分属性选择」。也就是上面算法的属性选择。

上个式子就是求集合中所有类别的「信息增益」最大的属性公式。

较为著名的就是ID3（Iterative Dichotomiser，迭代二分器）决策树学习算法就是以「信息增益」为准则来选择划分属性。

案例：给出数据集D如下表（绿色文字是好瓜Y1，红色文字是坏瓜Y2）

编号	色泽(A1)	根蒂(A2)	敲声(A3)	纹理(A4)	脐部(A5)	触感(A6)	是否好瓜(Y)
x1	青绿	蜷缩	浑浊	清晰	凹陷	硬滑	是Y1
x2	乌黑	蜷缩	沉闷	清晰	凹陷	硬滑	是Y1
x3	乌黑	蜷缩	浑浊