机器学习算法12——决策树1

浏览: 1433

决策树

导读

决策树Decision Tree是一种基本的分类回归方法。决策树模型呈现树形结构,在分类问题上,主要是基于特征对样本实例进行分类。其主要是的优点是:

  • 模型具有可读性和解释型,推理过程容易理解,决策推理过程可以表示为if - then的形式
  • 在训练数据的时候,根据损失函数最小化的原则建立决策树模型
  • 推理过程完全取决于属性变量的取值特点
  • 可以自动忽略没有贡献的属性变量,为判断属性的重要性,减少变量的数目提供参考,提高分类速度

决策树三步骤

  • 特征选择
  • 决策树的生成
  • 决策树的修剪
    • 预剪枝
    • 后剪枝

常用的算法

  • ID3
  • C4.5
  • CART


决策树模型与学习

定义

分类决策树模型是一种描述实例进行分类的树形结构。决策树由决策节点node、分支(也叫有向边directed edge)和叶子leaf组成。节点分为两种:

  • 内部节点:internal node,表示一个特征或者属性
  • 叶子节点:leaf node,表示一个具体的类

具体过程:根节点开始,对实例的某一个特征进行分类,根据测试结果,将实例分配到其子节点;子节点对应着该特征的一个取值。递归分配,直至到达叶结点,最后将实例分配到叶结点的类中。

栗子

image.png

  • 根节点:决策树最上面的点,整个决策树的开始
  • 叶子:每个分支是新的决策节点
  • 决策节点:对应一个待分类的特征或者属性

决策树与条件概率分布

  • 决策树表示给定特征条件下,类的条件概率分布。
  • 条件概率分布定义在特定空间的一个划分partition,将特征空间划分成互不相交的单元cell或者区域region
  • 每个单元定义一个类的概率分布就构成了一个条件概率分布
    • 条件:在某个特征或者属性X的划分之下
    • 概率分布:根据特征或属性将实例划分到某个类别Y中,可以表示为P(Y|X)
  • 整个决策树的条件概率分布由所有类的条件概率分布组成

决策树学习

假设给定一个训练数据集D=\{(x_1,y_1),...,(x_N,y_N)\}其中,x_i=(x_i^{(1)},x_i^{(2)},...,x_i^{(n)})^T为输入实例,或者称之为特征向量(属性),n为特征个数,y_i \in \{1,2,3,...,K\}为输出类的标记i=1,2,3,...,N,N为样本容量。决策树的目标是根据给定的训练集数据构造一个决策树模型,使它能够对实例进行正确地分类。

决策树的本质:是从训练数据集中归纳出一组分了规则。能够对训练数据集进行正确分类的决策树可能有多个,可能一个也没有。决策树学习是由训练数据集估计条件概率模型。

  • 选择一个和训练数据矛盾较小的决策树
  • 泛化能力好,即对新的数据能够较好地预测分类

决策树学习的损失函数通常是正则化的极大似然函数,策略是最小化损失函数

决策树学习算法

决策树学习算法通常是一个个递归地选择最优化特征,并且根据该特征对训练数据集进行分割,使得对各个子数据集有一个最好的分类的过程。该过程包含:特征空间的划分 + 决策树的生成。

  • 构建根节点,将全部的数据放在根节点上进行训练
  • 选择一个最优特征,按照这个特征将训练数据分割成子集,使得各个子集在当前最好的类中
  • 如果子集能够被基本正确分类,构建叶结点,并将这些子集分到对应的叶结点中去
  • 如果子集不能被正确地分类,继续选择最优的特征,继续分类,构建相应的节点
  • 递归以上的步骤,直至所有的数据子集能够被基本正确分类,生成一棵决策树。
推荐 0
本文由 皮大大 创作,采用 知识共享署名-相同方式共享 3.0 中国大陆许可协议 进行许可。
转载、引用前需联系作者,并署名作者且注明文章出处。
本站文章版权归原作者及原出处所有 。内容为作者个人观点, 并不代表本站赞同其观点和对其真实性负责。本站是一个个人学习交流的平台,并不用于任何商业目的,如果有任何问题,请及时联系我们,我们将根据著作权人的要求,立即更正或者删除有关内容。本站拥有对此声明的最终解释权。

0 个评论

要回复文章请先登录注册