fp树.txt

FP树算法源代码 FP树算法源代码 FP树算法源代码

/*----------------------------------------------------------------------
  File    : fpgrowth.h
  Contents: fpgrowth algorithm for finding frequent sets
  Author  : Bart Goethals
  Update  : 4/4/2003
  ----------------------------------------------------------------------*/

class FPgrowth
{
 public:

  FPgrowth();
  ~FPgrowth();

  void setData(char *file, int type){data = new Data(file,type);}
  void setMinsup(unsigned ms){minsup = ms;}
  void setOutput(char *of);
  int mine();

 private:

  unsigned minsup;
  Data *data;
  FPtree *fpt;
 
  FILE *out;
};
 
File    : fpgrowth.cpp
  Contents: fpgrowth algorithm for finding frequent sets
  Author  : Bart Goethals
  Update  : 04/04/2003
  16/04/2003 support of {} also sent to output
  ----------------------------------------------------------------------*/

#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
#include <time.h>
#include "data.h"
#include "item.h"
#include "fptree.h"
#include "fpgrowth.h"

FPgrowth::FPgrowth() : data(0), out(0)
{
  fpt = new FPtree();
}

FPgrowth::~FPgrowth()
{
  if(data) delete data;
  if(fpt) delete fpt;
}

void FPgrowth::setOutput(char *of)
{
  out = fopen(of, "wt");
}

int FPgrowth::mine()
{
  int added=0;
  clock_t start;

  fpt->setMinsup(minsup);
  fpt->setOutput(out);

  start = clock();
  int tmin=1000000, tmax=0, ttotal=0, tnr=0;
  while(Transaction *t = data->getNext()) {
    if(t->length) {
      fpt->processItems(t);
      ttotal += t->length;
      if(t->length < tmin) tmin = t->length;
      if(t->length > tmax) tmax = t->length;
    }
    delete t;
    tnr++;
  }

  cout << "items read [" << (clock()-start)/double(CLOCKS_PER_SEC) << "s]" << endl;

  start = clock();
  fpt->ReOrder();
  fpt->Prune();
  cout << "items reordered and pruned [" << (clock()-start)/double(CLOCKS_PER_SEC) << "s]" << endl;

  start = clock();
  while(Transaction *t = data->getNext()) {
    int i;
    vector<int> list;
    for(i=0; i<t->length; i++) {
      set<Element>::iterator it = fpt->relist->find(Element(t->t,0));
      if(it!=fpt->relist->end()) list.push_back(it->id);
    }
    int size=list.size();
    sort(list.begin(), list.end());
    delete t;

    t = new Transaction(size);
    for(i=0; i<size; i++) t->t = list;
    if(t->length) fpt->processTransaction(t);
    delete t;
  }
  cout << "FPtree constructed [" << (clock()-start)/double(CLOCKS_PER_SEC) << "s]" << endl;

  if(out) fprintf(out,"(%d)
", tnr);

  start = clock();
  int *tmp  = new int[100];
  added = fpt->grow(tmp,1);
  delete [] tmp;
  delete [] FPtree::remap;
  delete FPtree::relist;
  cout << "Frequent sets generated [" << (clock()-start)/double(CLOCKS_PER_SEC) << "s]" << endl;

  return added;
}
 File    : fptree.h
  Contents: fpgrowth algorithm for finding frequent sets
  Author  : Bart Goethals
  Update  : 8/4/2003 - single prefix path bug fixed (Thanks to Xiaonan Wang)
  ----------------------------------------------------------------------*/

#include <set>

using namespace std;

class Element
{
 public:
  Element(int s, int i) : support(s), id(i){}
 
  int support;
  int id;
  bool operator< (const Element  &e) const {return support > e.support;}
};

class FPtree
{
 public:
 
  FPtree();
  ~FPtree();
 
  int processTransaction(Transaction *t, int times=1);
  int processItems(Transaction *t, int times=1);
  void setMinsup(int ms) {minsup = ms;}
  int grow(int *current, int depth);
  void ReOrder();
  int Prune();
  void setOutput(FILE *of) {out =of;}
  void print(int *itemset, int il, int *comb, int cl, int support, int spos=0, int depth=0, int *current=0);

  static int *remap;
  static set<Element> *relist;
 
 private:
 
  set<Item> header;
  set<Item> *root;
  int minsup;
  unsigned nodes;
  bool singlepath;

  FILE *out;
};
File    : fptree.cpp
  Contents: fpgrowth algorithm for finding frequent sets
  Author  : Bart Goethals
  Update  : 08/04/2003 - single prefix path bug fixed (Thanks to Xiaonan Wang)
  ----------------------------------------------------------------------*/

#include <iostream>
#include <stdio.h>
#include <set>
using namespace std;
#include "data.h"
#include "item.h"
#include "fptree.h"

int *FPtree::remap = 0;
set<Element> *FPtree::relist = 0;

FPtree::FPtree()
{
  root = new set<Item>;
  nodes = 0;
  singlepath=true;
}

FPtree::~FPtree()
{
  set<Item>::iterator it;

  for(it = root->begin(); it != root->end(); it++)
    it->removeChildren();
  delete root;
}

int FPtree::processItems(Transaction *t, int times)
{
  set<Item>::iterator head;
  int added=0;

  for(int depth=0; depth < t->length; depth++) {
    head = header.find(Item(t->t[depth], 0));
    if(head == header.end()) {
      head = header.insert(Item(t->t[depth], 0)).first;
      added++;
    }
    head->Increment(times);
  }

  return added;
}

int FPtree::processTransaction(Transaction *t, int times)
{
  set<Item>::iterator it, head;
  set<Item>* items = root;
  Item_ *current = 0;
  int added=0;
 
  for(int depth=0; depth < t->length; depth++) {
    head = header.find(Item(t->t[depth], 0));
    if(head != header.end()) {
      it = items->find(Item(t->t[depth], 0));

      if(it == items->end()) {
 it = items->insert(Item(t->t[depth], current)).first;
 it->setNext(head->getNext());
 head->setNext(it->getItem());
 nodes++;
 added++;
 if(singlepath && (items->size()>1)) singlepath=false;   
      }

      it->Increment(times);
      current = it->getItem();
      items = it->makeChildren();
    }
  }

  return added;
}

int FPtree::grow(int *current, int depth)
{
  int added=0, factor=1;
  if(header.size() == 0) return 0;

  if(singlepath) { 
    int *comb = new int[header.size()];
    int cl=0;
    for(set<Item>::iterator it=header.begin(); it != header.end(); it++) {
      current[depth-1] = it->getId(); 
      print(current,depth,comb,cl,it->getSupport());
      comb[cl++] = it->getId();
      added += factor;
      factor *= 2;
    }
    delete [] comb;
  }
  else {
    for(set<Item>::iterator it=header.begin(); it != header.end(); it++) {
      Item_ *i;
      current[depth-1] = it->getId(); 
      FPtree *cfpt = new FPtree();
      cfpt->setMinsup(minsup);
      cfpt->setOutput(out);

      int *tmp = new int[header.size()];
      for(i = it->getNext(); i; i = i->nodelink) {
 int l=0;
 for(Item_ *p=i->parent; p; p = p->parent) tmp[l++] = p->id;
 Transaction *t = new Transaction(l);
 for(int j=0; j<l; j++) t->t[j] = tmp[l-j-1];
 cfpt->processItems(t,i->supp);
 delete t;
      }
      cfpt->Prune();
      for(i = it->getNext(); i; i = i->nodelink) {
 int l=0;
 for(Item_ *p=i->parent; p; p = p->parent) tmp[l++] = p->id;
 Transaction *t = new Transaction(l);
 for(int j=0; j<l; j++) t->t[j] = tmp[l-j-1];
 cfpt->processTransaction(t,i->supp);
 delete t;
      }
      delete [] tmp;
      print(current,depth,0,0,it->getSupport());
      added ++;
      added += cfpt->grow(current,depth+1);
      delete cfpt;
    }
  }
  return added;
}

int FPtree::Prune()
{
  int left=0;
 
  for(set<Item>::iterator it = header.begin();it != header.end(); ) {
    if(it->getSupport() < minsup) {
      set<Item>::iterator tmp = it++;
      header.erase(tmp);
    }
    else {
      left++;
      it++;
    }
  }
  return left;
}

void FPtree::ReOrder()
{
  set<Item>::iterator itI;
  multiset<Element>::iterator itE;
  multiset<Element> list;
 
  for(itI = header.begin(); itI != header.end(); itI++)
    list.insert(Element(itI->getSupport(), itI->getId()));
 
  remap = new int[list.size()+1];
  relist = new set<Element>;
  header.clear();
  int i=1;
  for(itE=list.begin(); itE!=list.end(); itE++) {
    if(itE->support >= minsup) {
      remap = itE->id;
      relist->insert(Element(itE->id,i));
      Item a(i,0);
      itI = header.insert(a).first;
      itI->Increment(itE->support);
      i++;
    }
  }
}

void FPtree::print(int *itemset, int il, int *comb, int cl, int support, int spos, int depth, int *current)
{
  if(current==0) {
    if(out) {
      set<int> outset;
      for(int j=0; j<il; j++) outset.insert(remap[itemset[j]]); 
      for(set<int>::iterator k=outset.begin(); k!=outset.end(); k++) fprintf(out, "%d ", *k);
      fprintf(out, "(%d)
", support);
      if(cl) {
 current = new int[cl];
 print(itemset,il,comb,cl,support,0,1,current);
 delete [] current;
      }
    }
  }
  else {
    int loper = spos;
    spos = cl;
    while(--spos >= loper) {
      set<int> outset;
      current[depth-1] = comb[spos];
      for(int i=0; i<depth; i++) outset.insert(remap[current]); 
      for(int j=0; j<il; j++) outset.insert(remap[itemset[j]]); 
      for(set<int>::iterator k=outset.begin(); k!=outset.end(); k++) fprintf(out, "%d ", *k);