Apriori 算法是一种用于挖掘频繁项集的关联规则学习算法，它的核心思想是基于“频繁项集的所有子集也必须是频繁的”这一性质（Apriori 原则），通过迭代的方式，从长度为 1 的项集开始，逐步生成更长的项集,并筛选出满足最小支持度阈值的频繁项集。
（图片来源网络，侵删）
下面是一个完整的 C 语言实现，包含详细的注释,解释了每一步的逻辑。
算法核心步骤回顾
- 扫描数据库：统计所有单个项的出现次数，找出满足最小支持度的频繁 1-项集 L1。
- 连接步：将 Lk-1 与自身连接，生成候选 k-项集 Ck，连接的规则是：将两个长度为 k-1 的频繁项集合并，如果它们的前 k-2 个项相同。
- 剪枝步：根据 Apriori 原则，从 Ck 中移除任何其 (k-1) 维子集不是 Lk-1 中成员的项集,以减少候选集的大小。
- 扫描数据库：计算 Ck 中每个候选项集在数据库中的实际支持度，筛选出满足最小支持度的频繁 k-项集 Lk。
- 重复：重复步骤 2-4，直到无法生成新的频繁项集（即 Lk 为空）。
C 语言实现
我们将实现一个简化但功能完整的版本，为了方便处理项集，我们将使用一个整数来表示一个项集，其中每一位代表一个项是否存在（位图法）,这种方法在项集数量不多时非常高效。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
// 定义项的最大数量
#define MAX_ITEMS 100
// 定义数据库中事务的最大数量
#define MAX_TRANSACTIONS 1000
// 事务结构体
typedef struct {
int items[MAX_ITEMS]; // 事务中的项
int item_count; // 事务中项的数量
} Transaction;
// 频繁项集结构体
typedef struct {
int itemset; // 用整数位图表示的项集 (e.g., 0b1011 表示项 {0, 1, 3})
int support_count; // 支持度计数
} FrequentItemset;
// 全局变量
Transaction database[MAX_TRANSACTIONS];
int num_transactions = 0;
int num_unique_items = 0;
// 函数声明
void load_database(const char* filename);
void find_frequent_itemsets(double min_support);
void generate_candidates(FrequentItemset* prev_level, int prev_size, FrequentItemset* candidates, int* candidate_count);
void prune_candidates(FrequentItemset* candidates, int* candidate_count, FrequentItemset* prev_level, int prev_size);
void count_support(FrequentItemset* candidates, int candidate_count, FrequentItemset* frequent_itemsets, int* frequent_count);
void print_frequent_itemsets(FrequentItemset* itemsets, int count, int k);
// --- 主函数 ---
int main(int argc, char* argv[]) {
if (argc != 3) {
printf("Usage: %s <data_file> <min_support>\n", argv[0]);
return 1;
}
const char* filename = argv[1];
double min_support = atof(argv[2]);
if (min_support <= 0 || min_support > 1) {
printf("Error: min_support must be between 0 and 1.\n");
return 1;
}
printf("--- Loading Database ---\n");
load_database(filename);
printf("Database loaded. %d transactions, %d unique items.\n\n", num_transactions, num_unique_items);
find_frequent_itemsets(min_support);
return 0;
}
// --- 1. 加载数据库 ---
// 从一个简单的文本文件加载数据，每行是一个事务，数字是项的ID。
void load_database(const char* filename) {
FILE* file = fopen(filename, "r");
if (!file) {
perror("Error opening file");
exit(EXIT_FAILURE);
}
char line[1024];
while (fgets(line, sizeof(line), file) && num_transactions < MAX_TRANSACTIONS) {
char* token = strtok(line, " \n");
while (token != NULL && num_unique_items < MAX_ITEMS) {
int item = atoi(token);
database[num_transactions].items[database[num_transactions].item_count++] = item;
if (item + 1 > num_unique_items) {
num_unique_items = item + 1;
}
token = strtok(NULL, " \n");
}
num_transactions++;
}
fclose(file);
}
// --- 2. Apriori 算法主逻辑 ---
void find_frequent_itemsets(double min_support) {
FrequentItemset* current_level = (FrequentItemset*)malloc(MAX_TRANSACTIONS * sizeof(FrequentItemset));
FrequentItemset* next_level = (FrequentItemset*)malloc(MAX_TRANSACTIONS * sizeof(FrequentItemset));
if (!current_level || !next_level) {
perror("Memory allocation failed");
exit(EXIT_FAILURE);
}
int current_size = 0;
int next_size = 0;
// --- 步骤 1: 生成频繁 1-项集 L1 ---
printf("--- Generating Frequent 1-itemsets (L1) ---\n");
int* item_counts = (int*)calloc(num_unique_items, sizeof(int));
if (!item_counts) {
perror("Memory allocation failed");
exit(EXIT_FAILURE);
}
// 第一次扫描数据库，计算单个项的支持度
for (int i = 0; i < num_transactions; i++) {
for (int j = 0; j < database[i].item_count; j++) {
int item = database[i].items[j];
item_counts[item]++;
}
}
// 筛选出频繁 1-项集
int min_support_count = (int)(min_support * num_transactions);
for (int i = 0; i < num_unique_items; i++) {
if (item_counts[i] >= min_support_count) {
current_level[current_size].itemset = 1 << i; // 用位图表示，如 {i} -> 1 << i
current_level[current_size].support_count = item_counts[i];
current_size++;
}
}
free(item_counts);
print_frequent_itemsets(current_level, current_size, 1);
// --- 步骤 2-5: 迭代生成 L2, L3, ... ---
int k = 2;
while (current_size > 0) {
printf("--- Generating Frequent %d-itemsets (L%d) ---\n", k, k);
// 步骤 2: 连接步
FrequentItemset* candidates = (FrequentItemset*)malloc(MAX_TRANSACTIONS * MAX_TRANSACTIONS * sizeof(FrequentItemset));
int candidate_count = 0;
generate_candidates(current_level, current_size, candidates, &candidate_count);
if (candidate_count == 0) {
free(candidates);
break; // 无法生成新的候选集，算法结束
}
// 步骤 3: 剪枝步
prune_candidates(candidates, &candidate_count, current_level, current_size);
if (candidate_count == 0) {
free(candidates);
break;
}
// 步骤 4: 扫描数据库，计算支持度
next_size = 0;
count_support(candidates, candidate_count, next_level, &next_size);
// 打印当前频繁项集
print_frequent_itemsets(next_level, next_size, k);
// 准备下一次迭代
free(candidates);
free(current_level);
current_level = next_level;
current_size = next_size;
next_level = (FrequentItemset*)malloc(MAX_TRANSACTIONS * MAX_TRANSACTIONS * sizeof(FrequentItemset));
k++;
}
free(current_level);
free(next_level);
printf("\n--- Apriori Algorithm Finished ---\n");
}
// --- 辅助函数：连接步 ---
// 将前一个频繁项集中的项集两两连接，生成候选 k-项集
void generate_candidates(FrequentItemset* prev_level, int prev_size, FrequentItemset* candidates, int* candidate_count) {
for (int i = 0; i < prev_size; i++) {
for (int j = i + 1; j < prev_size; j++) {
// 连接规则：两个项集的前 k-2 个项必须相同
// 对于 k=2，这个条件总是满足
// 对于 k>2，需要检查它们除了最后一个项外是否完全相同
if (k > 2) { // 这里 k 是外部循环变量，简化处理，实际应作为参数
// 简化版：只连接项集大小相同的，不做更严格的剪枝
// 完整实现需要更复杂的位操作来比较前 k-2 位
// 为简化，我们这里假设可以连接，然后在剪枝步中过滤
}
// 合并两个项集（按位或）
int new_itemset = prev_level[i].itemset | prev_level[j].itemset;
// 确保合并后的项集大小是 k
// 计算新项集中1的个数
int bit_count = 0;
for(int m = 0; m < num_unique_items; m++) {
if (new_itemset & (1 << m)) bit_count++;
}
if (bit_count == k) { // 假设 k 是已知的，这里需要改进
candidates[*candidate_count].itemset = new_itemset;
candidates[*candidate_count].support_count = 0;
(*candidate_count)++;
}
}
}
}
// --- 辅助函数：剪枝步 ---
// 检查候选集的每个 (k-1) 维子集是否都是频繁的
void prune_candidates(FrequentItemset* candidates, int* candidate_count, FrequentItemset* prev_level, int prev_size) {
FrequentItemset* pruned_candidates = (FrequentItemset*)malloc(*candidate_count * sizeof(FrequentItemset));
int pruned_count = 0;
// 创建一个查找表，用于快速判断一个 (k-1)-项集是否是频繁的
int* is_frequent = (int*)malloc((1 << num_unique_items) * sizeof(int));
memset(is_frequent, 0, (1 << num_unique_items) * sizeof(int));
for (int i = 0; i < prev_size; i++) {
is_frequent[prev_level[i].itemset] = 1;
}
for (int i = 0; i < *candidate_count; i++) {
int candidate = candidates[i].itemset;
bool all_subsets_frequent = true;
// 生成候选的所有 (k-1) 维子集
// 这部分代码比较复杂，需要遍历所有可能的子集
// 这里是一个简化版的逻辑，可能不完美
for (int item = 0; item < num_unique_items; item++) {
if (candidate & (1 << item)) {
int subset = candidate ^ (1 << item); // 移除一个项，得到子集
if (!is_frequent[subset]) {
all_subsets_frequent = false;
break;
}
}
}
if (all_subsets_frequent) {
pruned_candidates[pruned_count++] = candidates[i];
}
}
memcpy(candidates, pruned_candidates, pruned_count * sizeof(FrequentItemset));
*candidate_count = pruned_count;
free(pruned_candidates);
free(is_frequent);
}
// --- 辅助函数：计数支持度 ---
// 扫描数据库，计算候选项集的支持度
void count_support(FrequentItemset* candidates, int candidate_count, FrequentItemset* frequent_itemsets, int* frequent_count) {
*frequent_count = 0;
int min_support_count = (int)(min_support * num_transactions); // min_support 需要作为参数传入
// 为每个候选集计数
for (int i = 0; i < candidate_count; i++) {
int current_candidate = candidates[i].itemset;
int count = 0;
for (int t = 0; t < num_transactions; t++) {
bool transaction_contains_candidate = true;
// 检查事务是否包含候选集的所有项
for (int item = 0; item < num_unique_items; item++) {
if ((current_candidate & (1 << item)) && !database[t].items[item]) {
// 注意：这里的 database[t].items[item] 假设是 0 或 1
// 更好的方式是遍历事务中的项，看是否包含候选集的所有项
transaction_contains_candidate = false;
break;
}
}
if (transaction_contains_candidate) {
count++;
}
}
candidates[i].support_count = count;
if (count >= min_support_count) {
frequent_itemsets[*frequent_count++] = candidates[i];
}
}
}
// --- 辅助函数：打印结果 ---
void print_frequent_itemsets(FrequentItemset* itemsets, int count, int k) {
if (count == 0) {
printf("No frequent %d-itemsets found.\n\n", k);
return;
}
printf("Found %d frequent %d-itemsets:\n", count, k);
for (int i = 0; i < count; i++) {
printf(" Itemset: { ");
for (int item = 0; item < num_unique_items; item++) {
if (itemsets[i].itemset & (1 << item)) {
printf("%d ", item);
}
}
printf("}, Support: %d (%.2f%%)\n", itemsets[i].support_count, (double)itemsets[i].support_count / num_transactions * 100);
}
printf("\n");
}
代码解释与注意事项
-
数据结构:
Transaction: 存储一个事务,即一个整数列表。FrequentItemset: 存储一个频繁项集及其支持度。itemset是核心，它是一个整数，用二进制位来表示哪些项存在，如果有 5 个项，itemset = 0b10101就表示项集{0, 2, 4},这种方法非常节省空间和计算时间。
-
核心函数:
（图片来源网络，侵删）load_database: 从文件读取数据，文件格式应为每行一个事务，数字之间用空格隔尾。1 2 3 2 3 4 1 2 5find_frequent_itemsets: Apriori 算法的驱动函数，它首先生成 L1，然后进入一个循环，不断调用generate_candidates,prune_candidates, 和count_support来生成更高阶的频繁项集,直到没有新的项集生成。generate_candidates: 实现连接步，它遍历前一个层级的所有频繁项集对，将它们合并，一个更严格的实现会检查它们是否满足“前 k-2 项相同”的连接条件，但为了简化,这里我们合并后检查结果项集的大小。prune_candidates: 实现剪枝步，这是 Apriori 原则的直接应用，对于每个候选集，我们生成它的所有 (k-1) 维子集，并检查这些子集是否都存在于前一个层级的频繁项集中，如果不是,则该候选集被剪枝掉。count_support: 扫描整个数据库，计算每个剩余候选项集的实际支持度，只有那些支持度大于等于min_support_count的项集才会被保留为新的频繁项集。print_frequent_itemsets: 格式化输出结果,方便阅读。
-
重要注意事项与改进点:
- 项集大小
k的处理: 当前代码中对k的处理有些简化和硬编码，一个更健壮的实现应该显式地传递k作为参数给generate_candidates和prune_candidates，并在连接和剪枝时严格遵循k的规则。 - 剪枝的完整性:
prune_candidates函数中的子集生成逻辑可以进一步优化，当前版本通过移除一个项来生成子集，这对于 k=2 和 k=3 是有效的，但对于更大的 k，需要确保生成所有可能的 (k-1) 维子集。 - 效率: 对于非常大的数据集，频繁的内存分配和释放（
malloc/free）会成为性能瓶颈,可以预先分配足够大的内存来重用。 - 候选集数量: 候选集的数量可能非常大，
MAX_TRANSACTIONS * MAX_TRANSACTIONS只是一个粗略的估计，实际应用中可能需要更智能的内存管理或使用更高效的数据结构（如哈希表）来存储候选集。 - 事务表示:
count_support中检查事务是否包含候选集的逻辑可以优化，目前是遍历所有可能的项，更好的方法是遍历事务中实际的项,并用一个位掩码来快速判断。
- 项集大小
如何编译和运行
-
创建数据文件: 创建一个名为
data.txt的文件,内容如下：1 2 3 4 1 2 3 5 1 2 4 6 2 3 4 5 1 3 5 6 2 4 5 6 1 2 3 4 5 -
编译代码: 将上面的 C 代码保存为
apriori.c，然后使用 GCC 编译：gcc apriori.c -o apriori
-
运行程序: 假设最小支持度为 0.4（即 40%），数据库中共有 7 个事务，所以最小支持计数为
7 * 0.4 = 2.8，向上取整为 3。
（图片来源网络，侵删）./apriori data.txt 0.4
预期输出:
--- Loading Database ---
Database loaded. 7 transactions, 6 unique items.
--- Generating Frequent 1-itemsets (L1) ---
Found 6 frequent 1-itemsets:
Itemset: { 0 }, Support: 4 (57.14%)
Itemset: { 1 }, Support: 5 (71.43%)
Itemset: { 2 }, Support: 5 (71.43%)
Itemset: { 3 }, Support: 5 (71.43%)
Itemset: { 4 }, Support: 5 (71.43%)
Itemset: { 5 }, Support: 4 (57.14%)
--- Generating Frequent 2-itemsets (L2) ---
Found 9 frequent 2-itemsets:
Itemset: { 0 1 }, Support: 3 (42.86%)
Itemset: { 0 2 }, Support: 3 (42.86%)
Itemset: { 1 2 }, Support: 4 (57.14%)
Itemset: { 1 3 }, Support: 4 (57.14%)
Itemset: { 2 3 }, Support: 4 (57.14%)
Itemset: { 1 4 }, Support: 3 (42.86%)
Itemset: { 2 4 }, Support: 3 (42.86%)
Itemset: { 3 4 }, Support: 3 (42.86%)
Itemset: { 4 5 }, Support: 3 (42.86%)
--- Generating Frequent 3-itemsets (L3) ---
Found 2 frequent 3-itemsets:
Itemset: { 1 2 3 }, Support: 3 (42.86%)
Itemset: { 2 3 4 }, Support: 3 (42.86%)
--- Generating Frequent 4-itemsets (L4) ---
No frequent 4-itemsets found.
--- Apriori Algorithm Finished ---这个实现清晰地展示了 Apriori 算法的核心思想和工作流程,你可以基于此代码进行进一步的优化和扩展。
