ines.c

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

/*----------------------------------------------------------------------
  File    : ines.c
  Contents: Induction of NEtwork Structures (learning graphical models)
  Author  : Christian Borgelt
  History : 03.11.1995 file created
            08.11.1995 computation of probability distribution added
            26.11.1995 adapted to modified module attset
            08.12.1995 log file added, in and out file made global
            18.01.1996 adapted to modified function as_read
            22.02.1996 error message 'missing option argument' added
            05.03.1996 lower bound for improvement added
            06.03.1996 adapted to modified set of evaluation measures
            17.03.1996 adapted to modified parse function
            22.11.1996 options -b, -f, and -r (table structure) added
            28.02.1997 option -m (possibilistic model) added
            08.03.1997 list of evaluation measures added
            02.02.1998 option -u (unknown value characters) added
            16.02.1998 options -g, -G (merge, greedy merge) added
            10.06.1998 option -t (write a full tree) added
            24.02.1999 options -z (measure sensitivity)
                       and -p (prior/equiv. sample size) added
            24.04.1999 simplified using the new module 'io'
            25.11.2001 adapted to modified scanner functions
            03.03.2002 network induction functions moved to gramod2.c
            11.04.2002 simulated annealing added from file sian.c
            16.01.2003 optional approximation for poss. maximum removed
            17.01.2003 normalization of possibilistic measures added
            16.08.2003 slight changes in error message output
----------------------------------------------------------------------*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdarg.h>
#include <time.h>
#include <assert.h>
#ifndef AS_RDWR
#define AS_RDWR
#endif
#ifndef AS_PARSE
#define AS_PARSE
#endif
#ifndef TAB_RDWR
#define TAB_RDWR
#endif
#include "io.h"
#ifndef GM_PARSE
#define GM_PARSE
#endif
#ifndef GM_EVAL
#define GM_EVAL
#endif
#ifndef GM_INDUCE
#define GM_INDUCE
#endif
#include "gramod.h"
#ifdef STORAGE
#include "storage.h"
#endif

/*----------------------------------------------------------------------
  Preprocessor Definitions
----------------------------------------------------------------------*/
#define PRGNAME     "ines"
#define DESCRIPTION "induction of network structures"
#define VERSION     "version 2.7 (2004.08.12)         " \
                    "(c) 1995-2004   Christian Borgelt"

/* --- error codes --- */
#define OK            0         /* no error */
#define E_NONE        0         /* no error */
#define E_NOMEM     (-1)        /* not enough memory */
#define E_FOPEN     (-2)        /* file open failed */
#define E_FREAD     (-3)        /* file read failed */
#define E_FWRITE    (-4)        /* file write failed */
#define E_OPTION    (-5)        /* unknown option */
#define E_OPTARG    (-6)        /* missing option argument */
#define E_ARGCNT    (-7)        /* wrong number of arguments */
#define E_SEARCH    (-8)        /* unknown search method */
#define E_MEASURE   (-9)        /* unknown measure */
#define E_STDIN    (-10)        /* double assignment of stdin */
#define E_COMBI    (-11)        /* illegal method/measure combination */
#define E_PARSE    (-12)        /* parse error */
#define E_UNKNOWN  (-13)        /* unknown error */

/*----------------------------------------------------------------------
  Type Definitions
----------------------------------------------------------------------*/
typedef struct {                /* --- measure information --- */
  int  code;                    /* measure code */
  char *name;                   /* name of the measure */
} MINFO;                        /* (measure information) */

/*----------------------------------------------------------------------
  Constants
----------------------------------------------------------------------*/
static const MINFO m_prob[] = { /* --- probabilistic measures */
  { PT_NONE,    "none"    },    /* no measure */
  { PT_INFGAIN, "infgain" },    /* information gain */
  { PT_INFGBAL, "infgbal" },    /* balanced information gain */
  { PT_INFGR,   "infgr"   },    /* information gain ratio */
  { PT_INFSGR1, "infsgr1" },    /* sym. information gain ratio 1 */
  { PT_INFSGR2, "infsgr2" },    /* sym. information gain ratio 2 */
  { PT_QIGAIN,  "qigain"  },    /* quadratic information gain */
  { PT_QIGBAL,  "qigbal"  },    /* balanced quad. information gain */
  { PT_QIGR,    "qigr"    },    /* quadratic information gain ratio */
  { PT_QISGR1,  "qisgr1"  },    /* sym. quad. info. gain ratio 1 */
  { PT_QISGR2,  "qisgr2"  },    /* sym. quad. info. gain ratio 2 */
  { PT_GINI,    "gini"    },    /* Gini index */
  { PT_GINISYM, "ginisym" },    /* symmetric Gini index */
  { PT_GINIMOD, "ginimod" },    /* modified Gini index */
  { PT_RELIEF,  "relief"  },    /* relief measure */
  { PT_WDIFF,   "wdiff"   },    /* sum of weighted differences */
  { PT_CHI2,    "chi2"    },    /* chi^2 measure */
  { PT_CHI2NRM, "chi2nrm" },    /* normalized chi^2 measure */
  { PT_WEVID,   "wevid"   },    /* weight of evidence */
  { PT_RELEV,   "relev"   },    /* relevance */
  { PT_BDM,     "bdm"     },    /* Bayesian-Dirichlet / K2 metric */
  { PT_BDMOD,   "bdmod"   },    /* modified BD / K2 metric */
  { PT_RDLREL,  "rdlrel"  },    /* red. of desc. length (rel. freq.) */
  { PT_RDLABS,  "rdlabs"  },    /* red. of desc. length (abs. freq.) */
  { PT_STOCO,   "stoco"   },    /* stochastic complexity */
  { -1,         NULL      }     /* sentinel */
};

static const MINFO m_poss[] = { /* --- possibilistic measures */
  { PT_SPCGAIN, "spcgain" },    /* specificity gain */
  { PT_SPCGBAL, "spcgbal" },    /* balanced specificity gain */
  { PT_SPCGR,   "spcgr"   },    /* specificity gain ratio */
  { PT_SPCSGR1, "spcsgr1" },    /* sym. specificity gain ratio 1 */
  { PT_SPCSGR2, "spcsgr2" },    /* sym. specificity gain ratio 2 */
  { PT_WDIFF,   "wdiff"   },    /* weighted (absolute) difference */
  { PT_CHI2,    "chi2"    },    /* possibilistic chi^2 measure */
  { PT_MUTSPC,  "mutspc"  },    /* mutual specificity */
  { -1,          NULL     }     /* sentinel */
};

static const MINFO sminfo[] = { /* search method information */
  { GM_NONE,    "none"    },    /* no search, only param. estim. */
  { GM_OWST,    "owst"    },    /* optimum weight spanning tree */
  { GM_EXTST,   "extst"   },    /* extension of spanning tree */
  { GM_TOPORD,  "topord"  },    /* greedy on topological order */
  { GM_NOLOOP,  "noloop"  },    /* greedy avoiding loops */
  { GM_UNRES,   "unres"   },    /* unrestricted greedy */
  { GM_SIAN,    "sian"   },     /* hypertree simulated annealing */
  { -1,          NULL     }     /* sentinel */
};

static const char *errmsgs[] = {/* error messages */
  /* E_NONE      0 */ "no error\n",
  /* E_NOMEM    -1 */ "not enough memory\n",
  /* E_FOPEN    -2 */ "cannot open file %s\n",
  /* E_FREAD    -3 */ "read error on file %s\n",
  /* E_FWRITE   -4 */ "write error on file %s\n",
  /* E_OPTION   -5 */ "unknown option -%c\n",
  /* E_OPTARG   -6 */ "missing option argument\n",
  /* E_ARGCNT   -7 */ "wrong number of arguments\n",
  /* E_SEARCH   -8 */ "unknown search method %s\n",
  /* E_MEASURE  -9 */ "unknown evaluation measure %s\n",
  /* E_STDIN   -10 */ "double assignment of standard input\n",
  /* E_COMBI   -11 */ "illegal method/measure combination\n",
  /* E_PARSE   -12 */ "parse error(s) on file %s\n",
  /* E_UNKNOWN -13 */ "unknown error\n"
};

/*----------------------------------------------------------------------
  Global Variables
----------------------------------------------------------------------*/
const  char   *prgname = NULL;  /* program name for error messages */
static SCAN   *scan    = NULL;  /* scanner (for domain file) */
static ATTSET *attset  = NULL;  /* attribute set */
static TABLE  *table   = NULL;  /* table to induce network from */
static GRAMOD *gramod  = NULL;  /* induced graphical model */
static FILE   *out     = NULL;  /* output file */

/*----------------------------------------------------------------------
  Random Number Functions
----------------------------------------------------------------------*/
#ifdef DRAND48                  /* if library for drand48() available */
extern void   srand48 (long seed);
extern double drand48 (void);   /* use drand48 functions */
#define dseed(s) srand48((long)(s))
#define drand    drand48

#else                           /* if only standard rand() available */
#define dseed(s) srand((unsigned)(s))
static double drand (void)      /* compute value from rand() result */
{ return rand()/(RAND_MAX +1.0); }

#endif
/*----------------------------------------------------------------------
  Main Functions
----------------------------------------------------------------------*/

static void error (int code, ...)
{                               /* --- print error messages */
  va_list    args;              /* list of variable arguments */
  const char *msg;              /* error message */

  assert(prgname);              /* check the program name */
  if (code < E_UNKNOWN) code = E_UNKNOWN;
  if (code < 0) {               /* if to report an error, */
    msg = errmsgs[-code];       /* get the error message */
    if (!msg) msg = errmsgs[-E_UNKNOWN];
    fprintf(stderr, "\n%s: ", prgname);
    va_start(args, code);       /* get variable arguments */
    vfprintf(stderr, msg, args);/* print the error message */
    va_end(args);               /* end argument evaluation */
  }
  #ifndef NDEBUG
  if (table)  tab_delete(table, 0);
  if (gramod) gm_delete(gramod, 0);
  if (attset) as_delete(attset);/* clean up memory */
  if (scan)   sc_delete(scan);  /* and close files */
  if (out && (out != stdout)) fclose(out);
  #endif
  #ifdef STORAGE
  showmem("at end of program"); /* check memory usage */
  #endif
  exit(code);                   /* abort the program */
}  /* error() */

/*--------------------------------------------------------------------*/

static void help (void)
{                               /* --- print help on methods/measures */
  const MINFO *m;               /* to travserse the measure info */

  fprintf(stderr, "\n");        /* terminate the startup message */
  printf("list of search methods (option -s#)\n");
  for (m = sminfo; m->name; m++)
    printf("  %-9s  %s\n",   m->name, gm_sname(m->code));
  printf("\nlist of evaluation measures (option -e#)\n");
  printf("measures for probabilistic networks\n");
  printf("  name       measure\n");
  for (m = m_prob; m->name; m++)
    printf("  %-9s  %s%s\n", m->name, pt_mname(PT_PROB, m->code),
           (pt_minfo(PT_PROB, m->code) == PT_SYM) ? " *" : "");
  printf("\nmeasures for possibilistic networks\n");
  printf("  name       measure\n");
  for (m = m_poss; m->name; m++)
    printf("  %-9s  %s%s\n", m->name, pt_mname(PT_POSS, m->code),
           (pt_minfo(PT_POSS, m->code) == PT_SYM) ? " *" : "");
  printf("\nThe search methods owst and extst can only be used with\n"
         "symmetric evaluation measures, ");
  printf("which are marked with a *.\n");
  exit(0);                      /* abort porgram */
}  /* help() */

/*--------------------------------------------------------------------*/

static int code (const MINFO *tab, const char *name)
{                               /* --- get measure code */