《数据挖掘基础与案例》 课件 第4-7章 分类概念与方法-案例分析

第4章分类概念与方法数据挖掘基础与案例学习目标/Target掌握决策树基本原理、属性划分度量、决策树剪枝策略以及典型的决策树算法C4.5和CART等了解分类的基本概念和一般方法掌握分类模型评估与选择的方法、指标以及可能遇到的问题掌握Logistic回归的基本原理及特点掌握最近邻分类法的原理和特点，掌握朴素贝叶斯分类器的原理和特点学习目标/Target了解人工神经网络的概念、方法，掌握BP算法的原理了解集成学习方法的基本原理，掌握随机森林算法了解分类的典型应用掌握支持向量机的原理目录/Contents01分类的基本概念02分类的一般方法03决策树归纳04模型的评估与选择05最近邻分类法06朴素贝叶斯分类器目录/Contents0809支持向量机10集成学习07Logistic回归人工神经网络11分类的典型应用分类的基本概念4.14.1分类的基本概念分类是指通过在数据集中学习，得到一个分类模型，该模型能把数据集中的每个属性值集X映射到一个预先定义的类标号y。属性集X可以包含离散属性，也可以包含连续属性，但类标号属性y（即目标变量）是离散且无序的。分类模型是对数据集中属性集与类标号之间关系的形式化抽象表达，表达形式可以是树、规则、概率表、网络或一个实值参数的向量等。有了分类模型，就能对数据集中的每个属性值集确定一个预先定义的类标号（即预测值）。分类模型也被称为分类函数或分类器（classifier）。从数据中获得模型的过程被称为“学习（learning）”或“训练（training）”，该过程通过执行某个算法来完成。训练模型的数据集被称为训练集（trainingset）4.1分类的基本概念分类建模用途：描述性建模，概括数据实例中的结构，作为解释工具，用来区分不同类中的对象；预测性建模，用于预测未知记录的类标号。分类模型是一个黑盒子，当给定未知记录的属性集取值时，自动赋予未知样本一个类标号。分类模型最适合描述或预测二元类型或标称类型的数据集。分类法：根据训练数据集训练或建立分类模型的方法。有决策树法、基于规则的分类法、贝叶斯分类法、神经网络、支持向量机等。分类的一般方法4.24.2分类的一般方法分类过程有两个阶段：学习阶段，分类阶段。学习阶段：通过分类算法在训练集上学习来构建分类模型，是一个归纳（induction）过程分类阶段：使用已建模型对将来的或未知实例进行分类（给定一个类标号），是一个演绎（deduction）过程。由学习算法构建的模型既要很好地拟合训练数据，也要能尽可能正确地预测未知实例的类标号。分类阶段首先要评估分类模型的预测准确率（或错误率）。分类模型可能拟合了训练数据中的特定异常，用训练集评估分类模型会导致过于乐观的结果，因此评估分类模型的数据集应独立于训练集，以洞察模型的泛化性能。评估分类模型泛化性能的数据集被称为测试集（testset），测试集中实例的类标号是已知的。多数分类算法致力于学习测试集上最高准确率或最低错误率的模型。4.2分类的一般方法

预测的类别

C1C2

实际的类别C1f11f12C2f21f22

预测的类别

C1C2C3

实际的类别C1f11f12f13C2f21f22f23

C3f31f32f33决策树归纳4.34.3决策树归纳决策树包含一个根结点、若干个内部结点和若干个叶结点。根结点没有入边，只有出边；内部结点既有入边，也有出边；叶结点只有入边，没有出边。根结点和内部结点表示一个属性上的测试，每个分枝代表该测试的一个输出，每个叶结点存放一个类标号，表示决策结果。决策树可能是二叉树（如CART算法），也可能是多路分枝树（如C4.5算法）。决策树的生成包含两个部分：决策树的构建和决策树的剪枝。在开始构建决策树时，所有的训练实例都集中在根节点，然后递归地选择属性对数据集不断地进行分裂。对决策树进行剪枝是因为充分生长的决策树中的许多分枝可能反映的是训练数据中的特殊情况或异常，树剪枝试图检测并剪去这样的分枝，以提高模型在一般使用中的泛化性能。4.3决策树归纳决策树的生成包含：决策树的构建，决策树的剪枝。开始构建决策树时，所有训练实例都集中在根节点，然后递归地选择属性不断分裂数据集。对决策树剪枝，是因为充分生长的决策树中的许多分枝可能反映的是训练数据中的特殊情况或异常，树剪枝试图检测并剪去这样的分枝，以提高模型在一般使用中的泛化性能。4.3.1决策树归纳的基本原理决策树归纳的思想：分而治之。决策树生成策略：自顶向下的贪心递归划分。从训练集中属性集和它们相关联的类标号开始构建决策树。随着树的生长，训练集递归地被划分成一个个子集。首先要选择一个属性放置在根节点上作为测试属性，接着为每个可能的属性值产生一个分枝，训练集被分裂成若干个子集，一个子集对应一个属性值。然后对每个分枝仅使用到达这个分枝的实例递归地重复上述过程，直到产生叶节点为止。基本算法如算法4.1。4.3.1决策树归纳的基本原理三种情形下递归返回：（1）当前节点上的元组属于同一类时，将当前结点标记为叶结点，存放该类标号；（2）当前属性集为空，或所有当前元组在所选属性上取值相同，将当前结点标记为叶结点，存放当前元组集中多数类的类标号；（3）当前结点包含的元组集为空，将当前结点标记为叶结点，存放其父结点所包含元组集中多数类的类标号。问题：对于一个给定的训练集，如何判断应该在哪个属性上进行分裂，即如何选择最优的分裂属性呢？4.3.2属性划分的度量

信息增益4.3.2属性划分的度量

信息增益

4.3.2属性划分的度量

信息增益

4.3.2属性划分的度量

信息增益率

4.3.2属性划分的度量

基尼指数

4.3.3树剪枝剪枝是决策树算法处理“过拟合”的主要手段。使用统计度量剪掉最不可靠的分枝，降低决策树过拟合风险，从而提升模型的泛化性能。决策树剪枝策略有先剪枝和后剪枝。先剪枝通过提前停止树的生长对树进行剪枝。当前节点是否成为叶结点，可以通过预设诸如结点中包含的实例数、信息增益、基尼指数等度量的阈值或泛化误差来评估划分的优劣。如果划分一个结点所产生的不纯性的下降未达到阈值，或泛化误差的估计值没有下降，则停止分裂该结点存放的数据子集并使其成为叶结点，并用子集中最多数类别的类标号进行标记。先剪枝能降低过拟合风险，缩短训练时间和测试时间，但很难选取一个适当的阈值。高阈值可能导致提前结束树的生长，低阈值可能导致不能充分解决过拟合问题。先剪枝

4.3.3树剪枝后剪枝：先在训练集上生成一棵“完全生长”的决策树，然后按自底向上方式进行修剪。后剪枝有两种操作：①将某个非叶结点为根结点的子树替换为叶结点，并用子树中最多数类别的类标号进行标记，称为子树替换。②用子树中最常用分枝置换子树，称为子树提升。子树替换是主要后剪枝操作。替换前的决策树如图4.4a所示，使用子树替换操作得到的决策树，如图4.4b所示。模型中除C之外均为连续属性，类标号为P和N。考虑将属性C子树的三个子结点替换成单个叶结点，然后从该叶结点开始，将只有两个叶结点的B子树替换成单个叶结点，类标号为N（设N为多数类）。后剪枝

4.3.3树剪枝替换前的决策树是在训练集上按照最大规模生长的一棵完整的决策树。子树替换会导致模型在训练集上的准确率下降，但会提高模型在独立检验集上的准确率，即提升模型的泛化性能。后剪枝

图4.4子树替换举例4.3.3树剪枝图4.5用虚拟例子解释子树提升。考虑对决策树a进行子树提升，剪枝结果如决策树b。操作中，自C以下的子树被提升上来替换以B为根结点的子树。这里C的子结点和B的另外两个子结点是叶结点，但也可以是完整的子树。进行子树提升，需要将结点L4和结点L5处的实例重新划分到标有C的新子树中去。假设从B到C的分枝比从B到结点L4或者B到结点L5的分支有更多训练实例，考虑图中所示提升。如果结点L4是B的主要子结点，则将考虑提升结点L4代替B，并重新对C以下的所有实例以及结点L5的实例进行分类后加入到新的结点。后剪枝

4.3.3树剪枝是否用单个叶结点替换一个内部结点(子树替换)，或用位于一个内部结点下的某结点来替换该内部结点(子树提升)，取决于剪枝对决策树泛化性能的提升。用一个独立的测试集在所考察的结点处进行错误率估计。通过比较替换子树和被替换子树错误率决定是否对某个子树进行替换或提升操作。先剪枝难以精确估计何时停止树增长；后剪枝欠拟合风险小，泛化性能常优于先剪枝。后剪枝更常用。后剪枝

图4.5子树提升举例（节点C提升并包含节点B）4.3.4决策树归纳算法C4.5算法是ID3算法的改良，采用信息增益率作为划分属性的度量准则，以校正ID3采用信息增益作为划分属性度量准则时对多值属性的倾向性。为防止校正过度，C4.5在选择增益率最大的侯选属性作为划分属性时，增加了一个约束：该属性的信息增益要大于等于所考察属性的信息增益的平均值。C4.5对ID3的改良还包括处理连续属性（离散化）、缺失值、噪声数据以及树剪枝的方法和由决策树产生规则的方法等。商业化版本C5.0是C4.5的进阶，增加了使用交叉验证（CrossValidation）法评估模型，使用提升法提高模型的准确率。C5.0的核心算法仍以C4.5为主，下面介绍C4.5中分枝的产生和剪枝。C4.5

4.3.4决策树归纳算法（1）决策树的创建设当前结点为t，计算每个侯选属性的信息增益率，穷举搜索所有可能的分枝，从中选择具有最大信息增益率的侯选属性作为结点t处的划分属性，要求选取的划分属性的信息增益不低于所有侯选属性的平均信息增益。C4.5在表4.5气象数据集D上训练的决策树如图4.6所示。C4.5

图4.6C4.5在气象数据集D上训练的决策树4.3.4决策树归纳算法

C4.5

4.3.4决策树归纳算法（3）剪枝C4.5使用悲观错误剪枝（PessimisticErrorPruning，PEP）方法修剪决策树。悲观错误剪枝方法通过增加一个惩罚来调节训练集上的错误率，抵消出现的偏倚。对于一个子树，其悲观错误率是该子树中所有叶子节点的悲观错误率之和。尝试将一个子树替换为一个叶子节点，计算剪枝后的悲观错误率。如果剪枝后的悲观错误率在一定“机制”下不超过未剪枝时的悲观错误率，则进行剪枝操作，即将该子树的根节点变为一个叶子节点，该叶子节点的类别为该子树中实例数最多的类别，否则保留该子树。C4.5

4.3.4决策树归纳算法CART算法建立二叉树。既可以用于类别变量以及连续变量的分类问题，也可以用于回归问题。对于分类问题（例如，预测贷款者是否拖欠还款），CART以基尼指数作为选择划分属性的度量准则，对分枝节点进行数据分裂，建立一个二元划分的分类树；对于回归问题（例如，预测一个人的年龄），将样本的平方误差最小化作为结点分裂的依据，建立一个二元划分的回归树。（1）分类树的二元划分使用基尼指数考虑每个属性的二元划分。如果A是离散属性，在训练集D中有k个不同取值{a1,a2,…,ak}。为确定A上最好的二元划分，考察A的已知值形成的所有可能子集对D的二元分裂。基于A的二元划分，共有2k-1-1种对D的可能分裂方法。CART

4.3.4决策树归纳算法

CART

4.3.4决策树归纳算法

CART

4.3.4决策树归纳算法

CART

4.3.4决策树归纳算法

CART

4.3.4决策树归纳算法

CART

4.3.4决策树归纳算法（3）剪枝CART使用后剪枝算法CCP（代价复杂度）来处理模型的过拟合。将树的复杂度看作树中叶结点个数和树误差率的函数。从树的底部开始，对于每个内部结点t，计算t的子树的代价复杂度和该子树剪枝后t的子树（用一个叶结点替换）的代价复杂度。如果剪去t的子树导致较小的代价复杂度，则剪去该子树，否则，保留该子树。CART

4.3.5由决策树提取规则从决策树中可以提取IF-THEN规则，建立基于规则的分类器。规则可能更易于理解。基于规则的分类器使用一组表示为“IF…THEN…”的规则集，或一组蕴含式ri:(conditioni)→yi对实例分类。左边称为规则的“前件”或“前提”，右边称为规则的“后件”或“结论”。从决策树根节点到每一个叶结点的路径都可提取一个分类规则。路径上的测试条件的合取形成规则的前件，叶结点处的类标号形成规则的后件。规则直接从决策树提取，所以规则集是互斥的，也是穷举的。分类规则

4.3.6决策树归纳的一般特点（1）适用性。决策树归纳是一种构建分类模型的非参数方法，它不需要任何关于数据的类别和其他属性的概率分布的先验假设，因此适用于各种数据集。（2）表达能力。决策树为离散值函数提供了一个通用表示。（3）解释能力。决策树简单直观，解释性强。（4）计算效率。许多决策树算法采用基于启发式的方法在大规模的搜索空间中寻找决策树，即使训练集的规模很大，也能快速构建合理的决策树。（5）处理缺失值。对于有缺失值的训练集和测试集，决策树分类器可以通过多种方式进行处理。（6）处理属性之间的相互作用。（7）处理不相关属性。（8）处理冗余属性。（9）不纯性度量的选择。不同的不纯性度量，其值往往是一致的（例如熵、基尼指数和分类误差），因此不纯性度量的选择通常对决策树的性能没有影响。

（10）直线决策边界。决策边界为平行于坐标轴的直线段（单变量决策树），或不平行于坐标轴的斜线段（多变量决策树）。模型的评估与选择4.44.4.1模型的过拟合学习方法的泛化能力，指由该方法训练得到的模型对未知实例的预测能力。将模型的预测输出与实例的真实输出之间的差异称为“误差”。分类模型的误差大致分为两种：训练误差和泛化误差。训练误差，是指模型在训练集上的误差。泛化误差是指模型在未知实例上的误差，用来评价学习方法的泛化能力。无法直接获得泛化误差，通常努力使训练误差最小化。有些模型即使有很小的训练误差，也可能表现出较差的泛化性能。需要一个独立于训练集的含有类别标号的测试集，通过计算模型在测试集上的测试误差（TestingError）来估计泛化误差，以反应模型对未知实例的预测能力。4.4.1模型的过拟合模型的过拟合，是指模型训练过程中，学得“太好”，以致于把训练实例中的个性化特点当成一般性质，导致模型泛化能力的下降。模型的欠拟合，是指在训练集上的学习不够充分，尚未学习到数据中的“普遍规律”。欠拟合较过拟合，比较容易克服。在决策树生长初期，决策树过于简单，训练集和测试集上的错误率一般都很高，属于模型欠拟合（即拟合不足）。随着决策树中结点数的增加，训练集和测试集上的错误率均会下降，但当决策树规模增大到一定程度之后，训练集上的错误率会继续变小，甚至下降为零，而测试集上的错误率却不再减小，反而可能会越来越大，这模型的过拟合现象。模型过拟合的最主要因素：模型的复杂度过高，训练实例的代表性不足等。4.4.1模型的过拟合比较复杂的模型能够更好地表达数据中的复杂模式。例如，和叶结点数目较少的决策树相比，具有更多叶结点的决策树能够表达更复杂的决策边界。相对于训练集，一个过于复杂的模型由于强大的学习能力，会将训练集中的特定模式或异常与普遍规律一并学习到。模型由于拟合了训练集中的特定模式或异常，不能很好地对新样本进行预测。常以模型的参数数量度量模型的复杂度。学习时模型所包含的参数过多就容易过拟合。模型的复杂度过高

4.4.1模型的过拟合表4.13中有10个实例，其中蝙蝠与鲸都是哺乳类动物，却错误地被标记为非哺乳类动物（即噪声数据）。以该实例集作为训练集，建立模型M1和M2，如图4.12所示。以表4.14中的实例作为测试集。M1完全拟合了训练实例，训练误差为0，但M1在测试集上的错误率高达30%。M2未拟合全部训练数据，训练集上的错误率为20%，但在测试集上具有较低的错误率10%。M1过分拟合了包括噪声在内的所有训练实例，因为存在一个更简单、在测试集上的错误率更低的模型M2。数据中难免存在噪声，决策树的规模越大，与训练数据的拟合越好，但模型的复杂度就越高，过拟合的风险也就越大。剪枝是应对过拟合的重要手段，通过去掉一些分枝降低模型的复杂度，减小过拟合的风险。模型的复杂度过高

4.4.1模型的过拟合表4.15中的每个实例的类别标号都是正确的（即无噪声数据），以其中的六个实例为训练集，建立图4.13中决策树模型。模型完全拟合了训练实例，在训练集上的错误率为0，但在表4.14中的测试集上的错误率高达30%。“人”“象”“海豚”均被模型错误地分类为“非哺乳类动物”。原因是模型从“鹰”这个唯一“体温=恒温”且“冬眠=否”、类别标号为“非哺乳类动物”的实例学习到“恒温”但“不冬眠”的脊椎动物为“非哺乳类动物”的决策。少量训练实例往往缺乏代表性，所建立的分类模型容易发生过拟合，做出的预测很可能是错误的预测。训练数据的代表性不足

4.4.2模型的性能度量评估模型的泛化性能，首先要有衡量模型泛化能力的评价标准，即性能度量。在比较不同模型的泛化性能时，不同的性能度量可能导致不同的评判结果，即模型的优劣是相对的。一个模型是否为高质量的模型，不仅取决于数据和算法，还取决于任务需求。准确率或错误率是最常用的性能度量，但它们对类分布不平衡问题并不适用。对类倾斜敏感的评估指标有：真正率、真负率、精度、召回率、F1度量等。混淆矩阵是分析分类器识别能力的常用工具。二分类问题的混淆矩阵：表4.16二分类问题的混淆矩阵4.4.2模型的性能度量

准确率与错误率

4.4.2模型的性能度量

真正率、真负率与G-mean

4.4.2模型的性能度量

假正率、假负率与G-mean

4.4.2模型的性能度量

精度、召回率与F1度量

4.4.1模型的过拟合

精度、召回率与F1度量

4.4.2模型的性能度量

精度、召回率与F1度量

4.4.2模型的性能度量接收者操作特征（ReceiverOperatingCharacteristic，ROC）曲线，一种用于分类器综合评估的可视化工具，显示分类器在不同评分阈值时真正率与假正率之间的折中。对于二类问题，通过ROC曲线，可以对于测试集的不同部分，观察模型正确识别正样本的比例与错误地把负样本识别成正样本的比例之间的权衡。现实任务中，根据有限个坐标对，绘制近似的ROC曲线。ROC与AUC

4.4.2模型的性能度量在ROC曲线中，纵轴为TPR，横轴为FPR。计算并绘制ROC曲线的一般步骤如下。1）根据分类器产生的预测值的递减序对样本进行排序。2）以序列表中排在第一位的样本的预测值作为阈值，将预测值大于等于该阈值的测试样本分到正类，将预测值小于该阈值的测试样本分到负类，计算TP、FP,、TN、FN，以及TPR与FPR。3）选择下一个预测值作为阈值，将预测值大于等于该阈值的测试样本分到正类，将预测值小于该阈值的测试样本分到负类，更新TP、FP、TN和FN的值，并计算TPR与FPR。4）重复步骤3），直到选择序列表中最小预测值为阈值时，将所有的样本都分到正类，这时TN=FN=0，TPR=FPR=1。5）将各点连接起来绘制折线。ROC与AUC

4.4.2模型的性能度量在例4.7绘制的ROC曲线图中（图4.14），主对角线代表随机猜测。把每个样本都预测为负类时，TPR=0，FPR=0；把每个样本都预测为正类时，TPR=1，FPR=1；理想模型，TPR=1，FPR=0。一个模型的ROC曲线离对角线越近，模型的准确率越低。一个分类器的ROC曲线将另一个分类器的ROC曲线完全包住时，该模型的性能优于后者；当两个模型的ROC曲线相交叉时，无法一般性地判断哪个模型性能更优，只能分段比较，更合理的方法是比较ROC曲线下的面积（AreaUnderROCCurve，AUC），如图5.17所示。ROC与AUC

4.4.2模型的性能度量ROC与AUC

图4.14例4.7ROC曲线图4.15两个不同分类器的ROC曲线4.4.3模型评估方法交叉验证被广泛使用，有效地利用了所有标记实例进行训练和测试，以减少由于保持法取样而引起的偏差。k折交叉验证法，首先确定一个固定折数k，将数据集D随机分成大小大致相等的k个互斥子集Di（i=1,2,…,k），每个子集应该尽可能保持数据分布的一致性；然后将Di（i=1,2,…,k）轮流用作测试集，将剩余的k-1个子集中的数据用作训练集，共进行k次训练和测试，最终的评估值为k次评估值的平均。实验表明：10折交叉验证可被作为标准方法。为减少数据集的不同划分对评估结果带来的不稳定性，通常将k折交叉验证法重复n次，最终的评估结果是n次k折交叉验证结果的平均值。标准程序是重复10次10折交叉验证，然后取平均值。对于大型数据集，过高的k值会造成很大的计算开销。在大多数的实际应用中，k值取为5~10。交叉验证

4.4.4模型选择

结合模型复杂度的泛化误差估计

4.4.4模型选择

单个模型错误率的置信区间

4.4.4模型选择交叉验证的t检验法假设由训练集建立了两个分类模型M1和M2，并进行了10次10-折交叉验证。每次对数据都进行不同的10折划分，每个划分都独立抽取。分别对M1和M2得到的10个错误率计算平均值，得到每个模型的平均错误率。平均错误率只是对模型在未知数据上的错误率的估计值。k-折交叉验证实验的各错误率之间可能存在很大的方差。M1和M2的平均错误率之间的差异是否具有统计显著性？提出原假设：两个平均错误率之差为0，如果能够拒绝原假设，则可以断言M1和M2之间的差异是统计显著的。就可以选择具有较低错误率的模型。通常使用相同数据集测试M1和M2。对于10-折交叉验证的每一轮，逐对比较两个模型。使用统计显著性检验选择模型

4.4.4模型选择

使用统计显著性检验选择模型

K-最近邻分类4.54.5.1K-最近邻分类器急切学习法在接到待分类新实例之前，根据训练集构造了分类模型，如决策树归纳。惰性学习法需要对新实例分类之时才构造模型。给定训练集，惰性学习法只是对它进行简单存储（或稍加处理），等到给定一个需要分类的实例时，才进行泛化，以便根据与存储的训练实例的相似性，对该实例进行分类。k-最近邻（k-NearestNeighbor,k-NN）分类法搜索模式空间，找出与未知实例最相似的k个训练实例（称为未知实例的k个最近邻），将未知实例指派到它的k个最近邻的多数类。k-最近邻算法的过程如算法4.2所示。算法4.2K-最近邻（K-NN）分类算法4.5.1K-最近邻分类器

4.5.2K-最近邻分类器的特点最近邻分类器具有以下特点：1）一种基于实例的学习，不需要建立全局模型，但需要一个邻近性度量来确定实例间的相似性。2）需要计算待分类实例与所有训练实例之间的邻近度，所以分类一个测试实例开销很大。但一些引入更高级数据结构的算法，能够成功处理数千维的实例空间。3）可以生成任意形状的决策边界，与决策树和基于规则的分类器通常局限于直线决策边界相比，最近邻分类器能提供更加灵活的模型表示。4）需要适当的邻近性度量和数据预处理步骤，以防止邻近性度量被某些属性所左右而产生错误的预测。5）基于局部信息进行预测，k很小时，对噪声非常敏感。6）难以处理训练集与测试集中的缺失值。7）不能确定相关属性，当包含大量不相关属性和冗余属性时，将产生较高的分类错误率。但如果通过属性预处理能确定一组最佳的相关属性，通常会工作得好。贝叶斯分类器4.64.7贝叶斯分类器当属性集与类别变量之间具有不确定性关系时，即使测试实例的属性集和某些训练实例相同，也不能正确地预测它的类标号，比如体育比赛。贝叶斯分类器是一种概率框架下的统计学习分类器，它通过对训练数据的属性集和类别变量的概率关系建模，来解决涉及不确定性的分类问题。贝叶斯分类器基于贝叶斯定理。朴素贝叶斯分类器是贝叶斯分类器中的一种简单而又有效的分类法，具有和随机森林、神经网络等分类器可比的性能，常用于垃圾文本过滤、情感预测、推荐系统等。4.6.1贝叶斯定理

4.6.2朴素贝叶斯分类器

朴素贝叶斯分类器的基本原理

4.6.2朴素贝叶斯分类器

朴素贝叶斯分类器的基本原理

4.6.2朴素贝叶斯分类器

类先验概率与类条件概率的估计

4.6.2朴素贝叶斯分类器

类先验概率与类条件概率的估计

4.6.2朴素贝叶斯分类器

零条件概率的拉普拉斯修正

4.6.3朴素贝叶斯分类器的特征朴素贝叶斯分类器具有以下特征：1）是能够通过提供后验概率估计来量化预测中的不确定性的概率分类模型。它试图捕捉生成属于每个类的数据实例背后的基础机制。有助于获取预测性和描述性见解。2）朴素贝叶斯假设使得在给定类标号的条件下，可以容易地计算高维情况下的类条件概率。3）对孤立的噪声点具有鲁棒性。4）在计算条件概率时，通过忽略每个属性的缺失值来处理训练集中的缺失值。在计算后验概率时，它通过只使用非缺失的属性值来有效地处理测试实例中的缺失值。如果特定属性的缺失值的频率取决于类标号，则该方法无法准确地估计后验概率。5）对不相关属性具有鲁棒性。6）相关属性可能会降低朴素贝叶斯分类器的性能，因为对于这些属性，类条件独立的假设已不成立。

Logistic回归4.74.7.1Logistic回归的基本原理Logistic回归（LogisticRegression）是一种解决二分类问题的有监督学习算法，它通过构建概率模型来预测样本属于某个类别的可能性。L其核心目标是：根据输入属性，预测一个样本属于某个类别的概率。Logistic回归基础是线性回归，但线性回归的输出是连续值，而分类问题的类标签是离散值。Logistic回归引入sigmoid函数，将线性回归的输出映射到[0,1]区间，以此表示样本属于某一类别的概率

核心思想

4.7.1Logistic回归的基本原理图4.17sigmoid函数曲线

模型构建与参数估计

4.7.1Logistic回归的基本原理

决策边界与分类

4.7.1Logistic回归的基本原理4.7.2Logistic回归的特点Logistic回归具有以下特点：1）本质是线性分类模型，但输出为概率值。这种结构既保留了线性模型的简洁性，又能直接输出分类的可信度，既体现了属性对目标变量的线性影响，又量化了结果的不确定性。2）可解释性强，权重参数具有明确意义。模型中的权重参数直接反映了属性对分类结果的影响程度和方向。这种可解释性使其在需要“透明决策”的领域（如医疗诊断、信贷审批等）具有优势。3）训练高效，是用于大规模数据集。Logistic回归的参数求解基于极大似然估计，可通过梯度下降等优化算法快速收敛，计算复杂度低。即使面对百万级样本，也能在短时间内完成训练。4）支持二分类，多分类问题需要使用One-vs-Rest策略等进行特殊处理。5）对数据预处理敏感，需重视特征工程。数值型属性需标准化，难以直接处理非线性关系。6）抗过拟合能力较弱，需通过正则化提升模型的泛化能力。7）对异常值和多重共线性敏感。4.8.1多层前馈神经网络人工神经网络（ArtificialNeuralNetworks，ANN）也简称为神经网络（NN），是模拟生物神经网络进行信息处理的一种数学模型。以对大脑的生理研究成果为基础，目的在于模拟大脑的某些机理与机制，实现一些人脑功能的基本特性。人工神经网络具有突出的特点和优势，神经网络具有高度的并行结构和并行实现能力，能够发挥计算机的高速运算能力，可能很快找到优化解，具有自学习、自组织、自适应能力，具有非线性处理能力，人脑的思维是非线性的，故神经网络模拟人的思维也应是非线性的。神经元模型4.8.1多层前馈神经网络

M-P神经元模型为上一层神经元的输出或者网络输入，为神经元的连接权重，σ为激活函数，b为偏置，ο为神经元的输出Sigmoid函数：Tanh函数：Relu函数：多层前馈神经网络4.8.1多层前馈神经网络多层前馈神经网络结构图一个典型的多层前馈神经网络是一个至少包含三个层次的网络，它们分别是输入层、隐含层和输出层。(a)通常被称为单隐层网络，(b)是拥有两个隐含层，且两个隐含层中的神经元的数量不同的网络。向前传播4.8.1多层前馈神经网络简单的多层前馈神经网络向后传播算法的原理4.8.2误差的后向传播算法BP算法由正向传播过程和反向传播过程组成，正向传播过程即前馈的过程。定义损失：如果输出层没有得到期望计算结果，则定义样本输出值与样本目标变量值间的误差作为目标函数，反向转播：计逐层求出目标函数对各神经元中权值和偏置的偏导数，构成目标函数对权值和偏置的梯度，目标是更新权值和偏置，使损失最小向后传播算法的原理4.8.2误差的后向传播算法算法5.4向后传播算法向后传播算法的实例4.8.2误差的后向传播算法利用Scikit-Learn库在Iris数据集上训练一个BP神经网络fromsklearnimportdatasetsfromsklearn.model_selectionimporttrain_test_splitfromsklearn.neural_networkimportMLPClassifieriris=datasets.load_iris()iris_x=iris.datairis_y=iris.targetx_train,x_test,y_train,y_test=train_test_split(iris_x,iris_y,test_size=0.3)#定义模型bp=MLPClassifier(hidden_layer_sizes=100,max_iter=10000\,learning_rate_init=0.001,activation='logistic')bp.fit(x_train,y_train)score=bp.score(x_test,y_test)print('模型的准确度：{0}'.format(score))fromsklearnimportdatasetsfromsklearn.model_selectionimporttrain_test_splitfromsklearn.neural_networkimportMLPClassifieriris=datasets.load_iris()iris_x=iris.datairis_y=iris.targetx_train,x_test,y_train,y_test=train_test_split(iris_x,iris_y,test_size=0.3)#定义模型bp=MLPClassifier(hidden_layer_sizes=100,max_iter=10000\,learning_rate_init=0.001,activation='logistic')bp.fit(x_train,y_train)score=bp.score(x_test,y_test)print('模型的准确度：{0}'.format(score))例4.14在Iris数据集上训练一个BP神经网络实现鸢尾花的分类。使用Scikit-Learn库中的多层感知器MLP的MLPClassifier()方法。该方法用随机梯度下降（SGD）算法进行训练。网络输入数据是花萼长度、花萼宽度、花瓣长度和花瓣宽度4个特征组成的样本，是一个n行四4列的矩阵。设x_train为输入数据，y_train为目标变量y的数据，则x_train为n行4列的矩阵，y_train为n个数值的列表。在如下实现代码中，MLPClassifier()模型的参数，hidden_layer_sizes=100为隐含层神经元的数量，仅有1个隐含层，如果需要定义多层则使用元组设定该参数，激活函数activation的取值为“'logistic'”，即Sigmoid函数作为激活函数，学习率learning_rate_init=0.001。输出该网络训练完成后在测试集上的预测准确定为100%。4.8.3

人工神经网络的特点神经网络的优点：（1）非线性映射能力。（2）自学习和自适应能力。（3）泛化能力。（4）容错能力强。神经网络的缺点：（1）局部最优问题（2）神经网络算法的收敛速度慢。（3）神经网络结构选择不一（4）应用实例与网络规模的矛盾问题（5）神经网络预测能力和训练能力的矛盾问题（6）神经网络样本依赖性问题神经网络的优点4.8.4人工神经网络与深度学习（1）人工神经网络是深度学习的基础，深度学习是在人工神经网络的基础上，通过增加网络的深度和复杂度，进一步提升模型的表现。（2）人工神经网络通常只有一两个隐藏层，而深度学习的网络可以有数十甚至数百层。（3）人工神经网络在特征提取方面能力有限，通常需要人为设计特征（特征工程），而深度学习通过多层网络，能够自动从数据中学习层次化特征。（4）人工神经网络适用于简单的分类和回归任务，而深度学习能够处理更复杂、更高维的任务。（5）深度学习的应用场景包括图像识别、自然语言处理、语音识别、自动驾驶、医疗诊断等。（6）人工神经网络对计算资源的需求较低，适合小规模数据，而深度学习需要大量的计算资源（如GPU/TPU）和大规模数据进行训练。神经网络与深度学习支持向量机4.91963年，VladimirVapnik就提出了支持向量的概念。1968年，VladimirVapnik和AlexeyChervonenkis提出了“VC维”理论，1974年又提出了结构风险最小化原则。在这些统计学习理论的基础上，1992年VladimirVapnik与他的同事发表了支持向量机的第一篇论文，1995年发表的文章与出版的书籍对支持向量机进行了更详细的讨论。随着支持向量机在文本分类问题上取得巨大成功，支持向量机很快成为机器学习的主流技术。支持向量机（SupportVectorMachines,SVM）是一种二分类模型，模型利用定义在特征空间中的线性或非线性决策边界来分类，用来分离类。其学习策略是间隔最大化，即选择更好地隔离两个类的超平面作为决策边界。SVM的一个独特特点是它仅使用训练实例的一个子集表示决策边界，该子集被称作支持向量。SVM的学习方法根据训练数据是否线性可分分为线性支持向量机和非线性支持向量机。4.9支持向量机4.9.1线性可分支持向量机

数据集的线性可分性4.9.1线性可分支持向量机

数据集的线性可分性4.9.1线性可分支持向量机

线性可分支持向量机的基本原理

可以划分样本的多个超平面4.9.1线性可分支持向量机

线性可分支持向量机的基本原理4.9.1线性可分支持向量机距离分离超平面最近的训练样本点使式成立，被称为支持向量支持向量对于超平面的位置和方向具有决定性的影响作用，两个不同的支持向量到超平面的距离之和被称为（硬）间隔（Margin），记为γ，支持向量间隔线性可分支持向量机的基本原理4.9.1线性可分支持向量机

学习的对偶算法（5.77）

4.9.1线性可分支持向量机学习的对偶算法（5.77）将式

带入4.9.1线性可分SVM与硬间隔最大化学习的对偶算法（5.77）此时，将原始问题利用拉格朗日乘子法转换为其对偶问题，对偶问题与原始优化问题的解是等价的。对偶问题是先极小化再极大化问题，仅涉及拉格朗日乘子和训练数据，而原始问题涉及拉格朗日乘子和决策边界（分类超平面）中的参数。解出之后

（后续求解），即可求得

，从而得到最大间隔超平面，表示为式求解时

，由于它对应于训练样本，需要满足一定的约束条件，实际为KKT条件：4.9.1线性可分支持向量机

（5.77）SMO（SequentialMinimalOptimization）是序列最小优化算法。

4.9.1线性可分支持向量机

（5.77）

理论上，可选任意向量并通过求解上面的式子获得。在实际应用中，有多个支持向量时，可算出多个偏移项值，通常取它们的平均值作为最终的

值4.9.1线性可分支持向量机

（5.77）。

4.9.1线性可分支持向量机

（5.77）例4.15有一个包含8个训练样本的二维数据集，通过求解优化问题已得到每一个训练样本的拉格朗日乘子，如表5.24所示。4.9.2软间隔支持向量机软间隔最大化（5.77）对于线性不可分的训练数据，由于不存在超平面能够将两类样本完美分开，也就是式(5.71)的条件约束不能满足，所以线性可分问题的支持向量机学习方法不适用于线性不可分问题。

软间隔最大化（SoftMargin）是指在支持向量机中，通过引入松弛变量（slackvariable）允许一些样本点出现在分类器错误的一侧，从而允许一定程度上的分类误差。在软间隔SVM中，目标是最大化“间隔”的同时，通过引入的松弛变量来控制误分类样本对最大化间隔的影响，从而得到一个更加健壮的分类器。

学习的对偶算法（5.77）构造拉格朗日乘子函数

将求导式带入，得到4.9.2软间隔支持向量机

学习的对偶算法（5.77）线性不可分（近似线性可分）的线性支持向量机满足的KKT条件为式

4.9.2软间隔支持向量机得到支持向量后，可得线性支持向量机的分类超平面和决策函数，并且表达形式相同。如果输入数据是可以线性分类的，则软间隔SVM与硬间隔SVM表现相同，但即使不可线性分类，仍能学习出可行的分类规则。4.9.2软间隔支持向量机

（5.77）例4.16使用Scikit-Learn中的make_blobs()方法生成200个具有两个中心的数据集，在此数据集上使用SVM算法进行分类。在make_blobs生成的数据集上使用SVM算法进行分类importnumpyasnpfromsklearn.datasetsimportmake_blobsfromsklearn.svmimportSVCfromsklearn.model_selectionimporttrain_test_split#利用sklearn随机生成数据x,y=make_blobs(n_samples=200,centers=2,random_state=0,cluster_std=0.5)x_train,x_test,y_train,y_test=train_test_split(x,y,test_size=0.3)model=SVC(kernel='linear',C=0.4)#初始化一个线性的支持向量机model.fit(x_train,y_train)print(model.get_params())pred_y_test=model.predict(x_test)print('模型的准确度：{0}'.format(model.score(x_test,y_test)))decision_Function=model.decision_function(x_test)print("Decision_Function:\n",decision_Function)4.9.3非线性支持向量机（5.77）非线性样本空间

如果原始样本空间维度有限，可通过非线性变换将原空间的样本映射到转化为某个更高维特征空间中，将非线性分类问题变换为线性分类问题，然后在新的高维特征空间中用线性分类学习方法学习线性支持向量机。在这个过程中，要用到核函数4.9.3非线性支持向量机核函数的基本思想是将样本数据从低维空间映射到高维空间，使得在高维空间中，数据线性可分。通过这种方式，SVM可以在高维空间中找到一个线性超平面来分离两种类型的样本（5.77）核函数

名称核函数参数线性核无参数多项式核高斯核拉普拉斯核Sigmoid核

常用核函数4.9.3非线性支持向量机

（5.77）核函数的应用非线性样本映射到更高维空间

4.9.3非线性支持向量机（5.77）例4.17使用Scikit-Learn库中的非线性SVM方法SVR对糖尿病数据集进行回归预测。回归中对比不同核函数对分类的影响。可观察到除核函数外，SVM对参数非常敏感。利用Scikit-Learn库中的SVR对糖尿病数据集进行回归预测fromsklearn.datasetsimportload_diabetesfromsklearn.model_selectionimporttrain_test_splitfromsklearn.svmimportSVRfromsklearn.preprocessingimportStandardScalerfromsklearnimportmetrics#导入数据集diabetes=load_diabetes()data=diabetes.datatarget=diabetes.target#数据预处理x_train,x_test,y_train,y_test=train_test_split(data,target,test_size=0.3)Stand_data=StandardScaler()#特征进行标准化Stand_target=StandardScaler()#标签进行标准化x_train=Stand_data.fit_transform(x_train)x_test=Stand_data.transform(x_test)y_train=Stand_target.fit_transform(y_train.reshape(-1,1))y_test=Stand_target.transform(y_test.reshape(-1,1))

4.9.3非线性支持向量机

（5.77）例4.17使用Scikit-Learn库中的非线性SVM方法SVR对糖尿病数据集进行回归预测。回归中对比不同核函数对分类的影响。可观察到除核函数外，SVM对参数非常敏感。利用Scikit-Learn库中的SVR对糖尿病数据集进行回归预测Rg_SVR=SVR(kernel='rbf',C=10,gamma=0.1,coef0=0.1)Rg_SVR.fit(x_train,y_train)y_pred=Rg_SVR.predict(x_test)print("高斯核函数R2得分：",metrics.r2_score(y_test,y_pred.reshape(-1,1)))Rg_SVR=SVR(kernel='sigmoid',C=10,gamma=0.1,coef0=0.1)Rg_SVR.fit(x_train,y_train)y_pred=Rg_SVR.predict(x_test)print("Sigmoid核函数R2得分：",metrics.r2_score(y_test,y_pred.reshape(-1,1)))Rg_SVR=SVR(kernel='poly',C=10,gamma=0.1,coef0=0.1)Rg_SVR.fit(x_train,y_train)y_pred=Rg_SVR.predict(x_test)print("多项式核函数R2得分：",metrics.r2_score(y_test,y_pred.reshape(-1,1)))4.9.2支持向量机的优缺点（5.77）SVM的优缺点优点：在高维空间中有效有效避免过拟合易于解释可以处理非线性问题缺点：对大规模数据集的处理效率较低对参数的选择比较敏感不能直接处理多分类问题集成学习方法4.104.10集成学习方法集成学习（EnsembleLearning）就是将多个弱学习模型进行集成，通过组合多个模型来消除任何单个模型中的偏差，以期得到一个更好的、更全面的强学习模型集成学习可以用于分类问题集成、回归问题集成、特征选取集成、异常点检测集成等4.10.1基本原理

集成学习示意图集成学习中的弱学习器，即个体学习器或基学习器有两类所有的个体学习器都是同一个种类的，称为同质，如都是决策树，或者都是神经网络；第二类是个体弱学习器不全是同一类的，称为异质，如对训练集采用支持向量机，逻辑回归和朴素贝叶斯方法来学习个体学习器，再通过某种结合策略来确定最终的强学习器。目前同质弱学习器的应用更广泛，而同质弱学习器使用最多的模型是CART决策树和神经网络等。同质弱学习器按照学习器之间是否存在依赖关系可以分为两类并行集成学习，其代表方法有袋装（Bagging，全称为BootstrapAggregating）和随机森林（RandomForest）等；串行集成学习，其代表是提升（Boosting）系列算法，如AdaBoost算法。4.10.1基本原理并行集成学习算法

并行集成学习（ParallelEnsembleLearning）的弱学习器之间不存在强依赖关系，可以并行训练得到，然后将这一系列弱学习器进行组合，得到强学习器。

Bagging是典型的并行集成学习算法。图5.28Bagging算法流程4.10.1基本原理串行集成学习算法

串行集成学习方法（SequentialEnsembleLearning）串行地训练一系列弱学习器，每个弱学习器都基于先前学习器的输出，将这一系列弱学习器进行集成，得到强学习器。Boosting系列算法是典型的串行集成学习算法Boosting算法流程4.10.1基本原理集成策略

平均法。对于回归问题，通常使用算术平均法或加权平均法作为集成策略

4.10.1基本原理集成策略投票法。对于分类问题的预测，通常使用的集成策略是投票法。投票法有“硬投票（hardvoting）”与“软投票（softvoting）”之分。在硬投票法中，学习器的预测结果是类标记；在软投票法中，学习器的预测结果是类概率(5.102)

相对多数投票法，其投票原则就是常说的少数服从多数。

绝对多数投票法，是常说的票过半数。加权投票法和加权平均法一样，每个弱学习器的分类票数要乘以一个权重，最终将各类别的加权票数求和，最大值对应的类别为最终类别

4.10.1基本原理集成策略学习法。首先学习多个弱学习器，组合多个弱学习器的输出后，再次进行学习得到强学习器，典型代表为Stacking。Stacking从初始数据集训练出个体学习器，再把个体学习器的输出组合成新的数据集，然后通过算法学习个体学习器的输出集合，最终得到强学习器。将个体学习器称为初级学习器，用于集成的学习器称为次级学习器。(5.102)4.10.2随机森林随机森林的步骤随机森林（RandomForest,RF）是Bagging的一个变体，最早由LeoBreiman和AdeleCutler提出。随机森林试图构造多个相关决策树，组合多个决策树分类器来提高泛化性能。它兼顾了解决回归问题和分类问题的能力，是最常用也是最强大的监督学习算法之一。(5.102)

4.10.2随机森林

（5.77）例4.19使用Scikit-Learn自带的乳腺癌数据集，建立随机森林，并使用交叉验证cross_val_score()方法计算模型的得分乳腺癌数据集上建立随机森林并计算交叉验证的平均得分fromsklearn.datasetsimportload_breast_cancerfromsklearn.ensembleimportRandomForestClassifierfromsklearn.model_selectionimportcross_val_scorebreast=load_breast_cancer()data=breast.datatarget=breast.targetrfc=RandomForestClassifier(n_estimators=100,random_state=90)score_pre=cross_val_score(rfc,data,target,cv=10).mean()print("平均得分：{0}".format(score_pre))4.10.2随机森林随机森林的优点(5.102)（1）由于采用了集成算法，精度比大多数单模型算法要好，所以准确性高；（2）在测试集上表现良好，由于两个随机性的引入，随机森林不容易陷入过拟合；（3）由于两个随机性的引入，随机森林具有一定的抗噪声能力；（4）由于决策树的集成，随机森林可以处理非线性数据，本身属于非线性分类模型；（5）能够处理很高维度的数据，并且不用做特征选择，对数据集的适应能力强，既能处理离散型数据，也能处理连续型数据，数据集无需规范化；（6）训练速度快，可以运用在大规模数据集上；（7）可以处理缺失值，不用对缺失值进行额外处理；（8）由于存在袋外数据（OOB），可以在模型生成过程中取得真实误差的无偏估计，且不损失训练数据量；（9）在训练过程中，能够检测到特征之间的互相影响，且可以得出特征的重要性，具有一定参考意义；（10）由于每棵树可以独立、同时生成，容易做成并行化方法。4.10.2随机森林随机森林的缺点(5.102)

（1）当随机森林中的决策树个数很多时，训练需要的空间比较大，时间比较长；

（2）在某些噪声数据量比较大的样本集上，随机森林模型容易陷入过拟合。

（3）划分取值比较多的特征容易对随机森林的决策产生更大的影响，从而影响拟合模型的效果。分类的典型应用4.114.11分类的典型应用图像分类技术广泛应用于人脸识别、医学影像分析和自动驾驶等领域。文本分类中分类技术用于情感分析、垃圾邮件过滤和新闻主题分类等场景。语音识别的中AmazonAlexa、GoogleAssistant、苹果Siri通过语音识别执行用户指令，通过语音指令控制灯光、空调、扫地机器人。分类技术在图像、文本、语音领域的未来将围绕更加智能化、人性化、普惠化方向发展，随着多模态学习、边缘计算、生成式AI的融合，分类技术将成为数字社会的基础设施，推动从感知智能向认知智能的跃迁，有望在更多的领域提供更加高效便捷的智能化服务。本章小结本章在介绍分类的概念和一般方法的基础上，主要讲解了决策树、模型的评估与选择、基于规则的分类、最近邻分类、朴素贝叶斯分类、Logistic回归和后向传播分类、支持向量机、集成学习方法、多类问题等分类任务中的重要方法和算法。本章小结第5章关联分析概念与方法数据挖掘基础与案例学习目标/Target掌握Apriori算法挖掘关联规则的基本步骤，能够熟练完成频繁项集挖掘和规则生成。了解Apriori算法的优缺点，了解提升算法效率的方法。了解关联模式评估的指标,

熟悉各指标的应用场景。掌握关联分析的基本概念，理解频繁项集和关联规则的内容，掌握先验原理。引言/Introduction关联分析（associationanalysis）从大量数据中发现项集之间有趣的联系，被用于发现隐藏在大型数据集中的有意义的关联。通常将所发现的联系表示为关联规则（associationrule）或频繁项集（frequentitemset）。目录/Contents01基本概念02关联分析的基本任务04频繁项集的紧凑表示03关联分析方法05关联分析的基本任务06关联分析的典型应用基本概念5.15.1.1购物篮分析关联分析的目的是发现被顾客放入购物篮中的不同商品之间的联系，从而分析顾客的购买习惯，了解哪些商品经常被顾客连带购买，为制定方便顾客选取的货架摆放方案和合理的营销策略提供依据，也被称为购物篮分析。完整的购物篮数据至少包含两方面的信息：一方面是顾客的购买行为序号，一个顾客可能会发生多次购买行为，每次购买行为均被记录下来，这个序号也就是超市或者商店的交易流水号；另一方面是顾客在每次购物过程中交易的商品列表，此处商品列表只涉及顾客购买的不同商品的名称。5.1.1购物篮分析购物篮数据涉及关联分析的两个基本术语：事务（transaction）和项集（itemset）。事务是关联分析的研究对象，一个事务包含一个唯一标识TID和对应顾客购买的商品的集合。项目（item）是事务中的单个对象。一次交易中的商品通常是若干个项目的集合，叫作项集。购物篮分析的目的是找到所有购物篮中不同商品之间的关联关系，从而了解哪些商品频繁地被顾客同时购买，帮助零售商制定合理的营销策略。5.1.1购物篮分析在对购物篮数据进行关联分析时，需要处理两个关键问题：第一，计算复杂度问题。从大型事务数据集中发现有意义的规则在计算上要付出很高的代价；第二，规则的筛选问题。所发现的某些规则可能是虚假的或不令人感兴趣的，因为它们可能是偶然发生的或者是已经被研究者所熟知的。除了购物篮分析外，关联分析也被应用于公共管理、生物信息学、医疗诊断、网页挖掘和推荐系统等领域。例如，关联分析可以帮助公安机关从已有的案件中找到各属性之间的隐含关系，发现其中的犯罪行为规律，为新案件的侦破提供线索；在移动通信行业，关联分析可以帮助运营商发现不同业务之间的关联关系，从而推进新业务的发展；关联分析也可以用来分析保险行业的客户数据，找到各险种可能被购买的人群特征，进而进行精准营销。5.1.2频繁项集和关联规则

5.1.2频繁项集和关联规则

5.1.2频繁项集和关联规则

5.1.2频繁项集和关联规则实际应用中的关联规则有许多类型，可以根据不同的标准对关联规则进行分类。根据处理的数据类型，关联规则可以分为布尔关联规则和量化关联规则。布尔型关联规则是指处理的数据类型都是离散属性或分类属性，量化关联规则则是指处理的数据类型包含连续属性。根据处理的数据维度，关联规则可以分为单维关联规则和多维关联规则。单维关联规则通常从事务数据中挖掘，涉及到数据的只有一个维度，处理的是单个维内的关系。根据数据的抽象层次，关联规则可以分为单层关联规则和多层关联规则。在单层关联规则中，没有考虑现实数据的多层次性。多层关联规则是指在规则挖掘中，对数据的多层性进行了充分考虑。关联分析的基本任务5.25.2关联分析的基本任务大多数关联规则挖掘算法通常将关联规则挖掘任务分解为如下两个主要的子任务，以方便进行剪枝。产生频繁项集目标是发现满足最小支持度阈值的所有项集，这些项集称作频繁项集。产生规则目标是从上一步发现的频繁项集中提取所有高置信度的规则，高置信度的规则满足最小置信度阈值，这些规则称为强规则。如何高效率地生成频繁项集，并从得到的频繁项集中找到所有的强规则，是关联分析相关算法需要解决的两个问题。关联分析方法5.3

5.3.1先验原理

5.3.1先验原理即，一旦发现一个非频繁项集，那么包含该项集的所有超集都可以被剪枝，这样的方法被称为基于支持度的剪枝（support-basedpruning）。基于支持度的剪枝依赖于支持度度量的性质，即一个项集的支持度决不会超过它的子集的支持度，这个性质也被称为支持度度量的反单调性（anti-monotone）。任何具有反单调性的度量都能够直接结合到挖掘算法中，对候选项集的指数搜索空间有效地进行剪枝，以降低生成频繁项集的计算代价。5.3.2Apriori算法产生频繁项集Apriori算法是关联规则挖掘的经典算法，它开创性地使用了基于支持度的剪枝技术来控制候选项集的指数增长。此处以下表所示的事务数据集为例，展示Apriori算法挖掘频繁项集产生强关联规则的基本过程。TID商品集合1牛奶，鸡蛋，面包，薯片2鸡蛋，爆米花，薯片，啤酒3鸡蛋，面包，薯片4牛奶，鸡蛋，面包，爆米花，薯片，啤酒5牛奶，面包，啤酒6鸡蛋，面包，啤酒7牛奶，面包，薯片8牛奶，鸡蛋，面包，黄油，薯片9牛奶，鸡蛋，黄油，薯片5.3.2Apriori算法产生频繁项集

项集支持度计数{爆米花}2{黄油}2{鸡蛋}7{面包}7{牛奶}6{薯片}7{啤酒}45.3.2Apriori算法产生频繁项集

项集支持度计数{鸡蛋}7{面包}7{牛奶}6{薯片}7{啤酒}45.3.2Apriori算法产生频繁项集

项集支持度计数{鸡蛋，面包}5{鸡蛋，薯片}6{鸡蛋，啤酒}3{面包，薯片}5{面包，啤酒}3{牛奶，鸡蛋}4{牛奶，面包}5{牛奶，薯片}5{牛奶，啤酒}2{薯片，啤酒}25.3.2Apriori算法产生频繁项集

项集支持度计数{鸡蛋，面包}5{鸡蛋，薯片}6{鸡蛋，啤酒}3{面包，薯片}5{面包，啤酒}3{牛奶，鸡蛋}4{牛奶，面包}5{牛奶，薯片}55.3.2Apriori算法产生频繁项集

5.3.2Apriori算法产生频繁项集

项集支持度计数{鸡蛋，面包，薯片}4{鸡蛋，面包，啤酒}2{牛奶，鸡蛋，面包}3{牛奶，鸡蛋，薯片}4{牛奶，面包，薯片}45.3.2Apriori算法产生频繁项集

项集支持度计数{鸡蛋，面包，薯片}4{牛奶，鸡蛋，面包}3{牛奶，鸡蛋，薯片}4{牛奶，面包，薯片}45.3.2Apriori算法产生频繁项集

项集支持度计数{牛奶，鸡蛋，面包，薯片}35.3.2Apriori算法产生频繁项集

5.3.2Apriori算法产生频繁项集

项集支持度计数5.3.2Apriori算法产生频繁项集

5.3.2Apriori算法产生频繁项集

产生候选项集5.3.2Apriori算法产生频繁项集

产生候选项集5.3.2Apriori算法产生频繁项集

5.3.2Apriori算法产生频繁项集候选项集剪枝

5.3.2Apriori算法产生频繁项集计算支持度计数

5.3.2Apriori算法产生频繁项集计算支持度计数

5.3.2Apriori算法产生频繁项集计算支持度计数

5.3.2Apriori算法产生频繁项集计算支持度计数

5.3.2Apriori算法产生频繁项集计算支持度计数

5.3.2Apriori算法产生频繁项集计算支持度计数5.3.2Apriori算法产生频繁项集计算支持度计数首先进行第一层散列，首项为1的项集，应该散列在左边，而首项为2的散列在中间，首项为3的散列在右边，如下图所示：5.3.2Apriori算法产生频繁项集计算支持度计数按同样方式进行第二层散列，第1项为1的3-项集中第2项为2、