fbayes.c

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

        for (pos = 0; pos < ind; pos++) fputc(' ', file);
      }                         /* indent to the opening parenthesis */
      fputs(buf, file); pos += len;
    }                           /* print the name of the attribute */
    fputc('|', file);           /* print condition indicator */
    att = as_att(fbc->attset, fbc->clsid);
    sc_format(buf, att_name(att), 0);
    fputs(buf, file);           /* print the class attribute name */
    fputs(") = {\n    ", file); /* and start the 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 */
      fputs(": N(", file);      /* start a normal distribution */
      mvn_desc(fbc->mvns[i], file, -(ind+4), maxlen);
      fputc(')', file);         /* describe multivar. normal dists. */
    }                           /* and terminate the distribution */
    fputs(" };\n", file);       /* terminate the cond. distribution */
  }
  fputs("};\n", file);          /* terminate the classifier */

  return ferror(file) ? -1 : 0; /* return the write status */
}  /* fbc_desc() */

/*--------------------------------------------------------------------*/
#ifdef FBC_PARSE

static int _parse (ATTSET *attset, SCAN *scan, FBC **pfbc)
{                               /* --- parse a full Bayes classifier */
  int    i = -1, t;             /* loop variable, buffer */
  int    clsid, attid;          /* (class) attribute index */
  ATT    *att;                  /* class attribute */
  FBC    *fbc;                  /* created full Bayes classifier */
  double *p, f;                 /* to traverse the frequencies */
  int    *flags;                /* to traverse the attribute flags */
  FBCID  *ni;                   /* to traverse the numeric att. ids. */

  /* --- read start of description --- */
  if ((sc_token(scan) != T_ID)
  ||  (strcmp(sc_value(scan), "fbc") != 0))
    ERR_STR("fbc");             /* check for 'fbc' */
  GET_TOK();                    /* consume 'fbc' */
  GET_CHR('(');                 /* consume '(' */
  t = sc_token(scan);           /* check for a name */
  if ((t != T_ID) && (t != T_NUM)) ERROR(E_ATTEXP);
  clsid = as_attid(attset, sc_value(scan));
  if (clsid < 0)                   ERROR(E_UNKATT);
  att = as_att(attset, clsid);  /* get and check the class attribute */
  if (att_type(att) != AT_NOM)     ERROR(E_CLSTYPE);
  if (att_valcnt(att) < 1)         ERROR(E_CLSCNT);
  *pfbc = fbc = fbc_create(attset, clsid);
  if (!fbc) ERROR(E_NOMEM);     /* create a full Bayes classifier */
  GET_TOK();                    /* consume the class name */
  GET_CHR(')');                 /* consume '(' */
  GET_CHR('=');                 /* consume '=' */
  GET_CHR('{');                 /* consume '{' */

  /* --- read parameters --- */
  if ((sc_token(scan) == T_ID)  /* if 'params' follows */
  &&  (strcmp(sc_value(scan), "params") == 0)) {
    GET_TOK();                  /* consume 'params' */
    GET_CHR('=');               /* consume '=' */
    if (sc_token(scan) != T_NUM)  ERROR(E_NUMEXP);
    fbc->lcorr = atof(sc_value(scan));
    if (fbc->lcorr < 0)           ERROR(E_NUMBER);
    GET_TOK();                  /* get Laplace correction */
    while (sc_token(scan) == ',') {
      GET_TOK();                /* read list of parameters */
      if (sc_token(scan) != T_ID) ERROR(E_PAREXP);
      if (strcmp(sc_value(scan), "maxllh") == 0)
        fbc->mode |= FBC_MAXLLH;/* use max. likelihood estimate */
      else ERROR(E_PAREXP);     /* abort on all other values */
      GET_TOK();                /* consume the estimator flag */
    }
    GET_CHR(';');               /* consume ';' */
  }

  /* --- read class distribution --- */
  if ((sc_token(scan) != T_ID)
  ||  ((strcmp(sc_value(scan), "prob") != 0)
  &&   (strcmp(sc_value(scan), "P")    != 0)))
    ERR_STR("prob");            /* check for 'prob' or 'P' */
  GET_TOK();                    /* consume   'prob' or 'P' */
  GET_CHR('(');                 /* consume '(' */
  t = sc_token(scan);           /* get the next token */
  if (((t != T_ID) && (t != T_NUM))
  ||  (strcmp(sc_value(scan), att_name(att)) != 0))
    ERROR(E_ATTEXP);            /* check for the class att. name */
  GET_TOK();                    /* consume the class att. name */
  GET_CHR(')');                 /* consume ')' */
  GET_CHR('=');                 /* consume '=' */
  GET_CHR('{');                 /* consume '{' */
  for (p = fbc->frqs +(i = fbc->clscnt); --i >= 0; )
    *--p = -1;                  /* clear the class frequencies */
  while (1) {                   /* class value read loop */
    t = sc_token(scan);         /* check for the class att. name */
    if ((t != T_ID) && (t != T_NUM)) ERROR(E_CLSEXP);
    if (t != T_NUM) t = ':';    /* if the token is no number, */
    else {                      /* the token must be a class, */
      GET_TOK();                /* otherwise consume the token, */
      t = sc_token(scan);       /* note the next token, and */
      sc_back(scan);            /* go back to the previous one */
    }                           /* (look ahead one token) */
    if (t != ':')               /* if no ':' follows, */
      i = (i+1) % fbc->clscnt;  /* get the cyclic successor id */
    else {                      /* if a  ':' follows */
      i = att_valid(att, sc_value(scan));
      if (i < 0) ERROR(E_UNKCLS);
      GET_TOK();                /* get and consume the class value */
      GET_CHR(':');             /* consume ':' */
    }
    if (sc_token(scan) != T_NUM) ERROR(E_NUMEXP);
    f = atof(sc_value(scan));   /* get and check */
    if (f < 0) ERROR(E_NUMBER); /* the class frequency */
    if (fbc->frqs[i] >= 0)      /* check whether frequency is set */
      XERROR(E_DUPCLS, att_valname(att, i));
    fbc->frqs[i] = f;           /* set the class frequency */
    GET_TOK();                  /* consume the class frequency */
    if (sc_token(scan) == '('){ /* if a relative number follows, */
      GET_TOK();                /* consume '(' */
      if (sc_token(scan) != T_NUM)  ERROR(E_NUMEXP);
      if (atof(sc_value(scan)) < 0) ERROR(E_NUMBER);
      GET_TOK();                /* consume the relative number */
      GET_CHR('%');             /* consume '%' */
      GET_CHR(')');             /* consume ')' */
    }
    if (sc_token(scan) != ',') break;
    GET_TOK();                  /* if at end of list, abort loop, */
  }                             /* otherwise consume ',' */
  GET_CHR('}');                 /* consume '}' (end of distribution) */
  for (f = 0, p = fbc->frqs +(i = fbc->clscnt); --i >= 0; ) {
    if (*--p < 0) *p = 0;       /* clear the unset frequencies */
    else          f += *p;      /* and sum all other frequancies */
  }                             /* to obtain the total frequency */
  fbc->total = f;               /* set the sum of the frequencies */
  GET_CHR(';');                 /* consume ';' */

  /* --- read conditional distributions --- */
  if (fbc->numcnt <= 0) {       /* if there are no numeric attributes */
    GET_CHR('}');               /* consume '}' */
    GET_CHR(';');               /* consume ';' (end of classifier) */
    return 0;                   /* return 'ok' */
  }
  if ((sc_token(scan) != T_ID)
  ||  ((strcmp(sc_value(scan), "prob") != 0)
  &&   (strcmp(sc_value(scan), "P")    != 0)))
    ERR_STR("prob");            /* check for 'prob' or 'P' */
  GET_TOK();                    /* consume   'prob' or 'P' */
  GET_CHR('(');                 /* consume '(' */
  if (sc_token(scan) == '*') {  /* if a star follows, */
    GET_TOK(); }                /* simply consume it */
  else {                        /* if a list of attributes follows */
    for (flags = fbc->flags +(i = fbc->attcnt); --i >= 0; )
      *--flags = 0;             /* clear all attribute flags */
    for (ni = fbc->numids +(i = fbc->numcnt); --i >= 0; )
      flags[(--ni)->id] = -1;   /* set flags of numeric attributes */
    while (1) {                 /* attribute read loop */
      t = sc_token(scan);       /* check for a name */
      if ((t != T_ID) && (t != T_NUM)) ERROR(E_ATTEXP);
      attid = as_attid(attset, sc_value(scan));
      if (attid < 0)         ERROR(E_UNKATT);
      if (flags[attid] == 0) ERROR(E_DUPATT);
      flags[attid] = 0;         /* check and clear the attribute flag */
      GET_TOK();                /* consume the attribute name */
      if (sc_token(scan) != ',') break; 
      GET_TOK();                /* if at end of the list, abort loop, */
    }                           /* otherwise consume ',' */
    for (i = fbc->attcnt; --i >= 0; )
      if (flags[i]) XERROR(E_MISATT, att_name(as_att(attset, i)));
  }                             /* check the attribute flags */
  GET_CHR('|');                 /* consume '|' (condition indicator) */
  t = sc_token(scan);           /* get the next token */
  if (((t != T_ID) && (t != T_NUM))
  ||  (strcmp(sc_value(scan), att_name(att)) != 0))
    ERROR(E_CLSEXP);            /* check for a class name */
  GET_TOK();                    /* consume the class name */
  GET_CHR(')');                 /* consume ')' */
  GET_CHR('=');                 /* consume '=' */
  GET_CHR('{');                 /* consume '{' */

  for (p = fbc->posts +(i = fbc->clscnt); --i >= 0; )
    *--p = -1;                  /* mark all classes as unread */
  while (1) {                   /* class value read loop */
    t = sc_token(scan);         /* check for name, number, or 'N' */
    if ((t != T_ID) && (t != T_NUM)) ERROR(E_CLSEXP);
    if (t == T_NUM) t = ':';    /* if the token is a number, */
    else {                      /* the token must be a class, */
      GET_TOK();                /* otherwise consume the token, */
      t = sc_token(scan);       /* note the next token, and */
      sc_back(scan);            /* go back to the previous one */
    }                           /* (look ahead one token) */
    if (t != ':')               /* if no ':' follows, */
      i = (i+1) % fbc->clscnt;  /* get the cyclic successor id */
    else {                      /* if a  ':' follows */
      i = att_valid(att, sc_value(scan));
      if (i < 0) ERROR(E_UNKCLS);
      GET_TOK();                /* get and consume class value */
      GET_CHR(':');             /* consume ':' */
    }
    if (fbc->posts[i] >= 0) ERROR(E_DUPCLS);
    fbc->posts[i] = 1;          /* check and set the read marker */
    if ((sc_token(scan) != T_ID)
    ||  (strcmp(sc_value(scan), "N") != 0))
      ERR_STR("N");             /* check for an 'N' */
    GET_TOK();                  /* consume 'N' */
    GET_CHR('(');               /* consume '(' */
    i = mvn_parse(fbc->mvns[i], scan, fbc->frqs[i]);
    if (i != 0) return i;       /* parse a multivariate normal dist. */
    GET_CHR(')');               /* consume ')' */
    if (sc_token(scan) != ',') break;
    GET_TOK();                  /* if at end of list, abort loop, */
  }                             /* otherwise consume ',' */
  for (p = fbc->posts, i = 0; i < fbc->clscnt; p++, i++) {
    if ((*p < 0) && (fbc->frqs[i] > 0))
      XERROR(E_MISCLS, att_valname(att, i));
  }                             /* check for a complete classifier */
  GET_CHR('}');                 /* consume '}' */
  GET_CHR(';');                 /* consume ';' (end of distribution) */

  GET_CHR('}');                 /* consume '}' */
  GET_CHR(';');                 /* consume ';' (end of classifier) */
  return 0;                     /* return 'ok' */
}  /* _parse() */

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

FBC* fbc_parse (ATTSET *attset, SCAN *scan)
{                               /* --- parse a full Bayes classifier */
  FBC *fbc = NULL;              /* created full Bayes classifier */

  assert(attset && scan);       /* check the function arguments */
  pa_init(scan);                /* initialize parsing */
  if (_parse(attset, scan, &fbc) != 0) {
    if (fbc) fbc_delete(fbc,0); /* parse a full Bayes classifier */
    return NULL;                /* if an error occurred, */
  }                             /* delete the classifier and abort */
  fbc_setup(fbc, fbc->mode, fbc->lcorr);
  return fbc;                   /* set up the created classifier */
}  /* fbc_parse() */            /* and then return it */

#endif