istree.c

用VC++實現apriori演算法

current node to arrive at the support counter for the subset. The path
variable is initialized to [0]: <item>, [1]: <offset+i>, since the
support counters for S and T can be inspected directly. Then this
path is followed from the parent node of the current node, which is
equivalent to checking the subset that can be obtained by removing
from the union of S and T the item that corresponds to the parent node
(in the path to S or T, resp.).
  Iteratively making the parent node the current node, adding its
corresponding item to the path and checking the support counter at the
end of the path variable when starting from its (the new current node's)
parent node tests all other subsets.
  Another criterion is that the extended set must not contain two items
which may appear only in the head of a rule. If two such items are
contained in a set, neither can a rule be formed from its items nor can
it be the antecedent of a rule. Whether a set contains two head only
items is determined from the nodes 'hdonly' flag and the appearance
flags of the items.
----------------------------------------------------------------------*/

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->lvls[ist->height]; node; ) {
    t = node; node = node->succ; free(t); }
  ist->lvls[ist->height] = NULL;/* delete all created nodes */
  for (node = ist->lvls[ist->height -1]; node; node = node->succ)
    node->chcnt = 0;            /* clear the child node counters */
}  /* _cleanup() */             /* of the deepest nodes in the tree */

/*----------------------------------------------------------------------
  Additional Rule 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 chi2cdf(n*_chi2(set, body, head, n), 1);
}  /* _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 (ITEMSET *set, int mode, int supp, double conf)
{                               /* --- create an item set tree */
  int    cnt, n;                /* number of items, buffer */
  ISTREE *ist;                  /* created item set tree */
  ISNODE *root;                 /* root node of the tree */

  assert(set                    /* check the function arguments */
     && (supp >= 0) && (conf >= 0) && (conf <= 1));

  /* --- allocate memory --- */ 
  cnt = is_cnt(set);            /* get the number of items */
  ist = (ISTREE*)malloc(sizeof(ISTREE));
  if (!ist) return NULL;        /* allocate the tree body */
  ist->lvls = (ISNODE**)malloc(BLKSIZE *sizeof(ISNODE*));
  if (!ist->lvls) {                  free(ist); return NULL; }
  ist->buf  = (int*)    malloc(BLKSIZE *sizeof(int));
  if (!ist->buf)  { free(ist->lvls); free(ist); return NULL; }
  ist->map  = (int*)    malloc(cnt *sizeof(int));
  if (!ist->map)  { free(ist->buf);
                    free(ist->lvls); 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
  ist->lvls[0] = ist->curr =    /* allocate a root node */
  root = (ISNODE*)calloc(1, sizeof(ISNODE) +(n-1) *sizeof(int));
  if (!root)        { free(ist->map);  free(ist->buf);
                      free(ist->lvls); free(ist); return NULL; }

  /* --- initialize structures --- */
  ist->set     = set;           /* copy parameters to the structure */
  ist->mode    = mode;
  ist->tacnt   = is_gettac(set);
  ist->vsz     = BLKSIZE;
  ist->height  = 1;
  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->sccnt   = ist->scnec = cnt;
  ist->cpcnt   = ist->cpnec = 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;
  while (--cnt >= 0)            /* copy the item frequencies */
    root->cnts[cnt] = is_getfrq(set, cnt); 
  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->height; --i >= 0; ) {
    for (node = ist->lvls[i]; node; ) {
      t = node; node = node->succ; free(t); }
  }                             /* delete all nodes, */
  free(ist->lvls);              /* 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->height)       /* recursively count transaction */
    _count(ist->lvls[0], set, cnt, ist->height);
}  /* ist_count() */

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

void ist_countx (ISTREE *ist, TATREE *tat)
{                               /* --- count transaction in tree */
  assert(ist && tat);           /* check the function arguments */
  _countx(ist->lvls[0], tat, ist->height);
}  /* ist_countx() */           /* recursively count the trans. tree */

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

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->lvls[0]->size; --i >= 0; )
    marks[i] = 0;               /* clear the marker vector */
  _checkuse(ist->lvls[0], marks, ist->supp);
  for (n = 0, i = ist->lvls[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 --- */