094. 使用C语言实现简单的数据挖掘算法

在C语言中实现一个简单的数据挖掘算法是一个很好的练习，可以帮助你理解数据挖掘的基本概念。这里我将展示一个简单的关联规则挖掘算法——Apriori算法。Apriori算法是一种经典的关联规则挖掘算法，用于从交易数据中发现频繁项集和关联规则。

Apriori算法简介

Apriori算法的核心思想是利用频繁项集的性质（如果一个项集是频繁的，那么它的所有子集也必须是频繁的）来减少搜索空间。算法的基本步骤如下：

生成频繁1-项集：扫描数据集，找出所有频繁的单个项。
生成频繁k-项集：从频繁k−1-项集生成候选k-项集，然后扫描数据集，找出频繁的k-项集。
生成关联规则：从频繁项集中生成关联规则。

示例代码：简单的Apriori算法

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_TRANSACTIONS 100
#define MAX_ITEMS_PER_TRANSACTION 10
#define MAX_ITEMSETS 100
#define MIN_SUPPORT 2

typedef struct {
    int items[MAX_ITEMS_PER_TRANSACTION];
    int size;
} Itemset;

// 数据集
int transactions[MAX_TRANSACTIONS][MAX_ITEMS_PER_TRANSACTION] = {
    {1, 2, 3, 4, 0},
    {2, 3, 4, 5, 0},
    {1, 2, 4, 0},
    {1, 2, 3, 5, 0},
    {1, 3, 4, 0}
};

int numTransactions = 5;

// 比较函数，用于排序
int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

// 检查项集是否在交易中
int isSubset(int* transaction, int* itemset, int size) {
    for (int i = 0; i < size; i++) {
        if (!bsearch(&itemset[i], transaction, MAX_ITEMS_PER_TRANSACTION, sizeof(int), compare)) {
            return 0;
        }
    }
    return 1;
}

// 生成频繁1-项集
void generateFrequent1Itemsets(Itemset* frequentItemsets, int* numFrequentItemsets) {
    int itemCounts[MAX_ITEMS_PER_TRANSACTION] = {0};
    for (int i = 0; i < numTransactions; i++) {
        for (int j = 0; transactions[i][j] != 0; j++) {
            itemCounts[transactions[i][j]]++;
        }
    }

    *numFrequentItemsets = 0;
    for (int i = 1; i < MAX_ITEMS_PER_TRANSACTION; i++) {
        if (itemCounts[i] >= MIN_SUPPORT) {
            frequentItemsets[*numFrequentItemsets].items[0] = i;
            frequentItemsets[*numFrequentItemsets].size = 1;
            (*numFrequentItemsets)++;
        }
    }
}

// 生成候选k-项集
void generateCandidateItemsets(Itemset* frequentItemsets, int numFrequentItemsets, Itemset* candidateItemsets, int* numCandidateItemsets, int k) {
    *numCandidateItemsets = 0;
    for (int i = 0; i < numFrequentItemsets; i++) {
        for (int j = i + 1; j < numFrequentItemsets; j++) {
            int unionSet[MAX_ITEMS_PER_TRANSACTION] = {0};
            int unionSize = 0;
            for (int m = 0; m < k - 1; m++) {
                unionSet[unionSize++] = frequentItemsets[i].items[m];
            }
            for (int m = 0; m < k - 1; m++) {
                if (!bsearch(&frequentItemsets[i].items[m], frequentItemsets[j].items, frequentItemsets[j].size, sizeof(int), compare)) {
                    unionSet[unionSize++] = frequentItemsets[j].items[m];
                }
            }
            if (unionSize == k) {
                candidateItemsets[*numCandidateItemsets].size = k;
                for (int m = 0; m < k; m++) {
                    candidateItemsets[*numCandidateItemsets].items[m] = unionSet[m];
                }
                (*numCandidateItemsets)++;
            }
        }
    }
}

// 生成频繁k-项集
void generateFrequentItemsets(Itemset* candidateItemsets, int numCandidateItemsets, Itemset* frequentItemsets, int* numFrequentItemsets, int k) {
    int counts[MAX_ITEMSETS] = {0};
    for (int i = 0; i < numCandidateItemsets; i++) {
        for (int j = 0; j < numTransactions; j++) {
            if (isSubset(transactions[j], candidateItemsets[i].items, k)) {
                counts[i]++;
            }
        }
    }

    *numFrequentItemsets = 0;
    for (int i = 0; i < numCandidateItemsets; i++) {
        if (counts[i] >= MIN_SUPPORT) {
            frequentItemsets[*numFrequentItemsets] = candidateItemsets[i];
            (*numFrequentItemsets)++;
        }
    }
}

int main() {
    Itemset frequentItemsets[MAX_ITEMSETS];
    Itemset candidateItemsets[MAX_ITEMSETS];
    int numFrequentItemsets, numCandidateItemsets;

    // 生成频繁1-项集
    generateFrequent1Itemsets(frequentItemsets, &numFrequentItemsets);

    printf("Frequent 1-itemsets:\n");
    for (int i = 0; i < numFrequentItemsets; i++) {
        for (int j = 0; j < frequentItemsets[i].size; j++) {
            printf("%d ", frequentItemsets[i].items[j]);
        }
        printf("\n");
    }

    // 生成频繁2-项集
    generateCandidateItemsets(frequentItemsets, numFrequentItemsets, candidateItemsets, &numCandidateItemsets, 2);
    generateFrequentItemsets(candidateItemsets, numCandidateItemsets, frequentItemsets, &numFrequentItemsets, 2);

    printf("Frequent 2-itemsets:\n");
    for (int i = 0; i < numFrequentItemsets; i++) {
        for (int j = 0; j < frequentItemsets[i].size; j++) {
            printf("%d ", frequentItemsets[i].items[j]);
        }
        printf("\n");
    }

    return 0;
}

代码说明

数据集：定义了一个简单的交易数据集 transactions，每个交易是一个整数数组。
生成频繁1-项集：扫描数据集，统计每个项的出现次数，找出频繁的1-项集。
生成候选k-项集：从频繁k−1-项集生成候选k-项集。
生成频繁k-项集：扫描数据集，统计每个候选项集的出现次数，找出频繁的k-项集。
主函数：生成频繁1-项集和频繁2-项集，并打印结果。

示例运行

Frequent 1-itemsets:
1 
2 
3 
4 
5 
Frequent 2-itemsets:
1 2 
1 3 
1 4 
2 3 
2 4 
3 4

扩展功能

生成关联规则：从频繁项集中生成关联规则，计算置信度和提升度。
优化性能：使用更高效的数据结构（如哈希表）来存储项集和计数。
支持更大的数据集：使用动态内存分配来支持更大的数据集和项集。
并行化：使用多线程或并行计算来加速频繁项集的生成。

视频讲解

BiliBili： 视睿网络-哔哩哔哩视频 (bilibili.com)