vartab.c

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

/*----------------------------------------------------------------------
  File    : vartab.c
  Contents: variation table management
  Author  : Christian Borgelt
  History : 14.09.2000 file created
            17.12.2000 first version completed
----------------------------------------------------------------------*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <assert.h>
#include "vartab.h"
#ifdef STORAGE
#include "storage.h"
#endif

/*----------------------------------------------------------------------
  Preprocessor Definitions
----------------------------------------------------------------------*/
#define EPSILON     1e-12       /* to handle roundoff errors */

/*----------------------------------------------------------------------
  Type Definitions
----------------------------------------------------------------------*/
#ifdef VT_EVAL
typedef double EVALFN (VARTAB* vtab, int measure, double *params);

/*----------------------------------------------------------------------
  Constants
----------------------------------------------------------------------*/
static const char* mnames[VEM_UNKNOWN+1] = {
  /* VEM_NONE    0 */ "no measure",
  /* VEM_SSE     1 */ "reduction of sum of squared errors",
  /* VEM_MSE     2 */ "reduction of mean squared error",
  /* VEM_RMSE    3 */ "reduction of square root of mean squared error",
  /* VEM_VAR     4 */ "reduction of variance (unbiased estimator)",
  /* VEM_SDEV    5 */ "reduction of standard deviation (from variance)",
  /* VEM_UNKNOWN 6 */ "<unknown measure>",
};                              /* names of evaluation measures */

/*----------------------------------------------------------------------
  Evaluation Functions
----------------------------------------------------------------------*/

static double _sse (VARTAB *vtab, int measure, double *params)
{                               /* --- sum of squared errors */
  int     i;                    /* loop variable */
  VARDATA *p;                   /* to traverse the variance data */
  double  red;                  /* reduction of sse */

  assert(vtab);                 /* check the function arguments */
  if (vtab->known <= 0)         /* if there are too few cases, */
    return 0;                   /* abort the function */
  red = vtab->sse;              /* get the global error sum */
  for (p = vtab->data +(i = vtab->cnt +1); --i > 0; )
    red -= (--p)->sse;          /* subtract sums of squared errors */
  if (measure & VEF_WGTD) red *= vtab->known/vtab->frq;
  return red;                   /* return the (weighted) reduction */
}  /* _sse() */

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

static double _mse (VARTAB *vtab, int measure, double *params)
{                               /* --- mean squared error */
  int     i;                    /* loop variable */
  VARDATA *p;                   /* to traverse the variance data */
  double  red = 0;              /* reduction of mse */

  assert(vtab);                 /* check the function arguments */
  if (vtab->known <= 0)         /* if there are too few cases, */
    return 0;                   /* abort the function */
  for (p = vtab->data +(i = vtab->cnt +1); --i > 0; )
    red += (--p)->sse;          /* sum the sums of the squared errors */
  red = vtab->sse /vtab->frq    /* compute the reduction */
      - red /vtab->known;       /* of the mean squared error */
  if (measure & VEF_WGTD) red *= vtab->known/vtab->frq;
  return red;                   /* return the (weighted) reduction */
}  /* _mse() */

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

static double _rmse (VARTAB *vtab, int measure, double *params)
{                               /* --- root of mean squared error */
  int     i;                    /* loop variable */
  VARDATA *p;                   /* to traverse the variance data */
  double  red = 0;              /* reduction of rmse */

  assert(vtab);                 /* check the function arguments */
  if (vtab->known <= 0)         /* if there are too few cases, */
    return 0;                   /* abort the function */
  for (p = vtab->data +(i = vtab->cnt +1); --i > 0; ) {
    --p;                        /* compute a weighted sum */
    red += sqrt(p->sse*p->frq); /* of the columns' rmses, */
  }                             /* i.e., \sum frq *\sqrt{sse/frq} */
  red = sqrt(vtab->sse /vtab->frq)
      - red /vtab->known;       /* compute the reduction */
  if (measure & VEF_WGTD) red *= vtab->known/vtab->frq;
  return red;                   /* return the (weighted) reduction */
}  /* _rmse() */

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

static double _var (VARTAB *vtab, int measure, double *params)
{                               /* --- variance */
  int     i;                    /* loop variable */
  VARDATA *p;                   /* to traverse the variance data */
  double  var, frq;             /* global variance, buffer */
  double  red = 0;              /* reduction of variance */

  assert(vtab);                 /* check the function arguments */
  if (vtab->known <= 0)         /* if there are too few cases, */
    return 0;                   /* abort the function */
  frq = vtab->frq -1;           /* compute the global variance */
  var = (frq > 0) ? vtab->sse /frq : 0;
  for (p = vtab->data +(i = vtab->cnt +1); --i > 0; ) {
    frq  = (--p)->frq -1;       /* traverse the table columns */
    red += p->frq *((frq > 0) ? p->sse /frq : var);
  }                             /* weighted sum of the variances */
  red = var -red /vtab->known;  /* reduction of variance */
  if (measure & VEF_WGTD) red *= vtab->known/vtab->frq;
  return red;                   /* return the (weighted) reduction */
}  /* _var() */

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

static double _sdev (VARTAB *vtab, int measure, double *params)
{                               /* --- standard deviation */
  int     i;                    /* loop variable */
  VARDATA *p;                   /* to traverse the variance data */
  double  sdev, frq;            /* global standard deviation, buffer */
  double  red = 0;              /* reduction of standard deviation */

  assert(vtab);                 /* check the function arguments */
  if (vtab->known <= 0)         /* if there are too few cases, */
    return 0;                   /* abort the function */
  frq  = vtab->frq -1;          /* compute the global std. deviation */
  sdev = (frq > 0) ? sqrt(vtab->sse /frq) : 0;
  for (p = vtab->data +(i = vtab->cnt +1); --i > 0; ) {
    frq  = (--p)->frq -1;       /* traverse the table columns */
    red += p->frq *((frq > 0) ? sqrt(p->sse /frq) : sdev);
  }                             /* weighted sum of the std. devs. */
  red = sdev -red /vtab->known; /* reduction of standard deviation */
  if (measure & VEF_WGTD) red *= vtab->known/vtab->frq;
  return red;                   /* return the (weighted) reduction */
}  /* _sdev() */

/*----------------------------------------------------------------------
  Table of Evaluation Functions
----------------------------------------------------------------------*/
static EVALFN *_evalfn[] = {    /* evaluation functions */
  (EVALFN*)0,                   /* VEM_NONE  0 */
  _sse,                         /* VEM_SSE   1 */
  _mse,                         /* VEM_MSE   2 */
  _rmse,                        /* VEM_RMSE  3 */
  _var,                         /* VEM_VAR   4 */
  _sdev,                        /* VEM_SDEV  5 */
};

#endif  /* #ifdef VT_EVAL */
/*----------------------------------------------------------------------
  Main Functions
----------------------------------------------------------------------*/

VARTAB* vt_create (int size)
{                               /* --- create a variance table */
  VARTAB *vtab;                 /* created variance table */

  if (size < 1) size = 1;       /* check the function argument */
  vtab = (VARTAB*)malloc(sizeof(VARTAB) +size *sizeof(VARDATA));
  if (!vtab) return NULL;       /* create a variance table and */
  vtab->size = size;            /* set its size (number of columns) */
  vtab->cnt  = 0;
  vtab->dsts = (int*)malloc((size+1) *sizeof(int));
  if (!vtab->dsts) { free(vtab); return NULL; }
  vtab->dsts++;                 /* create column destination table */
  return vtab;                  /* and return the created structure */
}  /* vt_create() */

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

void vt_delete (VARTAB *vtab)
{                               /* --- delete a variance table */
  assert(vtab);                 /* check the function argument */
  free(vtab->dsts -1);          /* delete the column dest. table */
  free(vtab);                   /* and the base structure */
}  /* vt_delete() */

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

int vt_init (VARTAB *vtab, int cnt)
{                               /* --- initialize a variance table */
  int     x;                    /* loop variable */
  VARDATA *p;                   /* to traverse the variance data */
  int     *d;                   /* to traverse the destination refs. */

  assert(vtab                   /* check the function arguments */
      && (cnt <= vtab->size));
  if (cnt >= 0) vtab->cnt = cnt;/* note the number of columns */
  for (p = vtab->data +(x = vtab->cnt +1); --x >= 0; ) {
    --p; p->frq = p->sum = p->ssv = 0; }  /* clear the statistics */
  for (d = vtab->dsts +(x = vtab->cnt), x++; --x >= 0; )
    *--d = -1;                  /* clear the column destination refs. */
  return 0;                     /* return 'ok' */
}  /* vt_init() */