istree.h

数据挖掘中的关联规则算法

/*----------------------------------------------------------------------
  File    : istree.h
  Contents: item set tree management
  Author  : Christian Borgelt
  History : 22.01.1996 file created
            29.01.1996 ISNODE.offset and ISNODE.id added
            08.02.1996 ISTREE.tacnt, ISTREE.curr, ISTREE.index,
                       ISTREE.head and ISTREE.conf added
            28.03.1996 support made relative to number of item sets
            23.11.1996 ISTREE.levels (first nodes of each level) added
            24.11.1996 ISTREE.arem (add. rule evaluation measure) added
            18.08.1997 chi^2 evaluation measure added
                       parameter 'minlen' added to function ist_init()
            11.02.1998 parameter 'minval' added to function ist_init()
            14.05.1998 item set tree navigation functions added
            08.08.1998 parameter 'apps' added to function ist_create()
            20.08.1998 structure ISNODE redesigned
            07.09.1998 function ist_hedge added
            08.12.1998 function ist_gettac added,
                       float changed to double
            05.02.1999 long int changed to int
            26.08.1999 functions ist_first and ist_last added
            05.11.1999 rule evaluation measure EM_AIMP added
            08.11.1999 parameter 'aval' added to function ist_rule
            01.04.2001 functions ist_set and ist_getcntx added
            28.12.2001 sort function moved to module tract
            07.02.2002 function ist_clear removed, ist_settac added
            11.02.2002 optional use of identifier maps in nodes added
            12.02.2002 ist_first and ist_last replaced by ist_next
            12.03.2003 parameter lift added to function ist_rule
            17.07.2003 functions ist_itemcnt and ist_check added
            18.07.2003 function ist_maxfrq added (item set filter)
            11.08.2003 item set filtering generalized (ist_filter)
            09.05.2004 parameter 'aval' added to function ist_set
----------------------------------------------------------------------*/
#ifndef __ISTREE__
#define __ISTREE__
#include "tract.h"

/*----------------------------------------------------------------------
  Preprocessor Definitions
----------------------------------------------------------------------*/
/* --- additional evaluation measures --- */
#define EM_NONE     0           /* no measure */
#define EM_DIFF     1           /* absolute conf. difference to prior */
#define EM_LOGQ     1           /* logarithm of support quotient */
#define EM_QUOT     2           /* difference of conf. quotient to 1 */
#define EM_AIMP     3           /* abs. diff. of improvement to 1 */
#define EM_INFO     4           /* information difference to prior */
#define EM_CHI2     5           /* normalized chi^2 measure */
#define EM_UNKNOWN  6           /* unknown measure */

/* --- item appearances --- */
#define IST_IGNORE  0           /* ignore item */
#define IST_BODY    1           /* item may appear in rule body */
#define IST_HEAD    2           /* item may appear in rule head */
#define IST_BOTH    (IST_HEAD|IST_BODY)

/* --- item set filter modes --- */
#define IST_MAXFRQ  0           /* maximally frequent item sets */
#define IST_CLOSED  1           /* closed item sets */

/*----------------------------------------------------------------------
  Type Definitions
----------------------------------------------------------------------*/
typedef struct _isnode {        /* --- item set node --- */
  struct _isnode *parent;       /* parent node */
  struct _isnode *succ;         /* successor node on same level */
  int            id;            /* identifier used in parent node */
  int            chcnt;         /* number of child nodes */
  int            size;          /* size   of counter vector */
  int            offset;        /* offset of counter vector */
  int            cnts[1];       /* counter vector */
} ISNODE;                       /* (item set node) */

typedef struct {                /* --- item set tree --- */
  int    tacnt;                 /* number of transactions counted */
  int    lvlvsz;                /* size of level vector */
  int    lvlcnt;                /* number of levels (tree height) */
  ISNODE **levels;              /* first node of each level */
  double supp;                  /* minimal support of an item set */
  double conf;                  /* minimal confidence of a rule */
  int    rsdef;                 /* rule support definition */
  int    arem;                  /* additional rule evaluation measure */
  double minval;                /* minimal evaluation measure value */
  ISNODE *curr;                 /* current node for traversal */
  int    size;                  /* size of item set/rule/hyperedge */
  ISNODE *node;                 /* item set node for extraction */
  int    index;                 /* index in item set node */
  ISNODE *head;                 /* head item node for extraction */
  int    item;                  /* head item of previous rule */
  int    *buf;                  /* buffer for paths (support check) */
  int    *path;                 /* current path / (partial) item set */
  int    plen;                  /* current path length */
  int    hdonly;                /* head only item in current set */
  int    memopt;                /* whether to optimize memory usage */
  int    *map;                  /* to create identifier maps */
#ifdef BENCH                    /* if benchmark version */
  int    cnt;                   /* number of counters */
  int    nec;                   /* number of necessary counters */
  int    chcnt;                 /* number of child pointers */
  int    chnec;                 /* number of necessary child pointers */
  int    bytes;                 /* number of bytes used */
#endif
  char   apps[1];               /* item appearances */
} ISTREE;                       /* (item set tree) */

/*----------------------------------------------------------------------
  Functions
----------------------------------------------------------------------*/
extern ISTREE* ist_create  (int itemcnt, double supp, double conf,
                            int rsdef, const char *apps, int memopt);
extern void    ist_delete  (ISTREE *ist);
extern int     ist_itemcnt (ISTREE *ist);

extern void    ist_count   (ISTREE *ist, int *set, int cnt);
extern void    ist_countx  (ISTREE *ist, TATREE *tat);
extern int     ist_settac  (ISTREE *ist, int cnt);
extern int     ist_gettac  (ISTREE *ist);
extern int     ist_check   (ISTREE *ist, char *marks);
extern int     ist_addlvl  (ISTREE *ist);
extern int     ist_height  (ISTREE *ist);

extern void    ist_up      (ISTREE *ist, int root);
extern int     ist_down    (ISTREE *ist, int item);
extern int     ist_next    (ISTREE *ist, int item);
extern void    ist_setcnt  (ISTREE *ist, int item, int cnt);
extern int     ist_getcnt  (ISTREE *ist, int item);
extern int     ist_getcntx (ISTREE *ist, int *set, int cnt);

extern void    ist_filter  (ISTREE *ist, int mode);
extern void    ist_init    (ISTREE *ist, int minlen,
                            int arem, double minval);
extern int     ist_set     (ISTREE *ist, int *set,
                            double *supp, double *aval);
extern int     ist_rule    (ISTREE *ist, int *rule,
                            double *supp, double *conf,
                            double *lift, double *aval);
extern int     ist_hedge   (ISTREE *ist, int *hedge,
                            double *supp, double *conf);

#ifndef NDEBUG
extern void    ist_show    (ISTREE *ist);
#endif

/*----------------------------------------------------------------------
  Preprocessor Definitions
----------------------------------------------------------------------*/
#define ist_itemcnt(t)     ((t)->levels[0]->size)
#define ist_settac(t,n)    ((t)->tacnt = (n))
#define ist_gettac(t)      ((t)->tacnt)
#define ist_height(t)      ((t)->lvlcnt)

#endif