www.pudn.com > FP-GROWTH.rar > 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