apriorisets.cpp

data mining description

/*----------------------------------------------------------------------
  File     : AprioriSets.cpp
  Contents : apriori algorithm for finding frequent sets
  Author   : Bart Goethals
  Update   : 1/6/2003 
  ----------------------------------------------------------------------*/
#include "stdafx.h"
#include <time.h>
#include <algorithm>
#include <iostream>
#include <time.h>
using namespace std;
#include "AprioriSets.h"

AprioriSets::AprioriSets()
{
  data=0;
  minsup=0;
  remap=0;
  relist=0;
  trie = new Item(0);
  verbose = false;
  countType = 1;
}

AprioriSets::~AprioriSets()
{
  if(data) delete data;
  if(trie) {
    trie->deleteChildren();
    delete trie;
  }
  if(remap) delete remap;
  if(relist) delete relist;
}

void AprioriSets::setData(char *fn, int type)
{
  data = new Data(fn, type);
}

int AprioriSets::setOutputSets(char *fn)
{
  setsout.open(fn);
  if(!setsout.is_open()) {
    cerr << "error: could not open " << fn << endl;
    return -1;
  }
  return 0;
}

int AprioriSets::generateSets()
{
  int total=0, pass=0;
  bool running = true;

  while(running) {
    clock_t start;
    int generated=0, nodes=0, tnr=0, pruned;

    pass++;
    cout << pass << " " << flush;

    if(pass>2) {
      start = clock();
      generated = generateCandidates(pass);
      nodes = pruneNodes(pass);
      if(verbose) cout << generated << " [" << (clock()-start)/double(CLOCKS_PER_SEC) << "s] " << flush;
    }

    start = clock();
    tnr = countCandidates(pass);
    if(verbose) {
      if(pass == 1) cout << trie->getChildren()->size() << " ";
      cout << tnr << " [" << (clock()-start)/double(CLOCKS_PER_SEC) << "s] " << flush;
    }

    if(pass==1 && setsout.is_open()) printSet(*trie,0,0); 

    start = clock();
    pruned = pruneCandidates(pass);
    if(verbose) cout << pruned << " [" << (clock()-start)/double(CLOCKS_PER_SEC) << "s]\n" << flush;

    if(pass==1) ReOrder(); // Reorder all items

    total += pruned;
    if(pruned <= pass) running = false;
  }

  cout << endl;

  return total;
}

int AprioriSets::generateCandidates(int level)
{
  int *tmp = new int[level];
  int generated = generateCandidates(level, trie->getChildren(), 1, tmp);
  delete [] tmp;

  return generated;
}

int AprioriSets::generateCandidates(int level, set<Item> *items, int depth, int *current)
{
  if(items == 0) return 0;

  int generated = 0;
  set<Item>::reverse_iterator runner;

  if(depth == level-1) {
    for(runner = items->rbegin(); runner != items->rend(); runner++) {
      current[depth-1] = runner->getId();
      set<Item> *children = runner->makeChildren();

      for(set<Item>::reverse_iterator it = items->rbegin(); it != runner; it++) {
	current[depth] = it->getId();
	if(level<=2 || checkSubsets(level,current, trie->getChildren(), 0, 1)) {
	  children->insert(Item(it->getId()));
	  generated++;
	}
      }
    }
  }
  else {
    for(runner = items->rbegin(); runner != items->rend(); runner++) {
      current[depth-1] = runner->getId();
      generated += generateCandidates(level, runner->getChildren(), depth+1, current);
    }
  }
  return generated;
}

bool AprioriSets::checkSubsets(int sl, int *iset, set<Item> *items, int spos, int depth)
{
  if(items==0) return 0;

  bool ok = true;
  set<Item>::iterator runner;
  int loper = spos;
  spos = depth+1;

  while(ok && (--spos >= loper)) {
    runner = items->find(Item(iset[spos]));
    if(runner != items->end()) {
      if(depth<sl-1) ok = checkSubsets(sl, iset, runner->getChildren(), spos+1, depth+1);
    }
    else ok=false;
  }

  return ok;
}

int AprioriSets::pruneNodes(int level)
{
  return pruneNodes(level,trie->getChildren(),1);
}

int AprioriSets::pruneNodes(int level, set<Item> *items, int depth)
{
  if(items == 0) return 0;

  int nodes = 0;

  if(depth==level) nodes = items->size();
  else {
    for(set<Item>::iterator runner = items->begin(); runner != items->end(); ) {
      int now = pruneNodes(level, runner->getChildren(), depth+1);
      if(now) {
	nodes += now;
	nodes++;
	runner++;
      }
      else {
	runner->deleteChildren();
	set<Item>::iterator tmp = runner++;
	items->erase(tmp);
      }
    }
  }

  return nodes;
}

int AprioriSets::countCandidates(int level)
{
  int trans=0;

  // count all single items
  if(level==1) {