关联分析——FP-growth算法 C++带类实现及案例

FP-growth算法是一种非常常用的关联分析算法，可以用于挖掘数据集中的频繁项集，进而发现数据集中不同项之间的关联关系。C++作为一种高效的编程语言，也可以用于实现FP-growth算法。

下面是一个基于C++类的FP-growth算法实现及案例示例：

#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;

class Node {
public:
    string name;
    int count;
    Node* parent;
    map<string, Node*> children;

    Node() {
        name = "";
        count = 0;
        parent = NULL;
    }

    Node(string name, int count) {
        this->name = name;
        this->count = count;
        parent = NULL;
    }

    void inc(int num) {
        count += num;
    }
};

class FPTree {
public:
    Node* root;
    map<string, int> headerTable;

    FPTree() {
        root = new Node();
        headerTable.clear();
    }

    void insert(vector<string>& transaction) {
        Node* cur = root;
        for (int i = 0; i < transaction.size(); i++) {
            string item = transaction[i];
            if (cur->children.count(item) == 0) {
                cur->children[item] = new Node(item, 1);
                cur->children[item]->parent = cur;
                if (headerTable.count(item) == 0) {
                    headerTable[item] = 1;
                } else {
                    headerTable[item]++;
                }
            } else {
                cur->children[item]->count++;
            }
            cur = cur->children[item];
        }
    }
};

class FPGrowth {
public:
    FPTree* tree;
    map<string, int> items;
    vector<vector<string>> transactions;

    FPGrowth() {
        tree = NULL;
    }

    void loadTransactions(string filename) {
        ifstream fin(filename);
        if (!fin.is_open()) {
            return;
        }
        string line;
        while (getline(fin, line)) {
            vector<string> transaction;
            string item;
            for (int i = 0; i < line.size(); i++) {
                if (line[i] == ' ') {
                    if (items.count(item) == 0) {
                        items[item] = 1;
                    } else {
                        items[item]++;
                    }
                    transaction.push_back(item);
                    item = "";
                } else {
                    item += line[i];
                }
            }
            if (!item.empty()) {
                if (items.count(item) == 0) {
                    items[item] = 1;
                } else {
                    items[item]++;
                }
                transaction.push_back(item);
            }
            transactions.push_back(transaction);
        }
        fin.close();
    }

    bool cmp(const pair<string, int>& a, const pair<string, int>& b) {
        return a.second > b.second;
    }

    void buildTree() {
        tree = new FPTree();
        for (int i = 0; i < transactions.size(); i++) {
            vector<string>& transaction = transactions[i];
            sort(transaction.begin(), transaction.end(), [&](string a, string b) {
                return items[a] > items[b];
            });
            tree->insert(transaction);
        }
    }

    void findPrefixPath(string item, Node* node, vector<Node*>& prefixPath) {
        while (node != tree->root) {
            if (node->name == item) {
                prefixPath.push_back(node);
            }
            node = node->parent;
        }
    }

    void mineFrequentItemsets(int minSup) {
        vector<pair<string, int>> freqItems;
        for (auto it = items.begin(); it != items.end(); it++) {
            if (it->second >= minSup) {
                freqItems.push_back(*it);
            }
        }
        sort(freqItems.begin(), freqItems.end(), cmp);
        for (int i = 0; i < freqItems.size(); i++) {
            vector<string> prefix;
            prefix.push_back(freqItems[i].first);
            int sup = freqItems[i].second;
            findPrefixPaths(prefix, tree->headerTable, sup);
        }
    }

    void findPrefixPaths(vector<string>& prefix, map<string, Node*> headerTable, int sup) {
        string item = prefix[prefix.size() - 1];
        Node* node = headerTable[item]->parent;
        vector<Node*> prefixPath;
        while (node != tree->root) {
            prefixPath.clear();
            findPrefixPath(item, node, prefixPath);
            vector<string> subPrefix;
            for (int i = 0; i < prefix.size() - 1; i++) {
                subPrefix.push_back(prefix[i]);
            }
            subPrefix.push_back(node->name);
            int count = node->count;
            for (int i = 0; i < prefixPath.size(); i++) {
                count = min(count, prefixPath[i]->count);
            }
            if (count >= sup) {
                cout << "{";
                for (int i = 0; i < subPrefix.size(); i++) {
                    cout << subPrefix[i] << " ";
                }
                cout << item << "} : " << count << endl;
                findPrefixPaths(subPrefix, node->children, sup);
            }
            node = node->parent;
        }
    }
};

int main() {
    FPGrowth fpg;
    fpg.loadTransactions("transactions.txt");
    fpg.buildTree();
    fpg.mineFrequentItemsets(2);
    return 0;
}

上述代码实现了一个基于类的FP-growth算法，并且支持从文件中加载交易数据，并挖掘出频繁项集。其中，`Node`类表示FP树中的节点，`FPTree`类表示FP树，`FPGrowth`类表示FP-growth算法。具体实现细节可以参考代码注释。

需要注意的是，本示例中的实现仅支持从文件中加载交易数据，并不支持在线实时插入交易数据，如果需要支持在线插入数据，需要对代码进行一定的修改。另外，本示例中的实现也没有进行过多的优化，不适用于大型数据集的挖掘。