gramod2.c

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

    c[(*  p)->y].cnt++;         /* determine for each node */
  }                             /* the number of incident edges */
  while (n > 0) {               /* while there are undirected edges */
    for (p = q = csel->seles; --n >= 0; q++) {
      x = (*q)->x;              /* traverse the edges and */
      y = (*q)->y;              /* get the connected nodes */
      if      (c[x].cnt <= 1) { /* if edge can be dir. to 1st node */
        if (gm_conadd(csel->gm, x, y) < 0) return -1;
        csel->etab[x][x].eval = (*q)->eval; }
      else if (c[y].cnt <= 1) { /* if edge can be dir. to 2nd node */
        if (gm_conadd(csel->gm, y, x) < 0) return -1;
        csel->etab[y][y].eval = (*q)->eval; }
      else {                    /* if the edge cannot be directed, */
        *p++ = *q; continue; }  /* keep it for the next traversal */
      c[x].cnt--;               /* remove the edge from the counters */
      c[y].cnt--;               /* so that the counters always refer */
    }                           /* to undirected edges only */
    n = (int)(p -csel->seles);  /* get the number of remaining edges */
  }
  return 0;                     /* return 'ok' */
}  /* _owst() */

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

static int _extst (CSEL *csel)
{                               /* --- extension of a spanning tree */
  int  i, k, n;                 /* loop variables, number of edges */
  int  x, y;                    /* node identifiers */
  EDGE *e, **p, **q;            /* to traverse the edges */

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

  /* --- initialize --- */
  if (_owst(csel) != 0)         /* build an optimum weight */
    return -1;                  /* spanning tree first */

  /* --- collect possible edges --- */
  p = csel->seles;              /* traverse the attributes */
  for (i = csel->attcnt; --i >= 0; ) {
    n = gm_depcnt(csel->gm, i); /* get the number of children */
    if (n <= 0) continue;       /* skip childless nodes (leaves) */
    if (gm_concnt(csel->gm, i) > 0) {  /* if there is a parent */
      y = gm_conid(csel->gm, i, 0);    /* (this not the root) */
      for (k = n; --k >= 0; ) { /* traverse the children */
        x = gm_depid(csel->gm, i, k);
        e = csel->etab[x] +y;   /* collect edges from the parent */
        if (e->mark > 0) { e->mark |= 4; *p++ = e; }
      }                         /* these edges have a fixed dir. */
    }                           /* (from the parent to the child) */
    while (--n > 0) {           /* traverse the children */
      y = gm_depid(csel->gm, i, n);
      for (k = n; --k >= 0; ) { /* traverse the preceding children */
        x = gm_depid(csel->gm, i, k);
        e = csel->etab[x] +y;   /* collect edges between children */
        if (e->mark > 0) { e->mark &= ~4; *p++ = e; }
      }                         /* these edges do not have a fixed */
    }                           /* direction, but can be oriented */
  }                             /* either way */
  n = (int)(p -csel->seles);    /* get the number of selected edges */

  /* --- build tree extension and direct edges --- */
  if (_eval(csel, n, 1) != 0) return -1;
  n = _tree(csel, n);           /* evaluate the selectable edges */
  if (n < 0) return -1;         /* and build a spanning tree */
  for (p = q = csel->seles; --n >= 0; q++) {
    if ((*q)->mark & 4) gm_conadd(csel->gm, (*q)->x, (*q)->y);
    else *p++ = *q;             /* direct edges with fixed direction */
  }                             /* (from parent to child) */
  for (n = (int)(p -csel->seles); n > 0; ) {
    k = n;                      /* while there are undirected edges */
    for (p = q = csel->seles; --n >= 0; q++) {
      if      (gm_concnt(csel->gm, (*q)->x) > 1)
        gm_conadd(csel->gm, (*q)->y, (*q)->x);
      else if (gm_concnt(csel->gm, (*p)->y) > 1)
        gm_conadd(csel->gm, (*q)->x, (*q)->y);
      else *p++ = *q;           /* an edge can be directed */
    }                           /* if one node has two parents */
    n = (int)(p -csel->seles);  /* get the number of remaining edges */
    if (k <= n) { n--; p--;     /* if no edge has been directed */
      gm_conadd(csel->gm, (*p)->x, (*p)->y); }
  }                             /* direct an arbitrary edge */
  return 0;                     /* return 'ok' */
}  /* _extst() */

/*----------------------------------------------------------------------
  Greedy Condition Selection
----------------------------------------------------------------------*/

static int _topord (CSEL *csel)
{                               /* --- selection on topological order */
  int   i, k, n;                /* loop variables, number of edges */
  EDGE  *e, **p, *best;         /* to traverse the edges, best edge */
  int   y, t;                   /* node identifier, top. order flag */

  assert(csel);                 /* check the function argument */
  for (i = csel->attcnt; --i >= 0; )
    csel->seles[i] = csel->etab[i] +i;
  if (_eval(csel, csel->attcnt, 0) != 0)
    return -1;                  /* compute the initial evaluation */

  /* --- mark possible edges --- */
  t = (csel->search == GM_TOPORD);
  for (i = csel->attcnt; --i >= 0; ) {
    for (k = gm_cddcnt(csel->gm, i); --k >= 0; ) {
      y = gm_cddid(csel->gm, i, k);
      if (!t || (y < i)) csel->etab[i][y].mark = 1;
    }                           /* traverse the candidate attributes */
    for (k = gm_concnt(csel->gm, i); --k >= 0; ) {
      y = gm_conid(csel->gm, i, k);
      if (!t || (y < i)) csel->etab[i][y].mark = 0;
    }                           /* traverse the existing conditions */
  }                             /* and mark the selectable edges */

  /* --- select conditions --- */
  while (1) {                   /* condition selection loop */
    p = csel->seles;            /* traverse the edge table */
    for (i = csel->attcnt; --i >= 0; ) {
      e = csel->etab[i];        /* get the next table column */
      if (e[i].mark < 0)        /* if an attribute is marked, */
        continue;               /* no conditions can be added */
      if (gm_concnt(csel->gm, i) >= csel->maxcon) {
        e[i].mark = -1;         /* if the maximum number is reached, */
        continue;               /* no more conditions can be added, */
      }                         /* so mark this attribute */
      for (n = 0, e += k = (t ? i : csel->attcnt); --k >= 0; )
        if ((--e)->mark > 0) { *p++ = e; n++; }
      if (!n) e[i].mark = -1;   /* collect the selectable edges and */
    }                           /* mark attributes without edges */
    n = (int)(p -csel->seles);  /* compute the number of edges */
    if (n <= 0) return 0;       /* if there are no edges left, abort */
    if (_eval(csel, n, 0) != 0) /* evaluate the */
      return -1;                /* selected edges */
    for (i = csel->attcnt; --i >= 0; ) {
      e = csel->etab[i];        /* get the next table column */
      if (e[i].mark < 0)        /* for marked attributes */
        continue;               /* no conditions were tested */
      best = e +i;              /* traverse the selectable conditions */
      for (e += k = (t ? i : csel->attcnt); --k >= 0; ) {
        if (((--e)->mark > 0) && (e->eval > best->eval))
          best = e;             /* traverse the edges and */
      }                         /* find the best condition */
      if ((best->y == i)
      ||  (best->eval -e[i].eval < csel->minimp)) {
        e[i].mark = -1;         /* if adding the condition does not */
        continue;               /* lead to a sufficient improvement, */
      }                         /* stop selecting conditions */
      if (gm_conadd(csel->gm, i, best->y) < 0)
        return -1;              /* add the selected condition */
      best->mark = 0;           /* and invalidate (unmark) it */
      e[i].eval  = best->eval;  /* note the new base evaluation */
    }                           /* (relative to which the next */
  }                             /* improvement will be measured) */
  return 0;                     /* return 'ok' */
}  /* _topord() */

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

static int _noloop (CSEL *csel)
{                               /* --- selection avoiding loops */
  int    i, k, n;               /* loop variables, number of edges */
  EDGE   *e, **p, *best = NULL; /* to traverse the edges, best edge */
  double base, imp;             /* evaluation and improvement */

  assert(csel);                 /* check the function argument */
  for (i = csel->attcnt; --i >= 0; )
    csel->seles[i] = csel->etab[i] +i;
  if (_eval(csel, csel->attcnt, 0) != 0)
    return -1;                  /* compute the initial evaluation */

  /* --- mark possible edges --- */
  for (i = csel->attcnt; --i >= 0; ) {
    for (k = gm_cddcnt(csel->gm, i); --k >= 0; )
      csel->etab[i][gm_cddid(csel->gm, i, k)].mark = 1;
    for (k = gm_concnt(csel->gm, i); --k >= 0; )
      csel->etab[i][gm_conid(csel->gm, i, k)].mark = 0;
  }                             /* mark the selectable edges */

  /* --- select conditions --- */
  while (1) {                   /* condition selection loop */
    p = csel->seles;            /* traverse the edge table */
    for (i = csel->attcnt; --i >= 0; ) {
      e = csel->etab[i];        /* get the next table column */
      if (e[i].mark < 0)        /* if an attribute is marked, */
        continue;               /* no conditions can be added */
      if (gm_concnt(csel->gm, i) >= csel->maxcon) {
        e[i].mark = -1;         /* if the maximum number is reached, */
        continue;               /* no more conditions can be added, */
      }                         /* so mark this attribute */
      for (n = 0, e += k = csel->attcnt; --k >= 0; ) {
        if ((--e)->mark <= 0)   /* traverse the edges/conditions, */
          continue;             /* but skip unmarked edges */
        if (gm_check(csel->gm, i, k) != 0)
          e->mark = 0;          /* remove edges that create a loop */
        else {                  /* and collect the selectable edges */
          if (!best || (i == best->x)) *p++ = e;
          n++;                  /* (collect edges only for the */
        }                       /* child of the previous step) */
      }
      if (!n) e[i].mark = -1;   /* mark attributes for which */
    }                           /* no edges (conditions) are left */
    n = (int)(p -csel->seles);  /* compute the number of edges */
    if (_eval(csel, n, 0) != 0) /* and evaluate the */
      return -1;                /* selected edges */
    imp = -DBL_MAX;             /* traverse the table columns */
    for (i = csel->attcnt; --i >= 0; ) {
      e = csel->etab[i];        /* get the next table column */
      if (e[i].mark < 0)        /* for a marked attribute */
        continue;               /* no conditions were tested */
      base = e[i].eval;         /* get the base evaluation */
      for (e += k = csel->attcnt; --k >= 0; ) {
        if (((--e)->mark > 0) && (e->eval -base > imp)) {
          imp = e->eval -base; best = e; }
      }                         /* traverse the edges and */
    }                           /* find the best condition */
    if (imp < csel->minimp)     /* if the improvement is too small, */
      return 0;                 /* abort the search */
    if (gm_conadd(csel->gm, best->x, best->y) < 0)
      return -1;                /* add the selected condition */ 
    best->mark = 0;             /* and invalidate (unmark) it */
    e = csel->etab[best->x] +best->x;
    e->eval = best->eval;       /* note the new base evaluation */
  }
  return 0;                     /* return 'ok' */
}  /* _noloop() */

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

double gm_csel (GRAMOD *gm, TABLE *table, int search, int measure,
                double *params, double minimp, int lwise, double mrgimp,
                int maxcon, int maxtest, int verbose)
{                               /* --- induce by selecting conditions */
  int    i, k, n;               /* loop variables */
  double tplcnt;                /* number of tuples (weight) */
  CSEL   csel;                  /* structure of induction variables */
  EDGE   *e;                    /* to traverse the edge table */

  assert(gm && table);          /* check the function arguments */
  if ((search < GM_NONE) || (search >= GM_UNKNOWN))
    return GM_ERROR;            /* check the method identifier */
  if ((search == GM_OWST) || (search == GM_EXTST))
    lwise = -1;                 /* no merging for tree search modes */
  tplcnt = tab_getwgt(table, 0, INT_MAX);
  if ((gm->type & GM_POSS)      /* for poss. graphical models */
  &&  (tab_opc(table, TAB_COND) != 0))
    return GM_ERROR;            /* compute one point coverages */
  gm_clear(gm, (search > GM_NONE) ? 1 : 0);
  if ((gm_estim(gm, table, 0) != 0)
  ||  (gm_eval(gm, measure, params) == GM_ERROR))
    return GM_ERROR;            /* estimate parameters and evaluate */
  gm_setnorm(gm, tplcnt);       /* set number of tuples for norm. */
  if ((search  <= GM_NONE)      /* if no search is to be done */
  ||  (measure <= PT_NONE)) {   /* or no measure is given */
    if ((lwise >= 0) && (gm_local(gm, lwise, mrgimp) == GM_ERROR))
      return GM_ERROR;          /* do local structure learning */
    return gm->eval;            /* return the model evaluation */
  }
  csel.gm        = gm;          /* initialize the */
  csel.attset    = gm->attset;  /* induction variables */
  csel.table     = table;
  csel.search    = search;
  csel.measure   = measure;
  csel.params[0] = params[0];
  csel.params[1] = params[1];
  csel.minimp    = (minimp == 0) ? 16*DBL_EPSILON : minimp;
  csel.mrgimp    = mrgimp;
  csel.lwise     = lwise;
  csel.attcnt    = n = gm->attcnt;
  csel.maxcon    = (maxcon >= n) ? n-1 : maxcon;