数据挖掘模式发现：Python实现Apriori与PrefixSpan的完整实战

简介：面向正在学习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 调到 50，2-项集数量翻倍，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", encoding="utf-8")，如果报编码错误，改成encoding="latin-1"或errors="ignore"临时绕过。路径问题一律在运行命令里写相对路径，别写绝对路径。

问题 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 但数据总量只有 500，100是相对比例，那么会出现结果爆多的情况。
• 解决：在支持度计数函数入口处统一做一次转换：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，而是先手工验算三个小模式的计数。全部对上了才继续往下改，这一招替我挡掉了大量的“看起来跑通了但结果其实是错的”的假象。做数据挖掘这一行，输出的每一个频繁项集都敢被人拿原始数据抽查，心里才踏实。希望这套代码包的方法和经验帮到你。

本文还有配套的精品资源，点击获取