开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > 数值算法/人工智能 > 人工智能/神经网络 > 查看源码
istree.c
资源名称：apriori(c).zip　[点击查看]
上传用户：lengbin
上传日期：2010-03-31
资源大小：121k
文件大小：69k
源码类别：

人工智能/神经网络

开发平台：

C/C++

istree.c：源码内容
  1. /*----------------------------------------------------------------------
  2.   File    : istree.c
  3.   Contents: item set tree management
  4.   Author  : Christian Borgelt
  5.   History : 22.01.1996 file created
  6.             07.02.1996 _child, _count, ist_addlvl, and ist_count
  7.             09.02.1996 ist_rule programmed and debugged
  8.             10.02.1996 empty rule bodies made optional
  9.             28.03.1996 support made relative to number of item sets
  10.             25.06.1996 function _count optimized
  11.             23.11.1996 rule extraction redesigned
  12.             24.11.1996 rule selection criteria added
  13.             18.08.1997 normalized chi^2 measure added
  14.                        parameter minlen added to function ist_init()
  15.             15.01.1998 confidence comparison changed to >=
  16.             23.01.1998 integer support computation changed (ceil)
  17.             26.01.1998 condition added to set extension in _child
  18.             10.02.1998 bug in computation of EM_INFO fixed
  19.             11.02.1998 parameter 'minval' added to function ist_init()
  20.             14.05.1998 item set tree navigation functions added
  21.             08.08.1998 item appearances considered for rule selection
  22.             20.08.1998 deferred child node vector allocation added
  23.             02.09.1998 several assertions added
  24.             05.09.1998 bug concerning node id fixed
  25.             07.09.1998 function ist_hedge added
  26.             22.09.1998 bug in rule extraction (item appearances) fixed
  27.             23.09.1998 computation of chi^2 measure simplified
  28.             05.02.1999 long int changed to int
  29.             25.08.1999 rule extraction simplified
  30.             05.11.1999 rule evaluation measure EM_AIMP added
  31.             08.11.1999 parameter 'aval' added to function ist_rule
  32.             11.11.1999 rule consequents moved to first field
  33.             01.12.1999 bug in node reallocation fixed
  34.             01.04.2001 functions ist_set and ist_getcntx added,
  35.                        functions _count and _getsupp improved
  36.             28.12.2001 sort function moved to module tract
  37.             07.02.2002 tree clearing removed, counting improved
  38.             08.02.2002 child creation improved (check of body support)
  39.             10.02.2002 IST_IGNORE bugs fixed (ist_set and ist_hedge)
  40.             11.02.2002 memory usage minimization option added
  41.             12.02.2002 ist_first and ist_last replaced by ist_next
  42.             19.02.2002 transaction tree functions added
  43.             09.10.2002 bug in function ist_hedge fixed (conf. comp.)
  44.             12.03.2003 parameter lift added to function ist_rule
  45.             17.07.2003 check of item usage added (function ist_check)
  46.             18.07.2003 maximally frequent item set filter added
  47.             11.08.2003 item set filtering generalized (ist_filter)
  48.             15.08.2003 renamed new to cur in ist_addlvl (C++ compat.)
  49.             14.11.2003 definition of F_HDONLY changed to INT_MIN
  50.             02.12.2003 skipping unnecessary subtrees added (_stskip)
  51.             03.12.2003 bug in ist_check for rule mining fixed
  52.             12.12.2003 padding for 64 bit architecture added
  53.             09.05.2004 additional selection measure for sets added
  54.             09.12.2004 bug in add. evaluation measure for sets fixed
  55. ----------------------------------------------------------------------*/
  56. #include <stdio.h>
  57. #include <stdlib.h>
  58. #include <string.h>
  59. #include <limits.h>
  60. #include <float.h>
  61. #include <math.h>
  62. #include <assert.h>
  63. #include "istree.h"
  64. #ifdef STORAGE
  65. #include "storage.h"
  66. #endif
  68. /*----------------------------------------------------------------------
  69.   Preprocessor Definitions
  70. ----------------------------------------------------------------------*/
  71. #define LN_2       0.69314718055994530942   /* ln(2) */
  72. #define EPSILON    1e-12        /* to cope with roundoff errors */
  73. #define BLKSIZE    32           /* block size for level vector */
  74. #define F_HDONLY   INT_MIN      /* flag for head only item in path */
  75. #define F_SKIP     INT_MIN      /* flag for subtree skipping */
  76. #define ID(n)      ((int)((n)->id & ~F_HDONLY))
  77. #define HDONLY(n)  ((int)((n)->id &  F_HDONLY))
  79. /*----------------------------------------------------------------------
  80.   Type Definitions
  81. ----------------------------------------------------------------------*/
  82. typedef double EVALFN (double head, double body, double post);
  83. /* function to compute an additional evaluation measure */
  85. /*----------------------------------------------------------------------
  86.   Auxiliary Functions
  87. ----------------------------------------------------------------------*/
  89. static int _bsearch (int *vec, int n, int id)
  90. {                               /* --- binary search for an item */
  91.   int i, k;                     /* left and middle index */
  93.   assert(vec && (n > 0));       /* check the function arguments */
  94.   for (i = 0; i < n; ) {        /* while the range is not empty */
  95.     k = (i + n) >> 1;           /* get index of middle element */
  96.     if      (vec[k] > id) n = k;
  97.     else if (vec[k] < id) i = k+1;
  98.     else return k;              /* adapt range boundaries or return */
  99.   }                             /* the index the id. was found at */
  100.   return -1;                    /* return 'not found' */
  101. }  /* _bsearch() */
  103. /*--------------------------------------------------------------------*/
  105. static void _count (ISNODE *node, int *set, int cnt, int min)
  106. {                               /* --- count transaction recursively */
  107.   int    i;                     /* vector index */
  108.   int    *map, n;               /* identifier map and its size */
  109.   ISNODE **vec;                 /* child node vector */
  111.   assert(node                   /* check the function arguments */
  112.       && (cnt >= 0) && (set || (cnt <= 0)));
  113.   if (node->offset >= 0) {      /* if a pure vector is used */
  114.     if (node->chcnt == 0) {     /* if this is a new node */
  115.       n = node->offset;         /* get the index offset */
  116.       while ((cnt > 0) && (*set < n)) {
  117.         cnt--; set++; }         /* skip items before first counter */
  118.       while (--cnt >= 0) {      /* traverse the transaction's items */
  119.         i = *set++ -n;          /* compute counter vector index */
  120.         if (i >= node->size) return;
  121.         node->cnts[i]++;        /* if the counter exists, */
  122.       } }                       /* count the transaction */
  123.     else if (node->chcnt > 0) { /* if there are child nodes */
  124.       vec = (ISNODE**)(node->cnts +node->size);
  125.       n   = ID(vec[0]);         /* get the child node vector */
  126.       min--;                    /* one item less to the deepest nodes */
  127.       while ((cnt > min) && (*set < n)) {
  128.         cnt--; set++; }         /* skip items before first child */
  129.       while (--cnt >= min) {    /* traverse the transaction's items */
  130.         i = *set++ -n;          /* compute child vector index */
  131.         if (i >= node->chcnt) return;
  132.         if (vec[i]) _count(vec[i], set, cnt, min);
  133.       }                         /* if the child exists, */
  134.     } }                         /* count the transaction recursively */
  135.   else {                        /* if an identifer map is used */
  136.     map = node->cnts +(n = node->size);
  137.     if (node->chcnt == 0) {     /* if this is a new node */
  138.       while (--cnt >= 0) {      /* traverse the transaction's items */
  139.         if (*set > map[n-1]) return;  /* if beyond last item, abort */
  140.         i = _bsearch(map, n, *set++);
  141.         if (i >= 0) node->cnts[i]++;
  142.       } }                       /* find index and count transaction */
  143.     else if (node->chcnt > 0) { /* if there are child nodes */
  144.       vec = (ISNODE**)(map +n); /* get id. map and child vector */
  145.       if (node->chcnt < n)      /* if a secondary id. map exists */
  146.         map = (int*)(vec +(n = node->chcnt));
  147.       min--;                    /* one item less to the deepest nodes */
  148.       while (--cnt >= min) {    /* traverse the transaction's items */
  149.         if (*set > map[n-1]) return;  /* if beyond last item, abort */
  150.         i = _bsearch(map, n, *set++);
  151.         if ((i >= 0) && vec[i]) _count(vec[i], set, cnt, min);
  152.       }                         /* search for the proper index */
  153.     }                           /* and if the child exists, */
  154.   }                             /* count the transaction recursively */
  155. }  /* _count() */
  157. /*--------------------------------------------------------------------*/
  159. static void _countx (ISNODE *node, TATREE *tat, int min)
  160. {                               /* --- count t.a. tree recursively */
  161.   int    i, k;                  /* vector index, loop variable */
  162.   int    *map, n;               /* identifier map and its size */
  163.   ISNODE **vec;                 /* child node vector */
  165.   assert(node && tat);          /* check the function arguments */
  166.   if (tat_max(tat) < min)       /* if the transactions are too short, */
  167.     return;                     /* abort the recursion */
  168.   k = tat_size(tat);            /* get the number of children */
  169.   if (k <= 0) {                 /* if there are no children */
  170.     if (k < 0) _count(node, tat_items(tat), -k, min);
  171.     return;                     /* count the normal transaction */
  172.   }                             /* and abort the function */
  173.   while (--k >= 0)              /* count the transactions recursively */
  174.     _countx(node, tat_child(tat, k), min);
  175.   if (node->offset >= 0) {      /* if a pure vector is used */
  176.     if (node->chcnt == 0) {     /* if this is a new node */
  177.       n = node->offset;         /* get the index offset */
  178.       for (k = tat_size(tat); --k >= 0; ) {
  179.         i = tat_item(tat,k) -n; /* traverse the items */
  180.         if (i < 0) return;      /* if before first item, abort */
  181.         if (i < node->size)     /* if inside the counter range */
  182.           node->cnts[i] += tat_cnt(tat_child(tat, k));
  183.       } }                       /* count the transaction */
  184.     else if (node->chcnt > 0) { /* if there are child nodes */
  185.       vec = (ISNODE**)(node->cnts +node->size);
  186.       n   = ID(vec[0]);         /* get the child node vector */
  187.       min--;                    /* one item less to the deepest nodes */
  188.       for (k = tat_size(tat); --k >= 0; ) {
  189.         i = tat_item(tat,k) -n; /* traverse the items */
  190.         if (i < 0) return;      /* if before first item, abort */
  191.         if ((i < node->chcnt) && vec[i])
  192.           _countx(vec[i], tat_child(tat, k), min);
  193.       }                         /* if the child exists, */
  194.     } }                         /* count the transaction recursively */
  195.   else {                        /* if an identifer map is used */
  196.     map = node->cnts +(n = node->size);
  197.     if (node->chcnt == 0) {     /* if this is a new node */
  198.       for (k = tat_size(tat); --k >= 0; ) {
  199.         i = tat_item(tat, k);   /* get the next item */
  200.         if (i < map[0]) return; /* if before first item, abort */
  201.         i = _bsearch(map, n, i);
  202.         if (i >= 0) node->cnts[i] += tat_cnt(tat_child(tat, k));
  203.       } }                       /* find index and count transaction */
  204.     else if (node->chcnt > 0) { /* if there are child nodes */
  205.       vec = (ISNODE**)(map +n); /* get id. map and child vector */
  206.       if (node->chcnt < n)      /* if a secondary id. map exists */
  207.         map = (int*)(vec +(n = node->chcnt));
  208.       min--;                    /* one item less to the deepest nodes */
  209.       for (k = tat_size(tat); --k >= 0; ) {
  210.         i = tat_item(tat, k);   /* get the next item */
  211.         if (i < map[0]) return; /* if before first item, abort */
  212.         i = _bsearch(map, n, i);
  213.         if ((i >= 0) && vec[i]) _countx(vec[i], tat_child(tat, k), min);
  214.       }                         /* search for the proper index */
  215.     }                           /* and if the child exists, */
  216.   }                             /* count the transaction recursively */
  217. }  /* _countx() */
  219. /*--------------------------------------------------------------------*/
  221. static int _stskip (ISNODE *node)
  222. {                               /* --- set subtree skip flags */
  223.   int    i, r;                  /* vector index, result */
  224.   ISNODE **vec;                 /* child node vector */
  226.   assert(node);                 /* check the function argument */
  227.   if (node->chcnt  == 0) return  0;  /* do not skip new leaves */
  228.   if (node->chcnt  <  0) return -1;  /* skip marked subtrees */
  229.   if (node->offset >= 0)        /* if a pure vector is used */
  230.     vec = (ISNODE**)(node->cnts +node->size);
  231.   else                          /* if an identifer map is used */
  232.     vec = (ISNODE**)(node->cnts +node->size +node->size);
  233.   for (r = -1, i = node->chcnt; --i >= 0; )
  234.     if (vec[i]) r &= _stskip(vec[i]);
  235.   if (!r) return 0;             /* recursively check all children */
  236.   node->chcnt |= F_SKIP;        /* set the skip flag if possible */
  237.   return -1;                    /* return 'skip subtree' */
  238. }  /* _stskip() */
  240. /*--------------------------------------------------------------------*/
  242. static int _check (ISNODE *node, char *marks, int supp)
  243. {                               /* --- recursively check item usage */
  244.   int    i, r = 0;              /* vector index, result of check */
  245.   int    *map, n;               /* identifier map and its size */
  246.   ISNODE **vec;                 /* child node vector */
  248.   assert(node && marks);        /* check the function arguments */
  249.   if (node->offset >= 0) {      /* if a pure vector is used */
  250.     if (node->chcnt == 0) {     /* if this is a new node */
  251.       n = node->offset;         /* get the index offset */
  252.       for (i = node->size; --i >= 0; ) {
  253.         if (node->cnts[i] >= supp)
  254.           marks[n+i] = r = 1;   /* mark items in set that satisfies */
  255.       } }                       /* the minimum support criterion */
  256.     else if (node->chcnt > 0) { /* if there are child nodes */
  257.       vec = (ISNODE**)(node->cnts +node->size);
  258.       for (i = node->chcnt; --i >= 0; )
  259.         if (vec[i]) r |= _check(vec[i], marks, supp);
  260.     } }                         /* recursively process all children */
  261.   else {                        /* if an identifer map is used */
  262.     map = node->cnts +node->size;
  263.     if (node->chcnt == 0) {     /* if this is a new node */
  264.       for (i = node->size; --i >= 0; ) {
  265.         if (node->cnts[i] >= supp)
  266.           marks[map[i]] = r = 1;/* mark items in set that satisfies */
  267.       } }                       /* the minimum support criterion */
  268.     else if (node->chcnt > 0) { /* if there are child nodes */
  269.       vec = (ISNODE**)(map +node->size);
  270.       for (i = node->chcnt; --i >= 0; )
  271.         if (vec[i]) r |= _check(vec[i], marks, supp);
  272.     }                           /* get the child vector and */
  273.   }                             /* recursively process all children */
  274.   if ((r != 0) && node->parent) /* if the check succeeded, mark */
  275.     marks[ID(node)] = 1;        /* the item associated with the node */
  276.   return r;                     /* return the check result */
  277. }  /* _check() */
  279. /*--------------------------------------------------------------------*/
  281. static int _getsupp (ISNODE *node, int *set, int cnt)
  282. {                               /* --- get support of an item set */
  283.   int    i, n, c;               /* vector index, buffers */
  284.   int    *map;                  /* identifier map */
  285.   ISNODE **vec;                 /* vector of child nodes */
  287.   assert(node && set && (cnt >= 0)); /* check the function arguments */
  288.   while (--cnt > 0) {           /* follow the set/path from the node */
  289.     c = node->chcnt & ~F_SKIP;  /* if there are no children, */
  290.     if (c <= 0) return -1;      /* the support is less than minsupp */
  291.     if (node->offset >= 0) {    /* if a pure vector is used */
  292.       vec = (ISNODE**)(node->cnts +node->size);
  293.       i   = *set++ -ID(vec[0]); /* compute the child vector index and */
  294.       if (i >= c) return -1; }  /* abort if the child does not exist */
  295.     else {                      /* if an identifier map is used */
  296.       map = node->cnts +(n = node->size);
  297.       vec = (ISNODE**)(map +n); /* get id. map and child vector */
  298.       if (c < n)                /* if a secondary id. map exists, */
  299.         map = (int*)(vec +(n = c));    /* get this identifier map */
  300.       i = _bsearch(map, n, *set++);
  301.     }                           /* search for the proper index */
  302.     if (i < 0) return -1;       /* abort if index is out of range */
  303.     node = vec[i];              /* go to the corresponding child */
  304.     if (!node) return -1;       /* if the child does not exists, */
  305.   }                             /* the support is less than minsupp */
  306.   if (node->offset >= 0) {      /* if a pure vector is used, */
  307.     i = *set -node->offset;     /* compute the counter index */
  308.     if (i >= node->size) return -1; }
  309.   else {                        /* if an identifier map is used */
  310.     map = node->cnts +(n = node->size);
  311.     i   = _bsearch(map, n, *set);
  312.   }                             /* search for the proper index */
  313.   if (i < 0) return -1;         /* abort if index is out of range */
  314.   return node->cnts[i];         /* return the item set support */
  315. }  /* _getsupp() */
  317. /*--------------------------------------------------------------------*/
  319. static void _clrsupp (ISNODE *node, int *set, int cnt, int supp)
  320. {                               /* --- clear support of an item set */
  321.   int    i, n, c;               /* vector index, buffers */
  322.   int    *map;                  /* identifier map */
  323.   ISNODE **vec;                 /* vector of child nodes */
  325.   assert(node && set && (cnt >= 0)); /* check the function arguments */
  326.   while (--cnt > 0) {           /* follow the set/path from the node */
  327.     if (node->offset >= 0) {    /* if a pure vector is used */
  328.       vec = (ISNODE**)(node->cnts +node->size);
  329.       i   = *set++ -ID(vec[0]);}/* compute the child vector index */
  330.     else {                      /* if an identifier map is used */
  331.       map = node->cnts +(n = node->size);
  332.       vec = (ISNODE**)(map +n); /* get id. map, child vector and */
  333.       c   = node->chcnt & ~F_SKIP;     /* the number of children */
  334.       if (c < n)                /* if a secondary id. map exists, */
  335.         map = (int*)(vec +(n = c));    /* get this identifier map */
  336.       i = _bsearch(map, n, *set++);
  337.     }                           /* search for the proper index */
  338.     node = vec[i];              /* go to the corresponding child */
  339.   }
  340.   if (node->offset >= 0)        /* if a pure vector is used, */
  341.     i = *set -node->offset;     /* compute the counter index */
  342.   else {                        /* if an identifier map is used */
  343.     map = node->cnts +(n = node->size);
  344.     i   = _bsearch(map, n, *set);
  345.   }                             /* search for the proper index */
  346.   if ((supp < 0)                /* if to clear unconditionally */
  347.   ||  (node->cnts[i] == supp))  /* or the support is the same */
  348.     node->cnts[i] = -(node->cnts[i] & ~F_SKIP);
  349. }  /* _clrsupp() */             /* clear the item set support */
  351. /*--------------------------------------------------------------------*/
  353. static ISNODE* _child (ISTREE *ist, ISNODE *node, int index,
  354.                        int s_min, int s_sub)
  355. {                               /* --- create child node (extend set) */
  356.   int    i, k, n;               /* loop variables, counters */
  357.   ISNODE *curr;                 /* to traverse the path to the root */
  358.   int    item, cnt;             /* item identifier, number of items */
  359.   int    *set;                  /* next (partial) item set to check */
  360.   int    body;                  /* enough support for a rule body */
  361.   int    hdonly;                /* whether head only item on path */
  362.   int    app;                   /* appearance flags of an item */
  363.   int    s_set;                 /* support of an item set */
  365.   assert(ist && node            /* check the function arguments */
  366.      && (index >= 0) && (index < node->size));
  367.   if (node->offset >= 0) item = node->offset +index;
  368.   else                   item = node->cnts[node->size +index];
  369.   app = ist->apps[item];        /* get item id. and appearance flag */
  370.   if ((app == IST_IGNORE)       /* do not extend an item to ignore */
  371.   ||  ((HDONLY(node) && (app == IST_HEAD))))
  372.     return NULL;                /* nor a set with two head only items */
  373.   hdonly = HDONLY(node) || (app == IST_HEAD);
  375.   /* --- initialize --- */
  376.   s_set = node->cnts[index];    /* get support of item set to extend */
  377.   if (s_set < s_min)            /* if set support is insufficient, */
  378.     return NULL;                /* no child is needed, so abort */
  379.   body = (s_set >= s_sub)       /* if the set has enough support for */
  380.        ? 1 : 0;                 /* a rule body, set the body flag */
  381.   ist->buf[ist->lvlvsz -2] = item;   /* init. set for support checks */
  383.   /* --- check candidates --- */
  384.   for (n = 0, i = index; ++i < node->size; ) {
  385.     if (node->offset >= 0) k = node->offset +i;
  386.     else                   k = node->cnts[node->size +i];
  387.     app = ist->apps[k];         /* traverse the candidate items */
  388.     if ((app == IST_IGNORE) || (hdonly && (app == IST_HEAD)))
  389.       continue;                 /* skip sets with two head only items */
  390.     s_set = node->cnts[i];      /* traverse the candidate items */
  391.     if (s_set <  s_min)         /* if set support is insufficient, */
  392.       continue;                 /* ignore the corresponding candidate */
  393.     body &= 1;                  /* restrict body flags to the set S */
  394.     if (s_set >= s_sub)         /* if set support is sufficient for */
  395.       body |= 2;                /* a rule body, set the body flag */ 
  396.     set    = ist->buf +ist->lvlvsz -(cnt = 2);
  397.     set[1] = k;                 /* add the candidate item to the set */
  398.     for (curr = node; curr->parent; curr = curr->parent) {
  399.       s_set = _getsupp(curr->parent, set, cnt);
  400.       if (s_set <  s_min)       /* get the item set support and */
  401.         break;                  /* if it is too low, abort the loop */
  402.       if (s_set >= s_sub)       /* if some subset has enough support */
  403.         body |= 4;              /* for a rule body, set the body flag */
  404.       *--set = ID(curr); cnt++; /* add id of current node to the set */
  405.     }                           /* and adapt the number of items */
  406.     if (!curr->parent && body)  /* if subset support is high enough */
  407.       ist->map[n++] = k;        /* for a full rule and a rule body, */
  408.   }                             /* note the item identifier */
  409.   if (n <= 0) return NULL;      /* if no child is needed, abort */
  410.   #ifdef BENCH                  /* if benchmark version: */
  411.   ist->nec += n;                /* sum the necessary counters */
  412.   #endif
  414.   /* --- decide on node structure --- */
  415.   k = ist->map[n-1] -ist->map[0] +1;
  416.   if    (!ist->memopt) n = k;   /* check the size of a pure vector */
  417.   else if (3*n >= 2*k) n = k;   /* use a pure vector if it is small */
  418.   else                 k = n+n; /* enough, otherwise use an id. map */
  419.   #ifdef ARCH64                 /* if 64 bit architecture */
  420.   if ((n == k) && (k & 1)) n = ++k;
  421.   #endif                        /* pad to even number of counters */
  422.   #ifdef BENCH                  /* if benchmark version */
  423.   ist->cnt   += n;              /* sum the number of counters */
  424.   ist->bytes += sizeof(ISNODE) +(k-1) *sizeof(int) +8;
  425.   #endif                        /* determine the memory usage */
  427.   /* --- create child --- */
  428.   curr = (ISNODE*)malloc(sizeof(ISNODE) +(k-1) *sizeof(int));
  429.   if (!curr) return (void*)-1;  /* create a child node */
  430.   curr->parent = node;          /* set pointer to parent node */
  431.   curr->succ   = NULL;          /* and clear successor pointer */
  432.   curr->id     = item;          /* initialize the item id. and */
  433.   if (hdonly) curr->id |= F_HDONLY;  /* set the head only flag */
  434.   curr->chcnt  = 0;             /* there are no children yet */
  435.   curr->size   = n;             /* set size of counter vector */
  436.   if (n == k)                   /* if to use a pure vector, */
  437.     curr->offset = ist->map[0]; /* note the first item as an offset */
  438.   else {                        /* if to use an identifier map, */
  439.     curr->offset = -1;          /* use the offset as an indicator */
  440.     for (set = curr->cnts +n +(i = n); --i >= 0; )
  441.       *--set = ist->map[i];     /* copy the identifier map */
  442.   }                             /* from the buffer to the node */
  443.   for (set = curr->cnts +(i = n); --i >= 0; )
  444.     *--set = 0;                 /* clear all counters of the node */
  445.   return curr;                  /* return pointer to created child */
  446. }  /* _child() */
  448. /*----------------------------------------------------------------------
  449.   In the above function the set S represented by the index-th vector
  450. element of the current node is extended only by combining it with the
  451. sets represented by the fields that follow it in the node vector,
  452. i.e. by the sets represented by vec[index+1] to vec[size-1]. The sets
  453. that can be formed by combining the set S and the sets represented by
  454. vec[0] to vec[index-1] are processed in the branches for these sets.
  455.   In the 'check candidates' loop it is checked for each set represented
  456. by vec[index+1] to vec[size-1] whether this set and all other subsets
  457. of the same size, which can be formed from the union of this set and
  458. the set S, have enough support, so that a child node is necessary.
  459.   Note that i +offset is the identifier of the item that has to be
  460. added to set S to form the union of the set S and the set T represented
  461. by vec[i], since S and T have the same path with the exception of the
  462. index in the current node. Hence we can speak of candidate items that
  463. are added to S.
  464.   Checking the support of the other subsets of the union of S and T
  465. that have the same size as S and T is done with the aid of a path
  466. variable. The items in this variable combined with the items on the
  467. path to the current node always represent the subset currently tested.
  468. That is, the path variable holds the path to be followed from the
  469. current node to arrive at the support counter for the subset. The path
  470. variable is initialized to [0]: <item>, [1]: <offset+i>, since the
  471. support counters for S and T can be inspected directly. Then this
  472. path is followed from the parent node of the current node, which is
  473. equivalent to checking the subset that can be obtained by removing
  474. from the union of S and T the item that corresponds to the parent node
  475. (in the path to S or T, resp.).
  476.   Iteratively making the parent node the current node, adding its
  477. corresponding item to the path and checking the support counter at the
  478. end of the path variable when starting from its (the new current node's)
  479. parent node tests all other subsets.
  480.   Another criterion is that the extended set must not contain two items
  481. which may appear only in the head of a rule. If two such items are
  482. contained in a set, neither can a rule be formed from its items nor can
  483. it be the antecedent of a rule. Whether a set contains two head only
  484. items is determined from the nodes 'hdonly' flag and the appearance
  485. flags of the items.
  486. ----------------------------------------------------------------------*/
  488. static void _cleanup (ISTREE *ist)
  489. {                               /* --- clean up on error */
  490.   ISNODE *node, *t;             /* to traverse the nodes */
  492.   assert(ist);                  /* check the function argument */
  493.   for (node = ist->levels[ist->lvlcnt]; node; ) {
  494.     t = node; node = node->succ; free(t); }
  495.   ist->levels[ist->lvlcnt] = NULL; /* delete all created nodes */
  496.   for (node = ist->levels[ist->lvlcnt -1]; node; node = node->succ)
  497.     node->chcnt = 0;            /* clear the child node counters */
  498. }  /* _cleanup() */             /* of the deepest nodes in the tree */
  500. /*----------------------------------------------------------------------
  501.   Additional Evaluation Measure Functions
  502. ----------------------------------------------------------------------*/
  504. static double _none (double head, double body, double post)
  505. { return 1; }                   /* --- no add. evaluation measure */
  507. /*--------------------------------------------------------------------*/
  509. static double _diff (double head, double body, double post)
  510. { return fabs(post -head); }    /* --- absolute confidence difference */
  512. /*--------------------------------------------------------------------*/
  514. static double _quot (double head, double body, double post)
  515. {                               /* --- diff. of conf. quotient to 1 */
  516.   if (post > head) return 1 -head/post;
  517.   return (head <= 0) ? 0 : (1 -post/head);
  518. }  /* _quot() */
  520. /*--------------------------------------------------------------------*/
  522. static double _aimp (double head, double body, double post)
  523. {                               /* --- abs. diff. of improvement to 1 */
  524.   return (head <= 0) ? 0 : fabs(1 -post/head);
  525. }  /* _aimp() */
  527. /*--------------------------------------------------------------------*/
  529. static double _info (double head, double body, double post)
  530. {                               /* --- information diff. to prior */
  531.   double res, t;                /* result, temporary buffer */
  533.   if ((head < EPSILON) || (1-head < EPSILON)
  534.   ||  (body < EPSILON) || (1-body < EPSILON))
  535.     return 0;                   /* check for strict positivity */
  536.   post *= body; res = 0;        /* support of     head and     body */
  537.   if (post > 0) res += post *log(post /(   head  *   body));
  538.   t = body -post;               /* support of not head and     body */
  539.   if (t    > 0) res += t    *log(t    /((1-head) *   body));
  540.   t = head -post;               /* support of     head and not body */
  541.   if (t    > 0) res += t    *log(t    /(   head  *(1-body)));
  542.   t = 1-head -body +post;       /* support of not head and not body */
  543.   if (t    > 0) res += t    *log(t    /((1-head) *(1-body)));
  544.   return res/LN_2;              /* return information gain in bits */
  545. }  /* _info() */
  547. /*--------------------------------------------------------------------*/
  549. static double _chi2 (double head, double body, double post)
  550. {                               /* --- normalized chi^2 measure */
  551.   double t;                     /* temporary buffer */
  553.   if ((head < EPSILON) || (1-head < EPSILON)
  554.   ||  (body < EPSILON) || (1-body < EPSILON))
  555.     return 0;                   /* check for strict positivity */
  556.   t = (head -post) *body;       /* compute and return chi^2 measure */
  557.   return (t*t) / (head *(1-head) *body *(1-body));
  558. }  /* _chi2() */
  560. /*--------------------------------------------------------------------*/
  562. static EVALFN *_evalfns[EM_UNKNOWN] = {
  563.   /* EM_NONE  0 */  _none,      /* no additional evaluation measure */
  564.   /* EM_DIFF  1 */  _diff,      /* absolute confidence difference */
  565.   /* EM_QUOT  2 */  _quot,      /* difference of conf. quotient to 1 */
  566.   /* EM_AIMP  3 */  _aimp,      /* abs. diff. of improvement to 1 */
  567.   /* EM_INFO  4 */  _info,      /* information difference to prior */
  568.   /* EM_CHI2  5 */  _chi2,      /* normalized chi^2 measure */
  569. };                              /* table of evaluation functions */
  571. /*----------------------------------------------------------------------
  572.   Main Functions
  573. ----------------------------------------------------------------------*/
  575. ISTREE* ist_create (int itemcnt, double supp, double conf,
  576.                     int rsdef, const char *apps, int memopt)
  577. {                               /* --- create an item set tree */
  578.   ISTREE *ist;                  /* created item set tree */
  579.   ISNODE **lvl;                 /* vector of tree levels */
  580.   ISNODE *root;                 /* root node of the tree */
  581.   int    *buf, *map;            /* buffer vector, identifier map */
  582.   char   *a;                    /* to traverse appearances vector */
  583.   int    n;                     /* temporary buffer */
  585.   assert((itemcnt >= 0)         /* check the function arguments */
  586.       && (supp >= 0) && (supp <= 1) && (conf >= 0) && (conf <= 1));
  588.   /* --- allocate memory --- */ 
  589.   ist = (ISTREE*)malloc(sizeof(ISTREE) +(itemcnt-1) *sizeof(char));
  590.   if (!ist) return NULL;        /* allocate the tree body */
  591.   ist->levels = lvl = (ISNODE**)malloc(BLKSIZE *sizeof(ISNODE*));
  592.   if (!lvl) { free(ist); return NULL; }
  593.   ist->buf    = buf = (int*)    malloc(BLKSIZE *sizeof(int));
  594.   if (!buf) { free(lvl); free(ist); return NULL; }
  595.   ist->map    = map = (int*)    malloc(itemcnt *sizeof(int));
  596.   if (!map) { free(buf); free(lvl); free(ist); return NULL; }
  597.   #ifdef ARCH64                 /* if 64 bit architecture */
  598.   n = (itemcnt & 1) ? itemcnt+1 : itemcnt;
  599.   #else                         /* pad counters to even number */
  600.   n = itemcnt;                  /* on 32 bit systems, however, */
  601.   #endif                        /* use the number of items directly */
  602.   lvl[0] = ist->curr = root =   /* allocate a root node */
  603.     (ISNODE*)calloc(1, sizeof(ISNODE) +(n-1) *sizeof(int));
  604.   if (!root){ free(map); free(buf); free(lvl); free(ist); return NULL; }
  606.   /* --- initialize structures --- */
  607.   ist->lvlvsz  = BLKSIZE;       /* copy parameters to the structure */
  608.   ist->lvlcnt  = 1;    ist->tacnt = 0;
  609.   ist->supp    = supp; ist->conf  = conf;
  610.   ist->rsdef   = rsdef & IST_BOTH;
  611.   ist->memopt  = memopt;
  612.   #ifdef BENCH                  /* if benchmark version */
  613.   ist->cnt     = ist->nec   = itemcnt;
  614.   ist->chcnt   = ist->chnec = 0;
  615.   ist->bytes   = sizeof(ISTREE) +itemcnt *sizeof(char) +8
  616.                + BLKSIZE *sizeof(ISNODE*) +8
  617.                + BLKSIZE *sizeof(int) +8
  618.                + itemcnt *sizeof(int) +8;
  619.   #endif                        /* initialize the benchmark variables */
  620.   ist_init(ist, 1, EM_NONE, 1); /* initialize rule extraction */
  621.   root->parent = root->succ = NULL;
  622.   root->offset = root->id   = 0;
  623.   root->chcnt  = 0;             /* initialize the root node */
  624.   root->size   = n;
  625.   a = ist->apps;                /* copy item appearances */
  626.   if (apps) { while (--itemcnt >= 0) *a++ = *apps++ & IST_BOTH; }
  627.   else      { while (--itemcnt >= 0) *a++ = IST_BOTH;           }
  628.   return ist;                   /* return created item set tree */
  629. }  /* ist_create() */
  631. /*--------------------------------------------------------------------*/
  633. void ist_delete (ISTREE *ist)
  634. {                               /* --- delete an item set tree */
  635.   int    i;                     /* loop variables */
  636.   ISNODE *node, *t;             /* to traverse the nodes */
  638.   assert(ist);                  /* check the function argument */
  639.   for (i = ist->lvlcnt; --i >= 0; ) {
  640.     for (node = ist->levels[i]; node; ) {
  641.       t = node; node = node->succ; free(t); }
  642.   }                             /* delete all nodes, */
  643.   free(ist->levels);            /* the level vector, */
  644.   free(ist->map);               /* the identifier map, */
  645.   free(ist->buf);               /* the path buffer, */
  646.   free(ist);                    /* and the tree body */
  647. }  /* ist_delete() */
  649. /*--------------------------------------------------------------------*/
  651. void ist_count (ISTREE *ist, int *set, int cnt)
  652. {                               /* --- count transaction in tree */
  653.   assert(ist                    /* check the function arguments */
  654.      && (cnt >= 0) && (set || (cnt <= 0)));
  655.   if (cnt >= ist->lvlcnt)       /* recursively count transaction */
  656.     _count(ist->levels[0], set, cnt, ist->lvlcnt);
  657.   ist->tacnt++;                 /* increment the transaction counter */
  658. }  /* ist_count() */
  660. /*--------------------------------------------------------------------*/
  662. void ist_countx (ISTREE *ist, TATREE *tat)
  663. {                               /* --- count transaction in tree */
  664.   assert(ist && tat);           /* check the function arguments */
  665.   _countx(ist->levels[0], tat, ist->lvlcnt);
  666.   ist->tacnt = tat_cnt(tat);    /* recursively count the tree and */
  667. }  /* ist_countx() */           /* set the transaction counter */
  669. /*--------------------------------------------------------------------*/
  671. int ist_check (ISTREE *ist, char *marks)
  672. {                               /* --- check item usage */
  673.   int i, n;                     /* loop variable, number of items */
  675.   assert(ist);                  /* check the function argument */
  676.   for (i = ist->levels[0]->size; --i >= 0; )
  677.     marks[i] = 0;               /* clear the marker vector */
  678.   n = (ist->rsdef == IST_BOTH)  /* get the minimum support */
  679.     ? (int)ceil(ist->tacnt *ist->supp)
  680.     : (int)ceil(ist->tacnt *ist->supp *ist->conf);
  681.   _check(ist->levels[0], marks, n);  /* check the item usage */
  682.   for (n = 0, i = ist->levels[0]->size; --i >= 0; )
  683.     if (marks[i]) n++;          /* count used items */
  684.   return n;                     /* and return this number */
  685. }  /* ist_check() */
  687. /*--------------------------------------------------------------------*/
  689. int ist_addlvl (ISTREE *ist)
  690. {                               /* --- add a level to item set tree */
  691.   int    i, n, c;               /* loop variable, counter, buffer */
  692.   ISNODE **ndp;                 /* to traverse the nodes */
  693.   ISNODE *node;                 /* new (reallocated) node */
  694.   ISNODE **end;                 /* end of new level node list */
  695.   ISNODE *cur;                  /* current node in new level */
  696.   ISNODE *frst;                 /* first child of current node */
  697.   ISNODE *last;                 /* last  child of current node */
  698.   ISNODE **vec;                 /* child node vector */
  699.   int    *map;                  /* identifier map */
  700.   int    s_min;                 /* minimal support of a set */
  701.   int    s_sub;                 /* minimal support of a subset */
  702.   void   *p;                    /* temporary buffer */
  704.   assert(ist);                  /* check the function arguments */
  706.   /* --- enlarge level vector --- */
  707.   if (ist->lvlcnt >= ist->lvlvsz) { /* if the level vector is full */
  708.     n = ist->lvlvsz +BLKSIZE;   /* compute new vector size */
  709.     p = realloc(ist->levels, n *sizeof(ISNODE*));
  710.     if (!p) return -1;          /* enlarge the level vector */
  711.     ist->levels = (ISNODE**)p;  /* and set the new vector */
  712.     p = realloc(ist->buf,    n *sizeof(int));
  713.     if (!p) return -1;          /* enlarge the buffer vector */
  714.     ist->buf    = (int*)p;      /* and set the new vector */
  715.     ist->lvlvsz = n;            /* set the new vector size */
  716.   }                             /* (applies to buf and levels) */
  717.   end  = ist->levels +ist->lvlcnt;
  718.   *end = NULL;                  /* start a new tree level */
  720.   /* --- add tree level --- */
  721.   s_sub = (int)ceil(ist->tacnt *ist->supp); /* minimal subset support */
  722.   s_min = (ist->rsdef == IST_BOTH) ? s_sub  /* minimal rule   support */
  723.         : (int)ceil(ist->tacnt *ist->supp *ist->conf);
  724.   for (ndp = ist->levels +ist->lvlcnt -1; *ndp; ndp = &(*ndp)->succ) {
  725.     frst = last = NULL;         /* traverse the deepest nodes */
  726.     for (i = n = 0; i < (*ndp)->size; i++) {
  727.       cur = _child(ist, *ndp, i, s_min, s_sub);
  728.       if (!cur) continue;       /* create a child if necessary */
  729.       if (cur == (void*)-1) { _cleanup(ist); return -1; }
  730.       if (!frst) frst = cur;    /* note first and last child node */
  731.       *end = last = cur;        /* add node at the end of the list */
  732.       end  = &cur->succ; n++;   /* that contains the new level */
  733.     }                           /* and advance end pointer */
  734.     if (n <= 0) {               /* if no child node was created, */
  735.       (*ndp)->chcnt = F_SKIP; continue; }       /* skip the node */
  736.     #ifdef BENCH                /* if benchmark version */
  737.     ist->chnec += n;            /* sum the number of necessary */
  738.     #endif                      /* child pointers */
  739.     node = *ndp;                /* decide on the node structure: */
  740.     if (node->offset >= 0) {    /* if a pure counter vector is used, */
  741.       n = ID(last)-ID(frst)+1;  /* always add a pure child vector */
  742.       i = (node->size -1) *sizeof(int) +n *sizeof(ISNODE*); }
  743.     else if (2*n > node->size){ /* if a single id. map is best, */
  744.       n = node->size;           /* only add a child vector */
  745.       i = (n+n-1) *sizeof(int) +n *sizeof(ISNODE*); }
  746.     else {                      /* if two identifier maps are best, */
  747.       i = node->size;           /* add a child vector and a map */
  748.       i = (i+i-1) *sizeof(int) +n *(sizeof(ISNODE*) +sizeof(int));
  749.     }                           /* get size of additional vectors */
  750.     node = (ISNODE*)realloc(node, sizeof(ISNODE) +i);
  751.     if (!node) { _cleanup(ist); return -1; }
  752.     node->chcnt = n;            /* add a child vector to the node */
  753.     #ifdef BENCH                /* if benchmark version */
  754.     ist->chcnt += n;            /* sum the number of child pointers */
  755.     if ((node->offset >= 0) || (node->size == n))
  756.          ist->bytes += n * sizeof(ISNODE*);
  757.     else ist->bytes += n *(sizeof(ISNODE*) +sizeof(int));
  758.     #endif                      /* determine the memory usage */
  759.     if ((node != *ndp) && node->parent) {
  760.       last = node->parent;      /* adapt the ref. from the parent */
  761.       if (last->offset >= 0) {  /* if a pure vector is used */
  762.         vec = (ISNODE**)(last->cnts +last->size);
  763.         vec[(vec[0] != *ndp) ? ID(node) -ID(vec[0]) : 0] = node; }
  764.       else {                    /* if an identifier map is used */
  765.         map = last->cnts +(i = last->size);
  766.         vec = (ISNODE**)(map+i);/* get identifier map, child vector, */
  767.         c   = last->chcnt & ~F_SKIP;   /* and the number of children */
  768.         if (c < i)              /* if a secondary id. map exists, */
  769.           map = (int*)(vec +(i = c));  /* get this identifier map */
  770.         vec[_bsearch(map, i, node->id)] = node;
  771.       }                         /* find the proper index and */
  772.     }                           /* set the new child pointer */
  773.     *ndp = node;                /* set new (reallocated) node */
  774.     if (node->offset >= 0) {    /* if to use pure vectors */
  775.       vec = (ISNODE**)(node->cnts +node->size);
  776.       while (--n >= 0) vec[n] = NULL;
  777.       i = ID(frst);             /* get item identifier of first child */
  778.       for (cur = frst; cur; cur = cur->succ) {
  779.         vec[ID(cur)-i] = cur;   /* set the child node pointer */
  780.         cur->parent    = node;  /* and the parent pointer */
  781.       } }                       /* in the new node */
  782.     else if (n < node->size) {  /* if two identifier maps are used */
  783.       vec = (ISNODE**)(node->cnts +node->size +node->size);
  784.       map = (int*)(vec +n);     /* get the secondary identifier map */
  785.       for (i = 0, cur = frst; cur; cur = cur->succ) {
  786.         vec[i]      = cur;      /* set the child node pointer, */
  787.         map[i++]    = cur->id;  /* the identifier map entry, */
  788.         cur->parent = node;     /* and the parent pointer */
  789.       } }                       /* in the new node */
  790.     else {                      /* if one identifier map is used */
  791.       map = node->cnts +(i = node->size);
  792.       vec = (ISNODE**)(map +i); /* get id. map and child vector */
  793.       while (--n >= 0) vec[n] = NULL;
  794.       for (cur = frst; cur; cur = cur->succ) {
  795.         vec[_bsearch(map, i, cur->id)] = cur;
  796.         cur->parent = node;     /* set the child node pointer */
  797.       }                         /* and the parent pointer */
  798.     }                           /* in the new node */
  799.   }
  800.   if (!ist->levels[ist->lvlcnt])/* if no child has been added, */
  801.     return 1;                   /* abort the function, otherwise */
  802.   ist->lvlcnt++;                /* increment the level counter */
  803.   ist->tacnt = 0;               /* clear the transaction counter and */
  804.   ist->node  = NULL;            /* the item set node for rule extr. */
  805.   _stskip(ist->levels[0]);      /* mark subtrees to be skipped */
  806.   return 0;                     /* return 'ok' */
  807. }  /* ist_addlvl() */
  809. /*--------------------------------------------------------------------*/
  811. void ist_up (ISTREE *ist, int root)
  812. {                               /* --- go up in item set tree */
  813.   assert(ist && ist->curr);     /* check the function argument */
  814.   if      (root)                /* if root flag set, */
  815.     ist->curr = ist->levels[0]; /* go to the root node */
  816.   else if (ist->curr->parent)   /* if it exists, go to the parent */
  817.     ist->curr = ist->curr->parent;
  818. }  /* ist_up() */
  820. /*--------------------------------------------------------------------*/
  822. int ist_down (ISTREE *ist, int item)
  823. {                               /* --- go down in item set tree */
  824.   ISNODE *node;                 /* the current node */
  825.   ISNODE **vec;                 /* child node vector of current node */
  826.   int    *map, n;               /* identifier map and its size */
  827.   int    c;                     /* number of children */
  829.   assert(ist && ist->curr);     /* check the function argument */
  830.   node = ist->curr;             /* get the current node */
  831.   c = node->chcnt & ~F_SKIP;    /* if there are no child nodes, */
  832.   if (c <= 0) return -1;        /* abort the function */
  833.   if (node->offset >= 0) {      /* if a pure vector is used */
  834.     vec = (ISNODE**)(node->cnts +node->size);
  835.     item -= ID(vec[0]);         /* compute index in child node vector */
  836.     if (item >= c) return -1; } /* and abort if there is no child */
  837.   else {                        /* if an identifier map is used */
  838.     map = node->cnts +(n = node->size);
  839.     vec = (ISNODE**)(map +n);   /* get id. map and child vector */
  840.     if (c < n)                  /* if a secondary id. map exists, */
  841.       map = (int*)(vec +(n = c));      /* get this identifier map */
  842.     item = _bsearch(map, n, item);
  843.   }                             /* search for the proper index */
  844.   if ((item < 0) || !vec[item]) /* if the index is out of range */
  845.     return -1;                  /* or the child does not exist, abort */
  846.   ist->curr = vec[item];        /* otherwise go to the child node */
  847.   return 0;                     /* return 'ok' */
  848. }  /* ist_down() */
  850. /*--------------------------------------------------------------------*/
  852. int ist_next (ISTREE *ist, int item)
  853. {                               /* --- get next item with a counter */
  854.   int    i;                     /* vector index */
  855.   ISNODE *node;                 /* the current node */
  856.   int    *map, n;               /* identifier map and its size */
  858.   assert(ist && ist->curr);     /* check the function argument */
  859.   node = ist->curr;             /* get the current node */
  860.   if (node->offset >= 0) {      /* if a pure vector is used, */
  861.     if (item <  node->offset) return node->offset;
  862.     if (item >= node->offset +node->size) return -1;
  863.     return item +1; }           /* return the next item identifier */
  864.   else {                        /* if an identifier map is used */
  865.     map = node->cnts +(n = node->size);
  866.     if (item <  map[0])   return map[0];
  867.     if (item >= map[n-1]) return -1;
  868.     i = _bsearch(map, n, item); /* try to find the item directly */
  869.     if (i >= 0) return map[i+1];/* and return the following one */
  870.     while ((--n >= 0) && (*map > item)) map++;
  871.     return (n >= 0) ? *map :-1; /* search iteratively for the next */
  872.   }                             /* item identifier and return it */
  873. }  /* ist_next() */
  875. /*--------------------------------------------------------------------*/
  877. void ist_setcnt (ISTREE *ist, int item, int cnt)
  878. {                               /* --- set counter for an item */
  879.   ISNODE *node;                 /* the current node */
  880.   ISNODE **vec;                 /* child node vector of current node */
  881.   int    *map, n;               /* identifier map and its size */
  882.   int    c;                     /* number of children */
  884.   assert(ist && ist->curr);     /* check the function argument */
  885.   node = ist->curr;             /* get the current node */
  886.   if (node->offset >= 0) {      /* if a pure vector is used, */
  887.     item -= node->offset;       /* get index in counter vector */
  888.     if (item >= node->size) return; }
  889.   else {                        /* if an identifier map is used */
  890.     map = node->cnts +(n = node->size);
  891.     vec = (ISNODE**)(map +n);   /* get id. map and child vector */
  892.     c = node->chcnt & ~F_SKIP;  /* and the number of children */
  893.     if (c < n)                  /* if a secondary id. map exists, */
  894.       map = (int*)(vec +(n = c));      /* get this identifier map */
  895.     item = _bsearch(map, n, item);
  896.   }                             /* search for the proper index */
  897.   if (item >= 0) node->cnts[item] = cnt;
  898. }  /* ist_setcnt() */           /* set the frequency counter */
  900. /*--------------------------------------------------------------------*/
  902. int ist_getcnt (ISTREE *ist, int item)
  903. {                               /* --- get counter for an item */
  904.   ISNODE *node;                 /* the current node */
  905.   ISNODE **vec;                 /* child node vector of current node */
  906.   int    *map, n;               /* identifier map and its size */
  907.   int    c;                     /* number of children */
  909.   assert(ist && ist->curr);     /* check the function argument */
  910.   node = ist->curr;             /* get the current node */
  911.   if (node->offset >= 0) {      /* if pure vectors are used, */
  912.     item -= node->offset;       /* get index in counter vector */
  913.     if (item >= node->size) return -1; }
  914.   else {                        /* if an identifier map is used */
  915.     map = node->cnts +(n = node->size);
  916.     vec = (ISNODE**)(map +n);   /* get id. map and child vector */
  917.     c = node->chcnt & ~F_SKIP;  /* and the number of children */
  918.     if (c < n)                  /* if a secondary id. map exists, */
  919.       map = (int*)(vec +(n = c));      /* get this identifier map */
  920.     item = _bsearch(map, n, item);
  921.   }                             /* search for the proper index */
  922.   if (item < 0) return -1;      /* abort if index is out of range */
  923.   return node->cnts[item];      /* return the value of the counter */
  924. }  /* ist_getcnt() */
  926. /*--------------------------------------------------------------------*/
  928. int ist_getcntx (ISTREE *ist, int *set, int cnt)
  929. {                               /* --- get counter for an item set */
  930.   assert(ist                    /* check the function arguments */
  931.      && (cnt >= 0) && (set || (cnt <= 0)));
  932.   if (cnt <= 0)                 /* if the item set is empty, */
  933.     return ist->tacnt;          /* return the transaction count */
  934.   return _getsupp(ist->levels[0], set, cnt);
  935. }  /* ist_getcntx() */          /* return the item set support */
  937. /*--------------------------------------------------------------------*/
  939. void ist_filter (ISTREE *ist, int mode)
  940. {                               /* --- filter max. freq. item sets */
  941.   int    i, k, n;               /* loop variables */
  942.   ISNODE *node, *curr;          /* to traverse the nodes */
  943.   int    s_min, supp;           /* (minimum) support of an item set */
  944.   int    *set;                  /* next (partial) item set to process */
  946.   assert(ist);                  /* check the function argument */
  947.   s_min = (int)ceil(ist->tacnt *ist->supp);
  948.   if (s_min <= 0) s_min = 1;    /* get minimal support */
  949.   for (n = 1; n < ist->lvlcnt; n++) {
  950.     for (node = ist->levels[n]; node; node = node->succ) {
  951.       for (i = 0; i < node->size; i++) {
  952.         if (node->cnts[i] < s_min)
  953.           continue;             /* skip infrequent item sets */
  954.         supp = (mode == IST_CLOSED) ? node->cnts[i] : -1;
  955.         if (node->offset >= 0) k = node->offset +i;
  956.         else                   k = node->cnts[node->size +i];
  957.         set    = ist->buf +ist->lvlvsz;
  958.         *--set = k;        _clrsupp(node->parent, set, 1, supp);
  959.         *--set = ID(node); _clrsupp(node->parent, set, 1, supp);
  960.         k = 2;                  /* clear counters in parent node */
  961.         for (curr = node->parent; curr->parent; curr = curr->parent) {
  962.           _clrsupp(curr->parent, set, k, supp);
  963.           *--set = ID(curr); k++;
  964.         }                       /* climb up the tree and use the */
  965.       }                         /* constructed (partial) item sets */
  966.     }                           /* as paths to find the counters */
  967.   }                             /* that have to be cleared */
  968. }  /* ist_filter() */
  970. /*--------------------------------------------------------------------*/
  972. void ist_init (ISTREE *ist, int minlen, int arem, double minval)
  973. {                               /* --- initialize (rule) extraction */
  974.   assert(ist                    /* check the function arguments */
  975.       && (minlen > 0) && (minval >= 0.0) && (minval <= 1.0));
  976.   ist->index = ist->item = -1;
  977.   ist->node  = ist->head = NULL;
  978.   ist->size  = minlen;          /* initialize rule extraction */
  979.   if ((arem < EM_NONE) || (arem >= EM_UNKNOWN))
  980.     arem = EM_NONE;             /* check, adapt, and note */
  981.   ist->arem   = arem;           /* additional evaluation measure */
  982.   ist->minval = minval;         /* and its minimal value */
  983. }  /* ist_init() */
  985. /*--------------------------------------------------------------------*/
  987. int ist_set (ISTREE *ist, int *set, double *supp, double *aval)
  988. {                               /* --- extract next frequent item set */
  989.   int    i;                     /* loop variable */
  990.   int    item;                  /* an item identifier */
  991.   ISNODE *node, *tmp;           /* current item set node, buffer */
  992.   int    *cnts;                 /* to access the item frequencies */
  993.   int    s_min;                 /* minimal support of a set */
  994.   int    s_set;                 /* support of the current set */
  995.   double dev;                   /* deviation from indep. occurrence */
  996.   double nrm;                   /* freq. normalization factor */
  998.   assert(ist && set && supp);   /* check the function arguments */
  1000.   /* --- initialize --- */
  1001.   if (ist->size > ist->lvlcnt)  /* if the tree is not high enough */
  1002.     return -1;                  /* for the item set size, abort */
  1003.   s_min = (int)ceil(ist->tacnt *ist->supp); /* get minimal support */
  1004.   if (!ist->node)               /* on first item set, initialize */
  1005.     ist->node = ist->levels[ist->size-1];    /* the current node */
  1006.   node = ist->node;             /* get the current item set node */
  1007.   nrm  = (ist->tacnt > 0)       /* compute the normalization factor */
  1008.        ? 1.0/ist->tacnt : 1.0;  /* for the item set support and */
  1009.   cnts = ist->levels[0]->cnts;  /* get the item frequency vector */
  1011.   /* --- find frequent item set --- */
  1012.   while (1) {                   /* search for a frequent item set */
  1013.     if (++ist->index >= node->size) { /* if all subsets have been */
  1014.       node = node->succ;        /* processed, go to the successor */
  1015.       if (!node) {              /* if at the end of a level, go down */
  1016.         if (++ist->size > ist->lvlcnt)
  1017.           return -1;            /* if beyond the deepest level, abort */
  1018.         node = ist->levels[ist->size -1];
  1019.       }                         /* get the 1st node of the new level */
  1020.       ist->node  = node;        /* note the new item set node */
  1021.       ist->index = 0;           /* start with the first item set */
  1022.     }                           /* of the new item set node */
  1023.     if (node->offset >= 0) item = node->offset +ist->index;
  1024.     else                   item = node->cnts[node->size +ist->index];
  1025.     if (ist->apps[item] == IST_IGNORE)
  1026.       continue;                 /* skip items to ignore */
  1027.     s_set = node->cnts[ist->index];
  1028.     if (s_set < s_min)          /* if the support is not sufficient, */
  1029.       continue;                 /* go to the next item set */
  1030.     if      (ist->arem == EM_LOGQ){ /* if logarithm of supp. quotient */
  1031.       dev = log(abs(cnts[item]) /(double)ist->tacnt);
  1032.       for (tmp = node; tmp->parent; tmp = tmp->parent)
  1033.         dev += log(abs(cnts[ID(tmp)]) /(double)ist->tacnt);
  1034.       dev = (log(s_set /(double)ist->tacnt) -dev) /(100*LN_2); }
  1035.     else if (ist->arem == EM_QUOT) { /* if measure is the quotient */
  1036.       dev = abs(cnts[item]);    /* compute the expected support */
  1037.       for (tmp = node; tmp->parent; tmp = tmp->parent)
  1038.         dev *= abs(cnts[ID(tmp)]) *nrm;
  1039.       dev = s_set /dev -1.0;  } /* compute the support quotient -1 */
  1040.     else {                      /* if no add. evaluation measure, */
  1041.       dev = 0; break; }         /* abort the search loop */
  1042.     if (dev >= ist->minval)     /* if the value of the additional */
  1043.       break;                    /* evaluation measure is high enough, */
  1044.   }                             /* abort the search loop */
  1045.   *supp = s_set *nrm;           /* compute the item set support */
  1047.   /* --- build frequent item set --- */
  1048.   i        = ist->size;         /* get the current item set size */
  1049.   set[--i] = item;              /* and store the first item */
  1050.   while (node->parent) {        /* while not at the root node */
  1051.     set[--i] = ID(node);        /* add item to the item set */
  1052.     node = node->parent;        /* and go to the parent node */
  1053.   }
  1054.   if (aval) *aval = dev;        /* set the add. evaluation measure */
  1055.   return ist->size;             /* return the item set size */
  1056. }  /* ist_set() */
  1058. /*--------------------------------------------------------------------*/
  1060. int ist_rule (ISTREE *ist, int *rule,
  1061.               double *supp, double *conf, double *lift, double *aval)
  1062. {                               /* --- extract next rule */
  1063.   int    i;                     /* loop variable */
  1064.   int    item;                  /* an item identifier */
  1065.   ISNODE *node;                 /* current item set node */
  1066.   ISNODE *parent;               /* parent of the item set node */
  1067.   ISNODE **vec;                 /* child node vector */
  1068.   int    *map, n;               /* identifier map and its size */
  1069.   int    s_rule;                /* minimal support of a rule */
  1070.   int    s_min;                 /* minimal support of a set */
  1071.   int    s_set;                 /* support of set    (body & head) */
  1072.   int    s_sub;                 /* support of subset (body) */
  1073.   double p_body, p_head;        /* prior confidences/probabilities */
  1074.   double c, v;                  /* confidence and measure value */
  1075.   int    app;                   /* appearance flag of head item */
  1077.   assert(ist && rule && supp && conf);  /* check function arguments */
  1079.   /* --- initialize --- */
  1080.   if (ist->size > ist->lvlcnt)  /* if the tree is not high enough */
  1081.     return -1;                  /* for the rule length, abort */
  1082.   s_rule = (int)ceil(ist->tacnt *ist->supp);  /* minimal rule support */
  1083.   s_min  = (ist->rsdef == IST_BOTH) ? s_rule  /* minimal set  support */
  1084.          : (int)ceil(ist->tacnt *ist->supp *ist->conf);
  1085.   if (ist->node)                /* if this is not the first rule, */
  1086.     node = ist->node;           /* get the buffered item set node */
  1087.   else {                        /* if this is the first rule */
  1088.     node = ist->node = ist->levels[ist->size -1];
  1089.     ist->index = ist->item = -1;/* initialize the */
  1090.   }                             /* rule extraction variables */
  1092.   /* --- find rule --- */
  1093.   while (1) {                   /* search for a rule */
  1094.     if (ist->item >= 0) {       /* --- select next item subset */
  1095.       *--ist->path = ist->item; /* add previous head to the path */
  1096.       ist->plen++;              /* and get the next head item */
  1097.       ist->item = ID(ist->head);
  1098.       ist->head = ist->head->parent;
  1099.       if (!ist->head)           /* if all subsets have been processed */
  1100.         ist->item = -1;         /* clear the head item to trigger the */
  1101.     }                           /* selection of a new item set */
  1102.     if (ist->item < 0) {        /* --- select next item set */
  1103.       if (++ist->index >= node->size){/* if all subsets have been */
  1104.         node = node->succ;      /* processed, go to the successor */
  1105.         if (!node) {            /* if at the end of a level, go down */
  1106.           if (++ist->size > ist->lvlcnt)
  1107.             return -1;          /* if beyond the deepest level, abort */
  1108.           node = ist->levels[ist->size -1];
  1109.         }                       /* get the 1st node of the new level */
  1110.         ist->node = node;       /* note the new item set node and */
  1111.         ist->index  = 0;        /* start with the first item set */
  1112.       }                         /* of the new item set node */
  1113.       if (node->offset >= 0) item = node->offset +ist->index;
  1114.       else                   item = node->cnts[node->size +ist->index];
  1115.       if ((ist->apps[item] == IST_IGNORE)
  1116.       ||  (HDONLY(node) && (ist->apps[item] == IST_HEAD)))
  1117.         continue;               /* skip sets with two head only items */
  1118.       ist->item   = item;       /* set the head item identifier */
  1119.       ist->hdonly = HDONLY(node) || (ist->apps[item] == IST_HEAD);
  1120.       ist->head   = node;       /* set the new head item node */
  1121.       ist->path   = ist->buf +ist->lvlvsz;
  1122.       ist->plen   = 0;          /* clear the path */
  1123.     }
  1124.     app = ist->apps[ist->item]; /* get head item appearance */
  1125.     if (!(app & IST_HEAD) || (ist->hdonly && (app != IST_HEAD)))
  1126.       continue;                 /* if rule is not allowed, skip it */
  1127.     s_set = node->cnts[ist->index]; /* get the item set support */
  1128.     if (s_set < s_min) {        /* if the set support is too low, */
  1129.       ist->item = -1; continue; }   /* skip this item set */
  1130.     parent = node->parent;      /* get the parent node */
  1131.     if (ist->plen > 0)          /* if there is a path, use it */
  1132.       s_sub = _getsupp(ist->head, ist->path, ist->plen);
  1133.     else if (!parent)           /* if there is no parent (root node), */
  1134.       s_sub = ist->tacnt;       /* get the number of transactions */
  1135.     else if (parent->offset >= 0)   /* if a pure vector is used */
  1136.       s_sub = parent->cnts[ID(node) -parent->offset];
  1137.     else {                      /* if an identifier map is used */
  1138.       map = parent->cnts +(n = parent->size);
  1139.       vec = (ISNODE**)(map +n); /* get id. map and child vector */
  1140.       s_sub = parent->cnts[_bsearch(map, n, ID(node))];
  1141.     }                           /* find vector index and get support */
  1142.     if (s_sub < s_rule)         /* if the subset support is too low, */
  1143.       continue;                 /* get the next subset/next set */
  1144.     c = (s_sub > 0)             /* compute the rule confidence */
  1145.       ? (double)s_set/s_sub : 1;
  1146.     if (c < ist->conf -EPSILON) /* if the confidence is too low, */
  1147.       continue;                 /* get the next item subset/item set */
  1148.     if (ist->arem == EM_NONE) { /* if no add. eval. measure given, */
  1149.       v = 0; break; }           /* abort the loop (select the rule) */
  1150.     if (ist->size < 2) {        /* if rule has an empty antecedent, */
  1151.       v = 0; break; }           /* abort the loop (select the rule) */
  1152.     if (ist->tacnt <= 0)        /* if there are no transactions, */
  1153.       p_body = p_head = 1;      /* all probabilities are 1 */
  1154.     else {                      /* if there are transactions */
  1155.       p_body = (double)s_sub                           /ist->tacnt;
  1156.       p_head = (double)ist->levels[0]->cnts[ist->item] /ist->tacnt;
  1157.     }                           /* estimate prior probabilities */
  1158.     v = _evalfns[ist->arem](p_head, p_body, c);
  1159.     if (v >= ist->minval)       /* if rule value exceeds the minimal */
  1160.       break;                    /* of the add. rule eval. measure, */
  1161.   }  /* while (1) */            /* abort the loop (select rule) */
  1162.   *supp = (ist->tacnt <= 0) ? 1 /* compute the rule support */
  1163.         : ((ist->rsdef == IST_BODY) ? s_sub : s_set)
  1164.         / (double)ist->tacnt;   /* (respect the rule support def.) */
  1165.   if (lift)                     /* compute and store the lift value */
  1166.     *lift = (c *ist->tacnt)/(double)ist->levels[0]->cnts[ist->item];
  1168.   /* --- build rule --- */
  1169.   if (node->offset >= 0) item = node->offset +ist->index;
  1170.   else                   item = node->cnts[node->size +ist->index];
  1171.   i = ist->size;                /* get the current item and */
  1172.   if (item != ist->item)        /* if this item is not the head, */
  1173.     rule[--i] = item;           /* add it to the rule body */
  1174.   while (node->parent) {        /* traverse the path to the root */
  1175.     if (ID(node) != ist->item)  /* and add all items on this */
  1176.       rule[--i] = ID(node);     /* path to the rule body */
  1177.     node = node->parent;        /* (except the head of the rule) */
  1178.   }
  1179.   rule[0] = ist->item;          /* set the head of the rule, */
  1180.   *conf   = c;                  /* the rule confidence, and */
  1181.   if (aval) *aval = v;          /* the value of the add. measure */
  1182.   return ist->size;             /* return the rule size */
  1183. }  /* ist_rule() */
  1185. /*--------------------------------------------------------------------*/
  1187. int ist_hedge (ISTREE *ist, int *hedge, double *supp, double *conf)
  1188. {                               /* --- extract next hyperedge */
  1189.   int    i;                     /* loop variable */
  1190.   int    item;                  /* an item identifier */
  1191.   ISNODE *node;                 /* current item set node */
  1192.   ISNODE *head;                 /* node containing the rule head */
  1193.   ISNODE **vec;                 /* child node vector of head node */
  1194.   int    *map, n;               /* identifier map and its size */
  1195.   int    *path, plen;           /* path in tree and its length */
  1196.   int    s_min;                 /* minimal support of a hyperedge */
  1197.   int    s_set;                 /* support of set    (body & head) */
  1198.   int    s_sub;                 /* support of subset (body) */
  1200.   assert(ist && hedge && supp && conf);  /* check function arguments */
  1202.   /* --- initialize --- */
  1203.   if (ist->size > ist->lvlcnt)  /* if the tree is not high enough */
  1204.     return -1;                  /* for the hyperedge size, abort */
  1205.   s_min = (int)ceil(ist->tacnt *ist->supp); /* get minimal support */
  1206.   if (!ist->node)               /* on first hyperedge, initialize */
  1207.     ist->node = ist->levels[ist->size -1];    /* the current node */
  1208.   node = ist->node;             /* get the current item set node */
  1210.   /* --- find hyperedge --- */
  1211.   while (1) {                   /* search for a hyperedge */
  1212.     if (++ist->index >= node->size) { /* if all subsets have been */
  1213.       node = node->succ;        /* processed, go to the successor */
  1214.       if (!node) {              /* if at the end of a level, go down */
  1215.         if (++ist->size > ist->lvlcnt)
  1216.           return -1;            /* if beyond the deepest level, abort */
  1217.         node = ist->levels[ist->size -1];
  1218.       }                         /* get the 1st node of the new level */
  1219.       ist->node  = node;        /* note the new item set node and */
  1220.       ist->index = 0;           /* start with the first item set */
  1221.     }                           /* of the new item set node */
  1222.     if (node->offset >= 0) item = node->offset +ist->index;
  1223.     else                   item = node->cnts[node->size +ist->index];
  1224.     if (ist->apps[item] == IST_IGNORE)
  1225.       continue;                 /* skip items to ignore */
  1226.     s_set = node->cnts[ist->index];
  1227.     if (s_set < s_min)          /* if the set support is too low, */
  1228.       continue;                 /* skip this item set */
  1229.     head = node->parent;        /* get subset support from parent */
  1230.     if (!head)                  /* if there is no parent (root node), */
  1231.       s_sub = ist->tacnt;       /* get the total number of sets */
  1232.     else if (head->offset >= 0) /* if pure vectors are used */
  1233.       s_sub = head->cnts[ID(node) -head->offset];
  1234.     else {                      /* if an identifier map is used */
  1235.       map = head->cnts +(n = head->size);
  1236.       vec = (ISNODE**)(map +n); /* get id. map and child vector */
  1237.       s_sub = head->cnts[_bsearch(map, n, ID(node))];
  1238.     }                           /* find index and get the support */
  1239.     *conf   = (s_sub > 0)       /* compute confidence of first rule */
  1240.             ? (double)s_set/s_sub : 1;
  1241.     path    = ist->buf +ist->lvlvsz;
  1242.     *--path = ist->index +node->offset;
  1243.     plen    = 1;                /* initialize the path, */
  1244.     item    = ID(node);         /* note the next head item, and */
  1245.     while (head) {              /* traverse the path up to root */
  1246.       s_sub = _getsupp(head, path, plen);
  1247.       *conf += (s_sub > 0)      /* sum the rule confidences */
  1248.              ? (double)s_set/s_sub : 1;
  1249.       *--path = item; plen++;   /* store the previous head item */
  1250.       item = ID(head);          /* in the path (extend path) */
  1251.       head = head->parent;      /* and go to the parent node */
  1252.     }                           /* (get the next rule head) */
  1253.     *conf /= ist->size;         /* average the rule confidences */
  1254.     if (*conf >= ist->minval) break;
  1255.   }  /* while(1) */             /* if confidence suffices, abort loop */
  1256.   *supp = (ist->tacnt > 0)      /* compute the hyperedge support */
  1257.         ? (double)s_set/ist->tacnt : 1;
  1259.   /* --- build hyperedge --- */
  1260.   i = ist->size -1;             /* store the first item */
  1261.   if (node->offset >= 0) hedge[i] = ist->index +node->offset;
  1262.   else                   hedge[i] = node->cnts[node->size +ist->index];
  1263.   while (node->parent) {        /* while not at the root node */
  1264.     hedge[--i] = ID(node);      /* add item to the hyperedge */
  1265.     node = node->parent;        /* and go to the parent node */
  1266.   }
  1267.   return ist->size;             /* return the hyperedge size */
  1268. }  /* ist_hedge() */
  1270. /*--------------------------------------------------------------------*/
  1271. #ifndef NDEBUG
  1273. static void _showtree (ISNODE *node, int level)
  1274. {                               /* --- show subtree */
  1275.   int    i, k;                  /* loop variables, buffer */
  1276.   int    *map, n;               /* identifier map and its size */
  1277.   int    c;                     /* number of children */
  1278.   ISNODE **vec;                 /* vector of child nodes */
  1280.   assert(node && (level >= 0)); /* check the function arguments */
  1281.   c = node->chcnt & ~F_SKIP;    /* get the number of children */
  1282.   if      (c <= 0)              /* if there are no children, */
  1283.     vec = NULL;                 /* clear the child vector variable */
  1284.   else if (node->offset >= 0)   /* if a pure vector is used */
  1285.     vec = (ISNODE**)(node->cnts +node->size);
  1286.   else {                        /* if an identifier map is used */
  1287.     map = node->cnts +(n = node->size);
  1288.     vec = (ISNODE**)(map +n);   /* get id. map and child vector */
  1289.     if (c < n)                  /* if a secondary id. map exists, */
  1290.       map = (int*)(vec +(n = c));      /* get this identifier map */
  1291.   }                             /* get child access variables */
  1292.   for (i = 0; i < node->size; i++) {
  1293.     for (k = level; --k >= 0; ) /* indent and print */
  1294.       printf("   ");            /* item identifier and counter */
  1295.     if (node->offset >= 0) k = node->offset +i;
  1296.     else                   k = node->cnts[node->size +i];
  1297.     printf("%d: %dn", k, node->cnts[i]);
  1298.     if (!vec) continue;         /* check whether there are children */
  1299.     if (node->offset >= 0) k -= ID(vec[0]);
  1300.     else                   k = _bsearch(map, n, k);
  1301.     if ((k >= 0) && (k < c) && vec[k])
  1302.       _showtree(vec[k], level +1);
  1303.   }                             /* show subtree recursively */
  1304. }  /* _showtree() */
  1306. /*--------------------------------------------------------------------*/
  1308. void ist_show (ISTREE *ist)
  1309. {                               /* --- show an item set tree */
  1310.   assert(ist);                  /* check the function argument */
  1311.   _showtree(ist->levels[0], 0); /* show nodes recursively */
  1312.   printf("total: %dn", ist->tacnt);
  1313. }  /* ist_show() */             /* print number of transactions */
  1315. #endif