fptree.cpp

FP-GROWTH算法实现数据挖掘中的关联规则

/*----------------------------------------------------------------------
  File    : fptree.cpp
  Contents: fpgrowth algorithm for finding frequent sets
    Update  : 12/3/2005 - 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);
      fprintf(out, "(%d)
", support);
      print(itemset, il, comb, cl, support, spos+1, depth+1, current);
    }
  }
}