istree.c

数据挖掘中的关联规则算法

{                               /* --- clean up on error */
  ISNODE *node, *t;             /* to traverse the nodes */

  assert(ist);                  /* check the function argument */
  for (node = ist->levels[ist->lvlcnt]; node; ) {
    t = node; node = node->succ; free(t); }
  ist->levels[ist->lvlcnt] = NULL; /* delete all created nodes */
  for (node = ist->levels[ist->lvlcnt -1]; node; node = node->succ)
    node->chcnt = 0;            /* clear the child node counters */
}  /* _cleanup() */             /* of the deepest nodes in the tree */

/*----------------------------------------------------------------------
  Additional Evaluation Measure Functions
----------------------------------------------------------------------*/

static double _none (double head, double body, double post)
{ return 1; }                   /* --- no add. evaluation measure */

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

static double _diff (double head, double body, double post)
{ return fabs(post -head); }    /* --- absolute confidence difference */

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

static double _quot (double head, double body, double post)
{                               /* --- diff. of conf. quotient to 1 */
  if (post > head) return 1 -head/post;
  return (head <= 0) ? 0 : (1 -post/head);
}  /* _quot() */

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

static double _aimp (double head, double body, double post)
{                               /* --- abs. diff. of improvement to 1 */
  return (head <= 0) ? 0 : fabs(1 -post/head);
}  /* _aimp() */

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

static double _info (double head, double body, double post)
{                               /* --- information diff. to prior */
  double res, t;                /* result, temporary buffer */

  if ((head < EPSILON) || (1-head < EPSILON)
  ||  (body < EPSILON) || (1-body < EPSILON))
    return 0;                   /* check for strict positivity */
  post *= body; res = 0;        /* support of     head and     body */
  if (post > 0) res += post *log(post /(   head  *   body));
  t = body -post;               /* support of not head and     body */
  if (t    > 0) res += t    *log(t    /((1-head) *   body));
  t = head -post;               /* support of     head and not body */
  if (t    > 0) res += t    *log(t    /(   head  *(1-body)));
  t = 1-head -body +post;       /* support of not head and not body */
  if (t    > 0) res += t    *log(t    /((1-head) *(1-body)));
  return res/LN_2;              /* return information gain in bits */
}  /* _info() */

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

static double _chi2 (double head, double body, double post)
{                               /* --- normalized chi^2 measure */
  double t;                     /* temporary buffer */

  if ((head < EPSILON) || (1-head < EPSILON)
  ||  (body < EPSILON) || (1-body < EPSILON))
    return 0;                   /* check for strict positivity */
  t = (head -post) *body;       /* compute and return chi^2 measure */
  return (t*t) / (head *(1-head) *body *(1-body));
}  /* _chi2() */

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

static EVALFN *_evalfns[EM_UNKNOWN] = {
  /* EM_NONE  0 */  _none,      /* no additional evaluation measure */
  /* EM_DIFF  1 */  _diff,      /* absolute confidence difference */
  /* EM_QUOT  2 */  _quot,      /* difference of conf. quotient to 1 */
  /* EM_AIMP  3 */  _aimp,      /* abs. diff. of improvement to 1 */
  /* EM_INFO  4 */  _info,      /* information difference to prior */
  /* EM_CHI2  5 */  _chi2,      /* normalized chi^2 measure */
};                              /* table of evaluation functions */

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

ISTREE* ist_create (int itemcnt, double supp, double conf,
                    int rsdef, const char *apps, int memopt)
{                               /* --- create an item set tree */
  ISTREE *ist;                  /* created item set tree */
  ISNODE **lvl;                 /* vector of tree levels */
  ISNODE *root;                 /* root node of the tree */
  int    *buf, *map;            /* buffer vector, identifier map */
  char   *a;                    /* to traverse appearances vector */
  int    n;                     /* temporary buffer */

  assert((itemcnt >= 0)         /* check the function arguments */
      && (supp >= 0) && (supp <= 1) && (conf >= 0) && (conf <= 1));

  /* --- allocate memory --- */ 
  ist = (ISTREE*)malloc(sizeof(ISTREE) +(itemcnt-1) *sizeof(char));
  if (!ist) return NULL;        /* allocate the tree body */
  ist->levels = lvl = (ISNODE**)malloc(BLKSIZE *sizeof(ISNODE*));
  if (!lvl) { free(ist); return NULL; }
  ist->buf    = buf = (int*)    malloc(BLKSIZE *sizeof(int));
  if (!buf) { free(lvl); free(ist); return NULL; }
  ist->map    = map = (int*)    malloc(itemcnt *sizeof(int));
  if (!map) { free(buf); free(lvl); free(ist); return NULL; }
  #ifdef ARCH64                 /* if 64 bit architecture */
  n = (itemcnt & 1) ? itemcnt+1 : itemcnt;
  #else                         /* pad counters to even number */
  n = itemcnt;                  /* on 32 bit systems, however, */
  #endif                        /* use the number of items directly */
  lvl[0] = ist->curr = root =   /* allocate a root node */
    (ISNODE*)calloc(1, sizeof(ISNODE) +(n-1) *sizeof(int));
  if (!root){ free(map); free(buf); free(lvl); free(ist); return NULL; }

  /* --- initialize structures --- */
  ist->lvlvsz  = BLKSIZE;       /* copy parameters to the structure */
  ist->lvlcnt  = 1;    ist->tacnt = 0;
  ist->supp    = supp; ist->conf  = conf;
  ist->rsdef   = rsdef & IST_BOTH;
  ist->memopt  = memopt;
  #ifdef BENCH                  /* if benchmark version */
  ist->cnt     = ist->nec   = itemcnt;
  ist->chcnt   = ist->chnec = 0;
  ist->bytes   = sizeof(ISTREE) +itemcnt *sizeof(char) +8
               + BLKSIZE *sizeof(ISNODE*) +8
               + BLKSIZE *sizeof(int) +8
               + itemcnt *sizeof(int) +8;
  #endif                        /* initialize the benchmark variables */
  ist_init(ist, 1, EM_NONE, 1); /* initialize rule extraction */
  root->parent = root->succ = NULL;
  root->offset = root->id   = 0;
  root->chcnt  = 0;             /* initialize the root node */
  root->size   = n;
  a = ist->apps;                /* copy item appearances */
  if (apps) { while (--itemcnt >= 0) *a++ = *apps++ & IST_BOTH; }
  else      { while (--itemcnt >= 0) *a++ = IST_BOTH;           }
  return ist;                   /* return created item set tree */
}  /* ist_create() */

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

void ist_delete (ISTREE *ist)
{                               /* --- delete an item set tree */
  int    i;                     /* loop variables */
  ISNODE *node, *t;             /* to traverse the nodes */

  assert(ist);                  /* check the function argument */
  for (i = ist->lvlcnt; --i >= 0; ) {
    for (node = ist->levels[i]; node; ) {
      t = node; node = node->succ; free(t); }
  }                             /* delete all nodes, */
  free(ist->levels);            /* the level vector, */
  free(ist->map);               /* the identifier map, */
  free(ist->buf);               /* the path buffer, */
  free(ist);                    /* and the tree body */
}  /* ist_delete() */

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

void ist_count (ISTREE *ist, int *set, int cnt)
{                               /* --- count transaction in tree */
  assert(ist                    /* check the function arguments */
     && (cnt >= 0) && (set || (cnt <= 0)));
  if (cnt >= ist->lvlcnt)       /* recursively count transaction */
    _count(ist->levels[0], set, cnt, ist->lvlcnt);
  ist->tacnt++;                 /* increment the transaction counter */
}  /* ist_count() */

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

void ist_countx (ISTREE *ist, TATREE *tat)
{                               /* --- count transaction in tree */
  assert(ist && tat);           /* check the function arguments */
  _countx(ist->levels[0], tat, ist->lvlcnt);
  ist->tacnt = tat_cnt(tat);    /* recursively count the tree and */
}  /* ist_countx() */           /* set the transaction counter */

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

int ist_check (ISTREE *ist, char *marks)
{                               /* --- check item usage */
  int i, n;                     /* loop variable, number of items */

  assert(ist);                  /* check the function argument */
  for (i = ist->levels[0]->size; --i >= 0; )
    marks[i] = 0;               /* clear the marker vector */
  n = (ist->rsdef == IST_BOTH)  /* get the minimum support */
    ? (int)ceil(ist->tacnt *ist->supp)
    : (int)ceil(ist->tacnt *ist->supp *ist->conf);
  _check(ist->levels[0], marks, n);  /* check the item usage */
  for (n = 0, i = ist->levels[0]->size; --i >= 0; )
    if (marks[i]) n++;          /* count used items */
  return n;                     /* and return this number */
}  /* ist_check() */

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

int ist_addlvl (ISTREE *ist)
{                               /* --- add a level to item set tree */
  int    i, n, c;               /* loop variable, counter, buffer */
  ISNODE **ndp;                 /* to traverse the nodes */
  ISNODE *node;                 /* new (reallocated) node */
  ISNODE **end;                 /* end of new level node list */
  ISNODE *cur;                  /* current node in new level */
  ISNODE *frst;                 /* first child of current node */
  ISNODE *last;                 /* last  child of current node */
  ISNODE **vec;                 /* child node vector */
  int    *map;                  /* identifier map */
  int    s_min;                 /* minimal support of a set */
  int    s_sub;                 /* minimal support of a subset */
  void   *p;                    /* temporary buffer */

  assert(ist);                  /* check the function arguments */

  /* --- enlarge level vector --- */
  if (ist->lvlcnt >= ist->lvlvsz) { /* if the level vector is full */
    n = ist->lvlvsz +BLKSIZE;   /* compute new vector size */
    p = realloc(ist->levels, n *sizeof(ISNODE*));
    if (!p) return -1;          /* enlarge the level vector */
    ist->levels = (ISNODE**)p;  /* and set the new vector */
    p = realloc(ist->buf,    n *sizeof(int));
    if (!p) return -1;          /* enlarge the buffer vector */
    ist->buf    = (int*)p;      /* and set the new vector */
    ist->lvlvsz = n;            /* set the new vector size */
  }                             /* (applies to buf and levels) */
  end  = ist->levels +ist->lvlcnt;
  *end = NULL;                  /* start a new tree level */

  /* --- add tree level --- */
  s_sub = (int)ceil(ist->tacnt *ist->supp); /* minimal subset support */
  s_min = (ist->rsdef == IST_BOTH) ? s_sub  /* minimal rule   support */
        : (int)ceil(ist->tacnt *ist->supp *ist->conf);
  for (ndp = ist->levels +ist->lvlcnt -1; *ndp; ndp = &(*ndp)->succ) {
    frst = last = NULL;         /* traverse the deepest nodes */
    for (i = n = 0; i < (*ndp)->size; i++) {
      cur = _child(ist, *ndp, i, s_min, s_sub);
      if (!cur) continue;       /* create a child if necessary */
      if (cur == (void*)-1) { _cleanup(ist); return -1; }
      if (!frst) frst = cur;    /* note first and last child node */
      *end = last = cur;        /* add node at the end of the list */
      end  = &cur->succ; n++;   /* that contains the new level */