2025年数据挖掘(关联规则挖掘)试卷及答案

2025年数据挖掘(关联规则挖掘)试卷及答案1.单项选择题（每题2分，共20分）1.1在Apriori算法中，若频繁k项集Lk非空，则任意(k+1)项集要成为候选(k+1)项集Ck+1，其所有k子集必须满足A.支持度≥min_supB.支持度<min_supC.在Lk中D.在Ck中答案：C1.2给定事务数据库，min_sup=30%，min_conf=70%。规则{牛奶}→{面包}的支持度计数为120，事务总数为400，则该规则的置信度为A.30%B.70%C.75%D.无法确定答案：D（缺少{牛奶}的计数）1.3下列度量中，对“偶然共存”最不敏感的是A.提升度B.χ²C.全置信度allconfidenceD.余弦度量答案：C1.4FPGrowth相比Apriori的最大优势是A.无需多次扫描数据库B.支持并行化C.可处理高维稀疏数据D.天然支持数据流答案：A1.5在垂直数据格式中，项集的支持度计数通过A.事务表扫描B.Tidlist交集长度C.Hash树遍历D.Bitmap与操作答案：B1.6ECLAT算法采用何种策略生成候选项集A.自连接B.深度优先搜索C.交集D.前缀树答案：C1.7若规则A→B的lift=1.2，则A.A与B负相关B.A与B独立C.A与B正相关D.无法判断答案：C1.8在MSApriori中，若项i的最低支持度阈值为0.1，项j为0.2，则项集{i,j}的最低支持度为A.0.1B.0.2C.0.3D.min(0.1,0.2)答案：A1.9下列哪项技术可直接用于挖掘负关联规则A.AprioriInverseB.FPGrowthC.ECLATD.SON答案：A1.10在MapReduce框架下，Apriori的哪一步最适合放在Reducer端A.候选生成B.支持度计数C.频繁项集筛选D.自连接答案：C2.多项选择题（每题3分，共15分，多选少选均不得分）2.1下列哪些操作会降低Apriori的I/O开销A.事务压缩B.划分C.抽样D.Hash桶剪枝答案：ABD2.2关于闭频繁项集，正确的有A.闭项集的直接超集支持度必小于它B.闭项集可无损还原所有频繁项集C.闭项集数量≤频繁项集数量D.最大频繁项集一定是闭项集答案：ABC2.3下列哪些度量具有“零不变性”A.置信度B.KulczynskiC.余弦D.提升度答案：BC2.4在数据流关联规则挖掘中，面临的主要挑战有A.单遍扫描限制B.概念漂移C.内存受限D.事务长度固定答案：ABC2.5下列哪些算法采用位图压缩事务数据库A.MAFIAB.CharmC.FPGrowthD.Relim答案：AB3.填空题（每空2分，共20分）3.1Apriori性质：若项集频繁，则其所有________必频繁。答案：子集3.2给定事务总数|D|=1000，项集X的支持度计数为150，则support(X)=________。答案：0.153.3规则A→B的conviction计算公式为________。答案：(1−support(B))/(1−confidence(A→B))3.4FPTree的头表作用是为________提供快速访问路径。答案：相同项的节点链表3.5在垂直格式中，若项A的Tidlist为{1,3,5}，项B为{2,3,5,6}，则support({A,B})=________。答案：23.6若项集X的闭包c(X)=X，则X称为________。答案：闭项集3.7在MSApriori排序策略中，项按________升序排列。答案：MIS（最小项支持度）3.8采用Diffset优化后，Charm算法将Tidlist替换为________。答案：差集3.9在稠密数据库中，最大频繁项集挖掘常用________剪枝策略。答案：超集等价3.10若规则A→B的leverage=0.05，则其绝对支持度增益为________。答案：0.05×|D|4.判断题（每题1分，共10分，正确打“√”，错误打“×”）4.1Apriori的候选生成过程保证不重复且完备。答案：√4.2提升度大于1一定意味着因果性。答案：×4.3FPGrowth的压缩率与事务排序方式无关。答案：×4.4闭频繁项集的数量可能等于最大频繁项集数量。答案：√4.5在负关联规则中，支持度可定义为sup(¬A∪B)。答案：√4.6ECLAT对稀疏数据效率低于FPGrowth。答案：√4.7置信度满足反单调性。答案：×4.8使用Hash树进行支持度计数时，桶内计数可直接剪枝。答案：√4.9SON算法要求两次扫描即可得到精确结果。答案：√4.10在数据流中，衰减窗口模型比滑动窗口更节省内存。答案：√5.简答题（每题8分，共24分）5.1封闭型：阐述Apriori算法中“自连接”步骤的输入、输出及剪枝条件，并给出伪代码。答案：输入：频繁k项集Lk输出：候选(k+1)项集Ck+1步骤：1.对Lk中任意两项p,q，若前(k−1)项相同且第k项字典序p[k]<q[k]，则连接生成(k+1)项集c=p∪q2.剪枝：若c的任意k子集不在Lk中，则从Ck+1删除伪代码：foreachp∈Lkforeachq∈Lkifp[1..k1]=q[1..k1]andp[k]<q[k]thenc=p∪qif∀s⊂c,|s|=k→s∈LkthenaddctoCk+15.2开放型：解释为何在高维稀疏数据中，最大频繁项集挖掘可能丢失有用规则，并提出一种改进思路。答案：最大频繁项集仅保留最长频繁项集，导致其所有子集的支持度信息丢失，无法计算置信度、提升度等度量，从而无法评估规则强度。改进思路：在挖掘最大项集的同时，维护一个“支持度摘要”结构，如使用近似计数Sketch或Bloom过滤器，记录各子集的近似支持度，使得后续规则生成阶段仍能快速估算度量值，兼顾内存与精度。5.3封闭型：给出FPGrowth中“条件模式基”的定义，并举例说明其构建过程。答案：定义：以某个项为后缀，在FPTree中收集所有包含该项的前缀路径，形成投影数据库，每条路径的支持度为路径末端节点计数的总和。例：对下表事务（min_sup=2）：T1:a,b,cT2:a,b,dT3:a,c,dFPTree构建后，对项d的条件模式基为：路径1:a:1,b:1支持度1路径2:a:1,c:1支持度1合并相同前缀得：a:2（支持度2），进一步构建条件FPTree，可挖掘出频繁项集{a,d}。6.计算与分析题（共41分）6.1基础计算（10分）给定事务数据库：T1:{A,B,C}T2:{A,B,D}T3:{A,C,D}T4:{B,C,D}T5:{A,B,C,D}min_sup=2，min_conf=70%(1)列出所有频繁1项集及其支持度计数；(2)使用Apriori生成频繁2项集；(3)列出所有满足min_conf的2项规则并给出置信度。答案：(1)A:4,B:4,C:4,D:4(2)C2:{A,B}:3,{A,C}:3,{A,D}:3,{B,C}:3,{B,D}:3,{C,D}:3→全部频繁(3)规则及置信度：A→B:3/4=75%B→A:3/4=75%A→C:3/4=75%C→A:3/4=75%A→D:3/4=75%D→A:3/4=75%B→C:3/4=75%C→B:3/4=75%B→D:3/4=75%D→B:3/4=75%C→D:3/4=75%D→C:3/4=75%共12条规则均满足≥70%。6.2FPTree构建与挖掘（11分）事务同上，按支持度降序排序，构建全局FPTree，画出结构图并给出节点计数；然后挖掘以D为后缀的频繁项集。答案：排序：A,B,C,D均4次，字典序A<B<C<DFPTree：root→A:4A→B:3A→C:1B→C:2C→D:2B→D:1A→D:1条件模式基（D）：路径1:A:1,B:1,C:1支持度1路径2:A:1,B:1支持度1路径3:A:1,C:1支持度1合并：A:3,B:2,C:2条件FPTree：A:3→B:2→C:2挖掘得：{A,D}:3,{B,D}:2,{C,D}:2,{A,B,D}:2,{A,C,D}:2,{B,C,D}:2,{A,B,C,D}:2其中支持度≥2的频繁项集：{A,D}:3,{B,D}:2,{C,D}:2,{A,B,D}:2,{A,C,D}:2,{B,C,D}:2,{A,B,C,D}:26.3垂直格式与ECLAT（10分）将上述数据库转为垂直格式，给出Tidlist；使用ECLAT深度优先搜索，按字典序生成所有频繁3项集，写出交集过程及最终列表。答案：垂直格式：A:{1,2,3,5}B:{1,2,4,5}C:{1,3,4,5}D:{2,3,4,5}深度优先：从A开始：A∩B={1,2,5}→sup=3→频繁A∩B∩C={1,5}→sup=2→频繁A∩B∩D={2,5}→sup=2→频繁A∩C∩D={3,5}→sup=2→频繁B∩C∩D={4,5}→sup=2→频繁最终频繁3项集：{A,B,C}:2,{A,B,D}:2,{A,C,D}:2,{B,C,D}:26.4综合应用：超市购物篮优化（10分）某连锁超市拥有1亿条购物篮记录，平均事务长度12项，项空间20000。现需每周更新关联规则，要求：(1)内存峰值<8GB；(2)单次扫描完成；(3)结果误差<5%。设计一套基于抽样+Sketch的解决方案，说明抽样比例、Sketch结构、误差控制方法及规则生成流程。答案：方案：1.抽样：采用两阶段抽样，先按门店分层随机抽取10%交易，约1000万条，内存约12项×4字节×10M≈480MB。2.构建CountMinSketch：宽度w=2²⁴（16M桶），深度d=7，占用内存16M×7×4字节≈448MB，可保证支持度计数误差ε=1/w≈0.06%，置信度1−δ=(1−1/e^d)>99.9%。3.单遍扫描抽样数据，更新Sketch，同