gramod1.c

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

  int   cnt;                    /* number of conditions */
  GMATT *att;                   /* to access the attribute */
  GMATT *con;                   /* to access the condition */
  int   vsz;                    /* new dependent atts. vector size */
  int   *vec;                   /* new dependent atts. vector */

  assert(gm && (conid != attid) /* check the function arguments */
      && (attid >= 0) && (attid < gm->attcnt)
      && (conid >= 0) && (conid < gm->attcnt)
      && (att_type(gm->atts[attid].att) == AT_SYM)
      && (att_type(gm->atts[conid].att) == AT_SYM));
  att = gm->atts +attid;        /* get the attribute */
  con = gm->atts +conid;        /* and the condition */
  cnt = pt_concnt(att->ptree);  /* get number of existing conditions */
  assert(cnt < PT_MAXCON);      /* and check it against the maximum */
  #ifndef NDEBUG                /* if to compile a debug version, */
  for (vsz = cnt; --vsz >= 0; ) /* check for a duplicate condition */
    assert(pt_conid(att->ptree, vsz) != conid);
  #endif
  if (con->depcnt >= con->depvsz) {
    vsz = con->depvsz           /* if dependent atts. vector is full */
        + ((con->depvsz > BLKSIZE) ? (con->depvsz >> 1) : BLKSIZE);
    vec = (int*)realloc(con->deps, vsz *sizeof(int));
    if (!vec) return -1;        /* (re)allocate a dep. atts. vector */
    con->deps = vec; con->depvsz = vsz;
  }                             /* set the new vector and its size */
  if (pt_conadd(att->ptree, cnt, gm->atts[conid].att) < 0)
    return -1;                  /* add the condition to the tree */
  con->deps[con->depcnt++] = attid; /* add a dependent attribute */
  if (con->pos > att->pos)      /* check positions in top. order and */
    gm->order[0] = -1;          /* invalidate the order if necessary */
  gm->concnt++;                 /* increment the condition counter */
  return cnt;                   /* return the index of the condition */
}  /* gm_conadd() */

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

void gm_conrem (GRAMOD *gm, int attid, int index)
{                               /* --- remove a condition */
  int   i, k, n;                /* loop variables, buffer */
  GMATT *att;                   /* to access the attribute/condition */
  PTREE *pt;                    /* probability/possibility tree */

  assert(gm && (attid < gm->attcnt)  /* check the function arguments */
      && ((attid < 0) || (att_type(gm->atts[attid].att) == AT_SYM)));
  if (attid < 0) {              /* if to remove all conditions */
    for (att = gm->atts +(i = gm->attcnt); --i >= 0; ) {
      if (!(--att)->ptree) continue;
      pt_conrem(att->ptree, -1, 0);
      att->depcnt = 0;          /* traverse the attributes */
    }                           /* and remove all conditions */
    gm->concnt = 0; return;     /* reinit. the condition counter */
  }                             /* and abort the function */
  pt = gm->atts[attid].ptree;   /* get the prob./poss. tree and */
  assert(index < pt_concnt(pt));/* check the condition index */
  if (index < 0) { n = 0;     i = pt_concnt(pt); }
  else           { n = index; i = index +1; }
  gm->concnt -= i-n;            /* decrement the condition counter */
  while (--i >= n) {            /* traverse the conditions to remove */
    att = gm->atts +pt_conid(pt, i);
    for (k = att->depcnt; --k >= 0; ) {
      if (att->deps[k] == attid) {
        att->deps[k] = att->deps[--att->depcnt]; break; }
    }                           /* traverse dependent atts. vector */
  }                             /* and remove the attribute from it */
  pt_conrem(pt, index, 0);      /* remove condition(s) from the tree */
  /* A topological order of the attributes (gm->order), which may */
  /* exist, remains valid, because the new set of conditions is */
  /* weaker than the old (there are fewer edges in the graph). */
}  /* gm_conrem() */

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

void gm_clear (GRAMOD *gm, int delnodes)
{                               /* --- clear distributions */
  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_clear(att->ptree, delnodes);
}  /* gm_clear() */             /* clear the prob./poss. tree(s) */

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

int gm_aggr (GRAMOD *gm, int distuv)
{                               /* --- aggregate instantiation weight */
  int   i;                      /* loop variable */
  GMATT *att;                   /* to traverse the attributes */
  float wgt;                    /* weight of the instantiation */

  assert(gm);                   /* check the function arguments */
  wgt = as_getwgt(gm->attset);  /* get the instantiation weight */
  for (att = gm->atts +(i = gm->attcnt); --i >= 0; )
    if ((--att)->ptree && (pt_aggr(att->ptree, wgt, distuv) < 0))
      return -1;                /* aggregate the instantiation weight */
  return 0;                     /* return 'ok' */
}  /* gm_aggr() */

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

static int _check (GMATT *atts, int attid, int conid)
{                               /* --- recursively check for a loop */
  int i;                        /* loop variable */
  int *dep;                     /* to traverse the dep. att. ids. */

  assert(atts                   /* check the function arguments */
     && (attid >= 0) && (conid >= 0));
  if (atts[attid].pos > atts[conid].pos)
    return 0;                   /* check positions in top. order */
  for (dep = atts[attid].deps +(i = atts[attid].depcnt); --i >= 0; )
    if ((*--dep == conid) || (_check(atts, *dep, conid) != 0))
      return -1;                /* if the condition is among the */
  return 0;                     /* descendent attributes, abort, */
}  /* _check() */               /* otherwise return `ok' */

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

int gm_check (GRAMOD *gm, int attid, int conid)
{                               /* --- check graphical model */
  assert(gm);                   /* check the function argument */
  if ((gm->order[0] < 0)        /* if no topological order exists */
  &&  (_order(gm) != 0))        /* and it cannot be created either, */
    return -1;                  /* abort the function with failure */
  if (attid < 0) return 0;      /* if no edge to test is given, abort */
  assert((attid < gm->attcnt)   /* check the function arguments */
      && (conid < gm->attcnt) && (conid >= 0));
  if (attid == conid)           /* if the attributes are identical, */
    return -1;                  /* there is a direct loop */
  return _check(gm->atts, attid, conid);
}  /* gm_check() */             /* recursively check for a loop */

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

int gm_rand (GRAMOD *gm, double randfn(void))
{                               /* --- compute random instances */
  int   i;                      /* loop variable */
  int   *o;                     /* to traverse the topological order */
  GMATT *att;                   /* to traverse the attributes */

  assert(gm && randfn);         /* check the function arguments */
  if ((gm->order[0] < 0)        /* if no topological order exists */
  &&  (_order(gm) != 0))        /* and it cannot be created either, */
    return -1;                  /* abort the function */
  o = gm->order;                /* traverse in topological order */
  for (i = gm->attcnt; --i >= 0; ) {
    att = gm->atts +*o++;       /* get the next attribute */
    switch (att_type(att->att)){/* and evaluate its type */
      case AT_FLT: att_inst(att->att)->f = 0.0F;  break;
      case AT_INT: att_inst(att->att)->i = 0;     break;
      default    : att_inst(att->att)->i =
                     pt_rand(att->ptree, randfn); break;
    }                           /* clear numeric attributes and */
  }                             /* randomly instantiate symbolic ones */
  return 0;                     /* return 'ok' */
}  /* gm_rand() */

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

double gm_exec (GRAMOD *gm)
{                               /* --- determine prob./deg. of poss. */
  int    i;                     /* loop variable */
  GMATT  *att;                  /* to traverse the attributes */
  double p = 1, t;              /* probability/possibility, buffer */

  assert(gm);                   /* check the function argument */
  for (att = gm->atts +(i = gm->attcnt); --i >= 0; ) {
    if (!(--att)->ptree) continue;
    t = pt_exec(att->ptree);    /* traverse the symbolic attributes */
    if (t <= 0) return 0;       /* and compute the prob./poss. degree */
    if (gm->type == GM_PROB) p *= t;
    else if (t < p)          p  = t;
  }                             /* aggregate prob./poss. */
  return p;                     /* and return the result */
}  /* gm_exec() */

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

int gm_execx (GRAMOD *gm, double res[])
{                               /* --- determine prob./deg. of poss. */
  int    i, k, n;               /* loop variables, counter */
  INST   *inst;                 /* instance of attribute */
  GMATT  *att;                  /* to traverse the attributes */
  int    *o;                    /* to traverse attribute identifiers */
  int    *unks, *u;             /* unknown attribute ids. vector */
  int    cnt;                   /* number of unknown attributes */
  double p;                     /* probability/possibility */

  assert(gm);                   /* check the function arguments */
  if ((gm->order[0] < 0)        /* if no topological order exists */
  &&  (_order(gm) != 0))        /* and it cannot be created either, */
    return -1;                  /* abort the function */

  /* --- collect unknown attributes --- */
  unks = u = gm->buf;           /* get the auxiliary vector */
  att  = gm->atts;              /* and traverse the attributes */
  for (i = 0; i < gm->attcnt; i++, att++) {
    if (!att->ptree) {          /* if attribute is not symbolic, */
      att->prob = 1; continue;} /* set default prob./poss. degree */
    att->prob = -1;             /* invalidate prob./poss. degree */
    inst = att_inst(att->att);  /* get the attribute instance and */
    if (inst->i == UV_SYM) {    /* if the attribute value is unknown, */
      *u++ = i;                 /* note the attribute identifier */
      inst->i = att_valcnt(att->att) -1;
    }                           /* set the last value of the domain */
  }                             /* (first instantiation to try) */
  cnt = (int)(u -unks);         /* compute number of unknown atts. */

  /* --- aggregate probabilities/possibility degrees --- */
  res[2] = res[0] = n = 0;      /* init. the aggregates to compute */
  res[1] = DBL_MAX;             /* and the instantiation counter */
  do {                          /* value combination loop */
    p = 1;                      /* traverse attributes in top. order */
    for (o = gm->order, i = gm->attcnt; --i >= 0; ) {
      att = gm->atts +*o++;     /* get the condition data */
      if (att->prob < 0)        /* if the probability is invalid, */
        att->prob = pt_exec(att->ptree);        /* (re)compute it */
      if (att->prob <= 0) {    p  = 0; break; }
      if (gm->type == GM_PROB) p *= att->prob;
      else if (att->prob < p)  p  = att->prob;
    }                           /* compute value of instantiation */
    if (p < res[1]) res[1] = p; /* update minimum */
    if (p > res[2]) res[2] = p; /* and maximum */
    res[0] += p; n++;           /* and sum and count tuples */
    for (u = unks +(i = cnt); --i >= 0; ) {
      att = gm->atts +*--u;     /* invalidate prob./poss. of attrib. */
      att->prob = -1;           /* and traverse dependent attributes */
      for (o = att->deps +(k = att->depcnt); --k >= 0; )
        gm->atts[*--o].prob = -1;   /* invalidate prob./poss. degree */
      inst = att_inst(att->att);    /* get the attribute instance */
      if (--inst->i >= 0) break;
      inst->i = att_valcnt(att->att) -1;
    }                           /* compute next value combination */
  } while (i >= 0);             /* while there is another combination */
  if (n      >  0) res[0] /= n; /* determine average value and */
  if (res[2] <= 0) res[1]  = 0; /* correct minimum if maximum is zero */

  /* --- clean up --- */
  for (u = unks +(i = cnt); --i >= 0; )
    att_inst(gm->atts[*--u].att)->i = UV_SYM;
  return 0;                     /* reset attributes to unknown values */
}  /* gm_execx() */             /* and return 'ok' */

/*----------------------------------------------------------------------
  Description Functions
----------------------------------------------------------------------*/

int gm_desc (GRAMOD *gm, FILE *file, int mode, int maxlen)
{                               /* --- describe a graphical model */
  int   i, k;                   /* loop variables, flag */
  GMATT *att;                   /* to traverse the attributes */

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

  /* --- print header (as a comment) --- */
  if (mode & GM_TITLE) {        /* if the title flag is set */
    i = k = (maxlen > 0) ? maxlen -2 : 70;
    fputs("/*", file); while (--i >= 0) putc('-', file);