fptree.c

数据挖掘中FP增长算法在VC下的实现

  for (k = item; k >= 0; ) {    /* traverse the tree levels */
    for ( ; node; node = node->succ) {
      par  = node->parent;      /* get each node's parent and */
      copy = par->copy;         /* the copy of this parent */
      if (copy) {               /* if a copy already exists */
        /* Note that if k == item, the only case in which */
        /* copy != NULL is when copy == &proj->root.      */
        if (k < item) node->parent = copy;
        copy->cnt += node->cnt; /* sum the number of transactions */
        if (copy->item >= 0) lists[copy->item].cnt += node->cnt;
        continue;               /* update the item frequency */
      }                         /* otherwise create a copy */
      par->copy = copy = ms_alloc(fpt->mem);
      if (!copy) { _cleanup(fpt, proj); return NULL; }
      if (k < item) node->parent = copy;
      copy->item = i = par->item;  /* copy the item of the node and */
      copy->succ = lists[i].node;  /* insert copy into corresp. list */
      lists[i].node = copy;        /* in the projected tree */
      lists[i].cnt += copy->cnt = node->cnt;
      copy->parent  = par->parent;
      copy->copy    = NULL;     /* set the support of the node */
    }                           /* and the parent pointer */
    node = lists[--k].node;     /* go to the created node list */
  }
  _detach(fpt);                 /* detach created tree projection, */
  return proj;                  /* prune last level of orig. tree, */
}  /* _proj_level() */          /* and return created projection */

/*----------------------------------------------------------------------
Of the above two projection methods, method _proj_path generally seems
to yield better results, which is why it is the default.
----------------------------------------------------------------------*/

static void _bonsai (FPTREE *fpt, int supp)
{                               /* --- prune projection to bonsai */
  int     i, k;                 /* loop variables, buffer */
  FPTLIST *lists;               /* to traverse the level lists */
  FPTNODE *node, *anc;          /* to traverse the tree nodes */

  lists = fpt->lists;           /* buffer the tree level vector */
  for (i = fpt->cnt; (--i >= 0) && (lists[i].cnt < supp); )
    _prune(fpt);                /* prune deepest tree levels */
  for (k = 0; k < fpt->cnt; k++)/* traverse the levels downwards */
    if ((lists[k].cnt < supp) && (lists[k].cnt > 0))
      break;                    /* find first infrequent item */
  for (i = k; ++i < fpt->cnt;){ /* traverse the deeper tree levels */
    if (lists[i].cnt < supp)    /* skip tree levels that refer */
      continue;                 /* to an infrequent item */
    for (node = lists[i].node; node; node = node->succ) {
      anc = node->parent;       /* traverse the node list */
      while ((anc->item >= 0) && (lists[anc->item].cnt < supp))
        anc = anc->parent;      /* find frequent ancestor or root */
      if (anc->copy && (anc->copy->item == anc->item))
        anc = anc->copy;        /* if ancestor is merged, get dest. */
      if (!anc->copy            /* if ancestor has not been visited */
      ||  (anc->copy->item != i)){ /* or child is on another level, */
        anc->copy    = node;    /* note the current node as a child */
        node->parent = anc; }   /* and set ancestor as new parent */
      else {                    /* if child on this level is known */
        node->copy = anc->copy; node->copy->cnt += node->cnt; }
    }                           /* merge current node to this child */
  }
  for ( ; k < fpt->cnt; k++) {  /* traverse the deeper tree levels */
    node = lists[k].node;       /* get the node list of the level */
    if (!node) continue;        /* skip empty tree levels */
    if (lists[k].cnt < supp) {  /* if a level is to be deleted, */
      do {                      /* delete the node list: */
        anc  = node;            /* note the current node, */
        node = node->succ;      /* go to the successor node, */
        ms_free(fpt->mem, anc); /* and delete the current node */
      } while (node);           /* while the list is not empty */
      lists[k].cnt = 0; lists[k].node = NULL;
      continue;                 /* clear the counter and the list */
    }
    while (node->succ) {        /* while not at last list element */
      if (!node->succ->copy || (node->succ->copy->item != k)) {
        node->parent->copy = node->copy = NULL;
        node = node->succ;      /* if the successor was not merged, */
        continue;               /* clear possible child pointers */
      }                         /* and keep the successor node */
      anc = node->succ;         /* if the successor was merged, */
      node->succ = anc->succ;   /* note the successor node */
      ms_free(fpt->mem, anc);   /* and remove it from the list, */
    }                           /* then delete the node */
    node->parent->copy = node->copy = NULL;
  }                             /* clear possible child pointers */
}  /* _bonsai() */

/*----------------------------------------------------------------------
For clarity and memory efficiency the above function already removes the
pruned tree levels. This is not really necessary as it would otherwise
be done in the search function, once the level to be removed becomes the
deepest in the pruned tree.
----------------------------------------------------------------------*/

static void _chain (FPTNODE *node, int d, int pfx, int max, FPRS *rs)
{                               /* --- process an item chain */
  int k, n;                     /* output flag, buffer */

  d++;                          /* increment the recursion depth */
  while (1) {                   /* traverse the item list */
    n = (node->cnt < max) ? node->cnt : max;
    k = 0;                      /* get support and clear output flag */
    rs->items[d-1] = node->item;/* store the next item */
    if (d >= rs->min) {         /* if the item set is large enough */
      k = rs->report(rs->items, d, pfx, n, rs->data);
      if (k) { rs->cnt++; pfx = d-1; }
    }                           /* report the frequent item set */
    node = node->parent;        /* remove the processed head item */
    if (node->item < 0) return; /* check for an empty tail list */
    if (d < rs->max) _chain(node, d, pfx +k, n, rs);
  }                             /* process the tail with head item */
}  /* _chain() */               /* and without (in the next loop) */

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

static int _search (FPTREE *fpt, int d, int pfx, FPRS *rs)
{                               /* --- rec. search frequent patterns */
  int     i, k, n;              /* loop variables, buffer */
  int     *refs;                /* counters for node references */
  FPTREE  *proj;                /* projected frequent pattern tree */
  FPTLIST *list;                /* node list for current item */
  FPTNODE *node, *tmp;          /* to traverse the tree nodes */

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

  /* --- find the chain section --- */
  refs = rs->items +d;          /* get the reference counters */
  for (n = 0; n < fpt->cnt; n++) {
    node = fpt->lists[n].node;  /* traverse the items and their lists */
    if (!node) continue;        /* skip empty lists */
    if (node->succ) break;      /* list must have at most one elem. */
    i = node->parent->item;     /* check references to the parent */
    if ((i >= 0) && (++refs[i] > 1)) break;
    refs[n] = 0;                /* there must be no more than one */
  }                             /* parent reference to each node */

  /* --- process the tree section --- */
  d++;                          /* increment the recursion depth */
  for (i = fpt->cnt; --i >= n; ) {
    list = fpt->lists +i;       /* traverse the items and their lists */
    if (list->cnt < rs->supp) { /* skip infrequent items */
      _prune(fpt); continue; }  /* (just prune their node list) */
    rs->items[d-1] = i; k = 0;  /* store the last item of the set */
    if (d >= rs->min) {         /* if the item set is large enough */
      k = rs->report(rs->items, d, pfx, list->cnt, rs->data);
      if (k) { rs->cnt++; pfx = d-1; }
    }                           /* report the frequent item set */
    if ((d >= rs->max)          /* if maximal size has been reached */
    ||  (i <= 0)) {             /* or at first (and thus only) item, */
      _prune(fpt); continue; }  /* skip the recursion */
    proj = rs->proj(fpt, i);    /* project the freq. pattern tree, */
    if (rs->bonsai)             /* if the bonsai flag is set, */
      _bonsai(proj, rs->supp);  /* prune the projection to a bonsai */
    k = _search(proj, d, pfx +k, rs);
    free(proj);                 /* recursively search the projection */
    if (k) return -1;           /* if an error occurred, abort */
  }                             /* (after this only chains remain) */

  /* --- process remaining chains --- */
  --d;                          /* decrement the recursion depth */
  while (--fpt->cnt >= 0) {     /* traverse the items in chains */
    node = fpt->lists[fpt->cnt].node;
    if (!node) continue;        /* skip empty node lists */
    if (!rs->bonsai) {          /* if not pruned to bonsai */
      if (node->cnt < rs->supp){/* remove infrequent items */
        ms_free(fpt->mem, node); continue; }
      do {                      /* traverse the chain */
        for (tmp = node->parent; tmp->cnt < rs->supp; )
          tmp = tmp->parent;    /* remove infrequent items */
        node = node->parent = tmp;
      } while (node->item >= 0);/* keep frequent items */
      node = fpt->lists[fpt->cnt].node;
    }                           /* get the chain start again */
    _chain(node, d, pfx, fpt->root.cnt, rs);
    do {                        /* process an item chain */
      fpt->lists[node->item].node = NULL;
      tmp  = node;              /* note the current node */
      node = node->parent;      /* and go to its parent */
      ms_free(fpt->mem, tmp);   /* delete the buffered node */
    } while (node->item >= 0);  /* while not at the end of the chain */
  }
  return 0;                     /* return 'ok' */
}  /* _search() */

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

int fpt_search (FPTREE *fpt, int supp, int min, int max, int mode,
                FPTREPFN report, void *data)
{                               /* --- search frequent patterns */
  int  n;                       /* number of frequent item sets */
  FPRS *rs;                     /* structure for recursive search */

  assert(fpt                    /* check the function arguments */
	 && (supp > 0) && (max >= min) && (min >= 0) && report);
  rs = (FPRS*)malloc(sizeof(FPRS) +(fpt->cnt -1) *sizeof(int));
  if (!rs) return -1;           /* create recursive search structure */
  rs->supp   = (supp > 0) ? supp : 1;
  rs->min    = min;             /* initialize the fields */
  rs->max    = max;             /* with the given parameters */
  rs->bonsai = (mode & FPT_BONSAI)  ? -1 : 0;
  rs->proj   = (mode & FPT_ALTPROJ) ? _proj_level : _proj_path;
  rs->report = report;
  rs->data   = data;
  rs->cnt    = 0;               /* initialize the item set counter */
  if (_search(fpt, 0, 0, rs) != 0)
    return -1;                  /* search the tree recursively */
  n = rs->cnt; free(rs);        /* delete the search structure and */
  return n;                     /* return number of freq. item sets */
}  /* fpt_search() */

/*--------------------------------------------------------------------*/
#ifndef NDEBUG

void fpt_show (FPTREE *fpt, const char *title)
{                               /* --- show a freq. pattern tree */
  int     i;                    /* loop variable */
  FPTNODE *node;                /* to traverse the node lists */

  printf("\n%s\n", title);      /* leave one line empty */
  for (i = 0; i < fpt->cnt; i++) {         /* traverse the items */
    printf("%s ", is_name(fpt->itemset, i));  /* print the item */
    printf("(%d):", fpt->lists[i].cnt);       /* and its support */
    for (node = fpt->lists[i].node; node; node = node->succ) {
      printf(" %d", node->cnt); /* print the node support */
      if (node->parent)         /* if the parent exists */
        printf("[%s]", is_name(fpt->itemset, node->parent->item));
    }                           /* print the item in the parent */
    printf("\n");               /* terminate the line */
  }                             /* after each node list */
}  /* fpt_show() */

#endif