C++实现关联规则挖掘（从零开始掌握Apriori算法与频繁项集发现）

Apriori算法原理

Apriori算法C++实现的核心思想基于“先验性质”：如果一个项集是频繁的，那么它的所有子集也必须是频繁的。反之，如果一个项集是非频繁的，那么它的超集也一定是非频繁的。

算法步骤如下：

1. 扫描数据库，找出所有支持度 ≥ 最小支持度的单个项（1-项集）。
2. 由k-项集生成(k+1)-项集候选集。
3. 再次扫描数据库，计算每个候选集的支持度。
4. 保留支持度 ≥ 最小支持度的项集，重复步骤2-3，直到无法生成新的频繁项集。
5. 从频繁项集中生成满足最小置信度的关联规则。

C++代码实现

下面是一个简化但完整的数据挖掘C++ Apriori算法实现。我们将使用标准库（vector、map、set等）来处理数据。

#include <iostream>#include <vector>#include <set>#include <map>#include <algorithm>using namespace std;// 计算项集的支持度int getSupport(const set<int>& itemset,                 const vector<set<int>>& transactions) {    int count = 0;    for (const auto& t : transactions) {        if (includes(t.begin(), t.end(),                       itemset.begin(), itemset.end())) {            count++;        }    }    return count;}// 生成k+1项集候选vector<set<int>> generateCandidates(    const vector<set<int>>& freqItemsets) {    vector<set<int>> candidates;    int n = freqItemsets.size();    for (int i = 0; i < n; ++i) {        for (int j = i + 1; j < n; ++j) {            set<int> merged;            set_union(freqItemsets[i].begin(), freqItemsets[i].end(),                      freqItemsets[j].begin(), freqItemsets[j].end(),                      inserter(merged, merged.begin()));            // 只有当合并后大小比原来大1时才有效            if (merged.size() == freqItemsets[i].size() + 1) {                candidates.push_back(merged);            }        }    }    // 去重    sort(candidates.begin(), candidates.end());    candidates.erase(unique(candidates.begin(), candidates.end()),                      candidates.end());    return candidates;}// 主函数：Apriori算法void apriori(const vector<set<int>>& transactions,               double minSupportRatio) {    int total = transactions.size();    int minSupport = static_cast<int>(minSupportRatio * total);    // 步骤1：找出所有频繁1-项集    map<int, int> itemCount;    for (const auto& t : transactions) {        for (int item : t) {            itemCount[item]++;        }    }    vector<set<int>> freqItemsets;    for (const auto& p : itemCount) {        if (p.second >= minSupport) {            freqItemsets.push_back({p.first});        }    }    int k = 1;    while (!freqItemsets.empty()) {        cout << "频繁" << k << "-项集: ";        for (const auto& itemset : freqItemsets) {            cout << "{";            bool first = true;            for (int item : itemset) {                if (!first) cout << ", ";                cout << item;                first = false;            }            cout << "} ";        }        cout << endl;        // 生成候选(k+1)-项集        vector<set<int>> candidates = generateCandidates(freqItemsets);        vector<set<int>> nextFreqItemsets;        for (const auto& cand : candidates) {            int support = getSupport(cand, transactions);            if (support >= minSupport) {                nextFreqItemsets.push_back(cand);            }        }        freqItemsets = nextFreqItemsets;        k++;    }}int main() {    // 示例交易数据：每个set代表一个购物篮    vector<set<int>> transactions = {        {1, 2, 3},        {1, 2},        {1, 3},        {1, 4},        {2, 3},        {2, 4},        {1, 2, 3, 4}    };    double minSupport = 0.3; // 最小支持度30%    cout << "正在执行Apriori算法...\n";    apriori(transactions, minSupport);    return 0;}

如何编译和运行？

将上述代码保存为 apriori.cpp，然后在终端执行：

g++ -std=c++11 apriori.cpp -o apriori./apriori

你将看到程序输出所有满足最小支持度的频繁项集挖掘结果。

总结

通过本教程，你已经掌握了使用C++实现Apriori算法的基本方法。虽然实际工业级系统会使用更高效的优化（如哈希树、FP-Growth等），但理解Apriori是学习数据挖掘C++关联规则的基础。

你可以尝试：

• 修改最小支持度阈值，观察结果变化
• 添加规则生成模块（计算置信度）
• 用真实购物数据测试算法

希望这篇关于C++关联规则算法的入门教程对你有所帮助！继续探索频繁项集挖掘的奇妙世界吧！