C++编程生成频繁项集

生成频繁项集是数据挖掘中的一个重要任务，可以使用一些常见的算法如 Apriori 和 FP-Growth 算法来实现。

以 Apriori 算法为例，主要思路是先生成所有可能的单项集，然后逐渐扩展成更大的项集，直到不能再加入新的项集为止。在每次扩展时，需要统计数据集中每个项集出现的次数，并筛选出出现次数大于等于设定的阈值的项集作为频繁项集。

下面是一个简单的 C++ 实现：

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

vector<vector<int>> apriori(vector<vector<int>> transactions, int min_support) {
    vector<vector<int>> freq_items;
    unordered_map<int, int> item_counts;
    for (auto transaction : transactions) {
        for (auto item : transaction) {
            item_counts[item]++;
        }
    }
    vector<pair<int, int>> items;
    for (auto item_count : item_counts) {
        items.push_back(item_count);
    }
    int k = 1;
    while (!items.empty()) {
        vector<pair<vector<int>, int>> candidates;
        for (int i = 0; i < items.size(); i++) {
            for (int j = i + 1; j < items.size(); j++) {
                vector<int> itemset = {items[i].first, items[j].first};
                candidates.push_back({itemset, 0});
            }
        }
        for (auto transaction : transactions) {
            for (auto& candidate : candidates) {
                if (includes(transaction.begin(), transaction.end(), candidate.first.begin(), candidate.first.end())) {
                    candidate.second++;
                }
            }
        }
        vector<pair<vector<int>, int>> freq_candidates;
        for (auto candidate : candidates) {
            if (candidate.second >= min_support) {
                freq_candidates.push_back(candidate);
            }
        }
        if (freq_candidates.empty()) {
            break;
        }
        freq_items.clear();
        for (auto freq_candidate : freq_candidates) {
            freq_items.push_back(freq_candidate.first);
        }
        items.clear();
        for (auto freq_item : freq_items) {
            for (auto item : freq_item) {
                if (find(items.begin(), items.end(), make_pair(item, 0)) == items.end()) {
                    items.push_back(make_pair(item, 0));
                }
            }
        }
        for (auto& item : items) {
            for (auto freq_item : freq_items) {
                if (find(freq_item.begin(), freq_item.end(), item.first) != freq_item.end()) {
                    item.second++;
                }
            }
        }
        items.erase(remove_if(items.begin(), items.end(), [&](auto item_count) {
            return item_count.second < k + 1;
        }), items.end());
        k++;
    }
    return freq_items;
}

int main() {
    vector<vector<int>> transactions = {{1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4}, {1, 2, 3, 4}};
    int min_support = 3;
    vector<vector<int>> freq_items = apriori(transactions, min_support);
    for (auto freq_item : freq_items) {
        for (auto item : freq_item) {
            cout << item << " ";
        }
        cout << endl;
    }
    return 0;
}

这个实现中，输入参数 transactions 是一个包含多个事务的向量，每个事务是一个包含多个项的向量。min_support 是设定的阈值，用来筛选频繁项集。

在 apriori 函数中，首先统计每个项在所有事务中出现的次数。然后按照 Apriori 算法的步骤，逐渐生成更大的项集，并筛选出频繁项集。最后返回频繁项集。

在主函数中，我们用一个例子来测试这个实现。给定一个包含 5 个事务的数据集，每个事务包含 1 到 4 个项，我们设定 min_support 为 3，即出现次数大于等于 3 的项集为频繁项集。运行结果如下：

1 
2 
3 
4 
1 2 
1 3 
1 4 
2 3 
2 4 
3 4 
1 2 3 
1 2 4 
1 3 4 
2 3 4 
1 2 3 4 

可以看到，我们成功地生成了所有频繁项集。