第4章 分类概念与方法

数据挖掘基础与案例习题参考答案第4章分类概念与方法习题1：使用决策树模型分类分为两个阶段：决策树模型构建和决策树模型应用。第一阶段：决策树模型的构建。这个阶段的主要步骤如下：（1）数据准备收集已标注类别的数据集，并进行必要的数据预处理（如处理缺失值、异常值、连续属性离散化等）。将数据划分为训练集和测试集。（2）选择划分属性从根节点开始，将训练集视为当前节点数据集，根据所选算法使用的不纯性度量（如信息增益、增益率、基尼指数等），从可用特征中选择一个最佳特征，将当前节点的数据集划分为更纯的子集。（3）节点分裂与树生长根据所选特征的取值创建分支，每个分支形成一个子节点。对每个子节点递归地重复步骤（2），使用其对应的数据子集和剩余特征继续划分。（4）停止分裂与标记叶节点当满足以下任一停止条件时，当前节点停止分裂，成为叶节点。1）节点上的样本属于同一类别2）没有可用属性，或属性取值相同3）样本数量少于预定阈值。4）达到预设树的最大深度5）划分带来的“纯度”提升小于阈值。（5）剪枝对初始决策树剪枝，以解决过拟合问题。有先剪枝和后剪枝两种剪枝方法。（6）模型评估使用测试集数据，评估最终决策树模型的分类性能。常用指标包括：准确率、精确率、召回率、F1度量、AUC等。（7）超参数调优根据评估结果，调整模型构建时的超参数（如树的最大深度、最小分裂样本数、剪枝标准等），通过交叉验证寻找最优配置，确立泛化性能最好的决策树模型。第二阶段：模型应用。这个阶段的任务是使用第一阶段已构建的决策树模型对新样本分类，即对于一个未知样本，从树的根节点开始，根据其有关属性的取值，沿着对应的分支向下遍历决策树，直到到达某个叶节点。该叶节点所代表的类别即为模型对该未知样本预测的类别。习题2：（1）计算训练集关于类别的熵。记训练数据集为D，Entropy（2）计算属性x1、x2的信息增益。Gain=≈Gain=≈（3）对连续属性x3，计算所有可能的划分的信息增益。按x31.03.04.05.06.07.08.0+-+-,-++,--最好的分割点可能在2.0、3.5、4.5、5.5、6.5、7.5处取到，下面计算每个分割点对应的信息增益：Gain=≈0.14269bit同理可得：GainD,xGainD,Gain可见，2.0为分割点时信息增益最大，所以2.0是最好的分割点。（4）根据信息增益，找出x1、x2、x3中的最佳划分。比较(3)中GainD,x1、GainD,x2和GainD,x3,2.0的数值，TTF+:1-:4x+:3-:1（5）如果用基尼指数作为不纯性的度量，哪个划分是x1、x2、x3中的最佳划分。计算属性x1、x2、x3作为分裂属性时子节点的基尼指数GGGGiniD,x1、GiniD,x2和GiniD,x3,2.0的数值，GiniD习题3：计算属性x1、x2、x3作为分裂属性时子节点的信息增益率：GGGGiniRatioD,xxxx+:3-:5x+:1-:0同理，对沿右侧分支下来的8个样本重复上述计算，选择最佳分裂。习题4：（1）使用乐观方法计算决策树的泛化错误率。训练误差可提供对泛化误差的乐观估计。将图5.37中的训练样本依此提交图中的决策树，分别得到类标号：+，+，-，-，-，-，-，+，-，-。对照可得训练误差率=0.30，所以泛化错误率的乐观估计为0.30。（2）使用悲观方法计算决策树的泛化错误率，罚项因子取0.5。悲观误差估计是指结合模型复杂度，使用训练误差与模型复杂度罚项的和作为泛化误差的估计。即泛化错误率的悲观估计为：0.3+（3）使用测试集计算决策树的泛化错误率。这种方法叫作降低误差剪枝。将测试样本依此提交决策树，分别得到类标号：+，-，-，+，-，对照可得泛化误差为：+0+01011B-AC-+0训练集实例编号ABC类别1000+2001+3010+4011-5100+6100+7110-8101+9110-10110-测试集实例编号ABC类别11000+12011+13110+14101-15100+图5.37习题4的决策树和数据集习题5：（1）R=S=3+2+5+6+6+5=27（2）M习题6：表4.26比较决策树T1和T2的测试准确率数据集准确率T1T2A0.860.97B0.840.77（1）分析：T1在训练集A上准确率为0.86，T2在A上为0.97，即T2几乎完全拟合了训练集，T1拟合适中。测试集B上的准确率：T1为0.84，T2为0.77，即T2的准确率下降明显，说明过拟合训练集。而T1在测试集B上的准确率几乎和训练集一致，说明泛化能力更好。总之，T1在未知实例（测试集B）上的性能更好，而T2过拟合了训练集，泛化能力较差。（2）分析：在（A+B）上测试，T1的准确率为0.85，T2的准确率为0.87，虽然T2在整体数据集上准确率略高，但注意到（A+B）是已知数据，相当于在训练集与测试集混合之后的数据集上进行测试，复杂度更高的T2的过拟合可能掩盖了泛化性能不足的问题。从小样本测试（AvsB）来看，T2在未知数据上准确率低（0.77），表明泛化能力比T1差，T1训练-测试差异小，说明性能稳定，泛化可靠。综合考虑：仍应选择T1进行分类，因为它在未知实例上更稳健，泛化能力更强。虽然T2在整体准确率稍高，但这是在已知数据上计算的结果，可能受到过拟合的影响。习题7：表4.27习题6的数据集x0.53.04.54.64.95.25.35.57.09.5y--+++--+--（1）数据点x=5.0与表5.30中的各数据点（自左向右依此记为x1,x2,…,x10）之间的欧几里得距离依次为：4.5,2.0,0.5,0.4,0.1,0.2,0.3,0.5,2.0,4.5。k取1时，x=5.0的最近邻是x5=4.9，由此判断其类别号为+。k取3时，x=5.0的3个最近邻是x5=4.9，x6=5.2，x7=5.3，由此判断其类别号为-。k取5时，x=5.0的5个最近邻是x5=4.9，x6=5.2，x7=5.3，x4=4.6，x3=4.5，按多数类标号判断其类别号为+。k取9时，x=5.0的9个最近邻是x5=4.9，x6=5.2，x7=5.3，x4=4.6，x3=4.5，x8=5.5，x2=3.0，x9=7.0，x1=0.5按多数类标号判断其类别号为-。（2）距离加权表决法（Distance-WeightedVoting）是k-最近邻（k-NN）算法的一种改进方法。在标准的k-NN中，所有最近邻的投票权重相同，分类结果由简单多数投票决定。而距离加权表决法，则根据每个最近邻与待分类点之间的距离来分配投票权重，使距离更近的邻居对分类结果的影响更大。对于每个近邻，根据距离分配权重。通常权重是距离的递减函数，这里选则wi=1/di（i=1,2,…,10）。对于每个类别，将属于该类别的所有最近邻的权重相加，得到该类别的总权重。最后将待分类数据点指派到总权重最大的类别。利用（1）中所计算的x=5.0与每个点的距离，得到如下权重：w5=10，w6=5，w7=3.33，w4=2.5，w3=2，w8=2，w2=0.5，w9=0.5，w1=0.22，w10=0.22。对每个k值，计算正类（+）和负类（-）的权重和：k=1时，x5（+）对应的w5=10，正类权重和10，负类权重和0，故分类结果为+k=3时，x5（+）对应的w5=10，x6（-）对应的权重w6=5，x7（-）对应的权重w6=3.33。正类权重和为10，负类权重和为8.33，正类胜出，故分类结果为+k=5时，同理可得：正类权重和为10+2.5+2=14.5，负类权重和为5+3.33=8.33，正类胜出，故分类结果为+同理可得，k=9时，仍然正类胜出，分类结果为+因此，使用距离加权表决法时，对于k=1,3,5,9时，分类结果均为+习题8：（1）朴素贝叶斯分类器的核心是贝叶斯定理，算法通过贝叶斯公式计算样本属于某个类别的后验概率，然后据此进行分类。贝叶斯定理公式为：P目标：对于给定的样本属性集X，找到使后验概率P(Y∣由于P(X)（2）类条件独立性（关键假设）：假设样本的所有属性在给定类别条件下是相互独立的，即：P该假设简化了联合概率P(X∣虽然现实中属性往往相关，但该假设使得模型计算高效且在许多场景（尤其是文本分类）中效果良好。习题9：在二分类问题中，如果正负样本数量差异很大（如欺诈交易很少，正常交易很多），普通分类器很可能会偏向多数类，导致少数类（欺诈）预测准确率低。（1）处理类别不平衡常用方法包括：数据层面方法和算法层面的方法。数据层面方法包括：过采样和欠采样等。过采样增加少数类样本数量，通过合成新样本来平衡类别；欠采样减少多数类样本数量，避免模型被多数类主导。算法层面方法包括：调整分类器权重、调整分类阈值和特殊算法设计等。调整分类器权重通过给少数类样本分配更高权重，让模型在训练时更关注欺诈样本；调整分类阈值在模型输出概率后，不按0.5划分类别，而是使用对少数类更敏感的阈值；特殊算法设计使用专门处理不平衡数据的算法，如集成方法（Boosting、Bagging）等。处理类别不平衡数据时，评估指标的选择也要考虑。不能只看准确率（Accuracy），因为在严重不平衡下，大部分样本属于多数类，准确率可能很高，但少数类完全被错误预测。通常综合精度（Precision）、召回率（Recall）、F1-score、AUC-ROC等指标衡量模型在少数类上的表现。（2）构造高质量信用卡欺诈分类器的方法假设银行有大量非欺诈交易和少量欺诈交易的数据集。数据预处理：可以先对非欺诈样本做

欠采样

或对欺诈样本做

过采样（SMOTE），得到平衡训练集。保留原始比例的测试集，用于真实性能评估。算法选择与调整：选择对不平衡数据鲁棒的算法，如随机森林等。在训练时设置类别权重，让模型更关注欺诈样本。阈值与评估：调整分类阈值以增加对欺诈的召回率，同时监控精度，避免误报太高。使用AUC-ROC或F1-score作为主要评估指标。模型验证：使用交叉验证保证模型泛化能力。避免模型只在训练集上表现好（过拟合多数类）。总之，通过数据平衡+权重调整+精确评估指标，可以构建既能捕捉少数欺诈交易，又能控制误报的高质量分类器。习题10：向前传播工作原理：1)前向传播过程中，输入数据首先进入输入层，然后通过权重和偏置传递到隐藏层，隐藏层中的节点对输入进行加权求和，并通过激活函数进行非线性转换，最后输出层接收到经过隐藏层处理的信号，并产生最终的输出。2)激活函数的作用是在网络中引入非线性，使得网络能够学习和模拟复杂的函数映射。常见的激活函数包括Sigmoid、Tanh、ReLU等。3)权重是连接输入层和隐藏层、隐藏层和输出层的连接强度，偏置是加在输入上的一个常数，用于调整激活函数的输出。后向传播工作原理：1)定义一个损失函数来衡量模型预测值与实际值之间的差异，常见的损失函数包括均方误差（MSE）、交叉熵损失等。2)在训练过程中反向传播计算损失函数关于权重的梯度。3)使用梯度下降或其变体（如Adam、RMSprop等）更新权重和偏置，以最小化损失函数。习题11：单层神经网络（感知机）由一个输入层、一个输出层和一个激活函数组成。在输入层和输出层之间没有其他层，只能够实现线性分类，线性分类是指可以使用一条直线将数据点分成两类的分类方法。然而，异或问题是一个非线性分类问题，因此单层神经网络无法解决，由于异或问题的数据点无法通过一条直线进行完美分割。对于异或问题，需要引入多层神经网络，以解决非线性分类问题，多层神经网络具有多个隐藏层，每个隐藏层都可以学习并提取不同的特征，从而更好地解决复杂的分类问题。通过引入隐藏层，神经网络可以学习到更复杂的特征组合，并且可以通过多个非线性变换来逼近异或问题的决策边界。习题12：SVM的超平面仅由支持向量决定，而非全部样本，超平面的表达式为，其中参数和的优化完全依赖于支持向量，这些样本是临界样本，直接决定了间隔的大小和超平面的位置。这种“少数样本决定模型”的特性，使得噪声点（尤其是靠近分类边界的噪声）极易成为支持向量，进而直接扭曲超平面的位置和方向。若数据中存在噪声，硬间隔SVM会因无法满足“所有样本正确分类”的约束，导致无法找到有效超平面。为处理噪声和线性不可分问题，软间隔SVM引入了松弛变量和惩罚参数C，但软间隔仍无法完全解决噪声敏感问题，若C过大，对噪声点的惩罚严厉，模型会强制将噪声点“拉回”间隔外，导致超平面被噪声点严重扭曲。若C过小，对噪声点的惩罚宽松，模型允许大量样本违反间隔，导致超平面过于“迁就”噪声，间隔缩小甚至分类边界模糊，模型欠拟合。习题13：SVM是一种二类分类模型。它的基本模型是在特征空间中寻找间隔最大化的分离超平面的线性分类器。当训练样本线性可分时，通过硬间隔最大化，学习一个线性分类器，即线性可分支持向量机；当训练数据近似线性可分时，引入松弛变量，通过软间隔最大化，学习一个线性分类器，即线性支持向量机；当训练数据线性不可分时，通过使用核技巧及软间隔最大化，学习非线性支持向量机。SVM的数学原理可以概括为：构建优化问题，找到一个能够最大化间隔的超平面；引入拉格朗日乘子，将优化问题转换为对偶问题，以便于求解；求解对偶问题，通过求解对偶问题得到权重向量和偏置；引入核函数，对于线性不可分的数据，通过核函数将数据映射到高维空间。习题14：决策树的训练过程中，最耗时的步骤是节点分裂，对于每个内部节点，需要遍历所有可用特征，对每个特征尝试所有可能的分裂点，并通过计算分裂增益选择“最优分裂