fbayes.c

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

/*----------------------------------------------------------------------
  File    : fbayes.c
  Contents: Full Bayes classifier management
  Author  : Christian Borgelt
  History : 2000.11.26 file created
            2000.11.29 first version completed
            2001.07.15 parser improved (global variables removed)
            2001.07.16 adapted to modified module scan
            2001.07.17 parser improved (conditional look ahead)
            2001.09.15 '*' instead of list of attributes made possible
            2003.04.26 function fbc_rand added
            2004.08.12 adapted to new module parse
            2007.02.13 adapted to modified module attset
            2007.03.21 function fbc_exec extended (posterior probs.)
            2007.10.19 bug in fbc_exec fixed (posterior probs.)
----------------------------------------------------------------------*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <assert.h>
#include "fbayes.h"
#ifdef STORAGE
#include "storage.h"
#endif

/*----------------------------------------------------------------------
  Preprocessor Definitions
----------------------------------------------------------------------*/
#define EPSILON     1e-12       /* to handle roundoff errors */
#define BLKSIZE     16          /* block size for vectors */

/*----------------------------------------------------------------------
  Auxiliary Functions
----------------------------------------------------------------------*/
#ifdef FBC_INDUCE

static int _clsrsz (FBC *fbc, int clscnt)
{                               /* --- resize class dependent vectors */
  int    i;                     /* loop variable */
  int    clsvsz;                /* size of the class dep. vectors */
  double *frq;                  /* to traverse the frequency vectors */
  MVNORM **mvn;                 /* to traverse the distributions */

  assert(fbc && (clscnt >= 0)); /* check the function arguments */

  /* --- resize the class dependent vectors --- */
  clsvsz = fbc->clsvsz;         /* get the class dep. vector size */
  if (clscnt >= clsvsz) {       /* if the vectors are too small */
    clsvsz += (clsvsz > BLKSIZE) ? clsvsz >> 1 : BLKSIZE;
    if (clscnt >= clsvsz) clsvsz = clscnt;
    frq = (double*)realloc(fbc->frqs, clsvsz *3 *sizeof(double));
    if (!frq) return -1;        /* resize the frequencies vector */
    fbc->frqs   = frq;          /* and set the new vector */
    fbc->priors = fbc->frqs   +clsvsz;  /* organize the rest of the */
    fbc->posts  = fbc->priors +clsvsz;  /* allocated memory block */
    for (frq += clsvsz, i = clsvsz -fbc->clsvsz; --i >= 0; )
      *--frq = 0;               /* clear the new vector fields */
    mvn = (MVNORM**)realloc(fbc->mvns, clsvsz *sizeof(MVNORM*));
    if (!mvn) return -1;        /* resize the distribution vector */
    fbc->mvns   = mvn;          /* and set the new vector */
    fbc->clsvsz = clsvsz;       /* set the new size of the */
  }                             /* class dependent vectors */

  /* --- create new conditional distributions --- */
  mvn = fbc->mvns +clscnt;      /* traverse the normal distributions */
  for (i = clscnt -fbc->clscnt; --i >= 0; ) {
    *--mvn = mvn_create(fbc->numcnt);
    if (!*mvn) break;           /* create new normal distributions */
  }
  if (i >= 0) {                 /* if an error occurred */
    for (i = fbc->clscnt -i; --i >= 0; mvn++)
      mvn_delete(*mvn);         /* delete the newly created */
    return -1;                  /* multivariate normal distributions */
  }                             /* and abort the function */

  fbc->clscnt = clscnt;         /* set the new number of classes */
  return 0;                     /* return 'ok' */
}  /* _clsrsz() */

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

static void _getvals (FBC *fbc, const TUPLE *tpl)
{                               /* --- get the attribute values */
  int    i;                     /* loop variable */
  const  INST *inst;            /* to traverse the instances */
  FBCID  *p;                    /* to traverse the attribute ids. */
  double *v;                    /* to traverse the att. value vector */

  assert(fbc);                  /* check the function argument */
  v = fbc->vals +fbc->numcnt;   /* get the attribute value vector */
  for (p = fbc->numids +(i = fbc->numcnt); --i >= 0; ) {
    --p;                        /* traverse the numeric attributes */
    inst = (tpl) ? tpl_colval(tpl, p->id) : att_inst(p->att);
    if (p->type == AT_REAL)     /* if the attribute is real-valued */
      *--v = (inst->f <= NV_REAL) ? MVN_NULL : (double)inst->f;
    else                        /* if the attribute is integer-valued */
      *--v = (inst->i <= NV_INT)  ? MVN_NULL : (double)inst->i;
  }                             /* (collect attribute values) */
}  /* _getvals() */

/*----------------------------------------------------------------------
  Main Functions
----------------------------------------------------------------------*/

FBC* fbc_create (ATTSET *attset, int clsid)
{                               /* --- create a full Bayes classifier */
  int    i, t;                  /* loop variable, attribute type */
  FBC    *fbc;                  /* created classifier */
  FBCID  *p;                    /* to traverse the attribute ids. */
  ATT    *att;                  /* to traverse the attributes */
  double *frq;                  /* to traverse the frequency vector */
  MVNORM **mvn;                 /* to traverse the distributions */

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

  /* --- create the classifier body --- */
  i   = as_attcnt(attset);      /* get the number of attributes */
  fbc = (FBC*)malloc(sizeof(FBC) +(i-1) *sizeof(int));
  if (!fbc) return NULL;        /* allocate the classifier body */
  fbc->attset = attset;         /* and initialize the fields */
  fbc->attcnt = i;
  fbc->numcnt = 0;
  fbc->numids = NULL;
  fbc->clsid  = clsid;
  fbc->clsvsz = att_valcnt(as_att(attset, clsid));
  fbc->clscnt = fbc->clsvsz;
  fbc->total  = 0;
  fbc->lcorr  = 0;
  fbc->mode   = 0;
  fbc->frqs   = fbc->priors = fbc->posts = NULL;
  fbc->vals   = NULL;           /* clear pointers for a */
  fbc->mvns   = NULL;           /* proper cleanup on error */

  /* --- create the attribute information --- */
  fbc->numids = p = (FBCID*)malloc(fbc->attcnt *sizeof(FBCID));
  if (!p) { fbc_delete(fbc, 0); return NULL; }
  for (i = 0; i < fbc->attcnt; i++) {
    att = as_att(attset, i); t = att_type(att);
    if ((t != AT_INT) && (t != AT_REAL)) continue;
    p->id  = i; p->type = t;    /* count the numeric attributes */ 
    p->att = att; p++;          /* and note their identifications */
  }                             /* and types */
  fbc->numcnt = (int)(p -fbc->numids);
  fbc->vals = (double*)malloc(fbc->attcnt *sizeof(double));
  if (!fbc->vals) { fbc_delete(fbc, 0); return NULL; }
                                /* create an attribute value buffer */

  /* --- initialize the distributions --- */
  if (fbc->clscnt > 0) {        /* if there are classes, */
    fbc->frqs =                 /* allocate class vectors */
    frq = (double*)malloc(fbc->clsvsz *3 *sizeof(double));
    if (!frq) { fbc_delete(fbc, 0); return NULL; }
    fbc->priors = fbc->frqs   +fbc->clsvsz;
    fbc->posts  = fbc->priors +fbc->clsvsz;
    for (frq += i = fbc->clsvsz; --i >= 0; )
      *--frq = 0;               /* init. the class frequencies */
    fbc->mvns = mvn = (MVNORM**)calloc(fbc->clscnt, sizeof(MVNORM*));
    if (!mvn) { fbc_delete(fbc, 0); return NULL; }
    for (mvn += i = fbc->clscnt; --i >= 0; ) {
      *--mvn = mvn_create(fbc->numcnt);
      if (!*mvn) { fbc_delete(fbc, 0); return NULL; }
    }                           /* allocate a distribution vector and */
  }                             /* create multivariate normal dists. */

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

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

FBC* fbc_clone (const FBC *fbc, int cloneas)
{                               /* --- clone a full Bayes classifier */
  int    i;                     /* loop variable */
  FBC    *clone;                /* created classifier clone */
  ATTSET *attset;               /* clone of attribute set */
  double *df; const double *sf; /* to traverse the frequency vectors */
  FBCID  *di; const FBCID  *si; /* to traverse the attribute ids. */
  MVNORM **mvn;                 /* to traverse the distributions */

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

  /* --- copy the classifier body --- */
  attset = fbc->attset;         /* get the attribute set */
  if (cloneas) {                /* if the corresp. flag is set, */
    attset = as_clone(attset);  /* clone the attribute set */
    if (!attset) return NULL;   /* of the original classifier, */
  }                             /* and then create a classifier */
  clone = (FBC*)malloc(sizeof(FBC) +(fbc->attcnt -1) *sizeof(int));
  if (!clone) { if (cloneas) as_delete(attset); return NULL; }
  clone->attset = attset;       /* allocate a classifier body */
  clone->attcnt = fbc->attcnt;  /* and copy the fields */
  clone->numcnt = fbc->numcnt;
  clone->numids = NULL;
  clone->clsid  = fbc->clsid;
  clone->clsvsz = fbc->clscnt;
  clone->clscnt = fbc->clscnt;
  clone->total  = fbc->total;
  clone->lcorr  = fbc->lcorr;
  clone->mode   = fbc->mode;
  clone->frqs   = clone->priors = clone->posts = NULL;
  clone->vals   = NULL;         /* clear pointers for a */
  clone->mvns   = NULL;         /* proper cleanup on error */

  /* --- copy the attribute information --- */
  clone->numids = di = (FBCID*)malloc(clone->attcnt *sizeof(FBCID));
  if (!di) { fbc_delete(clone, cloneas); return NULL; }
  si = fbc->numids +clone->numcnt;
  for (di += i = clone->numcnt; --i >= 0; )
    *--di = *--si;              /* copy the attribute identifications */
  clone->vals = (double*)malloc(clone->attcnt *sizeof(double));
  if (!clone->vals) { fbc_delete(clone, cloneas); return NULL; }
                                /* create an attribute value buffer */

  /* --- copy the distributions --- */
  if (clone->clscnt > 0) {      /* if there are classes, */
    clone->frqs =               /* allocate class vectors */
    df = (double*)malloc(clone->clsvsz *3 *sizeof(double));
    if (!df) { fbc_delete(clone, cloneas); return NULL; }
    clone->priors = clone->frqs   +clone->clsvsz;
    clone->posts  = clone->priors +clone->clsvsz;
    sf = fbc->frqs +2 *clone->clscnt;
    for (df += i = 2 *clone->clscnt; --i >= 0; )
      *--df = *--sf;            /* copy the class frequencies */
    clone->mvns =               /* allocate a distribution vector */
    mvn = (MVNORM**)calloc(clone->clscnt, sizeof(MVNORM*));
    if (!mvn) { fbc_delete(clone, cloneas); return NULL; }
    for (mvn += i = clone->clscnt; --i >= 0; ) {
      *--mvn = mvn_clone(fbc->mvns[i]);
      if (!*mvn) { fbc_delete(clone, cloneas); return NULL; }
    }                           /* copy all multivariate */
  }                             /* normal distributions */

  return clone;                 /* return the created clone */
}  /* fbc_clone() */

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

void fbc_delete (FBC *fbc, int delas)
{                               /* --- delete a full Bayes classifier */
  int    i;                     /* loop variable */
  MVNORM **p;                   /* to traverse the distrib. vector */

  assert(fbc);                  /* check the function argument */
  if (fbc->mvns) {              /* if there is a distribution vector */
    for (p = fbc->mvns +(i = fbc->clscnt); --i >= 0; )