机器学习（八）：决策树

一、什么是决策树？

决策树算法采用树形结构，使用层层推理来实现最终的分类。决策树由下面几种元素构成：

• 根节点：包含样本的全集
• 内部节点：对应特征属性测试
• 叶节点：代表决策的结果 如图所示：

预测时，在树的内部节点处用某一属性值进行判断，根据判断结果决定进入哪个分支节点，直到到达叶节点处，得到分类结果。

这是一种基于 if-then-else 规则的有监督学习算法，决策树的这些规则通过训练得到，而不是人工制定的。

举个简单的例子，以女生约会为案例：第一眼先看照片，颜值打几分？然后再看年收入，长得帅的就可以少挣点，毕竟 “帅也可以当饭吃啊”。不帅的呢？那收入必须要求高一点，“颜值不够，薪资来凑”。薪资还差点的，再看看学历是不是研究生 / 985/211，看看身高有没有 180…… 所以你就可以对号入座了，发现自己哪条都不符合，好了，去好好“搬砖” 吧。 再举个案例：银行要用机器学习算法来确定是否给客户发放贷款，为此需要考察客户的年收入，是否有房产这两个指标。领导安排你实现这个算法，你想到了最简单的决策模型，很快就完成了这个任务。

二、决策树学习的 3 个步骤

如图：

2.1 特征选择

特征选择决定了使用哪些特征来做判断。在训练数据集中，每个样本的属性可能有很多个，不同属性的作用有大有小。因而特征选择的作用就是筛选出跟分类结果相关性较高的特征，也就是分类能力较强的特征。

在特征选择中通常使用的准则是：信息增益。我们可以用PC算法来做到。

2.2 决策树生成

选择好特征后，就从根节点触发，对节点计算所有特征的信息增益，选择信息增益最大的特征作为节点特征，根据该特征的不同取值建立子节点；对每个子节点使用相同的方式生成新的子节点，直到信息增益很小或者没有特征可以选择为止。

2.3 决策树剪枝

剪枝的主要目的是对抗「过拟合」，通过主动去掉部分分支来降低过拟合的风险。

三、信息增益、信息增益率、Gini系数 3.1 熵

熵描述事件的不确定性，单位是bit。如果某个事件有 n 个结果，每个结果的概率为 pn。那么这个事件的熵 H§ 的定义为： 举例：大学期末的数学考试有单选题和多选题。对于一个完全没有学习过的学生，分别来做两种题型。

• 假设做单项选择题，4个选项是正确选项的概率都是1/4。那么单项选择题的答案的熵就是，-0.25log0.25-0.25log0.25-0.25log0.25-0.25log0.25=-40.25log0.25=2bit。
• 假设做多项选择题，一共有15个答案。那么多项选择题的答案的熵就是，-15*（1/15）*log（1/15）=3.91bit。

3.2 条件熵

熵是对事件结果不确定性的度量，但在知道有些条件时，不确定性会变小。例如，一个人是否是艾滋病的阳性，这个事件的不确定性会存着医疗检测结果而降低。

条件熵衡量的就是在某个条件 X 下，事件 Y 的不确定性，记作 H(Y|X) 。其定义式为 理解为，X 事件每个可能性的结果的熵乘以发生概率的求和。

3.3 信息熵

信息熵是用来评估样本集合的纯度的一个参数，就是说，给出一个样本集合，这个样本集合中的样本可能属于好多不同的类别，也可能只属于一个类别，那么如果属于好多不同的类别的话，我们就说这个样本是不纯的，如果只属于一个类别，那么，我们就说这个样本是纯洁的。

而信息熵这个东西就是来计算一个样本集合中的数据是纯洁的还是不纯洁的。公式：

理解：计算一个集合的纯度，就是把集合中每一个类别所占的比例（k从1到 ，其中 表示类别的个数）乘上它的对数，然后加到一起，然后经过计算之后，可以得到一个数据集的信息熵，然后根据信息熵，可以判断这个数据集是否纯粹。信息熵越小的话，表明这个数据集越纯粹。信息熵的最小值为0，此时数据集D中只含有一个类别。

3.4 信息增益

信息增益是知道了某个条件后，事件的不确定性下降的程度。写作 g(X,Y)。它的计算方式为熵减去条件熵，如下 表示的是，知道了某个条件后，原来事件不确定性降低的幅度。简单理解为信息熵的变化值就是信息增益。

信息增益有什么用呢？有用，可以根据信息增益值的大小来判断是否要用这个属性去划分数据集，如果得到的信息增益比较大，那么就说明这个属性是用来划分数据集比较好的属性，否则则认为该属性不适合用来划分数据集。这样有助于去构建决策树。著名的算法ID3就是采用信息增益来作为判断是否用该属性划分数据集的标准。

3.5 信息增益率

用信息增益作为评判划分属性的方法其实是有一定的缺陷的，信息增益准则对那些属性的取值比较多的属性有所偏好，也就是说，采用信息增益作为判定方法，会倾向于去选择属性取值比较多的属性。为了弥补这个缺点，如果属性值较少的话，我们使用信息增益率作为判定方法。

假如某个条件极其严格，比如某个同学提前知道了所有选题的答案，那么将选题的序号作为条件，不存在任何不确定性，所以可以得到最大的信息增益。但是这个条件是没有意义的，假设老师换一份考卷答案就全部作废了。信息增益率在信息增益的基础上增加了惩罚项，惩罚项是特征的固有值，是避免上述情况而设计的。

采用信息增益率可以解决ID3算法中存在的问题，因此将采用信息增益率作为判定划分属性好坏的方法称为C4.5。需要注意的是，增益率准则对属性取值较少的时候会有偏好，为了解决这个问题，C4.5并不是直接选择增益率最大的属性作为划分属性，而是之前先通过一遍筛选，先把信息增益低于平均水平的属性剔除掉，之后从剩下的属性中选择信息增益率最高的，这样的话，相当于两方面都得到了兼顾。

3.6 基尼系数

基尼指数（基尼不纯度）：表示在样本集合中一个随机选中的样本被分错的概率。 简单直观地来说，基尼系数反映了从数据集D中随机抽取两个样本，类别标记不同的概率。

基尼系数比信息熵要简单很多，基尼系数的计算公式如下所示：

对于一个系统来说一共有k类的信息，第i类信息所占比例为pi。如三个类别的鸢尾花数据集一共有 150 个样本，其中每个类别的样本个数都是 50，因此对于鸢尾花数据集来说，k=3:

• 第一种鸢尾花所占比例为 50/150=1/3,即p1
• 第二种鸢尾花所占比例为 50/150=1/3,即p2
• 第三种鸢尾花所占比例为 50/150=1/3,即p3

举例：有一个三个类别的数据集A,三个类别所长比例都为1/3,则此时这个系统的基尼系数为： 举例：有一个三个类别的数据集B，三个类别所占比例分别为1/10,2/10,7/10。此时这个系统的基尼系数为： Gini系数越小，代表D集合中的数据越纯，这和信息增益（比）相反。CART算法就是“选择那个使得划分后基尼系数最小的属性作为最优化分属性”.。

四、3 种典型的决策树算法

4.1 ID3 算法

ID3 是最早提出的决策树算法，他就是利用信息增益来选择特征的。

4.2 C4.5 算法

它是 ID3 的改进版，他不是直接使用信息增益，而是引入“信息增益比”指标作为特征的选择依据。

4.3 CART

这种算法即可以用于分类，也可以用于回归问题。CART 算法使用了基尼系数取代了信息熵模型。

4.4 三种算法的比较

• ID3：倾向于选择水平数量较多的变量（偏向数值比较多的特征），可能导致训练得到一个庞大且深度浅的树；另外输入变量必须是分类变量（连续变量必须离散化）；最后无法处理空值。
• C4.5在ID3的基础上选择了信息增益率替代信息增益，它更偏心于数量较少的变量。同时，采用二分法来处理连续值的特征，但是生成树浅的问题还是存在，且只能处理分类问题。
• CART以基尼系数替代熵，划分规则是最小化不纯度而不是最大化信息增益（率）。同时只允许生成二叉树，增加树的深度，而且可以处理连续特征和回归问题。
• scikit-learn实现的决策树更默认是CRAT决策树，即判断标准默认为基尼系数。也可以手动修改，比如节点的划分标准也可以选择采用熵来划分。

五、案例实现

决策树主要用于分类，因此我在这里介绍的是分类，而不是回归。

5.1 数据集

数据集如下： 每一列的变量说明如下：

• 购买价格
• 保养价格
• 门的数量
• 可容纳人数
• 后备箱大小
• 安全性大小

最后一列表示安全性，分别表示六种可能性：

• acc （接受）
• unacc（不接受）
• good（好）
• v-good（非常好）

5.2 算法参数

分类决策树总共有12个参数可以自己调整，以下是主要参数说明：

1.用于模型调参的参数：

• criterion（划分标准）：有两个参数 ‘entropy’（熵） 和 ‘gini’（基尼系数）可选，默认为gini。
• max_depth（树的最大深度）：默认为None，此时决策树在建立子树的时候不会限制子树的深度。也可以设置具体的整数，一般来说，数据少或者特征少的时候可以不管这个值。如果模型样本量多，特征也多的情况下，推荐限制这个最大深度，具体的取值取决于数据的分布。常用的可以取值10-100之间。
• min_samples_split（分割内部节点所需的最小样本数）：意思就是只要在某个结点里有k个以上的样本，这个节点才需要继续划分，这个参数的默认值为2，也就是说只要有2个以上的样本被划分在一个节点，如果这两个样本还可以细分，这个节点就会继续细分
• min_samples_leaf（叶子节点上的最小样本数）：当你划分给某个叶子节点的样本少于设定的个数时，这个叶子节点会被剪枝，这样可以去除一些明显异常的噪声数据。默认为1，也就是说只有有两个样本类别不一样，就会继续划分。如果是int，那么将min_samples_leaf视为最小数量。如果为float，则min_samples_leaf为分数，ceil(min _ samples _ leaf * n _ samples)为每个节点的最小样本数。

2.用于不平衡样本预处理参数：

• class_weight: 这个参数是用于样本不均衡的情况下，给正负样本设置不同权重的参数。默认为None，即不设置权重。

5.3 案例实现

第一步：读取数据

import pandas as pd
import warnings
warnings.filterwarnings('ignore') # 忽略警告

data = 'car_evaluation.csv'
col_names =['buying', 'maint', 'doors', 'persons', 'lug_boot', 'safety', 'class']

df = pd.read_csv(data) 
df.columns = col_names # 添加列名

df

如下： 第二步： 简单的探索分析。 1）查看类别数量

df['class'].value_counts() # 查看每一个类数量

如下：

unacc    1209
acc       384
good       69
vgood      65
Name: class, dtype: int64

2）查看缺失值数量

df.isnull().sum() # 缺失值查看

如下：

buying      0
maint       0
doors       0
persons     0
lug_boot    0
safety      0
class       0
dtype: int64

第三步： 提取自变量与因变量

X = df.drop(['class'], axis=1) 

y = df['class']

第四步：分割数据

from sklearn.model_selection import train_test_split
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size = 0.25, random_state = 42) 

第五步： 数据转换。将原始数据转换为有用特征的过程，可以揭示有关模型的有用见解，从而提高其预测能力。在此步骤中，对分类值进行编码并对数据进行其他适当的更改。

# pip install category_encoders
import category_encoders as ce

encoder = ce.OrdinalEncoder(cols=['buying', 'maint', 'doors', 'persons', 'lug_boot', 'safety'])
X_train = encoder.fit_transform(X_train)
X_test = encoder.transform(X_test)
X_train.head()

如下：

第六步：建立模型并训练。

from sklearn.tree import DecisionTreeClassifier # 导入决策树
# 选择基尼系数作为判断标准，树深度为3
clf_gini = DecisionTreeClassifier(criterion='gini', max_depth=3, random_state=0)

clf_gini.fit(X_train, y_train) #训练模型

第七步： 预测。

y_pred_gini = clf_gini.predict(X_test) # 预测模型
y_pred_gini[0:5] # 预测前五个结果

如下：

array(['unacc', 'unacc', 'unacc', 'acc', 'unacc'], dtype=object)

第八步：评估。

from sklearn.metrics import accuracy_score

print('标准为基尼指数的模型准确度得分: {0:0.4f}'. format(accuracy_score(y_test, y_pred_gini)))

输出：

标准为基尼指数的模型准确度得分: 0.7940

第九步：根据训练与测试的准确度来看看是否过拟合与欠拟合。通过计算训练数据和测试数据的准确度得分来确保模型既不会过拟合也不会欠拟合数据。

print('训练精度: {:.4f}'.format(clf_gini.score(X_train, y_train)))

print('测试精度: {:.4f}'.format(clf_gini.score(X_test, y_test)))

输出：

训练准确度: 0.7907
测试准确度: 0.7940

第十步：可视化决策过程。

import matplotlib.pyplot as plt

plt.figure(figsize=(12,8))
from sklearn import tree
tree.plot_tree(clf_gini.fit(X_train, y_train))

如下： 彩色的图形：

import graphviz 
dot_data = tree.export_graphviz(clf_gini, out_file=None, 
                              feature_names=X_train.columns,  
                              class_names=y_train,  
                              filled=True, rounded=True,  
                              special_characters=True)

graph = graphviz.Source(dot_data) 

graph 

如下： 第十一步 ：计算混淆矩阵。

from sklearn.metrics import confusion_matrix
cm = confusion_matrix(y_test, y_pred_gini)
print('混淆矩阵\n\n',cm)

如下：

[[ 93   0  12   0]
 [ 16   0   0   0]
 [ 40   0 250   0]
 [ 21   0   0   0]]

第十二步： 可视化混淆矩阵：

# 可视化混淆矩阵
from sklearn.metrics import plot_confusion_matrix
plot_confusion_matrix(clf_gini , X_test, y_test)  
plt.show()

如下：

四、参数调优 4.1 确定max_depth最优

我们只能通过无限遍历来选择：

## 确定最佳深度
import numpy as np
from sklearn.tree import DecisionTreeClassifier # 导入决策树
score_all=[]
# range(start, stop[, step])
for i in range(1,100,1):
    # 选择基尼系数作为判断标准，树深度为3
    clf_gini = DecisionTreeClassifier(criterion='gini', max_depth=i, random_state=0)
    clf_gini.fit(X_train, y_train) #训练模型
    y_pred_gini = clf_gini.predict(X_test) # 预测模型
    y_pred_gini[0:5] # 预测前五个结果
    from sklearn.metrics import accuracy_score
    acc=accuracy_score(y_test, y_pred_gini)
#   print(acc)
    score_all.append([i,acc])
ScoreAll = np.array(score_all)
max_score = np.where(ScoreAll==np.max(ScoreAll[:,1]))[0][0] #找出最高得分对应的索引
print("最优参数以及最高得分:",ScoreAll[max_score])  
plt.figure(figsize=[20,5])
plt.plot(ScoreAll[:,0],ScoreAll[:,1])
plt.show()

如下： 所以深度最佳为12。确定好后再去修改原来设定的参数3为12,重新跑一遍，重新跑如下： 训练决策图如下： 保存决策树图形为pdf：

import graphviz 
dot_data = tree.export_graphviz(clf_gini, out_file=None, 
                              feature_names=X_train.columns,  
                              class_names=y_train,  
                              filled=True, rounded=True,  
                              special_characters=True)

graph = graphviz.Source(dot_data) 
graph.render(view=True,format="pdf",filename='etree.pdf') #保存为pdf

graph 

4.2 确定min_samples_split最优

# 分割内部节点所需的最小样本数
## 确定最佳深度max_depth
import numpy as np
import matplotlib.pyplot as plt
from sklearn.tree import DecisionTreeClassifier # 导入决策树
score_all=[]
# range(start, stop[, step])
# 带入最佳深度后，再遍历2到20的内部最小样本数
for i in range(2,20,1):
    # 选择基尼系数作为判断标准，树深度为3
    clf_gini = DecisionTreeClassifier(criterion='gini', max_depth=12, min_samples_split=i,random_state=0)
    clf_gini.fit(X_train, y_train) #训练模型
    y_pred_gini = clf_gini.predict(X_test) # 预测模型
    y_pred_gini[0:5] # 预测前五个结果
    from sklearn.metrics import accuracy_score
    acc=accuracy_score(y_test, y_pred_gini)
#   print(acc)
    score_all.append([i,acc])
ScoreAll = np.array(score_all)
max_score = np.where(ScoreAll==np.max(ScoreAll[:,1]))[0][0] #找出最高得分对应的索引
print("最优参数以及最高得分:",ScoreAll[max_score])  
plt.figure(figsize=[20,5])
plt.plot(ScoreAll[:,0],ScoreAll[:,1])
plt.show()
# 结果显示默认的2就是最佳

如图： 结果显示默认的2就是最佳。

4.3 确定min_samples_leaf参数

# 确定
# 分割内部节点所需的最小样本数min_samples_split
## 确定最佳深度max_depth
import numpy as np
import matplotlib.pyplot as plt
from sklearn.tree import DecisionTreeClassifier # 导入决策树
score_all=[]
# range(start, stop[, step])
# 带入最佳深度=12，min_samples_split=2，遍历min_samples_leaf = i
for i in range(1,20,1):
    # 选择基尼系数作为判断标准，树深度为3
    clf_gini = DecisionTreeClassifier(criterion='gini', max_depth=12, min_samples_split=2,min_samples_leaf = i,random_state=0)
    clf_gini.fit(X_train, y_train) #训练模型
    y_pred_gini = clf_gini.predict(X_test) # 预测模型
    y_pred_gini[0:5] # 预测前五个结果
    from sklearn.metrics import accuracy_score
    acc=accuracy_score(y_test, y_pred_gini)
    score_all.append([i,acc])
ScoreAll = np.array(score_all)
max_score = np.where(ScoreAll==np.max(ScoreAll[:,1]))[0][0] #找出最高得分对应的索引
print("最优参数以及最高得分:",ScoreAll[max_score])  
plt.figure(figsize=[20,5])
plt.plot(ScoreAll[:,0],ScoreAll[:,1])
plt.show()
# 最佳参数还是1

如下：

4.4 利用网格搜索确定最佳

根据我们前边的一系列操作，我们确定因为max_depth在12附近，min_samples_split在2附近，min_samples_leaf在1附近是最优参数，所以我们分别在这个附近利用网格搜索得到最优参数。因为要涉及到三个参数联调，这里就要用到网格搜索函数。代码如下：

# 网格搜索确定内联最佳
from sklearn.model_selection import GridSearchCV
param_grid = {
    'max_depth':np.arange(9, 15),
    'min_samples_leaf':np.arange(2, 5),
    'min_samples_split':np.arange(1, 5)}

rfc = DecisionTreeClassifier(random_state=66)
GS = GridSearchCV(rfc,param_grid,cv=10)
GS.fit(X_train, y_train)
print(GS.best_params_)
print(GS.best_score_)
#这里三个参数和我们前边所暂定的参数都不一样。证明三者之间确实是相互影响的。最终确定还是选取开始的三个。

结果为：

{'max_depth': 12, 'min_samples_leaf': 2, 'min_samples_split': 2}
0.9304889683959452

更加暴力网格搜索：

# 更加完整暴利用网格搜索确定内联最佳。但是计算更花时间。
from sklearn.model_selection import GridSearchCV
param_grid = {
    'max_depth':np.arange(1, 30),
    'min_samples_leaf':np.arange(2, 6),
    'min_samples_split':np.arange(1, 6)}

rfc = DecisionTreeClassifier(random_state=66)
GS = GridSearchCV(rfc,param_grid,cv=10)
GS.fit(X_train, y_train)
print(GS.best_params_)
print(GS.best_score_)
#暴利费时间,还是得出结果与上面一样。

如下：

{'max_depth': 12, 'min_samples_leaf': 2, 'min_samples_split': 2}
0.9304889683959452

经过我们的调优，从开始的0.79调至0.93，这是很大的进步。

五、决策树的优缺点

优点：

• 决策树易于理解和解释，可以可视化分析，容易提取出规则；
• 可以同时处理标称型和数值型数据；
• 比较适合处理有缺失属性的样本；
• 能够处理不相关的特征；
• 测试数据集时，运行速度比较快；
• 在相对短的时间内能够对大型数据源做出可行且效果良好的结果。
• 决策树不需要对数据进行标准化
• 决策树清楚地表明哪些字段对于预测或分类最重要。

缺点：

• 容易发生过拟合（随机森林可以很大程度上减少过拟合）；
• 容易忽略数据集中属性的相互关联；
• 决策树不太适合目标是预测连续属性值的估计任务。