决策树
2018-04-13 本文已影响4人
汤尧
- 读书笔记
- 机器学习
- 决策树
- 基本概念
- 基于树结构进行决策，即有一个根结点，若干个内部节点和若干个叶节点。
- 目的是为了产生一一个泛化能力强，即处理未见示例能力强的决策树。
- 基本流程
- 输入
- 训练集D
- 属性集A
- 过程：函数TreeGenerate（D，A）
- 生成节点node
- if D中样本全部属于同一类别C then
将node标记为C中类叶节点；return- end if
- if A = empty set or D中样本在A上的取值相同 then
将node标为叶节点，其类别标记为D中样本数最多的类；return- end if
- 从A中选择最优属性a*
- for a* 中的每一个值a` do
为node生成一个分支；令Dv表示D中在a*上取值为a`的样本子集if Dv为空 then将分支结点标记为叶节点，其类别标记为D中样本最多的类；returnelse以TreeGenerate（D，A\{a*}）为分支结点end if- end for
- 输出
- 以node为根节点的一颗决策数
- 输入
- 决策数的生成是一个递归的过程，有三种情况决策树会导致递归返回。
- 当前节点包含的样本全属于同一类别，无须划分
- 当前属性集为空，或是所有样本在所有属性上取值相同，无法划分
- 当前结点包含的样本集合为空，不能划分。
- 划分选择
- 在决策数算法中，最重要的是如何选择最优属性。一般而言，随之划分过程的不断进行，我们希望决策树的分支节点所包含的样本尽可能属于同一类别，即结点的纯度（purity）越来越高
- 信息增益（ID3）
- 度量样本集合纯度的指标：信息熵
- 假定当前样本集合D中第k类样本所占的比例为Pk（k = 1，2·······|y|），则D中信息熵Ent（D）为-Pk·log2（Pk）从1到|y|的和。
- 假设离散属性a有n个取值，如果用属性a对样本D进行划分，那么就会得出n个分支结点，对每个分支结点上取到的样本Dv，计算出每个Dv的信息熵，乘以权重（Dv的样本数与D样本数之商），的和，在用总的信息熵减去其，得出信息增益。
- 缺点：信息增益准则对可取值数目较多的属性有所偏好。
- 度量样本集合纯度的指标：信息熵
- 增益率（C4.5改善信息增益的缺点）
- 用信息增益除以固有值IV。令a =Dv的样本数与D样本数之商。IV = a·log2a 对于所有的v之和
- 但是，增益率准则可能对取值数目较少的属性有所偏好，所以C4.5并不是直接采用选择增益率最大的候选划分属性，而是采用一种启发式，先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。
- 基尼指数（CART）
- 基尼值反映了从数据集中随机抽取两个样本，其类别标记不一致的概率，基尼值越小，样本纯度越高
- 基尼指数为a乘以基尼值之和
- 剪枝处理
- 目的是为了对付过拟合
- 基本策略
- 预剪枝（prepruning）
- 指在决策树生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点标记为叶结点
- 优点：不仅降低了过拟合的风险，还显著减少了决策树的训练时间开销和测试时间开销。
- 缺点：有些分支的当前划分虽不能提高泛化性能、甚至可能导致泛化性能暂时下降，但在其基础上进行的后续划分却有可能导致性能显著提高，会带来欠拟合的风险。
- 后剪枝（post-prunning）
- 先从训练集生成一棵完整的决策树，然后自底向下地对非叶节点进行考察，若将该结点对应的子树替换成叶结点能带来决策树泛化性能提升，则将该子树替换成叶结点
- 优点：欠拟合风险小，泛化性能往往优于预剪枝决策树。
- 缺点：开销时间大
- 预剪枝（prepruning）
- 连续值与缺失值
- 连续值处理
- 采用二分法对连续属性离散化
- 给定样本集D和连续属性a，假定a在D上出现了n个不同的取值，将这些值从小到大排序，记为{a1,a2·······an}，基于划分点t可将D分为子集D-和D+，其中D-包含那些在属性a上取值不大于t的样本，而D+则包含哪些在属性a上取值大于t的样本，显然，对相邻的属性取值ai与ai+1来说，t在区间[ai,ai+1）取任意值所产生的划分效果相同。因此，对连续属性a，我们可考察包含n-1个元素的候选划分点集合Ta = {(ai+ai+1)/2|1<=i<=n-1},即把区间[ai,ai+1）的中位点作为候选划分点，然后，我们就可像离散属性值一样考察这些划分点，选取最优的划分点进行样本集合的划分，依旧采用信息增益。取最优解。
- 与离散属性不同，若当前结点划分属性为连续属性，该属性还可作其后代结点的划分属性。
- 缺失值处理
- 面临的问题
- 如何在属性值缺失的情况下进行划分属性选择
- 给定划分属性，若样本在该属性上的值缺失，如何对样本进行划分
- 将缺失值根据权重放入每个属性中。权重剪枝时使用。
- 面临的问题
- 采用二分法对连续属性离散化
- 连续值处理
- 基本概念
- 决策树
- 机器学习
