fbayes.c

数据挖掘中的bayes算法,很好的代码

      if (*--p) mvn_delete(*p); /* delete the multivar. normal dists. */
    free(fbc->mvns);            /* and delete the vector itself, */
  }                             /* then delete the frequency vectors */
  if (fbc->frqs)   free(fbc->frqs);
  if (fbc->vals)   free(fbc->vals);
  if (fbc->numids) free(fbc->numids);
  if (delas)       as_delete(fbc->attset);
  free(fbc);                    /* delete the classifier body */
}  /* fbc_delete() */

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

void fbc_clear (FBC *fbc)
{                               /* --- clear a full Bayes classifier */
  int    i;                     /* loop variables */
  double *frq;                  /* to traverse the frequency vectors */

  assert(fbc);                  /* check the function argument */
  fbc->total = 0;               /* clear the total number of cases */
  for (frq = fbc->frqs +(i = fbc->clscnt); --i >= 0; ) {
    *--frq = 0;                 /* clear the frequency distribution */
    mvn_clear(fbc->mvns[i]);    /* and the multivariate normal */
  }                             /* distributions */
}  /* fbc_clear() */

/*--------------------------------------------------------------------*/
#ifdef FBC_INDUCE

int fbc_add (FBC *fbc, const TUPLE *tpl)
{                               /* --- add an instantiation */
  int   cls;                    /* value of class attribute */
  float wgt;                    /* instantiation weight */

  assert(fbc);                  /* check the function argument */

  /* --- get class and weight --- */
  if (tpl) {                    /* if a tuple is given */
    cls = tpl_colval(tpl, fbc->clsid)->i;
    wgt = tpl_getwgt(tpl); }    /* get the class and the tuple weight */
  else {                        /* if no tuple is given */
    cls = att_inst(as_att(fbc->attset, fbc->clsid))->i;
    wgt = as_getwgt(fbc->attset);
  }                             /* get the class and the inst. weight */
  if (cls < 0) return 0;        /* if the class is null, abort */
  assert(wgt >= 0.0F);          /* check the tuple weight */

  /* --- update the class distribution --- */
  if ((cls >= fbc->clscnt)      /* if the class is a new one, */
  &&  (_clsrsz(fbc,cls+1) != 0))/* resize the class dependent vectors */
    return -1;                  /* (frequencies and distributions) */
  fbc->frqs[cls] += wgt;        /* update the class frequency */
  fbc->total     += wgt;        /* and the total frequency */

  /* --- update the conditional distributions --- */
  _getvals(fbc, tpl);           /* get the attribute value vector */
  mvn_add(fbc->mvns[cls], fbc->vals, wgt);
  return 0;                     /* add inst. to the cond. distrib. */
}  /* fbc_add() */              /* return 'ok' */

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

FBC* fbc_induce (TABLE *table, int clsid, int mode, double lcorr)
{                               /* --- create a full Bayes classifier */
  int    i;                     /* loop variable */
  FBC    *fbc;                  /* created full Bayes classifier */
  ATTSET *attset;               /* attribute set of the classifier */

  assert(table                  /* check the function arguments */
      && (clsid >= 0) && (clsid < tab_colcnt(table))
      && (att_type(as_att(tab_attset(table), clsid)) == AT_NOM));

  /* --- create a classifier --- */
  attset = tab_attset(table);   /* get the attribute set of the table */
  if (mode & FBC_CLONE) {       /* if the corresp. flag is set, */
    attset = as_clone(attset);  /* clone the attribute set */
    if (!attset) return NULL;   /* of the given data table, */
  }                             /* then create a classifier */
  fbc = fbc_create(attset, clsid);
  if (!fbc) { if (mode & FBC_CLONE) as_delete(attset); return NULL; }

  /* --- build the classifier --- */
  for (i = tab_tplcnt(table); --i >= 0; )
    fbc_add(fbc, tab_tpl(table, i));        /* add all tuples */
  fbc_setup(fbc, mode, lcorr);   /* and set up the classifier */

  return fbc;                    /* return the created classifier */
}  /* fbc_induce() */

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

int fbc_mark (FBC *fbc)
{                               /* --- mark selected attributes */
  int   i;                      /* loop variable, attibute counter */
  FBCID *p;                     /* to traverse the attribute ids. */

  assert(fbc);                  /* check the function argument */
  for (i = fbc->attcnt; --i >= 0; )   /* unmark all attributes */
    att_setmark(as_att(fbc->attset, i), -1);
  for (p = fbc->numids +(i = fbc->numcnt); --i >= 0; ) {
    --p; att_setmark(p->att, 1); }    /* mark all numeric attributes */
  att_setmark(as_att(fbc->attset, fbc->clsid), 0);
  return fbc->numcnt +1;        /* mark the class attribute and */
}  /* fbc_mark() */             /* return the number of marked atts. */

#endif
/*--------------------------------------------------------------------*/

void fbc_setup (FBC *fbc, int mode, double lcorr)
{                               /* --- set up a full Bayes classifier */
  int    i, n;                  /* loop variables */
  double cnt;                   /* number of cases, sum of priors */
  double *frq, *prb;            /* to traverse the value frqs./probs. */
  MVNORM **mvn;                 /* to traverse the distributions */

  assert(fbc && (lcorr >= 0));  /* check the function arguments */
  fbc->mode  = mode = mode & FBC_MAXLLH;
  fbc->lcorr = lcorr;           /* note estimation parameters */

  /* --- estimate class probabilities --- */
  n   = fbc->clscnt;            /* get the number of classes and */
  prb = fbc->priors +n;         /* traverse the class probabilities */
  cnt = fbc->total +lcorr *fbc->clscnt;
  if (cnt <= 0)                 /* if the denominator is invalid, */
    while (--n >= 0) *--prb = 0;       /* clear all probabilities */
  else {                        /* if the denominator is valid, */
    frq = fbc->frqs +n;         /* traverse the class frequencies */
    while (--n >= 0) *--prb = (*--frq +lcorr) /cnt;
  }                             /* estimate the class probabilities */

  /* --- estimate conditional probabilities --- */
  mode |= MVN_EXPVAR|MVN_COVAR|MVN_INVERSE|MVN_DECOM;
  for (mvn = fbc->mvns +(i = fbc->clscnt); --i >= 0; )
    mvn_calc(*--mvn, mode);     /* calculate all parameters */
}  /* fbc_setup() */

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

int fbc_exec (FBC *fbc, const TUPLE *tpl, double *conf)
{                               /* --- execute a full Bayes class. */
  int    i;                     /* loop variable */
  double *s, *d;                /* to traverse the probabilities */
  MVNORM **mvn;                 /* to traverse the distributions */
  double sum;                   /* sum of class probabilities */

  assert(fbc);                  /* check the function argument */
  _getvals(fbc, tpl);           /* get the attribute value vector */
  s = fbc->priors +fbc->clscnt; /* get the prior     distribution */
  d = fbc->posts  +fbc->clscnt; /* and the posterior distribution */
  for (mvn = fbc->mvns +(i = fbc->clscnt); --i >= 0; ) {
    --mvn;                      /* traverse the cond. distributions */
    *--d = *--s * mvn_eval(*mvn, fbc->vals);
  }                             /* compute the posterior probability */
  for (s = d, sum = *s, i = fbc->clscnt; --i > 0; ) {
    if (*++s > *d) d = s;       /* find the most probable class */
    sum += *s;                  /* and sum all probabilities */
  }                             /* (for the later normalization) */
  sum = (sum > 0) ? 1/sum : 1;  /* compute normalization factor */
  for (i = fbc->clscnt; --i >= 0; )
    fbc->posts[i] *= sum;       /* normalize probabilities */
  if (conf) *conf = *d;         /* get the confidence value and */
  return (int)(d -fbc->posts);  /* return the classification result */
}  /* fbc_exec() */

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

double* fbc_rand (FBC *fbc, double drand (void))
{                               /* --- generate a random tuple */
  int    i;                     /* loop variable */
  double t, sum;                /* random number, sum of probs. */
  double *p = fbc->priors;      /* to access the class probabilities */
  FBCID  *q = fbc->numids;      /* to traverse the attributes */

  t = drand();                  /* generate a random number */
  for (sum = i = 0; i < fbc->clscnt; i++) {
    sum += p[i]; if (sum >= t) break; }
  if (i >= fbc->clscnt)         /* find the class that corresponds */
    i = fbc->clscnt -1;         /* to the generated random number */
  att_inst(as_att(fbc->attset, fbc->clsid))->i = i;
  p = mvn_rand(fbc->mvns[i], drand);   /* generate a random point */
  for (q = fbc->numids +(i = fbc->numcnt); --i >= 0; ) {
    --q; att_inst(q->att)->f = (float)p[i]; }
  return p;                     /* copy the point to the att. set */
}  /* fbc_rand() */             /* and return the generated point */

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

int fbc_desc (FBC *fbc, FILE *file, int mode, int maxlen)
{                               /* --- describe a full Bayes class. */
  int   i, k;                   /* loop variables */
  int   pos, ind;               /* current position and indentation */
  int   len;                    /* length of a class value name */
  ATT   *att;                   /* to traverse the attributes */
  FBCID *p;                     /* to traverse the attribute ids. */
  char  buf[4*AS_MAXLEN+4];     /* output buffer */

  assert(fbc && file);          /* check the function arguments */

  /* --- print a header (as a comment) --- */
  if (mode & FBC_TITLE) {       /* if the title flag is set */
    i = k = (maxlen > 0) ? maxlen -2 : 70;
    fputs("/*", file); while (--i >= 0) fputc('-', file);
    fputs("\n  full Bayes classifier\n", file);
    while (--k >= 0) fputc('-', file); fputs("*/\n", file);
  }                             /* print a title header */
  if (maxlen <= 0) maxlen = INT_MAX;

  /* --- start description --- */
  att = as_att(fbc->attset, fbc->clsid);
  sc_format(buf, att_name(att), 0);
  fputs("fbc(", file);          /* get the class attribute name */
  fputs(buf, file);             /* and print it */
  fputs(") = {\n", file);       /* start the classifier */
  if ((fbc->lcorr > 0)          /* if estimation parameters */
  ||   fbc->mode) {             /* differ from default values */
    fprintf(file, "  params = %g", fbc->lcorr);
    if (fbc->mode & FBC_MAXLLH) fputs(", maxllh", file);
    fputs(";\n", file);         /* print Laplace correction */
  }                             /* and estimation mode */

  /* --- print class distribution --- */
  fputs("  prob(", file);       /* print a distribution indicator */
  fputs(buf, file);             /* print the class att. name and */
  fputs(") = {\n    ", file);   /* start the the class distribution */
  ind = att_valwd(att, 0) +4;   /* compute the indentation and */
  for (i = 0; i < fbc->clscnt; i++) {  /* traverse the classes */
    if (i > 0)                  /* if this is not the first class, */
      fputs(",\n    ", file);   /* start a new output line */
    len = sc_format(buf, att_valname(att, i), 0);
    fputs(buf, file);           /* get and print the class name */
    for (pos = len+4; pos < ind; pos++)
      putc(' ', file);          /* pad with blanks to equal width */
    fprintf(file, ": %g", fbc->frqs[i]);
    if (mode & FBC_REL)         /* print the absolute class frequency */
      fprintf(file, " (%.1f%%)", fbc->priors[i] *100);
  }                             /* print the relative class frequency */
  fputs(" };\n", file);         /* terminate the class distribution */

  /* --- print conditional distributions --- */
  if (fbc->numcnt > 0) {        /* if there are numeric attributes */
    fputs("  prob(", file);     /* print a distribution indicator */
    pos = ind = 7;              /* and traverse the num. attributes */
    for (p = fbc->numids, i = 0; i < fbc->numcnt; p++, i++) {
      if (i > 0) {              /* if this is not the first att., */
        fputc(',', file); pos++; }           /* print a separator */
      len = sc_format(buf, att_name(p->att), 0);
      if ((pos +len > maxlen-1) /* get the condition name and */
      &&  (pos      > ind)) {   /* if the line would get too long, */
        fputc('\n', file);      /* start a new line and indent */