快速搭建个人网站,百度网址大全首页,免费外链网盘,wid2008vps创建网站一、决策树简介 首先决策树是一种有监督的机器学习算法#xff0c;其采用的方法是自顶向下的递归方法#xff0c;构建一颗树状结构的树#xff0c;其具有分类和预测功能。其基本思想是以信息熵为度量构造一棵熵值下降最快的树#xff0c;到叶子节点处的熵值为零。决策树的构…一、决策树简介 首先决策树是一种有监督的机器学习算法其采用的方法是自顶向下的递归方法构建一颗树状结构的树其具有分类和预测功能。其基本思想是以信息熵为度量构造一棵熵值下降最快的树到叶子节点处的熵值为零。决策树的构建通常分为三个步骤
1、特征选择 特征选择就是要选取具有较强分类能力的特征分类能力通过信息增益或信息增益率来进行刻画。选择的标准是找出局部最优的特征作为判断进行切分取决于切分后节点数据集合中类别的有序程度。衡量节点的数据集合的纯度有信息增益率、基尼系数和方差方差主要是针对回归的。
2、决策树的生成 在决策树的生成算法中常规的算法有ID3和C4.5生成算法。两者生成的过程类似区别在于前者采用信息增益作为特征的度量而后者采用信息增益率。但ID3和C4.5存在某些不足因此改进的CART算法便产生了它是采用基尼系数作为度量属性的选择。
3、决策树剪枝 决策树需要剪枝的原因是决策树的生成算法生成的树对训练数据的预测很准确但是对于未知的数据分类能力却很差容易产生过拟合的现象。剪枝的过程是从已经生成的决策树上剪掉一些子树或者叶子节点。剪枝的目标是通过极小化决策树的整体损失函数或代价函数实现其目的是提高模型的泛化能力。
二、决策树的生成算法
主要有ID3、C4.5和CART树算法。
首先来介绍ID3算法 其思路是用信息增益的大小来判断当前节点应该用什么特征来构建决策树用计算出的信息增益最大的特征来建立决策树的当前节点。 特征A对训练数据集D的信息增益g(D,A)定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差即
g(D,A)H(D) – H(D|A) 其中H(D)度量了D的不确定性H(D|A)度量了D在知道了A以后D剩下的不确定性两者之差则度量了D在知道了A以后不确定性的减少程度。
ID3算法的不足
1、其没有考虑连续特征比如长度密度都是连续值
2、其采用的信息增益大的特征优先建立决策树的节点。这就导致了在相同条件下取值较多的特征比取值较少的特征的信息增益 大。例如一个变量有两个值都为1/2另一个变量有三个值都为1/3由于他们都是完全不确定的变量但是取3个值的比取2个值的信息增益大。
3、ID3算法没有对于缺失值的情况做考虑。
4、ID3算法没有考虑过拟合的问题。
其次是C4.5算法
对于ID3算法存在的问题C4.5对其做了进一步的改进。 首先对于不能处理连续特征的问题C4.5的思路是将连续的特征离散化。比如m个样本的连续特征A有m个从小到大排列为a1,a2...,am则C4.5取相邻两样本值的平均数一共取得m-1个划分点其中第i个划分点Ti表示为Ti(aia(i1))/2。对于这m-1个点分别计算该点作为二元分类点时的信息增益。选择信息增益最大的点作为该连续特征的二元离散分类点。比如取到的增益最大的点为at则小于at的值为类别1大于为类别2这样就做到连续特征的离散化处理。 其次对于信息增益作为标准容易偏向于取值较多的特征的问题。引入了信息增益率作为度量特征的选择它是信息增益和特征熵的比值。表达式如下
Gr(D,A) g(D,A) / HA(D)
信息熵g(D,A)H(A)为特征熵对于H(A)其表达式如下 其中n为特征A的类别数Di为特征A的第i个取值对应的样本个数。D为样本个数。 再者对于缺失值的问题主要解决的问题主要有两个一是在样本某些特征缺失的情况下选择划分的属性二是选定了划分属性对于在该属性上缺失特征的样本处理。 最后对于过拟合的问题C4.5引入了正则化系数进行初步的剪枝。
C4.5算法的不足
1、C4.5剪枝的算法存在优化的空间。
2、C4.5算法生成的是多叉树即一个父节点可以有多个节点。
3、C4.5只能用于分类
4、C4.5由于使用了熵模型里面有大量的耗时的对数运算。
下面介绍CART算法 CART分类树算法使用基尼系数来代替信息增益比基尼系数代表了模型的不纯度基尼系数越小则不纯度越低特征越好。这和信息增益是相反的。 在分类问题中假设有K个类别第k个类别的概率为pk,则基尼系数的表达为 如果是二分类为题计算就更加简单如果属于第一个样本输出的概率为p则基尼系数的表达式为
Gini(p)2p(1-p) 对于给定的样本D假设有K个类别第k个类别的数量为Ck则样本D的基尼系数表达式为 Gini(D)1-∑|Ck|/|D|^2
特别地对于样本D如果根据特征A的某个值a把D分为D1和D2两部分则在特征A的条件下D的基尼系数表达式为 三、决策树CART算法的剪枝 目的 对于没有进行剪枝的树就是一个完全生长的决策树是过拟合的因此需要去掉一些不必要的节点以以提高训练出的决策树模型的泛化能力。
决策树算法剪枝的过程是由两个过程组成
1、从T0开始不断的剪枝直到剪成一颗单节点的树这些剪枝树形成一个剪枝树序列{T0,T1,T2...,Tn}。
2、从上面形成的剪枝序列中挑选出最优剪枝树。方法是通过交叉验证法使用验证数据集对剪枝树序列进行测试。
首先给出决策树算法的损失函数
Cα(T)C(T)α|T| 其中C(T)为决策树对训练数据的预测误差|T|为决策树的叶子节点数
对固定的α存在使Cα(T)最小的树令其为Tα可以证明Tα是唯一的。
当α大时Tα偏小即决策树比较简单
当α小时Tα偏大即决策树比较复杂
当α0时生成的决策树就是最优的
当α为无穷时根组成的一个单节点树就是最优的。
考虑生成树T0.对T0内的任意节点t,以t为单节点树记作t的损失函数为Cα(t)C(t)α,以t为根的子树Tt的损失函数为
Cα(Tt)C(Tt)α|Tt|。可以证明
当α0及充分小时有Cα(Tt)Cα(t)
当α增大到某个值时有Cα(Tt)Cα(t)
当α再增大时时有Cα(Tt)Cα(t) 因此令αC(tC(Tt))/(|Tt|-1),此时t与Tt有相同的损失函数值但是t的叶节点更少于是对Tt进行减值成一颗单节点树t了。 对T0内部的每一个节点t定义g(t)C(tC(Tt))/(|Tt|-1)。设T0内g(t)最小的子树为Tt*,令该最小值的g(t)为α1。从T0中剪去Tt*即得到剪枝树T1重复这种“求g(t)-剪枝”过程直到根节点即完成剪枝。在此过程中不断增加αi的值从而生成剪枝树序列。 CART剪枝交叉验证过程是通过验证数据集测试剪枝树序列{T0,T1,T2...,Tn}中个剪枝树的。对于CART回归树是考察剪枝树的平方误差平方误差最小的决策树被认为是最有决策树。对于CART分类树是考察基尼指数基尼指数最小的决策树被认为是最优的决策树。
四、决策树代码实例 下面是一个使用Python的scikit-learn库实现决策树的代码示例
# 导入所需的库
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.tree import DecisionTreeClassifier
from sklearn import metrics
import matplotlib.pyplot as plt
from sklearn.tree import plot_tree# 加载数据集
iris load_iris()
X iris.data # 特征向量
y iris.target # 目标变量# 将数据集划分为训练集和测试集
X_train, X_test, y_train, y_test train_test_split(X, y, test_size0.3, random_state1)# 创建决策树分类器
clf DecisionTreeClassifier(max_depth3, random_state1)# 训练决策树模型
clf.fit(X_train, y_train)# 使用训练好的模型进行预测
y_pred clf.predict(X_test)# 计算准确率
accuracy metrics.accuracy_score(y_test, y_pred)
print(准确率:, accuracy)# 可视化决策树
plt.figure(figsize(10, 6))
plot_tree(clf, filledTrue, roundedTrue, feature_namesiris.feature_names, class_namesiris.target_names)
plt.show() 以上代码实现了对鸢尾花数据集的分类任务。首先导入所需的库。然后加载鸢尾花数据集其中X是特征向量y是目标变量。接着将数据集划分为训练集和测试集其中测试集占总数据集的30%。然后创建一个决策树分类器并指定最大深度为3和随机种子为1。 在决策树模型中设置最大深度可以控制决策树的复杂度避免过拟合。较小的最大深度可以降低模型的复杂度但也可能导致欠拟合。随机种子用于重现结果确保每次运行代码时得到相同的结果。 接着使用训练集对决策树模型进行训练。然后使用训练好的模型对测试集进行预测并得到预测结果y_pred。 使用metrics.accuracy_score函数计算预测准确率并将结果打印出来。 最后使用matplotlib库将决策树可视化显示出来。通过调用plot_tree函数并传入决策树模型、特征名和目标类别名等参数可以生成决策树的图形化显示。
