基于决策树算法完成鸢尾花品种预测任务

type

status

date

slug

summary

实验说明

本实验通过鸢尾花数据集 iris.csv 来实现对决策树进一步的了解。其中，Iris 鸢尾花数据集是一个经典数据集，在统计学习和机器学习领域都经常被用作示例。数据集内包含 3 类共 150 条记录，每类各 50 个数据，每条记录都有 4 项特征：花萼长度、花萼宽度、花瓣长度、花瓣宽度，可以通过这 4 个特征预测鸢尾花卉属于（ iris-setosa, iris- vers icolour, iris-virginica）三个类别中的哪一品种。

本实验将五分之四的数据集作为训练集对决策树模型进行训练；将剩余五分之一的数据集作为测试集，采用训练好的决策树模型对其进行预测。训练集与测试集的数据随机选取。本实验采用准确率 (accuracy)作为模型的评估函数：预测结果正确的数量占样本总数。

实验步骤与内容

前置理论学习

决策树：

每个分支节点代表着多个备选方案中的某一个选择

每个叶节点代表一种分类或决策

CLS 算法：

输入T为训练集数据，创建T节点

如果T节点中数据全属于同一类别C，将T节点标记为C类叶节点，返回决策树

从T中选择出一个最佳属性X，X的取值为

根据X不同的取值将T分为不同的子集，创建N个子节点

对每个子节点重复这个过程

ID3：Iterative Dichotomizer (version) 3

Entropy 熵

信息熵是度量样本集合的随机性（不确定性/不稳定性）最常用的一种指标。

假定当前样本集合S中第k类(共c类)样本所占的比例为

二分类问题的熵如下：

信息增益 Information Gain

假定离散属性A有n个可能的取值，若用A来对样本集S进行划分，则会产生n个分支结点，其中第v个分支结点包含了S中所有在属性A上取值为的样本，记为。

计算出的信息熵，再考虑不同分支所包含的样本数不同，给分支结点赋予权重，即样本数越多的分支结点的影响越大，于是可以计算出用属性A对样本集S进行划分所获得的"信息增益"：

ID3生成算法

每一轮我们分别计算每个属性的信息增益(Information Gain)，选出信息增益最大的属性（分类后的信息熵的加权和越小，不确定性越低）作为最佳属性构建决策树

C4.5：An Extension of ID3

ID3生成决策树算法中Information Gain会偏向于可能值较多的属性，但是对于某些属性比如：学号，属性取值唯一，计算出来的信息增益将远大于其他属性。这个属性产生的分支结点中将仅包含一个样本，这些分支结点的纯度已经达到最大。然而，这样的决策树显然不具有泛化能力，无法对新样本进行有效预测。C4.5算法是对ID3的后继与改进，最优属性的决定依赖于信息增益率。

C4.5额外的功能：

数值（连续）属性的纳入。

单个属性的名义（离散）值可以分组，以支持更复杂的测试。

在树的归纳后进行剪枝，例如基于测试集，以提高准确性。

C4.5可以处理不完整信息（缺失的属性值）。

使用增益比而不是信息增益。

处理数字属性：将连续数据→离散数据 选择连续属性的分割点：

按连续属性的值对示例进行排序。

找出目标标签和属性值不同的相邻示例→一组候选分割点

计算每个分割点的增益，并选择增益最高的分割点。

信息增益率 GainRatio

定义为属性A对数据集S的信息增益与数据集S关于属性A的信息熵的比

称为属性A的固有值，属性A的可能取值数目越多，它的值越大。

增益率准则对可取值数目较少的属性有所偏好，因此C4.5算法并不是直接选择增益率最大的候选划分属性，而是使用了一个启发式算法：先从候选划分属性中找出信息增益Information Gain高于平均水平的属性，再从中选择增益率GainRatio最高的

CART

分类与回归树

生成二叉决策树：每个节点仅创建两个子节点（而ID3为每个子类别创建一个子节点）。

每次分裂使子集比分裂前更加pure

在ID3中，使用熵来衡量分裂；而在CART中，则使用impurity

node impurity：当所有节点是相同类别时为0，当节点上的所有类别出现的概率相等时，达到最大值

Entropy Impurity

Gini Impurity

Misclassification impurity

3个算法的主要区别在于度量信息方法、选择节点特征还有分支数量的不同。

ID3，采用熵（entropy）来度量信息不确定度，选择“信息增益”最大的作为节点特征，它是多叉树，即一个节点可以有多个分支。

C4.5，同样采用熵（entropy）来度量信息不确定度，选择“信息增益比”最大的作为节点特征，同样是多叉树，即一个节点可以有多个分支。

CART，采用基尼指数（Gini index）来度量信息不纯度，选择基尼指数最小的作为节点特征，它是二叉树，即一个节点只分两支。

决策树剪枝【预剪枝、后剪枝】

剪枝分为”预剪枝(prepruning)”和”后剪枝(postpruning)”两种

预剪枝是指在决策树构建过程中, 对每个节点在划分前先进行估计, 若不能带来决策树泛化性能提升, 就停止划分, 并将当前结点标记为叶结点

后剪枝则是先构成一颗完整的决策树, 再考察非叶结点. 若该结点对应的子树替换为叶结点能带来决策树泛化性能提升, 则将该字数替换为叶结点

决策时剪枝可以减少过拟合

剪枝的具体操作就是，将数据集分为“训练集”和“测试集“，用训练集来生成决策树，用测试集的准确率，来测试每一个分支是否可以剪掉，剪掉后测试集的准确率上升，可以剪掉，反之剪掉后测试集的准确率下降，不可以剪掉。

实践

首先观察数据分布及关系

本实验要求输出测试集各样本的预测标签和真实标签，并计算模型准确率。另外，给出 3 个可视化预测结果（如散点图）。

可以分别尝试 ID3,C4.5,cart 等决策树算法，并评判效果。

基础实验内容

首先实现数据集加载及将数据集划分为训练集和测试集的函数，如下

ID3决策树算法

由前置理论学习可知，ID3决策树采用熵（entropy）来度量信息不确定度，选择“信息增益”最大的作为节点特征，它是多叉树，即一个节点可以有多个分支，它所能接受的数据应为离散数据，因此我们需要考虑将连续数据离散化处理

接着，我们需要实现ID3决策树算法如下：

其中需要用到的计算熵和信息增益的函数如下：

C4.5决策树

C4.5决策树与ID3决策树的区别在于选择了信息增益比代替信息增益来选择节点特征

CART决策树

CART决策树可以直接处理连续数据，因此不需要先对数据进行离散化了

CART决策树采用基尼指数（Gini index）来度量信息不纯度，选择基尼指数最小的作为节点特征，它是二叉树，即一个节点只分两支。

具体实现代码如下：

为了突出模型之间的差异，在某些精确度较低的seed下检验，并使用散点图可视化展示结果如下：

=== ID3决策树 === 模型准确率: 86.67%

=== C4.5决策树 === 模型准确率: 86.67%

=== CART决策树 === CART准确率: 93.33%

根据实验结果分析，在Iris这类小规模数据集上，由于样本量有限（仅150条，测试集30条），ID3、C4.5和CART三种决策树算法的性能差异容易被数据划分的随机性所掩盖。但在某些实验中，能清晰的看出CART决策树效果显著好于ID3决策树和C4.5决策树。