fpgrowth.c

数据挖掘中FP增长算法在VC下的实现

/*----------------------------------------------------------------------
  File    : fpgrowth.c
  Contents: fpgrowth algorithm for finding frequent item sets
  Author  : Christian Borgelt
  History : 2004.11.21 file created from eclat.c
            2004.11.22 pruning of tree projection to bonsai added
            2004.11.23 absolute/relative support output changed
            2004.12.09 filter added (binary logarithm of supp. quotient)
            2005.06.20 use of flag for "no item sorting" corrected
            2006.11.26 adapted to new structures ISFMTR and ISEVAL
            2007.02.13 adapted to modified module tabscan
            2008.05.02 default limit for maximal number of items removed
----------------------------------------------------------------------*/
#include <stdio.h>
#include <stdlib.h>
#include <stdarg.h>
#include <limits.h>
#include <float.h>
#include <math.h>
#include <time.h>
#include <assert.h>
#include "scan.h"
#include "fptree.h"
#ifdef STORAGE
#include "storage.h"
#endif

/*----------------------------------------------------------------------
  Preprocessor Definitions
----------------------------------------------------------------------*/
#define PRGNAME     "fpgrowth"
#define DESCRIPTION "find frequent item sets " \
                    "with the fpgrowth algorithm"
#define VERSION     "version 1.13 (2008.05.02)        " \
                    "(c) 2004-2008   Christian Borgelt"

/* --- output flags --- */
#define OF_REL      0x01        /* print relative support */
#define OF_ABS      0x02        /* print absolute support */
#define OF_DEV      0x04        /* print deviation from indep. occ. */
#define OF_SCAN     0x08        /* convert names to scanable form */

/* --- error codes --- */
#define E_OPTION    (-5)        /* unknown option */
#define E_OPTARG    (-6)        /* missing option argument */
#define E_ARGCNT    (-7)        /* too few/many arguments */
#define E_STDIN     (-8)        /* double assignment of stdin */
#define E_SUPP      (-9)        /* invalid item set support */
#define E_ITEMCNT  (-10)        /* invalid number of items */
#define E_NOTAS    (-11)        /* no items or transactions */
#define E_UNKNOWN  (-18)        /* unknown error */

#ifndef QUIET                   /* if not quiet version */
#define MSG(x)        x         /* print messages */
#else                           /* if quiet version */
#define MSG(x)                  /* suppress messages */
#endif

#define SEC_SINCE(t)  ((clock()-(t)) /(double)CLOCKS_PER_SEC)
#define RECCNT(s)     (ts_reccnt(is_tabscan(s)) \
                      - ((ts_delim(is_tabscan(s)) == TS_REC) ? 1 : 0))
#define BUFFER(s)     ts_buf(is_tabscan(s))

/*----------------------------------------------------------------------
  Constants
----------------------------------------------------------------------*/
#ifndef QUIET                   /* if not quiet version */
/* --- error messages --- */
static const char *errmsgs[] = {
  /* E_NONE      0 */  "no error\n",
  /* E_NOMEM    -1 */  "not enough memory\n",
  /* E_FOPEN    -2 */  "cannot open file %s\n",
  /* E_FREAD    -3 */  "read error on file %s\n",
  /* E_FWRITE   -4 */  "write error on file %s\n",
  /* E_OPTION   -5 */  "unknown option -%c\n",
  /* E_OPTARG   -6 */  "missing option argument\n",
  /* E_ARGCNT   -7 */  "wrong number of arguments\n",
  /* E_STDIN    -8 */  "double assignment of standard input\n",
  /* E_SUPP     -9 */  "invalid minimal support %g%%\n",
  /* E_ITEMCNT -10 */  "invalid number of items %d\n",
  /* E_NOTAS   -11 */  "no items or transactions to work on\n",
  /*    -12 to -15 */  NULL, NULL, NULL, NULL,
  /* E_ITEMEXP -16 */  "file %s, record %d: item expected\n",
  /* E_DUPITEM -17 */  "file %s, record %d: duplicate item %s\n",
  /* E_UNKNOWN -18 */  "unknown error\n"
};
#endif

/*----------------------------------------------------------------------
  Global Variables
----------------------------------------------------------------------*/
#ifndef QUIET
static char    *prgname;        /* program name for error messages */
#endif
static ITEMSET *itemset = NULL;     /* item set */
static TASET   *taset   = NULL;     /* transaction set */
static FPTREE  *fptree  = NULL;     /* frequent pattern tree */
static FILE    *in      = NULL;     /* input  file */
static FILE    *out     = NULL;     /* output file */
static int     tacnt    = 0;        /* number of transactions */
static ISEVAL  *isevl   = NULL;     /* item set evaluator */
static ISFMTR  *isfmt   = NULL;     /* item set formatter */
static double  mindev   = -DBL_MAX; /* minimal value of deviation */
static int     flags    = OF_REL;   /* output flags */
static char    *fmt     = "%.1f";   /* output format for support */

/*----------------------------------------------------------------------
  Item Set Report Function
----------------------------------------------------------------------*/

static int _report (int *ids, int cnt, int pfx, int supp, void *data)
{                               /* --- report a frequent item set */
  double dev = 0;               /* deviation from indep. occurrence */

  assert(ids);                  /* check the function arguments */
  if (flags & OF_DEV) {         /* if to filter w.r.t. deviation */
    dev = ise_eval(isevl, ids, cnt, pfx, supp);
    if (dev < mindev) return 0; /* compute and check the deviation */
  }                             /* from an independent occurrence */
  isf_format(isfmt, ids, cnt, pfx);
  isf_print(isfmt, out);        /* print the items of the set */
  fputs(" (", out);             /* print rel. and abs. support */
  if (flags & OF_REL) { fprintf(out, fmt, (supp/(double)tacnt) *100);
                        fputs((flags & OF_ABS) ? "%/" : "%", out); }
  if (flags & OF_ABS) { fprintf(out, "%d", supp); }
  if (flags & OF_DEV) { fputs(", ", out); fprintf(out, fmt, dev); }
  fputs(")\n", out);            /* print deviation from independence */
  return 1;                     /* return 'reported 1 item set' */
}  /* _report() */

/*----------------------------------------------------------------------
  Main Functions
----------------------------------------------------------------------*/

static void error (int code, ...)
{                               /* --- print an error message */
  #ifndef QUIET                 /* if not quiet version */
  va_list    args;              /* list of variable arguments */
  const char *msg;              /* error message */

  assert(prgname);              /* check the program name */
  if (code < E_UNKNOWN) code = E_UNKNOWN;
  if (code < 0) {               /* if to report an error, */
    msg = errmsgs[-code];       /* get the error message */
    if (!msg) msg = errmsgs[-E_UNKNOWN];
    fprintf(stderr, "\n%s: ", prgname);
    va_start(args, code);       /* get variable arguments */
    vfprintf(stderr, msg, args);/* print error message */
    va_end(args);               /* end argument evaluation */
  }
  #endif
  #ifndef NDEBUG                /* if debug version */
  if (isfmt)   isf_delete(isfmt);  /* clean up memory */
  if (isevl)   ise_delete(isevl);  /* and close files */
  if (fptree)  fpt_delete(fptree);
  if (taset)   tas_delete(taset, 0);
  if (itemset) is_delete(itemset);
  if (in  && (in  != stdin))  fclose(in);
  if (out && (out != stdout)) fclose(out);
  #endif
  #ifdef STORAGE                /* if storage debugging */
  showmem("at end of program"); /* check memory usage */
  #endif
  exit(code);                   /* abort the program */
}  /* error() */

/*--------------------------------------------------------------------*/

int main (int argc, char *argv[])
{                               /* --- main function */
  int     i, k = 0, n;          /* loop variables, counters */
  char    *s;                   /* to traverse the options */
  char    **optarg = NULL;      /* option argument */
  char    *fn_in   = NULL;      /* name of input  file */
  char    *fn_out  = NULL;      /* name of output file */
  char    *blanks  = NULL;      /* blanks */
  char    *fldseps = NULL;      /* field  separators */
  char    *recseps = NULL;      /* record separators */
  char    *cominds = NULL;      /* comment indicators */
  double  supp     = 0.1;       /* minimal support (in percent) */
  int     min      =  1;        /* minimal size of item set */
  int     max      = INT_MAX;   /* maximal size of item set */
  int     sort     = -2;        /* flag for item sorting and recoding */
  int     mode     = FPT_BONSAI;/* tree projection mode */
  int     heap     =  1;        /* flag for heap sort vs. quick sort */
  int     *map;                 /* identifier map for recoding */