Part5—Python实现CART决策树

1.前言

2.数据处理

读取文件名为filename的数据文件，其每一行代表一个样本数据，每一列代表一个特征，最后一列为样本值。

给定数据集dataSet，根据特征值对（feature，value）将数据集划分为两部分：

3.构建CART树

生成叶子节点，即得到叶子节点中样本数据的均值。

根据和方差最小的方式选择最佳的特征和特征值对数据进行划分，calcErr函数用均方差乘以样本数据集中的样本个数，计算数据集的平方误差。

根据和方差最小原则，chooseBestSplit遍历数据集中所有的特征值对，找出最佳的特征值对用于划分数据集；其中，contrlVar=(errLimit,numLimit)可用于控制函数停止的阈值，如果误差减小值小于阈值errLimit或者切分后样本个数小于阈值numLimit，则直接生成叶节点而不再对数据集进行划分。其实，这里已经用到了预剪枝的思想。

由chooseBestSplit选出最佳特征值对，将数据集划分为两部分；然后递归调用createTree生成用字典表示的决策树。

4.决策树剪枝

4.1预剪枝

在chooseBestSplit中已经用了预剪枝的思想，通过输入两个阈值控制决策树停止生成的时机，减小决策树的复杂度。处理过程简单高效，但是需要通过多次尝试修改阈值来获得合理的决策树。

4.2后剪枝

使用后剪枝需要将数据集分为训练集与测试集，训练集用来生成决策树，测试集用来验证生成的决策树并对其进行剪枝以减小过拟合。

cutTree对测试数据集进行切分直到遇见叶子节点，然后对叶子节点合并前后的误差进行比较，如果合并能够减小误差，则合并左右叶子节点。

Coding Your Ambition！