fpgrowth.c

关联规则挖掘算法FP-growth算法C++实现

  #ifndef QUIET                 /* if not quiet version */
  prgname = argv[0];            /* get program name for error msgs. */

  /* --- print usage message --- */
  if (argc > 1) {               /* if arguments are given */
    fprintf(stderr, "%s - %s\n", argv[0], DESCRIPTION);
    fprintf(stderr, VERSION); } /* print a startup message */
  else {                        /* if no arguments given */
    printf("usage: %s [options] infile outfile\n", argv[0]);
    printf("%s\n", DESCRIPTION);
    printf("%s\n", VERSION);
    printf("-m#      minimal number of items per item set "
                    "(default: %d)\n", min);
    printf("-n#      maximal number of items per item set "
                    "(default: %d)\n", max);
    printf("-s#      minimal support of an item set "
                    "(default: %g%%)\n", supp *100);
    printf("         (positive: percentage, "
                    "negative: absolute number)\n");
    printf("-d#      minimal binary logarithm of support quotient "
                    "(default: none)\n");
    printf("-p#      output format for the item set support "
                    "(default: \"%s\")\n", fmt);
    printf("-a       print absolute support "
                    "(number of transactions)\n");
    printf("-g       write output in scanable form "
                    "(quote certain characters)\n");
    printf("-q#      sort items w.r.t. their frequency (default: %d)\n"
           "         (1: ascending, -1: descending, 0: do not sort,\n"
           "          2: ascending, -2: descending w.r.t. "
                    "transaction size sum)\n", sort);
    printf("-u       use alternative tree projection method\n");
    printf("-z       do not prune tree projections to bonsai\n");
    printf("-j       use quicksort to sort the transactions "
                    "(default: heapsort)\n");
    printf("-i#      ignore records starting with a character "
                    "in the given string\n");
    printf("-b/f/r#  blank characters, field and record separators\n"
           "         (default: \" \\t\\r\", \" \\t\", \"\\n\")\n");
    printf("infile   file to read transactions from\n");
    printf("outfile  file to write frequent item sets to\n");
    return 0;                   /* print a usage message */
  }                             /* and abort the program */
  #endif  /* #ifndef QUIET */

  /* --- evaluate arguments --- */
  for (i = 1; i < argc; i++) {  /* traverse arguments */
    s = argv[i];                /* get option argument */
    if (optarg) { *optarg = s; optarg = NULL; continue; }
    if ((*s == '-') && *++s) {  /* -- if argument is an option */
      while (*s) {              /* traverse options */
        switch (*s++) {         /* evaluate switches */
          case 'm': min    = (int)strtol(s, &s, 0); break;
          case 'n': max    = (int)strtol(s, &s, 0); break;
          case 's': supp   = 0.01*strtod(s, &s);    break;
          case 'd': mindev =      strtod(s, &s);    break;
          case 'p': optarg = &fmt;                  break;
          case 'a': flags |= OF_ABS;                break;
          case 'g': flags |= OF_SCAN;               break;
          case 'q': sort   = (int)strtol(s, &s, 0); break;
          case 'u': mode  |=  FPT_ALTPROJ;          break;
          case 'z': mode  &= ~FPT_BONSAI;           break;
          case 'j': heap   = 0;                     break;
          case 'i': optarg = &cominds;              break;
          case 'b': optarg = &blanks;               break;
          case 'f': optarg = &fldseps;              break;
          case 'r': optarg = &recseps;              break;
          default : error(E_OPTION, *--s);          break;
        }                       /* set option variables */
        if (optarg && *s) { *optarg = s; optarg = NULL; break; }
      } }                       /* get option argument */
    else {                      /* -- if argument is no option */
      switch (k++) {            /* evaluate non-options */
        case  0: fn_in  = s;      break;
        case  1: fn_out = s;      break;
        default: error(E_ARGCNT); break;
      }                         /* note filenames */
    }
  }
  if (optarg) error(E_OPTARG);  /* check option argument */
  if (k != 2) error(E_ARGCNT);  /* and the number of arguments */
  if (supp > 1)                 /* check the minimal support */
    error(E_SUPP, supp);        /* (< 0: absolute number) */
  if (min <= 0) error(E_ITEMCNT, min);   /* check the limits */
  if (max <= 0) error(E_ITEMCNT, max);   /* for the set size */
  if (mindev > -DBL_MAX) flags |= OF_DEV;

  /* --- create item set and transaction set --- */
  itemset = is_create();        /* create an item set and */
  if (!itemset) error(E_NOMEM); /* set the special characters */
  is_chars(itemset, blanks, fldseps, recseps, cominds);
  taset = tas_create(itemset);  /* create a transaction set */
  if (!taset) error(E_NOMEM);   /* to store the transactions */
  MSG(fprintf(stderr, "\n"));   /* terminate the startup message */

  /* --- read transactions --- */
  t = clock();                  /* start the timer */
  if (fn_in && *fn_in)          /* if an input file name is given, */
    in = fopen(fn_in, "r");     /* open input file for reading */
  else {                        /* if no input file name is given, */
    in = stdin; fn_in = "<stdin>"; }   /* read from standard input */
  MSG(fprintf(stderr, "reading %s ... ", fn_in));
  if (!in) error(E_FOPEN, fn_in);
  for (tacnt = 0; 1; tacnt++) { /* transaction read loop */
    k = is_read(itemset, in);   /* read the next transaction */
    if (k < 0) error(k, fn_in, RECCNT(itemset), BUFFER(itemset));
    if (k > 0) break;           /* check for error and end of file */
    if (tas_add(taset, NULL, 0) != 0)
      error(E_NOMEM);           /* add the loaded transaction */
  }                             /* to the transaction set */
  if (in != stdin) fclose(in);  /* if not read from standard input, */
  in = NULL;                    /* close the input file */
  n  = is_cnt(itemset);         /* get the number of items */
  MSG(fprintf(stderr, "[%d item(s),", n));
  MSG(fprintf(stderr, " %d transaction(s)] done ", tacnt));
  MSG(fprintf(stderr, "[%.2fs].", SEC_SINCE(t)));
  if ((n <= 0) || (tacnt <= 0)) error(E_NOTAS);
  MSG(fprintf(stderr, "\n"));   /* check for at least one transaction */
  if (supp >= 0)                /* if relative support is given */
    supp = ceil(tacnt *supp);   /* compute absolute support */
  else {                        /* if absolute support is given */
    supp = ceil(-100  *supp);   /* make the support value positive */
    if (!(flags & OF_ABS)) flags = (flags & ~OF_REL) | OF_ABS;
  }                             /* switch to absolute support output */

  /* --- sort and recode items --- */
  MSG(fprintf(stderr, "filtering, sorting and recoding items ... "));
  t   = clock();                /* start the timer */
  map = (int*)malloc(is_cnt(itemset) *sizeof(int));
  if (!map) error(E_NOMEM);     /* create an item identifier map */
  n = is_recode(itemset, (int)supp, sort, map);
  is_trunc(itemset, n);         /* truncate the itemset and */
  tas_recode(taset, map, n);    /* recode the loaded transactions */
  free(map);                    /* delete the item identifier map */
  if (flags & OF_DEV) {         /* if to compute deviation */
    isevl = ise_create(itemset, tacnt);
    if (!isevl) error(E_NOMEM); /* create an item set evaluator */
  }                             /* (to exploit same prefixes) */
  MSG(fprintf(stderr, "[%d item(s)] ", n));
  MSG(fprintf(stderr, "done [%.2fs].", SEC_SINCE(t)));
  if (n <= 0) error(E_NOTAS);   /* print a log message and */
  MSG(fprintf(stderr, "\n"));   /* check the number of items */

  /* --- create a frequent pattern tree --- */
  MSG(fprintf(stderr, "creating frequent pattern tree ... "));
  t = clock();                  /* start the timer */
  tas_sort(taset, heap);        /* sort the transactions */
  fptree = fpt_create(taset);   /* create a frequent pattern tree */
  if (!fptree) error(E_NOMEM);  /* to represent the transactions */
  tas_delete(taset, 0);         /* delete the transaction set */
  taset = NULL;                 /* and print a success message */
  MSG(fprintf(stderr, "done [%.2fs].\n", SEC_SINCE(t)));

  /* --- find frequent item sets --- */
  t = clock();                  /* start the timer */
  if (fn_out && *fn_out)        /* if an output file name is given, */
    out = fopen(fn_out, "w");   /* open the output file */
  else {                        /* if no output file name is given, */
    out = stdout; fn_out = "<stdout>"; }    /* write to std. output */
  MSG(fprintf(stderr, "writing %s ... ", fn_out));
  if (!out)   error(E_FOPEN, fn_out);
  isfmt = isf_create(itemset, flags & OF_SCAN);
  if (!isfmt) error(E_NOMEM);   /* create an item set formatter */
  k = fpt_search(fptree, (int)supp, min, max, mode, _report, NULL);
  if (k < 0)  error(E_NOMEM);   /* search for frequent item sets */
  if (fflush(out) != 0) error(E_FWRITE, fn_out);
  if (out != stdout) fclose(out);
  out = NULL;                   /* close the output file */
  MSG(fprintf(stderr, "[%d set(s)] done ", k));
  MSG(fprintf(stderr, "[%.2fs].\n", SEC_SINCE(t)));

  /* --- clean up --- */
  #ifndef NDEBUG                /* if this is a debug version */
  isf_delete(isfmt);            /* delete the item set formatter, */
  if (isevl) ise_delete(isevl); /* the item set evaluator, */
  fpt_delete(fptree);           /* the frequent pattern tree, */
  is_delete(itemset);           /* and the item set */
  #endif
  #ifdef STORAGE                /* if storage debugging */
  showmem("at end of program"); /* check memory usage */
  #endif
  return 0;                     /* return 'ok' */
}  /* main() */