tract.c

数据挖掘Apriori算法在VC下的实现

    while (--taset->cnt >= 0)   /* traverse the transaction vector */
      free(taset->tracts[taset->cnt]);
    free(taset->tracts);        /* delete all transactions */
  }                             /* and the transaction vector */
  if (delis && taset->itemset) is_delete(taset->itemset);
  free(taset);                  /* delete the item set and */
}  /* tas_delete() */           /* the transaction set body */

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

int tas_add (TASET *taset, const int *items, int n)
{                               /* --- add a transaction */
  TRACT *ta;                    /* new transaction */
  int   *p;                     /* to traverse the transaction */
  TRACT **vec;                  /* new transaction vector */
  int   size;                   /* new transaction vector size */

  assert(taset);                /* check the function arguments */
  size = taset->vsz;            /* get the transaction vector size */
  if (taset->cnt >= size) {     /* if the transaction vector is full */
    size += (size > BLKSIZE) ? (size >> 1) : BLKSIZE;
    vec   = (TRACT**)realloc(taset->tracts, size *sizeof(TRACT*));
    if (!vec) return -1;        /* enlarge the transaction vector */
    taset->tracts = vec; taset->vsz = size;
  }                             /* set the new vector and its size */
  if (!items) {                 /* if no transaction is given */
    items = is_tract(taset->itemset);
    n     = is_tsize(taset->itemset);
  }                             /* get it from the item set */
  ta = (TRACT*)malloc(sizeof(TRACT) +(n-1) *sizeof(int));
  if (!ta) return -1;           /* create a new transaction */
  taset->tracts[taset->cnt++]  = ta;
  if (n > taset->max)           /* store the transaction and */
    taset->max = n;             /* update maximal transaction size */
  taset->total += n;            /* sum the number of items */
  for (p = ta->items +(ta->cnt = n); --n >= 0; )
    *--p = items[n];            /* copy the items of the t.a. */
  return 0;                     /* return 'ok' */
}  /* tas_add() */

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

void tas_recode (TASET *taset, int *map, int cnt)
{                               /* --- recode items */
  int   i, k, n, x;             /* loop variables, buffer */
  TRACT *t;                     /* to traverse the transactions */
  int   *p;                     /* to traverse the item identifiers */

  assert(taset && map);         /* check the function arguments */
  taset->max = taset->total = 0;/* clear the maximal size and total */
  for (n = taset->cnt; --n >= 0; ) {
    t = taset->tracts[n];       /* traverse the transactions and */
    p = t->items;               /* the items of each transaction */
    for (i = k = 0; i < t->cnt; i++) {
      x = map[p[i]];            /* recode the items and */
      if (x < cnt) p[k++] = x;  /* remove superfluous items */
    }                           /* from the transaction */
    if (k > taset->max)         /* update the max. transaction size */
      taset->max = k;           /* with the new size of the t.a. */
    taset->total += k;          /* sum the number of items */
    ta_sort(t->items, t->cnt = k);
  }                             /* resort the item identifiers */
}  /* tas_recode() */

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

int tas_filter (TASET *taset, const char *marks)
{                               /* --- filter items in a trans. set */
  int   i, max = 0;             /* loop variable, max. num. of items */
  TRACT *t;                     /* to traverse the transactions */

  assert(taset && marks);       /* check the function arguments */
  taset->total = 0;             /* clear the total number of items */
  for (i = taset->cnt; --i >= 0; ) {
    t = taset->tracts[i];       /* traverse the transactions */
    t->cnt = ta_filter(t->items, t->cnt, marks);
    if (t->cnt > max) max = t->cnt;
    taset->total += t->cnt;     /* filter each transaction and */
  }                             /* update maximal size and total */
  return max;                   /* return maximum number of items */
}  /* tas_filter() */

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

void tas_sort (TASET *taset, int heap)
{                               /* --- sort a transaction set */
  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);
}  /* tas_sort() */

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

int tas_occur (TASET *taset, const int *items, int n)
{                               /* --- count transaction occurrences */
  int l, r, m, k = taset->cnt;  /* index variables */

  assert(taset && items);       /* check the function arguments */
  for (r = m = 0; r < k; ) {    /* find right boundary */
    m = (r + k) >> 1;           /* by a binary search */
    if (ta_cmpx(taset->tracts[m], items, n) > 0) k = m;
    else                                         r = m+1;
  }
  for (l = m = 0; l < k; ) {    /* find left boundary */
    m = (l + k) >> 1;           /* by a binary search */
    if (ta_cmpx(taset->tracts[m], items, n) < 0) l = m+1;
    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