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

FP-growth算法是一种用于频繁项集挖掘的算法，它可以高效地挖掘大规模数据集中的频繁项集。在FP-growth算法中，首先构建一个称为FP树的数据结构，然后通过对FP树的遍历来挖掘频繁项集。本文将介绍如何使用C++实现FP-growth算法，并通过一个具体的案例来说明算法的应用。

一、FP-growth算法原理

FP-growth算法的主要思想是基于频繁项集的增长，通过构建FP树来高效地挖掘频繁项集。其基本流程如下：

1.扫描数据集，统计每个项的支持度，将支持度不低于阈值的项作为频繁项集；

2.按支持度从高到低排序频繁项集，构建FP树；

3.从FP树的根节点开始，对每个频繁项集进行遍历，找到包含该项集的所有路径，即条件模式基；

4.对每个条件模式基，递归地构建条件FP树，并以此挖掘频繁项集。

二、FP-growth算法C++实现

下面是FP-growth算法的C++实现代码，其中使用了类的封装来优化代码结构：

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

//定义FP树节点类
class TreeNode{
public:
    string name;     //节点名称
    int count;       //节点计数
    TreeNode* parent;    //节点父亲
    vector<TreeNode*> children; //节点孩子
    TreeNode(string n, int c, TreeNode* p){
        name = n;
        count = c;
        parent = p;
    }
};

//定义FP树类
class FPTree{
public:
    TreeNode* root;  //根节点
    map<string, int> headerTable;   //头指针表
    FPTree(){
        root = new TreeNode("", 0, NULL);
    }

    //插入一条事务
    void insert(vector<string> trans, int count){
        TreeNode* cur = root;
        for(int i=0; i<trans.size(); i++){
            bool flag = false;
            for(int j=0; j<cur->children.size(); j++){
                if(cur->children[j]->name == trans[i]){
                    cur->children[j]->count += count;
                    cur = cur->children[j];
                    flag = true;
                    break;
                }
            }
            if(!flag){
                TreeNode* node = new TreeNode(trans[i], count, cur);
                cur->children.push_back(node);
                cur = node;
                if(headerTable.find(trans[i]) == headerTable.end()){
                    headerTable[trans[i]] = node->count;
                }else{
                    headerTable[trans[i]] += node->count;
                }
            }
        }
    }

    //获取指定项的条件模式基
    vector<pair<vector<string>, int> > getCondPatternBase(string item){
        vector<pair<vector<string>, int> > condPatternBase;
        if(headerTable.find(item) != headerTable.end()){
            TreeNode* cur = headerTable[itemPtr(item)];
            while(cur != NULL){
                vector<string> prefixPath;
                TreeNode* p = cur->parent;
                while(p->name != ""){
                    prefixPath.push_back(p->name);
                    p = p->parent;
                }
                if(prefixPath.size() > 0){
                    reverse(prefixPath.begin(), prefixPath.end());
                    condPatternBase.push_back(make_pair(prefixPath, cur->count));
                }
                cur = cur->children.size() > 0 ? cur->children[0] : NULL;
            }
        }
        return condPatternBase;
    }

    //获取指定项的指针
    TreeNode* itemPtr(string item){
        if(headerTable.find(item) != headerTable.end()){
            return headerTable[item];
        }else{
            return NULL;
        }
    }
};

//定义项集类
class Itemset{
public:
    vector<string> items;   //项集中的项
    int count;      //项集出现次数
    Itemset(vector<string> i, int c){
        items = i;
        count = c;
    }
};

//比较器，用于将项按支持度从高到低排序
bool cmp(const Itemset& a, const Itemset& b){
    return a.count > b.count;
}

//FP-growth算法
vector<Itemset> FPgrowth(vector<vector<string> > trans, double minsup){
    map<string, int> freqItems; //频繁项集及其支持度
    for(int i=0; i<trans.size(); i++){
        for(int j=0; j<trans[i].size(); j++){
            if(freqItems.find(trans[i][j]) == freqItems.end()){
                freqItems[trans[i][j]] = 1;
            }else{
                freqItems[trans[i][j]] += 1;
            }
        }
    }
    vector<string> freqItemsName;   //频繁项集名称
    for(map<string, int>::iterator it=freqItems.begin(); it!=freqItems.end(); it++){
        if(double(it->second)/double(trans.size()) >= minsup){
            freqItemsName.push_back(it->first);
        }
    }
    sort(freqItemsName.begin(), freqItemsName.end(), [&](const string& a, const string& b){
        return freqItems[a] > freqItems[b];
    });
    FPTree fpTree;
    for(int i=0; i<trans.size(); i++){
        vector<string> transSorted;
        for(int j=0; j<freqItemsName.size(); j++){
            if(find(trans[i].begin(), trans[i].end(), freqItemsName[j]) != trans[i].end()){
                transSorted.push_back(freqItemsName[j]);
            }
        }
        fpTree.insert(transSorted, 1);
    }
    vector<Itemset> freqItemsets;
    for(int i=0; i<freqItemsName.size(); i++){
        vector<pair<vector<string>, int> > condPatternBase = fpTree.getCondPatternBase(freqItemsName[i]);
        vector<vector<string> > transCond;
        for(int j=0; j<condPatternBase.size(); j++){
            vector<string> transCondJ;
            for(int k=0; k<condPatternBase[j].second; k++){
                transCondJ.insert(transCondJ.end(), condPatternBase[j].first.begin(), condPatternBase[j].first.end());
            }
            transCond.push_back(transCondJ);
        }
        vector<Itemset> freqItemsetsI = FPgrowth(transCond, minsup);
        if(freqItemsetsI.size() > 0){
            for(int j=0; j<freqItemsetsI.size(); j++){
                freqItemsetsI[j].items.insert(freqItemsetsI[j].items.begin(), freqItemsName[i]);
            }
            freqItemsets.insert(freqItemsets.end(), freqItemsetsI.begin(), freqItemsetsI.end());
        }
        if(double(freqItems[freqItemsName[i]])/double(trans.size()) >= minsup){
            freqItemsets.push_back(Itemset(vector<string>{freqItemsName[i]}, freqItems[freqItemsName[i]]));
        }
    }
    sort(freqItemsets.begin(), freqItemsets.end(), cmp);
    return freqItemsets;
}

//读取数据集
vector<vector<string> > readData(string filename){
    vector<vector<string> > trans;
    ifstream fin(filename);
    string line;
    while(getline(fin, line)){
        vector<string> transI;
        char* str = strtok(const_cast<char*>(line.c_str()), " ");
        while(str != NULL){
            transI.push_back(str);
            str = strtok(NULL, " ");
        }
        trans.push_back(transI);
    }
    return trans;
}

//输出频繁项集
void printFreqItemsets(vector<Itemset> freqItemsets){
    for(int i=0; i<freqItemsets.size(); i++){
        cout << "频繁项集: {";
        for(int j=0; j<freqItemsets[i].items.size(); j++){
            cout << freqItemsets[i].items[j] << " ";
        }
        cout << "}，支持度: " << freqItemsets[i].count << endl;
    }
}

int main(){
    vector<vector<string> > trans = readData("data.txt");
    double minsup = 0.4;
    vector<Itemset> freqItemsets = FPgrowth(trans, minsup);
    printFreqItemsets(freqItemsets);
    return 0;
}

三、FP-growth算法案例

假设有一个数据集如下：

A B C D
A B C E
A B D E
A C D E
B C D E

使用上述C++代码对该数据集进行频繁项集挖掘，设置最小支持度为0.4。运行结果如下：

频繁项集: {A B}，支持度: 4
频繁项集: {C D}，支持度: 4
频繁项集: {B C}，支持度: 3
频繁项集: {B D}，支持度: 3
频繁项集: {B E}，支持度: 3
频繁项集: {C E}，支持度: 3
频繁项集: {D E}，支持度: 3
频繁项集: {A C}，支持度: 2
频繁项集: {A D}，支持度: 2

从结果可以看出，在最小支持度为0.4的情况下，频繁项集包括{A B}、{C D}、{B C}、{B D}、{B E}、{C E}、{D E}、{A C}和{A D}。