前言
决策树是一种基本的分类与回归方法。其中在分类问题中，决策树是一个基于特征对实例进行分类的过程，可以理解为是if-then规则的集合，或者是定义在特征空间上的条件概率分布。其优点是可读性强、分类速度快。决策树学习时，利用训练数据，根据损失函数最小化原则建立决策树模型，预测时，对新数据依照训练出的模型进行分类。决策树通常的步骤分为：特征选择、决策树的生成、决策树的剪枝。
模型准备
决策树的定义：分类决策树模型是根据一类特征描述对实例进行分类的树形结构。决策树由节点和向边构成，其中结点分为内部结点和叶结点，内部结点表示一个特征或属性，叶结点表示一个类
决策树与if-then规则：决策树的每一个实例都能被一条路径或一条规则所覆盖，而且只被一条路径或一条规则所覆盖，即互斥且完备性
决策树与条件概率分布：假设X为表示特征的随机向量，Y为表示类的随机向量，则条件概率分布表现为P(Y|X),X取值于给定划分下单元的集合，Y取决于类的集合，各叶节点上的条件概率往往偏向某个类，属于某个类的概率较大，分类时间，决策树将该节点的实例强行分到条件概率大的那一类去
特征选择相关名词定义
信息增益
熵
定义：表示随机变量不确定性的度量，设X是一个取有限个值的离散型随机变量，其概率分布为<br /><br />则随机变量X的熵定义为 ；<br /> 特点：熵只取决于X的分布，而与X的取值无关，所以也将X的熵记为；<br /> 熵越大，随机变量的不确定性越大；<br />
条件熵
定义：在已知随机变量X的条件下，随机变量Y的不确定性，即：X给定条件下Y的条件概率分布的熵对X的数据期望<br />
信息增益
定义：表示得知特征X的信息而使得类Y的信息的不确定性减少的程度；
特征A对训练数据集D的信息增益
特点：信息增益依赖于特征X，不同的特征X有不同的信息增益，信息增益大的特征分类能力较强;
信息增益的大小相对于训练数据集而言，训练数据集的信息熵越大，信息增益值越大
信息增益比
定义：表示特征X的信息增益与训练数据集D的经验熵的比；<br /> <br /> 特点：矫正了信息增益值受到训练数据集D的影响的问题，可做为特征选择的另一个准则；
基尼指数
定义：分类问题中，假设有K个类，样本点属于第K个类的概率为,则概率分布的基尼指数的定义为<br /> <br /> 样本集合D的基尼指数的定义为<br /> 特征A条件下集合D的基尼指数 <br /> 特征：基尼指数表示 集合D的不确定性，表示经过A=a 分割后，集合D的不确定性；基尼指数越大，不确定性也越大；<br />
决策树的生成-模型构建
ID3算法
原理
在决策树各个节点上按照信息增益最大的原则选择特征，递归地构建决策树；在根节点上，计算所有特征的信息增益，选择信息增益最大的特征作为结点，再由该特征的不同特征值建立子节点，计算信息增益，递归调用以上方法，直到所有特征的信息增益均很小或者没有特征可以选择为止。
算法
C4.5的生成算法
原理
C4.5的算法与ID3类似，唯一的区别在于C4.5是基于信息增益比来选择特征
算法
决策树的剪枝
背景
决策树往往会对训练数据的分类很准确，但是对未知测试数据的分类会出现过拟合的现象，不是那么准确。这是因为在决策树分类的过程中过多的考虑了分类的正确性而构建出过于复杂的决策树
原理
通过极小化决策树整体的损失函数或者代价函数来实现剪枝，损失函数<br />的定义为
若有收获，就点个赞吧
0 人点赞
