数挖——基本分类

构造决策树有多种算法：
1、Hunt算法 (决策树归纳算法框架)
2、CART
3、ID3, C4.5 (重点)
4、SLIQ,SPRINT

Hunt算法：

设D_t是与当前结点t相关联的记录集，处理t的递归过程：

• 如果D_t 中所有记录都属于同一个类y_t，则t是叶结点，用y_t 标记。
• 如果D_t是一个空集，则t是叶结点，用缺省类y_d标记。
• 如果D_t中包含属于多个类的记录，则选择一个属性测试条件，将数据集划分成较小的子集:
  (1) 对于测试条件的每个输出，创建一个子女结点；
  (2) 根据测试结果将D_t中的记录分配到子女结点中。
  (3) 对每个子女结点，递归调用该算法

重点难点：

如何划分训练集？

• 如何指定属性测试条件？
  依赖于属性类型
   标称属性
   序数属性
   数值属性
  依赖于测试的输出个数
   二路划分
   多路划分
• 如何确定最佳划分？
  引入结点不纯性的度量
   Gini指标（Gini Index）
   熵（Entropy）
   误分率（Misclassification error）

何时停止划分？

• 当所有记录从属同一个类时停止扩展结点
  Hunt算法引入的条件
• 当所有记录中对应属性的取值都相同时停止扩展
  再划分不能改变当前训练集的类分布
• 早期停止
  防止过分拟合(在后面阐述“过分拟合问题”时再讨论)

属性测试条件

划分	基于标称属性的划分	基于序数属性的划分	基于数值属性的划分
多路划分	输出个数取决于该属性不同属性值的个数	输出个数取决于该属性不同属性值的个数(不违背序数属性值的有序性)	离散化成序数属性。静态 – 开始建树时一次性离散化；动态 – 扩展当前结点时再离散化
二路划分	将属性值划分成两个子集	将属性值划分成两个子集	(A < v) or (A > v)，考虑所有可能的划分点v，寻找最佳的划分点

基于Gini指标的划分

不纯性度量: Gini

(注: p( j | t) 是类j在结点t的出现概率)

Gini指标的取值范围:
最大1 - 1/n_c，出现的情况是t对应的记录集在所有类中均匀分布（n_c表示类的个数）
最小0，出现的情况是t对应的所有记录都属于同一个类

基于Gini指标的划分在树归纳算法CART, SLIQ, SPRINT中使用，当一个结点p输出k个子女时，该划分的总Gini指标计算为：

其中，n_i = 子女结点i对应的记录个数，n = 结点p对应的记录个数

基于熵的划分标准

结点t的熵定义为:

(注意: p( j | t) 是类j在结点t的出现概率)

熵的取值范围:
最大log₂n_c，出现的情况是t对应的记录集在所有类中均匀分布
最小0，出现的情况是t对应的所有记录都属于同一个类

信息增益——ID3算法引入:

结点p输出k个子女；n_i是第i个子女对应的记录个数

由于划分导致熵减少；选择熵减少量最大的划分点，即信息增益最大的划分点
与Gini指标的共同缺点: 倾向于产生很多分区的划分点，因为每个分区更纯

增益率——C4.5算法引入:

使用划分信息(SplitInfo)调整信息增益，惩罚更高的划分信息（即更多的小分区）

基于误分率的划分标准

结点t的误分率定义为:

(注意: p( j | t) 是类j在结点t的出现概率，max指所有类中最大的概率值)

误分率的取值范围
最大1 - 1/n_c，出现的情况是t对应的记录集在所有类中均匀分布
最小0，出现的情况是t对应的所有记录都属于同一个类

对于二类问题: 三种不纯性度量的比较

分类的两大实际问题

1、过分拟合（Overfitting）
2、遗漏值（Missing Values）

过分拟合（Overfitting）

• 导致过分拟合的原因：(1) 噪声；(2) 缺乏样本
• 过分拟合源于过于复杂的决策树，复杂部分可以看作是对噪声或小类样本的拟合，训练误差不再是决策树预测准确率的合适估计，不能再用于引导决策树的增长

估计误差的新方法：泛化误差（generalization error）

• 再代入误差: ∑e(t)/N，其中t是叶子结点，e(t)是叶子t的错误样本数，N是样本总数
• 泛化误差：模型在未知记录上的期望误差，即 ∑ e’(t)/N
  泛化误差估计的方法:
  1、乐观估计方法：e’(t) = e(t)
  2、悲观估计方法：e’(t) = e(t)+0.5 （0.5是每个叶子的惩罚项）
  全部错误: e’(T) = e(T) + n*0.5 (n是决策树的叶子数)
  例子：对于一个具有30个叶子的决策树，若对1000个训练样本有10个错误，则
  训练误差 = 10/1000 = 1%
  泛化误差 = (10 + 30*0.5)/1000 = 2.5%
• 使用确认集估计泛化误差 （一般2/3的数据集用来训练，1/3做确认集）

悲观误差估计：Occam剃刀原则

• Occam剃刀(Occam’s razor)原则，又名节俭原则，即给定两个具有相同训练误差的模型，较简单的模型更可取
• 原因：复杂模型中的附加成分很可能是对错误数据的拟合
• 当两个模型的训练误差不同时，如何在训练误差和简单性两个方面作权衡？
  1、使用悲观误差估计
  2、使用最小描述长度原则

最小描述长度(MDL)原则

最小描述长度( MDL) 原理是 Rissane 在研究通用编码时提出的。其基本原理是对于一组给定的实例数据 D，如果要对其进行保存，为了节省存储空间， 一般采用某种模型对其进行编码压缩（对误分类记录），然后再保存压缩后的数据。同时， 为了以后正确恢复这些实例数据，将所用的模型也保存起来。所以需要保存的数据长度( 比特数) 等于这些实例数据进行编码压缩后的长度加上保存模型所需的数据长度，将该数据长度称为总描述长度。最小描述长度( MDL) 原理就是要求选择总描述长度最小的模型。
如果将贝叶斯网络作为对实例数据进行压缩编码的模型， MDL原理就可以用于贝叶斯网络的学习。该度量被视为网络结构的描述长度和在给定结构下样本数据集的描述长度之和。一方面，用于描述网络结构的编码位随模型复杂度的增加而增加 ； 另一方面， 对数据集描述的编码位随模型复杂度的增加而下降。因此，贝叶斯网络的 MDL总是力求在模型精度和模型复杂度之间找到平衡。构建贝叶斯网络首先定义一个评分函数， 该评分函数描述了每个可能结构对观察到的数据拟合， 其目的就是发现评分最大的结构，这个过程连续进行到新模型的评分分数不再比老模型的高为止。
公式：
Cost(Model,Data) = Cost(Data|Model) + Cost(Model)
其中：Cost(Data|Model)是对误分类记录编码所需的比特数；
Cost(Model)是对模型编码所需的比特数

如何处理过分拟合

• 前剪枝 (提前终止规则)
  在产生完全的决策树之前停止树增长
  针对当前结点的典型停止条件:
   当所有实例属于同一类时停止
   当所有实例对应属性的取值都相同时停止
  更加严格的条件，比如:
   当实例的个数小于某个用户指定的阈值时停止
   当实例的类分布独立于余下的属性时停止 (比如使用 χ2 检验来验证独立性)
   当扩展结点不能改善不纯性（如Gini指标）时停止
• 后剪枝
  初始决策树按照最大规模生成，再自底向上的方式修剪决策树如果修剪后泛化误差得到改善，则以叶子结点替换原来的子树
   叶子结点的类标是原来子树对应实例的多数类
   可以使用悲观泛化误差作为后剪枝的根据

遗漏值

遗漏值在三个方面影响决策树的构造:
1、影响不纯性度量的计算
2、影响带遗漏值的训练记录分配给子女结点
3、影响带遗漏值的测试记录的归类

产生原因：数据难于获取、历史数据遗失
基于决策树的解决办法
1、不纯性度量的计算（完整记录数占全部记录数的比例作为权重）
2、训练记录的分配（将缺失记录按完整记录的分类比例划分进不同类别）
3、测试记录的归类（根据已知条件算出属于不同类别的可能性）

模型评估

性能评估的度量

考虑的度量：着重于模型的预测能力，而不是模型构造或应用的效率(efficiency)和可伸缩性(scalability)等等

混淆矩阵（Confusion Matrix）

a: TP (true positive)；b: FN (false negative)；c: FP (false positive)；d: TN (true negative)

最常用的度量——准确率（Accuracy）

准确率的局限性
考虑一个二类问题
类0的样本数 = 9990；类1的样本数 = 10
若模型预测所有记录为类0，则准确率就是9990/10000 = 99.9 %
该模型不能检测任何类1的样本，准确率是误导的
因此，准确率可能不适合分析不平衡的数据集

代价矩阵和分类代价

C( i | j ): 将类 j 的样本错误划分为类 i 的代价
分类代价：Cost = TP*C(Yes|Yes) + FN*C(No|Yes) + FP*C(Yes|No) + TN*C(No|No)

分类代价的计算

Accuracy = 80% Cost = 3910；Accuracy = 90% Cost = 4255

其他常用度量

• 查准率/精度（Precision）：预测的正例中有多少是预测对的
• 查全率/召回率（Recall）：实际的正例中有多少是预测对的
• F度量（F-measure）：查准率和查全率的调和均值
  min(p,r) ≤ F ≤ max(p,r)
  F ≤ (p+r)/2
  例子：p=10%, r=50%, 则F=20.10.5/(0.1+0.5)=16.67%

如何得到可靠的估计?

1、保持方法（holdout）
2、随机二次抽样（random subsampling）
3、交叉验证（cross validation）
4、自助法/自举法（bootstrapping）

保持方法

• 输入数据中
  保留2/3的记录作为训练集
  余下1/3的记录作为测试集
  在测试集上评估模型的性能
• 测试集(test set) vs 确认集(validation set)
  确认集是训练集的一个子集，在模型构造过程中使用，用于估计泛化误差以作为剪枝的根据
  测试集与训练集不相交，在模型评估过程中使用

随机二次抽样

多次重复保持方法

k 次重复
acc_i 是第i次执行保持方法得到的准确率
缺点：没有控制每个记录用于训练和检验的次数

交叉验证(k折（k-fold）交叉验证)

将数据集划分成k个不相交的子集，根据既有实验结果，k一般取10较好
将k-1个分区的记录用作训练，将余下1个分区的记录用作测试，重复k次

特点：每个记录用于训练的次数相同用于测试恰好一次
留一（leave-one-out）法
k折交叉验证的一个特例，k=N，N是数据集的大小

自助法/自举法

采用有放回的抽样产生大小为N的样本集，N是数据集大小
每个记录被抽中的概率是1-(1-1/N)^N，当N充分大时，该概率逼近1-e^-1=0.632
抽中的记录构成训练集，没抽中的记录构成测试集
抽样过程重复b次，每次在测试集上的准确率是

总准确率

acc_s是由包含所有样本的训练集计算的准确率

Rapidminer中简化成