fp树.txt

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

      fprintf(out, "(%d)
", support);
      print(itemset, il, comb, cl, support, spos+1, depth+1, current);
    }
  }
}
File    : item.h
  Contents: itemset management
  Author  : Bart Goethals
  Update  : 4/4/2003
  ----------------------------------------------------------------------*/

#include <set>

using namespace std;

class Item;

class Item_
{
 public:
 
  Item_();
  ~Item_();
 
 
  int id;
  int supp;
 
  set<Item> *children;
 
  Item_ *parent;
  Item_ *nodelink;
};

class Item
{
 public:
 
  Item(int s, Item_ *p);
  Item::Item(const Item& i);
  ~Item();
 
  int getId() const {return item->id;}  
  int getSupport() const {return item->supp;}
 
  set<Item> *getChildren() const {return item->children;}
  set<Item> *makeChildren() const;
 
  Item_ *getItem() const {return item;}
  Item_ *getNext() const {return item->nodelink;}
  void setNext(Item_ *i) const {item->nodelink = i;}
  bool isFrequent(int ms) const {return item->supp >= ms;}
  void Increment(int i=1) const {item->supp += i;}
 
  void removeChildren() const;
 
  bool operator< (const Item &i) const {return getId() < i.getId();}

 private:
 
  Item_ *item;
};
File    : item.cpp
  Contents: itemset management
  Author  : Bart Goethals
  Update  : 04/04/2003
  ----------------------------------------------------------------------*/

#include <stdio.h>
#include "item.h"

Item_::Item_()
{
  supp = 0;
  parent = 0;
  nodelink = 0;
  id = 0;
  children = 0;
}

Item_::~Item_()
{}

Item::Item(int s, Item_ *p)
{
  item = new Item_();
  item->id = s;
  item->parent = p;
}

Item::Item(const Item& i)
{
  Item_ *tmp = i.getItem();

  item = new Item_();
  item->id  = tmp->id;
  item->parent = tmp->parent;
  item->children = tmp->children;
  item->nodelink = tmp->nodelink;
  item->supp = tmp->supp;
}

Item::~Item()
{
  delete item;
}

set<Item> *Item::makeChildren() const
{
  if(item->children==0) item->children = new set<Item>;
  return item->children;
}


void Item::removeChildren() const
{
  set<Item> *items = item->children;
  for(set<Item>::iterator it = items->begin();it != items->end(); it++) it->removeChildren();
  delete item->children;
  item->children = 0;
}
File    : Data.h
  Contents: data set management
  Author  : Bart Goethals
  Update  : 4/4/2003
  ----------------------------------------------------------------------*/

#include <stdio.h>

class Transaction
{
 public:
 
  Transaction(int l) : length(l) {t = new int[l];}
  Transaction(const Transaction &tr);
  ~Transaction(){delete [] t;}
 
  int length;
  int *t;
};

class Data
{
 public:
 
  Data(char *filename, int t=0);
  ~Data();
 
  Transaction *getNext();

 private:
 
  Transaction *getNextAs();
  Transaction *getNextAsFlat();
  Transaction *getNextAsQuest();
  Transaction *getNextBin();
 
  FILE *in;
  char *fn;
  int current;
  int type;
};
 
File    : data.cpp
  Contents: data set management
  Author  : Bart Goethals
  Update  : 04/04/2003
  ----------------------------------------------------------------------*/

#include <vector>
using namespace std;
#include "data.h"

Transaction::Transaction(const Transaction &tr)
{
  length = tr.length;
  t = new int[tr.length];
  for(int i=0; i< length; i++) t = tr.t;
}

Data::Data(char *filename, int t)
{
  fn = filename;
  type = t;
  current=0;

  if(type>1) in = fopen(fn,"rt");
  else in = fopen(fn,"rb");
}

Data::~Data()
{
  if(in) fclose(in);
}

Transaction *Data::getNext()
{
  Transaction *t=0;

  switch(type){
  case 1: t= getNextBin(); break;
  case 2: t= getNextAs(); break;
  case 3: t= getNextAsFlat(); break;
  case 4: t= getNextAsQuest(); break;
  }

  if(t) current++;
  else {
    rewind(in);
    current=0;
  }

  return t;
}

Transaction *Data::getNextAs() 
{
  Transaction *t;
  int tid, item, i, dummy;
  vector<int> list;
  static int cur=0,prev=-1;
  static bool begin=true;
  
  if(feof(in)) {
    begin=true;
    prev=-1;
    return 0;
  }

  if(!begin) list.push_back(cur);
  else begin=false;

  while(true) {
    fscanf(in, "%d %d %d",&dummy, &tid, &item);
    if(feof(in)) {
      int size=list.size();
      t = new Transaction(size);
      for(i=0; i<size; i++) t->t = list;
      list.clear();

      return t;
    }
    else if(prev<0) prev=tid;
    else if(tid != prev){
      prev = tid;
      cur = item;
      int size=list.size();
      t = new Transaction(size);
      for(i=0; i<size; i++) t->t = list;
      list.clear();
   
      return t;
    }

    list.push_back(item);
  }
}

Transaction *Data::getNextAsFlat()
{
  vector<int> list;
  char c;

  // read list of items
  do {
    int item=0, pos=0;
    c = getc(in);
    while((c >= '0') && (c <= '9')) {
      item *=10;
      item += int(c)-int('0');
      c = getc(in);
      pos++;
    }
    if(pos) list.push_back(item);
  }while(c != '
' && !feof(in));
  
  // if end of file is reached, rewind to beginning for next pass
  if(feof(in)){
    rewind(in);
    return 0;
  }
  // Note, also last transaction must end with newline, 
  // else, it will be ignored
  
  // sort list of items
  // sort(list.begin(),list.end());

  // put items in Transaction structure
  Transaction *t = new Transaction(list.size());
  for(int i=0; i<int(list.size()); i++)
    t->t = list;

  return t;
}

Transaction *Data::getNextAsQuest()
{
  int tmptid, tid,l,i;
  Transaction *t;
 
  fscanf(in,"%d %d %d",&tmptid,&tid,&l);
  if(feof(in)) return 0;
 
  t = new Transaction(l);
  for(i=0; i<l; i++) fscanf(in,"%d",&t->t);
  return t;
}

Transaction *Data::getNextBin()
{
  int tmptid, tid,l,i;
  Transaction *t;
 
  fread(&tmptid,4, 1,in);
  if(feof(in)) return 0;
 
  fread(&tid,4, 1,in);
  fread(&l,4, 1,in);
  t = new Transaction(l);
  for(i=0; i<l; i++) fread(&t->t,4, 1,in);

  return t;
}
File     : testfpgrowth.cpp
  Contents : FP-growth algorithm for finding frequent sets
  Author   : Bart Goethals
  Update   : 04/04/2003
----------------------------------------------------------------------*/

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

int main(int argc, char *argv[])
{
  cout << "FP-growth frequent itemset mining implementation" << endl;
  cout << "by Bart Goethals, 2000-2003" << endl;
  cout << "http://www.cs.helsinki.fi/u/goethals/" << endl << endl;
  
  if(argc < 4){
    cerr << "usage: " << argv[0] << " datafile datatype minsup [output]" << endl;
    cerr << "datatype = 1 for Quest datagenerator binary" << endl;
    cerr << "datatype = 2 for Quest datagenerator ascii" << endl;
    cerr << "datatype = 3 for flat, i.e. all items per transaction on a single line" << endl;
    cerr << "datatype = 4 for ascii version of Quest datagenerator binary" << endl;
  }
  else{
    FPgrowth *fpgrowth = new FPgrowth();
    
    fpgrowth->setData(argv[1],atoi(argv[2]));
    fpgrowth->setMinsup(atoi(argv[3]));
    if(argc==5) fpgrowth->setOutput(argv[4]);
    
    clock_t start = clock();
    int added = fpgrowth->mine();
    cout << added << "\t[" << (clock()-start)/double(CLOCKS_PER_SEC) << "s]" << endl;
    if(argc==5) cout << "Frequent sets written to " << argv[4] << endl;
    
    delete fpgrowth;
  }
  
  return 0;
}