istree.c

apriori算法是数据挖掘的经典算法之1,其基于关联规则的思想.这是我的第2个收藏算法

    }                           /* and advance end pointer */
    if (n <= 0) {               /* if no child node was created, */
      (*ndp)->chcnt = 0; continue; }            /* skip the node */
    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 */
    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 id. map and child vector */
        if (last->chcnt < i)    /* if a secondary id. map exists */
          map = (int*)(vec +(i = last->chcnt));
        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 (new = frst; new; new = new->succ) {
        vec[ID(new)-i] = new;   /* set the child node pointer */
        new->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, new = frst; new; new = new->succ) {
        vec[i]      = new;      /* set the child node pointer, */
        map[i++]    = new->id;  /* the identifier map entry, */
        new->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 (new = frst; new; new = new->succ) {
        vec[_bsearch(map, i, new->id)] = new;
        new->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. */
  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 */

  assert(ist && ist->curr);     /* check the function argument */
  node = ist->curr;             /* get the current node */
  if (node->chcnt <= 0)         /* if there are no child nodes, */
    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 >= node->chcnt) 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 */
    if (node->chcnt < n)        /* if a secondary id. map exists */
      map = (int*)(vec +(n = node->chcnt));
    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 next the 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 */

  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 */
    if (node->chcnt < n)        /* if a secondary id. map exists */
      map = (int*)(vec +(n = node->chcnt));
    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 */

  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 */
    if (node->chcnt < n)        /* if a secondary id. map exists */
      map = (int*)(vec +(n = node->chcnt));
    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_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;
  ist->node  = ist->head = NULL;
  ist->size  = minlen;          /* initialize rule extraction */
  if ((arem < EM_NONE) || (arem >= EM_UNKNOWN))
    arem = EM_NONE;             /* check, adapt, and note */
  ist->arem   = arem;           /* additional evaluation measure */
  ist->minval = minval;         /* and its minimal value */
}  /* ist_init() */

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

int ist_set (ISTREE *ist, int *set, double *supp)
{                               /* --- extract next frequent item set */
  int    i;                     /* loop variable */
  int    item;                  /* an item identifier */
  ISNODE *node;                 /* current item set node */
  int    s_min;                 /* minimal support of a set */
  int    s_set;                 /* support of the current set */

  assert(ist && set && supp);   /* check the function arguments */

  /* --- initialize --- */
  if (ist->size > ist->lvlcnt)  /* if the tree is not high enough */
    return -1;                  /* for the item set size, abort */
  s_min = (int)ceil(ist->tacnt *ist->supp); /* get minimal support */
  if (!ist->node)               /* on first item set, initialize */
    ist->node = ist->levels[ist->size-1];    /* the current node */
  node = ist->node;             /* get the current item set node */

  /* --- find frequent item set --- */
  while (1) {                   /* search for a frequent item set */
    if (++ist->index >= node->size) { /* if all subsets have been */
      node = node->succ;        /* processed, go to the successor */
      if (!node) {              /* if at the end of a level, go down */
        if (++ist->size > ist->lvlcnt)
          return -1;            /* if beyond the deepest level, abort */
        node = ist->levels[ist->size -1];
      }                         /* get the 1st node of the new level */
      ist->node  = node;        /* note the new item set node */
      ist->index = 0;           /* start with the first item set */
    }                           /* of the new item set node */
    if (node->offset >= 0) item = node->offset +ist->index;
    else                   item = node->cnts[node->size +ist->index];
    if (ist->apps[item] == IST_IGNORE)
      continue;                 /* skip items to ignore */
    s_set = node->cnts[ist->index];
    if (s_set >= s_min) break;  /* if the set support is sufficient, */
  }                             /* abort the search loop */
  *supp = (ist->tacnt > 0)      /* compute the item set support */
        ? (double)s_set/ist->tacnt : 1;

  /* --- build frequent item set --- */
  i        = ist->size;         /* get the current item set size */
  set[--i] = item;              /* and store the first item */
  while (node->parent) {        /* while not at the root node */
    set[--i] = ID(node);        /* add item to the item set */
    node = node->parent;        /* and go to the parent node */
  }
  return ist->size;             /* return item set size */
}  /* ist_set() */