机器学习——决策树(Decision Trees)

一、决策树

1、决策树的定义

决策树属于有监督学习算法，又称为CART（Classification and Regression Trees），可以用于解决分类和回归问题。

本文主要讨论决策分类树（下文称为决策树），即通过一系列决策规则分类数据。

2、适用场景

数据沿轴具有局部分段线性（local-piecewise linearity）。

3、核心思想——分而治之（Divide and Conquer）

决策树先选择数据属性，再构造决策规则。如下图所示，根据属性决策规则，划分数据类别。

二、决策树四要素

1、数据

决策树的数据即一系列自变量以及对应的因变量（分类标签）。

2、模型

根节点没有入边，有零个或多个出边，它表示所有数据，包含了属性决策规则。
中间节点有一个入边，有多个出边，包含了属性决策规则。
叶节点有一个入边，没有出边，具有分类标签，表示一个类别。
3、属性选择标准

决策树的属性选择标准（criterion），旨在降低每个节点的杂质（impurity）。
- Information Gain——Entropy
  $H(D)=-\sum_{i=1}^{n}\frac{\left| C_{i} \right|}{\left | D \right |}log\frac{\left| C_{i} \right|}{\left | D \right |}$
  
  其中，D为数据，n为类别数， $\left| D \right|$ 为D中的数据数量， $\left| C_{i} \right|$ 为D中属于第 i 个类别的数据数量，H(D)为数据D的熵值。
  
  $H(D|A)=\sum_{j=1}^{m}\frac{\left| D_{j} \right|}{\left | D \right |}H(D_{j})$
  
  其中，m为划分的数据子集数， $\left| D_{j} \right|$ 为划分后的第 j 个数据子集中数据数量，H(D|A)为D根据属性A划分后的熵值。
  
  其中，Gain(D,A)为Information Gain。
  - Gain Ratio
    相较于Information Gain，Gain Ratio考虑了属性划分产生的熵值，并进行调整。
    
    $H_{A}(D)=-\sum_{j=1}^{m}\frac{\left| D_{j} \right|}{\left | D \right |}log\frac{\left| D_{j} \right|}{\left | D \right |}$
    
    其中， $H_{A}(D)$ 为属性划分产生的熵值。
    
    $Gain Ratio(D,A)=\frac{Gain(D,A)}{H_{A}(D)}$
    
    其中，GainRatio(D,A)为Gain Ratio。
    - Gini Index
      $Gini(D)=\sum_{i=1}^{n}\frac{\left| C_{i} \right|}{\left | D \right |}(1-\frac{\left| C_{i} \right|}{\left | D \right |})=1-\sum_{i=1}^{n}(\frac{\left| C_{i} \right|}{\left | D \right |})^{2}$
      
      其中，Gini(D)为数据D的基尼系数。
      
      $Gini(D|A)=\sum_{j=1}^{m}\frac{\left| D_{j} \right|}{\left | D \right |}Gini(D_{j})$
      
      其中，Gini(D|A)为D根据属性A划分后的基尼系数。
      
      其中，GiniGain(D,A)为Gini Gain。
      
      4、构造算法
      
      决策树的构造算法，具体流程如下：
      1. 构造一个根节点，包含所有数据；
      2. 根据属性选择标准（Information Gain等），选择一个属性；
      3. 根据所选属性的值划分数据为不同数据子集；
      4. 为每个数据子集构造子节点，包含对应数据；
      5. 递归重复2-4步，直到满足停止标准。
      停止标准通常有三种：
      1. 纯净（purity）：叶节点只包含同一个类别的数据。
      2. 阈值（threshold）：叶节点中数据数量少于阈值。
      3. 没有剩余属性划分：通常每个属性仅划分一次，没有剩余属性即停止。
      根据属性选择标准不同，常用的构造算法有三种：
      1. ID3：使用Information Gain
      2. CART：使用Gini Index
      3. C4.5：使用Gain Ratio
      三、决策树削弱过拟合方法
      
      1、预剪枝（Pre-Purning）
      
      预剪枝即早停止，当叶节点数据数量少于阈值时停止。
      
      2、后剪枝（Post-Purning）
      
      后剪枝先构建一棵完整深入的树，当树出现过拟合问题（例如验证集准确度下降），再剪枝。
      
      四、随机森林
      
      1、随机森林的定义
      
      随机森林属于有监督学习算法，通过随机的数据子集和随机的属性选择构造多棵决策树，再汇总每棵决策树的结果产生最终结果。
      
      2、随机森林构造算法
      1. 随机选取部分样本构造数据子集，选取后放回；
      2. 根据数据子集构造决策树，随机选择属性进行构造；
      3. 重复1-2，构造多棵决策树；
      4. 根据所有决策树的结果，选择多数结果为最终结果。
      五、决策树实践（sklearn）
      
      以kaggle中数据集“Drugs A, B, C, X, Y for Decision Trees”为例
      
      1、数据准备
      
      直接下载使用“Drugs A, B, C, X, Y for Decision Trees”数据集，并读取数据集
```
import pandas as pd
dataset = pd.read_csv('./drug200.csv')  # 读取csv文件
```
      特征工程，将字符型的列进行序号编码
```
import category_encoders as ce
encoder = ce.OrdinalEncoder(cols=['Sex', 'BP', 'Cholesterol']).fit(dataset)  # 对Sex, BP, Cholesterol进行编码，并拟合
dataset_encoded = encoder.transform(dataset)  # 对dataset数据进行编码
```
      2、训练模型
      
      Hold-out，划分训练集和测试集
```
from sklearn.model_selection import train_test_split
X = dataset_encoded.drop(['Drug'], axis=1)  # 删除'Drug'列，得到特征矩阵X
y = dataset_encoded['Drug']  # 提取'Drug'列，得到目标向量y
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.33,
     random_state=23)  # 将X和y按照33%的比例划分为训练集和测试集，设置随机种子为23
```
      分别训练一个基于熵的决策树和一个基于基尼系数的决策树
```
from sklearn.tree import DecisionTreeClassifier
DTR_entropy = DecisionTreeClassifier(criterion='entropy', max_depth=3,
                                     random_state=0)  # 创建一个基于熵的决策树，设置最大深度为3，随机种子为0
DTR_gini = DecisionTreeClassifier(criterion='gini', max_depth=3, random_state=0)  # 创建一个基于基尼系数的决策树，设置最大深度为3，随机种子为0
DTR_entropy.fit(X_train, y_train)  # 用训练集数据拟合熵决策树
DTR_gini.fit(X_train, y_train)  # 用训练集数据拟合基尼系数决策树
```
      3、评估模型
      
      分别输出基于熵的决策树和基于基尼系数的决策树在训练集和测试集下的准确率
```
print("Score of train-set using entropy : {:.4f}".format(DTR_entropy.score(X_train, y_train)))  # 打印信息熵决策树在训练集上的准确率
print("Score of test-set using entropy : {:.4f}".format(DTR_entropy.score(X_test, y_test)))  # 打印信息熵决策树在测试集上的准确率
print("Score of train-set using gini : {:.4f}".format(DTR_gini.score(X_train, y_train)))  # 打印基尼系数决策树在训练集上的准确率
print("Score of test-set using gini : {:.4f}".format(DTR_gini.score(X_test, y_test)))  # 打印基尼系数决策树在测试集上的准确率
```
      结果如下：
      
      Score of train-set using entropy : 0.9254
      Score of test-set using entropy : 0.9091
      Score of train-set using gini : 0.9254
      Score of test-set using gini : 0.9091
      
      可视化基于熵的决策树和基于基尼系数的决策树
```
import matplotlib.pyplot as plt
from sklearn import tree
plt.figure(figsize=(12, 8))
plt.subplot(121)
tree.plot_tree(DTR_entropy.fit(X_train, y_train))  # 绘制熵决策树的图形
plt.title('Using entropy')
plt.subplot(122)
tree.plot_tree(DTR_entropy.fit(X_train, y_train))  # 绘制基尼系数决策树的图形
plt.title('Using gini')
plt.show()
```
      结果如下：