ptree.h

数据挖掘中的一算法 ines算法 c下实现的。适合初学习数据挖掘者借鉴

/*----------------------------------------------------------------------
  File    : ptree.h
  Contents: probability/possibility tree management
  Author  : Christian Borgelt
  History : 22.10.1995 file created
            26.10.1995 PTREE.curr and pt_down and pt_up added
            27.10.1995 range checks removed
            29.10.1995 function pt_conadd added
            02.11.1995 functions pt_conrem and pt_eval added
            08.11.1995 function pt_getcnt added
            11.12.1995 evaluation measure 'EM_INFGAIN' added
            05.02.1996 some evaluation measures added
            07.02.1996 evaluation measure 'EM_GINI' added
            23.02.1996 functions pt_mname and pt_minfo added
            15.03.1996 number of levels restricted to PT_MAXCON+1
            29.06.1996 second specificity gain measure added
            15.11.1996 function pt_total added
            27.11.1996 type of counters changed to floating point
            28.02.1997 tree mode (PT_PROB/PT_POSS) added, redesign
            01.03.1997 functions pt_aggr and pt_conrem improved
            06.03.1997 some evaluation measures added
            10.03.1997 second sym. info./spec. gain ratio added
            11.03.1997 alternate measure versions added
            25.03.1997 function pt_depend added
            13.02.1998 links between nodes made possible (pt_link)
            18.02.1998 some evaluation measures added
            20.02.1998 Bayesian Dirichlet l.e. uniform metric added
            10.06.1998 semantics of function pt_down changed
            20.02.1999 structure PTLVL added, structure PTREE modified
            24.02.1999 based on attribute set management
            25.04.1999 function pt_concopy added
            11.12.1999 evaluation measure 'EM_WDIFF' added
            01.11.2001 module renamed to ptree (prob./poss. tree)
            24.02.2002 function pt_getcntx added
            05.03.2002 description flag PT_INFO added
            11.03.2002 number of tuples added for poss. normalization
            04.04.2002 function pt_parcnt added
            10.04.2002 parameter flags for function pt_parse removed
            01.07.2002 field pathcnt added to structure PTLEAF
            03.07.2002 field occur added to structure PTREE
            16.07.2002 parameter 'delnodes' added to function pt_clear
            17.07.2002 PTREE.buf added (for nonspecificity comp.)
----------------------------------------------------------------------*/
#ifndef __PTREE__
#define __PTREE__
#include <limits.h>
#include <float.h>
#ifdef PT_PARSE
#include "parse.h"
#endif
#include "attset.h"

/*----------------------------------------------------------------------
  Preprocessor Definitions
----------------------------------------------------------------------*/
/* --- sizes --- */
#define PT_MAXCON   31          /* maximum number of conditions */

/* --- tree types --- */
#define PT_PROB     0x0000      /* probability tree (sum) */
#define PT_POSS     0x0001      /* possibility tree (maximum) */
#define PT_AUTO     0x8000      /* determine type from input file */

/* --- node flags --- */
#define PT_OCCUR    INT_MIN     /* whether a subtree is not empty */

/* --- modes for pt_up --- */
#define PT_ROOT      0          /* go up to the root node */
#define PT_PARENT    1          /* go up to the true parent */
#define PT_DESCENT   2          /* go up to where descended from */

/* --- modes for pt_desc/pt_parse --- */
#define PT_TITLE    0x0001      /* print a title (as a comment) */
#define PT_INFO     0x0002      /* print add. info (as a comment) */
#define PT_FULL     0x0004      /* print a full tree (all branches) */
#define PT_REL      0x0008      /* print relative frequencies */
#define PT_INDENT   0x0010      /* indent lines (for graph. model) */

/* --- probabilistic evaluation measures --- */
#define PT_NONE      0          /* no measure */
#define PT_INFGAIN   1          /* information gain */
#define PT_INFGBAL   2          /* balanced information gain */
#define PT_INFGR     3          /* information gain ratio */
#define PT_INFSGR1   4          /* sym. information gain ratio 1 */
#define PT_INFSGR2   5          /* sym. information gain ratio 2 */
#define PT_QIGAIN    6          /* quadratic information gain */
#define PT_QIGBAL    7          /* balanced quad. information gain */
#define PT_QIGR      8          /* quad. information gain ratio */
#define PT_QISGR1    9          /* sym. quad. info. gain ratio 1 */
#define PT_QISGR2   10          /* sym. quad. info. gain ratio 2 */
#define PT_GINI     11          /* gini index */
#define PT_GINISYM  12          /* symmetric gini index */
#define PT_GINIMOD  13          /* modified gini index */
#define PT_RELIEF   14          /* relief measure */
#define PT_WDIFF    15          /* sum of weighted differences */
#define PT_CHI2     16          /* chi^2 measure */
#define PT_CHI2NRM  17          /* normalized chi^2 measure */
#define PT_WEVID    18          /* weight of evidence */
#define PT_RELEV    19          /* relevance */
#define PT_BDM      20          /* Bayesian-Dirichlet / K2 metric */
#define PT_BDMOD    21          /* modified BD / K2 metric */
#define PT_RDLREL   22          /* red. of desc. length (rel. freq.) */
#define PT_RDLABS   23          /* red. of desc. length (abs. freq.) */
#define PT_STOCO    24          /* stochastic complexity */
#define PT_UNKNOWN  25          /* unknown measure */

/* --- possibilistic evaluation measures --- */
#define PT_SPCGAIN   1          /* specificity gain */
#define PT_SPCGBAL   2          /* balanced specificity gain */
#define PT_SPCGR     3          /* specificity gain ratio */
#define PT_SPCSGR1   4          /* sym. specificity gain ratio */
#define PT_SPCSGR2   5          /* sym. specificity gain ratio */
/*      PT_WDIFF    15 */       /* weighted general difference */
/*      PT_CHI2     16 */       /* possibilistic chi^2 measure */
#define PT_MUTSPC   20          /* mutual specificity */

/* --- other values --- */
#define PT_SYM      0x8000      /* whether measure is symmetric */
#define PT_ERROR    (-DBL_MAX)  /* to indicate an evaluation error */

/*----------------------------------------------------------------------
  Type Definitions
----------------------------------------------------------------------*/
typedef struct _ptnode {        /* --- prob./poss. tree node --- */
  struct _ptnode *succ;         /* successor node on same level */
  struct _ptnode *parent;       /* parent node on preceding level */
  int            index;         /* vector index in parent node */
  int            pathcnt;       /* number of paths to this node */
  struct _ptnode *children[1];  /* vector of child nodes */
} PTNODE;                       /* (prob./poss. tree node) */

typedef struct _ptleaf {        /* --- prob./poss. tree leaf --- */
  struct _ptleaf *succ;         /* successor node on same level */
  struct _ptnode *parent;       /* parent node on preceding level */
  int            index;         /* vector index in parent node */
  int            pathcnt;       /* number of paths to this leaf */
  double         eval;          /* evaluation term */
  float          total;         /* aggregate of leaf counters */
  float          cnts[1];       /* vector of counters */
} PTLEAF;                       /* (prob./poss. tree leaf) */

typedef struct {                /* --- prob./poss. tree level --- */
  int    cnt;                   /* number of children per node */
  ATT    *att;                  /* corresponding attribute */
  PTNODE *list;                 /* list of nodes on this level */
  PTNODE *node;                 /* current node on this level */
  int    index;                 /* child index used in current node */
  int    link;                  /* child index used on link */
  float  total;                 /* aggregate of counters in buffer */
  float  *buf;                  /* buffer for aggregation */
} PTLVL;                        /* (prob./poss. tree level) */

typedef struct {                /* --- prob./poss. tree --- */
  ATT    *att;                  /* conditioned attribute */
  int    type;                  /* tree type (PT_PROB or PT_POSS) */
  int    concnt;                /* number of conditions */
  int    fullcnt;               /* number of leaves of a full tree */
  int    leafcnt;               /* number of leaf nodes */
  int    parcnt;                /* number of parameters */
  int    pathlen;               /* path length (current level) */
  PTNODE *curr;                 /* current node (tree cursor) */
  float  tplcnt;                /* number of tuples for norm. */
  float  total;                 /* total of all counters */
  float  lcorr;                 /* Laplace correction */
  int    occur;                 /* whether occurrence flags are set */
  int    measure;               /* evaluation measure */
  double params[2];             /* evaluation parameters */
  double res0[5];               /* intermediate evaluation results */
  double res1[5];               /* ditto, for final computation */
  double eval;                  /* result of evaluation */
  float  *buf;                  /* buffer for specificity computation */
  PTLVL  levels[PT_MAXCON+1];   /* tree level descriptions */
} PTREE;                        /* (prob./poss. tree) */

/*----------------------------------------------------------------------
  Functions
----------------------------------------------------------------------*/
extern PTREE* pt_create  (ATT *att,  int type);
extern void   pt_delete  (PTREE *pt, int delatts);
extern void   pt_clear   (PTREE *pt, int delnodes);
extern int    pt_type    (PTREE *pt);
extern float  pt_setnorm (PTREE *pt, float tplcnt);
extern float  pt_getnorm (PTREE *pt);
extern float  pt_setlc   (PTREE *pt, float lcorr);
extern float  pt_getlc   (PTREE *pt);

extern int    pt_attid   (PTREE *pt);
extern ATT*   pt_att     (PTREE *pt);
extern int    pt_concnt  (PTREE *pt);
extern int    pt_conadd  (PTREE *pt, int lvlid, ATT *att);
extern void   pt_conrem  (PTREE *pt, int lvlid, int delatt);
extern int    pt_concopy (PTREE *dst, PTREE *src);
extern int    pt_conid   (PTREE *pt, int lvlid);
extern ATT*   pt_con     (PTREE *pt, int lvlid);

extern int    pt_level   (PTREE *pt);
extern int    pt_atleaf  (PTREE *pt);
extern void   pt_down    (PTREE *pt, int index);
extern void   pt_up      (PTREE *pt, int mode);
extern int    pt_setcnt  (PTREE *pt, int index, float cnt);
extern float  pt_getcnt  (PTREE *pt, int index);
extern float  pt_getcntx (PTREE *pt);
extern float  pt_gettot  (PTREE *pt);
extern int    pt_occur   (PTREE *pt);
extern int    pt_path    (PTREE *pt, int *path);
extern int    pt_link    (PTREE *pt, int index, const int *path);

extern int    pt_parcnt  (PTREE *pt);
extern float  pt_total   (PTREE *pt);
extern int    pt_aggr    (PTREE *pt, float wgt, int distuv);
extern int    pt_rand    (PTREE *pt, double randfn(void));
extern float  pt_exec    (PTREE *pt);
extern float  pt_poss    (PTREE *pt);

extern double pt_eval    (PTREE *pt, int measure, double *params);
extern double pt_reeval  (PTREE *pt);
extern double pt_local   (PTREE *pt, int lwise, double minimp);
extern double pt_depend  (PTREE *pt, int measure, double *params);
extern CCHAR* pt_mname   (int type, int measure);
extern int    pt_minfo   (int type, int measure);
extern double pt_nsp     (float *dist, int n);

extern int    pt_desc    (PTREE *pt, FILE *file, int mode, int maxlen);
#ifdef PT_PARSE
extern PTREE* pt_parse   (ATTSET *attset, SCAN *scan, int type);
#endif

/*----------------------------------------------------------------------
  Preprocessor Definitions
----------------------------------------------------------------------*/
#define pt_type(p)       ((p)->type)
#define pt_setnorm(p,c)  ((p)->tplcnt = (c))
#define pt_getnorm(p)    ((p)->tplcnt)
#define pt_setlc(p,c)    ((p)->lcorr = (c))
#define pt_getlc(p)      ((p)->lcorr)

#define pt_attid(p)      att_id((p)->att)
#define pt_att(p)        ((p)->att)
#define pt_concnt(p)     ((p)->concnt)
#define pt_conid(p,l)    att_id((p)->levels[l].att)
#define pt_con(p,l)      ((p)->levels[l].att)

#define pt_level(p)      ((p)->pathlen)
#define pt_atleaf(p)     ((p)->pathlen >= (p)->concnt)
#define pt_getcnt(p,i)   ((p)->curr ? ((PTLEAF*)p->curr)->cnts[i] : 0)
#endif