apriori.h

/**************************************************************************
 * Copyright (c) 2004-2011 T. M. Murali                                   *
 * Copyright (c) 2004 Greg Grothaus                                       *
 *                                                                        *
 * This file is part of Biorithm.                                         *
 *                                                                        *
 * Biorithm is free software: you can redistribute it and/or modify       *
 * it under the terms of the GNU General Public License as published by   *
 * the Free Software Foundation, either version 3 of the License, or      *
 * (at your option) any later version.                                    *
 *                                                                        *
 * Biorithm is distributed in the hope that it will be useful,            *
 * but WITHOUT ANY WARRANTY; without even the implied warranty of         *
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the          *
 * GNU General Public License for more details.                           *
 *                                                                        *
 * You should have received a copy of the GNU General Public License      *
 * along with Biorithm.  If not, see <http://www.gnu.org/licenses/>.      *
 *                                                                        *
 **************************************************************************/

#ifndef APRIORI
#define APRIORI

#include<iostream>
#include<fstream>
#include<map>
#include<string>
#include<sstream>
#include<vector>
#include<algorithm>


using namespace std;

#include "dag.h"
#include "itemset.h"
#include "histogram.h"

// start at 1 since  0 will correspond to the union of all edge types
// (LATTICE_GENERIC_EDGE). LATTICE_COMPLEMENT is used by
// AprioriWithComplement to indicate that the parent contains rows
// that are complements of the rows in the child.
enum AprioriLatticeEdgeType { LATTICE_NO_EDGE = -1, LATTICE_GENERIC_EDGE = 0, LATTICE_EDGE = 1, LATTICE_COMPLEMENT_EDGE = 2 };

typedef DAGNode< Itemset > LatticeNode;
typedef DAG< LatticeNode > ItemsetLattice;

// defined in the appropriate Makefile.am now.
//#define APRIORI_RANDOM_CONSIDER_COMPLEMENTS 0

#ifdef APRIORI_RANDOM_CONSIDER_COMPLEMENTS
// what is the type of the key for random distributions of itemset row sizes.
//typedef unsigned int ItemsetRandomRowDistKeyType;
typedef pair< unsigned int, unsigned int > ItemsetRandomRowDistKeyType;
#else
typedef unsigned int ItemsetRandomRowDistKeyType;
#endif

class Apriori
{
protected:

  //minimum number of rows/cols before region is an itemset
  unsigned int minrows; 
  unsigned int mincols;
  
  bool transposed;      //whether or not the dataset was transposed

  vector<vector<unsigned int> > data;
  map<unsigned int,string> columnNames,rowNames;        //stores the column and row names mapped from indices

  // variables to keep track of multiple data sets.
  
  unsigned int _numDatasets;
  // which data set does a row belong to? 
  vector< unsigned int > _rowIndexToDatasetIndex;
  
  
  vector<Itemset> itemsets;
  bool _itemsetsComputed;
  
  ItemsetLattice _closedLattice;
  ItemsetLattice _reducedLattice;
  bool _latticeComputed;

protected:
  // compute all the rows to select the random set from.
  virtual void _computeAllRows(vector< unsigned int > &allRows) const;

  // computed a random set of rows in data. see comment in
  // Apriori::computeRandomDistribution() to see why this method
  // returns an unsigned int.
  virtual unsigned int _computeRandomRows(const vector< unsigned int > &allRows,
                                  vector< unsigned int > &randomRows) const;

  // are the rows i and j in the same dataset?
  virtual bool _areRowsInSameDataset(unsigned int i, unsigned int j) const
    {
      return(_rowIndexToDatasetIndex[i] == _rowIndexToDatasetIndex[j]);
    }
  
private:
  //converts a string to an integer
  int atoi(string in);

  // count the number of ones in a row.
  unsigned int _getNumOnes(unsigned int index) const;
  
  void finalizeItemset(Itemset &itm, unsigned int index);
  
  
  void finalizeItemsets();

  // return true iff itemset contains rows from at least two datasets.
  // if there is only one dataset, always return true.
  bool _isStraddler(Itemset &itemset);
  
  // after setting minimums, remove all columns with < minrows ones
  // and all rows with < mincols columns.
  void _resizeData();
  
  // returns the transpose of a matrix, alters the internal variables
  // to correspond to the new transpose
  void transpose();

  
public:
  Apriori()
      : minrows(1), mincols(1), transposed(false), data(),
        columnNames(), rowNames(), _numDatasets(0), _rowIndexToDatasetIndex(),
        itemsets(), _itemsetsComputed(false),
        _closedLattice(), _reducedLattice(), _latticeComputed(false)
    {}


  Apriori(string filename);

  //expects a vector of vectors as input, as well as maps specifying the row (major) vector names
  //and the column (minor) vector names.  Example: The vector matrix[i] corresponds to majornames[i]
  Apriori(vector<vector<unsigned int> > &matrix,
          map<unsigned int,string> &majorNames,
          map<unsigned int,string> &minorNames);

  virtual ~Apriori()
    {}
  
  virtual bool checkIfClosed(Itemset &itemset) const;
  

  
  virtual void computeItemsetFromRows(vector< unsigned int > &rowIndices, Itemset &itemset);
  
  virtual void computeItemsetFromRows(Itemset &itemset);

  virtual void computeItemsets(const set< unsigned int > *rowsToAvoidInSeed = NULL,
                       const set< unsigned int > *rowsToAvoidCompletely = NULL);

  virtual void computeItemsetsLowRAM(const set< unsigned int > *rowsToAvoidInSeed = NULL,
                       const set< unsigned int > *rowsToAvoidCompletely = NULL);
  virtual AprioriLatticeEdgeType computeLatticeEdgeType(const Itemset &itm1, const Itemset &itm2) const;
  

  virtual void computeLattice();

  virtual void computeRandomDistribution(ostream &ostrm, unsigned int numTries,
                                 map< ItemsetRandomRowDistKeyType, MyHistogram >&rowDists,
                                 map< unsigned int, MyHistogram >&columnDists,
                                 MyHistogram &sizeDist);
  

  bool containsColumn(Itemset &itemset, unsigned int index) const;
  

  bool containsRow(Itemset &itemset, unsigned int index) const;

  virtual void getItemsets(vector<Itemset> &itemsets, bool deleteItemsets = false);

  virtual void getLattice(ItemsetLattice &lattice, bool deleteLattice = false);
  
  virtual void getClosedLattice(ItemsetLattice &closedLattice, bool deleteLattice = false);

  virtual unsigned int getNumItemsets() const
    {
      return(itemsets.size());
    }

  virtual unsigned int getNumLatticeEdges() const
    {
      return(_reducedLattice.getNumEdges());
    }

  virtual void printItemsets(ostream& ostr) const;
  
  virtual void printItemsets(string outputFile) const;

  virtual void printItemsetsGraph(ostream& ostr) const;

  virtual void printItemsetsGraph(string outputFile) const;

  virtual void printItemsetStatistics(ostream& ostr) const;
  
  void readFile(string filename);

  virtual void setItemsets(const vector< Itemset > &isets);
  
  //sets the minimum number of rows/columns in a itemset before it is returned
  //default is 1, meaning that single array elements can be returned
  virtual unsigned int setMinimums(unsigned int rows, unsigned int columns)
    {
      minrows=rows; mincols=columns;
      _resizeData();
    }
  
};

inline void _computeComplement(vector< unsigned int > &binaryVector)
{
  for (unsigned int i = 0; i < binaryVector.size(); i++)
    binaryVector[i] = 1 - binaryVector[i];
}


class AprioriWithComplement : public Apriori
{
private:
  // _complementRows[i] stores the index of the complement of row i in data.
  vector< unsigned int > _originalRowsToComplementRows;
  // _complementRowsToOriginalRows stores the set of rows that are
  // complements and which original row corresponds to each
  // complement.
  map< unsigned int, unsigned int > _complementRowsToOriginalRows;
  // _complementRowsSet just stores the set of rows that are complements.
  set< unsigned int > _complementRowsSet;
  
  
protected:
  // compute all the rows to select the random set from.
  virtual void _computeAllRows(vector< unsigned int > &allRows) const;
  
  
  // computed a random set of rows in data. in this class, i ensure
  // that no rows and its complement appear in randomRows and that at
  // least one row is not a complement.
  //
  // see comment in Apriori::computeRandomDistribution() to see why
  // this method returns an unsigned int.

  virtual unsigned int _computeRandomRows(const vector< unsigned int > &allRows,
                                  vector< unsigned int > &randomRows) const;

  // return true iff index corresponds to a complemented row.
  virtual bool _isComplementRow(unsigned int index) const
    {
      return(_complementRowsToOriginalRows.end() != _complementRowsToOriginalRows.find(index));
    }
  // assumes that _isComplementRow(index) returned true. return the
  // original row corresponding to index.
  virtual unsigned int _getOriginalRow(unsigned int index) const
    {
      return(_complementRowsToOriginalRows.find(index)->second);
    }
  
public:
  
  AprioriWithComplement()
      : Apriori(), _originalRowsToComplementRows(), _complementRowsToOriginalRows()
    {}



                       //  Apriori(string filename);

  //expects a vector of vectors as input, as well as maps specifying the row (major) vector names
  //and the column (minor) vector names.  Example: The vector matrix[i] corresponds to majornames[i]
  AprioriWithComplement(vector<vector<unsigned int> > &matrix,
          map<unsigned int,string> &majorNames,
          map<unsigned int,string> &minorNames);

  virtual ~AprioriWithComplement()
    {}
  
  
  virtual void computeItemsets(const set< unsigned int > *rowsToAvoidInSeed = NULL,
                               const set< unsigned int > *rowsToAvoidCompletely = NULL);


  virtual AprioriLatticeEdgeType computeLatticeEdgeType(const Itemset &itm1, const Itemset &itm2) const;

  
  //  virtual void printItemsetsGraph(ostream& ostr) const;

  //  virtual void printItemsetsGraph(string outputFile) const;

};

#endif