数据分析：决策树原理

主要解决三个问题：

选择哪个属性作为根节点；
选择哪些属性作为子节点；
什么时候停止并得到目标状态，即叶节点。

剪枝

给决策树瘦身，防止“过拟合”和“欠拟合”发生。

剪枝可以分为“预剪枝”（Pre-Pruning）和“后剪枝”（Post-Pruning）。

预剪枝：预剪枝是在决策树构造时就进行剪枝。方法是在构造的过程中对节点进行评估，如果对某个节点进行划分，在验证集中不能带来准确性的提升，那么对这个节点进行划分就没有意义，这时就会把当前节点作为叶节点，不对其进行划分。
后剪枝：后剪枝就是在生成决策树之后再进行剪枝，通常会从决策树的叶节点开始，逐层向上对每个节点进行评估。如果剪掉这个节点子树，与保留该节点子树在分类准确性上差别不大，或者剪掉该节点子树，能在验证集中带来准确性的提升，那么就可以把该节点子树进行剪枝。方法是：用这个节点子树的叶子节点来替代该节点，类标记为这个节点子树中最频繁的那个类。

指标

纯度：可以把决策树的构造过程理解成为寻找纯净划分的过程。数学上，我们可以用纯度来表示，纯度换一种方式来解释就是让目标变量的分歧最小。
信息熵：表示了信息的不确定度，随机离散事件出现的概率存在着不确定性，为了衡量这种信息的不确定性，提出了信息熵的概念。

p(i|t) 代表了节点 t 为分类 i 的概率，c代表结果有几种可能性。信息熵越大，纯度越低。当集合中的所有样本均匀混合时，信息熵最大，纯度最低。

我们在构造决策树的时候，会基于纯度来构建。而经典的 “不纯度”的指标有三种，分别是信息增益（ID3 算法）、信息增益率（C4.5 算法）以及基尼指数（Cart 算法）。

1. ID3算法（信息增益）：划分可以带来纯度的提高，信息熵下降

计算每个子节点的归一化信息熵，即按照每个子节点在父节点中出现的概率（下图中的 $\frac{|D_i|}{|D|}$ ），来计算这些子节点的信息熵，然后计算出该属性的信息增益。

- D：父亲节点
- $D_i$ ：子节点
- $Gain(D,a)$ ： $a$ 作为D（父亲）的属性选择

所以 ID3 有一个缺陷就是，有些属性可能对分类任务没有太大作用，但是他们仍然可能会被选为最优属性。这种缺陷不是每次都会发生，只是存在一定的概率。在大部分情况下，ID3 都能生成不错的决策树分类。针对可能发生的缺陷，后人提出了新的算法进行改进。

2. C4.5算法（ID3改进）：

使用信息增益率来代替信息增益
信息增益率=信息增益 / 属性熵
属性熵就是该属性自身的熵，如下例子中的温度属性熵如下计算：

采用悲观剪枝
离散化处理连续属性：C4.5 可以处理连续属性的情况，对连续的属性进行离散化的处理。比如打篮球存在的“湿度”属性，不按照“高、中”划分，而是按照湿度值进行计算，那么湿度取什么值都有可能。该怎么选择这个阈值呢，C4.5 选择具有最高信息增益的划分所对应的阈值。
处理缺失值

ID3 算法的优点是方法简单，缺点是对噪声敏感。训练数据如果有少量错误，可能会产生决策树分类错误。C4.5 在 ID3 的基础上，用信息增益率代替了信息增益，解决了噪声敏感的问题，并且可以对构造树进行剪枝、处理连续数值以及数值缺失等情况，但是由于 C4.5 需要对数据集进行多次扫描，算法效率相对较低。

使用graphviz绘制决策树

from sklearn import tree
import sys
import os
import graphviz
import numpy as np

data = np.array([[1,1], [1,0], [0,1], [0,0]])
target = np.array([1,1,0,0]) # 数据标注
clf = tree.DecisionTreeClassifier(criterion='entropy') # 创建决策树分类模型
clf = clf.fit(data, target) # 拟合数据

dot_data = tree.export_graphviz(clf, filled=True, out_file=None)
graph = graphviz.Source(dot_data)
graph

结果如下：

entropy代表信息增量
samples代表当前分类下的样本数目
value=[2, 0]是分类概率（是好苹果，不是好苹果）

CART决策树

基尼系数：用来衡量一个国家收入差距的常用指标。当基尼系数大于 0.4 的时候，说明财富差异悬殊。基尼系数在 0.2-0.4 之间说明分配合理，财富差距不大。
基尼系数本身反应了样本的不确定度。当基尼系数越小的时候，说明样本之间的差异性小，不确定程度低。分类的过程本身是一个不确定度降低的过程，即纯度的提升过程。所以 CART 算法在构造分类树的时候，会选择基尼系数最小的属性作为属性的划分。

公式如下：

$P(C_k|t)$ 表示节点t属于类型 $C_k$ 的概率，节点 $t$ 的基尼系数为 1 减去各类别 $C_k$ 概率平方和。

在 CART 算法中，基于基尼系数对特征属性进行二元分裂，假设属性 A 将节点 D 划分成了 D1 和 D2，如下图所示：

节点 D 的基尼系数等于子节点 D1 和 D2 的归一化基尼系数之和，用公式表示为：

所以在属性 A 的划分下，节点 D 的基尼系数为：

节点 D 被属性 A 划分后的基尼系数越大，样本集合的不确定性越大，也就是不纯度越高。

如何使用CART算法来创建分类树

直接使用DecisionTreeClassifier这个类，创建这个类的时候，默认情况下 criterion 这个参数等于 gini，也就是按照基尼系数来选择属性划分，即默认采用的是 CART 分类树。

from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score
from sklearn.tree import DecisionTreeClassifier
from sklearn.datasets import load_iris
# 准备数据集
iris=load_iris()
# 获取特征集和分类标识
features=iris.data
labels=iris.target
# 随机抽取33%数据作为测试集，其余作为训练集
train_features, test_features, train_labels, test_labels=train_test_split(features, labels, test_size=0.33, random_state=0)
# 创建CART分类树
clf = DecisionTreeClassifier(criterion='gini')
# 拟合构造CART分类树
clf = clf.fit(train_features, train_labels)
# 用CART分类树做预测
test_predict = clf.predict(test_features)
# 预测结果与测试集结果作比对
score = accuracy_score(test_labels, test_predict)
score

CART 回归树的工作流程

CART 回归树划分数据集的过程和分类树的过程是一样的，只是回归树得到的预测结果是连续值，而且评判“不纯度”的指标不同。在 CART 分类树中采用的是基尼系数作为标准，那么在 CART 回归树中，如何评价“不纯度”呢？实际上我们要根据样本的混乱程度，也就是样本的离散程度来评价“不纯度”。

样本的离散程度具体的计算方式是，先计算所有样本的均值，然后计算每个样本值到均值的差值。我们假设 x 为样本的个体，均值为 u。为了统计样本的离散程度，我们可以取差值的绝对值，或者方差。

其中差值的绝对值为样本值减去样本均值的绝对值： $|X-\mu|$
方差为每个样本值减去样本均值的平方和除以样本个数： $s=\frac{\sum \left ( x-\mu \right )^2}{n}$

所以这两种节点划分的标准，分别对应着两种目标函数最优化的标准，即用最小绝对偏差（LAD），或者使用最小二乘偏差（LSD）。这两种方式都可以让我们找到节点划分的方法，通常使用最小二乘偏差的情况更常见一些。

# 预测波士顿房价
from sklearn.metrics import mean_squared_error
from sklearn.model_selection import train_test_split
from sklearn.datasets import load_boston
from sklearn.metrics import r2_score,mean_absolute_error,mean_squared_error
from sklearn.tree import DecisionTreeRegressor

boston = load_boston()
print(boston.feature_names)
# 获取特征集和房价
features=boston.data
prices=boston.target
# 随机抽取33%的数据作为测试集
train_features, test_features, train_prices, test_prices=train_test_split(features, prices, test_size=0.33)
# 创建回归树
dtr=DecisionTreeRegressor()
dtr.fit(train_features, train_prices)
predict_price=dtr.predict(test_features)
print('回归树二乘偏差均值:', mean_squared_error(test_prices, predict_price))
print('回归树绝对值偏差均值:', mean_absolute_error(test_prices, predict_price))

['CRIM' 'ZN' 'INDUS' 'CHAS' 'NOX' 'RM' 'AGE' 'DIS' 'RAD' 'TAX' 'PTRATIO'
 'B' 'LSTAT']
回归树二乘偏差均值: 20.5040119760479
回归树绝对值偏差均值: 2.9850299401197606

输出图片：

from IPython.display import Image  
import pydotplus
graph=pydotplus.graph_from_dot_data(dot_data)
Image(graph.create_png())

CART决策树剪枝

CART 决策树的剪枝主要采用的是 CCP 方法，它是一种后剪枝的方法，英文全称叫做 cost-complexity prune。

这种剪枝方式用到一个指标叫做节点的表面误差率增益值，以此作为剪枝前后误差的定义。

其中 $Tt$ 代表以 t 为根节点的子树， $C(T_t)$ 表示节点 t 的子树没被裁剪时子树 $Tt$ 的误差， $C(t)$ 表示节点 t 的子树被剪枝后节点 t 的误差， $|T_t|$ 代子树 $Tt$ 的叶子数，剪枝后，T 的叶子数减少了 $|T_t|-1$ 。

所以节点的表面误差率增益值等于节点 t 的子树被剪枝后的误差变化除以剪掉的叶子数量。

因为我们希望剪枝前后误差最小，所以我们要寻找的就是最小α值对应的节点，把它剪掉。这时候生成了第一个子树。重复上面的过程，继续剪枝，直到最后只剩下根节点，即为最后一个子树。

得到了剪枝后的子树集合后，我们需要用验证集对所有子树的误差计算一遍。可以通过计算每个子树的基尼指数或者平方误差，取误差最小的那个树，得到我们想要的结果。

总结

CART 决策树，它是一棵决策二叉树，既可以做分类树，也可以做回归树。你需要记住的是，作为分类树，CART 采用基尼系数作为节点划分的依据，得到的是离散的结果，也就是分类结果；作为回归树，CART 可以采用最小绝对偏差（LAD），或者最小二乘偏差（LSD）作为节点划分的依据，得到的是连续值，即回归预测结果。

ID3 算法，基于信息增益做判断；
C4.5 算法，基于信息增益率做判断；
CART 算法，分类树是基于基尼系数做判断。回归树是基于偏差做判断。
工具：sklearn 中的 DecisionTreeClassifier 创建 CART 分类树，通过 DecisionTreeRegressor 创建 CART 回归树。