ptree5.c

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

  return s;                     /* return the leaf evaluation */
}  /* _bdmod() */

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

static double _dlrel (PTREE *pt, PTLEAF *leaf1, PTLEAF *leaf2)
{                               /* --- desc. length change (rel.frq.) */
  int    i;                     /* loop variable */
  PTLVL  *lvl;                  /* leaf level description */
  float  *c1, *c2, c, n;        /* to traverse the counters */
  double s;                     /* sum of description length terms */

  assert(pt && leaf1 && leaf2   /* check the function arguments */
     && (leaf1->total > 0) && (leaf2->total > 0));
  pt->res1[0] = pt->res0[0];    /* copy the reference evaluation */
  pt->res1[1] = pt->res0[1];    /* (data and model desc. length) */
  lvl = pt->levels +pt->concnt; /* get the leaf level description */
  c1  = leaf1->cnts +(i = lvl->cnt);
  c2  = leaf2->cnts + i;        /* traverse the leaf counters and */
  for (s = 0; --i >= 0; ) {     /* sum the entropy terms for the leaf */
    c = *--c1 +*--c2; if (c > 0) s += c *log(c); }
  n = leaf1->total +leaf2->total;
  s = n *log(n) -s;             /* evaluate the merged leaf */
  pt->res1[2] = pt->res0[2] +(s -leaf1->eval -leaf2->eval);
  pt->res1[3] = pt->res0[3]     /* update the description lengths */
              + logGa(n +lvl->cnt) -logGa(n+1) +logGa(lvl->cnt)
              - logGa(leaf1->total +lvl->cnt) +logGa(leaf1->total+1)
              - logGa(leaf2->total +lvl->cnt) +logGa(leaf2->total+1);
  return s;                     /* return the leaf evaluation */
}  /* _dlrel() */

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

static double _dlabs (PTREE *pt, PTLEAF *leaf1, PTLEAF *leaf2)
{                               /* --- desc. length change (abs.frq.) */
  int    i;                     /* loop variable */
  PTLVL  *lvl;                  /* leaf level description */
  float  *c1, *c2, c, n;        /* to traverse the counters */
  double s, lG;                 /* sum of description length terms */

  assert(pt && leaf1 && leaf2   /* check the function arguments */
     && (leaf1->total > 0) && (leaf2->total > 0));
  pt->res1[0] = pt->res0[0];    /* copy the reference evaluation */
  pt->res1[1] = pt->res0[1];    /* (data and model desc. length) */
  lvl = pt->levels +pt->concnt; /* get the leaf level description */
  c1  = leaf1->cnts +(i = lvl->cnt);
  c2  = leaf2->cnts + i;        /* traverse the leaf counters and */
  for (s = 0; --i >= 0; ) {     /* compute bits for code book page */
    c = *--c1 +*--c2; s += logGa(c+1); }
  n  = leaf1->total +leaf2->total;
  lG = logGa(n+1); s = lG -s;   /* evaluate the merged leaf */
  pt->res1[2] = pt->res0[2] +(s -leaf1->eval -leaf2->eval);
  pt->res1[3] = pt->res0[3]     /* update the description lengths */
              + logGa(n +lvl->cnt) -lG +logGa(lvl->cnt)
              - logGa(leaf1->total +lvl->cnt) +logGa(leaf1->total+1)
              - logGa(leaf2->total +lvl->cnt) +logGa(leaf2->total+1);
  return s;                     /* return the leaf evaluation */
}  /* _dlabs() */

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

static double _stoco (PTREE *pt, PTLEAF *leaf1, PTLEAF *leaf2)
{                               /* --- stochastic complexity change */
  PTLVL  *lvl;                  /* leaf level description */
  float  n1, n2, n;             /* leaf counter totals */
  double s;                     /* sum of squared frequencies */

  assert(pt && leaf1 && leaf2   /* check the function arguments */
     && (leaf1->total > 0) && (leaf2->total > 0));
  s   = _info(pt,leaf1,leaf2);  /* compute the entropies */
  lvl = pt->levels +pt->concnt; /* get the leaf level description */
  n1  = leaf1->total;           /* get the leaf totals and */
  n2  = leaf2->total; n = n1+n2;/* update the penalty term */
  pt->res1[3] = pt->res0[3] +(log(0.5*n) -log(0.5*n1) -log(0.5*n2))
                            *0.5 *(lvl->cnt -1);
  pt->res1[4] = (2 -pt->leafcnt) *log(pow(M_PI, 0.5 *lvl->cnt))
              - logGa(0.5 *lvl->cnt);
  return s;                     /* return the leaf evaluation */
}  /* _stoco() */

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

static double _wdiff (PTREE *pt, PTLEAF *leaf1, PTLEAF *leaf2)
{                               /* --- weighted difference change */
  int    i;                     /* loop variable */
  PTLVL  *lvl;                  /* leaf level description */
  float  *c1, *c2, c, n, *b;    /* to traverse the counters */
  double s, t;                  /* sum of differences, buffer */

  assert(pt && leaf1 && leaf2   /* check the function arguments */
     && (leaf1->total > 0) && (leaf2->total > 0));
  lvl = pt->levels +pt->concnt; /* get the leaf level description */
  n   = leaf1->total +leaf2->total;
  c1  = leaf1->cnts +(i = lvl->cnt);
  c2  = leaf2->cnts + i;        /* traverse the leaf counters */
  b   = lvl->buf    + i;        /* and the evaluation buffer */
  for (s = 0; --i >= 0; ) {     /* compute the evaluation */
    c = *--c1 + *--c2;          /* of a merged leaf, i.e., */
    t = *--b *n - c *pt->total; /* for summed counters */
    if      (pt->params[0] == 1) s += c *fabs(t);
    else if (pt->params[0] == 2) s += c *t *t;
    else                         s += c *pow(fabs(t), pt->params[0]);
  }                             /* update the sum of differences */
  pt->res1[0] = pt->res0[0] +(s -leaf1->eval -leaf2->eval);
  pt->res1[1] = pt->leafcnt-2;  /* note the normalization factor */
  return s;                     /* return the leaf evaluation */
}  /* _wdiff() */

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

static double _chi2 (PTREE *pt, PTLEAF *leaf1, PTLEAF *leaf2)
{                               /* --- chi^2 measure change */
  int    i;                     /* loop variable */
  PTLVL  *lvl;                  /* leaf level description */
  float  *c1, *c2, n, *b;       /* to traverse the counters */
  double s, t, p;               /* sum of chi^2 terms, buffers */

  assert(pt && leaf1 && leaf2   /* check the function arguments */
     && (leaf1->total > 0) && (leaf2->total > 0));
  lvl = pt->levels +pt->concnt; /* get the leaf level description */
  n   = leaf1->total +leaf2->total;
  c1  = leaf1->cnts +(i = lvl->cnt);
  c2  = leaf2->cnts + i;        /* traverse the leaf counters */
  b   = lvl->buf    + i;        /* and the evaluation buffer */
  for (s = 0; --i >= 0; ) {     /* compute the evaluation */
    --c1; --c2; p = *--b *n;    /* of a merged leaf, i.e., */
    if (p <= 0) continue;       /* for summed counters */
    t  = p - (*c1 + *c2) *pt->total;
    s += t *t /p;               /* sum the chi^2 terms and */
  }                             /* update the chi^2 measure */
  pt->res1[0] = pt->res0[0] +(s -leaf1->eval -leaf2->eval);
  pt->res1[1] = pt->leafcnt-2;  /* note the normalization factor */
  return s;                     /* return the leaf evaluation */
}  /* _chi2() */

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

static double _evid (PTREE *pt, PTLEAF *leaf1, PTLEAF *leaf2)
{                               /* --- weight of evidence change */
  int    i;                     /* loop variable */
  PTLVL  *lvl;                  /* leaf level description */
  float  *c1, *c2, c, n, *b;    /* to traverse the counters */
  double s, x, y, z;            /* sum of evidence terms, buffers */

  assert(pt && leaf1 && leaf2   /* check the function arguments */
     && (leaf1->total > 0) && (leaf2->total > 0));
  lvl = pt->levels +pt->concnt; /* get the leaf level description */
  n   = leaf1->total +leaf2->total;
  c1  = leaf1->cnts +(i = lvl->cnt);
  c2  = leaf2->cnts + i;        /* traverse the leaf counters */
  b   = lvl->buf    + i;        /* and the evaluation buffer */
  for (s = 0; --i >= 0; ) {     /* compute the evaluation */
    c = *--c1 + *--c2;          /* of a merged leaf, i.e., */
    z = (double)c * *--b;       /* for summed counters */
    x = (double)c *pt->total -z; if (x == 0) continue;
    y = (double)*b *n        -z; if (y == 0) continue;
    s += *b *fabs(log(x/y));    /* sum the odds fractions weighted */
  }                             /* with the marginal probability */
  pt->res1[0] = pt->res0[0] +(s -leaf1->eval -leaf2->eval);
  pt->res1[1] = pt->leafcnt-2;  /* note the normalization factor */
  return s;                     /* return the leaf evaluation */
}  /* _evid() */

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

static double _relev (PTREE *pt, PTLEAF *leaf1, PTLEAF *leaf2)
{                               /* --- relevance change */
  int    i;                     /* loop variable */
  PTLVL  *lvl;                  /* leaf level description */
  float  *c1, *c2, *b;          /* to traverse the counters */
  double s, m, t;               /* sum of relevance terms, buffer */

  assert(pt && leaf1 && leaf2   /* check the function arguments */
     && (leaf1->total > 0) && (leaf2->total > 0));
  lvl = pt->levels +pt->concnt; /* get the leaf level description */
  c1  = leaf1->cnts +(i = lvl->cnt);
  c2  = leaf2->cnts + i;        /* traverse the leaf counters */
  b   = lvl->buf    + i;        /* and the evaluation buffer */
  for (s = m = 0; --i >= 0; ) { /* compute the evaluation */
    --c1; --c2;                 /* of a merged leaf, i.e., */
    if (*--b <= 0) continue;    /* for summed counters */
    t = (double)(*c1 +*c2) / *b;
    if (t <= m) { s += t; } else { s += m; m = t; }
  }                             /* update the total relevance */
  pt->res1[0] = pt->res0[0] +(s -leaf1->eval -leaf2->eval);
  pt->res1[1] = pt->leafcnt-2;  /* note the normalization factor */
  return s;                     /* return the leaf evaluation */
}  /* _relev() */

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

static double _pdiff (PTREE *pt, PTLEAF *leaf1, PTLEAF *leaf2)
{                               /* --- weighted difference change */
  int    i;                     /* loop variable */
  PTLVL  *lvl;                  /* leaf level description */
  float  *c1, *c2, c, n, *b;    /* to traverse the counters */
  double s, t;                  /* sum of differences, buffer */

  assert(pt && leaf1 && leaf2   /* check the function arguments */
     && (leaf1->total > 0) && (leaf2->total > 0));
  lvl = pt->levels +pt->concnt; /* get the leaf level description */
  n   = leaf1->total +leaf2->total;
  c1  = leaf1->cnts +(i = lvl->cnt);
  c2  = leaf2->cnts + i;        /* traverse the leaf counters */
  b   = lvl->buf    + i;        /* and the evaluation buffer */
  for (s = 0; --i >= 0; ) {     /* compute the evaluation */
    c = *--c1 + *--c2;          /* of a merged leaf */
    t = ((*--b < n) ? *b : n) - c;
    if      (pt->params[0] == 1) s += c *fabs(t);
    else if (pt->params[0] == 2) s += c *t *t;
    else                         s += c *pow(fabs(t), pt->params[0]);
  }                             /* update the sum of differences */
  pt->res1[0] = pt->res0[0] +(s -leaf1->eval -leaf2->eval);
  pt->res1[1] = pt->leafcnt-2;  /* note the normalization factor */
  return s;                     /* return the leaf evaluation */
}  /* _pdiff() */

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

static double _pchi2 (PTREE *pt, PTLEAF *leaf1, PTLEAF *leaf2)
{                               /* --- possibilistic chi^2 change */
  int    i;                     /* loop variable */
  PTLVL  *lvl;                  /* leaf level description */
  float  *c1, *c2, c, n, *b;    /* to traverse the counters */
  double s, t, p;               /* sum of chi^2 terms, buffers */

  assert(pt && leaf1 && leaf2   /* check the function arguments */
     && (leaf1->total > 0) && (leaf2->total > 0));
  lvl = pt->levels +pt->concnt; /* get the leaf level description */
  n   = leaf1->total +leaf2->total;
  c1  = leaf1->cnts +(i = lvl->cnt);
  c2  = leaf2->cnts + i;        /* traverse the leaf counters */
  b   = lvl->buf    + i;        /* and the evaluation buffer */
  for (s = 0; --i >= 0; ) {     /* compute the evaluation */
    c = *--c1 + *--c2;          /* of a merged leaf, i.e., */
    p = (*--b < n) ? *b : n;    /* for summed counters */
    if (p <= 0) continue;
    t = p -c; s += t *t /p;     /* sum the chi^2 terms and */
  }                             /* update the chi^2 measure */
  pt->res1[0] = pt->res0[0] +(s -leaf1->eval -leaf2->eval);
  pt->res1[1] = pt->leafcnt-2;  /* note the normalization factor */
  return s;                     /* return the leaf evaluation */
}  /* _pchi2() */

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

static double _mutspc (PTREE *pt, PTLEAF *leaf1, PTLEAF *leaf2)
{                               /* --- mutual specificity change */
  int    i;                     /* loop variable */
  PTLVL  *lvl;                  /* leaf level description */
  float  *c1, *c2, c, n, *b;    /* to traverse the counters */
  double s, t;                  /* sum of difference terms, buffer */

  assert(pt && leaf1 && leaf2   /* check the function arguments */
     && (leaf1->total > 0) && (leaf2->total > 0));
  lvl = pt->levels +pt->concnt; /* get the leaf level description */
  n   = leaf1->total +leaf2->total;
  c1  = leaf1->cnts +(i = lvl->cnt);
  c2  = leaf2->cnts + i;        /* traverse the leaf counters */
  b   = lvl->buf    + i;        /* and the evaluation buffer */
  for (s = 0; --i >= 0; ) {     /* compute the evaluation */
    c = *--c1 + *--c2;          /* of a merged leaf, i.e., */
    t = (*--b < n) ? *b : n;    /* for summed counters */
    if ((c > 0) && (t > 0)) s += c *log(t / c);
  }                             /* update the mutual specificity */
  pt->res1[0] = pt->res0[0] +(s -leaf1->eval -leaf2->eval);
  pt->res1[1] = pt->leafcnt-2;  /* note the normalization factor */
  return s;                     /* return the leaf evaluation */
}  /* _mutspc() */

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

static FTE fn_prob[PT_UNKNOWN+1] = {
  /* PT_NONE     0 */ { (EVALFN*)0, MRG_INDEP  },
  /* PT_INFGAIN  1 */ { _info,      MRG_INDEP  },