【机器学习】决策树原理及scikit-learn使用-CSDN博客

---

决策树详解

决策树Decision Tree是一种非参数的有监督学习方法它能够从一系列有特征和标签的数据中总结出决策规则并用树状图的结构来呈现这些规则以解决分类和回归问题。

决策树由结点(node)和有向边(directed edge)组成。结点有两种内部结点(internal node)和叶子结点(leaf node)其中内部结点表示一个特征或者属性叶子结点表示一个类。

下图为是否为哺乳动物的二分类决策树体温和胎生为特征哺乳动物和非哺乳动物为类别。【可以看成if-else的结够根据给定的数据一路走下去最后得出结论】

原则上讲任意一个数据集上的所有特征都可以被拿来分枝特征上的任意节点又可以自由组合所以一个数据集上可以发展出非常非常多棵决策树其数量可达指数级。在这些树中总有那么一棵树比其他的树分类效力都好那样的树叫做”全局最优树“。

暴力搜索方法肯定行不通时间复杂度太高。
机器学习研究者们开发了一些有效的算法能够在合理的时间内构造出具有一定准确率的次最优决策树。这些算法基本都执行”贪心策略“即通过局部的最优来达到我们相信是最接近全局最优的结果。

在学习算法之前先了解几个概念

1. 信息熵熵度量了事物的不确定性越不确定的事物它的熵就越大。
   随机变量X的熵的表达式如下
   

其中n代表X的n种不同的离散取值。而$p_{x_i}$代表了X取值为i的概率log为以2或者e为底的对数。

2. 条件熵 (Conditional Entropy)$H(X\mid Y)$ 表示在已知随机变量Y的条件下随机变量X的不确定性。

$$H(X|Y)=\sum _{j=1}^{n}p(y_i)H(X|y_i)$$

3. 信息增益特征A对训练数据集D的信息增益$I(D,A)$,定义为集合D的经验熵$H(D)$与给定特征A在给定条件下D的经验条件熵$H(D|A)$之差即

$$I(D,A)=H(D)-H(D|A)$$

$H(D|A)$表示在特征A在给定条件下对数据集D进行分类的不确定性二者之差即为信息增益表示特征A使得数据集D的分类不确定性减少的程度。
显然对于信息增益大的特征具有更强的分类能力。

4. 具体计算示例

构建最优树的算法

ID3 算法

ID3算法的核心就是在决策树各个节点上应用信息增益准则选择特征递归地构建决策树。

具体过程-

1. 输入训练数据集D、特征集A、阈值ϵ
2. 输出 决策树T

判断T是否需要选择特征生成决策树

• 若D中所有实例属于同一类则T为单结点树记录实例类别$C_k$以此作为该结点的类标记并返回T;
• 若D中所有实例无任何特征(A=空集)则T为单结点树记录D中实例个数最多类别$C_k$以此作为该结点的类标记并返回T ;

否则计算A中各特征的信息增益并选择信息增益最大的特征$A_g$;

• 若$A_g$的信息增益小于ϵ则T为单结点树记录D中实例个数最多类别$C_k$ 以此作为该结点的类标记并返回T ;
• 否则按照$A_g$的每个可能值$a_i$将D分为若干非空子集$D_i$将$D_i$中实例个数最多的类别作为标记构建子结点以结点和其子节点构成T并返回T ;

第$i$个子结点以$D_i$为训练集$A-A_g$为特征集合递归地调用以上步骤得到子树$T_i$并返回。

C4.5算法

D3算法有四个主要的不足一是不能处理连续特征第二个就是用信息增益作为标准容易偏向于取值较多的特征最后两个是缺失值处理的问和过拟合问题。C4.5算法中改进了上述4个问题。

==信息增益作为标准容易偏向于取值较多的特征的问题。==我们引入一个信息增益比的变量$I_R(X,Y)$它是信息增益和特征熵的比值。表达式如下

$$I_R(D,A)=\frac{I(A,D)}{H_A(D)}$$

其中D为样本特征输出的集合A为样本特征对于特征熵$H_A(D$), 表达式如下

$$H_A(D)=-\sum _{i=1}^n\frac{|D_i|}{|D|}lo{g}_2\frac{|D_i|}{|D|}$$
其中n为特征A的类别数$D_i$为特征A的第i个取值对应的样本个数。$|D|$为样本个数。
特征数越多的特征对应的特征熵越大它作为分母可以校正信息增益容易偏向于取值较多的特征的问题。

算法流程同ID3将信息增益换成信息增益比即可。

CART 算法

1. ID3算法中我们使用了信息增益来选择特征信息增益大的优先选择。
2. C4.5算法中采用了信息增益比来选择特征以减少信息增益容易选择特征值多的特征的问题。
3. CART分类树算法使用基尼系数来代替信息增益比基尼系数代表了模型的不纯度基尼系数越小则不纯度越低特征越好。【简化了运算没有那么多对数运算】

具体的在分类问题中假设有K个类别第k个类别的概率为$p_k$, 则基尼系数的表达式为
$$Gini(p)=\sum _{k=1}^K{p}_k(1-p_k)=1-\sum _{k=1}^K{p}_k^2$$
对于个给定的样本D,假设有K个类别, 第k个类别的数量为$C_k$,则样本D的基尼系数表达式为
$$Gini(D)=1-\sum _{k=1}^K\frac{|C_k|}{|D|}$$

二分类
$$Gini(D)=2p(1-p)$$

对于样本D,如果根据特征A的某个值a,把D分成D1和D2两部分则在特征A的条件下D的基尼系数表达式为

$$Gini(D,A)=\frac{|D_1|}{|D|}Gini(D_1)+\frac{|D_2|}{|D|}Gini(D_2)$$

CART既可以用于分类又可以用来回归其中对回归树用平方误差最小化准则对分类树用基尼指数最小化原则进行特征选择生成二叉树。下表列出了三种不同决策树算法的差别
CART生成分类树是用基尼指数选择最优特征后生成的二叉树

具体流程

1. 输入训练数据集D、特征集A、阈值
2. 输出CART决策树T

从根节点出发进行操作构建二叉树;

结点处的训练数据集为D计算现有特征对该数据集的基尼指数并选择最优特征。

• 在特征$A_g$下对其可能取的每个值$a_g$根据样本点对$A_g=a_g$的测试为“是”或“否”将D分割成$D_1$和$D_2$两部分计算$A_g=a_g$时的基尼指数。
• 选择基尼指数最小的那个值作为该特征下的最优切分点。
• 计算每个特征下的最优切分点并比较在最优切分下的每个特征的基尼指数选择基尼指数最小的那个特征即最优特征。

根据最优特征与最优切分点从现结点生成两个子结点将训练数据集依特征分配到两个子结点中去。

分别对两个子结点递归地调用上述步骤直至满足停止条件比如结点中的样本个数小于预定阈值或样本集的基尼指数小于预定阈值样本基本属于同一类或者没有更多特征即生成CART决策树。

示例
基尼指数最小的是青年和老年都可以作为最优划分点总的年龄这个特征的基尼指数是0.44划分点为青年/老年。

有工作这个特征的基尼指数是0.32只有两个划分不需要区分划分点了。

有自己房子这个特征的基尼指数0.27

信贷情况的基尼指数是0.32以一般为划分点

基尼指数从小到大排序有自己房子0.27有工作0.32信贷情况0.32一般年龄0.44青年/老年越小的越好分类

所以以有自己房子开始进行分类
在没有房子的条件下计算其他特征的基尼指数
很明显有工作这个特征它的基尼指数肯定是等于0的其他基尼指数都大于0所以选择有工作进行划分

CART生成回归树

CART决策树剪枝

---

scikit-learn使用

sklearn.tree	介绍
tree.DecisionTreeClassifier	分类树
tree.DecisionTreeRegressor	回归树
tree.export_graphviz	将生成的决策树导出为DOT格式画图专用
tree.ExtraTreeClassifier	高随机版本的分类树
tree.ExtraTreeRegressor	高随机版本的回归树

分类树

分类树核心代码

from sklearn import tree #导入需要的模块
clf = tree.DecisionTreeClassifier()     #实例化
clf = clf.fit(X_train,y_train) #用训练集数据训练模型
result = clf.score(X_test,y_test) #导入测试集从接口中调用需要的信息

DecisionTreeClassifier参数详解
简单示例

导入的库

from sklearn import tree  # 决策树
from sklearn.datasets import load_wine # 酒的数据集
from sklearn.model_selection import train_test_split  # 把数据集分成训练集和测试集

打印看看白酒数据集
可以通过pandas把数据集拼接一起
把数据集分成训练集和测试集参数test_size表示测试集的比例

Xtrain, Xtest, Ytrain, Ytest = train_test_split(wine.data, wine.target, test_size=0.3)

定义模型开始训练测试

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, feature_names=feature_name, class_names=['清酒', '雪梨', '贝尔摩德'], filled=True, rounded=True)
graph = graphviz.Source(dot_data)
graph  # graph.view()

注意如果pycharm能显示图片而jupyter不能报错找不到graphviz模块可以试一下下面操作在jupyter中执行conda install python-graphviz

• 第一行划分条件脯氨酸是否小于760是往左边走不是往右边走。
• 第二行entropy信息增益比越大分类越好越靠前。当entropy=0时可以选出类别了。
• sample 样本数量。
• value每个类别的数量。
• class类别

决策树并不会选择全部特征可以通过feature_importances_来查看

scikit-learn在每次分枝时不从使用全部特征而是随机选取一部分特征从中选取不纯度相关指标最优的作为分枝用的节点。这样每次生成的树也就不同了准确率也不一样不希望每次结果不一样需要添加参数random_state来控制随机性

random_state用来设置分枝中的随机模式的参数默认None在高维度时随机性会表现更明显低维度的数据比如鸢尾花数据集随机性几乎不会显现。输入任意整数会一直长出同一棵树让模型稳定下来。

clf = tree.DecisionTreeClassifier(criterion="entropy",random_state=30)
clf = clf.fit(Xtrain, Ytrain)
score = clf.score(Xtest, Ytest) #返回预测的准确度
score

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

dot_data = tree.export_graphviz(clf
                                ,feature_names= feature_name
                                ,class_names=["琴酒","雪莉","贝尔摩德"]
                                ,filled=True
                                ,rounded=True
                                )
graph = graphviz.Source(dot_data)
graph

随机性增加了树变深了。

剪枝参数

在不加限制的情况下一棵决策树会生长到衡量entropy的指标最优或者没有更多的特征可用为止。这样的决策树往往会过拟合这就是说它会在训练集上表现很好在测试集上却表现糟糕我们需要使用剪枝参数来防止过拟合。

剪枝策略对决策树的影响巨大正确的剪枝策略是优化
决策树算法的核心。sklearn为我们提供了不同的剪枝策略

• max_depth
  限制树的最大深度超过设定深度的树枝全部剪掉
  这是用得最广泛的剪枝参数在高维度低样本量时非常有效。决策树多生长一层对样本量的需求会增加一倍所以限制树深度能够有效地限制过拟合。在集成算法中也非常实用。实际使用时建议从=3开始尝试看看拟合的效果再决定是否增加设定深度。

• min_samples_leaf & min_samples_split 限定叶子节点
  min_samples_leaf限定一个节点在分枝后的每个子节点都必须包含至少min_samples_leaf个训练样本【对应图中simple值】否则分枝就不会发生或者分枝会朝着满足每个子节点都包含min_samples_leaf个样本的方向去发生
  一般搭配max_depth使用在回归树中有神奇的效果可以让模型变得更加平滑。
  这个参数的数量设置得太小会引起过拟合设置得太大就会阻止模型学习数据。
  一般来说建议从=5开始使用。如果叶节点中含有的样本量变化很大建议输入浮点数作为样本量的百分比来使用。同时这个参数可以保证每个叶子的最小尺寸可以在回归问题中避免低方差过拟合的叶子节点出现。对于类别不多的分类问题=1通常就是最佳选择。
  min_samples_split限定一个节点必须要包含至少min_samples_split个训练样本这个节点才允许被分枝否则分枝就不会发生。

clf = tree.DecisionTreeClassifier(criterion='entropy'
                                  ,random_state=30
                                  # ,splitter='random'
                                  ,max_depth=3
                                  ,min_samples_leaf=10
                                  ,min_samples_split=10
                                  )
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

我们对上面的几个参数进行调参找准确率最高的

• max_features & min_impurity_decrease
  一般max_depth使用用作树的”精修“
  max_features限制分枝时考虑的特征个数超过限制个数的特征都会被舍弃。和max_depth异曲同工max_features是用来限制高维度数据的过拟合的剪枝参数但其方法比较暴力是直接限制可以使用的特征数量而强行使决策树停下的参数在不知道决策树中的各个特征的重要性的情况下强行设定这个参数可能会导致模型学习不足。如果希望通过降维的方式防止过拟合建议使用PCAICA或者特征选择模块中的降维算法。
  min_impurity_decrease限制信息增益的大小信息增益小于设定数值的分枝不会发生。

确认最优的剪枝参数
使用确定超参数的曲线来进行判断了继续使用我们已经训练好的决策树模型clf。超参数的学习曲线是一条以超参数的取值为横坐标模型的度量指标为纵坐标的曲线它是用来衡量不同超参数取值下模型的表现的线。在我们建好的决策树里我们的模型度量指标就是score。

以 max_depth为例

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

可以看到max_depth=4时准确度最高。

• class_weight & min_weight_fraction_leaf 【控制目标权重】
  完成样本标签平衡的参数。样本不平衡是指在一组数据集中标签的一类天生占有很大的比例。比如说在银行要判断“一个办了信用卡的人是否会违约”就是是vs否1%99%的比例。这种分类状况下即便模型什么也不做全把结果预测成“否”正确率也能有99%。因此我们要使用class_weight参数对样本标签进行一定的均衡给少量的标签更多的权重让模型更偏向少数类向捕获少数类的方向建模。该参数默认None此模式表示自动给与数据集中的所有标签相同的权重。
  有了权重之后样本量就不再是单纯地记录数目而是受输入的权重影响了因此这时候剪枝就需要搭配min_weight_fraction_leaf这个基于权重的剪枝参数来使用。另请注意基于权重的剪枝参数例如min_weight_fraction_leaf将比不知道样本权重的标准比如min_samples_leaf更少偏向主导类。如果样本是加权的则使用基于权重的预修剪标准来更容易优化树结构这确保叶节点至少包含样本权重的总和的一小部分。

重要属性和接口

属性是在模型训练之后能够调用查看的模型的各种性质。对决策树来说最重要的是feature_importances_能够查看各个特征对模型的重要性。

决策树最常用的接口

• fit
• score
• apply
• predict

#apply返回每个测试样本所在的叶子节点的索引
clf.apply(Xtest)
#predict返回每个测试样本的分类/回归结果
clf.predict(Xtest)

回归树

DecisionTreeRegressor几乎所有参数属性及接口都和分类树一模一样。需要注意的是在回归树种没有标签分布是否均衡的问题因此没有class_weight这样的参数。

重要参数属性及接口

criterion
回归树衡量分枝质量的指标支持的标准有三种
1输入"mse"使用均方误差mean squared error(MSE)父节点和叶子节点之间的均方误差的差额将被用来作为特征选择的标准这种方法通过使用叶子节点的均值来最小化L2损失
2输入“friedman_mse”使用费尔德曼均方误差这种指标使用弗里德曼针对潜在分枝中的问题改进后的均方误差
3输入"mae"使用绝对平均误差MAEmean absolute error
这种指标使用叶节点的中值来最小化L1损失属性中最重要的依然是feature_importances_
接口依然是apply, fit, predict, score最核心。

交叉验证

交叉验证是用来观察模型的稳定性的一种方法我们将数据划分为n份依次使用其中一份作为测试集其他n-1份作为训练集多次计算模型的精确性来评估模型的平均准确程度。训练集和测试集的划分会干扰模型的结果因此用交叉验证n次的结果求出的平均值是对模型效果的一个更好的度量。

代码示例

from sklearn.datasets import load_boston  # 波士顿房价数据集
from sklearn.model_selection import cross_val_score # 交叉验证
from sklearn.tree import DecisionTreeRegressor # 回归树
boston = load_boston()
regressor = DecisionTreeRegressor(random_state=0)
cross_val_score(regressor, boston.data, boston.target, cv=10, 
                scoring = "neg_mean_squared_error") # 均方误差

一维回归的图像绘制

import numpy as np
from sklearn.tree import DecisionTreeRegressor
import matplotlib.pyplot as plt

rng = np.random.RandomState(1)
X = np.sort(5 * rng.rand(80,1), axis=0) # 创建80个01的随机数扩大五倍排序
y = np.sin(X).ravel()  # 降维ravel
y[::5] += 3 * (0.5 - rng.rand(16)) # 每个5个数制造一个噪声

regr_1 = DecisionTreeRegressor(max_depth=2) # 模型1
regr_2 = DecisionTreeRegressor(max_depth=5) # 模型2
regr_1.fit(X, y) # 模型1训练
regr_2.fit(X, y) # 模型2训练

X_test = np.arange(0.0, 5.0, 0.01)[:, np.newaxis] # 创建一组测试集 np.newaxis 增维
y_1 = regr_1.predict(X_test) # 预测 模型1
y_2 = regr_2.predict(X_test) # 预测 模型2

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) # 回归预测图1
plt.plot(X_test, y_2, color="yellowgreen", label="max_depth=5", linewidth=2) # 回归预测图2
plt.xlabel("data")
plt.ylabel("target")
plt.title("Decision Tree Regression")
plt.legend()
plt.show()

如果树的最大深度由max_depth参数控制设置得太高则决策树学习得太精细它从训练数据中学了很多细节包括噪声得呈现从而使模型偏离真实的正弦曲线形成过拟合。

---