fptree.c

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

/*----------------------------------------------------------------------
  File    : fptree.c
  Contents: frequent pattern tree management
  Author  : Christian Borgelt
  History : 2004.11.21 file created
            2004.11.22 second projection added, bonsai pruning added
            2004.12.09 adapted to changed report function
            2004.12.10 adapted to general memory management system
            2004.12.28 bug in function fpt_delete fixed
            2005.12.06 bug in function _proj_level fixed
            2006.11.26 reuse of item set prefix made possible
            2008.01.22 special processing of chains added
            2008.01.23 bonsai pruning corrected (node merging)
----------------------------------------------------------------------*/
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "fptree.h"
#ifdef STORAGE
#include "storage.h"
#endif

/*----------------------------------------------------------------------
  Preprocessor Definition
----------------------------------------------------------------------*/
#define BLKSIZE    6553         /* block size for memory management */

/*----------------------------------------------------------------------
  Type Definition
----------------------------------------------------------------------*/
typedef FPTREE* PROJFN (FPTREE *fpt, int item);

typedef struct {                /* --- structure for recursive search */
  int      min;                 /* minimum number of items */
  int      max;                 /* maximum number of items */
  int      supp;                /* minimum support (num. of trans.) */
  int      bonsai;              /* flag for pruning to bonsai */
  PROJFN   *proj;               /* projection function */
  FPTREPFN *report;             /* report function for results */
  void     *data;               /* user data for report function */
  int      cnt;                 /* number of frequent item sets */
  int      items[1];            /* item vector for reporting */
} FPRS;                         /* (structure for rec. search) */

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

static FPTREE* _create (MEMSYS *mem, int cnt)
{                               /* --- create a base freq. pat. tree */
  FPTREE  *fpt;                 /* created frequent pattern tree */
  FPTLIST *list;                /* to traverse the node lists */

  assert(cnt > 0);              /* check the function arguments */
  fpt = (FPTREE*)malloc(sizeof(FPTREE) +(cnt-1) *sizeof(FPTLIST));
  if (!fpt) return NULL;        /* allocate the base structure */
  fpt->cnt = cnt;               /* and note the number of items */
  fpt->root.item = -1;          /* initialize the root node */
  fpt->root.cnt  =  0;          /* (dummy connecting the trees) */
  fpt->root.copy = fpt->root.parent = NULL;
  if (mem) fpt->mem = mem;      /* if a memory management is given, */
  else {                        /* simply store it, otherwise */
    fpt->mem = ms_create(sizeof(FPTNODE), BLKSIZE);
    if (!fpt->mem) { free(fpt); return NULL; }
  }                             /* create a memory management system */
  for (list = fpt->lists +cnt; --cnt >= 0; ) {
    (--list)->cnt = 0; list->node = NULL;
  }                             /* initialize the node list and */
  return fpt;                   /* return the created freq. pat. tree */
}  /* _create() */

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

static int _build (FPTREE *fpt, FPTNODE *parent,
                   TASET *taset, int lft, int rgt, int pos)
{                               /* --- recursively build f.p. tree */
  int     i, k;                 /* loop variable, buffer */
  int     item;                 /* to traverse the items at pos */
  FPTLIST *list;                /* to access the node lists */
  FPTNODE *node;                /* created freq. pattern tree node */

  assert(fpt && taset && (pos >= 0)); /* check the function arguments */
  while ((lft <= rgt) && (tas_tsize(taset, lft) <= pos))
    lft++;                      /* skip trans. that are too short */
  if (lft > rgt) return 0;      /* check for an empty item range */
  item = k = tas_tract(taset, i = rgt)[pos];   /* get first item */
  do {                          /* traverse the longer transactions */
    while (--i >= lft) {        /* while not at start of section */
      k = tas_tract(taset, i)[pos];
      if (k != item) break;     /* try to find a transaction */
    }                           /* with a different item */
    node = ms_alloc(fpt->mem);  /* create a new tree node */
    if (!node) return -1;       /* for the current item and */
    list = fpt->lists +item;    /* get the corresponding node list */
    node->item   = item;        /* store the item and its support */
    list->cnt   += node->cnt = rgt -i;
    node->succ   = list->node;  /* insert the node into the list */
    list->node   = node;        /* (add at head of list) */
    node->parent = parent;      /* init. the parent pointer */
    node->copy   = NULL;        /* clear the copy pointer */
    if (_build(fpt, node, taset, i+1, rgt, pos+1) != 0)
      return -1;                /* build the child node recursively */
    item = k; rgt = i;          /* remove processed transaction from */
  } while (lft <= rgt);         /* the interval and note next item */
  return 0;                     /* return 'ok' */
}  /* _build() */

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

FPTREE* fpt_create (TASET *taset)
{                               /* --- create a freq. pattern tree */
  FPTREE *fpt;                  /* created frequent pattern tree */

  assert(taset);                /* check the function argument */
  fpt = _create(NULL, is_cnt(tas_itemset(taset)));
  if (!fpt) return NULL;        /* allocate a base f.p. tree */
  fpt->itemset  = tas_itemset(taset);
  fpt->root.cnt = tas_cnt(taset);
  if ((fpt->root.cnt > 0)       /* recursively build the f.p. tree */
  &&  (_build(fpt, &fpt->root, taset, 0, fpt->root.cnt-1, 0) != 0)) {
    fpt_delete(fpt); return NULL; }
  return fpt;                   /* return the created tree */
}  /* fpt_create() */

/*----------------------------------------------------------------------
The above function assumes that the items in each transaction in taset
are sorted and that the transactions are sorted accordingly.
----------------------------------------------------------------------*/

void fpt_delete (FPTREE *fpt)
{                               /* --- delete a freq. pattern tree */
  assert(fpt);                  /* check the function argument */
  ms_delete(fpt->mem);          /* delete the memory system */
  free(fpt);                    /* and the base structure */
}  /* fpt_delete() */

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

static void _prune (FPTREE *fpt)
{                               /* --- prune nodes for last item */
  FPTNODE *node, *buf;          /* to traverse the nodes to delete */

  assert(fpt);                  /* check the function argument */
  for (node = fpt->lists[--fpt->cnt].node; node; ) {
    buf  = node;                /* while there is another node */
    node = node->succ;          /* note the current node and */
    ms_free(fpt->mem, buf);     /* remove it from the list, */
  }                             /* and then delete the node */
}  /* _prune() */

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

static void _detach (FPTREE *fpt)
{                               /* --- detach a projection */
  FPTNODE *node, *anc;          /* to traverse the ancestors */

  assert(fpt);                  /* check the function argument */
  fpt->root.copy = NULL;        /* clear the root's copy pointer */
  node = fpt->lists[--fpt->cnt].node;
  while (node) {                /* while there is another node */
    for (anc = node->parent; anc && anc->copy; anc = anc->parent)
      anc->copy = NULL;         /* clear the copy pointers */
    anc  = node;                /* note the current node and */
    node = node->succ;          /* remove it from the list, */
    ms_free(fpt->mem, anc);     /* then delete the node */
  }                             /* (prune deepest tree level) */
}  /* _detach() */

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

static void _cleanup (FPTREE *fpt, FPTREE *proj)
{                               /* --- clean up after failure */
  assert(fpt && proj);          /* check the function argument */
  _detach(fpt);                 /* detach projection from tree */
  while (proj->cnt > 0) _prune(proj);
  free(proj);                   /* delete the projection */
}  /* _cleanup() */             /* (only called on failure) */

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

static FPTREE* _proj_path (FPTREE *fpt, int item)
{                               /* --- project a freq. pattern tree */
  int     i;                    /* loop variable */
  FPTREE  *proj;                /* projected frequent pattern tree */
  FPTNODE *node, *anc, *copy;   /* to traverse the tree nodes */
  FPTNODE **prev;               /* to link copies to their parents */
  FPTLIST *lists;               /* to access the node lists */

  assert(fpt);                  /* check the function argument */
  proj = _create(fpt->mem, item);
  if (!proj) return NULL;       /* create a base freq. pattern tree */
  proj->itemset = fpt->itemset; /* note the underlying item set */
  fpt->root.copy = &proj->root; /* set the copy of the root node */
  lists = proj->lists;          /* get the node lists of the proj. */
  for (node = fpt->lists[item].node; node; node = node->succ) {
    prev = NULL;                /* traverse the nodes for the item */
    for (anc = node->parent; !anc->copy; anc = anc->parent) {
      anc->copy =               /* traverse and copy all ancestors */
      copy = ms_alloc(fpt->mem);        /* that are not yet copied */
      if (!copy) { _cleanup(fpt, proj); return NULL; }
      copy->item = i = anc->item;      /* store/copy the item */
      if (prev) *prev = copy;   /* set parent link from child */
      copy->succ = lists[i].node;
      lists[i].node = copy;     /* insert copy into corresp. list */
      lists[i].cnt += copy->cnt = node->cnt;
      copy->copy = NULL;        /* copy the support of the node */
      prev = &copy->parent;     /* and note the parent pointer */
    }                           /* address for later linking */
    if (prev) *prev = anc->copy;/* set last parent link from child */
    for ( ; anc; anc = anc->parent) {
      anc->copy->cnt += node->cnt;
      if (anc->item >= 0) lists[anc->item].cnt += node->cnt;
    }                           /* traverse ancestors up to the root */
  }                             /* and sum the support values */
  _detach(fpt);                 /* detach created tree projection, */
  return proj;                  /* prune last level of orig. tree, */
}  /* _proj_path() */           /* and return created projection */

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

static FPTREE* _proj_level (FPTREE *fpt, int item)
{                               /* --- project a freq. pattern tree */
  int     i, k;                 /* loop variables */
  FPTREE  *proj;                /* projected frequent pattern tree */
  FPTNODE *node, *par, *copy;   /* to traverse the tree nodes */
  FPTLIST *lists;               /* to access the node lists */

  assert(fpt);                  /* check the function argument */
  proj = _create(fpt->mem, item);
  if (!proj) return NULL;       /* create a base freq. pattern tree */
  proj->itemset = fpt->itemset; /* note the underlying item set */
  fpt->root.copy = &proj->root; /* set the copy of the root node */
  lists = proj->lists;          /* get the node lists of the proj. */
  node = fpt->lists[item].node; /* first traverse the old leaves */