fbayes.c

程序用C语言实现了贝叶斯在数据挖掘中分类和预测中的应用

/*----------------------------------------------------------------------
  File    : fbayes.c
  Contents: Full Bayes classifier management
  Author  : Christian Borgelt
  History : 26.11.2000 file created
            29.11.2000 first version completed
            15.07.2001 parser improved (global variables removed)
            16.07.2001 adapted to modified module scan
            17.07.2001 parser improved (conditional look ahead)
            15.09.2001 '*' instead of list of attributes made possible
            26.04.2003 function fbc_rand added
            12.08.2004 adapted to new module parse
----------------------------------------------------------------------*/
#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_FLT)      /* if the attribute is real-valued */
      *--v = (inst->f <= UV_FLT) ? MVN_UNKNOWN : (double)inst->f;
    else                        /* if the attribute is integer-valued */
      *--v = (inst->i <= UV_INT) ? MVN_UNKNOWN : (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_SYM));

  /* --- 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_FLT)) 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_dup (const FBC *fbc, int dupas)
{                               /* --- duplicate a full Bayes class. */
  int    i;                     /* loop variable */
  FBC    *dup;                  /* created classifier duplicate */
  ATTSET *attset;               /* duplicate 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 (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 = (FBC*)malloc(sizeof(FBC) +(fbc->attcnt -1) *sizeof(int));
  if (!dup) { if (dupas) as_delete(attset); return NULL; }
  dup->attset = attset;         /* allocate a classifier body */
  dup->attcnt = fbc->attcnt;    /* and copy the fields */
  dup->numcnt = fbc->numcnt;
  dup->numids = NULL;
  dup->clsid  = fbc->clsid;
  dup->clsvsz = fbc->clscnt;
  dup->clscnt = fbc->clscnt;
  dup->total  = fbc->total;
  dup->lcorr  = fbc->lcorr;
  dup->mode   = fbc->mode;
  dup->frqs   = dup->priors = dup->posts = NULL;
  dup->vals   = NULL;           /* clear pointers for a */
  dup->mvns   = NULL;           /* proper cleanup on error */

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

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

  return dup;                   /* return the created duplicate */
}  /* fbc_dup() */

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

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; )
      if (*--p) mvn_delete(*p); /* delete the multivar. normal dists. */