fpgrowth.cpp

FP-Growth算法

/*----------------------------------------------------------------------
  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"
extern FILE *ResultOut;
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");
  ResultOut=out;;
}

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++;
  }
  start = clock();
  fpt->ReOrder();         //程序到目前为止遍历了一遍数据，并且按照出现的多少排序
  fpt->Prune();       //根据输入的第3个参数来去掉一些不能产生符合条件的关联规则.

  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[i],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[i] = list[i];
    if(t->length) fpt->processTransaction(t);
    delete t;
  }

  if(out) fprintf(out,"(事务个数 %d)\n", tnr);

  start = clock();
  int *tmp  = new int[100];
  added = fpt->grow(tmp,1);
  delete [] tmp;
  delete [] FPtree::remap;
  delete FPtree::relist;

  return added;
}