数据挖掘导论学习笔记（三）
第四章 分类：基本概念，决策树与评估模型
在本节中概述了一些基本概念。首先介绍基本概念。（1）首先介绍基本概念。
注释
（2）分类
定义：通过学习获得了一个目标函数f，在这种情况下会将每个属性集x对应于一个预先设定好的类标号y。
分类模型的作用包括两类：
第一类是描述性建模，在这种情况下它被用作分析手段来识别不同类别之间的差异；
第二类是预测性建模，在这种情况下它被用作一种方法来预测数据点所属的具体类别。
典型的分类问题解决方案基于以下要素：首先需要一个训练集（training set），它由具有已知类别标签的数据样本组成；其次需要利用训练集来构建分类模型（classifier）；最后将该模型应用于测试集（test set），测试集包含待分类的数据样本，并根据模型预测结果判断其所属类别
分类模型的表现基于对正确与错误预测的数量进行检验来评估；这些数量被存储在被称为混淆矩阵 的数据结构中。被分类器正确识别的总样本数等于f_{true\:positive} + false\:negative的数量；误分样本数量等于f_{false\:positive} + true\:negative的数量。性能度量方面包括准确率与误分率的具体计算方法：准确率为(true\:positive + true\:negative)除以(true\:positive + false\:negative + false\:positive + true\:negative)；而误分为(false\:positive + false\:negative)除以同样的分母。
决策树基本知识：
基于节点和有向边构建而成的层级式架构。
该结构包含以下几种类型的节点：
（1）根节点：无入边且具有零个或多个出边。
（2）内部节点：每条内部节点均拥有一个入边以及两个或多个出边。
（3）终结点（包括根节点）：每条终结点仅有一个入边且没有出边。
非终结点（包括内部结点和根节点）通过属性测试条件区分不同特性的数据记录。
基于Hunt算法构建决策树的过程如下所述：首先通过对训练数据集进行逐步划分形成较为纯净的小集合随后按照一定策略构建决策树结构具体步骤如下所述
当Di中的所有实例都被分类到同一类别yt时则该节点成为叶子节点并标记为yt
若Di包含多个类别则需选择合适的属性及其分割阈值并将其分割成较小的数据子集对于每一个分割结果创建相应的子节点并根据实际分类将原始数据分配到其子节点中之后对每个子节点重复上述过程
表示属性测试条件的方式：
在决策树模型中对不同类型的变量都需要定义相应的特征提取规则以生成对应的分类边界。
其中：
（1）对于二元变量而言，在决策树中生成的测试条件会导出两种可能的结果。
（2）而标称型变量具有多个不同的取值，在决策树中可以通过两种不同的方式来构建其对应的划分标准。
在多路划分的情况下（即输出结果数目大于等于2），其输出数取决于该变量不同取值的个数。
以CART等算法为例，在构建决策树时通常只能进行二元分割。
而对于序数型变量而言，则支持同时实现二元分割与多路分割策略。
最后，
（3）对于连续型变量而言，
在构建决策树时可以选择基于比较运算或区间范围查询的方式来处理其对应的特征提取问题。
选择最佳划分的度量：
其中c代表类的数量，在计算熵的过程中有定义：0log₂(0)=0
决策树归纳具有以下显著特点：
（1）它属于一种基于分类的非参数方法，在无需预先设定先验分布假设的情况下进行分析与建模。
（2）确定最优结构的过程属于NP完全问题，在实际应用中常需依赖启发式搜索策略来缩小假设空间范围。
（3）该方法具有较低计算成本，在训练样本数量极大时仍能高效构建出有效的预测模型。
（4）其优势在于在小型决策树情况下尤其直观易懂，并且能够提供清晰的数据驱动决策依据。
（5）在机器学习领域中通常用于表示离散值函数这一特定任务类型中表现突出。
（6）该算法对于噪声数据表现出很强的鲁棒性，在适当避免过拟合后能够有效提升预测准确性。
（7）冗余属性的存在并不会对模型准确率产生负面影响，并且在合理设计下还能进一步提升分类性能。
（8）多数算法采用自顶向下的递归划分策略会导致训练集中实例数量逐步减少直至达到预设终止条件。
（9）由于子树可能在构建过程中重复出现的现象较为常见，在实际应用中可能导致决策过程过于复杂难以解释。
一些基本概念如下：
分类边界：两类样本之间分界线。
斜率决策树：支持多维度特征进行划分。
构建归纳模型：提供了一种新的数据分类方法。
模型的过分拟合：
分类模型的误差主要分为两种类型：
其中一种类型被称为训练错误或表现错误，在实际应用中容易出现的问题。
另一种类型被称为泛化错误，在测试数据集上的平均预测偏差即为泛化风险。
当决策树较简单时，在训练与检验阶段的错误率均较高，并被称为模型欠拟合的情况。
当树变得过于复杂时，尽管在训练集上的误差仍在下降，但测试集的误差却开始上升；这种情况被定义为过度拟合的表现。
在理想情况下（即所谓的完美拟合），随着节点数量的持续增加会使训练误差降至零；然而，在测试阶段仍会存在显著地存在较大差异的问题。
在泛化误差估计方面：
1 采用再代入估算法
该方法基于假设训练数据集良好地代表了数据整体，并将训练错误率（即重归错误率）作为依据来积极预测泛化性能。好的结果通常来自于良好的模型选择和充分的数据准备。
然而，在这种情况下, 直接以训练集上的错误率作为测试集错误率的近似是一种糟糕的近似
随着模型复杂度的增加，在过拟合方面出现的风险也随之上升。根据奥卡姆剃刀原则，在泛化能力相等的情况下，默认选择较为简洁且简单的模型作为最优解更为合理。在悲观误差评估框架下，第一种方法通过整合训练集上的损失函数值与正则化项来综合推导出总体性能指标。其计算出的结果实质上等同于对整个系统的悲观风险估计。
最小描述长度原则：另一种思路将模型复杂度与信息论中的概念相结合的方法被称为最小描述长度原则。
- 估计统计上界
不仅可以用统计调整的方法来估算泛化错误。
然而由于泛化错误通常大于其对应的 training error 因此在实际应用中通常会计算出该 training error 的上界。
这种上界计算主要基于决策树某个叶子节点所对应的 training 样本数量。 - 使用确定集
与传统的基于 training set 的方法不同 我们将原始的数据拆分为两部分较小的数据集。
其中一部分用于模型构建 另一份则用于评估模型性能（称为验证集或测试集）。
典型的实现策略是将数据按2:1的比例分配给 model building 和 performance evaluation 分别占用了三分之二和三分之一的比例。
处理过拟合问题通常通过剪枝技术来解决
评估分类器性能：
在保持方法中，
将被标记的数据分为两部分互不重叠的集合，
分别作为训练集和验证集。
在这一过程中使用的数据量决定了模型的质量，
通过交叉验证的方式优化参数设置。
选择合适的正则化参数有助于提升模型的泛化能力。
这种方法的优点在于能够有效避免过拟合的风险，
然而其计算资源的需求相对较高。
然而该方法也存在一些不足之处：
对于小规模的数据集来说，
这种做法可能会导致欠拟合现象的发生，
无法充分反映数据的真实特征。
此外，
这种简单的划分方式可能导致实验结果不够稳定，
因为不同的划分标准可能会带来较大的模型表现差异
2 随机二次抽样：可以重复保持方法来改进对分类器性能的估计。
3 交叉验证
（1）二分法交叉验证：假设将数据集划分为大小相等的两个子集，则选择其中一个作为训练数据集、另一个作为测试数据集。随后交换两组角色：原先作为训练的数据集转为测试数据集、反之亦然。
（2）k-分法交叉验证：这是二分法的推广方式即分割成k个子集
（3）留一检验：每个测试集中仅包含一个记录
优点：尽可能多地利用训练样本
缺点：性能评估指标估计方差较大
4 自助法
Training records are subjected to with replacement sampling, meaning that once a record has been selected for training, it is placed back into the original pool and has an equal probability of being reselected.
The most commonly used is the .632 bootstrap method.
比较两个分类器的方法：
- 计算准确度置信区间的步骤
通过将分类任务建模为二项式实验来推导置信区间。这种实验具有以下特征：
（1）实验由N次独立的伯努利试验组成，在每次试验中有两种可能的结果：成功或失败。
（2）每次试验成功的概率p是恒定的常数。 - 采用模型性能评估方法进行比较
- 使用分类器性能标准进行评估