ROC与AUC
ROC全称是：受试者工作特征。
很多模型是为测试样本产生一个实值或概率预测，然后将这个预测值与一个分类阈值进行比较。
若大于阈值则分为正类。否则为反类。
AUC：ROC曲线下的面积。
非均等代价：为权衡不同类型错误所造成的不同损失。
在非均等代价下，我们所希望的不再是简单的最小化错误次数，而是希望最小化“总体代价”
比较检验
（本节默认以错误率为性能度量）
决策树
决策树是基于树结构来进行决策的。
一般的，一颗决策树包含一个根节点、若干个内部节点和若干个叶节点。其中，叶节点对应于决策结果。其他每个节点则对应于一个属性测试；每个节点包含的样本集合根据属性测试的结果被划分到子节点中；根节点包含样本全集。从根节点到每个叶节点的路径对应了一个判定测试序列。
决策树的目的就是产生一颗泛化能力强的决策树，即处理未见示例能力强的决策树。其基本流程遵循简单且直观的"分而治之"策略。
决策树的生成是一种递归过程，在决策树基本算法中，有三种情形会导致递归返回：
（1）当前节点包含的样本全属于同一个类别，无需划分
（2）当前的属性集合为空，或是所有样本在所有属性上取值相同。无需划分。
（3）当前节点包含的样本集合为空，不能划分。
其中，在（2）情形下，我们把当前节点标记为叶节点，并将其类别设定为该节点所包含样本最多的类别。（利用当前节点的后验分布）
在（3）情形下，同样把当前节点设为叶节点，但将其类别设定为其父节点所包含样本最多的类别。（把父节点的样本分布作为当前节点的先验分布）
划分选择
一般而言，随着划分过程不断进行，我们希望决策树的分支节点所包含的样本尽可能属于同一个类别，即节点的“纯度”越来越高。
信息增益
“信息熵”是度量样本集合纯度最常用的一种指标。假定当前样本集合D中第k类样本所占的比例为
（k=1，2，......|y|）则D的信息熵定义为：
信息增益越大，意味着使用该属性来进行划分所获得的“纯度提升”越大。假定a有V个可能的取值（
，
........
），若使用a来对样本集合D进行划分，则会产生V个分支节点，其中第v个分支节点包含了D中所有在属性a上取值为的样本，记为
.我们根据上式可计算出信息熵，在考虑到不同的分支节点所包含的样本数不同，给分支点赋予权重||/|D|，即样本数越多的分支节点的影响越大。于是我们可计算出用属性a对样本集D进行划分所获得的“信息增益”
著名的ID3决策树学习算法就是以信息增益为准则来选择划分属性。
决策树划分步骤：
1.算出根节点的信息熵
2.然后计算每个属性的信息增益，找出信息增益大的属性，以它为第一个划分依据。
3.然后对第一划分依据的每个分支节点，再次算出其他每个属性在此划分依据下的信息增益，再次找出信息增益大的属性进行划分。
4.以此类推，直至属性划分完毕。
增益率
实际上，信息增益准则对可能取值数目较多的属性有所偏好，为减少这种偏好所带来的不利影响。著名的C4.5算法提出了“增益率”来选择最优划分。
其中，
注意：增益率对可取值数目较少的属性也有所偏好，C4.5算法是一个启发式，并不直接选择增益率最大的候选划分为属性，而是：先从候选属性中找出信息增益高于平均水平，再从中选择增益率高的。
基尼系数
CART算法使用“基尼系数”来选择划分属性。
基尼值：
Gain(D)反映了从数据集D中随机抽取两个样本，其类别标记不一致的概率。Gain(D)越小，则数据集D的纯度越高。
属性a的基尼指数定义为：
我们在候选属性集合A中，选择那个使得划分后基尼指数最小的属性作为最优分属性。
剪枝处理
剪枝是决策树学习算法对付“过拟合”的主要手段。
决策树剪枝的基本策略有“预剪枝”和“后剪枝”
预剪枝：指在划分前先进行估计，若当前节点划分不能带来决策树泛化性能提升，则停止划分并将当前节点标记为叶节点。
后剪枝：先从训练集中生成一颗完整的决策树，然后自底向上地对非叶节点进行考察，若将该节点对应的子树替换为叶节点能带来决策树泛化性能的提升，则将该子树替换为叶节点。
用性能评估方法来判断决策树繁华能力的提升。
预剪枝VS后剪枝
预剪枝：使得决策树的很多分支都没有“展开”，还显著减少了决策树的训练的时间开销和测试时间开销。但另一方面有些分支的当前划分虽不能提升泛化性能、甚至可能导致泛化性能暂时下降，但在其基础上进行的后续划分却又可能导致性能显著提高；预剪枝基于“贪心”本质禁止这些分支展开，给预剪枝决策树带来欠拟合的风险。
后剪枝：后剪枝决策树通常比预剪枝决策树保留了更多的分支。一般情形下，后剪枝决策树的欠拟合风险很小，泛化能力往往优于预剪枝决策树。但相较于预剪枝，其训练时间开销要大得多。
连续与缺失值
连续值处理
因为连续取值的可取值数目不在有限，因此不能直接根据连续属性的可取值来对结点进行划分。这时，连续属性离散化技术可派上用场。最简单的就是采用二分法（C4.5决策树算法中采用的机制）
做法：
我们把连续相邻的取值的中位数作为候选划分点。
像离散属性值一样来考察这些划分点，选取最优的划分点进行样本集合的划分。
注意：与离散属性不同，若当前节点划分属性为连续属性，该属性还可作为其后代结点的划分属性。
缺失值处理
给定训练集D和属性a,令
表示D在属性a上没有缺失值的样本子集。假定属性a有V个可取值{，........}，令
表示中在属性a上取值为的样本子集，
表示中属于第K类的样本子集，则显然有
，
。
为权重。
对属性a，
表示无缺失值样本所占的比例。
表示无缺失值样本中第k类所占的比例，
表示无缺失值样本在属性a上取值的样本所占的比例。
信息增益公式为：
其中，
做法：
若样本x在划分属性a上的取值已知，则将x划入与其取值对应的子节点，且样本权值在子节点中保持为。若样本x在划分属性a上的取值未知，则将x同时划入所有子节点，且样本x在与属性值对应的子节点中调整为. 。直观的看。这就是让同一个样本以不同的概率划入到不同的子节点中。
多变量决策树
我们把每个属性视为坐标空间中的一个坐标轴，则d个属性描述的样本就对应可d维空间中的一个数据点。对样本分类则意味着在这个坐标空间中寻找不同类样本之间的分类边界。如果分类边界每一段都是与坐标轴平行的，这样的使得学习结果有了较好的可解释性。但在实际中，决策树更多是很复杂的，这时我们就采用：斜划分。多变量决策树就是实现这个的决策树。在多变量决策树中，不再是为每一个非叶节点寻找一个最优划分而是试图建立一个合适的线性分类器。