机器学习[3] - 监督模型之树模型

作者: 屹然1ran | 来源:发表于2021-03-17 17:10 被阅读0次

1. 基本概念

决策树模型为非参数监督模型，该模型为根据一系列的if-else逻辑组合而成。树可以看作是一个分段函数，并且树的层数越深，就会更贴合数据(fitted)。

西瓜问题的一颗决策树
显然决策树的生成时一个递归过程，且在以下三种情形下会导致递归返回：

当前结点包含的样本全属于同一类别：例如敲声清脆的瓜都是好瓜，则敲声音清脆下无需继续划分。
当前属性集为空，或是所有样本在所有属性上取值相同，无法划分：例如色泽黑色的瓜全都是敲声浊响根蒂蜷缩。
当前节点包含的样本集合为空，不能划分

分类和回归任务，决策树模型一般均可以执行。

1.1 分类树

DecisionTreeClassifier可以用作训练决策树分类模型。

from sklearn.datasets import load_iris
from sklearn import tree
X, y = load_iris(return_X_y=True)
clf = tree.DecisionTreeClassifier()
clf = clf.fit(X, y)
tree.plot_tree(clf)

Out[310]: 
[Text(167.4, 199.32, 'X[2] <= 2.45\ngini = 0.667\nsamples = 150\nvalue = [50, 50, 50]'),
 Text(141.64615384615385, 163.07999999999998, 'gini = 0.0\nsamples = 50\nvalue = [50, 0, 0]'),
 Text(193.15384615384616, 163.07999999999998, 'X[3] <= 1.75\ngini = 0.5\nsamples = 100\nvalue = [0, 50, 50]'),
 Text(103.01538461538462, 126.83999999999999, 'X[2] <= 4.95\ngini = 0.168\nsamples = 54\nvalue = [0, 49, 5]'),
 Text(51.50769230769231, 90.6, 'X[3] <= 1.65\ngini = 0.041\nsamples = 48\nvalue = [0, 47, 1]'),
 Text(25.753846153846155, 54.359999999999985, 'gini = 0.0\nsamples = 47\nvalue = [0, 47, 0]'),
 Text(77.26153846153846, 54.359999999999985, 'gini = 0.0\nsamples = 1\nvalue = [0, 0, 1]'),
 Text(154.52307692307693, 90.6, 'X[3] <= 1.55\ngini = 0.444\nsamples = 6\nvalue = [0, 2, 4]'),
 Text(128.76923076923077, 54.359999999999985, 'gini = 0.0\nsamples = 3\nvalue = [0, 0, 3]'),
 Text(180.27692307692308, 54.359999999999985, 'X[2] <= 5.45\ngini = 0.444\nsamples = 3\nvalue = [0, 2, 1]'),
 Text(154.52307692307693, 18.119999999999976, 'gini = 0.0\nsamples = 2\nvalue = [0, 2, 0]'),
 Text(206.03076923076924, 18.119999999999976, 'gini = 0.0\nsamples = 1\nvalue = [0, 0, 1]'),
 Text(283.2923076923077, 126.83999999999999, 'X[2] <= 4.85\ngini = 0.043\nsamples = 46\nvalue = [0, 1, 45]'),
 Text(257.53846153846155, 90.6, 'X[1] <= 3.1\ngini = 0.444\nsamples = 3\nvalue = [0, 1, 2]'),
 Text(231.7846153846154, 54.359999999999985, 'gini = 0.0\nsamples = 2\nvalue = [0, 0, 2]'),
 Text(283.2923076923077, 54.359999999999985, 'gini = 0.0\nsamples = 1\nvalue = [0, 1, 0]'),
 Text(309.04615384615386, 90.6, 'gini = 0.0\nsamples = 43\nvalue = [0, 0, 43]')]

1.2 回归树

DecisionTreeRegressor可以用于构建回归树。回归树为该叶节点的预测值为该组的值。

# 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)

2 划分选择

决策树模型的关键为划分选择，即应该使用哪个属性进行划分，以及该属性为连续值时该从哪个值划分。以下介绍常用于划分的几个指标。

2.1 信息增益 (information gain)

信息熵(information entropy)是度量样本集合纯度常用的一个指标。 $Ent(D)$ 越小，则纯度越高。

$Ent(D) = -\sum_{k=1}^{|y|}p_klog_2p_K$

对数为什么选择2作为底数，是信息学约定俗称的一个习惯，笔者这里推断可能原因是与2进制有关。

信息增益(information gain)则为在一个节点，划分后对划分前所带来的增益。一般而言， $Gain(D, a)$ 越大则使用属性 $a$ 进行划分带来的纯度提升越大。

$Gain(D, a) = Ent(D) - \sum_{v=1}^{V} \frac{D^v}{D} Ent(D^v)$

即我们选择信息增益大的属性a来进行划分，数学上的表示为 $a_* = arg max_{a \in A} Gain(D, a)$

使用信息增益作为划分指标，也就是经典的ID3(Iterative Dichotomise 3rd) 模型 [Quinlan, 1979, 1986]。

初次接触很难理解，以下为一个构建决策树的实例。

2.1.1 例子

周志华西瓜数据集

首先我们需要计算出根节点的信息熵，即使用“好瓜”这个字段来计算 $Ent(D)$ 。

$Ent(D) = -\sum_{k=1}^{|y|}p_klog_2p_K = -(\frac{8}{17}log_2\frac{8}{17} + \frac{9}{17}log_2\frac{9}{17} = 0.998)$

然后我们要计算出当前数据集内，每个属性的信息增益。以色泽为例，.若使用该属性对 D 进行划分，则可得到3个子集，分别记为：D1 (色泽=青绿)，D2 (色泽=乌黑)，D3 (色泽=浅白)：

$\begin{aligned} Ent(D^1) &= -(\frac{3}{6}log_2\frac{3}{6} + \frac{3}{6}log_2\frac{3}{6}) = 1.000, \\ Ent(D^2) &= -(\frac{4}{6}log_2\frac{4}{6} + \frac{2}{6}log_2\frac{2}{6}) = 0.918, \\ Ent(D^2) &= -(\frac{1}{5}log_2\frac{1}{5} + \frac{4}{5}log_2\frac{4}{5}) = 0.722, \\ Gain(D, 色泽) &= Ent(D) - \sum_{v=1}^{V} \frac{D^v}{D} Ent(D^v) \\ &= 0.998 - (\frac{6}{17} \times 1.000 + \frac{6}{17} \times 0.918 + \frac{5}{17} \times 0.722) \\ &= 0.109 \end{aligned}$

使用同样方法计算其他属性的信息增益：
$\begin{aligned} Gain(D, 色泽) &= 0.143, \\ Gain(D, 敲声) &= 0.141, \\ Gain(D, 纹理) &= 0.381, \\ Gain(D, 脐部) &= 0.289, \\ Gain(D, 触感) &= 0.006, \end{aligned}$

由于纹理的信息增益最高，所以选择他为划分属性。

基于纹理对根节点划分

然后每个节点再继续对比信息增益，然后向下划分。例如选择纹理=“清晰”为例，基于 $D^1$ 计算各属性的信息增益：

$\begin{aligned} Gain(D^1, 色泽) &= 0.043, \\ Gain(D^1, 根蒂) &= 0.458, \\ Gain(D^1, 敲声) &= 0.331, \\ Gain(D^1, 脐部) &= 0.458, \\ Gain(D^1, 触感) &= 0.458, \end{aligned}$

"根蒂"、 "脐部"、 "触感" 3 个属性均取得了最大的信息增益，可任选其中之一作为划分属性。最终我们获得了以下决策树：

西瓜数据集基于信息增益生成的决策树

2.2 增益率(gain ratio)

另一个经典的C4.5算法[Quinlan, 1993]则使用了增益率作为划分指标。引入增益率的原因为，ID3中的信息增益遇到多分类特征时，会偏大，便偏向于对多分类特征。

$\begin{aligned} Gain\_ratio(D, a) &= \frac{Gain(D, a)}{IV(a)} \\ IV(a) &= -\sum_{v=1}^{V}\frac{D^v}{D}log_2\frac{D^v}{D} \end{aligned}$

属性a可取值的数目越多， $IV(a)$ 便会越高，则对 $Gain(D, a)$ 的惩罚就会越大。

2.3 基尼系数(Gini index)

CART决策树[Breiman et al., 1984]使用基尼系数来选择划分属性。

$\begin{aligned} Gini(D) &= \sum_{k=1}^{|y|}\sum_{k' \neq k}p_kp_{k'} \\ &= 1 - \sum_{k = 1}^{|y|}p_k^2 \\ Gini_index(D, a) &=\sum_{v=1}^{V}\frac{D^v}{D}Gini(D^v) \end{aligned}$
于是，我们在候选属性集合A中，选择那个使得划分后基尼指数小的属性作为最优划分属性，即 $a_* = argmin_{a \in A} Gini\_index(D, a)$

3. 剪枝

剪枝(purning)是决策树对付“过拟合”的主要手段。在决策树学习中，为了尽可能正确分类训练样本，结点划分过程将不断重复，有时会造成决策树分支过多，这时就可能因训练样本学得“太好”了。剪枝，顾名思义就是将一个节点之后分叉剪掉，让该节点变为一个叶节点。

3.1 预剪枝

对每个结点划分前先进行估计，若当前结点的划分不能带来决策树的泛化性能的提升，则停止划分，并标记为叶结点。

西瓜数据集预剪枝

3.2 后剪枝

先从训练集生成一棵完整的决策树，然后自底向上对非叶子结点进行考察，若该结点对应的子树用叶结点能带来决策树泛化性能的提升，则将该子树替换为叶结点。

西瓜数据集后剪枝

后剪枝决策树的欠拟合风险很小，泛化性能往往优于预剪枝决策树。但后剪枝过程是在生成完全决策树之后进行的，并且要白底向上地对树中的所有非叶结点进行逐一考察，因此其训练时间开销比未剪枝决策树和预剪枝决策树都要大得多。

4. 连续值与缺失值

4.1 连续值

将连续值拆分，最简单的方法为二分法(bi-partition)。
给定拥有 $n$ 个样本量的样本集 $D$ 和连续属性 $a$ ，将 $a$ 的值从大到小排列，记为 $\{a^1, a^2, a^3,..., a^n\}\$ 。基于划分点 $t$ 可将D分为子集 $D_t^-$ 和 $D_t^+$ ， $D_t^-$ 为小于 $t$ 的样本， $D_t^+$ 为大于等于 $t$ 的样本。
$\begin{aligned} Gain(D, a) &= max_{t \in T_a} Gain(D,a,t) \\&=max_{t \in T_a}Ent(D) - \sum_{\lambda \in \lbrace-, +\rbrace }\frac{|D_t^\lambda|}{|D|}Ent(D_t^\lambda|) \end{aligned}$
于是我们选择一个可以最大化 $Gain(D, a, t)$ 的划分点。

4.1.1 例子：

data = pd.DataFrame({'is_house_owner': list('TFFTTFFFFT'),
                     'marriage': list('SMSMDDSMSD'),
                     'income': [125, 100, 100, 110, 60, 95, 85, 75, 90, 220],
                     'is_unable_payloan': list('FFFFFTTFTF')})

data
Out[197]: 
  is_house_owner marriage  income is_unable_payloan
0              T        S     125                 F
1              F        M     100                 F
2              F        S     100                 F
3              T        M     110                 F
4              T        D      60                 F
5              F        D      95                 T
6              F        S      85                 T
7              F        M      75                 F
8              F        S      90                 T
9              T        D     220                 F

我们需要将收入( $income$ 作为分类的特征)。

from numpy import log2
import numpy as np
import pandas as pd


def Sum_Every_Part_Log2(a):
    return -(a/a.sum()[0]*log2(a/a.sum()[0])).sum()[0]

def Cal_Entropy(ridge, data, y_name, x_name):
    df = data[[y_name, x_name]]
    return Sum_Every_Part_Log2(df[df[x_name] >= ridge].groupby(y_name).count()) + Sum_Every_Part_Log2(df[df[x_name] < ridge].groupby(y_name).count())

Entropy_Result = pd.DataFrame({'ridge': data['income'].sort_values().append(pd.Series([max(data['income'])]))})
Entropy_Result['Entropy'] = Entropy_Result['ridge'].apply(lambda x: Cal_Entropy(x, data, 'is_unable_payloan', 'income'))

Entropy_Result
Out[203]: 
   ridge   Entropy
4     60  0.881291
7     75  0.918296
6     85  0.954434
8     90  1.781416
5     95  1.650022
1    100  0.970951
2    100  0.970951
3    110  0.985228
0    125  0.954434
9    220  0.918296
0    220  0.918296

可以看到在95的时候，信息熵最大，故选择95作为划分点划分为>=95和<95两部分。

4.2 缺失值

缺失值的处理方法为，在计算 $Gain(D, a)$ 时，乘特征a的数据缺失率。
例如：
$Gain(D,色泽)=\rho \times Gain(D,色泽)$

5. 例子

使用CART对titanic dataset的用户生存率进行预测。

import graphviz
import numpy as np
import pandas as pd
from sklearn import tree
from sklearn.feature_extraction import DictVectorizer
from sklearn.model_selection import cross_val_score
from sklearn.tree import DecisionTreeClassifier

x = titan[['pclass', 'age', 'sex', 'fare']]
y = titan['survived']

x_train, x_test, y_train, y_test = train_test_split(x, y, random_state = 99)

transfer = DictVectorizer(sparse=False)
x_train = transfer.fit_transform(x_train.to_dict(orient="records"))
x_test = transfer.fit_transform(x_test.to_dict(orient="records"))

score = []

for i in range(1, 21):
    estimator = DecisionTreeClassifier(criterion="entropy", max_depth = i)
    estimator.fit(x_train, y_train)
    precision.append(estimator.score(x_test, y_test))

score

Out[183]: 
[0.7477477477477478,
 0.7477477477477478,
 0.7972972972972973,
 0.7972972972972973,
 0.8063063063063063,
 0.7882882882882883,
 0.7882882882882883,
 0.7927927927927928,
 0.7882882882882883,
 0.7882882882882883,
 0.7702702702702703,
 0.7522522522522522,
 0.7837837837837838,
 0.7612612612612613,
 0.7567567567567568,
 0.7387387387387387,
 0.7432432432432432,
 0.7432432432432432,
 0.7477477477477478,
 0.7477477477477478]

可以看到树的深度在5时，测试集的精度最好，故我们选择五层的CART模型作为最终模型。

使用测试集来确定一个新的参数，有可能会引起模型的泛化问题，避免这一问题可以多预留一个另外的测试集。

estimator = DecisionTreeClassifier(criterion="gini", max_depth = 5)
estimator.fit(x_train, y_train)
dot_tree = tree.export_graphviz(estimator, out_file=None)
graph = graphviz.Source(dot_tree)
graph.view('titanic')

titanic CART树

reference

周志华，机器学习
Quinlan, J. R. (1986). "Induction of decision trees." Machine Learning
scikit learn官方文档