dtree.h

dTree是一个运行在WinCE上的文件管理软件。类似文件管理器,功能强大

/*----------------------------------------------------------------------
  File    : dtree.h
  Contents: decision and regression tree management
  Author  : Christian Borgelt
  History : 27.05.1997 file created
            08.08.1997 first version completed
            25.08.1997 multiple child references made possible
            26.08.1997 function dt_size added
            28.08.1997 pruning methods added
            10.09.1997 function dt_height added
            16.09.1997 function dt_link added
            17.09.1997 parameter 'check' added to function dt_down
                       parameter 'mode' added to function dt_desc
            02.02.1998 field 'link' added to structure DTDATA
            08.02.1998 function dt_parse transferred from parse.c
            03.09.1998 parameters 'supp' and 'err' added to dt_exec
            24.02.1999 parameters 'params' and 'minval' added to dt_grow
            11.03.1999 definition of DT_DUPAS added
            20.03.1999 DTREE.buf changed from 'float' to 'double'
            16.12.2000 regression tree functionality added
            19.07.2001 adapted to modified module scan
            11.01.2002 number of attributes stored in DTREE structure
            01.03.2002 parameter testlb added to function dt_prune
            12.08.2004 adapted to new module parse
            13.09.2004 trivial pruning of grown tree made optional
            07.02.2006 cut value changed from 'float' to 'double'
----------------------------------------------------------------------*/
#ifndef __DTREE__
#define __DTREE__
#ifdef DT_PARSE
#include "parse.h"
#endif
#include "table.h"
#ifdef DT_GROW
#ifndef FT_EVAL
#define FT_EVAL
#endif
#ifndef VT_EVAL
#define VT_EVAL
#endif
#endif
#include "frqtab.h"
#include "vartab.h"
#ifdef DT_RULES
#include "rules.h"
#endif

/*----------------------------------------------------------------------
  Preprocessor Definitions
----------------------------------------------------------------------*/
/* --- pruning methods --- */
#define PM_NONE     0           /* no pruning */
#define PM_PESS     1           /* pessimistic pruning */
#define PM_CLVL     2           /* confidence level pruning */
#define PM_MDL      3           /* minimum description length pruning */
                                /* (PM_MDL not implemented yet) */
/* --- flags/modes --- */
#define DT_LEAF     0x0001      /* whether node is a leaf */
#define DT_LINK     0x0002      /* whether node contains links */
#define DT_EVAL     0x0001      /* only evaluate attributes */
#define DT_SUBSET   0x0002      /* try to form subsets */
#define DT_DUPAS    0x0004      /* duplicate attribute set */
#define DT_NOPRUNE  0x0008      /* no trivial pruning of grown tree */

/* --- description modes --- */
#define DT_TITLE    0x0001      /* print a title (as a comment) */
#define DT_INFO     0x0002      /* print add. info. (as a comment) */
#define DT_ALIGN    0x0004      /* align values of test attribute */
#define DT_REL      0x0008      /* print relative numbers */

/*----------------------------------------------------------------------
  Type Definitions
----------------------------------------------------------------------*/
typedef union _dtdata {         /* --- decision tree node data --- */
  float          frq;           /* class frequency (for leaves) */
  struct _dtnode *child;        /* child node (for inner nodes) */
  union  _dtdata *link;         /* link to another data field */
} DTDATA;                       /* (decision tree node data) */

typedef struct _dtnode {        /* --- decision tree node --- */
  int    flags;                 /* node flags, e.g. DF_LEAF */
  int    attid;                 /* identifier of attribute to test */
  double cut;                   /* cut value for numeric attribute */
  float  frq;                   /* frequency (number of tuples) */
  double err;                   /* number of leaf errors */
  INST   trg;                   /* most frequent class/expected value */
  int    size;                  /* size of the data vector */
  DTDATA vec[1];                /* vector of children/frequencies */
} DTNODE;                       /* (decision tree node) */

typedef struct {                /* --- decision tree --- */
  ATTSET *attset;               /* attribute set */
  DTNODE *root;                 /* root node */
  DTNODE *curr;                 /* current node */
  DTNODE **newp;                /* position of new node */
  DTNODE **path;                /* nodes on path to current node */
  int    plen;                  /* length of path (number of nodes) */
  int    pvsz;                  /* size of the path vector */
  int    trgid;                 /* identifier of target attribute */
  int    type;                  /* type of target attribute */
  int    clscnt;                /* number of classes (sym. target) */
  int    attcnt;                /* number of attributes (incl. class) */
  int    height;                /* height (length of longest path) */
  int    size;                  /* number of nodes (including leaves) */
  float  total;                 /* total frequency (number of tuples) */
  double *buf;                  /* buffer for frequencies etc. */
  TUPLE  *tuple;                /* tuple to classify */
} DTREE;                        /* (decision tree) */

/*----------------------------------------------------------------------
  Functions
----------------------------------------------------------------------*/
extern DTREE*   dt_create (ATTSET *attset, int trgid);
extern void     dt_delete (DTREE *dt, int delas);
extern ATTSET*  dt_attset (DTREE *dt);
extern int      dt_trgid  (DTREE *dt);
extern int      dt_type   (DTREE *dt);
extern int      dt_clscnt (DTREE *dt);
extern int      dt_height (DTREE *dt);
extern int      dt_size   (DTREE *dt);
extern float    dt_total  (DTREE *dt);

extern int      dt_atleaf (DTREE *dt);
extern int      dt_attid  (DTREE *dt);
extern int      dt_width  (DTREE *dt);
extern double   dt_cutval (DTREE *dt);
extern float    dt_freq   (DTREE *dt);
extern int      dt_mfcls  (DTREE *dt);
extern float    dt_value  (DTREE *dt);
extern float    dt_errs   (DTREE *dt);

extern void     dt_up     (DTREE *dt, int  root);
extern int      dt_down   (DTREE *dt, int index, int check);
extern int      dt_node   (DTREE *dt, int attid, double cutval);
extern int      dt_link   (DTREE *dt, int src, int dst);
extern int      dt_dest   (DTREE *dt, int index);
extern float    dt_setfrq (DTREE *dt, int index, float frq);
extern float    dt_getfrq (DTREE *dt, int index);

extern int      dt_attchk (DTREE *dt);
extern int      dt_attcnt (DTREE *dt);

#ifdef DT_GROW
extern DTREE*   dt_grow   (TABLE *table, int trgid,
                           int measure, double *params, double minval,
                           int maxht, float mincnt, int flags);
#endif
#ifdef DT_PRUNE
extern int      dt_prune  (DTREE *dt, int method, double param,
                           int maxht, int testlb, TABLE *table);
#endif
extern int      dt_exec   (DTREE *dt, TUPLE *tuple, INST *res,
                           float *supp, float *conf);
extern int      dt_desc   (DTREE *dt, FILE *file, int mode, int maxlen);
#ifdef DT_PARSE
extern DTREE*   dt_parse  (ATTSET *attset, SCAN *scan);
#endif
#ifdef DT_RULES
extern RULESET* dt_rules  (DTREE *dt);
#endif

/*----------------------------------------------------------------------
  Preprocessor Definitions
----------------------------------------------------------------------*/
#define dt_attset(t)     ((t)->attset)
#define dt_trgid(t)      ((t)->trgid)
#define dt_type(t)       ((t)->type)
#define dt_clscnt(t)     ((t)->clscnt)
#define dt_height(t)     ((t)->height)
#define dt_size(t)       ((t)->size)

#define dt_atleaf(t)     ((t)->curr && ((t)->curr->flags & DT_LEAF))
#define dt_attid(t)      (((t)->curr) ? (t)->curr->attid : -1)
#define dt_width(t)      (((t)->curr) ? (t)->curr->size  : -1)
#define dt_cutval(t)     (((t)->curr) ? (t)->curr->cut   : UV_FLT)
#define dt_freq(t)       (((t)->curr) ? (t)->curr->frq   : -1)
#define dt_mfcls(t)      (((t)->curr) ? (t)->curr->trg.i : -1)
#define dt_value(t)      (((t)->curr) ? (t)->curr->trg.f : -1)
#define dt_errs(t)       (((t)->curr) ? (t)->curr->err   : -1)

#define dt_setfrq(t,i,f) ((t)->total = -1, \
                          (t)->curr->vec[i].frq = (f))
#define dt_getfrq(t,i)   ((t)->curr->vec[i].frq)

#endif