决策树
导读
决策树Decision Tree是一种基本的分类和回归方法。决策树模型呈现树形结构，在分类问题上，主要是基于特征对样本实例进行分类。其主要是的优点是：
- 模型具有可读性和解释型，推理过程容易理解，决策推理过程可以表示为
if - then的形式 - 在训练数据的时候，根据损失函数最小化的原则建立决策树模型
- 推理过程完全取决于属性变量的取值特点
- 可以自动忽略没有贡献的属性变量，为判断属性的重要性，减少变量的数目提供参考，提高分类速度
image.png
决策树三步骤
- 特征选择
- 决策树的生成
- 决策树的修剪
- 预剪枝
- 后剪枝
常用的算法
- ID3
- C4.5
- CART
决策树模型与学习
定义
分类决策树模型是一种描述实例进行分类的树形结构。决策树由决策节点
node、分支（也叫有向边directed edge）和叶子leaf组成。节点分为两种：
- 内部节点：
internal node，表示一个特征或者属性 - 叶子节点：
leaf node，表示一个具体的类
具体过程：根节点开始，对实例的某一个特征进行分类，根据测试结果，将实例分配到其子节点；子节点对应着该特征的一个取值。递归分配，直至到达叶结点，最后将实例分配到叶结点的类中。
栗子
image.png
- 根节点：决策树最上面的点，整个决策树的开始
- 叶子：每个分支是新的决策节点
- 决策节点：对应一个待分类的特征或者属性
决策树与条件概率分布
- 决策树表示给定特征条件下，类的条件概率分布。
- 条件概率分布定义在特定空间的一个划分
partition，将特征空间划分成互不相交的单元cell或者区域region - 每个单元定义一个类的概率分布就构成了一个条件概率分布
- 条件：在某个特征或者属性
X的划分之下 - 概率分布：根据特征或属性将实例划分到某个类别Y中，可以表示为
- 条件：在某个特征或者属性
- 整个决策树的条件概率分布由所有类的条件概率分布组成
决策树学习
假设给定一个训练数据集其中，
为输入实例，或者称之为特征向量（属性），
n为特征个数，，
,
为样本容量。决策树的目标是根据给定的训练集数据构造一个决策树模型，使它能够对实例进行正确地分类。
决策树的本质：是从训练数据集中归纳出一组分了规则。能够对训练数据集进行正确分类的决策树可能有多个，可能一个也没有。决策树学习是由训练数据集估计条件概率模型。
- 选择一个和训练数据矛盾较小的决策树
- 泛化能力好，即对新的数据能够较好地预测分类
决策树学习的损失函数通常是正则化的极大似然函数，策略是最小化损失函数
决策树学习算法
决策树学习算法通常是一个个递归地选择最优化特征，并且根据该特征对训练数据集进行分割，使得对各个子数据集有一个最好的分类的过程。该过程包含：特征空间的划分 + 决策树的生成。
- 构建根节点，将全部的数据放在根节点上进行训练
- 选择一个最优特征，按照这个特征将训练数据分割成子集，使得各个子集在当前最好的类中
- 如果子集能够被基本正确分类，构建叶结点，并将这些子集分到对应的叶结点中去
- 如果子集不能被正确地分类，继续选择最优的特征，继续分类，构建相应的节点
- 递归以上的步骤，直至所有的数据子集能够被基本正确分类，生成一棵决策树。
网友评论