frqtab.c

it is tree Dtree algorithm. so see it. it is in c++

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

static double _rdlen (FRQTAB *ftab, int measure, double *params)
{                               /* --- reduction of desc. length */
  int    x, y;                  /* loop variables */
  double **c;                   /* to traverse the table columns */
  double *fx, *fy, *fxy;        /* to traverse the frequencies */
  double lGy;                   /* buffer for log_2(Gamma(ycnt)) */
  double a;                     /* sensitivity parameter */
  double dat, mod, s, t;        /* description lengths, buffer */

  assert(ftab);                 /* check the function argument */
  if (ftab->known < EPSILON) return 0;
  lGy = logGa(ftab->ycnt);      /* note \ln\Gamma(number of classes)) */
  a   = (params || (params[0]+1 > 0)) ? params[0]+1 : 1;
  dat = mod = 0;                /* get the sensitivity parameter */
  c   = ftab->frq_xy +ftab->xcnt;

  /* --- relative frequency coding --- */
  if ((measure & 0xff) == FEM_RDLREL) {
    for (fx = ftab->frq_x +(x = ftab->xcnt); --x >= 0; --c) {
      if (*--fx <= 0) continue; /* skip empty and combined columns */
      s = 0;                    /* process a conditional distribution */
      for (fxy = *c +(y = ftab->ycnt); --y >= 0; )
        if (*--fxy > 0) s += *fxy *log(*fxy);
      dat -= *fx *log(*fx) -s;  /* compute and sum cond. entropy */
      mod -= logGa(*fx +ftab->ycnt) -logGa(*fx +1) -lGy;
    }                           /* sum conditional model terms */
    s = 0;                      /* process the row distribution */
    for (fy = ftab->frq_y +(y = ftab->ycnt); --y >= 0; )
      if (*--fy > 0) s += *fy *log(*fy);
    dat += ftab->known *log(ftab->known) -s;
    mod += logGa(ftab->known +ftab->ycnt) -logGa(ftab->known +1) -lGy;
  }                             /* compute red. of desc. lengths */

  /* --- absolute frequency coding --- */
  else {                        /* ((measure & 0xff) == FEM_RDLABS) */
    for (fx = ftab->frq_x +(x = ftab->xcnt); --x >= 0; --c) {
      if (*--fx <= 0) continue; /* skip empty and combined columns */
      s = 0;                    /* process a conditional distribution */
      for (fxy = *c +(y = ftab->ycnt); --y >= 0; )
        s += logGa(*--fxy +1);  /* compute data description length */
      dat -= (t = logGa(*fx +1)) -s;         /* and sum the result */
      mod -= logGa(*fx +ftab->ycnt) -t -lGy;
    }                           /* sum model description lengths */
    s = 0;                      /* process the row distribution */
    for (fy = ftab->frq_y +(y = ftab->ycnt); --y >= 0; )
      s += logGa(*--fy +1);     /* compute data description length */
    dat += (t = logGa(ftab->known +1)) -s;
    mod += logGa(ftab->known +ftab->ycnt) -t -lGy;
  }                             /* compute red. of desc. lengths */

  return (dat +mod/a)           /* return the weighted measure */
       / (LN_2 *((measure & FEF_WGTD) ? ftab->frq : ftab->known));
}  /* _rdlen() */

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

static double _stoco (FRQTAB *ftab, int measure, double *params)
{                               /* --- stochastic complexity */
  int    x;                     /* loop variable */
  double *fx;                   /* to traverse the frequencies */
  double stc;                   /* stochastic complexity */

  assert(ftab);                 /* check the function argument */
  if (ftab->known < EPSILON) return 0;
  stc = log(0.5 *ftab->known);  /* compute log(n../2) */
  for (fx = ftab->frq_x +(x = ftab->xcnt); --x >= 0; ) {
    if (*--fx > 0) stc -= log(0.5 * *fx);
  }                             /* compute (r_y -1)/2 *[ log(n../2) */
  stc *= 0.5 *(ftab->ycnt-1);   /*    - sum_{j=1}{r_x} log(n.j/2) ] */
  stc -= (ftab->xcnt-1) *(log(pow(M_PI, 0.5 *ftab->ycnt))
                        - logGa(0.5 *ftab->ycnt));
  stc /= LN_2 *ftab->known;     /* scale and normalize the length and */
  stc += _info(ftab, FEM_INFGAIN, NULL);  /* add the information gain */
  if (measure & FEF_WGTD) return stc *(ftab->known/ftab->frq);
  return stc;                   /* return the stochastic complexity */
}  /* _stoco() */

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

static double _spec (FRQTAB *ftab, int measure, double *params)
{                               /* --- specificity measures */
  int    x, y;                  /* loop variables */
  double **c;                   /* to traverse the table columns */
  double *fx, *fxy;             /* to traverse the frequencies */
  double *bx, *by, *bxy;        /* to traverse the buffers */
  double s_x, s_y, s_xy;        /* nonspecificities */
  double spec;                  /* specificity gain (ratio) */

  assert(ftab);                 /* check the function argument */
  if ((ftab->xcnt <= 1) || (ftab->ycnt <= 1)
  ||  (ftab->known < EPSILON)) return 0;
  for (bx = ftab->buf_x  +(x = ftab->xcnt); --x >= 0; ) *--bx = 0;
  for (by = ftab->buf_y  +(y = ftab->ycnt); --y >= 0; ) *--by = 0;
  bxy = ftab->buf_xy;           /* clear the buffers */
  c  = ftab->frq_xy+ftab->xcnt; /* traverse the joint distribution */
  bx = ftab->buf_x +ftab->xcnt; /* and the frequency buffers */
  for (fx = ftab->frq_x +(x = ftab->xcnt); --x >= 0; --c) {
    --bx;                       /* go to the next column */
    if (*--fx <= 0) continue;   /* skip empty and combined columns */
    by = ftab->buf_y +ftab->ycnt;
    for (fxy = *c +(y = ftab->ycnt); --y >= 0; ) {
      --by; --fxy;              /* traverse the rows of the column */
      if (*fxy > 0)   *bxy++ = *fxy;
      if (*fxy > *by) *by    = *fxy;
      if (*fxy > *bx) *bx    = *fxy;
    }                           /* compute the joint and marginal */
  }                             /* possibility distributions */
  s_x  = _nsp(ftab->buf_x,  ftab->xcnt);  /* compute the */
  s_y  = _nsp(ftab->buf_y,  ftab->ycnt);  /* nonspecificities */
  s_xy = _nsp(ftab->buf_xy, (int)(bxy -ftab->buf_xy));
  spec = s_x +s_y -s_xy;        /* compute the specificity gain */
  switch (measure & 0xff) {     /* evaluate the measure code */
    case FEM_SPCGBAL: spec /= log(ftab->xcnt); break;
    case FEM_SPCGR  : if (s_x      <= 0) return 0;
                      spec /= s_x;          break;
    case FEM_SPCSGR1: if (s_xy     <= 0) return 0;
                      spec /= s_xy;         break;
    case FEM_SPCSGR2: if (s_x +s_y <= 0) return 0;
                      spec /= s_x +s_y;     break;
    default:          spec /= LN_2;         break;
  }                             /* form requested nonspec. ratio */
  if (measure & FEF_WGTD) return spec *(ftab->known/ftab->frq);
  return spec;                  /* return the specificity measure */
}  /* _spec() */

/*----------------------------------------------------------------------
  Table of Evaluation Functions
----------------------------------------------------------------------*/
static EVALFN *_evalfn[] = {    /* evaluation functions */
  /* FEM_NONE      0 */ (EVALFN*)0,
  /* FEM_INFGAIN   1 */ _info,
  /* FEM_INFGBAL   2 */ _info,
  /* FEM_INFGR     3 */ _info,
  /* FEM_INFSGR1   4 */ _info,
  /* FEM_INFSGR2   5 */ _info,
  /* FEM_QIGAIN    6 */ _quad,
  /* FEM_QIGBAL    7 */ _quad,
  /* FEM_QIGR      8 */ _quad,
  /* FEM_QISGR1    9 */ _quad,
  /* FEM_QISGR2   10 */ _quad,
  /* FEM_GINI     11 */ _gini,
  /* FEM_GINISYM  12 */ _gini,
  /* FEM_GINIMOD  13 */ _gini,
  /* FEM_RELIEF   14 */ _gini,
  /* FEM_WDIFF    15 */ _wdiff,
  /* FEM_CHI2     16 */ _chi2,
  /* FEM_CHI2NRM  17 */ _chi2,
  /* FEM_WEVID    18 */ _wevid,
  /* FEM_RELEV    19 */ _relev,
  /* FEM_BDM      20 */ _bdm,
  /* FEM_BDMOD    21 */ _bdmod,
  /* FEM_RDLEN1   22 */ _rdlen,
  /* FEM_RDLEN2   23 */ _rdlen,
  /* FEM_STOCO    24 */ _stoco,
  /* FEM_SPCGAIN  25 */ _spec,
  /* FEM_SPCGBAL  26 */ _spec,
  /* FEM_SPCGR    27 */ _spec,
  /* FEM_SPCSGR1  28 */ _spec,
  /* FEM_SPCSGR2  29 */ _spec,
  /* FEM_UNKNOWN  30 */ (EVALFN*)0,
};

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

FRQTAB* ft_create (int xsize, int ysize)
{                               /* --- create a frequency table */
  int    i;                     /* loop variable, temporary buffer */
  FRQTAB *ftab;                 /* created frequency table */
  double *p;                    /* to traverse the table elements */

  if (xsize < 1) xsize = 1;     /* check and correct */
  if (ysize < 1) ysize = 1;     /* the function arguments */
  i = xsize*ysize +xsize+ysize; /* compute number of buffer elements */
  ftab = (FRQTAB*)calloc(1, sizeof(FRQTAB) +xsize *sizeof(double*));
  if (!ftab) return NULL;       /* allocate frequency table body */
  ftab->xsize = xsize++;        /* and set the number of classes and */
  ftab->ysize = ysize++;        /* the maximal number of att. values */
  ftab->dsts  = (int*)malloc(xsize *sizeof(int));
  if (!ftab->dsts) { free(ftab); return NULL; }
  ftab->dsts++;                 /* allocate destination vector */
  i += xsize*ysize+xsize+ysize; /* add number of table elements */
  p = (double*)malloc(i *sizeof(double));
  if (!p) { free(ftab->dsts-1); free(ftab); return NULL; }
  ftab->frq_x = p += 1;         /* allocate table and buffer */
  ftab->frq_y = p += xsize;     /* elements and organize them */
  for (i = xsize; --i >= 0; )
    ftab->frq_xy[i] = p += ysize;
  ftab->buf_x  = p += ysize -1;
  ftab->buf_y  = p += xsize -1;
  ftab->buf_xy = p += ysize -1;
  return ftab;                  /* return the created structure */
}  /* ft_create() */

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

void ft_delete (FRQTAB* ftab)
{                               /* --- delete a frequency table */
  assert(ftab);                 /* check the function argument */
  if (ftab->frq_x) free(ftab->frq_x -1);
  if (ftab->dsts)  free(ftab->dsts  -1);
  free(ftab);                   /* delete table entries, vectors, */
}  /* ft_delete() */            /* and the table body */

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

int ft_init (FRQTAB *ftab, int xcnt, int ycnt)
{                               /* --- initialize a frequency table */
  int    x, y;                  /* loop variables */
  double *fxy;                  /* to traverse the frequencies */
  int    *d;                    /* to traverse the destination refs. */

  assert(ftab                   /* check the function arguments */
      && (xcnt <= ftab->xsize) && (ycnt <= ftab->ysize));
  if (xcnt >= 0) ftab->xcnt = xcnt;  /* note the number of */
  if (ycnt >= 0) ftab->ycnt = ycnt;  /* columns and rows */
  for (x = ftab->xcnt +1; --x >= 0; )
    for (fxy = ftab->frq_xy[x] +(y = ftab->ycnt), ++y; --y >= 0; )
      *--fxy = 0;               /* clear the joint frequencies */
  for (d = ftab->dsts +(x = ftab->xcnt), ++x; --x >= 0; )
    *--d = -1;                  /* clear the column destination refs. */
  return 0;                     /* return 'ok' */
}  /* ft_init() */

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

void ft_copy (FRQTAB *dst, const FRQTAB *src)
{                               /* --- copy a frequency table */
  int    x, y;                  /* loop variable */