导图社区 机器学习之决策树
总结了几种常用的决策树算法，如ID3算法，C4.5算法，CART算法，以及剪枝技术和特征缺失问题等，欢迎查看。
提示: 本内容由社区用户上传并分享。平台不对内容的真实性、合法性、知识产权归属及是否侵害第三方权利进行事前审核或保证。本内容可能包含受版权保护的图片、字体或其他第三方素材，使用前请自行确认授权范围。
总结了循环神经网络RNN的基本内容，如RNN基本结构原理、RNN计算训练的BPTT算法、长短期记忆模型LSTM和门控循环单元GRU的基本原理等
总结了卷积神经网络的主要内容，如基本概念，卷积运算，基本结构，参数学习方法以及一些卷积神经网络实例结构。
总结了最基本的神经网络结构——多层感知机MLP和前馈网络FNN，在此基础上总结了神经网络的目标函数和优化技术，反向传播算法计算目标函数对网络权系数的梯度问题，以及神经网络优化的辅助技术如初始化、正则化等。
社区模板帮助中心，点此进入>>
互联网9大思维
组织架构-单商户商城webAPP 思维导图。
域控上线
python思维导图
css
CSS
计算机操作系统思维导图
计算机组成原理
IMX6UL(A7)
考试学情分析系统
机器学习 决策树
基本决策树算法
决策树的基本结构
节点
表示特征
有多少特征，就有多少层节点
根节点
最顶点的根节点
叶节点
已经可以做出分类结果的节点
父节点
子节点
边
特征取值
特征取值数量就是该特征节点向下分叉数量
决策树构造算法的核心
如何决定一个节点已是叶节点还是继续向下引出新的节点
信息增益和ID3算法
构造决策树的方法 贪婪分层搜索算法
确定根节点
通过一个准则找到一个最合适的特征作为根节点
子节点与子样本集
根据根节点特征的不同取值把样本集分成几组子样本集
将子样本集中根节点已用到的特征删去
叶节点判断
若某子样本集的所有标注都相同，该节点确定为叶节点
若一个节点对应的子样本集标注不同且特征向量非空，该节点确定为新的根节点
依次类推至所有端节点都为叶节点
不纯性度量IM
来源
若样本集所有标注都是一致的，不纯性为0，无需更多的决策
若样本集只有两类标注且数目近似一致，则不纯性最高，需要更多的决策
熵（ID3算法）
pk是标注第k类的概率
根节点定量选择
选择(熵增益最大）对不纯性降低最大的特征构成根节点
条件熵
熵增益
ID3算法
创建树的根节点
若特征D中的所有标注都相同，返回一个单一根节点树，输出为该标注类型
若特征向量为空，返回一个单一根节点数，输出为标注最多的类
计算各特征的信息增益
将信息增益最大的特征记为A
A作为根节点特征，对于A的每个取值i
在根节点下加一条新的边，其对应的测试条件为A=i
令Di为D中满足A=i的样本子集
如果Di为空
该边下端设为叶节点，叶节点的输出为D中标注最多的类
否则在这个边下端加一个新的子树，重新调用ID3，Di作为初始特征
返回根
信息增益率和C4.5算法
C4.5相较于ID3优点
由于ID3中用信息增益选择特征时偏向选择取值数多的特征，C4.5用信息增益率选择特征，适用于特征之间取值数目比较分散的情况
针对ID3易于过拟合的问题，在树构造过程中引入剪枝技术
ID3的特征只能取离散值，若一个特征是连续数值量，则需要预先离散化，C4.5既可以处理离散特征，也可处理连续特征
能够处理样本特征缺失的情况
特征A的分裂信息
信息增益率
除以分裂信息可以抑制取值多的特征的信息增益值
问题
某个特征几乎只取某个值，信息增益容易非常大或不存在
避免方法
先计算信息增益，并计算增益平均值，对于信息增益大于平均值的特征再计算信息增益率，并利用计算出的信息增益率选择特征
C4.5算法
除了以信息增益率替代信息增益作为选择特征的准则外，算法流程与ID3算法的叙述是一致的
CART算法
分类树
基尼指数（不纯性度量）
分支构造思路
特征值A只有两个取值
两个分支分别表示这两个取值
下层节点中将特征A删除
特征A有多个取值
A=j
下层节点中把A特征删除
A≠j
将A特征的取值j删除，其他取值仍需继续测试
判断叶节点条件
该节点对应的子样本集为空，在较大规模的问题中，更一般规则是该节点样本数小于预定的阈值
该节点所有样本都是同一标注，或更一般的基尼指数小于预定的阈值
或已没有更多特征可用
CART分类算法
若D中的所有标注都相同，返回一个单一根节点树，输出为该标注类
若特征向量为空，返回一个单一根节点数树，输出为标注最多的类
若一个特征A只有一个取值，删除该特征
计算各特征和特征的各取值的Gini指数
若特征A只有两个取值，只计算第1个值的基尼指数
具有最小基尼指数的特征和取值为A=j，以A=j为是或否将样本集分为D1和D2，分为两条支路
判断
调用CART-C（D1，分类类型，删除特征A）
调用CART-C（D1，分类类型，删除特征取值A=j）
若Di为空，节点设为叶节点，叶节点的输出为D中标注最多的类
若Di只有一种标注，节点设为叶节点，输出为该标注
若特征为空，节点设为叶节点，Di中最多类型的标注为输出
回归树
平方逼近误差（不纯性度量）
误差最小的gm为标注的平均值
特征和切分点选择
叶节点判断阈值
CART回归算法
创建根节点
所有特征均无切分点
所有标注值取平均输出，并退出
有特征存在切分点
对Ai的取值做切分，切分样本集并计算逼近值
计算所有特征和切分点情况的误差平方和
遍历所有特征和切分点所对应的误差平方和，找到误差和最小的特征的切分点
均方根误差小于阈值
作为叶节点，输出标注值
均方根误差大于阈值
调用CART-R（Dm）
回归模型
决策树的一些实际问题
连续数值变量
切分点
标注发生变化的两个特征取值的平均
特征选择
选择使不纯性降低最大的特征和对应的切分点作为当前节点的决策特征
正则化和剪枝技术
目的
控制不纯性最小化和模型最小化之间的平衡
提高泛化能力，减小过拟合
树的损失函数
不纯性度量+树复杂度的惩罚项
剪枝思路
确定超参数
交叉验证，将样本集分出独立的一组样本作为验证集
损失函数下降法
从树的最底层叶节点开始，删除该节点得到新树T1，计算T1的损失函数
依次类推删除节点，直至损失函数最小
剪枝后损失函数减少度量
单节点树t的损失函数
以t为根节点的子树Tt的损失函数
CART剪枝算法
计算各节点剪枝损失函数度量
对最小α的内部节点进行剪枝
删除t的所有子孙节点并设t为叶节点，剪枝后的树记为Tk
分类问题
输出用多数表决法确定其类
回归问题
用各样本标注值的平均作为节点输出
剪枝结束判断
如果Tk不是由根节点及两个叶节点构成的树，则需重新进行上述步骤
最优选择
计算产生的各子树的目标函数
使目标函数最小的树Ti和对应参数αi作为最优的剪枝决策树和相应超参数
缺失属性的训练样本问题
缺失属性样本例子
问卷调查
医疗检查
处理方法
填补法
对所有与该样本标注相同的样本子集的该特征取均值，用均值对该缺失特征赋值
对样本集中所有缺失样本赋值后，用标准方法生成决策树
概率分配法
概率计算
删除特征A取值缺失的样本，删除后样本占原来的比例
各标注类型k样本占删除后样本集的概率估计
特征A各取值的概率估计
特征A信息增益
分配方法
特征划分
按照信息增益最大的特征A0对全部样本集进行划分
概率分配
样本特征A0有值
按取值分配到对应子样本集，加权系数wn不变
样本特征A0缺失
将其分配到所有子样本集中，但加权系数变为
