首页 > 编程语言 >【高级机器学习算法】7.决策树

【高级机器学习算法】7.决策树

时间:2023-10-15 21:00:58浏览次数:64  
标签:分割 机器 特征 样本 算法 Ent 节点 决策树

决策树模型

决策树定义

决策树是一种基本的分类与回归方法,是一种树形结构,其中每个非叶子节点表示一个特征属性上的测试,

每个分支代表这个特征属性在某个值域上的输出,每个叶子节点存放一个类别。

决策树学习算法的任务是在所有可能的决策树中选择一个表现良好的决策树,即在训练集上表现良好且能很好地泛化到新数据(如交叉验证集和测试集)的决策树。

img

  • 节点:
    • 根节点:没有进入的边,表示整个数据集
    • 决策节点:有进入的边,表示数据集的一个子集
    • 叶子节点:没有出去的边,表示一个类别

分类过程

使用决策树进行决策的过程就是从根节点开始,测试待分类项中相应的特征属性,并按照其值选择输出分支,直到到达叶子节点,将叶子节点存放的类别作为决策结果。

决策树的构造

选择用于分割的特征

  • 纯净:一个节点中只有一种类别
  • 杂质:一个节点中有多种类别

用于分割的特征应该使得分割后的子节点尽可能的纯净,即杂质尽可能的小。

信息熵

信息熵是度量样本集合纯度最常用的一种指标,假定当前样本集合D中第k类样本所占的比例为\(p_k(k=1,2,\cdots,|\mathcal{Y}|)\),则D的信息熵定义为:

\[Ent(D)=-\sum_{k=1}^{|\mathcal{Y}|}p_k\log_2p_k \]

定义\(log_2(0)=0\)

为了选择最佳拆分特性,可能要计算每个特征的加权信息熵,计算方法如下:

\[w_left*Ent(p_{left})+w_right*Ent(p_{right}) \]

其中,\(w_left\)和\(w_right\)分别是左右子树中样本所占的比例。

信息增益

信息增益表示得知特征X的信息而使得类Y的信息的不确定性减少的程度。

特征A对训练数据集D的信息增益\(infomation Gain(D,A)\),定义为集合D的信息熵\(Ent(D)\)与特征A给定条件下D的信息条件熵\(Ent(D|A)\)之差,即:

\[infomation Gain(D,A)=Ent(p_1^{root})-(w_left*Ent(p_{left})+w_right*Ent(p_{right})) \]

img

分割的停止条件

  • 当前节点中的样本全部属于同一类别
  • 当树的深度达到预先设定的最大深度
  • 分割带来的杂质下降不大于预先设定的阈值
  • 当前节点中的样本个数小于预先设定的阈值

递归构建决策树

从根节点开始,对节点计算所有可能的特征的信息增益,选择信息增益最大的特征作为节点的特征,由该特征的不同取值建立子节点,再对子节点递归地调用以上方法,构建决策树,直到所有截至条件满足为止。

复杂特征值处理

独热编码

多值特征是指一个特征的取值不是固定的,而是有多个取值,比如一个人的爱好,一个人可能有多个爱好,比如爱好是:篮球、足球、乒乓球,这样的特征就是多值特征。

独热编码是指将一个特征的每个取值都转化为一个新的特征,新特征的取值只有0和1,1表示这个样本的这个特征取值是这个,0表示这个样本的这个特征取值不是这个。

一个人的爱好是篮球,则独热编码后的特征为:篮球:1,足球:0,乒乓球:0

连续值处理

决策树学习算法需要考虑在不同特征上进行分割,如果在连续特征上分割可以获得更好的信息增益,那么就选择该特征进行分割。

选择最佳分割点

对于连续特征,我们可以选择一个最佳分割点,将连续特征分割成两个离散的值,然后再进行分割。

回归树

回归树同决策树类似,只是回归树的叶子节点存放的是一个数值,而不是一个类别。回归树完成了对数据的回归拟合。

回归树的构造

分裂特征的选择:选择一个特征和一个分割点,使得分割后的两个子集的均方差最小。

树集

多决策树

单一决策树的泛化能力较差,容易过拟合,因此可以使用多个决策树进行集成,即多决策树

在树集成中,每个决策树都对新的测试样本进行预测,最终的预测结果由所有决策树的预测结果综合得到。

随机森林

有放回抽样

有放回抽样:每次抽取一个样本后,都将该样本放回,使得该样本在下一次抽取时仍有可能被抽取到。

在构建树集成时,有放回抽样可以用于从原始数据集中生成多个不同的训练子集,以便为每个子集训练一个独立的决策树,确保树集成中的决策树具有足够的多样性,提高模型的健壮性

随机森林的构建

随机森林的构建过程如下:

  1. 从原始数据集中使用有放回抽样的方式抽取n个样本,作为训练集,剩余的样本作为测试集。

  2. 从训练集中使用有放回抽样的方式抽取m个特征,作为决策树的分割特征。

    m一般取\(\sqrt{d}\),d为特征的个数

  3. 使用上述训练集和分割特征训练一个决策树。

  4. 重复上述步骤1-3,构建多个决策树。

由于有放回抽样过程使得算法探索了许多对数据的小变化,并且在训练不同的决策树时对这些变化进行平均,所以对训练集的进一步小变化不太可能对随机森林算法的整体输出产生巨大影响。这使得随机森林比单个决策树更具有健壮性。

XGBoost

XGBoost是一种集成学习算法,它是梯度提升算法的一种实现,它在梯度提升算法的基础上做了一些改进,使得它在速度准确率上都有所提升。

XGBoost实现

分类的实现

from xgboost import XGBClassifier
model = XGBClassifier()
model.fit(X_train, y_train)

y_pred = model.predict(X_test)

回归的实现

from xgboost import XGBRegressor
model = XGBRegressor()
model.fit(X_train, y_train)

y_pred = model.predict(X_test)

决策树和神经网络的选择

决策树:

  • 在结构化数据上表现良好
  • 训练速度快
  • 小型决策树解释性强

神经网络:

  • 在所有类型的数据上表现良好,包括结构化数据和非结构化数据、混合数据
  • 训练速度慢
  • 神经网络适用于迁移学习,对于只有少量数据的应用而言,这非常重要。
  • 构建多个机器学习模型协同工作的系统时,将多个神经网络连接并训练可能比多个决策树更容易

标签:分割,机器,特征,样本,算法,Ent,节点,决策树
From: https://www.cnblogs.com/agitm/p/17766173.html

相关文章

  • 文心一言 VS 讯飞星火 VS chatgpt (113)-- 算法导论10.2 5题
    五、用go语言,使用单向循环链表实现字典操作INSERT、DELETE和SEARCH,并给出所写过程的运行时间。文心一言:在Go语言中,我们首先需要定义一个Node结构体来表示单向循环链表的节点,然后再定义一个LinkedList结构体来表示单向循环链表。接下来,我们可以实现INSERT、DELETE和SEARCH操作。......
  • 文心一言 VS 讯飞星火 VS chatgpt (113)-- 算法导论10.2 5题
    五、用go语言,使用单向循环链表实现字典操作INSERT、DELETE和SEARCH,并给出所写过程的运行时间。文心一言:在Go语言中,我们首先需要定义一个Node结构体来表示单向循环链表的节点,然后再定义一个LinkedList结构体来表示单向循环链表。接下来,我们可以实现INSERT、DELETE和SEARCH操作......
  • 车辆车型识别系统python+TensorFlow+Django网页界面+算法模型
    一、介绍车辆车型识别系统。本系统使用Python作为主要开发编程语言,通过TensorFlow搭建算法模型网络对收集到的多种车辆车型图片数据集进行训练,最后得到一个识别精度较高的模型文件。并基于该模型搭建Django框架的WEB网页端可视化操作界面。实现用户上传一张车辆车型图片识别其名称......
  • 旋转调度算法
              ......
  • 搜索与图论2.2-Floyd算法
    一、简述\(Floyd\)算法是一种可以快速求解图上所有顶点之间最短路径的算法。\(Bellman-Ford\)和\(Dijkstra\)算法求解的都是从一个起始点开始的最短路。如果想要求解图中所有顶点之间的最短路,就需要枚举每个点做为起点,这样十分低效。\(Floyd\)算法(也称\(Floyd-Warshall\)......
  • 车辆车型识别系统python+TensorFlow+Django网页界面+算法模型
    一、介绍车辆车型识别系统。本系统使用Python作为主要开发编程语言,通过TensorFlow搭建算法模型网络对收集到的多种车辆车型图片数据集进行训练,最后得到一个识别精度较高的模型文件。并基于该模型搭建Django框架的WEB网页端可视化操作界面。实现用户上传一张车辆车型图片识别其名......
  • 磁盘调度算法
            ......
  • 科普知识:Arduino助力人工智能机器人课程
    一、课程目标初级课程主要面向大学通识课程、中小学教师,通过教师讲解了解机器人的发展、基本原理、关键技术以及与人工智能的关系和发展,通过文献调研对机器人领域形成自己的认识,通过课堂协作、竞赛任务完成实践对机器人的设计、控制和优化。共计32学时。1、Arduino的优势比如你......
  • 排序算法
    排序算法1、冒泡排序​ 冒泡排序是一种非常直接,但是性能比较低的排序方法,其时间复杂度为$\mathcal{O}{n^2}$,它通过两两比较数组中的元素,若第一个元素大于第二个元素,则将两个元素交换位置,逐步将元素中的最大值归位。其排序过程如下图所示:C++代码如下:template<typenameT>void......
  • Python滑动窗口算法:滑动窗口算法(4 by 4 sliding window price)
    我知道滑动窗口算法的时间复杂度是o(N),但是可变大小的滑动窗口算法的时间复杂度是多少。对于e-数组=[1,2,3,4,5,6]当滑动窗口的大小为=1时窗口-[1],[2],[3],[4],[5],[6]当滑动窗口的大小为=2时窗口-[1,2],[2,3],[3,4],[4,5],[5,6]当滑动窗口的大小为=3时窗口-[1,2,3],[2......