eclat.hpp

Go to the documentation of this file.

#ifndef __ECLAT_HPP_
#define __ECLAT_HPP_ t

// feature flags:


#ifdef ECLAT_DEFECT
static const bool EXTENSION_DESCRIPTION_DEFECTS = true; // false means: COVERS
static const bool OMIT_FINAL_INCIDENCE_MATRIX = true;
static const bool PRUNE_EQUISUPPORT_EXTENSIONS = true;
static const bool EARLY_FILTERING = true;
//static const bool EARLY_FILTERING = false;
static const bool INTERSECTION_ROWSWAPPING = false; // false seems to give better results.
#endif

#ifdef ECLAT_COVER
static const bool EXTENSION_DESCRIPTION_DEFECTS = false; // false means: COVERS
static const bool OMIT_FINAL_INCIDENCE_MATRIX = true;
static const bool PRUNE_EQUISUPPORT_EXTENSIONS = true;
static const bool EARLY_FILTERING = true;
//static const bool EARLY_FILTERING = false;
static const bool INTERSECTION_ROWSWAPPING = false; // false seems to give better results.
#endif


// #include "SparseBitmatrix.hpp"
#include "SparseBitmatrix_create.hpp"
#include "SparseBitmatrix_setdifference.hpp"
#include "SparseBitmatrix_intersection.hpp"
//#include "SparseBitmatrix_intersection_membervariables-v2.hpp"

#include "common/debug.hpp"
#include "io/input/transaction_reader/TransactionReader.hpp"
#include "common.hpp"

#include <vector>

// debugging options:
static const bool OUTPUT_HINTS = false;



template <class TRANSACTION_READER, class PATTERN_WRITER>
class Eclat 
{
public:
  Eclat(TRANSACTION_READER& tdb, CounterItemPairs& freqItems, int minSup, int numTransactions, PATTERN_WRITER& out) :
    tdb(tdb), freqItems(freqItems), minSup(minSup), numTransactions(numTransactions), out(out)
  {
    MAX_PATTERN_LENGTH = 1000; // FIXME: should be numItems for sets.
    ptis = new (SparseBitmatrix*)[MAX_PATTERN_LENGTH];
    eeIterator = new typename PATTERN_WRITER::EquisupportItemOutputIterator(out);
  }
  ~Eclat() {};

  void findFrequentPatterns();
  
private:
  TRANSACTION_READER& tdb;
  CounterItemPairs& freqItems;
  int minSup;
  int numTransactions;
  PATTERN_WRITER& out;

  typename PATTERN_WRITER::EquisupportItemOutputIterator* eeIterator;

  // int numItems;
  int MAX_PATTERN_LENGTH;

  int depth;

  int maxdefect;

  SparseBitmatrix** ptis;

  void checkUpToTwoRows(SparseBitmatrix* iti, counter_t minSup, counter_t maxdefect);

  void depthFirstWalk();


};


template <class TRANSACTION_READER, class PATTERN_WRITER>
void Eclat<TRANSACTION_READER, PATTERN_WRITER>::findFrequentPatterns() {
  // 0. write empty pattern
  if (numTransactions >= minSup)
    out.write(numTransactions);
  
  // 1. build item/transaction incidence matrix:
  std::cout << "build item/transaction incidence matrix..." << std::flush;
  SparseBitmatrix* iti = createSparseItemTransactionIncidenceMatrix(tdb, freqItems);
  int numItems = freqItems.size();
  std::cout << " - done" << std::endl;

#if DEBUG_LEVEL >= 20  
  std::cout << "iti:" << std::endl;
  iti->dump();
#endif

#if DEBUG_LEVEL >= 20  
  std::cout << "item freqs: ";
  for(CounterItemPairs::iterator it_freqItems = freqItems.begin(); it_freqItems != freqItems.end(); ++it_freqItems )
    std::cout << it_freqItems->first << " "; 
  std::cout << endl;
#endif

  // if we do COVERS and not DEFECTS
  if (! EXTENSION_DESCRIPTION_DEFECTS) { // COVERS:
    std::cout << "compute covers..." << std::flush;
    for (int i = 0; i < MAX_PATTERN_LENGTH; i++)
      ptis[i] = NULL;
    ptis[0] = iti;
    depth = 0;
    depthFirstWalk();
    std::cout << " - done" << std::endl;
    return;
  }

  // 2. allocate space:
  int rowCapacityIti2 = iti->computeMaxRowLength();
  if (EARLY_FILTERING) 
    rowCapacityIti2 -= minSup;
  SparseBitmatrix* iti2 = new SparseBitmatrix(numItems-1, rowCapacityIti2); // This will eat all your memory, although it is optimal.
  depth = 1;
  // for (int i = 0; i < MAX_PATTERN_LENGTH; i++)
  //   ptis[i] = NULL;
  ptis[0] = iti;
  ptis[1] = iti2;

  // 3. compute set differences of all row pairs:
  std::cout << "compute defects..." << std::flush;
  // int* itiRowLengths = iti->rowLengths;
  // int* itiRowLabels = iti->rowLabels;
  for (int i = 0; i < numItems-1; i++) {
    // b. output 1-itemsets:
    assert(i >= 0 && i < iti->nRows());
    out.pushItem(iti->rowLabel(i)); // itiRowLabels[i]);
    int itiRowLengthi = iti->rowLength(i); // itiRowLengths[i];
    // c. compute 2-itemsets via initial set differences and walk:
    maxdefect = itiRowLengthi - minSup;
    int numPairs = setdifferenceOfSparseBitmatrix<EARLY_FILTERING,PRUNE_EQUISUPPORT_EXTENSIONS>(*iti, i, *iti2, maxdefect, *eeIterator);

    if (numPairs > 0)
      depthFirstWalk();
    
    out.write(itiRowLengthi);
    out.popItem();
  }
  // d. output last 1-itemsets:
  out.pushItem(iti->rowLabel(numItems-1)); // itiRowLabels[numItems-1]);
  out.write(iti->rowLength(numItems-1)); // itiRowLengths[numItems-1]); 
  std::cout << " - done" << std::endl;
}



template <class TRANSACTION_READER, class PATTERN_WRITER>
void Eclat<TRANSACTION_READER, PATTERN_WRITER>::checkUpToTwoRows(SparseBitmatrix* iti, 
                                                                 counter_t minSup, counter_t maxdefect) {
  assert(iti->nRows() <= 2);

  // 1. record pattern for row[0]:
  out.pushItem(iti->rowLabel(0));
  if (OUTPUT_HINTS) out.hint(string("a"));
  out.write(EXTENSION_DESCRIPTION_DEFECTS  
            ? minSup+maxdefect-iti->rowLength(0)
            : iti->rowLength(0)); 
  out.popItem();
  
  if (iti->nRows() == 2) {
    // 2. record pattern for row[1]:
    out.pushItem(iti->rowLabel(1)); 
    if (OUTPUT_HINTS) out.hint(string("b"));
    out.write(EXTENSION_DESCRIPTION_DEFECTS  
              ? minSup+maxdefect-iti->rowLength(1)
              : iti->rowLength(1)); 
    out.popItem();

    // 3. compute |row1 \ row0|
    int maxdef0 = maxdefect - iti->rowLength(0);
    int rowlen01 = EXTENSION_DESCRIPTION_DEFECTS
      ? cardinalitySetdifferenceBySparseBitmatrix_TwoRows<EARLY_FILTERING>(*iti, maxdef0)
      : cardinalityIntersectionSparseBitmatrix_TwoRows<EARLY_FILTERING>(*iti, minSup);
    if ((EXTENSION_DESCRIPTION_DEFECTS 
         ? rowlen01 <= maxdef0
         : rowlen01 >= minSup)) {
      // 4. record pattern for row[0]+row[1]:
      out.pushItem(iti->rowLabel(0));
      out.pushItem(iti->rowLabel(1)); 
      if (OUTPUT_HINTS) out.hint(string("c"));
      out.write(EXTENSION_DESCRIPTION_DEFECTS  
                ? minSup+maxdef0-rowlen01
                : rowlen01);
      out.popItem();
      out.popItem();
    }
  }
}

template <class TRANSACTION_READER, class PATTERN_WRITER>
void Eclat<TRANSACTION_READER, PATTERN_WRITER>::depthFirstWalk() {
#if DEBUG_LEVEL >= 10
  cout << endl
       << out.getCurrentPatternAsString() << " "
       << " (maxdefect=" << maxdefect << ", depth = " << depth <<", nrows = " << ptis[depth]->nRows() << "):" << endl;
#endif
#if DEBUG_LEVEL >= 30
  ptis[depth]->dump();
#endif

  // 1. allocate new bit matrix if necessary:
  assert(ptis[depth] != NULL);
  SparseBitmatrix* pti = ptis[depth];
  
  SparseBitmatrix* bmOut;
  if (OMIT_FINAL_INCIDENCE_MATRIX || pti->nRows() >= 2) { // (ALLOC_ITI_PRE_LOCAL)
    if (EXTENSION_DESCRIPTION_DEFECTS) {
      int rowCapacity = pti->maxRowLength(); // second-largest would do, but as rowlengths are not guaranteed to decrease this in general is *NOT* pti->rowLengths[1]
      if (EARLY_FILTERING && maxdefect < rowCapacity)
        rowCapacity = maxdefect; // [lst 2005/05/04] fixed now. was +1 as otherwise we get SEGFAULTS: setdifference seemed to go one beyond what is necessary.
      bmOut = new SparseBitmatrix(pti->nRows()-1, rowCapacity);
    } else { // if (EXTENSION_DESCRIPTION_COVERS)
      bmOut = ptis[depth+1];
      if (bmOut == NULL)
        bmOut = new SparseBitmatrix(ptis[0]->nRows()-depth-1, &(ptis[0]->capacities()[depth+1]));
      // bmOut = new SparseBitmatrix(ptis[0]->nRows()-depth-1, &(ptis[0]->capacity(depth+1)));
    // bmOut = new SparseBitmatrix(pti->numRows-1, pti->maxRowLength);
    }
    ptis[depth+1] = bmOut;
  } else
    bmOut = NULL;

  int numSiblings = pti->nRows();
  
  // 2. walk children:
  depth++;
  for (int i = 0; i < numSiblings-1; i++) {
    assert(i < pti->capacity());
    // a. add item to pattern:
    out.pushItem(pti->rowLabel(i));
    
    // b. compute intersection:
    int numSiblingsNext; 
    if (EXTENSION_DESCRIPTION_DEFECTS) {
      numSiblingsNext = setdifferenceBySparseBitmatrix<EARLY_FILTERING,PRUNE_EQUISUPPORT_EXTENSIONS>(*pti, i, *bmOut, maxdefect-pti->rowLength(i), *eeIterator);
      if (numSiblingsNext > 0) {
        maxdefect -= pti->rowLength(i);
        if (OMIT_FINAL_INCIDENCE_MATRIX && numSiblingsNext <= 2)
          checkUpToTwoRows(bmOut, minSup, maxdefect);
        else
          depthFirstWalk(); 
        maxdefect += pti->rowLength(i);
      }
    } else { // if (EXTENSION_DESCRIPTION_COVERS)
      numSiblingsNext = intersectSparseBitmatrix<EARLY_FILTERING, INTERSECTION_ROWSWAPPING, PRUNE_EQUISUPPORT_EXTENSIONS>(*pti, i, *bmOut, minSup, *eeIterator);
      if (numSiblingsNext > 0) 
        depthFirstWalk(); 
    }
    
    // c. record base pattern:
    assert(i >= 0 && i < pti->numRows);
    if (OUTPUT_HINTS) out.hint(string("d"));
    out.write(EXTENSION_DESCRIPTION_DEFECTS  
              ? minSup+maxdefect-pti->rowLength(i)
              : pti->rowLength(i)); 
    out.popItem();
  }
  
  // 3. write last pattern:
  int i = numSiblings-1;
  out.pushItem(pti->rowLabel(i)); 
  if (OUTPUT_HINTS) out.hint(string("e"));
    out.write(EXTENSION_DESCRIPTION_DEFECTS 
              ? minSup+maxdefect-pti->rowLength(i)
              : pti->rowLength(i)); 
  out.popItem();

  // 4. delete old bit matrix (ALLOC_ITI_PRE_LOCAL)
  if (EXTENSION_DESCRIPTION_DEFECTS && bmOut != NULL) { // for COVERS we have ALLOC_ITI_PRE_GLOBAL
    delete bmOut;  // = ptis[depth];
    ptis[depth] = NULL;
  }
  
  depth--;
}


#endif

---