决策树目录
一、决策树 (Decision Tree)1、决策树模型的基本概念2、决策树的基本流程3、决策树的关键——查找合适的“划分属性”3.1 信息熵 (Information Entropy)3.2 ID3 — 信息增益 (Information Gain)3.3 C4.5 — 增益率(Gain Ratio)3.4 CART— 基尼指数( Gini Index)
4、剪枝 (Prunig)4.1 剪枝的两种方法预剪枝 (PrePruning)后剪枝 (PostPruning)
4.2 预剪枝 VS 后剪枝
二、利用决策树进行红酒数据集分类预测三、单变量决策树四、多变量决策树五、实验总结
一、决策树 (Decision Tree)
1、决策树模型的基本概念
决策树是一种解决分类问题的算法，基于树的结构进行决策，从根节点开始，沿着划分属性进行分支，直到叶节点。
根节点：包含样本的全集。内部结点：有根结点和中间结点，某个属性上的测试（test），这里的test是针对特征属性进行判断叶节点：预测结果分支：该测试的可能结果，属性有多少个取值，就有多少个分支
预测时，在树的内部节点处用某一个属性值进行判断，根据判断结果决定进入哪个分支节点，直到到达叶结点处，得到分类结果。
这是一种基于if-then-else规则的有监督学习方法，决策树的这些规则通过训练得到，而不是人工制定。 举个例子：银行用机器学习算法来确定是否给客户发放贷款，为此需要考虑客户的年收入，是否有房产这两个指标。
“ 首先判断客户的年收入指标，如果大于20万，可以贷款；否则继续判断客户是否有房产，如果有房产，可以贷款，否则不能贷款。”
2、决策树的基本流程
决策树是一个由根到叶的递归过程，在每一个中间节点寻找划分属性，递归算法最重要的就是设置停止条件：
当前结点包含的样本属于同一个类别，无需划分；当前属性集为空，或者所有样本在所有属性上取值相同无法划分，简单理解就是当分到这一节点时，所有的特征属性都用完了，没有特征可用了，就根据Label数量多的给这一节点打标签，使其变成叶节点（用样本出现的后验概率做先验概率）当前结点包含的样本集为空，不能划分。这种情况是因为该样本数据缺少这个属性取值，根据父结点的Label情况为该结点打标记（用父结点出现的后验概率做该结点的先验概率）
3、决策树的关键——查找合适的“划分属性”
决策树学习的关键时如何选择最优划分属性。划分过程中，决策树的分支结点所包含的样本尽可能属于同一个类别，结点的“ 纯度 (Purity) ” 越来越高。
3.1 信息熵 (Information Entropy)
信息熵是度量样本集合纯度最常用的一种指标。 样本集合：D 第k类样本所占比例L：Pk 属性a对样本D进行划分产生分支节点个数：V
假设当前样本集合D中第k类样本所占的比例来为Pk（k=1，2…… |y|），则D的信息熵定义为
E
n
t
（
D
）
=
−
∑
k
=
1
∣
y
∣
P
k
log
2
P
k
Ent（D） =-\sum_{k=1}^{\vert y|}P_k\log_2P_k
Ent（D）=−k=1∑∣y∣Pklog2Pk
Ent(D)的值越小，则D的纯度越高计算信息熵时约定：若p = 0，则
P
log
2
P
=
0
P\log_2P=0
Plog2P=0Ent(D)的最小值为0，最大值为
log
2
∣
y
∣
\log_2{|y|}
log2∣y∣。
3.2 ID3 — 信息增益 (Information Gain)
假定离散属性a有V个可能的取值{
a
1
a^1
a1,
a
2
a^2
a2,
a
3
a^3
a3……
a
v
a^v
av}，若使用a来对样本集D进行划分，则会产生V个分支结点，其中第v个分支结点包含了D中所有在属性a上取值为
a
v
a^v
av的样本，即为
D
v
D^v
Dv 给分支结点赋予权重
∣
D
k
∣
∣
D
∣
\frac{\vert D_k|}{\vert D|}
∣D∣∣Dk∣，样本数越多的分支结点的影响越大，信息增益越大，使用属性a对样本集D进行划分所获得的纯度提升越大。
G
a
i
n
(
D
)
=
E
n
t
(
D
)
−
∑
k
=
1
∣
y
∣
∣
D
k
∣
∣
D
∣
E
n
t
(
D
k
)
Gain(D) = Ent(D)-\sum_{k=1}^{\vert y|}\frac{\vert D_k|}{\vert D|}Ent(D^k)
Gain(D)=Ent(D)−k=1∑∣y∣∣D∣∣Dk∣Ent(Dk)
一般而言，信息增益越大，则意味着使用属性a来进行划分所获得的“纯度提升”越大。
ID3 (Iterative Dichotomiser,迭代二分器) 决策树学习算法，以信息增益准则来选择划分属性。信息增益准则可对取值数目较多的属性有所偏好。
从属性集A中选择最优划分属性
a
∗
=
a
r
g
m
a
x
G
a
i
n
(
D
,
a
)
a
∈
A
a_* = arg\ max\ Gain(D,a) \quad a\in A
a∗=arg max Gain(D,a)a∈A
3.3 C4.5 — 增益率(Gain Ratio)
在决策树中不直接使用信息增益，而是使用增益率来选择最优划分属性。 增益率准则对可取值数目较少的属性有所偏好。
I
V
(
a
)
=
−
∑
v
=
1
V
∣
D
v
∣
∣
D
∣
log
2
∣
D
v
∣
∣
D
∣
IV(a) = -\sum_{v=1}^V \frac{\vert D^v|}{\vert D|}\log_2 \frac{\vert D^v|}{\vert D|}
IV(a)=−v=1∑V∣D∣∣Dv∣log2∣D∣∣Dv∣ IV(a) 称为属性a的“固有值” ，属性a的可能取值数目越多（即V越大），则IV(a)的值通常就越大。
G
a
i
n
R
a
t
i
o
(
D
,
a
)
=
G
a
i
n
(
D
,
a
)
I
V
(
a
)
GainRatio (D,a) = \frac{Gain(D,a)}{IV(a)}
GainRatio(D,a)=IV(a)Gain(D,a) C4.5决策树 采用一种启发式的方式，选出信息增益高于平均水平的属性，然后再从中选择增益率最高的。
3.4 CART— 基尼指数( Gini Index)
CART决策树使用基尼指数来选择划分属性。数据集D的纯度，用基尼值度量为：
G
i
n
i
(
D
)
=
∑
k
=
1
∣
y
∣
∑
k
‘
≠
k
P
k
P
k
‘
=
1
−
∑
k
=
1
∣
y
∣
p
k
2
Gini(D) = \sum_{k=1}^{\vert y|}\sum_{{k^`}\not=k}P_kP^`_k= 1- \sum_{k=1}^{\vert y|} p^2_k
Gini(D)=k=1∑∣y∣k‘=k∑PkPk‘=1−k=1∑∣y∣pk2 Gini(D) 的值越小，则D的纯度越高。 属性a的基尼指数定义为：
G
i
n
i
I
n
d
e
x
(
D
,
a
)
=
∑
v
=
1
V
∣
D
v
∣
∣
D
∣
G
i
n
i
(
D
)
Gini \ Index(D,a) = \sum_{v=1}^{V} \frac{\vert D^v|}{|D|}Gini(D)
Gini Index(D,a)=v=1∑V∣D∣∣Dv∣Gini(D) 从属性集A中选择基尼指数最小的属性最为最优划分属性
a
∗
=
a
r
g
m
i
n
G
a
i
n
I
n
d
e
x
(
D
,
a
)
a
∈
A
a_* = arg\ min\ GainIndex(D,a)\quad a\in A
a∗=arg min GainIndex(D,a)a∈A
4、剪枝 (Prunig)
“剪枝”是决策树学习算法对付“过拟合”的主要手段，可通过“剪枝”来一定程度避免因决策分支过多，以致于把训练集自身的一些特点当做所有数据都具有的一般性质而导致的过拟合。
【西瓜数据集】未剪枝决策树流程图，选择属性“脐部”来对训练集进行划分判别西瓜的好坏。
4.1 剪枝的两种方法
预剪枝 (PrePruning)
预剪枝是指在决策树生成过程中，对每个结点在划分前进行估计，若当前结点的划分不能带来决策树泛化能力的提升，则停止划分并将当前结点标记为叶节点。 当节点划分前来确定是否继续增长，及早停止增长的主要方法有：
节点内数据样本低于某一阙值；所有节点特征都已分裂；节点划分前准确率比划分后准确率高。
后剪枝 (PostPruning)
后剪枝先从训练集生成一棵完整的决策树，然后自底向上地对非叶结点进行分析计算，若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升，则将该子树替换为叶结点。
例如：首先考虑结点6，若将其替换为叶结点，根据落在其上的训练样本{7,15}将其标记为“好瓜”，得到验证集精度提高至57.1%，则决定剪枝
然后考虑结点5，若将其替换为叶结点，根据落在其上的训练样本 {6,7,15}将其标记为“好瓜”，得到验证集精度仍为 57.1%，可以不进行剪枝
4.2 预剪枝 VS 后剪枝
预剪枝
优点 降低拟合风险 显著减少训练时间和测试时间开销缺点 欠拟合风险：有些分支的当前划分虽然不能提升泛化性能，但在其基础上进行的后续划分却有可能显著提高性能。 预剪枝基于“贪心”本质禁止这些分支展开，带来了欠拟合风险。
后剪枝
优点 后剪枝比预剪枝保留了更多的分支，欠拟合风险小，泛化性能往往优于预剪枝决策树。缺点 训练时间开销大：后剪枝过程是在生成完全决策树之后进行的，需要自底向上对所有非叶结点逐一计算
二、利用决策树进行红酒数据集分类预测
第一步：导入所需的包
from sklearn import tree
from sklearn.datasets import load_wine
from sklearn.model_selection import train_test_split
第二步：查看数据集
wine = load_wine()
wine.data.shape
wine.target
import pandas as pd
#数据集的标签分为0，1，2三种
pd.concat([pd.DataFrame(wine.data),pd.DataFrame(wine.target)],axis=1)#第一个参数是将两个DataFrame合并，axis默认为0，是纵向合并，为1是横向合并
#将数据集和标签合并
wine.feature_names
#红酒的属性名字
wine.target_names
Xtrain,Xtest,Ytrain,Ytest=train_test_split(wine.data,wine.target,test_size=0.3)
#将数据集分为训练集和测试集，训练集有70%，测试集有30%
Xtrain.shape
Xtest.shape
结果为：
第三步：建立模型
clf = tree.DecisionTreeClassifier(criterion="entropy")
clf = clf.fit(Xtrain,Ytrain)
score = clf.score(Xtest,Ytest)#返回预测的准确accuracy
score
第四步：画决策树
feature_name = ['酒精','苹果酸','灰','灰的碱性','镁','总酚','类黄酮','非黄烷类酚类','花青素','颜 色强度','色调','od280/od315稀释葡萄酒','脯氨酸']
import graphviz
dot_data = tree.export_graphviz(clf,out_file = None,feature_names= feature_name,class_names=["琴酒","雪莉","贝尔摩德"],filled=True,rounded=True)
graph = graphviz.Source(dot_data)
graph
结果为：
#特征重要性
clf.feature_importances_
[*zip(feature_name,clf.feature_importances_)]
[*zip(feature_name,clf.feature_importances_)]
结果为：
在每次分枝时，从不使用全部特征，而是随机选取一部分特征，从中选取不纯度相关指标最优的作为分枝用的节点。
#选择的最优的树：random_state & splitter
clf = tree.DecisionTreeClassifier(criterion="entropy",random_state=30)
clf = clf.fit(Xtrain, Ytrain)
score = clf.score(Xtest, Ytest) #返回预测的准确度
score
random_state 用来设置分枝中的随机模式的参数，默认 None
在高维度时随机性会表现更明显，低维度的数据 （比如鸢尾花数据集），随机性几乎不会显现。
splitter 也是用来控制决策树中的随机选项的，有两种输入值：
① 输入 ”best" ，决策树在分枝时虽然随机，但是还是会优先选择更重要的特征进行分枝（重要性可以通过属性feature_importances_ 查看； ② 输入 “random" ，决策树在分枝时会更加随机，树会因为含有更多的不必要信息而更深更大，并因这些不必要信息而降低对训练集的拟合。
这也是防止过拟合的一种方式。当预测到模型会过拟合，用这两个参数来帮助降低树建成之后过拟合的可能性。
clf = tree.DecisionTreeClassifier(criterion="entropy",random_state=30 ,splitter="random")
clf = clf.fit(Xtrain, Ytrain)
score = clf.score(Xtest, Ytest)
score
结果为：
import graphviz
dot_data = tree.export_graphviz(clf,feature_names= feature_name,class_names=["琴酒","雪莉","贝尔摩德"],filled=True,rounded=True )
graph = graphviz.Source(dot_data)
graph
结果为：
在不加限制的情况下，一棵决策树会生长到衡量不纯度的指标最优，或者没有更多的特征可用为止。
这样的决策树 往往会过拟合，这就是说，它会在训练集上表现很好，在测试集上却表现糟糕。
#我们的树对训练集的拟合程度如何？
score_train = clf.score(Xtrain, Ytrain)
score_train
模型对训练集效果太好，这很容易造成过拟合，为了让决策树有更好的泛化性，我们要对决策树进行剪枝。
max_depth ：限制树的最大深度，超过设定深度的树枝全部剪掉 这是用得最广泛的剪枝参数，在高维度低样本量时非常有效。决策树多生长一层，对样本量的需求会增加一倍，所以限制树深度能够有效地限制过拟合。
min_samples_leaf： 限定一个节点在分枝后的每个子节点都必须包含至少 min_samples_leaf 个训练样本，否则分 枝就不会发生。或者，分枝会朝着满足每个子节点都包含min_samples_leaf 个样本的方向去发生。
clf=tree.DecisionTreeClassifier(criterion="entropy",random_state=30,splitter="random",max_depth=3,min_samples_leaf=5,min_samples_split=5)
clf = clf.fit(Xtrain, Ytrain)
dot_data = tree.export_graphviz(clf,feature_names= feature_name,class_names=["琴酒","雪莉","贝尔摩德"],filled=True,rounded=True)
graph = graphviz.Source(dot_data)
graph
结果为：
score = clf.score(Xtest, Ytest)
score
结果为：
import matplotlib.pyplot as plt
test = []
for i in range(10):
clf = tree.DecisionTreeClassifier(max_depth=i+1,criterion="entropy",random_state=30,splitter="random")
clf = clf.fit(Xtrain, Ytrain)
score = clf.score(Xtest, Ytest)
test.append(score)
plt.plot(range(1,11),test,color="red",label="max_depth")
plt.legend()
plt.show()
结果为：
三、单变量决策树
从“树”到“规则” 一棵决策树对应于一个“规则集”，每个从根结点到叶结点的分支路径对应于一条规则。
举例：
单变量决策树（Univariate Decision Tree）是一种特殊类型的决策树，它仅考虑单个特征进行决策。在这种决策树中，每个内部节点都对应于一个特征，并通过将数据集基于该特征的阈值进行分割来进行决策。
举例：
当学习任务所对应的分类边界很复杂时，需要非常多段划分才能获得较好的近似。
若能使用斜的划分模型，则决策树模型就会大大简化。这就引入了“多变量决策树”。
四、多变量决策树
多变量决策树：每个非叶结点不仅考虑一个属性，例如“斜决策树” (oblique decision tree) 不是为每个非叶结点寻找最优划分属性，而是建立一个线性分类器。 举例：
五、实验总结
决策树是一种监督学习算法，广泛应用于分类和回归问题。它通过将数据集的特征空间划分为不同的区域来构建一个树状模型，每个区域对应于一个决策路径。决策树通过选择最佳的特征来进行决策，常见的特征选择方法有信息增益、基尼系数等。在实验过程中，常常会遇到过拟合问题，通过剪枝方法修剪决策树的叶子节点或合并相邻的叶子节点来减小模型复杂度。在实践中，对决策树进行适当的调参和剪枝操作非常重要，以获得更好的泛化能力和预测性能。
参考文献： https://blog.csdn.net/weixin_41667472/article/details/110421324
推荐文章
发表评论