condep.c

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

/*----------------------------------------------------------------------
  File    : condep.c
  contents: measure strength of (conditional) dependences
  Author  : Christian Borgelt
  History : 25.03.1997 file created (as file cind.c)
            02.02.1998 option -u (unknown values characters) added
            23.06.1998 adapted to modified attset functions
            18.04.1999 simplified using the new module 'io'
            30.04.1999 use of temporary file removed
            08.01.2002 generalized to different evaluation measures
            12.01.2002 made independent of module ascons
            22.01.2002 option -w (weight distribution) added
            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 <assert.h>
#include <math.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"
#include "ptree.h"
#ifdef STORAGE
#include "storage.h"
#endif

/*----------------------------------------------------------------------
  Preprocessor Definitions
----------------------------------------------------------------------*/
#define PRGNAME     "condep"
#define DESCRIPTION "measure strength of (conditional) dependences"
#define VERSION     "version 1.9 (2004.08.12)         " \
                    "(c) 1997-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_STDIN     (-8)        /* double assignment of stdin */
#define E_PARSE     (-9)        /* parse error */
#define E_MEASURE  (-10)        /* unknown evaluation measure */
#define E_ATTCNT   (-11)        /* too few attributes */
#define E_UNKNOWN  (-12)        /* unknown error */

/*----------------------------------------------------------------------
  Constants
----------------------------------------------------------------------*/
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_STDIN    -8 */  "double assignment of standard input\n",
  /* E_PARSE    -9 */  "parse error(s) on file %s\n",
  /* E_MEASURE -10 */  "unknown evaluation measure %s\n",
  /* E_ATTCNT  -11 */  "too few attributes (need at least 2)\n",
  /* E_UNKNOWN -12 */  "unknown error\n"
};

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

/*----------------------------------------------------------------------
  Constants
----------------------------------------------------------------------*/
static const MINFO mi_prob[] = {/* --- probabilistic measures */
  { PT_INFGAIN, "infgain" },    /* information gain */
  { PT_INFSGR1, "infsgr1" },    /* sym. information gain ratio 1 */
  { PT_INFSGR2, "infsgr2" },    /* sym. information gain ratio 2 */
  { PT_QIGAIN,  "qigain"  },    /* quadratic information gain */
  { PT_QISGR1,  "qisgr1"  },    /* sym. quad. info. gain ratio 1 */
  { PT_QISGR2,  "qisgr2"  },    /* sym. quad. info. gain ratio 2 */
  { PT_GINISYM, "ginisym" },    /* symmetric Gini index */
  { PT_WDIFF,   "wdiff"   },    /* sum of weighted differences */
  { PT_CHI2,    "chi2"    },    /* chi^2 measure */
  { PT_CHI2NRM, "chi2nrm" },    /* normalized chi^2 measure */
  { -1,          NULL     }     /* sentinel */
};

static const MINFO mi_poss[] = {/* --- possibilistic measures */
  { PT_SPCGAIN, "spcgain" },    /* specificity gain */
  { 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 */
};

/*----------------------------------------------------------------------
  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 */
static PTREE  **ptrees = NULL;  /* prob./poss. trees for testing */
static int    ptcnt    = 0;     /* number of probability trees */
static int    *ids     = NULL;  /* vector of attribute identifiers */
static FILE   *out     = NULL;  /* output file */

/*----------------------------------------------------------------------
  Auxiliary Functions
----------------------------------------------------------------------*/
#ifndef NDEBUG

static void del_ptrees (void)
{                               /* --- delete prob./poss. trees */
  if (!ptrees) return;          /* if there are no trees, abort */
  while (--ptcnt > 0)           /* delete all prob./poss. trees */
    if (ptrees[ptcnt]) pt_delete(ptrees[ptcnt], 0);
  free(ptrees);                 /* delete the tree vector */
}  /* del_ptrees() */

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

static void error (int code, ...)
{                               /* --- print error message */
  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 (ptrees) del_ptrees();     /* clean up memory */
  if (ids)    free(ids);        /* and close files */
  if (table)  tab_delete(table, 0);
  if (attset) as_delete(attset);
  if (scan)   sc_delete(scan);
  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 eval. measures */
  int i;                        /* loop variable */

  fprintf(stderr, "\n");        /* terminate the startup message */
  printf("\nlist of evaluation measures (option -e#)\n");
  printf("measures for probabilistic mode\n");
  printf("  name       measure\n");
  for (i = 0; i < (int)(sizeof(mi_prob)/sizeof(MINFO)-1); i++)
    printf("  %-9s  %s\n", mi_prob[i].name,
           pt_mname(PT_PROB, mi_prob[i].code));
  printf("\nmeasures for possibilistic mode\n");
  printf("  name       measure\n");
  for (i = 0; i < (int)(sizeof(mi_poss)/sizeof(MINFO)-1); i++)
    printf("  %-9s  %s\n", mi_poss[i].name,
           pt_mname(PT_POSS, mi_poss[i].code));
  exit(0);                      /* abort porgram */
}  /* help() */

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

static int code (const MINFO *tab, const char *name)
{                               /* --- get measure code */
  for ( ; tab->name; tab++)     /* look up name in table */
    if (strcmp(tab->name, name) == 0)
      return tab->code;         /* return the measure code */
  return -1;                    /* or an error indicator */
}  /* code() */

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

static int next_test (int cnt, int cur, int max, int *ids)
{                               /* --- generate next dependence test */
  int i, k;                     /* loop variable, buffer */
  int *p;                       /* to traverse the identifiers */

  assert(ids                    /* check the function arguments */
     && (cnt >= 2) && (cur >= -1) && (cur <= max) && (max <= cnt-2));
  if (cur < 0) {                /* if not initialized, set first ids. */
    ids[0] = 0; ids[1] = 1; return 0; }
  for (k = cnt, p = ids+2 +(i = cur); --i >= 0; ) {
    (*--p)++;                   /* increase the condition identifier */
    if (*p  == ids[0]) (*p)++;  /* and make sure that it differs */
    if (*p  == ids[1]) (*p)++;  /* from the first two identifiers */
    if (--k == ids[1]) k--;     /* compute the upper bound */
    if (  k == ids[0]) k--;     /* for the current condition */
    if (*p <= k)                /* if the increased condition */
      break;                    /* does not exceed its upper bound, */
  }                             /* abort the loop */
  if (i < 0) {                  /* if no condition could be increased */
    if (++ids[1] >= cnt) {      /* try to increase the 2nd identifier */
      if (++ids[0] >= cnt-1) {  /* and on failure  the 1st identifier */
        if (++cur > max)        /* if the max. number of conditions */
          return -1;            /* is reached, abort the function, */