机器学习笔记（四）
一、决策树的基本概念
决策树学习的目的是为了产生一棵泛化能力强，即处理未见示例能力强的决策树。
第3行解释，当前结点包含的样本全部属于同一类别。
第6行解释，当前属性集为空，或所有样本在所有属性上取值相同。
第12行解释，当前结点包含的样本集合为空。
二、划分选择
决策树学习的关键在于如何选择最优划分属性。一般而言，随着划分过程不断进行，我们希望决策树的分支结点所包含的样本尽可能属于同一类别，即结点的“纯度”(purity)越来越高
经典的属性划分方法：
1.信息增益
”信息熵”是度量样本集合纯度最常用的一种指标，假定当前样本集合中第类样本所占的比例为，则D的信
息熵定义为.Ent(D)的值越小，D的纯度越高。
离散属性a有v个可能的取值，用a来进行划分，则会产生v个分支结点，其中第v个分支结点包含了D中所有在属性上a取值为
的样本，记为
。则可计算出用属性对样本集进行划分所获得的“信息增益”：
为分支结点权重，样本数越多的分支结点的影响越大。
一般而言，信息增益越大，则意味着使用属性来进行划分所获得的“纯度提升”越大。而且信息增益对可取值数目较多的属性有所偏好
2.信息增益率
，其中
，称为属性的“固有值” [Quinlan, 1993] ，属性a的可能取值数目越多（即V越大），则IV（a）的值通常就越大。但是增益率准则对可取值数目较少的属性有所偏好。
3.基尼指数
数据集的纯度可用“基尼值”来度量，Gini（D）越小，数据集的纯度越高。
三、剪枝处理
为什么剪枝
“剪枝”是决策树学习算法对付“过拟合”的主要手段，可通过“剪枝”来一定程度避免因决策分支过多，以致于把训练集自身的一些特点当做所有数据都具有的一般性质而导致的过拟合。
剪枝的基本策略
1.预剪枝
2.后剪枝
剪枝处理-预剪枝
1.决策树生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点记为叶结点，其类别标记为训练样例数最多的类别
2.针对上述数据集，基于信息增益准则，选取属性“脐部”划分训练集。分别计算划分前（即直接将该结点作为叶结点）及划分后的验证集精度，判断是否需要划分。若划分后能提高验证集精度，则划分，对划分后的属性，执行同样判断；否则，不划分
预剪枝的优缺点
.优点
.降低过拟合风险
.显著减少训练时间和测试时间开销
.缺点
.欠拟合风险：有些分支的当前划分虽然不能提升泛化性能，但在其基础上进行的后续划分却有可能导致性能显著提高。预剪枝基于“贪心”本质禁止这些分支展开，带来了欠拟合风险
剪枝处理-后剪枝
先从训练集生成一棵完整的决策树，然后自底向上地对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升，则将该子树替换为叶结点。
后剪枝的优缺点
优点，后剪枝比预剪枝保留了更多的分支，欠拟合风险小，泛化性能往往优于预剪枝决策树。
缺点，训练时间开销大：后剪枝过程是在生成完全决策树之后进行的，需要自底向上对所有非叶结点逐一考察。
四、连续与缺失值– 连续值处理
连续属性离散化(二分法)
五、多变量决策树
单变量：决策树分类边界:轴平行
多变量决策树：1.非叶节点不再是仅对某个属性,而是对属性的线性组合。
2.每个非叶结点是一个形如的线性分类器，其中w是属性a的权值， w和t可在该结点所含的样本集和属性集上学得