istree.c

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

    }                           /* and advance end pointer */
    if (n <= 0) {               /* if no child node was created, */
      (*ndp)->chcnt = F_SKIP; continue; }       /* skip the node */
    #ifdef BENCH                /* if benchmark version */
    ist->chnec += n;            /* sum the number of necessary */
    #endif                      /* child pointers */
    node = *ndp;                /* decide on the node structure: */
    if (node->offset >= 0) {    /* if a pure counter vector is used, */
      n = ID(last)-ID(frst)+1;  /* always add a pure child vector */
      i = (node->size -1) *sizeof(int) +n *sizeof(ISNODE*); }
    else if (2*n > node->size){ /* if a single id. map is best, */
      n = node->size;           /* only add a child vector */
      i = (n+n-1) *sizeof(int) +n *sizeof(ISNODE*); }
    else {                      /* if two identifier maps are best, */
      i = node->size;           /* add a child vector and a map */
      i = (i+i-1) *sizeof(int) +n *(sizeof(ISNODE*) +sizeof(int));
    }                           /* get size of additional vectors */
    node = (ISNODE*)realloc(node, sizeof(ISNODE) +i);
    if (!node) { _cleanup(ist); return -1; }
    node->chcnt = n;            /* add a child vector to the node */
    #ifdef BENCH                /* if benchmark version */
    ist->chcnt += n;            /* sum the number of child pointers */
    if ((node->offset >= 0) || (node->size == n))
         ist->bytes += n * sizeof(ISNODE*);
    else ist->bytes += n *(sizeof(ISNODE*) +sizeof(int));
    #endif                      /* determine the memory usage */
    if ((node != *ndp) && node->parent) {
      last = node->parent;      /* adapt the ref. from the parent */
      if (last->offset >= 0) {  /* if a pure vector is used */
        vec = (ISNODE**)(last->cnts +last->size);
        vec[(vec[0] != *ndp) ? ID(node) -ID(vec[0]) : 0] = node; }
      else {                    /* if an identifier map is used */
        map = last->cnts +(i = last->size);
        vec = (ISNODE**)(map+i);/* get identifier map, child vector, */
        c   = last->chcnt & ~F_SKIP;   /* and the number of children */
        if (c < i)              /* if a secondary id. map exists, */
          map = (int*)(vec +(i = c));  /* get this identifier map */
        vec[_bsearch(map, i, node->id)] = node;
      }                         /* find the proper index and */
    }                           /* set the new child pointer */
    *ndp = node;                /* set new (reallocated) node */
    if (node->offset >= 0) {    /* if to use pure vectors */
      vec = (ISNODE**)(node->cnts +node->size);
      while (--n >= 0) vec[n] = NULL;
      i = ID(frst);             /* get item identifier of first child */
      for (cur = frst; cur; cur = cur->succ) {
        vec[ID(cur)-i] = cur;   /* set the child node pointer */
        cur->parent    = node;  /* and the parent pointer */
      } }                       /* in the new node */
    else if (n < node->size) {  /* if two identifier maps are used */
      vec = (ISNODE**)(node->cnts +node->size +node->size);
      map = (int*)(vec +n);     /* get the secondary identifier map */
      for (i = 0, cur = frst; cur; cur = cur->succ) {
        vec[i]      = cur;      /* set the child node pointer, */
        map[i++]    = cur->id;  /* the identifier map entry, */
        cur->parent = node;     /* and the parent pointer */
      } }                       /* in the new node */
    else {                      /* if one identifier map is used */
      map = node->cnts +(i = node->size);
      vec = (ISNODE**)(map +i); /* get id. map and child vector */
      while (--n >= 0) vec[n] = NULL;
      for (cur = frst; cur; cur = cur->succ) {
        vec[_bsearch(map, i, cur->id)] = cur;
        cur->parent = node;     /* set the child node pointer */
      }                         /* and the parent pointer */
    }                           /* in the new node */
  }
  if (!ist->levels[ist->lvlcnt])/* if no child has been added, */
    return 1;                   /* abort the function, otherwise */
  ist->lvlcnt++;                /* increment the level counter */
  ist->tacnt = 0;               /* clear the transaction counter and */
  ist->node  = NULL;            /* the item set node for rule extr. */
  _stskip(ist->levels[0]);      /* mark subtrees to be skipped */
  return 0;                     /* return 'ok' */
}  /* ist_addlvl() */

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

void ist_up (ISTREE *ist, int root)
{                               /* --- go up in item set tree */
  assert(ist && ist->curr);     /* check the function argument */
  if      (root)                /* if root flag set, */
    ist->curr = ist->levels[0]; /* go to the root node */
  else if (ist->curr->parent)   /* if it exists, go to the parent */
    ist->curr = ist->curr->parent;
}  /* ist_up() */

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

int ist_down (ISTREE *ist, int item)
{                               /* --- go down in item set tree */
  ISNODE *node;                 /* the current node */
  ISNODE **vec;                 /* child node vector of current node */
  int    *map, n;               /* identifier map and its size */
  int    c;                     /* number of children */

  assert(ist && ist->curr);     /* check the function argument */
  node = ist->curr;             /* get the current node */
  c = node->chcnt & ~F_SKIP;    /* if there are no child nodes, */
  if (c <= 0) return -1;        /* abort the function */
  if (node->offset >= 0) {      /* if a pure vector is used */
    vec = (ISNODE**)(node->cnts +node->size);
    item -= ID(vec[0]);         /* compute index in child node vector */
    if (item >= c) return -1; } /* and abort if there is no child */
  else {                        /* if an identifier map is used */
    map = node->cnts +(n = node->size);
    vec = (ISNODE**)(map +n);   /* get id. map and child vector */
    if (c < n)                  /* if a secondary id. map exists, */
      map = (int*)(vec +(n = c));      /* get this identifier map */
    item = _bsearch(map, n, item);
  }                             /* search for the proper index */
  if ((item < 0) || !vec[item]) /* if the index is out of range */
    return -1;                  /* or the child does not exist, abort */
  ist->curr = vec[item];        /* otherwise go to the child node */
  return 0;                     /* return 'ok' */
}  /* ist_down() */

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

int ist_next (ISTREE *ist, int item)
{                               /* --- get next item with a counter */
  int    i;                     /* vector index */
  ISNODE *node;                 /* the current node */
  int    *map, n;               /* identifier map and its size */

  assert(ist && ist->curr);     /* check the function argument */
  node = ist->curr;             /* get the current node */
  if (node->offset >= 0) {      /* if a pure vector is used, */
    if (item <  node->offset) return node->offset;
    if (item >= node->offset +node->size) return -1;
    return item +1; }           /* return the next item identifier */
  else {                        /* if an identifier map is used */
    map = node->cnts +(n = node->size);
    if (item <  map[0])   return map[0];
    if (item >= map[n-1]) return -1;
    i = _bsearch(map, n, item); /* try to find the item directly */
    if (i >= 0) return map[i+1];/* and return the following one */
    while ((--n >= 0) && (*map > item)) map++;
    return (n >= 0) ? *map :-1; /* search iteratively for the next */
  }                             /* item identifier and return it */
}  /* ist_next() */

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

void ist_setcnt (ISTREE *ist, int item, int cnt)
{                               /* --- set counter for an item */
  ISNODE *node;                 /* the current node */
  ISNODE **vec;                 /* child node vector of current node */
  int    *map, n;               /* identifier map and its size */
  int    c;                     /* number of children */

  assert(ist && ist->curr);     /* check the function argument */
  node = ist->curr;             /* get the current node */
  if (node->offset >= 0) {      /* if a pure vector is used, */
    item -= node->offset;       /* get index in counter vector */
    if (item >= node->size) return; }
  else {                        /* if an identifier map is used */
    map = node->cnts +(n = node->size);
    vec = (ISNODE**)(map +n);   /* get id. map and child vector */
    c = node->chcnt & ~F_SKIP;  /* and the number of children */
    if (c < n)                  /* if a secondary id. map exists, */
      map = (int*)(vec +(n = c));      /* get this identifier map */
    item = _bsearch(map, n, item);
  }                             /* search for the proper index */
  if (item >= 0) node->cnts[item] = cnt;
}  /* ist_setcnt() */           /* set the frequency counter */

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

int ist_getcnt (ISTREE *ist, int item)
{                               /* --- get counter for an item */
  ISNODE *node;                 /* the current node */
  ISNODE **vec;                 /* child node vector of current node */
  int    *map, n;               /* identifier map and its size */
  int    c;                     /* number of children */

  assert(ist && ist->curr);     /* check the function argument */
  node = ist->curr;             /* get the current node */
  if (node->offset >= 0) {      /* if pure vectors are used, */
    item -= node->offset;       /* get index in counter vector */
    if (item >= node->size) return -1; }
  else {                        /* if an identifier map is used */
    map = node->cnts +(n = node->size);
    vec = (ISNODE**)(map +n);   /* get id. map and child vector */
    c = node->chcnt & ~F_SKIP;  /* and the number of children */
    if (c < n)                  /* if a secondary id. map exists, */
      map = (int*)(vec +(n = c));      /* get this identifier map */
    item = _bsearch(map, n, item);
  }                             /* search for the proper index */
  if (item < 0) return -1;      /* abort if index is out of range */
  return node->cnts[item];      /* return the value of the counter */
}  /* ist_getcnt() */

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

int ist_getcntx (ISTREE *ist, int *set, int cnt)
{                               /* --- get counter for an item set */
  assert(ist                    /* check the function arguments */
     && (cnt >= 0) && (set || (cnt <= 0)));
  if (cnt <= 0)                 /* if the item set is empty, */
    return ist->tacnt;          /* return the transaction count */
  return _getsupp(ist->levels[0], set, cnt);
}  /* ist_getcntx() */          /* return the item set support */

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

void ist_filter (ISTREE *ist, int mode)
{                               /* --- filter max. freq. item sets */
  int    i, k, n;               /* loop variables */
  ISNODE *node, *curr;          /* to traverse the nodes */
  int    s_min, supp;           /* (minimum) support of an item set */
  int    *set;                  /* next (partial) item set to process */

  assert(ist);                  /* check the function argument */
  s_min = (int)ceil(ist->tacnt *ist->supp);
  if (s_min <= 0) s_min = 1;    /* get minimal support */
  for (n = 1; n < ist->lvlcnt; n++) {
    for (node = ist->levels[n]; node; node = node->succ) {
      for (i = 0; i < node->size; i++) {
        if (node->cnts[i] < s_min)
          continue;             /* skip infrequent item sets */
        supp = (mode == IST_CLOSED) ? node->cnts[i] : -1;
        if (node->offset >= 0) k = node->offset +i;
        else                   k = node->cnts[node->size +i];
        set    = ist->buf +ist->lvlvsz;
        *--set = k;        _clrsupp(node->parent, set, 1, supp);
        *--set = ID(node); _clrsupp(node->parent, set, 1, supp);
        k = 2;                  /* clear counters in parent node */
        for (curr = node->parent; curr->parent; curr = curr->parent) {
          _clrsupp(curr->parent, set, k, supp);
          *--set = ID(curr); k++;
        }                       /* climb up the tree and use the */
      }                         /* constructed (partial) item sets */
    }                           /* as paths to find the counters */
  }                             /* that have to be cleared */
}  /* ist_filter() */

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

void ist_init (ISTREE *ist, int minlen, int arem, double minval)
{                               /* --- initialize (rule) extraction */
  assert(ist                    /* check the function arguments */
      && (minlen > 0) && (minval >= 0.0) && (minval <= 1.0));
  ist->index = ist->item = -1;