【数据挖掘笔记八】分类：基本概念

分类是一种重要的数据分析形式，它提取刻画重要数据类的模型，这种模型称为分类器，预测分类的（离散的、无序的）类标号。

分类和回归（数值预测）是预测问题的两种主要类型。数据分类是一个两阶段过程，包括学习阶段构建分类模型和分类阶段使用模型预测给定数据的类标号。

学习阶段由于提供了每个训练元组的类标号，也称为监督学习，不同于无监督学习，每个训练元组的类标号是未知的，并且要学习的类的个数或集合实现也可能不知情。

分类阶段首先要评估分类器的预测准确率，存在过拟合情况（即在学习期间，学习器可能包含了训练数据中的某些特定的异常，但这些异常不在一般的数据集中出现），需要使用由检验元组和与它们相关联的类标号组成的检验集，独立于训练集。分类器在给定检验集上的准确率是分类器正确分类的检验元组所占的百分比。

决策树归纳是从有类标号的训练元组中学习决策树。在决策树构造中，使用属性选择度量来选择将元组最好地划分成不同的类的属性。决策树建立时，许多分枝可能反应训练数据中的噪声或离群点，树剪枝试图识别并剪去这种分枝，以提高在未知数据上分类的准确率。ID3、C4.5和CART都采用贪心（非回溯的）方法，其中决策树以自顶向下递归的分治方式构造。

属性选择度量是决策树选择分类的准则，把给定类标记的训练元组的数据分区最好地划分成单独类的启发式方法。属性选择度量为描述给定训练元组的每个属性提供了秩评定。具有最好度量得分的属性被选为元组的分裂属性。信息增益、增益率和基尼指数是三种常见的属性选择度量。信息增益偏向多值属性，增益率调整了这种偏倚，但也倾向于产生不平衡的划分，其中一个分区比其他分区小得多。基尼指数偏向于多值属性，并且当类的数量很大时会有困难，还倾向于导致相等大小的分区和纯度。

决策树剪枝方法有先剪枝和后剪枝：

1）先剪枝方法中，通过提前停止树的构建（如通过决定在给定的结点不再分裂或划分训练元组的子集）而对树剪枝，一旦停止，结点就成为树叶，该树叶持有子集元组中最频繁的类或这些原则的概率分布。在构造树时，可以使用统计显著性、信息增益、基尼指数等度量来评估划分的优劣。

2）后剪枝方法，在完全生长的树再剪去分枝，通过删除结点的分枝并用树叶替换它而剪掉给定结点上的子树。CART使用的代价复杂度剪枝算法是后剪枝方法的一个实例。该方法把树的复杂度看做树中树叶结点的个数和树的错误率的函数。从树的底部开始，对每个内部结点N，计算N的子树的代价复杂度和该子树剪枝后N的子树的代价复杂度，比较这两个值，如果剪去结点N的子树导致较小的代价复杂度，则剪掉该子树。

训练集过大，在主存和高速缓存换进换出，计算成本大，要研究可以处理可伸缩的决策树算法，如RainForest，能适应可用的内存量，并可用于任意决策树归纳算法；如BOAT自助乐观算法使用自助法的统计学技术。

基于感知的分类是一种基于多维可视化技术的交互式方法，允许用户在构建决策树时加上关于数据的背景知识。

贝叶斯分类法是统计学分类方法，可以预测类隶属关系的概率，如一个给定的元组属于一个特定类的概率。贝叶斯分类基于贝叶斯定理。贝叶斯定义是后验概率和先验概率以及证据构成。

朴素贝叶斯分类法假定一个属性值在给定类上的影响独立于其他属性的值，即类条件独立性。

基于规则的分类器使用一组IF-THEN规则进行分类。IF是规则的前提，THEN是规则的结论。规则可以用覆盖率和准确率来评估。IF-THEN规则可从决策树中提取。使用顺序覆盖算法（sequential covering algorithm）可以直接从训练数据中提取IT-THEN规则而不必产生决策树。

评估分类器性能的度量中混淆矩阵是一种有用的工具，相关指标有准确率、错误率、误分类率、灵敏性、特效性、精度、召回率、ROC曲线。

除了基于准确率的度量外，还可以在其他方面比较分类器：

1）速度：产生和使用分类器的计算开销；

2）鲁棒性：假定数据有噪声或有缺失值时分类器做出正确预测的能力，通常，鲁棒性用噪声和缺失值渐增的一系列合成数据集评估；

3）可伸缩性：涉及给定大量数据集，有效地构造分类器的能力，通常，可伸缩性用规模渐增的一系列数据集评估；

4）可解释性：分类器或预测器提供的理解和洞察水平。

模型评估还对样本抽样采用一定技术，如交叉验证、自助法（有放回的均匀采样）、留一法。模型选择上也采用统计检验方法。

组合分类器（ensemble）是一个复合模型，由多个分类器组合而成。组合分类方法，包括装袋、提升。组合分类器比它的基分类器更准确。

1）装袋Bagging：有放回抽样选择N个训练集，给N个基分类器训练，分类结果采用投票机制确定，并行集成。

2）提升Boosting：权重赋予每个训练元组，迭代地学习k个分类器，前一个学习后更新权重再开始后一个学习。

  随机森林是Bagging的案例，Adaboost是Boosting的案例。

提高准确率除了在模型上下功夫意外，对样本也是有研究的，通过提高类不平衡数据可提高类别准确率。传统的分类算法旨在最小化分类误差。提高不平衡数据分类准确率的方法包括：过抽样、欠抽样、阈值移动、组合技术。

1）分类是一种数据分析形式，它提取描述数据类的模型。分类器或分类模型预测类别标号。数值预测建立连续值函数模型。分类和数值预测是两类主要的预测问题。

2）决策树归纳是一种自顶向下递归树归纳算法，它使用一种属性选择度量为树的每个非树叶结点选择属性测试。ID3、C4.5和CART是这个算法的例子，他们使用不同的属性选择度量。树剪枝是算法试图通过剪去反映数据中噪声的分枝，提高准确率。早起的决策树算法通常假定数据是驻留内存的，已经为可伸缩性的数归纳提出了一些可伸缩算法，如Rainforest。

3）朴素贝叶斯基于后验概率的贝叶斯定力，它假定类条件独立，即一个属性值对给定类的影响独立于其他属性的值。

4）基于规则的分类器使用IT-THEN规则进行分类。规则可以从决策树中提取，或者使用顺序覆盖算法直接由训练数据产生。

5）混淆矩阵可以用来评估分类器的质量。对于两类问题，它显示真正例、真负例、假正例、假负例。评估分类器预测能力的度量包括准确率、灵敏度（召回率）、特效性、精度、F等。当感兴趣的主类占少数时，过分依赖准确率度量可能受骗。

6）分类器的构造和评估需要把标记的数据集划分为训练集和验证集。保持、随机抽样、交叉验证和自助法都用于这种划分的典型方法。

7）显著性检验和ROC曲线对于模型选择是有用的。显著性检验可以用来评估两个分类器准确率的差别是否出于偶然。ROC曲线绘制一个或多个分类器的真正例率（或灵敏性）与假正例率（或1-specificity）。

8）组合方法可以通过学习和组合一系列个体（基）分类器模型提高总体准确率。装袋、提升和随机森林是流行的组合方法。

9）当感兴趣的主类只有少量元组代表时就会出现类不平衡问题。处理这一问题的策略包括过抽样、欠抽样、阈值移动和组合技术。