nposs.c

Programs to induce a naive possibilistic classifier (a possibilistic analog of the naive Bayes class

  fputs("npc(", file);          /* (is needed repeatedly below) */
  sc_format(name, clsname, 0);  /* format and print */
  fputs(name, file);            /* the class attribute name */
  fputs(") = {\n", file);       /* and start the description */
  fprintf(file, "  total = %g;\n", npc->total);

  /* --- print the class distribution --- */
  fputs("  poss(", file);       /* print a distribution indicator */
  fputs(name, file);            /* and the class attribute name and */
  fputs(") = {\n    ", file);   /* start the class distribution */
  pos = 4;                      /* initialize the output position */
  ind = att_valwd(clsatt,0) +2; /* compute position and indentation */
  for (i = 0; i < npc->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(name, att_valname(clsatt, i), 0);
    fputs(name, file);          /* get and print the class name */
    for (pos = len+2; pos < ind; pos++)
      putc(' ', file);          /* pad with blanks to equal width */
    fprintf(file, ": %g", npc->frqs[i]);
    if (mode & NPC_POSS)        /* print the absolute class frequency */
      fprintf(file, " (%.1f%%)", npc->priors[i] *100);
  }                             /* print the relative class frequency */
  fputs(" };\n", file);         /* terminate the class distribution */

  /* --- print the (conditional) distributions --- */
  for (dvec = npc->dvecs, n = 0; n < npc->attcnt; dvec++, n++) {
    if ((dvec->type != AT_SYM)  /* traverse symbolic attributes, */
    ||  (dvec->mark < 0))       /* but skip all unmarked attributes */
      continue;
    fputs("  poss(", file);     /* print a distribution indicator */
    att = as_att(npc->attset,n);/* and get the next attribute */
    sc_format(name, att_name(att), 0);
    fputs(name, file);          /* print the attribute name */
    putc('|', file);            /* and the condition separator */
    sc_format(name, clsname,0); /* format and print */
    fputs(name, file);          /* the class attribute name */
    fputs(") = {\n    ", file); /* and start the cond. distribution */
    pd = dvec->possds;          /* traverse the poss. distributions */
    for (i = 0; i < npc->clscnt; pd++, i++) {
      if (i > 0)                /* if this is not the first class, */
        fputs(",\n    ", file); /* start a new output line */
      len = sc_format(name, att_valname(clsatt, i), 0);
      fputs(name, file);        /* get and print the class name */
      for (pos = len+2; pos < ind; pos++)
        putc(' ', file);        /* pad with blanks to equal width */
      fputs(":{", file);        /* start the value distribution and */
      pos += 3;                 /* traverse the attribute values */
      for (k = 0; k < dvec->valcnt; k++) {
        if (k > 0) {            /* if this is not the first value, */
          putc(',', file); pos++; }         /* print a separator */
        len  = sc_format(name, att_valname(att, k), 0);
        len += l = sprintf(num, ": %g", pd->frqs[k]);
        if (mode & NPC_POSS)    /* format value frequency */
          len += sprintf(num +l, " (%.1f%%)", pd->poss[k]*100);
        if ((pos      > ind)    /* if the line would get too long */
        &&  (pos +len > maxlen -4)) {
          putc('\n', file);     /* start a new line and indent */
          for (pos = 0; pos < ind; pos++) putc(' ', file); }
        else {                  /* if there is enough space left, */
          putc(' ', file); pos++; }     /* only print a separator */
        fputs(name, file); fputs(num, file);
        pos += len;             /* print value and its frequency */
      }                         /* and update the output position */
      fputs(" }", file);        /* terminate the value distribution */
    }
    fputs("};\n", file);        /* terminate the distributions */
  }  /* for (n = 0; .. */
  fputs("};\n", file);          /* terminate the classifier */

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

/*--------------------------------------------------------------------*/
#ifdef NPC_PARSE

static int _distin (SCAN *scan, ATT *att, double *frqs)
{                               /* --- read a poss. distribution */
  int    i, cnt;                /* loop variable, number of values */
  double *p, f;                 /* to traverse the frequencies */
  int    t;                     /* buffer for token */

  assert(scan && att && frqs);  /* check the function arguments */
  GET_CHR('{');                 /* consume '{' (start of distrib.) */
  cnt = att_valcnt(att);        /* get the number of att. values */
  for (p = frqs +(i = cnt); --i >= 0; )
    *--p = -1;                  /* clear the value frequencies */
  while (1) {                   /* value read loop */
    t = sc_token(scan);         /* check for a name */
    if ((t != T_ID) && (t != T_NUM)) ERROR(E_VALEXP);
    if (t != T_NUM) t = ':';    /* if the token is no number, */
    else {                      /* the token must be an att. value, */
      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) % cnt;          /* get the cyclic successor id */
    else {                      /* if a  ':' follows */
      i = att_valid(att, sc_value(scan));
      if (i < 0) ERROR(E_UNKVAL);
      sc_next(scan);            /* get and consume the value */
      GET_TOK();                /* consume ':' */
    }
    if (frqs[i] >= 0)           /* check whether value has been read */
      XERROR(E_DUPVAL, att_valname(att, i));
    if (sc_token(scan) != T_NUM) ERROR(E_NUMEXP);
    f = atof(sc_value(scan));   /* get and check */
    if (f < 0) ERROR(E_ILLNUM); /* the value frequency */
    frqs[i] = f;                /* set the value frequency */
    GET_TOK();                  /* consume the value 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_ILLNUM);
      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 (p = frqs +(i = cnt); --i >= 0; )
    if (*--p < 0) *p = 0;       /* clear the unset frequencies */
  return 0;                     /* return 'ok' */
}  /* _distin() */

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

static int _dvecsin (NPC *npc, SCAN *scan, ATT *clsatt)
{                               /* --- read distribution vectors */
  int   i, t;                   /* loop variable, buffer */
  int   attid;                  /* attribute identifier */
  ATT   *att;                   /* current attribute */
  DVEC  *dvec;                  /* to traverse the distrib. vectors */
  POSSD *pd;                    /* to access poss. distribution */

  assert(npc && scan && clsatt);   /* check the function arguments */
  while ((sc_token(scan) == T_ID)  /* while another dist. follows */
  &&     (strcmp(sc_value(scan), "poss") == 0)) {

    /* --- read distribution header --- */
    GET_TOK();                  /* consume 'poss' */
    GET_CHR('(');               /* consume '(' */
    t = sc_token(scan);         /* check for a name */
    if ((t != T_ID) && (t != T_NUM)) ERROR(E_ATTEXP);
    attid = as_attid(npc->attset, sc_value(scan));
    if (attid < 0)                   ERROR(E_UNKATT);
    att  = as_att(npc->attset, attid);
    dvec = npc->dvecs +attid;   /* get and check the attribute */
    if (dvec->type == 0) ERROR(E_ILLATT);
    if (dvec->mark >= 0) ERROR(E_DUPATT);
    dvec->mark = 1;             /* set the read flag */
    GET_TOK();                  /* consume the attribute name */
    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(clsatt)) != 0))
      ERROR(E_CLSEXP);          /* check for the class att. name */
    GET_TOK();                  /* consume the class att. name */
    GET_CHR(')');               /* consume ')' */
    GET_CHR('=');               /* consume '=' */
    GET_CHR('{');               /* consume '{' */

    /* --- read conditional distribution --- */
    if (sc_token(scan) != '}'){ /* if a distribution vector follows */
      for (pd = dvec->possds +(i = npc->clscnt); --i >= 0; )
        (--pd)->poss = NULL;    /* unmark all distributions */
      while (1) {               /* class read loop */
        if (sc_token(scan) == '{')  /* if no class name is given, */
          i = (i+1) % npc->clscnt;  /* get the cyclic successor */
        else {                  /* if a class name is given */
          t = sc_token(scan);   /* check for a name */
          if ((t != T_ID) && (t != T_NUM)) ERROR(E_VALEXP);
          i = att_valid(clsatt, sc_value(scan));
          if (i < 0) ERROR(E_UNKVAL);
          GET_TOK();            /* get and consume the value */
          GET_CHR(':');         /* consume ':' */
        }
        pd = dvec->possds +i;   /* get and check the distribution */
        if (pd->poss) XERROR(E_DUPVAL, att_valname(clsatt, i));
        pd->poss = pd->frqs +dvec->valcnt;
        t = _distin(scan, att, pd->frqs);
        if (t) return t;        /* read the poss. distribution */
        if (sc_token(scan) != ',') break;
        GET_TOK();              /* if at end of list, abort loop, */
      }                         /* otherwise consume ',' */
      for (pd = dvec->possds +(i = npc->clscnt); --i >= 0; )
        if (!(--pd)->poss) pd->poss = pd->frqs +dvec->valcnt;
    }                           /* clear the unset counters */

    GET_CHR('}');               /* consume '}' */
    GET_CHR(';');               /* consume ';' */
  }  /* while ((sc_token == T_ID) .. */
  return 0;                     /* return `ok' */
}  /* _dvecsin() */

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

static int _parse (ATTSET *attset, SCAN *scan, NPC **pnpc)
{                               /* --- parse naive poss. classifier */
  int  i, t;                    /* loop variable, buffer */
  int  err = 0;                 /* error flag */
  int  clsid;                   /* class attribute index */
  ATT  *att;                    /* class attribute */
  NPC  *npc;                    /* created naive poss. classifier */
  DVEC *dvec;                   /* to traverse the distrib. vectors */

  /* --- read header --- */
  if ((sc_token(scan) != T_ID)
  ||  (strcmp(sc_value(scan), "npc") != 0))
    ERR_STR("npc");             /* check for 'npc' */
  GET_TOK();                    /* consume 'npc' */
  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_SYM)     ERROR(E_CLSTYPE);
  if (att_valcnt(att) < 1)         ERROR(E_CLSCNT);
  *pnpc = npc = npc_create(attset, clsid);
  if (!npc) ERROR(E_NOMEM);     /* create a naive poss. classifier */
  GET_TOK();                    /* consume the class name */
  GET_CHR(')');                 /* consume '(' */
  GET_CHR('=');                 /* consume '=' */
  GET_CHR('{');                 /* consume '{' */

  /* --- read total number of cases --- */
  if ((sc_token(scan) != T_ID)
  ||  (strcmp(sc_value(scan), "total") != 0))
    ERR_STR("total");           /* check for 'total' */
  GET_TOK();                    /* consume 'total' */
  GET_CHR('=');                 /* consume '=' */
  if (sc_token(scan) != T_NUM)  ERROR(E_NUMEXP);
  npc->total = atof(sc_value(scan));
  if (npc->total < 0)           ERROR(E_ILLNUM);
  GET_TOK();                    /* consume the number of cases */
  GET_CHR(';');                 /* consume ';' */

  /* --- read class distribution --- */
  if ((sc_token(scan) != T_ID)
  ||  (strcmp(sc_value(scan), "poss") != 0))
    ERR_STR("prob");            /* check for 'poss' */
  GET_TOK();                    /* consume 'poss' */
  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_CLSEXP);            /* check for a class name */
  GET_TOK();                    /* consume the class name */
  GET_CHR(')');                 /* consume ')' */
  GET_CHR('=');                 /* consume '=' */
  t = _distin(scan, att, npc->frqs);
  if (t) return t;              /* read the class distribution */
  GET_CHR(';');                 /* consume ';' */
  npc->dvecs[clsid].mark = 0;   /* mark the class attribute */

  /* --- read conditional distributions --- */
  do {                          /* read the distributions, */
    t = _dvecsin(npc,scan,att); /* trying to recover on errors */
    if (t) { err = t; sc_recover(scan, ';', 0, 0, 0); }
  } while (t);                  /* while not all dists. read */
  if (err) return err;          /* if an error occurred, abort */
  for (dvec = npc->dvecs, i = 0; i < npc->attcnt; dvec++, i++) {
    if ((dvec->mark < 0) && (npc->frqs[i] > 0))
      XERROR(E_MISATT, att_name(as_att(attset, i)));
  }                             /* check for a complete classifier */

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

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

NPC* npc_parse (ATTSET *attset, SCAN *scan)
{                               /* --- parse a naive poss. class. */
  NPC *npc = NULL;              /* created naive poss. classifier */

  assert(attset);               /* check the function arguments */
  pa_init(scan);                /* initialize parsing */
  if (_parse(attset, scan, &npc) != 0) {   
    if (npc) npc_delete(npc,0); /* parse a naive poss. classifier */
    return NULL;                /* if an error occurred, */
  }                             /* delete the classifier and abort */
  npc_setup(npc);               /* set up the created classifier */
  return npc;                   /* and then return it */
}  /* npc_parse() */

#endif