简介面向正在学习Coursera“数据挖掘中的模式发现”课程的学员这份压缩包收录了与课程测验配套的代码与说明文档。资源共4个文件包括2个Python脚本、1个R脚本及1个Markdown说明整体仅2KB体量虽小却覆盖了quiz1、quiz3和quiz2的作业实现方便对照练习与查漏补缺。已有108人学习下载适合希望巩固数据挖掘原理、熟悉编程实现细节的初中级学习者。通过阅读代码可了解如何使用Python完成数据清洗、特征处理、聚类与分类等环节同时借助R脚本对比不同语言在模式发现任务中的写法进一步掌握从原始数据中提取关联规则、发现潜在模式的完整思路。对于正在完成该课程作业或备战数据挖掘相关面试的读者这份资源能提供直接可运行的参考样例帮助快速定位常见实现问题提升学习效率。1. 拿到「数据挖掘中的模式发现」课程代码包先分清作业代码和评测脚本如果你和我一样是冲着这门课的名头去下载代码包的大概率会经历一个“翻车”瞬间解压之后发现目录里躺着十来个文件名带given、student、grader的 Python 文件和几个不认识的.txt数据集直接跑python main.py根本跑不起来连入口在哪都得找半天。这套代码包对应的正是这门公开课里“模式发现”专题的课后编程作业涉及频繁项集挖掘典型的是 Apriori和序列模式挖掘典型的是 PrefixSpan全部用 Python 实现自带评测脚本和玩具数据集。它解决的不只是“作业怎么写”而是让你能在本地完整走一遍从数据载入、模式挖掘到评测打分的闭环。适合刚学完数据挖掘理论、想动手验证一遍算法细节的从业者和学生也适合需要一份能直接改造成实验框架的代码底子的人。2. 代码包目录与运行入口三条命令跑通核心流程2.1 代码包长什么样文件命名里的三层含义我拆过不少课程代码包这套的模式比较有代表性根目录下通常是一堆.py文件和dataset/、output/两个文件夹。.py文件按角色分三类带given_前缀的是课程方提供的参考实现框架函数名和接口已经定死但核心算法留空带student_前缀的是你要补全的文件里面通常有TODO注释剩下的grader_*.py或test_*.py是评测脚本负责读入你的输出并算分。其中output/文件夹一开始是空的所有挖掘结果必须写到这里文件名和行格式都不能改因为评测脚本是按固定路径去读的。你要是自作聪明改了输出文件名评测直接报 “file not found”这个坑我后面会细说。. ├── given_apriori.py # Apriori 算法框架核心部分留空 ├── given_prefixspan.py # PrefixSpan 算法框架 ├── student_apriori.py # 你要补全的 Apriori 实现 ├── student_prefixspan.py # 你要补全的 PrefixSpan 实现 ├── grader_freq.py # 频繁项集评测脚本 ├── grader_seq.py # 序列模式评测脚本 ├── dataset/ │ ├── transactions.txt # 购物篮数据每行一个事务 │ └── sequences.txt # 序列数据SPMF 格式 └── output/ ├── freq_patterns.txt # 待生成的频繁项集输出 └── seq_patterns.txt # 待生成的序列模式输出用find . -name *.py | xargs grep -n TODO可以快速定位所有需要补全的位置。大部分课程的框架代码里都留了函数签名和注释你只需要把算法逻辑填进去。少数版本做得更狠连candidate_gen这种核心函数都要自己从头写那就需要先读given_文件里的函数调用关系。2.2 跑通第一个频繁项集命令、参数与数据格式先把入口和环境摸清。这套代码一般不需要第三方库grader_freq.py里会 importstudent_apriori所以运行评测脚本之前必须先确保student_apriori.py能被 Python 找到且不报语法错误。# 在代码包根目录执行 python grader_freq.py --input dataset/transactions.txt --output output/freq_patterns.txt --min-support 100 # 如果只测试 Apriori 单模块可以直接运行学生文件里的 main python student_apriori.py dataset/transactions.txt --min-support 100 --max-k 3逻辑说明评测脚本先调用你实现的apriori(transactions, min_support)再把返回的频繁项集按照 “项集内用逗号分隔、不同项集换行” 的约定写入指定的output文件。第一个命令是完整流程第二个命令是单模块调试。注意--min-support在不同课程版本里含义不同有的传的是绝对支持度至少出现 100 次有的传的是相对支持度例如 0.01 表示 1%。你需要在student_apriori.py开头打印一下传入参数的类型来判断别想当然。参数说明--max-k不是必须的但调试时建议加上只生成 1-项集和 2-项集跑得快方便核对。事务文件transactions.txt的格式通常是每行一个事务item 之间用空格或逗号分隔。先跑一遍生成输出后再用wc -l output/freq_patterns.txt看行数和评测期望大致对比一下能提前发现支持度阈值理解错的问题。3. 纯 Python 实现 Apriori剪枝循环与输出格式的边界3.1 课程为什么用 Apriori 而不是 FP-Growth公开课选 Apriori 当教学案例不是因为它在工业界性能好而是因为它结构简单、每一步都能打印中间结果方便和理论对照。FP-Growth 用 FP-Tree 压缩存储性能确实好几倍但代码量至少翻倍而且很难在教学场景下把“条件模式基”“条件 FP-Tree”这些概念拆成小块演示。Apriori 的核心就是一句“一个项集频繁它的所有子集必然频繁”的逆否命题候选生成时剪掉有非频繁子集的项集。这正是课程想让你理解的模式发现底层思想。我实际对比过在transactions.txt只有几千到几万行、item 种类几十个的场景下纯 Python Apriori 配合剪枝跑 3-项集和 4-项集也就秒级到分钟级完全够用。真正卡住人的不是性能而是候选项集生成时的去重逻辑和剪枝条件。下面这部分是核心。3.2 候选生成与剪枝的代码骨架下面这段代码是我把课程框架补全后的核心部分注释里标出了最容易写错的两个位置。def candidate_gen(prev_itemsets, k): 由 k-1 频繁项集生成候选 k 项集并做 Apriori 剪枝。 prev_itemsets: list of frozenset每个长度为 k-1 返回值: 剪枝后的候选 k-项集列表 candidates [] n len(prev_itemsets) for i in range(n): for j in range(i 1, n): # 连接步前 k-2 个元素相同且第 k-1 个元素满足大小关系 a list(prev_itemsets[i]) b list(prev_itemsets[j]) # 统一排序这是去重的前提 a.sort() b.sort() if a[:-1] b[:-1] and a[-1] b[-1]: cand frozenset(a [b[-1]]) # 连接生成新项集 # 剪枝步检查所有长度为 k-1 的子集是否都频繁 prune False for subset in itertools.combinations(cand, k - 1): if frozenset(subset) not in prev_itemset_set: prune True break if not prune: candidates.append(cand) # 这一步很关键候选集自身也要去重 return list(set(candidates))逻辑说明连接步的条件a[:-1] b[:-1] and a[-1] b[-1]是 Apriori 算法教科书上的标准写法目的是确保两个(k-1)-项集能拼成一个有序的k-项集而且不会重复拼接。如果不加而用!同一个候选会被生成两次。剪枝步遍历候选的所有(k-1)-子集只要有一个子集不在上一轮的频繁项集集合prev_itemset_set里就说明这个候选不可能频繁直接丢掉。参数说明prev_itemset_set需要提前用set(map(frozenset, prev_itemsets))构建不能用list判断成员否则数据量稍微一大就是 O(n²) 的灾难。排序必须在连接前做因为frozenset本身是无序的a[:-1] b[:-1]全靠排序后的列表保证可比性。这行 sort 不写后面全乱套。3.3 支持度计数的两种实现与阈值单位问题候选生成好了接下来是统计支持度。常见做法是按事务逐项检查候选是否被包含但纯 Python 里更快的做法是倒排索引——对每个 item 记录出现它的事务编号集合然后多个 item 的支持度就是它们的编号集合取交集。def count_support(candidates, transactions, min_sup): 对候选 k-项集做支持度计数返回支持度 min_sup 的项集列表。 # 构建 item - 事务id集合 的倒排索引 item_to_tids defaultdict(set) for tid, trans in enumerate(transactions): for item in trans: item_to_tids[item].add(tid) freq [] for cand in candidates: # 取该候选所有 item 的 tid 集合交集 common_tids None for item in cand: tids item_to_tids[item] common_tids tids if common_tids is None else common_tids tids sup len(common_tids) if sup min_sup: freq.append((cand, sup)) return freq逻辑说明倒排索引一次遍历事务文件就能建好后续每个候选只做集合交集运算比每趟全表扫事务要快一个数量级。common_tids从第一个 item 的 tid 集合开始逐一和后续 item 的 tid 集合取交集交集长度就是该项集的事务支持度。注意min_sup的语义要和评测脚本一致如果评测脚本里是float比如0.01你需要先算事务总数total再用int(min_sup * total)转成绝对支持度如果已经是int直接比较即可。判断阈值类型的代码放在函数开头最保险if isinstance(min_sup, float): min_sup int(min_sup * len(transactions))。支持度阈值调低一档运行时间可能是指数级上升。比如从 100 调到 502-项集数量翻倍3-项集可能翻四倍。课程数据是特意设计的“安全区”但调到太低照样会跑出几十万候选。4. 序列模式挖掘PrefixSpan 的递归实现与三道坎4.1 序列模式比频繁项集难在哪如果你把 Apriori 那一套直接搬到序列数据上会发现三个问题第一序列里的 item 是有顺序的{A, B}和{A → B}是两个完全不同的东西前者是项集、后者是序列第二同一序列中一个 item 可以出现多次比如A → A → B做支持度计数时不能简单用集合交集第三序列模式挖掘产生的候选空间比项集大得多因为不同长度、不同排列都要考虑。所以 PrefixSpan 不走“生成候选”这条路而是用“分治”的思路每次只关注序列的第一个项前缀找所有包含这个前缀的序列把剩余部分作为后缀然后递归挖掘。这种方法不需要显式生成候选内存占用小很多也是课程代码包在序列模式这部分选择它的原因。但代价是递归深度和中间数据集的构建要小心处理不然很容易栈溢出。4.2 投影数据库构建与递归入口PrefixSpan 的核心操作是“构建投影数据库”。下面这段代码是从课程框架里补全的最简版本把 every 序列中匹配前缀之后的元素收集成新序列。def build_projected_db(sequences, prefix_item): projected [] for seq in sequences: # 找前缀第一次出现的位置 pos -1 for i, itemset in enumerate(seq): if prefix_item in itemset: pos i break if pos ! -1: # 后缀从当前元素中移除前缀项再取剩余部分 tail [] for j in range(pos, len(seq)): rest [x for x in seq[j] if x ! prefix_item] if rest: tail.append(rest) if tail: projected.append(tail) return projected逻辑说明这个函数做的事是“给定一个前缀项找到所有包含它的序列并把每个序列中该前缀后面的部分提取出来”。注意pos找的是第一个出现位置因为 PrefixSpan 的投影规则是“从第一次出现开始后续部分都算后缀”。rest里去掉prefix_item是避免递归时重复统计同一个项但后续还会出现在后面的itemset里。比如序列[(A,B), (A,C)]前缀A第一次出现在第一个itemset去掉A后剩(B)后缀就变成[(B), (A,C)]而不是只有(B)。参数说明seq里的每个元素是itemset一个项集itemset本身也是可迭代的。这里用list表示序列、用list of str/int表示项集。如果课程代码里是用tuple记得把x ! prefix_item的过滤逻辑改成列表推导式后转回tuple否则后面append(tail)会报类型错误。构建好投影库后递归就是在每个 projection 上继续找更高频的前缀项直到没有元素达到min_sup。4.3 输出格式与评测脚本的字节级对齐序列模式挖掘写完最容易被扣分的反而不是算法本身而是输出格式。课程的评测脚本通常只做一件事把你输出文件里的每一行和一个标准答案模式库做匹配。匹配规则严格到什么程度呢空格、制表符、结尾换行都算。def write_seq_patterns(patterns, out_path): 把序列模式写入输出文件格式模式 支持度每行一条。 with open(out_path, w) as f: for seq, sup in patterns: # 序列内部用空格分隔项集内用逗号分隔项集间用 -1 分隔 line_parts [] for itemset in seq: line_parts.append(,.join(str(x) for x in itemset)) line -1 .join(line_parts) -2 str(sup) \n f.write(line)逻辑说明这行line -1 .join(...) -2 str(sup)是评测脚本能读懂的约定格式。-1是 SPMF 格式里“项集结束”的标记-2是“序列结束”的标记末尾的支持度是整数。如果你写成str(sup) -1 ...或者漏掉-2评测脚本解析出来的序列就是错的分会很低。这个格式和dataset/sequences.txt里的原始数据格式一致所以最稳妥的办法是先head dataset/sequences.txt看一眼原始格式照着写输出。另一个容易踩的地方是支持度的定义在序列模式里一个前缀模式在某个序列中出现多次只算一次支持度。如果你的实现里把“出现次数”累计进去了计数会偏大评测脚本也会判定为错。5. 复现过程中最常见的五个问题从跑不起来到结果诡异这一章是我把代码包从拿到手到完全跑通的过程中实际遇到或替别人排查过的五类典型问题。每条都按“现象 → 原因 → 解决”来写你照着排查能省不少时间。问题 1运行评测脚本直接报UnicodeDecodeError或FileNotFoundError现象python grader_freq.py ...执行后报错指向读取dataset/transactions.txt时编码错误或者提示文件不存在。原因绝大多数课程数据文件是 UTF-8 编码但个别版本在 Windows 上用记事本另存成了 GBK文件不存在多半是因为你在 Windows 上解压路径分隔符问题或者目录名大小写不一致。我遇到过把dataset解压成DataSet的情况Linux 下大小写敏感直接报错。解决先ls dataset/看实际文件名。读文件时用open(path, r, encodingutf-8)如果报编码错误改成encodinglatin-1或errorsignore临时绕过。路径问题一律在运行命令里写相对路径别写绝对路径。问题 2同一次运行中频繁项集结果比预期多出很多简单项集现象输出文件里出现大量重复项集比如1, 2和2, 1同时存在。原因候选生成时没做排序frozenset无序两个不同顺序的项集在set去重时被当成不同元素。出现这个说明连接步里少了a[-1] b[-1]的约束或者排序写在连接之后。解决在candidate_gen最开头对prev_itemsets里的每个项集先sorted再转list并严格按a[:-1] b[:-1] and a[-1] b[-1]做连接判断。完成后用len(candidates) len(set(candidates))断言加一道保险。问题 3递归深度超出限制RecursionError: maximum recursion depth exceeded现象student_prefixspan.py在运行到某个较深层次时直接崩溃。原因PrefixSpan 递归深度和序列长度成正比课程数据如果序列长度超过 1000默认递归深度 1000 就不够用。也可能你的投影数据库构建有误后缀没被缩短导致递归死循环。解决在脚本入口加sys.setrecursionlimit(10000)临时增加上限但更关键的是查build_projected_db是不是真的把后缀削减了。我调试时会打印每次递归的len(projected)如果不变小就是在死循环。注意setrecursionlimit只能缓解不能解决逻辑错误。问题 4评测脚本说输出文件为空或格式解析失败现象跑完评测后日志显示某个模式的数量为 0或者 “parse error at line 3”。原因输出文件的换行符或末尾标记不对。Windows 上 Python 写文件默认用\r\n但评测脚本在解析时可能只认\n另外项集间的-1和序列末尾的-2少一个或者顺序反了也会解析失败。解决写文件时显式指定newline\n并在写完最后一行后手动 flush。格式问题对着dataset/sequences.txt里面任一行的结构逐字符比对最直接。注意行尾不能有额外空格否则匹配不上。问题 5支持度阈值明明是 0.01结果一个模式都挖不出来现象--min-support 0.01跑完输出文件是空的。原因0.01是相对支持度需要乘以事务总数得到绝对支持度。如果你直接把0.01当作绝对次数去比较几乎所有项集都不满足结果为空。反过来如果传 100 但数据总量只有 500100是相对比例那么会出现结果爆多的情况。解决在支持度计数函数入口处统一做一次转换if min_sup 1: min_sup int(min_sup * len(transactions))。同时打印min_sup转换前后的值确认和评测脚本的预期一致。6. 把课程代码变成实验工具改一个计数器验证算法的正确性代码包跑通以后别急着删它其实是一个很适合当“算法验算台”的框架。我的习惯是拿它做一件事核对单个模式的支持度到底怎么数出来的。这一点在调试自己的改进算法时作用非常大也是我最后想分享的具体技巧。具体做法是在count_support里加一个全局计数器对每个事务只统计一次该模式是否出现不要累计次数。很多人在自己实现 FP-Growth 或 Eclat 时会在这个点上翻车因为“项集在事务中出现次数”和“包含项集的事务数”是两个完全不同的概念。频繁项集用的是后者叫支持度计数前者在关联规则挖掘里没有任何意义。给代码加上下面这段调试逻辑能帮你牢牢盯住这件事def sanity_check(transactions, pattern): 手动核对某个模式的真实支持度。 count 0 for tid, trans in enumerate(transactions): if set(pattern).issubset(set(trans)): count 1 return count验证方法随机挑 5 个你挖掘出来的频繁项集用这个函数重新数一遍支持度和自己代码输出的支持度做对比。如果全部对上说明核心计数逻辑没问题对不上就从candidate_gen的剪枝一路排查到count_support里的集合交集。序列模式也同理只是要把issubset的逐项检查换成序列子序列判断逻辑稍微复杂一点但思路完全一样。从那以后我每次拿到任何课程代码包或开源挖掘项目第一件事不是看画饼的 README而是先手工验算三个小模式的计数。全部对上了才继续往下改这一招替我挡掉了大量的“看起来跑通了但结果其实是错的”的假象。做数据挖掘这一行输出的每一个频繁项集都敢被人拿原始数据抽查心里才踏实。希望这套代码包的方法和经验帮到你。本文还有配套的精品资源点击获取
