ines.c

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

  for ( ; tab->name; tab++)     /* look up name in table */
    if (strcmp(tab->name, name) == 0)
      return tab->code;         /* return the measure code */
  return -1;                    /* or an error indicator */
}  /* code() */

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

int main (int argc, char *argv[])
{                               /* --- main function */
  int    i, k = 0;              /* 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_net   = NULL;      /* name of network file */
  char   *blanks   = NULL;      /* blanks */
  char   *fldseps  = NULL;      /* field  separators */
  char   *recseps  = NULL;      /* record separators */
  char   *uvchars  = NULL;      /* unknown value characters */
  char   *sname    = NULL;      /* name of search method */
  char   *mname    = NULL;      /* name of evaluation measure */
  int    mode      = GM_PROB;   /* mode/type of graphical model */
  int    search    = 0;         /* search method */
  int    measure   = 0;         /* evaluation measure */
  double params[2] = { 0, 1 };  /* evaluation measure parameters */
  double minimp    = 0;         /* minimal evaluation improvement */
  double mrgimp    = 0;         /* minimal imp. for distrib. merging */
  int    local     = -1;        /* flag for local structure learning */
  int    maxcon    = 2;         /* maximum number of conditions */
  int    maxtest   = 64;        /* maximum number of parallel tests */
  int    trials    = 1000;      /* number of trials */
  double keep      = 0.8;       /* fraction of hyperedges to keep */
  double qrfrac    = 0.001;     /* final fraction of quality range */
  double ppwgt     = 0.0;       /* parameter penalty weight */
  long   seed      = time(NULL);/* seed for random number generator */
  int    inflags   = AS_NOXATT|AS_NOXVAL; /* table file read flags */
  int    desc      = GM_TITLE|GM_INFO;  /* description mode */
  int    maxlen    = 0;         /* maximal output line length */
  double eval;                  /* evaluation result */

  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 netfile\n", argv[0]);
    printf("%s\n", DESCRIPTION);
    printf("%s\n", VERSION);
    printf("-m       possibilistic mode "
                    "(default: probabilistic mode)\n");
    printf("-s#      search method      "
                    "(default: none, only parameter estimation)\n");
    printf("-e#      evaluation measure (default: infgain/spcgain)\n");
    printf("-!       print a list of search methods "
                    "and evaluation measures\n");
    printf("-z#      sensitivity parameter (default: %g)\n", params[0]);
    printf("         (for measures wdiff, bdm, bdmod, "
                    "rdlrel, and rdlabs)\n");
    printf("-p#      prior (if positive) "
                    "or equivalent sample size (if negative)\n");
    printf("         (for measures bdm and bdmod; "
                    "default: %g)\n", params[1]);
    printf("-c#      maximum number of conditions per attribute\n");
    printf("         or maximum size of a hyperedge minus 1 "
                    "(default: %d)\n", maxcon);
    printf("-i#      minimum evaluation improvement per condition "
                    "(default: %g)\n", minimp);
    printf("-g#/G#   greedy merging of conditional distributions "
                    "(default: no merging)\n");
    printf("-y#      maximum number of parallel tests "
                    "(default: %d)\n", maxtest);
    printf("-t#      number of trials for simulated annealing "
                    "(default: %d)\n", trials);
    printf("-k#      percentage of hyperedges to keep "
                    "(default: %g%%)\n", keep *100);
    printf("-j#      final fraction of quality range "
                    "(default: %g)\n", qrfrac);
    printf("-w#      parameter penalty weight for simulated annealing "
                    "(default: %g)\n", ppwgt);
    printf("-S#      seed for random number generator "
                    "(default: time)\n");
    printf("-x       print a full probability/possibility tree "
                    "(all branches)\n");
    printf("-q       print relative frequencies (in percent)\n");
    printf("-l#      output line length (default: no limit)\n");
    printf("-n       number of tuple occurrences in last field\n");
    printf("-b/f/r#  blanks, field and record separators "
                    "(default: \" \\t\", \" \\t\", \"\\n\")\n");
    printf("-u#      unknown value characters (default: \"?\")\n");
    printf("domfile  file containing domain descriptions "
                    "(in topological order)\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("netfile  file to write induced network structure to\n");
    /* unused lowercase letters: o, v */
    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      = GM_POSS;                  break;
          case 's': optarg    = &sname;                   break;
          case 'e': optarg    = &mname;                   break;
          case 'z': params[0] =      strtod(s, &s);       break;
          case 'p': params[1] =      strtod(s, &s);       break;
          case 'c': maxcon    = (int)strtol(s, &s, 0);    break;
          case 'i': minimp    =      strtod(s, &s);       break;
          case 'g': mrgimp    = strtod(s, &s); local = 0; break;
          case 'G': mrgimp    = strtod(s, &s); local = 1; break;
          case 'y': maxtest   = (int)strtol(s, &s, 0);    break;
          case 't': trials    =      strtol(s, &s, 0);    break;
          case 'k': keep      = 0.01*strtod(s, &s);       break;
          case 'j': qrfrac    =      strtod(s, &s);       break;
          case 'w': ppwgt     =      strtod(s, &s);       break;
          case 'S': seed      =      strtol(s, &s, 0);    break;
          case 'x': desc     |= GM_FULL;                  break;
          case 'q': desc     |= GM_REL;                   break;
          case 'l': maxlen    = (int)strtol(s, &s, 0);    break;
          case 'b': optarg    = &blanks;                  break;
          case 'f': optarg    = &fldseps;                 break;
          case 'r': optarg    = &recseps;                 break;
          case 'u': optarg    = &uvchars;                 break;
          case 'n': inflags  |= AS_WEIGHT;                break;
          case 'd': inflags  |= 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_net = 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) && (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 */
  search  = (sname) ? code(sminfo, sname) : GM_NONE;
  if (search < 0) error(E_SEARCH);
  measure = (mode == PT_PROB)   /* get search method and measure */
          ? ((mname) ? code(m_prob, mname) : PT_INFGAIN)
          : ((mname) ? code(m_poss, mname) : PT_SPCGAIN);
  if (measure < 0) error(E_MEASURE, mname);
  if (((search == GM_OWST)      /* for the tree search methods */
  ||   (search == GM_EXTST))    /* the measure must be symmetric */
  &&  !(pt_minfo(mode, measure) & PT_SYM))
    error(E_COMBI);             /* check method/measure combination */
  if (fn_hdr)                   /* set the header file flag */
    inflags = AS_ATT | (inflags & ~AS_DFLT);
  if (trials <= 0) trials = 1;  /* adapt number of trials */
  if (maxcon <  0) maxcon = 0;  /* and maximum number of conditions */
  if (keep   <  0) keep   = 0;  /* check and adapt the percentage */
  if (keep   >  1) keep   = 1;  /* of hyperedges to keep */

  /* --- read domain/network file --- */
  scan = sc_create(fn_dom);     /* create a scanner */
  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));
  gramod = gm_parse(attset, scan, mode|GM_CDDS|GM_DFLT);
  if (!gramod || !sc_eof(scan)) /* parse or create a graphical model */
    error(E_PARSE, sc_fname(scan));
  fprintf(stderr, "[%d attribute(s)] done.\n", as_attcnt(attset));
  sc_delete(scan); scan = NULL; /* delete the scanner */

  /* --- read table --- */
  as_chars(attset, blanks, fldseps, recseps, uvchars);
  table = io_tabin(attset, fn_hdr, fn_tab, inflags, "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/",                 tab_tplcnt(table));
  fprintf(stderr, "%g tuple(s)] done.\n", tab_getwgt(table,0,INT_MAX));

  /* --- induce graphical model --- */
  fprintf(stderr, "inducing network ... ");
  if       (search == GM_SIAN){ /* if to do simulated annealing */
    dseed(seed);                /* init. the random number generator */
    eval = gm_sian(gramod, table, trials, maxcon+1,
                   keep, qrfrac, ppwgt, 0, drand, 1); }
  else if ((search == GM_OWST)  /* if optimum weight tree induction */
  ||       (search == GM_EXTST)) {
    eval = gm_tree(gramod, table, search,
                   measure, params, maxtest, 1); }
  else {                        /* if greedy condition selection */
    eval = gm_csel(gramod, table, search, measure, params,
                   minimp, local, mrgimp, maxcon, maxtest, 1);
  }                             /* induce a graphical model */
  if (eval <= GM_ERROR) error(E_NOMEM);
  fprintf(stderr, "[evaluation: %g] done.\n", eval);

  /* --- write network structure --- */
  if (fn_net && *fn_net)        /* if an output file name is given, */
    out = fopen(fn_net, "w");   /* open the output file for writing */
  else {                        /* if no output file name is given, */
    out = stdout; fn_net = "<stdout>"; }    /* write to std. output */
  fprintf(stderr, "writing %s ... ", fn_net);
  if (!out) error(E_FOPEN, fn_net);
  if (as_desc(attset, out, AS_TITLE, maxlen) != 0)
    error(E_FWRITE, fn_net);    /* write the domain definitions */
  fputc('\n', out);             /* leave one line empty */
  if (gm_desc(gramod, out, desc, maxlen) != 0)
    error(E_FWRITE, fn_net);    /* write the network structure */
  if (out != stdout) {          /* if not written to stdout */
    i = fclose(out); out = NULL;/* close the output file */
    if (i) error(E_FWRITE, fn_net);
  }                             /* print network information */
  fprintf(stderr, "[%d attribute(s)/",        gm_attcnt(gramod));
  fprintf(stderr, "%d condition(s)] done.\n", gm_concnt(gramod, -1));
  
  /* --- clean up --- */
  #ifndef NDEBUG
  tab_delete(table, 0);         /* delete the table and */
  gm_delete(gramod, 1);         /* the graphical model */
  #endif
  #ifdef STORAGE
  showmem("at end of program"); /* check memory usage */
  #endif
  return 0;                     /* return 'ok' */
}  /* main() */