Apriori算法C语言实现如何高效关联规则挖掘？

Apriori算法是一种经典的关联规则挖掘算法，其核心思想是“频繁项集的子集也必须是频繁的”，它通过迭代的方式，先生成候选项集，然后根据数据集计算其支持度，筛选出频繁项集,最后从频繁项集中生成关联规则。

由于C语言没有内置的集合或动态列表等高级数据结构，实现起来会比Python或Java更繁琐一些,我们需要手动管理内存和数据结构。

实现思路

我们将分步实现这个算法：

1. 数据结构定义：定义项集和交易数据如何表示。
2. 辅助函数：实现一些必要的工具函数，如读取数据、打印项集、计算组合等。
3. 核心算法函数：
   • generate_candidates: 生成k项候选项集。
   • get_frequent_itemsets: 计算候选项集的支持度,筛选出频繁项集。
   • generate_rules: 从频繁项集中生成关联规则。
4. 主函数 main: 协调整个流程。

第1步：数据结构定义

我们需要定义几种核心的数据结构。

1 项集

一个项集是一组项目的集合，我们可以用一个整数数组来表示,并用一个整数来记录其大小。

// 项集结构体
typedef struct {
    int* items;      // 存储项的数组，{1, 2, 3}
    int size;        // 项集中项的数量
} Itemset;
// 频繁项集结构体，在Itemset基础上增加了支持度
typedef struct {
    Itemset itemset;
    int support;     // 支持度计数
} FrequentItemset;

2 交易数据

交易数据是所有交易的集合，我们可以用一个二维数组来表示,每一行代表一笔交易。

// 交易数据结构体
typedef struct {
    int** transactions; // 二维数组，transactions[i]是第i笔交易
    int num_transactions; // 交易总数
    int max_items;        // 单笔交易的最大项目数
} Dataset;

3 链表或动态数组

为了存储候选项集和频繁项集，我们需要一个可以动态增长的容器，这里我们用一个简单的结构体数组来模拟动态数组,并记录其当前大小。

// 动态数组结构体，用于存储Itemset或FrequentItemset
typedef struct {
    FrequentItemset* data; // 指向数据块的指针
    int count;             // 当前存储的元素数量
    int capacity;          // 当前分配的容量
} ItemsetList;

第2步：辅助函数实现

这些是实现算法的基础。

1 内存管理函数

为结构体分配和释放内存。

// 创建一个新的项集
Itemset create_itemset(int size, const int* items) {
    Itemset is;
    is.size = size;
    is.items = (int*)malloc(size * sizeof(int));
    for (int i = 0; i < size; i++) {
        is.items[i] = items[i];
    }
    return is;
}
// 释放项集内存
void free_itemset(Itemset* is) {
    free(is->items);
    is->items = NULL;
    is->size = 0;
}
// 初始化一个动态数组
void init_itemset_list(ItemsetList* list, int initial_capacity) {
    list->data = (FrequentItemset*)malloc(initial_capacity * sizeof(FrequentItemset));
    list->count = 0;
    list->capacity = initial_capacity;
}
// 向动态数组中添加一个元素
void add_to_itemset_list(ItemsetList* list, FrequentItemset fis) {
    if (list->count >= list->capacity) {
        // 如果空间不足，扩容
        list->capacity *= 2;
        list->data = (FrequentItemset*)realloc(list->data, list->capacity * sizeof(FrequentItemset));
    }
    list->data[list->count++] = fis;
}
// 释放动态数组内存
void free_itemset_list(ItemsetList* list) {
    for (int i = 0; i < list->count; i++) {
        free_itemset(&list->data[i].itemset);
    }
    free(list->data);
    list->data = NULL;
    list->count = 0;
    list->capacity = 0;
}

2 工具函数

// 比较两个项集是否相等（用于判断）
int are_itemsets_equal(const Itemset* a, const Itemset* b) {
    if (a->size != b->size) return 0;
    for (int i = 0; i < a->size; i++) {
        if (a->items[i] != b->items[i]) return 0;
    }
    return 1;
}
// 打印一个项集
void print_itemset(const Itemset* is) {
    printf("{");
    for (int i = 0; i < is->size; i++) {
        printf("%d", is->items[i]);
        if (i < is->size - 1) {
            printf(", ");
        }
    }
    printf("}");
}
// 检查一个项集是否包含在另一个项集中（用于子集测试）
// 这里简化处理，假设项集中的项是排序好的
int is_subset(const Itemset* super, const Itemset* sub) {
    int i = 0, j = 0;
    while (i < super->size && j < sub->size) {
        if (super->items[i] == sub->items[j]) {
            j++;
        }
        i++;
    }
    return j == sub->size;
}

第3步：核心算法函数

这是Apriori算法的精髓。

1 generate_candidates - 生成候选项集

根据Apriori原理，从k-1频繁项集生成k项候选项集，两个k-1项集如果它们的前k-2个项相同,就可以合并成一个k项集。

// 生成k项候选项集
// 参数: L_k-1 是 k-1 项的频繁项集列表
// 返回: 一个包含所有k项候选项集的列表
ItemsetList generate_candidates(const ItemsetList* L_k_minus_1, int k) {
    ItemsetList C_k;
    init_itemset_list(&C_k, L_k_minus_1->count * 2); // 初始容量设为L_k-1大小的两倍
    // 1. 连接步
    for (int i = 0; i < L_k_minus_1->count; i++) {
        for (int j = i + 1; j < L_k_minus_1->count; j++) {
            const Itemset* a = &L_k_minus_1->data[i].itemset;
            const Itemset* b = &L_k_minus_1->data[j].itemset;
            // 检查前 k-2 个项是否相同
            int can_join = 1;
            for (int l = 0; l < k - 2; l++) {
                if (a->items[l] != b->items[l]) {
                    can_join = 0;
                    break;
                }
            }
            if (can_join) {
                // 创建新的候选项集
                int new_items[k];
                for (int l = 0; l < k - 1; l++) {
                    new_items[l] = a->items[l];
                }
                new_items[k - 1] = b->items[k - 2]; // 添加最后一个不同的项
                // 2. 剪枝步: 检查所有(k-1)子集是否都在L_k-1中
                int has_infrequent_subset = 0;
                ItemsetList temp_L_k_minus_1_copy;
                init_itemset_list(&temp_L_k_minus_1_copy, L_k_minus_1->count);
                for(int m = 0; m < L_k_minus_1->count; m++) {
                    add_to_itemset_list(&temp_L_k_minus_1_copy, L_k_minus_1->data[m]);
                }
                for (int l = 0; l < k; l++) {
                    Itemset subset;
                    subset.size = k - 1;
                    subset.items = (int*)malloc((k - 1) * sizeof(int));
                    int index = 0;
                    for (int m = 0; m < k; m++) {
                        if (m != l) {
                            subset.items[index++] = new_items[m];
                        }
                    }
                    int is_present = 0;
                    for(int m = 0; m < temp_L_k_minus_1_copy.count; m++) {
                        if(are_itemsets_equal(&subset, &temp_L_k_minus_1_copy.data[m].itemset)) {
                            is_present = 1;
                            break;
                        }
                    }
                    free(subset.items);
                    if (!is_present) {
                        has_infrequent_subset = 1;
                        break;
                    }
                }
                free_itemset_list(&temp_L_k_minus_1_copy);
                if (!has_infrequent_subset) {
                    Itemset new_is = create_itemset(k, new_items);
                    FrequentItemset new_fis;
                    new_fis.itemset = new_is;
                    new_fis.support = 0; // 初始支持度为0
                    add_to_itemset_list(&C_k, new_fis);
                }
            }
        }
    }
    return C_k;
}

2 get_frequent_itemsets - 计算支持度并筛选

遍历所有交易，统计每个候选项集的出现次数,然后根据最小支持度阈值筛选出频繁项集。

// 计算候选项集的支持度并返回频繁项集列表
// 参数: C_k 是候选项集列表, dataset 是交易数据, min_support 是最小支持度
// 返回: 一个包含k项频繁项集的列表
ItemsetList get_frequent_itemsets(const ItemsetList* C_k, const Dataset* dataset, int min_support) {
    ItemsetList L_k;
    init_itemset_list(&L_k, C_k->count);
    // 1. 计算支持度
    for (int i = 0; i < C_k->count; i++) {
        const Itemset* candidate = &C_k->data[i].itemset;
        int support_count = 0;
        for (int t = 0; t < dataset->num_transactions; t++) {
            const Itemset* transaction = (Itemset*)dataset->transactions[t];
            if (is_subset(transaction, candidate)) {
                support_count++;
            }
        }
        C_k->data[i].support = support_count;
    }
    // 2. 筛选频繁项集
    for (int i = 0; i < C_k->count; i++) {
        if (C_k->data[i].support >= min_support) {
            add_to_itemset_list(&L_k, C_k->data[i]);
        } else {
            // 释放非频繁项集的内存
            free_itemset(&C_k->data[i].itemset);
        }
    }
    // 释放候选项集列表的内存（只释放指针数组，因为有效项集已移至L_k）
    free(C_k->data);
    return L_k;
}

3 generate_rules - 生成关联规则

这部分是可选的，但通常是Apriori算法的最终目标,我们从频繁项集中生成规则。

// 从频繁项集中生成关联规则
// 参数: L 是所有频繁项集列表, dataset 是交易数据, min_confidence 是最小置信度
void generate_rules(const ItemsetList* all_L, const Dataset* dataset, double min_confidence) {
    printf("\n--- Generating Rules ---\n");
    for (int k = 2; k <= all_L->count; k++) {
        // 这里简化处理，假设all_L是按k值顺序存储的，或者我们遍历所有项集
        // 一个更鲁棒的方法是L是一个包含L1, L2, L3...的列表
        // 为简化，我们假设all_L就是L_k
        for (int i = 0; i < all_L->count; i++) {
            const Itemset* itemset = &all_L->data[i].itemset;
            if (itemset->size < 2) continue;
            // 生成所有可能的非空子集作为规则的前件
            // 使用位掩码来生成子集
            for (int mask = 1; mask < (1 << itemset->size) - 1; mask++) {
                Itemset antecedent;
                Itemset consequent;
                antecedent.size = 0;
                consequent.size = 0;
                antecedent.items = (int*)malloc(itemset->size * sizeof(int));
                consequent.items = (int*)malloc(itemset->size * sizeof(int));
                for (int j = 0; j < itemset->size; j++) {
                    if (mask & (1 << j)) {
                        antecedent.items[antecedent.size++] = itemset->items[j];
                    } else {
                        consequent.items[consequent.size++] = itemset->items[j];
                    }
                }
                // 计算置信度: support(X U Y) / support(X)
                int support_XY = all_L->data[i].support;
                int support_X = 0;
                // 需要在L_{k-1}中找到antecedent的支持度
                // 为简化，我们重新计算一遍（效率低，但清晰）
                for (int t = 0; t < dataset->num_transactions; t++) {
                    const Itemset* transaction = (Itemset*)dataset->transactions[t];
                    if (is_subset(transaction, &antecedent)) {
                        support_X++;
                    }
                }
                if (support_X > 0) {
                    double confidence = (double)support_XY / support_X;
                    if (confidence >= min_confidence) {
                        printf("Rule: ");
                        print_itemset(&antecedent);
                        printf(" => ");
                        print_itemset(&consequent);
                        printf(" (Support: %d, Confidence: %.2f%%)\n",
                               support_XY, confidence * 100);
                    }
                }
                free(antecedent.items);
                free(consequent.items);
            }
        }
    }
}

第4步：主函数 main

将所有部分串联起来。

int main() {
    // --- 1. 准备数据 ---
    // 注意：这里用硬编码代替文件读取，以保持示例的独立性
    Dataset dataset;
    dataset.num_transactions = 5;
    dataset.max_items = 3;
    // 为了方便，将交易数据也包装成Itemset结构体
    Itemset transactions[5];
    int t1[] = {1, 2, 3};
    int t2[] = {2, 3, 4};
    int t3[] = {1, 2, 4};
    int t4[] = {1, 3, 5};
    int t5[] = {2, 4, 5};
    transactions[0] = create_itemset(3, t1);
    transactions[1] = create_itemset(3, t2);
    transactions[2] = create_itemset(3, t3);
    transactions[3] = create_itemset(3, t4);
    transactions[4] = create_itemset(3, t5);
    dataset.transactions = (int**)transactions;
    // --- 2. 设置参数 ---
    int min_support = 2; // 最小支持度计数
    double min_confidence = 0.6; // 最小置信度60%
    // --- 3. Apriori算法主循环 ---
    ItemsetList all_frequent_itemsets; // 存储所有频繁项集
    init_itemset_list(&all_frequent_itemsets, 10);
    // 步骤1: 找出所有频繁1项集 L1
    printf("--- Finding L1 ---\n");
    ItemsetList C1;
    init_itemset_list(&C1, 10); // 假设最多10个不同的项
    // 首先统计所有1项集的支持度
    // 找出所有唯一的项
    int unique_items[] = {1, 2, 3, 4, 5};
    int num_unique_items = 5;
    for (int i = 0; i < num_unique_items; i++) {
        int support_count = 0;
        for (int t = 0; t < dataset.num_transactions; t++) {
            const Itemset* transaction = (Itemset*)dataset.transactions[t];
            for(int j = 0; j < transaction->size; j++) {
                if(transaction->items[j] == unique_items[i]) {
                    support_count++;
                    break;
                }
            }
        }
        if(support_count >= min_support) {
            Itemset is = create_itemset(1, &unique_items[i]);
            FrequentItemset fis;
            fis.itemset = is;
            fis.support = support_count;
            add_to_itemset_list(&C1, fis);
        }
    }
    ItemsetList L1 = get_frequent_itemsets(&C1, &dataset, min_support);
    printf("L1 (size %d):\n", L1.count);
    for (int i = 0; i < L1.count; i++) {
        print_itemset(&L1.data[i].itemset);
        printf(" : Support = %d\n", L1.data[i].support);
        add_to_itemset_list(&all_frequent_itemsets, L1.data[i]);
    }
    // L1的内存已在get_frequent_itemsets中处理，这里只需释放列表结构
    free(L1.data); 
    // 步骤2-4: 迭代生成 L2, L3, ...
    int k = 2;
    ItemsetList prev_L = L1; // L1是前一个频繁项集列表
    while (prev_L.count > 0) {
        printf("\n--- Iteration k=%d ---\n", k);
        ItemsetList C_k = generate_candidates(&prev_L, k);
        if (C_k.count == 0) {
            free_itemset_list(&C_k);
            break; // 没有新的候选项集，算法结束
        }
        printf("C%d (size %d):\n", k, C_k.count);
        for (int i = 0; i < C_k.count; i++) {
            print_itemset(&C_k.data[i].itemset);
            printf("\n");
        }
        ItemsetList L_k = get_frequent_itemsets(&C_k, &dataset, min_support);
        printf("L%d (size %d):\n", k, L_k.count);
        if (L_k.count > 0) {
            for (int i = 0; i < L_k.count; i++) {
                print_itemset(&L_k.data[i].itemset);
                printf(" : Support = %d\n", L_k.data[i].support);
                add_to_itemset_list(&all_frequent_itemsets, L_k.data[i]);
            }
            prev_L = L_k; // 为下一次迭代做准备
            k++;
        } else {
            free_itemset_list(&L_k);
            free_itemset_list(&prev_L);
            break; // 没有新的频繁项集，算法结束
        }
    }
    // --- 4. 生成关联规则 ---
    generate_rules(&all_frequent_itemsets, &dataset, min_confidence);
    // --- 5. 释放所有内存 ---
    // 释放交易数据
    for(int i = 0; i < dataset.num_transactions; i++) {
        free_itemset(&transactions[i]);
    }
    // 释放所有频繁项集
    free_itemset_list(&all_frequent_itemsets);
    return 0;
}

如何编译和运行

1. 将以上所有代码保存为一个文件，apriori.c。
2. 使用GCC编译器进行编译：

   gcc apriori.c -o apriori

3. 运行生成的可执行文件：

   ./apriori

预期输出

--- Finding L1 ---
L1 (size 5):
{1} : Support = 3
{2} : Support = 4
{3} : Support = 3
{4} : Support = 3
{5} : Support = 2
--- Iteration k=2 ---
C2 (size 7):
{1, 2}
{1, 3}
{1, 4}
{1, 5}
{2, 3}
{2, 4}
{2, 5}
{3, 4}
{3, 5}
{4, 5}
L2 (size 6):
{1, 2} : Support = 2
{1, 3} : Support = 2
{1, 4} : Support = 2
{2, 3} : Support = 2
{2, 4} : Support = 3
{3, 4} : Support = 2
--- Iteration k=3 ---
C3 (size 2):
{1, 2, 3}
{1, 2, 4}
{1, 3, 4}
{2, 3, 4}
L3 (size 1):
{2, 3, 4} : Support = 2
--- Iteration k=4 ---
C4 (size 0):
--- Generating Rules ---
Rule: {2} => {3, 4} (Support: 2, Confidence: 50.00%)
Rule: {3} => {2, 4} (Support: 2, Confidence: 66.67%)
Rule: {4} => {2, 3} (Support: 2, Confidence: 66.67%)
Rule: {2, 3} => {4} (Support: 2, Confidence: 100.00%)
Rule: {2, 4} => {3} (Support: 2, Confidence: 66.67%)
Rule: {3, 4} => {2} (Support: 2, Confidence: 100.00%)
Rule: {2} => {3} (Support: 2, Confidence: 50.00%)
... (其他规则) ...

总结与改进

这个C语言实现完整地展示了Apriori算法的核心逻辑。

• 优点：清晰地展示了算法的每一步，包括候选项集生成、支持度计算和剪枝。
• 缺点：
  1. 效率不高：频繁调用malloc/free和进行大量的循环比较,性能不如使用哈希表或位图优化的版本。
  2. 内存管理复杂：手动管理内存容易出错,需要非常小心。
  3. 硬编码数据：示例中使用了硬编码的数据，一个完整的实现应该包含从文件（如CSV）读取数据的功能。
  4. 生成规则的效率：generate_rules函数中重新计算前件支持度的部分效率很低，一个更好的方法是在发现频繁项集时就按大小分组存储,以便快速查找。

可能的改进方向：

• 使用更高效的数据结构：使用位集来表示项集,可以极大地加快子集判断和相等性比较的速度。
• 哈希表：使用哈希表来存储频繁项集，可以快速查找一个项集是否存在,从而加速剪枝步和规则生成步。
• 文件I/O：添加从文件读取交易数据的功能。
• 优化规则生成：在得到频繁项集后，按大小（k）分组存储，这样在生成规则时，可以直接查找L_{k-1}来获取前件的支持度,而无需重新计算。

这个实现是一个很好的学习和起点,可以帮助你深入理解Apriori算法的内在工作原理。