tract.c

关联规则挖掘算法FP-growth算法C++实现

    else                                         k = m;
  }
  return r -l;                  /* compute the number of occurrences */
}  /* tas_occur() */

/*--------------------------------------------------------------------*/
#ifndef NDEBUG

void tas_show (TASET *taset)
{                               /* --- show a transaction set */
  int   i, k;                   /* loop variables */
  TRACT *t;                     /* to traverse the transactions */

  assert(taset);                /* check the function argument */
  for (i = 0; i < taset->cnt; i++) {
    t = taset->tracts[i];       /* traverse the transactions */
    for (k = 0; k < t->cnt; k++) {  /* traverse the items */
      if (k > 0) putc(' ', stdout); /* print a separator */
      printf(is_name(taset->itemset, t->items[k]));
    }                           /* print the next item */
    putc('\n', stdout);         /* terminate the transaction */
  }                             /* finally print the number of t.a. */
  printf("%d transaction(s)\n", taset->cnt);
}  /* tas_show() */

#endif
/*----------------------------------------------------------------------
  Transaction Tree Functions
----------------------------------------------------------------------*/

TATREE* _create (TRACT **tracts, int cnt, int index)
{                               /* --- recursive part of tat_create() */
  int    i, k, t;               /* loop variables, buffer */
  int    item, n;               /* item and item counter */
  TATREE *tat;                  /* created transaction tree */
  TATREE **vec;                 /* vector of child pointers */

  assert(tracts                 /* check the function arguments */
     && (cnt >= 0) && (index >= 0));
  if (cnt <= 1) {               /* if only one transaction left */
    n   = (cnt > 0) ? (*tracts)->cnt -index : 0;
    tat = (TATREE*)malloc(sizeof(TATREE) +(n-1) *sizeof(int));
    if (!tat) return NULL;      /* create a transaction tree node */
    tat->cnt  = cnt;            /* and initialize its fields */
    tat->size = -n;
    tat->max  =  n;
    while (--n >= 0) tat->items[n] = (*tracts)->items[index +n];
    return tat;
  }
  for (k = cnt; (--k >= 0) && ((*tracts)->cnt <= index); )
    tracts++;                   /* skip t.a. that are too short */
  n = 0; item = -1;             /* init. item and item counter */
  for (tracts += i = ++k; --i >= 0; ) {
    t = (*--tracts)->items[index]; /* traverse the transactions */
    if (t != item) { item = t; n++; }
  }                             /* count the different items */
  #ifdef ARCH64                 /* adapt to even item number */
  i = (n & 1) ? n : (n+1);      /* so that pointer addresses are */
  #else                         /* multiples of 8 on 64 bit systems */
  i = n;                        /* on 32 bit systems, however, */
  #endif                        /* use the exact number of items */
  tat = (TATREE*)malloc(sizeof(TATREE) + (i-1) *sizeof(int)
                                       + n     *sizeof(TATREE*));
  if (!tat) return NULL;        /* create a transaction tree node */
  tat->cnt  = cnt;              /* and initialize its fields */
  tat->size = n;
  tat->max  = 0;
  if (n <= 0) return tat;       /* if t.a. are fully captured, abort */
  vec  = (TATREE**)(tat->items +i);
  item = tracts[--k]->items[index];
  for (tracts += i = k; --i >= 0; ) {
    t = (*--tracts)->items[index];     /* traverse the transactions, */
    if (t == item) continue;    /* but skip those with the same item */
    tat->items[--n] = item; item = t;
    vec[n] = _create(tracts+1, k-i, index+1);
    if (!vec[n]) break;         /* note the item identifier */
    t = vec[n]->max +1; if (t > tat->max) tat->max = t;
    k = i;                      /* recursively create subtrees */
  }                             /* and adapt the section end index */
  if (i < 0) {                  /* if child creation was successful */
    tat->items[--n] = item;     /* note the last item identifier */
    vec[n] = _create(tracts, k+1, index+1);
    if (vec[n]) {               /* create the last child */
      t = vec[n]->max +1; if (t > tat->max) tat->max = t;
      return tat;               /* return the created */
    }                           /* transaction tree */
  }                             
  for (i = tat->size; --i > n; ) tat_delete(vec[i]);
  free(tat);                    /* on error delete created subtrees */
  return NULL;                  /* and the transaction tree node */
}  /* _create() */

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

TATREE* tat_create (TASET *taset, int heap)
{                               /* --- create a transactions tree */
  assert(taset);                /* check the function argument */
  if (heap) v_heapsort(taset->tracts, taset->cnt, ta_cmp, NULL);
  else      v_sort    (taset->tracts, taset->cnt, ta_cmp, NULL);
  return _create(taset->tracts, taset->cnt, 0);
}  /* tat_create() */

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

void tat_delete (TATREE *tat)
{                               /* --- delete a transaction tree */
  int    i;                     /* loop variable */
  TATREE **vec;                 /* vector of child nodes */

  assert(tat);                  /* check the function argument */
  #ifdef ARCH64                 /* if 64 bit architecture */
  i = (tat->size & 1) ? tat->size : (tat->size+1);
  #else                         /* address must be a multiple of 8 */
  i = tat->size;                /* on 32 bit systems, however, */
  #endif                        /* use the number of items directly */
  vec = (TATREE**)(tat->items +i);
  for (i = tat->size; --i >= 0; )
    tat_delete(vec[i]);         /* recursively delete the subtrees */
  free(tat);                    /* and the tree node itself */
}  /* tat_delete() */

/*--------------------------------------------------------------------*/
#ifdef ARCH64

TATREE* tat_child (TATREE *tat, int index)
{                               /* --- go to a child node */
  int s;                        /* padded size of the node */

  assert(tat                    /* check the function arguments */
     && (index >= 0) && (index < tat->size));
  s = (tat->size & 1) ? tat->size : (tat->size +1);
  return ((TATREE**)(tat->items +s))[index];
}  /* tat_child */              /* return the child node/subtree */

#endif
/*--------------------------------------------------------------------*/

void tat_mark (TATREE *tat)
{                               /* --- mark end of transactions */
  int i;                        /* loop variable */

  assert(tat);                  /* check the function argument */
  if      (tat->size < 0)       /* if there is a transaction, */
    tat->items[tat->max-1] |= INT_MIN;  /* mark end of trans. */
  else {                        /* if there are subtrees */
    for (i = tat->size; --i >= 0; )
      tat_mark(tat_child(tat, i));
  }                             /* recursively mark the subtrees */
}  /* tat_mark() */

/*--------------------------------------------------------------------*/
#ifndef NDEBUG

void _show (TATREE *tat, int ind)
{                               /* --- rekursive part of tat_show() */
  int    i, k;                  /* loop variables */
  TATREE **vec;                 /* vector of child nodes */

  assert(tat && (ind >= 0));    /* check the function arguments */
  if (tat->size <= 0) {         /* if this is a leaf node */
    for (i = 0; i < tat->max; i++)
      printf("%d ", tat->items[i] & ~INT_MIN);
    printf("\n"); return;       /* print the items in the */
  }                             /* (rest of) the transaction */
  vec = (TATREE**)(tat->items +tat->size);
  for (i = 0; i < tat->size; i++) {
    if (i > 0) for (k = ind; --k >= 0; ) printf("  ");
    printf("%d ", tat->items[i]);
    _show(vec[i], ind+1);       /* traverse the items, print them, */
  }                             /* and show the children recursively */
}  /* _show() */

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

void tat_show (TATREE *tat)
{                               /* --- show a transaction tree */
  assert(tat);                  /* check the function argument */
  _show(tat, 0);                /* just call the recursive function */
}  /* tat_show() */

#endif
/*----------------------------------------------------------------------
  Item Set Evaluation Functions
----------------------------------------------------------------------*/

ISEVAL* ise_create (ITEMSET *iset, int tacnt)
{                               /* --- create an item set evaluation */
  int    i;                     /* loop variable */
  ISEVAL *eval;                 /* created item set evaluator */

  i    = is_cnt(iset);          /* get the number of items */
  eval = (ISEVAL*)malloc(sizeof(ISEVAL) +(i+i) *sizeof(double));
  if (!eval) return NULL;       /* create an evaluation object */
  eval->logfs = eval->lsums +i +1;  /* and organize the memory */
  eval->logta = log(tacnt);     /* store log of number of trans. */
  while (--i >= 0)              /* compute logarithms of item freqs. */
    eval->logfs[i] = log(is_getfrq(iset, i));
  eval->lsums[0] = 0;           /* init. first sum of logarithms */
  return eval;                  /* return created item set evaluator */
}  /* ise_create() */

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

double ise_eval (ISEVAL *eval, int *ids, int cnt, int pfx, int supp)
{                               /* --- evaluate an item set */
  double sum;                   /* sum of logarithms of frequencies */

  pfx = 0;

  sum = (pfx > 0)               /* if there is a prefix, */
      ? eval->lsums[pfx-1] : 0; /* get already known logarithm sum */
  printf("%g ", sum);
  for ( ; pfx < cnt; pfx++) {   /* compute and add remaining terms */
    eval->lsums[pfx] = sum += eval->logfs[ids[pfx]];
    printf("%g ", sum);
  }
  printf(": %g\n", (log(supp) -sum +(cnt-1) *eval->logta) * (1.0/LN_2));


  return (log(supp) -sum +(cnt-1) *eval->logta) * (1.0/LN_2);
}  /* ise_eval() */             /* compute logarithm of quotient */

/*----------------------------------------------------------------------
  Item Set Formatting Functions
----------------------------------------------------------------------*/

ISFMTR* isf_create (ITEMSET *iset, int scan)
{                               /* --- create an item set formatter */
  int        i, k, n;           /* loop variable, buffers */
  int        len, sum;          /* length of an item name and sum */
  ISFMTR     *fmt;              /* created item set formatter */
  char       buf[4*TS_SIZE+4];  /* buffer for formatting */
  const char *name;             /* to traverse the item names */
  char       *copy;             /* for copies of formatted names */

  n   = is_cnt(iset);           /* get the number of items */
  fmt = (ISFMTR*)malloc(sizeof(ISFMTR) + n    *sizeof(int)
                                       +(n-1) *sizeof(char*));
  if (!fmt) return NULL;        /* create the base structure */
  fmt->buf  = NULL;             /* and organize the memory */
  fmt->offs = (int*)(fmt->names +n);
  for (i = sum = fmt->cnt = 0; i < n; i++) {
    name = is_name(iset, i);    /* traverse the item names */
    len  = strlen(name);        /* and get their length */
    sum += k = (scan) ? sc_format(buf, name, 0) : len;
    if (k > len) {              /* if formatting was needed */
      copy = (char*)malloc((k+1) *sizeof(char));
      if (!copy) { fmt->cnt = i-1; isf_delete(fmt); return NULL; }
      name = strcpy(copy, buf); /* copy the formatted name */
    }                           /* into a newly created string */
    fmt->names[i] = name;       /* store (formatted) item name */
  }                             /* afterwards create output buffer */
  if (scan) fmt->cnt = n;       /* note the number of items */
  fmt->buf = (char*)malloc((sum +n +1) *sizeof(char));
  if (!fmt->buf) { isf_delete(fmt); return NULL; }
  fmt->offs[0] = 0;             /* init. the first prefix offset */
  return fmt;                   /* return created item set formatter */
}  /* isf_create() */

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

void isf_delete (ISFMTR *fmt)
{                               /* --- delete an item set formatter */
  int i;                        /* loop variable */
  for (i = fmt->cnt; --i >= 0; )
    if ((fmt->names[i]    != NULL)
    &&  (fmt->names[i][0] == '"'))
      free((void*)fmt->names[i]);
  if (fmt->buf) free(fmt->buf); /* delete reformatted item names, */
  free(fmt);                    /* the output buffer and the base */
}  /* isf_delete() */

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

const char* isf_format (ISFMTR *fmt, int *ids, int cnt, int pre)
{                               /* --- format an item set */
  char       *p;                /* to traverse the output buffer */
  const char *name;             /* to traverse the item names */

  p = fmt->buf +fmt->offs[pre]; /* get position for appending */
  while (pre < cnt) {           /* traverse the additional items */
    name = fmt->names[ids[pre]];/* copy the item name to the output */
    while (*name) *p++ = *name++;
    *p++ = ' ';                 /* add an item separator */
    fmt->offs[++pre] = (int)(p-fmt->buf);
  }                             /* record the new offset */
  *p = '\0';                    /* terminate the formatted item set */
  fmt->len = (int)(p-fmt->buf); /* note the length of the description */
  return fmt->buf;              /* return the output buffer */
}  /* isf_format() */