istree.c

用VC++實現apriori演算法

        if (mode == IST_CLOSED) supp = node->cnts[i];
        _marksub(ist, node, i, supp);
      }                         /* mark all n-1 subsets */
    }                           /* of the current item set */
  }                             /* that have to be cleared/marked */
}  /* 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->item = ist->index = -1;  /* initialize rule extraction */
  ist->node = ist->lvls[minlen -1];
  ist->size = minlen;
  ist->head = NULL;
  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, int *supp, double *aval)
{                               /* --- extract next frequent item set */
  int    i;                     /* loop variable */
  int    item;                  /* an item identifier */
  ISNODE *node, *tmp;           /* current item set node, buffer */
  int    *cnts;                 /* to access the item frequencies */
  int    s_set;                 /* support of the current set */
  double dev;                   /* deviation from indep. occurrence */

  assert(ist && set && supp);   /* check the function arguments */
  if (ist->size > ist->height)  /* if the tree is not high enough */
    return -1;                  /* for the item set size, abort */

  /* --- find frequent item set --- */
  node = ist->node;             /* get the current item set node */
  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->height)
          return -1;            /* if beyond the deepest level, abort */
        node = ist->lvls[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 (is_getapp(ist->set, item) == IST_IGNORE)
      continue;                 /* skip items to ignore */
    s_set = node->cnts[ist->index];
    if (s_set < ist->supp)      /* if the support is not sufficient, */
      continue;                 /* go to the next item set */
    /* Note that this check automatically skips all item sets that */
    /* are marked with the flag F_SKIP, because s_set is negative  */
    /* with this flag and thus necessarily smaller than ist->supp. */
    dev = 0;                    /* init. add. evaluation measure */
    if (ist->arem == EM_DIFF) { /* if logarithm of support quotient */
      cnts = ist->lvls[0]->cnts;
      dev  = log(s_set) -log(COUNT(cnts[item]));
      for (tmp = node; tmp->parent; tmp = tmp->parent)
        dev -= log(COUNT(cnts[ID(tmp)]));
      dev = (dev +(ist->size-1) *log(ist->tacnt)) *(0.01/LN_2);
      if (dev < ist->minval)    /* if the value of the additional */
        continue;               /* eval. measure is not high enough, */
    }                           /* skip the item set */
    break;                      /* otherwise abort the search loop */
  }
  *supp = s_set;                /* store the item set support and */
  if (aval) *aval = dev;        /* the value of the add. measure */

  /* --- 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 the item set size */
}  /* ist_set() */

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

int ist_rule (ISTREE *ist, int *rule,
              int *supp, double *conf, double *lift, double *aval)
{                               /* --- extract next rule */
  int    i;                     /* loop variable */
  int    item;                  /* an item identifier */
  ISNODE *node;                 /* current item set node */
  ISNODE *parent;               /* parent of the item set node */
  int    *map, n;               /* identifier map and its size */
  int    s_set;                 /* support of set  (body & head) */
  int    s_body;                /* support of body (antecedent) */
  int    s_head;                /* support of head (consequent) */
  double c, v;                  /* confidence and measure value */
  int    app;                   /* appearance flag of head item */

  assert(ist && rule && supp);  /* check the function arguments */
  if (ist->size > ist->height)  /* if the tree is not high enough */
    return -1;                  /* for the rule length, abort */

  /* --- find rule --- */
  node = ist->node;             /* get the current item set node */
  while (1) {                   /* search for a rule */
    if (ist->item >= 0) {       /* --- select next item subset */
      *--ist->path = ist->item; /* add previous head to the path */
      ist->plen++;              /* and get the next head item */
      ist->item = ID(ist->head);
      ist->head = ist->head->parent;
      if (!ist->head)           /* if all subsets have been processed */
        ist->item = -1;         /* clear the head item to trigger the */
    }                           /* selection of a new item set */
    if (ist->item < 0) {        /* --- select next 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->height)
            return -1;          /* if beyond the deepest level, abort */
          node = ist->lvls[ist->size -1];
        }                       /* get the 1st node of the new level */
        ist->node = node;       /* note the new item set node and */
        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];
      app = is_getapp(ist->set, item);
      if ((app == IST_IGNORE) || (HDONLY(node) && (app == IST_HEAD)))
        continue;               /* skip sets with two head only items */
      ist->item   = item;       /* set the head item identifier */
      ist->hdonly = HDONLY(node) || (app == IST_HEAD);
      ist->head   = node;       /* set the new head item node */
      ist->path   = ist->buf +ist->vsz;
      ist->plen   = 0;          /* clear the path */
    }
    app = is_getapp(ist->set, ist->item); /* get head item appearance */
    if (!(app & IST_HEAD) || (ist->hdonly && (app != IST_HEAD)))
      continue;                 /* if rule is not allowed, skip it */
    s_set = COUNT(node->cnts[ist->index]);
    if (s_set < ist->supp) {    /* get and check the item set support */
      ist->item = -1; continue; }
    parent = node->parent;      /* get the parent node */
    if (ist->plen > 0)          /* if there is a path, use it */
      s_body = COUNT(_getsupp(ist->head, ist->path, ist->plen));
    else if (!parent)           /* if there is no parent (root node), */
      s_body = ist->tacnt;      /* get the number of transactions */
    else if (parent->offset >= 0)  /* if a pure vector is used */
      s_body = COUNT(parent->cnts[ID(node) -parent->offset]);
    else {                      /* if an identifier map is used */
      map = parent->cnts +(n = parent->size);
      s_body = COUNT(parent->cnts[_bsearch(map, n, ID(node))]);
    }                           /* find vector index and get support */
    if (s_body < ist->rule)     /* if the body support is too low, */
      continue;                 /* get the next subset/next set */
    c = s_set/(double)s_body;   /* compute the rule confidence */
    if (c < ist->conf -EPSILON) /* if the confidence is too low, */
      continue;                 /* go to the next item (sub)set */
    s_head = COUNT(ist->lvls[0]->cnts[ist->item]);
    if (ist->arem == EM_NONE) { /* if no add. eval. measure given, */
      v = 0; break; }           /* abort the loop (select the rule) */
    if (ist->size < 2) {        /* if rule has an empty antecedent, */
      v = 0; break; }           /* abort the loop (select the rule) */
    v = _evalfns[ist->arem](s_set, s_body, s_head, ist->tacnt);
    if (v >= ist->minval)       /* if rule value exceeds the minimal */
      break;                    /* of the add. rule eval. measure, */
  }  /* while (1) */            /* abort the loop (select rule) */
  *supp = (ist->mode & IST_HEAD) ? s_set : s_body;
  if (lift)                     /* compute and store the lift value */
    *lift = (c *ist->tacnt)/(double)s_head;
  if (conf) *conf = c;          /* store the rule confidence and */
  if (aval) *aval = v;          /* the value of the add. measure */

  /* --- build rule --- */
  if (node->offset >= 0) item = node->offset +ist->index;
  else                   item = node->cnts[node->size +ist->index];
  i = ist->size;                /* get the current item and */
  if (item != ist->item)        /* if this item is not the head, */
    rule[--i] = item;           /* add it to the rule body */
  while (node->parent) {        /* traverse the path to the root */
    if (ID(node) != ist->item)  /* and add all items on this */
      rule[--i] = ID(node);     /* path to the rule body */
    node = node->parent;        /* (except the head of the rule) */
  }
  rule[0] = ist->item;          /* set the head of the rule, */
  return ist->size;             /* return the rule size */
}  /* ist_rule() */

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

int ist_hedge (ISTREE *ist, int *hedge,
               int *supp, double *conf, double *aval)
{                               /* --- extract next hyperedge */
  int    i;                     /* loop variable */
  int    item;                  /* an item identifier */
  ISNODE *node;                 /* current item set node */
  ISNODE *head;                 /* node containing the rule head */
  int    *map, n;               /* identifier map and its size */
  int    *path, plen;           /* path in tree and its length */
  int    s_set;                 /* support of set (body & head) */
  int    s_body;                /* support of body (antecedent) */
  int    s_head;                /* support of head (consequent) */
  double c, t, v = 0;           /* confidence and measure value */

  assert(ist && hedge && supp); /* check the function arguments */
  if (ist->size > ist->height)  /* if the tree is not high enough */
    return -1;                  /* for the hyperedge size, abort */

  /* --- find hyperedge --- */
  node = ist->node;             /* get the current item set node */
  while (1) {                   /* search for a hyperedge */
    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->height)
          return -1;            /* if beyond the deepest level, abort */
        node = ist->lvls[ist->size -1];
      }                         /* get the 1st node of the new level */
      ist->node  = node;        /* note the new item set node and */
      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 (is_getapp(ist->set, item) == IST_IGNORE)
      continue;                 /* skip items to ignore */
    s_set = COUNT(node->cnts[ist->index]);
    if (s_set < ist->supp)      /* if the set support is too low, */
      continue;                 /* skip this item set */
    head = node->parent;        /* get subset support from parent */
    if (!head)                  /* if there is no parent (root node), */
      s_body = ist->tacnt;      /* get the total number of sets */
    else if (head->offset >= 0) /* if pure vectors are used */
      s_body = head->cnts[ID(node) -head->offset];
    else {                      /* if an identifier map is used */
      map = head->cnts +(n = head->size);
      s_body = head->cnts[_bsearch(map, n, ID(node))];
    }                           /* find index and get the support */
    if (s_body & F_SKIP) {      /* check for a valid body */
      node->cnts[ist->index] |= F_SKIP; continue; }
    s_body = COUNT(s_body);     /* get the support of body and head */
    s_head = COUNT(ist->lvls[0]->cnts[