[TOC]

---

分类基本概念、决策树与模型评估

基本概念

分类：确定对象属于哪个预定义的目标类（目标类的总体是已知的）。分类问题中，类标号必须是离散属性，这也是区分分类和回归（regression，回归的目标属性是连续的）的关键特征。

分类，classification，通过学习训练样本得到一个目标函数f（target function），把属性集x映射到预先定义的类标号y。

分类模型（classification model）有两个目的：

• 描述性建模，作为区分不同类中的对象的解释性工具。
• 预测性建模，用以预测未知记录的类标号。

分类技术特点：适合描述或预测二元或标称类型的数据集，对序数分类不太有效，因为分类技术不考虑隐含在目标类中的序号关系。（即分类器只负责区分元素们属于哪一类，对于某一类中的元素之间的序关系不做表达）

分类方法：决策树分类法、基于规则的分类法、神经网络、支持向量机和朴素贝叶斯分类法。殊途同归，都是通过学习算法（learning algorithm）从训练数据集提炼一种模型拟合输入数据的类标号和属性之间的联系。

泛化：在模型的评估中，泛化是一个重要的概念，它表达通过已知数据建立的模型在应用到未知数据上的时候的有效性。这个泛可以理解为广泛、扩大，从特定的已有的数据一般化到所有的未知的数据。

分类过程：$$训练集（training set)\rightarrow学习模型\rightarrow模型\rightarrow应用模型\rightarrow检验集(test set)$$

模型评估：通过正确和错误的记录数量评估，列一个混淆矩阵（confusion matrix）可清晰算得相应的新能度量（performance metric）。

• 准确率，accuracy：$$准确率=\frac{正确预测数}{预测总数}=\frac{f_{11}+f_{00}}{f_{11}+f_{00}+f_{10}+f_{01}}$$
• 错误率，error rate：$$错误率=\frac{错误预测数}{预测总数}=\frac{f_{10}+f_{01}}{f_{11}+f_{00}+f_{10}+f_{01}}$$
• $$f_{10}$$表示原本属于类1，被分类到类0的记录数。

---

决策树

1. 决策树（decision tree）原理

   由结点和有向边组成的层次的结构，包含根结点（root node）、内部结点（internal node，只有一条入边）、叶节点（leaf node）或终结点（terminal node）。页结点具有类标号，非页结点包含属性测试条件，即从root node开始通过属性测试条件依次分流到树的不同叶子上，最终归类到不同的类。

2. 建立决策树

   寻找最佳决策树由于搜索空间是指数增长所以是不可行的，但可以通过合理的算法找到次优决策树，通常采用贪心策略，采取一系列局部最优策略来构造决策树。

   Hunt算法：递归将训练集划分分较纯的子集。若集合全都属于同一个类，则该结点为叶节点，若结点上存在多个类的记录，则择优一个属性测试条件进行划分。划分中有以下情况：

   • 某结点划分的子节点为空，即不存在与该节点相关联的记录，没有一个训练记录包含与这样的结点相关联的属性值组合。即子划分情况记录未出现，则该结点升级为叶结点，类标号取其父节点中的多数类。
   • 某结点中个记录属性相同，但类标号出现不同，取多者，认为少数为异常情况忽略。
   • 冗余属性：强相关的两个属性，可以舍弃一个，选用一个作用属性测试进行划分。但如果不相关属性过多会导致决策树太庞大，这个时候需要用特征选择技术删除部分不相关属性。

   划分中需要考虑以下两个问题：

   • 如何分裂记录：选择最优的分裂属性，根据不同属性制定不同的属性测试条件。
   • 如何停止分裂：记录都是一个类型，或记录都具有相同的属性集。还要考虑停止条件是否太精细导致过拟合。

3. 属性测试条件

   • 二元属性：正好二茬划分。
   • 标称属性：多个平等的离散属性值。可以直接多路划分，也可以划分成两个部分做二路划分（对于k个属性有$$(2^{k-1}-1)$$种划分情况）。
   • 序数属性：属性值之间存在序列关系，划分的时候不能打破这种有序关系。如属性值为：很大、大、中、小、很小。可以划分成{很大，大}{中}{小，很小}三路划分，也可以两路，但是不能打破这个顺序。
   • 连续属性：对于连续属性，采用区间划分，通常需要选择最佳的划分点，即区间边界点。若是多路区间划分，多路区间的离散表示值必须是有序的，不能打乱顺序。如将[0,10]的连续区间映射到三个划分区间[0,3]、[3 , 6]、[ 6 , 10]，用离散值0,1,2有序表示。

4. 最佳属性划分的度量

   测试条件中属性的划分有多种方法，那么怎么划分才是最合理的性能最优的呢？用划分前后的类分布来衡量。划分后的子集纯度越高越好。即最佳划分的度量是选择划分子集最高纯度，即不纯度越低越低。

   注意：纯度，和不纯度，给出的度量公式都是不纯度的，要的是高纯度。

   不纯性度量有：(注$$p(i|t)$$表示结点记录集t中属于类i的比例或概率，c表示类的个数)

   熵，$Entropy(t)=-\sum_{i=0}^{c-1}p(i|t)log_2p(i|t)$

   基尼系数，$Gini(t)=1-\sum_{i=0}^{{c-1}[p(i|t)]}2$

   分类错误率，$classification error(t)=1-max_i[p(i|t)]$

   这三个度量值越高，说明不纯度越高，说明纯度越低，划分效果越差，应该改进划分方案。

   确定测试条件：需要比较父节点和子节点的不纯度，它们差值越大越好，父节点纯度一定，则子节点的纯度越小越好。定义增益来度量划分效果：

   $$\Delta = I(parent)-\sum_{j=1}^{k}\frac{N(v_j)}{N}I(v_j)$$

   上式中$I$表示不纯性度量值，N表示记录个数。当不纯性度量选用熵的时候，结果被称为信息增益，information gain，$\Delta_{info}$。

   • 二元属性划分：计算划分后的基尼指数选小的即可。
   • 标称属性划分：同上，值得注意的是，划分的路数越多不纯性越小，纯度越高。
   • 连续属性划分：连续属性的区间边界需要拿每一个取值去试求Gini值，取最小的，这种开销太大，计算复杂度为$O(N^2)$，可采用排序降低复杂度。

5. 决策树归纳算法

   通过输入的训练集E和属性集F，递归地选择最优的属性进行划分，扩展树的结点，直到结束条件。

   建立决策树之后，后续通常会进行树剪枝（tree-pruning）

6. 决策树归纳特点

   • 非参数建模方法，非先验假设方法。
   • 寻找最佳决策树是NP完全问题（？？？）
   • 当叶结点的记录太少时不能做出具有统计意义的判决。称为数据碎片，data fragmentation。
   • 多个属性共同作为一个判决条件进行划分，得到决策边界（decision boundary）不规整的决策树，如斜决策树（oblique decision tree）

---

模型过拟合问题

分类模型误差：

• 训练误差，training error = 再带入误差，resubstitution error = 表现误差，apparent error，表示训练记录上错误分类的样本比例
• 泛化误差，generalization error，模型应用到未知记录做预测时的期望误差。

模型拟合不足（model underfitting），训练和泛化误差都很大，原因是模型尚未学到数据的真实结构。

模型过分拟合（model overfitting），树的规模持续变大，训练误差持续降低，但泛化误差开始增大。

• 噪声导致的过分拟合
• 缺乏代表性样本导致的过分拟合，通常是样本数太小。

泛化误差估计

• 使用再带入估计：假设训练集就已经很具有代表性，能代表整体数据，故直接选用训练误差作为泛化误差的估计。然而这种方法很差。

• 结合模型复杂度：原理是模型复杂度越大，出现过分拟合的几率越高，已知过分拟合时泛化误差是增大的，故可以结合模型的复杂度，对泛化误差做估计。

  奥卡姆剃刀（Occam‘s razor）：具有相同泛化误差的两个模型，复杂度小的更可取。

• 估计统计上界：因泛化误差倾向于比训练误差大，故可以用训练无擦的统计修正来估计。

• 使用确认集：把训练集分为两个子集，一个用作训练，一个用作确认集，用以估计泛化误差。

处理（避免）决策树归纳中的过分拟合

• 先剪枝，也叫提前终止规则。生成树的过程中通过设置某些条件提前终止树的扩张。
• 后剪枝，针对已经生成的决策树。1）子树替换，subtree replacement：用新的叶结点替换子树。2）子树提升，subtree raising：采用子树中常使用的分支代替子树

分类器性能评估方法

本章描述对某一个分类器的性能的评估方法。

• 保持方法，Holdout：原数据集分为两个不相交子集，一个训练集用于归纳分类模型，一个检验集用以评估模型性能。
• 随机二次抽样：用多次重复的保持方法对分类器性能进行评估。
• 交叉验证，cross-validation：将数据集分为K个子集，第i个集合用作检验集，剩下k-1个用作训练集，交叉k次。当K=2时称为二折交叉验证。当K=N，即子集数量等于记录数量，每个子集只有一个记录时，称为留一法（leave-one-out）。
• 自助法，bootstrap：训练集记录在训练时有放回得使用。

分类器比较

本章描述两个或多个分类器之间的对比方法，针对不同分类方法在不同规模的数据集上的准确性比较。即得到不同分类方法在忽略数据量下的性能对比。

• 评估准确度的置信区间
• 比较两个模型的性能
• 比较两种分类法的性能

---

任务

任务一：决策树-最佳属性划分度量-连续属性划分算法，实现二分划分点选择算法，考虑连续属性的多路划分的划分点选择算法【深入研究切入点：C4.5算法】。

任务二：决策树-决策树归纳算法

任务三：尝试树剪枝