剪枝分类器
剪枝分类器是指，对于d次维的输入变量x，任意选定其中一维，通过将其与给定阈值相比较来进行分类的线性分类器
剪枝分类器的要素：
• 一个输入维度
• 一个阈值
决策树
决策树是最符合人类决策机制的模型之一
决策树： 剪枝分类器经过一层一层累积，形成树状的结构
• 分叉节点：剪枝分类器
• 叶节点：判断结果
预测流程
- 数据样本从根节点进入决策树
- 数据节点在分支节点进行判定，根据判定
结果导入该节点的子节点 - 数据样本若到达分支节点，重复第2步；
若到达叶节点，得到最终判定结果
叶节点的输出判定
• 每个叶节点保存了一部分训练数据的子集
• 训练数据子集的类型分布决定了叶节点的输出概率
决策树学习
决策树学习过程就是树枝不断分裂长成大树的过程 （剪枝分类器的组合）
决策树学习：不断根据属性划分训练数据的过程
关键在于如何选择最优划分属性。一般而言，随着划分过程不断进行，我们希望经过分支结点划分后的样本尽可能属于同一类别，即“纯度” (purity)越来越高
经典的属性划分方法：
– 信息增益
– 增益率
– 基尼指数
评价指标-信息熵
“信息熵” 是度量样本集合纯度最常用的一种指标，假定当前样本集合D中第k类样本所占的比例为 ， 则
的信息熵定义为
信息增益
增益率
基尼指数
剪枝处理
为什么剪枝
– “剪枝” 是决策树学习算法对付“过拟合” 的主要手段
– 可通过“剪枝” 来一定程度避免因决策分支过多， 以致于把训练集自身的一些特点当做所有数据都具有的一般性质而导致的过拟合
剪枝的基本策略
– 预剪枝
– 后剪枝
剪枝依据-决策树泛化性能
– 留出法：预留一部分数据用作“验证集” 以进行性能评估
– 交叉验证法
预剪枝
决策树生成过程中， 对每个结点在划分前先进行估计， 若当前结点的划分不能带来决策树泛化性能提升， 则停止划分并将当前结点记为叶结点， 其类别标记为训练样例数最多的类别
预剪枝优缺点
优点
– 降低过拟合风险
– 显著减少训练时间和测试时间开销
缺点
– 欠拟合风险：有些分支的当前划分虽然不能提升泛化性能， 但在其基础上进行的后续划分却有可能导致性能显著提高。 预剪枝基于“贪心” 本质禁止这些分支展开， 带来了欠拟合风险
后剪枝
先从训练集生成一棵完整的决策树， 然后自底向上地对非叶结点进行考察， 若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升， 则将该子树替换为叶结点
后剪枝的优缺点
优点
– 后剪枝比预剪枝保留了更多的分支， 欠拟合风险小， 泛化性能往往优于预剪枝决策树
缺点
– 训练时间开销大：后剪枝过程是在生成完全决策树之后进行的，需要自底向上对所有非叶结点逐一考察
连续属性的处理
与离散属性不同， 若当前结点划分属性为连续属性，连续属性还可作为后代结点的划分属性
1.png)
2.png)
多变量决策树
• 分支节点根据多个属性的线性组合（一个节点由多个属性和对应权重决定）来进行判定
集成学习
指将多个性能较低的“弱” 分类器通过适当组合而形成高性能的“强” 分类器的方法
多个模型的组合性能高于单个模型的性能-》模型之间的多样性越大，组合性能越好
Boosting学习法
对多个弱学习器依次进行学习；每个弱学习器是对前一个弱学习器的强化
通过样本权重的变换来生成多样化的训练数据
Bagging学习法
对多个弱学习器进行独立学习；通过训练样本的随机采样来生成多样化的模型
随机森林(random forest)
随机森林 = bagging学习 + 决策树
随机性的目的：确保决策树组合的多样性
• 数据集的随机性(bagging学习法)
• 分支节点属性的随机性
