relx.c

数据挖掘中的一算法 relim算法

          dst->succ  = subls[item].head;
          subls[item].head = dst++;
        }                       /* store the item vector in the elem. */
      }                         /* and insert it into the corr. list */
    }                           /* (collect relevant transactions) */

    /* --- report a frequent item set --- */
    if ((s->supp < re->supp)    /* if the support is too low */
    ||  (d > re->max)) {        /* or the maximal size is reached */
      if (dst > elems) {        /* if transactions were collected */
        for (item = re->cnt; --item > i; ) {
          subls[item].head = NULL;
          subls[item].supp = 0; /* clear all lists that may have */
        }                       /* been filled with transactions */
      }                         /* for the next pass/list */
      dst = NULL; }             /* inhibit transaction copying */
    else {                      /* if the support is high enough, */
      re->items[d-1] = i;       /* store the last item of the set */
      if (d >= re->min)         /* if the item set is large enough */
        re->isc += re->report(re->items, d, s->supp);
    }                           /* report the found freq. item set */
    src     = s->head;          /* get the transaction list and */
    s->head = NULL;             /* clear the list's head pointer */
    s->supp = 0;                /* and the transaction counter */
    if (++i >= re->cnt) break;  /* if at last transaction list, abort */

    /* -- process transactions containing item i -- */
    while (src) {               /* item elimination loop */
      buf = src;                /* get the next list element and */
      src = src->succ;          /* remove it from the trans. list */
      if (!buf->items)          /* if the list element is empty, */
        item = re->cnt;         /* get a special item code, */
      else {                    /* otherwise (if there are items), */
        item = *buf->items++;   /* get and remove the first item */
        if (item & RE_EOT) {    /* if there is only the first item, */
          item &= ~RE_EOT;      /* remove the end of trans. marker */
          buf->items = NULL;    /* and clear the item pointer */
        }                       /* (the transaction is empty now) */
      }
      buf->succ = lists[item].head;
      lists[item].head  = buf;  /* move elem. to corresp. trans. list */
      lists[item].supp += buf->wgt;     /* and count the added trans. */
      if (dst) {                /* if to collect transactions */
        dst->items = buf->items;
        subls[item].supp += dst->wgt = buf->wgt;
        dst->succ  = subls[item].head;
        subls[item].head  = dst++;       /* add the transaction */
      }                         /* in a new list element to the */
    }                           /* corresponding transaction sublist */

    /* --- recursively process collected transactions --- */
    if (dst && re_vecs(subls, d, i, re) < 0)
      return -1;                /* if transactions were collected, */
  }                             /* process transactions recursively */
  lists[re->cnt-1].head = NULL; /* clear the last transaction list */
  lists[re->cnt-1].supp = 0;    /* (which is not diassembled above) */
  return 0;                     /* return 'ok' */
}  /* re_vecs() */

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

static int vecs (TASET *taset, float supp, int min, int max,
                 float minwgt, float *pens, REPFN report)
{                               /* --- run recursive elimination */
  int    i, k, n;               /* loop variables, counters */
  TALIST *lists;                /* vector of transaction lists */
  TALE   *elems, *e;            /* vector of transaction list elems. */
  int    *t;                    /* to traverse the transactions */
  RELIM  *re;                   /* structure for recursion data */

  if (supp <= 0)                /* check and adapt minimum support */
    supp = (minwgt > 0) ? minwgt : 1e-12;
  i  = is_cnt(tas_itemset(taset));
  n  = tas_cnt(taset);          /* get the number of items */
  if (n < supp) return 0;       /* and the number of transactions */
  re = (RELIM*)malloc(sizeof(RELIM) +(n-1) *sizeof(int));
  if (!re) return -1;           /* create recursion data structure */
  re->lists = (TALIST**)calloc(i, sizeof(TALIST*));
  if (!re->lists) {                  free(re); return -1; }
  re->elems = (TALE**)  calloc(i, sizeof(TALE*));
  if (!re->elems) { free(re->lists); free(re); return -1; }
  re->cnt    = i;               /* create buffers for list vectors */
  re->min    = min;             /* and trans. list element vectors */
  re->max    = max;             /* needed in the recursion to avoid */
  re->supp   = supp;            /* multiple allocation and deletion, */
  re->minwgt = minwgt;          /* then initialize the variables */
  re->pens   = pens;            /* with the given parameters */
  re->trcnt  = n;
  re->report = report;
  re->isc    = 0;
  lists = (TALIST*)calloc(i+1, sizeof(TALIST));
  if (!lists) { free(re);              return -1; }
  elems = (TALE*)  malloc(n *sizeof(TALE));
  if (!elems) { free(lists); free(re); return -1; }
  e = elems;                    /* create initial transaction lists */
  while (--n >= 0) {            /* traverse the transactions */
    k = tas_tsize(taset, n);    /* get the transaction size */
    if (k <= 0) {               /* if the transactions is empty, */
      t = NULL;                 /* clear the transaction and */
      i = re->cnt; }            /* get a special item code */
    else {                      /* if there are items */
      t = tas_tract(taset, n);  /* get the transaction (item vector) */
      i = *t++;                 /* and from it the first item */
      if (--k <= 0) t = NULL;   /* if there is only one item, */
      else t[k-1] |= RE_EOT;    /* clear the transaction, otherwise */
    }                           /* mark the end of the transaction */
    e->items = t;               /* store the transaction and */
    lists[i].supp += e->wgt = 1;/* init. the transaction weight */
    e->succ = lists[i].head;    /* add the new list element */
    lists[i].head = e++;        /* to the transaction list */
  }                             /* for the leading item */
  if (re_vecs(lists, 0, 0, re) < 0)
    return -1;                  /* call the recursive elimination */
  n = re->isc;                  /* get number of frequent item sets */
  #ifndef NDEBUG                /* in debug version clean up memory */
  for (i = is_cnt(tas_itemset(taset)); --i >= 0; ) {
    if (re->lists[i]) free(re->lists[i]);
    if (re->elems[i]) free(re->elems[i]);
  }                             /* delete the recursion level vectors */
  free(elems); free(lists);     /* and the base structures */
  free(re->elems); free(re->lists); free(re);
  #endif
  return n;                     /* return num. of frequent item sets */
}  /* vecs() */

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

static void error (int code, ...)
{                               /* --- print an error message */
  #ifndef QUIET                 /* if not quiet version */
  va_list    args;              /* list of variable arguments */
  const char *msg;              /* error message */

  assert(prgname);              /* check the program name */
  if (code < E_UNKNOWN) code = E_UNKNOWN;
  if (code < 0) {               /* if to report an error, */
    msg = errmsgs[-code];       /* get the error message */
    if (!msg) msg = errmsgs[-E_UNKNOWN];
    fprintf(stderr, "\n%s: ", prgname);
    va_start(args, code);       /* get variable arguments */
    vfprintf(stderr, msg, args);/* print error message */
    va_end(args);               /* end argument evaluation */
  }
  #endif
  #ifndef NDEBUG                /* if debug version */
  if (pens)    free(pens);            /* clean up memory */
  if (taset)   tas_delete(taset, 0);  /* and close files */
  if (itemset) is_delete(itemset);
  if (in  && (in  != stdin))  fclose(in);
  if (out && (out != stdout)) fclose(out);
  #endif
  #ifdef STORAGE                /* if storage debugging */
  showmem("at end of program"); /* check memory usage */
  #endif
  exit(code);                   /* abort the program */
}  /* error() */

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

int readpens (ITEMSET *iset, FILE *file)
{                               /* --- read insertion penalties */
  TFSCAN *tfscan;               /* table file scanner */
  int    d, n;                  /* delimiter type, loop variable */
  char   *buf, *s;              /* read buffer, conversion pointer */
  int    item;                  /* item identifier */
  float  pen;                   /* insertion penalty */

  assert(iset && file);         /* check the function arguments */
  tfscan = is_tfscan(iset);     /* get the table file scanner */
  if (tfs_skip(tfscan, file) < 0)
    return E_FREAD;             /* skip leading comments */
  buf = tfs_buf(tfscan);        /* read the first record (one field) */
  d   = tfs_getfld(tfscan, file, NULL, 0);
  if (d <  0)       return E_FREAD;
  if (d >= TFS_FLD) return E_FLDCNT;
  pen = (float)strtod(buf, &s); /* get the default insertion penalty */
  if (*s || (pen < 0) || (pen > 1))
    return E_ILLPEN;            /* check the insertion penalty */
  n  = is_cnt(iset);            /* get the number of items */
  pens = (float*)malloc(n *sizeof(float));
  if (!pens) return E_NOMEM;    /* create an insertion costs vector */
  for (item = n; --item >= 0; ) /* and initialize it with */
    pens[item] = pen;           /* default insertion penalty */
  while (d > TFS_EOF) {         /* read item/indicator pairs */
    if (tfs_skip(tfscan, file) < 0)
      return E_FREAD;           /* skip more comments */
    d = tfs_getfld(tfscan, file, NULL, 0);
    if (d <= TFS_EOF)           /* read the next item */
      return (d < 0) ? E_FREAD : 0;
    if (buf[0] == '\0')         /* check for end of file */
      return E_ITEMEXP;         /* and for a missing item */
    item = is_item(iset, buf);  /* get the item identifier */
    if (d <  TFS_FLD) return E_PENEXP;
    d = tfs_getfld(tfscan, file, NULL, 0);
    if (d <  0)       return E_FREAD;
    if (d >= TFS_FLD) return E_FLDCNT;
    pen = (float)strtod(buf,&s);/* get the insertion penalty */
    if (*s || (pen < 0) || (pen > 1))
      return E_ILLPEN;          /* check the insertion penalty */
    if ((item >= 0) && (item < n))
      pens[item] = pen;         /* store the insertion penalty */
  }
  return 0;                     /* return 'ok' */
}  /* readpens() */

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

int main (int argc, char *argv[])
{                               /* --- main function */
  int     i, k = 0, n;          /* loop variables, counters */
  char    *s;                   /* to traverse the options */
  char    **optarg = NULL;      /* option argument */