数据挖掘期末考试计算题及答案

数据挖掘期末考试计算题及答案一、关联规则挖掘（Apriori算法）某超市记录了100条顾客购物事务数据（部分事务如下表），项集包含商品：牛奶（M）、面包（B）、鸡蛋（E）、水果（F）、饮料（D）。假设最小支持度为30%（即支持计数≥30），最小置信度为60%。事务ID购买商品T1M,B,ET2M,B,DT3B,E,FT4M,B,E,FT5M,B,DT6B,E,FT7M,B,ET8M,DT9B,E,FT10M,B,E,D......T100M,B,E（注：为简化计算，假设T1-T100中，各商品组合出现的频率如下：M出现70次，B出现80次，E出现65次，F出现45次，D出现50次；MB出现60次，ME出现55次，BE出现50次，MF出现35次，MD出现40次，BF出现38次，BD出现32次，EF出现42次；MBE出现45次，MBF出现30次，MBD出现35次，BEF出现33次；MBEF出现25次。）问题1：计算所有频繁项集（支持度≥30%）。问题2：从最大频繁项集中提供所有可能的关联规则，并筛选置信度≥60%的强关联规则。解答1：频繁项集计算1.1-项集（L1）：支持计数≥30的项：M（70）、B（80）、E（65）、F（45）、D（50）。因此，L1={M,B,E,F,D}。2.2-项集（C2→L2）：候选2-项集C2由L1中项两两组合提供，共C(5,2)=10个。计算各候选的支持计数：MB（60）、ME（55）、BE（50）、MF（35）、MD（40）、BF（38）、BD（32）、EF（42）、MF（35）、DF（假设支持计数28，<30）。支持计数≥30的项集：MB（60）、ME（55）、BE（50）、MF（35）、MD（40）、BF（38）、EF（42）。因此，L2={MB,ME,BE,MF,MD,BF,EF}。3.3-项集（C3→L3）：C3由L2中项集通过连接步（前k-1项相同）和剪枝步（所有子集属于L2）提供。MB与ME连接得MBE（子集MB、ME、BE均属于L2），支持计数45≥30；MB与MF连接得MBF（子集MB、MF、BF均属于L2），支持计数30≥30；MB与MD连接得MBD（子集MB、MD、BD（BD支持计数32≥30）均属于L2），支持计数35≥30；BE与BF连接得BEF（子集BE、BF、EF均属于L2），支持计数33≥30；其他组合（如ME与MF）的子集可能包含非频繁项集（如EF虽频繁，但MEF的子集MF、ME、EF均频繁，需计算支持计数，假设MEF支持计数28<30，被剪枝）。因此，L3={MBE,MBF,MBD,BEF}。4.4-项集（C4→L4）：C4由L3中项集连接提供，如MBE与MBF连接得MBEF（子集MBE、MBF、BEF、MBF中的MBE、MBF、BEF、MBF的子集均属于L3），支持计数25<30（最小支持度30），因此L4为空。综上，所有频繁项集为：L1={M,B,E,F,D}；L2={MB,ME,BE,MF,MD,BF,EF}；L3={MBE,MBF,MBD,BEF}。解答2：强关联规则提供最大频繁项集为L3（3-项集），以MBE（支持计数45）为例，可能的规则：MBE→空（无意义）；单前件规则：M→BE，B→ME，E→MB；双前件规则：MB→E，ME→B，BE→M。计算各规则的置信度（置信度=支持计数(前件∪后件)/支持计数(前件)）：1.单前件规则：M→BE：支持计数(MBE)=45，支持计数(M)=70→置信度=45/70≈64.29%≥60%；B→ME：支持计数(MBE)=45，支持计数(B)=80→置信度=45/80=56.25%<60%（淘汰）；E→MB：支持计数(MBE)=45，支持计数(E)=65→置信度=45/65≈69.23%≥60%。2.双前件规则：MB→E：支持计数(MBE)=45，支持计数(MB)=60→置信度=45/60=75%≥60%；ME→B：支持计数(MBE)=45，支持计数(ME)=55→置信度=45/55≈81.82%≥60%；BE→M：支持计数(MBE)=45，支持计数(BE)=50→置信度=45/50=90%≥60%。同理，对L3中其他项集（如MBF、MBD、BEF）进行类似计算，最终强关联规则包括（仅列部分）：M→BE（置信度64.29%）；E→MB（置信度69.23%）；MB→E（置信度75%）；ME→B（置信度81.82%）；BE→M（置信度90%）；（其他项集提供的规则如MB→F（MBF支持计数30，MB支持计数60，置信度30/60=50%<60%，淘汰）等）。二、决策树分类（ID3算法）某高校记录了100名学生的课程学习数据，属性包括：出勤率（高：≥80%；中：60%-79%；低：<60%）；作业完成率（高：≥90%；中：70%-89%；低：<70%）；实验成绩（合格、不合格）；类别标签为“是否通过考试”（是、否）。部分数据统计如下（总样本100）：类别分布：通过（70）、未通过（30）；出勤率为“高”的样本50个，其中通过45个，未通过5个；出勤率为“中”的样本30个，其中通过20个，未通过10个；出勤率为“低”的样本20个，其中通过5个，未通过15个；作业完成率为“高”的样本40个，其中通过35个，未通过5个；作业完成率为“中”的样本40个，其中通过25个，未通过15个；作业完成率为“低”的样本20个，其中通过10个，未通过10个；实验成绩“合格”的样本70个，其中通过60个，未通过10个；实验成绩“不合格”的样本30个，其中通过10个，未通过20个。问题：计算各属性的信息增益（InformationGain），并确定根节点应选择哪个属性。解答：信息增益计算公式：IG其中，En1.原始数据集的信息熵（Entropy(S)）：p(是)En2.出勤率（A）的信息增益：出勤率“高”（S1，50个样本）：p(是)En出勤率“中”（S2，30个样本）：p(是)En出勤率“低”（S3，20个样本）：p(是)En条件熵H(信息增益IG3.作业完成率（H）的信息增益：作业“高”（S1，40个样本）：p(是)En作业“中”（S2，40个样本）：p(是)En作业“低”（S3，20个样本）：p(是)En条件熵H(信息增益IG4.实验成绩（E）的信息增益：实验“合格”（S1，70个样本）：p(是)En实验“不合格”（S2，30个样本）：p(是)En条件熵H(信息增益IG结论：出勤率的信息增益（0.2310）最大，因此根节点应选择“出勤率”属性。三、K-means聚类算法给定二维数据集D={(2,5),(3,4),(5,6),(7,8),(9,10),(1,2),(4,3),(6,7),(8,9),(10,11)}，要求使用K-means算法（K=2）聚类，初始质心为μ1=(3,4)和μ2=(7,8)。问题：迭代两次，输出每次迭代后的簇划分和质心坐标（保留2位小数）。解答：K-means步骤：计算样本到质心的欧氏距离，分配到最近簇，更新质心。第一次迭代：1.计算各样本到μ1=(3,4)和μ2=(7,8)的距离：(2,5)：d1=√[(2-3)²+(5-4)²]=√2≈1.41，d2=√[(2-7)²+(5-8)²]=√34≈5.83→簇1；(3,4)：d1=0，d2=√[(3-7)²+(4-8)²]=√32≈5.66→簇1；(5,6)：d1=√[(5-3)²+(6-4)²]=√8≈2.83，d2=√[(5-7)²+(6-8)²]=√8≈2.83→随机分配（假设分配簇1）；(7,8)：d1=√[(7-3)²+(8-4)²]=√32≈5.66，d2=0→簇2；(9,10)：d1=√[(9-3)²+(10-4)²]=√72≈8.49，d2=√[(9-7)²+(10-8)²]=√8≈2.83→簇2；(1,2)：d1=√[(1-3)²+(2-4)²]=√8≈2.83，d2=√[(1-7)²+(2-8)²]=√72≈8.49→簇1；(4,3)：d1=√[(4-3)²+(3-4)²]=√2≈1.41，d2=√[(4-7)²+(3-8)²]=√34≈5.83→簇1；(6,7)：d1=√[(6-3)²+(7-4)²]=√18≈4.24，d2=√[(6-7)²+(7-8)²]=√2≈1.41→簇2；(8,9)：d1=√[(8-3)²+(9-4)²]=√50≈7.07，d2=√[(8-7)²+(9-8)²]=√2≈1.41→簇2；(10,11)：d1=√[(10-3)²+(11-4)²]=√98≈9.90，d2=√[(10-7)²+(11-8)²]=√18≈4.24→簇2。簇1样本：(2,5),(3,4),(5,6),(1,2),(4,3)（共5个）；簇2样本：(7,8),(9,10),(6,7),(8,9),(10,11)（共5个）。2.更新质心：μ1新：x=(2+3+5+1+4)/5=15/5=3.00，y=(5+4+6+2+3)/5=20/5=4.00→μ1=(3.00,4.00)；μ2新：x=(7+9+6+8+10)/5=40/5=8.00，y=(8+10+7+9+11)/5=45/5=9.00→μ2=(8.00,9.00)。第二次迭代：1.计算各样本到新质心μ1=(3.00,4.00)和μ2=(8.00,9.00)的距离：(2,5)：d1=√[(2-3)²+(5-4)²]=√2≈1.41，d2=√[(2-8)²+(5-9)²]=√52≈7.21→簇1；(3,4)：d1=0，d2=√[(3-8)²+(4-9)²]=√50≈7.07→簇1；(5,6)：d1=√[(5-3)²+(6-4)²]=√8≈2.83，d2=√[(5-8)²+(6-9)²]=√18≈4.24→簇1；(1,2)：d1=√[(1-3)²+(2-4)²]=√8≈2.83，d2=√[(1-8)²+(2-9)²]=√98≈9.90→簇1；(4,3)：d1=√[(4-3)²+(3-4)²]=√2≈1.41，d2=√[(4-8)²+(3-9)²]=√52≈7.21→簇1；(7,8)：d1=√[(7-3)²+(8-4)²]=√32≈5.66，d2=√[(7-8)²+(8-9)²]=√2≈1.41→簇2；(9,10)：d1=√[(9-3)²+(10-4)²]=√72≈8.49，d2=√[(9-8)²+(10-9)²]=√2≈1.41→簇2；(6,7)：d1=√[(6-3)²+(7-4)²]=√18≈4.24，d2=√[(6-8)²+(7-9)²]=√8≈2.83→簇2；(8,9)：d1=√[(8-3)²+(9-4)²]=√50≈7.07，d2=√[(8-8)²+(9-9)²]=0→簇2；(10,11)：d1=√[(10-3)²+(11-4)²]=√98≈9.90，d2=√[(10-8)²+(11-9)²]=√8≈2.83→簇2。簇1样本不变：(2,5),(3,4),(5,6),(1,2),(4,3)；簇2样本不变：(7,8),(9,10),(6,7),(8,9),(10,11)。2.更新质心（与第一次迭代后相同，算法收敛）：μ1=(3.00,4.00)，μ2=(8.00,9.00)。四、数据预处理与异常检测某电商用户数据集包含以下字段（部分数据）：用户ID年龄（岁）月收入（元）购物频率（次/月）U12580005U230120003U3缺失90004U428缺失6U535150002U62270007U740缺失1U8缺失100005问题1：使用均值填充法处理年龄和月收入的缺失值（保留整数）。问题2：对填充后的年龄和月收入进行Z-score标准化（保留2位小数）。问题3：假设购物频率服从正态分布，使用Z-score方法（阈值±3σ）检测异常值。解答1：缺失值填充1.年龄填充：非缺失年龄值：25,30,28,35,22,40→均值=(25+30+28+35+22+40)/6=180/6=30岁。缺失年龄（U3、U8）填充为30岁。2.月收入填充：非缺失收入值：8000,12000,9000,15000,7000,10000→均值=(8000+12000+9000+15000+7000+10000)/6=61000/6≈10167元（保留整数为10167）。缺失收入（U4、U7）填充为10167元。填充后数据集：用户ID年龄月收入购物频率U12580005U230120003U33090004U428101676U535150002U62270007U740101671U830100005解答2：Z-score标准化Z-score公式：z=1.年龄标准化：均值μ_age=(25+30+30+28+35+22+40+30)/8=240/8=30；标准差σ_age=√[((25-30)²+(30-30)²+...+(30-30)²)/8]=√[(25+0+0+4+25+64+100+0)/8]=√[218/8]≈√27.25≈5.22；标准化后年龄：U1:(25-30)/5.22≈-0.96；U2:0/5.22=0.00；U3:0.00；U4:(28-30)/5.22≈-0.38；U5:(35-30)/5.22≈0.96；U6:(22-30)/5.22≈-1.53；U7:(40-30)/5.22≈1.92；U8:0.00。2.月收入标准化：均值μ_income=(8000+12000+9000+10167+15000+7000+10167+10000)/8=81334/8≈10167；标准差σ_income=√[((8000-10167)²+...+(10000-10167)²)/8]=√[(4700889+3356889+1361889+0+23238889+9908889+0+27889)/8]≈√[(4700889+3356889=8057778;+1361889=9419667;+23238889=32658556;+9908889=42567445;+27889=42595334)/8]≈√[42595334/8]≈√5324416.75≈2307.47；标准化