机器学习算法——决策树1（基础）

2019-08-20 本文已影响0人皮皮大

决策树

导读

决策树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中，可以表示为 $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$ 为样本容量。决策树的目标是根据给定的训练集数据构造一个决策树模型，使它能够对实例进行正确地分类。