condep.c

数据挖掘中的一算法 ines算法 c下实现的。适合初学习数据挖掘者借鉴

        ids[0] = 0;             /* otherwise reinit. and generate */
      }                         /* tests with one condition more */
      ids[1] = ids[0] +1;       /* reinitialize second identifier */
    }
    if (cur <= 0) return cur;   /* if no conditions to generate, */
    *p = i = 0;                 /* there is nothing else to do, */
  }                             /* otherwise init. first condition */
  while (1) {                   /* condition initialization loop */
    if (*p == ids[0]) (*p)++;   /* skip the first two identifiers */
    if (*p == ids[1]) (*p)++;   /* (must not appear as conditions) */
    if (++i >= cur) break;      /* if all conditions generated, abort */
    p[1] = *p+1; p++;           /* initialize the next condition */
  }
  return cur;                   /* return the number of conditions */
}  /* next_test() */

/*----------------------------------------------------------------------
cnt: number of attributes
cur: current number of conditions (-1 on first call)
max: maximum number of conditions
ids: vector of attribute identifiers,
     the two conditioned attributes followed by the conditions
----------------------------------------------------------------------*/

int main (int argc, char *argv[])
{                               /* --- main function */
  int    i, k = 0, n;           /* loop variables, counter */
  char   *s;                    /* to traverse options */
  char   **optarg = NULL;       /* option argument */
  char   *fn_dom  = NULL;       /* name of domains file */
  char   *fn_hdr  = NULL;       /* name of table header file */
  char   *fn_tab  = NULL;       /* name of table file */
  char   *fn_out  = NULL;       /* name of output file */
  char   *blanks  = NULL;       /* blanks */
  char   *fldseps = NULL;       /* field  separators */
  char   *recseps = NULL;       /* record separators */
  char   *uvchars = NULL;       /* unknown value characters */
  char   *format  = "%g";       /* format for number output */
  char   *mname   = NULL;       /* name of evaluation measure */
  int    mode     = PT_PROB;    /* evaluation mode */
  int    measure  = 1;          /* evaluation measure */
  int    distuv   = 0;          /* whether to distribute for unknowns */
  int    flags    = AS_NOXATT;  /* table file read flags */
  double param    = 2;          /* parameter for measure wdiff */
  int    maxcon   = 0;          /* maximum number of conditions */
  int    maxpt    = 32;         /* maximum number of trees */
  int    attcnt;                /* number of attributes */
  int    concnt;                /* number of conditions */
  PTREE  **pt;                  /* to traverse the prob./poss. trees */

  prgname = argv[0];            /* get program name for error msgs. */

  /* --- print startup/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 argument given */
    printf("usage: %s [options] domfile "
                     "[-d|-h hdrfile] tabfile outfile\n", argv[0]);
    printf("%s\n", DESCRIPTION);
    printf("%s\n", VERSION);
    printf("-m       possibilistic mode (default: probabilistic)\n");
    printf("-e#      evaluation measure (default: infgain/spcgain)\n");
    printf("-!       print a list of evaluation measures\n");
    printf("-p#      parameter for evaluation measure wdiff\n");
    printf("-w       distribute tuple weight for unknown values\n");
    printf("-c#      maximum number of conditions     "
                    "(default: %d)\n", maxcon);
    printf("-k#      maximum number of parallel tests "
                    "(default: %d)\n", maxpt);
    printf("-o#      format for number output "
                    "(default: \"%s\")\n", format);
    printf("-b/f/r#  blanks, field and record separators "
                    "(default: \" \\t\", \" \\t\", \"\\n\")\n");
    printf("-u#      unknown value characters (default: \"?\")\n");
    printf("-n       number of occurrences in last field\n");
    printf("-d       use default table header "
                    "(field names = field numbers)\n");
    printf("-h       read table header (field names) from hdrfile\n");
    printf("hdrfile  file containing table header (field names)\n");
    printf("tabfile  table file to read "
                    "(first record containing field names)\n");
    printf("resfile  file to write results to (optional)\n");
    return 0;                   /* print a usage message */
  }                             /* and abort the program */

  /* --- 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 (1) {               /* traverse characters */
        switch (*s++) {         /* evaluate option */
          case '!': help();                          break;
          case 'm': mode    = PT_POSS;               break;
          case 'e': optarg  = &mname;                break;
          case 'p': param   =      strtod(s, &s);    break;
          case 'w': distuv  = 1;                     break;
          case 'c': maxcon  = (int)strtol(s, &s, 0); break;
          case 'k': maxpt   = (int)strtol(s, &s, 0); break;
          case 'o': optarg  = &format;               break;
          case 'b': optarg  = &blanks;               break;
          case 'f': optarg  = &fldseps;              break;
          case 'r': optarg  = &recseps;              break;
          case 'u': optarg  = &uvchars;              break;
          case 'n': flags  |= AS_WEIGHT;             break;
          case 'd': flags  |= AS_DFLT;               break;
          case 'h': optarg  = &fn_hdr;               break;
          default : error(E_OPTION, *(--s));         break;
        }                       /* set option variables */
        if (!*s) break;         /* if at end of string, abort loop */
        if (optarg) { *optarg = s; optarg = NULL; break; }
      } }                       /* get option argument */
    else {                      /* -- if argument is no option */
      switch (k++) {            /* evaluate non-option */
        case  0: fn_dom = s;      break;
        case  1: fn_tab = s;      break;
        case  2: fn_out = s;      break;
        default: error(E_ARGCNT); break;
      }                         /* note filenames */
    }
  }
  if (optarg) error(E_OPTARG);  /* check the option argument */
  if (k != 3) error(E_ARGCNT);  /* and the number of arguments */
  if (fn_hdr) {                 /* set the header file flag */
    flags = AS_ATT | (flags & ~AS_DFLT);
    if (strcmp(fn_hdr, "-") == 0) fn_hdr = "";
  }                             /* convert "-" to "" */
  i = (!fn_dom || !*fn_dom) ? 1 : 0;
  if  (!fn_tab || !*fn_tab) i++;
  if  ( fn_hdr && !*fn_hdr) i++;/* check assignments of stdin: */
  if (i > 1) error(E_STDIN);    /* stdin must not be used twice */
  measure = (mode == PT_PROB)   /* get the evaluation measure code */
          ? ((mname) ? code(mi_prob, mname) : PT_INFGAIN)
          : ((mname) ? code(mi_poss, mname) : PT_SPCGAIN);
  if (measure < 0) error(E_MEASURE, mname);

  /* --- read domain file --- */
  scan = sc_create(fn_dom);     /* create a scanner for the file */
  if (!scan) error((!fn_dom || !*fn_dom) ? E_NOMEM : E_FOPEN, fn_dom);
  attset = as_create("domains", att_delete);
  if (!attset) error(E_NOMEM);  /* create an attribute set */
  fprintf(stderr, "\nreading %s ... ", sc_fname(scan));
  if ((sc_nexter(scan)   <  0)  /* start scanning (get first token) */
  ||  (as_parse(attset, scan, AT_SYM) != 0)
  ||  (as_attcnt(attset) <= 0)) /* parse attribute set */
    error(E_PARSE, sc_fname(scan));
  attcnt = as_attcnt(attset);   /* get the number of attributes */
  fprintf(stderr, "[%d attribute(s)] done.", attcnt);
  sc_delete(scan); scan = NULL; /* delete the scanner */
  if (attcnt < 2) error(E_ATTCNT);
  fprintf(stderr, "\n");        /* check the number of attributes */

  /* --- read table --- */
  as_chars(attset, blanks, fldseps, recseps, uvchars);
  table = io_tabin(attset, fn_hdr, fn_tab, flags, "table", 1);
  if (!table) error(1);         /* read the table file */
  fprintf(stderr, "reducing table ... ");
  tab_reduce(table);            /* reduce the table for speed up */
  fprintf(stderr, "[%d/%g tuple(s)] done.\n",
          tab_tplcnt(table), tab_getwgt(table, 0, INT_MAX));

  /* --- measure (conditional) dependences --- */
  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 */
  fprintf(stderr, "writing %s ... ", fn_out);
  if (!out) error(E_FOPEN, fn_out);
  ids    = (int*)   malloc(attcnt *sizeof(int));
  ptrees = (PTREE**)calloc(maxpt, sizeof(PTREE*));
  if (!ids || !ptrees) error(E_NOMEM);
  if (maxcon > attcnt-2)        /* the number of attributes limits */
    maxcon = attcnt-2;          /* the maximal number of conditions */
  if (maxcon >= PT_MAXCON)      /* the data structure also enforces */
    maxcon = PT_MAXCON-1;       /* an upper bound on this number */
  for (concnt = -1, k = maxpt; k >= maxpt; ) {
    pt = ptrees;                /* while more tests to carry out */
    for (ptcnt = 0; ptcnt < maxpt; ptcnt++) {
      concnt = next_test(attcnt, concnt, maxcon, ids);
      if (concnt < 0) break;    /* generate the next dependence test */
      *pt = pt_create(as_att(attset, ids[0]), mode);
      if (!*pt) error(E_NOMEM); /* create a prob./poss. tree */
      for (k = 0, i = concnt+2; --i > 0; k++) {
        if (pt_conadd(*pt, k, as_att(attset, ids[i])) < 0)
          error(E_NOMEM);       /* add the other attribute */
      }                         /* and the conditions according to */
      pt++;                     /* the generated identifier vector, */
    }                           /* then go to the next tree */
    if (ptcnt <= 0) break;      /* if no tree generated, abort loop */
    for (i = tab_tplcnt(table); --i >= 0; ) {
      tpl_toas(tab_tpl(table, i));  /* traverse the table */
      for (pt = ptrees +(k = ptcnt); --k >= 0; ) {
        if (pt_aggr(*--pt, as_getwgt(attset), distuv) != 0)
          error(E_NOMEM);       /* traverse the prob./poss. trees */
      }                         /* and aggregate the tuples */
    }                           /* for all of them */
    pt = ptrees;                /* traverse the prob./poss. trees */
    for (k = ptcnt; --ptcnt >= 0; ) {
      n = pt_concnt(*pt)-1;     /* print the two conditioned atts. */
      fprintf(out, "%s ", att_name(pt_att(*pt)));
      fprintf(out, "%s ", att_name(pt_con(*pt, n)));
      if (n > 0) fprintf(out, "| ");
      for (i = n; --i >= 0; )   /* print the conditions */
        fprintf(out, "%s ", att_name(pt_con(*pt, i)));
      fprintf(out, format, pt_depend(*pt, measure, &param));
      fprintf(out, "\n");       /* print the evaluation result */
      pt_delete(*pt, 0); *pt++ = NULL;
    }                           /* delete the tree and clean up */
  }
  if (out != stdout) {          /* if not written to standard output, */
    i = fclose(out); out = NULL;/* close the output file */
    if (i != 0) error(E_FWRITE, fn_out);
  }                             /* check for success and */
  fprintf(stderr, "done.\n");   /* print a success message */

  /* --- clean up --- */
  #ifndef NDEBUG
  free(ptrees);                 /* delete the tree vector, */
  free(ids);                    /* the identifier vector, */
  tab_delete(table, 0);         /* the table, and */
  as_delete(attset);            /* the attribute set */
  #endif
  #ifdef STORAGE
  showmem("at end of program"); /* check memory usage */
  #endif
  return 0;                     /* return 'ok' */
}  /* main() */