经典决策树CART、ID3与C4.5

2023-11-19 20:11:46

经典决策树CART、ID3与C4.5 – 潘登同学的Machine Learning笔记

文章目录

经典决策树CART、ID3与C4.5 -- 潘登同学的Machine Learning笔记
决策树模型
- 决策树的数学表达
- - 整体表达式
  - 迭代表达式
决策树的分裂指标
何时停止分裂？
总结
- 决策树的优缺点
- CART、ID3与C4.5
实战鸢尾花数据集
- 绘制不同超参数对应决策树模型的图形
实现回归树
- 不同超参数对应决策树模型的回归树

决策树模型

决策树是属于有监督机器学习的一种，起源非常早，符合直觉并且非常直观，模仿人类做决策的过程。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-JN46EW80-1638460764806)(img/决策树.png)]

决策树模型的特点

1.可以处理非线性的问题
2.可解释性强没有θ（参数)
3.模型简单，模型预测效率高, 模型本质就是if else
4.不容易显示的使用函数表达，不可微(如：XGBoost）

决策树的数学表达

整体表达式

G ( x ) = ∑ t = 1 T q t ( x ) g t ( x ) G(x) = \sum_{t=1}^Tq_t(x)g_t(x) G(x)=t=1∑Tqt(x)gt(x)

变量解释：

G ( x ) G(x) G(x)的结果最终是 [ 0 , k ] [0,k] [0,k]上的整数， k k k是叶子节点的个数
g t ( x ) g_t(x) gt(x)是一个决策树上从根节点到叶子节点的路径, 也可以理解为一个叶子节点，因为叶子节点数=路径数
q t ( x ) q_t(x) qt(x)是一个0-1变量，如果满足 g t ( x ) g_t(x) gt(x)就是1，否则就是0
t = 1 , … , T t=1,\ldots, T t=1,…,T则表示这个决策树有多少层，上图这个有两层（一般是不算根节点）

对 g t ( x ) 、 G ( x ) g_t(x)、G(x) gt(x)、G(x)举个栗子(用上图)：

对叶子节点从左到右,人为给他们一个值：0，1，2，3，4，5
对路径第一层 g 1 ( x ) g_1(x) g1(x): 0，2，3
对路径第二层 g 2 ( x ) g_2(x) g2(x): 0，1，0，1，2
然后从根节点顺着路径，把路径上的权值加起来就能得到叶子节点的值

迭代表达式

迭代表达式是把决策树看成很多的只有一层的决策树, 然后采用迭代的方法表示的

G ( x ) = ∑ c = 1 C [ b ( x ) = c ] ∗ G c ( x ) G(x) = \sum_{c=1}^C[b(x)=c]*G_c(x) G(x)=c=1∑C[b(x)=c]∗Gc(x)

变量解释：

c = 1 , … , C c=1,\ldots,C c=1,…,C表示一个节点下有 C C C个子树
b ( x ) b(x) b(x)表示分支条件， c c c表示某棵子树的条件，如果符合条件 [ b ( x ) = c ] [b(x)=c] [b(x)=c]为1，否则为0
G c ( x ) G_c(x) Gc(x)则表示 c c c条件下对应的子树

迭代表达式的算法表述：

所以我们要解决的问题就是：

每次分成几份，分裂的标准
停止的条件
如何用节点共性代表未来预测值

决策树的分裂指标

Gini 系数与CART

基尼系数是指国际上通用的、用以衡量一个国家或地区居民收入差距的常用指标。基尼系数最大为“1”，最小等于“0”。基尼系数越接近 0 表明收入分配越是趋向平等。国际惯例把 0.2 以下视为收入绝对平均，0.2-0.3 视为收入比较平均；0.3-0.4 视为收入相对合理；0.4-0.5 视为收入差距较大，当基尼系数达到 0.5 以上时，则表示收入悬殊

具体含义是指，在全部居民收入中，用于进行不平均分配的那部分收入所占的比例。

把Gini 系数用在决策树里，就是想要将同一类的数据分为两类，这也是一个最基础的决策树，叫CART（Classification and Regression tree），是一种二叉树。

CART（Classification And Regression Tree，分类回归树）由 L.Breiman，J.Friedman， R.Olshen 和 C.Stone 于 1984 年提出，是一种应用相当广泛的决策树学习方法。值得一提的是，CART 和 C4.5 一同被评为数据挖掘领域十大算法。

CART 算法采用一种二分递归分割的技术，将当前的样本集分为两个子样本集，使得生成的的每个非叶子节点都有两个分支。因此，CART 算法生成的决策树是结构简洁的二叉树。

CART用于分类目标

Gini 系数的计算公式
G i n i ( P ) = ∑ i = 1 k P i ( 1 − P i ) = 1 − ∑ i = 1 K P i 2 Gini(P) = \sum_{i=1}^k P_i(1-P_i) = 1 - \sum_{i=1}^K P_i^2 Gini(P)=i=1∑kPi(1−Pi)=1−i=1∑KPi2

其中, i = 1 , … , K i=1,\ldots,K i=1,…,K表示总共有 K K K个类别， P i P_i Pi表示在集合 P P P中属于第 i i i个的概率；

分裂后的Gini 系数
G i n i ( D , a ) = ∣ D 1 ∣ ∣ D ∣ G i n i ( D 1 ) + ∣ D 2 ∣ ∣ D ∣ G i n i ( D 2 ) Gini(D,a) = \frac{|D_1|}{|D|}Gini(D_1) + \frac{|D_2|}{|D|}Gini(D_2) Gini(D,a)=∣D∣∣D1∣Gini(D1)+∣D∣∣D2∣Gini(D2)

其中，a表示D中的一个属性

决策树分裂条件的选择原则：

每一步的收益最大（也就是Gini系数最小），具体做法就是把一个一列数据依次从小到大排开，分别以每个数据为分类标准，分别计算，得出一个Gini系数最小的那个数据，以他为分裂标准
对于鸢尾花数据集的划分

CART用于回归目标

每一个节点的 y ˉ \bar{y} yˉ就是这个类的所有 y i y_i yi的平均值，评判分裂优劣的指标就是MSE
M S E = ∑ n = 1 m ( y ^ − y ) 2 MSE = \sum_{n=1}^{m} (\hat{y} - y)^{2} MSE=n=1∑m(y^−y)2

信息增益与ID3

在信息世界，熵越高，则能传输越多的信息，熵越低，则意味着传输的信息越少。还是举例说明，假设 Kathy 在买衣服的时候有颜色，尺寸，款式以及设计年份四种要求，而 North 只有颜色和尺寸的要求，那么在购买衣服这个层面上 Kathy 由于选择更多因而不确定性因素更大，最终 Kathy 所获取的信息更多，也就是熵更大。所以信息量=熵=不确定性，通俗易懂。在叙述决策树时我们用熵表示不纯度（Impurity）。

熵的公式：
H ( N ) = − ∑ j = 1 k p ( w j ) ln ⁡ p ( w j ) H(N) = -\sum_{j=1}^kp(w_j)\ln p(w_j) H(N)=−j=1∑kp(wj)lnp(wj)

其中， p ( w j ) p(w_j) p(wj)表示属于第 j j j类的概率

信息增益
G a i n ( D , a ) = H ( N ) − ∑ v = 1 V ∣ D v ∣ ∣ D ∣ H ( D v ) Gain(D,a) = H(N) - \sum_{v=1}^V\frac{|D^v|}{|D|}H(D^v) Gain(D,a)=H(N)−v=1∑V∣D∣∣Dv∣H(Dv)

其中， D v D^v Dv表示分类后的节点的熵；

我们希望，每一次分裂的信息增益越大越好；

ID3是一个多叉树，就是有别于上面二叉树的一种改进

熵与交叉熵的关系

（逻辑回归）交叉熵是衡量 y ˉ \bar{y} yˉ与y是否相等
L ( θ ) = − ∑ i = 1 m ( y i log ⁡ h θ ( x i ) + ( 1 − y i ) log ⁡ ( 1 − h θ ( x i ) ) L(\theta) = -\sum_{i=1}^{m}(y_{i}\log h_{\theta}(x_{i}) + (1-y_{i})\log (1-h_{\theta}(x_{i})) L(θ)=−i=1∑m(yiloghθ(xi)+(1−yi)log(1−hθ(xi))

交叉熵的 log ⁡ \log log前后的y一个是实际一个是预测，而熵的 log ⁡ \log log前后都是相同的 p p p

信息熵与Gini系数的关系

{ H ( X ) = − ∑ j = 1 k p ( w j ) ln ⁡ p ( w j ) G i n i ( P ) = ∑ i = 1 k P i ( 1 − P i ) \begin{cases} H(X) = -\sum_{j=1}^kp(w_j)\ln p(w_j) \\ Gini(P) = \sum_{i=1}^k P_i(1-P_i)\\ \end{cases} {H(X)=−∑j=1kp(wj)lnp(wj)Gini(P)=∑i=1kPi(1−Pi)

把 f ( x ) = − ln ⁡ x f(x) = -\ln x f(x)=−lnx在 x = 1 x=1 x=1处进行一阶泰勒展开

f ( x ) = f ( x 0 ) + f ′ ( x 0 ) ( x − x 0 ) = f ( 1 ) + f ′ ( 1 ) ( x − 1 ) = 1 − x \begin{aligned} f(x) &= f(x_0) + f'(x_0)(x-x_0)\\ &= f(1) + f'(1)(x-1)\\ &= 1-x \end{aligned} f(x)=f(x0)+f′(x0)(x−x0)=f(1)+f′(1)(x−1)=1−x

因此，熵可以转化为:
H ( x ) = − ∑ j = 1 k p ( w j ) ln ⁡ p ( w j ) = ∑ j = 1 k p ( w j ) ( − ln ⁡ p ( w j ) ) ≈ ∑ i = 1 k P i ( 1 − P i ) \begin{aligned} H(x) &= -\sum_{j=1}^kp(w_j)\ln p(w_j)\\ &= \sum_{j=1}^kp(w_j)(-\ln p(w_j))\\ &\approx \sum_{i=1}^k P_i(1-P_i)\\ \end{aligned} H(x)=−j=1∑kp(wj)lnp(wj)=j=1∑kp(wj)(−lnp(wj))≈i=1∑kPi(1−Pi)
所以基尼系数在1是近似等于信息熵

信息增益率与C4.5

而对于多叉树ID3，如果一次不限制分类的节点数，那么他完全将每个都分为一类，然后就能将信息熵降为0，我们想权衡分裂的出的节点数与信息增益,所以引入信息增益率。

信息增益率 ( I G R ) = 信息增益（类别）本身的熵（类别）本身的熵 = − ∑ i = 1 K ∣ D v ∣ ∣ D ∣ H ( D v ) 信息增益率(IGR) = \frac{信息增益}{（类别）本身的熵}\\ （类别）本身的熵 = -\sum_{i=1}^K\frac{|D^v|}{|D|}H(D^v)\\ 信息增益率(IGR)=（类别）本身的熵信息增益（类别）本身的熵=−i=1∑K∣D∣∣Dv∣H(Dv)

ID3与C4.5

ID3（Iterative Dichotomiser 3，迭代二叉树 3 代）由 Ross Quinlan 于 1986 年提出。 1993 年，他对 ID3 进行改进设计出了 C4.5 算法

使用信息增益会让 ID3 算法更偏向于选择值多的属性。信息增益反映给定一个条件后不确定性减少的程度，必然是分得越细的数据集确定性更高，也就是信息熵越小，信息增益越大。因此，在一定条件下，值多的属性具有更大的信息增益。

而 C4.5 则使用信息增益率选择属性。信息增益率通过引入一个被称作分裂信息(Split information)的项来惩罚取值较多的属性，分裂信息用来衡量属性分裂数据的广度和均匀性。这样就改进了 ID3 偏向选择值多属性的缺点

相对于 ID3 只能处理离散数据，C4.5 还能对连续属性进行处理，具体步骤为：

把需要处理的样本(对应根节点)或样本子集(对应子树)按照连续变量的大小从小到大进行排序
假设该属性对应的不同的属性值一共有 N 个，那么总共有 N−1 个可能的候选分割阈值点，每个候选的分割阈值点的值为上述排序后的属性值中两两前后连续元素的中点，根据这个分割点把原来连续的属性分成 bool 属性。实际上可以不用检查所有 N−1 个分割点。(连续属性值比较多的时候，由于需要排序和扫描，会使 C4.5 的性能有所下降)。
用信息增益比率选择最佳划分

C4.5的其他优缺点

优点
- 在树的构造过程中可以进行剪枝，缓解过拟合
- 能够对连续属性进行离散化处理（二分法）
- 能够对缺失值进行处理
缺点
- 构造树的过程需要对数据集进行多次顺序扫描和排序，导致算法低效

何时停止分裂？

对于决策树做分类或者回归问题，肯定是要把每一个节点都分到一个独有的叶子节点中，训练的效果才会最好，可是这样就会导致过拟合，从而预测结果不好；

对于前面的有监督学习，我们采用的方式一般是增加惩罚项，而决策树一般有两种方法，分别是前剪枝与后剪枝

前剪枝（常用）

前剪枝可以理解为限制数的结构，一般是通过超参数来限制的

{ c r i t e r i o n = ′ ′ g i n i ′ ′ 表示分裂条件 s p l i t t e r = ′ ′ b e s t ′ ′ 表示选择分裂的依据， b e s t 表示贪婪 m a x _ d e p t h = N o n e 表示树的最大深度 m i n _ s a m p l e s _ l e a f = 2 表示每个根节点最多分裂成两个子节点 m a x _ w e i g h t _ f r a c t i o n _ l e a f = 0 叶节点中的样本量最少占总体的 % m a x _ f e a t u r e s = N o n e 表示树的一次分类时考虑的最大属性个数 r a n d o m _ s t a t e = N o n e 随机种子 m a x _ l e a f _ n o d e s = N o n e 表示树的最大叶节点数 m i n _ i m p u r i t y _ d e c r e a s e = 0 表示每次分裂的最小收益 m a x _ i m p u r i t y _ s p l i t = N o n e 表示树停止分裂的阈值 c l a s s _ w e i g h t = N o n e 传入数组表示各个属性的重要程度 p r e s o r t = F a l s e 强排序，主要是用于将连续值变为离散值 \begin{cases} criterion = ''gini'' &{表示分裂条件}\\ splitter = ''best'' &{表示选择分裂的依据，best表示贪婪}\\ max\_depth = None &{表示树的最大深度}\\ min\_samples\_leaf = 2 &{表示每个根节点最多分裂成两个子节点}\\ max\_weight\_fraction\_leaf = 0 &{叶节点中的样本量最少占总体的\%}\\ max\_features = None &{表示树的一次分类时考虑的最大属性个数}\\ random\_state = None &{随机种子}\\ max\_leaf\_nodes = None &{表示树的最大叶节点数}\\ min\_impurity\_decrease = 0 &{表示每次分裂的最小收益}\\ max\_impurity\_split = None &{表示树停止分裂的阈值}\\ class\_weight = None &{传入数组表示各个属性的重要程度}\\ presort=False &{强排序，主要是用于将连续值变为离散值}\\ \end{cases} ⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧criterion=′′gini′′splitter=′′best′′max_depth=Nonemin_samples_leaf=2max_weight_fraction_leaf=0max_features=Nonerandom_state=Nonemax_leaf_nodes=Nonemin_impurity_decrease=0max_impurity_split=Noneclass_weight=Nonepresort=False表示分裂条件表示选择分裂的依据，best表示贪婪表示树的最大深度表示每个根节点最多分裂成两个子节点叶节点中的样本量最少占总体的%表示树的一次分类时考虑的最大属性个数随机种子表示树的最大叶节点数表示每次分裂的最小收益表示树停止分裂的阈值传入数组表示各个属性的重要程度强排序，主要是用于将连续值变为离散值

后剪枝（不常用）

在决策树构建好之后，才开始剪枝

常见的有三种

REP—错误率降低剪枝
PEP—悲观剪枝（C4.5）
CCP—代价复杂度剪枝（CART）

总结

决策树的优缺点

优点
- 1.决策过程接近人的思维习惯。
- 2.模型容易解释，比线性模型具有更好的解释性。
- 3.能清楚地使用图形化描述模型。
- 4.处理定性特征比较容易。
- 5.能解决异或问题（线性模型得升维）
缺点
- 一般来说，决策树学习方法的准确率不如其他的模型
- 不支持在线学习。当有新样本来的时候，需要重建决策树。
- 容易产生过拟合现象。

CART、ID3与C4.5

C4.5 算法是在 ID3 算法的基础上采用信息增益率的方法选择决策属性。C4.5 改进了 ID3 偏向选择值多属性以及只能处理离散属性等缺点。ID3 算法和 C4.5 算法虽然在对训练样本集的学习中能尽可能多地挖掘信息，但其生成的决策树分支较大，规模较大。为了简化决策树的规模，提高生成决策树的效率，又出现了根据 GINI 系数来选择测试属性的决策树算法 CART。

CART 算法采用一种二分递归分割的技术，与基于信息熵的算法不同，CART 算法对每次样本集的划分计算 GINI 系数，GINI 系数越小则划分越合理。CART 算法总是将当前样本集分割为两个子样本集，使得生成的决策树的每个非叶结点都只有两个分枝。因此 CART 算法生成的决策树是结构简洁的二叉树。

实战鸢尾花数据集

上代码!!!

import pandas as pd
import numpy as np
from sklearn.datasets import load_iris
from sklearn.tree import DecisionTreeClassifier
from sklearn.tree import export_graphviz  #外接画图小工具
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score
import matplotlib.pyplot as plt
import matplotlib as mpl

iris = load_iris()
data = pd.DataFrame(iris.data)
data.columns = iris.feature_names
data['Species'] = load_iris().target
print(data)

x = data.iloc[:, 0:4]
y = data.iloc[:, -1]
# y = pd.Categorical(data.iloc[:,4]).codes  是一个pandas自带的计算类别的函数
# print(x)
# print(y)


x_train, x_test, y_train, y_test = train_test_split(x, y, test_size=0.25, random_state=2)

tree_clf = DecisionTreeClassifier(max_depth=8, criterion='gini',random_state=42)
tree_clf.fit(x_train, y_train)

print(x_train.shape)

export_graphviz(
    tree_clf,
    out_file="./iris_tree.dot",
    feature_names=iris.feature_names[:],
    class_names=iris.target_names,
    rounded=True,
    filled=True
)
#在cmd打开
# cd C:\Program Files (x86)\Graphviz2.38\bin
# dot -T png C:\Users\潘登\Documents\python全系列\人工智能\iris_tree.dot -o C:\Users\潘登\Documents\python全系列\人工智能\iris_tree.png

y_test_hat = tree_clf.predict(x_test)
print("acc score:", accuracy_score(y_test, y_test_hat))

print(tree_clf.feature_importances_)  #特征的重要程度

# print(tree_clf.predict_proba([[5, 1.5]]))  #上面输出概率值
# print(tree_clf.predict([[5, 1.5]]))  #下面输出类别号

结果如下

使用accuracy_score查看测试结果的准确率，测试集的分类准确率也很高，到达95%；
使用tree_clf.feature_importances_查看特征的重要程度，越大越重要；

在决策树里，使用graphviz这个强大的画图工具，能展示出决策树的结果；具体使用方法，在代码注释里，请放心食用；

绘制不同超参数对应决策树模型的图形

接着上面的代码

#%% 探索超参数
depth = np.arange(1, 15)
err_list = []

for d in depth:
    # print('\n')
    clf = DecisionTreeClassifier(criterion='gini', max_depth=d)
    clf.fit(x_train, y_train)
    y_test_hat = clf.predict(x_test)
    result = (y_test_hat == y_test)
    if d == 1:
        print(result)
    err = 1 - np.mean(result)
    # print(100 * err)
    err_list.append(err)
    print(d, ' 错误率：%.2f%%' % (100 * err))

mpl.rcParams['font.sans-serif'] = ['SimHei']
plt.figure(facecolor='w')
plt.plot(depth, err_list, 'ro-', lw=2)
plt.xlabel('决策树深度', fontsize=15)
plt.ylabel('错误率', fontsize=15)
plt.title('决策树深度和过拟合', fontsize=18)
plt.grid(True)
plt.show()

结果如下

从图中也可以看出，决策树深度为3的时候，预测效果与过拟合程度都较优；

实现回归树

目标：用回归树,拟合函数
f ( x ) = sin ⁡ x f(x) = \sin x f(x)=sinx

#%%代码实现回归树
import numpy as np
from sklearn.tree import DecisionTreeRegressor
import matplotlib.pyplot as plt

plt.rcParams['font.sans-serif'] = ['SimHei']
plt.rcParams['axes.unicode_minus'] = False
N = 100 #一百个样本
x = np.random.rand(N)*6-3
y = np.sin(x) + np.random.rand(N)*0.05  #加一点点噪声
# print(y)

x = x.reshape(-1,1)  #因为y应该是一个m*n的矩阵，所以把x转为二维的数组

dt_reg = DecisionTreeRegressor(criterion='mse',max_depth = 3)
dt_reg.fit(x,y)

x_test = np.linspace(-3,3,50).reshape(-1,1)
y_hat = dt_reg.predict(x_test)
plt.figure(1)
plt.plot(x,y,'y*',label = 'actual')
plt.plot(x_test,y_hat,'b-',linewidth = 2,label = 'presict')
plt.legend(loc = 'upper left')
plt.grid()
plt.show()

结果如下：

可以看出，拟合的曲线都是阶梯型的，这就是决策树的特点，一个区间的数据一般都被划分到一类里，所以看上去就是阶梯型的；

不同超参数对应决策树模型的回归树

#查看不同深度的树的拟合情况
plt.figure(2)
depth = [2,4,6,8,10]
color = 'rgbmy'
dt_reg = DecisionTreeRegressor()
plt.plot(x,y,'b*',label = 'actual')
for d,c in zip(depth,color):
    dt_reg.set_params(max_depth = d)
    dt_reg.fit(x,y)
    y_hat = dt_reg.predict(x_test)
    y_theory = np.sin(x_test).reshape(-1)
    err = sum(abs(y_hat-y_theory) >0.05)
    print(d, ' 错误率：%.2f%%' % (err))
    plt.plot(x_test,y_hat,'-',color = c,linewidth = 1.5,label = 'depth=%d'%d)
plt.legend(loc = 'upper left')
plt.grid()
plt.show()

结果如下：

可以看出，树的深度越深，拟合效果就越好；

经典决策树CART、ID3与C4.5就是这样了, 继续下一章吧！pd的Machine Learning

码农公寓