系列笔记

  1. Decision Tree
  2. Ensemble Learning
  3. GBDT / XGBoost / LightGBM

简介

决策树由结点和有向边组成。结点有两种类型：内部节点和叶结点，内部结点表示一个特征或属性，叶结点表示一个类。棵树仅有一层划分的决策树，亦称“决策树桩”（decision stump）

二叉树的几何解释：向量空间中特征不相关的矩阵划分，经过一系列的决策划分，得到相应类别区域。

决策树是一个递归过程，有三种情形会导致递归返回：
（1）当前结点包含的样本全属于同一类别，无需划分
（2）当前属性集为空，或所有样本在所有属性上的取值相同，无法划分
（3）当前节点包含的样本集合为空，不能划分

决策树学习的基本算法
决策树学习的基本算法

决策树的关键问题

  • 问题数：
    • 离散值情况：以特征或特征的可能离散值作为问题
    • 连续值情况：以每个维度的样本特征值作为问题
  • 划分（问题）选择
    1. 非纯度（Impurity Measure）：IM最大时各类别概率相等；IM最小时只有一类
      • 非纯度的熵度量
        $$ I(D)=Entropy(D)=-sum^k_{i=1}p_ilog p_i $$
      • 非纯度的基尼度量
        $$ I(D)=Gini(D)=1-\sum^k_{i=1}p_i^2 $$
    2. 划分选择目标：选择最大减少类别非纯度的问题作为划分点
      • 非纯度的减少量：
        $$ \Delta I(t)=I(t)-\frac{N_{tY}}{N_t}I(tY)-\frac{N_{tN}}{N_t}I(tN)$$
    3. 基于非纯度变化量的三个指标：
      1. 信息增益（熵度量）：越大越好
        对于样本集合$D$，类别数为$K$，数据集$D$的经验熵表示为：
        $$H(D)=-\sum^K_{k=1}\frac{|C_k|}{|D|}log_2\frac{|C_k|}{|D|}$$
        其中$C_k$是样本集合$D$中属于第$k$类的样本子集，$|C_k|$表示该子集的元素个数，$|D|$表示样本集合的元素个数，计算某个特征$A$对于数据集$D$的经验条件熵$H(D|A)$为：
        $$H(D|A)=\sum^n_{i=1}\frac{|D_i|}{|D|}H(D_i)=\sum^n_{i=1}\frac{|D_i|}{|D|}(-\sum^k_{k=1}\frac{|D_{ik}|}{|D_i|}log_2\frac{|D_{ik}|}{|D_i|})$$
        其中$D_i$表示$D$中特征$A$取第$i$个值的样本子集，$D_{ik}$表示$D_i$中属于第$k$类的样本子集，于是信息增益可以表示为二者的差：
        $$ Gain(D,a)=H(D)-H(D|A)$$
        存在的问题：$Gain(D,a)$倾向于具有大量值的属性
      2. 增益率（信息增益与数据集$D$关于问题$a$的熵值之比）：越大越好，特征$A$对于数据集$D$的信息增益比定义为：
        $$ Gini_ratio(D,A)=\frac{Gain(D,A)}{H_A(D)} $$
        $$H_A(D)=-\sum^n_{i=1}\frac{｜D_i｜}{｜D｜}log_2\frac{｜D_i｜}{｜D｜}$$
      3. 基尼指数（基尼度量）：越小越好，描述数据的纯度，与信息熵含义类似
        $$Gini(D)=1-\sum^n_{k=1}(\frac{|C_k|}{|D|})^2$$
        特征$A$的基尼指数定义为：
        $$Gini(D｜A)=\sum^n_{i=1}\frac{|D_i|}{|D|}Gini(D_i)$$
    4. 节点类别设置：叶子结点纯度达到预设阈值后停止划分，并对叶子结点进行类别设置。按概率最大的类别设定：
      $$j=argmax_i p_i$$
  • 决策树生成
    从顶向下（不断增加一个节点）
    • 准则：所有划分中选择一个使$\Delta I$(非纯度减少量)最大的划分为节点，加入决策树
    • 贪婪学习：根据划分准则，在问题集上进行划分，直到Impurity不能再改善或达到较小的改善
    • 停止规则：设定阈值
  • 剪枝处理（防止过拟合）
    1. 预剪枝（prepruning）：在决策树生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点标记为叶结点
    2. 后剪枝（postpruning）：先从训练集生成一颗完整的决策树，然后自底向上对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升，则将该子树替换为叶结点。后剪枝决策树的欠拟合风险很小，训练时间开销比未剪枝决策树和预剪枝决策树都要大得多

经典决策树模型

ID3

  • 属性特征作为结点问题，划分选择实际是特征选择的过程
  • 划分选择依据：最大化信息增益
  • ID3相当于用极大似然法进行概率模型的选择
  • 算法流程：
    ID3
    ID3决策树

C4.5

  • 属性特征作为结点问题，划分选择实际是特征选择的过程
  • 划分选择依据：最大化信息增益率
  • 算法流程：
    C4.5
    C4.5决策树

对ID3的改进：

  • 用信息增益率选择属性，克服了信息增益选择属性时偏向选择取值多的属性的不足
  • 在树构造的过程中进行剪枝
  • 能完成对连续属性的离散化处理
  • 能够对不完整数据进行处理

CART

  • 属性特征离散值作为节点问题，本质是二叉树
  • 划分选择依据：最小化基尼指数
  • 预测结果为概率分布，即在输入给定的条件下输出条件概率分布
  • ID3、C4.5只能分类，CART既能分类也能回归，回归时采用均方误差做评价；ID3、C4.5特征只使用一次，CART的特征可重复利用
  • 算法流程
    CART
    CART决策树

决策树计算实例

分别利用三种决策树计算最有划分特征

eg

  1. ID3（最大化信息增益）
    $$H(D)=-\frac{3}{5}log_2\frac{3}{5}-\frac{2}{5}log_2\frac{2}{5}=0.971$$
    $$\begin{aligned}
    H(D|年龄)&=\frac{1}{5}H(老)+\frac{4}{5}H(年轻)=\frac{1}{5}(-0)+\frac{4}{5}(-\frac{2}{4}log_2\frac{2}{4}-\frac{2}{4}log_2\frac{2}{4})=0.8
    \end{aligned}$$
    $$g(D,年龄)=H(D)-H(D|年龄)=0.171$$
    同理：
    $g(D,长相)=0.42$
    $g(D,工资)=0.42$
    $g(D,写代码)=0.971$
    写代码为最优划分特征

  2. C4.5（最大化信息增益率）
    $$H_{年龄}(D)=-\frac{1}{5}log_2\frac{1}{5}-\frac{4}{5}log_2\frac{4}{5}=0.722$$
    $$g_R(D,年龄)=\frac{g(D,年龄)}{H_{年龄}(D)}=\frac{0.171}{0.722}=0.236$$
    同理：
    $g_R(D,长相)=0.306$
    $g_R(D,工资)=0.306$
    $g_R(D,写代码)=1$
    写代码为最优划分特征

  3. CART（最小基尼指数）
    $$\begin{aligned}
    Gini(D|年龄=老)=\frac{1}{5}\times(1-1)+\frac{4}{5}\times(1-(\frac{1}{2})^2-(\frac{1}{2})^2)=0.4=Gini(D|年龄=年轻)=Gini(D|年龄)
    \end{aligned}$$
    $$\begin{aligned}
    Gini(D|长相=帅)=\frac{4}{5}\times(1-(\frac{1}{2})^2-(\frac{1}{2})^2)=0.4=Gini(D|长相=丑)
    \end{aligned}$$
    $$\begin{aligned}
    Gini(D|写代码)&=\frac{3}{5}\times(1-1)+\frac{2}{5}\times(1-1)=0
    \end{aligned}$$
    $$\begin{aligned}
    Gini(D|工资=高)&=\frac{3}{5}\times(1-(\frac{1}{3})^2-(\frac{2}{3})^2)+\frac{2}{5}\times(1-(\frac{1}{2})^2-(\frac{1}{2})^2)=0.47
    \end{aligned}$$
    $$\begin{aligned}
    Gini(D|工资=中等)&=\frac{4}{5}\times(1-(\frac{3}{4})^2-(\frac{1}{4})^2)=0.3
    \end{aligned}$$
    $$\begin{aligned}
    Gini(D|工资=低)&=\frac{4}{5}\times(1-(\frac{1}{2})^2-(\frac{1}{2})^2)=0.4
    \end{aligned}$$
    写代码为最优划分特征

代码实现

sklearn默认使用的是CART决策树，既可以分类也可以回归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
# Import the necessary modules and libraries
import numpy as np
from sklearn.tree import DecisionTreeRegressor
import matplotlib.pyplot as plt

# Create a random dataset
rng = np.random.RandomState(1)
X = np.sort(5 * rng.rand(80, 1), axis=0)
y = np.sin(X).ravel()
y[::5] += 3 * (0.5 - rng.rand(16))

# Fit regression model
regr_1 = DecisionTreeRegressor(max_depth=2)
regr_2 = DecisionTreeRegressor(max_depth=5)
regr_1.fit(X, y)
regr_2.fit(X, y)

# Predict
X_test = np.arange(0.0, 5.0, 0.01)[:, np.newaxis]
y_1 = regr_1.predict(X_test)
y_2 = regr_2.predict(X_test)

# Plot the results
plt.figure()
plt.scatter(X, y, s=20, edgecolor="black", c="darkorange", label="data")
plt.plot(X_test, y_1, color="cornflowerblue", label="max_depth=2", linewidth=2)
plt.plot(X_test, y_2, color="yellowgreen", label="max_depth=5", linewidth=2)
plt.xlabel("data")
plt.ylabel("target")
plt.title("Decision Tree Regression")
plt.legend()
plt.show()

运行结果：

decision tree regression

参考资料