istree.c

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

static void _cleanup (ISTREE *ist)
{                               /* --- 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 (int set, int body, int head, int n)
{ return 1; }                   /* --- no add. evaluation measure */

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

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

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

static double _quot (int set, int body, int head, int n)
{                               /* --- diff. of conf. quotient to 1 */
  double t;                     /* temporary buffer */

  if ((head <= 0) || (body <= 0)) return 0;
  t = (set/(double)body) /(head/(double)n);
  return 1 -((t > 1) ? 1/t : t);  /* return the confidence quotient */
}  /* _quot() */

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

static double _aimp (int set, int body, int head, int n)
{                               /* --- abs. diff. of improvement to 1 */
  if ((head <= 0) || (body <= 0)) return 0;
  return fabs((set/(double)body) /(head/(double)n) -1);
}  /* _aimp() */

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

static double _info (int set, int body, int head, int n)
{                               /* --- information diff. to prior */
  double sum, t;                /* result, temporary buffer */

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

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

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

  if ((head <= 0) || (head >= n)
  ||  (body <= 0) || (body >= n))
    return 0;                   /* check for strict positivity */
  t = head *(double)body -set *(double)n;
  return (t*t) / (((double)head) *(n-head) *body *(n-body));
}  /* _chi2() */                /* compute and return chi^2 measure */

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

static double _pval (int set, int body, int head, int n)
{                               /* --- p-value from chi^2 measure */
  return incGa(0.5, 0.5*n*_chi2(set, body, head, n));
}  /* _pval() */

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

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 */
  /* EM_PVAL  6 */  _pval,      /* p-value of chi^2 measure */
};                              /* table of evaluation functions */

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

ISTREE* ist_create (int mode, int cnt, int supp, double conf,
                    const char *apps)
{                               /* --- 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((cnt >= 0)             /* check the function arguments */
      && (supp >= 0) && (conf >= 0) && (conf <= 1));

  /* --- allocate memory --- */ 
  ist = (ISTREE*)malloc(sizeof(ISTREE) +(cnt-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(cnt *sizeof(int));
  if (!map) { free(buf); free(lvl); free(ist); return NULL; }
  #ifdef ARCH64                 /* if 64 bit architecture, */
  n = cnt +(cnt & 1);           /* pad counters to even number */
  #else                         /* on 32 bit systems, however, */
  n = cnt;                      /* use the number of items directly */
  #endif
  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->mode    = mode;
  ist->tacnt   = 0;
  ist->rule    = (supp > 0) ? supp : 1;
  if (mode & IST_HEAD) supp = (int)ceil(conf *supp);
  ist->supp    = (supp > 0) ? supp : 1;
  ist->conf    = conf;
  #ifdef BENCH                  /* if benchmark version */
  ist->cnt     = ist->nec   = cnt;
  ist->chcnt   = ist->chnec = 0;
  ist->bytes   = sizeof(ISTREE) +cnt *sizeof(char) +8
               + BLKSIZE *sizeof(ISNODE*) +8
               + BLKSIZE *sizeof(int) +8
               + cnt     *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 (--cnt >= 0) *a++ = *apps++ & IST_BOTH; }
  else      { while (--cnt >= 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 */
  _check(ist->levels[0], marks, ist->supp);
  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 */
  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 --- */