决策树模型之CART树和C5.0

树模型基本思想：计算结点的纯度来选择最具显著性的切分
不同树模型之间的差异：差异在于衡量纯度变化的标准不同

CART树：Gini系数
C5.0树：信息熵增益

1.回归树(CART树)

回归树也成为分类回归树，是一种既可用于分类也可用于回归的算法。

CART树分类的主要步骤：

1. 决策树的生成：递归的构建而决策树的过程，基于训练数据生成决策树，生成的决策树数量应尽量大。

自上而下的从根开始建立节点，在每个节点处选择一个最好的属性来分类，使子节点红的训练集尽可能的顿。

不同算法使用不同的指标来衡量“最好”：

分类算法：一般选择Gini系数

回归算法：使用最小二乘偏差（LSD）或最小绝对偏差（LSA）

2.决策树剪枝：用验证数据集对已生成的树进行剪枝并选择最优子树这时损失函数最小做为标准

分类树的生成

对每个特征A，对它所有的可能取值a，将数据集划分为A=a和A!=a两个部分计算集合D的基尼指数：

遍历所有的特征 A，计算其所有可能取值 a 的基尼指数，选择 D 的基尼指数最小值对应的特征及切分点作为最优的划分，将数据分为两个子集。
对上述两个子节点递归调用步骤(1)(2), 直到满足停止条件。
生成CART树

基尼指数：

是一种不等度的度量

是介于0~1之间的数，0-完全相等，1-完全不相等

总体内包含的类别越杂乱，Gini指数就越大

分类问题中，假设存在K个类，样本属于第k个类的概率为pk，则概率分布的Gini指数为：

样本集合D的Gini指数为：

当在数据集D上根据某一取值a进行分割，得到D1、D2两部分后，那么特征A下集合D的Gini指数为：

算法停止条件：

节点中样本个数小于预定阈值
样本的Gini指数小于阈值
没有更多特征

剪枝

在完整的的决策树上，减掉一些完整的子支是决策树变小，从而防止决策树过拟合。

决策树很容易产生过拟合，改善的方式包括：

通过阈值控制终止条件，防止分支过细

对决策树进行剪枝

建立随机森林

2.C5.0

节点分裂标准：信息增益比

C系列决策树发展过程：

阶段一：ID3
　　　节点选择标准：信息增益
　　　缺陷：1. 方法会倾向与属性值比较多的变量（如省份字段存在31个水平，性别由两个水平，信息增益会考虑选择省份做特征节点
　　　　　2.构造树时不能很好地处理连续变量

阶段二：C4.5
　　　节点选择标准：信息增益比（避免了偏袒）
　　　缺点：运行效率很低

阶段三：C5.0
　　　商业版的C4.5，提升了算法效率，但没有公布具体算法细节

C5.0算法特点

1.C5.0是一种多叉树。

如果根节点或者中间节点为连续变量，则改变量一定会一分为二成为两个分支；如果根节点或者中间节点为离散变量，则分开离散变量水平数个分支；因此一个变量一旦被使用，后面节点都不会在使用该变量。

2.C5.0生成树采用信息增益比进行分裂节点的选择

3.剪枝采用“减少误差”法和“减少损失”法进行。

减少误差法：核心思想是比较剪枝前后的误差率
　　　误差率的计算：如果第i个节点中包含N个样本，其中预测错误的样本量为M，则该节点的错误率为f=M/N

减少损失法：该方法结合损失矩阵对树进行剪枝，核心是剪枝前后的的损失量。