istree.c

apriori算法使用VC++编写的 使用前

      }                         /* constructed (partial) item sets */
    }                           /* as paths to find the counters */
  }                             /* 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->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, 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 */
  double nrm;                   /* frequency normalization factor */

  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 */
  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 */
  cnts = ist->levels[0]->cnts;  /* and the item frequency vector */
  nrm  = (ist->tacnt > 0)       /* compute the normalization factor */
       ? 1.0/ist->tacnt : 1.0;  /* for the item set support */

  /* --- 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 < 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. */
    if      (ist->arem == EM_LOGQ){ /* if logarithm of supp. quotient */
      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); }
    else if (ist->arem == EM_QUOT) { /* if measure is the quotient */
      dev = COUNT(cnts[item]);  /* compute the expected support */
      for (tmp = node; tmp->parent; tmp = tmp->parent)
        dev *= COUNT(cnts[ID(tmp)]) *nrm;
      dev = s_set /dev -1.0;  } /* compute the support quotient -1 */
    else {                      /* if no add. evaluation measure, */
      dev = 0; break; }         /* abort the search loop */
    if (dev >= ist->minval)     /* if the value of the additional */
      break;                    /* evaluation measure is high enough, */
  }                             /* abort the search loop */
  *supp = s_set;                /* store the item set support */

  /* --- 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 */
  }
  if (aval) *aval = dev;        /* set the add. evaluation measure */
  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 && conf);  /* check function arguments */

  /* --- initialize --- */
  if (ist->size > ist->lvlcnt)  /* if the tree is not high enough */
    return -1;                  /* for the rule length, abort */
  if (ist->node)                /* if this is not the first rule, */
    node = ist->node;           /* get the buffered item set node */
  else {                        /* if this is the first rule */
    node = ist->node = ist->levels[ist->size -1];
    ist->index = ist->item = -1;/* initialize the */
  }                             /* rule extraction variables */

  /* --- find rule --- */
  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->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 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 ((ist->apps[item] == IST_IGNORE)
      ||  (HDONLY(node) && (ist->apps[item] == IST_HEAD)))
        continue;               /* skip sets with two head only items */
      ist->item   = item;       /* set the head item identifier */
      ist->hdonly = HDONLY(node) || (ist->apps[item] == IST_HEAD);
      ist->head   = node;       /* set the new head item node */
      ist->path   = ist->buf +ist->lvlvsz;
      ist->plen   = 0;          /* clear the path */
    }
    app = ist->apps[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->levels[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;

  /* --- 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, */
  *conf   = c;                  /* the rule confidence, and */
  if (aval) *aval = v;          /* the value of the add. measure */
  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 && conf);  /* check function arguments */

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

  /* --- find hyperedge --- */
  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->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 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