gramod1.c

数据挖掘中的一算法 ines算法 c下实现的。适合初学习数据挖掘者借鉴

/*----------------------------------------------------------------------
  File    : gramod1.c
  Contents: graphical model management (based on directed graphs)
            base functions
  Author  : Christian Borgelt
  History : 23.02.1996 file created as ascons.c
            24.02.1996 functions debugged
            17.03.1996 adapted to attribute types
            26.03.1996 adapted to modified ptree functions
            09.04.1996 functions gm_rand and _order modified
            12.04.1996 deletion of candidate vector in gm_delete added
            18.06.1996 output of frequencies changed to relative numbers
            23.06.1996 line length checks debugged
            26.07.1996 output precision reduced
            15.11.1996 description modes added
            27.11.1996 adapted to floating point counters
            28.02.1997 adapted to prob./poss. tree types
            01.03.1997 function gm_exec added, redesign
            10.03.1997 bug in function gm_exec fixed
            28.08.1997 bug in functions gm_aggr fixed
            08.02.1998 function gm_parse transferred from parse.c
            14.02.1998 description and parsing of links added
            20.02.1998 zero frequency output suppression removed
            23.06.1998 adapted to modified attset functions
            01.03.1999 adapted to extended prob./poss. tree structure
            05.04.1999 parameters 'attid' and 'conid' added to gm_check
            30.04.1999 parameter 'all' added to function gm_parse
            22.10.1999 missing init. of GMATT->deps added to gm_parse
            02.12.1999 parameter 'corr' added to function gm_exec
            26.05.2001 adapted to changed module scan
            08.02.2002 adapted to changed module ptree
            03.03.2002 module renamed to gramod
            11.03.2002 creation of default model added to gm_parse
            16.07.2002 parameter 'delnodes' added to function gm_clear
----------------------------------------------------------------------*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include "gramod.h"
#ifdef STORAGE
#include "storage.h"
#endif

/*----------------------------------------------------------------------
  Preprocessor Definitions
----------------------------------------------------------------------*/
#define BLKSIZE   (PT_MAXCON+1) /* block size for candidate vector */

/*----------------------------------------------------------------------
  Auxiliary Functions
----------------------------------------------------------------------*/

static int _order (GRAMOD *gm)
{                               /* --- find a topological order */
  int   i, k, n, prv;           /* loop variables, counters */
  GMATT *att;                   /* to traverse the attributes */
  int   *ord;                   /* to traverse the topological order */

  assert(gm);                   /* check the function argument */
  ord = gm->order;              /* get the topological order vector */
  att = gm->atts;               /* and traverse the attributes */
  for (i = n = 0; i < gm->attcnt; i++, att++) {
    if (att->ptree              /* if there are conditions */
    && (pt_concnt(att->ptree) > 0)) {
      att->pos = -1; continue;} /* clear the attribute position, */
    *ord++   = i;               /* otherwise add the attribute */
    att->pos = n++;             /* to the topological order */
  }                             /* (collect parentless attributes) */
  while (n < gm->attcnt) {      /* while there are attributes left */
    prv = n;                    /* note the old counter value */
    att = gm->atts;             /* and traverse the attributes */
    for (i = 0; i < gm->attcnt; i++, att++) {
      if (att->pos >= 0)        /* skip all attributes that are */
        continue;               /* already in the topological order */
      for (k = pt_concnt(att->ptree); --k >= 0; )
        if (gm->atts[pt_conid(att->ptree, k)].pos < 0)
          break;                /* skip attributes with a condition */
      if (k >= 0) continue;     /* that is not yet in the top. order */
      *ord++   = i;             /* otherwise add the attribute */
      att->pos = n++;           /* to the topological order */
    }
    if (n <= prv)               /* if no attribute was added, */
      return gm->order[0] = -1; /* there is at least one loop, */
  }                             /* so invalidate the order and abort */
  return 0;                     /* return 'ok' */
}  /* _order() */

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

static GRAMOD* _create (ATTSET *attset, int type)
{                               /* --- create a graphical model */
  int    i;                     /* number of atts. and loop variable */
  GRAMOD *gm;                   /* created graphical model */
  GMATT  *att;                  /* to traverse the attributes */

  assert(attset);               /* check the function argument */
  i  = as_attcnt(attset);       /* get the number of attributes */
  gm = (GRAMOD*)calloc(1, sizeof(GRAMOD) +(i-1) *sizeof(GMATT));
  if (!gm) return NULL;         /* allocate the base structure */
  gm->order    = (int*)malloc(2 *i *sizeof(int));
  if (!gm->order) { free(gm); return NULL; }
  gm->buf    = gm->order +i;    /* create and organize vectors */
  gm->type   = type & GM_POSS;  /* set the tree type (prob./poss.) */
  gm->attset = attset;          /* note the attribute set */
  gm->attcnt = i;               /* and the number of attributes */
  gm->concnt = 0;               /* clear the number of conditions */
  gm->tplcnt = 0;               /* the number of tuples, */
  gm->eval   = 0;               /* and the evaluation result */
  gm->order[0] = -1;            /* invalidate the topological order */
  for (att = gm->atts +i; --i >= 0; )  /* note the */
    (--att)->att = as_att(attset, i);  /* corresp. attributes */
  return gm;                    /* return created graphical model */
}  /* _create() */

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

GRAMOD* gm_create (ATTSET *attset, int type)
{                               /* --- create a graphical model */
  int    i;                     /* loop variable */
  GRAMOD *gm;                   /* created graphical model */
  GMATT  *att;                  /* to traverse the attributes */

  assert(attset);               /* check the function argument */
  gm = _create(attset, type);   /* create a graphical model */
  if (!gm) return NULL;         /* and traverse the attributes */
  for (att = gm->atts +(i = gm->attcnt); --i >= 0; ) {
    if (att_type((--att)->att) != AT_SYM)
      continue;                 /* skip non-symbolic attributes */
    att->ptree = pt_create(att->att, type);
    if (!att->ptree) { gm_delete(gm, 0); return NULL; }
  }                             /* create prob./poss. trees */
  return gm;                    /* return created graphical model */
}  /* gm_create() */

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

void gm_delete (GRAMOD *gm, int delas)
{                               /* --- delete a graphical model */
  int    i;                     /* loop variable */
  GMATT *att;                   /* to traverse the attributes */

  assert(gm);                   /* check the function argument */
  for (att = gm->atts +(i = gm->attcnt); --i >= 0; ) {
    if ((--att)->ptree) pt_delete(att->ptree, 0);
    if (att->cdds) free(att->cdds);
    if (att->deps) free(att->deps);
  }                             /* delete prob./poss tree and vectors */
  if (delas) as_delete(gm->attset);
  free(gm->order);              /* delete attribute set, top. order, */
  free(gm);                     /* and graphical model body */
}  /* gm_delete() */

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

double gm_setnorm (GRAMOD *gm, double tplcnt)
{                               /* --- set number of tuples for norm. */
  int   i;                      /* loop variable */
  GMATT *att;                   /* to traverse the attributes */

  assert(gm && (tplcnt >= 0));  /* check the function arguments */
  for (att = gm->atts +(i = gm->attcnt); --i >= 0; )
    if ((--att)->ptree) pt_setnorm(att->ptree, (float)tplcnt);
  return gm->tplcnt = tplcnt;   /* update the prob./poss. trees */
}  /* gm_setnorm() */           /* and note the number of tuples */

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

float gm_setlc (GRAMOD *gm, float lcorr)
{                               /* --- set Laplace correction */
  int   i;                      /* loop variable */
  GMATT *att;                   /* to traverse the attributes */

  assert(gm && (lcorr >= 0));   /* check the function arguments */
  for (att = gm->atts +(i = gm->attcnt); --i >= 0; )
    if ((--att)->ptree) pt_setlc(att->ptree, lcorr);
  return gm->lcorr = lcorr;     /* update the prob./poss. trees */
}  /* gm_setlc() */             /* and note the Laplace correction */

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

int gm_consum (GRAMOD *gm)
{                               /* --- get the number of conitions */
  int   i, n = 0;               /* loop variable, counter */
  GMATT *att;                   /* to traverse the attributes */

  assert(gm);                   /* check the function argument */
  for (att = gm->atts +(i = gm->attcnt); --i >= 0; )
    if ((--att)->ptree) n += pt_concnt(att->ptree);
  return n;                     /* sum the number of conditions */
}  /* gm_consum() */            /* of the prob./poss. trees */

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

int gm_parsum (GRAMOD *gm)
{                               /* --- get the number of parameters */
  int   i, n = 0;               /* loop variable, counter */
  GMATT *att;                   /* to traverse the attributes */

  assert(gm);                   /* check the function argument */
  for (att = gm->atts +(i = gm->attcnt); --i >= 0; )
    if ((--att)->ptree) n += pt_parcnt(att->ptree);
  return n;                     /* sum the number of parameters */
}  /* gm_parsum() */            /* of the prob./poss. trees */

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

int gm_cddadd (GRAMOD *gm, int attid, int cddid)
{                               /* --- add a condition candidate */
  GMATT *att;                   /* to access the attribute */
  int   vsz;                    /* new candidate vector size */
  int   *vec;                   /* new candidate vector */

  assert(gm && (cddid != attid) /* check the function arguments */
      && (attid >= 0) && (attid < gm->attcnt)
      && (cddid >= 0) && (cddid < gm->attcnt));
  att = gm->atts +attid;        /* get the attribute */
  #ifndef NDEBUG                /* if to compile a debug version */
  for (vsz = att->cddcnt; --vsz >= 0; )
    assert(att->cdds[vsz] != cddid);
  #endif                        /* check for a duplicate candidate */
  if (att->cddcnt >= att->cddvsz) {
    vsz = att->cddvsz           /* if the candidate vector is full */
        + ((att->cddvsz > BLKSIZE) ? (att->cddvsz >> 1) : BLKSIZE);
    vec = (int*)realloc(att->cdds, vsz *sizeof(int));
    if (!vec) return -1;        /* allocate a new candidate vector */
    att->cdds = vec; att->cddvsz = vsz;
  }                             /* set the new vector and its size */
  att->cdds[att->cddcnt] = cddid;  /* add the new candidate */
  return att->cddcnt++;            /* and return its index */
}  /* gm_cddadd() */

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

void gm_cddrem (GRAMOD *gm, int attid, int index)
{                               /* --- remove a condition candidate */
  GMATT *att;                   /* to access the attribute */
  int   *p;                     /* to traverse the candidate vector */

  assert(gm                     /* check the function arguments */
      && (attid >= 0) && (attid < gm->attcnt));
  att = gm->atts +attid;        /* get the attribute */
  assert(index < att->cddcnt);  /* check the function arguments */
  if (index < 0)                /* if to remove all candidates, */
    att->cddcnt = 0;            /* clear the candidate counter */
  else {                        /* if to remove one candidate, */
    p = att->cdds +index;       /* traverse the candidate vector */
    for (index = --att->cddcnt -index; --index >= 0; ) {
      p[0] = p[1]; p++; }       /* shift left/up all candidates */
  }                             /* following the one to remove */
}  /* gm_cddrem() */

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

int gm_conadd (GRAMOD *gm, int attid, int conid)
{                               /* --- add a condition */