nposs.c

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

  if (npc->frqs) free(npc->frqs);
  if (delas)     as_delete(npc->attset);
  free(npc);                    /* delete the classifier body */
}  /* npc_delete() */

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

void npc_clear (NPC *npc)
{                               /* --- clear a naive poss. classifier */
  int    i, k, n;               /* loop variables */
  DVEC   *dvec;                 /* to traverse the distrib. vectors */
  POSSD  *pd;                   /* to traverse the poss. distribs. */
  double *frq;                  /* to traverse the frequency vectors */

  assert(npc);                  /* check the function argument */
  npc->total = 0;               /* clear the total number of cases */
  for (frq = npc->frqs +(i = npc->clscnt); --i >= 0; )
    *--frq = 0;                 /* clear the class frequencies */
  for (dvec = npc->dvecs +(i = npc->attcnt); --i >= 0; ) {
    if (!(--dvec)->possds)      /* traverse all */
      continue;                 /* symbolic attributes */
    for (pd = dvec->possds +(k = npc->clscnt); --k >= 0; ) {
      for (frq = (--pd)->frqs +(n = dvec->valcnt); --n >= 0; )
        *--frq = 0;             /* for each distribution */
    }                           /* traverse the frequency vector */
  }                             /* and clear the value frequencies */
}  /* npc_clear() */

/*--------------------------------------------------------------------*/
#ifdef NPC_INDUCE

NPC* npc_induce (TABLE *table, int clsid, int mode)
{                               /* --- induce a naive poss. class. */
  int    i, r = 0, t;           /* loop variable, buffers */
  int    cnt;                   /* number of selectable attributes */
  int    cls;                   /* predicted class */
  NPC    *npc;                  /* created classifier */
  ATTSET *attset;               /* attribute set of the classifier */
  SELATT *savec;                /* vector of selectable attributes */
  SELATT *sa, *best;            /* to traverse the selectable atts. */
  TUPLE  *tpl;                  /* to traverse the tuples */
  DVEC   *dvec;                 /* to traverse the distrib. vectors */
  double *p;                    /* to traverse the class possib. */
  double max;                   /* maximum of class possibilities */
  double errs;                  /* weight sum of misclassified tuples */

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

  /* --- create a classifier --- */
  attset = tab_attset(table);   /* get the attribute set of the table */
  if (mode & NPC_DUPAS) {       /* if the corresp. flag is set, */
    attset = as_dup(attset);    /* duplicate the attribute set */
    if (!attset) return NULL;   /* of the given data table, */
  }                             /* then create a classifier */
  npc = npc_create(attset, clsid);
  if (!npc) { if (mode & NPC_DUPAS) as_delete(attset); return NULL; }

  /* --- build initial classifier --- */
  if (mode & NPC_ADD) {         /* if to add attributes */
    for (i = tab_tplcnt(table); --i >= 0; ) {
      tpl = tab_tpl(table,i);   /* traverse the tuples in the table */
      cls = tpl_colval(tpl, npc->clsid)->i;
      if (cls < 0) continue;    /* skip tuples with an unknown class */
      assert(cls < npc->clscnt);/* and check the class value */
      npc->frqs[cls] += tpl_getwgt(tpl);
    } }                         /* determine the class frequencies */
  else {                        /* if to remove attributes */
    for (dvec = npc->dvecs +(i = npc->attcnt); --i >= 0; ) {
      t = (--dvec)->type;       /* traverse all attributes */
      dvec->mark = ((t == 0) || (t == AT_SYM)) ? i : -1;
      att_setmark(as_att(attset, i), dvec->mark);
    }                           /* mark class and symbolic attributes */
    if (_induce(npc, table) != 0) {
      npc_delete(npc, mode & NPC_DUPAS); return NULL; }
  }                             /* create a full classifier */
  npc_setup(npc);               /* set up classifier for execution */
  if (!(mode & (NPC_ADD|NPC_REMOVE))) /* if no simp. is requested, */
    return npc;                 /* return the created classifier */

  /* --- evaluate initial classifier --- */
  if (mode & NPC_ADD) {         /* if to add attributes */
    p = npc->frqs; errs = max = *p;
    for (i = npc->clscnt; --i > 0; ) {
      errs += *++p;             /* traverse the class frequencies, */
      if (*p > max) max = *p;   /* sum them, and determine their */
    }                           /* maximum (find the majority class) */
    errs -= max; }              /* compute the number of prior errors */
  else {                        /* if to remove attributes */
    for (errs = 0, i = tab_tplcnt(table); --i >= 0; ) {
      tpl = tab_tpl(table,i);   /* traverse the tuples in the table */
      cls = tpl_colval(tpl, clsid)->i;
      if (cls < 0) continue;    /* skip tuples with an unknown class */
      if (npc_exec(npc, tpl, NULL) != cls)
        errs += tpl_getwgt(tpl);/* classify the current tuple */
    }                           /* and determine the number */
  }                             /* of misclassifications */
  #ifndef NDEBUG
  fprintf(stderr, "\n%8g errors initially\n", errs);
  #endif                        /* print a counter for debugging */

  /* --- collect selectable attributes --- */
  savec = malloc(npc->attcnt *sizeof(SELATT));
  if (!savec) { npc_delete(npc, mode & NPC_DUPAS); return NULL; }
  sa = savec;                   /* create vector of selectable atts. */
  for (dvec = npc->dvecs +(i = npc->attcnt); --i >= 0; ) {
    (--dvec)->mark = -1;        /* traverse all attributes */
    if ( (dvec->type == 0)      /* except the class attribute */
    ||  ((dvec->type == AT_SYM) /* and all symbolic attributes */
    &&   (dvec->valcnt <= 0)))  /* that do not have any values */
      continue;
    if (dvec->type != AT_SYM)   /* skip all attributes */
      continue;                 /* that are not symbolic */
    if (mode & NPC_REMOVE)      /* if to remove attributes, */
      dvec->mark = i;           /* mark all selectable attributes */
    sa->attid = i;              /* note selectable attributes and */
    sa->errs  = 0; sa++;        /* initialize the number of errors */
  }
  cnt = (int)(sa -savec);       /* compute the number of attributes */
  npc->dvecs[npc->clsid].mark = npc->clsid;       /* mark the class */
  for (dvec = npc->dvecs +(i = npc->attcnt); --i >= 0; ) {
    --dvec; att_setmark(as_att(attset, i), dvec->mark);
  }                             /* transfer markers to attribute set */

  /* --- select attributes --- */
  while ((cnt  > 0)             /* while there are selectable atts. */
  &&     (errs > 0)) {          /* and the classifier is not perfect */
    for (sa = savec +(i = cnt); --i >= 0; )
      (--sa)->errs = 0;         /* clear the numbers of errors */
    r = _eval(npc, table, mode, savec, cnt);
    if (r < 0) break;           /* evaluate selectable attributes */
    best = sa = savec;          /* traverse the selectable attributes */
    for (i = cnt; --i > 0; ) {  /* in order to find the best */
      if (((++sa)->errs <  best->errs)
      ||  ((  sa ->errs <= best->errs) && (mode & NPC_ADD)))
        best = sa;              /* find least number of errors and */
    }                           /* note the corresponding attribute */
    if ( (best->errs >  errs)   /* if more tuples were misclassified */
    ||  ((best->errs >= errs) && (mode & NPC_ADD)))
      break;                    /* abort the selection loop */
    errs = best->errs;          /* note the new number of errors */
    #ifndef NDEBUG
    fprintf(stderr, "%8g errors %s\n", best->errs,
            att_name(as_att(attset, best->attid)));
    #endif                      /* print a counter for debugging */
    i = (mode & NPC_ADD) ? best->attid : -1;  /* mark/unmark the */
    npc->dvecs[best->attid].mark = i;      /* selected attribute */
    att_setmark(as_att(attset, best->attid), i);
    for (--cnt; best < sa; best++)  /* remove the selected */
      best->attid = best[1].attid;  /* attribute from the  */
  }                                 /* list of attributes  */
  free(savec);                  /* delete the selectable atts. vector */

  if ((r < 0)                   /* if an error occurred or the class. */
  ||  (_induce(npc, table) != 0)) {     /* cannot be reinduced, abort */
    npc_delete(npc, mode & NPC_DUPAS); return NULL; }
  npc_setup(npc);               /* set up classifier for execution */
  return npc;                   /* and return the created classifier */
}  /* npc_induce() */

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

int npc_mark (NPC *npc)
{                               /* --- mark selected attributes */
  int  i, m;                    /* loop variable, buffer for marker */
  DVEC *dvec;                   /* to traverse the distrib. vectors */
  int  cnt = 0;                 /* attribute counter */

  assert(npc);                  /* check the function argument */
  for (dvec = npc->dvecs +(i = npc->attcnt); --i >= 0; ) {
    if ((--dvec)->mark < 0) m = -1;
    else           { cnt++; m =  1; }
    att_setmark(as_att(npc->attset, i), m);
  }                             /* transfer marker to attribute set */
  att_setmark(as_att(npc->attset, npc->clsid), 0);
  return cnt;                   /* return number of marked atts. */
}  /* npc_mark() */

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

void npc_setup (NPC *npc)
{                               /* --- set up a naive poss. class. */
  int    i, k, n;               /* loop variables */
  DVEC   *dvec;                 /* to traverse the distrib. vectors */
  POSSD  *pd;                   /* to traverse the poss. distribs. */
  double *frq, *poss;           /* to traverse the value frqs./poss. */
  double cnt;                   /* (reciprocal of) number of cases */

  assert(npc);                  /* check the function argument */
  cnt = npc->total;             /* get the total number of cases */

  /* --- compute class possibilities --- */
  n    = npc->clscnt;           /* get the number of classes and */
  poss = npc->priors +n;        /* traverse the class possibilities */
  if (cnt <= 0)                 /* if the denominator is invalid, */
    while (--n >= 0) *--poss = 0;      /* clear all possibilities */
  else {                        /* if the denominator is valid, */
    cnt = 1/cnt;                /* compute normalization factor */
    for (frq = npc->frqs +n; --n >= 0; )
      *--poss = *--frq *cnt;    /* compute the class possibilities */
  }                             /* from the one point coverages */

  /* --- compute conditional possibilities --- */
  for (dvec = npc->dvecs +(i = npc->attcnt); --i >= 0; ) {
    --dvec;                     /* traverse all attributes */
    if ((dvec->type != AT_SYM)  /* skip the class attribute */
    ||  (dvec->valcnt <= 0)     /* and symbolic attributes */
    ||  (dvec->mark   <  0))    /* without any values */
      continue;                 /* and unmarked attributes */
    for (pd = dvec->possds +(k = npc->clscnt); --k >= 0; ) {
      n    = dvec->valcnt;      /* for each distribution */
      poss = (--pd)->poss +n;   /* traverse the possibilities */
      if (cnt <= 0)             /* if the denominator is invalid, */
        while (--n >= 0) *--poss = 0;        /* clear all poss. */
      else {                    /* if the denominator is valid */
        for (frq = pd->frqs +n; --n >= 0; )
          *--poss = *--frq *cnt;
      }                         /* compute the value possibilities */
    }                           /* from the one point coverages */
  }
}  /* npc_setup() */

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

int npc_exec (const NPC *npc, const TUPLE *tpl, double *conf)
{                               /* --- execute a naive poss. class. */
  int         i, k;             /* loop variables */
  const DVEC  *dvec;            /* to traverse the distrib. vectors */
  const INST  *inst;            /* to traverse the instances */
  const POSSD *pd;              /* to traverse the poss. distribs. */
  double      *s, *d;           /* to traverse the possibilities */
  double      poss;             /* buffer for cond. possibility */

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

  /* --- initialize --- */
  s = npc->priors +npc->clscnt; /* init. the posterior distribution */
  d = npc->posts  +npc->clscnt; /* with  the prior     distribution */
  for (k = npc->clscnt; --k >= 0; ) *--d = *--s;

  /* --- process attribute values --- */
  for (dvec = npc->dvecs +(i = npc->attcnt); --i >= 0; ) {
    --dvec;                     /* traverse all attributes */
    if ((dvec->type != AT_SYM)  /* except the class attribute, */
    ||  (dvec->mark < 0))       /* all non-symbolic attributes, */
      continue;                 /* and all unmarked attributes */
    inst = (tpl)                /* get the attribute instantiation */
         ? tpl_colval(tpl, i)   /* from the tuple or the att. set */
         : att_inst(as_att(npc->attset, i));
    if ((inst->i < 0) || (inst->i >= dvec->valcnt))
      continue;                 /* skip unknown and illegal values */
    pd = dvec->possds +npc->clscnt;  /* traverse the cond. distrib. */
    d  = npc->posts   +npc->clscnt;  /* and the posterior distrib. */
    for (k = npc->clscnt; --k >= 0; ) {
      poss = (--pd)->poss[inst->i];
      if (poss < *--d) *d = poss;
    }                           /* determine the minimum */
  }                             /* of the degrees of possibility */
  s = d = npc->posts;           /* traverse the final distribution */
  for (k = npc->clscnt; --k > 0; )
    if (*++s > *d) d = s;       /* find the most possible class */
  if (conf) *conf = *d;         /* and get the confidence value */
  return (int)(d -npc->posts);  /* return the classification result */
}  /* npc_exec() */

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

int npc_desc (const NPC *npc, FILE *file, int mode, int maxlen)
{                               /* --- describe a naive poss. class. */
  int         i, k, n;          /* loop variables */
  int         pos, ind;         /* current position and indentation */
  int         len, l;           /* length of class/value name/number */
  const char  *clsname;         /* name of class attribute */
  ATT         *att, *clsatt;    /* to traverse the attributes */
  const DVEC  *dvec;            /* to traverse the distrib. vectors */
  const POSSD *pd;              /* to traverse the poss. distribs. */
  char  name[4*AS_MAXLEN+4];    /* output buffer for names */
  char  num[64];                /* output buffer for numbers */

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

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

  /* --- start description --- */
  clsatt  = as_att(npc->attset, npc->clsid);
  clsname = att_name(clsatt);   /* note the class attribute name */