决策树学习用损失函数表示这一目标，其损失函数通常是正则化的极大似然函数，决策树学习的策略是以损失函数为目标函数的最小化。
树：
树有三种类型的节点
- 根节点
- 内部节点
- 叶子节点
树的节点包含一个数据元素及若干指向其子树的分支。节点拥有的子树数称为结点的度(Degree)。度为0的结点称为叶子节点(Leaf)或终端节点。度不为0的节点称为非终端节点或分支节点。除根节点之外，分支节点也称为内部节点。树的度是树内各节点的度的最大值。
信息熵：
X 信息熵定义为信息的期望值。
信息熵就是用来衡量一个随机变量取值的不确定性的一个指标，信息熵越大则不确定性越大，信息熵越小则不确定性也就越小。
假设一个随机变量X的概率分布如下：
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-LTW2Y3dB-41)(C:\Users\RUCchen\AppData\Roaming\Typora\typora-user-images\image-.png)]
条件熵：
设二维随机变量(X, Y)的概率分布为：
随机变量X给定条件下随机变量Y的条件熵表示为H(Y|X),已知随机变量X的情况下随机变量Y的不确定性，给定X的条件下随机变量Y的熵对于X的期望值，其定义如下：
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-HXE4Ywse-44)(C:\Users\RUCchen\AppData\Roaming\Typora\typora-user-images\image-.png)]
显然，对于数据集D而言，信息增益依赖于特征，不同的特征往往具有不同的信息增益，信息增益大的特征具有更强的分类能力。根据信息增益准则的特征选择方法：对训练数据集（或子集）D，计算其每个特征的信息增益，并比较它们的大小，选择信息增益最大的特征。
1.先计算信息熵 2.算特征下的的条件熵 3.算信息增益
信息增益率
信息增益值的大小是相对于训练数据集而言的，并没有绝对意义。在训练数据集的信息熵大的时候，信息增益值会偏大。反之，信息增益值会偏小。使用信息增益率（information gain ratio）可以对这一问题进行校正。
基尼系数
构建决策树
决策树学习的算法通常是一个递归地选择最优特征，并根据该特征对训练数据进行分割，使得各个子数据集有一个最好的分类的过程。
1） 开始：构建根节点，将所有训练数据都放在根节点，选择一个最优特征，按着这一特征将训练数据集分割成子集，使得各个子集有一个在当前条件下最好的分类。
2） 如果这些子集已经能够被基本正确分类，那么构建叶节点，并将这些子集分到所对应的叶节点去。
3）如果还有子集不能够被正确的分类，那么就对这些子集选择新的最优特征，继续对其进行分割，构建相应内部节点，如果递归进行，直至所有训练数据子集被基本正确的分类，或者没有合适的特征为止。
4）每个子集都被分到叶节点上，即都有了明确的类，这样就生成了一颗决策树。
如何决定什么时候停止分支呢？
ID3算法
在决策树各个结点上应用信息增益准则选择特征，递归地构建决策树。具体方法是：从根结点开始，对结点计算所有可能的特征的信息增益，选择信息增益最大的特征作为根结点的特征，由该特征的不同取值建立子结点。之后，对子结点递归地调用以上方法，构建决策树，直到所有特征的信息增益均很小或没有特征可以选择为止，最终得到一个决策树。ID3相当于用极大似然法进行概率模型的选择。
输入：训练数据集合D，特征集A，阈值ϵ
输出：决策树T
1.若D中所有实例属于同一类Ck则T为单结点树，并将类Ck作为该结点的类标记，返回决策树T
2.若A是空集，T为单节点树，并将D的实例树最大的类Ck作为该节点的类标记，返回决策树
3.否则，计算A各特征对D的信息增益，选择信息增益最大的特征a
4.如果a的信息增益小于阈值ϵ，则T为单节点数，将D里的实例树最大的类Ck作为该节点
5.否则对于a的每一个可能值a*，按照a=a*将D分割为若干非空子集Dv，将Dv里的实例数最大的类作为该节点，构建子节点，由节点和子节点构成决策树T，返回决策树T。
6.对第 v个子结点，以Dv为训练集，以A−{a}为特征集，递归地调用第(1)步~第(5)步，得到子树T
C4.5算法
C4.5决策树算法不直接使用信息增益来选择划分属性，而是使用信息增益率来选择最优划分属性。
信息增益率越大就优先变成为节点。
评价
参数学习：先假定数据属于一定的分布，然后再进行操作
非参数学习：不做先验假设
决策树算法：
属于非参数学习；有强的解释力；计算效率不一定高；
在训练数据集合具有相关性（比如多重共线性）则不用决策树模型；
决策树模型对于处理移失值具有优势（利用基于概率的切分方法、基于替换的切分方法等）
非参数学习：不做先验假设
决策树算法：
属于非参数学习；有强的解释力；计算效率不一定高；
在训练数据集合具有相关性（比如多重共线性）则不用决策树模型；
决策树模型对于处理移失值具有优势（利用基于概率的切分方法、基于替换的切分方法等）
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/178653.html原文链接：https://javaforall.net
