/*----------------------------------------------------------------------  File    : nposs.c  Contents: Naive possibilistic classifier management  Author  : Christian Borgelt  History : 07.02.2001 file created from file nbayes.c            09.02.2001 first version of standalone module completed            15.07.2001 parser improved (global variables removed)            17.07.2001 adapted to modified module scan            12.08.2004 adapted to new module parse----------------------------------------------------------------------*/#include <stdio.h>#include <stdlib.h>#include <string.h>#include <math.h>#include <assert.h>#ifndef TAB_OPC#define TAB_OPC#endif#include "nposs.h"#ifdef STORAGE#include "storage.h"#endif/*----------------------------------------------------------------------  Type Definitions----------------------------------------------------------------------*/typedef struct {                /* --- selectable attribute --- */  int    attid;                 /* attribute identifier */  double errs;                  /* number of misclassifications */} SELATT;                       /* (selectable attribute) *//*----------------------------------------------------------------------  Auxiliary Functions----------------------------------------------------------------------*/#ifdef NPC_INDUCEstatic int _induce (NPC *npc, TABLE *table){                               /* --- induce a poss. classifier */  int    i, k, n;               /* loop variables, buffer */  int    clsid;                 /* index of the class attribute */  int    cls;                   /* value of the class attribute */  TABLE  *opc;                  /* table of one point coverages */  ATTSET *sel;                  /* current selection of attributes */  TUPLE  *tpl;                  /* to traverse the tuples */  DVEC   *dvec;                 /* to traverse the distrib. vectors */  POSSD  *dist;                 /* to traverse the distributions */  double *p;                    /* to traverse the poss. degrees */  float  wgt;                   /* buffer for tuple weight */  assert(npc && table);         /* check the function arguments */  /* --- determine one point coverages --- */  sel = as_create("opc", att_delete);  if (!sel) return -1;          /* create a table for the */  opc = tab_create("opc", sel, tpl_delete);  /* one point */  if (!opc) { as_delete(sel); return -1; }   /* coverages */  if (tab_colcopy(opc, table, TAB_MARKED) != 0) {    tab_delete(opc, 1); return -1; }  tab_reduce(opc);              /* determine one point coverages */  if (tab_opc(opc, TAB_COND) != 0) {      /* for the subspace of */    tab_delete(opc, 1); return -1; }      /* the sel. attributes */  for (clsid = as_attcnt(sel); --clsid >= 0; )    if (att_getmark(as_att(sel, clsid)) == npc->clsid)      break;                    /* find the index of the class */  assert(clsid >= 0);           /* attribute in the o.p.c. table */  /* --- build the classifier --- */  npc_clear(npc);               /* clear the classifier */  npc->total = tab_getwgt(table, 0, INT_MAX);  for (n = tab_tplcnt(opc); --n >= 0; ) {    tpl = tab_tpl(opc, n);      /* traverse the one point coverages */    cls = tpl_colval(tpl, clsid)->i;    if (cls < 0) continue;      /* skip tuples with an unknown class */    assert(cls < npc->clscnt);  /* check the class value */    wgt = tpl_getwgt(tpl);      /* get the tuple weight */    for (i = as_attcnt(sel); --i >= 0; ) {      if (i == clsid) {         /* traverse all attributes */        p = npc->frqs +cls;     /* if this is the class attribute, */        if (wgt > *p) *p = wgt; /* update the maximum projection */        continue;               /* and continue with the next att. */      }      dvec = npc->dvecs +att_getmark(as_att(sel, i));      dist = dvec->possds +cls; /* get the class spec. distribution */      k = tpl_colval(tpl,i)->i; /* get the current attribute's value */      assert(k < dvec->valcnt); /* and check it */      if (k >= 0) {             /* if the attribute value is known, */        p = dist->frqs +k;      /* process this value */        if (wgt > *p) *p = wgt; }      else {                    /* otherwise traverse all values */        for (p = dist->frqs +(k = dvec->valcnt); --k >= 0; )          if (wgt > *--p) *p = wgt;      }                         /* (update the maximum projection */    }                           /* to the subspace scaffolded by */  }                             /* the class and the attribute) */  /* --- clean up --- */  tab_delete(opc, 1);           /* delete the one point coverages */  return 0;                     /* return `ok' */}  /* _induce() *//*--------------------------------------------------------------------*/static int _eval (NPC *npc, TABLE *table, int mode,                  SELATT *savec, int cnt){                               /* --- evaluate selectable attributes */  int    i, k;                  /* loop variables */  int    cls;                   /* predicted class */  ATT    *att;                  /* to traverse the attributes */  SELATT *sa;                   /* to traverse the selectable atts. */  TUPLE  *tpl;                  /* to traverse the tuples */  assert(npc && table && savec  /* check the function arguments */     && (cnt > 0) && (mode & (NPC_ADD|NPC_REMOVE)));  for (sa = savec +(i = cnt); --i >= 0; ) {    --sa;                       /* traverse the selectable attributes */    npc->dvecs[sa->attid].mark = k = (mode & NPC_ADD) ? sa->attid : -1;    att = as_att(npc->attset, sa->attid);    att_setmark(att, k);        /* mark/unmark the next attribute */    if (_induce(npc, table) != 0)      return -1;                /* induce a possibilistic classifier */    npc_setup(npc);             /* and set it up for execution */    for (k = tab_tplcnt(table); --k >= 0; ) {      tpl = tab_tpl(table, k);  /* traverse the original tuples */      cls = tpl_colval(tpl, npc->clsid)->i;      if (cls < 0) continue;    /* skip tuples with an unknown class */      if (npc_exec(npc, tpl, NULL) != cls)        sa->errs += tpl_getwgt(tpl);    }                           /* count the number of misclassific. */    npc->dvecs[sa->attid].mark = k = (mode & NPC_ADD) ? -1 : sa->attid;    att_setmark(att, k);        /* restore the attribute mark */  }                             /* (restore old set of attributes) */  return 0;                     /* return 'ok' */}  /* _eval() */#endif/*----------------------------------------------------------------------  Functions----------------------------------------------------------------------*/NPC* npc_create (ATTSET *attset, int clsid){                               /* --- create a naive poss. class. */  int    i, k, n;               /* loop variables */  NPC    *npc;                  /* created possibilistic classifier */  ATT    *att;                  /* to traverse the attributes */  DVEC   *dvec;                 /* to traverse the distrib. vectors */  POSSD  *pd;                   /* to traverse the poss. distribs. */  double *frq;                  /* to traverse the frequency vectors */  assert(attset && (clsid >= 0) /* check the function arguments */      && (clsid < as_attcnt(attset))      && (att_type(as_att(attset, clsid)) == AT_SYM));  i   = as_attcnt(attset);      /* get the number of attributes */  npc = (NPC*)malloc(sizeof(NPC) +(i-1) *sizeof(DVEC));  if (!npc) return NULL;        /* allocate the classifier body */  for (dvec = npc->dvecs +(k = i); --k >= 0; )    (--dvec)->possds = NULL;    /* clear the distribution vectors */  npc->attset = attset;         /* (for a proper clean up on error) */  npc->attcnt = i;              /* and initialize the other fields */  npc->clsid  = clsid;  npc->clscnt = att_valcnt(as_att(attset, clsid));  npc->total  = 0;  if (npc->clscnt <= 0) {       /* if there are no classes, */    npc->frqs   =               /* no class vectors are needed */    npc->priors = npc->posts = npc->buf = NULL; }  else {                        /* if there are classes, */    npc->frqs =                 /* allocate class vectors */    frq = (double*)malloc(npc->clscnt *4 *sizeof(double));    if (!frq) { npc_delete(npc, 0); return NULL; }    npc->priors = frq         +npc->clscnt;    npc->posts  = npc->priors +npc->clscnt;    npc->buf    = npc->posts  +npc->clscnt;    for (frq += k = npc->clscnt; --k >= 0; )      *--frq = 0;               /* traverse the frequency vector */  }                             /* and init. the class frequencies */  for (dvec = npc->dvecs +(i = npc->attcnt); --i >= 0; ) {    (--dvec)->mark = -1;        /* traverse and unmark all attributes */    if (i == clsid) {           /* if this is the class attribute, */      dvec->type = 0; continue;}/* clear the type for easier recogn. */    att = as_att(attset, i);    /* get the next attribute */    dvec->type = att_type(att); /* and its type */    if (dvec->type != AT_SYM)   /* skip all attributes */      continue;                 /* that are not symbolic */    dvec->valcnt = att_valcnt(att);    if (npc->clscnt <= 0)       /* if there are no classes, */      continue;                 /* there is nothing else to do */    dvec->possds =              /* create a vector of poss. distribs. */    pd = (POSSD*)calloc(npc->clscnt, sizeof(POSSD));    if (!pd) { npc_delete(npc, 0); return NULL; }    if (dvec->valcnt <= 0)      /* if the attribute has no values, */      continue;                 /* there is nothing else to do */    for (pd += k = npc->clscnt; --k >= 0; ) {      (--pd)->frqs =            /* create a value frequency vector */      frq = (double*)malloc(dvec->valcnt *2 *sizeof(double));      pd->poss = frq +dvec->valcnt;      for (frq += n = dvec->valcnt; --n >= 0; )        *--frq = 0;             /* traverse the frequency vectors */    }                           /* and init. the value frequencies */  }  return npc;                   /* return the created classifier */}  /* npc_create() *//*--------------------------------------------------------------------*/NPC* npc_dup (NPC *npc, int dupas){                               /* --- duplicate a naive poss. class. */  NPC    *dup;                  /* created classifier duplicate */  ATTSET *attset;               /* duplicate of attribute set */  int    i, k, n;               /* loop variables */  DVEC   *dv; const DVEC   *sv; /* to traverse the distrib. vectors */  POSSD  *dd; const POSSD  *sd; /* to traverse the poss. distribs. */  double *df; const double *sf; /* to traverse the frequency vectors */  assert(npc);                  /* check the function argument */  /* --- copy the classifier body --- */  attset = npc->attset;         /* get the attribute set */  if (dupas) {                  /* if the corresp. flag is set, */    attset = as_dup(attset);    /* duplicate the attribute set */    if (!attset) return NULL;   /* of the original classifier, */  }                             /* and then create a classifier */  dup = (NPC*)malloc(sizeof(NPC) +(npc->attcnt-1) *sizeof(DVEC));  if (!dup) { if (dupas) as_delete(attset); return NULL; }  for (dv = dup->dvecs +(i = dup->attcnt); --i >= 0; )    (--dv)->possds = NULL;      /* clear the distribution vectors */  dup->attset = attset;         /* (for a proper clean up on error) */  dup->attcnt = npc->attcnt;    /* and copy the other fields */  dup->clsid  = npc->clsid;  dup->clscnt = npc->clscnt;  dup->total  = npc->total;  /* --- copy the class distributions --- */  if (npc->clscnt <= 0)         /* if there are no classes, */    dup->frqs   =               /* no class vectors are needed */    dup->priors = dup->posts = dup->buf = NULL;  else {                        /* if there are classes, */    dup->frqs =                 /* allocate class vectors */    df = (double*)malloc(dup->clscnt *4 *sizeof(double));    if (!df) { npc_delete(dup, dupas); return NULL; }    dup->priors = dup->frqs   +dup->clscnt;    dup->posts  = dup->priors +dup->clscnt;    dup->buf    = dup->posts  +dup->clscnt;    sf = npc->frqs +2 *dup->clscnt;    for (df += k = 2 *dup->clscnt; --k >= 0; )      *--df = *--sf;            /* traverse the frequency vector */  }                             /* and copy the class frequencies */  sv = npc->dvecs +npc->attcnt; /* get pointers to the */  dv = dup->dvecs +npc->attcnt; /* distribution vectors */  for (i = npc->attcnt; --i >= 0; ) {    --sv; (--dv)->mark = -1;    /* traverse the distribution vectors */    dv->mark   = sv->mark;      /* copy the attribute mark, */    dv->type   = sv->type;      /* the attribute type, */    dv->valcnt = sv->valcnt;    /* the number of attribute values */    if ((sv->type != AT_SYM)    /* if the attribute is not symbolic */    ||  (npc->clscnt <= 0))     /* or if there are no classes, */      continue;                 /* there is nothing else to do */    dv->possds =                /* create a vector of poss. dists. */    dd = (POSSD*)calloc(dup->clscnt, sizeof(POSSD));    if (!dd) { npc_delete(dup, dupas); return NULL; }    if (sv->valcnt <= 0)        /* if the attribute has no values, */      continue;                 /* there is nothing else to do */    sd = sv->possds +npc->clscnt;    for (dd += (k = npc->clscnt); --k >= 0; ) {      --dd; --sd;               /* traverse the poss. distributions */      dd->frqs =                /* create a value frequency vector */      df = (double*)malloc(dv->valcnt *2 *sizeof(double));      if (!df) { npc_delete(dup, dupas); return NULL; }      dd->poss = df +dv->valcnt;      sf = sd->frqs +2 *dv->valcnt;      for (df += n = 2 *dv->valcnt; --n >= 0; )        *--df = *--sf;          /* traverse the frequency vectors */    }                           /* and copy the value frequencies */  }  return dup;                   /* return the created duplicate */}  /* npc_dup() *//*--------------------------------------------------------------------*/void npc_delete (NPC *npc, int delas){                               /* --- delete a naive poss. class. */  int   i, k;                   /* loop variables */  DVEC  *dvec;                  /* to traverse the distrib. vectors */  POSSD *pd;                    /* to traverse the poss. distribs. */  assert(npc);                  /* check the function argument */  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; )      if ((--pd)->frqs) free(pd->frqs);    free(dvec->possds);         /* delete all frequency vectors */  }                             /* and the distribution vectors */