relim.c

数据挖掘中的relim算法,很好的代码

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

static int vecs (TASET *taset, int supp, int min, int max, REPFN report)
{                               /* --- run recursive elimination */
  int    i, n;                  /* loop variable, buffer */
  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) supp = 1;      /* check and adapt minimum support */
  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) +(i-1) *sizeof(int));
  if (!re) return -1;           /* create recursion data structure */
  re->lists = calloc(i, sizeof(TALIST*));
  if (!re->lists) {                  free(re); return -1; }
  re->elems = 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->report = report;          /* then initialize the variables */
  re->isc    = 0;               /* with the given parameters */
  lists = (TALIST*)calloc(i, 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 */
    i = tas_tsize(taset, n);    /* get the transaction size */
    if (i <= 0) continue;       /* and skip empty transactions */
    t = tas_tract(taset, n);    /* get the next transaction and */
    lists[*t].supp++;           /* count it for the leading item */
    if (--i <= 0) { e++; continue; } /* skip one item transactions */
    e->succ = (TALE*)lists[*t].head;
    lists[*t].head = e;         /* add the element to the trans. list */
    e->items = t+1; e++;        /* store the shortened transaction */
    t[i] |= RE_EOT;             /* mark the end of the transaction */
  }                             /* so that no size var. is needed and */
  re->trcnt = (int)(e -elems);  /* note number of transactions */
  if ((re->trcnt >= supp)       /* if there are enough transactions */
  &&  (re_vecs(lists, 0, 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() */

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

static int re_trees (TALIST *lists, int i, int d, int pfx,
                     TTLE *ext, RELIM *re)
{                               /* --- recursive elimination */
  int    j, k, n, x, item;      /* loop variables, buffers */
  TALIST *subls, *p;            /* lists of subset of transactions */
  TTLE   *elems;                /* elements of transaction lists */
  TTLE   *src, *dst, *buf;      /* to traverse the transaction lists */
  TATREE *root, *child;         /* to traverse the children */

  subls = re->lists[d];         /* get the subset lists vector */
  if (!subls) {                 /* if it does not exist yet */
    re->lists[d] = subls = (TALIST*)calloc(re->cnt, sizeof(TALIST));
    if (!subls) return -1;      /* create a new subset lists vector */
  }                             /* and store it in the vector buffer */
  elems = (TTLE*)re->elems[d];  /* get the list elements vector */
  if (!elems) {                 /* if it does not exist yet */
    re->elems[d] = elems = (TTLE*)  malloc(re->trcnt *sizeof(TTLE));
    if (!elems) return -1;      /* create a new list elements vector */
  }                             /* and store it in the vector buffer */
  for (d++; i < re->cnt; i++) { /* traverse the trans. tree lists */
    p = lists +i;               /* get the next trans. tree list */
    if (p->supp <= 0) continue; /* skip empty transaction tree lists */
    dst = NULL; x = 0;          /* default: only eliminate item */
    if (p->supp >= re->supp) {  /* if the support is high enough */
      if (d < re->max)          /* if not already at maximum size, */
        dst = elems;            /* collect subset of transactions */
      re->items[d-1] = i;       /* store the last item of the set */
      if (d >= re->min) {       /* if the item set is large enough */
        x = re->report(re->items, d, pfx, p->supp);
        if (x) { re->isc++; pfx = d-1; }
      }                         /* report the frequent item set and */
    }                           /* update counter and prefix length */
    p->supp = 0;                /* clear the transaction counter */
    src     = p->head;          /* get the transaction tree */
    if (!src) continue;         /* skip empty transaction trees */
    p->head = NULL;             /* clear the list vector element */
    n = 0;                      /* initialize the transaction counter */
    do {                        /* item elimination loop */
      if (src->supp > 0) {      /* if list element is an item vector */
        n += src->supp;         /* sum the number of transactions */
        item = *((int*)src->items);  /* get and remove first item */
        src->items = ((int*)src->items) +1;
        if (item & RE_EOT) {    /* if there is only the first item, */
          item &= ~RE_EOT;      /* get this item and increment the */
          lists[item].supp += src->supp; /* corresponding counters */
          if (dst) { dst++; subls[item].supp += src->supp; }
          src = src->succ; }    /* simply skip the list element */
        else {                  /* if there is more than one item, */
          buf = src;            /* move the list element to the */
          src = src->succ;      /* corresponding transaction list */
          buf->succ = (TTLE*)lists[item].head;
          lists[item].head  = buf;  /* count the transactions */
          lists[item].supp += buf->supp;
          if (dst) {            /* if to collect transactions */
            dst->items = buf->items;
            subls[item].supp += dst->supp = buf->supp;
            dst->succ  = (TTLE*)subls[item].head;
            subls[item].head = dst++;
          }                     /* add a new list element to the */
        } }                     /* corresponding transaction sublist */
      else {                    /* if list element is a subtree */
        buf  = src;             /* get and remove the next element */
        src  = src->succ;       /* and get the subtree root from it, */
        root = (TATREE*)buf->items;    /* then traverse the branches */
        for (j = tat_size(root); --j >= 0; ) {
          child = tat_child(root, j);  /* get the next child and */
          item  = tat_item (root, j);  /* the corresponding item */
          lists[item].supp += k = tat_cnt(child);
          if (dst) { dst++; subls[item].supp += k; }
          n += k;               /* sum the number of transactions */
          k = tat_size(child);  /* get the type of the child */
          if (k == 0) continue; /* skip empty tree branches */
          if (!buf) buf = ext++;/* get another list element */
          if (k <  0) {         /* if only an item vector left, */
            buf->items = tat_items(child);  /* store the item vector */
            buf->supp  = tat_cnt(child); }  /* and its support */
          else {                /* if a transaction subtree left, */
            buf->items = child; /* store the transaction subtree */
            buf->supp  = -1;    /* and set the counter negative as an */
          }                     /* indicator for a transaction tree */
          buf->succ = (TTLE*)lists[item].head;
          lists[item].head = buf;  /* reassign the list element */
          if (dst) {            /* if to collect transaction subset */
            dst->items = buf->items;
            dst->supp  = buf->supp;
            dst->succ  = (TTLE*)subls[item].head;
            subls[item].head = dst++;
          }                     /* get and store a new list element */
          buf = NULL;           /* clear the list element buffer */
        }                       /* to indicate that a new element */
      }                         /* is needed for the next child */
    } while (src);              /* while trans. tree list not empty */
    if (!dst) continue;         /* if no trans. collected, skip rest */
    if (n >= re->supp) {        /* if subset support is big enough */
      if (re_trees(subls, i+1, d, pfx +x, dst, re) < 0)
        return -1; }            /* process transactions recursively */
    else if (dst > elems) {     /* if trans. have been collected */
      for (k = re->cnt; --k >= d; ) {
        subls[k].head = NULL;   /* clear all lists that may have */
        subls[k].supp = 0;      /* been filled with transactions */
      }                         /* to have a clean list vector */
    }                           /* for the next collection run */
  }
  return 0;                     /* return 'ok' */
}  /* re_trees() */

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

static int trees (TATREE *tree, ITEMSET *itemset,
                  int supp, int min, int max, REPFN report)
{                               /* --- run recursive elimination */
  int    i, k, n;               /* loop variables, counters */
  TALIST *lists;                /* vector of transaction lists */
  TTLE   *elems, *p;            /* vector of transaction list elems. */
  TATREE *child;                /* to traverse the tree branches */
  RELIM  *re;                   /* structure for recursion data */

  if (supp <= 0) supp = 1;      /* check and adapt minimum support */
  n  = is_cnt(itemset);         /* get the number of items */
  re = (RELIM*)malloc(sizeof(RELIM) +(n-1) *sizeof(int));
  if (!re) return -1;           /* create recursion data structure */
  re->lists = calloc(n, sizeof(TALIST*));
  if (!re->lists) {                  free(re); return -1; }
  re->elems = calloc(n, sizeof(TTLE*));
  if (!re->elems) { free(re->lists); free(re); return -1; }
  re->cnt    = n;               /* 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->report = report;          /* then initialize the variables */
  re->isc    = 0;               /* with the given parameters */
  lists = (TALIST*)calloc(n, sizeof(TALIST));
  if (!lists) { free(re);              return -1; }
  n = tat_cnt(tatree);          /* get the number of transactions */
  elems = (TTLE*)  malloc(n *sizeof(TTLE));
  if (!elems) { free(lists); free(re); return -1; }
  p = elems; re->trcnt = 0;     /* create initial transaction lists */
  n = tat_size(tatree);         /* get the type of the root node */
  if (n < 0) {                  /* if there is only an item vector */
    i = tat_item(tatree, 0);    /* get the leading item */
    p->supp  = lists[i].supp = re->trcnt = tat_cnt(tatree);
    p->items = tat_items(tatree);
    p->succ  = NULL;            /* store the items and their support */
    lists[i].head = p++;        /* and insert the new list element */
  }                             /* into the corresponding list */
  while (--n >= 0) {            /* otherwise traverse the branches */
    child = tat_child(tatree,n);/* get the next tree branch and */
    i     = tat_item (tatree,n);/* store the number of transactions */
    re->trcnt += lists[i].supp = tat_cnt(child);
    k = tat_size(child);        /* get the type of the child */
    if (k == 0) continue;       /* skip empty tree branches */
    if (k <  0) {               /* if only an item vector left, */
      p->items = tat_items(child);    /* store this item vector */
      p->supp  = tat_cnt(child); }    /* and its support */
    else {                      /* if a transaction subtree left, */
      p->items = child;         /* store the transaction subtree */
      p->supp  = -1;            /* and set the counter negative as an */
    }                           /* indicator for a transaction tree */
    p->succ       = NULL;       /* insert the new list element */
    lists[i].head = p++;        /* into the corresponding list */
  }
  tat_mark(tatree);             /* mark ends of transactions */
  if ((re->trcnt >= supp)       /* if there are enough transactions */
  &&  (re_trees(lists, 0, 0, 0, p, re) < 0))
    return -1;                  /* call the recursive elimination */
  #ifndef NDEBUG                /* in debug version clean up memory */
  for (i = is_cnt(itemset); --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 re->isc;               /* return num. of frequent item sets */
}  /* trees() */

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