gramod1.c

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

    fprintf(file, "\n  graphical model\n");
    while (--k >= 0) putc('-', file); fputs("*/\n", file);
  }                             /* print a title header */
  mode &= ~GM_TITLE;            /* remove the title flag */

  /* --- print distributions --- */
  if (gm->type == GM_PROB)      /* if this is a probabilistic model */
    fprintf(file, "probnet = {\n");
  else                          /* if this is a possibilistic model */
    fprintf(file, "possnet = {\n  total = %g;\n\n", gm->tplcnt);
  att = gm->atts;               /* traverse the attributes */
  for (k = 0, i = gm->attcnt; --i >= 0; att++) {
    if (!att->ptree) continue;  /* skip non-symbolic attributes */
    if (k++ > 0)                /* if this is not the first tree */
      fputc('\n', file);        /* that gets printed, skip a line */
    if (pt_desc(att->ptree, file, mode | PT_INDENT, maxlen) != 0)
      return -1;                /* print the prob./poss. tree */
  }
  fputs("};\n", file);          /* terminate the graphical model */

  /* --- print additional information (as a comment) --- */
  if (mode & GM_INFO) {         /* if the add. info. flag is set */
    i = k = (maxlen > 0) ? maxlen -2 : 70;
    fputs("\n/*", file); while (--i >= 0) putc('-', file);
    fprintf(file, "\n  number of attributes: %d", gm->attcnt);
    fprintf(file, "\n  number of conditions: %d", gm->concnt);
    if (gm->tplcnt > 0)
      fprintf(file, "\n  number of tuples    : %g", gm->tplcnt);
    fprintf(file, "\n  evaluation result   : %g\n", gm->eval);
    while (--k >= 0) putc('-', file); fputs("*/\n", file);
  }                             /* print add. model information */
  return (ferror(file)) ? -1 : 0;
}  /* gm_desc() */              /* return the writing result */

/*----------------------------------------------------------------------
  Parse Functions
----------------------------------------------------------------------*/
#ifdef GM_PARSE

static int _clists (GRAMOD *gm, SCAN *scan)
{                               /* --- read candidate lists */
  int  i, k, n;                 /* attribute identifier, counter */
  int  cdd1, cdd2;              /* candidate identifiers */
  int  t;                       /* buffer for a token */
  const char *s;                /* to access the token value */

  while ((sc_token(scan) == T_ID)  /* read the candidate lists */
  &&     (strcmp(sc_value(scan), "cand") == 0)) {
    GET_TOK();                  /* consume 'cand' */
    GET_CHR('(');               /* consume '(' */
    t = sc_token(scan);         /* check for an attribute name */
    if ((t != T_ID) && (t != T_NUM)) ERROR(E_ATTEXP);
    i = as_attid(gm->attset, sc_value(scan));
    if (i < 0)                       ERROR(E_UNKATT);
    if (gm->atts[i].pos)             ERROR(E_DUPCDL);
    gm->atts[i].pos = -1;       /* mark the attribute as read */
    GET_TOK();                  /* and consume the attribute name */
    GET_CHR(')');               /* consume ')' */
    GET_CHR('=');               /* consume '=' */
    GET_CHR('{');               /* consume '{' */
    k = 0;                      /* initialize the read counter */
    while (sc_token(scan) != '}') {     /* attribute read loop */
      if (++k > 1) {            /* if this is not the first att., */
        GET_CHR(','); }         /* consume ',' (separator) */
      t = sc_token(scan);       /* check for an attribute name */
      if ((t != T_ID) && (t != T_NUM)) ERROR(E_ATTEXP);
      cdd1 = as_attid(gm->attset, sc_value(scan));
      if (cdd1 < 0)                    ERROR(E_UNKATT);
      GET_TOK();                /* consume the first candidate */
      t = sc_token(scan);       /* check for a range of atts. */
      s = sc_value(scan);       /* (that is: "att1 - att2") */
      if ((t != T_ID)           /* if no range is given */
      ||  (s[0] != '-') || (s[1] != '\0'))
        cdd2 = cdd1;            /* form a one element range */
      else {                    /* if a range is given */
        GET_TOK();              /* consume '-' */
        t = sc_token(scan);     /* check for an attribute name */
        if ((t != T_ID) && (t != T_NUM)) ERROR(E_ATTEXP);
        cdd2 = as_attid(gm->attset, s);
        if (cdd2 < 0)                    ERROR(E_UNKATT);
        GET_TOK();              /* consume the second candidate */
        if (cdd1 > cdd2)                 ERROR(E_RANGE);
      }                         /* check the candidate range */
      for ( ; cdd1 <= cdd2; cdd1++) {
        if (cdd1 == i)          /* traverse condition candidates, */
          continue;             /* but ignore attribute itself */
        n = gm_cddadd(gm, i, cdd1);
        if (n >=  0) continue;  /* add a condition candidate */
        if (n >= -1) ERROR(E_NOMEM);
        XERROR(E_ILLCDD, att_name(as_att(gm->attset, cdd1)));
      }                         /* if an error occurred, abort */
    }
    GET_TOK();                  /* consume '}' */
    GET_CHR(';');               /* consume ';' */
  }  /* while ((sc_token(scan) == T_ID) .. */
  return 0;                     /* return 'ok' */
}  /* _clists() */

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

static int _cldflt (GRAMOD *gm)
{                               /* --- set default candidate lists */
  int   i, k;                   /* loop variables */
  GMATT *att;                   /* to traverse the attributes */
  int   type;                   /* attribute type */

  assert(gm);                   /* check the function argument */
  for (att = gm->atts +(i = gm->attcnt); --i >= 0; ) {
    type = att_type((--att)->att); /* traverse all attributes */
    if ((type == AT_FLT)        /* if an attribute is real */
    ||  (type == AT_INT)        /* or integer valued */
    ||  (att->pos != 0)) {      /* or if it is marked as read, */
      att->pos = 0; continue; } /* ignore the attribute */
    for (k = 0; k < gm->attcnt; k++)
      if ((k != i) && (gm_cddadd(gm, i, k) < 0))
        return -1;              /* add default candidate list */
  }                             /* (all other attributes) */
  return 0;                     /* return 'ok' */
}  /* _cldflt() */

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

static int _setdeps (GRAMOD *gm)
{                               /* --- set list of dep. attributes */
  int   i, k;                   /* loop variables */
  PTREE *pt;                    /* prob./poss. tree of current att. */
  GMATT *con;                   /* to access the condition attribute */
  int   vsz;                    /* new dependent atts. vector size */
  int   *vec;                   /* new dependent atts. vector */

  assert(gm);                   /* check the function argument */
  for (i = gm->attcnt; --i >= 0; ) {
    pt = gm->atts[i].ptree;     /* traverse the attributes */
    if (!pt) continue;          /* with a condition tree */
    for (k = pt_concnt(pt); --k >= 0; ) {
      con = gm->atts +pt_conid(pt, k);
      if (con->depcnt >= con->depvsz) {
        vsz = con->depvsz       /* if dependent att. vector is full */
            + ((con->depvsz > BLKSIZE) ? (con->depvsz >> 1) : BLKSIZE);
        vec = (int*)realloc(con->deps, vsz *sizeof(int));
        if (!vec) return -1;    /* enlarge the attribute vector */
        con->deps = vec; con->depvsz = vsz;
      }                         /* set the new vector and its size */
      con->deps[con->depcnt++] = i;
    }                           /* the current attribute depends */
  }                             /* on its conditioning attributes */
  return 0;                     /* return `ok' */
}  /* _setdeps() */

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

static int _parse (ATTSET *attset, SCAN *scan, int type, GRAMOD **pgm)
{                               /* --- parse a graphical model */
  int   i, t = -1;              /* loop variable, buffer */
  GMATT *att;                   /* to traverse the attributes */
  PTREE *pt;                    /* buffer for prob./poss. tree */
  int   err = 0;                /* parse error status */

  assert(attset && scan && pgm);/* check the function arguments */

  /* --- read header --- */
  if (sc_token(scan) == T_ID) { /* check for 'probnet' or 'possnet' */
    if      (strcmp(sc_value(scan), "probnet") == 0) t = GM_PROB;
    else if (strcmp(sc_value(scan), "possnet") == 0) t = GM_POSS;
  }                             /* determine the model type */
  if ((t < 0) && (type & GM_DFLT)) {
    *pgm = gm_create(attset, type & GM_POSS);
    if (!*pgm || (_cldflt(*pgm) != 0))
      ERROR(E_NOMEM);  /* if no proper token was found, */
    return 0;                   /* but the default flag is set, */
  }                             /* create a default model */
  if ((t < 0)                   /* if no proper token was found */
  ||  (!(type & GM_AUTO)        /* or not in automatic mode */
  &&   ((type ^ t) & GM_POSS))) /* and wrong token found, abort */
    ERR_STR((type & GM_POSS) ? "possnet" : "probnet");
  if (type & GM_AUTO)           /* set the proper model type */
    type = (type & ~(GM_POSS|GM_AUTO)) | t;
  *pgm = _create(attset, type & GM_POSS);
  if (!*pgm) ERROR(E_NOMEM);    /* create a graphical model */
  GET_TOK();                    /* consume 'probnet' or 'possnet' */
  GET_CHR('=');                 /* consume '=' */
  GET_CHR('{');                 /* consume '{' */

  /* --- read total number of cases --- */
  if ((type & GM_POSS)          /* if this is a possibilistic model */
  &&  (sc_token(scan) == T_ID)  /* check for 'total' or 'tplcnt' */
  &&  ((strcmp(sc_value(scan), "total")  == 0)
  ||   (strcmp(sc_value(scan), "tplcnt") == 0))) {
    GET_TOK();                  /* consume 'total' or 'tplcnt' */
    GET_CHR('=');               /* consume '=' */
    if (sc_token(scan) != T_NUM) ERROR(E_NUMEXP);
    (*pgm)->tplcnt = atof(sc_value(scan));
    if ((*pgm)->tplcnt < 0)      ERROR(E_ILLNUM);
    GET_TOK();                  /* consume the number of cases */
    GET_CHR(';');               /* consume ';' */
  }

  /* --- read candidate lists --- */
  if (type & GM_CDDS) {         /* if the candidates flag is set */
    while (1) {                 /* read loop (with recovery) */
      t = _clists(*pgm, scan);  /* read candidate lists */
      if (t == 0) break;        /* if no error occurred, abort */
      err = -1;                 /* otherwise set the error flag */
      if (t == E_NOMEM) break;  /* always abort on 'out of memory' */
      sc_recover(scan, ';', 0, 0, 0);
    }                           /* otherwise recover from the error */
    if (_cldflt(*pgm) != 0)     /* set default candidates */
      ERROR(E_NOMEM);           /* for all other attributes */
  }                             /* (make everything else a cdd.) */

  /* --- read prob./poss. distributions --- */
  while (sc_token(scan) != '}'){/* as long as there is another tree */
    pt = pt_parse(attset, scan, type);
    if (!pt) { err = -1; sc_recover(scan, ';', 0, 0, 0); continue; }
    att = (*pgm)->atts +pt_attid(pt);
    att->ptree = pt;            /* read a prob./poss. tree and */
    att_setmark(att->att, 1);   /* mark the corresponding attribute */
    if ((type & GM_POSS)        /* for a possibilistic model */
    &&  ((*pgm)->tplcnt >= 0))  /* set number of tuples for norm. */
      pt_setnorm(pt, (float)(*pgm)->tplcnt);
    (*pgm)->concnt += pt_concnt(pt);
  }                             /* sum the conditions */
  if (err) return err;          /* check for a parse error */
  (*pgm)->type = type & GM_POSS;/* set the model type (prob./poss.) */
  for (att = (*pgm)->atts, i = (*pgm)->attcnt; --i >= 0; att++) {
    if (att->ptree              /* traverse the attributes */
    ||  (att_type(att->att) != AT_SYM))
      continue;                 /* skip read and numeric attributes */
    if (type & GM_ALL)          /* if all trees must be present */
      XERROR(E_MISATT, att_name(att->att));
    att->ptree = pt_create(att->att, type);
    if (!att->ptree) ERROR(E_NOMEM);
  }                             /* create missing prob./poss. trees */
  if ((i >= 0) || (_setdeps(*pgm) != 0))
    return -1;                  /* set list of dependent attributes */
  GET_CHR('}');                 /* consume '}' */
  GET_CHR(';');                 /* consume ';' */
  return err;                   /* return the parse error status */
}  /* _parse() */

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

GRAMOD* gm_parse (ATTSET *attset, SCAN *scan, int type)
{                               /* --- parse a graphical model */
  GRAMOD *gm = NULL;            /* created graphical model */

  assert(attset && scan);       /* check the function arguments */
  pa_init(scan);                /* initialize parsing */
  if (_parse(attset, scan, type, &gm) != 0) {
    if (gm) gm_delete(gm, 0);   /* parse graphical model */
    return NULL;                /* if an error occurred, delete */
  }                             /* the graphical model and abort */
  return gm;                    /* return created graphical model */
}  /* gm_parse() */

#endif