什麽是决策树

一种对实例进行分类的树形结构，通过多层判断区分目标所属类别 

本质：通过多层判断，从训练数据集中归纳出一组分类规则

构造树的基本想法是随着树深度的增加，节点的熵迅速地降低。熵降低的速度越快越好，这样我们有望得到一棵最矮的决策树。

优点：

1.计算量小，运算速度快        

2.易于理解，可清晰查看各属性的重要性

缺点：

1.忽略属性间的相关性        

2.样本类别分佈不均匀时，容易影响模型表现

3.ID3 没有剪枝策略，容易过拟合

4.信息增益准则对可取值数目较多的特征有所偏好，类似“编号”的特征其信息增益接近于 1

5.只能用于处理离散分布的特征

6.没有考虑缺失值

决策树求解

目标：根据训练数据集构建一个决策树模型，使它能够对实例进行正确的分类

问题核心：特征选择，每一个节点，应该选用哪个特征

三种求解方法：ID3、C4.5、CART

ID3方法详解

熵本质上代表的是内部信息的混乱程度。

信息熵（entropy） 是度量随机变量不确定性的指标，信息熵越大，变量不确定性越大。

ID3方法整体思路就是在每个节点处，对比不同属性带来的信息增益，选取增益大的属性，继续分叉，直到满足某个停止条件（为提升泛化能力，可能还有剪枝操作）为止。样本集合D中第k类样本所佔比例为Pk，则D的信息熵为：

以属性a进行样本划分带来的信息增益：即 划分前的信息熵 - 划分后的信息熵，则信息增益越大越好。

活跃度的信息增益比性别的信息增益大，也就是说，活跃度对用户流失的影响比性别大。在做特征选择或者数据分析的时候，我们应该重点考察活跃度这个指标。

 

C4.5方法详解

是ID3的增强版，为了解决属性很多样本很少，即分的过于精细导致泛化能力差的问题而提出的信息增益比（增益率）。增益率可看作是信息增益与自身熵值（数值很大）的比值。

C4.5 相对于 ID3 的缺点对应有以下改进方式：

1.引入悲观剪枝策略进行后剪枝；

2.引入信息增益率作为划分标准；

3.能够处理连续型的属性。首先将连续型属性离散化，把连续型属性的值分成不同的区间，依据是比较各个分裂点Gian值的大小；

4.缺失数据的考虑：在构建决策树时，可以简单地忽略缺失数据，即在计算增益时，仅考虑具有属性值的记录；

预剪枝：

在构建决策树的过程中，提前停止。在节点划分前来确定是否继续增长，及早停止增长的主要方法有：

• 节点内数据样本低于某一阈值；
• 所有节点特征都已分裂；
• 节点划分前准确率比划分后准确率高。

预剪枝不仅可以降低过拟合的风险而且还可以减少训练时间，但另一方面它是基于“贪心”策略，会带来欠拟合风险。

后剪枝：

决策树构建好后，然后才开始剪裁。在已经生成的决策树上进行剪枝，从而得到简化版的剪枝决策树。

C4.5 采用的悲观剪枝方法，用递归的方式从低往上针对每一个非叶子节点，评估用一个最佳叶子节点去代替这课子树是否有益。如果剪枝后与剪枝前相比其错误率是保持或者下降，则这棵子树就可以被替换掉。（比较损失函数）C4.5 通过训练数据集上的错误分类数量来估算未知样本上的错误率。

后剪枝决策树的欠拟合风险很小，泛化性能往往优于预剪枝决策树。但同时其训练时间会大的多。

缺点：

1.剪枝策略可以再优化；

2.C4.5 用的是多叉树，用二叉树效率更高；

3.C4.5 只能用于分类；

4.C4.5 使用的熵模型拥有大量耗时的对数运算，连续值还有排序运算；

5.C4.5 在构造树的过程中，对数值属性值需要按照其大小进行排序，从中选择一个分割点，所以只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时，程序无法运行。

CART方法详解

基尼指数

总结

最后通过总结的方式对比下 ID3、C4.5 和 CART 三者之间的差异。

• 划分标准的差异：ID3 使用信息增益偏向特征值多的特征，C4.5 使用信息增益率克服信息增益的缺点，偏向于特征值小的特征，CART 使用基尼指数克服 C4.5 需要求 log 的巨大计算量，偏向于特征值较多的特征。
• 使用场景的差异：ID3 和 C4.5 都只能用于分类问题，CART 可以用于分类和回归问题；ID3 和 C4.5 是多叉树，速度较慢，CART 是二叉树，计算速度很快；
• 样本数据的差异：ID3 只能处理离散数据且缺失值敏感，C4.5 和 CART 可以处理连续性数据且有多种方式处理缺失值；从样本量考虑的话，小样本建议 C4.5、大样本建议 CART。C4.5 处理过程中需对数据集进行多次扫描排序，处理成本耗时较高，而 CART 本身是一种大样本的统计方法，小样本处理下泛化误差较大 ；
• 样本特征的差异：ID3 和 C4.5 层级之间只使用一次特征，CART 可多次重复使用特征；
• 剪枝策略的差异：ID3 没有剪枝策略，C4.5 是通过悲观剪枝策略来修正树的准确性，而 CART 是通过代价复杂度剪枝。

决策树算法应用

在 sklearn 库中与决策树相关的算法都存放在sklearn.tree模块里，该模块提供了 4 个决策树算法，下面对这些算法做简单的介绍：

1) .DecisionTreeClassifier()

这是一个经典的决策树分类算法，它提供了许多有用的参数，比如criterion，该参数有两个参数值，分别是 gini（基尼指数）和 entropy（信息增益），默认情况下使用“基尼指数”，其中“gini”用于创建 CART 分类决策树，而“entropy”用于创建 ID3 分类决策树。

2) .DecisionTreeRegressor()

它表示用决策树算法解决回归问题。

3) .ExtraTreeClassifier()

该算法属于决策树分类算法，但又不同于.DecisionTreeClassifier()算法，因为.ExtraTreeClassifier()选择“特征维度”作为判别条件时具有随机性，它首先从特征集合中随机抽取 n 个特征维度来构建新的集合，然后再从新的集合中选取“判别条件”。

4) .ExtraTreeRegressor()

该算法同样具有随机性，它与.ExtraTreeClassifier()随机过程类似，它主要解决机器学习中的回归问题。

决策树实现步骤

1) 确定纯度指标

确定纯度指标，用它来衡量不同“特征属性”所得到的纯度，并选取使得纯度取得最大值的“特征属性”作为的“判别条件”。

2) 切分数据集

通过特征属性做为“判别条件”对数据集集合进行切分。注意，使用过的“特征属性”不允许重复使用，该属性会从特征集合中删除。

3) 获取正确分类

选择特征集合内的特征属性，直至没有属性可供选择，或者是数据集样本已经完成分类为止。切记要选择占比最大的类别做为分类结果。

决策树算法应用

下面使用决策树算法对 Sklearn 库中的红酒数据进行模型训练，与数据预测，示例代码如下：

# 加载红酒数据集
from sklearn.datasets import load_wine
# 导入决策树分类器
from sklearn.tree import DecisionTreeClassifier
# 导入分割数据集的方法
from sklearn.model_selection import train_test_split
# 导入科学计算包
import numpy as np

# 加载红酒数据集
wine_dataset=load_wine()

# 分割训练集与测试集
X_train,X_test,y_train,y_test=train_test_split(wine_dataset['data'],wine_dataset['target'],test_size=0.2,random_state=0)

# 创建决策时分类器--ID3算法
tree_model=DecisionTreeClassifier(criterion="entropy")
# 喂入数据
tree_model.fit(X_train,y_train)
# 打印模型评分
print(tree_model.score(X_test,y_test))

# 给出一组数据预测分类
X_wine_test=np.array([[11.8,4.39,2.39,29,82,2.86,3.53,0.21,2.85,2.8,.75,3.78,490]])
predict_result=tree_model.predict(X_wine_test)
print(predict_result)
print("分类结果：{}".format(wine_dataset['target_names'][predict_result]))

0.9166666666666666

[1]

分类结果：['class_1']